crap, i think LKD3 explains linked list head nodes incorrectly ...

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



  ... and this might be embarrasing for me since i might have been the
one who dashed off the explanation for it to the author.

  if you have a copy of LKD3, on p. 90, a linked list "head" node is
described as "a special pointer that refers to your linked list,
without being a list node itself."

  i'm pretty sure that second part is incorrect as a kernel LL head
node *is* a member of the list, albeit it's a list member that has to
be treated specially.

  according to the code, an empty kernel LL is defined by a "struct
list_head", both of whose pointers point back to itself.  this should
be obvious from the test for an empty list in the header file
<linux/list.h>:


static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}


  and the other thing to notice about a LL's head node is that it has
no enclosing payload -- you should never try to "dereference" the head
node with "container_of()" to get at the surrounding data structure
since there is none.  this should be obvious if you look at the macro
for iterating over a list starting with its head node:


#define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)


note how that iteration macro, given a list head, starts iterating at
the *next* item in the list, and stop when it gets back to the head,
*** without ever processing the head node itself ***.  in short, while
a head node *is* just another "struct list_head" on a linked list, it
must always be recognized as the head node of the list to make sure
you never try to *process* it as a normal list entry.

  that also suggests that a passage on p. 91 of LKD3 is inaccurate,
where it claims that "because the lists are circular, you can
generally pass any element for head."  but that can't be right, since
you must *always* keep track of the head node for any list, to avoid
processing it normally.  if you simply drop someone into the middle of
a circular, doubly-linked kernel list, there is no way that i can see
to know which node in that list is the head node when you run across
it during iteration.

  does this make sense?

rday

-- 

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

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

--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx
Please read the FAQ at http://kernelnewbies.org/FAQ



[Index of Archives]     [Newbies FAQ]     [Linux Kernel Mentors]     [Linux Kernel Development]     [IETF Annouce]     [Git]     [Networking]     [Security]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux RAID]     [Linux SCSI]     [Linux ACPI]
  Powered by Linux