Skip to contentSkip to conversation

Lock-less list

RFC In review Huang Ying 4 participants 13 messages Dec 23, 2010 – Dec 24, 2010

Subsystems (11)
Networking x86 PowerPC Library code +7 more subsystems
lore
Share & tools
lore

Huang Ying

author
#0 lore raw

cover Lock-less list

Add a lock-less NULL-terminated linked list implementation. And use that in irq_work and replace net/rds/xlist.h.

v9:

- Split out lock-less allocator, will repost allocator with its user in another patchset.
- Use lock-less list in irq_work and replace net/rds/xlist.h

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

[RFC -v9 1/4] Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG [RFC -v9 2/4] lib, Add lock-less NULL terminated single list [RFC -v9 3/4] irq_work, Use llist in irq_work
[RFC -v9 4/4] net, rds, Replace xlist in net/rds/xlist.h with llist

author
#1 lore raw

RFC 1/4 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).

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(+)
arch/Kconfig +3 -0
@@ -175,4 +175,7 @@ config HAVE_PERF_EVENTS_NMI
 config HAVE_ARCH_JUMP_LABEL
 	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
@@ -138,6 +138,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
@@ -94,6 +94,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
maintainer
#2 lore raw

Re: [RFC -v9 1/4] Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG

From: Huang Ying <[email protected]>
Date: Thu, 23 Dec 2010 13:43:20 +0800

arch/sparc/Kconfig config SPARC · line 28

Quoted 10 lines
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

This should only be set for "SPARC64". SPARC32's cmpxchg uses spinlocks and IRQ disabling, which is not NMI safe.

author
#3 lore raw

Re: [RFC -v9 1/4] Add Kconfig option ARCH_HAVE_NMI_SAFE_CMPXCHG

Hi, David,

Thanks for review.

Quoted 16 lines · David Miller

From: Huang Ying <[email protected]>
Date: Thu, 23 Dec 2010 13:43:20 +0800

arch/sparc/Kconfig config SPARC · line 28

Quoted 10 lines
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

This should only be set for "SPARC64". SPARC32's cmpxchg uses spinlocks and IRQ disabling, which is not NMI safe.

I will fix this.

Best Regards,
Huang Ying

author
#4 lore raw

RFC 2/4 lib, Add lock-less NULL terminated single list

In reply to Huang Ying

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.

---
 include/linux/llist.h |   99 +++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig           |    3 +
 lib/Makefile          |    2 
 lib/llist.c           |  119 ++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 223 insertions(+)
 create mode 100644 include/linux/llist.h
 create mode 100644 lib/llist.c
