remove the BKL (Big Kernel Lock), this time for real

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

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

@@ -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 */

@@ -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

@@ -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

@@ -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);

I really think this is wrong.

Maybe not from a conceptual standpoint, but that implementation with the scheduler doing "reaquire_kernel_lock()" and doing a down() there is just wrong, wrong, wrong.

If we're going to do a down() and block immediately after being scheduled, I don't think we should have been picked in the first place.

Yeah, yeah, you have all that magic to not recurse by setting lock-depth negative before doing the down(), but it still feels fundamentally wrong to me. There's also the question whether this actually _helps_ anything, since it may well just replace the spinning with lots of new scheduler activity.

And you make schedule() a lot more expensive for kernel lock holders by copying the CPU map. You may have tested it on a machine where the CPU map is just a single word, but what about the big machines?

Spinlocks really _are_ cheaper. Wouldn't it be nice to just continue removing kernel lock users and keeping a very _simple_ kernel lock for legacy issues?

In other words, I'd _really_ like to see some serious numbers for this.

Linus

agreed, and that codepath is only for correctness - the semaphore code will make sure most of the time that this doesnt happen. It's the same as the need_resched check - it doesnt happen in 99.9% of the cases but when it happens it must happen.

Rare activity that still runs under the BKL (e.g. mounting, or ioctls) can introduce many milliseconds of scheduling delays that hurt latencies. None of this is really performance-sensitive as it's almost always used for some big old piece of code. Anything that is frequently taken/dropped we've replaced with proper spinlocks already. So what's left is the code for which 1) everyone hurts most from it not being a real semaphore 2) no _user_ or maintainer of that code cares about the BKL because it's not performance-critical.

we dont really care about BKL _users_, other than correctness. We've got cpusets for the bitmap overhead reduction.

and it's not that bad - if it's .. 512 CPUs then _BKL users_ copy 64 bytes. I dont think the 512-CPU guys will complain about this patch. If there are any frequent BKL users on such big boxes then they need serious and quick fixing anyway, because they are bouncing a global spinlock madly across 512 CPUs, 32 cross-connects and 4 backplanes! The 64-byte copy within the CPU-local task structure really dwarves in comparison...

yes, but progress in this area seems to have slowed down, and people are hurting from the latencies introduced by the BKL meanwhile. Who cares if some rare big chunk of code runs under a semaphore, as long as it's preemptable?

a global spinlock isnt all that much cheaper than a semaphore, even if it's not taken or lightly taken. If it's heavily taken then a semaphore wins. There is clearly an interim area where a spinlock will win - but only if the spinlock is well-localized to some resource or CPU - this is absolutely not true for the BKL which is as global as it gets.

fully agreed about that too!

Ingo

"as long as it's preemptable" is the key there. Not all arch's can run with PREEMPT enabled (yet) -- sparc/sparc64 for but one. And at the moment, PREEMPT is a bit on the hosed side.

--Ricky

there's no problem at all - with my patch you'll still get the other advantage:

- there is no time wasted spinning on the BKL if there's BKL contention

so if a platform doesnt support PREEMPT (or a user doesnt enable it) then BKS-holding kernel code wont be preempted of course.

Ingo

Is it not worth looking at the worst offenders (ioctl will be hard I suspect) and fixing these as an interim step?

--cw

Well, I'm more concerned that the users all need to be swept anyway. This could make sense to do anyway, but the sweeps IMHO are necessary because the users almost universally are those that haven't been taught to do any locking yet, stale and crusty code that needs porting, or things where the locking hasn't quite been debugged or straightened out.

One thing I like is that this eliminates the implicit dropping on sleep as a source of bugs (e.g. it was recently pointed out to me that setfl() uses the BKL to protect ->f_flags in a codepath spanning a sleeping call to ->fasync()), where the semaphore may be retained while sleeping. I originally wanted to make sleeping under the BKL illegal and sweep users to repair when it is, but maybe that's unrealistic, particularly considering that the sum of my BKL sweeps to date are one removal from procfs "protecting" its access of nr_threads.

