I thought to write about Linux kernel architecture and various components in it. But before digging into that let me introduce you several built-in “code entities” in the Linux kernel .Though it is written in “C” it does not use libc, it got its own entities . As with any large software project, the Linux kernel provides these “code entities” to encourage code reuse. Kernel developers should use these data structures whenever possible and not “roll our own” solutions.
In the following sections, we cover the most useful of these generic data structures and other kernel code components
Linked List:
As you know in “C” , the size of the array is static and inserting a new element in the array ((not at the end 🙂 ) is potentially expensive . Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak.
An array allocates memory for all its elements lumped together as one block of memory. In contrast, a linked list allocates space for each element separately in its own block of memory called a “linked list element” or “node”. The list gets is overall structure by using pointers to connect all its nodes together like the links in a chain.The first element is often represented by a special pointer—called the head.
Types of Linked Lists:
Singly Linked List:
Each node contains two fields: a “data” field to store whatever element type the list holds for its client, and a “next” field which is a pointer used to link one node to the next node.
/* node in a singly linked list */
struct node {
void *data;
struct node *next; /* pointer to the next element */
};
Doubly linked list
In some linked lists, each element also contains a pointer to the previous element.These lists are called doubly linked lists because they are linked both forward and backward.
/* a node in a doubly linked list */
struct node {
void *data; /* the payload */
struct list_element *next; /* pointer to the next element */
struct list_element *prev; /* pointer to the previous element */
};
Circular Linked Lists:
Normally, because the last element in a linked list has no next element, it is set to point to a special value, such as NULL, to indicate it is the last element in the list. In some linked lists, the last element does not point to a special value. Instead, it points back to the first value.This linked list is called a circular linked list because the list is cyclic. Circular linked lists can come in both doubly and singly linked versions. In a circular doubly linked list, the first node’s “previous” pointer points at the last node.
Circular singly linked list:
Circular doubly linked list:
Linux Kernel Linked List implementation:
The Linux kernel’s linked list implementation is unique, it is fundamentally a circular doubly linked list. Using this type of linked list provides the greatest flexibility.
For example , we have a structure like as shown below
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
};
The common pattern for storing this structure in a linked list is to embed the list pointer in the structure as shown below
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
struct todo_tasks *next,*prev;
};
The Linux kernel approach is different. Instead of turning the structure into a linked list, the Linux approach is to embed a linked list node in the structure!
The kernel list code is declared in <linux/types.h> , These are implemented by a single include file <linux/list.h> . There is no separate “.c” file with any library of support routines. All of the code for handling linked lists is simple enough to be implemented using inline functions. Thus it is very easy to use this implementation in any other (GPLv2-licensed) project.
The list_head structure is shown below
struct list_head {
struct list_head *next,*prev;
};
The next pointer points to the next list node, and the prev pointer points to the previous
list node.Yet, seemingly, this is not particularly useful.
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
struct list_head tasks_list
};
With this, tasks_list.next in todo_tasks points to the next element, and taks_list.prev in todo_tasks points to the previous. Now this is becoming useful.
The kernel provides a family of routines to manipulate linked lists. For example, the list_add() method adds a new node to an existing linked list.These methods , are generic and they accept only list_head structures.
So how to find the address of the parent structure containing the kernel lists.?
Kernel uses the below code to do that.
344/** 345 * list_entry - get the struct for this entry 346 * @ptr: the &struct list_head pointer. 347 * @type: the type of the struct this is embedded in. 348 * @member: the name of the list_struct within the struct. 349 */ 350#define list_entry(ptr, type, member) \ 351 container_of(ptr, type, member) 684/** 685 * container_of - cast a member of a structure out to the containing structure 686 * @ptr: the pointer to the member. 687 * @type: the type of the container struct this is embedded in. 688 * @member: the name of the member within the struct. 689 * 690 */ 691#define container_of(ptr, type, member) ({ \ 692 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 693 (type *)( (char *)__mptr - offsetof(type,member) );}) 20#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
Don’t get confused with the above the code snippets it is quite simple and a well-known technique. Given a pointer to struct list_head in a data structure, macro list_entry() simply computes the pointer of the data structure. To achieve this we need to figure out where in the data structure the list_head is (offset of list_head). Then, simply deduct the list_head’s offset from the actual pointer passed to the macro.
Now the question is how can we compute the offset of an element in a structure? Suppose in the above data structure structtodo_tasks to find the offset of element tasks_list in it, this is how you do it:
(unsigned long)(&((struct todo_tasks *)0)->tasks_list)
Take memory address 0, and cast it to whatever the type of structure you have– in this case struct todo_tasks. Then, take the address of the member you’re interested in. This gives the offset of the member within the structure. Since we already know the absolute memory address of this element for a particular instance of the structure (for example in stuct todo_tasks *task1, by way of task1->tasks.list) deducting this offset point us to the address of the structure itself. That’s all there is to it.
To get a better handle on this I suggest you play around with the below code.
#include <stdio.h>
#include <stdlib.h>
struct foobar{
unsigned int foo;
char bar;
char boo;
};
int main(int argc, char** argv){
struct foobar tmp;
printf(“address of &tmp is= %p\n\n”, &tmp);
printf(“address of tmp->foo= %p \t offset of tmp->foo= %lu\n”, &tmp.foo, (unsigned long) &((struct foobar *)0)->foo);
printf(“address of tmp->bar= %p \t offset of tmp->bar= %lu\n”, &tmp.bar, (unsigned long) &((struct foobar *)0)->bar);
printf(“address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n”, &tmp.boo, (unsigned long) &((struct foobar *)0)->boo);
printf(“computed address of &tmp using:\n”);
printf(“\taddress and offset of tmp->foo= %p\n”,
(struct foobar *) (((char *) &tmp.foo) – ((unsigned long) &((struct foobar *)0)->foo)));
printf(“\taddress and offset of tmp->bar= %p\n”,
(struct foobar *) (((char *) &tmp.bar) – ((unsigned long) &((struct foobar *)0)->bar)));
printf(“\taddress and offset of tmp->boo= %p\n”,
(struct foobar *) (((char *) &tmp.boo) – ((unsigned long) &((struct foobar *)0)->boo)));
return 0;
}
Output from this code is:
address of &tmp is= 0xbff43dfc
address of tmp->foo= 0xbff43dfc offset of tmp->foo= 0
address of tmp->bar= 0xbff43e00 offset of tmp->bar= 4
address of tmp->boo= 0xbff43e01 offset of tmp->boo= 5
computed address of &tmp using:
address and offset of tmp->foo= 0xbff43dfc
address and offset of tmp->bar= 0xbff43dfc
address and offset of tmp->boo= 0xbff43dfc
Couple of things to note here about kernel lists.
- You can put struct list_head anywhere in your structure.
- You can name struct list_head variable anything you wish.
- You can have multiple lists!
So for example, the declaration below is also a valid one:
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
int sub_tasks;
int subtasks_completed;
struct list_head completed_subtasks;/* list structure */
int subtasks_waiting;
struct list_head waiting_subtasks; /* another list of same or different items! */
struct list_head todo_list; /* list of todo_tasks */
};
Here are some examples of such lists from the kernel:
http://lxr.linux.no/linux+v3.6/include/linux/fs.h#L692
http://lxr.linux.no/linux+v3.6/include/linux/fs.h#L782
Manipulating Linked Lists:
The kernel provides a family of functions to manipulate linked lists.They all take pointers to one or more list_head structures.The functions are implemented as inline functions in generic C and can be found in <linux/list.h>.
Interestingly, all these functions are O(1).1 This means they execute in constant time, regardless of the size of the list or any other inputs. For example, it takes the same amount of time to add or remove an entry to or from a list whether that list has 3 or 3,000 entries.
For example To add a node to a linked list:
list_add(struct list_head *new, struct list_head *head)
This function adds the new node to the given list immediately after the head node.Because the list is circular and generally has no concept of first or last nodes, you can pass any element for head. If you do pass the “last” element, however, this function can be used to implement a stack.
To add a node to the end of a linked list:
list_add_tail(struct list_head *new, struct list_head *head)
This function adds the new node to the given list immediately before the head node. As with list_add(), because the lists are circular, you can generally pass any element for head. This function can be used to implement a queue, however, if you pass the “first” element.
I think the best way to get familiar with the list functions is to simply scan this file and this kernel.org doc . There are some examples of adding,deleting,traversing through kernel lists here .
References
1) Linux.Kernel.Development.3rd.Edition
2) Linux.Kernel.Primer.A.Top.Down.Approach.for.x86.and.PowerPC.Architectures
3) http://lwn.net/Articles/336255/
4) http://isis.poly.edu/kulesh/stuff/src/klist/
/Suresh
The Linux Desk 