include/linux/llist.h new file +99 -0
@@ -0,0 +1,99 @@
+#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);
+void llist_add_batch(struct llist_node *new, struct llist_node *tail,
+		     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
@@ -210,4 +210,7 @@ config GENERIC_ATOMIC64
 config LRU_CACHE
 	tristate
 
+config LLIST
+	bool
+
 endmenu
lib/Makefile +2 -0
@@ -106,6 +106,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic
 
 obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
 
+obj-$(CONFIG_LLIST) += llist.o
+
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
 
lib/llist.c new file +119 -0

119 lines not on this page · raw message

author
#5 lore raw

RFC 3/4 irq_work, Use llist in irq_work

In reply to Huang Ying

Use llist in irq_work instead of the lock-less linked list implementation in irq_work to avoid the code duplication.

Cc Peter Zijlstra <[email protected]>
---
 include/linux/irq_work.h |   15 ++++---
 init/Kconfig             |    1 
 kernel/irq_work.c        |   90 ++++++++++++++++++-----------------------------
 3 files changed, 46 insertions(+), 60 deletions(-)
include/linux/irq_work.h +9 -6
@@ -1,20 +1,23 @@
 #ifndef _LINUX_IRQ_WORK_H
 #define _LINUX_IRQ_WORK_H
 
+#include <linux/llist.h>
+
 struct irq_work {
-	struct irq_work *next;
+	unsigned long flags;
+	struct llist_node llnode;
 	void (*func)(struct irq_work *);
 };
 
 static inline
-void init_irq_work(struct irq_work *entry, void (*func)(struct irq_work *))
+void init_irq_work(struct irq_work *work, void (*func)(struct irq_work *))
 {
-	entry->next = NULL;
-	entry->func = func;
+	work->flags = 0;
+	work->func = func;
 }
 
-bool irq_work_queue(struct irq_work *entry);
+bool irq_work_queue(struct irq_work *work);
 void irq_work_run(void);
-void irq_work_sync(struct irq_work *entry);
+void irq_work_sync(struct irq_work *work);
 
 #endif /* _LINUX_IRQ_WORK_H */
init/Kconfig +1 -0
@@ -27,6 +27,7 @@ config HAVE_IRQ_WORK
 config IRQ_WORK
 	bool
 	depends on HAVE_IRQ_WORK
+	select LLIST
 
 menu "General setup"
 
kernel/irq_work.c +36 -54

166 lines not on this page · raw message

author
#6 lore raw

RFC 4/4 net, rds, Replace xlist in net/rds/xlist.h with llist

In reply to Huang Ying

The functionality of xlist and llist is almost same. This patch replace xlist with llist to avoid code duplication.

Known issues: don't know how to test this, need special hardware?

---
 net/rds/Kconfig   |    1 
 net/rds/ib_rdma.c |  110 ++++++++++++++++++++++++------------------------------
 net/rds/xlist.h   |   80 ---------------------------------------
 3 files changed, 50 insertions(+), 141 deletions(-)
 delete mode 100644 net/rds/xlist.h
net/rds/Kconfig +1 -0
@@ -9,6 +9,7 @@ config RDS
 
 config RDS_RDMA
 	tristate "RDS over Infiniband and iWARP"
+	select LLIST
 	depends on RDS && INFINIBAND && INFINIBAND_ADDR_TRANS
 	---help---
 	  Allow RDS to use Infiniband and iWARP as a transport.
net/rds/ib_rdma.c +49 -61

212 lines not on this page · raw message

net/rds/xlist.h deleted +0 -80

80 lines not on this page · raw message

#7 lore raw

Re: [RFC -v9 4/4] net, rds, Replace xlist in net/rds/xlist.h with llist

Quoted 9 lines · Huang Ying

The functionality of xlist and llist is almost same. This patch replace xlist with llist to avoid code duplication.

/*
- * this takes a list head of mrs and turns it into an xlist of clusters.
- * each cluster has an xlist of MR_CLUSTER_SIZE mrs that are ready for
- * reuse.
+ * this takes a list head of mrs and turns it into linked llist nodes. */

This comment change loses a lot of information. The original 3 lines tells me a lot about what the data structure is and what it's used for, the replacement is a 'b +=5; /* add 5 to b */' type of comment.

author
#8 lore raw

Re: [RFC -v9 4/4] net, rds, Replace xlist in net/rds/xlist.h with llist

Hi,

Quoted 11 lines · On Thu, 2010-12-23 at 15:05 +0800, [email protected] wrote:
Quoted 9 lines · Huang Ying

The functionality of xlist and llist is almost same. This patch replace xlist with llist to avoid code duplication.

/*
- * this takes a list head of mrs and turns it into an xlist of clusters.
- * each cluster has an xlist of MR_CLUSTER_SIZE mrs that are ready for
- * reuse.
+ * this takes a list head of mrs and turns it into linked llist nodes. */

Quoted 3 lines

This comment change loses a lot of information. The original 3 lines tells me a lot about what the data structure is and what it's used for, the replacement is a 'b +=5; /* add 5 to b */' type of comment.

Sorry, maybe I misunderstand the comments and code. From comments I imagine the result is a two-dimension lock-less list, but from the code I only find an one-dimension lock-less list. Is it?

Best Regards,
Huang Ying

#9 lore raw

Re: [RFC -v9 4/4] net, rds, Replace xlist in net/rds/xlist.h with llist

In reply to Huang Ying

Excerpts from Huang Ying's message of 2010-12-23 00:43:23 -0500:

Quoted 2 lines

The functionality of xlist and llist is almost same. This patch replace xlist with llist to avoid code duplication.

I'm not against it, the goal was always to move this to include/linux as more users popped up. We can test it out here with rds RDMA.

-chris

author
#10 lore raw

Re: [RFC -v9 4/4] net, rds, Replace xlist in net/rds/xlist.h with llist

Quoted 6 lines · Chris Mason

Excerpts from Huang Ying's message of 2010-12-23 00:43:23 -0500:

Quoted 2 lines

The functionality of xlist and llist is almost same. This patch replace xlist with llist to avoid code duplication.

I'm not against it, the goal was always to move this to include/linux as more users popped up. We can test it out here with rds RDMA.

Thanks for your helping.

Best Regards,
Huang Ying

#11 lore raw
In reply to Huang Ying
Quoted 2 lines · Huang Ying

Add a lock-less NULL-terminated linked list implementation. And use that in irq_work and replace net/rds/xlist.h.

A quick overview of the code looks mostly sane. What I don't see is an explanation of *why* this is being added. What benefits does it have over the current code? Is it faster? Smaller? Simply getting rid of near-duplicate versions in rds and irq_work? Something else?

author
#12 lore raw

Hi, Valdis,

Thanks for your comments.

Quoted 8 lines · On Thu, 2010-12-23 at 14:05 +0800, [email protected] wrote:
Quoted 2 lines · Huang Ying

Add a lock-less NULL-terminated linked list implementation. And use that in irq_work and replace net/rds/xlist.h.

A quick overview of the code looks mostly sane. What I don't see is an explanation of *why* this is being added. What benefits does it have over the current code? Is it faster? Smaller? Simply getting rid of near-duplicate versions in rds and irq_work? Something else?

The code is almost same. Just to avoid code duplicating, provide better document, and make it easier for future users.

Best Regards,
Huang Ying