2021q1 Homework2 (quiz2)

contributed by < chiehen >

tags:linux2021

測驗一

解釋程式碼

根據 q_insert_head 程式碼, 一個 queue 的架構大約如下:

改用 Graphviz 製圖

jserv

• list_cut_position()

/**
 * list_cut_position() - Move beginning of a list to another list
 * @head_to: pointer to the head of the list which receives nodes
 * @head_from: pointer to the head of the list
 * @node: pointer to the node in which defines the cutting point
 */
static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

假設 list_from 是 head 為 head_from 的 list;
list_to 是 head 為 head_to 的 list;
將原本在 list_from 的 node 從 第一個 list_ele_t 到 node 搬至 list_to, 因此 head_from 留下 node->next 到最後
因為操作上只有使用到 其中的list node 因此圖片只展示 list node

結束函式後:

• list_splice_tail()

/**
 * list_splice_tail() - Add list nodes from a list to end of another list
 * @list: pointer to the head of the list with the node entries
 * @head: pointer to the head of the list
 */
static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next, *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

將 list 所連接的 node 接在 head 所串起的這個 list 的後面

看到這裡時覺得很奇怪, 為什麼不用處理 list 的記憶體, 仔細看才發現在宣告的時候並沒有使用到 malloc

When and why to use malloc?

You use malloc when you need to allocate objects that must exist beyond the lifetime of execution of the current block (where a copy-on-return would be expensive as well), or if you need to allocate memory greater than the size of that stack (ie: a 3mb local stack array is a bad idea).

C99 7.20.3 Memory management functions

The lifetime of an allocated object extends from the allocation until the deallocation.

依照這個可發現 queue_t left; 在 list_merge 後已不需要, struct list_head sorted; 則是在執行 list_splice_tail(&sorted, &q->list); 後完成任務

• container of 的 macro 可以從 member 推出 struct 的記憶體起始位置

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

除了在題目中所說到的外,將 __pmember 轉型成 char* 是因為指標在進行加減時，是以 dereference 後的型態的大小作為單位, 而因為 offsetof 回傳的單位是 bytes, 因此在進行運算時先轉型成 deference 後單位同為 1 byte 的char*

pointer to zero??

---

測驗二

解釋程式碼

func 接受一個 16 位元無號整數 N 並回傳小於或等於 N 的 power-of-2

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

直觀上想找到符合題目要求的值，便會想到從 MSB 開始找第一個不是零的位元(以下稱目標位元)，他的數值便是所求，舉例來說:
N = 10101₂ = 21₁₀ , func(N) = 16₁₀ = 10000₂
N = 100000₂ = 32₁₀, func(N) = 32₁₀ = 100000₂

而配合註解可以發現，此程式透過將目標位元以下的位元都賦值為 1 , 再將此數字 +1 變可得到(目標位元+1個位元)的數值, 因此只要再又一個 bit 就是所求，舉例:
N = 10101₂ = 21₁₀

1. 11111₂
2. 100000₂
3. 10000₂ = 16₁₀

而如何將目標位元以下的位元都賦值為 1, 便是測驗的部分。而以看似最難以達成的 N = 8000₁₆ (最多 0 需要被設為 1)舉例

1. 因為目標位元保證為 1 ，在第三行後能保證目標位元及下一個位元都為 1, (N=C000₁₆)
2. 基於上一點, 第四行則能保證目標位元及比他小的三個位元都為 1, (N = F000₁₆)
3. 基於上一點, 第五行則能保證目標位元及比他小的7個位元都為 1, (N = FF00₁₆)
4. 基於上一點, 第六行則能保證目標位元及比他小的15個位元都為 1, (N = FFFF₁₆)

因此能保證此方法對 16 位元能達到預期的效果

P.S. 事實上，如果最初值為 N = 8000₁₆, 會在最後 N + 1 時發生 overflow, 所以應另外做處理

---

測驗三