Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Dave Hylands]

Hi Arlie,


On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie at worldash.org> wrote:
>
> 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.

So the real secret is that it's a circular list with a dummy node. This
dummy node just has head/tail pointers and nothing else.

So when you're advancing through the list, instead of testing list->next
for NULL you check to see if list->next is equal to the list head.

So if you want your cursor object to be self-contained, then it should
include both a list head and a list current.

If you want your cursor to be generic, then it should probably look
something like:

struct list_cursor {
    struct list_head *list;
    struct list_head *curr;
};

I think you'll find that the cursor operations make a lot more sense if you
keep the cursor generic and try not to include the type information about
the list node.

To initialize the cursor:

cursor->list = somelist
cursor->curr = somelist

To advance to the first node (remember the list has a dummy head node)

cursor->curr = cursor->curr->next

If the result is == cursor->head then there aren't any nodes except for the
dummy node (i.e. list is empty)

To get at the actual entry, use list_entry as per usual.

I see RPDay has posted the link to his little tutorial, and I was going to
do the same, but I didn't have it saved anywhere. I highly recommend
reading through that.

--
Dave Hylands
Shuswap, BC, Canada
http://www.davehylands.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20130319/753679a6/attachment.html