struct list_node
RFC PATCH 1/1 struct list_node
The current list.h has the same type for list elements and list heads even though most code and coders treat them as distinct.
I've had a version of list.h (for userspace work) for about a year which uses a different type for nodes and it works very well: code is clearer, and mistakes like list_add() argument reversal are detected. Code which really wants to treat a list node as a head can append ".h".
To avoid a massive flag day, this patch uses gcc's "cast to union" to allow either list_head or list_node in various places.
Notes:
1) A new function in_list() is introduced, equivalent to "list_empty(&e)" but for nodes.
2) The duplicated kerneldoc in list_debug.c is excised.
3) The more obscure list functions have yet to be converted.
include/linux/list.h +70 -26
@@ -22,6 +22,26 @@ struct list_head {struct list_head *next, *prev; }; +/* A list node is the same as the head of the list, but it's useful to +* think of them as a separate type. */ +struct list_node { +struct list_head h; +}; + +/* This allows us to support old style list_head as well as list_node. */ +union list_head_or_node { +struct list_head *_h; +struct list_node *_n; +}; +union list_head_or_node_const { +struct list_head *_h; +struct list_node *_n; +const struct list_head *_ch; +const struct list_node *_cn; +}; +#define __lh (n) (((union list_head_or_node)(n))._h) +#define __clh (n) (((union list_head_or_node_const)(n))._h) +#define LIST_HEAD_INIT (name) { &(name), &(name) }#define LIST_HEAD (name) \
@@ -63,15 +83,15 @@ extern void __list_add(struct list_head* Insert a new entry after the specified head. * This is good for implementing stacks. */ +#define list_add (new, head) list_add_lh(__lh(new), head)#ifndef CONFIG_DEBUG_LIST -static inline void list_add (struct list_head *new,struct list_head *head) +static inline void list_add_lh (struct list_head *new,struct list_head *head) {__list_add (new, head, head->next); }#else -extern void list_add (struct list_head *new,struct list_head *head); +extern void list_add_lh (struct list_head *new,struct list_head *head);#endif -/** * list_add_tail - add a new entry
@@ -81,7 +101,9 @@ extern void list_add(struct list_head *n* Insert a new entry before the specified head. * This is useful for implementing queues. */ -static inline void list_add_tail (struct list_head *new,struct list_head *head) +#define list_add_tail (new, head) list_add_tail_lh(__lh(new), head) +static inline void list_add_tail_lh (struct list_head *new, +struct list_head *head) {__list_add (new, head->prev, head); }
@@ -118,7 +140,9 @@ static inline void __list_add_rcu(struct* the _rcu list-traversal primitives, such as * list_for_each_entry_rcu(). */ -static inline void list_add_rcu (struct list_head *new,struct list_head *head) +#define list_add_rcu (new, head) list_add_rcu_lh(__lh(new), (head)) +static inline void list_add_rcu_lh (struct list_head *new, +struct list_head *head) {__list_add_rcu (new, head, head->next); }
@@ -139,7 +163,8 @@ static inline void list_add_rcu(struct l* the _rcu list-traversal primitives, such as * list_for_each_entry_rcu(). */ -static inline void list_add_tail_rcu (struct list_head *new, +#define list_add_tail_rcu (new, head) list_add_tail_rcu_lh(__lh(new), (head)) +static inline void list_add_tail_rcu_lh (struct list_head *new,struct list_head *head) {__list_add_rcu (new, head->prev, head);
@@ -164,15 +189,16 @@ static inline void __list_del(struct lis* Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */ +#define list_del (entry) list_del_lh(__lh(entry))#ifndef CONFIG_DEBUG_LIST -static inline void list_del (struct list_head *entry) +static inline void list_del_lh (struct list_head *entry) {__list_del (entry->prev, entry->next); entry->next =LIST_POISON1 ; entry->prev =LIST_POISON2 ; }#else -extern void list_del (struct list_head *entry); +extern void list_del_lh (struct list_head *entry);#endif /**
@@ -199,7 +225,8 @@ extern void list_del(struct list_head *e* or call_rcu() must be used to defer freeing until an RCU * grace period has elapsed. */ -static inline void list_del_rcu (struct list_head *entry) +#define list_del_rcu (e) list_del_rcu_lh(__lh(e)) +static inline void list_del_rcu_lh (struct list_head *entry) {__list_del (entry->prev, entry->next); entry->prev =LIST_POISON2 ;
@@ -251,7 +278,8 @@ static inline void list_replace_rcu(stru* list_del_init - deletes entry from list and reinitialize it. * @entry: the element to delete from the list. */ -static inline void list_del_init (struct list_head *entry) +#define list_del_init (e) list_del_init_lh(__lh(e)) +static inline void list_del_init_lh (struct list_head *entry) {__list_del (entry->prev, entry->next);INIT_LIST_HEAD (entry);
@@ -259,10 +287,12 @@ static inline void list_del_init(struct/** * list_move - delete from one list and add as another's head -* @list: the entry to move +* @e: the entry to move * @head: the head that will precede our entry */ -static inline void list_move (struct list_head *list,struct list_head *head) +#define list_move (e, head) list_move_lh(__lh(e), (head)) +static inline void list_move_lh (struct list_head *list, +struct list_head *head) {__list_del (list->prev, list->next);list_add (list, head);
@@ -270,11 +300,12 @@ static inline void list_move(struct list/** * list_move_tail - delete from one list and add as another's tail -* @list: the entry to move +* @e: the entry to move * @head: the head that will follow our entry */ -static inline void list_move_tail (struct list_head *list, -struct list_head *head) +#define list_move_tail (e, head) list_move_tail_lh(__lh(e), (head)) +static inline void list_move_tail_lh (struct list_head *list, +struct list_head *head) {__list_del (list->prev, list->next);list_add_tail (list, head);
@@ -282,11 +313,12 @@ static inline void list_move_tail(struct/** * list_is_last - tests whether @list is the last entry in list @head -* @list: the entry to test +* @e: the entry to test * @head: the head of the list */ -static inline int list_is_last (const struct list_head *list, -const struct list_head *head) +#define list_is_last (e, head) list_is_last_lh(__clh(e), (head)) +static inline int list_is_last_lh (const struct list_head *list, +const struct list_head *head) {return list->next == head; }
@@ -298,6 +330,17 @@ static inline int list_empty(const strucstatic inline int list_empty (const struct list_head *head) {return head->next == head; +} + +/** +* in_list - tests whether element is in a list. +* @entry: the entry to test +* +* Returns false if the list elem was deleted from list (except __list_del) +*/ +static inline int in_list (const struct list_node *entry) +{ +return entry->h.next == &entry->h; }/**
@@ -418,12 +461,13 @@ static inline void list_splice_init_rcu(/** * list_entry - get the struct for this entry -* @ptr: the &struct list_head pointer. +* @ptr: the &struct list_node pointer. * @type: the type of the struct this is embedded in. -* @member: the name of the list_struct within the struct. -*/ -#define list_entry (ptr, type, member) \ - container_of(ptr, type, member) +* @member: the name of the list_node within the struct. +*/ +#define list_entry (ptr, type, member) ({ \ + const typeof(((type *)0)->member) *__mptr = (void *)(ptr); \ + (type *)( (char *)__mptr - offsetof(type,member) );})/** * list_first_entry - get the first element from a list
@@ -481,12 +525,12 @@ static inline void list_splice_init_rcu(* list_for_each_entry - iterate over list of given type * @pos: the type * to use as a loop cursor. * @head: the head for your list. -* @member: the name of the list_struct within the struct. +* @member: the name of the list_node within the struct. */ #define list_for_each_entry (pos, head, member) \ for (pos = list_entry((head)->next, typeof(*pos), member); \ - prefetch(pos->member.next), &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) + prefetch(__clh(&pos->member)->next), __clh(&pos->member) != (head); \ + pos = list_entry(__clh(&pos->member)->next, typeof(*pos), member))/** * list_for_each_entry_reverse - iterate backwards over list of given type.
lib/list_debug.c +4 -18
@@ -39,27 +39,13 @@ void __list_add(struct list_head *new, }EXPORT_SYMBOL (__list_add); -/** -* list_add - add a new entry -* @new: new entry to be added -* @head: list head to add it after -* -* Insert a new entry after the specified head. -* This is good for implementing stacks. -*/ -void list_add (struct list_head *new,struct list_head *head) +void list_add_lh (struct list_head *new,struct list_head *head) {__list_add (new, head, head->next); } -EXPORT_SYMBOL (list_add); +EXPORT_SYMBOL (list_add_lh); -/** -* list_del - deletes entry from list. -* @entry: the element to delete from the list. -* Note: list_empty on entry does not return true after this, the entry is -* in an undefined state. -*/ -void list_del (struct list_head *entry) +void list_del_lh (struct list_head *entry) {if (unlikely (entry->prev->next != entry)) { printk(KERN_ERR "list_del corruption. prev->next should be %p, "
@@ -75,4 +61,4 @@ void list_del(struct list_head *entry) entry->next =LIST_POISON1 ; entry->prev =LIST_POISON2 ; } -EXPORT_SYMBOL (list_del); +EXPORT_SYMBOL (list_del_lh);
Quoted 8 lines · On Sun, 10 Jun 2007 15:11:30 +1000 Rusty Russell wrote:
The current
list.hhas the same type for list elements and list heads even though most code and coders treat them as distinct.I've had a version of
list.h(for userspace work) for about a year which uses a different type for nodes and it works very well: code is clearer, and mistakes likelist_add()argument reversal are detected. Code which really wants to treat a list node as a head can append ".h".
Quoted 6 lines
To avoid a massive flag day, this patch uses gcc's "cast to union" to allow either
list_headorlist_nodein various places.Notes:
1) A new functionin_list()is introduced, equivalent to "list_empty(&e)" but for nodes.
in_list() sounds like it would scan an entire list and return true if &e is found, false if &e is not found...
and that's what the short description sounds like to me as well...
I'm just confuzed. And you aren't supposed to write confuzing interfaces. :)
Quoted 5 lines
+/**
+ *in_list- tests whether element is in a list.
+ * @entry: the entry to test
+ *
+ * Returns false if the list elem was deleted from list (except__list_del)
What is "elem"? How can this function determine is a list element was deleted vs. was never added?
include/linux/list.h static inline int list_empty(const struc · line 344
Quoted 5 lines
+ */
include/linux/list.h +3
-0+static inline int in_list (const struct list_node *entry) +{ +return entry->h.next == &entry->h; }
---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***
Linus Torvalds
NAKQuoted 3 lines · Rusty Russell
The current
list.hhas the same type for list elements and list heads even though most code and coders treat them as distinct.
I think the old list.h is technically superior to yours.
Exactly *because* nodes and heads are interchangeable.
In fact, you are incorrect that "most code" treat them as distinct. Most code that uses list.h in fact uses it as a list of entries, often without any head at all (and each *entry* is a point of removal), because the way to actually *find* the structure that contains the lists is separate from the lists themselves.
In other words, I think your patch is HORRIBLY BAD, because it totally obscures the beauty of the current list.h implementation, and makes it be something *average*.
The Linux kernel list.h is _better_ than most stupid list implementations that think that a head node is different from the list node. Exactly because it very naturally supports the notion of "this structure exists in a 'ring of entries'" where each node is 100% equivalent to any other node, and there _is_ no head.
And your patch totally misunderstands that, and breaks it.
Nack.
Linus
Quoted 6 lines · Linus Torvalds
The Linux kernel
list.his _better_ than most stupid list implementations that think that a head node is different from the list node. Exactly because it very naturally supports the notion of "this structure exists in a 'ring of entries'" where each node is 100% equivalent to any other node, and there _is_ no head.
Btw, to extend a bit on this: there actually *is* a "list with a head" implementation in <linux/list.h>, called "hlist".
Now, the "h" actually historically stands for "hash", but if you prefer, you can think of it as standing for "head", and be happy.
And if you want a head, you really do want to use "hlist", since the head is smaller than a list entry (a single pointer rather than two).
And yes, I'm sure we could change some "struct list" users to "struct hlist" if you wanted to.
Linus
Quoted 2 lines · Linus Torvalds
And if you want a head, you really do want to use "hlist", since the head is smaller than a list entry (a single pointer rather than two).
No, now you're entirely missing the point.
The normal Linux lists are beautiful, and should be used! I share your enthusiasm for them.
They could just use a little more type safety for the common case. That is all.
Hope that clarifies,
Rusty.
Quoted 8 lines · Linus Torvalds
Quoted 3 lines · Rusty Russell
The current
list.hhas the same type for list elements and list heads even though most code and coders treat them as distinct.I think the old
list.his technically superior to yours.
Quoted 7 lines
Exactly *because* nodes and heads are interchangeable.
In fact, you are incorrect that "most code" treat them as distinct. Most code that uses
list.hin fact uses it as a list of entries, often without any head at all (and each *entry* is a point of removal), because the way to actually *find* the structure that contains the lists is separate from the lists themselves.
Sorry, do you really believe a ring is "often" the case? It's not entirely trivial to audit, but I can do a random sample of 100 list_heads.
The list iterators reinforce the "standalone head" model (ie. it's not called list_for_each_other_entry), and they're pretty popular.
Quoted 5 lines
The Linux kernel
list.his _better_ than most stupid list implementations that think that a head node is different from the list node. Exactly because it very naturally supports the notion of "this structure exists in a 'ring of entries'" where each node is 100% equivalent to any other node, and there _is_ no head.
I agree it's a wonderful feature, but you talk about "no head" but they're all called "list_head"? In my version, they'd all be list_node, and you can trivially treat it as a head with ->h.
It's a little more work for rings, but it's more explicit and gives us type checking on the common case.
Thanks for your consideration,
Rusty.
Quoted 11 lines · Rusty Russell
include/linux/list.h +10
-0+/* A list node is the same as the head of the list, but it's useful to +* think of them as a separate type. */ +struct list_node { +struct list_head h; +}; + +/* This allows us to support old style list_head as well as list_node. */ +union list_head_or_node { +struct list_head *_h; +struct list_node *_n;
include/linux/list.h struct list_head { · line 44
Quoted 10 lines
include/linux/list.h +10
-0+}; +union list_head_or_node_const { +struct list_head *_h; +struct list_node *_n; +const struct list_head *_ch; +const struct list_node *_cn; +}; +#define __lh (n) (((union list_head_or_node)(n))._h) +#define __clh (n) (((union list_head_or_node_const)(n))._h) +
Any reason why you don't use __attribute__ ((transparent_union)) ? I guess this is exactly the case for which it was invented.
Cheers,
Jan