latched RB-trees and __module_address()

Currently the RCU usage in module is an inconsistent mess of RCU and RCU-sched, this is broken for CONFIG_PREEMPT where synchronize_rcu() does not imply synchronize_sched().

Most usage sites use preempt_{dis,en}able() which is RCU-sched, but (most of) the modification sites use synchronize_rcu(). With the exception of the module bug list, which actually uses RCU.

Convert everything over to RCU-sched.

Furthermore add lockdep asserts to all sites, because its not at all clear to me the required locking is observed, esp. on exported functions.

Quoted 6 lines

kernel/module.c +6 -0

+static void module_assert_mutex_or_preempt(void)
+{
+#ifdef CONFIG_LOCKDEP
+	int rcu_held = rcu_read_lock_sched_held();
+	int mutex_held = 1;
+

kernel/module.c static LIST_HEAD(modules); · line 123

Quoted 4 lines

kernel/module.c +4 -0

+	if (debug_locks)
+		mutex_held = lockdep_is_held(&module_mutex);
+
+	WARN_ON(!rcu_held && !mutex_held);

So because rcu_read_lock_sched_held() also depends on debug_locks being on to be fully correct, shouldn't the warning also be within the debug_locks condition?

Quoted 6 lines · Ingo Molnar

Quoted 6 lines

kernel/module.c +6 -0

+static void module_assert_mutex_or_preempt(void)
+{
+#ifdef CONFIG_LOCKDEP
+	int rcu_held = rcu_read_lock_sched_held();
+	int mutex_held = 1;
+

Quoted 8 lines

kernel/module.c static LIST_HEAD(modules); · line 123

Quoted 4 lines

kernel/module.c +4 -0

+	if (debug_locks)
+		mutex_held = lockdep_is_held(&module_mutex);
+
+	WARN_ON(!rcu_held && !mutex_held);

So because rcu_read_lock_sched_held() also depends on debug_locks being on to be fully correct, shouldn't the warning also be within the debug_locks condition?

Ah, see how mutex_held will be true for !debug_locks and therefore we'll not trigger the warn.

Maybe not the best way to code that though.

Something like so perhaps:

static void module_assert_mutex_or_preempt(void)
{

#ifdef CONFIG_LOCKDEP
	if (!debug_locks)
		return;

	WARN_ON(!rcu_held_lock_sched_held() &&
		!lockdep_is_held(&module_mutex));

#endif

Change the insert and erase code such that lockless searches are non-fatal.

In and of itself an rbtree cannot be correctly searched while in-modification, we can however provide weaker guarantees that will allow the rbtree to be used in conjunction with other techniques, such as latches; see 9b0fd802e8c0 ("seqcount: Add raw_write_seqcount_latch()").

For this to work we need the following guarantees from the rbtree code:

1) a lockless reader must not see partial stores, this would allow it to observe nodes that are invalid memory.

2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.

For 1) we must use WRITE_ONCE() for all updates to the tree structure; in particular this patch only does rb_{left,right} as those are the only element required for simple searches.

It generates slightly worse code, probably because volatile. But in pointer chasing heavy code a few instructions more should not matter.

+/*
+ * Notes on lockless lookups:
+ *
+ * All stores to the tree structure (rb_left and rb_right) must be done using
+ * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
+ * tree structure as seen in program order.
+ *
+ * These two requirements will allow lockless iteration of the tree -- not

+ * correct iteration mind you, tree rotations are not atomic so a lookup might
+ * miss entire subtrees.
+ *
+ * But they do guarantee that any such traversal will only see valid elements
+ * and that it will indeed complete -- does not get stuck in a loop.
+ *
+ * It also guarantees that if the lookup returns an element it is the 'correct'
+ * one. But not returning an element does _NOT_ mean its not present.

include/linux/rbtree.h static inline void rb_link_node(struct r · line 90

Quoted 2 lines

include/linux/rbtree.h +2 -0

+static inline void rb_link_node_rcu(struct rb_node * node, struct rb_node * parent,
+				    struct rb_node ** rb_link)

Minor stylistic nit, the standard pattern I suspect has spaces fewer by three:

static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
struct rb_node **rb_link)

+/**
* raw_write_seqcount_latch - redirect readers to even/odd copy
* @s: pointer to seqcount_t
+ *
+ * The latch technique is a multiversion concurrency control method that allows
+ * queries during non atomic modifications. If you can guarantee queries never
+ * interrupt the modification -- e.g. the concurrency is strictly between CPUs
+ * -- you most likely do not need this.

+ *
+ * Where the traditional RCU/lockless data structures rely on atomic
+ * modifications to ensure queries observe either the old or the new state the
+ * latch allows the same for non atomic updates. The trade-off is doubling the
+ * cost of storage; we have to maintain two copies of the entire data
+ * structure.

+ * The query will have a form like:
+ *
+ * struct entry *latch_query(struct latch_struct *latch, ...)
+ * {
+ * struct entry *entry;
+ * unsigned seq, idx;
+ *
+ * do {

+ * seq = latch->seq;
+ * smp_rmb();
+ *
+ * idx = seq & 0x01;
+ * entry = data_query(latch->data[idx], ...);
+ *
+ * smp_rmb();
+ * } while (seq != latch->seq);

Quoted 8 lines

+ * The query will have a form like:
+ *
+ * struct entry *latch_query(struct latch_struct *latch, ...)
+ * {
+ * struct entry *entry;
+ * unsigned seq, idx;
+ *
+ * do {

Quoted 8 lines

+ * seq = latch->seq;
+ * smp_rmb();
+ *
+ * idx = seq & 0x01;
+ * entry = data_query(latch->data[idx], ...);
+ *
+ * smp_rmb();
+ * } while (seq != latch->seq);

Btw., I realize this is just a sample, but couldn't this be written more optimally as:

	do {
		seq = READ_ONCE(latch->seq);
		smp_read_barrier_depends();

		idx = seq & 0x01;
		entry = data_query(latch->data[idx], ...);

		smp_rmb();
	} while (seq != latch->seq);

Note that there's just a single smp_rmb() barrier: the READ_ONCE() is there to make sure GCC doesn't calculate 'idx' from two separate reads, but otherwise there's a direct data dependency on latch->seq so no smp_rmb() is needed, only a data dependency barrier when doing the first lookup AFAICS?

(This doesn't matter on x86 where smp_rmb() is barrier().)

----- Original Message -----

Quoted 3 lines · Peter Zijlstra

[...]

Quoted 36 lines

Quoted 8 lines

+ * The query will have a form like:
+ *
+ * struct entry *latch_query(struct latch_struct *latch, ...)
+ * {
+ * struct entry *entry;
+ * unsigned seq, idx;
+ *
+ * do {

Quoted 8 lines

+ * seq = latch->seq;
+ * smp_rmb();
+ *
+ * idx = seq & 0x01;
+ * entry = data_query(latch->data[idx], ...);
+ *
+ * smp_rmb();
+ * } while (seq != latch->seq);

Btw., I realize this is just a sample, but couldn't this be written more optimally as:

	do {
		seq = READ_ONCE(latch->seq);
		smp_read_barrier_depends();

		idx = seq & 0x01;
		entry = data_query(latch->data[idx], ...);

		smp_rmb();
	} while (seq != latch->seq);

Note that there's just a single smp_rmb() barrier: the READ_ONCE() is there to make sure GCC doesn't calculate 'idx' from two separate reads, but otherwise there's a direct data dependency on latch->seq so no smp_rmb() is needed, only a data dependency barrier when doing the first lookup AFAICS?

Quoted 1 line

(This doesn't matter on x86 where smp_rmb() is barrier().)

The latch evolved from seqlock.h, where there was no data dependency between the sequence counter and the data read, hence the smp_rmb(). Indeed, there is a data dependency in the case of the latch, so I think your approach of READ_ONCE + smp_read_barrier_depends() is appropriate.

A shorthand for READ_ONCE + smp_read_barrier_depends() is the shiny new lockless_dereference()

Quoted 3 lines · Paul E. McKenney

A shorthand for READ_ONCE + smp_read_barrier_depends() is the shiny new lockless_dereference()

Related side note - I think people should get used to seeing "smp_load_acquire()". It has well-defined memory ordering properties and should generally perform well on most architectures. It's (much) stronger than lockless_dereference(), and together with smp_store_release() you can make rather clear guarantees about passing data locklessly from one CPU to another.

I'd like to see us use more of the pattern of

- one thread does:

.. allocate/create some data
smp_store_release() to "expose it"

- another thread does:

smp_load_acquire() to read index/pointer/flag/whatever .. use the data any damn way you want ..

and we should probably aim to prefer that pattern over a lot of our traditional memory barriers.

Quoted 22 lines · Linus Torvalds

Quoted 3 lines · Paul E. McKenney

A shorthand for READ_ONCE + smp_read_barrier_depends() is the shiny new lockless_dereference()

Related side note - I think people should get used to seeing "smp_load_acquire()". It has well-defined memory ordering properties and should generally perform well on most architectures. It's (much) stronger than lockless_dereference(), and together with smp_store_release() you can make rather clear guarantees about passing data locklessly from one CPU to another.

I'd like to see us use more of the pattern of

- one thread does:

.. allocate/create some data
smp_store_release() to "expose it"

- another thread does:

Quoted 5 lines

smp_load_acquire() to read index/pointer/flag/whatever .. use the data any damn way you want ..

and we should probably aim to prefer that pattern over a lot of our traditional memory barriers.

I couldn't agree more!

RCU made a similar move from open-coding smp_read_barrier_depends() to using rcu_dereference() many years ago, and that change made RCU code -much- easier to read and understand. I believe that moving from smp_mb(), smp_rmb(), and smp_wmb() to smp_store_release() and smp_load_acquire() will provide similar maintainability benefits. Furthermore, when the current code uses smp_mb(), smp_store_release() and smp_load_acquire() generate faster code on most architectures.

Quoted 23 lines · Paul E. McKenney

Quoted 22 lines · Linus Torvalds

Quoted 3 lines · Paul E. McKenney

A shorthand for READ_ONCE + smp_read_barrier_depends() is the shiny new lockless_dereference()

Related side note - I think people should get used to seeing "smp_load_acquire()". It has well-defined memory ordering properties and should generally perform well on most architectures. It's (much) stronger than lockless_dereference(), and together with smp_store_release() you can make rather clear guarantees about passing data locklessly from one CPU to another.

I'd like to see us use more of the pattern of

- one thread does:

.. allocate/create some data
smp_store_release() to "expose it"

- another thread does:

Quoted 7 lines

Quoted 5 lines

smp_load_acquire() to read index/pointer/flag/whatever .. use the data any damn way you want ..

and we should probably aim to prefer that pattern over a lot of our traditional memory barriers.

I couldn't agree more!

/me too!

Quoted 8 lines

RCU made a similar move from open-coding smp_read_barrier_depends() to using rcu_dereference() many years ago, and that change made RCU code -much- easier to read and understand. I believe that moving from smp_mb(), smp_rmb(), and smp_wmb() to smp_store_release() and smp_load_acquire() will provide similar maintainability benefits. Furthermore, when the current code uses smp_mb(), smp_store_release() and smp_load_acquire() generate faster code on most architectures.

A similar maintainability argument can be made for locking:
spin_lock(x) was a big step forward compared to lock_kernel(), primarily not because it improves scalability (it often does), but because the '(x)' very clearly documents the data structure that is being accessed and makes locking and data access bugs a lot more visible in the review phase already.

I wish rcu_read_lock() had a data argument, for similar reasons - even if it just pointed to a pre-existing lock or an rcu head it never touches ;-)

As an example I picked a random file out of the kernel that uses RCU:
kernel/cpuset.c::validate_change():

static int validate_change(struct cpuset *cur, struct cpuset *trial)

{
	struct cgroup_subsys_state *css;
	struct cpuset *c, *par;
	int ret;

	rcu_read_lock();

	/* Each of our child cpusets must be a subset of us */
	ret = -EBUSY;
	cpuset_for_each_child(c, css, cur)
		if (!is_cpuset_subset(c, trial))
			goto out;

	/* Remaining checks don't apply to root cpuset */
	ret = 0;
	if (cur == &top_cpuset)
		goto out;

	par = parent_cs(cur);

	/* On legacy hiearchy, we must be a subset of our parent cpuset. */
	ret = -EACCES;
	if (!cgroup_on_dfl(cur->css.cgroup) && !is_cpuset_subset(trial, par))
		goto out;

	/*
	 * If either I or some sibling (!= me) is exclusive, we can't
	 * overlap
	 */
	ret = -EINVAL;
	cpuset_for_each_child(c, css, par) {
		if ((is_cpu_exclusive(trial) || is_cpu_exclusive(c)) &&
		    c != cur &&
		    cpumask_intersects(trial->cpus_allowed, c->cpus_allowed))
			goto out;
		if ((is_mem_exclusive(trial) || is_mem_exclusive(c)) &&
		    c != cur &&
		    nodes_intersects(trial->mems_allowed, c->mems_allowed))
			goto out;
	}

	/*
	 * Cpusets with tasks - existing or newly being attached - can't
	 * be changed to have empty cpus_allowed or mems_allowed.
	 */
	ret = -ENOSPC;
	if ((cgroup_has_tasks(cur->css.cgroup) || cur->attach_in_progress)) {
		if (!cpumask_empty(cur->cpus_allowed) &&
		    cpumask_empty(trial->cpus_allowed))
			goto out;
		if (!nodes_empty(cur->mems_allowed) &&
		    nodes_empty(trial->mems_allowed))
			goto out;
	}

	/*
	 * We can't shrink if we won't have enough room for SCHED_DEADLINE
	 * tasks.
	 */
	ret = -EBUSY;
	if (is_cpu_exclusive(cur) &&
	    !cpuset_cpumask_can_shrink(cur->cpus_allowed,
				       trial->cpus_allowed))
		goto out;

	ret = 0;
out:
	rcu_read_unlock();
	return ret;
}

