remove the BKL (Big Kernel Lock), this time for real
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 2 lines · Ingo Molnar
the attached patch is a new approach to get rid of Linux's Big Kernel Lock as we know it today.
Interesting approach. Did you measure what it does to context switch rates? Usually adding semaphores tends to increase them a lot.
One minor comment only:
Please CSE "current" manually. It generates much better code on some architectures because the compiler cannot do it for you.
-Andi
Quoted 7 lines · Andi Kleen
Quoted 2 lines · Ingo Molnar
the attached patch is a new approach to get rid of Linux's Big Kernel Lock as we know it today.
Interesting approach. Did you measure what it does to context switch rates? Usually adding semaphores tends to increase them a lot.
not yet - i've coded it up today. Perhaps the lowlatency audio folks (who are most interested in BKL-latency removal) could report some numbers?
but as i've replied to Linus too, i believe that _if_ the context-switch rate goes up then some piece of code uses the BKL way too often! So having a semaphore here might in fact help fixing those rare cases.
Quoted 3 lines
One minor comment only:
Please CSE "current" manually. It generates much better code on some architectures because the compiler cannot do it for you.
yeah, agreed, will do.
Ingo
Quoted 3 lines · Andi Kleen
One minor comment only:
Please CSE "current" manually. It generates much better code on some architectures because the compiler cannot do it for you.
new patch attached - this one uses 'current' as few times as possible.
Ingo
the attached patch is a new approach to get rid of Linux's Big Kernel Lock as we know it today.
The trick is to turn the BKL spinlock + depth counter into a special type of cpu-affine, recursive semaphore, which gets released by schedule() but not by preempt_schedule().
this gives the following advantages:
- BKL critical sections are fully preemptable with this patch applied
- there is no time wasted spinning on the BKL if there's BKL contention
- no changes are needed for lock_kernel() users - the new semaphore-based approach is fully compatible with the BKL.
code using lock_kernel()/unlock_kernel() will see very similar semantics as they got from the BKL, so correctness should be fully preserved. Per-CPU assumptions still work, locking exclusion and lock-recursion still works the same way as it did with the BKL.
non-BKL code sees no overhead from this approach. (other than the slighly smaller code due to the uninlining of the BKL APIs.)
(the patch is against vanilla 2.6.9-rc2. I have tested it on x86 UP+PREEMPT, UP+!PREEMPT, SMP+PREEMPT, SMP+!PREEMPT and x64 SMP+PREEMPT.)
include/linux/smp_lock.h renamed from include/linux/smp_lock.h.orig +3 -48
@@ -7,59 +7,14 @@#if defined(CONFIG_SMP ) || defined(CONFIG_PREEMPT ) -extern spinlock_t kernel_flag; - -#define kernel_locked () (current->lock_depth >= 0) - -#define get_kernel_lock () spin_lock(&kernel_flag) -#define put_kernel_lock () spin_unlock(&kernel_flag) - -/* -* Release global kernel lock. -*/ -static inline void release_kernel_lock (struct task_struct *task) -{ -if (unlikely (task->lock_depth >=0 )) -put_kernel_lock (); -} - -/* -* Re-acquire the kernel lock -*/ -static inline void reacquire_kernel_lock (struct task_struct *task) -{ -if (unlikely (task->lock_depth >=0 )) -get_kernel_lock (); -} - -/* -* Getting the big kernel lock. -* -* This cannot happen asynchronously, -* so we only need to worry about other -* CPU's. -*/ -static inline void lock_kernel (void ) -{ -int depth = current->lock_depth+1 ; -if (likely (!depth)) -get_kernel_lock (); - current->lock_depth = depth; -} - -static inline void unlock_kernel (void ) -{ -BUG_ON (current->lock_depth <0 ); -if (likely (--current->lock_depth <0 )) -put_kernel_lock (); -} +extern int kernel_locked (void ); +extern void lock_kernel (void ); +extern void unlock_kernel (void );#else #define lock_kernel () do { } while(0)#define unlock_kernel () do { } while(0) -#define release_kernel_lock (task) do { } while(0) -#define reacquire_kernel_lock (task) do { } while(0)#define kernel_locked () 1#endif /* CONFIG_SMP || CONFIG_PREEMPT */
include/linux/hardirq.h renamed from include/linux/hardirq.h.orig +2 -2
@@ -32,12 +32,12 @@#define hardirq_trylock () (!in_interrupt())#define hardirq_endlock () do { } while (0) +#define in_atomic () ((preempt_count() & ~PREEMPT_ACTIVE) != 0) +#ifdef CONFIG_PREEMPT -# define in_atomic () ((preempt_count() & ~PREEMPT_ACTIVE) != kernel_locked())# define preemptible () (preempt_count() == 0 && !irqs_disabled())# define IRQ_EXIT_OFFSET (HARDIRQ_OFFSET-1)#else -# define in_atomic () (preempt_count() != 0)# define preemptible () 0# define IRQ_EXIT_OFFSET HARDIRQ_OFFSET#endif
include/linux/sched.h renamed from include/linux/sched.h.orig +1 -0
@@ -454,6 +454,7 @@ struct task_struct {unsigned long policy;cpumask_t cpus_allowed; +cpumask_t saved_cpus_allowed;unsigned int time_slice, first_time_slice;#ifdef CONFIG_SCHEDSTATS
kernel/sched.c renamed from kernel/sched.c.orig +134 -21
212 lines not on this page · raw message
init/main.c renamed from init/main.c.orig +7 -0
@@ -435,6 +435,7 @@ static void noinline rest_init(void)kernel_thread (init,NULL ,CLONE_FS |CLONE_SIGHAND );numa_default_policy ();unlock_kernel (); +preempt_enable_no_resched ();cpu_idle (); }
@@ -500,6 +501,12 @@ asmlinkage void __init start_kernel(void* time - but meanwhile we still have a functioning scheduler. */ sched_init (); +/* +* The early boot stage up until we run the first idle thread +* is a very volatile affair for the scheduler. Disable preemption +* up until the init thread has been started: +*/ +preempt_disable ();build_all_zonelists ();page_alloc_init ();printk ("Kernel command line: %s\n" , saved_command_line);
Quoted 5 lines · Ingo Molnar
code using lock_kernel()/unlock_kernel() will see very similar semantics as they got from the BKL, so correctness should be fully preserved. Per-CPU assumptions still work, locking exclusion and lock-recursion still works the same way as it did with the BKL.
Hi Ingo,
One change is that lock_kernel now sleeps, while it previously didn't, I think?
Is this going to be a problem? Or have you checked the remaining bkl users to ensure this is OK? Am I on drugs? :)
Nick
Quoted 10 lines · Andi Kleen
Quoted 2 lines · Ingo Molnar
the attached patch is a new approach to get rid of Linux's Big Kernel Lock as we know it today.
Interesting approach. Did you measure what it does to context switch rates? Usually adding semaphores tends to increase them a lot.
Is that (necessarily) a bad thing? If it results in less time waiting for BKL, and/or more time doing user work, that may drive throughput and responsiveness up. It depends if the time for two ctx is greater or less than the spin time on BKL.
It would be nice to have the best of both worlds, use the semaphore if there is a process on the run queue, and spin if not. That sounds complex, and hopefully not worth the effort.
High ctx rates are not necessarily bad, when we implemented O_DIRECT for an application the rate went up 30%, the outbound bandwidth went up 10-15%, and waitio dropped by half at peak load. As long as something useful is being done with the time previously wasted in spinning, I would expect it to be a win.
Signature · 3 lines
-bill davidsen ([email protected]) "The secret to procrastination is to put things off until the last possible moment - but no longer" -me
Quoted 8 lines · Bill Davidsen
Is that (necessarily) a bad thing? If it results in less time waiting for BKL, and/or more time doing user work, that may drive throughput and responsiveness up. It depends if the time for two ctx is greater or less than the spin time on BKL.
It would be nice to have the best of both worlds, use the semaphore if there is a process on the run queue, and spin if not. That sounds complex, and hopefully not worth the effort.
FreeBSD-current uses adaptive mutexes. However they spin on that mutex only if the thread owning it is running across another CPU at that time, otherwise it sleeps, maybe priority inherited depending on the circumstance. It's kind of heavy weight, I know, but it might be a good place to look for an example implementation of this thing.
I'm sure that a simplified adaptive mutex can be used that's compatible with the Linux SMP/preemption methology if this becomes relevant.
Quoted 5 lines
High ctx rates are not necessarily bad, when we implemented
O_DIRECTfor an application the rate went up 30%, the outbound bandwidth went up 10-15%, and waitio dropped by half at peak load. As long as something useful is being done with the time previously wasted in spinning, I would expect it to be a win.
It's critical for other devices as well, like keeping a GPU fully engaged so that there isn't computational stalls since the process queue is empty, etc...
Anybody thought about using this to protect RCU-ed critical sections yet even though it doesn't guarantee quiescience ? or has the recent work softirq-ing them sufficient ? Can't this be used as a kind per CPU-local data guard much like {get,set}_cpu() and friends ?
bill
Quoted 4 lines · On Thu, 16 Sep 2004 15:29:03 -0700 Bill Huey (hui) <[email protected]> wrote:
FreeBSD-current uses adaptive mutexes. However they spin on that mutex only if the thread owning it is running across another CPU at that time, otherwise it sleeps, maybe priority inherited depending on the circumstance.
This is how Solaris MUTEX objects work too.
Quoted 9 lines · David S. Miller
Quoted 4 lines · On Thu, 16 Sep 2004 15:29:03 -0700 Bill Huey (hui) <[email protected]> wrote:
FreeBSD-current uses adaptive mutexes. However they spin on that mutex only if the thread owning it is running across another CPU at that time, otherwise it sleeps, maybe priority inherited depending on the circumstance.
This is how Solaris MUTEX objects work too.
Yeah, I know from Solaris Internals and FreeBSD can be considered a Solaris style kernel. In contract, I think the Linux community has a few things up on FreeBSD/Solaris style SMP. Specifically, the FreeBSD community has ignored a lot of the really hard work of pushing down locks in favor of "getting fancier locks", which only abuses thread priorities and the scheduler. A large part of it is because they have really create a very complicated SMP infrastructure that less than a handful of their kernel engineers really know how to use, 2-3, it seems.
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
bill
Quoted 5 lines · On Thu, 16 Sep 2004 15:51:02 -0700 Bill Huey (hui) <[email protected]> wrote:
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
This is what Linus proclaimed 6 or 7 years ago when people were trying to convince us to do things like Solaris and other big Unixes at the time.
Quoted 9 lines · David S. Miller
Quoted 5 lines · On Thu, 16 Sep 2004 15:51:02 -0700 Bill Huey (hui) <[email protected]> wrote:
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
Quoted 3 lines
This is what Linus proclaimed 6 or 7 years ago when people were trying to convince us to do things like Solaris and other big Unixes at the time.
FreeBSD's SMPng project is stalled for the most part and developers that disagree with that approach have move onto the DragonFly BSD community. It has a much more top-down driven locking system that's conceptually CPU local called tokens, effectively deadlock free and difficult to misused. It's already been able to multi-thread the networking stack using lock-less techniques, while the FreeBSD-current tree had to retract their "all or nothing" approach with threading their network stack. Jeffery Hsu is the main developer pushing that subsystem.
bill
Quoted 5 lines · On Thu, 16 Sep 2004 15:51:02 -0700 Bill Huey (hui) wrote:
Quoted 5 lines
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
Quoted 3 lines · David S. Miller
This is what Linus proclaimed 6 or 7 years ago when people were trying to convince us to do things like Solaris and other big Unixes at the time.
Just in case, I didn't claim it was my idea, I merely gave empirical evidence.
-- wli
Quoted 5 lines · Bill Huey
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
a clarification: note that the current BKL is a special case. No way do i suggest that the BKS is the proper model for any SMP implementation. It is a narrow special-case because it wraps historic UP-only kernel code.
our primary multiprocessing primitives are still the following 4:
lockless data structures, RCU, spinlocks and mutexes. (reverse ordered by level of parallelism.) The BKS is basically a fifth method, a special type of semaphore that i'd never want to be seen used by any new SMP code. It is completely local to sched.c.
Ingo
Quoted 14 lines · Ingo Molnar
Quoted 5 lines · Bill Huey
Judging from how the Linux code is done and the numbers I get from Bill Irwin in casual conversation, the Linux SMP approach is clearly the right track at this time with it's hand honed per-CPU awareness of things. The only serious problem that spinlocks have as they aren't preemptable, which is what Ingo is trying to fix.
a clarification: note that the current BKL is a special case. No way do i suggest that the BKS is the proper model for any SMP implementation. It is a narrow special-case because it wraps historic UP-only kernel code.
Quoted 7 lines
our primary multiprocessing primitives are still the following 4:
lockless data structures, RCU, spinlocks and mutexes. (reverse ordered by level of parallelism.) The BKS is basically a fifth method, a special type of semaphore that i'd never want to be seen used by any new SMP code. It is completely local tosched.c.Ingo
I coded a IPC system before use atomic add + share memory. It works very well (fast) on 4 CPU SMP system, since it doesn't use
any locking API at all. Very good for resource allocation for
SMP. I implemented speciall malloc/free use by ISR, different
prority process
completely without any lock. Negative side, it use more memory.
Signature · 2 lines
-Tony Having a lot of fun with Xilinx Virtex Pro II reconfigurable HW + ppc + Linux