---
tags: linux2024
---
# 2024q1 Homework2 (quiz1+2)
contributed by <[Howard Chen](https://github.com/howardjchen/linux2024-hw2)>

## 第一周測驗
### 測驗 1:

This function was used to calcaute the length of the list by traversing from head to the end whcih is NULL.

@@ -61,7 +61,7 @@ int list_length(node_t **left)
     int n = 0;
     while (*left) {
         ++n;
-        left = &(BBBB);
+        left = &((*left)->next);
     }
     return n;
 }

This function was implemented to return the last node of the list. Since this is a singly linked list, the last node was linked with NULL. We have to traverse until the end to get the last node.

@@ -52,7 +52,7 @@
 node_t *list_tail(node_t **left)
 {
     while ((*left) && (*left)->next)
-        left = &(AAAA);
+        left = &((*left)->next);
     return *left;
 }

This part of the code is responsible for partitioning the sublist into two smaller sublists (```left``` and ```right```). It iterates through each node in the sublist ```p``` and adds it to either the ```left``` or ```right``` sublist based on its value compared to the pivot value. This partitioning step divide the list into smaller parts for sorting.

 @@ -107,16 +112,16 @@ void quick_sort(node_t **list)

             while (p) {
                 node_t *n = p;
-                p = CCCC;
+                p = p->next;
                 list_add(n->value > value ? &right : &left, n);
             }

In below code segment, after partitioning the sublist into ```left```, ```pivot```, and ```right``` sublists, the pointers begin and end are updated to reflect the boundaries of these sublists. Additionally, the pointers ```left``` and ```right``` are reset to NULL, and the loop counter i is incremented by 2 to move to the next level of sublists.
- `begin[i] = left` and `end[i] = list_tail(&left)`: Set the beginning and ending nodes of the left sublist.
- `begin[i + 1] = pivot` and `end[i + 1] = pivot`: Set the beginning and ending nodes of the pivot sublist (which is essentially just the pivot node).
- `begin[i + 2] = right` and `end[i + 2] = list_tail(&right)`: Set the beginning and ending nodes of the right sublist.
- `left = right = NULL`: Reset the left and right pointers to NULL to prepare for the next iteration.

             begin[i] = left;
-            end[i] = DDDD;
+            end[i] = list_tail(&left);;
             begin[i + 1] = pivot;
             end[i + 1] = pivot;
             begin[i + 2] = right;
-            end[i + 2] = EEEE;
+            end[i + 2] = list_tail(&right);;

### 測驗 2:

### Timsort 程式運作原理：

The main spriti of timsort is that it divides the data into smaller chunks called "runs" and then uses a combination of insertion sort and merge sort to sort these runs efficiently.