So just from taking a glance at that function can you tell me what is being RCU protected here? I cannot, I can only guess that it must either be cpuset_for_each_child() or maybe the cpumasks or other internals.

And if I search the file for call_rcu() it shows me nothing. Only if I know that cpusets are integrated with cgroups and I search kernel/cgroup.c for call_rcu(), do I find:

        call_rcu(&css->rcu_head, css_free_rcu_fn);

aha!

... or if I drill down 3 levels into cpuset_for_each_child() -> css_for_each_child() -> css_next_child() do I see the RCU iteration.

It would have been a lot clearer from the onset, if I had a hint syntactically:

	rcu_read_lock(&css->rcu_head);
	...
	rcu_read_unlock(&css->rcu_head);

beyond the reviewer bonus I bet this would allow some extra debugging as well (only enabled in debug kernels):

- for example to make sure we only access a field if _that field_ is RCU locked (reducing the chance of having the right locking for the wrong reason)

- we could possibly also build lockdep dependencies out of such annotated RCU locking patterns.

- RCU aware list walking primitives could auto-check that this particular list is properly RCU locked.

This could be introduced gradually by using a different API name:

	rcu_lock(&css->rcu_head);
	...
	rcu_unlock(&css->rcu_head);

(the 'read' is implied in RCU locking anyway.)

