[RFC patch 0/2] API renaming: "llist" (lockless list) to "llstack" (lockless stack)

[RFC patch 0/2] API renaming: "llist" (lockless list) to "llstack" (lockless stack)

[Mathieu Desnoyers]

Hi,

I am proposing these 2 patches:

1) Rename the llist API into llstack
2) make llstack_push return "prior empty state" information

The API change in (2) assumes that this "lockless list" behaves like a
stack. Having a "list" API that has a stack behavior cast in stone does
not make sense, but nevertheless some stack properties are really
useful. So reflect the behavior of the lockless structure (stack/lifo)
into the API.

These patches apply on Linux v3.1-rc4.

Comments are welcome,

Best regards,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

[RFC patch 1/2] Rename the "llist" (lockless list) to "llstack" (lockless stack)

[Mathieu Desnoyers]

[-- Attachment #1: llist-rename-to-llstack.patch --]
[-- Type: text/plain, Size: 25599 bytes --]

The API we can provide with a lock-less structure does not only depend
on how the elements are organized, but also on the operations allowed on
the structure. So the API should reflect that.

This is illustrated by the following feature request: Previously, the
concensus was to keep the "llist" name until we could gather evidence
that this name is inappropriate. A feature request from Peter Zijlstra
outlines very well the need for an llstack API that allows the push
operation to return whether the stack was empty or not before the
operation.

By taking advantage of the stack structure, the "push" operation can
return whether the stack was empty or not prior to the push with almost
no cost (the old stack head is already in registers). Adding this
feature to the push API is not a good fit for a "generic llist" API
however, because it would cast in stone the fact that this llist behaves
like a stack.

The only reason why we can get away this easily with knowing atomically
if the structure was empty prior to the insertion is because this "list"
behaves like a stack (LIFO). I foresee we'll need to add "lockless
queues" at some point (with FIFO behavior), which has the ability to
enqueue/dequeue concurrently without sharing the same cache-lines when
the queue is non-empty. Within that kind of queue structure, knowing if
the queue was empty prior to insertion would become a bottleneck, so I
would not advise to make that part of _that_ API, which would require to
add a new "llqueue" API. And at that point, the "llist" vs "llqueue"
semantic would become really confusing. This is why I propose to rename
the "llist" to the less confusing "llstack" right away.

If we don't fix that now, I think we're heading into a lock-free
structure namespacing trainwreck that will limit our ability to add
other lock-free operations due vague naming that does not take the
operations allowed on the structure into consideration, combined with
API constraints permitted by a specific given behavior (e.g. FIFO
semantic) that tend to define these lock-free APIs.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Huang Ying <ying.huang@intel.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: "lenb@kernel.org" <lenb@kernel.org>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 drivers/acpi/apei/Kconfig |    2 
 drivers/acpi/apei/ghes.c  |   19 +++---
 include/linux/llist.h     |  126 --------------------------------------------
 include/linux/llstack.h   |  126 ++++++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig               |    2 
 lib/Makefile              |    2 
 lib/llist.c               |  129 ----------------------------------------------
 lib/llstack.c             |  129 ++++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 268 insertions(+), 267 deletions(-)

Index: linux-2.6-lttng/include/linux/llist.h
===================================================================
--- linux-2.6-lttng.orig/include/linux/llist.h
+++ /dev/null
@@ -1,126 +0,0 @@
-#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 (or llist_del_all, 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.
- *
- * This can be summarized as follow:
- *
- *           |   add    | del_first |  del_all
- * add       |    -     |     -     |     -
- * del_first |          |     L     |     L
- * del_all   |          |           |     -
- *
- * Where "-" stands for no lock is needed, while "L" stands for lock
- * is needed.
- *
- * 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.
- * The order of deleted entries is from the newest to the oldest added
- * one.  If you want to traverse from the oldest to the newest, you
- * must reverse the order by yourself before traversing.
- *
- * 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.
- *
- * If being used on entries deleted from lock-less list directly, the
- * traverse order is from the newest to the oldest added entry.  If
- * you want to traverse from the oldest to the newest, you must
- * reverse the order by yourself before traversing.
- */
-#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.
- *
- * If being used on entries deleted from lock-less list directly, the
- * traverse order is from the newest to the oldest added entry.  If
- * you want to traverse from the oldest to the newest, you must
- * reverse the order by yourself before traversing.
- */
-#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
- *
- * Not guaranteed to be accurate or up to date.  Just a quick way to
- * test whether the list is empty without deleting something from the
- * list.
- */
-static inline int llist_empty(const struct llist_head *head)
-{
-	return ACCESS_ONCE(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 */
Index: linux-2.6-lttng/include/linux/llstack.h
===================================================================
--- /dev/null
+++ linux-2.6-lttng/include/linux/llstack.h
@@ -0,0 +1,126 @@
+#ifndef LLSTACK_H
+#define LLSTACK_H
+/*
+ * Lock-less NULL terminated single linked list stack (LIFO)
+ *
+ * If there are multiple producers and multiple consumers, llstack_add
+ * can be used in producers and llstack_del_all can be used in
+ * consumers.  They can work simultaneously without lock.  But
+ * llstack_del_first can not be used here.  Because llstack_del_first
+ * depends on list->first->next does not changed if list->first is not
+ * changed during its operation, but llstack_del_first, llstack_add,
+ * llstack_add (or llstack_del_all, llstack_add, llstack_add) sequence in
+ * another consumer may violate that.
+ *
+ * If there are multiple producers and one consumer, llstack_add can be
+ * used in producers and llstack_del_all or llstack_del_first can be used
+ * in the consumer.
+ *
+ * This can be summarized as follow:
+ *
+ *           |  push    |    pop    |  pop_all
+ * push      |    -     |     -     |     -
+ * pop       |          |     L     |     L
+ * pop_all   |          |           |     -
+ *
+ * Where "-" stands for no lock is needed, while "L" stands for lock
+ * is needed.
+ *
+ * The list entries deleted via llstack_del_all can be traversed with
+ * traversing function such as llstack_for_each etc.  But the list
+ * entries can not be traversed safely before deleted from the list.
+ * The order of deleted entries is from the newest to the oldest added
+ * one.  If you want to traverse from the oldest to the newest, you
+ * must reverse the order by yourself before traversing.
+ *
+ * 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 llstack_head {
+	struct llstack_node *first;
+};
+
+struct llstack_node {
+	struct llstack_node *next;
+};
+
+#define LLSTACK_HEAD_INIT(name)	{ NULL }
+#define LLSTACK_HEAD(name)	struct llstack_head name = LLSTACK_HEAD_INIT(name)
+
+/**
+ * init_llstack_head - initialize lock-less list stack head
+ * @head:	the head for your lock-less list stack
+ */
+static inline void init_llstack_head(struct llstack_head *stack)
+{
+	stack->first = NULL;
+}
+
+/**
+ * llstack_entry - get the struct of this entry
+ * @ptr:	the &struct llstack_node pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the llstack_node within the struct.
+ */
+#define llstack_entry(ptr, type, member)		\
+	container_of(ptr, type, member)
+
+/**
+ * llstack_for_each - iterate over some deleted entries of a lock-less stack
+ * @pos:	the &struct llstack_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.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ */
+#define llstack_for_each(pos, node)			\
+	for ((pos) = (node); pos; (pos) = (pos)->next)
+
+/**
+ * llstack_for_each_entry - iterate over some deleted entries of lock-less stack 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 llstack_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.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ */
+#define llstack_for_each_entry(pos, node, member)			\
+	for ((pos) = llstack_entry((node), typeof(*(pos)), member);	\
+	     &(pos)->member != NULL;					\
+	     (pos) = llstack_entry((pos)->member.next, typeof(*(pos)), member))
+
+/**
+ * llstack_empty - tests whether a lock-less stack is empty
+ * @head:	the stack to test
+ *
+ * Not guaranteed to be accurate or up to date.  Just a quick way to
+ * test whether the list is empty without deleting something from the
+ * list.
+ */
+static inline int llstack_empty(const struct llstack_head *head)
+{
+	return ACCESS_ONCE(head->first) == NULL;
+}
+
+void llstack_push(struct llstack_node *new, struct llstack_head *head);
+void llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
+			struct llstack_head *head);
+struct llstack_node *llstack_pop(struct llstack_head *head);
+struct llstack_node *llstack_pop_all(struct llstack_head *head);
+#endif /* LLSTACK_H */
Index: linux-2.6-lttng/lib/Kconfig
===================================================================
--- linux-2.6-lttng.orig/lib/Kconfig
+++ linux-2.6-lttng/lib/Kconfig
@@ -276,7 +276,7 @@ config CORDIC
 	  so its calculations are in fixed point. Modules can select this
 	  when they require this function. Module will be called cordic.
 
-config LLIST
+config LLSTACK
 	bool
 
 endmenu
Index: linux-2.6-lttng/lib/Makefile
===================================================================
--- linux-2.6-lttng.orig/lib/Makefile
+++ linux-2.6-lttng/lib/Makefile
@@ -115,7 +115,7 @@ obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
 
 obj-$(CONFIG_CORDIC) += cordic.o
 
-obj-$(CONFIG_LLIST) += llist.o
+obj-$(CONFIG_LLSTACK) += llstack.o
 
 hostprogs-y	:= gen_crc32table
 clean-files	:= crc32table.h
Index: linux-2.6-lttng/lib/llist.c
===================================================================
--- linux-2.6-lttng.orig/lib/llist.c
+++ /dev/null
@@ -1,129 +0,0 @@
-/*
- * 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,2011 Intel Corp.
- *   Author: Huang Ying <ying.huang@intel.com>
- *
- * 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, *old_entry;
-
-#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
-	BUG_ON(in_nmi());
-#endif
-
-	entry = head->first;
-	do {
-		old_entry = entry;
-		new->next = entry;
-		cpu_relax();
-	} while ((entry = cmpxchg(&head->first, old_entry, new)) != old_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, *old_entry;
-
-#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
-	BUG_ON(in_nmi());
-#endif
-
-	entry = head->first;
-	do {
-		old_entry = entry;
-		new_last->next = entry;
-		cpu_relax();
-	} while ((entry = cmpxchg(&head->first, old_entry, new_first)) != old_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, this is the newest added one.
- *
- * 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 (or llist_del_all, 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 or use lock between consumers.
- */
-struct llist_node *llist_del_first(struct llist_head *head)
-{
-	struct llist_node *entry, *old_entry, *next;
-
-#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
-	BUG_ON(in_nmi());
-#endif
-
-	entry = head->first;
-	do {
-		if (entry == NULL)
-			return NULL;
-		old_entry = entry;
-		next = entry->next;
-		cpu_relax();
-	} while ((entry = cmpxchg(&head->first, old_entry, next)) != old_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.  The order of entries
- * deleted is from the newest to the oldest added one.
- */
-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);
Index: linux-2.6-lttng/lib/llstack.c
===================================================================
--- /dev/null
+++ linux-2.6-lttng/lib/llstack.c
@@ -0,0 +1,129 @@
+/*
+ * Lock-less NULL terminated single linked list stack (LIFO)
+ *
+ * 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,2011 Intel Corp.
+ *   Author: Huang Ying <ying.huang@intel.com>
+ *
+ * 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/llstack.h>
+
+#include <asm/system.h>
+
+/**
+ * llstack_push - push a node into a lock-less stack.
+ * @new:       new entry to be added
+ * @head:      the head for your lock-less stack
+ */
+void llstack_push(struct llstack_node *new, struct llstack_head *head)
+{
+	struct llstack_node *entry, *old_entry;
+
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+	BUG_ON(in_nmi());
+#endif
+
+	entry = head->first;
+	do {
+		old_entry = entry;
+		new->next = entry;
+		cpu_relax();
+	} while ((entry = cmpxchg(&head->first, old_entry, new)) != old_entry);
+}
+EXPORT_SYMBOL_GPL(llstack_push);
+
+/**
+ * llstack_push_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 llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
+			struct llstack_head *head)
+{
+	struct llstack_node *entry, *old_entry;
+
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+	BUG_ON(in_nmi());
+#endif
+
+	entry = head->first;
+	do {
+		old_entry = entry;
+		new_last->next = entry;
+		cpu_relax();
+	} while ((entry = cmpxchg(&head->first, old_entry, new_first)) != old_entry);
+}
+EXPORT_SYMBOL_GPL(llstack_push_batch);
+
+/**
+ * llstack_pop - pop the first entry of lock-less list stack
+ * @head:	the head for your lock-less list
+ *
+ * If stack is empty, return NULL, otherwise, return the first entry
+ * removed, this is the newest added one.
+ *
+ * Only one llstack_pop user can be used simultaneously with
+ * multiple llstack_push users without lock.  Because otherwise
+ * llstack_pop, llstack_push, llstack_push (or llstack_pop_all, llstack_push,
+ * llstack_push) sequence in another user may change @head->first->next,
+ * but keep @head->first.  If multiple consumers are needed, please
+ * use llstack_pop_all or use lock between consumers.
+ */
+struct llstack_node *llstack_pop(struct llstack_head *head)
+{
+	struct llstack_node *entry, *old_entry, *next;
+
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+	BUG_ON(in_nmi());
+#endif
+
+	entry = head->first;
+	do {
+		if (entry == NULL)
+			return NULL;
+		old_entry = entry;
+		next = entry->next;
+		cpu_relax();
+	} while ((entry = cmpxchg(&head->first, old_entry, next)) != old_entry);
+
+	return entry;
+}
+EXPORT_SYMBOL_GPL(llstack_pop);
+
+/**
+ * llstack_pop_all - remove all entries from lock-less list stack
+ * @head:	the head of lock-less list to delete all entries
+ *
+ * If list stack is empty, return NULL, otherwise, delete all entries and
+ * return the pointer to the first entry.  The order of entries
+ * deleted is from the newest to the oldest added one.
+ */
+struct llstack_node *llstack_pop_all(struct llstack_head *head)
+{
+#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
+	BUG_ON(in_nmi());
+#endif
+
+	return xchg(&head->first, NULL);
+}
+EXPORT_SYMBOL_GPL(llstack_pop_all);
Index: linux-2.6-lttng/drivers/acpi/apei/ghes.c
===================================================================
--- linux-2.6-lttng.orig/drivers/acpi/apei/ghes.c
+++ linux-2.6-lttng/drivers/acpi/apei/ghes.c
@@ -43,7 +43,7 @@
 #include <linux/ratelimit.h>
 #include <linux/vmalloc.h>
 #include <linux/irq_work.h>
-#include <linux/llist.h>
+#include <linux/llstack.h>
 #include <linux/genalloc.h>
 #include <acpi/apei.h>
 #include <acpi/atomicio.h>
@@ -105,7 +105,7 @@ struct ghes {
 };
 
 struct ghes_estatus_node {
-	struct llist_node llnode;
+	struct llstack_node llnode;
 	struct acpi_hest_generic *generic;
 };
 
@@ -168,13 +168,13 @@ static DEFINE_SPINLOCK(ghes_ioremap_lock
  * printk is not safe in NMI context.  So in NMI handler, we allocate
  * required memory from lock-less memory allocator
  * (ghes_estatus_pool), save estatus into it, put them into lock-less
- * list (ghes_estatus_llist), then delay printk into IRQ context via
+ * list (ghes_estatus_llstack), then delay printk into IRQ context via
  * irq_work (ghes_proc_irq_work).  ghes_estatus_size_request record
  * required pool size by all NMI error source.
  */
 static struct gen_pool *ghes_estatus_pool;
 static unsigned long ghes_estatus_pool_size_request;
-static struct llist_head ghes_estatus_llist;
+static struct llstack_head ghes_estatus_llstack;
 static struct irq_work ghes_proc_irq_work;
 
 struct ghes_estatus_cache *ghes_estatus_caches[GHES_ESTATUS_CACHES_SIZE];
@@ -712,7 +712,7 @@ static int ghes_notify_sci(struct notifi
 
 static void ghes_proc_in_irq(struct irq_work *irq_work)
 {
-	struct llist_node *llnode, *next, *tail = NULL;
+	struct llstack_node *llnode, *next, *tail = NULL;
 	struct ghes_estatus_node *estatus_node;
 	struct acpi_hest_generic *generic;
 	struct acpi_hest_generic_status *estatus;
@@ -722,7 +722,7 @@ static void ghes_proc_in_irq(struct irq_
 	 * Because the time order of estatus in list is reversed,
 	 * revert it back to proper order.
 	 */
-	llnode = llist_del_all(&ghes_estatus_llist);
+	llnode = llstack_pop_all(&ghes_estatus_llstack);
 	while (llnode) {
 		next = llnode->next;
 		llnode->next = tail;
@@ -732,8 +732,8 @@ static void ghes_proc_in_irq(struct irq_
 	llnode = tail;
 	while (llnode) {
 		next = llnode->next;
-		estatus_node = llist_entry(llnode, struct ghes_estatus_node,
-					   llnode);
+		estatus_node = llstack_entry(llnode, struct ghes_estatus_node,
+					     llnode);
 		estatus = GHES_ESTATUS_FROM_NODE(estatus_node);
 		len = apei_estatus_len(estatus);
 		node_len = GHES_ESTATUS_NODE_LEN(len);
@@ -806,7 +806,8 @@ static int ghes_notify_nmi(struct notifi
 			estatus_node->generic = ghes->generic;
 			estatus = GHES_ESTATUS_FROM_NODE(estatus_node);
 			memcpy(estatus, ghes->estatus, len);
-			llist_add(&estatus_node->llnode, &ghes_estatus_llist);
+			llstack_push(&estatus_node->llnode,
+				     &ghes_estatus_llstack);
 		}
 next:
 #endif
Index: linux-2.6-lttng/drivers/acpi/apei/Kconfig
===================================================================
--- linux-2.6-lttng.orig/drivers/acpi/apei/Kconfig
+++ linux-2.6-lttng/drivers/acpi/apei/Kconfig
@@ -13,7 +13,7 @@ config ACPI_APEI_GHES
 	bool "APEI Generic Hardware Error Source"
 	depends on ACPI_APEI && X86
 	select ACPI_HED
-	select LLIST
+	select LLSTACK
 	select GENERIC_ALLOCATOR
 	help
 	  Generic Hardware Error Source provides a way to report

[RFC patch 2/2] llstack: make llstack_push return "prior empty state" information

[Mathieu Desnoyers]

[-- Attachment #1: llstack-push-return-empty-state.patch --]
[-- Type: text/plain, Size: 3630 bytes --]

A feature request from Peter Zijlstra outlines very well the need for an
llstack API that allows the push operation to return whether the stack
was empty or not before the operation. Peter wants to use this
information to know if a irq_work should be raised when pushing into the
stack.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
CC: Huang Ying <ying.huang@intel.com>
CC: Andi Kleen <andi@firstfloor.org>
CC: "lenb@kernel.org" <lenb@kernel.org>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Andrew Morton <akpm@linux-foundation.org>
---
 include/linux/llstack.h |    6 +++---
 lib/llstack.c           |   15 +++++++++++++--
 2 files changed, 16 insertions(+), 5 deletions(-)

Index: linux-2.6-lttng/lib/llstack.c
===================================================================
--- linux-2.6-lttng.orig/lib/llstack.c
+++ linux-2.6-lttng/lib/llstack.c
@@ -8,6 +8,7 @@
  *
  * Copyright 2010,2011 Intel Corp.
  *   Author: Huang Ying <ying.huang@intel.com>
+ * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License version
@@ -33,8 +34,11 @@
  * llstack_push - push a node into a lock-less stack.
  * @new:       new entry to be added
  * @head:      the head for your lock-less stack
+ *
+ * Returns 0 if the stack was empty prior to push operation (check performed
+ * atomically with push), returns 1 otherwise.
  */
-void llstack_push(struct llstack_node *new, struct llstack_head *head)
+int llstack_push(struct llstack_node *new, struct llstack_head *head)
 {
 	struct llstack_node *entry, *old_entry;
 
@@ -48,6 +52,8 @@ void llstack_push(struct llstack_node *n
 		new->next = entry;
 		cpu_relax();
 	} while ((entry = cmpxchg(&head->first, old_entry, new)) != old_entry);
+
+	return !!(unsigned long) entry;
 }
 EXPORT_SYMBOL_GPL(llstack_push);
 
@@ -56,8 +62,11 @@ EXPORT_SYMBOL_GPL(llstack_push);
  * @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
+ *
+ * Returns 0 if the stack was empty prior to push operation (check performed
+ * atomically with push), returns 1 otherwise.
  */
-void llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
+int llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
 			struct llstack_head *head)
 {
 	struct llstack_node *entry, *old_entry;
@@ -72,6 +81,8 @@ void llstack_push_batch(struct llstack_n
 		new_last->next = entry;
 		cpu_relax();
 	} while ((entry = cmpxchg(&head->first, old_entry, new_first)) != old_entry);
+
+	return !!(unsigned long) entry;
 }
 EXPORT_SYMBOL_GPL(llstack_push_batch);
 
Index: linux-2.6-lttng/include/linux/llstack.h
===================================================================
--- linux-2.6-lttng.orig/include/linux/llstack.h
+++ linux-2.6-lttng/include/linux/llstack.h
@@ -118,9 +118,9 @@ static inline int llstack_empty(const st
 	return ACCESS_ONCE(head->first) == NULL;
 }
 
-void llstack_push(struct llstack_node *new, struct llstack_head *head);
-void llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
-			struct llstack_head *head);
+int llstack_push(struct llstack_node *new, struct llstack_head *head);
+int llstack_push_batch(struct llstack_node *new_first, struct llstack_node *new_last,
+		       struct llstack_head *head);
 struct llstack_node *llstack_pop(struct llstack_head *head);
 struct llstack_node *llstack_pop_all(struct llstack_head *head);
 #endif /* LLSTACK_H */

Re: [RFC patch 1/2] Rename the "llist" (lockless list) to "llstack" (lockless stack)

[Andi Kleen]

I don't see why a rename is necessary. People implement stacks and queues
and all other kinds of data structures using the standard list.h.
No reason why this shouldn't work with llist.h either.

I would assume everyone hacking on the Linux kernel will understand
that a list can be used as a building block for all of these.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [RFC patch 1/2] Rename the "llist" (lockless list) to "llstack" (lockless stack)

[Mathieu Desnoyers]

Hi Andi,

* Andi Kleen (andi@firstfloor.org) wrote:
> 
> I don't see why a rename is necessary. People implement stacks and queues
> and all other kinds of data structures using the standard list.h.
> No reason why this shouldn't work with llist.h either.

What you are saying here is only partially true. Gien that Linux
supports multiprocessing, people implement stack ans queues with list.h
_and_ mutual exclusion (spin locks, mutexes, rwlocks) for SMP
synchronization.

The flexibility of list.h combined with the flexibility of mutual
exclusion synchronisation primitives allow people to implement basically
all the list-based data structure they feel like implementing, with the
known performance downsides of mutual exclusion: only one thread can
touch the data structure at a given time, and touching the mutex adds
cache-line bouncing. It's also not permitted to use mutual exclusion in
NMI handlers.

However, in the realm of lock-free data structures, things are very much
different. Synchronization can be performed in a much more fine-grained
fashion and the data structure is tailored to the needed
synchronization, which enables performance enhancements not possible
with mutual-exclusion techniques. The lock-free queue is a good example
(FIFO behavior):

With list.h and mutexes, you would implement this queue very
straightforwardly using:

DEFINE_MUTEX(somemutex);
LIST_HEAD(somelist);

And then protect all list_add_tail (enqueue) operations and list_del of
list_first_entry (dequeue) operations with the mutex.

A lock-free queue has come very interesting advantages compared to the
mutex-protected queue. One of them being that if the queue list
structure is crafted appropriately, enqueuer and dequeuer threads can
concurrently enqueue and dequeue elements to/from the queue without
wrestling for the same cache-line (when there is at least one element in
the queue, which is usually the case when high-throughput matters).

Now some words about stacks (LIFO behavior):

You can indeed implement stacks with mutex/list.h by using list_add
(push) and list_del of list_first_entry (pop) protected by a mutex, with
the downside of having to touch both the mutex and the list head for
each of these operations. Also, this is not safe to use in NMI handlers,
which seems to be a use-case NMI handler implementors are facing
(which is I think what motivated the implementation of llist.h in the
first place).

A lock-free stack lets you do this with a single cmpxchg on the push,
and an xchg on the "pop all" (there are also variants that can use a
xchg() on the push). In addition, it lets you return whether the stack
was empty when performing the push operation, which is a feature quite
useful to know if a wakeup should be triggered or not.

But the data structures required to implement a lock-free queue and a
lock-free stack differ quite significantly: some ways to implement a
lock-free queue require either special sequence numbering of both ends,
or dummy elements that ensures the queue is never empty. The lock-free
stack can be implemented by putting a NULL bottom node to detect the end
of stack. Moreover, even though the stack "push" operation can return
whether the stack was previously empty at no cost, it is not true for
the queue, because this would require the enqueuer to touch the dequeuer
cache-lines.


> I would assume everyone hacking on the Linux kernel will understand
> that a list can be used as a building block for all of these.

Although strictly speaking this is true, I'm afraid a single "generic"
list container would be at best a building block for either efficient
lock-free queues or stacks, but not both.

This is why I'm proposing to turn the generic "llist.h" namespace into
the more specific "llstack.h", so the API reflects not only the basic
list structure, but also the exposed behavior and the implicit
synchronization performed within this API, because those are
intrinsically linked to the data structure layout, unlike
mutual-exclusion-based approaches.

Best regards,

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Re: [RFC patch 1/2] Rename the "llist" (lockless list) to "llstack" (lockless stack)

[Huang Ying]

IMHO, I prefer to keep "llist" as the name of the best general lock-less
list we can implemented.  Maybe in the future we can replace the
implementation totally, or add/change its API.  I don't like the name of
"llstack" because we don't want to implement or use a lock-less stack,
we just can only implement stack like operations so far,  maybe in the
future we can work out some solution for other operations.

Best Regards,
Huang Ying