### About weekly test
During the weekly test, Google sheet deteremined my answer for BBBB and CCCC were incorrect. However, the real answers of `&a->next` and `&b->next` meaning the same expression as what I filled as below. They're all aim to assign the address of `a->next` and `b->next` to `tail` since `tail` is a pointer that pointed to the address of head.

         if (cmp(priv, a, b) <= 0) {
             *tail = a;
-            tail = BBBB;
+            tail = &(a->next);
             a = a->next;
             if (!a) {
                 *tail = b;

@@ -130,7 +130,7 @@ static struct list_head *merge(void *priv,
             }
         } else {
             *tail = b;
-            tail = CCCC;
+            tail = &(b->next);
             b = b->next;
             if (!b) {
                 *tail = a;

### Merge timsort to lab0-c
In the original timsort code, the `cmp` funtion was comparing integer number. However, we need to modified to compare `char*` in order to used timsort in lab0-c
**[Commit: Add support to return queue size](https://github.com/sysprog21/lab0-c/commit/e0742e8eae25616ca7aaf2cf96b35dd05db28169)**
**[Commit: Complete basic functions for make test pass](https://github.com/sysprog21/lab0-c/commit/e08f65f40b7dde07af70f087023df6d994907a51)**

-    int res = list_entry(b, element_t, list)->value -
-              list_entry(a, element_t, list)->value;
+    int res = strcmp(list_entry(a, element_t, list)->value,
+                     list_entry(b, element_t, list)->value);

### Comparing timsort and q_sort performance
We use `perf` command to help analysis the performance and cache-miss of q_sort and timsort. In order to use the same data, we copy `trace-15-perf.cmd` and modified the `sort` command to `timsort`

sudo perf stat -r 100 -e cache-misses,cache-references,instructions,cycles ./qtest -f ./traces/trace-tim15.cmd

We could find that by using timsort, we could have less cache miss and better performance. The outcome confirms that Timsort exhibits a characteristic advantageous for memory locality.

Because Timsort divides the input data into small blocks called "runs." These runs represent contiguous subsequences of the input data that are already partially sorted. By sorting small chunks of data at a time, Timsort improves memory locality because it increases the likelihood that the elements being accessed during sorting are stored close together in memory.

#### `q_sort`

 Performance counter stats for './qtest -f ./traces/trace-15-perf.cmd' (100 runs):

           1870609      cache-misses              #    4.760 % of all cache refs      ( +-  1.42% )
          39672133      cache-references                                              ( +-  0.23% )
         772755378      instructions              #    0.97  insn per cycle           ( +-  0.00% )
         795976486      cycles                                                        ( +-  0.14% )

          0.170038 +- 0.000270 seconds time elapsed  ( +-  0.16% )

#### `timsort`

 Performance counter stats for './qtest -f ./traces/trace-tim15.cmd' (100 runs):

           1563182      cache-misses              #    4.017 % of all cache refs      ( +-  1.78% )
          39160639      cache-references                                              ( +-  0.24% )
         772729482      instructions              #    0.99  insn per cycle           ( +-  0.00% )
         772852364      cycles                                                        ( +-  0.16% )

          0.167184 +- 0.000283 seconds time elapsed  ( +-  0.17% )

## 第二周測驗
### 測驗 1
#### 透過前序與中序建構樹程式運作原理

1. hlist_node: This structure represents a node in a hash list.
- `next`: Points to the next node in the hash list.
- `pprev`: Points to the pointer that points to this node. In other words, it points to the previous node's `next`, which allows efficient removal of nodes from the list without traversing the list from the beginning.

2. `hlist_head`: This structure represents the head of a hash list.

- `first`: Points to the first node in the hash table.

3. `order_node`: This structure represents a node containing ordered information.

- `node`: An instance of the `hlist_node` structure, allowing it to be part of a hash list.
- `val`: Holds the value of the node.
- `idx`: Holds the index of the node.

struct hlist_node {
    struct hlist_node *next, **pprev;
};

struct hlist_head {
    struct hlist_node *first;
};

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};


The `hlist_add_head` function is used to add a node to the head of a hash list.

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

+ n->next = h->first;
- n->next = AAAA;

The `find` funtion is used to find the index of root from indorer list

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &head[hash]) {
        struct order_node *on = container_of(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

+ struct order_node *on = container_of(p, struct order_node, node);
- struct order_node *on = CCCC(p, struct order_node, node);

+ hlist_for_each (p, &head[hash]) {
- hlist_for_each (p, BBBB) {

### **`dfs`**
- Checks if the current subtree bounds are valid.
- Allocates memory for a new TreeNode and sets its value to the first element in the preorder traversal.
- Finds the index of the root node in the inorder list
- Recursively constructs the `left` subtree:
- Updates the subtree bounds and recursively calls `dfs` for the left subtree.
- Recursively constructs the `right` subtree:
- Updates the subtree bounds and recursively calls `dfs` for the right subtree.
- Returns the root node of the constructed binary tree.

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

### The meaning of`pre_low + (idx - in_low)`:
The expression is used to determine the range of elements in the preorder list that correspond to the left subtree of the current node being constructed.

#### Breakdown of the Expression:
- `pre_low`: Index of the root node in the preorder list.
- `idx`: Index of the root node in the inorder list.
- `in_low`: Starting index of the current range in the inorder list.

#### Explanation:
- In the inorder list, elements to the left of the root node (from index `in_low` to `idx - 1`) belong to the left subtree of the current node.
- To find the corresponding range of elements in the preorder list for the left subtree:
- The left subtree in the preorder list immediately follows the root node.
- The number of elements in the left subtree of the current node is determined by the difference between the index of the root node in the inorder list (`idx`) and the starting index of the current range in the inorder list (`in_low`).
- Therefore, `idx - in_low` gives us the count of elements in the left subtree. Adding this count to the index of the root node in the preorder list (`pre_low`) gives us the index of the first element of the left subtree in the preorder list.

### The meaning of `pre_high - (in_high - idx - 1)`
**Same as previous, this expression is aim for the right subtree.**
- The right subtree in the preorder list is located after the left subtree and the root node.
- We need to consider the number of elements in the right subtree of the current node, which is determined by the difference between the index of the last element in the inorder list (`in_high`) and the index of the root node (`idx`), plus 1 to include the root node.
- Subtracting this count from the index of the last element in the preorder list (`pre_high`) gives us the index of the first element of the right subtree in the preorder list.

### `node_add`
This function add the node to the hash list and count the hash key using it's value and the list size.

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);
}

+ hlist_add_head(&on->node, &heads[hash]);
- hlist_add_head(&on->node, DDDD);

### `buildTree`
First of all, build a hash table for inorder list. Then `dfs` is used to build the tree

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));

    for (int i = 0; i < inorderSize; i++)
        INIT_HLIST_HEAD(&in_heads[i]);

    for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);

    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}

### 測驗 2
#### LRU 資料結構:
The LRUCache and LRUNode structures are used together to implement a Least Recently Used (LRU) cache.

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

#### ```LRUCache```
- `LRUCache` represents the main cache structure.
- It contains the following members:
- `capacity`: The maximum capacity of the cache.
- `count`: The current number of elements in the cache.
- `dhead`: The head of a doubly linked list used to maintain the order of elements based on their usage.
- `hhead[]`: An array of hash lists used for quick lookup of elements by their key.

#### ```LRUNode```
- `LRUNode` represents a node in the cache.
- Each node contains the following members:
- `key`: The key associated with the node.
- `value`: The value associated with the key.
- `node`: An instance of `hlist_node` used to link nodes within a hash list.
- `link`: An instance of `list_head` used to link nodes within the doubly linked list maintained by the LRUCache.
- **Each LRUNode is stored in both a hash list and the doubly linked list.**
- **The hash list provides fast access to nodes based on their key, while the doubly linked list maintains the order of nodes based on their usage.**

digraph G {
    graph [fontsize=12  compound=true];
    node [shape="record"];
    rankdir = "LR"
    
    subgraph cluster_a
    {
        label = "LRUNode_key 2";
        node1 [label="<head>list_head|{<prev> *prev |<next> *next}"];
    }
    
    subgraph cluster_b
    {
        label = "LRUNode_key 3";
        node2 [label="<head>list_head|{<prev> *prev |<next> *next}"];
    }
    
    subgraph cluster_c
    {
        label = "LRUNode_key 1";
        node3 [label="<head>list_head|{<prev> *prev |<next> *next}"];
    }
    
    subgraph cluster_d
    {
        color=red 
        label = "LRUNode_key 4";
        node4 [label="<head>list_head|{<prev> *prev |<next> *next}"];
    }


    "*dhead"->node4:head ;
    node4:next->node1 ;
    // node1:prev:s->node4:head ;
    node1:next->node2 ;
    // node2:prev:s->node1:head ;
    node2:next->node3 ;
    // node3:prev:s->node2:head ;



     rankdir=LR;

    node[shape=record];
    map [label="<head>hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "];
    
    "*hhead";

    subgraph cluster_1 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn1 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="LRUNode_key 1"
    }
    
    subgraph cluster_2 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn2 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="LRUNode_key 2"
    }
    
    subgraph cluster_3 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn3 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="LRUNode_key 3"
    }
    
    subgraph cluster_4 {
        style=filled;
		color=lightgrey;
        node [shape=record];
        hn4 [label="hlist_node | {<prev>pprev | <next>next}"];
        label="LRUNode_key 4"
    }
    
    map:ht1 -> hn1
    hn1:next -> hn2
    hn2:prev:s -> hn1:next:s
    map:ht5 -> hn4
    hn4:next->hn3
    hn1:prev:s -> map:ht1
    hn4:prev:s -> map:ht5
    hn3:prev:s -> hn4:next
    "*hhead"->map:head;
}