... and if you think this approach has any merit, I volunteer the perf and sched subsystems as guinea pigs! :-)

What do you think?

Quoted 3 lines

I wish rcu_read_lock() had a data argument, for similar reasons - even if it just pointed to a pre-existing lock or an rcu head it never touches ;-)

Heh! Jack Slingwine and I had that argument back in 1993. I advocated placing the update-side lock into the rcu_read_lock() equivalent, and he responded by showing me a use cases were (1) there were no update-side locks and (2) there were many update-side locks, and it was impossible to select just one on the read side. ;-)

However, DYNIX/ptx did not have anything like rcu_dereference() or list_for_each_entry_rcu(), which perhaps can be used in your example below. (Hey, that was 20 years ago, when 50MB was a lot of main memory. So we relied on compilers being quite dumb.)

Quoted 10 lines

know that cpusets are integrated with cgroups and I search kernel/cgroup.c for call_rcu(), do I find:

        call_rcu(&css->rcu_head, css_free_rcu_fn);

aha!

... or if I drill down 3 levels into cpuset_for_each_child() -> css_for_each_child() -> css_next_child() do I see the RCU iteration.

And I have felt that reviewing pain as well.

But shouldn't these API members be tagged with "_rcu" to make that more clear? Sort of like the difference between list_for_each_entry and list_for_each_entry_rcu()?

