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))
({ 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); }
  1. 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); } }
  1. 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:

    Doxygen

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