| Message ID | 1370280485-10047-2-git-send-email-joern@logfs.org (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, 6 June 2013 22:32:55 +0300, Andy Shevchenko wrote: > On Mon, Jun 3, 2013 at 8:28 PM, Joern Engel <joern@logfs.org> wrote: > > I have seen a lot of boilerplate code that either follows the pattern of > > while (!list_empty(head)) { > > pos = list_entry(head->next, struct foo, list); > > list_del(pos->list); > > ... > > } > > or some variant thereof. > > What the problem to use list_for_each_safe()? The loop may terminate with elements left on the list. There is more, but I would consider this the main problem. Jörn -- If you're willing to restrict the flexibility of your approach, you can almost always do something better. -- John Carmack -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Jun 3, 2013 at 8:28 PM, Joern Engel <joern@logfs.org> wrote: > I have seen a lot of boilerplate code that either follows the pattern of > while (!list_empty(head)) { > pos = list_entry(head->next, struct foo, list); > list_del(pos->list); > ... > } > or some variant thereof. What the problem to use list_for_each_safe()? -- With Best Regards, Andy Shevchenko -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Jun 6, 2013 at 9:12 PM, Jörn Engel <joern@logfs.org> wrote: > On Thu, 6 June 2013 22:32:55 +0300, Andy Shevchenko wrote: >> On Mon, Jun 3, 2013 at 8:28 PM, Joern Engel <joern@logfs.org> wrote: >> > I have seen a lot of boilerplate code that either follows the pattern of >> > while (!list_empty(head)) { >> > pos = list_entry(head->next, struct foo, list); >> > list_del(pos->list); >> > ... >> > } >> > or some variant thereof. >> >> What the problem to use list_for_each_safe()? > > The loop may terminate with elements left on the list. There is more, > but I would consider this the main problem. I didn't quite get what you mean. list_for_each_safe() and list_for_each_entry_safe() traverse across list. User actually decides when the proper time to remove an element from the list. I'm sorry, I didn't see any advantages from list_for_each_del() (or entry variant). -- With Best Regards, Andy Shevchenko -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, 6 June 2013 22:49:22 +0300, Andy Shevchenko wrote: > On Thu, Jun 6, 2013 at 9:12 PM, Jörn Engel <joern@logfs.org> wrote: > > On Thu, 6 June 2013 22:32:55 +0300, Andy Shevchenko wrote: > >> On Mon, Jun 3, 2013 at 8:28 PM, Joern Engel <joern@logfs.org> wrote: > >> > I have seen a lot of boilerplate code that either follows the pattern of > >> > while (!list_empty(head)) { > >> > pos = list_entry(head->next, struct foo, list); > >> > list_del(pos->list); > >> > ... > >> > } > >> > or some variant thereof. > >> > >> What the problem to use list_for_each_safe()? > > > > The loop may terminate with elements left on the list. There is more, > > but I would consider this the main problem. > > I didn't quite get what you mean. Take two threads, one doing a list_for_each_entry_safe loop and dropping the lock after list_del, the other doing list_add. Result is that you finish the list_for_each_entry_safe loop with something remaining on the list. spin_lock list_for_each_entry_safe list_del spin_unlock spin_lock list_add spin_unlock If you search for this pattern in the kernel, you won't find too many examples. Quite likely that is because a) people realized this and used a while (!list_empty()) loop to begin with or b) they started out wrong and fixed the bug later. Not sure how many examples of b) there are. At any rate, this is a purely janitorial patch. It is almost by definition of moderate utility and if there is significant opposition or the patch actually causes harm in some way, we should drop it. Jörn -- Time? What's that? Time is only worth what you do with it. -- Theo de Raadt -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Jun 7, 2013 at 7:36 PM, Jörn Engel <joern@logfs.org> wrote: > On Thu, 6 June 2013 22:49:22 +0300, Andy Shevchenko wrote: >> On Thu, Jun 6, 2013 at 9:12 PM, Jörn Engel <joern@logfs.org> wrote: >> > On Thu, 6 June 2013 22:32:55 +0300, Andy Shevchenko wrote: >> >> What the problem to use list_for_each_safe()? >> > >> > The loop may terminate with elements left on the list. There is more, >> > but I would consider this the main problem. >> >> I didn't quite get what you mean. > > Take two threads, one doing a list_for_each_entry_safe loop and > dropping the lock after list_del, the other doing list_add. Result is > that you finish the list_for_each_entry_safe loop with something > remaining on the list. > > spin_lock > list_for_each_entry_safe > list_del > spin_unlock Who is doing such thing? Usually if you unlock, you exit from function, or you already done iteration through the list. Like lock() list_for_each_safe() { if (condition) { list_del() unlock() return; } } unlock() return; In case you have to do unlock()/lock() routine inside iteration you always can do an additional check at the end list_for_each_safe() { unlock(); lock(); } if (!list_empty()) { do_smth() } unlock(); Thus, I don't see how list*del will help. > If you search for this pattern in the kernel, you won't find too many > examples. Quite likely that is because a) people realized this and > used a while (!list_empty()) loop to begin with or b) they started out > wrong and fixed the bug later. Not sure how many examples of b) there > are. -- With Best Regards, Andy Shevchenko -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, 7 June 2013 21:30:16 +0300, Andy Shevchenko wrote: > > > > spin_lock > > list_for_each_entry_safe > > list_del > > spin_unlock > > Who is doing such thing? Replace list_for_each_entry_safe with 'while (!list_empty(...))' and just grep. My patch is about 'while (!list_empty(...))', not about list_for_each_entry_safe. Jörn -- There are three principal ways to lose money: wine, women, and engineers. While the first two are more pleasant, the third is by far the more certain. -- Baron Rothschild -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Jun 7, 2013 at 9:48 PM, Jörn Engel <joern@logfs.org> wrote: > On Fri, 7 June 2013 21:30:16 +0300, Andy Shevchenko wrote: >> > >> > spin_lock >> > list_for_each_entry_safe >> > list_del >> > spin_unlock >> >> Who is doing such thing? > > Replace list_for_each_entry_safe with 'while (!list_empty(...))' and > just grep. My patch is about 'while (!list_empty(...))', not about > list_for_each_entry_safe. I saw your patch against btrfs. I didn't see locking there. Any excerpt like while (!list_empty(&prefs)) { ref = list_first_entry(&prefs, struct __prelim_ref, list); list_del(&ref->list); could be transformed to struct __prelim_ref *_ref; list_for_each_entry_safe(ref, _ref, &prefs, list) { list_del(&ref->list); ... } but is it worth to do? (Same question to your approach) I see two potential issues with while_list_drain_entry() or whatever name you like: - you delete list as a first operation - you limit user to think in that way, if you choose deletion as last operation, who will go to free resources (call kfree() for example)? - you always use the same ordering (list_first_entry() call), someone may not be satisfied by that So, the approach with while (!list_empty()) { e = list_entry(); list_del(&e->list); ... } actually not bad. If there any bugs in code, better to fix those bugs explicitly. What do I not understand? -- With Best Regards, Andy Shevchenko -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/list.h b/include/linux/list.h index 6a1f8df..e09fe10 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -361,6 +361,17 @@ static inline void list_splice_tail_init(struct list_head *list, #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member) +static inline struct list_head *list_first_del(struct list_head *head) +{ + struct list_head *item; + + if (list_empty(head)) + return NULL; + item = head->next; + list_del(item); + return item; +} + /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. @@ -483,6 +494,28 @@ static inline void list_splice_tail_init(struct list_head *list, pos = list_entry(pos->member.next, typeof(*pos), member)) /** + * list_for_each_remove - iterate over a list, deleting each entry + * @pos: the &struct list_head to use as a loop cursor. + * @head: the head of your list. + * + * Calls list_del() on pos on each iteration + */ +#define list_for_each_del(pos, head) \ + while ((pos = list_first_del(head))) + +/** + * list_for_each_entry_remove - iterate over a list of given type, deleting each entry + * @pos: the type * to use as loop cursor. + * @head: the head of your list. + * @member: the name of the list_struct within the struct + * + * Calls list_del() on pos on each iteration + */ +#define list_for_each_entry_del(pos, head, member) \ + while (pos = list_entry(list_first_del(head), typeof(*pos), member), \ + &pos->member) + +/** * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry * @pos: the type * to use as a loop cursor. * @n: another type * to use as temporary storage
I have seen a lot of boilerplate code that either follows the pattern of while (!list_empty(head)) { pos = list_entry(head->next, struct foo, list); list_del(pos->list); ... } or some variant thereof. With this patch in, people can use list_for_each_entry_del(pos, head, list) { ... } The patch also adds a list_for_each_del variant, even though I have only found a single user for that one so far. Signed-off-by: Joern Engel <joern@logfs.org> --- include/linux/list.h | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+)