---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)

contributed by < `SmallHanley` >

> [linux2022-quiz1](https://hackmd.io/@sysprog/linux2022-quiz1)

## 測驗 `1`

:::success
解釋上述程式碼運作原理
:::

首先是資料結構的部分：

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

`struct hlist_node` 這個結構體包含指標 `next` ，用來指向下一個節點，以及指標的指標 `prev`，指向前一個節點的 `next` 指標，可以在接到 `hlist_head` 時不用額外判斷，避免分支。

:::warning
這裡不懂開發者選擇使用雙向鏈結串列的考量，查看 history 最早出現 `hash_node` 是在 [v2.5.64](https://elixir.bootlin.com/linux/v2.5.64/A/ident/hlist_node)，github commit history 沒有這麼舊的資料，[ChangeLog-2.5.64](https://cdn.kernel.org/pub/linux/kernel/v2.5/ChangeLog-2.5.64) 也沒有查到有用的資訊。
:::

`struct hlist_head` 結構體則是 hash table 各個 bucket 的 head，其中 `first` 指標指向第一個 `struct hlist_node` 節點。

而 `map_t` 是 hash table，`bits` 代表 bucket 的多寡 (以多少位元表示)，因此 bucket 的數量為 2 的冪。`ht` 則是一個陣列，用來存放每個 bucket 的 head。

`struct hash_key` 結構體是用來包裝每個 key-value pair，key 會根據 hash function 找到對應的 bucket，該 bucket 的 `struct hlist_head` 會串接所有映射到這個 bucket 的 `struct hlist_node`，示意圖如下：

digraph G {

    rankdir=LR;

    node[shape=record];
    map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
    
    node[shape=none]
    null1 [label=NULL]
    null2 [label=NULL]

    subgraph cluster_1 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key 1"
    }
    
    subgraph cluster_2 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key 2"
    }
    
    subgraph cluster_3 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="hash_key 3"
    }
    
    map:ht1 -> hn1
    hn1:next -> hn2
    hn2:next -> null1
    hn2:prev:s -> hn1:next:s
    map:ht5 -> hn3
    hn3:next -> null2
    
    hn1:prev:s -> map:ht1
    hn3:prev:s -> map:ht5
}

* **map_init()**
根據傳進來的 `bits` 來決定 hash table 的大小，`bits` 代表 bucket 的多寡 (以多少位元表示)，因此 hash table 的 size 為 2 的冪。配置 `map_t` 以及 `map->ht` 的空間，並將所有 entry 的 `first` 指標指向 `NULL`。
* **hash()**
即 hash function 的所在，這裡使用 magic number `0x61C88647`，看後續分析 linux kernel 相關實作會不會探討，這裡先跳過。
* **find_key()**
首先根據 key 的值，透過 hash function 映射到 hash table 的其中一個 bucket，並用 for 迴圈走訪每一個 `struct hlist_node` 結構體，如果該結構體的 `key` 是我們要找的，則回傳該結構體，若找不到則回傳 `NULL`。
* **map_get()**
先呼叫 `find_key()` 取得目標結構體，並回傳其 `data`。
* **map_add()**
插入新的 key-data pair 到 hash table，如果該 key 已經存在，則不做任何事情。
* **map_deinit()**
釋放 hash table 相關的資源。

