Revised Unreliable Kernel Locking Guide
OK, I've put the html version up for your reading pleasure: the diff is quite extensive and hard to read.
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
Feedback welcome,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 6 lines · Rusty Russell
OK, I've put the html version up for your reading pleasure: the diff is quite extensive and hard to read.
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
Feedback welcome,
Hi Rusty,
Might be worth mentioning in the Per-CPU data section that code doing
operations on CPU registers (MSRs and the like) needs to be protected by an explicit preempt_disable() / preempt_enable() pair if it's doing operations that it expects to run on a specific CPU.
For examples, see arch/i386/kernel/msr.c & cpuid.c
Dave
Quoted 4 lines · Dave Jones
Might be worth mentioning in the Per-CPU data section that code doing operations on CPU registers (MSRs and the like) needs to be protected by an explicit
preempt_disable()/preempt_enable()pair if it's doing operations that it expects to run on a specific CPU.
Also calls to smp_call_function() need to be wrapped in preempt_disable, plus any work that is done on the current cpu before/after calling a function on the other cpus. Lack of preempt disable could result in the operation being done twice on one cpu and not at all on another.
Quoted 11 lines · Keith Owens
Quoted 4 lines · Dave Jones
Might be worth mentioning in the Per-CPU data section that code doing operations on CPU registers (MSRs and the like) needs to be protected by an explicit
preempt_disable()/preempt_enable()pair if it's doing operations that it expects to run on a specific CPU.Also calls to
smp_call_function()need to be wrapped inpreempt_disable, plus any work that is done on the current cpu before/after calling a function on the other cpus. Lack of preempt disable could result in the operation being done twice on one cpu and not at all on another.
And where you want to do the same thing on every processor, there's a handy on_each_cpu() which takes care of this for you.
Dave
Quoted 8 lines · Dave Jones
Quoted 4 lines · Keith Owens
Also calls to
smp_call_function()need to be wrapped inpreempt_disable, plus any work that is done on the current cpu before/after calling a function on the other cpus. Lack of preempt disable could result in the operation being done twice on one cpu and not at all on another.And where you want to do the same thing on every processor, there's a handy
on_each_cpu()which takes care of this for you.
I know, but there is code in 2.6 that calls smp_call_function directly, without preempt disable around it.
Quoted 6 lines · Dave Jones
Might be worth mentioning in the Per-CPU data section that code doing
operations on CPU registers (MSRs and the like) needs to be protected by an explicitpreempt_disable()/preempt_enable()pair if it's doing operations that it expects to run on a specific CPU.For examples, see
arch/i386/kernel/msr.c&cpuid.c
Good point.
I think this can be generalized to "you must remain atomic so long as you expect the processor state to remain consistent." For example, while manipulating processor registers or modes.
This means that you must disable kernel preemption and must not sleep within the critical region.
Rob Love
In message <[email protected]> you write:
Quoted 8 lines · Rusty Russell
Quoted 6 lines
OK, I've put the html version up for your reading pleasure: the diff is quite extensive and hard to read.
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
Feedback welcome,
Quoted 7 lines
Hi Rusty,
Might be worth mentioning in the Per-CPU data section that code doing
operations on CPU registers (MSRs and the like) needs to be protected by an explicitpreempt_disable()/preempt_enable()pair if it's doing operations that it expects to run on a specific CPU.For examples, see
arch/i386/kernel/msr.c&cpuid.c
I don't think it belongs in per-cpu data, that's a bit disingenous. It's a separate section by itself, I think. But it's also fairly rare.
The smp_call_function() case is more subtle, but in fact, there are only two calls to smp_call_function in non-arch-specific code, and both are wrong:
mm/slab.c: smp_call_function_all_cpus() should just be on_each_cpu.
net/core/flow.c: This should also be on_each_cpu: I actually have a
patch for this, too.
The aim of this document is to give the reader an overview core techniques, not describe every possible variant. IMHO a more likely candidate for a section would be atomic_dec_and_lock(), which there is no real concept of an "owner" of an object, but the destroy is implicit (and atomic) by the last user.
Hope that clarifies,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 9 lines · Rusty Russell
OK, I've put the html version up for your reading pleasure: the diff is quite extensive and hard to read.
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
Feedback welcome,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Hello, Rusty,
Good stuff! A few comments, as always!
Thanx, Paul
Glossary:
o Hardware Interrupt / Hardware IRQ: How does in_irq()
know that interrupts have been blocked? The local_irq_disable() does not seem to mess with the counter, and preempt_disable() just does the standard inc/dec stuff...
o in_irq() is hardirq_count().
o hardirq_count() is (preempt_count() & HARDIRQ_MASK).
o preempt_count is an integer, HARDIRQ_MASK is a constant that
is out of the normal inc/dec range.
I see how an interrupt handler causes in_irq() to do its thing via the irq_enter() and irq_exit() macros, but I don't see how masking interrupts makes this happen.
Probably just my confusion, but...
Ditto for "in_interrupt()". That would be for both the analysis and the probable confusion on my part.
o Software Interrupt / softirq: formatting botch "of'software".
This would be "o'software", right?
o Preemption: Would it be worth changing the first bit
of the second sentence to read something like: "In 2.5.4 and later, when CONFIG_PREEMPT is set, this changes:"?
Overzealous Prevention Of Deadlocks: Cute!!!
Avoiding Locks: Read Copy Update
o Might be worth noting explicitly early on that updaters are
running concurrently with readers. Should be obvious given that the readers aren't doing any explicit synchronization, but I have run into confusion on this point surprisingly often.
o Please add a note to the list_for_each_entry_rcu() description
saying that writers (who hold appropriate locks) need not use the _rcu() variant.
o Don't understand the blank line before and after the
"struct rcu_head rcu;", but clearly doesn't affect functionality. ;-)
o If nothing blocks between the call to __cache_find() and the
eventual object_put(), it is worthwhile to avoid the reference-count manipulation. This would make all of cache_find() be almost as fast as UP, rather than just __cache_find().
A few comments on top of Paul's and another seperate one;
Quoted 10 lines · Paul E. McKenney
o Hardware Interrupt / Hardware IRQ: How does
in_irq()
know that interrupts have been blocked? Thelocal_irq_disable()does not seem to mess with the counter, andpreempt_disable()just does the standard inc/dec stuff...o
in_irq()ishardirq_count().
ohardirq_count()is (preempt_count()&HARDIRQ_MASK).
opreempt_countis an integer,HARDIRQ_MASKis a constant that
is out of the normal inc/dec range.
Quoted 8 lines
I see how an interrupt handler causes
in_irq()to do its thing via theirq_enter()andirq_exit()macros, but I don't see how masking interrupts makes this happen.Probably just my confusion, but...
Ditto for "
in_interrupt()". That would be for both the analysis and the probable confusion on my part.
I'd have to agree, it would require OR'ing with irqs_disabled(). And another addendum would be that in_interrupt() also returns true when in a softirq handler.
Quoted 7 lines
o Software Interrupt / softirq: formatting botch "of'software".
This would be "o'software", right?o Preemption: Would it be worth changing the first bit
of the second sentence to read something like: "In 2.5.4 and later, whenCONFIG_PREEMPTis set, this changes:"?
I think he could also add that local_irq_disable() also disables preemption implicitely.
User Context
The kernel executing on behalf of a particular process (ie. a system call or trap) or kernel thread. You can tell which process with the current() macro.) Not to be confused with userspace. Can be interrupted by software or hardware interrupts.
Small nit, it's 'current'
In message <[email protected]> you write:
Quoted 2 lines
I think he could also add that
local_irq_disable()also disables preemption implicitely.
True, but I don't actually mention preemption very much at all, except in RCU. That belongs more in the Unreliable Guide To Kernel Hacking, IMHO.
Revising which is next weeks' job.
Quoted 1 line
Small nit, it's 'current'
Thanks fixed!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
In message <[email protected]> you write:
Quoted 15 lines · Rusty Russell
Quoted 9 lines
OK, I've put the html version up for your reading pleasure: the diff is quite extensive and hard to read.
http://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/
Feedback welcome,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.Hello, Rusty,
Good stuff! A few comments, as always!
Quoted 8 lines
Thanx, Paul
Glossary:
o Hardware Interrupt / Hardware IRQ: How does
in_irq()
know that interrupts have been blocked? Thelocal_irq_disable()does not seem to mess with the counter, andpreempt_disable()just does the standard inc/dec stuff...
You're right, it doesn't.
Quoted 5 lines
o
in_irq()ishardirq_count().
ohardirq_count()is (preempt_count()&HARDIRQ_MASK).
opreempt_countis an integer,HARDIRQ_MASKis a constant that
is out of the normal inc/dec range.
Quoted 8 lines
I see how an interrupt handler causes
in_irq()to do its thing via theirq_enter()andirq_exit()macros, but I don't see how masking interrupts makes this happen.Probably just my confusion, but...
Ditto for "
in_interrupt()". That would be for both the analysis and the probable confusion on my part.
Yes. I've removed both those: AFAICT they were never true.
Quoted 2 lines
o Software Interrupt / softirq: formatting botch "of'software".
This would be "o'software", right?
Looks ok here:
Tasklets and softirqs both fall into the category of 'software interrupts'.
Quoted 3 lines
o Preemption: Would it be worth changing the first bit
of the second sentence to read something like: "In 2.5.4 and later, whenCONFIG_PREEMPTis set, this changes:"?
I was trying to make it a little future-proof: I think CONFIG_PREEMPT should go away some day.
Quoted 1 line
Overzealous Prevention Of Deadlocks: Cute!!!
This is untouched from the old version of the document. I had a troubled youth...
Quoted 6 lines
Avoiding Locks: Read Copy Update
o Might be worth noting explicitly early on that updaters are
running concurrently with readers. Should be obvious given that the readers aren't doing any explicit synchronization, but I have run into confusion on this point surprisingly often.
OK. Changed the second paragraph from:
How do we get rid of read locks? That is actually quite simple:
to:
How do we get rid of read locks? Getting rid of read locks means that writers may be changing the list underneath the readers. That is actually quite simple:
Quoted 3 lines
o Please add a note to the
list_for_each_entry_rcu()description
saying that writers (who hold appropriate locks) need not use the_rcu()variant.
OK:
Once again, there is a <function>list_for_each_entry_rcu()</function> (<filename>include/linux/list.h</filename>) to help you. Of course, writers can just use <function>list_for_each_entry()</function>, since there cannot be two simultaneous writers.
Quoted 3 lines
o Don't understand the blank line before and after the
"structrcu_headrcu;", but clearly doesn't affect functionality. ;-)
Hmm, it would logically be at the start of the structure. I think I wanted to avoid associating it with the refcnt_t.
Quoted 5 lines
o If nothing blocks between the call to
__cache_find()and the
eventualobject_put(), it is worthwhile to avoid the reference-count manipulation. This would make all ofcache_find()be almost as fast as UP, rather than just__cache_find().
Good point. Text added at the bottom of that section:
<para>
There is a furthur optimization possible here: remember our original cache code, where there were no reference counts and the caller simply held the lock whenever using the object? This is still possible: if you hold the lock, noone can delete the object, so you don't need to get and put the reference count.
</para>
<para>
Now, because the 'read lock' in RCU is simply disabling preemption, a caller which always preemption disabled between calling <function>cache_find()</function> and <function>object_put()</function> does not need to actually get and put the reference count: we could expose <function>__cache_find()</function> by making it non-static, and such callers could simply call that.
</para>
<para>
The benefit here is that the reference count is not written to: the object is not altered in any way, which is much faster on SMP machines due to caching.
</para>
I've uploaded a new draft with these and other fixes...
Thanks!
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
Quoted 7 lines · Rusty Russell
In message <[email protected]> you write:
Quoted 2 lines
o Software Interrupt / softirq: formatting botch "of'software".
This would be "o'software", right?Looks ok here:
Tasklets and softirqs both fall into the category of 'software interrupts'.
It was late and my eyes were tired. Can't even blame it on my browser!!!
Quoted 6 lines
Quoted 3 lines
o Preemption: Would it be worth changing the first bit
of the second sentence to read something like: "In 2.5.4 and later, whenCONFIG_PREEMPTis set, this changes:"?I was trying to make it a little future-proof: I think
CONFIG_PREEMPTshould go away some day.
I hear you! But I suspect that it may take quite some time for that day to arrive.
Quoted 4 lines
Quoted 1 line
Overzealous Prevention Of Deadlocks: Cute!!!
This is untouched from the old version of the document. I had a troubled youth...
;-) Well, don't wring -all- of the fun out of the document!
Quoted 9 lines
Quoted 6 lines
Avoiding Locks: Read Copy Update
o Might be worth noting explicitly early on that updaters are
running concurrently with readers. Should be obvious given that the readers aren't doing any explicit synchronization, but I have run into confusion on this point surprisingly often.OK. Changed the second paragraph from:
Quoted 7 lines
How do we get rid of read locks? That is actually quite simple:
to:
How do we get rid of read locks? Getting rid of read locks means that writers may be changing the list underneath the readers. That is actually quite simple:
Looks good! Upon rereading... Does "wmb()" want to be "smp_wmb()"?
Quoted 4 lines
Quoted 3 lines
o Please add a note to the
list_for_each_entry_rcu()description
saying that writers (who hold appropriate locks) need not use the_rcu()variant.
Quoted 8 lines
OK:
Once again, there is a <function>list_for_each_entry_rcu()</function> (<filename>include/linux/list.h</filename>) to help you. Of course, writers can just use <function>list_for_each_entry()</function>, since there cannot be two simultaneous writers.
Also looks good!
Again, upon rereading, "read Read Copy Update code" probably wants to
be "real Read Copy Update code". I moused it this time, given
my past record with eyeballing. ;-)
Quoted 16 lines
Quoted 5 lines
o If nothing blocks between the call to
__cache_find()and the
eventualobject_put(), it is worthwhile to avoid the reference-count manipulation. This would make all ofcache_find()be almost as fast as UP, rather than just__cache_find().Good point. Text added at the bottom of that section:
<para>
There is a furthur optimization possible here: remember our original cache code, where there were no reference counts and the caller simply held the lock whenever using the object? This is still possible: if you hold the lock, noone can delete the object, so you don't need to get and put the reference count.
</para>
Quoted 3 lines
<para>
Now, because the 'read lock' in RCU is simply disabling preemption, a caller which always preemption disabled between calling
disables preemption
Quoted 11 lines
<function>cache_find()</function> and <function>object_put()</function> does not need to actually get and put the reference count: we could expose <function>__cache_find()</function> by making it non-static, and such callers could simply call that.
</para>
<para>
The benefit here is that the reference count is not written to: the object is not altered in any way, which is much faster on SMP machines due to caching.
</para>
Other than the grammar nit above, looks good!
Quoted 1 line
I've uploaded a new draft with these and other fixes...
Good stuff, thank you!!!
Thanx, Paul
In message <[email protected]> you write:
Quoted 5 lines
Quoted 3 lines
How do we get rid of read locks? Getting rid of read locks means that writers may be changing the list underneath the readers. That is actually quite simple:
Looks good! Upon rereading... Does "
wmb()" want to be "smp_wmb()"?
Yes, but I didn't want to turn this into a document on memory
barriers: you'll note that I almost avoided it entirely.
Quoted 3 lines
Again, upon rereading, "read Read Copy Update code" probably wants to
be "real Read Copy Update code". I moused it this time, given
my past record with eyeballing. ;-)
Fixed.
Quoted 3 lines
Quoted 2 lines
Now, because the 'read lock' in RCU is simply disabling preemption, a caller which always preemption disabled between calling
disables preemption
Ah, I inserted a 'has' as well (a caller which always has preemption disabled...). The implication that the caller probably has preempt disabled as a side effect of being in an interrupt or holding a spinlock.
Quoted 3 lines
Quoted 1 line
I've uploaded a new draft with these and other fixes...
Good stuff, thank you!!!
Hey, thanks for the review!
Cheers,
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.