:::success
Reference from [marvin0102](https://hackmd.io/hhUqTWYhR0uEDiENY67cpA?view) figure to illustrate the relationship of LRUCache and LRUNode as above.
:::

The `lRUCacheFree` function is responsible for freeing the memory allocated for the LRUCache object and its associated LRUNodes. It iterates through the doubly linked list of LRUNodes, deletes each node from the list, frees the memory associated with it, and finally frees the memory occupied by the LRUCache object itself.

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
-       LRUNode *cache = list_entry(pos, LRUNode, FFFF);
+       LRUNode *cache = list_entry(pos, LRUNode, link);
-       list_del(GGGG);
+       list_del(&(cache->link));
        free(cache);
    }
    free(obj);
}

The `lRUCacheGet` function is used to retrieve the value associated with a given key from the LRUCache object.

- It calculates the hash value for the key using the modulo operation `%` with the capacity of the ```LRUCache```.
- It then iterates through the hash list associated with the computed hash value.
- Within the loop, it obtains each LRUNode corresponding to the current hash value using the `list_entry`.
- It checks if the key of the current LRUNode matches the key being searched for.
- If a match is found, it moves the LRUNode to the front of the doubly linked list using the `list_move` function to indicate that it was recently accessed and returns the value associated with the key.
- If no matching key is found, it returns `-1` indicating that the key was not found in the LRUCache.

