Before moving to and describing how the kernel keeps track of the various processes in the system,
we would like to emphasize the role of special data structures that implement doubly linked lists.
For each list, a set of primitives operations must be implemented: initializing the lists, inserting and
deleting an element, scanning the list, and so on. It would be both a waste of programmers' effort
and a waste of memory to replicate the primitive operations for each different list.
Therefore, the Linux kernel defines the list_head data structure, whose only fields next and prev
represent the forward and back pointers of a generic doubly linked list element, respectively. It is
important to note, however, that the pointers in a list_head field store the addresses of other list_heads
rather then the addresses of the whole data structure in which the list_head structure is included;
A new list is created by using the LIST_HEAD(list_name) macro. It declares a new variable named
list_name of type list_head, which is a dummy first element that acts as a placeholder for the head
of the new list, and initializes the prev and next fields of the list_head data structure so as to point
to the list_name variable itself.
The Process List
The first example of a doubly linked list we will examine is the process list, a list that links together
all existing process descriptors. Each task_struct structure includes a tasks field of type list_head
whose prev and next fields point, respectively, to the previous and to the next task_struct element.
The head of the process list is the init_task task_struct descriptor; it is the process descriptor of the
so-called process 0 or swapper. The task->prev field of init_task points to the tasks field of the process
descriptor inserted last in the list.
The SET_LINK and REMOVE_LINK macros are used to insert and to remove a process descriptor
in the process list, respectively. These macros also take care of the parenthood relationship of the
process.
Another useful macro, called for_each_process, scans the whole process list. It is defined as follows.
The macro is the loop control statement after which the kernel programmer supplies the loop. Notice
how the init_task process descriptor just plays the role of list header. The macro starts by moving
past init_task to the next task and continues until it reaches init_task again (thanks to the circularity
of the list). At each interation, the variable passed as the argument of the macro contains the address
of the currently scanned process descriptor, as returned by the list_entry macro.
#define for_each_process(p)
for (p = &init_task; (p = list_entry((p)->tasks.next,
struct task_struct, tasks)
) != &init_task;)