-- wli

the attached patch is a simplified variant of the remove-bkl patch i sent two days ago: it doesnt do the ->cpus_allowed trick.

The question is, is there any BKL-using kernel code that relies on the task not migrating to another CPU within the BLK critical section?

(Patch is against 2.6.9-rc2-mm1. Patch booted fine on x86 SMP+PREEMPT and UP and the previous patch was tested on x64 as well so i'd expect this one to work fine on all platforms.)

Ingo

@@ -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 */

@@ -27,12 +27,12 @@
 #define in_softirq()		(softirq_count())
 #define in_interrupt()		(irq_count())
 
+#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() & ~PREEMPT_ACTIVE) != 0)
 # define preemptible()	0
 # define IRQ_EXIT_OFFSET HARDIRQ_OFFSET
 #endif

@@ -436,6 +436,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();
 } 
 

@@ -501,6 +502,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();
 	trap_init();

I very much doubt, I'd expect this to work, but it really should be a config option if you don't open 2.7. This is the kind of thing that cannot happen in a 2.6.* release without a config option to leave off in production IMHO since it can have implications well outside the mainline kernel (every driver outside the kernel would be affected too).

IMHO this would be more likely to fix bugs than introduce them so long as the BKL is acquired before spinlocks in all instances. There are many instances where scheduling under the BKL is inadvertent and thus racy, but very few (if any) where the BKL is an inner lock or a holder of the BKL yields so something that will wake it can acquire the BKL.

-- wli

that reinforces my argument, that's another case that can break with this patch.

I don't think it has a chance to fix any bug, if something it will trigger some deadlock or race condition, but OTOH I agree it should work fine (all code I can recall by memory takes the BKL before any inner spinlock too, and I don't think we left anything that depends on smp_processor_id()), but again this is the kind of change that requires some testing and cannot be shipped by default in a stable tree, it requires config option at the very least.

But the corner cases I outlined don't exist; the case that does exist is where the BKL is dropped by mistake by e.g. a call to a function that may sleep. c.f. fs/fcntl.c:setfl().

-- wli

the attached debug patch is ontop of the above patch and prints warnings if code uses smp_processor_id() in a preemptible section of code. The patch gets rid of a number of common false positives but more false positives are more than likely.

The patch has already uncovered a bug: softirq invocation had a softirq invocation race possibly leading to (<1msec) softirq processing delays in the PREEMPT case. But more importantly it has found no BKL user so far that relied on smp_processor_id(), which makes me hopeful that the problem is not widespread at all and we could opt for the simpler, semaphore-based BKS design.

(patch tested on x86 and x64, should work on all architectures.)

Ingo

@@ -34,7 +34,7 @@ inline void __const_udelay(unsigned long
 	xloops *= 4;
 	__asm__("mull %0"
 		:"=d" (xloops), "=&a" (d0)
-		:"1" (xloops),"0" (current_cpu_data.loops_per_jiffy * (HZ/4)));
+		:"1" (xloops),"0" (boot_cpu_data.loops_per_jiffy * (HZ/4)));
         __delay(++xloops);
 }
 

@@ -34,7 +34,7 @@ void __delay(unsigned long loops)
 
 inline void __const_udelay(unsigned long xloops)
 {
-        __delay(((xloops * current_cpu_data.loops_per_jiffy) >> 32) * HZ);
+        __delay(((xloops * boot_cpu_data.loops_per_jiffy) >> 32) * HZ);
 }
 
 void __udelay(unsigned long usecs)

@@ -50,7 +50,7 @@ extern u8 x86_cpu_to_apicid[];
  * from the initial startup. We map APIC_BASE very early in page_setup(),
  * so this is correct in the x86 case.
  */
-#define smp_processor_id() (current_thread_info()->cpu)
+#define __smp_processor_id() (current_thread_info()->cpu)
 
 extern cpumask_t cpu_callout_map;
 #define cpu_possible_map cpu_callout_map

@@ -66,7 +66,7 @@ static inline int num_booting_cpus(void)
 	return cpus_weight(cpu_callout_map);
 }
 
