Kernel Linux List - An Efficient Generic Linked List

Linux Kernel Linked List

Linux Kernel especially in the past years was plenty of different and replicated implementation of generic data structures such as linked lists, stacks and queues.  Kernel's developers decided to provide a unique set of API for using these kind of software machineries. We will briefly look in this article  at the list.h file (in the linux source tree under /usr/src/linux-headers-`uname -r`/include/) that provides macros and function for utilizing a doubly linked circular list. It is a very smart written piece of code that is worth to take a look at as it is  an opportunity  to improve  C programming skills and at the same time to see an "unconventional" implementation for a common data structure.

From canonical list to Linux kernel linked list

The canonical implementation of a C's linked list consists of a structure and two (for a doubly linked) recursive pointer fields to the structure itself. The links to the previous and subsequent element of the list.


struct point2DNode{
 int x,y;
 struct point2DNode* prev, next;
};

The drawback of this approach is that in order to manipulate that list one have to write type specific code for adding/removing nodes in/from the list.

Usage and implementation

Creation

To overcome this problem list in the kernel are implemented s.t. to use them one has just to add a field of type struct list_head inside the structure we want the list to be made of.

struct list_head is defined as follow :

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

With that in mind our kernel point2D list would be

struct point2D{
 int x,y;
 struct list_head list;
};

The first thing to do in order to utilized it is to create a list head, a start point for the data structure. This could be accomplished using the macro

LIST_HEAD(listStart)

internally defined as

 

 #define LIST_HEAD(name) \
     struct list_head name =LIST_HEAD_INIT(name)

 #define LIST_HEAD_INIT(name) { &(name), &(name) }

 

that simply create a single node linked list.
Note that is clear from here that one can also declare a point2D as start point and initialize directly its list_head field by means of the LIST_HEAD_INIT macro. Out list is now ready to be filled out with "nodes" that can be added to the list using different functions (to the front, or tail for instance, useful for using the list for implementing other data structures as stacks or queues). For example we will use the list_add function provided that add the new node right after the head of the list. Let's add some points (representing the function       ) to our freshly created list:

LIST_HEAD(listStart);
struct point2D* tmp;
 int i=0;
 for(;i<LIMIT;i++){
  tmp = malloc(sizeof(struct point2D));
  tmp->x=i;
  tmp->y=i*i;
  INIT_LIST_HEAD(&tmp->list);
  list_add(&(tmp->list),&listStart);
 }

where

 /*
  * Insert a new entry between two known consecutive  entries.
  *
  * This is only for internal list manipulation where  we know
  * the prev/next entries already!
  */
 static inline void __list_add(struct list_head  *new,
  struct list_head *prev,
  struct list_head *next)
 {
  next->prev = new;
  new->next = next;
  new->prev = prev;
  prev->next = new;
 }

 /**
  * list_add - add a new entry
  * @new: new entry to be added
  * @head: list head to add it after
  *
  * Insert a new entry after the specified head.
  * This is good for implementing stacks.
  */
 static inline void list_add(struct list_head *new,        struct list_head *head)
 {
  __list_add(new, head, head->next);
 }

the list_add function relies on the internal __list_add function defined above. Note that it accept two parameter and it will insert the first parameter just after the second (if we pass as second parameter the head we are actually implementing a stack). Another function

 void list_add_tail(struct list_head *new, struct  list_head *head);

insert the new node right before the second parameter (useful for implementing queues). We have just created our linked list and now we are ready to loop over it. The kernel implementation provide a macro that make the iteration easy:

Iterate over the list

/**
 * list_for_each-iterate over a list
 * @pos:the &struct list_head to use as a loop counter.
 * @head:the head for your list.
 */
 #define list_for_each(pos, head) \
 for (pos = (head)->next; pos != (head); pos = pos->next)
 

But as you may have noticed the loop is now over the struct list_head so, how can one retrieve the embedding structure (a some point we would like to access linked lists' node fields).
Using the list_entry function provided is the answer.

/**
 * list_entry - get the struct for this entry
 * @ptr:the &struct list_head pointer.
 * @type:the type of the struct this is embedded in.
 * @member:the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
  ( (type *)( (char *)(ptr)-(unsigned long)(&( (type *) 0 )->member) ) )

here the ptr pointer is a pointer within our loop pointing the current struct list_head element, type is the typename of the embedding structure (in our example point2D) and member is the name of the struct list_head inside the point2D structure.
How does it intuitively works? Well the field struct list_head is at a certain offset from the beginning of the embedding structure point2D. This offset is simply computed casting a null pointer to our point2D structure &( (type *)0)->member) ) and accessing the member field (internally this acces is just an offset calculation from the beginning of the structure, pointer arithmetic). This offset is substracted to the actual address of the list_head pointer inside the current point2D element (For more information refear to this article). We have now our node, ready to be used.

Here an example of usage.

 struct list_head* current;
 struct point2D* currPoint;
//prints out all the points2D currently in the list
  list_for_each(current, &listStart){
    currPoint = list_entry(current,struct point2D,list);
    printf("x=%d, y=%d\n",currPoint->x,currPoint->y);
  }

It is important to note here that this kind of lists permit very easily for a struct to be part of several lists at the same time (using several pointer to list_head)

However, this article shows just a very basic usage of the API that actually counts many many other function for deleting nodes, merging or splitting lists and many others. The source code is well commented and documented.

A ready to use (stripped from kernel dependent code) is downloadable from here.

ap01fig04

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>