Skip to contentSkip to conversation

x86: Move msr accesses out of line

PATCH In review Andi Kleen 8 participants 34 messages Feb 21, 2015 – Mar 2, 2015

Subsystems (4)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/3 x86: Move msr accesses out of line

From: Andi Kleen <[email protected]>

To add trace points to msr accesses we need to include linux/tracepoint.h. Unfortunately this causes hellish include loops when with the msr inlines in asm/msr.h, which is included all over.

I tried to fix several of them, but eventually gave up.

This patch moves the MSR functions out of line. A MSR access is typically 40-100 cycles or even slower, a call is a few cycles at best, so the additional function call is not really significant.

Kernel text size is neutral:
11852945 1671656 1822720 15347321 ea2e79 vmlinux-no-msr
11852969 1671656 1822720 15347345 ea2e91 vmlinux-msr

---
 arch/x86/include/asm/msr.h | 51 ++++----------------------------------------
 arch/x86/lib/msr.c         | 53 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+), 47 deletions(-)
arch/x86/include/asm/msr.h +4 -47
index de36f22..99d6864 100644
@@ -57,53 +57,10 @@ static inline unsigned long long native_read_tscp(unsigned int *aux)
 #define EAX_EDX_RET(val, low, high)	"=A" (val)
 #endif
 
-static inline unsigned long long native_read_msr(unsigned int msr)
-{
-	DECLARE_ARGS(val, low, high);
-
-	asm volatile("rdmsr" : EAX_EDX_RET(val, low, high) : "c" (msr));
-	return EAX_EDX_VAL(val, low, high);
-}
-
-static inline unsigned long long native_read_msr_safe(unsigned int msr,
-						      int *err)
-{
-	DECLARE_ARGS(val, low, high);
-
-	asm volatile("2: rdmsr ; xor %[err],%[err]\n"
-		     "1:\n\t"
-		     ".section .fixup,\"ax\"\n\t"
-		     "3:  mov %[fault],%[err] ; jmp 1b\n\t"
-		     ".previous\n\t"
-		     _ASM_EXTABLE(2b, 3b)
-		     : [err] "=r" (*err), EAX_EDX_RET(val, low, high)
-		     : "c" (msr), [fault] "i" (-EIO));
-	return EAX_EDX_VAL(val, low, high);
-}
-
-static inline void native_write_msr(unsigned int msr,
-				    unsigned low, unsigned high)
-{
-	asm volatile("wrmsr" : : "c" (msr), "a"(low), "d" (high) : "memory");
-}
-
-/* Can be uninlined because referenced by paravirt */
-notrace static inline int native_write_msr_safe(unsigned int msr,
-					unsigned low, unsigned high)
-{
-	int err;
-	asm volatile("2: wrmsr ; xor %[err],%[err]\n"
-		     "1:\n\t"
-		     ".section .fixup,\"ax\"\n\t"
-		     "3:  mov %[fault],%[err] ; jmp 1b\n\t"
-		     ".previous\n\t"
-		     _ASM_EXTABLE(2b, 3b)
-		     : [err] "=a" (err)
-		     : "c" (msr), "0" (low), "d" (high),
-		       [fault] "i" (-EIO)
-		     : "memory");
-	return err;
-}
+extern unsigned long long native_read_msr(unsigned int msr);
+extern unsigned long long native_read_msr_safe(unsigned int msr, int *err);
+extern int native_write_msr_safe(unsigned int msr, unsigned low, unsigned high);
+extern void native_write_msr(unsigned int msr, unsigned low, unsigned high);
 
 extern unsigned long long native_read_tsc(void);
 
arch/x86/lib/msr.c +53 -0

56 lines not on this page · raw message

Signature · 1 line
1.9.3
author
#1 lore raw

PATCH 2/3 x86: Add trace point for MSR accesses

From: Andi Kleen <[email protected]>

For debugging low level code interacting with the CPU it is often useful to trace the MSR read/writes. This gives a concise summary of PMU and other operations.

perf has an ad-hoc way to do this using trace_printk, but it's somewhat limited (and also now spews ugly messages when enabled)

Instead define real trace points for all MSR accesses.

This adds two new trace point: read_msr and write_msr. They also report if the access faulted (if *_safe is used)

This allows filtering and triggering on specific
MSR values, which allows various more advanced
debugging techniques.

All the values are well defined in the CPU documentation.

I only added it to native MSR accesses in C, not paravirtualized or in entry*.S (which is not too interesting)

---
 arch/x86/lib/msr.c         | 14 ++++++++++++--
 include/trace/events/msr.h | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+), 2 deletions(-)
 create mode 100644 include/trace/events/msr.h
arch/x86/lib/msr.c +12 -2
index 7eed044..29d1952 100644
@@ -1,6 +1,8 @@
 #include <linux/module.h>
 #include <linux/preempt.h>
 #include <asm/msr.h>
