2019q1 Homework1 (list)

contributed by < lineagech >

Something I had not realized…

• container_of(ptr, type, member)

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

• typeof
  typeof is a compiler extension

• offsetof
  Using 0 address and cast it into type pointer, and then points to member to get the offset from 0 address, and finally cast to size_t.

#define offsetof(type, member) ((size_t)&(((type *)0)->member))

• Statements and Declarations in Expressions
  The value of this subexpression serves as the value of the entire construct. The followiing example shows that the value will be z.

({ int y = foo (); int z;
   if (y > 0) z = y;
   else z = - y;
   z; })

• Makefile

  • Suffix rules are rules of the form .c.o. They are a way of telling make that any time you see, say, a .f file (the source file), you can make a .o file (the target file) from it by following that rule, where $< indicates the source file and $@ represents the target file.

  • Static pattern rules are rules which specify multiple targets and construct the prerequisite names for each target based on the target name. They are more general than ordinary rules with multiple targets because the targets do not have to have identical prerequisites. Their prerequisites must be analogous, but not necessarily identical.

    $(objects): %.o: %.c
    $(CC) -c $(CFLAGS) $< -o $@

Requirements

• 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
  Ans. Macro can be expanded when preprocessing, and is not like function call that needs to push arguments abd return address to stack, and even modify base/stack pointers creating calling frame. So it can just reduce more instructions execution required.
• Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
  Ans.

列出 Linux 核心程式碼時，需要標注版本資訊，避免資訊過時
:notes: jserv

1. The first one came to my mind is scheduling queue, so I just look for list_head in task_struct in include/linux/sched.h, and there is a run_list, and its operation like real-time scheduling: push a list of entities to a priority queue according to the entity's priority

static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, unsigned int flags)
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
	struct rt_prio_array *array = &rt_rq->active;
	struct rt_rq *group_rq = group_rt_rq(rt_se);
	struct list_head *queue = array->queue + rt_se_prio(rt_se);

	/*
	 * Don't enqueue the group if its throttled, or when empty.
	 * The latter is a consequence of the former when a child group
	 * get throttled and the current group doesn't have any other
	 * active members.
	 */
	if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running)) {
		if (rt_se->on_list)
			__delist_rt_entity(rt_se, array);
		return;
	}

	if (move_entity(flags)) {
		WARN_ON_ONCE(rt_se->on_list);
		if (flags & ENQUEUE_HEAD)
			list_add(&rt_se->run_list, queue);
		else
			list_add_tail(&rt_se->run_list, queue);

		__set_bit(rt_se_prio(rt_se), array->bitmap);
		rt_se->on_list = 1;
	}
	rt_se->on_rq = 1;

	inc_rt_tasks(rt_se, rt_rq);
}

2. Also I found that linux uses list_head in page table related operations, at line 14, it just retrives each page according to its list_head lru. Here I guess it sorts pages according to lru policy and then can find relative struct ebased on the list_head noe:

void vmalloc_sync_all(void)
{
	unsigned long address;

	if (SHARED_KERNEL_PMD)
		return;

	for (address = VMALLOC_START & PMD_MASK;
	     address >= TASK_SIZE_MAX && address < FIXADDR_TOP;
	     address += PMD_SIZE) {
		struct page *page;

		spin_lock(&pgd_lock);
		list_for_each_entry(page, &pgd_list, lru) {
			spinlock_t *pgt_lock;
			pmd_t *ret;

			/* the pgt_lock only for Xen */
			pgt_lock = &pgd_page_get_mm(page)->page_table_lock;

			spin_lock(pgt_lock);
			ret = vmalloc_sync_one(page_address(page), address);
			spin_unlock(pgt_lock);

			if (!ret)
				break;
		}
		spin_unlock(&pgd_lock);
	}
}

3. I saw in arch/arm/mm/mmu.c, linux memory management maintains a static virtual memory which may be used by ioremap/vmalloc(?) list. The follwoing code fill dummy vm entries by traversing the list.