Quoted 6 lines

It would have been a lot clearer from the onset, if I had a hint syntactically:

	rcu_read_lock(&css->rcu_head);
	...
	rcu_read_unlock(&css->rcu_head);

I cannot resist asking what you put there if the update side uses synchronize_rcu()... A NULL pointer? A pointer to synchronize_rcu()? Something else? [...]

[...] And what do you do in the not-uncommon case where multiple RCU chains are being traversed in the same RCU read-side critical section? One approach would be to use varargs, I suppose. Though with a hash table, list, or tree, you could have a -lot- of ->rcu_head structures to reference, and concurrent additions and deletions mean that you wouldn't necessarily know which at rcu_read_lock() time.

Quoted 7 lines

beyond the reviewer bonus I bet this would allow some extra debugging as well (only enabled in debug kernels):

- for example to make sure we only access a field if _that field_ is RCU locked (reducing the chance of having the right locking for the wrong reason)

One possibility would be to mark each traversal of an RCU-protected pointer. Currently, if a multilinked structure is inserted in one shot, only the initial pointer to that structure needs to have rcu_dereference(). Otherwise, it is hard to tell exactly how far the RCU protection is to extend. (Been having too much fun with this sort of thing in the standards committees...)

Quoted 2 lines

- we could possibly also build lockdep dependencies out of such annotated RCU locking patterns.

Tell me more?

Quoted 2 lines

- RCU aware list walking primitives could auto-check that this particular list is properly RCU locked.

For example, that a lock in the proper update class was held during the corresponding update?

Quoted 10 lines · Paul E. McKenney

Quoted 3 lines

I wish rcu_read_lock() had a data argument, for similar reasons - even if it just pointed to a pre-existing lock or an rcu head it never touches ;-)

Heh! Jack Slingwine and I had that argument back in 1993. I advocated placing the update-side lock into the rcu_read_lock() equivalent, and he responded by showing me a use cases were (1) there were no update-side locks and (2) there were many update-side locks, and it was impossible to select just one on the read side. ;-)

So as a response I'd have attempted to hand-wave something about those scenarios being either not that common, or not that interesting?!! :-)

Quoted 4 lines

However, DYNIX/ptx did not have anything like rcu_dereference() or list_for_each_entry_rcu(), which perhaps can be used in your example below. (Hey, that was 20 years ago, when 50MB was a lot of main memory. So we relied on compilers being quite dumb.)

I guess compilers are still dumb in many ways ;-)

Quoted 11 lines

Quoted 10 lines

know that cpusets are integrated with cgroups and I search kernel/cgroup.c for call_rcu(), do I find:

        call_rcu(&css->rcu_head, css_free_rcu_fn);