@@ -140,9 +140,9 @@ 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);
+        LRUNode *cache = list_entry(pos, LRUNode, node);
         if (cache->key == key) {
-            list_move(IIII, &obj->dhead);
+            list_move(&(cache->link), &obj->dhead);
             return cache->value;
         }
     }

The `lRUCachePut` function is used to insert a key-value pair into the `LRUCache`.

- It calculates the hash value for the key using the modulo operation `%` with the capacity of the LRUCache and iterates through the hash list associated with the computed hash value to check if the key already exists in the cache.
- **If the key exist:**
- If the key already exists, it moves the `LRUNode` to the front of the doubly linked list to indicate that it was recently accessed.
- It updates the `cache` pointer with the found LRUNode.
- **If the key does not exist:**
- If the cache is full, it removes the `LRUNode` associated with the least recently used key from the cache by moving it to the front of the doubly linked list and updating the hash list.
- It creates a new LRUNode for the key-value pair, adds it to the cache, and updates the count.
- Finally, it sets the value of the `LRUNode` to the specified value.

@@ -155,9 +155,9 @@ void lRUCachePut(LRUCache *obj, int key, int value)
     int hash = key % obj->capacity;
     struct hlist_node *pos;
     hlist_for_each (pos, &obj->hhead[hash]) {
-        LRUNode *c = list_entry(pos, LRUNode, JJJJ);
+        LRUNode *c = list_entry(pos, LRUNode, node);
         if (c->key == key) {
-            list_move(KKKK, &obj->dhead);
+            list_move(&c->link, &obj->dhead);
             cache = c;
         }
     }

### 測驗 3
`sz % BITS_PER_LONG` calculates the remainder when `sz` is divided by `BITS_PER_LONG`. It determines if there are any remaining bits after dividing `sz` into groups of `BITS_PER_LONG`.
The result of this expression is used as a condition to check if there are any remaining bits in the last word. If there are remaining bits, the macro performs additional operations to handle the last word separately.

@@ -49,7 +49,7 @@ static inline unsigned long hweight_long(unsigned long w)
             nr -= w;                                            \
         }                                                       \
                                                                 \
-        if (sz CCCC BITS_PER_LONG)                              \
+        if (sz % BITS_PER_LONG)                              \
             tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
     found:                                                      \
         sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \

The `__ffs` function efficiently finds the position of the first set (non-zero) bit in a 64-bit word. The function first checks if the lower 32 bits of the word are all zeros. This is done by bitwise AND operation with 0xffffffff, which isolates the lower 32 bits.

@@ -67,7 +67,7 @@ static inline unsigned long __ffs(unsigned long word)
     int num = 0;

 #if BITS_PER_LONG == 64
-    if ((word & AAAA) == 0) {
+    if ((word & 0xffffffff) == 0) {
         num += 32;
         word >>= 32;
     }

`__clear_bit` function calculate the mask for the specific bit to be cleared using `BIT_MASK(nr)`. This creates a bitmask with all bits set to 1 except for the bit at position `nr`, which is set to 0. For the address, it calculates the address of the word (a group of bits) containing the bit to be cleared. This is done by adding the word index (determined by `BIT_WORD(nr)`) to the base address `addr`. In the end, it perform a bitwise AND operation between the value pointed to by `p` and the complement of the mask (`~mask`). This clears the bit at position `nr` in the word.

@@ -98,7 +98,7 @@ 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 &= BBBB;
+    *p &= ~mask;
 }