Lockless memory allocator and list
Subsystems (10)
cover Lockless memory allocator and list
This patchset adds a lockless memory allocator and a lock-less list.
v8:
- Rebased on mmotm 2010-12-02
v7:
- Revise ARCH_HAVE_NMI_SAFE_CMPXCHG definition for some architectures according to architecture maitainers' comments.
- Remove spin_trylock_irqsave based fallback for lockless memory allocator, because it does not work for !CONFIG_SMP and is not likely to be used.
- Make lockless memory allocator and list does not depend on ARCH_HAVE_NMI_SAFE_CMPXCHG. Instead, require the user to depend on it when needed. And BUG_ON(in_nmi()) is added in necessary place to prevent silent race.
v6:
- Revise ARCH_HAVE_NMI_SAFE_CMPXCHG definition for some architectures according to architecture maitainers' comments.
v5:
- Add ARCH_HAVE_NMI_SAFE_CMPXCHG
- Add spin_trylock_irqsave based fallback in lockless memory allocator if ARCH_HAVE_NMI_SAFE_CMPXCHG=n
- Make lockless list depends on ARCH_HAVE_NMI_SAFE_CMPXCHG
v4:
- Split from APEI patchset
- Update patch description and comments according to ML comments
v3:
- Rework lockless memory allocator and list according to ML comments
[PATCH -mm -v8 1/3] Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG [PATCH -mm -v8 2/3] lib, Make gen_pool memory allocator lockless [PATCH -mm -v8 3/3] lib, Add lock-less NULL terminated single list
PATCH 1/3 Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG
cmpxchg() is widely used by lockless code, including NMI-safe lockless code. But on some architectures, the cmpxchg() implementation is not NMI-safe, on these architectures the lockless code may need to a spin_trylock_irqsave() based implementation.
This patch adds a Kconfig option: ARCH_HAVE_NMI_SAFE_CMPXCHG, so that NMI-safe lockless code can depend on it or provide different implementation according to it.
On many architectures, cmpxchg is only NMI-safe for several specific operand sizes. So, ARCH_HAVE_NMI_SAFE_CMPXCHG define in this patch only guarantees cmpxchg is NMI-safe for sizeof(unsigned long).
--- arch/Kconfig | 3 +++ arch/alpha/Kconfig | 1 + arch/avr32/Kconfig | 1 + arch/frv/Kconfig | 1 + arch/ia64/Kconfig | 1 + arch/m68k/Kconfig | 1 + arch/parisc/Kconfig | 1 + arch/powerpc/Kconfig | 1 + arch/s390/Kconfig | 1 + arch/sh/Kconfig | 1 + arch/sparc/Kconfig | 1 + arch/tile/Kconfig | 1 + arch/x86/Kconfig | 1 + 13 files changed, 15 insertions(+), 0 deletions(-)
arch/Kconfig +3 -0
@@ -178,4 +178,7 @@ config HAVE_ARCH_JUMP_LABEL config HAVE_ARCH_MUTEX_CPU_RELAX bool +config ARCH_HAVE_NMI_SAFE_CMPXCHG + bool + source "kernel/gcov/Kconfig"
arch/alpha/Kconfig +1 -0
@@ -7,6 +7,7 @@ config ALPHA select HAVE_SYSCALL_WRAPPERS select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG select HAVE_DMA_ATTRS help The Alpha is a 64-bit general-purpose processor designed and
arch/avr32/Kconfig +1 -0
@@ -6,6 +6,7 @@ config AVR32 select HAVE_CLK select HAVE_OPROFILE select HAVE_KPROBES + select ARCH_HAVE_NMI_SAFE_CMPXCHG help AVR32 is a high-performance 32-bit RISC microprocessor core, designed for cost-sensitive embedded applications, with particular
arch/frv/Kconfig +1 -0
@@ -5,6 +5,7 @@ config FRV select HAVE_ARCH_TRACEHOOK select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG config ZONE_DMA bool
arch/ia64/Kconfig +1 -0
@@ -22,6 +22,7 @@ config IA64 select HAVE_KVM select HAVE_ARCH_TRACEHOOK select HAVE_DMA_API_DEBUG + select ARCH_HAVE_NMI_SAFE_CMPXCHG default y help The Itanium Processor Family is Intel's 64-bit successor to
arch/m68k/Kconfig +1 -0
@@ -4,6 +4,7 @@ config M68K select HAVE_AOUT select HAVE_IDE select GENERIC_ATOMIC64 + select ARCH_HAVE_NMI_SAFE_CMPXCHG if RMW_INSNS config MMU bool
arch/parisc/Kconfig +1 -0
@@ -11,6 +11,7 @@ config PARISC select BUG select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG select GENERIC_ATOMIC64 if !64BIT select GENERIC_HARDIRQS_NO__DO_IRQ help
arch/powerpc/Kconfig +1 -0
@@ -145,6 +145,7 @@ config PPC select GENERIC_ATOMIC64 if PPC32 select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG select HAVE_REGS_AND_STACK_ACCESS_API select HAVE_HW_BREAKPOINT if PERF_EVENTS && PPC_BOOK3S_64
arch/s390/Kconfig +1 -0
@@ -82,6 +82,7 @@ config S390 select INIT_ALL_POSSIBLE select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG select HAVE_KERNEL_GZIP select HAVE_KERNEL_BZIP2 select HAVE_KERNEL_LZMA
arch/sh/Kconfig +1 -0
@@ -11,6 +11,7 @@ config SUPERH select HAVE_DMA_ATTRS select HAVE_IRQ_WORK select HAVE_PERF_EVENTS + select ARCH_HAVE_NMI_SAFE_CMPXCHG if (GUSA_RB || CPU_SH4A) select PERF_USE_VMALLOC select HAVE_KERNEL_GZIP select HAVE_KERNEL_BZIP2
arch/sparc/Kconfig +1 -0
@@ -22,6 +22,7 @@ config SPARC select RTC_CLASS select RTC_DRV_M48T59 select HAVE_IRQ_WORK + select ARCH_HAVE_NMI_SAFE_CMPXCHG select HAVE_DMA_ATTRS select HAVE_DMA_API_DEBUG select HAVE_ARCH_JUMP_LABEL
arch/tile/Kconfig +1 -0
@@ -104,6 +104,7 @@ config TILE select GENERIC_FIND_NEXT_BIT select USE_GENERIC_SMP_HELPERS select CC_OPTIMIZE_FOR_SIZE + select ARCH_HAVE_NMI_SAFE_CMPXCHG # FIXME: investigate whether we need/want these options. # select HAVE_IOREMAP_PROT
arch/x86/Kconfig +1 -0
@@ -23,6 +23,7 @@ config X86 select HAVE_OPROFILE select HAVE_PERF_EVENTS select HAVE_IRQ_WORK + select ARCH_HAVE_NMI_SAFE_CMPXCHG if !M386 select HAVE_IOREMAP_PROT select HAVE_KPROBES select HAVE_MEMBLOCK
Signature · 1 line
1.7.2.3
PATCH 2/3 lib, Make gen_pool memory allocator lockless
In reply to Huang YingThis version of the gen_pool memory allocator supports lockless operation.
This makes it safe to use in NMI handlers and other special unblockable contexts that could otherwise deadlock on locks. This is implemented by using atomic operations and retries on any conflicts. The disadvantage is that there may be livelocks in extreme cases. For better scalability, one gen_pool allocator can be used for each CPU.
The lockless operation only works if there is enough memory available. If new memory is added to the pool a lock has to be still taken. So any user relying on locklessness has to ensure that sufficient memory is preallocated.
The basic atomic operation of this allocator is cmpxchg on long. On architectures that don't have NMI-safe cmpxchg implementation, the allocator can NOT be used in NMI handler. So code uses the allocator in NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
--- include/linux/bitmap.h | 1 + include/linux/genalloc.h | 46 ++++++++- lib/bitmap.c | 2 - lib/genalloc.c | 246 +++++++++++++++++++++++++++++++++++++--------- 4 files changed, 241 insertions(+), 54 deletions(-)
include/linux/bitmap.h +1 -0
@@ -142,6 +142,7 @@ extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);extern int bitmap_allocate_region (unsigned long *bitmap,int pos,int order);extern void bitmap_copy_le (void *dst,const unsigned long *src,int nbits); +#define BITMAP_FIRST_WORD_MASK (start) (~0UL << ((start) % BITS_PER_LONG))#define BITMAP_LAST_WORD_MASK (nbits) \ ( \ ((nbits) % BITS_PER_LONG) ? \
include/linux/genalloc.h +40 -6
70 lines not on this page · raw message
lib/bitmap.c +0 -2
@@ -271,8 +271,6 @@ int __bitmap_weight(const unsigned long *bitmap, int bits) }EXPORT_SYMBOL (__bitmap_weight); -#define BITMAP_FIRST_WORD_MASK (start) (~0UL << ((start) % BITS_PER_LONG)) -void bitmap_set (unsigned long *map,int start,int nr) {unsigned long *p = map +BIT_WORD (start);
lib/genalloc.c +200 -46
314 lines not on this page · raw message
Signature · 1 line
1.7.2.3
PATCH 3/3 lib, Add lock-less NULL terminated single list
In reply to Huang YingCmpxchg is used to implement adding new entry to the list, deleting all entries from the list, deleting first entry of the list and some other operations.
Because this is a single list, so the tail can not be accessed in O(1).
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.
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 without proper synchronization with the list consumers.
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.
--- include/linux/llist.h | 97 +++++++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig | 3 ++ lib/Makefile | 2 + lib/llist.c | 97 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 199 insertions(+), 0 deletions(-) create mode 100644 include/linux/llist.h create mode 100644 lib/llist.c
include/linux/llist.h new file +97 -0
@@ -0,0 +1,97 @@ +#ifndef LLIST_H +#define LLIST_H +/* +* Lock-less NULL terminated single linked list +* +* 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. +* +* 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 +* without proper synchronization with the list consumers. +* +* 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 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 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)) + +/** +* llist_empty - tests whether a lock-less list is empty +* @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); +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
@@ -237,4 +237,7 @@ config IOQ If unsure, say N +config LLIST + bool + endmenu
lib/Makefile +2 -0
@@ -111,6 +111,8 @@ obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o obj-$(CONFIG_AVERAGE) += average.o +obj-$(CONFIG_LLIST) += llist.o + hostprogs-y := gen_crc32table clean-files := crc32table.h
lib/llist.c new file +97 -0
97 lines not on this page · raw message
Signature · 1 line
1.7.2.3
Quoted 2 lines · Huang Ying
This patchset adds a lockless memory allocator and a lock-less list.
Still no users the allocator, and no attempt to unify the existing lockless list implementations.
I'm getting very tired of this Huang.
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · Huang Ying
This patchset adds a lockless memory allocator and a lock-less list.
Still no users the allocator, and no attempt to unify the existing lockless list implementations.
I'm getting very tired of this Huang.
I just want to do that in the next step after merging the data structure itself. The first user of the allocator is APEI, which will go ACPI tree, lockless list in irq_work will go tip tree, lockless list in xlist will go net tree.
We must merge the data structure with its users together?
Best Regards,
Huang Ying
Quoted 8 lines · Huang Ying
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Huang Ying
This patchset adds a lockless memory allocator and a lock-less list.
Still no users the allocator, and no attempt to unify the existing lockless list implementations.
Quoted 8 lines
Quoted 1 line
I'm getting very tired of this Huang.
I just want to do that in the next step after merging the data structure itself. The first user of the allocator is APEI, which will go ACPI tree, lockless list in
irq_workwill go tip tree, lockless list in xlist will go net tree.We must merge the data structure with its users together?
Yes -- that's how new infrastructure gets merged. Because if we don't agree with the users (I don't) there is no point in merging these things either.
I would really like you to stop posting code and talk to the EDAC guys. You just keep on posting the same crap over and over again without making any kind of progress what so ever.
So stop pushing your crap, _please_, and talk to the EDAC and other RAS guys and come up with something together.
I haven't heard a single other RAS guy agree with your approach, and I'm getting really sick of you just pushing your stuff without even wanting to talk to them.
I don't want to see a single line of code from you until you've talked with other RAS folks and they agree that your bits make sense.
So let me put it in simple words: unless there's a non-Intel RAS guy signing off on your patches I'm objecting to them.
The thing is, a unified RAS infrastructure is much more useful for admins, it means they can use the same tools regardless of what platform they're running on.
Now I know creating such a thing seems daunting, but at least give it a try, its better to have tried and failed that not attempted at all, at worst you'll learn what you did wrong and can try to do better the second time around.
Quoted 33 lines · Peter Zijlstra
Quoted 8 lines · Huang Ying
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · Huang Ying
This patchset adds a lockless memory allocator and a lock-less list.
Still no users the allocator, and no attempt to unify the existing lockless list implementations.
Quoted 8 lines
Quoted 1 line
I'm getting very tired of this Huang.
I just want to do that in the next step after merging the data structure itself. The first user of the allocator is APEI, which will go ACPI tree, lockless list in
irq_workwill go tip tree, lockless list in xlist will go net tree.We must merge the data structure with its users together?
Yes -- that's how new infrastructure gets merged. Because if we don't agree with the users (I don't) there is no point in merging these things either.
I would really like you to stop posting code and talk to the EDAC guys. You just keep on posting the same crap over and over again without making any kind of progress what so ever.
So stop pushing your crap, _please_, and talk to the EDAC and other RAS guys and come up with something together.
I haven't heard a single other RAS guy agree with your approach, and I'm getting really sick of you just pushing your stuff without even wanting to talk to them.
Quoted 5 lines
I don't want to see a single line of code from you until you've talked with other RAS folks and they agree that your bits make sense.
So let me put it in simple words: unless there's a non-Intel RAS guy signing off on your patches I'm objecting to them.
Please take a look at the patchset, this patchset is not RAS specific, it is not hardware error reporting infrastructure or hardware error reporting interface. This is just lock-less data structure. So this is not a RAS patchset. Why I must get non-Intel RAS guys' signing off for a non-RAS patchset?
I will not post my original hardware error reporting infrastructure or interface after this patchset. Although I may use some part of this patchset in APEI code, that is just driver internal data structure usage, not general hardware error reporting infrastructure or interface.
Quoted 8 lines
The thing is, a unified RAS infrastructure is much more useful for admins, it means they can use the same tools regardless of what platform they're running on.
Now I know creating such a thing seems daunting, but at least give it a try, its better to have tried and failed that not attempted at all, at worst you'll learn what you did wrong and can try to do better the second time around.
I have tried to do that with my original hardware error reporting interface patchset. It is really generic, simple and can help RAS guys. But it seems that no many people like it, and no many people really take a look at it. So I stop doing that now.
And I remember the recent consensus on hardware error reporting is to use printk. Although I think it will be better if we have some other tool-oriented interface too. I will work on printk based hardware error reporting interface firstly.
Best Regards,
Huang Ying
Quoted 7 lines · huang ying
Quoted 5 lines · Peter Zijlstra
I don't want to see a single line of code from you until you've talked with other RAS folks and they agree that your bits make sense.
So let me put it in simple words: unless there's a non-Intel RAS guy signing off on your patches I'm objecting to them.
Quoted 8 lines
Please take a look at the patchset, this patchset is not RAS specific, it is not hardware error reporting infrastructure or hardware error reporting interface. This is just lock-less data structure. So this is not a RAS patchset. Why I must get non-Intel RAS guys' signing off for a non-RAS patchset?
I will not post my original hardware error reporting infrastructure or interface after this patchset. Although I may use some part of this
There are _NO_ users of that new infrastructure. And we do _NOT_ merge code which has no users and therefor no purpose just for fun. Period.
Quoted 3 lines
patchset in APEI code, that is just driver internal data structure usage, not general hardware error reporting infrastructure or interface.
So you want to use it in APEI code, then post it when your APEI code is ready, reviewed and mergeable, which requires the ack from the RAS folks.
And stop reposting it _BEFORE_ you have at least tried to address Peters other request:
Quoted 1 line
Quoted 1 line
Quoted 1 line
... and no attempt to unify the existing lockless list implementations.
That's a reasonable request as we have already lockless list implementations and adding another one is not of interest at all.
If you think your lockless list is superior, then replace the existing implementations and convert the users or at least one of them. Then we have a technical ground to discuss your new lockless list.
Thanks,
tglx