aha!

... or if I drill down 3 levels into cpuset_for_each_child() -> css_for_each_child() -> css_next_child() do I see the RCU iteration.

Quoted 5 lines

And I have felt that reviewing pain as well.

But shouldn't these API members be tagged with "_rcu" to make that more clear? Sort of like the difference between list_for_each_entry and list_for_each_entry_rcu()?

Yes, agreed absolutely!

Having it as a syntactic element instead of a stylistic one forces such self-documentation though.

At the cost of being an extra nuisance.

Quoted 10 lines

Quoted 6 lines

It would have been a lot clearer from the onset, if I had a hint syntactically:

	rcu_read_lock(&css->rcu_head);
	...
	rcu_read_unlock(&css->rcu_head);

I cannot resist asking what you put there if the update side uses synchronize_rcu()... A NULL pointer? A pointer to synchronize_rcu()? Something else? [...]

So I'd either put a suitable zero-size struct ('struct rcu_head_sync'?) into the protected data structure: i.e. still annotate it in an active fashion, but don't change any code.

This would be zero size in the non-debug case, but it would allow debugging data in the debug case.

Another solution would be to not require such linking in all cases, only when there's a single update side lock.

Quoted 7 lines

[...] And what do you do in the not-uncommon case where multiple RCU chains are being traversed in the same RCU read-side critical section? One approach would be to use varargs, I suppose. Though with a hash table, list, or tree, you could have a -lot- of ->rcu_head structures to reference, and concurrent additions and deletions mean that you wouldn't necessarily know which at rcu_read_lock() time.

I'd definitely keep it simple - i.e. no varargs.

I'd just try to link with the data structure in general. Or I'd just forget about handling these cases altogether, at least initially - first see how it works out for the simpler cases.

Quoted 14 lines

Quoted 6 lines

beyond the reviewer bonus I bet this would allow some extra debugging as well (only enabled in debug kernels):

- for example to make sure we only access a field if _that field_ is RCU locked (reducing the chance of having the right locking for the wrong reason)

One possibility would be to mark each traversal of an RCU-protected pointer. Currently, if a multilinked structure is inserted in one shot, only the initial pointer to that structure needs to have rcu_dereference(). Otherwise, it is hard to tell exactly how far the RCU protection is to extend. (Been having too much fun with this sort of thing in the standards committees...)

Quoted 4 lines

Quoted 2 lines

- we could possibly also build lockdep dependencies out of such annotated RCU locking patterns.

Tell me more?

So to backpedal a bit, I think that in practice the use rcu_dereference*() gives us a lot of protection and documentation already - so I might be over-doing it.

But we could essentially split up the current monolithic rcu_read_lock() class and turn it into classes mirroring the update side lock classes.

This would at minimum give us access to CONFIG_LOCK_STAT statistics about the frequency of use of the various locks. Right now I can only see this:

/proc/lockdep:ffffffff82d27887 OPS: 1412000 FD: 1 BD: 1 ......: rcu_read_lock

/proc/lock_stat:                         rcu_read_lock-R:             0              0           0.00           0.00           0.00           0.00              0        1135745           0.00         969.66     1355676.33           1.19
/proc/lock_stat:                   rcu_read_lock_sched-R:             0              0           0.00           0.00           0.00           0.00              0             16           0.25          20.71          30.40           1.90
/proc/lock_stat:                      rcu_read_lock_bh-R:             0              0           0.00           0.00           0.00           0.00              0           5602           0.33         126.70       40478.88           7.23

which merges them into essentially a single counter.

If we had a more finegrained structure we could tell more about usage patterns? Not sure how valuable that is though.

So for example on the SRCU side we could detect such deadlocks:

	mutex_lock(&mutex);
	synchronize_srcu(&srcu);

vs.

	srcu_read_lock(&srcu);
	mutex_lock(&mutex);

