after digging around in the linked list code, i'm more confident i see what's happening, but now i have a new confusion. first, as an earlier poster pointed out, all of the elements in a kernel linked list are *not* equivalent -- each list has an additional data-free entry (call it the "head"). so all those claims that you can treat a linked list equivalently no matter where you start traversing are simply untrue. consider the traversal macro __list_for_each: #define __list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) that traversal *clearly* excludes the starting (head) element, so that traversal macro is only valid if you *always* start at that head element, and nowhere else in the list. that there is a data-free head element is even more obvious when you consider the macro that checks for an empty list: static inline int list_empty(const struct list_head *head) { return head->next == head; } as you can see, an "empty" list is one with exactly one element -- the "head", whose link pointers point back to itself. so i believe we've established the structure of a kernel linked list, which brings us to splicing. consider this macro, which "splices" the contents of a non-empty list into another list: ===== static inline void __list_splice(struct list_head *list, struct list_head *head) { struct list_head *first = list->next; struct list_head *last = list->prev; struct list_head *at = head->next; first->prev = head; head->next = first; last->next = at; at->prev = last; } ===== take a minute or two and follow the code -- it takes the list referred to by the first argument (which has to be the "head" element of that list for this to make any sense), unlinks it from that "list" head element, and adds it into the list referred to by "head". in short, all of the "list" list is spliced into the "head" list, with the exception of the "list" head element itself, which is left dangling out in space, no longer needed. so far, so good? now, if you start traversing at "head", sure enough, you'll run through *all* of the elements, ending up back at head. good. but what about that lonely "list" head element that was left behind? what it *it* pointint to? well, what it's pointing to is really unsafe. since the fields of that "list" head element were unchanged by the above, the prev and next pointers are both still pointing at valid list elements ... *which are now part of a different list*! in other words, if you were to try to traverse a list starting with that "list" head element, you would immediately follow the pointer to the new list, traverse it entirely ... and you would keep traversing forever, since you're now on the new list and there's no pointer that takes you back to the original head element, which is the only way the traversal loop stops. can you see that? of course, one can always say that, if you splice a list into another one, you really shouldn't try to do anything with that first header again anyway. and maybe you shouldn't, but that's not the point -- the point is that you've left an obviously dangerous structure lying around that continues to contain valid pointers and that, if you try to traverse, bad things will happen (as long as i'm reading this correctly). an obvious fix is, once you do the splice, initialize that list header to designate an empty list, and in fact, there's a list function that does just that: ===== static inline void list_splice_init(struct list_head *list, struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); INIT_LIST_HEAD(list); <-- that solves the problem } } ===== which makes me wonder ... why aren't *all* list splices treated that way? what is the value of using just the first form and leaving that potentially dangerous head element lying around? in short, as long as i've understood this correctly, it would seem to make more sense for all list_splice() calls to be list_splice_init() instead, for safety. or did i screw something up? rday -- ======================================================================== Robert P. J. Day Linux Consulting, Training and Annoying Kernel Pedantry: Have classroom, will lecture. http://crashcourse.ca Waterloo, Ontario, CANADA ======================================================================== -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