Linux Kernel Queues
My senior design project for university has involved a lot of working in the Linux kernel. I’ve found that my primary difficulty with kernel work has been figuring out how the mass of code that already exists works and interacts with each other. It’s mostly very well thought out, but some things take a little time to wrap your head around. One such thing is the kernel’s unified implementation of linked lists.
It’s actually rather ingenious if you think about it, and there are plenty of references that give great explanations of how it all works, so I won’t do that here. The short version is that the list actually acts like an element within another data structure, which allows it to work for all types, rather than having to create new structures and functions for every structure to act like a list. What I recently found myself trying to do was create a queue (first-in-first-out) data structure using the linked lists provided. I decided to go about this after getting a little advice from a couple of fellas over at Stack Overflow. I haven’t fleshed it all out yet, but came to an important realization on how things work. It’s not really all that hard, but it was important enough for me to want to document: because it is a circular, doubly-linked structure, adding an item to the front and back of the list look very similar. In fact, they’re pretty much the same operation, except for where the external head and tail pointers point to. They’re so similar that I spent a bunch of time confused on how it all worked. I suppose that’s my fault for delving in and examining the overly-short elegant code.
The result of this is that their list_add_tail() function (which is commented to be useful for queues) is, in fact, useful for queues. It adds an element linked after the “last” element and before the “first,” given the head of the list. “Last” and “first” are in quotes here because it’s a circular list, so there technically aren’t a first and last, but there are. Anyway, what I still don’t quite understand is how the list_add() function is useful for stacks (also in the comments). Though I’m getting myself slightly confused just thinking about it further, so I’ll end the tirade here.
I guess if there’s one thing I can pass on here, it’s that if there’s comments documenting a series of functions (which the kernel’s include/linux/list.h file does), listen to the comments. I suppose this was a learning experience for me in the end, but I could have saved a bunch of time by just trusting what they said the functions do. On the flip side, if you’re curious, don’t trust them, and want to be sure about what the code is doing, you are always free to dive right in! I’m just convinced that the kernel developers are a lot smarter than I am, at least at this point in my career.
Related Links
- Linux Kernel Linked List Explained
- Another Kernel Linked List Explanation
- Stack Overflow question about kernel queues
- list.h on Linux Cross Reference