(I don't think we are detecting these right now.)

On the classical RCU side it's harder to construct deadlocks, because the read side is a non-sleeping and irq-safe primitive, while synchronize_rcu() is a sleeping method ;-) So most (all?) deadlock scenarios are avoided by just those properties.

Another use would be to potentially split up the RCU read side into multiple grace period domains, flushed independently, a bit like how SRCU does it? That would be a non-debugging use for it.

Quoted 5 lines

Quoted 2 lines

- RCU aware list walking primitives could auto-check that this particular list is properly RCU locked.

For example, that a lock in the proper update class was held during the corresponding update?

Yes, and also on the lookup side: that a 'lock' of the proper type is read-held during lookup. (with a few special annotations for special cases where as a side effect of other things we may have proper RCU read side protection.)

Btw., I realize this is just a sample, but couldn't this be written more optimally as:

	do {
		seq = READ_ONCE(latch->seq);
		smp_read_barrier_depends();

		idx = seq & 0x01;
		entry = data_query(latch->data[idx], ...);

		smp_rmb();
	} while (seq != latch->seq);

Quoted 8 lines · Ingo Molnar

Btw., I realize this is just a sample, but couldn't this be written more optimally as:

	do {
		seq = READ_ONCE(latch->seq);
		smp_read_barrier_depends();

Quoted 6 lines

		idx = seq & 0x01;
		entry = data_query(latch->data[idx], ...);

		smp_rmb();
	} while (seq != latch->seq);

Should we look at introducing yet another seq primitive?

Quoted 9 lines · Peter Zijlstra

Quoted 8 lines · Ingo Molnar

Btw., I realize this is just a sample, but couldn't this be written more optimally as:

	do {
		seq = READ_ONCE(latch->seq);
		smp_read_barrier_depends();

Quoted 8 lines

Quoted 6 lines

		idx = seq & 0x01;
		entry = data_query(latch->data[idx], ...);

		smp_rmb();
	} while (seq != latch->seq);

Should we look at introducing yet another seq primitive?

Like so?

---

include/linux/seqlock.h +6 -2

@@ -233,6 +233,11 @@ static inline void raw_write_seqcount_en
 	s->sequence++;
 }
 
