Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Arlie Stephens]

Hi Folks,

I'm trying to understand the linux way of doing things, so as to write
code which will be easier for experienced linux kernel people to
understand. Yesterday I wound up in a 3 engineer discussion about
something conceptually simple, that just didn't want to be done with
the tools at hand; what's worse, the only ways I could see to do it
were (a) do my own linked lists or (b) write some routines that relied
kind of heavily on the never-mentioned-in-documentation details of
linux/list.h   I'll probably go with option (b), as that seems less
insane, but I thought I might as well ask here as well.

Here's the problem. I have a collection of resources. Call them
A,B,C,D but note that resources get added at run time, so I don't know
how many to expect. I want to go through them in a round robin
fashion, but not all at once. On the first request, I use A. On a
later request I use B, etc. This seems to me to map naturally to a
circular linked list, with a "cursor" - a pointer of some kind to the
next one I want to use. To make my specific situation more
interesting, I actually have multiple cursors - that may or may not
happen to point to the same node at any given time, but usually will
not.

This is where I wish I could draw pictures in ascii emails ;-)
Perhaps the following will come through halfway sanely:

C1 C2 C3
V /    V
A<->B<->C-<->D 
^------------^ 

list.h implements a circular linked list - see for example
http://www.makelinux.net/books/lkd2/app01lev1sec2 - so I thought this
would be easy and natural. But then I discovered there was no such
thing as a list_next(). OK, I can write it - Something like:
cursor->resource = list_entry(cursor->resource->link.next, struct resource, link);
But the fact there was no interface made me ask advice from colleagues.
And that's when the debate erupted. 

First of all, it's unclear whether that would even work. If the list
is initialized following the standard pardigm, there may be a "head"
element embedded in the list, which all the existing interfaces know
to ignore. I.e.

LIST_HEAD(resources);

add_resource(...)
  new_resource = kmalloc(sizeof(struct resource), GFP_KERNEL);
  new_resource->ID = ...
  INIT_LIST_HEAD(&new_resource->link);
  list_add(&new_resource->link, &resources)

It looks as if the circular list is likely to include the variable
named 'resources', so new_resource->link.next might point to resources,
and list_entry(new_resource->link.next, struct resource, link) might
point to whatever unrelated variable happens to be somewhere near 'resources'. 

It's certain that the implementation makes no attempt to clarify what
kind of list it's using ... not when we had 3 experienced engineers
draw 2 different conclusions, one changing his mind midway. 

Obviously I can figure out what the link.h implementation actually
does, and code accordingly. That's my plan for this morning. I'm just
not sure it's going to produce code that other engineers will be
comfortable maintaining. And if they aren't comfortable, there will be
uneccessary bugs. 

So, how would a dyed-in-the-wool linux kernel engineer approach this
task? I.e. what's the natural design pattern here, within linux?
I think it's pretty clear that the one I've come up with seems so
unnatural to the authors of list.h that they never even imagined it. 

Thanks for any insights,

--
Arlie
(Arlie Stephens					arlie at worldash.org)