Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

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)

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Robert P. J. Day]

Quoting Arlie Stephens <arlie@worldash.org>:

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

... snip ...

http://crashcourse.ca/introduction-linux-kernel-programming/intermission-lets-talk-about-linked-lists-and-containerof-free

rday

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

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Anuz Pratap Singh Tomar]

On Tue, Mar 19, 2013 at 3:53 PM, Dave Hylands <dhylands@gmail.com> wrote:

> Hi Arlie,
>
>
>
> On Tue, Mar 19, 2013 at 8:34 AM, Arlie Stephens <arlie@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.
>
> Besides the Robert's link you can also have a look at FAQ on kernel newbies
http://kernelnewbies.org/FAQ/LinkedLists

LDD also covers it
http://www.makelinux.net/ldd3/chp-11-sect-5

There is a good explanation of kernel linked list in Robert Love's book as
well.

 --
> Dave Hylands
> Shuswap, BC, Canada
> http://www.davehylands.com
>
> _______________________________________________
> Kernelnewbies mailing list
> Kernelnewbies at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>
>


-- 
Thank you
Warm Regards
Anuz
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20130319/a0beab40/attachment.html 

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Arlie Stephens]

Hi Dave,

Thank you very much. 

On Mar 19 2013, Dave Hylands wrote:
> 
> Hi Arlie,
> 
[SNIP]

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

It's good to have confirmation of this. 
> 
> 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.

And this feels right, in a way that what I was doing did not. 
> 
> 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.

Good introduction. And a great link at the end. 

Interestingly, part of the debate yesterday probably resulted from one
engineer having Love's 2nd edition, and me having his 3rd
edition. Apparently RPDay pointed out some problems to Love which
resulted in him changing his linked list discussion in his 3rd
edition ;-) 

--
Arlie

(Arlie Stephens						 arlie at worldash.org)

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Robert P. J. Day]

Quoting Arlie Stephens <arlie@worldash.org>:

> Interestingly, part of the debate yesterday probably resulted from one
> engineer having Love's 2nd edition, and me having his 3rd
> edition. Apparently RPDay pointed out some problems to Love which
> resulted in him changing his linked list discussion in his 3rd
> edition ;-)

   Been a while since I re-read my own tutorial, it might merit a bit of
a rewrite. Is there anything about it that seems unclear -- I remember
my own moment of epiphany, "Holy crap, what an interesting way to do it."

   And, yes, if you try to reconcile Love's 2nd and 3rd editions on the
topic, that will not end well. :-)

rday

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Robert P. J. Day]

Quoting "Robert P. J. Day" <rpjday@crashcourse.ca>:

> Quoting Arlie Stephens <arlie@worldash.org>:
>
>> Interestingly, part of the debate yesterday probably resulted from one
>> engineer having Love's 2nd edition, and me having his 3rd
>> edition. Apparently RPDay pointed out some problems to Love which
>> resulted in him changing his linked list discussion in his 3rd
>> edition ;-)
>
>    Been a while since I re-read my own tutorial, it might merit a bit of
> a rewrite. Is there anything about it that seems unclear -- I remember
> my own moment of epiphany, "Holy crap, what an interesting way to do it."
>
>    And, yes, if you try to reconcile Love's 2nd and 3rd editions on the
> topic, that will not end well. :-)

   Oh, crap, I just remembered that even Robert Love's 3rd edition of
"Linux Kernel Development" (aka "LKD3") isn't 100% correct WRT linked
lists. A while back, I started keeping track of typoes/errors/whatever
in LKD3 for the benefit of the eventual LKD4, and I started a page here:

http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3

   Partway down that page, you can see my notes on linked lists:

http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3#Linked_lists

I'm going to have to review what I wrote there to remember why I wrote
it but, from a cursory glance, it appears that I still had complaints
about the presentation in LKD3. So feel free to read that wiki section
in conjunction with LKD3 to figure out what I was babbling about.

rday

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Arlie Stephens]

Hi Robert,

Thank you very much - for your web pages as well as for your responses
in this thread. 

On Mar 19 2013, Robert P. J. Day wrote:
>    Oh, crap, I just remembered that even Robert Love's 3rd edition of
> "Linux Kernel Development" (aka "LKD3") isn't 100% correct WRT linked
> lists. A while back, I started keeping track of typoes/errors/whatever
> in LKD3 for the benefit of the eventual LKD4, and I started a page here:
> 
> http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3
> 
>    Partway down that page, you can see my notes on linked lists:
> 
> http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3#Linked_lists

Beautiful! This page covers everything we were confused about
yesterday. And you are right - I read Love's 3rd edition as more 
ambiguous than wrong, but he does say the "head" node is not a member
of the list, and that's more wrong than ambiguous. Morevover, the
biggest problem with my first implementation was that I believed him.

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

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Victor Buciuc]

