About lock-less data structure patches
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): 20110330133411.GA11101@Krystal
A message that is not in the archive (sent off-list or not yet received): [email protected]
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
https://lkml.org/lkml/2011/2/21/15
Quoted 93 lines · Mathieu Desnoyers
Quoted 34 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 33 lines · * Andrew Morton ([email protected]) wrote:
Quoted 20 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 19 lines · Huang Ying
Quoted 17 lines · Andrew Morton
Quoted 5 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.h
vanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Quoted 4 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_node
Why call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Quoted 5 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)
Do we really need to distinguish between lock-free and wait-free from interface? Will we implement both slist_stack_push_lf and slist_stack_push_wf for one data structure?
mutex is needed between multiple "_slist_stack_pop", but not needed between slist_stack_push_lf and _slist_stack_pop. I think it is hard to explain that clearly via function naming.
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)
We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
Quoted 17 lines
include/linux/llist.h line 12
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 11 lines
include/linux/llist.h line 20
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list. Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.
Ok. I will add something like "traversing from head to tail" in the comments.
Quoted 62 lines
Quoted 62 lines
include/linux/llist.h new file +62
-0+* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +*/ + +struct llist_head { +struct llist_node *first; +}; + +struct llist_node { +struct llist_node *next; +}; + +#define LLIST_HEAD_INIT (name) { NULL } +#define LLIST_HEAD (name) struct llist_head name = LLIST_HEAD_INIT(name) + +/** +* init_llist_head - initialize lock-less list head +* @head: the head for your lock-less list +*/ +static inline void init_llist_head (struct llist_head *list) +{ + list->first =NULL ; +} + +/** +* llist_entry - get the struct of this entry +* @ptr: the &struct llist_node pointer. +* @type: the type of the struct this is embedded in. +* @member: the name of the llist_node within the struct. +*/ +#define llist_entry (ptr, type, member) \ + container_of(ptr, type, member) + +/** +* llist_for_each - iterate over some deleted entries of a lock-less list +* @pos: the &struct llist_node to use as a loop cursor +* @node: the first entry of deleted list entries +* +* In general, some entries of the lock-less list can be traversed +* safely only after being deleted from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each (pos, node) \ + for (pos = (node); pos; pos = pos->next) + +/** +* llist_for_each_entry - iterate over some deleted entries of lock-less list of given type +* @pos: the type * to use as a loop cursor. +* @node: the fist entry of deleted list entries. +* @member: the name of the llist_node with the struct. +* +* In general, some entries of the lock-less list can be traversed +* safely only after being removed from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each_entry (pos, node, member) \ + for (pos = llist_entry((node), typeof(*pos), member); \ + &pos->member != NULL; \ + pos = llist_entry(pos->member.next, typeof(*pos), member))
Quoted 8 lines
include/linux/llist.h line 85
Quoted 3 lines
include/linux/llist.h new file +3
-0+ +/** +* llist_empty - tests whether a lock-less list is empty How is this
llist_emptytest expected to be used in combination with other API members ? e.g.llist_del_first,llist_del_all,llist_add? I suspect that without mutex to ensure that there are no concurrent changes,llist_emptyreturn value can easily be non-current.
We don't need llist_empty to be accurate. Just a quick way to test whether list/stack is empty without deleting something from list/stack.
Best Regards,
Huang Ying
Quoted 160 lines
Thanks,
Mathieu
Quoted 156 lines
include/linux/llist.h new file +13
-0+* @head: the list to test +*/ +static inline int llist_empty (const struct llist_head *head) +{ +return head->first ==NULL ; +} + +void llist_add (struct llist_node *new,struct llist_head *head); +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head); +struct llist_node *llist_del_first (struct llist_head *head); +struct llist_node *llist_del_all (struct llist_head *head); +#endif /* LLIST_H */ lib/Kconfig +3
-0@@ -219,4 +219,7 @@ config LRU_CACHE config AVERAGE bool +config LLIST + bool + endmenulib/Makefile +2
-0@@ -110,6 +110,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomi obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_LLIST) += llist.o + hostprogs-y := gen_crc32table clean-files := crc32table.hlib/llist.c new file +119
-0@@ -0,0 +1,119 @@ +/* +* Lock-less NULL terminated single linked list +* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +* +* Copyright 2010 Intel Corp. +* Author: Huang Ying <[email protected]> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License version +* 2 as published by the Free Software Foundation; +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/llist.h> + +#include <asm/system.h> + +/** +* llist_add - add a new entry +* @new: new entry to be added +* @head: the head for your lock-less list +*/ +void llist_add (struct llist_node *new,struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new->next = entry; + }while (cmpxchg (&head->first, entry, new) != entry); +} +EXPORT_SYMBOL_GPL (llist_add); + +/** +* llist_add_batch - add several linked entries in batch +* @new_first: first entry in batch to be added +* @new_last: last entry in batch to be added +* @head: the head for your lock-less list +*/ +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new_last->next = entry; + }while (cmpxchg (&head->first, entry, new_first) != entry); +} +EXPORT_SYMBOL_GPL (llist_add_batch); + +/** +* llist_del_first - delete the first entry of lock-less list +* @head: the head for your lock-less list +* +* If list is empty, return NULL, otherwise, return the first entry deleted. +* +* Only one llist_del_first user can be used simultaneously with +* multiple llist_add users without lock. Because otherwise +* llist_del_first, llist_add, llist_add sequence in another user may +* change @head->first->next, but keep @head->first. If multiple +* consumers are needed, please use llist_del_all. +*/ +struct llist_node *llist_del_first (struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; +if (entry ==NULL ) +return NULL ; + }while (cmpxchg (&head->first, entry, entry->next) != entry); + +return entry; +} +EXPORT_SYMBOL_GPL (llist_del_first); + +/** +* llist_del_all - delete all entries from lock-less list +* @head: the head of lock-less list to delete all entries +* +* If list is empty, return NULL, otherwise, delete all entries and +* return the pointer to the first entry. +*/ +struct llist_node *llist_del_all (struct llist_head *head) +{ +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +return xchg (&head->first,NULL ); +} +EXPORT_SYMBOL_GPL (llist_del_all);
Quoted 6 lines · * Huang Ying ([email protected]) wrote:
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
I'll try to have a look in the following weeks.
Answer to comments below,
Quoted 104 lines · Mathieu Desnoyers
Quoted 93 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 34 lines · * Andrew Morton ([email protected]) wrote:
Quoted 33 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 21 lines · Huang Ying
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Quoted 6 lines
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.h
vanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?
Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
Quoted 10 lines
Quoted 5 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
Quoted 7 lines
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16
Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
Quoted 3 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
Quoted 9 lines
Quoted 6 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?
Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Quoted 4 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.
Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -
How about adding this (or something prettier) to the header ?
Quoted 10 lines
Quoted 6 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 37 lines
Quoted 18 lines
include/linux/llist.h line 12
Quoted 9 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 9 lines
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list.
Quoted 5 lines
Quoted 2 lines
Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
Quoted 72 lines
Quoted 63 lines
Quoted 63 lines
include/linux/llist.h new file +62
-0+* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +*/ + +struct llist_head { +struct llist_node *first; +}; + +struct llist_node { +struct llist_node *next; +}; + +#define LLIST_HEAD_INIT (name) { NULL } +#define LLIST_HEAD (name) struct llist_head name = LLIST_HEAD_INIT(name) + +/** +* init_llist_head - initialize lock-less list head +* @head: the head for your lock-less list +*/ +static inline void init_llist_head (struct llist_head *list) +{ + list->first =NULL ; +} + +/** +* llist_entry - get the struct of this entry +* @ptr: the &struct llist_node pointer. +* @type: the type of the struct this is embedded in. +* @member: the name of the llist_node within the struct. +*/ +#define llist_entry (ptr, type, member) \ + container_of(ptr, type, member) + +/** +* llist_for_each - iterate over some deleted entries of a lock-less list +* @pos: the &struct llist_node to use as a loop cursor +* @node: the first entry of deleted list entries +* +* In general, some entries of the lock-less list can be traversed +* safely only after being deleted from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each (pos, node) \ + for (pos = (node); pos; pos = pos->next) + +/** +* llist_for_each_entry - iterate over some deleted entries of lock-less list of given type +* @pos: the type * to use as a loop cursor. +* @node: the fist entry of deleted list entries. +* @member: the name of the llist_node with the struct. +* +* In general, some entries of the lock-less list can be traversed +* safely only after being removed from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each_entry (pos, node, member) \ + for (pos = llist_entry((node), typeof(*pos), member); \ + &pos->member != NULL; \ + pos = llist_entry(pos->member.next, typeof(*pos), member))Quoted 8 lines
include/linux/llist.h line 85
Quoted 3 lines
include/linux/llist.h new file +3
-0+ +/** +* llist_empty - tests whether a lock-less list is empty How is this
llist_emptytest expected to be used in combination with other API members ? e.g.llist_del_first,llist_del_all,llist_add? I suspect that without mutex to ensure that there are no concurrent changes,llist_emptyreturn value can easily be non-current.
Quoted 2 lines
We don't need
llist_emptyto be accurate. Just a quick way to test whether list/stack is empty without deleting something from list/stack.
OK, maybe specifying this limitation above the function would be appropriate.
Thanks,
Mathieu
Quoted 164 lines
Best Regards,
Huang YingQuoted 160 lines
Thanks,
Mathieu
Quoted 156 lines
include/linux/llist.h new file +13
-0+* @head: the list to test +*/ +static inline int llist_empty (const struct llist_head *head) +{ +return head->first ==NULL ; +} + +void llist_add (struct llist_node *new,struct llist_head *head); +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head); +struct llist_node *llist_del_first (struct llist_head *head); +struct llist_node *llist_del_all (struct llist_head *head); +#endif /* LLIST_H */ lib/Kconfig +3
-0@@ -219,4 +219,7 @@ config LRU_CACHE config AVERAGE bool +config LLIST + bool + endmenulib/Makefile +2
-0@@ -110,6 +110,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomi obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_LLIST) += llist.o + hostprogs-y := gen_crc32table clean-files := crc32table.hlib/llist.c new file +119
-0@@ -0,0 +1,119 @@ +/* +* Lock-less NULL terminated single linked list +* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +* +* Copyright 2010 Intel Corp. +* Author: Huang Ying <[email protected]> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License version +* 2 as published by the Free Software Foundation; +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/llist.h> + +#include <asm/system.h> + +/** +* llist_add - add a new entry +* @new: new entry to be added +* @head: the head for your lock-less list +*/ +void llist_add (struct llist_node *new,struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new->next = entry; + }while (cmpxchg (&head->first, entry, new) != entry); +} +EXPORT_SYMBOL_GPL (llist_add); + +/** +* llist_add_batch - add several linked entries in batch +* @new_first: first entry in batch to be added +* @new_last: last entry in batch to be added +* @head: the head for your lock-less list +*/ +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new_last->next = entry; + }while (cmpxchg (&head->first, entry, new_first) != entry); +} +EXPORT_SYMBOL_GPL (llist_add_batch); + +/** +* llist_del_first - delete the first entry of lock-less list +* @head: the head for your lock-less list +* +* If list is empty, return NULL, otherwise, return the first entry deleted. +* +* Only one llist_del_first user can be used simultaneously with +* multiple llist_add users without lock. Because otherwise +* llist_del_first, llist_add, llist_add sequence in another user may +* change @head->first->next, but keep @head->first. If multiple +* consumers are needed, please use llist_del_all. +*/ +struct llist_node *llist_del_first (struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; +if (entry ==NULL ) +return NULL ; + }while (cmpxchg (&head->first, entry, entry->next) != entry); + +return entry; +} +EXPORT_SYMBOL_GPL (llist_del_first); + +/** +* llist_del_all - delete all entries from lock-less list +* @head: the head of lock-less list to delete all entries +* +* If list is empty, return NULL, otherwise, delete all entries and +* return the pointer to the first entry. +*/ +struct llist_node *llist_del_all (struct llist_head *head) +{ +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +return xchg (&head->first,NULL ); +} +EXPORT_SYMBOL_GPL (llist_del_all);
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 9 lines · Mathieu Desnoyers
Quoted 6 lines · * Huang Ying ([email protected]) wrote:
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
I'll try to have a look in the following weeks.
Thanks.
Quoted 110 lines
Answer to comments below,
Quoted 104 lines · Mathieu Desnoyers
Quoted 93 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 34 lines · * Andrew Morton ([email protected]) wrote:
Quoted 33 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 21 lines · Huang Ying
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Quoted 6 lines
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.h
vanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Quoted 8 lines
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
OK. I see. Thanks for clarification. Takes a look at your "wfs" implementation. It seems that we need to disable interrupt in wf push side to make it possible to use pop in interrupt handler. Do you think so?
Quoted 13 lines
Quoted 13 lines
Quoted 4 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
Quoted 7 lines
Quoted 3 lines
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
For irq work, this is not an issue. irq work users should not depend on the order of raising. But if it is necessary, we can reserve the order again in irq_work_run to keep the original order. After deleting all nodes from lock-less list, we can operate on them at will.
Quoted 9 lines
Quoted 3 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
The llist is ordered list and has only one list "head", so the first entry is the one pointed to by the "head". Is it clear?
Quoted 2 lines
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
But what we need is just a lock-less list, not a stack. It behaves like a stack just because we can not implement other functions such as llist_add_tail etc in a lock-less way yet. And we will add these functions when we know how to do that.
Quoted 12 lines
Quoted 8 lines
Quoted 5 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 7 lines
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Yes. I agree. The semantics of my original lock-less list has already been used by irq work and xlist of net rds. My original implementation can be seen as generalizing the existing implementation. How about take my original implementation as the first step, that is, generalizing, then consider how to optimize it after that?
But if you want to compare the two semantics above, I am OK too.
Quoted 10 lines
Quoted 3 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 51 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 37 lines
Quoted 18 lines
include/linux/llist.h line 12
Quoted 9 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 9 lines
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
Quoted 251 lines
Quoted 71 lines
Quoted 62 lines
Quoted 62 lines
include/linux/llist.h new file +62
-0+* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +*/ + +struct llist_head { +struct llist_node *first; +}; + +struct llist_node { +struct llist_node *next; +}; + +#define LLIST_HEAD_INIT (name) { NULL } +#define LLIST_HEAD (name) struct llist_head name = LLIST_HEAD_INIT(name) + +/** +* init_llist_head - initialize lock-less list head +* @head: the head for your lock-less list +*/ +static inline void init_llist_head (struct llist_head *list) +{ + list->first =NULL ; +} + +/** +* llist_entry - get the struct of this entry +* @ptr: the &struct llist_node pointer. +* @type: the type of the struct this is embedded in. +* @member: the name of the llist_node within the struct. +*/ +#define llist_entry (ptr, type, member) \ + container_of(ptr, type, member) + +/** +* llist_for_each - iterate over some deleted entries of a lock-less list +* @pos: the &struct llist_node to use as a loop cursor +* @node: the first entry of deleted list entries +* +* In general, some entries of the lock-less list can be traversed +* safely only after being deleted from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each (pos, node) \ + for (pos = (node); pos; pos = pos->next) + +/** +* llist_for_each_entry - iterate over some deleted entries of lock-less list of given type +* @pos: the type * to use as a loop cursor. +* @node: the fist entry of deleted list entries. +* @member: the name of the llist_node with the struct. +* +* In general, some entries of the lock-less list can be traversed +* safely only after being removed from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each_entry (pos, node, member) \ + for (pos = llist_entry((node), typeof(*pos), member); \ + &pos->member != NULL; \ + pos = llist_entry(pos->member.next, typeof(*pos), member))Quoted 8 lines
include/linux/llist.h line 85
Quoted 3 lines
include/linux/llist.h new file +3
-0+ +/** +* llist_empty - tests whether a lock-less list is empty How is this
llist_emptytest expected to be used in combination with other API members ? e.g.llist_del_first,llist_del_all,llist_add? I suspect that without mutex to ensure that there are no concurrent changes,llist_emptyreturn value can easily be non-current.Quoted 2 lines
We don't need
llist_emptyto be accurate. Just a quick way to test whether list/stack is empty without deleting something from list/stack.OK, maybe specifying this limitation above the function would be appropriate.
Thanks,
Mathieu
Quoted 156 lines
Best Regards,
Huang YingQuoted 152 lines
Thanks,
Mathieu
Quoted 148 lines
include/linux/llist.h new file +13
-0+* @head: the list to test +*/ +static inline int llist_empty (const struct llist_head *head) +{ +return head->first ==NULL ; +} + +void llist_add (struct llist_node *new,struct llist_head *head); +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head); +struct llist_node *llist_del_first (struct llist_head *head); +struct llist_node *llist_del_all (struct llist_head *head); +#endif /* LLIST_H */ lib/Kconfig +3
-0@@ -219,4 +219,7 @@ config LRU_CACHE config AVERAGE bool +config LLIST + bool + endmenulib/Makefile +2
-0@@ -110,6 +110,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomi obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_LLIST) += llist.o + hostprogs-y := gen_crc32table clean-files := crc32table.hlib/llist.c new file +111
-0@@ -0,0 +1,119 @@ +/* +* Lock-less NULL terminated single linked list +* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +* +* Copyright 2010 Intel Corp. +* Author: Huang Ying <[email protected]> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License version +* 2 as published by the Free Software Foundation; +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/llist.h> + +#include <asm/system.h> + +/** +* llist_add - add a new entry +* @new: new entry to be added +* @head: the head for your lock-less list +*/ +void llist_add (struct llist_node *new,struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new->next = entry; + }while (cmpxchg (&head->first, entry, new) != entry); +} +EXPORT_SYMBOL_GPL (llist_add); + +/** +* llist_add_batch - add several linked entries in batch +* @new_first: first entry in batch to be added +* @new_last: last entry in batch to be added +* @head: the head for your lock-less list +*/ +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new_last->next = entry; + }while (cmpxchg (&head->first, entry, new_first) != entry); +} +EXPORT_SYMBOL_GPL (llist_add_batch); + +/** +* llist_del_first - delete the first entry of lock-less list +* @head: the head for your lock-less list +* +* If list is empty, return NULL, otherwise, return the first entry deleted. +* +* Only one llist_del_first user can be used simultaneously with +* multiple llist_add users without lock. Because otherwise +* llist_del_first, llist_add, llist_add sequence in another user may +* change @head->first->next, but keep @head->first. If multiple +* consumers are needed, please use llist_del_all. +*/ +struct llist_node *llist_del_first (struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; +if (entry ==NULL ) +return NULL ; + }while (cmpxchg (&head->first, entry, entry->next) != entry); + +return entry; +} +EXPORT_SYMBOL_GPL (llist_del_first); + +/** +* llist_del_all - delete all entries from lock-less list +* @head: the head of lock-less list to delete all entries +* +* If list is empty, return NULL, otherwise, delete all entries and +* return the pointer to the first entry. +*/ +struct llist_node *llist_del_all (struct llist_head *head)Quoted 8 lines
Quoted 8 lines
lib/llist.c line 119
Quoted 8 lines
lib/llist.c new file +8
-0+{ +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +return xchg (&head->first,NULL ); +} +EXPORT_SYMBOL_GPL (llist_del_all);--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
Quoted 128 lines · * Huang Ying ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers
Quoted 6 lines · * Huang Ying ([email protected]) wrote:
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
I'll try to have a look in the following weeks.
Thanks.
Quoted 115 lines
Answer to comments below,
Quoted 104 lines · Mathieu Desnoyers
Quoted 93 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 34 lines · * Andrew Morton ([email protected]) wrote:
Quoted 33 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 21 lines · Huang Ying
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Quoted 6 lines
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.h
vanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
Quoted 7 lines
Quoted 3 lines
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
OK. I see. Thanks for clarification. Takes a look at your "wfs" implementation. It seems that we need to disable interrupt in wf push side to make it possible to use pop in interrupt handler. Do you think so?
It would be appropriate, yes, because the irq handler doing "pop" can busy-wait during the short period of time during which it sees a "NULL" value. We don't want to have a softirq running on top of the push that would make the irq handler busy-wait for longer than the duration of interrupt handlers. In your case, the push is done by a NMI handler, which already has interrupts disabled, so no worry for this specific use-case.
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines
Quoted 5 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16
Quoted 8 lines
Quoted 3 lines
Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
For irq work, this is not an issue. irq work users should not depend on the order of raising. But if it is necessary, we can reserve the order again in
irq_work_runto keep the original order. After deleting all nodes from lock-less list, we can operate on them at will.
Ouch. This seems counter-intuitive. I'd rather prefer if we can change the way this lock-less list operates to use a "queue" fifo scheme rather than "stack" (lifo). This would seem much more intuitive: the first entry added to the list is the first to be removed. And for iteration on multiple entries removed at once, rather than iterating in reverse order, it would iterate from the oldest to the newest entry, which again seems more natural.
Quoted 14 lines
Quoted 10 lines
Quoted 4 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
The llist is ordered list and has only one list "head", so the first entry is the one pointed to by the "head". Is it clear?
Quoted 7 lines
Quoted 2 lines
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
But what we need is just a lock-less list, not a stack. It behaves like a stack just because we can not implement other functions such as
llist_add_tailetc in a lock-less way yet. And we will add these functions when we know how to do that.
Well, we do already know how to do that ;-) ;-) Please have a look at wfqueue.h and wfqueue-static.h in Userspace RCU library. In this implementation too, the "blocking" busy-wait can be replaced by an active busy-looping in pretty much the same way I explained for the stack implementation.
Quoted 21 lines
Quoted 13 lines
Quoted 9 lines
Quoted 6 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 7 lines
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Quoted 7 lines
Yes. I agree. The semantics of my original lock-less list has already been used by irq work and xlist of net rds. My original implementation can be seen as generalizing the existing implementation. How about take my original implementation as the first step, that is, generalizing, then consider how to optimize it after that?
But if you want to compare the two semantics above, I am OK too.
In the spirit of not providing more APIs than needed, I would argue that it would be better to settle on the question of stack vs queue before this API gets into mainline.
Unless we can show that you have users that need your list to behave like a stack, I would be in favor of moving it to a queue implementation and provide the semantic of "enqueue/dequeue", with list iteration order from oldest to newest node. Trying to change this afterward could bring us surprises, so it might be better to do it right now before this gets introduced.
Moreover, we're not talking about that many lines of code to port from the userspace implementation to kernel-space. It just needs very thorough testing.
Quoted 74 lines
Quoted 11 lines
Quoted 4 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 54 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 40 lines
Quoted 18 lines
include/linux/llist.h line 12
Quoted 9 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 11 lines
include/linux/llist.h line 20
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list. Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
head and tail, in a list implemented as a stack (but that is not clearly advertised as such), don't convey the meaning of "we're iterating from the newest element pushed to the oldest one". This counter-intuitiveness is part of why I would really like to see this turned into a queue.
Thanks,
Mathieu
Quoted 253 lines
Quoted 252 lines
Quoted 72 lines
Quoted 63 lines
Quoted 63 lines
include/linux/llist.h new file +62
-0+* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +*/ + +struct llist_head { +struct llist_node *first; +}; + +struct llist_node { +struct llist_node *next; +}; + +#define LLIST_HEAD_INIT (name) { NULL } +#define LLIST_HEAD (name) struct llist_head name = LLIST_HEAD_INIT(name) + +/** +* init_llist_head - initialize lock-less list head +* @head: the head for your lock-less list +*/ +static inline void init_llist_head (struct llist_head *list) +{ + list->first =NULL ; +} + +/** +* llist_entry - get the struct of this entry +* @ptr: the &struct llist_node pointer. +* @type: the type of the struct this is embedded in. +* @member: the name of the llist_node within the struct. +*/ +#define llist_entry (ptr, type, member) \ + container_of(ptr, type, member) + +/** +* llist_for_each - iterate over some deleted entries of a lock-less list +* @pos: the &struct llist_node to use as a loop cursor +* @node: the first entry of deleted list entries +* +* In general, some entries of the lock-less list can be traversed +* safely only after being deleted from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each (pos, node) \ + for (pos = (node); pos; pos = pos->next) + +/** +* llist_for_each_entry - iterate over some deleted entries of lock-less list of given type +* @pos: the type * to use as a loop cursor. +* @node: the fist entry of deleted list entries. +* @member: the name of the llist_node with the struct. +* +* In general, some entries of the lock-less list can be traversed +* safely only after being removed from list, so start with an entry +* instead of list head. +*/ +#define llist_for_each_entry (pos, node, member) \ + for (pos = llist_entry((node), typeof(*pos), member); \ + &pos->member != NULL; \ + pos = llist_entry(pos->member.next, typeof(*pos), member))Quoted 8 lines
include/linux/llist.h line 85
Quoted 3 lines
include/linux/llist.h new file +3
-0+ +/** +* llist_empty - tests whether a lock-less list is empty How is this
llist_emptytest expected to be used in combination with other API members ? e.g.llist_del_first,llist_del_all,llist_add? I suspect that without mutex to ensure that there are no concurrent changes,llist_emptyreturn value can easily be non-current.Quoted 2 lines
We don't need
llist_emptyto be accurate. Just a quick way to test whether list/stack is empty without deleting something from list/stack.OK, maybe specifying this limitation above the function would be appropriate.
Thanks,
Mathieu
Quoted 156 lines
Best Regards,
Huang YingQuoted 152 lines
Thanks,
Mathieu
Quoted 148 lines
include/linux/llist.h new file +13
-0+* @head: the list to test +*/ +static inline int llist_empty (const struct llist_head *head) +{ +return head->first ==NULL ; +} + +void llist_add (struct llist_node *new,struct llist_head *head); +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head); +struct llist_node *llist_del_first (struct llist_head *head); +struct llist_node *llist_del_all (struct llist_head *head); +#endif /* LLIST_H */ lib/Kconfig +3
-0@@ -219,4 +219,7 @@ config LRU_CACHE config AVERAGE bool +config LLIST + bool + endmenulib/Makefile +2
-0@@ -110,6 +110,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomi obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_LLIST) += llist.o + hostprogs-y := gen_crc32table clean-files := crc32table.hlib/llist.c new file +111
-0@@ -0,0 +1,119 @@ +/* +* Lock-less NULL terminated single linked list +* +* The basic atomic operation of this list is cmpxchg on long. On +* architectures that don't have NMI-safe cmpxchg implementation, the +* list can NOT be used in NMI handler. So code uses the list in NMI +* handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. +* +* Copyright 2010 Intel Corp. +* Author: Huang Ying <[email protected]> +* +* This program is free software; you can redistribute it and/or +* modify it under the terms of the GNU General Public License version +* 2 as published by the Free Software Foundation; +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with this program; if not, write to the Free Software +* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/llist.h> + +#include <asm/system.h> + +/** +* llist_add - add a new entry +* @new: new entry to be added +* @head: the head for your lock-less list +*/ +void llist_add (struct llist_node *new,struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new->next = entry; + }while (cmpxchg (&head->first, entry, new) != entry); +} +EXPORT_SYMBOL_GPL (llist_add); + +/** +* llist_add_batch - add several linked entries in batch +* @new_first: first entry in batch to be added +* @new_last: last entry in batch to be added +* @head: the head for your lock-less list +*/ +void llist_add_batch (struct llist_node *new_first,struct llist_node *new_last, +struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; + new_last->next = entry; + }while (cmpxchg (&head->first, entry, new_first) != entry); +} +EXPORT_SYMBOL_GPL (llist_add_batch); + +/** +* llist_del_first - delete the first entry of lock-less list +* @head: the head for your lock-less list +* +* If list is empty, return NULL, otherwise, return the first entry deleted. +* +* Only one llist_del_first user can be used simultaneously with +* multiple llist_add users without lock. Because otherwise +* llist_del_first, llist_add, llist_add sequence in another user may +* change @head->first->next, but keep @head->first. If multiple +* consumers are needed, please use llist_del_all. +*/ +struct llist_node *llist_del_first (struct llist_head *head) +{ +struct llist_node *entry; + +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +do { + entry = head->first; +if (entry ==NULL ) +return NULL ; + }while (cmpxchg (&head->first, entry, entry->next) != entry); + +return entry; +} +EXPORT_SYMBOL_GPL (llist_del_first); + +/** +* llist_del_all - delete all entries from lock-less list +* @head: the head of lock-less list to delete all entries +* +* If list is empty, return NULL, otherwise, delete all entries and +* return the pointer to the first entry. +*/ +struct llist_node *llist_del_all (struct llist_head *head)Quoted 8 lines
Quoted 8 lines
lib/llist.c line 119
Quoted 8 lines
lib/llist.c new file +8
-0+{ +#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG +BUG_ON (in_nmi ()); +#endif + +return xchg (&head->first,NULL ); +} +EXPORT_SYMBOL_GPL (llist_del_all);--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 137 lines · Mathieu Desnoyers
Quoted 128 lines · * Huang Ying ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers
Quoted 6 lines · * Huang Ying ([email protected]) wrote:
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
I'll try to have a look in the following weeks.
Thanks.
Quoted 115 lines
Answer to comments below,
Quoted 104 lines · Mathieu Desnoyers
Quoted 93 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 34 lines · * Andrew Morton ([email protected]) wrote:
Quoted 33 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 21 lines · Huang Ying
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Quoted 6 lines
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.hvanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
Quoted 7 lines
Quoted 3 lines
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
OK. I see. Thanks for clarification. Takes a look at your "wfs" implementation. It seems that we need to disable interrupt in wf push side to make it possible to use pop in interrupt handler. Do you think so?
Quoted 7 lines
It would be appropriate, yes, because the irq handler doing "pop" can busy-wait during the short period of time during which it sees a "NULL" value. We don't want to have a softirq running on top of the push that would make the irq handler busy-wait for longer than the duration of interrupt handlers. In your case, the push is done by a NMI handler, which already has interrupts disabled, so no worry for this specific use-case.
The semantics of irq_work doesn't restrict the push must be in NMI handler, it is possible for the push to be called in process context. And we are working on library code, so I don't think it is a good idea to restrict that the priority of context of push must be higher (such as NMI vs IRQ) than that of pop.
Quoted 26 lines
Quoted 17 lines
Quoted 17 lines
Quoted 16 lines
Quoted 4 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16Quoted 8 lines
Quoted 3 lines
Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
For irq work, this is not an issue. irq work users should not depend on the order of raising. But if it is necessary, we can reserve the order again in
irq_work_runto keep the original order. After deleting all nodes from lock-less list, we can operate on them at will.
Quoted 7 lines
Ouch. This seems counter-intuitive. I'd rather prefer if we can change the way this lock-less list operates to use a "queue" fifo scheme rather than "stack" (lifo). This would seem much more intuitive: the first entry added to the list is the first to be removed. And for iteration on multiple entries removed at once, rather than iterating in reverse order, it would iterate from the oldest to the newest entry, which again seems more natural.
I don't think "lifo" is a big issue here, although "fifo" may be more natural. After all, this is a very simple data structure with very simple code.
Quoted 20 lines
Quoted 12 lines
Quoted 8 lines
Quoted 2 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
The llist is ordered list and has only one list "head", so the first entry is the one pointed to by the "head". Is it clear?
Quoted 7 lines
Quoted 2 lines
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
But what we need is just a lock-less list, not a stack. It behaves like a stack just because we can not implement other functions such as
llist_add_tailetc in a lock-less way yet. And we will add these functions when we know how to do that.
Quoted 5 lines
Well, we do already know how to do that ;-) ;-) Please have a look at
wfqueue.handwfqueue-static.hin Userspace RCU library. In this implementation too, the "blocking" busy-wait can be replaced by an active busy-looping in pretty much the same way I explained for the stack implementation.
Find your wfqeueu implementation, that is great! I just have some concern about the performance. It seems hard to implement the dequeue_all, and IRQ may need to be turned off in enqueue side.
Quoted 39 lines
Quoted 20 lines
Quoted 12 lines
Quoted 8 lines
Quoted 5 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 7 lines
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Quoted 7 lines
Yes. I agree. The semantics of my original lock-less list has already been used by irq work and xlist of net rds. My original implementation can be seen as generalizing the existing implementation. How about take my original implementation as the first step, that is, generalizing, then consider how to optimize it after that?
But if you want to compare the two semantics above, I am OK too.
In the spirit of not providing more APIs than needed, I would argue that it would be better to settle on the question of stack vs queue before this API gets into mainline.
Unless we can show that you have users that need your list to behave like a stack, I would be in favor of moving it to a queue implementation and provide the semantic of "enqueue/dequeue", with list iteration order from oldest to newest node. Trying to change this afterward could bring us surprises, so it might be better to do it right now before this gets introduced.
Quoted 3 lines
Moreover, we're not talking about that many lines of code to port from the userspace implementation to kernel-space. It just needs very thorough testing.
The current users don't need a stack semantics. They are USING the stack semantics and implementation. So I am NOT writing a new data structure, I just generalize some existing data structure used by more than one user into lib directory.
So I think the lock-less list data structure should be done in 2 steps.
1. Generalize the existing lock-less list data structure into lib. Because exactly same implementation is used, there will be no big issue here. And if there are some issue in 2, we can revert to here easily.
2. Change the implementation/semantics of lock-less list data structure and change all users, this can based on your "queue" implementation. This involves performance compromise and semantics changing, so will need more testing and more review.
Do you agree?
Quoted 79 lines
Quoted 79 lines
Quoted 10 lines
Quoted 3 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 59 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 37 lines
Quoted 18 lines
include/linux/llist.h line 12
Quoted 9 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 9 lines
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list. Quoted 5 lines
Quoted 2 lines
Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
Quoted 8 lines
Quoted 2 lines
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
head and tail, in a list implemented as a stack (but that is not clearly advertised as such), don't convey the meaning of "we're iterating from the newest element pushed to the oldest one". This counter-intuitiveness is part of why I would really like to see this turned into a queue.
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Best Regards,
Huang Ying
Quoted 147 lines · * huang ying ([email protected]) wrote:
Quoted 137 lines · Mathieu Desnoyers
Quoted 128 lines · * Huang Ying ([email protected]) wrote:
Quoted 9 lines · Mathieu Desnoyers
Quoted 6 lines · * Huang Ying ([email protected]) wrote:
Hi, Mathieu,
Thank you very much for your review. Do you have time to take a look at the lock-less memory allocator as follow?
I'll try to have a look in the following weeks.
Thanks.
Quoted 115 lines
Answer to comments below,
Quoted 104 lines · Mathieu Desnoyers
Quoted 93 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 34 lines · * Andrew Morton ([email protected]) wrote:
Quoted 33 lines · On Wed, 30 Mar 2011 05:22:03 +0200 Andi Kleen <[email protected]> wrote:
Quoted 21 lines · Huang Ying
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Wed, 30 Mar 2011 09:14:45 +0800 Huang Ying <[email protected]> wrote:
Quoted 6 lines
Hi, Andrew and Len,
In my original APEI patches for 2.6.39, the following 3 patches is about lock-less data structure.
Quoted 7 lines
[PATCH 1/7] Add
KconfigoptionARCH_HAVE_NMI_SAFE_CMPXCHG[PATCH 2/7] lib, Add lock-less NULL terminated single list [PATCH 6/7] lib, Makegen_poolmemory allocator locklessLen think we need some non-Intel "Acked-by" or "Reviewed-by" for these patches to go through the ACPI git tree. Or they should go through other tree, such as -mm tree.
I just dropped a couple of your patches because
include/linux/llist.hvanished from linux-next. Did Len trip over the power cord?Quoted 7 lines
Quoted 5 lines
Len has dropped lock-less data structure patches from acpi git tree. He describe the reason in following mails.
https://lkml.org/lkml/2011/3/2/501
https://lkml.org/lkml/2011/3/23/6Ok so we still need a lockless reviewer really and I don't count.
Well I think you count ;) If this is some Intel thing then cluebeat, cluebeat, cluebeat, overruled.
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Copying Mathieu who did a lot of lockless stuff. Are you interested in reviewing Ying's patches?
That would be great.
Sure, I can have a look. Huang, can you resend those three patches adding me to CC list ? That will help me keep appropriate threading in my review. Adding Paul McKenney would also be appropriate.
I know, I know, I said I would wait for a repost, but now the answer burns my fingers. ;-) I'm replying to the patch found in
https://lkml.org/lkml/2011/2/21/13include/linux/llist.h line 4
Quoted 7 lines
include/linux/llist.h new file +4
-0@@ -0,0 +1,98 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
Quoted 7 lines
Quoted 3 lines
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
OK. I see. Thanks for clarification. Takes a look at your "wfs" implementation. It seems that we need to disable interrupt in wf push side to make it possible to use pop in interrupt handler. Do you think so?
Quoted 7 lines
It would be appropriate, yes, because the irq handler doing "pop" can busy-wait during the short period of time during which it sees a "NULL" value. We don't want to have a softirq running on top of the push that would make the irq handler busy-wait for longer than the duration of interrupt handlers. In your case, the push is done by a NMI handler, which already has interrupts disabled, so no worry for this specific use-case.
Quoted 5 lines
The semantics of
irq_workdoesn't restrict the push must be in NMI handler, it is possible for the push to be called in process context. And we are working on library code, so I don't think it is a good idea to restrict that the priority of context of push must be higher (such as NMI vs IRQ) than that of pop.
OK. Anyway, the busy-looping on the pop side is an implementation choice. We have the luxury to choose between either xchg on push/busy-loop on pop or a cmpxchg on push (as in your implementation), which removes the need for busy-loop on pop. Maybe going for a cmpxchg on push might make more sense, because it would not require to disable interrupts.
Quoted 35 lines
Quoted 27 lines
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines
Quoted 5 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16Quoted 8 lines
Quoted 3 lines
Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
For irq work, this is not an issue. irq work users should not depend on the order of raising. But if it is necessary, we can reserve the order again in
irq_work_runto keep the original order. After deleting all nodes from lock-less list, we can operate on them at will.Quoted 7 lines
Ouch. This seems counter-intuitive. I'd rather prefer if we can change the way this lock-less list operates to use a "queue" fifo scheme rather than "stack" (lifo). This would seem much more intuitive: the first entry added to the list is the first to be removed. And for iteration on multiple entries removed at once, rather than iterating in reverse order, it would iterate from the oldest to the newest entry, which again seems more natural.
Quoted 3 lines
I don't think "lifo" is a big issue here, although "fifo" may be more natural. After all, this is a very simple data structure with very simple code.
Yessss, although I would never apply the "simple" qualifier to lockless code. ;-)
Quoted 21 lines
Quoted 21 lines
Quoted 20 lines
Quoted 9 lines
Quoted 3 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
The llist is ordered list and has only one list "head", so the first entry is the one pointed to by the "head". Is it clear?
Quoted 2 lines
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
But what we need is just a lock-less list, not a stack. It behaves like a stack just because we can not implement other functions such as
llist_add_tailetc in a lock-less way yet. And we will add these functions when we know how to do that.
Quoted 8 lines
Quoted 5 lines
Well, we do already know how to do that ;-) ;-) Please have a look at
wfqueue.handwfqueue-static.hin Userspace RCU library. In this implementation too, the "blocking" busy-wait can be replaced by an active busy-looping in pretty much the same way I explained for the stack implementation.Find your wfqeueu implementation, that is great! I just have some concern about the performance.
I guess you are referring to the need to disable interrupts. As I stated above, we can choose to go for a cmpxchg-based push instead, which removes the busy-loop from dequeue altogether.
Quoted 2 lines
It seems hard to implement the
dequeue_all,
Actually, there is already one implemented :)
See urcu-call-rcu.c: call_rcu_thread()
Please note that this "dequeue all" implementation does not support concurrent "dequeue single node" operation (because we did not need it in the specific call_rcu() use-case), but it could possibly be adapted by handling the dummy node more carefully, although I'm not sure it's worth the effort (unless the combined use of dequeue one and dequeue all becomes an important use-case for a given list).
Quoted 1 line
and IRQ may need to be turned off in enqueue side.
Not if we use a cmpxchg-based enqueue.
Quoted 40 lines
Quoted 40 lines
Quoted 21 lines
Quoted 13 lines
Quoted 9 lines
Quoted 6 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 7 lines
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Quoted 7 lines
Yes. I agree. The semantics of my original lock-less list has already been used by irq work and xlist of net rds. My original implementation can be seen as generalizing the existing implementation. How about take my original implementation as the first step, that is, generalizing, then consider how to optimize it after that?
But if you want to compare the two semantics above, I am OK too.
In the spirit of not providing more APIs than needed, I would argue that it would be better to settle on the question of stack vs queue before this API gets into mainline.
Unless we can show that you have users that need your list to behave like a stack, I would be in favor of moving it to a queue implementation and provide the semantic of "enqueue/dequeue", with list iteration order from oldest to newest node. Trying to change this afterward could bring us surprises, so it might be better to do it right now before this gets introduced.
Quoted 8 lines
Quoted 3 lines
Moreover, we're not talking about that many lines of code to port from the userspace implementation to kernel-space. It just needs very thorough testing.
The current users don't need a stack semantics. They are USING the stack semantics and implementation. So I am NOT writing a new data structure, I just generalize some existing data structure used by more than one user into lib directory.
I see. That's the part of the big picture I was missing.
Quoted 8 lines
So I think the lock-less list data structure should be done in 2 steps.
1. Generalize the existing lock-less list data structure into lib. Because exactly same implementation is used, there will be no big issue here. And if there are some issue in 2, we can revert to here easily.
Quoted 6 lines
2. Change the implementation/semantics of lock-less list data structure and change all users, this can based on your "queue" implementation. This involves performance compromise and semantics changing, so will need more testing and more review.
Do you agree?
Yep. What I was missing is that you took existing implementations and merged them together and did not create your own implementation from scratch. Considering that there are already users of these implementation, it indeed makes sense to go through this intermediate step.
Quoted 83 lines
Quoted 83 lines
Quoted 82 lines
Quoted 11 lines
Quoted 4 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 51 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 37 lines
Quoted 18 lines
include/linux/llist.h line 12
Quoted 9 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and multiple consumers, llist_add +* can be used in producers and llist_del_all can be used in +* consumers. They can work simultaneously without lock. But +* llist_del_first can not be used here. Because llist_del_first +* depends on list->first->next does not changed if list->first is not +* changed during its operation, but llist_del_first, llist_add, +* llist_add sequence in another consumer may violate that. You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 9 lines
Quoted 8 lines
include/linux/llist.h new file +8
-0+* +* If there are multiple producers and one consumer, llist_add can be +* used in producers and llist_del_all or llist_del_first can be used +* in the consumer. +* +* The list entries deleted via llist_del_all can be traversed with +* traversing function such as llist_for_each etc. But the list +* entries can not be traversed safely before deleted from the list. Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
Quoted 8 lines
Quoted 5 lines
head and tail, in a list implemented as a stack (but that is not clearly advertised as such), don't convey the meaning of "we're iterating from the newest element pushed to the oldest one". This counter-intuitiveness is part of why I would really like to see this turned into a queue.
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g. call_rcu in the kernel) can start benefiting from it.
Thanks!
Mathieu
Quoted 3 lines
Best Regards,
Huang Ying
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
On Tue, Apr 5, 2011 at 12:42 PM, Mathieu Desnoyers [snip]
Quoted 76 lines
Quoted 70 lines
Quoted 62 lines
Quoted 54 lines
Quoted 54 lines
Quoted 45 lines
Quoted 36 lines
Because this single-linked-list works like a stack (with "push" operation for
llist_add, "pop" operation forllist_del_first), I would recommend to rename it accordingly (as a stack rather than "list"). If we think about other possible users of this kind of lock-free list, such ascall_rcu(), a "queue" would be rather more appropriate than a "stack" (with enqueue/dequeue operations). So at the very least I would like to make sure this API keeps room for lock-free queue implementations that won't be confused with this stack API. It would also be important to figure out if what we really want is a stack or a queue. Some naming ideas follow (maybe they are a bit verbose, comments are welcome).We should note that this list implements "lock-free" push and pop operations (cmpxchg loops), and a "wait-free" "
llist_del_all" operation (using xchg) (only really true for architectures with "true" xchg operation though, not those using LL/SC). We should think about the real use-case requirements put on this lockless stack to decide which variant is most appropriate. We can either have, with the implementation you propose:- Lock-free push
- Pop protected by mutex
- Wait-free pop allOr, as an example of an alternative structure (as Paul and I implemented in the userspace RCU library):
- Wait-free push (stronger real-time guarantees provided by
xchg())
- Blocking pop/pop all (use cmpxchg and busy-wait for very short time periods)(there are others, with e.g. lock-free push, lock-free pop, lock-free pop all, but this one requires RCU read lock across the pop/pop/pop all operations and that memory reclaim of the nodes is only performed after a RCU grace-period has elapsed. This deals with ABA issues of concurrent push/pop you noticed without requiring mutexes protecting pop operations.)
Quoted 8 lines
So it all boils down to which are the constraints of the push/pop callers. Typically, I would expect that the "push" operation has the most strict real-time constraints (and is possibly executed the most often, thus would also benefit from
xchg()which is typically slightly faster thancmpxchg()), which would argue in favor of a wait-free push/blocking pop. But maybe I'm lacking understanding of what you are trying to do with this stack. Do you need to ever pop from a NMI handler ?Quoted 3 lines
In my user case, I don't need to pop in a NMI handler, just push. But we need to pop in a IRQ handler, so we can not use blocking pop. Please take a look at the user case patches listed later.
Actually, I marked that as a "blocking" in our implementation because I have a busy-loop in there, and because my algorithm was implemented in user-space, I added an adaptative delay to make sure not to busy-loop waiting for a preempted thread to come back.
Quoted 7 lines
Quoted 3 lines
But by disabling preemption and using a real busy-loop in the kernel, the pop can trivially be made non-blocking, and thus OK for interrupt handlers.
OK. I see. Thanks for clarification. Takes a look at your "wfs" implementation. It seems that we need to disable interrupt in wf push side to make it possible to use pop in interrupt handler. Do you think so?
Quoted 7 lines
It would be appropriate, yes, because the irq handler doing "pop" can busy-wait during the short period of time during which it sees a "NULL" value. We don't want to have a softirq running on top of the push that would make the irq handler busy-wait for longer than the duration of interrupt handlers. In your case, the push is done by a NMI handler, which already has interrupts disabled, so no worry for this specific use-case.
Quoted 5 lines
The semantics of
irq_workdoesn't restrict the push must be in NMI handler, it is possible for the push to be called in process context. And we are working on library code, so I don't think it is a good idea to restrict that the priority of context of push must be higher (such as NMI vs IRQ) than that of pop.
Quoted 6 lines
OK. Anyway, the busy-looping on the pop side is an implementation choice. We have the luxury to choose between either xchg on push/busy-loop on pop or a cmpxchg on push (as in your implementation), which removes the need for busy-loop on pop. Maybe going for a cmpxchg on push might make more sense, because it would not require to disable interrupts.
Yes. It is luxury to have two choices. :-)
Quoted 68 lines
Quoted 34 lines
Quoted 26 lines
Quoted 17 lines
Quoted 17 lines
Quoted 16 lines
Quoted 4 lines
Some ideas for API identifiers:
struct
llist_head->slist_stack_head
structllist_node->slist_stack_nodeWhy call it a stack and a list? Because it is a stack implemented with single list? I think it is better to name after usage instead of implementation.
The next question is whether it should be named as stack or list. I think from current user's point of view, they think they are using a list instead of stack. There are 3 users so far as follow.
https://lkml.org/lkml/2011/1/17/14
https://lkml.org/lkml/2011/1/17/15
https://lkml.org/lkml/2011/2/21/16Quoted 8 lines
Quoted 3 lines
Hrm, I'm concerned about the impact of handing the irq work from one execution context to another in the reverse order (because a stack is implemented here). Can this have unwanted side-effects ?
For irq work, this is not an issue. irq work users should not depend on the order of raising. But if it is necessary, we can reserve the order again in
irq_work_runto keep the original order. After deleting all nodes from lock-less list, we can operate on them at will.Quoted 7 lines
Ouch. This seems counter-intuitive. I'd rather prefer if we can change the way this lock-less list operates to use a "queue" fifo scheme rather than "stack" (lifo). This would seem much more intuitive: the first entry added to the list is the first to be removed. And for iteration on multiple entries removed at once, rather than iterating in reverse order, it would iterate from the oldest to the newest entry, which again seems more natural.
Quoted 3 lines
I don't think "lifo" is a big issue here, although "fifo" may be more natural. After all, this is a very simple data structure with very simple code.
Yessss, although I would never apply the "simple" qualifier to lockless code. ;-)
Quoted 27 lines
Quoted 26 lines
Quoted 13 lines
Quoted 9 lines
Quoted 3 lines
And if we named this data structure as list, we can still use "queue" for another data structure. Do you think so?
Well, the "delete first entry" is really unclear if we call all this a "list". Which is the first entry ? The first added to the list, or the last one ? The natural reflex would be to think it is the first added, but in this case, it's the opposite. This is why I think using stack or lifo (with push/pop) would be clearer than "list" (with add/del).
The llist is ordered list and has only one list "head", so the first entry is the one pointed to by the "head". Is it clear?
Quoted 7 lines
Quoted 2 lines
So maybe "lockless stack" could be palatable ? The name "lockless lifo" came to my mind in the past days too.
But what we need is just a lock-less list, not a stack. It behaves like a stack just because we can not implement other functions such as
llist_add_tailetc in a lock-less way yet. And we will add these functions when we know how to do that.Well, we do already know how to do that ;-) ;-) Please have a look at
wfqueue.handwfqueue-static.hin Userspace RCU library. In this implementation too, the "blocking" busy-wait can be replaced by an active busy-looping in pretty much the same way I explained for the stack implementation.
Quoted 6 lines
Quoted 2 lines
Find your wfqeueu implementation, that is great! I just have some concern about the performance.
I guess you are referring to the need to disable interrupts. As I stated above, we can choose to go for a cmpxchg-based push instead, which removes the busy-loop from dequeue altogether.
That is great!
Quoted 6 lines
Quoted 2 lines
It seems hard to implement the
dequeue_all,Actually, there is already one implemented :)
See
urcu-call-rcu.c:call_rcu_thread()
Have not understand the whole algorithm fully. Will continue to study it. I found there is a synchronize_rcu() in call_crc_thread(). Must "dequeue_all" use that too?
Quoted 75 lines
Please note that this "dequeue all" implementation does not support concurrent "dequeue single node" operation (because we did not need it in the specific
call_rcu()use-case), but it could possibly be adapted by handling the dummy node more carefully, although I'm not sure it's worth the effort (unless the combined use of dequeue one and dequeue all becomes an important use-case for a given list).Quoted 1 line
and IRQ may need to be turned off in enqueue side.
Not if we use a cmpxchg-based enqueue.
Quoted 40 lines
Quoted 40 lines
Quoted 21 lines
Quoted 13 lines
Quoted 9 lines
Quoted 6 lines
* For your lock-free push/pop + wait-free
pop_allimplementation:
llist_add->slist_stack_push_lf(lock-free)llist_del_first->_slist_stack_pop(needs mutex protection)llist_del_all->slist_stack_pop_all_wf(wait-free)Do we really need to distinguish between lock-free and wait-free from interface?
I don't think it is needed, and it's probably even just more confusing for API users.
Quoted 7 lines
Quoted 2 lines
Will we implement both
slist_stack_push_lfandslist_stack_push_wffor one data structure?Those will possibly even require different data structures. It might be less confusing to find out clearly what our needs are, and only propose a single behavior, otherwise it will be confusing for users of these APIs without good reason.
Quoted 7 lines
Yes. I agree. The semantics of my original lock-less list has already been used by irq work and xlist of net rds. My original implementation can be seen as generalizing the existing implementation. How about take my original implementation as the first step, that is, generalizing, then consider how to optimize it after that?
But if you want to compare the two semantics above, I am OK too.
In the spirit of not providing more APIs than needed, I would argue that it would be better to settle on the question of stack vs queue before this API gets into mainline.
Unless we can show that you have users that need your list to behave like a stack, I would be in favor of moving it to a queue implementation and provide the semantic of "enqueue/dequeue", with list iteration order from oldest to newest node. Trying to change this afterward could bring us surprises, so it might be better to do it right now before this gets introduced.
Quoted 8 lines
Quoted 3 lines
Moreover, we're not talking about that many lines of code to port from the userspace implementation to kernel-space. It just needs very thorough testing.
The current users don't need a stack semantics. They are USING the stack semantics and implementation. So I am NOT writing a new data structure, I just generalize some existing data structure used by more than one user into lib directory.
I see. That's the part of the big picture I was missing.
Quoted 13 lines
So I think the lock-less list data structure should be done in 2 steps.
1. Generalize the existing lock-less list data structure into lib. Because exactly same implementation is used, there will be no big issue here. And if there are some issue in 2, we can revert to here easily.
2. Change the implementation/semantics of lock-less list data structure and change all users, this can based on your "queue" implementation. This involves performance compromise and semantics changing, so will need more testing and more review.
Quoted 7 lines
Quoted 1 line
Do you agree?
Yep. What I was missing is that you took existing implementations and merged them together and did not create your own implementation from scratch. Considering that there are already users of these implementation, it indeed makes sense to go through this intermediate step.
Thanks.
Quoted 88 lines
Quoted 88 lines
Quoted 87 lines
Quoted 73 lines
Quoted 10 lines
Quoted 3 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 54 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 40 lines
Quoted 18 lines
Quoted 9 lines
+ *
+ * If there are multiple producers and multiple consumers,llist_add
+ * can be used in producers andllist_del_allcan be used in
+ * consumers. They can work simultaneously without lock. But
+ *llist_del_firstcan not be used here. Becausellist_del_first
+ * depends onlist->first->nextdoes not changed iflist->firstis not
+ * changed during its operation, butllist_del_first,llist_add,
+ *llist_addsequence in another consumer may violate that.You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 11 lines
Quoted 8 lines
+ *
+ * If there are multiple producers and one consumer,llist_addcan be
+ * used in producers andllist_del_allorllist_del_firstcan be used
+ * in the consumer.
+ *
+ * The list entries deleted viallist_del_allcan be traversed with
+ * traversing function such asllist_for_eachetc. But the list
+ * entries can not be traversed safely before deleted from the list.Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
head and tail, in a list implemented as a stack (but that is not clearly advertised as such), don't convey the meaning of "we're iterating from the newest element pushed to the oldest one". This counter-intuitiveness is part of why I would really like to see this turned into a queue.
Quoted 7 lines
Quoted 2 lines
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g.
call_rcuin the kernel) can start benefiting from it.
I think that is good to move from stack to queue.
I will send out changed lock-less data structure patchset soon. And we can continue to work on the new lock-less queue at the same time.
Best Regards,
Huang Ying
Quoted 1 line · * huang ying ([email protected]) wrote:
On Tue, Apr 5, 2011 at 12:42 PM, Mathieu Desnoyers
[snip]
Quoted 11 lines
Quoted 7 lines
Quoted 3 lines
It seems hard to implement the
dequeue_all,Actually, there is already one implemented :)
See
urcu-call-rcu.c:call_rcu_thread()Have not understand the whole algorithm fully. Will continue to study it. I found there is a
synchronize_rcu()incall_crc_thread(). Must "dequeue_all" use that too?
Please note that call_rcu_thread() does more than just a dequeue_all: it dequeues all the current callbacks from the list, waits for a grace period to elapse, and then execute all the callbacks it got. So the synchronize_rcu() would not be needed in a dequeue_all implementation.
Quoted 97 lines
Quoted 89 lines
Quoted 89 lines
Quoted 88 lines
Quoted 74 lines
Quoted 11 lines
Quoted 4 lines
mutex is needed between multiple "
_slist_stack_pop", but not needed betweenslist_stack_push_lfand_slist_stack_pop. I think it is hard to explain that clearly via function naming.Good point. A ascii-art table might be appropriate here, e.g.:
M: Mutual exclusion needed to protect one from another. -: lockless.
Quoted 6 lines
| push | pop | pop_all push | - | - | - pop | | L | L pop_all | | | -How about adding this (or something prettier) to the header ?
Cool! I will add that to header.
Quoted 54 lines
Quoted 9 lines
Quoted 5 lines
* If we choose to go with an alternate wait-free push implementation:
llist_add->slist_stack_push_wf(wait-free)llist_del_first->slist_stack_pop_blocking(blocking)llist_del_all->slist_stack_pop_all_blocking(blocking)We need non-blocking pop, so maybe you need implement another data structure which has these interface. I think there can be multiple lock-less data structure in kernel.
As I noted earlier, the blocking was only due to our user-level implementation. It can be turned in a very short-lived busy loop instead.
Quoted 40 lines
Quoted 18 lines
Quoted 9 lines
+ *
+ * If there are multiple producers and multiple consumers,llist_add
+ * can be used in producers andllist_del_allcan be used in
+ * consumers. They can work simultaneously without lock. But
+ *llist_del_firstcan not be used here. Becausellist_del_first
+ * depends onlist->first->nextdoes not changed iflist->firstis not
+ * changed during its operation, butllist_del_first,llist_add,
+ *llist_addsequence in another consumer may violate that.You did not seem to define the locking rules when using both
llist_del_all
and
llist_del_firstin parallel. I expect that a mutex is needed, because a
Quoted 7 lines
llist_del_all,llist_add,llist_addin parallel with
llist_del_firstcould run into the same ABA problem as described above.
OK. I will add that.
Quoted 11 lines
Quoted 8 lines
+ *
+ * If there are multiple producers and one consumer,llist_addcan be
+ * used in producers andllist_del_allorllist_del_firstcan be used
+ * in the consumer.
+ *
+ * The list entries deleted viallist_del_allcan be traversed with
+ * traversing function such asllist_for_eachetc. But the list
+ * entries can not be traversed safely before deleted from the list.Given that this is in fact a stack, specifying the traversal order of
llist_for_eachand friends would be appropriate.Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Ok. I will add something like "traversing from head to tail" in the comments.
Traversing from last element pushed to first element pushed would probably be clearer.
head and tail describe the current state, while "last/first element pushed" describe the history. I think both are understandable.
head and tail, in a list implemented as a stack (but that is not clearly advertised as such), don't convey the meaning of "we're iterating from the newest element pushed to the oldest one". This counter-intuitiveness is part of why I would really like to see this turned into a queue.
Quoted 7 lines
Quoted 2 lines
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g.
call_rcuin the kernel) can start benefiting from it.
Quoted 4 lines
I think that is good to move from stack to queue.
I will send out changed lock-less data structure patchset soon. And we can continue to work on the new lock-less queue at the same time.
Sounds like a very good plan! Thanks!
Mathieu
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 1 line · Mathieu Desnoyers
* huang ying ([email protected]) wrote:
[snip]
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g.
call_rcuin the kernel) can start benefiting from it.
Quoted 6 lines
Quoted 4 lines
I think that is good to move from stack to queue.
I will send out changed lock-less data structure patchset soon. And we can continue to work on the new lock-less queue at the same time.
Sounds like a very good plan! Thanks!
Maybe you can send out your lock-less queue patches, so we can work on that.
Best Regards,
Huang Ying
Quoted 12 lines · * Huang Ying ([email protected]) wrote:
Quoted 1 line · Mathieu Desnoyers
* huang ying ([email protected]) wrote:
[snip]
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g.
call_rcuin the kernel) can start benefiting from it.
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
I think that is good to move from stack to queue.
I will send out changed lock-less data structure patchset soon. And we can continue to work on the new lock-less queue at the same time.
Sounds like a very good plan! Thanks!
Maybe you can send out your lock-less queue patches, so we can work on that.
Yep, let's wait until your implementation is finalized and merged, and then ping me again so I can cook up a RFC patch turning llist into a queue, if it's OK with you.
Thanks,
Mathieu
Quoted 3 lines
Best Regards,
Huang Ying
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 5 lines · Mathieu Desnoyers
Quoted 4 lines · * Huang Ying ([email protected]) wrote:
Quoted 1 line · Mathieu Desnoyers
* huang ying ([email protected]) wrote:
[snip]
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 2 lines
OK. I will change the comments, adding these semantics explanation. The user should be warned :)
Yes, that makes sense. After this generalization step, if you're ok with this, we could aim at moving the implementation from a stack to a queue and provide fifo semantic rather than lifo, so that other users (e.g.
call_rcuin the kernel) can start benefiting from it.
Just to be clear... Currently, call_rcu() works on a per-CPU basis, so that it can simply disable interrupts and then do the queuing non-atomically.
However, should it be necessary to cross-queue RCU callbacks in order to avoid ever executing an RCU callback on a given CPU, then something like this might become useful.
Thanx, Paul
Quoted 26 lines
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
I think that is good to move from stack to queue.
I will send out changed lock-less data structure patchset soon. And we can continue to work on the new lock-less queue at the same time.
Sounds like a very good plan! Thanks!
Maybe you can send out your lock-less queue patches, so we can work on that.
Yep, let's wait until your implementation is finalized and merged, and then ping me again so I can cook up a RFC patch turning llist into a queue, if it's OK with you.
Thanks,
Mathieu
Quoted 3 lines
Best Regards,
Huang YingSignature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com