-#define smp_processor_id() read_pda(cpunumber)
+#define __smp_processor_id() read_pda(cpunumber)
 
 extern __inline int hard_smp_processor_id(void)
 {

@@ -95,8 +95,11 @@ void smp_prepare_boot_cpu(void);
 /*
  *	These macros fold the SMP functionality into a single CPU system
  */
- 
-#define smp_processor_id()			0
+
+#if !defined(__smp_processor_id) || !defined(CONFIG_PREEMPT)
+# define smp_processor_id()			0
+
+#endif
 #define hard_smp_processor_id()			0
 #define smp_threads_ready			1
 #define smp_call_function(func,info,retry,wait)	({ 0; })

@@ -107,6 +110,17 @@ static inline void smp_send_reschedule(i
 
 #endif /* !SMP */
 
+#ifdef __smp_processor_id 
+# ifdef CONFIG_PREEMPT
+   extern unsigned int smp_processor_id(void);
+# else
+#  define smp_processor_id() __smp_processor_id()
+# endif
+# define _smp_processor_id() __smp_processor_id()
+#else
+# define _smp_processor_id() smp_processor_id()
+#endif
+
 #define get_cpu()		({ preempt_disable(); smp_processor_id(); })
 #define put_cpu()		preempt_enable()
 #define put_cpu_no_resched()	preempt_enable_no_resched()

@@ -105,7 +105,7 @@ struct rt_cache_stat 
 
 extern struct rt_cache_stat *rt_cache_stat;
 #define RT_CACHE_STAT_INC(field)					  \
-		(per_cpu_ptr(rt_cache_stat, smp_processor_id())->field++)
+		(per_cpu_ptr(rt_cache_stat, _smp_processor_id())->field++)
 
 extern struct ip_rt_acct *ip_rt_acct;
 

@@ -128,18 +128,18 @@ struct linux_mib {
 #define SNMP_STAT_USRPTR(name)	(name[1])
 
 #define SNMP_INC_STATS_BH(mib, field) 	\
-	(per_cpu_ptr(mib[0], smp_processor_id())->mibs[field]++)
+	(per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field]++)
 #define SNMP_INC_STATS_OFFSET_BH(mib, field, offset)	\
-	(per_cpu_ptr(mib[0], smp_processor_id())->mibs[field + (offset)]++)
+	(per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field + (offset)]++)
 #define SNMP_INC_STATS_USER(mib, field) \
-	(per_cpu_ptr(mib[1], smp_processor_id())->mibs[field]++)
+	(per_cpu_ptr(mib[1], _smp_processor_id())->mibs[field]++)
 #define SNMP_INC_STATS(mib, field) 	\
-	(per_cpu_ptr(mib[!in_softirq()], smp_processor_id())->mibs[field]++)
+	(per_cpu_ptr(mib[!in_softirq()], _smp_processor_id())->mibs[field]++)
 #define SNMP_DEC_STATS(mib, field) 	\
-	(per_cpu_ptr(mib[!in_softirq()], smp_processor_id())->mibs[field]--)
+	(per_cpu_ptr(mib[!in_softirq()], _smp_processor_id())->mibs[field]--)
 #define SNMP_ADD_STATS_BH(mib, field, addend) 	\
-	(per_cpu_ptr(mib[0], smp_processor_id())->mibs[field] += addend)
+	(per_cpu_ptr(mib[0], _smp_processor_id())->mibs[field] += addend)
 #define SNMP_ADD_STATS_USER(mib, field, addend) 	\
-	(per_cpu_ptr(mib[1], smp_processor_id())->mibs[field] += addend)
+	(per_cpu_ptr(mib[1], _smp_processor_id())->mibs[field] += addend)
 
 #endif

@@ -641,8 +641,9 @@ void release_console_sem(void)
 		_con_start = con_start;
 		_log_end = log_end;
 		con_start = log_end;		/* Flush */
-		spin_unlock_irqrestore(&logbuf_lock, flags);
+		spin_unlock(&logbuf_lock);
 		call_console_drivers(_con_start, _log_end);
+		local_irq_restore(flags);
 	}
 	console_locked = 0;
 	console_may_schedule = 0;

