list_add_tail_rcu has the effect of adding the newly created task’s tasks node to the tail of the init_task task list.Īs mentioned, the task list is mainly used when the Kernel needs to perform an action on each task. It uses RCU, which is a synchronization mechanism that supports concurrency between a single writer and multiple readers (no need to go into the details). List_add_tail_rcu is a variation of the list_add function from earlier. List_add_tail_rcu( &p ->tasks, &init_task.tasks) The Linux circular doubly linked list is defined in include/linux/list.h. The most popular is an intrusive circular doubly linked list. Linux includes a few different list structures. Of those, 28% of traversals either occurred on empty lists, or only visited one node (see Rusty Russel’s analysis of linked lists for more info).Īs Rusty’s analysis suggests, Linux mainly uses linked lists to keep lists of objects when either traversal is infrequent, or when the list size is small. An analysis of Linux during normal usage found that traversals were only 6% of total linked list operations.
In Linux, list nodes are added and removed a lot more than they are traversed. A search for the struct list_head structure returns over 10,000 results in Linux 5.2.
#Listhead linux kernel example free#
They are used for all kinds of tasks, from keeping track of free memory slabs, to iterating through each running process. The most popular linked lists in Linux are circular doubly linked lists. The list structure would contain an extra prev pointer: Linux uses circular doubly linked lists, so this section will cover both variations.Ī doubly linked list is a linked list that keeps pointers to both the next node and the previous node. Doubly and circular linked listsĭoubly linked lists and circular linked lists are variations of singly linked lists. Intrusive linked lists only require dereferencing the next list node.īefore looking at how processes are managed using linked lists in Linux, you need to understand doubly and circular linked lists. Iterating through a non-intrusive list node requires dereferencing a list node, and then dereferencing the list data. Intrusive linked lists also suffer less from cache thrashing.
This means fewer errors to be handled, because there are half as many cases where memory allocation can fail. With intrusive linked lists, you only need to allocate one object (since the list node is embedded in the object). With non-intrusive linked lists, creating a new object and adding it to a list requires two memory allocations: one for the object, and one for the list node. There are two main reasons to use intrusive lists over non-intrusive linked lists:
0 kommentar(er)
