In Linux Kernel source code, its common to find lots of manipulations related to List, like the double link list of the process descriptor. It's necessary to figure out those List APIs.

List Struct

We use struct list_head to represent the list data structure.

struct list_head{
  struct list_head *next, *prev;
}

This implementation make sure that we can get the list->next and list->prev(double linked),and every element in the list is list_head type.

List Macro

Also we need to iterate elements in the list. Linux define list_for_each as a macro.

#define list_for_each(pos,head)\
    for(pos=head->next;pos!=head;pos=pos->next)

list_head actually is like a address identifier of its container, which means that list_head can only indicates the current location of its container, but doesn't have any value. So how can we get its container. Linux give the solution below.

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

list_entry actually is identical to container_of ,which is used to calculate the container address position of ptr
The second param type is the type if container
The last param *member is the name of ptr in the container field.
offsetof(type,member) is aimed to calculate the offset from base address of type to the address of member.Its implementation is a little tricky since it cast 0 to the type of type. The address of 0 actually is the base address of struct. Followed by pointed to member, the result is the address offset of the member in type exactly.
Then we cast ptr to char* to make sure that the unit distance of address of ptr is one byte. Finally we use address of ptr minus offset and the result is the address of container. All done!

Application

With the API implemented above, we can realize the function like iterate all the children of current process as below.

list_for_each(list, &current->children) {
  task = list_entry(list, struct task_struct, sibling);
  /* task now points to one of current’s children */
}

People may get confused about the third param of list_entry, sibling. The figure below can explain that.

aaa.jpg

list_entry(task->tasks.next, struct task_struct, tasks)
list_entry(task->tasks.prev, struct task_struct, tasks)