static void __init fill_pmd_gaps(void)
{
	struct static_vm *svm;
	struct vm_struct *vm;
	unsigned long addr, next = 0;
	pmd_t *pmd;

	list_for_each_entry(svm, &static_vmlist, list) {
		vm = &svm->vm;
		addr = (unsigned long)vm->addr;
		if (addr < next)
			continue;

		/*
		 * Check if this vm starts on an odd section boundary.
		 * If so and the first section entry for this PMD is free
		 * then we block the corresponding virtual address.
		 */
		if ((addr & ~PMD_MASK) == SECTION_SIZE) {
			pmd = pmd_off_k(addr);
			if (pmd_none(*pmd))
				pmd_empty_section_gap(addr & PMD_MASK);
		}

		/*
		 * Then check if this vm ends on an odd section boundary.
		 * If so and the second section entry for this PMD is empty
		 * then we block the corresponding virtual address.
		 */
		addr += vm->size;
		if ((addr & ~PMD_MASK) == SECTION_SIZE) {
			pmd = pmd_off_k(addr) + 1;
			if (pmd_none(*pmd))
				pmd_empty_section_gap(addr);
		}

		/* no need to look at any vm entry until we hit the next PMD */
		next = (addr + PMD_SIZE - 1) & PMD_MASK;
	}
}

• GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
  It can refer to type of an expression.
  e.g.
  #define pointer(T) typeof(T *)
#define array(T, N) typeof(T [N])
  In pratice we can just get the type we wanted dynamically and like use it in macro.

• 解釋以下巨集的原理

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

  __extension__: GCC uses the extension attribute when using the -ansi/-pedantic flag to avoid warnings in headers with GCC extensions, such as ({…}).

  we can get the pointer __pmember type of type->member in struct by using typeof so that we dont need to know what type it is explicitly.
  And subtract the offset, from starting address to address of member by offsetof.
  Finally it gets the address of object containing member whose address is ptr.

• 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
  Ans.　In addition to add and delete, there are other operations like:

  • list_empty: check if list is only head itself
  • list_is_singular: check if list has only one element except for head
  • list_splice: move one list and add to another list
  • list_cut_position: cut part of list to anther list
  • list_move: move one node of a list to another list

  I think kernel maintains lots of lists which is sorted based on some criterions. Due to those macro operations, it can add or remove a node even a list to or from another more efficiently.

• LIST_POISONING 這樣的設計有何意義？
  It is defined in linux/position.h. And comment is

  ​​​​These are non-NULL pointers that will result in page faults 
  ​​​​under normal circumstances, used to verify that nobody uses 
  ​​​​non-initialized list entries. 
  

  Linux purposely let head point to specific addresses and page faults will happen. The design can make kernel know someone has accessed empty list, easy to debug(?), not very sure.

• linked list 採用環狀是基於哪些考量？
  I think it is a performance issue. Based on the operations defined in linux.h, sometimes it needs to add/delete a list at the head of tail. So circular list will make operations easier.

• 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
  Like priority-based scheduling, kernel will schedule process according to its priority value, and also the number of process is not fixed. So better using list and sort it.

• 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
  *

• list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
  list_for_each_safe additionaly memorize next pointer so that it allows users to delete node after getting it and will not affect traversing.

• for_each 風格的開發方式對程式開發者的影響為何？
  for_each is more like python as:

  ​​​​list = [1, 2, 3,...]
  ​​​​for i in list:
  ​​​​    ......
  

  It hide for-loop details and need simple one line. I think it is a more concise way for programmer.

• 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
  It is specified by Doxygen rules:

  

  Like function parameters, we can just specify @param etc. It is a clearer way for others tracing code afterwards

• tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
  Unit test means that testing every single function you have and write some test programs or scripts to test it. Like those *.c files in the tests/, every *.c is just a prgram to verify each list operation using assert

• tests/ 目錄的 unit test 可如何持續精進和改善呢？
  Under example/ folder, I just modify the source c file to get user input indicating unsorted array size and Makefile to do multiple unit tests automatically, the same as applying to tests/:

  ​​​​/* Get array size from user input */
  ​​​​while ((c = getopt(argc, argv, "s:")) != -1) {
  ​​​​    switch (c) {
  ​​​​    case 's':
  ​​​​        array_size = atoi(optarg);
  ​​​​        printf("size %u\n", array_size);
  ​​​​        break;
  ​​​​    default:
  ​​​​        break;
  ​​​​    }
  ​​​​}
  

  ​​​​NUMBERS = 256 512 1024 2048 4096 8192
  ​​​​@if [ $< = 'merge-sort' ]; then \
  ​	for i in $(NUMBERS); do\
  ​		./$< -s $$i && $(PRINTF) "\t$(PASS_COLOR)[ Verified ]$(NO_COLOR)\n";\
  ​	done;\
  ​fi
  