:::success
研讀 Linux 核心原始程式碼 [include/linux/hashtable.h](https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h) 及對應的文件 [How does the kernel implements Hashtables?](https://kernelnewbies.org/FAQ/Hashtables)，解釋 hash table 的設計和實作手法，並留意到 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 的 `GOLDEN_RATIO_PRIME`，探討其實作考量
:::

光是 hash table 的 define 就有分三種：

#define DEFINE_HASHTABLE(name, bits)						\
	struct hlist_head name[1 << (bits)] =					\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DEFINE_READ_MOSTLY_HASHTABLE(name, bits)				\
	struct hlist_head name[1 << (bits)] __read_mostly =			\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DECLARE_HASHTABLE(name, bits)                                   	\
	struct hlist_head name[1 << (bits)]

中間多了 `__read_mostly`，追蹤相關程式碼，發現 `__read_mostly` 的定義是被分散在不同處理器架構的 cache.h (arch/xxx/include/asm/cache.h)，其中，有部分架構定義如下，包含 `arm`、`arm64`、`ia64`、`mips`、`parisc`、`powerpc`、`s390`、`sh`、`sparc`、`x86`：

#define __read_mostly __section(".data..read_mostly")

其中 `__section` 又被定義在 [include/linux/compiler_attributes.h](https://elixir.bootlin.com/linux/latest/source/include/linux/compiler_attributes.h#L276) 中，在 [GNU C and C++](https://gcc.gnu.org/) 中，可以用來描述函式的特定性質 (參見 [Declaring Attributes of Functions](https://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html))。而這裡使用到的是 `section` 這個 attribute (參見 [Function-Attributes-section](https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Function-Attributes.html))，概念上是將一段程式放置在指定的 special section，推測跟 cache 的相關優化有關。

### hashtable.h

Linux hashtable.h 有 include `linux/rculist.h`，可以參考 linux Documentation [rcu.rst](https://github.com/torvalds/linux/blob/master/Documentation/RCU/rcu.rst)、[listRCU.rst](https://github.com/torvalds/linux/blob/master/Documentation/RCU/listRCU.rst)。

**重點整理：**
* RCU (read-copy update) 的概念是將 destructive operation 分成兩個部分，第一是將要 destroy 的資料隱藏不讓其他 reader 看到，第二是實際執行 destruction 的動作。而兩個部分中間有一段時間稱作 "grace period"，grace period 需要足夠長使得所有 reader drop the reference。
* RCU 在鏈結串列的操作之一，流程上是將節點從鏈結串列中移除，等待 grace period，然後釋放對應空間。
* 使用情境：==待補充==
* Read-mostly list: Deferred Destruction
* Read-Side Action Taken Outside of Lock: No In-Place Updates
* Handling In-Place Updates
* Eliminating Stale Data
* Skipping Stale Objects

#### hash_init()

* 將 hash table 初始化。
* 從上面示意圖可以知道 hash table 是一個 `struct hlist_head` 組成的陣列，每個 `struct hlist_head` 是映射到同一個 bucket 的鏈結串列的 head。將每個結構體的成員 `first` 初始化成 `NULL`。

// linux/list.h
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

// linux/hashtable.h
static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
	unsigned int i;

	for (i = 0; i < sz; i++)
		INIT_HLIST_HEAD(&ht[i]);
}

#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))

#### hash_add()

// linux/hashtable.h
#define hash_add(hashtable, node, key)						\
	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

// linux/list.h
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	WRITE_ONCE(n->next, first);
	if (first)
		WRITE_ONCE(first->pprev, &n->next);
	WRITE_ONCE(h->first, n);
	WRITE_ONCE(n->pprev, &h->first);
}

[commit c54a274](https://github.com/torvalds/linux/commit/c54a2744497db4b6887b9c905ef7aa0b3620c956)

> Also add various WRITE_ONCE() in __hlist_del(), hlist_add_head()
and hlist_add_before()/hlist_add_behind() to pair with
the READ_ONCE().

## hash.h

在 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 可以發現一個巨集 `GOLDEN_RATIO_PRIME`，

/*
 * Knuth recommends primes in approximately golden ratio to the maximum
 * integer representable by a machine word for multiplicative hashing.
 * Chuck Lever verified the effectiveness of this technique:
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 *
 * These primes are chosen to be bit-sparse, that is operations on
 * them can use shifts and additions instead of multiplications for
 * machines where multiplications are slow.
 */
#if BITS_PER_LONG == 32
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e370001UL
#elif BITS_PER_LONG == 64
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
#else
#error Define GOLDEN_RATIO_PRIME for your wordsize.
#endif

在 [commit 689de1d](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/include/linux/hash.h?id=689de1d6ca95b3b5bd8ee446863bf81a4883ea25) 後改成以下實作版本：

/*
 * This hash multiplies the input by a large odd number and takes the
 * high bits.  Since multiplication propagates changes to the most
 * significant end only, it is essential that the high bits of the
 * product be used for the hash value.
 *
 * Chuck Lever verified the effectiveness of this technique:
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 *
 * Although a random odd number will do, it turns out that the golden
 * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
 * properties.  (See Knuth vol 3, section 6.4, exercise 9.)
 *
 * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
 * which is very slightly easier to multiply by and makes no
 * difference to the hash distribution.
 */
#define GOLDEN_RATIO_32 0x61C88647
#define GOLDEN_RATIO_64 0x61C8864680B583EBull

其中有討論到有關 `GOLDEN_RATIO_PRIME` 的實作考量，出自於 The Art of Computer Programming (Knuth vol 3, section 6.4, exercise 9) 這本書，以下取自這本書的片段。

**Theorem S.** Let $\theta$ be any irrational number. When the points {$\theta$}, {$2\theta$}, ..., {$n\theta$} are placed in the line segment [0 ... 1], then $n + 1$ line segments formed have at most three different lengths. Moreover, the next point {$(n + 1)\theta$} will fall in one of the largest existing segments.
(用 Three-gap theorem 推導。)

:::info
{$n \theta$} 代表 $n \theta$ 的小數部分。
:::
之所以要取小數部分，原理是這個分割問題可以 model 成 [Three-gap theorem](https://en.wikipedia.org/wiki/Three-gap_theorem)。line segment [0 … 1] 對應到 Three-gap theorem 中周長為 1 的圓，$n \theta$ 的整數部分相當於繞了圓多少圈 (即在 line segment 循環多少次)，而小數部分相當於新的點坐落於圓上的哪一個位置 (即 line segment 中新分割點的位置)。

有關 **Theorem S** 的證明在 exercise 8



任意數乘上這兩個數再取其高位元，可呈現好的數值分布。實際的 hash function (舉 32-bit 為例) 是定義在 [tools/include/linux/hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h#L57-L69)：

#ifndef HAVE_ARCH__HASH_32
#define __hash_32 __hash_32_generic
#endif
static inline u32 __hash_32_generic(u32 val)
{
	return val * GOLDEN_RATIO_32;
}

static inline u32 hash_32(u32 val, unsigned int bits)
{
	/* High bits are more random, so use them. */
	return __hash_32(val) >> (32 - bits);
}

上述的實作是將 0 ~ 1 的浮點數以 32-bit 無號整數表示。第 6 行將欲進行 hash 的數值 `val` 乘上 `GOLDEN_RATIO_32` ，第 12 行是取最高的 `bits` 個位元。對應上述 Fibonacci Hashing 理論，`val` 對應到 $n$，`GOLDEN_RATIO_32` 為 $\phi^{-1}$ 以 32-bit 無號整數表示，兩者相乘，因為會產生溢位 (一次溢位相當於 Three-gap theorem 中繞了圓一圈)，相乘的結果為 {$n \phi^{-1}$} 以 32-bit 無號整數表示，取其高位元，則相當於取小數前幾位數。

## 實驗

實際對比新、舊版本的 `GOLDEN_RATIO_PRIME` 實作，新版的實作可以讓 hash function 結果的分佈更為均勻。以下分別測試 0 到 1000、10000 映射到 hash table 不同 locations 的次數，hash table 的大小為 1024 (10 bits)：



## Reference
[並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
[6.46 When is a Volatile Object Accessed?](https://gcc.gnu.org/onlinedocs/gcc/Volatiles.html)
[Documentation/memory-barriers](https://www.kernel.org/doc/Documentation/memory-barriers.txt)
[Golden_ratio](https://en.wikipedia.org/wiki/Golden_ratio)
[Fibonacci_number#Relation_to_the_golden_ratio](https://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio)