x86: Move msr accesses out of line
Subsystems (4)
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
@@ -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); - - asmvolatile ("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)); - returnEAX_EDX_VAL (val, low, high); -} - -static inline void native_write_msr (unsigned int msr, -unsigned low,unsigned high) -{ - asmvolatile ("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; - asmvolatile ("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
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
@@ -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)); - returnEAX_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) { asmvolatile ("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
PATCH 3/3 perf, x86: Remove old MSR perf tracing code
In reply to Andi KleenFrom: 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
@@ -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
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.
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
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
#endifxchg(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 elapsedroot@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 elapsedQuoted 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
Borislav Petkov
maintainerQuoted 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.
--RFC PATCH 1/1 module: Optimize __module_address() using a latched RB-tree
In reply to Andi KleenQuoted 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.
--- include/linux/module.h | 8 ++ kernel/module.c | 157 +++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 160 insertions(+), 5 deletions(-)
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 ];
kernel/module.c +183 -5
226 lines not on this page · raw message
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
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Peter ZijlstraQuoted 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
@@ -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
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.
Mathieu Desnoyers
reviewerRe: [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-treeQuoted 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/1805207Yeah, 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-treeOptimize
__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]>Signed-off-by Peter Zijlstra (Intel) <[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
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.
--- 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
Mathieu Desnoyers
reviewerRe: [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-treeQuoted 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 2015Currently
__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]>Signed-off-by Peter Zijlstra (Intel) <[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 *mmutex_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_infomutex_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(unsignedif (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
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.
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Mathieu DesnoyersQuoted 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 :-)
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Peter ZijlstraQuoted 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 2015Currently
__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]>Signed-off-by Peter Zijlstra (Intel) <[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 *mmutex_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_infomutex_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(unsignedif (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);
Mathieu Desnoyers
reviewerRe: [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-treeQuoted 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 2015Currently
__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]>Signed-off-by Peter Zijlstra (Intel) <[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()andrb_insert_color(), given that we are updating pointers while readers are traversing them,READ_ONCE()andWRITE_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()orlockless_dereference()instead ofREAD_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()orlockless_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()andpreempt_enable(). The matchingsynchronize_sched()is supplied bydo_init_module()andload_module(). I expected asynchronize_sched()infree_module()as well, but I only see asynchronize_rcu(). Is the requiredsynchronize_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 *mmutex_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_infomutex_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(unsignedif (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
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Paul E. McKenneyQuoted 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 theread_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()andrb_insert_color(), given that we are updating pointers while readers are traversing them,READ_ONCE()andWRITE_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()orlockless_dereference()instead ofREAD_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()orlockless_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()andpreempt_enable().
Indeed.
Quoted 6 lines
The matching
synchronize_sched()is supplied bydo_init_module()andload_module(). I expected asynchronize_sched()infree_module()as well, but I only see asynchronize_rcu(). Is the requiredsynchronize_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.
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 theread_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 inraw_write_seqcount_latch(), however, now that you made me look at it, I need one in here to ensuremn->modis 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()andrb_insert_color(), given that we are updating pointers while readers are traversing them,READ_ONCE()andWRITE_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()orlockless_dereference()instead ofREAD_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.cagain :/
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()orlockless_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()andpreempt_enable().Indeed.
Quoted 5 lines
The matching
synchronize_sched()is supplied bydo_init_module()andload_module(). I expected asynchronize_sched()infree_module()as well, but I only see asynchronize_rcu(). Is the requiredsynchronize_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()impliessync_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
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.
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
@@ -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
@@ -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
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Paul E. McKenneyQuoted 2 lines
Thoughts?
Just use my original patch using page tables which did not need any of these research projects.
http://www.serverphorums.com/read.php?12,1043794,1043796#msg-1043796
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
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.
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Paul E. McKenneyQuoted 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 anrmb(), but that won't help. For Alpha, you need thesmp_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()impliessync_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 ofget_state_synchronize_rcu()andcond_synchronize_rcu()for RCU-sched as well as for RCU, but also to makeget_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();
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 anrmb(), but that won't help. For Alpha, you need thesmp_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 userWRITE_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()impliessync_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 ofget_state_synchronize_rcu()andcond_synchronize_rcu()for RCU-sched as well as for RCU, but also to makeget_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
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Peter ZijlstraQuoted 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 inraw_write_seqcount_latch(), however, now that you made me look at it, I need one in here to ensuremn->modis 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.
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.
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
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.
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 RCUAnd 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
Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree
In reply to Peter ZijlstraQuoted 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.
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 ;-)