Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1287999

[PATCH v2 tip/core/rcu 14/14] list: Add lockless list traversal primitives

Show all headers | View raw

From: Alexey Kardashevskiy <aik@ozlabs.ru>

Although list_for_each_entry_rcu() can in theory be used anywhere
preemption is disabled, it can result in calls to lockdep, which cannot
be used in certain constrained execution environments, such as exception
handlers that do not map the entire kernel into their address spaces.
This commit therefore adds list_entry_lockless() and
list_for_each_entry_lockless(), which never invoke lockdep and can
therefore safely be used from these constrained environments, but only
as long as those environments are non-preemptible (or items are never
deleted from the list).

Use synchronize_sched(), call_rcu_sched(), or synchronize_sched_expedited()
in updates for the needed grace periods.  Of course, if items are never
deleted from the list, there is no need to wait for grace periods.

Signed-off-by: Alexey Kardashevskiy <aik@ozlabs.ru>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 include/linux/rculist.h | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index 5ed540986019..1fad79861e14 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -305,6 +305,42 @@ static inline void list_splice_init_rcu(struct list_head *list,
 		pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
 
 /**
+ * list_entry_lockless - get the struct for this entry
+ * @ptr:        the &struct list_head pointer.
+ * @type:       the type of the struct this is embedded in.
+ * @member:     the name of the list_head within the struct.
+ *
+ * This primitive may safely run concurrently with the _rcu list-mutation
+ * primitives such as list_add_rcu(), but requires some implicit RCU
+ * read-side guarding.  One example is running within a special
+ * exception-time environment where preemption is disabled and where
+ * lockdep cannot be invoked (in which case updaters must use RCU-sched,
+ * as in synchronize_sched(), call_rcu_sched(), and friends).  Another
+ * example is when items are added to the list, but never deleted.
+ */
+#define list_entry_lockless(ptr, type, member) \
+	container_of((typeof(ptr))lockless_dereference(ptr), type, member)
+
+/**
+ * list_for_each_entry_lockless - iterate over rcu list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ *
+ * This primitive may safely run concurrently with the _rcu list-mutation
+ * primitives such as list_add_rcu(), but requires some implicit RCU
+ * read-side guarding.  One example is running within a special
+ * exception-time environment where preemption is disabled and where
+ * lockdep cannot be invoked (in which case updaters must use RCU-sched,
+ * as in synchronize_sched(), call_rcu_sched(), and friends).  Another
+ * example is when items are added to the list, but never deleted.
+ */
+#define list_for_each_entry_lockless(pos, head, member) \
+	for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
+	     &pos->member != (head); \
+	     pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
+
+/**
  * list_for_each_entry_continue_rcu - continue iteration over list of given type
  * @pos:	the type * to use as a loop cursor.
  * @head:	the head for your list.
-- 
2.5.2

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH v2 tip/core/rcu 0/14] Miscellaneous fixes for 4.5 "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:10 +0100
  [PATCH v2 tip/core/rcu 14/14] list: Add lockless list traversal primitives "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 12/14] rcu: Move wakeup out from under rnp->lock "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 02/14] kernel: Make rcu/tree_trace.c explicitly non-modular "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 09/14] rcu: Make cpu_needs_another_gp() be bool "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 04/14] rcu: Remove lock-acquisition loop from rcu_read_unlock_special() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 06/14] rcu: Avoid tick_nohz_active checks on NOCBs CPUs "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 07/14] rcu: Stop disabling interrupts in scheduler fastpaths "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 10/14] rcu: Don't redundantly disable irqs in rcu_irq_{enter,exit}() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:20 +0100
  [PATCH v2 tip/core/rcu 03/14] rcu: Simplify rcu_sched_qs() control flow "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100
  [PATCH v2 tip/core/rcu 01/14] rcu: Move lock_class_key to local scope "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100
  [PATCH v2 tip/core/rcu 11/14] rcu: Fix comment for rcu_dereference_raw_notrace "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100
  [PATCH v2 tip/core/rcu 13/14] rcu: Make rcu_gp_init() be bool rather than int "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100
  [PATCH v2 tip/core/rcu 08/14] rcu: Eliminate unused rcu_init_one() argument "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100
  [PATCH v2 tip/core/rcu 05/14] rcu: Fix obsolete rcu_bootup_announce_oddness() comment "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-12-10 00:30 +0100

csiph-web