Try   HackMD

2021q1 Homework2 (quiz2)

tags:<linux2021>

題目1

考慮以下仿效 Linux 核心 include/linux/list.h 的精簡實作:

#include <stddef.h>

/**
 * container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
#ifndef container_of
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#endif

/**
 * struct list_head - Head and node of a doubly-linked list
 * @prev: pointer to the previous node in the list
 * @next: pointer to the next node in the list
 */
struct list_head {
    struct list_head *prev, *next;
};

/**
 * LIST_HEAD - Declare list head and initialize it
 * @head: name of the new object
 */
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

/**
 * INIT_LIST_HEAD() - Initialize empty list head
 * @head: pointer to list head
 */
static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head; head->prev = head;
}

/**
 * list_add_tail() - Add a list node to the end of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

/**
 * list_del() - Remove a list node from the list
 * @node: pointer to the node
 */
static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next, *prev = node->prev;
    next->prev = prev; prev->next = next;
}

/**
 * list_empty() - Check if list head has no nodes attached
 * @head: pointer to the head of the list
 */
static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

/**
 * list_is_singular() - Check if list head has exactly one node attached
 * @head: pointer to the head of the list
 */
static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

/**
 * 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_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_entry() - Calculate address of entry that contains list node
 * @node: pointer to list node
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_entry(node, type, member) container_of(node, type, member)

/**
 * list_first_entry() - get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

/**
 * list_for_each - iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

接著延伸上述程式碼時做 doubly-linked list 的 merge sort:

#include <string.h>

typedef struct __element {
    char *value;
    struct __element *next;
    struct list_head list;
} list_ele_t;

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
    struct list_head list;
} queue_t;

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (COND1 || COND2)
            break;
        fast = fast->next->next;
    }
    return list_entry(TTT, list_ele_t, list);
}

static void list_merge(struct list_head *lhs,
                       struct list_head *rhs,
                       struct list_head *head)
{
    INIT_LIST_HEAD(head);
    if (list_empty(lhs)) {
        list_splice_tail(lhs, head);
        return;
    }
    if (list_empty(rhs)) {
        list_splice_tail(rhs, head);
        return;
    }

    while (!list_empty(lhs) && !list_empty(rhs)) {
        char *lv = list_entry(lhs->next, list_ele_t, list)->value;
        char *rv = list_entry(rhs->next, list_ele_t, list)->value;
        struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
        list_del(tmp);
        list_add_tail(tmp, head);
    }
    list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

void list_merge_sort(queue_t *q)
{
    if (list_is_singular(&q->list))
        return;

    queue_t left;
    struct list_head sorted;
    INIT_LIST_HEAD(&left.list);
    list_cut_position(&left.list, &q->list, MMM);
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left.list, &q->list, &sorted);
    INIT_LIST_HEAD(&q->list);
    list_splice_tail(&sorted, &q->list);
}
  • COND1 : fast -> next == list
  • COND2 : fasr->next->next == list
  • MMM : &get_middle(&q->list)->list
  • TTT : slow

測試程式碼 main.c 如下:

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static bool validate(queue_t *q)
{
    struct list_head *node;
    list_for_each (node, &q->list) {
        if (node->next == &q->list)
            break;
        if (strcmp(list_entry(node, list_ele_t, list)->value,
                   list_entry(node->next, list_ele_t, list)->value) > 0)
            return false;
    }
    return true;
}

static queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q) return NULL;

    q->head = q->tail = NULL;
    q->size = 0;
    INIT_LIST_HEAD(&q->list);
    return q;
}

static void q_free(queue_t *q)
{
    if (!q) return;

    list_ele_t *current = q->head;
    while (current) {
        list_ele_t *tmp = current;
        current = current->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    char *new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;
    list_add_tail(&newh->list, &q->list);

    return true;
}

int main(void)
{
    FILE *fp = fopen("cities.txt", "r");
    if (!fp) {
        perror("failed to open cities.txt");
        exit(EXIT_FAILURE);
    }

    queue_t *q = q_new();
    char buf[256];
    while (fgets(buf, 256, fp))
        q_insert_head(q, buf);
    fclose(fp);

    list_merge_sort(q);
    assert(validate(q));

    q_free(q);

    return 0;
}

(一)解釋程式碼運作原理:

根據 merge-sort 的實作方法,第一步先將整個序列對半分割:







mergesort



O

Original Array



P1

P1



O->P1


partition into two



P2

P2



O->P2





分別將左右兩個序列依照一樣的步驟分割直到不能再分割(size is 1)後倆倆合併 :







merge



P1

E1(size 1)



P5

M1(size 2)



P1->P5


Merge



P2

E2(size 1)



P2->P5





P3

E3(size 1)



P6

M2(size 2)



P3->P6


  Merge



P4

E4(size 1)



P4->P6





P7

Final(size 4)



P5->P7


Merge



P6->P7





對於 Linked List 裡面該如何將其分成兩段?在程式碼中的 get_middle 使用的方法是利用 fastslow 指標,fast 指標走訪 linked list 的速度是 slow 的兩倍,因為是 doubly linked list 所以當 fast 走到開頭的時候代表整個串列已經走訪完,所以 slow 指標會指在串列的中間位置,對應的程式碼為:

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (fast->next == list || fast->next->next == list)
            break;
        fast = fast->next->next;
    }
    return list_entry(slow, list_ele_t, list);
}

上述程式碼在最後的回傳值是 list_ele_t* (pointer to list_ele_t) ,但是 slowstruct list_head* (pointer to struct list_head) ,所以在回傳時使用 list_entry 巨集算出包含 slow 指標的 list_ele_t 記憶體位置。
接著看程式碼中在哪裡呼叫 get_middle

...
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
...

由此可知是在 list_cut_position 中呼叫的,接下來看看 list_cut_position 的實作:

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;
}

對應的操作如圖:

  • 一開始的狀況,e1 為 list 的開頭 e3 為中間的節點






list



head_from_first

head_from_first



e2

e2



head_from_first->e2





head_from

head_from



e1

e1



head_from->e1





head_to

head_to



head_to->head_to





node_

node



e3

e3



node_->e3





e1->e2





e5

e5



e1->e5





e2->e1





e2->e3





e3->e2





e4

e4



e3->e4





e4->e3





e4->e5





e5->e1





e5->e4





  • e1 (head_from 所指的記憶體位址) 的 next 指向 e4 (node->next 所指的記憶體位址),e4 (head_from->next 所指的記憶體位址) 的 pre 指向 e1 (head_from 所指的記憶體位址)






list



head_from_first

head_from_first



e2

e2



head_from_first->e2





head_from

head_from



e1

e1



head_from->e1





head_to

head_to



head_to->head_to





node_

node



e3

e3



node_->e3





e4

e4



e1->e4





e5

e5



e1->e5





e2->e1





e2->e3





e3->e2





e3->e4





e4->e1





e4->e5





e5->e1





e5->e4





  • 接下來執行完剩下的四行,就可以拆成兩段了






list



head_from_first

head_from_first



e2

e2



head_from_first->e2





head_from

head_from



e1

e1



head_from->e1





head_to

head_to



head_to->e2


next



e3

e3



head_to->e3


pre



node_

node



node_->e3





e4

e4



e1->e4





e5

e5



e1->e5





e2->head_to





e2->e3





e3->head_to





e3->e2





e4->e1





e4->e5





e5->e1





e5->e4





接下來針對分出的兩段 linked list 個別去做 merge sort 依序遞迴下去,
(Keep going)

題目 2

考慮函式 func 接受一個 16 位元無號整數 N,並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
假定 N = 101012 = 2110,那麼 func(21) 要得到 16,請補完程式碼,使其運作符合預期。
實作程式碼如下:

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> X;
    N |= N >> Y;
    N |= N >> Z;

    return (N + 1) >> 1;
}
  • X : 2
  • Y : 4
  • Z : 8

(一)解釋程式碼運作原理

  • 考慮以下數字 0b 1000 0000






bits



Value:
Value:



Bits:
Bits:



Value:->Bits:





values

1

0

0

0

0

0

0

0



indices

0th

1th

2th

3th

4th

5th

6th

7th



  • 先將其向右 shift 一格會變成






bits



Value:
Value:



Bits:
Bits:



Value:->Bits:





values

0

1

0

0

0

0

0

0



indices

0th

1th

2th

3th

4th

5th

6th

7th



  • 將其對原數做 or(|) 運算後得到的結果可見最高位元的右邊一格變成 1






bits



Value:
Value:



Bits:
Bits:



Value:->Bits:





values

1

1

0

0

0

0

0

0



indices

0th

1th

2th

3th

4th

5th

6th

7th



  • 目的是希望最高位元的右邊全部都變為 1 ,故必須用剛得到的結果繼續做,由於現在最高的二位元都為 1 ,必須對向右移 2 的結果做 or 運算才能把前面 4 位元都變為 1 ,結果如圖






bits



Value:
Value:



Bits:
Bits:



Value:->Bits:





values

1

1

1

1

0

0

0

0



indices

0th

1th

2th

3th

4th

5th

6th

7th



  • 接下來為了把最右邊的 4 位元都變成 1 ,就將結果向右移動 4 位元再做 or 便可以把它填滿並變成 1






bits



Value:
Value:



Bits:
Bits:



Value:->Bits:





values

1

1

1

1

1

1

1

1



indices

0th

1th

2th

3th

4th

5th

6th

7th



  • 這邊舉例是 8 bit 的無號數,但題目敘述是對 16 bit 無號數做運算,故將剛剛得到的結果再向右移 8 個位元便可填滿最右邊 8 位元

(二)查閱 linux 核心原始碼

is_power_of_2

arch/microblaze/mm/pgtable.c 中將其定為 macro:

#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))

若該數為 2 的冪次方則該數的最高非 0 位元右側必定全都為 0 ,將該數對該數扣 1 做 and 運算若為 0 則該數為 2 的冪次方