Merge Sort Implementation

不需要張貼完整程式碼 (置於 GitHub 即可)，相反的，你應該闡述實作背後的思維及考量點，特別要談如何驗證功能
:notes: jserv

merge-sort.c:

• list_mergesort

void list_mergesort(struct list_head *head)
{
    struct list_head left;
    struct list_head right;

    /* Handle when there is only one node */
    if (list_is_singular(head))
        return;

    /* Split two parts */
    list_split(head, &left, &right);

    /* Sort each part */
    list_mergesort(&left);
    list_mergesort(&right);

    /* Merge to the final result head */
    list_merge(head, &left, &right);
}

• list_split

void list_split(struct list_head *head,
                struct list_head *front,
                struct list_head *back)
{
    struct list_head *slow, *fast;

    if (head == NULL || list_empty(head)) {
        return;
    }

    for (slow = head->next, fast = head->next;
         fast != head && fast->next != head;) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_cut_position(front, head, slow->prev);
    list_cut_position(back, head, (fast == head ? head->prev : fast));
}

• list_merge

void list_merge(struct list_head *head,
                struct list_head *front,
                struct list_head *back)
{
    struct list_head *front_curr = front->next;
    struct list_head *back_curr = back->next;
    struct list_head *next;
    struct listitem *front_item = NULL;
    struct listitem *back_item = NULL;

    while (front_curr != front && back_curr != back) {
        front_item = list_entry(front_curr, struct listitem, list);
        back_item = list_entry(back_curr, struct listitem, list);
        if (front_item->i <= back_item->i) {
            next = front_curr->next;
            // delete from origin
            list_del(front_curr);
            // add to new
            list_add_tail(front_curr, head);
            front_curr = next;
        } else {
            next = back_curr->next;
            list_del(back_curr);
            list_add_tail(back_curr, head);
            back_curr = next;
        }
    }
    if (!list_empty(front)) {
        list_splice_tail_init(front, head);
    } else {
        list_splice_tail_init(back, head);
    }

    assert(list_empty(front));
    assert(list_empty(back));
}

• unit test
  Create Makefile for three .c files. Type make to compile all source files and type make test to do unit test automatically:

include common.mk

CFLAGS = -I../include -I../private
CFLAGS += -std=c99 -Wall -Werror -W -pedantic

.PHONY = all check clean

TESTS = insert-sort \
        merge-sort \
		quick-sort

TESTS_OK = $(TESTS:=.ok)

deps = $(TESTS:%:%.o.d)

check: $(TESTS_OK)

$(TESTS_OK): %.ok : %
	$(Q)$(PRINTF) "*** Validating $< ***\n"
	$(Q)./$< && $(PRINTF) "\t$(PASS_COLOR)[ Verified ]$(NO_COLOR)\n"
	@touch $@

## standard build rules
.SUFFIXES: .o .c
.c.o:
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF $@.d $<

$(TESTS): % : %.o
	$(VECHO) "  LD\t$@\n"
	$(Q)$(CC) -o $@ $^ $(LDFLAGS)

clean:
	$(VECHO) "  Cleaning...\n"
	$(Q)$(RM) $(TESTS) $(TESTS_OK) $(TESTS:=.o) $(TESTS:=.o.d)

-include $(deps)  

int main(void)
{
    struct list_head head;
    struct listitem *item = NULL;
    struct listitem *is = NULL;
    size_t i;

    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));

    INIT_LIST_HEAD(&head);

    for (i = 0; i < ARRAY_SIZE(values); i++) {
        item = (struct listitem *) malloc(sizeof(*item));
        assert(item);
        item->i = values[i];
        list_add_tail(&(item->list), &head);
    }

    /* Get correct sorted array */
    qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);

    /* Merge sort */
    list_mergesort(&head);

    /* Verify the result */
    i = 0;
    list_for_each_entry_safe (item, is, &head, list) {
        assert(item->i == values[i++]);
        list_del(&item->list);
        free(item);
    }

    assert(i == ARRAY_SIZE(values));
    assert(list_empty(&head));

    return 0;
}