Friday, September 01, 2006

Linux kernel linked List Implementation

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...

Thursday, August 31, 2006

[off-topic]Hope One Day I Would Be..

I am alwayes very much keen to do my Ph.D in Operating System( It could be Real Time Opearating System also). I don't know when i will get chance to fulfill my dream. But i should do..i must do.. so now i have to prepare myself. But How? While I was thinking , i thouht first i have to find out what should i need? ...i could prepare a list like ..i need extensive knowledge , i have to do hard work, i have to read countless books or I have to ........................................................But first i could guess that , i should know how to do research ...while i was searching , i got a fantastic link which i should share with you...Have a look on this link
Advice on Reserch and Writing
You could visit this page. It's one of my research interest area...
CS Columbia University's Professor Erez Zadok Page

Tuesday, August 29, 2006

How to install GNU/Linux without any removal media

If you want to install GNU/Linux withoutany removal media(CD, USB, Floppy) then please cheack out
this given link.You need to just copy the (small) Linux installer on a hard disk and run it from your previous operating system. Finish using the network. That's all. In some cases you can substitute the network by a (big) hard disk if your network is not good..

LINK

Monday, August 28, 2006

Intrusion Detection System

We were searching for an efficient intrusion detection system. .We wanted to develop some differnt kind of system which can perform as a detection and prevention system.After a long time discussion and searching in the net, we finalized ythis approch..

In our system , We have two module. One from userspace called detection system.Another from kernel space called prevention system.System acts like

When packets come from the network to NIC, we capture the packets and send to the userspace program.
Still we are thinking to avoid IP stack for passing each packets to user space.Any way , a user space detection program checks the each and every packets and try to match with predefined rule. If this match happens then detection system calculates the rate of packets whichs falls under this rules. If it overtakes the thresold value then this packet address would be written into a configuration file and immediately send to the kernel module which is ruuning in kernel space. So next time if this type of packets is comming into the NIC, before passing to the network stack, our kernel module will drop theses packets. This procedure will occour recuresively and best way to name this project .....

" Knowledge based intrusion detection and prevention system"
While searching , i got very good metirial from net which i should mention here for further look up:

linux 2.4 Packet Filtering
Writing Network device Driver
Inside the Linux Packet Filter Part 1
Inside the Linux Packet Filter Part II

i will add more......