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
