From: Linus Torvalds <torvalds@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 2:41 pm 2008

On Wed, 14 May 2008, Ingo Molnar wrote:
> 
> Linus, Alan: the increased visibility and debuggability of the BKL 
> already uncovered a rather serious regression in upstream -git. You 
> might want to cherry pick this single fix, it will apply just fine to 
> current -git:

Ok, so I'm obviously happy. This is exactly the kind of thing I would want 
to see.

That said, the way it is now set up, it's unreasonable to merge anything 
directly, and while I can cherry-pick obvious fixes this way, I do think 
we could do things better.

It should be possible to set things up so that it's a config option, and 
we can mark it EXPERIMENTAL but still merge it into the standard kernel, 
so that we'd have the debug stuff there. That would get a lot more 
coverage, especially if it all still *works*, even if the debug stuff then 
complains (ie it would be nicer if the lock itself didn't start breaking).

So for example, have CONFIG_DEBUG_BKL turn it into a mutex (and select 
mutex debugging), and get all the debug coverage that way, but then when 
somebody enters the scheduler with the lock held, first complain, but then 
auto-release it anyway. That way, bugs get found and complained about, but 
hopefully the machine still ends up working.

		Linus
--

From: Jonathan Corbet <corbet@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree 
Date: May 14, 5:45 pm 2008

Sez Ingo:

> This task is not easy at all. 12 years after Linux has been converted to 
> an SMP OS we still have 1300+ legacy BKL using sites. There are 400+ 
> lock_kernel() critical sections and 800+ ioctls.

There's also every char device open() method - a rather long list in its
own right.  I'd be surprised if one in ten of them really needs it, but
one has to look...

I've been looking at the chrdev code anyway, and pondering on how this
might be addressed.  Here's some thoughts on alternatives, I'd be
curious what people think:

1: We could add an unlocked_open() to the file_operations structure;
   drivers could be converted over as they are verified not to need the
   BKL on open.  Disadvantages are that it grows this structure for a
   relatively rare case - most open() calls already don't need the BKL.
   But it's a relatively easy path without flag days.

2: Create a char_dev_ops structure for char devs and use it instead of
   file_operations.  I vaguely remember seeing Al mutter about that a
   while back.  Quite a while back.  This mirrors what was done with
   block devices, and makes some sense - there's a lot of stuff in
   struct file_operations which is not really applicable to char devs.
   Then struct char_dev_ops could have open() and locked_open(), with
   the latter destined for removal sometime around 2015 or so.

   Advantages are that it's cleaner and separates out some things which
   perhaps shouldn't be mixed anyway.  Disadvantage is...well...a fair
   amount of code churn.  It would also require chrdev-specific wrappers
   to map straight file_operations calls in the VFS to the new
   callbacks.

3: Provide a new form of cdev_add() which lets the driver indicate
   that the BKL is not needed on open (or anything else?).  At a
   minimum, it could just be a new parameter on cdev_add which has a
   value of zero or FIXME_I_STILL_NEED_BKL.  Still some churn but easier
   to script and smaller because a lot of drivers are still using
   register_chrdev() - something else worth fixing.

   A more involved form might provide a new chardev_add() which takes
   the new char_dev_ops structure too.  Mapping between new and old
   operations vectors would be done internally to avoid breaking older
   drivers before they can be fixed.

4: Just find every char dev open() function and shove in lock_kernel()
   calls, then remove the call from chrdev_open().  The disadvantage
   here is that, beyond lots of work and churn, there's no way to know
   which ones you missed.

I kind of like the combination of 2 and 3, done in such a way that
there's no "every driver must change" flag day.  This could be an
interesting project, even...  Thoughts?

jon
--


From: Linus Torvalds <torvalds@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree 
Date: May 14, 5:56 pm 2008

On Wed, 14 May 2008, Jonathan Corbet wrote:
> 
> There's also every char device open() method - a rather long list in its
> own right.  I'd be surprised if one in ten of them really needs it, but
> one has to look...

I don't think there are *that* many. I found only 83 instances of 
"register_chrdev()" in the kernel, so the open methods should be pretty 
limited.

Of course, some open methods call other sub-registrations, but you'd start 
off by moving the lock_kernel() down just *one* stage. 

So it literally should be:
 - remove one lock_kernel/unlock_kernel pair in fs/char_dev.c
 - add max 83 pairs in the places that register those things
 - external modules will need to add it themselves some day.

> 1: We could add an unlocked_open() to the file_operations structure;
>    drivers could be converted over as they are verified not to need the
>    BKL on open.  Disadvantages are that it grows this structure for a
>    relatively rare case - most open() calls already don't need the BKL.
>    But it's a relatively easy path without flag days.

I really don't think it's worth the pain. See above. The numbers aren't 
that huge, and external modules simply aren't a pressing enough issue.

		Linus
--


From: Jonathan Corbet <corbet@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree 
Date: May 14, 6:07 pm 2008

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> I don't think there are *that* many. I found only 83 instances of 
> "register_chrdev()" in the kernel, so the open methods should be pretty 
> limited.

There's the drivers calling cdev_add() directly as well - another
40ish.  Still not a huge list, I guess.
 
> So it literally should be:
>  - remove one lock_kernel/unlock_kernel pair in fs/char_dev.c
>  - add max 83 pairs in the places that register those things
>  - external modules will need to add it themselves some day.

This is all certainly doable, but it leaves me with one concern: there
will be no signal to external module maintainers that the change needs
to be made.  So, beyond doubt, quite a few of them will just continue to
be shipped unfixed - and they will still run.  If any of them actually
*need* the BKL, something awful may happen to somebody someday.

jon
--


From: Linus Torvalds <torvalds@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree 
Date: May 14, 6:14 pm 2008

On Wed, 14 May 2008, Jonathan Corbet wrote:
> 
> This is all certainly doable, but it leaves me with one concern: there
> will be no signal to external module maintainers that the change needs
> to be made.  So, beyond doubt, quite a few of them will just continue to
> be shipped unfixed - and they will still run.  If any of them actually
> *need* the BKL, something awful may happen to somebody someday.

External modules have bugs because interfaces change. Film at 11.

It's true, but it definitely shouldn't keep us from just doing it. 
Especially since well-maintained external modules (ie the authors follow 
big discussions like this) can just take the kernel lock regardless of 
kernel version, since it won't even be broken with old kernels.

Of course, well-maintained kernel modules wouldn't depend on the BKL in 
the first place. Oh, well.

		Linus


--

From: Andi Kleen <andi@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 2:30 pm 2008

Ingo Molnar <mingo@elte.hu> writes:

> As some of the latency junkies on lkml already know it, commit 8e3e076 
> ("BKL: revert back to the old spinlock implementation") in v2.6.26-rc2 
> removed the preemptible BKL feature and made the Big Kernel Lock a 
> spinlock and thus turned it into non-preemptible code again. This commit 
> returned the BKL code to the 2.6.7 state of affairs in essence.

It's a reasonable start, but have you considered doing this work
in tree instead? As in just add all the warnings, but don't actually
change the semantics yet.  I suspect you would get far more users
this way and the work would go faster. 

It would be reasonable to enable this in -mm if it the warnings are
not too intrusive (self disable itself etc.)

Also for fixing the ioctls I'm not sure that dynamic instrumentation
will really work because it would be tough to execute them all.

I suspect some variant of static code analysis would make sense
for the ioctls. 

I used to do some auditing with cflow. That won't
catch indirect function calls unfortunately, but if there's 
some way to find those and bail out one could do an automated
tool that flags all the ioctls that don't sleep for example
(don't have any sleeping functions in the call chain -- this
might need some manual annotation, but hopefully not much)

Then it would be possible to safely switch those over to a blocking
mutex variant of BKL. 

Now there could be some more automated analysis here: for example the 
main other user of BKL is character open. I suspect to really
make progress here you would also need a open_unlocked() and
do the same for all the open functions etc.

> According to my quick & dirty git-log analysis, at the current pace of 
> BKL removal we'd have to wait more than 10 years to remove most BKL 
> critical sections from the kernel and to get acceptable latencies again.

Hmm, is BKL really that common still that it's a latency problem?
The few VFS cases like locks can be fixed without extreme measures.

Most of the legacy users are unlikely to be latency problems,
simply because only very few people (or nobody) still has that hardware
and the code will never run.

Also I wouldn't lose sleep over e.g. let ISDN continue using BKL forever.

-Andi
--


From: Alan Cox <alan@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 5:00 pm 2008

> Most of the legacy users are unlikely to be latency problems,
> simply because only very few people (or nobody) still has that hardware
> and the code will never run.
> 
> Also I wouldn't lose sleep over e.g. let ISDN continue using BKL forever.

Most of the legacy users inflict that locking on other code - eg the ISN
use of the BKL directly impacts on the tty layer work.
--


From: Andi Kleen <andi@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 5:13 pm 2008

Alan Cox wrote:
>> Most of the legacy users are unlikely to be latency problems,
>> simply because only very few people (or nobody) still has that hardware
>> and the code will never run.
>>
>> Also I wouldn't lose sleep over e.g. let ISDN continue using BKL forever.
> 
> Most 

Most?

>of the legacy users inflict that locking on other code - eg the ISN
> use of the BKL directly impacts on the tty layer work.

So you just stick unlock_kernel()/lock_kernel() around the call
to TTY (or similar to the entry points)

-Andi




--


From: Alan Cox <alan@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 5:19 pm 2008

> Most?

Yes

> 
> >of the legacy users inflict that locking on other code - eg the ISN
> > use of the BKL directly impacts on the tty layer work.
> 
> So you just stick unlock_kernel()/lock_kernel() around the call
> to TTY (or similar to the entry points)

It isn't that simple - I've spent a good deal of time working on it.
There are lots of paths that rely on interactions between modules. Eg we
found stuff racing between the pid structs tty internals and procfs that
happened to be saved by the BKL.

That in itself is a problem Ingo's stuff won't help with: We have lots of
"magic" accidental, undocumented and pot luck BKL locking semantics
between subsystems that are not even visible.
--


From: Linus Torvalds <torvalds@...>
Subject: Re: [announce] "kill the Big Kernel Lock (BKL)" tree
Date: May 14, 5:45 pm 2008

On Wed, 14 May 2008, Alan Cox wrote:
> 
> That in itself is a problem Ingo's stuff won't help with: We have lots of
> "magic" accidental, undocumented and pot luck BKL locking semantics
> between subsystems that are not even visible.

The good news is that I suspect they are going away. It probably is mainly 
tty and /proc by now, and /proc is pretty close to done.

It's hard to have too many inter-module dependencies when most of the core 
modules no longer even take the kernel lock any more.

In the VFS layer, we still have 

 - the ioctl thing, obviously. That's just mind-numbing "move things 
   down", not hard per se. But there's a *lot* of them (and I suspect the 
   huge majority of them don't actually need it, since they'd already be 
   racing against read/write anyway if they did).

 - default_llseek(). Probably the same, just a lot less of it.

 - superblock read/write.

and the latter one in particular is really dubious (we already have 
"[un]lock_super()" around it all, I think).

The core kernel, VM and networking already don't really do BKL. And it's 
seldom the case that subsystems interact with other unrelated subsystems 
outside of the core areas.

So it's a lot of work, no doubt, but I do think we should be able to do 
it. The most mind-numbing part is literally all the ioctl crud. There's 
more ioctl points than there are lock_kernel() calls left anywhere else.

		Linus
--