+static inline int raw_read_seqcount_latch(seqcount_t *s)
+{
+	return lockless_dereference(s->sequence);
+}
+
 /**
  * raw_write_seqcount_latch - redirect readers to even/odd copy
  * @s: pointer to seqcount_t

@@ -284,8 +289,7 @@ static inline void raw_write_seqcount_en
  *	unsigned seq, idx;
  *
  *	do {
- *		seq = latch->seq;
- *		smp_rmb();
+ *		seq = lockless_dereference(latch->seq);
  *
  *		idx = seq & 0x01;
  *		entry = data_query(latch->data[idx], ...);

Implement a latched RB-tree in order to get unconditional RCU/lockless lookups.

Cc Oleg Nesterov <[email protected]>

Cc Michel Lespinasse <[email protected]>

Cc Andrea Arcangeli <[email protected]>

Cc David Woodhouse <[email protected]>

Cc Rik van Riel <[email protected]>

Cc Mathieu Desnoyers <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 include/linux/rbtree_latch.h |  212 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 212 insertions(+)

include/linux/rbtree_latch.h new file +19 -0

@@ -0,0 +1,212 @@
+/*
+ * Latched RB-trees
+ *
+ * Copyright (C) 2015 Intel Corp., Peter Zijlstra <[email protected]>
+ *
+ * Since RB-trees have non atomic modifications they're not immediately suited
+ * for RCU/lockless queries. Even though we made RB tree lookups non-fatal for
+ * lockless lookups; we cannot guarantee they return a correct result.
+ *
+ * The simplest solution is a seqlock + rb-tree, this will allow lockless
+ * lookups; but has the constraint (inherent to the seqlock) that read sides
+ * cannot nest in write sides.
+ *
+ * If we need to allow unconditional lookups (say as required for NMI context
+ * usage) we need a more complex setup; this data structure provides this by
+ * employing the latch technique -- see @raw_write_seqcount_latch -- to
+ * implement a latched RB-tree which does allow for unconditional lookups by
+ * virtue of always having (at least) one stable copy of the tree.
+ *

Minor nit: so this text has 3 variants to spell RB-trees:

RB-tree
RB tree
rb-tree

I suggest we pick one! :-)

Currently __module_address() is using a linear search through all modules in order to find the module corresponding to the provided address. With a lot of modules this can take a lot of time.

One of the users of this is kernel_text_address() which is employed in many stack unwinders; which in turn are used by perf-callchain and ftrace (possibly from NMI context).

So by optimizing __module_address() we optimize many stack unwinders which are used by both perf and tracing in performance sensitive code.

kernel/module.c +6 -0

+static __always_inline int
+mod_tree_comp(void *key, struct latch_tree_node *n)
+{
+	unsigned long val = (unsigned long)key;
+	unsigned long start, end;
+

Quoted 6 lines · Peter Zijlstra

kernel/module.c +6 -0

+static __always_inline int
+mod_tree_comp(void *key, struct latch_tree_node *n)
+{
+	unsigned long val = (unsigned long)key;
+	unsigned long start, end;
+

kernel/module.c line 160

Quoted 10 lines

kernel/module.c +10 -0

+	end = start = __mod_tree_val(n);
+	end += __mod_tree_size(n);
+
+	if (val < start)
+		return -1;
+
+	if (val >= end)
+		return 1;
+
+	return 0;

So since we are counting nanoseconds, I suspect this could be written more optimally as:

{
	unsigned long val = (unsigned long)key;
	unsigned long start, end;

	start = __mod_tree_val(n);
	if (val < start)
		return -1;

	end = start + __mod_tree_size(n);
	if (val >= end)
		return 1;

	return 0;
}

right?

Andrew worried about the overhead on small systems; only use the fancy code when either perf or tracing is enabled.

Cc Rusty Russell <[email protected]>

Cc Steven Rostedt <[email protected]>

Requested-by Andrew Morton <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 kernel/module.c |   30 ++++++++++++++++++++++++++++--
 1 file changed, 28 insertions(+), 2 deletions(-)

kernel/module.c +2 -0

@@ -102,6 +102,8 @@ DEFINE_MUTEX(module_mutex);
 EXPORT_SYMBOL_GPL(module_mutex);
 static LIST_HEAD(modules);
 
+#if defined(CONFIG_PERF_EVENTS) || defined(CONFIG_TRACING)
+
 /*
  * Use a latched RB-tree for __module_address(); this allows us to use
  * RCU-sched lookups of the address from any context.

__module_address() does an initial bound check before doing the {list/tree} iteration to find the actual module. The bound variables are nowhere near the mod_tree cacheline, in fact they're nowhere near one another.

module_addr_min lives in .data while module_addr_max lives in .bss (smarty pants GCC thinks the explicit 0 assignment is a mistake).

Rectify this by moving the two variables into a structure together with the latch_tree_root to guarantee they all share the same cacheline and avoid hitting two extra cachelines for the lookup.

While reworking the bounds code, move the bound update from allocation to insertion time, this avoids updating the bounds for a few error paths.

kernel/module.c +8 -0

+static struct mod_tree_root {
+	struct latch_tree_root root;
+	unsigned long addr_min;
+	unsigned long addr_max;
+} mod_tree __cacheline_aligned = {
+	.addr_min = -1UL,
+};
+

Quoted 15 lines · Peter Zijlstra

__module_address() does an initial bound check before doing the {list/tree} iteration to find the actual module. The bound variables are nowhere near the mod_tree cacheline, in fact they're nowhere near one another.

module_addr_min lives in .data while module_addr_max lives in .bss (smarty pants GCC thinks the explicit 0 assignment is a mistake).

Rectify this by moving the two variables into a structure together with the latch_tree_root to guarantee they all share the same cacheline and avoid hitting two extra cachelines for the lookup.

While reworking the bounds code, move the bound update from allocation to insertion time, this avoids updating the bounds for a few error paths.

kernel/module.c static const struct latch_tree_ops mod_t · line 183

Quoted 10 lines

kernel/module.c +10 -0

+static struct mod_tree_root {
+	struct latch_tree_root root;
+	unsigned long addr_min;
+	unsigned long addr_max;
+} mod_tree __cacheline_aligned = {
+	.addr_min = -1UL,
+};
+
+#define module_addr_min mod_tree.addr_min
+#define module_addr_max mod_tree.addr_max

Quoted 18 lines · Ingo Molnar

Quoted 15 lines · Peter Zijlstra

__module_address() does an initial bound check before doing the {list/tree} iteration to find the actual module. The bound variables are nowhere near the mod_tree cacheline, in fact they're nowhere near one another.

module_addr_min lives in .data while module_addr_max lives in .bss (smarty pants GCC thinks the explicit 0 assignment is a mistake).

Rectify this by moving the two variables into a structure together with the latch_tree_root to guarantee they all share the same cacheline and avoid hitting two extra cachelines for the lookup.

While reworking the bounds code, move the bound update from allocation to insertion time, this avoids updating the bounds for a few error paths.

Quoted 10 lines

kernel/module.c static const struct latch_tree_ops mod_t · line 183

Quoted 10 lines

kernel/module.c +10 -0

+static struct mod_tree_root {
+	struct latch_tree_root root;
+	unsigned long addr_min;
+	unsigned long addr_max;
+} mod_tree __cacheline_aligned = {
+	.addr_min = -1UL,
+};
+
+#define module_addr_min mod_tree.addr_min
+#define module_addr_max mod_tree.addr_max

Nice catch.

Does the min/max comparison still win us anything? (I'm guessing yes...)

In general, I'm happy with this series. Assume you want another go-round for Ingo's tweaks, then I'll take them for 4.2.

Quoted 4 lines

+ * Bounds of module allocation, for speeding up __module_address.
+ * Protected by module_mutex.
+ */
+static unsigned long module_addr_min = -1UL, module_addr_max = 0;

I suspect the same .data vs. .bss problem affects the #else branch as well?

If so then it would make sense IMHO to put the structure definition into generic code so that both variants benefit from the shared cacheline?

Quoted 7 lines · Ingo Molnar

Quoted 4 lines

+ * Bounds of module allocation, for speeding up __module_address.
+ * Protected by module_mutex.
+ */
+static unsigned long module_addr_min = -1UL, module_addr_max = 0;

I suspect the same .data vs. .bss problem affects the #else branch as well?

Yes, but the linear walk already has a 'problem', other than the linear walk itself being one, the list_head isn't actually on the same line as the 'key' entries -- although I suppose I could fix that for the !CONFIG_MODULES_TREE_LOOKUP case.

