# 2024q1 Homework2 (quiz1+2)
contributed by < [p96114175](https://github.com/p96114175) >
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
# quiz2(第二週)
## test 2
以下程式為 LRU Cache 的實現
實現 LRU Cache 所需的資料結構，如下
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
`capacity` 表示該 cache 最大的容量
`count` 表示目前該 cache 的容量
```c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
**lRUCacheCreate**
1. 採用 `lRUCacheCreate` 來為 Cache 分配記憶體以及相關參數初始化。
2. 應用 `cache->capacity = capacity` 來告訴 cache 的最大容量為多少。`cache->count = 0` 表示該 Cache 目前為空。
3. `INIT_LIST_HEAD(&cache->dhead)` 建立了一個雙向鏈結串列，`其中next` 和 `prev` 指標指向自身。
4. 接下來根據 capacity 的大小，遍尋 hhead[] 逐個初始化 hlist_head 以利之後可以執行插入和刪除操作。
```
LRUCache *lRUCacheCreate(int capacity)
{
LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
capacity * sizeof(struct list_head));
cache->capacity = capacity;
cache->count = 0;
INIT_LIST_HEAD(&cache->dhead);
for (int i = 0; i < capacity; i++)
INIT_HLIST_HEAD(&cache->hhead[i]);
return cache;
}
```
**lRUCacheFree**
應用 list_for_each_safe 走訪每一個 LRUNode，並將其相關的記憶體釋放。當釋放完全部的 LRUNode 後，將 LRUCache 的記憶體也釋放。
```
void lRUCacheFree(LRUCache *obj)
{
struct list_head *pos, *n;
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, FFFF);
list_del(GGGG);
free(cache);
}
free(obj);
}
```
**lRUCacheGet**
1. 透過 `key % obj->capacity` 求出 hash 值。
2. 接著應用 `hlist_for_each (pos, &obj->hhead[hash])` 來走訪 hhead[hash] 的 pos，再對 pos 應用 list_entry 巨集找出 LRUNode。
3. 比對該 LRUNode 的 key 值是否等於我們所尋找的 key 值。如果找到了，便會將該 LRUNode 搬移至 `&obj->dhead` 的下一個節點。從中可以知道 dhead 維護著 LRUNode 的更新順序，離 dhead 越遠的 LRUNode 意味著，越久沒有被訪問。
```c
int lRUCacheGet(LRUCache *obj, int key)
{
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *cache = list_entry(pos, LRUNode, HHHH);
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
return -1;
}
```
**lRUCachePut**
在對 Cache 執行 Put 操作前，會先對 hhead 中每一個 LRUNode 走訪，確認是否有該 key 值存在於 hhead 中。如果有找到便直接返回該 cache 值。
``` c
void lRUCachePut(LRUCache *obj, int key, int value)
{
LRUNode *cache = NULL;
int hash = key % obj->capacity;
struct hlist_node *pos;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *c = list_entry(pos, LRUNode, JJJJ);
if (c->key == key) {
list_move(KKKK, &obj->dhead);
cache = c;
}
}
...
cache->value = value;
}
```
假設在 hhead 中 key 值不存在，該 cache 為 NULL，便會通過 ` if (!cache)`接下來存在兩種情況。
情況一，Cache 的 capacity ==滿了==。接著便會找到離 dhead 最遠的 LRUNode(表示最少被使用到) 搬移至 dhead 旁，使其成為 dhead 的下一個節點，然後讓 `&obj->hhead[hash]` 取代 LRUNode(表示最少被使用到)，表示為最近被訪問到的 LRUNode。
```c
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
```
情況二，Cache 的 capacity ==沒有滿==。將目前要加入的 cache 新增至 `&obj->hhead[hash]` 中，並將位置移動到 dhead 的下一個節點，表示為最近被訪問到的 LRUNode。同時將當前 count 加一。
```c
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
```
## test 3
這一個則是在找出 word 中的第一個 bit。我們可以觀察到該程式並非採取逐個 bit 取確認，然後跑完 64*O(1)，這樣沒效率的方式。而是在每一次判斷中，採用 binary search 的邏輯，每一次會確認 word 的一半，然後將確認完的部分做 shift right，方便下一個 if 判斷式的執行。這個程式每次執行皆為固定時間。
假設輸入為 $00000000000000001000000000001000$
1.`if ((word & 0xffffffff) == 0)`，==00000000000000001000000000001000==，num=0
2.`if ((word & 0xffff) == 0)`，0000000000000000==1000000000001000==，num=0
3.`if ((word & 0xff) == 0)`，000000000000000010000000==00001000==，num=0
4.`if ((word & 0xf) == 0)`，0000000000000000100000000000==1000==，num=0
5.`if ((word & 0x3) == 0)`，000000000000000010000000000010==00==，num=2
6.`if ((word & 0x1) == 0)`，00000000000000001000000000001==0==00，num=3
```c
/* find first bit in word.
* @word: The word to search
*
* Undefined if no bit exists, so code should check against 0 first.
*/
static inline unsigned long __ffs(unsigned long word)
{
int num = 0;
#if BITS_PER_LONG == 64
if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
#endif
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
if ((word & 0x1) == 0)
num += 1;
return num;
}
```
1. 透過將 nr 輸入至 BIT_MASK 找出我們需要的 mask(裡面記錄著哪些 bit 要進行 clean)。
2. addr 則透過 BIT_WORD 來找出 `*p &= BBBB` 所需的運算元。
3. 在 *p &= ~mask 時，對 mask 取反，然後對著 p 中做 AND operation，這樣就可以對特定位置的 bit 做 clean 了。打個比方，假設 maks 為 0001，在 ~mask 後 就可以得到 1110，你可以觀察到 ~mask 中 0 bit 所在的位置，便是準備將 bit 進行 clean 的地方，如果你的 *p 為 1111 ，那麼在進行 clean 操作後，*p 應為 1110。
```c
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
```
```c
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
```
```c=
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= ~mask;
}
```
fns 該程式主要是在找 word 中第 n 個 set bit。這裡我舉個例子做說明，假設你 word 如下
```c
void main()
{
unsigned long word = 0b00000000000000001000001000001000;
printf("%ld", fns(word, 0));
}
```
那麼你可以得到以下輸出結果為 3 ，這個 3 表示LSB set 設為 1 的 index，這部分可以參考 [Find first set wiki](https://en.wikipedia.org/wiki/Find_first_set) 的說明
> find first set (ffs) or find first one is a bit operation that, given an unsigned machine word,[nb 1] designates the index or position of the least significant bit set to one in the word counting from the least significant bit position.
後續我將 n 設為 1 和 2 及 3 ，依序可以得到 9, 15, 64
從程式碼觀察你可以發現一件事，假設你的 word 為 $0b00000000000000001000001000001000$，n = 1，在 while loop 第一次的時候，bit 為 3，然後將 n 減一，接著對該 bit 執行 `__clear_bit(bit, &word)` 進行 clean。在 while loop 第二次的時候，bit 為 9 而不是 3，這是因為 3 已經被 clean out，此時 n=0，判斷成立，接著 return bit。
:::info
該程式我認為存在一個耗時問題，當你為你的 n 指定值時，勢必要跑過 n+1 次 __ffs function，但我還在思考有什麼方法可以直接做到跟 fns 一樣的效果。
:::
```c=
/* find N'th set bit in a word
* @word: The word to search
* @n: Bit to find
*/
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
Sign in with Wallet
Connect another wallet