Design Patterns in Linux Kernel: Fancy Tricks With Linked Lists
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@worldash.org)
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-let... rday
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
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@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
-- Thank you Warm Regards Anuz
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@worldash.org)
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
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
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@worldash.org)
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 ========================================================================
"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.
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 ========================================================================
participants (5)
-
Anuz Pratap Singh Tomar -
Arlie Stephens -
Dave Hylands -
Greg Freemyer -
Robert P. J. Day