latched RB-trees and __module_address()
Subsystems (6)
Peter Zijlstra
maintainercover latched RB-trees and __module_address()
This series is aimed at making __module_address() go fast(er).
On the way there it:
- annotates and sanitizes module locking
- introduces the latched RB-tree
- employs it to make __module_address() go fast
I've build and boot tested this on x86_64 with modules and lockdep enabled.
Peter Zijlstra
maintainerRFC PATCH 1/9 klp: Fix obvious RCU fail
While one must hold RCU-sched (aka. preempt_disable) for find_symbol() one must equally hold it over the use of the object returned.
The moment you release the RCU-sched read lock, the object can be dead and gone.
--- kernel/livepatch/core.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/livepatch/core.c +2 -1
@@ -248,11 +248,12 @@ static int klp_find_external_symbol(stru/* first, check if it's an exported symbol */ preempt_disable (); sym =find_symbol (name,NULL ,NULL , true, true); -preempt_enable ();if (sym) { *addr = sym->value; +preempt_enable ();return 0 ; } +preempt_enable ();/* otherwise check if it's in another .o within the patch module */ return klp_find_object_symbol (pmod->name, name, addr);
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
Quoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
I guess you'll be taking this together with the series, so I am not applying it.
Thanks,
Signature · 2 lines
Jiri Kosina SUSE Labs
Peter Zijlstra
maintainerRe: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
Quoted 18 lines · Jiri Kosina
Quoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 4 lines
Acked-by Jiri Kosina <[email protected]>I guess you'll be taking this together with the series, so I am not applying it.
Feel free to take it; this series might take a wee while longer to mature.
That said; I do have a follow up question on that code. So now you've successfully obtained an address in module space; but the moment you release that RCU-sched lock, the module can be gone.
How does the whole live patching stuff deal with module removal during patching?
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines
Acked-by Jiri Kosina <[email protected]>I guess you'll be taking this together with the series, so I am not applying it.
Feel free to take it; this series might take a wee while longer to mature.
OK, thanks.
Quoted 6 lines
That said; I do have a follow up question on that code. So now you've successfully obtained an address in module space; but the moment you release that RCU-sched lock, the module can be gone.
How does the whole live patching stuff deal with module removal during patching?
We have a module notifier that serializes using klp_mutex with the patching. Do you see a problem there?
Thanks,
Signature · 2 lines
Jiri Kosina SUSE Labs
Peter Zijlstra
maintainerRe: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
Quoted 11 lines · Jiri Kosina
Quoted 6 lines · Peter Zijlstra
That said; I do have a follow up question on that code. So now you've successfully obtained an address in module space; but the moment you release that RCU-sched lock, the module can be gone.
How does the whole live patching stuff deal with module removal during patching?
We have a module notifier that serializes using
klp_mutexwith the patching. Do you see a problem there?
Should work I think; might be worth noting this in a comment above this lookup though.
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
In reply to Peter ZijlstraQuoted 27 lines · Peter Zijlstra
Quoted 18 lines · Jiri Kosina
Quoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Quoted 4 lines
Acked-by Jiri Kosina <[email protected]>I guess you'll be taking this together with the series, so I am not applying it.
Feel free to take it; this series might take a wee while longer to mature.
Quoted 6 lines
That said; I do have a follow up question on that code. So now you've successfully obtained an address in module space; but the moment you release that RCU-sched lock, the module can be gone.
How does the whole live patching stuff deal with module removal during patching?
There is a notifier, see klp_module_notify(). It applies existing patches when an affected module is loaded. Also it removes patches when an affected module is going. It is serialized with the other operations using the klp_mutex lock.
Hmm, when I think about it. I am afraid that there is a race. For example, the going module might be unpatched by the notifier but a new patch might get applied when it is still visible by kallsyms. I am going to look at it.
Best Regards,
Petr
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Looks good to me.
Thank you,
Quoted 28 lines
--- kernel/livepatch/core.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)kernel/livepatch/core.c +2
-2@@ -248,11 +248,12 @@ static int klp_find_external_symbol(stru/* first, check if it's an exported symbol */ preempt_disable (); sym =find_symbol (name,NULL ,NULL , true, true); -preempt_enable ();if (sym) { *addr = sym->value; +preempt_enable ();return 0 ; } +preempt_enable ();/* otherwise check if it's in another .o within the patch module */ return klp_find_object_symbol (pmod->name, name, addr); --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 4 lines
Masami HIRAMATSU Software Platform Research Dept. Linux Technology Research Center Hitachi, Ltd., Yokohama Research Laboratory E-mail: [email protected]
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 22 lines
--- kernel/livepatch/core.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)kernel/livepatch/core.c +2
-1@@ -248,11 +248,12 @@ static int klp_find_external_symbol(stru/* first, check if it's an exported symbol */ preempt_disable (); sym =find_symbol (name,NULL ,NULL , true, true); -preempt_enable ();if (sym) { *addr = sym->value; +preempt_enable ();return 0 ; } +preempt_enable ();/* otherwise check if it's in another .o within the patch module */ return klp_find_object_symbol (pmod->name, name, addr);
Re: [RFC][PATCH 1/9] klp: Fix obvious RCU fail
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
While one must hold RCU-sched (aka.
preempt_disable) forfind_symbol()one must equally hold it over the use of the object returned.The moment you release the RCU-sched read lock, the object can be dead and gone.
Quoted 9 lines
Cc Seth Jennings <[email protected]>Cc Josh Poimboeuf <[email protected]>Cc Masami Hiramatsu <[email protected]>Cc Miroslav Benes <[email protected]>Cc Petr Mladek <[email protected]>Cc Jiri Kosina <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 22 lines
--- kernel/livepatch/core.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)kernel/livepatch/core.c +2
-1@@ -248,11 +248,12 @@ static int klp_find_external_symbol(stru/* first, check if it's an exported symbol */ preempt_disable (); sym =find_symbol (name,NULL ,NULL , true, true); -preempt_enable ();if (sym) { *addr = sym->value; +preempt_enable ();return 0 ; } +preempt_enable ();/* otherwise check if it's in another .o within the patch module */ return klp_find_object_symbol (pmod->name, name, addr);
Signature · 1 line
Josh
Peter Zijlstra
maintainerRFC PATCH 2/9 module: Sanitize RCU usage and locking
In reply to Peter ZijlstraCurrently the RCU usage in module is an inconsistent mess of RCU and RCU-sched, this is broken for CONFIG_PREEMPT where synchronize_rcu() does not imply synchronize_sched().
Convert everything over to RCU-sched.
Furthermore add lockdep asserts to all sites, because its not at all clear to me the required locking is observed, esp. on exported functions.
--- include/linux/module.h | 12 ++++++++++-- kernel/module.c | 42 ++++++++++++++++++++++++++++++++++-------- lib/bug.c | 7 +++++-- 3 files changed, 49 insertions(+), 12 deletions(-)
include/linux/module.h +10 -2
@@ -415,14 +415,22 @@ struct symsearch {bool unused; }; -/* Search for an exported symbol by name. */ +/* +* Search for an exported symbol by name. +* +* Must be called with module_mutex held or preemption disabled. +*/ const struct kernel_symbol *find_symbol (const char *name,struct module **owner,const unsigned long **crc,bool gplok,bool warn); -/* Walk the exported symbol table */ +/* +* Walk the exported symbol table +* +* Must be called with module_mutex held or preemption disabled. +*/ bool each_symbol_section (bool (*fn)(const struct symsearch *arr,struct module *owner,void *data),void *data);
kernel/module.c +34 -8
91 lines not on this page · raw message
lib/bug.c +5 -2
@@ -66,7 +66,7 @@ static const struct bug_entry *module_fistruct module *mod;const struct bug_entry *bug =NULL ; -rcu_read_lock (); +rcu_read_lock_sched ();list_for_each_entry_rcu (mod, &module_bug_list, bug_list) {unsigned i;
@@ -77,7 +77,7 @@ static const struct bug_entry *module_fi } bug =NULL ; out: -rcu_read_unlock (); +rcu_read_unlock_sched ();return bug; }
@@ -88,6 +88,8 @@ void module_bug_finalize(const Elf_Ehdrchar *secstrings;unsigned int i; +lockdep_assert_held (&module_mutex); + mod->bug_table =NULL ; mod->num_bugs =0 ;
@@ -113,6 +115,7 @@ void module_bug_finalize(const Elf_Ehdrvoid module_bug_cleanup (struct module *mod) { +lockdep_assert_held (&module_mutex);list_del_rcu (&mod->bug_list); }
Re: [RFC][PATCH 2/9] module: Sanitize RCU usage and locking
Quoted 3 lines · Peter Zijlstra
Currently the RCU usage in module is an inconsistent mess of RCU and RCU-sched, this is broken for
CONFIG_PREEMPTwheresynchronize_rcu()does not implysynchronize_sched().
Huh? It's not "an inconsistent mess". They're all synchronize_rcu(), except one.
That one is *specifically* a best effort bandaid for the case where module initialization has failed. It's theoretically racy, so we wait a bit before freeing.
That said, I love the new checks, thanks!
Quoted 7 lines
kernel/module.c +7
-0+static inline void module_assert_mutex (void ) +{ +lockdep_assert_held (&module_mutex); +} + +static inline void module_assert_mutex_or_preempt (void ) +{
kernel/module.c static LIST_HEAD(modules); · line 125
Quoted 10 lines
kernel/module.c +10
-0+#ifdef CONFIG_LOCKDEP +int rcu_held =rcu_read_lock_sched_held (); +int mutex_held =1 ; + +if (debug_locks) + mutex_held =lockdep_is_held (&module_mutex); + +WARN_ON (!rcu_held && !mutex_held); +#endif +}
Minor nitpick: I generally avoid static inline in C files (unless functions are unused under some config options, which these aren't).
In general, they mess up future cleanups, as gcc doesn't warn about unused functions.
Thanks,
Rusty.
Peter Zijlstra
maintainerRe: [RFC][PATCH 2/9] module: Sanitize RCU usage and locking
Quoted 7 lines · Rusty Russell
Quoted 3 lines · Peter Zijlstra
Currently the RCU usage in module is an inconsistent mess of RCU and RCU-sched, this is broken for
CONFIG_PREEMPTwheresynchronize_rcu()does not implysynchronize_sched().Huh? It's not "an inconsistent mess". They're all
synchronize_rcu(), except one.
Uhm, most of them use preempt_disable(), which is RCU-sched, not RCU.
The only RCU user I found was the bug-list thing.
What other RCU users are there?
Quoted 23 lines
That said, I love the new checks, thanks!
Quoted 7 lines
kernel/module.c +7
-0+static inline void module_assert_mutex (void ) +{ +lockdep_assert_held (&module_mutex); +} + +static inline void module_assert_mutex_or_preempt (void ) +{kernel/module.c static LIST_HEAD(modules); · line 125
Quoted 10 lines
kernel/module.c +10
-0+#ifdef CONFIG_LOCKDEP +int rcu_held =rcu_read_lock_sched_held (); +int mutex_held =1 ; + +if (debug_locks) + mutex_held =lockdep_is_held (&module_mutex); + +WARN_ON (!rcu_held && !mutex_held); +#endif +}Minor nitpick: I generally avoid static inline in C files (unless functions are unused under some config options, which these aren't).
Quoted 2 lines
In general, they mess up future cleanups, as gcc doesn't warn about unused functions.
Ah, sure. And I suppose gcc will not emit code for empty static functions anyhow - which is the reason I stuck the inline on, to avoid it generating code for the !LOCKDEP case.
Re: [RFC][PATCH 2/9] module: Sanitize RCU usage and locking
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
Currently the RCU usage in module is an inconsistent mess of RCU and RCU-sched, this is broken for
CONFIG_PREEMPTwheresynchronize_rcu()does not implysynchronize_sched().Convert everything over to RCU-sched.
Quoted 7 lines
Furthermore add lockdep asserts to all sites, because its not at all clear to me the required locking is observed, esp. on exported functions.
Cc "Paul E. McKenney" <[email protected]>Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Looks good -- just a couple of questions below.
Quoted 79 lines
--- include/linux/module.h | 12 ++++++++++-- kernel/module.c | 42 ++++++++++++++++++++++++++++++++++-------- lib/bug.c | 7 +++++-- 3 files changed, 49 insertions(+), 12 deletions(-)include/linux/module.h +10
-2@@ -415,14 +415,22 @@ struct symsearch {bool unused; }; -/* Search for an exported symbol by name. */ +/* +* Search for an exported symbol by name. +* +* Must be called with module_mutex held or preemption disabled. +*/ const struct kernel_symbol *find_symbol (const char *name,struct module **owner,const unsigned long **crc,bool gplok,bool warn); -/* Walk the exported symbol table */ +/* +* Walk the exported symbol table +* +* Must be called with module_mutex held or preemption disabled. +*/ bool each_symbol_section (bool (*fn)(const struct symsearch *arr,struct module *owner,void *data),void *data);kernel/module.c +22
-0@@ -106,6 +106,24 @@ static LIST_HEAD(modules);struct list_head *kdb_modules = &modules;/* kdb needs the list of modules */ #endif /* CONFIG_KGDB_KDB */ +static inline void module_assert_mutex (void ) +{ +lockdep_assert_held (&module_mutex); +} + +static inline void module_assert_mutex_or_preempt (void ) +{ +#ifdef CONFIG_LOCKDEP +int rcu_held =rcu_read_lock_sched_held (); +int mutex_held =1 ; + +if (debug_locks) + mutex_held =lockdep_is_held (&module_mutex); + +WARN_ON (!rcu_held && !mutex_held); +#endif +} +#ifdef CONFIG_MODULE_SIG #ifdef CONFIG_MODULE_SIG_FORCE static bool sig_enforce = true;@@ -319,6 +337,8 @@ bool each_symbol_section(bool (*fn)(cons#endif }; +module_assert_mutex_or_preempt (); +if (each_symbol_in_section (arr,ARRAY_SIZE (arr),NULL , fn, data))return true;@@ -458,6 +478,8 @@ static struct module *find_module_all(co {struct module *mod; +module_assert_mutex (); +list_for_each_entry (mod, &modules, list) {if (!even_unformed && mod->state ==MODULE_STATE_UNFORMED )continue ;
kernel/module.c static void free_module(struct module *m · line 1883
Quoted 8 lines
kernel/module.c +2
-2@@ -1856,8 +1878,8 @@ static void free_module(struct module *mlist_del_rcu (&mod->list);/* 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. */ -synchronize_rcu (); +/* Wait for RCU-sched synchronizing before releasing mod->list and buglist. */ +synchronize_sched ();mutex_unlock (&module_mutex);
There might be some reasons why the synchronize_sched() needs to be within the module_mutex critical section, but safe freeing of memory and the integrity of the list are not two of them. Doesn't hurt anything unless someone is being very active with their modules, of course.
Quoted 19 lines
kernel/module.c +4
-4/* This may be NULL, but that's OK */ @@ -3106,11 +3128,11 @@ static noinline int do_init_module(struc mod->init_text_size =0 ;/* * We want to free module_init, but be aware that kallsyms may be -* walking this with preempt disabled. In all the failure paths, -* we call synchronize_rcu/synchronize_sched, but we don't want -* to slow down the success path, so use actual RCU here. +* walking this with preempt disabled. In all the failure paths, we +* call synchronize_sched, but we don't want to slow down the success +* path, so use actual RCU here. */ -call_rcu (&freeinit->rcu, do_free_init); +call_rcu_sched (&freeinit->rcu, do_free_init);mutex_unlock (&module_mutex);wake_up_all (&module_wq);
kernel/module.c static int load_module(struct load_info · line 3395
Quoted 8 lines
kernel/module.c +2
-2@@ -3368,8 +3390,8 @@ static int load_module(struct load_info/* Unlink carefully: kallsyms could be walking list. */ list_del_rcu (&mod->list);wake_up_all (&module_wq); -/* Wait for RCU synchronizing before releasing mod->list. */ -synchronize_rcu (); +/* Wait for RCU-sched synchronizing before releasing mod->list. */ +synchronize_sched ();mutex_unlock (&module_mutex);
Same here.
Quoted 59 lines
kernel/module.c +4
-0free_module:/* Free lock-classes; relies on the preceding sync_rcu() */ @@ -3636,6 +3658,8 @@ int module_kallsyms_on_each_symbol(int (unsigned int i;int ret; +module_assert_mutex (); +list_for_each_entry (mod, &modules, list) {if (mod->state ==MODULE_STATE_UNFORMED )continue ;@@ -3810,6 +3834,8 @@ struct module *__module_address(unsignedif (addr < module_addr_min || addr > module_addr_max)return NULL ; +module_assert_mutex_or_preempt (); +list_for_each_entry_rcu (mod, &modules, list) {if (mod->state ==MODULE_STATE_UNFORMED )continue ;lib/bug.c +5
-2@@ -66,7 +66,7 @@ static const struct bug_entry *module_fistruct module *mod;const struct bug_entry *bug =NULL ; -rcu_read_lock (); +rcu_read_lock_sched ();list_for_each_entry_rcu (mod, &module_bug_list, bug_list) {unsigned i;@@ -77,7 +77,7 @@ static const struct bug_entry *module_fi } bug =NULL ; out: -rcu_read_unlock (); +rcu_read_unlock_sched ();return bug; }@@ -88,6 +88,8 @@ void module_bug_finalize(const Elf_Ehdrchar *secstrings;unsigned int i; +lockdep_assert_held (&module_mutex); + mod->bug_table =NULL ; mod->num_bugs =0 ;@@ -113,6 +115,7 @@ void module_bug_finalize(const Elf_Ehdrvoid module_bug_cleanup (struct module *mod) { +lockdep_assert_held (&module_mutex);list_del_rcu (&mod->bug_list); }
Peter Zijlstra
maintainerRe: [RFC][PATCH 2/9] module: Sanitize RCU usage and locking
Quoted 10 lines · Paul E. McKenney
kernel/module.c static void free_module(struct module *m · line 1883
Quoted 5 lines
kernel/module.c +2
-2-/* Wait for RCU synchronizing before releasing mod->list and buglist. */ -synchronize_rcu (); +/* Wait for RCU-sched synchronizing before releasing mod->list and buglist. */ +synchronize_sched ();mutex_unlock (&module_mutex);There might be some reasons why the
synchronize_sched()needs to be within themodule_mutexcritical section, but safe freeing of memory and the integrity of the list are not two of them. Doesn't hurt anything unless someone is being very active with their modules, of course.
Yeah, I could not find anything that relies on that; but I'm not too familiar with all the module stuff -- although a lot more now that I was a few weeks back ;-)
Peter Zijlstra
maintainerRFC PATCH 3/9 module: Annotate module version magic
In reply to Peter ZijlstraDue to the new lockdep checks we go:
[ 9.759380] ------------[ cut here ]------------ [ 9.759389] WARNING: CPU: 31 PID: 597 at ../kernel/module.c:216 each_symbol_section+0x121/0x130() [ 9.759391] Modules linked in: [ 9.759393] CPU: 31 PID: 597 Comm: modprobe Not tainted 4.0.0-rc1+ #65 [ 9.759393] Hardware name: Intel Corporation S2600GZ/S2600GZ, BIOS SE5C600.86B.02.02.0002.122320131210 12/23/2013 [ 9.759396] ffffffff817d8676 ffff880424567ca8 ffffffff8157e98b 0000000000000001 [ 9.759398] 0000000000000000 ffff880424567ce8 ffffffff8105fbc7 ffff880424567cd8 [ 9.759400] 0000000000000000 ffffffff810ec160 ffff880424567d40 0000000000000000 [ 9.759400] Call Trace: [ 9.759407] [<ffffffff8157e98b>] dump_stack+0x4f/0x7b [ 9.759410] [<ffffffff8105fbc7>] warn_slowpath_common+0x97/0xe0 [ 9.759412] [<ffffffff810ec160>] ? section_objs+0x60/0x60 [ 9.759414] [<ffffffff8105fc2a>] warn_slowpath_null+0x1a/0x20 [ 9.759415] [<ffffffff810ed9c1>] each_symbol_section+0x121/0x130 [ 9.759417] [<ffffffff810eda01>] find_symbol+0x31/0x70 [ 9.759420] [<ffffffff810ef5bf>] load_module+0x20f/0x2660 [ 9.759422] [<ffffffff8104ef10>] ? __do_page_fault+0x190/0x4e0 [ 9.759426] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759427] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759433] [<ffffffff810ae73d>] ? trace_hardirqs_on_caller+0x11d/0x1e0 [ 9.759437] [<ffffffff812fcc0e>] ? trace_hardirqs_on_thunk+0x3a/0x3f [ 9.759439] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759441] [<ffffffff810f1ade>] SyS_init_module+0xce/0x100 [ 9.759443] [<ffffffff81587429>] system_call_fastpath+0x12/0x17 [ 9.759445] ---[ end trace 9294429076a9c644 ]---
As per the comment this site should be fine, but lets wrap it in preempt_disable() anyhow to placate lockdep.
--- kernel/module.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-)
kernel/module.c +9 -3
@@ -1192,11 +1192,17 @@ static inline int check_modstruct_versio {const unsigned long *crc; -/* Since this should be found in kernel (which can't be removed), -* no locking is necessary. */ +/* +* Since this should be found in kernel (which can't be removed), +* no locking is necessary. +*/ +preempt_disable ();if (!find_symbol (VMLINUX_SYMBOL_STR (module_layout),NULL , - &crc, true, false)) + &crc, true, false)) { +preempt_enable ();BUG (); + } +preempt_enable ();return check_version (sechdrs, versindex,VMLINUX_SYMBOL_STR (module_layout), mod, crc,NULL );
Re: [RFC][PATCH 3/9] module: Annotate module version magic
Quoted 28 lines · Peter Zijlstra
Due to the new lockdep checks we go:
[ 9.759380] ------------[ cut here ]------------ [ 9.759389] WARNING: CPU: 31 PID: 597 at ../kernel/module.c:216 each_symbol_section+0x121/0x130() [ 9.759391] Modules linked in: [ 9.759393] CPU: 31 PID: 597 Comm: modprobe Not tainted 4.0.0-rc1+ #65 [ 9.759393] Hardware name: Intel Corporation S2600GZ/S2600GZ, BIOS SE5C600.86B.02.02.0002.122320131210 12/23/2013 [ 9.759396] ffffffff817d8676 ffff880424567ca8 ffffffff8157e98b 0000000000000001 [ 9.759398] 0000000000000000 ffff880424567ce8 ffffffff8105fbc7 ffff880424567cd8 [ 9.759400] 0000000000000000 ffffffff810ec160 ffff880424567d40 0000000000000000 [ 9.759400] Call Trace: [ 9.759407] [<ffffffff8157e98b>] dump_stack+0x4f/0x7b [ 9.759410] [<ffffffff8105fbc7>] warn_slowpath_common+0x97/0xe0 [ 9.759412] [<ffffffff810ec160>] ? section_objs+0x60/0x60 [ 9.759414] [<ffffffff8105fc2a>] warn_slowpath_null+0x1a/0x20 [ 9.759415] [<ffffffff810ed9c1>] each_symbol_section+0x121/0x130 [ 9.759417] [<ffffffff810eda01>] find_symbol+0x31/0x70 [ 9.759420] [<ffffffff810ef5bf>] load_module+0x20f/0x2660 [ 9.759422] [<ffffffff8104ef10>] ? __do_page_fault+0x190/0x4e0 [ 9.759426] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759427] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759433] [<ffffffff810ae73d>] ? trace_hardirqs_on_caller+0x11d/0x1e0 [ 9.759437] [<ffffffff812fcc0e>] ? trace_hardirqs_on_thunk+0x3a/0x3f [ 9.759439] [<ffffffff815880ec>] ? retint_restore_args+0x13/0x13 [ 9.759441] [<ffffffff810f1ade>] SyS_init_module+0xce/0x100 [ 9.759443] [<ffffffff81587429>] system_call_fastpath+0x12/0x17 [ 9.759445] ---[ end trace 9294429076a9c644 ]---
Quoted 5 lines
As per the comment this site should be fine, but lets wrap it in
preempt_disable()anyhow to placate lockdep.Cc Rusty Russell <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 29 lines
--- kernel/module.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-)kernel/module.c +9
-3@@ -1192,11 +1192,17 @@ static inline int check_modstruct_versio {const unsigned long *crc; -/* Since this should be found in kernel (which can't be removed), -* no locking is necessary. */ +/* +* Since this should be found in kernel (which can't be removed), +* no locking is necessary. +*/ +preempt_disable ();if (!find_symbol (VMLINUX_SYMBOL_STR (module_layout),NULL , - &crc, true, false)) + &crc, true, false)) { +preempt_enable ();BUG (); + } +preempt_enable ();return check_version (sechdrs, versindex,VMLINUX_SYMBOL_STR (module_layout), mod, crc,NULL );
Peter Zijlstra
maintainerRFC PATCH 4/9 module, jump_label: Fix module locking
In reply to Peter ZijlstraAs per the module core lockdep annotations:
[ 18.034047] ---[ end trace 9294429076a9c673 ]--- [ 18.047760] Hardware name: Intel Corporation S2600GZ/S2600GZ, BIOS SE5C600.86B.02.02.0002.122320131210 12/23/2013 [ 18.059228] ffffffff817d8676 ffff880036683c38 ffffffff8157e98b 0000000000000001 [ 18.067541] 0000000000000000 ffff880036683c78 ffffffff8105fbc7 ffff880036683c68 [ 18.075851] ffffffffa0046b08 0000000000000000 ffffffffa0046d00 ffffffffa0046cc8 [ 18.084173] Call Trace: [ 18.086906] [<ffffffff8157e98b>] dump_stack+0x4f/0x7b [ 18.092649] [<ffffffff8105fbc7>] warn_slowpath_common+0x97/0xe0 [ 18.099361] [<ffffffff8105fc2a>] warn_slowpath_null+0x1a/0x20 [ 18.105880] [<ffffffff810ee502>] __module_address+0x1d2/0x1e0 [ 18.112400] [<ffffffff81161153>] jump_label_module_notify+0x143/0x1e0 [ 18.119710] [<ffffffff810814bf>] notifier_call_chain+0x4f/0x70 [ 18.126326] [<ffffffff8108160e>] __blocking_notifier_call_chain+0x5e/0x90 [ 18.134009] [<ffffffff81081656>] blocking_notifier_call_chain+0x16/0x20 [ 18.141490] [<ffffffff810f0f00>] load_module+0x1b50/0x2660 [ 18.147720] [<ffffffff810f1ade>] SyS_init_module+0xce/0x100 [ 18.154045] [<ffffffff81587429>] system_call_fastpath+0x12/0x17 [ 18.160748] ---[ end trace 9294429076a9c674 ]---
Jump labels is not doing it right; fix this.
--- kernel/jump_label.c | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-)
kernel/jump_label.c +17 -4
@@ -280,6 +280,17 @@ void jump_label_apply_nops(struct module } } +static inline bool address_in_module (unsigned long addr,struct module *mod) +{ +bool ret; + +preempt_disable (); + ret =__module_address (addr) == mod; +preempt_enable (); + +return ret; +} +static int jump_label_add_module (struct module *mod) {struct jump_entry *iter_start = mod->jump_entries;
@@ -302,7 +313,7 @@ static int jump_label_add_module(structcontinue ; key = iterk; -if (__module_address (iter->key) == mod) { +if (address_in_module (iter->key, mod)) {/* * Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH. */
@@ -339,7 +350,7 @@ static void jump_label_del_module(struct key = (struct static_key *)(unsigned long )iter->key; -if (__module_address (iter->key) == mod) +if (address_in_module (iter->key, mod))continue ; prev = &key->next;
@@ -443,14 +454,16 @@ static void jump_label_update(struct sta {struct jump_entry *stop = __stop___jump_table;struct jump_entry *entry =jump_label_get_entries (key); -#ifdef CONFIG_MODULES -struct module *mod =__module_address ((unsigned long )key); +struct module *mod;__jump_label_mod_update (key, enable); +preempt_disable (); + mod =__module_address ((unsigned long )key);if (mod) stop = mod->jump_entries + mod->num_jump_entries; +preempt_enable ();#endif /* if there are no users, entry can be NULL */ if (entry)
Re: [RFC][PATCH 4/9] module, jump_label: Fix module locking
Quoted 21 lines · Peter Zijlstra
As per the module core lockdep annotations:
[ 18.034047] ---[ end trace 9294429076a9c673 ]--- [ 18.047760] Hardware name: Intel Corporation S2600GZ/S2600GZ, BIOS SE5C600.86B.02.02.0002.122320131210 12/23/2013 [ 18.059228] ffffffff817d8676 ffff880036683c38 ffffffff8157e98b 0000000000000001 [ 18.067541] 0000000000000000 ffff880036683c78 ffffffff8105fbc7 ffff880036683c68 [ 18.075851] ffffffffa0046b08 0000000000000000 ffffffffa0046d00 ffffffffa0046cc8 [ 18.084173] Call Trace: [ 18.086906] [<ffffffff8157e98b>] dump_stack+0x4f/0x7b [ 18.092649] [<ffffffff8105fbc7>] warn_slowpath_common+0x97/0xe0 [ 18.099361] [<ffffffff8105fc2a>] warn_slowpath_null+0x1a/0x20 [ 18.105880] [<ffffffff810ee502>] __module_address+0x1d2/0x1e0 [ 18.112400] [<ffffffff81161153>] jump_label_module_notify+0x143/0x1e0 [ 18.119710] [<ffffffff810814bf>] notifier_call_chain+0x4f/0x70 [ 18.126326] [<ffffffff8108160e>] __blocking_notifier_call_chain+0x5e/0x90 [ 18.134009] [<ffffffff81081656>] blocking_notifier_call_chain+0x16/0x20 [ 18.141490] [<ffffffff810f0f00>] load_module+0x1b50/0x2660 [ 18.147720] [<ffffffff810f1ade>] SyS_init_module+0xce/0x100 [ 18.154045] [<ffffffff81587429>] system_call_fastpath+0x12/0x17 [ 18.160748] ---[ end trace 9294429076a9c674 ]---
Quoted 5 lines
Jump labels is not doing it right; fix this.
Cc Rusty Russell <[email protected]>Cc Jason Baron <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 63 lines
--- kernel/jump_label.c | 21 +++++++++++++++++---- 1 file changed, 17 insertions(+), 4 deletions(-)kernel/jump_label.c +17
-4@@ -280,6 +280,17 @@ void jump_label_apply_nops(struct module } } +static inline bool address_in_module (unsigned long addr,struct module *mod) +{ +bool ret; + +preempt_disable (); + ret =__module_address (addr) == mod; +preempt_enable (); + +return ret; +} +static int jump_label_add_module (struct module *mod) {struct jump_entry *iter_start = mod->jump_entries;@@ -302,7 +313,7 @@ static int jump_label_add_module(structcontinue ; key = iterk; -if (__module_address (iter->key) == mod) { +if (address_in_module (iter->key, mod)) {/* * Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH. */ @@ -339,7 +350,7 @@ static void jump_label_del_module(struct key = (struct static_key *)(unsigned long )iter->key; -if (__module_address (iter->key) == mod) +if (address_in_module (iter->key, mod))continue ; prev = &key->next;@@ -443,14 +454,16 @@ static void jump_label_update(struct sta {struct jump_entry *stop = __stop___jump_table;struct jump_entry *entry =jump_label_get_entries (key); -#ifdef CONFIG_MODULES -struct module *mod =__module_address ((unsigned long )key); +struct module *mod;__jump_label_mod_update (key, enable); +preempt_disable (); + mod =__module_address ((unsigned long )key);if (mod) stop = mod->jump_entries + mod->num_jump_entries; +preempt_enable ();#endif /* if there are no users, entry can be NULL */ if (entry)
Peter Zijlstra
maintainerRFC PATCH 5/9 rbtree: Make lockless searches non-fatal
In reply to Peter ZijlstraChange the insert and erase code such that lockless searches are non-fatal.
In and of itself an rbtree cannot be correctly searched while in-modification, we can however provide weaker guarantees that will allow the rbtree to be used in conjunction with other techniques, such as latches; see 9b0fd802e8c0 ("seqcount: Add raw_write_seqcount_latch()").
For this to work we need the following guarantees from the rbtree code:
1) a lockless reader must not see partial stores, this would allow it to observe nodes that are invalid memory.
2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.
For 1) we must use WRITE_ONCE() for all updates to the tree structure; in particular this patch only does rb_{left,right} as those are the only element required for simple searches.
It generates slightly worse code, probably because gcc stinks at volatile. But in pointer chasing heavy code a few instructions more should not matter.
For 2) I have carefully audited the code and drawn every intermediate link state and not found a loop.
--- 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 <linux/rcupdate.h> struct rb_node {unsigned long __rb_parent_color;
@@ -85,6 +86,15 @@ static inline void rb_link_node(struct r *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 ; + +rcu_assign_pointer (*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, s {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 *nod 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 *nod*/ parent = successor; child2 = successor->rb_right; + augment->copy (node, successor); }else {/*
@@ -201,19 +204,23 @@ __rb_erase_augmented(struct rb_node *nod 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 5/9] rbtree: Make lockless searches non-fatal
----- Original Message -----
Quoted 20 lines
From: "Peter Zijlstra" <[email protected]>
To: [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], "Michel Lespinasse" <[email protected]>, "Andrea Arcangeli" <[email protected]>, "David Woodhouse" <[email protected]>, "Rik van Riel" <[email protected]>
Sent: Saturday, February 28, 2015 4:24:52 PM
Subject: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatalChange the insert and erase code such that lockless searches are non-fatal.
In and of itself an rbtree cannot be correctly searched while in-modification, we can however provide weaker guarantees that will allow the rbtree to be used in conjunction with other techniques, such as latches; see
9b0fd802e8c0("seqcount: Addraw_write_seqcount_latch()").For this to work we need the following guarantees from the rbtree code:
Quoted 6 lines
1) a lockless reader must not see partial stores, this would allow it to observe nodes that are invalid memory.
2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.
For (2), I don't think this is how the situation should be described.
Let's consider a scenario where an interrupt nests over the modification. First, the modification will switch the latch to the other version of the tree. Therefore, the interrupt will see a fully consistent tree, not the tree being modified. Therefore, a temporary loop in the tree should not be an issue for that peculiar situation.
However, if we have another thread traversing the tree while we concurrently switch the latch and modify one version of the tree, creating a temporary loop in the tree, this thread could possibly:
A) deadlock with the modification if there is a locking dependency between tree modification, tree read, and another lock (transitive dependency).
B) have the modifier starved by the other thread, if that thread has a higher scheduling priority (e.g. RT) than the modifier. The high priority thread would then use all its CPU time to perform the temporary loop.
So I agree that loops are unwanted there: it allows us to never have to care about situations A and B. However, the explanation about why should not involve, AFAIU, an interrupt handler nesting over the tree modification, because this is precisely one scenario that should not care about loops.
Thoughs ?
Thanks!
Mathieu
Quoted 281 lines
For 1) we must use
WRITE_ONCE()for all updates to the tree structure; in particular this patch only does rb_{left,right} as those are the only element required for simple searches.It generates slightly worse code, probably because gcc stinks at volatile. But in pointer chasing heavy code a few instructions more should not matter.
For 2) I have carefully audited the code and drawn every intermediate link state and not found a loop.
Cc Oleg Nesterov <[email protected]>Cc Michel Lespinasse <[email protected]>Cc Andrea Arcangeli <[email protected]>Cc David Woodhouse <[email protected]>Cc Rik van Riel <[email protected]>Cc Mathieu Desnoyers <[email protected]>Cc "Paul E. McKenney" <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- include/linux/rbtree.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 <linux/rcupdate.h> struct rb_node {unsigned long __rb_parent_color;@@ -85,6 +86,15 @@ static inline void rb_link_node(struct r *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 ; + +rcu_assign_pointer (*rb_link, node); +} +#define rb_entry_safe (ptr, type, member) \ ({ typeof(ptr) ____ptr = (ptr); \include/linux/rbtree.h +0
-0____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, s {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 *nod 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 *nod*/ parent = successor; child2 = successor->rb_right; + augment->copy (node, successor); }else {/* @@ -201,19 +204,23 @@ __rb_erase_augmented(struct rb_node *nod 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 +2
-0@@ -44,6 +44,25 @@* parentheses and have some accompanying text comment. */ +/* +* All stores to the tree structure (rb_left and rb_right) must be done using
+ *WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
+ * tree structure as seen in program order.
+ *
+ * These two requirements will allow lockless iteration of the tree -- not
+ * correct iteration mind you, tree rotations are not atomic so a lookup might
+ * miss entire subtrees.
+ *
+ * But they do guarantee that any such traversal will only see valid elements
+ * and that it will indeed complete -- does not get stuck in a loop.
+ *
+ * NOTE:
+ *
+ * Stores to__rb_parent_colorare not important for simple lookups so those
+ * are left undone as of now. Nor did I check for loops involving parent
+ * pointers.
+ */lib/rbtree.c +31
-22+static inline void rb_set_black (struct rb_node *rb) { rb->__rb_parent_color |=RB_BLACK ;@@ -129,8 +148,9 @@ __rb_insert(struct rb_node *node, struct* This still leaves us in violation of 4), the * continuation into Case 3 will fix that. */ - parent->rb_right = tmp = node->rb_left; - node->rb_left = parent; + tmp = node->rb_left; +WRITE_ONCE (parent->rb_right, tmp); +WRITE_ONCE (node->rb_left, parent);if (tmp)rb_set_parent_color (tmp, parent,RB_BLACK );@@ -149,8 +169,8 @@ __rb_insert(struct rb_node *node, struct* / \ * n U */ - gparent->rb_left = tmp;/* == parent->rb_right */ - parent->rb_right = gparent; +WRITE_ONCE (gparent->rb_left, tmp);/* == parent->rb_right */ +WRITE_ONCE (parent->rb_right, gparent);if (tmp)rb_set_parent_color (tmp, gparent,RB_BLACK );__rb_rotate_set_parents (gparent, parent, root,RB_RED );@@ -171,8 +191,9 @@ __rb_insert(struct rb_node *node, struct tmp = parent->rb_left;if (node == tmp) {/* Case 2 - right rotate at parent */ - parent->rb_left = tmp = node->rb_right; - node->rb_right = parent; + tmp = node->rb_right; +WRITE_ONCE (parent->rb_left, tmp); +WRITE_ONCE (node->rb_right, parent);if (tmp)rb_set_parent_color (tmp, parent,RB_BLACK );@@ -183,8 +204,8 @@ __rb_insert(struct rb_node *node, struct }/* Case 3 - left rotate at gparent */ - gparent->rb_right = tmp;/* == parent->rb_left */ - parent->rb_left = gparent; +WRITE_ONCE (gparent->rb_right, tmp);/* == parent->rb_left */ +WRITE_ONCE (parent->rb_left, gparent);if (tmp)rb_set_parent_color (tmp, gparent,RB_BLACK );__rb_rotate_set_parents (gparent, parent, root,RB_RED );@@ -224,8 +245,9 @@ ____rb_erase_color(struct rb_node *paren* / \ / \ * Sl Sr N Sl */ - parent->rb_right = tmp1 = sibling->rb_left; - sibling->rb_left = parent; + tmp1 = sibling->rb_left; +WRITE_ONCE (parent->rb_right, tmp1); +WRITE_ONCE (sibling->rb_left, parent);rb_set_parent_color (tmp1, parent,RB_BLACK );__rb_rotate_set_parents (parent, sibling, root,RB_RED );@@ -275,9 +297,10 @@ ____rb_erase_color(struct rb_node *paren* \ * Sr */ - sibling->rb_left = tmp1 = tmp2->rb_right; - tmp2->rb_right = sibling; - parent->rb_right = tmp2; + tmp1 = tmp2->rb_right; +WRITE_ONCE (sibling->rb_left, tmp1); +WRITE_ONCE (tmp2->rb_right, sibling); +WRITE_ONCE (parent->rb_right, tmp2);if (tmp1)rb_set_parent_color (tmp1, sibling,RB_BLACK );@@ -297,8 +320,9 @@ ____rb_erase_color(struct rb_node *paren* / \ / \ * (sl) sr N (sl) */ - parent->rb_right = tmp2 = sibling->rb_left; - sibling->rb_left = parent; + tmp2 = sibling->rb_left; +WRITE_ONCE (parent->rb_right, tmp2); +WRITE_ONCE (sibling->rb_left, parent);rb_set_parent_color (tmp1, sibling,RB_BLACK );if (tmp2)rb_set_parent (tmp2, parent);@@ -310,8 +334,9 @@ ____rb_erase_color(struct rb_node *paren sibling = parent->rb_left;if (rb_is_red (sibling)) {/* Case 1 - right rotate at parent */ - parent->rb_left = tmp1 = sibling->rb_right; - sibling->rb_right = parent; + tmp1 = sibling->rb_right; +WRITE_ONCE (parent->rb_left, tmp1); +WRITE_ONCE (sibling->rb_right, parent);rb_set_parent_color (tmp1, parent,RB_BLACK );__rb_rotate_set_parents (parent, sibling, root,RB_RED );@@ -336,9 +361,10 @@ ____rb_erase_color(struct rb_node *parenbreak ; }/* Case 3 - right rotate at sibling */ - sibling->rb_right = tmp1 = tmp2->rb_left; - tmp2->rb_left = sibling; - parent->rb_left = tmp2; + tmp1 = tmp2->rb_left; +WRITE_ONCE (sibling->rb_right, tmp1); +WRITE_ONCE (tmp2->rb_left, sibling); +WRITE_ONCE (parent->rb_left, tmp2);if (tmp1)rb_set_parent_color (tmp1, sibling,RB_BLACK );@@ -347,8 +373,9 @@ ____rb_erase_color(struct rb_node *paren sibling = tmp2; }/* Case 4 - left rotate at parent + color flips */ - parent->rb_left = tmp2 = sibling->rb_right; - sibling->rb_right = parent; + tmp2 = sibling->rb_right; +WRITE_ONCE (parent->rb_left, tmp2); +WRITE_ONCE (sibling->rb_right, parent);rb_set_parent_color (tmp1, sibling,RB_BLACK );if (tmp2)rb_set_parent (tmp2, parent);
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
Quoted 24 lines · Mathieu Desnoyers
Quoted 3 lines
2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.
For (2), I don't think this is how the situation should be described.
Let's consider a scenario where an interrupt nests over the modification. First, the modification will switch the latch to the other version of the tree. Therefore, the interrupt will see a fully consistent tree, not the tree being modified. Therefore, a temporary loop in the tree should not be an issue for that peculiar situation.
However, if we have another thread traversing the tree while we concurrently switch the latch and modify one version of the tree, creating a temporary loop in the tree, this thread could possibly:
A) deadlock with the modification if there is a locking dependency between tree modification, tree read, and another lock (transitive dependency).
B) have the modifier starved by the other thread, if that thread has a higher scheduling priority (e.g. RT) than the modifier. The high priority thread would then use all its CPU time to perform the temporary loop.
Quoted 7 lines
So I agree that loops are unwanted there: it allows us to never have to care about situations A and B. However, the explanation about why should not involve, AFAIU, an interrupt handler nesting over the tree modification, because this is precisely one scenario that should not care about loops.
Thoughs ?
This is true for the (later) proposed latched RB-tree, the description is however true in general. If you somehow did a lookup while doing the modification and you have loops in program order, you're stuck.
So in the interest of robustness I think we want this property nonetheless. And its 'free', I didn't have to change any code for this.
I shall however clarify this point in the latched RB-tree patch.
Re: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
In reply to Peter ZijlstraQuoted 18 lines · Peter Zijlstra
Change the insert and erase code such that lockless searches are non-fatal.
In and of itself an rbtree cannot be correctly searched while in-modification, we can however provide weaker guarantees that will allow the rbtree to be used in conjunction with other techniques, such as latches; see
9b0fd802e8c0("seqcount: Addraw_write_seqcount_latch()").For this to work we need the following guarantees from the rbtree code:
1) a lockless reader must not see partial stores, this would allow it to observe nodes that are invalid memory.
2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.
Quoted 7 lines
For 1) we must use
WRITE_ONCE()for all updates to the tree structure; in particular this patch only does rb_{left,right} as those are the only element required for simple searches.It generates slightly worse code, probably because gcc stinks at volatile. But in pointer chasing heavy code a few instructions more should not matter.
So, I was worried that this would penalize all rbtree users, for the benefit of just the one you're adding later in this series. We have several rbtrees where we care about performance a lot, such as the ones used in the scheduler or for indexing vmas.
That said, I checked with the compiler we are using here (gcc 4.7 variant) and I didn't see any change in the generated code. So, no issue here for me.
If the object code really is different in your setup, please use the lib/rbtree_test module to check the performance impact of the change.
Quoted 2 lines
For 2) I have carefully audited the code and drawn every intermediate link state and not found a loop.
As Mathieu remarked, we are never modifying the currently active tree, so the interrupt case is not the reason for avoiding loops.
I think your proposal will work well for the use case you have in mind (looking up modules based on address). However, I was wondering how you would compare your proposal against an alternative I hard Josh Triplett formulate before, where there would be one unique rbtree but rotations would allocate new nodes rather than modify the existing ones. I think this would be workable as well; I'm just not sure whether this would be more or less generally applicable than your proposal. Copying Josh in case he wants to chime in.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
Quoted 27 lines · Michel Lespinasse
Quoted 18 lines · Peter Zijlstra
Change the insert and erase code such that lockless searches are non-fatal.
In and of itself an rbtree cannot be correctly searched while in-modification, we can however provide weaker guarantees that will allow the rbtree to be used in conjunction with other techniques, such as latches; see
9b0fd802e8c0("seqcount: Addraw_write_seqcount_latch()").For this to work we need the following guarantees from the rbtree code:
1) a lockless reader must not see partial stores, this would allow it to observe nodes that are invalid memory.
2) there must not be (temporary) loops in the tree structure in the modifier's program order, this would cause a lookup which interrupts the modifier to get stuck indefinitely.
Quoted 7 lines
For 1) we must use
WRITE_ONCE()for all updates to the tree structure; in particular this patch only does rb_{left,right} as those are the only element required for simple searches.It generates slightly worse code, probably because gcc stinks at volatile. But in pointer chasing heavy code a few instructions more should not matter.
Quoted 8 lines
So, I was worried that this would penalize all rbtree users, for the benefit of just the one you're adding later in this series. We have several rbtrees where we care about performance a lot, such as the ones used in the scheduler or for indexing vmas.
That said, I checked with the compiler we are using here (gcc 4.7 variant) and I didn't see any change in the generated code. So, no issue here for me.
Yeah, I had that worry too. With gcc 4.9.1 on x86-64 defconfig I get this comparison:
lib/rbtree.o:
text data bss dec hex filename 3299 0 0 3299 ce3 rbtree.o.before 3308 0 0 3308 cec rbtree.o.after
+9 bytes.
Most of the difference seems minimal, involves an extra register move saving addresses in registers and using them there:
449: 4c 8b 60 10 mov 0x10(%rax),%r12 - 44d: 49 39 fc cmp %rdi,%r12 - 450: 0f 84 aa 00 00 00 je 500 <__rb_insert_augmented+0x1a0> - 456: 49 89 c6 mov %rax,%r14 - 459: 4d 85 e4 test %r12,%r12 - 45c: 4c 89 63 08 mov %r12,0x8(%rbx) - 460: 48 89 58 10 mov %rbx,0x10(%rax) - 464: 74 0b je 471 <__rb_insert_augmented+0x111>
449: 4c 8b 60 10 mov 0x10(%rax),%r12 + 44d: 48 89 c6 mov %rax,%rsi + 450: 49 39 fc cmp %rdi,%r12 + 453: 0f 84 97 00 00 00 je 4f0 <__rb_insert_augmented+0x190> + 459: 49 89 c6 mov %rax,%r14 + 45c: 4d 85 e4 test %r12,%r12 + 45f: 4c 89 63 08 mov %r12,0x8(%rbx) + 463: 48 89 5e 10 mov %rbx,0x10(%rsi) + 467: 74 0b je 474 <__rb_insert_augmented+0x114>
So here instead of using 0x10(%rax) again, GCC moved %rax into %rsi and used 0x10(%rsi). That seems to be plain compiler stupidity (that move to %rsi is senseless with or without volatile), and gcc might improve in the future.
In my (admittedly quick) comparison I saw no serious changes like extra memory loads or stack spills.
Thanks,
Ingo
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
In reply to Michel LespinasseQuoted 11 lines · Michel Lespinasse
Quoted 3 lines · Peter Zijlstra
It generates slightly worse code, probably because gcc stinks at volatile. But in pointer chasing heavy code a few instructions more should not matter.
So, I was worried that this would penalize all rbtree users, for the benefit of just the one you're adding later in this series. We have several rbtrees where we care about performance a lot, such as the ones used in the scheduler or for indexing vmas.
Quoted 6 lines
That said, I checked with the compiler we are using here (gcc 4.7 variant) and I didn't see any change in the generated code. So, no issue here for me.
If the object code really is different in your setup, please use the
lib/rbtree_testmodule to check the performance impact of the change.
I can do that; I had similar results to what Ingo posted. I meant to go build a 4.9 or 5.0 compiler to see what current GCC makes of it, but I've not yet gotten around to doing so.
My result were with 4.8.3 iirc.
Quoted 5 lines
Quoted 2 lines
For 2) I have carefully audited the code and drawn every intermediate link state and not found a loop.
As Mathieu remarked, we are never modifying the currently active tree, so the interrupt case is not the reason for avoiding loops.
Correct, for the proposed use we do no. I did however double (actually triple) check this property because I feel its a good property to have, no matter what you do to the tree, a (simple) lookup will be non-fatal.
But yes, I'll clarify things.
Quoted 8 lines
I think your proposal will work well for the use case you have in mind (looking up modules based on address). However, I was wondering how you would compare your proposal against an alternative I hard Josh Triplett formulate before, where there would be one unique rbtree but rotations would allocate new nodes rather than modify the existing ones. I think this would be workable as well; I'm just not sure whether this would be more or less generally applicable than your proposal. Copying Josh in case he wants to chime in.
So I was not aware of that particular solution.
It changes the rb-tree from using internal storage like we do now, to requiring external storage.
I do have experience with making an RCU safe (in memory) B+tree, and there the allocations were absolutely killing performance.
Peter Zijlstra
maintainerRe: [RFC][PATCH 5/9] rbtree: Make lockless searches non-fatal
Quoted 2 lines · Peter Zijlstra
It changes the rb-tree from using internal storage like we do now, to requiring external storage.
Note that one consequence of using external storage is that tree iteration will always require two cachelines per level. One to load the node and one to load the search key.
Peter Zijlstra
maintainerRFC PATCH 6/9 seqlock: Better document raw_write_seqcount_latch()
In reply to Peter ZijlstraImprove the documentation of the latch technique as used in the current timekeeping code, such that it can be readily employed elsewhere.
Borrow from the comments in timekeeping and replace those with a reference to this more generic comment.
--- include/linux/seqlock.h | 74 +++++++++++++++++++++++++++++++++++++++++++++- kernel/time/timekeeping.c | 27 ---------------- 2 files changed, 74 insertions(+), 27 deletions(-)
include/linux/seqlock.h +73 -1
@@ -233,9 +233,81 @@ static inline void raw_write_seqcount_en s->sequence++; } -/* +/** * raw_write_seqcount_latch - redirect readers to even/odd copy * @s: pointer to seqcount_t +* +* The latch technique is a multiversion concurrency control method that allows +* queries during non atomic modifications. If you can guarantee queries never +* interrupt the modification -- e.g. the concurrency is strictly between CPUs +* -- you most likely do not need this. +* +* Where the traditional RCU/lockless data structures rely on atomic +* modifications to ensure queries observe either the old or the new state the +* latch allows the same for non atomic updates. The trade-off is doubling the +* cost of storage; we have to maintain two copies of the entire data +* structure. +* +* Very simply put: we first modify one copy and then the other. This ensures +* there is always one copy in a stable state, ready to give us an answer. +* +* 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]. +* +* NOTE: The non-requirement for atomic modifications does _NOT_ include +* the publishing of new entries in the case where data is a dynamic +* data structure. +* +* An iteration might start in data[0] and get suspended long enough +* to miss an entire modification sequence, once it resumes it might +* observe the new entry. */ static inline void raw_write_seqcount_latch (seqcount_t *s) {
kernel/time/timekeeping.c +1 -26
@@ -235,32 +235,7 @@ static inline s64 timekeeping_get_ns_raw* We want to use this from any context including NMI and tracing / * instrumenting the timekeeping code itself. * -* So we handle this differently than the other timekeeping accessor -* functions which retry when the sequence count has changed. The -* update side does: -* -* smp_wmb(); <- Ensure that the last base[1] update is visible -* tkf->seq++; -* smp_wmb(); <- Ensure that the seqcount update is visible -* update(tkf->base[0], tkr); -* smp_wmb(); <- Ensure that the base[0] update is visible -* tkf->seq++; -* smp_wmb(); <- Ensure that the seqcount update is visible -* update(tkf->base[1], tkr); -* -* The reader side does: -* -* do { -* seq = tkf->seq; -* smp_rmb(); -* idx = seq & 0x01; -* now = now(tkf->base[idx]); -* smp_rmb(); -* } while (seq != tkf->seq) -* -* As long as we update base[0] readers are forced off to -* base[1]. Once base[0] is updated readers are redirected to base[0] -* and the base[1] update takes place. +* Employ the latch technique; see @raw_write_seqcount_latch. * * So if a NMI hits the update of base[0] then it will use base[1] * which is still consistent. In the worst case this can result is a
Re: [RFC][PATCH 6/9] seqlock: Better document raw_write_seqcount_latch()
----- Original Message -----
Quoted 118 lines
From: "Peter Zijlstra" <[email protected]>
To: [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], "Michel Lespinasse" <[email protected]>, "Andrea Arcangeli" <[email protected]>, "David Woodhouse" <[email protected]>, "Rik van Riel" <[email protected]>
Sent: Saturday, February 28, 2015 4:24:53 PM
Subject: [RFC][PATCH 6/9] seqlock: Better documentraw_write_seqcount_latch()Improve the documentation of the latch technique as used in the current timekeeping code, such that it can be readily employed elsewhere.
Borrow from the comments in timekeeping and replace those with a reference to this more generic comment.
Cc Oleg Nesterov <[email protected]>Cc Michel Lespinasse <[email protected]>Cc Andrea Arcangeli <[email protected]>Cc David Woodhouse <[email protected]>Cc Rik van Riel <[email protected]>Cc Mathieu Desnoyers <[email protected]>Cc "Paul E. McKenney" <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- include/linux/seqlock.h | 74 +++++++++++++++++++++++++++++++++++++++++++++- kernel/time/timekeeping.c | 27 ---------------- 2 files changed, 74 insertions(+), 27 deletions(-)include/linux/seqlock.h +3
-1@@ -233,9 +233,81 @@ static inline void raw_write_seqcount_en s->sequence++; } -/* +/** * raw_write_seqcount_latch - redirect readers to even/odd copy * @s: pointer to seqcount_t +* +* The latch technique is a multiversion concurrency control method that allows
+ * queries during non atomic modifications. If you can guarantee queries never
+ * interrupt the modification -- e.g. the concurrency is strictly between CPUs
+ * -- you most likely do not need this.
+ *
+ * Where the traditional RCU/lockless data structures rely on atomic
+ * modifications to ensure queries observe either the old or the new state the
+ * latch allows the same for non atomic updates. The trade-off is doubling the
+ * cost of storage; we have to maintain two copies of the entire data
+ * structure.
+ *
+ * Very simply put: we first modify one copy and then the other. This ensures
+ * there is always one copy in a stable state, ready to give us an answer.
+ *
+ * The basic form is a data structure like:
+ *
+ * structlatch_struct{
+ *seqcount_tseq;
+ * structdata_structdata[2];
+ * };
+ *
+ * Where a modification, which is assumed to be externally serialized, does the
+ * following:
+ *
+ * voidlatch_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(structlatch_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].
+ *
+ * NOTE: The non-requirement for atomic modifications does _NOT_ include
+ * the publishing of new entries in the case where data is a dynamic
+ * data structure.
+ *
Quoted 3 lines
+ * An iteration might start in data[0] and get suspended long enough + * to miss an entire modification sequence, once it resumes it might + * observe the new entry.
We might want to hint that in the case of dynamic data structures, RCU read-side C.S. and grace period should be used together with the latch to handle the object teardown.
The latch, AFAIU, takes care of making sure the new objects are initialized before being published into the data structure, so there would be no need to use RCU assign pointer. However, we really need RCU around reads, along with a grace period between removal of an object and its teardown.
Thanks,
Mathieu
Quoted 42 lines
*/
static inline voidraw_write_seqcount_latch(seqcount_t *s){kernel/time/timekeeping.c +1
-26@@ -235,32 +235,7 @@ static inline s64 timekeeping_get_ns_raw* We want to use this from any context including NMI and tracing / * instrumenting the timekeeping code itself. * -* So we handle this differently than the other timekeeping accessor -* functions which retry when the sequence count has changed. The -* update side does: -* -* smp_wmb(); <- Ensure that the last base[1] update is visible -* tkf->seq++; -* smp_wmb(); <- Ensure that the seqcount update is visible -* update(tkf->base[0], tkr); -* smp_wmb(); <- Ensure that the base[0] update is visible -* tkf->seq++; -* smp_wmb(); <- Ensure that the seqcount update is visible -* update(tkf->base[1], tkr); -* -* The reader side does: -* -* do { -* seq = tkf->seq; -* smp_rmb(); -* idx = seq & 0x01; -* now = now(tkf->base[idx]); -* smp_rmb(); -* } while (seq != tkf->seq) -* -* As long as we update base[0] readers are forced off to -* base[1]. Once base[0] is updated readers are redirected to base[0] -* and the base[1] update takes place. +* Employ the latch technique; see @raw_write_seqcount_latch. * * So if a NMI hits the update of base[0] then it will use base[1] * which is still consistent. In the worst case this can result is a
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Peter Zijlstra
maintainerRe: [RFC][PATCH 6/9] seqlock: Better document raw_write_seqcount_latch()
Quoted 12 lines · Mathieu Desnoyers
Quoted 11 lines
+ * 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].
+ *
+ * NOTE: The non-requirement for atomic modifications does _NOT_ include
+ * the publishing of new entries in the case where data is a dynamic
+ * data structure.
+ *+ * An iteration might start in data[0] and get suspended long enough + * to miss an entire modification sequence, once it resumes it might + * observe the new entry.
Quoted 3 lines
We might want to hint that in the case of dynamic data structures, RCU read-side
C.S. and grace period should be used together with the latch to handle the object teardown.
Can do.
Quoted 5 lines
The latch, AFAIU, takes care of making sure the new objects are initialized before being published into the data structure, so there would be no need to use RCU assign pointer. However, we really need RCU around reads, along with a grace period between removal of an object and its teardown.
So I do need the rcu_assign_pointer for the RB link because that also initializes the rb_node itself. Or put differently, be _very_ _VERY_ sure your entire object is initialized before the latch.
Secondly, note that the latch does a WMB and rcu_assign_pointer does a RELEASE, these are not equivalent.
So I don't think I will highlight this particular point. If you're sure enough to know the difference you can get away with it, sure. But in general I think people should still use rcu_assign_pointer; if only to make Paul sleep better at night ;-)
Peter Zijlstra
maintainerRe: [RFC][PATCH 6/9] seqlock: Better document raw_write_seqcount_latch()
Quoted 12 lines · Peter Zijlstra
Quoted 5 lines · Mathieu Desnoyers
The latch, AFAIU, takes care of making sure the new objects are initialized before being published into the data structure, so there would be no need to use RCU assign pointer. However, we really need RCU around reads, along with a grace period between removal of an object and its teardown.
So I do need the
rcu_assign_pointerfor the RB link because that also initializes therb_nodeitself. Or put differently, be _very_ _VERY_ sure your entire object is initialized before the latch.
Quoted 7 lines
Secondly, note that the latch does a WMB and
rcu_assign_pointerdoes a RELEASE, these are not equivalent.So I don't think I will highlight this particular point. If you're sure enough to know the difference you can get away with it, sure. But in general I think people should still use
rcu_assign_pointer; if only to make Paul sleep better at night ;-)
Also note that if you do not use rcu_assign_pointer() one will at the very least require WRITE_ONCE().
Re: [RFC][PATCH 6/9] seqlock: Better document raw_write_seqcount_latch()
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Peter Zijlstra
Quoted 5 lines · Mathieu Desnoyers
The latch, AFAIU, takes care of making sure the new objects are initialized before being published into the data structure, so there would be no need to use RCU assign pointer. However, we really need RCU around reads, along with a grace period between removal of an object and its teardown.
So I do need the
rcu_assign_pointerfor the RB link because that also initializes therb_nodeitself. Or put differently, be _very_ _VERY_ sure your entire object is initialized before the latch.
Quoted 7 lines
Quoted 7 lines
Secondly, note that the latch does a WMB and
rcu_assign_pointerdoes a RELEASE, these are not equivalent.So I don't think I will highlight this particular point. If you're sure enough to know the difference you can get away with it, sure. But in general I think people should still use
rcu_assign_pointer; if only to make Paul sleep better at night ;-)
I do appreciate that sentiment. ;-)
Quoted 2 lines
Also note that if you do not use
rcu_assign_pointer()one will at the very least requireWRITE_ONCE().
And, for ARM, IA64, and PowerPC, memory-barrier instructions.
Thanx, Paul
Re: [RFC][PATCH 6/9] seqlock: Better document raw_write_seqcount_latch()
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
Improve the documentation of the latch technique as used in the current timekeeping code, such that it can be readily employed elsewhere.
Borrow from the comments in timekeeping and replace those with a reference to this more generic comment.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Peter Zijlstra
maintainerRFC PATCH 7/9 rbtree: Implement generic latch_tree
In reply to Peter ZijlstraImplement a latched RB-tree in order to get RCU style lookups.
--- include/linux/rbtree_latch.h | 140 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 140 insertions(+)
include/linux/rbtree_latch.h new file +140 -0
@@ -0,0 +1,140 @@ +/* +* Latched RB-trees +* +* Copyright (C) 2015 Intel Corp., Peter Zijlstra <[email protected]> +*/ + +#ifndef RB_TREE_LATCH_H +#define RB_TREE_LATCH_H + +#include <linux/rbtree.h> +#include <linux/seqlock.h> + +/* +* Since RB-trees have non atomic modifications they're not suited for +* RCU/lockless queries. +* +* Employ the latch technique -- see @raw_write_seqcount_latch -- to implement +* a latched RB-tree which does allow this by virtue of always having (at +* least) one stable copy of the tree. +* +* However, while we have the guarantee that there is at all times one stable +* copy, this does not guarantee an iteration will not observe modifications. +* What might have been a stable copy at the start of the iteration, need not +* remain so for the duration of the iteration. +* +* Therefore, this does require a lockless RB-tree iteration to be non-fatal in +* all circumstances; see the comment in lib/rbtree.c. +*/ + +struct latch_tree_node { +void *priv; +struct rb_node node; +}; + +struct latch_tree_nodes { +struct latch_tree_node node[2 ]; +}; + +struct latch_tree_root { +seqcount_t seq; +struct rb_root tree[2 ]; +}; + +struct latch_tree_ops { +bool (*less)(struct latch_tree_node *a,struct latch_tree_node *b); +int (*comp)(void *key,struct latch_tree_node *b); +}; + +static __always_inline void +__lt_insert (struct latch_tree_node *ltn,struct rb_root *root, +bool (*less)(struct latch_tree_node *a,struct latch_tree_node *b)) +{ +struct rb_node **link = &root->rb_node; +struct rb_node *parent =NULL ; +struct latch_tree_node *ltp; + +while (*link) { + parent = *link; + ltp = container_of(parent, struct latch_tree_node, node); + +if (less (ltn, ltp)) + link = &parent->rb_left; +else + link = &parent->rb_right; + } + +rb_link_node_rcu (<n->node, parent, link); +rb_insert_color (<n->node, root); +} + +static __always_inline void +__lt_erase (struct latch_tree_node *ltn,struct rb_root *root) +{ +rb_erase (<n->node, root); +} + +static __always_inline struct latch_tree_node * +__lt_find (void *key,struct rb_root *root, +int (*comp)(void *key,struct latch_tree_node *ltn)) +{ +struct rb_node *n =rcu_dereference_raw (root->rb_node); +struct latch_tree_node *ltn; +int c; + +while (n) { + ltn = container_of(n, struct latch_tree_node, node); + c =comp (key, ltn); + +if (c <0 ) + n =rcu_dereference_raw (n->rb_left); +else if (c >0 ) + n =rcu_dereference_raw (n->rb_right); +else +return ltn; + } + +return NULL ; +} + +static __always_inline void +latch_tree_insert (struct latch_tree_nodes *nodes, +struct latch_tree_root *root, +void *priv, +const struct latch_tree_ops *ops) +{ + nodes->node[0 ].priv = nodes->node[1 ].priv = priv; + +raw_write_seqcount_latch (&root->seq); +__lt_insert (&nodes->node[0 ], &root->tree[0 ], ops->less); +raw_write_seqcount_latch (&root->seq); +__lt_insert (&nodes->node[1 ], &root->tree[1 ], ops->less); +} + +static __always_inline void +latch_tree_erase (struct latch_tree_nodes *nodes, +struct latch_tree_root *root, +const struct latch_tree_ops *ops) +{ +raw_write_seqcount_latch (&root->seq); +__lt_erase (&nodes->node[0 ], &root->tree[0 ]); +raw_write_seqcount_latch (&root->seq); +__lt_erase (&nodes->node[1 ], &root->tree[1 ]); +} + +static __always_inline struct latch_tree_node * +latch_tree_find (void *key,struct latch_tree_root *root, +const struct latch_tree_ops *ops) +{ +struct latch_tree_node *node; +unsigned int seq; + +do { + seq =raw_read_seqcount (&root->seq); + node =__lt_find (key, &root->tree[seq &1 ], ops->comp); + }while (read_seqcount_retry (&root->seq, seq)); + +return node; +} + +#endif /* RB_TREE_LATCH_H */
Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree
Quoted 1 line · Peter Zijlstra
Implement a latched RB-tree in order to get RCU style lookups.
Looks fine to me.
I wanted to ask, you are writing this as a generic layer even though there is a single use at the moment; do you anticipate this will get more usage soon ? I may have more comments if I knew what those may be (it's probably all fine if the rate of changes is very low such as with module load/unload, but I'm not sure what else you have in mind).
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Peter Zijlstra
maintainerRe: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree
Quoted 10 lines · Michel Lespinasse
Quoted 1 line · Peter Zijlstra
Implement a latched RB-tree in order to get RCU style lookups.
Looks fine to me.
I wanted to ask, you are writing this as a generic layer even though there is a single use at the moment; do you anticipate this will get more usage soon ? I may have more comments if I knew what those may be (it's probably all fine if the rate of changes is very low such as with module load/unload, but I'm not sure what else you have in mind).
It was more an exercise in separation in order to better document the various parts of this solution.
That said, we could maybe also use this for uprobes. Uprobes have a global RB tree and every lookup is currently serialized by a spinlock. I've not yet heard that its really painful, but I imagine a heavy uprobe workload on big machines will eventually hurt.
And through the years there have been 'demands' for RCU RB-trees, so maybe there's more potential users out there.
Note that while the update is more expensive than with a single tree, its still of the same complexity, so its not horrendously more expensive.
Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Implement a latched RB-tree in order to get RCU style lookups.
Cc Michel Lespinasse <[email protected]>Cc Andrea Arcangeli <[email protected]>Cc David Woodhouse <[email protected]>Cc Rik van Riel <[email protected]>Cc Mathieu Desnoyers <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Oleg Nesterov <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
The caller of latch_tree_erase() is required to wait for a grace period before freeing the erased nodes? Or am I missing something subtle here?
Thanx, Paul
Quoted 149 lines
--- include/linux/rbtree_latch.h | 140 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 140 insertions(+)include/linux/rbtree_latch.h new file +140
-0@@ -0,0 +1,140 @@ +/* +* Latched RB-trees +* +* Copyright (C) 2015 Intel Corp., Peter Zijlstra <[email protected]> +*/ + +#ifndef RB_TREE_LATCH_H +#define RB_TREE_LATCH_H + +#include <linux/rbtree.h> +#include <linux/seqlock.h> + +/* +* Since RB-trees have non atomic modifications they're not suited for +* RCU/lockless queries. +* +* Employ the latch technique -- see @raw_write_seqcount_latch -- to implement +* a latched RB-tree which does allow this by virtue of always having (at +* least) one stable copy of the tree. +* +* However, while we have the guarantee that there is at all times one stable +* copy, this does not guarantee an iteration will not observe modifications. +* What might have been a stable copy at the start of the iteration, need not +* remain so for the duration of the iteration. +* +* Therefore, this does require a lockless RB-tree iteration to be non-fatal in +* all circumstances; see the comment in lib/rbtree.c. +*/ + +struct latch_tree_node { +void *priv; +struct rb_node node; +}; + +struct latch_tree_nodes { +struct latch_tree_node node[2 ]; +}; + +struct latch_tree_root { +seqcount_t seq; +struct rb_root tree[2 ]; +}; + +struct latch_tree_ops { +bool (*less)(struct latch_tree_node *a,struct latch_tree_node *b); +int (*comp)(void *key,struct latch_tree_node *b); +}; + +static __always_inline void +__lt_insert (struct latch_tree_node *ltn,struct rb_root *root, +bool (*less)(struct latch_tree_node *a,struct latch_tree_node *b)) +{ +struct rb_node **link = &root->rb_node; +struct rb_node *parent =NULL ; +struct latch_tree_node *ltp; + +while (*link) { + parent = *link; + ltp = container_of(parent, struct latch_tree_node, node); + +if (less (ltn, ltp)) + link = &parent->rb_left; +else + link = &parent->rb_right; + } + +rb_link_node_rcu (<n->node, parent, link); +rb_insert_color (<n->node, root); +} + +static __always_inline void +__lt_erase (struct latch_tree_node *ltn,struct rb_root *root) +{ +rb_erase (<n->node, root); +} + +static __always_inline struct latch_tree_node * +__lt_find (void *key,struct rb_root *root, +int (*comp)(void *key,struct latch_tree_node *ltn)) +{ +struct rb_node *n =rcu_dereference_raw (root->rb_node); +struct latch_tree_node *ltn; +int c; + +while (n) { + ltn = container_of(n, struct latch_tree_node, node); + c =comp (key, ltn); + +if (c <0 ) + n =rcu_dereference_raw (n->rb_left); +else if (c >0 ) + n =rcu_dereference_raw (n->rb_right); +else +return ltn; + } + +return NULL ; +} + +static __always_inline void +latch_tree_insert (struct latch_tree_nodes *nodes, +struct latch_tree_root *root, +void *priv, +const struct latch_tree_ops *ops) +{ + nodes->node[0 ].priv = nodes->node[1 ].priv = priv; + +raw_write_seqcount_latch (&root->seq); +__lt_insert (&nodes->node[0 ], &root->tree[0 ], ops->less); +raw_write_seqcount_latch (&root->seq); +__lt_insert (&nodes->node[1 ], &root->tree[1 ], ops->less); +} + +static __always_inline void +latch_tree_erase (struct latch_tree_nodes *nodes, +struct latch_tree_root *root, +const struct latch_tree_ops *ops) +{ +raw_write_seqcount_latch (&root->seq); +__lt_erase (&nodes->node[0 ], &root->tree[0 ]); +raw_write_seqcount_latch (&root->seq); +__lt_erase (&nodes->node[1 ], &root->tree[1 ]); +} + +static __always_inline struct latch_tree_node * +latch_tree_find (void *key,struct latch_tree_root *root, +const struct latch_tree_ops *ops) +{ +struct latch_tree_node *node; +unsigned int seq; + +do { + seq =raw_read_seqcount (&root->seq); + node =__lt_find (key, &root->tree[seq &1 ], ops->comp); + }while (read_seqcount_retry (&root->seq, seq)); + +return node; +} + +#endif /* RB_TREE_LATCH_H */
Peter Zijlstra
maintainerRe: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree
Quoted 12 lines · Paul E. McKenney
Quoted 10 lines · Peter Zijlstra
Implement a latched RB-tree in order to get RCU style lookups.
Cc Michel Lespinasse <[email protected]>Cc Andrea Arcangeli <[email protected]>Cc David Woodhouse <[email protected]>Cc Rik van Riel <[email protected]>Cc Mathieu Desnoyers <[email protected]>Cc "Paul E. McKenney" <[email protected]>Cc Oleg Nesterov <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 2 lines
The caller of
latch_tree_erase()is required to wait for a grace period before freeing the erased nodes? Or am I missing something subtle here?
Correct; let me clarify this.
Peter Zijlstra
maintainerRFC PATCH 8/9 module: Optimize __module_address() using a latched RB-tree
In reply to Peter ZijlstraCurrently __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 | 22 ++++++++-- kernel/module.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 121 insertions(+), 8 deletions(-)
include/linux/module.h +19 -3
@@ -17,6 +17,7 @@#include <linux/moduleparam.h> #include <linux/jump_label.h> #include <linux/export.h> +#include <linux/rbtree_latch.h> #include <linux/percpu.h> #include <asm/module.h>
@@ -269,8 +270,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, +* init_text_size, core_text_size and ltn_core.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 +289,14 @@ struct module {/* The size of the executable code in each section. */ unsigned int init_text_size, core_text_size; +/* +* We rely on the order of these two entries; not only do we want +* core.node[0] to be in the same cacheline as the above entries, +* we also assume ltn_init has a higher address than ltn_core. +*/ +struct latch_tree_nodes ltn_core; +struct latch_tree_nodes ltn_init; +/* Size of RO sections of the module (text+rodata) */ unsigned int init_ro_size, core_ro_size;
@@ -361,7 +377,7 @@ struct module {ctor_fn_t *ctors;unsigned int num_ctors;#endif -}; +}____cacheline_aligned ;#ifndef MODULE_ARCH_INIT #define MODULE_ARCH_INIT {}#endif
kernel/module.c +102 -5
145 lines not on this page · raw message
Peter Zijlstra
maintainerRFC PATCH 9/9 module: Use __module_address() for module_address_lookup()
In reply to Peter ZijlstraUse the generic __module_address() addr to struct module lookup instead of open coding it once more.
--- kernel/module.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-)
kernel/module.c +7 -10
@@ -3515,19 +3515,15 @@ const char *module_address_lookup(unsignchar **modname, char *namebuf) { - struct module *mod; const char *ret = NULL; +struct module *mod;preempt_disable (); -list_for_each_entry_rcu (mod, &modules, list) { -if (mod->state ==MODULE_STATE_UNFORMED ) -continue ; -if (within_module (addr, mod)) { -if (modname) - *modname = mod->name; - ret =get_ksymbol (mod, addr, size, offset); -break ; - } + mod =__module_address (addr); +if (mod) { +if (modname) + *modname = mod->name; + ret =get_ksymbol (mod, addr, size, offset); }/* Make a copy in here where it's safe */ if (ret) {
@@ -3535,6 +3531,7 @@ const char *module_address_lookup(unsign ret = namebuf; }preempt_enable (); +return ret; }