@@ -137,12 +137,19 @@ EXPORT_SYMBOL(do_softirq);
 
 void local_bh_enable(void)
 {
-	__local_bh_enable();
 	WARN_ON(irqs_disabled());
-	if (unlikely(!in_interrupt() &&
-		     local_softirq_pending()))
+	if (unlikely(!in_interrupt() && local_softirq_pending())) {
+		/*
+		 * Keep preemption disabled until we are done with
+		 * softirq processing:
+	 	 */
+		preempt_count() -= SOFTIRQ_OFFSET - 1;
 		invoke_softirq();
-	preempt_check_resched();
+		preempt_enable();
+	} else {
+		__local_bh_enable();
+		preempt_check_resched();
+	}
 }
 EXPORT_SYMBOL(local_bh_enable);
 

This cannot be applied to 2.6 IMHO. it still doesn't track the lock_kernel usage inside a spinlock, and even if it did, we cannot use the stable 2.6 userbase for the beta testing and see if some production machine triggers those warnings.

If you would make this a config option *then* it could be included, OTOH for these kind of things 2.7 would be more appropriate (the config option is just a waste of resources since eventually the whole thing will go away).

Overall I think this is not a change that a vendor kernel could ever make in the middle of a stable series (it sounds quite similar to preempt, even if less risky, and it really buys nothing to the end user and in turn it's definitely not justified), and in turn I don't think it's appropriate for a 2.6 mainline either (at least by default without config option like you're posting).

Infact I'm not even convinced this is the right step forward in the removal of the BKL, rather than wasting our time discussing this, it'd be better to start removing the lock_kernel calls.

what do you mean? If something does lock_kernel() within spin_lock() then the might_sleep() check in down() catches it and will print a warning. (None of these warnings has triggered on any of my 3 systems yet, suggesting that the problem is not widespread. In any case it's very likely a _bug_ so we want to know!)

Ingo

I didn't see any patch that removed the CONFIG_DEBUG_SPINLOCK_SLEEP config option and avoided might_sleep to be defined to noop. If we apply your patch that's something we need IMHO, and that's what I meant with "it still doesn't track the lock_kernel usage inside a spinlock", I didn't specify "_always_ track the lock_kernel usage inside a spinlock", but I thought the "always" was implicitly, clearly it was not, sorry for not clarifying this.

wanting to know is fine with me, what's not fine with me is deadlocking a production box after that, when it could be a legitimate usage. It's not about the printk, it's about the following crash. As said this thing spreads all over the place, especially in possibly bogus drivers out of the tree, and I don't think it provides any significant benefit (Ok I'm biased since I tend to think about PREEMPT=n where a semaphore won't provide any benefit, and if there's any latency issue with the BKL that can be fixed without risks with cond_resched_bkl as pointed out earlier and it definitely doesn't need this patch). And as Linus mentioned the risk of overscheduling is also possible with the semaphore but that's the minor issue in this IMHO.

So in short if you change your patch to only add checks that leads into printk that's very much fine with me (basically you would have to change lock_kernel() to add an unconditional might_sleep in there, and the other stuff for the smp_processor_id). I'm not against wanting to know.

Overall I still don't see any benefit. The thing to fix is the lock_kernel global lock concept that doesn't scale and doesn't self-document what is being locked against what. IMHO changing the lock_kernel internal details in a way that changes the semantics in a subtle manner cannot bring any long term benefit and it can only hurt the short term due the potentail breakage it introduces.

I don't think there can be any _valid_ such use.

Anything that knows about CPU's has to use "get_cpu()/put_cpu()" anyway. You might add back in the debugging checks that we used to have for "smp_processor_id()" in this patch for testing, and if it goes into -mm we'd see if anything triggers.

I still don't exactly love this patch to death, but making the cpumask trickery go away does make it look a lot simpler, I have to say.

Linus