+#define CREATE_TRACE_POINTS
+#include <trace/events/msr.h>
 
 struct msr *msrs_alloc(void)
 {
@@ -111,16 +113,20 @@ int msr_clear_bit(u32 msr, u8 bit)
 
 inline unsigned long long native_read_msr(unsigned int msr)
 {
+	unsigned long long lval;
 	DECLARE_ARGS(val, low, high);
 
 	asm volatile("rdmsr" : EAX_EDX_RET(val, low, high) : "c" (msr));
-	return EAX_EDX_VAL(val, low, high);
+	lval = EAX_EDX_VAL(val, low, high);
+	trace_read_msr(msr, lval, 0);
+	return lval;
 }
 EXPORT_SYMBOL(native_read_msr);
 
 inline unsigned long long native_read_msr_safe(unsigned int msr,
 						      int *err)
 {
+	unsigned long long lval;
 	DECLARE_ARGS(val, low, high);
 
 	asm volatile("2: rdmsr ; xor %[err],%[err]\n"
@@ -131,7 +137,9 @@ inline unsigned long long native_read_msr_safe(unsigned int msr,
 		     _ASM_EXTABLE(2b, 3b)
 		     : [err] "=r" (*err), EAX_EDX_RET(val, low, high)
 		     : "c" (msr), [fault] "i" (-EIO));
-	return EAX_EDX_VAL(val, low, high);
+	lval = EAX_EDX_VAL(val, low, high);
+	trace_read_msr(msr, lval, *err);
+	return lval;
 }
 EXPORT_SYMBOL(native_read_msr_safe);
 
@@ -139,6 +147,7 @@ inline void native_write_msr(unsigned int msr,
 				    unsigned low, unsigned high)
 {
 	asm volatile("wrmsr" : : "c" (msr), "a"(low), "d" (high) : "memory");
+	trace_write_msr(msr, ((u64)high << 32 | low), 0);
 }
 EXPORT_SYMBOL(native_write_msr);
 
@@ -158,6 +167,7 @@ notrace inline int native_write_msr_safe(unsigned int msr,
 		     : "c" (msr), "0" (low), "d" (high),
 		       [fault] "i" (-EIO)
 		     : "memory");
+	trace_write_msr(msr, ((u64)high << 32 | low), err);
 	return err;
 }
 EXPORT_SYMBOL(native_write_msr_safe);
include/trace/events/msr.h new file +46 -0

46 lines not on this page · raw message

Signature · 1 line
1.9.3
author
#2 lore raw

PATCH 3/3 perf, x86: Remove old MSR perf tracing code

In reply to Andi Kleen

From: Andi Kleen <[email protected]>

Now that we have generic MSR trace points we can remove the old hackish perf MSR read tracing code.

---
 arch/x86/kernel/cpu/perf_event.h | 12 +-----------
 1 file changed, 1 insertion(+), 11 deletions(-)
arch/x86/kernel/cpu/perf_event.h +1 -11
index a371d27..aa316c0 100644
@@ -14,17 +14,7 @@
 
 #include <linux/perf_event.h>
 
-#if 0
-#undef wrmsrl
-#define wrmsrl(msr, val) 						\
-do {									\
-	unsigned int _msr = (msr);					\
-	u64 _val = (val);						\
-	trace_printk("wrmsrl(%x, %Lx)\n", (unsigned int)(_msr),		\
-			(unsigned long long)(_val));			\
-	native_write_msr((_msr), (u32)(_val), (u32)(_val >> 32));	\
-} while (0)
-#endif
+/* To enable MSR tracing please use the generic trace points. */
 
 /*
  *          |   NHM/WSM    |      SNB     |
Signature · 1 line
1.9.3
#3 lore raw
In reply to Andi Kleen
Quoted 3 lines · Andi Kleen

This patch moves the MSR functions out of line. A MSR access is typically 40-100 cycles or even slower, a call is a few cycles at best, so the additional function call is not really significant.

If I look at the below PDF a CALL+PUSH EBP+MOV RSP,RBP+ ... +POP+RET ends up being 5+1.5+0.5+ .. + 1.5+8 = 16.5 + .. cycles.

~16 is fairly significant on 40. And I figure people are working hard to make some MSR accesses cheaper, which means it'll be even worse in the future.

Now I appreciate the intent for debuggability, but I don't think we can do this unconditionally.

http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

#4 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 3 lines · Andi Kleen

This patch moves the MSR functions out of line. A MSR access is typically 40-100 cycles or even slower, a call is a few cycles at best, so the additional function call is not really significant.

If I look at the below PDF a CALL+PUSH EBP+MOV RSP,RBP+ ... +POP+RET ends up being 5+1.5+0.5+ .. + 1.5+8 = 16.5 + .. cycles.

You cannot just add up the latency cycles. The CPU runs all of this in parallel.

Latency cycles would only be interesting if these instructions were on the critical path for computing the result, which they are not.

It should be a few cycles overhead.

BTW if you really worry about perf overhead you could gain far more (in some cases ms) by applying
http://comments.gmane.org/gmane.linux.kernel/1805207

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only
#5 lore raw
Quoted 10 lines · Andi Kleen
Quoted 8 lines · Peter Zijlstra
Quoted 3 lines · Andi Kleen

This patch moves the MSR functions out of line. A MSR access is typically 40-100 cycles or even slower, a call is a few cycles at best, so the additional function call is not really significant.

If I look at the below PDF a CALL+PUSH EBP+MOV RSP,RBP+ ... +POP+RET ends up being 5+1.5+0.5+ .. + 1.5+8 = 16.5 + .. cycles.

Quoted 7 lines

You cannot just add up the latency cycles. The CPU runs all of this in parallel.

Latency cycles would only be interesting if these instructions were on the critical path for computing the result, which they are not.

It should be a few cycles overhead.

I thought that since CALL touches RSP, PUSH touches RSP, MOV RSP, (obviously) touches RSP, POP touches RSP and well, RET does too. There were strong dependencies on the instructions and there would be little room to parallelize things.

I'm glad you so patiently educated me on the wonders of modern architectures and how it can indeed do all this in parallel.

Still, I wondered, so I ran me a little test. Note that I used a serializing instruction (LOCK XCHG) because WRMSR is too.

I see a ~14 cycle difference between the inline and noinline version.

If I substitute the LOCK XCHG with XADD, I get to 1,5 cycles in difference, so clearly there is some magic happening, but serializing instructions wreck it.

Anybody can explain how such RSP deps get magiced away?

---

root@ivb-ep:~# cat call.c

#define __always_inline inline __attribute__((always_inline))
#define noinline __attribute__((noinline))

static int
#ifdef FOO
noinline
#else
__always_inline
#endif
xchg(int *ptr, int val)

{
        asm volatile ("LOCK xchgl %0, %1\n"
                        : "+r" (val), "+m" (*(ptr))
                        : : "memory", "cc");
        return val;
}

void main(void)

{
        int val = 0, old;

        for (int i = 0; i < 1000000000; i++)
                old = xchg(&val, i);
}
root@ivb-ep:~# gcc -std=gnu99 -O3 -fno-omit-frame-pointer -DFOO -o call call.c
root@ivb-ep:~# objdump -D call | awk '/<[^>]*>:/ {p=0} /<main>:/ {p=1} /<xchg>:/ {p=1} { if (p) print $0 }'
00000000004003e0 <main>:
  4003e0:       55                      push   %rbp
  4003e1:       48 89 e5                mov    %rsp,%rbp
  4003e4:       53                      push   %rbx
  4003e5:       31 db                   xor    %ebx,%ebx
  4003e7:       48 83 ec 18             sub    $0x18,%rsp
  4003eb:       c7 45 e0 00 00 00 00    movl   $0x0,-0x20(%rbp)
  4003f2:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  4003f8:       48 8d 7d e0             lea    -0x20(%rbp),%rdi
  4003fc:       89 de                   mov    %ebx,%esi
  4003fe:       83 c3 01                add    $0x1,%ebx
  400401:       e8 fa 00 00 00          callq  400500 <xchg>
  400406:       81 fb 00 ca 9a 3b       cmp    $0x3b9aca00,%ebx
  40040c:       75 ea                   jne    4003f8 <main+0x18>
  40040e:       48 83 c4 18             add    $0x18,%rsp
  400412:       5b                      pop    %rbx
  400413:       5d                      pop    %rbp
  400414:       c3                      retq   

0000000000400500 <xchg>:

  400500:       55                      push   %rbp
  400501:       89 f0                   mov    %esi,%eax
  400503:       48 89 e5                mov    %rsp,%rbp
  400506:       f0 87 07                lock xchg %eax,(%rdi)
  400509:       5d                      pop    %rbp
  40050a:       c3                      retq   
  40050b:       90                      nop
  40050c:       90                      nop
  40050d:       90                      nop
  40050e:       90                      nop
  40050f:       90                      nop
root@ivb-ep:~# gcc -std=gnu99 -O3 -fno-omit-frame-pointer -o call-inline call.c
root@ivb-ep:~# objdump -D call-inline | awk '/<[^>]*>:/ {p=0} /<main>:/ {p=1} /<xchg>:/ {p=1} { if (p) print $0 }'
00000000004003e0 <main>:
  4003e0:       55                      push   %rbp
  4003e1:       31 c0                   xor    %eax,%eax
  4003e3:       48 89 e5                mov    %rsp,%rbp
  4003e6:       c7 45 f0 00 00 00 00    movl   $0x0,-0x10(%rbp)
  4003ed:       0f 1f 00                nopl   (%rax)
  4003f0:       89 c2                   mov    %eax,%edx
  4003f2:       f0 87 55 f0             lock xchg %edx,-0x10(%rbp)
  4003f6:       83 c0 01                add    $0x1,%eax
  4003f9:       3d 00 ca 9a 3b          cmp    $0x3b9aca00,%eax
  4003fe:       75 f0                   jne    4003f0 <main+0x10>
  400400:       5d                      pop    %rbp
  400401:       c3                      retq   
root@ivb-ep:~# perf stat -e "cycles:u" ./call

Performance counter stats for './call':

    36,309,274,162      cycles:u                 

      10.561819310 seconds time elapsed
root@ivb-ep:~# perf stat -e "cycles:u" ./call-inline 

Performance counter stats for './call-inline':

    22,004,045,745      cycles:u                 

       6.498271508 seconds time elapsed
author
#6 lore raw
Quoted 2 lines

Still, I wondered, so I ran me a little test. Note that I used a serializing instruction (LOCK XCHG) because WRMSR is too.

WRMSR has a lot of uops internally unlike LOCK XCHG, so I expect it will mostly overlap with what it does. I'll run some benchmarks on this today.

Also we do quite a few RDMSRs, which are not necessarily serializing.

Quoted 7 lines

I see a ~14 cycle difference between the inline and noinline version.

If I substitute the LOCK XCHG with XADD, I get to 1,5 cycles in difference, so clearly there is some magic happening, but serializing instructions wreck it.

Anybody can explain how such RSP deps get magiced away?

On Intel Core (since Yonah), the CPU frontend has a special stack tracker that avoids these dependencies.

See 2.3.2.5 in the optimization manual

Also BTW just from tracing MSRs there is a lot of optimization potential. Will send some patches later.

-Andi

maintainer
#7 lore raw
Quoted 2 lines · Andi Kleen

Also we do quite a few RDMSRs, which are not necessarily serializing.

RDMSR is not serializing. Not even WRMSR when to certain ranges, see section 8.3 in the SDM 3A.

Signature · 5 lines
Regards/Gruss,
    Boris.

ECO tip #101: Trim your mails when you reply.
--
#8 lore raw

RFC PATCH 1/1 module: Optimize __module_address() using a latched RB-tree

In reply to Andi Kleen
Quoted 3 lines · Andi Kleen

BTW if you really worry about perf overhead you could gain far more (in some cases ms) by applying
http://comments.gmane.org/gmane.linux.kernel/1805207

Yeah, how about something like so instead; it would work for everybody.

It might maybe do with a few more comments.. also it appears to work, but I'm barely awake so who knows.

---
Subject: module: Optimize __module_address() using a latched RB-tree

Optimize __module_address() using a latched RB-tree.

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 (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.

Cc Mathieu Desnoyers <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
---
 include/linux/module.h |    8 ++
 kernel/module.c        |  157 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 160 insertions(+), 5 deletions(-)
include/linux/module.h +8 -0
Index: linux-2.6/include/linux/module.h
===================================================================
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,12 +211,19 @@
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
 	/* Member of list of modules */
 	struct list_head list;
 
+	struct module_node tree_node[4];
+
 	/* Unique handle for this module */
 	char name[MODULE_NAME_LEN];
 
kernel/module.c +183 -5

226 lines not on this page · raw message

#9 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

kernel/module.c line 277

Quoted 12 lines · Peter Zijlstra
kernel/module.c +12 -0
+static struct module *mod_tree_find(unsigned long addr)
+{
+	struct module *m;
+	unsigned int seq;
+
+	do {
+		seq = raw_read_seqcount(&mod_tree.seq);
+		m = __tree_find(&mod_tree.tree[seq & 1], addr);
+	} while (read_seqcount_retry(&mod_tree.seq, seq));
+
+	return m;
+}

Btw., if your approach works out fine I bet we could add one more optimization as well: a PER_CPU(last_module_found) front cache would help as well, as usually there's quite a bit of repetition between addresses being looked up and the resulting modules.

Thanks,

Ingo

#10 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Peter Zijlstra
Quoted 17 lines · Peter Zijlstra
(quoted diff) +17 -0
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		if (idx & 2) {				/* core */
+			if (addr < (unsigned long)m->module_core)
+				n = n->rb_left;
+			else if (addr >= (unsigned long)m->module_core + m->core_size)
+				n = n->rb_right;
+			else
+				return m;
+		} else {				/* init */
+			if (addr < (unsigned long)m->module_init)

Review

Quoted 10 lines
(quoted diff) +10 -0
+				n = n->rb_left;
+			else if (addr >= (unsigned long)m->module_init + m->init_size)
+				n = n->rb_right;
+			else
+				return m;
+		}
+	}
+
+	return NULL;
+}

Assuming struct module is cacheline aligned, Rusty? from what I can find its squirreled away in some data structure:

mod = (void *)info->sechdrs[info->index.mod].sh_addr

And I can't seem to quickly find its alignment. If its not cacheline aligned, can we make it so?

The below patch shuffles things around a bit and relies on the above assumption.

#pahole -EC module ivb-ep-build/kernel/module.o

struct module {
...

/* --- cacheline 6 boundary (384 bytes) --- */
void * module_init; /* 384 8 */
void * module_core; /* 392 8 */
unsigned int init_size; /* 400 4 */
unsigned int core_size; /* 404 4 */
unsigned int init_text_size; /* 408 4 */
unsigned int core_text_size; /* 412 4 */
struct module_node {
struct module * mod; /* 416 8 */
struct rb_node {
long unsigned int __rb_parent_color; /* 424 8 */
struct rb_node * rb_right; /* 432 8 */
struct rb_node * rb_left; /* 440 8 */
} node; /* 424 24 */
} tree_node[4]; /* 416 128 */

...
};

Which gets module_{init,core} and {init,core}_size on the same cacheline as tree_node[0].

And given that module loading/unloading is rare, tree modifications will be rare, and we'll normally always iterate tree latch0. Furthermore, execution of init code is brief and by switching core to elements 0,2 we've insured to typically only hit tree_node[0].

Therefore the loads in __tree_find() will (typically) hit the same cacheline and life is good.

---

include/linux/module.h +3 -3
Index: linux-2.6/include/linux/module.h
===================================================================
@@ -222,8 +222,6 @@
 	/* Member of list of modules */
 	struct list_head list;
 
-	struct module_node tree_node[4];
-
 	/* Unique handle for this module */
 	char name[MODULE_NAME_LEN];
 
@@ -278,7 +276,7 @@
 	int (*init)(void);
 
 	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -289,6 +287,8 @@
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
kernel/module.c +23 -23

95 lines not on this page · raw message

#11 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 9 lines · Peter Zijlstra

On Thu, Feb 26, 2015 at 12:43:09PM +0100, Peter Zijlstra wrote:

Assuming struct module is cacheline aligned, Rusty? from what I can find its squirreled away in some data structure:

mod = (void *)info->sechdrs[info->index.mod].sh_addr

And I can't seem to quickly find its alignment. If its not cacheline aligned, can we make it so?

If the ELF says to align it, it will be aligned. Thus your patch below should make it Just Work:

include/linux/module.h line 282

Quoted 9 lines
include/linux/module.h +1 -1
@@ -278,7 +276,7 @@
 	int (*init)(void);
 
 	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;

Cheers,
Rusty.

#12 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Peter Zijlstra

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

Quoted 29 lines

From: "Peter Zijlstra" <[email protected]>
To: "Andi Kleen" <[email protected]>
Cc: "Andi Kleen" <[email protected]>, [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected], [email protected], [email protected]
Sent: Thursday, February 26, 2015 6:43:09 AM
Subject: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 3 lines · Andi Kleen

BTW if you really worry about perf overhead you could gain far more (in some cases ms) by applying
http://comments.gmane.org/gmane.linux.kernel/1805207

Yeah, how about something like so instead; it would work for everybody.

It might maybe do with a few more comments.. also it appears to work, but I'm barely awake so who knows.

