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
This 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.
Signed-off-by: Huang Ying <[email protected]>
Reviewed-by: Andi Kleen <[email protected]>
---
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(-)
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index daf8c48..1092269 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -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) ? \
diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 9869ef3..400b008 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -1,8 +1,28 @@
+#ifndef GENALLOC_H
+#define GENALLOC_H
/*
- * Basic general purpose allocator for managing special purpose memory
- * not managed by the regular kmalloc/kfree interface.
- * Uses for this includes on-device special memory, uncached memory
- * etc.
+ * Basic general purpose allocator for managing special purpose
+ * memory, for example, memory that is not managed by the regular
+ * kmalloc/kfree interface. Uses for this includes on-device special
+ * memory, uncached memory etc.
+ *
+ * It is safe to use the allocator 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 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.
*
* This source code is licensed under the GNU General Public License,
* Version 2. See the file COPYING for more details.
@@ -13,7 +33,7 @@
* General purpose special memory pool descriptor.
*/
struct gen_pool {
- rwlock_t lock;
+ spinlock_t lock;
struct list_head chunks; /* list of chunks in this pool */
int min_alloc_order; /* minimum allocation order */
};
@@ -22,15 +42,29 @@ struct gen_pool {
* General purpose special memory pool chunk descriptor.
*/
struct gen_pool_chunk {
- spinlock_t lock;
struct list_head next_chunk; /* next chunk in pool */
+ atomic_t avail;
unsigned long start_addr; /* starting address of memory chunk */
unsigned long end_addr; /* ending address of memory chunk */
unsigned long bits[0]; /* bitmap for allocating memory chunk */
};
+/**
+ * gen_pool_for_each_chunk - iterate over chunks of generic memory pool
+ * @chunk: the struct gen_pool_chunk * to use as a loop cursor
+ * @pool: the generic memory pool
+ *
+ * Not lockless, proper mutual exclusion is needed to use this macro
+ * with other gen_pool function simultaneously.
+ */
+#define gen_pool_for_each_chunk(chunk, pool) \
+ list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk)
+
extern struct gen_pool *gen_pool_create(int, int);
extern int gen_pool_add(struct gen_pool *, unsigned long, size_t, int);
extern void gen_pool_destroy(struct gen_pool *);
extern unsigned long gen_pool_alloc(struct gen_pool *, size_t);
extern void gen_pool_free(struct gen_pool *, unsigned long, size_t);
+extern size_t gen_pool_avail(struct gen_pool *);
+extern size_t gen_pool_size(struct gen_pool *);
+#endif /* GENALLOC_H */
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 741fae9..c298714 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -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);
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 1923f14..e304a87 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -1,8 +1,26 @@
/*
- * Basic general purpose allocator for managing special purpose memory
- * not managed by the regular kmalloc/kfree interface.
- * Uses for this includes on-device special memory, uncached memory
- * etc.
+ * Basic general purpose allocator for managing special purpose
+ * memory, for example, memory that is not managed by the regular
+ * kmalloc/kfree interface. Uses for this includes on-device special
+ * memory, uncached memory etc.
+ *
+ * It is safe to use the allocator 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 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.
*
* Copyright 2005 (C) Jes Sorensen <[email protected]>
*
@@ -13,8 +31,107 @@
#include <linux/slab.h>
#include <linux/module.h>
#include <linux/bitmap.h>
+#include <linux/rculist.h>
+#include <linux/interrupt.h>
#include <linux/genalloc.h>
+static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set)
+{
+ unsigned long val, nval;
+
+ nval = *addr;
+ do {
+ val = nval;
+ if (val & mask_to_set)
+ return -EBUSY;
+ } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val);
+
+ return 0;
+}
+
+static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear)
+{
+ unsigned long val, nval;
+
+ nval = *addr;
+ do {
+ val = nval;
+ if ((val & mask_to_clear) != mask_to_clear)
+ return -EBUSY;
+ } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val);
+
+ return 0;
+}
+
+/*
+ * bitmap_set_ll - set the specified number of bits at the specified position
+ * @map: pointer to a bitmap
+ * @start: a bit position in @map
+ * @nr: number of bits to set
+ *
+ * Set @nr bits start from @start in @map lock-lessly. Several users
+ * can set/clear the same bitmap simultaneously without lock. If two
+ * users set the same bit, one user will return remain bits, otherwise
+ * return 0.
+ */
+static int bitmap_set_ll(unsigned long *map, int start, int nr)
+{
+ unsigned long *p = map + BIT_WORD(start);
+ const int size = start + nr;
+ int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+ unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+ while (nr - bits_to_set >= 0) {
+ if (set_bits_ll(p, mask_to_set))
+ return nr;
+ nr -= bits_to_set;
+ bits_to_set = BITS_PER_LONG;
+ mask_to_set = ~0UL;
+ p++;
+ }
+ if (nr) {
+ mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+ if (set_bits_ll(p, mask_to_set))
+ return nr;
+ }
+
+ return 0;
+}
+
+/*
+ * bitmap_clear_ll - clear the specified number of bits at the specified position
+ * @map: pointer to a bitmap
+ * @start: a bit position in @map
+ * @nr: number of bits to set
+ *
+ * Clear @nr bits start from @start in @map lock-lessly. Several users
+ * can set/clear the same bitmap simultaneously without lock. If two
+ * users clear the same bit, one user will return remain bits,
+ * otherwise return 0.
+ */
+static int bitmap_clear_ll(unsigned long *map, int start, int nr)
+{
+ unsigned long *p = map + BIT_WORD(start);
+ const int size = start + nr;
+ int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+ unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+
+ while (nr - bits_to_clear >= 0) {
+ if (clear_bits_ll(p, mask_to_clear))
+ return nr;
+ nr -= bits_to_clear;
+ bits_to_clear = BITS_PER_LONG;
+ mask_to_clear = ~0UL;
+ p++;
+ }
+ if (nr) {
+ mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+ if (clear_bits_ll(p, mask_to_clear))
+ return nr;
+ }
+
+ return 0;
+}
/**
* gen_pool_create - create a new special memory pool
@@ -30,7 +147,7 @@ struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid);
if (pool != NULL) {
- rwlock_init(&pool->lock);
+ spin_lock_init(&pool->lock);
INIT_LIST_HEAD(&pool->chunks);
pool->min_alloc_order = min_alloc_order;
}
@@ -58,15 +175,15 @@ int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size,
chunk = kmalloc_node(nbytes, GFP_KERNEL | __GFP_ZERO, nid);
if (unlikely(chunk == NULL))
- return -1;
+ return -ENOMEM;
- spin_lock_init(&chunk->lock);
chunk->start_addr = addr;
chunk->end_addr = addr + size;
+ atomic_set(&chunk->avail, size);
- write_lock(&pool->lock);
- list_add(&chunk->next_chunk, &pool->chunks);
- write_unlock(&pool->lock);
+ spin_lock(&pool->lock);
+ list_add_rcu(&chunk->next_chunk, &pool->chunks);
+ spin_unlock(&pool->lock);
return 0;
}
@@ -108,43 +225,47 @@ EXPORT_SYMBOL(gen_pool_destroy);
* @size: number of bytes to allocate from the pool
*
* Allocate the requested number of bytes from the specified pool.
- * Uses a first-fit algorithm.
+ * Uses a first-fit algorithm. Can not be used in NMI handler on
+ * architectures without NMI-safe cmpxchg implementation.
*/
unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
{
- struct list_head *_chunk;
struct gen_pool_chunk *chunk;
- unsigned long addr, flags;
+ unsigned long addr;
int order = pool->min_alloc_order;
- int nbits, start_bit, end_bit;
+ int nbits, start_bit = 0, end_bit, remain;
+
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+ BUG_ON(in_nmi());
+#endif
if (size == 0)
return 0;
nbits = (size + (1UL << order) - 1) >> order;
-
- read_lock(&pool->lock);
- list_for_each(_chunk, &pool->chunks) {
- chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
+ list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
+ if (size > atomic_read(&chunk->avail))
+ continue;
end_bit = (chunk->end_addr - chunk->start_addr) >> order;
-
- spin_lock_irqsave(&chunk->lock, flags);
- start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit, 0,
- nbits, 0);
- if (start_bit >= end_bit) {
- spin_unlock_irqrestore(&chunk->lock, flags);
+retry:
+ start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit,
+ start_bit, nbits, 0);
+ if (start_bit >= end_bit)
continue;
+ remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
+ if (remain) {
+ remain = bitmap_clear_ll(chunk->bits, start_bit,
+ nbits - remain);
+ BUG_ON(remain);
+ goto retry;
}
addr = chunk->start_addr + ((unsigned long)start_bit << order);
-
- bitmap_set(chunk->bits, start_bit, nbits);
- spin_unlock_irqrestore(&chunk->lock, flags);
- read_unlock(&pool->lock);
+ size = nbits << order;
+ atomic_sub(size, &chunk->avail);
return addr;
}
- read_unlock(&pool->lock);
return 0;
}
EXPORT_SYMBOL(gen_pool_alloc);
@@ -155,33 +276,66 @@ EXPORT_SYMBOL(gen_pool_alloc);
* @addr: starting address of memory to free back to pool
* @size: size in bytes of memory to free
*
- * Free previously allocated special memory back to the specified pool.
+ * Free previously allocated special memory back to the specified
+ * pool. Can not be used in NMI handler on architectures without
+ * NMI-safe cmpxchg implementation.
*/
void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
{
- struct list_head *_chunk;
struct gen_pool_chunk *chunk;
- unsigned long flags;
int order = pool->min_alloc_order;
- int bit, nbits;
-
- nbits = (size + (1UL << order) - 1) >> order;
+ int start_bit, nbits, remain;
- read_lock(&pool->lock);
- list_for_each(_chunk, &pool->chunks) {
- chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+ BUG_ON(in_nmi());
+#endif
+ nbits = (size + (1UL << order) - 1) >> order;
+ list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
if (addr >= chunk->start_addr && addr < chunk->end_addr) {
BUG_ON(addr + size > chunk->end_addr);
- spin_lock_irqsave(&chunk->lock, flags);
- bit = (addr - chunk->start_addr) >> order;
- while (nbits--)
- __clear_bit(bit++, chunk->bits);
- spin_unlock_irqrestore(&chunk->lock, flags);
- break;
+ start_bit = (addr - chunk->start_addr) >> order;
+ remain = bitmap_clear_ll(chunk->bits, start_bit, nbits);
+ BUG_ON(remain);
+ size = nbits << order;
+ atomic_add(size, &chunk->avail);
+ return;
}
}
- BUG_ON(nbits > 0);
- read_unlock(&pool->lock);
+ BUG();
}
EXPORT_SYMBOL(gen_pool_free);
+
+/**
+ * gen_pool_avail - get available free space of the pool
+ * @pool: pool to get available free space
+ *
+ * Return available free space of the specified pool.
+ */
+size_t gen_pool_avail(struct gen_pool *pool)
+{
+ struct gen_pool_chunk *chunk;
+ size_t avail = 0;
+
+ list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
+ avail += atomic_read(&chunk->avail);
+ return avail;
+}
+EXPORT_SYMBOL_GPL(gen_pool_avail);
+
+/**
+ * gen_pool_size - get size in bytes of memory managed by the pool
+ * @pool: pool to get size
+ *
+ * Return size in bytes of memory managed by the pool.
+ */
+size_t gen_pool_size(struct gen_pool *pool)
+{
+ struct gen_pool_chunk *chunk;
+ size_t size = 0;
+
+ list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
+ size += chunk->end_addr - chunk->start_addr;
+ return size;
+}
+EXPORT_SYMBOL_GPL(gen_pool_size);
--
1.7.2.3
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).
Signed-off-by: Huang Ying <[email protected]>
Acked-by: Mike Frysinger <[email protected]>
Acked-by: Paul Mundt <[email protected]>
Acked-by: Hans-Christian Egtvedt <[email protected]>
Acked-by: Benjamin Herrenschmidt <[email protected]>
Acked-by: Chris Metcalf <[email protected]>
CC: Richard Henderson <[email protected]>
CC: Russell King <[email protected]>
CC: Mikael Starvik <[email protected]>
CC: David Howells <[email protected]>
CC: Yoshinori Sato <[email protected]>
CC: Tony Luck <[email protected]>
CC: Hirokazu Takata <[email protected]>
CC: Geert Uytterhoeven <[email protected]>
CC: Michal Simek <[email protected]>
CC: Ralf Baechle <[email protected]>
CC: Kyle McMartin <[email protected]>
CC: Martin Schwidefsky <[email protected]>
CC: Chen Liqin <[email protected]>
CC: "David S. Miller" <[email protected]>
CC: Ingo Molnar <[email protected]>
CC: Chris Zankel <[email protected]>
---
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(-)
diff --git a/arch/Kconfig b/arch/Kconfig
index f78c2be..8dea68d 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -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"
diff --git a/arch/alpha/Kconfig b/arch/alpha/Kconfig
index 943fe69..4252a77 100644
--- a/arch/alpha/Kconfig
+++ b/arch/alpha/Kconfig
@@ -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
diff --git a/arch/avr32/Kconfig b/arch/avr32/Kconfig
index 313b130..1fc9bf8 100644
--- a/arch/avr32/Kconfig
+++ b/arch/avr32/Kconfig
@@ -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
diff --git a/arch/frv/Kconfig b/arch/frv/Kconfig
index 77deacd..01b5adb 100644
--- a/arch/frv/Kconfig
+++ b/arch/frv/Kconfig
@@ -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
diff --git a/arch/ia64/Kconfig b/arch/ia64/Kconfig
index e0f5b6d..2cacfa7 100644
--- a/arch/ia64/Kconfig
+++ b/arch/ia64/Kconfig
@@ -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
diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
index bc9271b..8259bd1 100644
--- a/arch/m68k/Kconfig
+++ b/arch/m68k/Kconfig
@@ -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
diff --git a/arch/parisc/Kconfig b/arch/parisc/Kconfig
index ca59250..79a3560 100644
--- a/arch/parisc/Kconfig
+++ b/arch/parisc/Kconfig
@@ -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
diff --git a/arch/powerpc/Kconfig b/arch/powerpc/Kconfig
index 9d44ad3..56a57ea 100644
--- a/arch/powerpc/Kconfig
+++ b/arch/powerpc/Kconfig
@@ -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
diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index c05d081..d3ff45d 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig
@@ -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
diff --git a/arch/sh/Kconfig b/arch/sh/Kconfig
index 84d8c87..a48f6fb 100644
--- a/arch/sh/Kconfig
+++ b/arch/sh/Kconfig
@@ -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
diff --git a/arch/sparc/Kconfig b/arch/sparc/Kconfig
index af40adf..8b70990 100644
--- a/arch/sparc/Kconfig
+++ b/arch/sparc/Kconfig
@@ -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
diff --git a/arch/tile/Kconfig b/arch/tile/Kconfig
index e11b5fc..b8ebec6 100644
--- a/arch/tile/Kconfig
+++ b/arch/tile/Kconfig
@@ -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
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index fe0bdb4..1b01117 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
--
1.7.2.3
Cmpxchg 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.
Signed-off-by: Huang Ying <[email protected]>
Reviewed-by: Andi Kleen <[email protected]>
---
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
diff --git a/include/linux/llist.h b/include/linux/llist.h
new file mode 100644
index 0000000..ab4b673
--- /dev/null
+++ b/include/linux/llist.h
@@ -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 */
diff --git a/lib/Kconfig b/lib/Kconfig
index ff13cd7..4e8dd2d 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -237,4 +237,7 @@ config IOQ
If unsure, say N
+config LLIST
+ bool
+
endmenu
diff --git a/lib/Makefile b/lib/Makefile
index 92212ff..d8648ad6 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -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
diff --git a/lib/llist.c b/lib/llist.c
new file mode 100644
index 0000000..f016011
--- /dev/null
+++ b/lib/llist.c
@@ -0,0 +1,97 @@
+/*
+ * 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_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);
--
1.7.2.3
On Thu, 2010-12-16 at 14:59 +0800, Huang Ying wrote:
> 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.
On Thu, 2010-12-16 at 17:24 +0800, Peter Zijlstra wrote:
> On Thu, 2010-12-16 at 14:59 +0800, Huang Ying wrote:
> > 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
On Fri, 2010-12-17 at 08:20 +0800, Huang Ying wrote:
> On Thu, 2010-12-16 at 17:24 +0800, Peter Zijlstra wrote:
> > On Thu, 2010-12-16 at 14:59 +0800, Huang Ying wrote:
> > > 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?
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.
On Fri, Dec 17, 2010 at 8:22 PM, Peter Zijlstra <[email protected]> wrote:
> On Fri, 2010-12-17 at 08:20 +0800, Huang Ying wrote:
>> On Thu, 2010-12-16 at 17:24 +0800, Peter Zijlstra wrote:
>> > On Thu, 2010-12-16 at 14:59 +0800, Huang Ying wrote:
>> > > 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?
>
> 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.
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.
> 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
B1;2401;0cOn Fri, 17 Dec 2010, huang ying wrote:
> On Fri, Dec 17, 2010 at 8:22 PM, Peter Zijlstra <[email protected]> wrote:
> > 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
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.
> 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:
>> > ... 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