Level: Intermediate
Yangshazhou (
Pubb@163.net)
Department of Computer Science and Technology
This article analyzes the implementation of the 2.6.x core in the 2.6.x core and detailed explanation of each linked list operation interface through an instance.
I. Introduction to the Data Structure of Links
The linked list is a commonly used data structure, which connects a series of data nodes into a data chain through a pointer to an important way for linear meter. Compared with the array, the linked list has better dynamics, and there is no need to know the total amount of data in advance, which can be randomly allocated to insert or delete data in any location in the linked list. The overhead of the linked list is mainly accessible and the space loss of the organizational chain.
Typically the chain table data structure should at least contain two domains: Data field and pointer domain, data domains for storing data, and pointer domains are used to establish contacts with the next node. According to the contact form of the tissue and the various nodes, the linked list can be divided into a single-link table, a double-linked list, a loop chain list, and a schematic diagram of these types of common linked lists:
Single-link list
Figure 1 single-link table
Single-nin list is the simplest type of list, it is characterized by only one normal domain points to the successor node (next), so the traversal of the single-linked list can only be performed from the head to the tail (usually NULL empty pointer).
2. Double-linked list
Figure 2 Double-linked list
By designing the front drive and after two numerals, the double-linked list can be traversed from two directions, which is where it is different from the single-linked list. If you disrupt the predecessor, subsequent dependence, you can constitute "binary tree"; if the front flute of the first node is reached to the chain tail node, the backpoint of the tail point points to the first node (as a broken line portion in Figure 2), it constitutes a loop chain list. If you design more pointer domains, you can constitute a variety of complex tree data structures.
3. Circulatory list
The feature of the circulating chain list is the successive point of the tailpoint points to the first node. A schematic diagram of a dual cyclic chain table has been given, and it is characterized by any one of the two directions, any of the two directions, can be found in any of the two directions. If you go to the front prigle, it is a single cycle list.
A large number of linked list structures are used in the Linux kernel to organize data, including list of devices, and data organizations in various functional modules. Most of these linies use a fairly exciting linked table data structure implemented in [include / Linux / List.h]. The subsequent part of this paper will be described in detail to the organization and use of this data structure.
Second, the implementation of the Linux 2.6 core list data structure
Although the 2.6 core is used as the basis of the explanation, the latheclast structure and 2.6 of the second.4 core are not distinguished. Different from 2.6 to expand two chain table data structures: Lin table read copy update (RCU) and HSH Links (HLIST). Both extensions are based on the most basic List structure, so this article mainly introduces the basic linked table structure, then briefly introduces RCU and HLIST.
The definition of the chain data structure is simple (for the [include / Linux / List.h], all of the following code unless otherwise specified, the rest is taken from this file):
Struct List_head {structure list_head * next, * prev;};
The List_head structure contains two pointers PREV and NEXT pointing to the list_head structure, which shows that the linked table of the kernel has a double-chain table function, in fact, usually it is organized into a dual cycle list.
Unlike the double-linked table structure model introduced in the first quarter, there is no data domain in list_head. In the Linux kernel list, it is not included in the linked list structure, but is included in the data structure. In data structural textbooks, the classic definition of the list is usually like this (as a single-link table):
Struct list_node {structure; elemType data;};
Because of ELEMTYPE, each data item type is required to define respective linked table structures. Experienced C programmers should know that in the standard template library
The C Template is used, using a template abstraction and data item type unrelated to the data item type unrelated to the interface.
In the Linux kernel list, you need to organize data to organize a Struct List_head member, for example, in [include / Linux / Netfilter.h] defined a NF_SOCKOPT_OPS structure to describe the getSockOpt / for a protocol family Setsockopt interface, there is a member of Struct List_Head List, and the NF_SOCKOPT_OPS structure of each protocol family is organized in a linked list through this List member organization, and the header is NF_SOCKOPTS in [NET / CORE / NETFILTER.C]. List_head). From the figure below, we can see that this universal linked table structure avoids trouble of defining your own linked list for each data item type. Linux's simple practical, not for perfect and standard style, is reflected here.
Figure 3 NF_SOCKOPTS chain representation intent
Third, the chain operation interface
Declaration and initialization
In fact, Linux only defines a chain list node, and does not specifically define the chain head, how is a list structure established? Let's take a look at List_head () this macro:
#define list_head_init (name) {& (name), & (name)} #define list_head (name) Struct list_head name = list_head_init (name)
When we declare a list of NF_SOCKOPTS with list_Head (nf_sockopts), its next, the Prev pointer is initialized to point to yourself, so that we have an empty list, because Linux is pointed to NEXT to point to yourself. Judging whether the linked list is empty:
Static inline int list_empty (const struct list_head * head) {return head-> next == head;}
In addition to using a list_head () macro, Linux also provides an init_list_head macro for the runtime initialization list:
#define init_list_head (ptr) DO {/ (PTR) -> Next = (PTR); (PTR) -> prev = (PTR); /} while (0)
We use INIT_LIST_HEAD (& nf_sockopts) to use it.
2. Insert / delete / merge
a) insert
There are two ways to insert the linked list: inserted in the header and inserted at the end tail. Linux provides two interfaces for this:
static inline void list_add (struct list_head * new, struct list_head * head); static inline void list_add_tail (struct list_head * new, struct list_head * head); as Linux chain is circular list, and next header, PREV point to the list The first and last node, so the difference between list_add and list_add_tail is not big, in fact, Linux uses
__List_Add (New, Head, Head-> Next);
with
__list_add (new, head-> prev, head);
To achieve two interfaces, it is visible, after the header is inserted in the head, and insertion insertion is inserted behind Head-> Prev.
Suppose there is a new NF_SOCKOPT_OPS structure variable new_sockopt needs to be added to the NF_SOCKOPTS linked table, we should do this:
List_add (& new_sockopt.list, & nf_sockopts);
From here we see that the NF_SOCKOPTS linked list is not the address of the new_sockopt, but the address of the List element. How to access New_SOCKOPT through a list? There will be a detailed introduction below.
b) Delete
Static Inline Void List_Del (Struct List_Head * Entry);
When we need to delete new_sockopt items added to the NF_SOCKOPTS list: we do this:
List_del (& new_sockopt.list);
The new_sockopt.list, prev, and next pointers are set to list_position2 and list_position1, respectively, so that the setting is to ensure that the node items not in the list are not accessible - access to list_position1 and list_position2 will cause page failure . Correspondingly, the list_del_init () function adds list_init_head () to the node as the node as a node.
c) Move
Linux provides actions that move nodes originally belonging to a linked list to another linked list, and divide two categories according to the position inserted into the new list:
Static inline void list_move (struct list_head * head); static inline void list_move_tail (struct list_head * list, struct list_head * head);
For example, list_move (& nf_sockopt.list, & nf_sockopts) deletes new_sockopt from its linked list and then link it into the NF_SOCKOPTS head.
d) merge
In addition to insertion, delete operations for nodes, the Linux linked list also provides the insert function of the entire linked list:
Static inline void list_splice (struct list_head * list, struct list_head * head);
Suppose there are two linked lists, the headers are List1 and List2 (all Struct List_Head Variables), when calling list_splice (& List1, & List2), as long as List1 is non-empty, the content of the List1 linked list will be hooked on the list2 list, Located between List2 and List2.next (the first node of the original list2 table). The new list2 linked list will be the first node in the original list1 table, and the tail node is unchanged. As shown in the figure (the dashed arrow is a NEXT pointer): Figure 4 Link meter merge list_splice (& List1, & List2)
When List1 is hidden to List2, as the next NEXT1 of the original table head pointer, Prev still points to the original node, in order to avoid confusion, Linux provides a list_splice_init () function:
Static inline void list_splice_init (struct list_head * list, struct list_head * head);
On the basis of incorporating List into the Head Link list, the function calls init_list_head (list) sets the list as a empty chain.
3. Traverse
Traversing is one of the most frequent operations of the list. In order to facilitate the core application traversal chain table, the Linux linked list will be traversed to abstract into several macros. Before introducing the traversal macro, let's see how to access our truly required data items from the list.
a) by the chain table node to the data item variable
We know that only the address of the List_head member variable in the data item structure is saved in the Linux Link, then how do we access the node data as its owner through this list_head member? Linux provides a list_entry (PTR, TYPE, MEMBER) macro, where PTR is a pointer to the list_head member in the data, which is the address value stored in the list, Type is the type of data item, and Member is a data item. Type definition variable names of list_head members, for example, we have to access the first nf_sockopt_ops variable in the nf_sockopts linked list, then call:
List_entry (nf_sockopts-> next, struct nf_sockopt_ops, list);
Here "List" is a node member variable name that is defined in the NF_SOCKOPT_OPS structure.
#define list_entry (PTR, TYPE, MEMBER) Container_of (PTR, TYPE, MEMBER) Container_of macro definition in [INCLUDE / Linux / kernel.h]: #define container_of (PTR, TYPE, MEMBER) ({/ Const Typeof) (TYPE *) 0) -> MEMBER) * __ MPTR = (PTR); / (type *) ((char *) __ mptr - offsetof (type, member));}) Offsetof macro definition in [include / Linux / STDDEF. H] in: #define offsetof (Type, Member) ((size_t) & ((TYPE *) 0) -> MEMBER)
SIZE_T is finally defined as unsigned int (I386).
It is used here that a small trick using the compiler technology, and then the structure member is obtained in the offset in the structure, and then the address of the main structural variable is derived according to the address of the member variable. Container_of () and offsetof () not only for linked list operations, the most interesting place here is ((Type *) 0) -> MEMBER, which enforces the 0 address to "convert" the pointer to the Type structure, and then access the TYPE structure Member member in MEMBER. In the Container_OF macro, it is used to provide parameters for typeOf () (TypeOf () is a GCC extension, and similar to sizeof ()) to obtain data types of Member members; in offsetof (), this MEMBER member's address is actually The offset of the Member member relative to the structural variable is on the TYPE data structure.
If you are not so good, let's take a look at this picture below:
Figure 5 OFFSTOF () Macro principle
For a given one, OFFSTOF (Type, Member) is a constant, and list_entry () is using this constant offset to obtain the variable address of the list data item.
b) Traverse
There is such a paragraph in the nf_register_sockopt () function of [Net / Core / Netfilter.c]:
... struct list_head * i; ... list_for_each (i, & nf_sockopts) {struct nf_sockopt_ops * Ops = (struct nf_sockopt_ops *) i; ......} ...
The function first defines a (struct list_head *) pointer variable I, then call List_for_each (i, & nf_sockopts) to traverse. In [incrude / Linux / List.h], the list_for_each () macro is as defined:
#define list_for_each (POS, Head) / for (POS = (Head) -> Next, Prefetch (POS-> Next); POS! = (Head); / POS = POS-> Next, Prefetch (POS-> Next) )
It is actually a for loop, using incoming POS as a loop variable, starting POS from the head head head, one item by item (NEXT direction) until returning to head (prefetch () can not consider, for pre- Take it to improve traversal speed).
Then act in nf_register_sockopt () is actually traversing the NF_SOCKOPTS linked list. Why can I directly use the List_Head member variable address as the address variable of the Struct NF_SOCKOPT_OPS data item variable? We noticed that in the struct nf_sockopt_ops structure, List is the first member, so its address is the address of the structural variable. More standardized access to data variable addresses should be:
Struct NF_SOCKOPT_OPS * OPS = LIST_ENTRY (I, Struct NF_SOCKOPT_OPS, LIST);
In most cases, you need to get a chain table node data item when traversing the linked list, that is, List_for_each () and list_entry () are always used simultaneously. A list_for_each_entry () macro is given to this linux:
#define list_for_each_entry (POS, Head, Member) ... Unlike list_for_each (), the POS here is the data item structure pointer type, not (struct list_head *). NF_REGISTER_SOCKOPT () functions can be designed with this macro:
... Struct NF_SOCKOPT_OPS * OPS; List_for_each_entry (OPS, & NF_SOCKOPTS, LIST) {...} ......
Some applications require reverse traversal lay lists, Linux provides list_for_each_prev () and list_for_each_entry_reverse () to complete this operation, use the method and list_for_each (), list_for_each_entry () is identical.
If the traversal is not from the linked watch, it can be used from a known node POS, and list_for_each_entry_continue (POS, Head, Member) can be used. This requires, that is, after a series of calculations, if the POS value is value, start traversing from POS, if not, start from the chain header, for this, Linux provides a list_prepare_entry (POS, Head, MEMBER) ) Macro, the return value as the POS parameter of list_for_each_entry_continue (), can meet this requirement.
4. Safety consideration
In the environment where concurrent execution, the chain operation usually should consider synchronous security issues. For convenience, Linux leaves this to apply yourself. There are two main aspects of the security of the Linux linked list:
a) List_empty () judgment
Basic list_empty () is only to determine whether the linked list is empty, and the Linux linker provides a list_empty_careful () macro, which also determines the NEXT and PREV of the head pointer, only when both point to himself Only returning. This is mainly in order to cope with another CPU that is processing the same chain list, which causes NEXT and prev inconsistent. However, the code annotation is also acknowledged that this security capacity is limited: unless other CPU's linked list is only list_del_init (), otherwise, it is still not guaranteed, that is, it is still necessary to lock protection.
b) Remove the last node
The previous introduction to several macros used for linked lists, which are all the purpose of traversing through mobile POS pointers. However, if the operation of the traversal contains the node pointed to by the POS pointer, the movement of the POS pointer will be interrupted because the List_Del (POS) will put the POS NEXT, PREV, and the special value of List_Position2 and List_Position1.
Of course, the caller can completely caching the next pointer to enable the traversal operation, but for the consistency of programming, the Linux linked list still provides two "_safe" interfaces corresponding to basic traversal operations: list_for_each_safe (POS, N, HEAD) , List_for_each_entry_safe (POS, N, Head, MeMBER), which requires the caller to provide a pointer N with the POS type of POS, temporarily store the address of the next node in the for loop, avoiding the broken due to the release of POS nodes chain.
Fourth, expand
HLIST
Figure 6 List and HLIST
Exquisite Linux Link Sheet Designer (because List.h is not signature, so it is probably Linus Torvalds) Think that the double-headed table of NEXT (PREV) is "too waste" for the Hash table, thus also designed for Hash Table Application HLIST Data Structure - Single Total Header Dual Cyclic Link Watch, can be seen from the above figure, HLIST's header has only one pointer to the first node, and does not point to the pointer to the end node, which may be massive The heads stored in the Hash table can reduce the space consumption of half. Because the data structure of the head and node is different, the insert operation occurs between the head and the first node, the conventional method will not pass: the first pointer of the head must modify the newly inserted node, but can not use List_Add () Such a unified description. To this end, the HLIST node's prev no longer refers to a pointer to a front node, but is NEXT in one node (which may be a header) pointer (Struct List_Head ** PPREV), thus The operation of the header insertion can be accessed and modified by a consistent "Node-> PPREV)".
2. Read-Copy Update
There is also a series of macros ending with "_rcu" in the Linux chain function interface, with many functions described above. RCU (Read-Copy Update) is a new technology introduced in the 2.5 / 2.6 core, which improves synchronous performance by delaying write operations.
We know that the data read operation in the system is far more than write operation, while the RWLock mechanism is rapidly decline in the SMP environment (see Resources 4). In response to this application background, the IBM Linux technology center PAUL E. Mckenney proposes the "read copy update" technology and applies it to the Linux kernel. The core of the RCU technology is written to write-update two steps, allowing the read operation to access any time, when the system is written, the update action has been delayed until all read operations of the data are completed. The RCU feature in the Linux Link is only a small part of the Linux RCU. For the implementation of the RCU, it has exceeded this article, interested readers can refer to the reference information of this article; and how the use of the RCU linked list and the use of basic linked lists basically the same.
V.
The procedures in the attachment have no practical effects in addition to the forward and reverse output files, only to demonstrate the use of the Linux linked list.
For the sake of simplicity, examples are user-state program templates. If you need to run, you can compile the following command:
GCC -D__kernel__ -i / usr / src / linux-2.6.7 / include pfile.c -o pfile
Because the kernel chain is limited, the internal nuclear is used, but in fact for the data structure itself is not only in the nuclear state, the "-d__kernel__" switch "deception" compiler is used in the author's compilation.
Reference
Wikipedia
http://en.wikipedia.org, a network dictionary published in GNU Documentation license, extension of the free software concept, the "Link List" concept of this article uses its version.
2. "Linux Kernel Scenario Analysis", Mr. Mao Decha's masterpiece can hardly answer most of the problem of the kernel, which also includes several key data structures of the kernel list. 3. Linux kernel 2.6.7 source code, all do not understand the problem, as long as you think about the code, you can always be clear.
4. Kernel Korner: USING RCU in The Linux 2.5 Kernel, RCU Main Developer Paul Mckenney October 2003 published in Linux Journal on an article on the article. in
Http://www.rdrop.com/Users/paulmck/rclock/ You can get more about the RCU.
About author
Yangshazhou, currently at the University of Defense Science and Technology University School of Software. Welcome to the technical problems in the text
Pubb@163.net questioning.
Full article:
IBM DeveloperWorks China website