---
Subject: module: Optimize __module_address() using a latched RB-tree

Optimize __module_address() using a latched RB-tree.

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.

Quoted 6 lines

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 (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.

It looks like a good re-use of the raw_write_seqcount_latch API we introduced for nmi-safe clock monotonic recently. This latch can indeed be applied to arbitrary data structures, as long as doubling the memory usage is not an issue.

Comment below,

Quoted 148 lines
Cc Mathieu Desnoyers <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
---
 include/linux/module.h |    8 ++
 kernel/module.c        |  157
 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 160 insertions(+), 5 deletions(-)

Index: linux-2.6/include/linux/module.h
===================================================================

include/linux/module.h +8 -0
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,12 +211,19 @@
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
 	/* Member of list of modules */
 	struct list_head list;
 
+	struct module_node tree_node[4];
+
 	/* Unique handle for this module */
 	char name[MODULE_NAME_LEN];
 

Index: linux-2.6/kernel/module.c
===================================================================

kernel/module.c +6 -0
@@ -102,6 +102,180 @@
 DEFINE_MUTEX(module_mutex);
 EXPORT_SYMBOL_GPL(module_mutex);
 static LIST_HEAD(modules);
+
+
+/*
+ * Use a latched RB-tree for __module_address()
+ *
+ * The latch concept is a multi-value concurrency data structure which

allows
+ * unserialized access and guarantees at least one version is stable.
+ *
+ * It is employed here to optimize __module_address(), which needs to find the
+ * module (if any) associated with an address. Such questions are best answered
+ * using a binary search tree.
+ *
+ * Since modules use non-overlapping memory ranges we can use a regular RB-tree
+ * (as opposed to the interval tree). However, BSTs cannot be iterated while
+ * modified.
+ *
+ * To overcome this we use the latched RB-tree, it basically consists of two
+ * RB-trees which are modified in order, ensuring one is always consistent.
+ *
+ * Things are somewhat more complicated because there are two ranges per
+ * module, but other than that its pretty straight forward.
+ *
+ * idx

+ *  0	- latch 0, init
+ *  1	- latch 1, init
+ *  2	- latch 0, core
+ *  3	- latch 1, core

+ */

kernel/module.c +33 -0
+
+struct latch_tree_root {
+	seqcount_t	seq;
+	struct rb_root	tree[2];
+};
+
+static unsigned long mod_value(struct module *mod, int idx)
+{
+	if (idx & 2) {		/* core */
+		return (unsigned long)mod->module_core;
+	} else {		/* init */
+		return (unsigned long)mod->module_init;
+	}
+}
+
+static struct module *mod_entry(struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	return mn->mod;
+}
+
+static int mod_node_idx(struct module *m, struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	int idx = mn - m->tree_node;
+
+	BUG_ON(mn->mod != m);
+	BUG_ON((unsigned)idx > 3);
+
+	return idx;
+}
+
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c +29 -0
+{
+	struct rb_root *root = &mod_tree->tree[idx & 1];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);
+	rb_insert_color(&mn->node, root);
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c line 201

Quoted 7 lines
kernel/module.c +7 -0
+{
+	struct rb_root *root = &mod_tree->tree[idx & 1];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);
+}
+

Perhaps you could use mod_value() below, and introduce a "mod_size()" too. This would keep the init vs core selection out of the traversal code.

kernel/module.c line 208

Quoted 7 lines
kernel/module.c +7 -0
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);

And change for this ?

		unsigned long m_addr = mod_value(m, n);
		unsigned long m_size = mod_size(m, n);

		if (addr < m_addr) {
			n = n->rb_left;
		else if (addr >= m_addr + m_size)
			n = n->rb_right;
		else
			return m;
Quoted 11 lines
kernel/module.c +11 -0
+		if (idx & 2) {				/* core */
+			if (addr < (unsigned long)m->module_core)
+				n = n->rb_left;
+			else if (addr >= (unsigned long)m->module_core + m->core_size)
+				n = n->rb_right;
+			else
+				return m;
+		} else {				/* init */
+			if (addr < (unsigned long)m->module_init)
+				n = n->rb_left;
+			else if (addr >= (unsigned long)m->module_init + m->init_size)

kernel/module.c line 230

Quoted 10 lines
kernel/module.c +10 -0
+				n = n->rb_right;
+			else
+				return m;
+		}
+	}
+
+	return NULL;
+}
+
+static struct latch_tree_root mod_tree;

Is it customary to define static variables in the
middle of a C file ?

The rest looks good, especially for use of the latch. I'd be tempted to turn "0, 1, 2, 3" into an enum though, so we can follow in the code what each of those array entry really means.

Thanks!

Mathieu

Quoted 104 lines
kernel/module.c +57 -5
+
+static void mod_tree_insert(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, 0);	/* init */
+	__tree_insert(&mod_tree, mod, 2);		/* core */
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, 1);	/* init */
+	__tree_insert(&mod_tree, mod, 3);		/* core */
+}
+
+static void mod_tree_remove_init(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, 0);	/* init */
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, 1);	/* init */
+}
+
+static void mod_tree_remove(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, 0);	/* init */
+	__tree_remove(&mod_tree, mod, 2);		/* core */
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, 1);	/* init */
+	__tree_remove(&mod_tree, mod, 3);		/* core */
+}
+
+static struct module *mod_tree_find(unsigned long addr)
+{
+	struct module *m;
+	unsigned int seq;
+
+	do {
+		seq = raw_read_seqcount(&mod_tree.seq);
+		m = __tree_find(&mod_tree.tree[seq & 1], addr);
+	} while (read_seqcount_retry(&mod_tree.seq, seq));
+
+	return m;
+}
+
 #ifdef CONFIG_KGDB_KDB
 struct list_head *kdb_modules = &modules; /* kdb needs the list of modules
 */
 #endif /* CONFIG_KGDB_KDB */
@@ -1854,6 +2028,7 @@
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	/* Remove this module from bug list, this uses list_del_rcu */
 	module_bug_cleanup(mod);
 	/* Wait for RCU synchronizing before releasing mod->list and buglist. */
@@ -3098,6 +3273,7 @@
 	mod->symtab = mod->core_symtab;
 	mod->strtab = mod->core_strtab;
 #endif
+	mod_tree_remove_init(mod);
 	unset_module_init_ro_nx(mod);
 	module_arch_freeing_init(mod);
 	mod->module_init = NULL;
@@ -3168,6 +3344,7 @@
 		goto out;
 	}
 	list_add_rcu(&mod->list, &modules);
+	mod_tree_insert(mod);
 	err = 0;
 
 out:
@@ -3370,6 +3547,7 @@
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	wake_up_all(&module_wq);
 	/* Wait for RCU synchronizing before releasing mod->list. */
 	synchronize_rcu();
@@ -3810,13 +3988,13 @@
 	if (addr < module_addr_min || addr > module_addr_max)
 		return NULL;
 
-	list_for_each_entry_rcu(mod, &modules, list) {
+	mod = mod_tree_find(addr);
+	if (mod) {
+		BUG_ON(!within_module(addr, mod));
 		if (mod->state == MODULE_STATE_UNFORMED)
-			continue;
-		if (within_module(addr, mod))
-			return mod;
+			mod = NULL;
 	}
-	return NULL;
+	return mod;
 }
 EXPORT_SYMBOL_GPL(__module_address);
 
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#13 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 3 lines · Mathieu Desnoyers

Perhaps you could use mod_value() below, and introduce a "mod_size()" too. This would keep the init vs core selection out of the traversal code.

Indeed!

Quoted 2 lines

Is it customary to define static variables in the middle of a C file ?

Dunno, it seemed like a good a place as any.

Quoted 4 lines

The rest looks good, especially for use of the latch. I'd be tempted to turn "0, 1, 2, 3" into an enum though, so we can follow in the code what each of those array entry really means.

Agreed.

---
Subject: module: Optimize __module_address() using a latched RB-tree
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 26 10:57:34 CET 2015

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.

Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Steven Rostedt <[email protected]>
Cc Mathieu Desnoyers <[email protected]>
---
 include/linux/module.h |   19 +++-
 kernel/module.c        |  212 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 224 insertions(+), 7 deletions(-)