Quoted 3 lines

If so then it would make sense IMHO to put the structure definition into generic code so that both variants benefit from the shared cacheline?

Isn't this optimizing hopeless code? I mean, I can make the change; something like the below. Although I suppose we should use ____cacheline_aligned here and just take the false sharing.

This series is aimed at making __module_address() go fast(er).

The reason for doing so is that most stack unwinders use kernel_text_address() to validate each frame. Perf and ftrace (can) end up doing a lot of stack traces from performance sensitive code.

On the way there it:
- annotates and sanitizes module locking
- introduces the latched RB-tree
- employs it to make __module_address() go fast.

I've build and boot tested this on x86_64 with modules and lockdep enabled. Performance numbers (below) are done with lockdep disabled.

As previously mentioned; the reason for writing the latched RB-tree as generic code is mostly for clarity/documentation purposes; as there are a number of separate and non trivial bits to the complete solution.

As measued on my ivb-ep system with 84 modules loaded; prior to patching the test module (below) reports (cache hot, performance cpufreq):

avg +- stdev

Before:   611 +- 10 [ns] per __module_address() call
After:     17 +-  5 [ns] per __module_address() call

PMI measurements for a cpu running loops in a module (also [ns]):

Before: Mean: 2719 +- 1, Stdev: 214, Samples: 40036
After:  Mean:  947 +- 0, Stdev: 132, Samples: 40037

Note; I have also tested things like: perf record -a -g modprobe mod_test, to make 'sure' to hit some of the more interesting paths.

Changes since last time:

- reworked generic latch_tree API (Lai Jiangshan)
- reworked module bounds (me)
- reworked all the testing code (not included)

Rusty, please consider merging this (for 4.2, I know its the merge window, no rush)

This series is aimed at making __module_address() go fast(er).

The reason for doing so is that most stack unwinders use kernel_text_address() to validate each frame. Perf and ftrace (can) end up doing a lot of stack traces from performance sensitive code.

On the way there it:
- annotates and sanitizes module locking
- introduces the latched RB-tree
- employs it to make __module_address() go fast.

I've build and boot tested this on x86_64 with modules and lockdep enabled. Performance numbers (below) are done with lockdep disabled.

As previously mentioned; the reason for writing the latched RB-tree as generic code is mostly for clarity/documentation purposes; as there are a number of separate and non trivial bits to the complete solution.

As measued on my ivb-ep system with 84 modules loaded; prior to patching the test module (below) reports (cache hot, performance cpufreq):

avg +- stdev

Before:   611 +- 10 [ns] per __module_address() call
After:     17 +-  5 [ns] per __module_address() call

PMI measurements for a cpu running loops in a module (also [ns]):

Before: Mean: 2719 +- 1, Stdev: 214, Samples: 40036
After: Mean: 947 +- 0, Stdev: 132, Samples: 40037

Note; I have also tested things like: perf record -a -g modprobe mod_test, to make 'sure' to hit some of the more interesting paths.

Changes since last time:

- reworked generic latch_tree API (Lai Jiangshan)
- reworked module bounds (me)
- reworked all the testing code (not included)

Rusty, please consider merging this (for 4.2, I know its the merge window, no rush)

I was tempted to sneak in those module rcu fixes for 4.1, but seeing Ingo's comments I'll wait for 4.2.

Quoted 2 lines · Rusty Russell

I was tempted to sneak in those module rcu fixes for 4.1, but seeing Ingo's comments I'll wait for 4.2.

I can get you a new version of that if you want. See below. The fixups are unmodified of the posting (patches 2,3).

Quoted 7 lines · Peter Zijlstra

Quoted 2 lines · Rusty Russell

I was tempted to sneak in those module rcu fixes for 4.1, but seeing Ingo's comments I'll wait for 4.2.

I can get you a new version of that if you want. See below. The fixups are unmodified of the posting (patches 2,3).

Another last-minute module-next patch just blew up some archs, so I'm erring back to being conservative :)

On Tue, Apr 14, 2015 at 12:27:05PM +0930, Rusty Russell wrote:

That's rcu_read_lock_sched_held, not rcu_held_lock_sched_held().

Also, your unlikely is weird and backwards.

I changed it as below, and folded. It's in modules-next.

I'm now going to do some *actual* testing, and I'll go all Torvalds on you if this spews warnings...

Quoted 4 lines · Rusty Russell

That's rcu_read_lock_sched_held, not rcu_held_lock_sched_held().

Also, your unlikely is weird and backwards.

Quoted 4 lines

I changed it as below, and folded. It's in modules-next.

I'm now going to do some *actual* testing, and I'll go all Torvalds on you if this spews warnings...

Fair enough, I did see the build robot fail on this. How come those only showed up now? This patch has been in your git tree for a long time; you picked up the rcu validation patches before the other ones.