Linked list is a very important data structure which allows large number of storage with efficiant manipulation on data.Most of the kernel code has been written with help of this data structure.So most of the kernel code (data structure) complexity depends on the implementation of that data structure. You could write your own code but the lack of bad design could give you bad performance. A good operating system should give not only stability but also good performance. So i was eager to know how linux implements linked list. Is it circular singly linked list or doubly linked list or circular doubly linked list ?
does It has some libray file where most of the functions would have been declared? Yes my search ends at
"/usr/src/linux/include/linux/list.h".
I could see all types of fuctions are declared here. Before discuss all these function i should tell somthing about how linux kernel adopts strategy to build efficiant implementation.
It has a unique style to implement the traversing,adding,deleting node into a circular link list.As it is circular , you don't need think about head node and last node.You just simple pick up a node and follow the pointers untill you get back the same original.This approch removes the extra head node implementation.So each routine simple needs a pointer to a single element in the list and it could be any element. You may be wondered to see the implementation.Normally we used to declared linked list as like
struct my_list{
int data,
struct my_list *prev;
struct my_list *next;
};
But if want to adopt linux implementation style then you could write like that
struct my_list{
struct list_head list; //linux kernel list implementation//
int data;
};
struct list_head { //Declared in list.h file
struct list_head *next;
struct list_head *prev;
}
Now note the name of the structure "list_node". Linux developers has taken this name in mind from the fact that there is no head node in the list. All node could be acted as a head node .The next pointer points the next element and prev pointer will point the previous pointer.Thanks the linux claver list implementation.You could forget about firat node and last node concept.Just just compare list as a big cycle with no first and last.There are many clever implementation of each function. Please go through the list.h.It is well documented.I thnik i couldn't make better documentation than this. I am sure , you can digest it within one hour.
Now some big questions may come:-)
1.) why should i learn linux kernel linked list implementation strategy though i could write my own code or i can take linked list library from somewhere?
2) How can i use linux linked list library in my user space application? What would be the benefit that i could get if i use this library?
Yes , I am trying to give answer of these two question. If you are not satisfied with my answer . please leave a comment...
Answer No 1:
1) If you want to see yourself as a future linux kernel hacker,you must learn this strategy. I can give a prof from a book "linux Kernel Development" by renowned kernel hacker Robert Love.See the Apendix-A
"All new User must use the exiting interfase,we are serious about this, do not reinvent the wheel"
2) Create various type of Data Structure: You can build any data structure as in your mind.
3) Portability: Otherwise it would not have been placed into main linux kerenl source tree.
4) East to learn. readibility: Yes, It is easy to learn, you can learn all function with one hour rigorious study.
5) Complexity: You would be wonderd that all these functions are O(1), means they execute in costant time regardless of the size of the list.
Answer: Q.No.2:
With some minor modification, You could include this list.h header file into your userspace application. It's a single header file. very handy! You need to do
a)Remove #ifdef __KERNE__ and its #endif
b)Remove all #include line
c)Remove rcu related functions(many of them there)
Yes , I am working on this list to publist my own list.h header file. I have already implemeted generic implementation of my own circular doubly linked list and have written same program with help of "list.h" file and compare
You could also ............
P.S: The kernel uses linked list to store the task list, Each process's task_struct is an element in the linked list.
look at this link...You will automatically understand how many times list_add function have been called:-)
Resource: Section
Yes i used to read from good article.Try to understand from the good article.And ofcouse i should share with you.Have a look
Ref 1: "Linux Kernel Development"-Robert Love Appendix -A
Ref 2: Linux kernel linked list for user space
Ref 3: Linux Kernel Linked List Explained
Happy Hacking...
does It has some libray file where most of the functions would have been declared? Yes my search ends at
"/usr/src/linux/include/linux/list.h".
I could see all types of fuctions are declared here. Before discuss all these function i should tell somthing about how linux kernel adopts strategy to build efficiant implementation.
It has a unique style to implement the traversing,adding,deleting node into a circular link list.As it is circular , you don't need think about head node and last node.You just simple pick up a node and follow the pointers untill you get back the same original.This approch removes the extra head node implementation.So each routine simple needs a pointer to a single element in the list and it could be any element. You may be wondered to see the implementation.Normally we used to declared linked list as like
struct my_list{
int data,
struct my_list *prev;
struct my_list *next;
};
But if want to adopt linux implementation style then you could write like that
struct my_list{
struct list_head list; //linux kernel list implementation//
int data;
};
struct list_head { //Declared in list.h file
struct list_head *next;
struct list_head *prev;
}
Now note the name of the structure "list_node". Linux developers has taken this name in mind from the fact that there is no head node in the list. All node could be acted as a head node .The next pointer points the next element and prev pointer will point the previous pointer.Thanks the linux claver list implementation.You could forget about firat node and last node concept.Just just compare list as a big cycle with no first and last.There are many clever implementation of each function. Please go through the list.h.It is well documented.I thnik i couldn't make better documentation than this. I am sure , you can digest it within one hour.
Now some big questions may come:-)
1.) why should i learn linux kernel linked list implementation strategy though i could write my own code or i can take linked list library from somewhere?
2) How can i use linux linked list library in my user space application? What would be the benefit that i could get if i use this library?
Yes , I am trying to give answer of these two question. If you are not satisfied with my answer . please leave a comment...
Answer No 1:
1) If you want to see yourself as a future linux kernel hacker,you must learn this strategy. I can give a prof from a book "linux Kernel Development" by renowned kernel hacker Robert Love.See the Apendix-A
"All new User must use the exiting interfase,we are serious about this, do not reinvent the wheel"
2) Create various type of Data Structure: You can build any data structure as in your mind.
3) Portability: Otherwise it would not have been placed into main linux kerenl source tree.
4) East to learn. readibility: Yes, It is easy to learn, you can learn all function with one hour rigorious study.
5) Complexity: You would be wonderd that all these functions are O(1), means they execute in costant time regardless of the size of the list.
Answer: Q.No.2:
With some minor modification, You could include this list.h header file into your userspace application. It's a single header file. very handy! You need to do
a)Remove #ifdef __KERNE__ and its #endif
b)Remove all #include line
c)Remove rcu related functions(many of them there)
Yes , I am working on this list to publist my own list.h header file. I have already implemeted generic implementation of my own circular doubly linked list and have written same program with help of "list.h" file and compare
You could also ............
P.S: The kernel uses linked list to store the task list, Each process's task_struct is an element in the linked list.
look at this link...You will automatically understand how many times list_add function have been called:-)
Resource: Section
Yes i used to read from good article.Try to understand from the good article.And ofcouse i should share with you.Have a look
Ref 1: "Linux Kernel Development"-Robert Love Appendix -A
Ref 2: Linux kernel linked list for user space
Ref 3: Linux Kernel Linked List Explained
Happy Hacking...