include/linux/module.h +17 -2
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,6 +211,11 @@ enum module_state {
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
@@ -269,8 +275,15 @@ struct module {
 	/* Startup function. */
 	int (*init)(void);
 
-	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	/*
+	 * If this is non-NULL, vfree after init() returns
+	 *
+	 * cacheline align here, such that:
+	 *   module_init, module_core, init_size, core_size and
+	 *   tree_node[0]
+	 * are on the same cacheline.
+	 */
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -281,6 +294,8 @@ struct module {
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
kernel/module.c +207 -5

250 lines not on this page · raw message

#14 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

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

Quoted 12 lines

From: "Peter Zijlstra" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: "Andi Kleen" <[email protected]>, "Andi Kleen" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Thursday, February 26, 2015 11:43:56 AM
Subject: Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 3 lines · Mathieu Desnoyers

Perhaps you could use mod_value() below, and introduce a "mod_size()" too. This would keep the init vs core selection out of the traversal code.

Quoted 6 lines

Indeed!

Quoted 2 lines

Is it customary to define static variables in the middle of a C file ?

Dunno, it seemed like a good a place as any.

My personal coding-style is to put all definitions at the top of C files, but I don't know if it's within the kernel coding style guide lines or just something I'm personally used to. I have no strong opinion here.

More nits inline below,

Quoted 61 lines
Quoted 5 lines

The rest looks good, especially for use of the latch. I'd be tempted to turn "0, 1, 2, 3" into an enum though, so we can follow in the code what each of those array entry really means.

Agreed.

---
Subject: module: Optimize __module_address() using a latched RB-tree
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 26 10:57:34 CET 2015

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.

Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Steven Rostedt <[email protected]>
Cc Mathieu Desnoyers <[email protected]>
---
 include/linux/module.h |   19 +++-
 kernel/module.c        |  212
 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 224 insertions(+), 7 deletions(-)
include/linux/module.h +6 -0
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,6 +211,11 @@ enum module_state {
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
@@ -269,8 +275,15 @@ struct module {
 	/* Startup function. */
 	int (*init)(void);

include/linux/module.h struct module { · line 284

Quoted 10 lines
include/linux/module.h +7 -2
 
-	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	/*
+	 * If this is non-NULL, vfree after init() returns
+	 *
+	 * cacheline align here, such that:
+	 *   module_init, module_core, init_size, core_size and
+	 *   tree_node[0]
+	 * are on the same cacheline.

Fat-fingered newline ? ;)

include/linux/module.h struct module { · line 297

Quoted 10 lines
include/linux/module.h +3 -0
+	 */
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -281,6 +294,8 @@ struct module {
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];

4 -> nr_module_addr_latch

Quoted 37 lines
include/linux/module.h +1 -0
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
kernel/module.c +6 -0
@@ -102,6 +102,204 @@
 DEFINE_MUTEX(module_mutex);
 EXPORT_SYMBOL_GPL(module_mutex);
 static LIST_HEAD(modules);
+
+
+/*
+ * Use a latched RB-tree for __module_address()
+ *
+ * The latch concept is a multi-value concurrency data structure which

allows
+ * unserialized access and guarantees at least one version is stable.
+ *
+ * It is employed here to optimize __module_address(), which needs to find the
+ * module (if any) associated with an address. Such questions are best answered
+ * using a binary search tree.
+ *
+ * Since modules use non-overlapping memory ranges we can use a regular RB-tree
+ * (as opposed to the interval tree). However, BSTs cannot be iterated while
+ * modified.
+ *
+ * To overcome this we use the latched RB-tree, it basically consists of two
+ * RB-trees which are modified in order, ensuring one is always consistent.
+ *
+ * Things are somewhat more complicated because there are two ranges per
+ * module, but other than that its pretty straight forward.
+ *
+ */

kernel/module.c line 133

Quoted 6 lines
kernel/module.c +6 -0
+
+enum {
+	latch0_core = 0,
+	latch1_core = 1,
+	latch0_init = 2,
+	latch1_init = 3,

nr_module_addr_latch,

Perhaps namespace this enum and move it to module.h so we can expose nr_module_addr_latch ?

Quoted 5 lines
kernel/module.c +5 -0
+};
+
+enum {
+	latch_bit = 0x01,
+	init_bit  = 0x02,

kernel/module.c line 148

Quoted 10 lines
kernel/module.c +10 -0
+};
+
+struct latch_tree_root {
+	seqcount_t	seq;
+	struct rb_root	tree[2];
+};
+
+static unsigned long mod_value(struct module *mod, int idx)
+{
+	if (idx & init_bit)

Hrm, my first reflex is to look for a "init_bit" variable here. Should we use caps for enum entries instead ? e.g. INIT_BIT ?

Thanks,

Mathieu

Quoted 212 lines
kernel/module.c +31 -0
+		return (unsigned long)mod->module_init;
+	else
+		return (unsigned long)mod->module_core;
+}
+
+static unsigned long mod_size(struct module *mod, int idx)
+{
+	if (idx & init_bit)
+		return mod->init_size;
+	else
+		return mod->core_size;
+}
+
+static struct module *mod_entry(struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	return mn->mod;
+}
+
+static int mod_node_idx(struct module *m, struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	int idx = mn - m->tree_node;
+
+	BUG_ON(mn->mod != m);
+	BUG_ON((unsigned)idx > 3);
+
+	return idx;
+}
+
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c +29 -0
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);
+	rb_insert_color(&mn->node, root);
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c +103 -5
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);
+}
+
+/*
+ * struct module is arranged such that:
+ *
+ *   module_init, module_core, init_size, core_size,
+ *   init_text_size, core_text_size and tree_node[0]
+ *
+ * are on the same cacheline, therefore if the below iteration is
+ * on latch0 and all module init has completed, we'll only hit
+ * tree_node[0] and every intermediate level will hit only a single
+ * cacheline.
+ *
+ * Furthermore, by ensuring init_text_size and core_text_size are
+ * also in this same cacheline we've made sure is_module_text_address()
+ * will also not require additional lines.
+ */
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+	unsigned long m_val, m_size;
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		m_val = mod_value(m, idx);
+		m_size = mod_size(m, idx);
+
+		if (addr < m_val)
+			n = n->rb_left;
+		else if (addr >= m_val + m_size)
+			n = n->rb_right;
+		else
+			return m;
+	}
+
+	return NULL;
+}
+
+static struct latch_tree_root mod_tree;
+
+static void mod_tree_insert(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove_init(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static struct module *mod_tree_find(unsigned long addr)
+{
+	struct module *m;
+	unsigned int seq;
+
+	do {
+		seq = raw_read_seqcount(&mod_tree.seq);
+		m = __tree_find(&mod_tree.tree[seq & latch_bit], addr);
+	} while (read_seqcount_retry(&mod_tree.seq, seq));
+
+	return m;
+}
+
 #ifdef CONFIG_KGDB_KDB
 struct list_head *kdb_modules = &modules; /* kdb needs the list of modules
 */
 #endif /* CONFIG_KGDB_KDB */
@@ -1854,6 +2052,7 @@ static void free_module(struct module *m
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	/* Remove this module from bug list, this uses list_del_rcu */
 	module_bug_cleanup(mod);
 	/* Wait for RCU synchronizing before releasing mod->list and buglist. */
@@ -3098,6 +3297,7 @@ static noinline int do_init_module(struc
 	mod->symtab = mod->core_symtab;
 	mod->strtab = mod->core_strtab;
 #endif
+	mod_tree_remove_init(mod);
 	unset_module_init_ro_nx(mod);
 	module_arch_freeing_init(mod);
 	mod->module_init = NULL;
@@ -3168,6 +3368,7 @@ static int add_unformed_module(struct mo
 		goto out;
 	}
 	list_add_rcu(&mod->list, &modules);
+	mod_tree_insert(mod);
 	err = 0;
 
 out:
@@ -3367,6 +3568,7 @@ static int load_module(struct load_info
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	wake_up_all(&module_wq);
 	/* Wait for RCU synchronizing before releasing mod->list. */
 	synchronize_rcu();
@@ -3810,13 +4012,13 @@ struct module *__module_address(unsigned
 	if (addr < module_addr_min || addr > module_addr_max)
 		return NULL;
 
-	list_for_each_entry_rcu(mod, &modules, list) {
+	mod = mod_tree_find(addr);
+	if (mod) {
+		BUG_ON(!within_module(addr, mod));
 		if (mod->state == MODULE_STATE_UNFORMED)
-			continue;
-		if (within_module(addr, mod))
-			return mod;
+			mod = NULL;
 	}
-	return NULL;
+	return mod;
 }
 EXPORT_SYMBOL_GPL(__module_address);
 
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#15 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 6 lines · Mathieu Desnoyers
Quoted 1 line

Dunno, it seemed like a good a place as any.

My personal coding-style is to put all definitions at the top of C files, but I don't know if it's within the kernel coding style guide lines or just something I'm personally used to. I have no strong opinion here.

So I had all the data structure definition in the C file as well to keep them private, and then you get into the situation where you can't put it at the top anyhow.

I further wanted to keep the entire mod_tree stuff together so it can be easily read. I suppose I can move it to the top of that section, but the reason I had it there is that it didn't need to exist before that.

Quoted 4 lines
Quoted 4 lines
include/linux/module.h +0 -0
@@ -269,8 +275,15 @@ struct module {
 	/* Startup function. */
 	int (*init)(void);
 
Quoted 9 lines

include/linux/module.h struct module { · line 284

Quoted 7 lines
include/linux/module.h +7 -0
+	/*
+	 * If this is non-NULL, vfree after init() returns
+	 *
+	 * cacheline align here, such that:
+	 *   module_init, module_core, init_size, core_size and
+	 *   tree_node[0]
+	 * are on the same cacheline.

Fat-fingered newline ? ;)

I made it:

/*
* If this is non-NULL, vfree after init() returns. *
* Cacheline align here, such that:
* module_init, module_core, init_size, core_size,
* init_text_size, core_text_size and tree_node[0]
* are on the same cacheline.
*/

To be consistent with the other comment.

Quoted 9 lines
Quoted 9 lines
include/linux/module.h +2 -0
+	 */
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -281,6 +294,8 @@ struct module {
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
Quoted 3 lines

include/linux/module.h struct module { · line 297

Quoted 1 line
include/linux/module.h +1 -0
+	struct module_node tree_node[4];

4 -> nr_module_addr_latch

Yeah, I dunno, that means moving that enum to the header file, I kinda liked having it all together in the C file.

What Rusty want though.

#16 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Mathieu Desnoyers
Quoted 6 lines · Mathieu Desnoyers

kernel/module.c line 148

Quoted 3 lines
kernel/module.c +3 -0
+static unsigned long mod_value(struct module *mod, int idx)
+{
+	if (idx & init_bit)

Hrm, my first reflex is to look for a "init_bit" variable here. Should we use caps for enum entries instead ? e.g. INIT_BIT ?

I could change those bit things to CPP and then use caps :-)

#17 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Peter Zijlstra
Quoted 35 lines · Peter Zijlstra
Quoted 3 lines · Mathieu Desnoyers

Perhaps you could use mod_value() below, and introduce a "mod_size()" too. This would keep the init vs core selection out of the traversal code.

Indeed!

Quoted 2 lines

Is it customary to define static variables in the middle of a C file ?

Dunno, it seemed like a good a place as any.

Quoted 4 lines

The rest looks good, especially for use of the latch. I'd be tempted to turn "0, 1, 2, 3" into an enum though, so we can follow in the code what each of those array entry really means.

Agreed.

---
Subject: module: Optimize __module_address() using a latched RB-tree
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 26 10:57:34 CET 2015

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.

Quoted 6 lines
Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Steven Rostedt <[email protected]>
Cc Mathieu Desnoyers <[email protected]>

Color me confused, both by the existing code and the modifications.

It appears that you are using seqlock to force readers to retry when a concurrent update occurs, but I don't see what is ensuring that the readers see good data when racing with an insertion or a deletion. Yes, the reader will be retried, courtesy of the seqlock, but that won't help if the reader segfaults before it gets to the read_seqcount_retry().

Questions below.

Quoted 150 lines
---
 include/linux/module.h |   19 +++-
 kernel/module.c        |  212 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 224 insertions(+), 7 deletions(-)
include/linux/module.h +17 -2
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,6 +211,11 @@ enum module_state {
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
@@ -269,8 +275,15 @@ struct module {
 	/* Startup function. */
 	int (*init)(void);
 
-	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	/*
+	 * If this is non-NULL, vfree after init() returns
+	 *
+	 * cacheline align here, such that:
+	 *   module_init, module_core, init_size, core_size and
+	 *   tree_node[0]
+	 * are on the same cacheline.
+	 */
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -281,6 +294,8 @@ struct module {
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
kernel/module.c +90 -0
@@ -102,6 +102,204 @@
 DEFINE_MUTEX(module_mutex);
 EXPORT_SYMBOL_GPL(module_mutex);
 static LIST_HEAD(modules);
+
+
+/*
+ * Use a latched RB-tree for __module_address()
+ *
+ * The latch concept is a multi-value concurrency data structure which allows
+ * unserialized access and guarantees at least one version is stable.
+ *
+ * It is employed here to optimize __module_address(), which needs to find the
+ * module (if any) associated with an address. Such questions are best answered
+ * using a binary search tree.
+ *
+ * Since modules use non-overlapping memory ranges we can use a regular RB-tree
+ * (as opposed to the interval tree). However, BSTs cannot be iterated while
+ * modified.
+ *
+ * To overcome this we use the latched RB-tree, it basically consists of two
+ * RB-trees which are modified in order, ensuring one is always consistent.
+ *
+ * Things are somewhat more complicated because there are two ranges per
+ * module, but other than that its pretty straight forward.
+ *
+ */
+
+enum {
+	latch0_core = 0,
+	latch1_core = 1,
+	latch0_init = 2,
+	latch1_init = 3,
+};
+
+enum {
+	latch_bit = 0x01,
+	init_bit  = 0x02,
+};
+
+struct latch_tree_root {
+	seqcount_t	seq;
+	struct rb_root	tree[2];
+};
+
+static unsigned long mod_value(struct module *mod, int idx)
+{
+	if (idx & init_bit)
+		return (unsigned long)mod->module_init;
+	else
+		return (unsigned long)mod->module_core;
+}
+
+static unsigned long mod_size(struct module *mod, int idx)
+{
+	if (idx & init_bit)
+		return mod->init_size;
+	else
+		return mod->core_size;
+}
+
+static struct module *mod_entry(struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	return mn->mod;
+}
+
+static int mod_node_idx(struct module *m, struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	int idx = mn - m->tree_node;
+
+	BUG_ON(mn->mod != m);
+	BUG_ON((unsigned)idx > 3);
+
+	return idx;
+}
+
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);

kernel/module.c line 204

Quoted 10 lines
kernel/module.c +10 -0
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly. There needs to be a memory barrier between initialization and this call to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the compiler (for everyone) can reorder, which could result in some hapless reader seeing pre-initialized data.

Or did I miss the memory barrier?

kernel/module.c line 205

Quoted 1 line
kernel/module.c +1 -0
+	rb_insert_color(&mn->node, root);

This -might- be OK -- the rotations do not make new nodes visible, instead simply rearranging nodes that are already visible.

For both rb_link_node() and rb_insert_color(), given that we are updating pointers while readers are traversing them, READ_ONCE() and WRITE_ONCE() would be good. Yes, the compiler -probably- doesn't mess you up, but it would be completely within its rights to do so. :-/

Alpha would like either rcu_dereference() or lockless_dereference() instead of READ_ONCE(), of course!

kernel/module.c line 213

Quoted 8 lines
kernel/module.c +8 -0
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);

This is just removing and not freeing, so OK from a read-side viewpoint. WRITE_ONCE() would be good.

Quoted 21 lines
kernel/module.c +21 -0
+}
+
+/*
+ * struct module is arranged such that:
+ *
+ *   module_init, module_core, init_size, core_size,
+ *   init_text_size, core_text_size and tree_node[0]
+ *
+ * are on the same cacheline, therefore if the below iteration is
+ * on latch0 and all module init has completed, we'll only hit
+ * tree_node[0] and every intermediate level will hit only a single
+ * cacheline.
+ *
+ * Furthermore, by ensuring init_text_size and core_text_size are
+ * also in this same cacheline we've made sure is_module_text_address()
+ * will also not require additional lines.
+ */
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+	unsigned long m_val, m_size;

kernel/module.c line 244

Quoted 10 lines
kernel/module.c +10 -0
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		m_val = mod_value(m, idx);
+		m_size = mod_size(m, idx);
+
+		if (addr < m_val)
+			n = n->rb_left;

We need a rcu_dereference() or lockless_dereference() here, I think.

kernel/module.c line 246

Quoted 2 lines
kernel/module.c +2 -0
+		else if (addr >= m_val + m_size)
+			n = n->rb_right;

And here.

kernel/module.c line 251

Quoted 5 lines
kernel/module.c +5 -0
+		else
+			return m;
+	}
+
+	return NULL;

I did finally find the RCU read-side critical section, supplied by is_module_text_address()'s preempt_disable() and preempt_enable(). The matching synchronize_sched() is supplied by do_init_module() and load_module(). I expected a synchronize_sched() in free_module() as well, but I only see a synchronize_rcu(). Is the required synchronize_sched() on this code path hiding somewhere?

Or did I miss an rcu_read_lock()/rcu_read_unlock() pair somewhere?

Thanx, Paul

Quoted 106 lines
kernel/module.c +60 -5
+}
+
+static struct latch_tree_root mod_tree;
+
+static void mod_tree_insert(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove_init(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static struct module *mod_tree_find(unsigned long addr)
+{
+	struct module *m;
+	unsigned int seq;
+
+	do {
+		seq = raw_read_seqcount(&mod_tree.seq);
+		m = __tree_find(&mod_tree.tree[seq & latch_bit], addr);
+	} while (read_seqcount_retry(&mod_tree.seq, seq));
+
+	return m;
+}
+
 #ifdef CONFIG_KGDB_KDB
 struct list_head *kdb_modules = &modules; /* kdb needs the list of modules */
 #endif /* CONFIG_KGDB_KDB */
@@ -1854,6 +2052,7 @@ static void free_module(struct module *m
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	/* Remove this module from bug list, this uses list_del_rcu */
 	module_bug_cleanup(mod);
 	/* Wait for RCU synchronizing before releasing mod->list and buglist. */
@@ -3098,6 +3297,7 @@ static noinline int do_init_module(struc
 	mod->symtab = mod->core_symtab;
 	mod->strtab = mod->core_strtab;
 #endif
+	mod_tree_remove_init(mod);
 	unset_module_init_ro_nx(mod);
 	module_arch_freeing_init(mod);
 	mod->module_init = NULL;
@@ -3168,6 +3368,7 @@ static int add_unformed_module(struct mo
 		goto out;
 	}
 	list_add_rcu(&mod->list, &modules);
+	mod_tree_insert(mod);
 	err = 0;
 
 out:
@@ -3367,6 +3568,7 @@ static int load_module(struct load_info
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	wake_up_all(&module_wq);
 	/* Wait for RCU synchronizing before releasing mod->list. */
 	synchronize_rcu();
@@ -3810,13 +4012,13 @@ struct module *__module_address(unsigned
 	if (addr < module_addr_min || addr > module_addr_max)
 		return NULL;
 
-	list_for_each_entry_rcu(mod, &modules, list) {
+	mod = mod_tree_find(addr);
+	if (mod) {
+		BUG_ON(!within_module(addr, mod));
 		if (mod->state == MODULE_STATE_UNFORMED)
-			continue;
-		if (within_module(addr, mod))
-			return mod;
+			mod = NULL;
 	}
-	return NULL;
+	return mod;
 }
 EXPORT_SYMBOL_GPL(__module_address);
 
#18 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

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

Quoted 51 lines

From: "Paul E. McKenney" <[email protected]>
To: "Peter Zijlstra" <[email protected]>
Cc: "Mathieu Desnoyers" <[email protected]>, "Andi Kleen" <[email protected]>, "Andi Kleen" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Thursday, February 26, 2015 1:28:17 PM
Subject: Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 35 lines · Peter Zijlstra
Quoted 3 lines · Mathieu Desnoyers

Perhaps you could use mod_value() below, and introduce a "mod_size()" too. This would keep the init vs core selection out of the traversal code.

Indeed!

Quoted 2 lines

Is it customary to define static variables in the middle of a C file ?

Dunno, it seemed like a good a place as any.

Quoted 4 lines

The rest looks good, especially for use of the latch. I'd be tempted to turn "0, 1, 2, 3" into an enum though, so we can follow in the code what each of those array entry really means.

Agreed.

---
Subject: module: Optimize __module_address() using a latched RB-tree
From: Peter Zijlstra <[email protected]>
Date: Thu Feb 26 10:57:34 CET 2015

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.

Quoted 6 lines
Cc Oleg Nesterov <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc Rusty Russell <[email protected]>
Cc Steven Rostedt <[email protected]>
Cc Mathieu Desnoyers <[email protected]>
Quoted 7 lines

Color me confused, both by the existing code and the modifications.

It appears that you are using seqlock to force readers to retry when a concurrent update occurs, but I don't see what is ensuring that the readers see good data when racing with an insertion or a deletion. Yes, the reader will be retried, courtesy of the seqlock, but that won't help if the reader segfaults before it gets to the read_seqcount_retry().

Good point! This scheme works when readers have no "side effect" due to reading a data structure while it is changing. Dereferencing a pointer is indeed a side-effect which could lead to a segfault.

Quoted 179 lines

Questions below.

Quoted 159 lines
---
 include/linux/module.h |   19 +++-
 kernel/module.c        |  212
 +++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 224 insertions(+), 7 deletions(-)
include/linux/module.h +17 -2
@@ -17,6 +17,7 @@
 #include <linux/moduleparam.h>
 #include <linux/jump_label.h>
 #include <linux/export.h>
+#include <linux/rbtree.h>
 
 #include <linux/percpu.h>
 #include <asm/module.h>
@@ -210,6 +211,11 @@ enum module_state {
 	MODULE_STATE_UNFORMED,	/* Still setting it up. */
 };
 
+struct module_node {
+	struct module *mod;
+	struct rb_node node;
+};
+
 struct module {
 	enum module_state state;
 
@@ -269,8 +275,15 @@ struct module {
 	/* Startup function. */
 	int (*init)(void);
 
-	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	/*
+	 * If this is non-NULL, vfree after init() returns
+	 *
+	 * cacheline align here, such that:
+	 *   module_init, module_core, init_size, core_size and
+	 *   tree_node[0]
+	 * are on the same cacheline.
+	 */
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -281,6 +294,8 @@ struct module {
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
kernel/module.c +6 -0
@@ -102,6 +102,204 @@
 DEFINE_MUTEX(module_mutex);
 EXPORT_SYMBOL_GPL(module_mutex);
 static LIST_HEAD(modules);
+
+
+/*
+ * Use a latched RB-tree for __module_address()
+ *
+ * The latch concept is a multi-value concurrency data structure which

allows
+ * unserialized access and guarantees at least one version is stable.
+ *
+ * It is employed here to optimize __module_address(), which needs to find the
+ * module (if any) associated with an address. Such questions are best answered
+ * using a binary search tree.
+ *
+ * Since modules use non-overlapping memory ranges we can use a regular RB-tree
+ * (as opposed to the interval tree). However, BSTs cannot be iterated while
+ * modified.
+ *
+ * To overcome this we use the latched RB-tree, it basically consists of two
+ * RB-trees which are modified in order, ensuring one is always consistent.
+ *
+ * Things are somewhat more complicated because there are two ranges per
+ * module, but other than that its pretty straight forward.
+ *
+ */

kernel/module.c +52 -0
+
+enum {
+	latch0_core = 0,
+	latch1_core = 1,
+	latch0_init = 2,
+	latch1_init = 3,
+};
+
+enum {
+	latch_bit = 0x01,
+	init_bit  = 0x02,
+};
+
+struct latch_tree_root {
+	seqcount_t	seq;
+	struct rb_root	tree[2];
+};
+
+static unsigned long mod_value(struct module *mod, int idx)
+{
+	if (idx & init_bit)
+		return (unsigned long)mod->module_init;
+	else
+		return (unsigned long)mod->module_core;
+}
+
+static unsigned long mod_size(struct module *mod, int idx)
+{
+	if (idx & init_bit)
+		return mod->init_size;
+	else
+		return mod->core_size;
+}
+
+static struct module *mod_entry(struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	return mn->mod;
+}
+
+static int mod_node_idx(struct module *m, struct rb_node *n)
+{
+	struct module_node *mn = container_of(n, struct module_node, node);
+	int idx = mn - m->tree_node;
+
+	BUG_ON(mn->mod != m);
+	BUG_ON((unsigned)idx > 3);
+
+	return idx;
+}
+
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c +15 -0
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);

kernel/module.c line 204

Quoted 10 lines
kernel/module.c +10 -0
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly. There needs to be a memory barrier between initialization and this call to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the compiler (for everyone) can reorder, which could result in some hapless reader seeing pre-initialized data.

Quoted 1 line

Or did I miss the memory barrier?

Given that readers (which will retry eventually) can indeed try to concurrently access the object, those would be needed.

Quoted 6 lines

kernel/module.c line 205

Quoted 2 lines
kernel/module.c +1 -0
+	rb_insert_color(&mn->node, root);

This -might- be OK -- the rotations do not make new nodes visible, instead simply rearranging nodes that are already visible.

Quoted 7 lines

For both rb_link_node() and rb_insert_color(), given that we are updating pointers while readers are traversing them, READ_ONCE() and WRITE_ONCE() would be good. Yes, the compiler -probably- doesn't mess you up, but it would be completely within its rights to do so. :-/

Alpha would like either rcu_dereference() or lockless_dereference() instead of READ_ONCE(), of course!

Yes, probably better to err on the safe side here. We have to take into account that a reader can observe the data structure while being modified, but if this occurs, it will retry (but should not segfault nor loop endlessly).

Quoted 13 lines

kernel/module.c line 213

Quoted 10 lines
kernel/module.c +3 -0
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module

*mod, int idx)

kernel/module.c +5 -0
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);

This is just removing and not freeing, so OK from a read-side viewpoint. WRITE_ONCE() would be good.

I'd be worried about the eventual free after this function. There is a need to use RCU here to delay reclaim.

Quoted 53 lines
Quoted 22 lines
kernel/module.c +21 -0
+}
+
+/*
+ * struct module is arranged such that:
+ *
+ *   module_init, module_core, init_size, core_size,
+ *   init_text_size, core_text_size and tree_node[0]
+ *
+ * are on the same cacheline, therefore if the below iteration is
+ * on latch0 and all module init has completed, we'll only hit
+ * tree_node[0] and every intermediate level will hit only a single
+ * cacheline.
+ *
+ * Furthermore, by ensuring init_text_size and core_text_size are
+ * also in this same cacheline we've made sure is_module_text_address()
+ * will also not require additional lines.
+ */
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+	unsigned long m_val, m_size;

kernel/module.c line 244

Quoted 10 lines
kernel/module.c +10 -0
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		m_val = mod_value(m, idx);
+		m_size = mod_size(m, idx);
+
+		if (addr < m_val)
+			n = n->rb_left;

We need a rcu_dereference() or lockless_dereference() here, I think.

kernel/module.c line 246

Quoted 2 lines
kernel/module.c +2 -0
+		else if (addr >= m_val + m_size)
+			n = n->rb_right;

And here.

kernel/module.c line 251

Quoted 5 lines
kernel/module.c +5 -0
+		else
+			return m;
+	}
+
+	return NULL;

I did finally find the RCU read-side critical section, supplied by is_module_text_address()'s preempt_disable() and preempt_enable(). The matching synchronize_sched() is supplied by do_init_module() and load_module(). I expected a synchronize_sched() in free_module() as well, but I only see a synchronize_rcu(). Is the required synchronize_sched() on this code path hiding somewhere?

Quoted 1 line

Or did I miss an rcu_read_lock()/rcu_read_unlock() pair somewhere?

I did not see any, nor any documentation that points to those. We might want to add documentation to raw_write_seqcount_latch() telling about the requirements about making sure concurrent readers don't trigger side-effects. It's not as simple as the timekeeper use-case, due to having pointers here.

Good catch !

Thanks,

Mathieu

Quoted 112 lines

Thanx, Paul

Quoted 107 lines
kernel/module.c +60 -5
+}
+
+static struct latch_tree_root mod_tree;
+
+static void mod_tree_insert(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_insert(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove_init(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static void mod_tree_remove(struct module *mod)
+{
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch0_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch0_init);
+	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, latch1_core);
+	if (mod->init_size)
+		__tree_remove(&mod_tree, mod, latch1_init);
+}
+
+static struct module *mod_tree_find(unsigned long addr)
+{
+	struct module *m;
+	unsigned int seq;
+
+	do {
+		seq = raw_read_seqcount(&mod_tree.seq);
+		m = __tree_find(&mod_tree.tree[seq & latch_bit], addr);
+	} while (read_seqcount_retry(&mod_tree.seq, seq));
+
+	return m;
+}
+
 #ifdef CONFIG_KGDB_KDB
 struct list_head *kdb_modules = &modules; /* kdb needs the list of modules
 */
 #endif /* CONFIG_KGDB_KDB */
@@ -1854,6 +2052,7 @@ static void free_module(struct module *m
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	/* Remove this module from bug list, this uses list_del_rcu */
 	module_bug_cleanup(mod);
 	/* Wait for RCU synchronizing before releasing mod->list and buglist. */
@@ -3098,6 +3297,7 @@ static noinline int do_init_module(struc
 	mod->symtab = mod->core_symtab;
 	mod->strtab = mod->core_strtab;
 #endif
+	mod_tree_remove_init(mod);
 	unset_module_init_ro_nx(mod);
 	module_arch_freeing_init(mod);
 	mod->module_init = NULL;
@@ -3168,6 +3368,7 @@ static int add_unformed_module(struct mo
 		goto out;
 	}
 	list_add_rcu(&mod->list, &modules);
+	mod_tree_insert(mod);
 	err = 0;
 
 out:
@@ -3367,6 +3568,7 @@ static int load_module(struct load_info
 	mutex_lock(&module_mutex);
 	/* Unlink carefully: kallsyms could be walking list. */
 	list_del_rcu(&mod->list);
+	mod_tree_remove(mod);
 	wake_up_all(&module_wq);
 	/* Wait for RCU synchronizing before releasing mod->list. */
 	synchronize_rcu();
@@ -3810,13 +4012,13 @@ struct module *__module_address(unsigned
 	if (addr < module_addr_min || addr > module_addr_max)
 		return NULL;
 
-	list_for_each_entry_rcu(mod, &modules, list) {
+	mod = mod_tree_find(addr);
+	if (mod) {
+		BUG_ON(!within_module(addr, mod));
 		if (mod->state == MODULE_STATE_UNFORMED)
-			continue;
-		if (within_module(addr, mod))
-			return mod;
+			mod = NULL;
 	}
-	return NULL;
+	return mod;
 }
 EXPORT_SYMBOL_GPL(__module_address);
 
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
#19 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Paul E. McKenney
Quoted 5 lines · Paul E. McKenney

Color me confused, both by the existing code and the modifications.

It appears that you are using seqlock to force readers to retry when a concurrent update occurs, but I don't see what is ensuring that the readers see good data when racing with an insertion or a deletion.

Yes, I suppose that needs a wee bit more work (and comments).

Quoted 3 lines

Yes,
the reader will be retried, courtesy of the seqlock, but that won't help if the reader segfaults before it gets to the read_seqcount_retry().

Right, I don't think that can happen, but see below.

Quoted 20 lines
Quoted 20 lines
kernel/module.c +20 -0
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
Quoted 8 lines

kernel/module.c line 204

Quoted 6 lines
kernel/module.c +6 -0
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly.

You do.

Quoted 6 lines

There needs to be a memory barrier between initialization and this call to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the compiler (for everyone) can reorder, which could result in some hapless reader seeing pre-initialized data.

Or did I miss the memory barrier?

I was going with the one in list_add_rcu() and the two in raw_write_seqcount_latch(), however, now that you made me look at it, I need one in here to ensure mn->mod is observed.

So yes. The best solution might be a mod_tree_init() which initializes those back pointers before this insertion.

Quoted 5 lines

kernel/module.c line 205

Quoted 1 line
kernel/module.c +1 -0
+	rb_insert_color(&mn->node, root);

This -might- be OK -- the rotations do not make new nodes visible, instead simply rearranging nodes that are already visible.

Quoted 7 lines

For both rb_link_node() and rb_insert_color(), given that we are updating pointers while readers are traversing them, READ_ONCE() and WRITE_ONCE() would be good. Yes, the compiler -probably- doesn't mess you up, but it would be completely within its rights to do so. :-/

Alpha would like either rcu_dereference() or lockless_dereference() instead of READ_ONCE(), of course!

I _think_ we should be ok here. Since as you say, we only reorder. If we observe nodes in the wrong order, our traversal gets confused and might return the wrong or no node.

That is fine.

Of course, as you say, the compiler is within its right to split stores and do other creative nonsense without the volatile thing. But I don't think it will actually do so for native word sized thingies.

If we're really paranoid I suppose I can go make copies of the functions that have READ/WRITE_ONCE() in.

As to Alpha, I think we're good there, the split cache would make us see stale data, which is perfectly fine, we'll traverse a crap tree, no problem. As long as native sized and native aligned loads/stores aren't split -- which I'm pretty sure doesn't happen (because of the split cache).

Quoted 11 lines

kernel/module.c line 213

Quoted 8 lines
kernel/module.c +8 -0
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);

This is just removing and not freeing, so OK from a read-side viewpoint. WRITE_ONCE() would be good.

Yah, would need a copy of lib/rbtree.c again :/

Quoted 17 lines
Quoted 4 lines
kernel/module.c +4 -0
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+	unsigned long m_val, m_size;

kernel/module.c line 244

Quoted 10 lines
kernel/module.c +10 -0
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		m_val = mod_value(m, idx);
+		m_size = mod_size(m, idx);
+
+		if (addr < m_val)
+			n = n->rb_left;

We need a rcu_dereference() or lockless_dereference() here, I think.

Quoted 4 lines

kernel/module.c line 246

Quoted 2 lines
kernel/module.c +2 -0
+		else if (addr >= m_val + m_size)
+			n = n->rb_right;

And here.

As per the above argument; without doing the whole READ/WRITE_ONCE for the rb tree primitives, I think we're fine. We don't actually need the read_barrier_depends() I think.

I think this because raw_read_seqcount() will issue an rmb, which should be enough for the 'stable' tree. For the unstable one we don't care as long as we don't see split loads/stores.

Quoted 8 lines

kernel/module.c line 251

Quoted 5 lines
kernel/module.c +5 -0
+		else
+			return m;
+	}
+
+	return NULL;

I did finally find the RCU read-side critical section, supplied by is_module_text_address()'s preempt_disable() and preempt_enable().

Indeed.

Quoted 6 lines

The matching synchronize_sched() is supplied by do_init_module() and load_module(). I expected a synchronize_sched() in free_module() as well, but I only see a synchronize_rcu(). Is the required synchronize_sched() on this code path hiding somewhere?

Or did I miss an rcu_read_lock()/rcu_read_unlock() pair somewhere?

No, I think someone is 'hoping' sync_rcu() implies sync_sched(). But yes, I should look harder at this. I was assuming the existing code was OK here.

#20 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 46 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney

Color me confused, both by the existing code and the modifications.

It appears that you are using seqlock to force readers to retry when a concurrent update occurs, but I don't see what is ensuring that the readers see good data when racing with an insertion or a deletion.

Yes, I suppose that needs a wee bit more work (and comments).

Quoted 3 lines

Yes,
the reader will be retried, courtesy of the seqlock, but that won't help if the reader segfaults before it gets to the read_seqcount_retry().

Right, I don't think that can happen, but see below.

Quoted 20 lines
Quoted 20 lines
kernel/module.c +20 -0
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
Quoted 8 lines

kernel/module.c line 204

Quoted 6 lines
kernel/module.c +6 -0
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly.

Quoted 1 line

You do.

Whew! ;-)

Quoted 5 lines
Quoted 5 lines

There needs to be a memory barrier between initialization and this call to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the compiler (for everyone) can reorder, which could result in some hapless reader seeing pre-initialized data.

Quoted 8 lines
Quoted 1 line

Or did I miss the memory barrier?

I was going with the one in list_add_rcu() and the two in raw_write_seqcount_latch(), however, now that you made me look at it, I need one in here to ensure mn->mod is observed.

So yes. The best solution might be a mod_tree_init() which initializes those back pointers before this insertion.

OK, sounds good.

Quoted 10 lines
Quoted 10 lines

kernel/module.c line 205

Quoted 1 line
kernel/module.c +1 -0
+	rb_insert_color(&mn->node, root);

This -might- be OK -- the rotations do not make new nodes visible, instead simply rearranging nodes that are already visible.

For both rb_link_node() and rb_insert_color(), given that we are updating pointers while readers are traversing them, READ_ONCE() and WRITE_ONCE() would be good. Yes, the compiler -probably- doesn't mess you up, but it would be completely within its rights to do so. :-/

Quoted 8 lines
Quoted 2 lines

Alpha would like either rcu_dereference() or lockless_dereference() instead of READ_ONCE(), of course!

I _think_ we should be ok here. Since as you say, we only reorder. If we observe nodes in the wrong order, our traversal gets confused and might return the wrong or no node.

That is fine.

And seeing an old pointer for some time might cause the CPU to loop, but the update should eventually make its way through the cache hierarchy, which should allow the CPU to find its way out. So agreed.

Quoted 6 lines

Of course, as you say, the compiler is within its right to split stores and do other creative nonsense without the volatile thing. But I don't think it will actually do so for native word sized thingies.

If we're really paranoid I suppose I can go make copies of the functions that have READ/WRITE_ONCE() in.

Well, I am really paranoid, as you know. ;-)

Quoted 5 lines

As to Alpha, I think we're good there, the split cache would make us see stale data, which is perfectly fine, we'll traverse a crap tree, no problem. As long as native sized and native aligned loads/stores aren't split -- which I'm pretty sure doesn't happen (because of the split cache).

I didn't see anything that would cause a pointer to span two cache lines. (Of course, that would break everywhere, not just on Alpha.)

Quoted 12 lines
Quoted 11 lines

kernel/module.c line 213

Quoted 8 lines
kernel/module.c +8 -0
+}
+
+static void __tree_remove(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+
+	rb_erase(&mn->node, root);

This is just removing and not freeing, so OK from a read-side viewpoint. WRITE_ONCE() would be good.

Quoted 1 line

Yah, would need a copy of lib/rbtree.c again :/

Or just have the *_ONCE() calls in the single version. I bet that there is no visible performance loss.

Quoted 22 lines
Quoted 17 lines
Quoted 4 lines
kernel/module.c +4 -0
+static struct module *__tree_find(struct rb_root *r, unsigned long addr)
+{
+	struct rb_node *n = r->rb_node;
+	unsigned long m_val, m_size;

kernel/module.c line 244

Quoted 10 lines
kernel/module.c +10 -0
+
+	while (n) {
+		struct module *m = mod_entry(n);
+		int idx = mod_node_idx(m, n);
+
+		m_val = mod_value(m, idx);
+		m_size = mod_size(m, idx);
+
+		if (addr < m_val)
+			n = n->rb_left;

We need a rcu_dereference() or lockless_dereference() here, I think.

Quoted 4 lines

kernel/module.c line 246

Quoted 2 lines
kernel/module.c +2 -0
+		else if (addr >= m_val + m_size)
+			n = n->rb_right;

And here.

Quoted 7 lines

As per the above argument; without doing the whole READ/WRITE_ONCE for the rb tree primitives, I think we're fine. We don't actually need the read_barrier_depends() I think.

I think this because raw_read_seqcount() will issue an rmb, which should be enough for the 'stable' tree. For the unstable one we don't care as long as we don't see split loads/stores.

I agree that raw_read_seqcount() will issue an rmb(), but that won't help. For Alpha, you need the smp_rmb() to be between the load of any given pointer and the first dereference of that same pointer.

Quoted 16 lines
Quoted 8 lines

kernel/module.c line 251

Quoted 5 lines
kernel/module.c +5 -0
+		else
+			return m;
+	}
+
+	return NULL;

I did finally find the RCU read-side critical section, supplied by is_module_text_address()'s preempt_disable() and preempt_enable().

Indeed.

Quoted 5 lines

The matching synchronize_sched() is supplied by do_init_module() and load_module(). I expected a synchronize_sched() in free_module() as well, but I only see a synchronize_rcu(). Is the required synchronize_sched() on this code path hiding somewhere?

Quoted 5 lines
Quoted 1 line

Or did I miss an rcu_read_lock()/rcu_read_unlock() pair somewhere?

No, I think someone is 'hoping' sync_rcu() implies sync_sched(). But yes, I should look harder at this. I was assuming the existing code was OK here.

I am not blaming you for the code itself, but rather just blaming you for causing me to notice that the code was broken. ;-)

How about if I make something that allows overlapping grace periods, so that we could be safe without latency penalty? One approach would be a synchronize_rcu_mult() with a bitmask indicating which to wait for. Another would be to make variants of get_state_synchronize_rcu() and cond_synchronize_rcu() for RCU-sched as well as for RCU, but also to make get_state_synchronize_rcu() force a grace period to start if one was not already in progress.

Thoughts?

Thanx, Paul

#21 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 2 lines · Paul E. McKenney

Or just have the *_ONCE() calls in the single version. I bet that there is no visible performance loss.

I'll go play with that tomorrow, see what GCC makes of it.

#22 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 5 lines · Peter Zijlstra
Quoted 2 lines · Paul E. McKenney

Or just have the *_ONCE() calls in the single version. I bet that there is no visible performance loss.

I'll go play with that tomorrow, see what GCC makes of it.

Who needs sleep anyhow.. ;-)

21 extra bytes, I've not quite yet figured out what for.

The below changes the insert/erase functions to use WRITE_ONCE() for the rb_{left,right} assignments and removes one program order loop.

I did make squiggles for all scenarios to see if any of the intermediate states had loops in, I only found the one case (erase, case 3).

I also added an rb_link_node_rcu() which does the store_release thing -- I didn't want to include rcupdate.h for fear of header insanity.

We need the store_release because of the node setup in there. So I can forget about my mod_tree_init().

---
 include/linux/rbtree.h           | 10 ++++++
 include/linux/rbtree_augmented.h | 21 ++++++++----
 lib/rbtree.c                     | 71 +++++++++++++++++++++++++++-------------
 3 files changed, 73 insertions(+), 29 deletions(-)
include/linux/rbtree.h +10 -0
index fb31765e935a..ae9df86bf9ba 100644
@@ -31,6 +31,7 @@
 
 #include <linux/kernel.h>
 #include <linux/stddef.h>
+#include <asm/barrier.h>
 
 struct rb_node {
 	unsigned long  __rb_parent_color;
@@ -85,6 +86,15 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 	*rb_link = node;
 }
 
+static inline void rb_link_node_rcu(struct rb_node * node, struct rb_node * parent,
+				struct rb_node ** rb_link)
+{
+	node->__rb_parent_color = (unsigned long)parent;
+	node->rb_left = node->rb_right = NULL;
+
+	smp_store_release(rb_link, node);
+}
+
 #define rb_entry_safe(ptr, type, member) \
 	({ typeof(ptr) ____ptr = (ptr); \
 	   ____ptr ? rb_entry(____ptr, type, member) : NULL; \
include/linux/rbtree_augmented.h +14 -7
index 378c5ee75f78..14d7b831b63a 100644
@@ -123,11 +123,11 @@ __rb_change_child(struct rb_node *old, struct rb_node *new,
 {
 	if (parent) {
 		if (parent->rb_left == old)
-			parent->rb_left = new;
+			WRITE_ONCE(parent->rb_left, new);
 		else
-			parent->rb_right = new;
+			WRITE_ONCE(parent->rb_right, new);
 	} else
-		root->rb_node = new;
+		WRITE_ONCE(root->rb_node, new);
 }
 
 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
@@ -137,7 +137,8 @@ static __always_inline struct rb_node *
 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 		     const struct rb_augment_callbacks *augment)
 {
-	struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+	struct rb_node *child = node->rb_right;
+	struct rb_node *tmp = node->rb_left;
 	struct rb_node *parent, *rebalance;
 	unsigned long pc;
 
@@ -167,6 +168,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 		tmp = parent;
 	} else {
 		struct rb_node *successor = child, *child2;
+
 		tmp = child->rb_left;
 		if (!tmp) {
 			/*
@@ -180,6 +182,7 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 			 */
 			parent = successor;
 			child2 = successor->rb_right;
+
 			augment->copy(node, successor);
 		} else {
 			/*
@@ -201,19 +204,23 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 				successor = tmp;
 				tmp = tmp->rb_left;
 			} while (tmp);
-			parent->rb_left = child2 = successor->rb_right;
-			successor->rb_right = child;
+			child2 = successor->rb_right;
+			WRITE_ONCE(parent->rb_left, child2);
+			WRITE_ONCE(successor->rb_right, child);
 			rb_set_parent(child, successor);
+
 			augment->copy(node, successor);
 			augment->propagate(parent, successor);
 		}
 
-		successor->rb_left = tmp = node->rb_left;
+		tmp = node->rb_left;
+		WRITE_ONCE(successor->rb_left, tmp);
 		rb_set_parent(tmp, successor);
 
 		pc = node->__rb_parent_color;
 		tmp = __rb_parent(pc);
 		__rb_change_child(node, successor, tmp, root);
+
 		if (child2) {
 			successor->__rb_parent_color = pc;
 			rb_set_parent_color(child2, parent, RB_BLACK);
lib/rbtree.c +49 -22

137 lines not on this page · raw message

#24 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 5 lines · Andi Kleen
Quoted 2 lines

Thoughts?

Just use my original patch using page tables which did not need any of these research projects.

Hey, some people actually like to think! And the benefit is that all archs get a win.

#25 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Paul E. McKenney
Quoted 11 lines · Paul E. McKenney
Quoted 7 lines

As per the above argument; without doing the whole READ/WRITE_ONCE for the rb tree primitives, I think we're fine. We don't actually need the read_barrier_depends() I think.

I think this because raw_read_seqcount() will issue an rmb, which should be enough for the 'stable' tree. For the unstable one we don't care as long as we don't see split loads/stores.

I agree that raw_read_seqcount() will issue an rmb(), but that won't help. For Alpha, you need the smp_rmb() to be between the load of any given pointer and the first dereference of that same pointer.

OK, it seems I'm confused on Alpha, perhaps you can clarify.

My confusion stems from the fact that when things are properly serialized with locks we do not need these additional barriers.

Then why would we need them to correctly iterate the stable copy of the tree?

I appreciate we would need them to correctly iterate an true lockless data structure, but our in-flight copy of the tree cannot be correctly iterated anyway, all we want is for that iteration to:

1) only observe valid nodes -- ie. no pointers out into the wild due to split load/stores.

2) terminate -- ie. not get stuck in loops.

And I don't see that read_barrier_depends() helping with either for the unstable tree; 1) is guaranteed by my patch making the modifiers user WRITE_ONCE(), and 2) we agreed is guaranteed by the modifiers not having loops in program order, any cache effects will disappear over time.

Quoted 7 lines
Quoted 3 lines

No, I think someone is 'hoping' sync_rcu() implies sync_sched(). But yes, I should look harder at this. I was assuming the existing code was OK here.

I am not blaming you for the code itself, but rather just blaming you for causing me to notice that the code was broken. ;-)

Quoted 7 lines

How about if I make something that allows overlapping grace periods, so that we could be safe without latency penalty? One approach would be a synchronize_rcu_mult() with a bitmask indicating which to wait for. Another would be to make variants of get_state_synchronize_rcu() and cond_synchronize_rcu() for RCU-sched as well as for RCU, but also to make get_state_synchronize_rcu() force a grace period to start if one was not already in progress.

This is module unload, not a fast path by anyones measure I think. However if you do go about making such a primitive I know of at least one other place this could be used; we have the following in _cpu_down():

#ifdef CONFIG_PREEMPT
	synchronize_sched();
#endif
	synchronize_rcu();
#26 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 9 lines · Peter Zijlstra
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines

As per the above argument; without doing the whole READ/WRITE_ONCE for the rb tree primitives, I think we're fine. We don't actually need the read_barrier_depends() I think.

I think this because raw_read_seqcount() will issue an rmb, which should be enough for the 'stable' tree. For the unstable one we don't care as long as we don't see split loads/stores.

Quoted 8 lines
Quoted 3 lines

I agree that raw_read_seqcount() will issue an rmb(), but that won't help. For Alpha, you need the smp_rmb() to be between the load of any given pointer and the first dereference of that same pointer.

OK, it seems I'm confused on Alpha, perhaps you can clarify.

My confusion stems from the fact that when things are properly serialized with locks we do not need these additional barriers.

The readers hold locks? Keep in mind that raw_read_seqcount() isn't really a lock -- updates can run concurrently with a read. A doomed read, to be sure, but nevertheless a read that is traversing pointers that are changing out from under it.

Quoted 11 lines

Then why would we need them to correctly iterate the stable copy of the tree?

I appreciate we would need them to correctly iterate an true lockless data structure, but our in-flight copy of the tree cannot be correctly iterated anyway, all we want is for that iteration to:

1) only observe valid nodes -- ie. no pointers out into the wild due to split load/stores.

2) terminate -- ie. not get stuck in loops.

True, but don't new nodes get inserted into a tree that might possibly be concurrently read?

Quoted 4 lines

And I don't see that read_barrier_depends() helping with either for the unstable tree; 1) is guaranteed by my patch making the modifiers user WRITE_ONCE(), and 2) we agreed is guaranteed by the modifiers not having loops in program order, any cache effects will disappear over time.

Well, if the readers and writer are really truly excluding each other, then no problem. But if the readers really can run concurrently with writers, even if the readers will subsequently retry, you do need those barriers on Alpha.

The canonical URL on this topic:

	http://www.openvms.compaq.com/wizard/wiz_2637.html
Quoted 20 lines
Quoted 7 lines
Quoted 3 lines

No, I think someone is 'hoping' sync_rcu() implies sync_sched(). But yes, I should look harder at this. I was assuming the existing code was OK here.

I am not blaming you for the code itself, but rather just blaming you for causing me to notice that the code was broken. ;-)

Quoted 7 lines

How about if I make something that allows overlapping grace periods, so that we could be safe without latency penalty? One approach would be a synchronize_rcu_mult() with a bitmask indicating which to wait for. Another would be to make variants of get_state_synchronize_rcu() and cond_synchronize_rcu() for RCU-sched as well as for RCU, but also to make get_state_synchronize_rcu() force a grace period to start if one was not already in progress.

This is module unload, not a fast path by anyones measure I think. However if you do go about making such a primitive I know of at least one other place this could be used; we have the following in _cpu_down():

Quoted 4 lines
#ifdef CONFIG_PREEMPT
	synchronize_sched();
#endif
	synchronize_rcu();

OK, definitely seems worth thinking about, then.

Thanx, Paul

#27 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Peter Zijlstra
Quoted 29 lines · Peter Zijlstra
Quoted 20 lines
Quoted 20 lines
kernel/module.c +20 -0
+static void __tree_insert(struct latch_tree_root *mod_tree, struct module *mod, int idx)
+{
+	struct rb_root *root = &mod_tree->tree[idx & latch_bit];
+	struct module_node *mn = &mod->tree_node[idx];
+	struct rb_node **link = &root->rb_node;
+	struct rb_node *parent = NULL;
+	unsigned long mod_val, m_val;
+	struct module *m;
+	int i;
+
+	mn->mod = mod;
+	mod_val = mod_value(mod, idx);
+
+	while (*link) {
+		parent = *link;
+		m = mod_entry(parent);
+		i = mod_node_idx(m, parent);
+		m_val = mod_value(m, i);
+
+		if (mod_val < m_val)
Quoted 8 lines

kernel/module.c line 204

Quoted 6 lines
kernel/module.c +6 -0
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly.

Quoted 1 line

You do.

I think I have reconsidered; this does not in fact make it visible.

Quoted 10 lines
Quoted 6 lines

There needs to be a memory barrier between initialization and this call to rb_link_node(), otherwise, both the CPU (well, for Alpha) and the compiler (for everyone) can reorder, which could result in some hapless reader seeing pre-initialized data.

Or did I miss the memory barrier?

I was going with the one in list_add_rcu() and the two in raw_write_seqcount_latch(), however, now that you made me look at it, I need one in here to ensure mn->mod is observed.

The 'second' raw_write_seqcount_latch() makes it visible, not the first.

Let me clarify with some documentation I just wrote:

* The basic form is a data structure like:
*
* struct latch_struct {

 *     seqcount_t              seq;
 *     struct data_struct      data[2];
 * };
 *
 * Where a modification, which is assumed to be externally serialized, does the
 * following:
 *
 * void latch_modify(struct latch_struct *latch, ...)
 * {
 *     smp_wmb();      <- Ensure that the last data[1] update is visible
 *     latch->seq++;
 *     smp_wmb();      <- Ensure that the seqcount update is visible
 *
 *     modify(latch->data[0], ...);
 *
 *     smp_wmb();      <- Ensure that the data[0] update is visible
 *     latch->seq++;
 *     smp_wmb();      <- Ensure that the seqcount update is visible
 *
 *     modify(latch->data[1], ...);
 * }
 *
 * The query will have a form like:
 *
 * struct entry *latch_query(struct latch_struct *latch, ...)
 * {
 *     struct entry *entry;
 *     unsigned seq;
 *     int idx;

*
* do {
* seq = latch->seq;
* smp_rmb();
*
* idx = seq & 0x01;
* entry = data_query(latch->data[idx], ...);
*
* smp_rmb();
* } while (seq != latch->seq);
*
* return entry;
* }
*
* So during the modification, queries are first redirected to data[1]. Then we
* modify data[0]. When that is complete, we redirect queries back to data[0]
* and we can modify data[1].

So any addition to data[0] does not become visible until we redirect the readers back to it, which is the second latch increment.

This therefore obviates the need for the atomic publish APIs RCU traditionally employs.

Let me go clarify this point in said documentation.

#28 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 7 lines · Peter Zijlstra
Quoted 5 lines
Quoted 3 lines

kernel/module.c line 204

Quoted 1 line
kernel/module.c +1 -0
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly.

You do.

I think I have reconsidered; this does not in fact make it visible.

Ah; never mind, it is. An iterator could have started in data[0], gone on holiday while the modification took place, and resumed once it is done and magically see the element appear.

Therefore we do indeed need the atomic publishing and I think this also settles my question about Alpha.

#29 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines
Quoted 3 lines

kernel/module.c line 204

Quoted 1 line
kernel/module.c +1 -0
+	rb_link_node(&mn->node, parent, link);

This makes the new module visible to readers, if I understand correctly.

You do.

Quoted 8 lines
Quoted 1 line

I think I have reconsidered; this does not in fact make it visible.

Ah; never mind, it is. An iterator could have started in data[0], gone on holiday while the modification took place, and resumed once it is done and magically see the element appear.

Therefore we do indeed need the atomic publishing and I think this also settles my question about Alpha.

Whew!

Though otherwise whatever you were doing would have been pretty cool and fun to learn about. ;-)

Thanx, Paul

#30 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 4 lines · Paul E. McKenney

Whew!

Though otherwise whatever you were doing would have been pretty cool and fun to learn about. ;-)

So I think I can do that; where readers and writers are fully separated, but it requires:

- tripple latch
- copy operator
- nested RCU

And the result would be horribly expensive (mostly due to the copy operator on dynamic data structures) on the update side, which severely limits the applicability of the scheme.

#31 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney

Whew!

Though otherwise whatever you were doing would have been pretty cool and fun to learn about. ;-)

So I think I can do that; where readers and writers are fully separated, but it requires:

Quoted 7 lines

- tripple latch
- copy operator
- nested RCU

And the result would be horribly expensive (mostly due to the copy operator on dynamic data structures) on the update side, which severely limits the applicability of the scheme.

True enough, if you have a single pointer to an RCU-protected data structure, you can update anything in any way by doing a deep copy of the original, updating, and swapping pointers. And what is a little copy overhead among friends? ;-)

Thanx, Paul

#32 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

In reply to Peter Zijlstra
Quoted 3 lines · Peter Zijlstra

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 (possibly from NMI context).

Um, so the stack unwinders use "does this look like a kernel address" because we omit the frame pointer?

To keep that optimization, we add 220 non-trivial lines to module.c?

Don't get me wrong, it's cute code, but I do wonder if at some point a grown up is going to come along and tell us to stop :)

Cheers,
Rusty.

#33 lore raw

Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

Quoted 7 lines · Rusty Russell
Quoted 3 lines · Peter Zijlstra

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 (possibly from NMI context).

Um, so the stack unwinders use "does this look like a kernel address" because we omit the frame pointer?

Not only because of that I think; also as a general robustness check. I'm not sure people want their stack unwinder to go off into the woods.

Quoted 1 line

To keep that optimization, we add 220 non-trivial lines to module.c?

Can I make you feel better by writing more comments? I'm not sure we can convince the arch people to take this test out. Its all over the place.

Quoted 2 lines

Don't get me wrong, it's cute code, but I do wonder if at some point a grown up is going to come along and tell us to stop :)

Now where's the fun in that ;-)