On Tue, Mar 19, 2013 at 8:50 PM, Victor Buciuc <victor.buciuc@gmail.com> wrote:
> On Tue, Mar 19, 2013 at 5:34 PM, Arlie Stephens <arlie@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
>> ^------------^
>>
>
> Hi,
>
> Another option might be to not iterate through the list but to simply
> move the element you're processing to the end of the list using
> list_rotate_left[1].
> And you could use list_next_entry[2] to get the next entry after the
> head. You'll
> have to check that the list is empty, tough.
>
> This would cost you some extra operations but you'll use the existing interface.
>
> [1] http://lxr.linux.no/linux+v3.8.3/include/linux/list.h#L214
> [2] http://lxr.linux.no/linux+v3.8.3/include/linux/list.h#L361
>
> Regards,
> Victor Buciuc.

Forgot to send to the list.

Regards,
Victor Buciuc.

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Robert P. J. Day]

On Tue, 19 Mar 2013, Arlie Stephens wrote:

> Hi Robert,
>
> Thank you very much - for your web pages as well as for your responses
> in this thread.
>
> On Mar 19 2013, Robert P. J. Day wrote:
> >    Oh, crap, I just remembered that even Robert Love's 3rd edition of
> > "Linux Kernel Development" (aka "LKD3") isn't 100% correct WRT linked
> > lists. A while back, I started keeping track of typoes/errors/whatever
> > in LKD3 for the benefit of the eventual LKD4, and I started a page here:
> >
> > http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3
> >
> >    Partway down that page, you can see my notes on linked lists:
> >
> > http://www.crashcourse.ca/wiki/index.php/Updates_to_LKD3#Linked_lists
>
> Beautiful! This page covers everything we were confused about
> yesterday. And you are right - I read Love's 3rd edition as more
> ambiguous than wrong, but he does say the "head" node is not a member
> of the list, and that's more wrong than ambiguous. Morevover, the
> biggest problem with my first implementation was that I believed him.

  glad i could help. i have plenty of wiki pages, a lot of which are
probably junk by now that could use either deleting or updating. when
i finish my current contract, i'll take a week and rip all of that
apart and put it back together properly.

rday

-- 

========================================================================
Robert P. J. Day                                 Ottawa, Ontario, CANADA
                        http://crashcourse.ca

Twitter:                                       http://twitter.com/rpjday
LinkedIn:                               http://ca.linkedin.com/in/rpjday
========================================================================

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Greg Freemyer]

"Robert P. J. Day" <rpjday@crashcourse.ca> wrote:

>Quoting Arlie Stephens <arlie@worldash.org>:
>
>> Interestingly, part of the debate yesterday probably resulted from
>one
>> engineer having Love's 2nd edition, and me having his 3rd
>> edition. Apparently RPDay pointed out some problems to Love which
>> resulted in him changing his linked list discussion in his 3rd
>> edition ;-)
>
>  Been a while since I re-read my own tutorial, it might merit a bit of
>a rewrite. Is there anything about it that seems unclear -- I remember
>my own moment of epiphany, "Holy crap, what an interesting way to do
>it."
>
>   And, yes, if you try to reconcile Love's 2nd and 3rd editions on the
>topic, that will not end well. :-)
>
>rday
>

Robert,

I read it briefly yesterday.  I don't recall it having an example like:

Instantiate head pointer
Add 2 or 3 list members
Walk list and printk a object member

I find examples like that make all the difference for me.

Greg
-- 
Sent from my Android phone with K-9 Mail. Please excuse my brevity.

Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists

[Robert P. J. Day]

On Wed, 20 Mar 2013, Greg Freemyer wrote:

> "Robert P. J. Day" <rpjday@crashcourse.ca> wrote:
>
> >Quoting Arlie Stephens <arlie@worldash.org>:
> >
> >> Interestingly, part of the debate yesterday probably resulted from
> >one
> >> engineer having Love's 2nd edition, and me having his 3rd
> >> edition. Apparently RPDay pointed out some problems to Love which
> >> resulted in him changing his linked list discussion in his 3rd
> >> edition ;-)
> >
> >  Been a while since I re-read my own tutorial, it might merit a bit of
> >a rewrite. Is there anything about it that seems unclear -- I remember
> >my own moment of epiphany, "Holy crap, what an interesting way to do
> >it."
> >
> >   And, yes, if you try to reconcile Love's 2nd and 3rd editions on the
> >topic, that will not end well. :-)
> >
> >rday
> >
>
> Robert,
>
> I read it briefly yesterday.  I don't recall it having an example like:

  "it" being ... ?

> Instantiate head pointer
> Add 2 or 3 list members
> Walk list and printk a object member
>
> I find examples like that make all the difference for me.

  i agree completely that a simple picture of an "empty" list showing
that it consisted of an initial "struct list_head" would have been
amazingly useful. i'm in the midst of (fingers crossed) moving my
entire site to a different technology, part of which should support
drawing cool diagrams with a minimum of fuss. at which point most of
my stuff will be totally rewritten. yes, i love diagrams.

rday

-- 

========================================================================
Robert P. J. Day                                 Ottawa, Ontario, CANADA
                        http://crashcourse.ca

Twitter:                                       http://twitter.com/rpjday
LinkedIn:                               http://ca.linkedin.com/in/rpjday
========================================================================