Linked lists in the linux kernel

A couple of days ago I was having to dig through the SCSI mid layer code in the linux kernel, and I came across many uses of struct list_head pointers using the linux kernel’s circular, doubly linked list implementation, which is quite strange the first time you see it, and which I’d forgotten about, not having looked at it in a long time. So I sort of had to re-figure it out, and I thought an explanation of it would make a good blog post, as it is a lot trickier than the linked lists you likely ran across in your college Data Structures class. When you see it being used somewhere in some code without knowing what’s behind it, you will likely find yourself thinking, “How can this work? What the heck is going on here?” But, I also thought, surely someone else has already explained this. And so they have, and done quite a good job of it too.

Linux Kernel Linked List Explained.

A very clever use of the offsetof() macro (which itself is very clever) is at the heart of this linked list implementation.

~ by scaryreasoner on July 25, 2008.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: