---
tags: linux2022
---

# 2022q1 Homework1 (quiz1)
contributed by < `bebo1010` >

## AAA

(a) /* no operation */
(b) n->pprev = first
(c) n->next = first
(d) n->pprev = n

首先我注意到一件事情，(b)和(d)是不可選的選項
pprev 是指標的指標，而 first 和 n 的型態是指標
因此填入(b)和(d)會發生編譯器報錯的問題

接下來我檢查了程式碼，了解缺失的部分就是把新增的 n 放入 list 的步驟
因此`AAA`和`BBB`必定填入`n->next`以及`n->pprev`相關的 code
由於已經有兩個選項遭到刪去，剩下的`n->next = first`就是唯一解
## BBB

(a) n->pprev = &h->first
(b) n->next = h
(c) n->next = n
(d) n->next = h->first
(e) n->next = &h->first

接續AAA的作答思路，AAA已經填入`n->next = first`後
BBB應該要填入`n->pprev`有相關的 code
因此直接選(a)回答
## trace code 時注意到的東西
當下在讀這份程式碼時，我注意到了 hash 的方式，這種 hash 的方式我從來沒有看過的

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

`quiz1`這份 code 的 hash 形式是把輸入的值乘上`GOLDEN_RATIO_32`後再向右位移 $32-x$ 個 bits
之後我也去大致翻了一下 linux 的 hash 作法 [link](https://elixir.bootlin.com/linux/v4.7/source/fs/btrfs/btrfs_inode.h#L222)

static inline unsigned long btrfs_inode_hash(u64 objectid,
					     const struct btrfs_root *root)
{
	u64 h = objectid ^ (root->objectid * GOLDEN_RATIO_PRIME);

#if BITS_PER_LONG == 32
	h = (h >> 32) ^ (h & 0xffffffff);
#endif

	return (unsigned long)h;
}

這個 hash 做法又跟`quiz1`內提到的不太相同，但是我也說不上這是什麼寫法
我自己在上學期作業系統的作業內寫過一種 hash

struct dummy * db_hash(char *key)
{
    //my hash function, just mod a prime number
    int hash_value = 0;
    if(key[1] == '\0' && key[0] == '\0')
        hash_value = 0;
    if(key[1] != '\0' && key[0] == '\0')
        hash_value = (int) key[1];
    if(key[1] == '\0' && key[0] != '\0')
        hash_value = (int) key[0];
    if(key[1] != '\0' && key[0] != '\0')
        hash_value = (int) (key[0] * key[1]);
    hash_value = hash_value % DB_LENGTH; //DB_LENGTH = 251

    return &db[hash_value];
}

這做法是把輸入(預設輸入都是字串)的前兩個字元做`ASCII code`的對應數值相乘後再對預先設定好的 hash table 長度(預先取一個質數)做模除運算
或許我的做法有點冗餘，但我認為整體來說和 linux 的做法可以互相比較一下
可是我不太確定這兩種做法間有什麼實質上的差別(扣除我的 code 寫得太過冗長以外)
或許教授和助教在改這份時可以給我點意見