Re: BKL removal

Re: BKL removal

[Greg KH]

<copied to lkml, as people there deserve to also see this>

On Sat, Jul 06, 2002 at 11:38:06AM -0700, Dave Hansen wrote:
> Rik van Riel wrote:
> >On Thu, 4 Jul 2002, Dave Hansen wrote:
> >
> >>Greg KH wrote:
> >>
> >>>How about another extreme example.  When you removed the BKL from the
> >>>input subsystem, you created a zillion race conditions.  I can dig up
> >>>the email reference if you really want.  Hopefully that mess is finally
> >>>cleaned up now.
> >>
> >>But it is mostly BKL-free now, right?  It may have been painful for
> >>some, but it is better than before I broke it.
> >
> >If there is no contention on the lock, why is the BKL a problem?
> 
> It is not just a matter of scalability, but maintainability.  I find 
> it hard to read and understand code which uses the BKL.  As Greg said 
> in his OLS coding style talk, I want you to be able to read my code to 
> find _my_ mistakes.  Your ability to do that will be impaired by every 
> bad indentation, typedef, and BKL use.

Excuse me, but please do NOT compare coding style with using the BKL!  I
can use the BKL in my code just fine, and it does not impare your
ability to use, modify, or understand my code.  As long as I comment why
I am using the BKL.

> A lock with a single purpose, guarding relatively small amounts of 
> data is much easier to understand than one such as the BKL.  Would you 
> want a simple VM operation to take 1 second as the TTY layer and ext3 
> take their sweet time with the BKL?

If ext3 is spinning on the BKL, then try to fix that, as it seems like a
worthwhile task (like the ext2 changes proved.)  If you want to remove
the BKL from the tty layer, be my guest, that will involve rewriting
that whole subsystem :)

> There seems to be a lot of fear that we'll scale the kernel into 
> oblivion by creating a different lock for every single bit in every 
> single data structure in the kernel with horribly complex locking 
> hierarchies.  We know the implications of locks which are too finely 
> grained and we see them magnified 20-fold on our NUMA-Q boxes (cache 
> bouncing there is painful).  Linux may approach that point sometime in 
> the future, but BKL use is about as far from this situation as possible.

Yes, there is that fear of scaling into oblivion, because other
operating systems have done this in the past.  Learn from their
mistakes, don't redo them yourself.  Go talk to the IRIX developers, and
ask their experiences.  I know one of them is a few rows away from you
at work.

> I would mind the BKL a lot less if it was as well understood 
> everywhere as it is in VFS.  The funny part is that a lock like the 
> BKL would not last very long if it were well understood or documented 
> everywhere it was used.

I would mind it a whole lot less if when you try to remove the BKL, you
do it correctly.  So far it seems like you enjoy doing "hit and run"
patches, without even fully understanding or testing your patches out
(the driverfs and input layer patches are proof of that.)  This does
nothing but aggravate the developers who have to go clean up after you.

Also, stay away from instances of it's use WHERE IT DOES NOT MATTER for
performance.  If I grab the BKL on insertion or removal of a USB device,
who cares?  I know you are trying to remove it entirely out of the
kernel, but please focus on places where it actually helps, and leave
the other instances alone.

thanks,

greg k-h

Re: BKL removal

[Oliver Neukum]

[..]
> Excuse me, but please do NOT compare coding style with using the BKL!  I
> can use the BKL in my code just fine, and it does not impare your
> ability to use, modify, or understand my code.  As long as I comment why
> I am using the BKL.

That should be something the maintainers enforce.

[..]
> > I would mind the BKL a lot less if it was as well understood
> > everywhere as it is in VFS.  The funny part is that a lock like the
> > BKL would not last very long if it were well understood or documented
> > everywhere it was used.
>
> I would mind it a whole lot less if when you try to remove the BKL, you
> do it correctly.  So far it seems like you enjoy doing "hit and run"
> patches, without even fully understanding or testing your patches out
> (the driverfs and input layer patches are proof of that.)  This does
> nothing but aggravate the developers who have to go clean up after you.
>
> Also, stay away from instances of it's use WHERE IT DOES NOT MATTER for
> performance.  If I grab the BKL on insertion or removal of a USB device,
> who cares?  I know you are trying to remove it entirely out of the
> kernel, but please focus on places where it actually helps, and leave
> the other instances alone.

If you really want to make maximum impact, do tests. Very few people can measure
lock contention on a 4-CPU system. And please rest assured that nobody wants to
be maintainer of the subsystem that ruins scalability.

And if you see a use of the BKL you don't understand ask first, or send a patch
to the subsystem's mailing list, not lkml. People will look at BKL usage if you ask.
In fact such a look might even uncover bugs as in case of USB.

	Regards
		Oliver

Re: BKL removal

[Dave Hansen]

Greg KH wrote:
>>It is not just a matter of scalability, but maintainability.  I find 
>>it hard to read and understand code which uses the BKL.  As Greg said 
>>in his OLS coding style talk, I want you to be able to read my code to 
>>find _my_ mistakes.  Your ability to do that will be impaired by every 
>>bad indentation, typedef, and BKL use.
> 
> Excuse me, but please do NOT compare coding style with using the BKL!  I
> can use the BKL in my code just fine, and it does not impare your
> ability to use, modify, or understand my code.  As long as I comment why
> I am using the BKL.

If it was easy to modify, I wouldn't be making such a mess of things, 
right? (this assumes I'm _not_ a blundering idiot, which hasn't been 
proven)

  "As long as I comment [and understand] why I am using the BKL." 
would be a bit more accurate.  How many places in the kernel have you 
seen comments about what the BKL is actually doing?  Could you point 
me to some of your comments where _you_ are using the BKL?  Once you 
fully understand why it is there, the extra step of removal is usually 
very small.

>>A lock with a single purpose, guarding relatively small amounts of 
>>data is much easier to understand than one such as the BKL.  Would you 
>>want a simple VM operation to take 1 second as the TTY layer and ext3 
>>take their sweet time with the BKL?
> 
> If ext3 is spinning on the BKL, then try to fix that, as it seems like a
> worthwhile task (like the ext2 changes proved.)  If you want to remove
> the BKL from the tty layer, be my guest, that will involve rewriting
> that whole subsystem :)

All that I'm saying is that there can be unintended consequences.  By 
having it in your code, you open the possibility of these strange 
interactions and a drop in _your_ code's reliability.

I'm staying well away from the TTY layer, it is just a well known 
example.

>>I would mind the BKL a lot less if it was as well understood 
>>everywhere as it is in VFS.  The funny part is that a lock like the 
>>BKL would not last very long if it were well understood or documented 
>>everywhere it was used.
> 
> I would mind it a whole lot less if when you try to remove the BKL, you
> do it correctly.  So far it seems like you enjoy doing "hit and run"
> patches, without even fully understanding or testing your patches out
> (the driverfs and input layer patches are proof of that.)  This does
> nothing but aggravate the developers who have to go clean up after you.

Like it or not, the only way to get maintainers to pay any attention 
at all is to give them code.  Is there more likely to be progress if I 
just say, "Hey Greg, why don't you take the BKL out of USB", or if I 
send you a crappy patch which has the beginning of a valid approach? 
Code gets people thinking.

> Also, stay away from instances of it's use WHERE IT DOES NOT MATTER for
> performance.  If I grab the BKL on insertion or removal of a USB device,
> who cares?  I know you are trying to remove it entirely out of the
> kernel, but please focus on places where it actually helps, and leave
> the other instances alone.

You're sorely mistaken because I'm not trying to remove it entirely 
from the kernel.  I wouldn't cry if that happened tomorrow, but I 
don't have any delusions about it happening any time soon.

Call me "Ike", but I'm a domino theorist.  One instance of the BKL 
spawns many more over time, because they tend to proliferate for no 
other reason than "just to be safe".  The hardest ones to remove are 
those that shouldn't have been there in the first place.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Thunder from the hill]

Hi,

On Sun, 7 Jul 2002, Dave Hansen wrote:
>   "As long as I comment [and understand] why I am using the BKL." 
> would be a bit more accurate.  How many places in the kernel have you 
> seen comments about what the BKL is actually doing?  Could you point 
> me to some of your comments where _you_ are using the BKL?  Once you 
> fully understand why it is there, the extra step of removal is usually 
> very small.

Old Blue, could you please bring me an example on where in USB the bkl 
shouldn't be used, but is? And can you explain why it's wrong to use bkl
there?

							Regards,
							Thunder
-- 
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o?  K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y- 
------END GEEK CODE BLOCK------

Re: BKL removal

[Dave Hansen]

Oliver Neukum wrote:
 >>> I would mind the BKL a lot less if it was as well understood
 >>> everywhere as it is in VFS.  The funny part is that a lock like
 >>>  the BKL would not last very long if it were well understood or
 >>>  documented everywhere it was used.
 >>
 >> I would mind it a whole lot less if when you try to remove the
 >> BKL, you do it correctly.  So far it seems like you enjoy doing
 >> "hit and run" patches, without even fully understanding or
 >> testing your patches out (the driverfs and input layer patches
 >> are proof of that.)  This does nothing but aggravate the
 >> developers who have to go clean up after you.
 >>
 >> Also, stay away from instances of it's use WHERE IT DOES NOT
 >> MATTER for performance.  If I grab the BKL on insertion or
 >> removal of a USB device, who cares?  I know you are trying to
 >> remove it entirely out of the kernel, but please focus on places
 >> where it actually helps, and leave the other instances alone.
 >
 > If you really want to make maximum impact, do tests. Very few
 > people can measure lock contention on a 4-CPU system.

Do you mean "see lock contention", or "have the hardware to measure
lock contention"?  We probably use lockmeter more than just about 
anyone else.  But, I do not, nor have I ever contended, that things 
like driverfs's BKL use have a performance impact.  I just consider 
them messy, and bad practice.

 > And please rest assured that nobody wants to be maintainer of the
 > subsystem that ruins scalability.

I agree completely.  All of the maintainers who are handed data that 
shows bad BKL contention have either done something about it, or are 
doing something about it now.  2.5 is 2 orders of magnitude better 
than 2.4 for BKL contention in most of the workloads that I see.

 > And if you see a use of the BKL you don't understand ask first, or
 > send a patch to the subsystem's mailing list, not lkml. People will
 >  look at BKL usage if you ask. In fact such a look might even
 > uncover bugs as in case of USB.

I guess I got discouraged by a few non-responsive mailing lists in the 
past.  I'll make an effort to use them more in the future.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Greg KH]

On Sun, Jul 07, 2002 at 02:35:31PM -0700, Dave Hansen wrote:
> 
>  "As long as I comment [and understand] why I am using the BKL." 
> would be a bit more accurate.  How many places in the kernel have you 
> seen comments about what the BKL is actually doing?  Could you point 
> me to some of your comments where _you_ are using the BKL?  Once you 
> fully understand why it is there, the extra step of removal is usually 
> very small.

I have never written any kernel code that added usages of the BKL.  The
fact that I am now maintaining code that uses it should not be confused
with this.  Yes, some of my filesystems (pcihpfs and usbfs) now use it,
but that was due to other people pushing it down, out of the VFS.

> >>A lock with a single purpose, guarding relatively small amounts of 
> >>data is much easier to understand than one such as the BKL.  Would you 
> >>want a simple VM operation to take 1 second as the TTY layer and ext3 
> >>take their sweet time with the BKL?
> >
> >If ext3 is spinning on the BKL, then try to fix that, as it seems like a
> >worthwhile task (like the ext2 changes proved.)  If you want to remove
> >the BKL from the tty layer, be my guest, that will involve rewriting
> >that whole subsystem :)
> 
> All that I'm saying is that there can be unintended consequences.  By 
> having it in your code, you open the possibility of these strange 
> interactions and a drop in _your_ code's reliability.

Yes, and there can be unintended conequences for just blindly removing
the BKL as your input layer patch proved.  The input layer was using the
BKL in a reliable manner, it just wasn't documented.  And by using the
BKL in my code, it does not decrease reliability in any way (just might
slow it down under some system loads, but it still works properly.)

> I'm staying well away from the TTY layer, it is just a well known 
> example.

Ah, so it's easier to try to pick on subsystems that don't matter like
USB and driverfs?  :)

> >>I would mind the BKL a lot less if it was as well understood 
> >>everywhere as it is in VFS.  The funny part is that a lock like the 
> >>BKL would not last very long if it were well understood or documented 
> >>everywhere it was used.
> >
> >I would mind it a whole lot less if when you try to remove the BKL, you
> >do it correctly.  So far it seems like you enjoy doing "hit and run"
> >patches, without even fully understanding or testing your patches out
> >(the driverfs and input layer patches are proof of that.)  This does
> >nothing but aggravate the developers who have to go clean up after you.
> 
> Like it or not, the only way to get maintainers to pay any attention 
> at all is to give them code.  Is there more likely to be progress if I 
> just say, "Hey Greg, why don't you take the BKL out of USB", or if I 
> send you a crappy patch which has the beginning of a valid approach? 
> Code gets people thinking.

Either way, you get my same response, "Why?"  Again, as someone stated,
where in the USB code is the BKL used that affects performance in any
real life situations?

And yes, sending crappy patches does get people jumping, but don't rely
on that being a good method of doing development.  People only fall for
that one so many times.

greg k-h

Re: BKL removal

[Oliver Neukum]

>  > If you really want to make maximum impact, do tests. Very few
>  > people can measure lock contention on a 4-CPU system.
>
> Do you mean "see lock contention", or "have the hardware to measure
> lock contention"?  We probably use lockmeter more than just about

Both, most use UP exclusively. You know, SMP costs serious money.
Actually very few people can walk over to some colleagues to gain access
to a 16-CPU box.

> anyone else.  But, I do not, nor have I ever contended, that things
> like driverfs's BKL use have a performance impact.  I just consider
> them messy, and bad practice.

Then show some creativity, if you must publish statistics on subsystems
having most inexplicable uses of the BKL. Make it a challenge, not an attack.

>  > And please rest assured that nobody wants to be maintainer of the
>  > subsystem that ruins scalability.
>
> I agree completely.  All of the maintainers who are handed data that
> shows bad BKL contention have either done something about it, or are
> doing something about it now.  2.5 is 2 orders of magnitude better
> than 2.4 for BKL contention in most of the workloads that I see.

Good - which lock is next in your noble quest for scalability?

>  > And if you see a use of the BKL you don't understand ask first, or
>  > send a patch to the subsystem's mailing list, not lkml. People will
>  >  look at BKL usage if you ask. In fact such a look might even
>  > uncover bugs as in case of USB.
>
> I guess I got discouraged by a few non-responsive mailing lists in the
> past.  I'll make an effort to use them more in the future.

Yes, please. "Linus, let's rip out some random locks which offend my sense
of beauty" tends to piss off people. Linus might even agree, but you don't
enjoy His Excellency's priviledges ;-)

	Regards
		Oliver

Re: BKL removal

[Dave Hansen]

Thunder from the hill wrote:

 >> "As long as I comment [and understand] why I am using the BKL."
 >> would be a bit more accurate.  How many places in the kernel have
 >> you seen comments about what the BKL is actually doing?  Could
 >> you point me to some of your comments where _you_ are using the
 >> BKL?  Once you fully understand why it is there, the extra step
 >> of removal is usually very small.
 >
 > Old Blue, could you please bring me an example on where in USB the
 > bkl shouldn't be used, but is?  And can you explain why it's wrong
 > to use bkl there?

Old Blue?  23 isn't _that_ old!

BKL use isn't right or wrong -- it isn't a case of creating a deadlock 
or a race.  I'm picking a relatively random function from "grep -r 
lock_kernel * | grep /usb/".  I'll show what I think isn't optimal 
about it.

"up" is a local variable.  There is no point in protecting its 
allocation.  If the goal is to protect data inside "up", there should 
probably be a subsystem-level lock for all "struct uhci_hcd"s or a 
lock contained inside of the structure itself.  Is this the kind of 
example you're looking for?

  static int uhci_proc_open(struct inode *inode, struct file *file)
  {
         const struct proc_dir_entry *dp = PDE(inode);
         struct uhci_hcd *uhci = dp->data;
         struct uhci_proc *up;
         unsigned long flags;
         int ret = -ENOMEM;

-       lock_kernel();

         up = kmalloc(sizeof(*up), GFP_KERNEL);
         if (!up)
                 goto out;

         up->data = kmalloc(MAX_OUTPUT, GFP_KERNEL);
         if (!up->data) {
                 kfree(up);
                 goto out;
         }

+       lock_kernel();
         spin_lock_irqsave(&uhci->frame_list_lock, flags);
         up->size = uhci_sprint_schedule(uhci, up->data, MAX_OUTPUT);
         spin_unlock_irqrestore(&uhci->frame_list_lock, flags);

         file->private_data = up;
+ 
unlock_kernel();

         ret = 0;
  out:
-       unlock_kernel();
         return ret;
  }



-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Thunder from the hill]

Hi,

On Sun, 7 Jul 2002, Dave Hansen wrote:
> Old Blue?  23 isn't _that_ old!

Obviously, you never read that book about the IBM s/370 named
"Old Blue"...

> BKL use isn't right or wrong -- it isn't a case of creating a deadlock 
> or a race.  I'm picking a relatively random function from "grep -r 
> lock_kernel * | grep /usb/".  I'll show what I think isn't optimal 
> about it.
> 
> "up" is a local variable.  There is no point in protecting its 
> allocation.  If the goal is to protect data inside "up", there should 
> probably be a subsystem-level lock for all "struct uhci_hcd"s or a 
> lock contained inside of the structure itself.  Is this the kind of 
> example you're looking for?

So the BKL isn't wrong here, but incorrectly used?

Is it really okay to "lock the whole kernel" because of one struct file? 
This brings us back to spinlocks...

You're possibly right about this one. What did Greg K-H say?

							Regards,
							Thunder
-- 
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o?  K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y- 
------END GEEK CODE BLOCK------

Re: BKL removal

[Oliver Neukum]

> BKL use isn't right or wrong -- it isn't a case of creating a deadlock
> or a race.  I'm picking a relatively random function from "grep -r
> lock_kernel * | grep /usb/".  I'll show what I think isn't optimal
> about it.

Perhaps, we could agree that the BKL is used wrongly if it
won't fulfill its presumed function, or fulfills another function
than the obvious without a comment stating that, or fulfills
a non obvious function without any comment ?

The first case is IMHO the worst, because, although BKL
can't hurt technically, it obscures locking.

	Regards
		Oliver

Re: BKL removal

[Dave Hansen]

Thunder from the hill wrote:
> On Sun, 7 Jul 2002, Dave Hansen wrote:
> 
>>Old Blue?  23 isn't _that_ old!
> 
> Obviously, you never read that book about the IBM s/370 named
> "Old Blue"...

Nope.  I missed that one.  Something like "The Little Mainfraime that 
could?"

>>BKL use isn't right or wrong -- it isn't a case of creating a deadlock 
>>or a race.  I'm picking a relatively random function from "grep -r 
>>lock_kernel * | grep /usb/".  I'll show what I think isn't optimal 
>>about it.
>>
>>"up" is a local variable.  There is no point in protecting its 
>>allocation.  If the goal is to protect data inside "up", there should 
>>probably be a subsystem-level lock for all "struct uhci_hcd"s or a 
>>lock contained inside of the structure itself.  Is this the kind of 
>>example you're looking for?
> 
> So the BKL isn't wrong here, but incorrectly used?

Not even incorrect, but badly used.  But, this was probably another 
VFS push.

> Is it really okay to "lock the whole kernel" because of one struct file? 
> This brings us back to spinlocks...

Don't think of it as locking the kernel, that isn't really what it 
does anymore.  You really need to think of it as a special spinlock.

> You're possibly right about this one. What did Greg K-H say?

Only time will tell...

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Oliver Neukum]

> > "up" is a local variable.  There is no point in protecting its
> > allocation.  If the goal is to protect data inside "up", there should
> > probably be a subsystem-level lock for all "struct uhci_hcd"s or a
> > lock contained inside of the structure itself.  Is this the kind of
> > example you're looking for?
>
> So the BKL isn't wrong here, but incorrectly used?

The BKL, unless used unbalanced, can never cause a bug.
It could be insufficient or superfluous, but never be really buggy in itself.

> Is it really okay to "lock the whole kernel" because of one struct file?
> This brings us back to spinlocks...
>
> You're possibly right about this one. What did Greg K-H say?

I don't speak for Greg, but in this example it could be dropped IMO.
The spinlock protects the critical section anyway. As a rule, if you
do a kmalloc without GFP_ATOMIC under BKL you are doing either insufficient
locking (you may need a semaphore) or useless locking.

This should have been posted on linux-usb long ago.

	Regards
		Oliver

Re: BKL removal

[Dave Hansen]

Oliver Neukum wrote:
>>BKL use isn't right or wrong -- it isn't a case of creating a deadlock
>>or a race.  I'm picking a relatively random function from "grep -r
>>lock_kernel * | grep /usb/".  I'll show what I think isn't optimal
>>about it.
> 
> Perhaps, we could agree that the BKL is used wrongly if it
> won't fulfill its presumed function, or fulfills another function
> than the obvious without a comment stating that, or fulfills
> a non obvious function without any comment ?

I wouldn't want to make comments the qualifier for correct use, 
because that makes large chunks of the kernel "wrong" for lack of 
comments.  In a development series we also don't want to restrict 
ourselves to changes of things that are wrong.  We can also improve 
things that are bad.


-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Thunder from the hill]

Hi,

On Sun, 7 Jul 2002, Dave Hansen wrote:
> Nope.  I missed that one.  Something like "The Little Mainfraime that 
> could?"

It was "The Y2K bug - the last day" by some Marc.

> > So the BKL isn't wrong here, but incorrectly used?
> 
> Not even incorrect, but badly used.  But, this was probably another 
> VFS push.

The most correct would be to lock the struct file in any way so it can't 
be used while I eat it. But I guess that's efficient locking vs. space, 
isn't it? What would happen if we had a locking field on every struct?!

> > Is it really okay to "lock the whole kernel" because of one struct file? 
> > This brings us back to spinlocks...
> 
> Don't think of it as locking the kernel, that isn't really what it 
> does anymore.  You really need to think of it as a special spinlock.

We should rename it to something that actually tells you what it does. 
BTW, when was lock_kernel()? It must be really old if it still locked the 
whole kernel.

							Regards,
							Thunder
-- 
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o?  K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y- 
------END GEEK CODE BLOCK------

Re: BKL removal

[Sean Neakums]

commence  Thunder from the hill  quotation:
> We should rename it to something that actually tells you what it does. 
> BTW, when was lock_kernel()? It must be really old if it still locked the 
> whole kernel.

It was added during the 1.3 development phase.  Dave's paper in the
OLS proceedings (that was yours, wasn't it?) covers it pretty nicely
(at least to my kernel-ignorant eyes).

-- 
 /                          |
[|] Sean Neakums            |  Questions are a burden to others;
[|] <sneakums@zork.net>     |      answers a prison for oneself.
 \                          |

Re: BKL removal

[Dave Hansen]

Oliver Neukum wrote:
 >>> "up" is a local variable.  There is no point in protecting its
 >>> allocation.  If the goal is to protect data inside "up", there
 >>> should probably be a subsystem-level lock for all "struct
 >>> uhci_hcd"s or a lock contained inside of the structure itself.
 >>> Is this the kind of example you're looking for?
 >>
 >> So the BKL isn't wrong here, but incorrectly used?
 >
 > The BKL, unless used unbalanced, can never cause a bug. It could be
 > insufficient or superfluous, but never be really buggy in itself.

Does incredibly high lock contention qualify as a bug?

 >> Is it really okay to "lock the whole kernel" because of one
 >> struct file? This brings us back to spinlocks...
 >>
 >> You're possibly right about this one. What did Greg K-H say?
 >
 > I don't speak for Greg, but in this example it could be dropped
 > IMO. The spinlock protects the critical section anyway. As a rule,
 > if you do a kmalloc without GFP_ATOMIC under BKL you are doing
 > either insufficient locking (you may need a semaphore) or useless
 > locking.

Don't forget that the BKL is released on sleep.  It is OK to hold it
over a schedule()able operation.  If I remember right, there is no 
real protection needed for the file->private_data either because there 
is 1 and only 1 struct file per open, and the data is not shared among 
struct files.

 > This should have been posted on linux-usb long ago.

I just pulled it out of thin air 10 minutes ago!

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Greg KH]

On Sun, Jul 07, 2002 at 03:42:56PM -0700, Dave Hansen wrote:
> BKL use isn't right or wrong -- it isn't a case of creating a deadlock 
> or a race.  I'm picking a relatively random function from "grep -r 
> lock_kernel * | grep /usb/".  I'll show what I think isn't optimal 
> about it.
> 
> "up" is a local variable.  There is no point in protecting its 
> allocation.  If the goal is to protect data inside "up", there should 
> probably be a subsystem-level lock for all "struct uhci_hcd"s or a 
> lock contained inside of the structure itself.  Is this the kind of 
> example you're looking for?

Nice example, it proves my previous points:
	- you didn't send this to the author of the code, who is very
	  responsive when you do.
	- you didn't send this to the linux-usb-devel list, which is a
	  very responsive list.
	- this is in the file drivers/usb/host/uhci-debug.c, which by
	  its very nature leads you to believe that this is not critical
	  code at all.  This is true if you look at the code.
	- it looks like you could just remove the BKL entirely from this
	  call, and not just move it around the kmalloc() call.  But
	  since I don't understand all of the different locking rules
	  inside the uhci-hcd.c driver, I'm not going to do this.  I'll
	  let the author of the driver do that, incase it really matters
	  (and yes, the locking in the uhci-hcd driver is tricky, but
	  nicely documented.)
	- this file is about to be radically rewritten, to use driverfs
	  instead of procfs, as the recent messages on linux-usb-devel
	  state.  So any patch you might make will probably be moot in
	  about 3 days :)  Again, contacting the author/maintainer is
	  the proper thing to do.
	- even if you remove the BKL from this code, what have you
	  achieved?  A faster kernel?  A very tiny bit smaller kernel,
	  yes, but not any faster overall.  This is not on _any_
	  critical
	  path.

thanks,

greg k-h

Re: BKL removal

[Dave Hansen]

Greg KH wrote:
> On Sun, Jul 07, 2002 at 03:42:56PM -0700, Dave Hansen wrote:
> 
>>BKL use isn't right or wrong -- it isn't a case of creating a deadlock 
>>or a race.  I'm picking a relatively random function from "grep -r 
>>lock_kernel * | grep /usb/".  I'll show what I think isn't optimal 
>>about it.
>>
>>"up" is a local variable.  There is no point in protecting its 
>>allocation.  If the goal is to protect data inside "up", there should 
>>probably be a subsystem-level lock for all "struct uhci_hcd"s or a 
>>lock contained inside of the structure itself.  Is this the kind of 
>>example you're looking for?
> 
> 
> Nice example, it proves my previous points:
> 	- you didn't send this to the author of the code, who is very
> 	  responsive when you do.
> 	- you didn't send this to the linux-usb-devel list, which is a
> 	  very responsive list.
> 	- this is in the file drivers/usb/host/uhci-debug.c, which by
> 	  its very nature leads you to believe that this is not critical
> 	  code at all.  This is true if you look at the code.
> 	- it looks like you could just remove the BKL entirely from this
> 	  call, and not just move it around the kmalloc() call.  But
> 	  since I don't understand all of the different locking rules
> 	  inside the uhci-hcd.c driver, I'm not going to do this.  I'll
> 	  let the author of the driver do that, incase it really matters
> 	  (and yes, the locking in the uhci-hcd driver is tricky, but
> 	  nicely documented.)
> 	- this file is about to be radically rewritten, to use driverfs
> 	  instead of procfs, as the recent messages on linux-usb-devel
> 	  state.  So any patch you might make will probably be moot in
> 	  about 3 days :)  Again, contacting the author/maintainer is
> 	  the proper thing to do.

You are taking this example way too seriously.  Thunder wanted an 
example and I grabbed the first one that I saw (I created it in the 
last hour).  I showed you how I arrived at it, just a quick grepping. 
  It wan't a real patch, only a quick little example snippet.

> 	- even if you remove the BKL from this code, what have you
> 	  achieved?  A faster kernel?  A very tiny bit smaller kernel,
> 	  yes, but not any faster overall.  This is not on _any_
> 	  critical path.

How many times do I have to say it?  We're going around in circles 
here.  I _know_ that it isn't on a critical path, or saving a large 
quantity of program text.  I just think that it is better than it was 
before.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Bernd Eckenfels]

In article <20020707222417.GC18298@kroah.com> you wrote:
> Either way, you get my same response, "Why?"  Again, as someone stated,
> where in the USB code is the BKL used that affects performance in any
> real life situations?

AFAIK the BKL in a not often used path can still be hold too long and affect
latecy. I think the most recent low latency patches find a few instances. I
am not completly shure if that is only about interrupts, or if it applies to
the BKL, too.

Greetings
Bernd

Re: BKL removal

[Greg KH]

On Sun, Jul 07, 2002 at 05:07:05PM -0700, Dave Hansen wrote:
> 
> You are taking this example way too seriously.  Thunder wanted an 
> example and I grabbed the first one that I saw (I created it in the 
> last hour).  I showed you how I arrived at it, just a quick grepping. 
>  It wan't a real patch, only a quick little example snippet.

I know that, you're taking my response way too seriously :)
I just showed the typical response to one of your posts, you just picked
the wrong example, or maybe any USB example you could have picked would
have evicted much the same response :)

> >	- even if you remove the BKL from this code, what have you
> >	  achieved?  A faster kernel?  A very tiny bit smaller kernel,
> >	  yes, but not any faster overall.  This is not on _any_
> >	  critical path.
> 
> How many times do I have to say it?  We're going around in circles 
> here.  I _know_ that it isn't on a critical path, or saving a large 
> quantity of program text.  I just think that it is better than it was 
> before.

So you agree with me?  Good.  I know you think the code is better than
it was before, but beauty is in the eye of the beholder, or in this
case, the eye of the people that fully understand the code :)

If nothing else, I hope you will think twice before sending off your
next BKL removel patch in a subsystem that you haven't fully tested or
understood.  That's the point I keep trying to get across here.

thanks,

greg k-h

Re: BKL removal

[Matthew Wilcox]

On Sun, Jul 07, 2002 at 04:45:21PM -0700, Dave Hansen wrote:
> Don't forget that the BKL is released on sleep.  It is OK to hold it
> over a schedule()able operation.  If I remember right, there is no 
> real protection needed for the file->private_data either because there 
> is 1 and only 1 struct file per open, and the data is not shared among 
> struct files.

one struct file per open(), yes.  however, fork() shares a struct file,
as does unix domain fd passing.  so we need protection between different
processes.  there's some pretty good reasons to want to use a semaphore
to protect the struct file (see fasync code.. bleugh).

however, our semaphores currently suck.  they attempt to acquire the sem
immediately and if they fail go straight to sleep.  schimmel (i think..)
suggests spinning for a certain number of iterations before sleeping.
the great thing is, it's all out of line slowpath code so the additional
size shouldn't matter.  obviously this is SMP-only, and it does require
someone to do it who can measure the difference (and figure out how may
iterations to spin for before sleeping).

i was wondering if this might be a project you'd like to take on which
would upset far fewer people and perhaps yield greater advantage.

-- 
Revolutions do not require corporate support.

Re: BKL removal

[Dave Hansen]

Matthew Wilcox wrote:
> On Sun, Jul 07, 2002 at 04:45:21PM -0700, Dave Hansen wrote:
> 
>>Don't forget that the BKL is released on sleep.  It is OK to hold it
>>over a schedule()able operation.  If I remember right, there is no 
>>real protection needed for the file->private_data either because there 
>>is 1 and only 1 struct file per open, and the data is not shared among 
>>struct files.
> 
> one struct file per open(), yes.  however, fork() shares a struct file,
> as does unix domain fd passing.  so we need protection between different
> processes.  there's some pretty good reasons to want to use a semaphore
> to protect the struct file (see fasync code.. bleugh).

But, this at least means that we don't need to protect 
file->private_data during the open itself, right?

> however, our semaphores currently suck.  they attempt to acquire the sem
> immediately and if they fail go straight to sleep.  schimmel (i think..)
> suggests spinning for a certain number of iterations before sleeping.
> the great thing is, it's all out of line slowpath code so the additional
> size shouldn't matter.  obviously this is SMP-only, and it does require
> someone to do it who can measure the difference (and figure out how may
> iterations to spin for before sleeping).

Well, I certainly have the hardware to measure the difference.  But, I 
seem to remember several conversations in the past where people didn't 
like this behavior.
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&threadm=linux.kernel.3C62DABA.3020906%40us.ibm.com

> i was wondering if this might be a project you'd like to take on which
> would upset far fewer people and perhaps yield greater advantage.

Yes, something less controvertial, please!  A dumb implementation 
would be pretty easy on top of current semaphores, but I think it was 
already done (see above).

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Alexander Viro]

On Mon, 8 Jul 2002, Matthew Wilcox wrote:

> one struct file per open(), yes.  however, fork() shares a struct file,
> as does unix domain fd passing.  so we need protection between different
> processes.  there's some pretty good reasons to want to use a semaphore
> to protect the struct file (see fasync code.. bleugh).

??? What exactly do you want to protect there?

ObAnotherQuestion: no, new_inode() doesn't need BKL.

Re: BKL removal

[Dave Hansen]

Alexander Viro wrote:
> 
> On Mon, 8 Jul 2002, Matthew Wilcox wrote:
> 
>>one struct file per open(), yes.  however, fork() shares a struct file,
>>as does unix domain fd passing.  so we need protection between different
>>processes.  there's some pretty good reasons to want to use a semaphore
>>to protect the struct file (see fasync code.. bleugh).
> 
> ??? What exactly do you want to protect there?
> 

I think we were talking about file->private_data

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Alexander Viro]

On Sun, 7 Jul 2002, Dave Hansen wrote:

> > as does unix domain fd passing.  so we need protection between different
> > processes.  there's some pretty good reasons to want to use a semaphore
> > to protect the struct file (see fasync code.. bleugh).
> 
> But, this at least means that we don't need to protect 
> file->private_data during the open itself, right?

Correct.  Moreover, most of the struct file instances that have ->private_data
tend to set it during ->open() and never change it afterwards.
 
> > however, our semaphores currently suck.  they attempt to acquire the sem
> > immediately and if they fail go straight to sleep.  schimmel (i think..)
> > suggests spinning for a certain number of iterations before sleeping.
> > the great thing is, it's all out of line slowpath code so the additional
> > size shouldn't matter.  obviously this is SMP-only, and it does require
> > someone to do it who can measure the difference (and figure out how may
> > iterations to spin for before sleeping).

The thing being, if you are already contended you are playing "I'll release
CPU now" vs. "I'll spin in hope that contender will go away right now".

IOW, it's a win only if you get contention often and for short intervals.
Which is a very good indication that something is rotten with your locking
scheme.  Like, say it, having lost the control over the amount of locks
as the result of brainde^Woverenthusiastic belief that fine-grained ==
good.  With everything that follows from that...

Re: BKL removal

[Oliver Neukum]

>  > The BKL, unless used unbalanced, can never cause a bug. It could be
>  > insufficient or superfluous, but never be really buggy in itself.
>
> Does incredibly high lock contention qualify as a bug?

Only if it occurs at a place that is used often. Even then it's
a minor bug, while a race is always a race.

>  >> Is it really okay to "lock the whole kernel" because of one
>  >> struct file? This brings us back to spinlocks...
>  >>
>  >> You're possibly right about this one. What did Greg K-H say?
>  >
>  > I don't speak for Greg, but in this example it could be dropped
>  > IMO. The spinlock protects the critical section anyway. As a rule,
>  > if you do a kmalloc without GFP_ATOMIC under BKL you are doing
>  > either insufficient locking (you may need a semaphore) or useless
>  > locking.
>
> Don't forget that the BKL is released on sleep.  It is OK to hold it

Exactly therefore it won't protect you from reentrance if you do
something that sleeps. If that's the case, you've found a race condition.

> over a schedule()able operation.  If I remember right, there is no
> real protection needed for the file->private_data either because there
> is 1 and only 1 struct file per open, and the data is not shared among
> struct files.

But between threads. Anyway, this was an open, if you use struct file
before open returns even the BKL can't help you.

>  > This should have been posted on linux-usb long ago.
>
> I just pulled it out of thin air 10 minutes ago!

Yes, I understand. But this is a symptom. We should have heard
about it.
You need to understand that people who run UP mostly won't
care about SMP beyond making sure that the drivers are SMP-safe.
This is not true for core kernel code, but for devices outside
the block layer and perhaps some network drivers, that's the case.

So you do the greps and question locking usage on the right lists.
It's quite important, you might uncover bugs and speed up the kernel.
And you need to be persistent about it. Take your time to find out why
the lock is used. Or why it makes no sense.
You should be able to improve the locking situation that way, with respect
to BKL contention and driver quality.

	Regards
		Oliver

Re: BKL removal

[Matthew Wilcox]

On Sun, Jul 07, 2002 at 10:58:04PM -0400, Alexander Viro wrote:
> On Mon, 8 Jul 2002, Matthew Wilcox wrote:
> > one struct file per open(), yes.  however, fork() shares a struct file,
> > as does unix domain fd passing.  so we need protection between different
> > processes.  there's some pretty good reasons to want to use a semaphore
> > to protect the struct file (see fasync code.. bleugh).
> 
> ??? What exactly do you want to protect there?

andrea & i discussed this off-list a few days ago... see fs/fcntl.c

                case F_SETFL:
                        lock_kernel();
                        err = setfl(fd, filp, arg);
                        unlock_kernel();

setfl() does:

        if ((arg ^ filp->f_flags) & FASYNC) {
                if (filp->f_op && filp->f_op->fasync) {
                        error = filp->f_op->fasync(fd, filp, (arg & FASYNC) != 0);

and:

        if (arg & O_DIRECT) {
                down(&inode->i_sem);
                if (!filp->f_iobuf)
                        error = alloc_kiovec(1, &filp->f_iobuf);
                up(&inode->i_sem);

and finally:

        filp->f_flags = (arg & SETFL_MASK) | (filp->f_flags & ~SETFL_MASK);

i pointed out that if alloc_kiovec slept, the BKL provides no protection
against someone else doing a setfl at the same time, so we can get the
wrong number of fasync events sent.  Marcus Alanen pointed out that
fasync can also sleep, so we're at risk anyway.  i don't think that
abusing i_sem as andrea did is the Right Thing to do...

-- 
Revolutions do not require corporate support.

Re: BKL removal

[Matthew Wilcox]

On Sun, Jul 07, 2002 at 07:52:34PM -0700, Dave Hansen wrote:
> Well, I certainly have the hardware to measure the difference.  But, I 
> seem to remember several conversations in the past where people didn't 
> like this behavior.
> http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&threadm=linux.kernel.3C62DABA.3020906%40us.ibm.com

I think this is a very different philosophy.  That's "well, this should
be a spinlock, but sometimes we sleep, and we don't want to think about
it too hard, so let's invent a magical lock".  This is "sometimes we
don't hold semaphores for very long so we can improve performance by
spinning 1000 times before sleeping".

-- 
Revolutions do not require corporate support.

Re: BKL removal

[Matthew Wilcox]

On Sun, Jul 07, 2002 at 11:06:32PM -0400, Alexander Viro wrote:
> The thing being, if you are already contended you are playing "I'll release
> CPU now" vs. "I'll spin in hope that contender will go away right now".
> 
> IOW, it's a win only if you get contention often and for short intervals.
> Which is a very good indication that something is rotten with your locking
> scheme.  Like, say it, having lost the control over the amount of locks
> as the result of brainde^Woverenthusiastic belief that fine-grained ==
> good.  With everything that follows from that...

So let's get some numbers.  It really shouldn't be hard to make our
current semaphores spin a little before they sleep.  If we get some
numbers showing it does help then either we need this change in mainline
or we need to fix our locking.

-- 
Revolutions do not require corporate support.

Re: BKL removal

[Dave Hansen]

Matthew Wilcox wrote:
> On Sun, Jul 07, 2002 at 11:06:32PM -0400, Alexander Viro wrote:
> 
>>The thing being, if you are already contended you are playing "I'll release
>>CPU now" vs. "I'll spin in hope that contender will go away right now".
>>
>>IOW, it's a win only if you get contention often and for short intervals.
>>Which is a very good indication that something is rotten with your locking
>>scheme.  Like, say it, having lost the control over the amount of locks
>>as the result of brainde^Woverenthusiastic belief that fine-grained ==
>>good.  With everything that follows from that...
> 
> So let's get some numbers.  It really shouldn't be hard to make our
> current semaphores spin a little before they sleep.  If we get some
> numbers showing it does help then either we need this change in mainline
> or we need to fix our locking.

Sounds good to me.  Do you have any code, or a workload that you know 
will trigger it?  I have a feeling that Specweb will probably show 
this behavior, but I want something simpler.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Rick Lindsley]

    So you agree with me?  Good.  I know you think the code is better
    than it was before, but beauty is in the eye of the beholder, or in
    this case, the eye of the people that fully understand the code :)

The problem is, of course, that to responsibly use the BKL, you must
fully understand ALL the code that utilizes it, so that you know your
new use of it doesn't conflict or interfere with existing code and
usage.  That's the same problem we have when it DOES show contention --
is the problem in the functions which can't grab it (for trying
unnecessarily), or in the functions that can (for holding it
unnecessarily)?

If you are the person who understands the BKL in all its usages
throughout the kernel, then thankfully, our search is over.  We've been
looking for you to help resolve some of these discussions.  If you
aren't that person, though, then you can't accurately say your use of
it doesn't affect anybody else adversely.  All you can assert is that
in your corner of the kernel, *you* use it for X, Y, and Z and they
don't interact poorly with each other.

With a narrowly defined and used lock, it is much less difficult to
determine who uses it, what it is guarding, and what impact yet another
use of it will have.  With the BKL (and a few other poorly documented
locks which have recently been cleaned up) nobody has had a hope of
understanding the interactions.

    If nothing else, I hope you will think twice before sending off
    your next BKL removel patch in a subsystem that you haven't fully
    tested or understood.  That's the point I keep trying to get across
    here.

So can you define for me under what conditions the BKL is appropriate
to use?  Removing it from legitimate uses would be bad, of course, but
part of the problem here is that it's currently used for a variety of
unrelated purposes.

Rick

Re: BKL removal

[Greg KH]

On Mon, Jul 08, 2002 at 06:46:12PM -0700, Rick Lindsley wrote:
>     So you agree with me?  Good.  I know you think the code is better
>     than it was before, but beauty is in the eye of the beholder, or in
>     this case, the eye of the people that fully understand the code :)
> 
> The problem is, of course, that to responsibly use the BKL, you must
> fully understand ALL the code that utilizes it, so that you know your
> new use of it doesn't conflict or interfere with existing code and
> usage.  That's the same problem we have when it DOES show contention --
> is the problem in the functions which can't grab it (for trying
> unnecessarily), or in the functions that can (for holding it
> unnecessarily)?

{Sigh}

But the driverfs and USB code do _not_ show contention.  Or if they do
(as Dave pointed out in the driverfs code) it's in a non-critical
point in the kernel's life (boot time, USB device removal, etc.)

> If you are the person who understands the BKL in all its usages
> throughout the kernel, then thankfully, our search is over.  We've been
> looking for you to help resolve some of these discussions.  If you
> aren't that person, though, then you can't accurately say your use of
> it doesn't affect anybody else adversely.  All you can assert is that
> in your corner of the kernel, *you* use it for X, Y, and Z and they
> don't interact poorly with each other.

Yes, that's what I am asserting, _and_ that when my "corner" of the
kernel uses it, it doesn't really matter if ext3, ext2, or even the
entire VFS layer grinds to a halt.  No one will care, or even notice.

> So can you define for me under what conditions the BKL is appropriate
> to use?  Removing it from legitimate uses would be bad, of course, but
> part of the problem here is that it's currently used for a variety of
> unrelated purposes.

Wait!  You're still not getting it.  I'm not against removing the BKL.
I'm not saying we should add it to more places.  What I am complaining
about (and I'm not the only one) is the method that people who are
trying to remove the BKL from various kernel subsystems are using.  I
think Oliver said it best in this quote from this thread:

	So you do the greps and question locking usage on the
	right lists.  It's quite important, you might uncover
	bugs and speed up the kernel.  And you need to be
	persistent about it. Take your time to find out why
	the lock is used. Or why it makes no sense.


So please, no more "hit and run" BKL patches that break things.  Please
come offering to help, with detailed reasons why BKL usage is wrong in
the specific portions of the code, and how possibly it might be cleaned
up, with patches that have _actually been tested_.  And then
flames^Wdiscussions like this one will not happen at all.

thanks,

greg k-h

Re: BKL removal

[Drew P. Vogel]

>    If nothing else, I hope you will think twice before sending off
>    your next BKL removel patch in a subsystem that you haven't fully
>    tested or understood.  That's the point I keep trying to get across
>    here.
>
>So can you define for me under what conditions the BKL is appropriate
>to use?  Removing it from legitimate uses would be bad, of course, but
>part of the problem here is that it's currently used for a variety of
>unrelated purposes.


If the trade-offs weigh in about the same, removing the BKL from
legitimate uses in favor of a different (neither better nor worse)
approach would be more than acceptable, would it not?

Would creating a few new names for lock_kernel() and friends be
acceptable? Just a few macros to give slightly more meaningful names to
each function call for 2.5. Then take lock_kernel() entirely away (the
name, not the function), in 2.7. By 2.9 it should be able to be removed
from nearly all "inappropriate" uses. This seems like it would encourage
more  explicit usage of the BKL, while giving maintainers ample time to
comply.

Note that I have never added or removed a lock from the kernel. I am
simply thinking aloud; half hoping to be corrected.

--Drew Vogel

Re: BKL removal

[Larry McVoy]

> The problem is, of course, that to responsibly use the BKL, you must
> fully understand ALL the code that utilizes it, so that you know your
> new use of it doesn't conflict or interfere with existing code and
> usage.  

Indeed.

       v
> With a narrowly defined and used lock, it is much less difficult to
       ^

If you were talking about replacing a big lock with one lock, you
might have a point.  But you aren't.  You can't be, because by
definition if you take out the big lock you have to put in lots
of little locks.  And then you get discover all the problems that
the BKL was hiding that you just exposed by removing it.

If you think that managing those is easier than managing the BKL,
you don't understand the first thing about threading.

I think the kernel crowd is starting to sense how complex things
are getting and are pushing back a bit.  Don't fight them, this
isn't IRIX/Dynix/PTX/AIX/Solaris.  It's Linux and part of the
appeal, part of the reason you are here, is that it is (was) simple.
All you are doing is suggesting that it should be more complex.
I don't agree at all.

> So can you define for me under what conditions the BKL is appropriate
> to use?  

Can you tell me for sure that there are no races introduced by your
proposed change?

Can you tell me the list of locks and what they cover in the last 
multi threaded OS you worked in?  I thought not.  Nobody could.
-- 
---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

Re: BKL removal

[Dave Hansen]

Drew P. Vogel wrote:
>>   If nothing else, I hope you will think twice before sending off
>>   your next BKL removel patch in a subsystem that you haven't fully
>>   tested or understood.  That's the point I keep trying to get across
>>   here.
>>
>>So can you define for me under what conditions the BKL is appropriate
>>to use?  Removing it from legitimate uses would be bad, of course, but
>>part of the problem here is that it's currently used for a variety of
>>unrelated purposes.
> 
> If the trade-offs weigh in about the same, removing the BKL from
> legitimate uses in favor of a different (neither better nor worse)
> approach would be more than acceptable, would it not?

I think Greg's main protests are about the methods, not the means.

> Would creating a few new names for lock_kernel() and friends be
> acceptable? Just a few macros to give slightly more meaningful names to
> each function call for 2.5. Then take lock_kernel() entirely away (the
> name, not the function), in 2.7. By 2.9 it should be able to be removed
> from nearly all "inappropriate" uses. This seems like it would encourage
> more  explicit usage of the BKL, while giving maintainers ample time to
> comply.

I would really prefer not to see the name changed.  In some places 
people do this:

#define mydriver_lock() lock_kernel();
#define mydriver_unlock() unlock_kernel();

All that this really does is obscure the BKL's use -- it makes it 1 
step harder to track down.  If you need a spinlock, use a spinlock. 
If you need the BKL, by all means, take the BKL.

A comment is immeasurable better than a different name.  I would say, 
if you need/want the BKL, justify it with a comment, not a name.

> Note that I have never added or removed a lock from the kernel. I am
> simply thinking aloud; half hoping to be corrected.

I know the feeling :)

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Roman Zippel]

Hi,

On Mon, 8 Jul 2002, Larry McVoy wrote:

> I think the kernel crowd is starting to sense how complex things
> are getting and are pushing back a bit.  Don't fight them, this
> isn't IRIX/Dynix/PTX/AIX/Solaris.  It's Linux and part of the
> appeal, part of the reason you are here, is that it is (was) simple.
> All you are doing is suggesting that it should be more complex.
> I don't agree at all.

Why do you think it was simple before?

bye, Roman

Re: BKL removal

[Dave Hansen]

Robert Love wrote:
> On Tue, 2002-07-09 at 14:00, William Lee Irwin III wrote:
> 
> 
>>This is an ugly aspect. But AFAICT the most that's needed to clean it
>>up is an explicit release before potentially sleeping.
> 
> 
> Yep that is all we need... remove the release_kernel_lock() and
> reacquire_kernel_lock() from schedule and do it explicitly everywhere it
> is needed.
> 
> The problem is, it is needed in a _lot_ of places.  Mostly instances
> where the lock is held across something that may implicitly sleep.

And _that_ is why I wrote the BKL debugging patch, to help find these 
places at runtime.  It may not be pretty, but it works.  I'll post it 
again if you're interested.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Dave Hansen]

Robert Love wrote:
> On Tue, 2002-07-09 at 07:19, Dave Hansen wrote:
> 
>>Robert Love wrote:
>>
>>>The problem is, it is needed in a _lot_ of places.  Mostly instances
>>>where the lock is held across something that may implicitly sleep.
>>
>>And _that_ is why I wrote the BKL debugging patch, to help find these 
>>places at runtime.  It may not be pretty, but it works.  I'll post it 
>>again if you're interested.
> 
> I saw the patch... the problem is we cannot say "oh I ran this code path
> with the patch and did not see anything, it is safe".  Can sleep != will
> sleep, and thus we have code that 99% will not sleep but it may.

That's a good point, but we have to start somewhere.  I think this is 
a reasonable way to start looking for bad behavior.  Since you have to 
fix all of them anyway, why not let the easy bunch come to you instead 
of seeking them out?  In a couple of kernel versions, I'd like to make 
it a BUG() to use the BKL in a nested fashion, or hold it during a 
schedule.  I think that his would be a reasonable thing to do during 
the early days of the first development series after we think we have 
this thing licked.  But, that is admittedly ages from now in kernel 
time.

The Stanford Checker or something resembling it would be invaluable 
here.  It would be a hell of a lot better than my litle patch!

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Rick Lindsley]

I wrote:

    > The problem is, of course, that to responsibly use the BKL, you must
    > fully understand ALL the code that utilizes it, so that you know your
    > new use of it doesn't conflict or interfere with existing code and
    > usage.  That's the same problem we have when it DOES show contention --
    > is the problem in the functions which can't grab it (for trying
    > unnecessarily), or in the functions that can (for holding it
    > unnecessarily)?
    
Greg responded:

    But the driverfs and USB code do _not_ show contention.  Or if they
    do (as Dave pointed out in the driverfs code) it's in a
    non-critical point in the kernel's life (boot time, USB device
    removal, etc.)

Ok, I think this underscores something I haven't seen clearly stated
here before.  Yes, if you can demonstrate contention, you have a
problem that needs fixing, and I think few would argue it shouldn't be
addressed.

However, I look at this from a supportability point of view as well --
a lock such as the BKL which is used for multiple reasons by multiple
subsystems, when it DOES show contention, is harder to fix.  People
trying to fix old code wonder if a particular section really needs the
BKL, and give up figuring it out because its too hard.

So while contention can bring a lot of (unwanted) attention to a
spinlock, including the BKL, I want to see the BKL reduced even if it's
NOT showing contention, because it makes it easier to debug the cases
where it IS being used.  Unless a developer is relying on the
release-on-sleep mechanism or the nested-locks-without-deadlock
mechanism, there's no reason an instance of the BKL can't be replaced
with another spinlock.

Arguing that efforts to replace it have indicated we don't know
how it is really used just supports my point.  I don't think anybody
exists who can claim (or will admit :) that they know why the BKL is
used everywhere it is.  We either need to develop that person (and keep
them safe from harm!) or make it easier to understand "on the fly".
I believe that reducing the varied usages, even harmless ones", will
make it easier to either clearly document the remaining usages or
to understand it "on the fly".

Rick

Re: BKL removal

[Rick Lindsley]

    Wait!  You're still not getting it.  I'm not against removing the
    BKL.  I'm not saying we should add it to more places.  What I am
    complaining about (and I'm not the only one) is the method that
    people who are trying to remove the BKL from various kernel
    subsystems are using.

    [ ... ]

    So please, no more "hit and run" BKL patches that break things.
    Please come offering to help, with detailed reasons why BKL usage
    is wrong in the specific portions of the code, and how possibly it
    might be cleaned up, with patches that have _actually been
    tested_.

I understand.  But there's a bit of a problem here.  We don't have
every device available to us that uses the BKL.  The maintainers, I
presume, do.  While we can inspect to our little hearts' content, and
code up "obviously" correct patches, nothing really tests it like,
well, testing it.  In the past, in writing to maintainers, we have
sometimes found that a) they ignore email that does not include actual
patches, or b) they don't know themselves if it is safe, and are afraid
or unwilling to try it themselves.  So there's no means to discuss
changes, no means to test them, and (some) maintainers then refuse to
apply ANY changes.

(Others take the opposite approach, and apply anything that looks like
a patch -- ALSO probably not the desired result :)

This is not to say that you, as a maintainer, behave this way.  But we
HAVE observed this behavior in our efforts.  What is the proper
response when a maintainer won't apply a change, won't help test it,
and won't even help derive a correct one?  About all that's left at
that point, it seems, is to provide a patch, appeal to the community at
large, and ask them to try it or comment upon it.

Rick

Re: BKL removal

[Greg KH]

On Tue, Jul 09, 2002 at 12:33:13PM -0700, Rick Lindsley wrote:
>     Wait!  You're still not getting it.  I'm not against removing the
>     BKL.  I'm not saying we should add it to more places.  What I am
>     complaining about (and I'm not the only one) is the method that
>     people who are trying to remove the BKL from various kernel
>     subsystems are using.
> 
>     [ ... ]
> 
>     So please, no more "hit and run" BKL patches that break things.
>     Please come offering to help, with detailed reasons why BKL usage
>     is wrong in the specific portions of the code, and how possibly it
>     might be cleaned up, with patches that have _actually been
>     tested_.
> 
> I understand.  But there's a bit of a problem here.  We don't have
> every device available to us that uses the BKL.

Wait.  The patches I specifically mention are in regards to devices that
both of you should have access to.  If not, you could have simply walked
over and asked me for one.  A single USB mouse or keyboard would have
proved that both the input and the driverfs patches were wrong.  Since
the patch was for these types of subsystems, not even attempting to test
it out is indefensible.

> The maintainers, I presume, do.

This too is incorrect.  I do not have some devices for drivers that I
have created and maintain.  I think this is also true for the majority
of the joystick drivers.  Granted, this isn't the best thing, but
companies aren't giving us free devices to write our free drivers for.
We rely on users for testing sometimes (debugging through email does
work, albeit slowly :)

> What is the proper response when a maintainer won't apply a change,
> won't help test it, and won't even help derive a correct one?

Post it to a public mailing list (like lkml) where people in general
care about these things.  Enough hounding will either shame the
maintainer into replying, or you might find yourself becoming the
maintainer if no one steps up (like ATM :)


greg k-h

Re: BKL removal

[Greg KH]

On Tue, Jul 09, 2002 at 12:31:13PM -0700, Rick Lindsley wrote:
> Unless a developer is relying on the release-on-sleep mechanism or the
> nested-locks-without-deadlock mechanism, there's no reason an instance
> of the BKL can't be replaced with another spinlock.

Um, not true.  You can call schedule with the BKL held, not true for a
spinlock.

And see the oft repeated messages on lkml about the spinlock/semaphore
hell that some oses have turned into when they try to do this.  Let's
learn from history this time around please.

greg k-h

Re: BKL removal

[Dave Hansen]

Alexander Viro wrote:
> 
> On Tue, 9 Jul 2002, Arnaldo Carvalho de Melo wrote:
> 
>>Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
>>
>>>On Tue, 2002-07-09 at 07:44, Dave Hansen wrote:
>>>
>>>>The Stanford Checker or something resembling it would be invaluable 
>>>>here.  It would be a hell of a lot better than my litle patch!
>>>
>>>The Stanford Checker would be infinitely invaluable here -- agreed.
>>>
>>>Anything that can graph call chains and do analysis... we can get it to
>>>tell us exactly who and what.
> 
> Not anything.  It can be used to find problems (and be very helpful at that)
> but it can't be used to verify anything.
> 
> The problem is that checker doesn't (and cannot) cover all code paths -
> by the time when it comes into the game the source had already passed
> through through cpp.  In other words, depending on the configuration
> you might get very different results.

I have the feeling that the filesystems' use of lots of function 
pointers will add a large amount of complexity to whatever programming 
any checker would require.  Bill Irwin and I were discussing it and we 
have ways of getting around most of them, but there are _lots_ of 
special cases.

   "Proving" correctness would obviously be ideal, but in an imperfect 
world, what are your feelings on a runtime system for detecting 
"magical/bad" BKL use?  I'm not proposing my kludgy "printk if you're 
bad" stuff, but something with much less impact.  I would like to do 
something somewhat like profile=2.  During each lock_kernel(), the 
program counter (any maybe more) could be stored in an internal kernel 
structure and retrieved later via a /proc file, just like readprofile. 
    This wouldn't have intrusive printk messages, and would be able to 
be activated by either a command-line parameter, or something else in 
/proc.  If we had this in our development kernel, interested 
developers could pay attention to the output, while the normal kernel 
developer could simply ignore it.

> Normally it's not that bad, but "can this function block?" is very nasty
> in that respect - changes of configuration can and do affect that in
> non-trivial ways.

I also wonder how it handles things like kmalloc(), which can block 
depending on arguments.

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Rick Lindsley]

I wrote:

    > Unless a developer is relying on the release-on-sleep mechanism or the
    > nested-locks-without-deadlock mechanism, there's no reason an instance
    > of the BKL can't be replaced with another spinlock.
    
Greg replied:

    Um, not true.  You can call schedule with the BKL held, not true for a
    spinlock.

Well, this is what I meant by the release-on-sleep.  When you go to
sleep, the BKL is actually released in the scheduler.

Anything which is relying on this behavior needs to be redesigned.  It
is holding, at best, an advisory lock.  The lock, after all, is only in
effect until you go to sleep.  No other lock behaves this way.  Is
there any code in the kernel which MUST have this feature? The code
should be written so that the code itself releases any locks it holds
before putting itself to sleep.  "magic" which happens simply because
you down'ed a semaphore is just more obfuscated code to the uninitiated
and more trouble to even the informed.

    And see the oft repeated messages on lkml about the
    spinlock/semaphore hell that some oses have turned into when they
    try to do this.  Let's learn from history this time around please.

Fire burns, but we seem to have gotten a handle on it.

Proper locking is hard, but that's not a reason to ignore it.  Be
careful, yes.  Avoid, no.

Rick

Re: BKL removal

[William Lee Irwin III]

On Tue, Jul 09, 2002 at 01:55:55PM -0700, Rick Lindsley wrote:
> Well, this is what I meant by the release-on-sleep.  When you go to
> sleep, the BKL is actually released in the scheduler.
> Anything which is relying on this behavior needs to be redesigned.  It

This is an ugly aspect. But AFAICT the most that's needed to clean it
up is an explicit release before potentially sleeping.


Cheers,
Bill

Re: BKL removal

[Robert Love]

On Tue, 2002-07-09 at 14:00, William Lee Irwin III wrote:

> This is an ugly aspect. But AFAICT the most that's needed to clean it
> up is an explicit release before potentially sleeping.

Yep that is all we need... remove the release_kernel_lock() and
reacquire_kernel_lock() from schedule and do it explicitly everywhere it
is needed.

The problem is, it is needed in a _lot_ of places.  Mostly instances
where the lock is held across something that may implicitly sleep.

Places that call schedule() explicitly holding the BKL are rare enough
we can probably handle them.  I have a patch that does so (thus turning
all cond_resched() calls into no-ops with the preemptive kernel -- my
goal).  The other implicit situations are near impossible to handle.

Summary is, I would love to do things like dismantle the BKLs odd-ball
features... cleanly and safely.  Good luck ;)

	Robert Love

Re: BKL removal

[Robert Love]

On Tue, 2002-07-09 at 07:19, Dave Hansen wrote:

> Robert Love wrote:
>
> > The problem is, it is needed in a _lot_ of places.  Mostly instances
> > where the lock is held across something that may implicitly sleep.
> 
> And _that_ is why I wrote the BKL debugging patch, to help find these 
> places at runtime.  It may not be pretty, but it works.  I'll post it 
> again if you're interested.

I saw the patch... the problem is we cannot say "oh I ran this code path
with the patch and did not see anything, it is safe".  Can sleep != will
sleep, and thus we have code that 99% will not sleep but it may.

I suspect on my 1GB machine I rarely page fault on copy_*_user but that
does not mean it could not sleep.

If you find all the culprits and think you can safely remove the
release/reacquire routines from schedule, all the power to you.

	Robert Love

Re: BKL removal

[Robert Love]

On Tue, 2002-07-09 at 07:44, Dave Hansen wrote:

> The Stanford Checker or something resembling it would be invaluable 
> here.  It would be a hell of a lot better than my litle patch!

The Stanford Checker would be infinitely invaluable here -- agreed.

Anything that can graph call chains and do analysis... we can get it to
tell us exactly who and what.

	Robert Love

Re: BKL removal

[William Lee Irwin III]

On Tue, Jul 09, 2002 at 02:12:55PM -0700, Robert Love wrote:
> Summary is, I would love to do things like dismantle the BKLs odd-ball
> features... cleanly and safely.  Good luck ;)

This is even automatable. "Can doing this schedule me away?" and "Is
the BKL held here?" can be handled by machines just fine so long as the
answer to the latter is not "sometimes", and when it is, it can be auto-
identified and fixed up by hand. Given something that can parse a cscope
database and maybe do some transitive closure operations on subgraphs of
the call graph this should be doable in a few days on decent hardware.
There's also a nice advantage in it being harder to screw up than removal.

Callbacks can of course be handled by relaxing the condition to "may call"
and propagating values around, though that might be done better by
stealing a lint front end as opposed to a cscope database, especially for
taking advantage of type information. For instance, the callbacks will be
a component with a given name in a struct of a given type. So finding the
set of all functions assigned to that component of a variable having that
struct as its type should suffice to bang out the "may call" relation then.

All of the above actually applies to "call function F under lock L", so
the effort could be reused to, for instance, find sleep under spinlock
scenarios, or failures to hold L while calling F. Last, but not least,
it may well be the case that all the code has already been written, and
is waiting for someone to use it. There are some open-source static
checkers coming out it seems.

... if only it weren't such a PITA to write...

Cheers,
Bill

Re: BKL removal

[Alan Cox]

> Places that call schedule() explicitly holding the BKL are rare enough
> we can probably handle them.  I have a patch that does so (thus turning
> all cond_resched() calls into no-ops with the preemptive kernel -- my
> goal).  The other implicit situations are near impossible to handle.

There are lots of them hiding 8)

> Summary is, I would love to do things like dismantle the BKLs odd-ball
> features... cleanly and safely.  Good luck ;)

You can actually do it with some testing to catch the missed cases. Move
them to spinlocks, lob a check if the lock is held into the schedule code
run it for a while through its various code paths, then remove the debug
once you trust it

Re: BKL removal

[Pavel Machek]

Hi!

> > I would mind the BKL a lot less if it was as well understood 
> > everywhere as it is in VFS.  The funny part is that a lock like the 
> > BKL would not last very long if it were well understood or documented 
> > everywhere it was used.
> 
> I would mind it a whole lot less if when you try to remove the BKL, you
> do it correctly.  So far it seems like you enjoy doing "hit and run"
> patches, without even fully understanding or testing your patches out
> (the driverfs and input layer patches are proof of that.)  This does
> nothing but aggravate the developers who have to go clean up after you.
> 
> Also, stay away from instances of it's use WHERE IT DOES NOT MATTER for
> performance.  If I grab the BKL on insertion or removal of a USB device,
> who cares?  I know you are trying to remove it entirely out of the

Well, BKL has some rather nasty semantics (release over schedule(),
IIRC), so killing it completely would simplify both documentation and
code.
								Pavel
-- 
Worst form of spam? Adding advertisment signatures ala sourceforge.net.
What goes next? Inserting advertisment *into* email?

Re: BKL removal

[Arnaldo Carvalho de Melo]

Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
> On Tue, 2002-07-09 at 07:44, Dave Hansen wrote:
> 
> > The Stanford Checker or something resembling it would be invaluable 
> > here.  It would be a hell of a lot better than my litle patch!
> 
> The Stanford Checker would be infinitely invaluable here -- agreed.
> 
> Anything that can graph call chains and do analysis... we can get it to
> tell us exactly who and what.

Try smatch:

http://smatch.sf.net

And see if you can write a smatch script to get a good broom for this trash 8)

- Arnaldo

Re: BKL removal

[Alexander Viro]

On Tue, 9 Jul 2002, Arnaldo Carvalho de Melo wrote:

> Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
> > On Tue, 2002-07-09 at 07:44, Dave Hansen wrote:
> > 
> > > The Stanford Checker or something resembling it would be invaluable 
> > > here.  It would be a hell of a lot better than my litle patch!
> > 
> > The Stanford Checker would be infinitely invaluable here -- agreed.
> > 
> > Anything that can graph call chains and do analysis... we can get it to
> > tell us exactly who and what.

Not anything.  It can be used to find problems (and be very helpful at that)
but it can't be used to verify anything.

The problem is that checker doesn't (and cannot) cover all code paths -
by the time when it comes into the game the source had already passed
through through cpp.  In other words, depending on the configuration
you might get very different results.

Normally it's not that bad, but "can this function block?" is very nasty
in that respect - changes of configuration can and do affect that in
non-trivial ways.  Checker can be _very_ useful since it allows to catch
some of the existing bugs, but it should not be used as a justification
of change that might introduce bugs if some assumption ever becomes false.

> Try smatch:
> 
> http://smatch.sf.net
> 
> And see if you can write a smatch script to get a good broom for this trash 8)

Re: BKL removal

[Alexander Viro]

On Tue, 9 Jul 2002, Dave Hansen wrote:

> I have the feeling that the filesystems' use of lots of function 
> pointers will add a large amount of complexity to whatever programming 
> any checker would require.  Bill Irwin and I were discussing it and we 
> have ways of getting around most of them, but there are _lots_ of 
> special cases.

The real complexity is _not_ on compiler level.  Checker manages that
quite fine.  The problem is in the coverage - making sure that code
gets to compiler is much, much more painful.
 
> > Normally it's not that bad, but "can this function block?" is very nasty
> > in that respect - changes of configuration can and do affect that in
> > non-trivial ways.
> 
> I also wonder how it handles things like kmalloc(), which can block 
> depending on arguments.

Not a big deal - checker can be taught how kmalloc() works (normally we
either pass it explict constant or an argument of calling function -
without any changes).

Again, the real mess is due to the way we use cpp.  It would be wonderful if
we had 4-6 options really affecting stuff (changing structure sizes, etc.)
and everything else would be handled either on compiler (
	if (CONFIG_FOO) {
		...
	}
and let compiler eliminate dead branches) or on the linker (
obj-$(CONFIG_BAR) += bar.o
) level.  Then the life would be _way_ easier and we would really have
a chance to do a meaningful coverage.

As it is, we have way too many ifdefs to hope that any automated tool
would be able to cope with the damn thing.  It used to be worse -
these days several really nasty piles of ifdefs are gone.  However,
we still have quite a few remaining.

Quick-and-dirty search shows ~1.2e4 ifdefs on CONFIG_... in the tree.
Most of them - patently ridiculous (random example: fs/ncpfs/symlink.c
/*
 <usual comments in the beginning>
 */

#include <linux/config.h>

#ifdef CONFIG_NCPFS_EXTRAS
<lots of stuff>
#endif

/* ----- EOF ----- */ 

which should be

ifneq ($(CONFIG_NCPFS_EXTRAS),n)
ifneq ($(CONFIG_NCPFS_EXTRAS),)
ncpfs-objs += symlink.o
endif
endif

in Makefile and none of the crap in symlink.c).

However, there's really bad stuff and it also has to be dealt with...

Re: BKL removal

[Marco Colombo]

[kernel-janitor people please Cc: me if you're going to remove l-k from
the Cc: list]

On Mon, 8 Jul 2002, Larry McVoy wrote:

[...]
> If you were talking about replacing a big lock with one lock, you
> might have a point.  But you aren't.  You can't be, because by
> definition if you take out the big lock you have to put in lots
> of little locks.  And then you get discover all the problems that
> the BKL was hiding that you just exposed by removing it.

[...]
> Can you tell me the list of locks and what they cover in the last 
> multi threaded OS you worked in?  I thought not.  Nobody could.

Larry, there's something I've always wanted to ask you about your
idea of the "locking cliff": when you're counting the number of locks,
are you looking at the running image of an OS or at the source? 
I mean, suppose we have a file object, with its private lock used
to protect access to its "internals" (whatever that means): of course
we may have thousands of these locks living in the running image of
the OS at a given time (most of them unused, BTW). At source level,
it is only one lock, instead. So are you worried about the proliferation
of locks in the source or in the live image of the OS? (I can see 
arguments against both.)

.TM.
-- 
      ____/  ____/   /
     /      /       /			Marco Colombo
    ___/  ___  /   /		      Technical Manager
   /          /   /			 ESI s.r.l.
 _____/ _____/  _/		       Colombo@ESI.it

Re: BKL removal

[Sandy Harris]

Alexander Viro wrote:

> Again, the real mess is due to the way we use cpp. ...
> 
> As it is, we have way too many ifdefs to hope that any automated tool
> would be able to cope with the damn thing.  It used to be worse -
> these days several really nasty piles of ifdefs are gone.  However,
> we still have quite a few remaining.
> 
> Quick-and-dirty search shows ~1.2e4 ifdefs on CONFIG_... in the tree.
> Most of them - patently ridiculous ...

There's a classic Usenix paper "#ifdef Considered Harmful":
http://www.google.ca/search?q=cache:kOjOJGuyArgC:www.literateprogramming.com/ifdefs.pdf+ifdef+considered+harmful&hl=en&ie=UTF-8

Re: BKL removal

[jlnance]

On Tue, Jul 09, 2002 at 11:21:25PM +0100, Alan Cox wrote:
> 
> There are lots of them hiding 8)

Just out of curisoty.  If I remember correctly SMP came to Linux when
Caldera hired you to make it work.  Did you invent the BKL?

Thanks,

Jim

Re: BKL removal

[Alan Cox]

> On Tue, Jul 09, 2002 at 11:21:25PM +0100, Alan Cox wrote:
> > 
> > There are lots of them hiding 8)
> 
> Just out of curisoty.  If I remember correctly SMP came to Linux when
> Caldera hired you to make it work.  Did you invent the BKL?

Caldera bought the hardware, rather than hiring me. Having said that at
the time the dual P90 board + processors was not exactly cheap. The board
btw is alive and well and currently owned by Dave Jones.

As far as the locking goes I invented the big kernel lock, but the basis of
that is all taken directly from "Unix systems for modern architectures"
by Schimmel which is required reading for anyone who cares about caches,
SMP and locking. 

	I'd prefer the trees to be separate for testing purposes: it 
	doens't	make much sense to have SMP support as a normal kernel 
	feature when most people won't have SMP anyway"
			-- Linus Torvalds

Alan

Re: BKL removal

[Matthew Wilcox]

On Wed, Jul 10, 2002 at 12:03:08PM +0200, Marco Colombo wrote:
> Larry, there's something I've always wanted to ask you about your
> idea of the "locking cliff": when you're counting the number of locks,
> are you looking at the running image of an OS or at the source? 

Larry normally talks about the number of conceptual locks.  So in order
to manipulate a `struct file', it really doesn't matter whether you have
to grab the BKL, the files_struct lock or the filp->lock.  There's a big
difference if you have to grab the filp->pos_lock, the filp->ra_lock and
the filp->iobuf_lock.  You'd have to know what order to grab them in,
for a start.

-- 
Revolutions do not require corporate support.

Re: BKL removal

[William Lee Irwin III]

On Wed, Jul 10, 2002 at 12:03:08PM +0200, Marco Colombo wrote:
>> Larry, there's something I've always wanted to ask you about your
>> idea of the "locking cliff": when you're counting the number of locks,
>> are you looking at the running image of an OS or at the source? 

On Wed, Jul 10, 2002 at 03:40:03PM +0100, Matthew Wilcox wrote:
> Larry normally talks about the number of conceptual locks.  So in order
> to manipulate a `struct file', it really doesn't matter whether you have
> to grab the BKL, the files_struct lock or the filp->lock.  There's a big
> difference if you have to grab the filp->pos_lock, the filp->ra_lock and
> the filp->iobuf_lock.  You'd have to know what order to grab them in,
> for a start.

This is called "lock depth" and is not related to the total number of
locks declared in the source. AFAIK no one wants to increase lock depth.


Cheers,
Bill

Re: BKL removal

[Rick Lindsley]

I wrote:
           v
    > With a narrowly defined and used lock, it is much less difficult to
           ^
    
Larry responded:
    If you were talking about replacing a big lock with one lock, you
    might have a point.  But you aren't.  You can't be, because by
    definition if you take out the big lock you have to put in lots
    of little locks.  And then you get discover all the problems that
    the BKL was hiding that you just exposed by removing it.

And this is bad ... how? A bad locking mechanism, or incorrect usage of
a good one, is exposed. Should it not be?
    
    If you think that managing those is easier than managing the BKL,
    you don't understand the first thing about threading.

So threading is difficult to manage or even impossible without a global
lock for everyone to use? True -- I suppose that would force people to
think about what they are locking and which lock is appropriate to avoid
unnecessary contention.  It would require that the new locks' scopes and
assumptions be documented instead of handed down verbally from 
teacher to student.  It would have the side effect of making it easier
for a newcomer to come up to speed on a particular section of code, thus
allowing a greater number of people to understand the code and offer fixes
or enhancements.
    
    I think the kernel crowd is starting to sense how complex things
    are getting and are pushing back a bit.  Don't fight them, this
    isn't IRIX/Dynix/PTX/AIX/Solaris.

In some ways, that's a shame.  All of those have valuable parts to them.

    It's Linux and part of the
    appeal, part of the reason you are here, is that it is (was) simple.

Feel free to return to version 7 anytime. Life was simpler with single
cpus and only physical memory.  It is true that more complex hardware
has demanded more complex software.

    All you are doing is suggesting that it should be more complex.
    I don't agree at all.

I respect your right to disagree, but I contest the assertion that
"all" we are doing is making it more complex.  In general, finer
grained locking is a good thing, as it isolates contention (both
present AND future) in areas that truly are contending for the same
resource.  As with all things, it is possible to overdo it.  While
certainly true on SMP machines, this is especially underscored with
NUMA machines.  Sometimes the cost of allowing other processors to have
access to a lock or set of data (and the attendant flushing and
reloading of caches) can actually make it more efficient to hold the
lock longer than is necessary for the simple operation you are
attempting.  This is the exception, however, not the rule, and is not a
reason to abandon finer-grained locking.

    > So can you define for me under what conditions the BKL is appropriate
    > to use?  
    
    Can you tell me for sure that there are no races introduced by your
    proposed change?

In many cases, no more than you can tell me, "for sure", what the
weather will be tomorrow.  I can tell you, after inspection, that I
*believe* there are no races and you would learn, after enough times,
that I'm right more often than not.  You'd learn that my word (and the
implied testing behind it) is sufficient. I don't expect anybody to
grant that right off. And even then, the world will find I'm still
wrong sometimes. This truly is the way Linux is supported now.

(And you can replace "I" with, I think, about any Linux luminary.)

The reason I asked the question is to point out that nobody CAN answer
it today.  That's bad.  Every subsystem should have either a maintainer
who can answer these sorts of questions, or clear documentation that
answers it for us. The BKL has (unfortunately) evolved beyond that.

This is exactly the supportability issue that reduction of the BKL will
address. Replacing an instance of it with a well-defined,
well-documented lock should make the new lock's use obvious to
newcomers, and the BKL's remaining uses marginally easier to
understand.

    Can you tell me the list of locks and what they cover in the last
    multi threaded OS you worked in?  I thought not.  Nobody could.

Off the top of my head? no. I'm not a walking encyclopedia.  From
comments and supporting documentation and supporting staff?  about
80%.  The 20% that could not be clearly identified tended to provide a
disproportionate number of bugs, and I think most people agreed they
were undesirable from a support standpoint.

Your argument seems to be, "things are very complicated right now but
they often work, so let's not change anything."  I would argue that
unless these things ARE understood, we are destined to spend a lot of
time uncovering bugs in the future -- so let's improve it now.

Rick

Re: BKL removal

[Daniel Phillips]

On Wednesday 10 July 2002 23:28, Rick Lindsley wrote:
> So threading is difficult to manage or even impossible without a global
> lock for everyone to use? True -- I suppose that would force people to
> think about what they are locking and which lock is appropriate to avoid
> unnecessary contention.  It would require that the new locks' scopes and
> assumptions be documented instead of handed down verbally from 
> teacher to student.

Hear hear!  Well, Al at least has made a pretty good attempt to do that
for VFS locks.  The rest of the kernel is pretty much a disaster.  If
we're lucky, we find the odd comment here and there: 'must be called
holding such-and-such lock', and on a good day the comment is even
correct.  Which reminds me of a janitorial idea I discussed briefly with
Acme, which is to replace all those above-the-function lock coverage
comments with assert-like thingies:

   spin_assert(&pagemap_lru_lock);

And everbody knows what that does: when compiled with no spinlock
debugging it does nothing, but with spinlock debugging enabled, it oopses
unless pagemap_lru_lock is held at that point in the code.  The practical
effect of this is that lots of 3 line comments get replaced with a
one line assert that actually does something useful.  That is, besides
documenting the lock coverage, this thing will actually check to see if
you're telling the truth, if you ask it to.

Oh, and they will stay up to date much better than the comments do,
because nobody needs to to be an ueber-hacker to turn on the option and
post any resulting oopses to lkml.

> It would have the side effect of making it easier
> for a newcomer to come up to speed on a particular section of code, thus
> allowing a greater number of people to understand the code and offer fixes
> or enhancements.

Yup, and double-yup.

-- 
Daniel

Re: spinlock assertion macros

[Jesse Barnes]

On Thu, Jul 11, 2002 at 12:24:06AM +0200, Daniel Phillips wrote:
> Acme, which is to replace all those above-the-function lock coverage
> comments with assert-like thingies:
> 
>    spin_assert(&pagemap_lru_lock);
> 
> And everbody knows what that does: when compiled with no spinlock
> debugging it does nothing, but with spinlock debugging enabled, it oopses
> unless pagemap_lru_lock is held at that point in the code.  The practical
> effect of this is that lots of 3 line comments get replaced with a
> one line assert that actually does something useful.  That is, besides
> documenting the lock coverage, this thing will actually check to see if
> you're telling the truth, if you ask it to.
> 
> Oh, and they will stay up to date much better than the comments do,
> because nobody needs to to be an ueber-hacker to turn on the option and
> post any resulting oopses to lkml.

Sounds like a great idea to me.  Were you thinking of something along
the lines of what I have below or perhaps something more
sophisticated?  I suppose it would be helpful to have the name of the
lock in addition to the file and line number...

Jesse


diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
--- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
+++ linux-2.5.25-spinassert/fs/inode.c	Wed Jul 10 16:30:18 2002
@@ -183,6 +183,8 @@
  */
 void __iget(struct inode * inode)
 {
+	spin_assert_locked(&inode_lock);
+
 	if (atomic_read(&inode->i_count)) {
 		atomic_inc(&inode->i_count);
 		return;
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
--- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
+++ linux-2.5.25-spinassert/include/linux/spinlock.h	Wed Jul 10 16:20:06 2002
@@ -118,6 +118,18 @@
 
 #endif /* !SMP */
 
+/*
+ * Simple lock assertions for debugging and documenting where locks need
+ * to be locked/unlocked.
+ */
+#ifdef CONFIG_DEBUG_SPINLOCK
+#define spin_assert_locked(lock)		if (!spin_is_locked(lock)) { printk("lock assertion failure: lock at %s:%d should be locked!\n", __FILE__, __LINE__); }
+#define spin_assert_unlocked(lock)		if (spin_is_locked(lock)) { printk("lock assertion failure: lock at %s:%d should be unlocked!\n", __FILE__, __LINE__); }
+#else
+#define spin_assert_locked(lock)		do { } while(0)
+#define spin_assert_unlocked(lock)		do { } while(0)
+#endif /* CONFIG_DEBUG_SPINLOCK */
+
 #ifdef CONFIG_PREEMPT
 
 asmlinkage void preempt_schedule(void);

Re: spinlock assertion macros

[Andreas Dilger]

On Jul 10, 2002  16:36 -0700, Jesse Barnes wrote:
> Sounds like a great idea to me.  Were you thinking of something along
> the lines of what I have below or perhaps something more
> sophisticated?  I suppose it would be helpful to have the name of the
> lock in addition to the file and line number...
> 
> Jesse
> 
> 
> diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
> --- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
> +++ linux-2.5.25-spinassert/fs/inode.c	Wed Jul 10 16:30:18 2002
> @@ -183,6 +183,8 @@
>   */
>  void __iget(struct inode * inode)
>  {
> +	spin_assert_locked(&inode_lock);
> +
>  	if (atomic_read(&inode->i_count)) {
>  		atomic_inc(&inode->i_count);
>  		return;
> diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
> --- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
> +++ linux-2.5.25-spinassert/include/linux/spinlock.h	Wed Jul 10 16:20:06 2002
> @@ -118,6 +118,18 @@
>  
>  #endif /* !SMP */
>  
> +/*
> + * Simple lock assertions for debugging and documenting where locks need
> + * to be locked/unlocked.
> + */
> +#ifdef CONFIG_DEBUG_SPINLOCK
> +#define spin_assert_locked(lock)	if (!spin_is_locked(lock)) { printk("lock assertion failure: lock at %s:%d should be locked!\n", __FILE__, __LINE__); }

You can use CPP to add in the lock name like:

#define spin_assert_locked(lock)	if (!spin_is_locked(lock))	\
	printk("lock assertion error: %s:%d: " #lock			\
	       " should be locked!\n", __FILE__, __LINE__)

#define spin_assert_unlocked(lock)	if (!spin_is_locked(lock))	\
	printk("lock assertion error: %s:%d: " #lock			\
	       " should be unlocked!\n", __FILE__, __LINE__)

Cheers, Andreas
--
Andreas Dilger
http://www-mddsp.enel.ucalgary.ca/People/adilger/
http://sourceforge.net/projects/ext2resize/

Re: spinlock assertion macros

[Jesse Barnes]

On Wed, Jul 10, 2002 at 06:54:24PM -0600, Andreas Dilger wrote:
> You can use CPP to add in the lock name like:
> 
> #define spin_assert_locked(lock)	if (!spin_is_locked(lock))	\
> 	printk("lock assertion error: %s:%d: " #lock			\
> 	       " should be locked!\n", __FILE__, __LINE__)
> 
> #define spin_assert_unlocked(lock)	if (!spin_is_locked(lock))	\
> 	printk("lock assertion error: %s:%d: " #lock			\
> 	       " should be unlocked!\n", __FILE__, __LINE__)

Oh yeah, I should have done that the first time.  How does this look?

Thanks,
Jesse


diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
--- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
+++ linux-2.5.25-spinassert/fs/inode.c	Wed Jul 10 16:30:18 2002
@@ -183,6 +183,8 @@
  */
 void __iget(struct inode * inode)
 {
+	spin_assert_locked(&inode_lock);
+
 	if (atomic_read(&inode->i_count)) {
 		atomic_inc(&inode->i_count);
 		return;
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
--- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
+++ linux-2.5.25-spinassert/include/linux/spinlock.h	Wed Jul 10 18:05:13 2002
@@ -118,6 +118,22 @@
 
 #endif /* !SMP */
 
+/*
+ * Simple lock assertions for debugging and documenting where locks need
+ * to be locked/unlocked.
+ */
+#if defined(CONFIG_DEBUG_SPINLOCK) && defined(SMP)
+#define spin_assert_locked(lock)		if (!spin_is_locked(lock)) { \
+	printk("lock assertion failure: %s:%d lock " #lock \
+		"should be locked!\n", __FILE__, __LINE__); }
+#define spin_assert_unlocked(lock)		if (spin_is_locked(lock)) { \
+	printk("lock assertion failure: %s:%d lock " #lock \
+		"should be unlocked!\n", __FILE__, __LINE__); }
+#else
+#define spin_assert_locked(lock)		do { } while(0)
+#define spin_assert_unlocked(lock)		do { } while(0)
+#endif /* CONFIG_DEBUG_SPINLOCK && SMP */
+
 #ifdef CONFIG_PREEMPT
 
 asmlinkage void preempt_schedule(void);

Re: spinlock assertion macros

[Daniel Phillips]

On Thursday 11 July 2002 01:36, Jesse Barnes wrote:
> On Thu, Jul 11, 2002 at 12:24:06AM +0200, Daniel Phillips wrote:
> > Acme, which is to replace all those above-the-function lock coverage
> > comments with assert-like thingies:
> > 
> >    spin_assert(&pagemap_lru_lock);
> > 
> > And everbody knows what that does: when compiled with no spinlock
> > debugging it does nothing, but with spinlock debugging enabled, it oopses
> > unless pagemap_lru_lock is held at that point in the code.  The practical
> > effect of this is that lots of 3 line comments get replaced with a
> > one line assert that actually does something useful.  That is, besides
> > documenting the lock coverage, this thing will actually check to see if
> > you're telling the truth, if you ask it to.
> > 
> > Oh, and they will stay up to date much better than the comments do,
> > because nobody needs to to be an ueber-hacker to turn on the option and
> > post any resulting oopses to lkml.
> 
> Sounds like a great idea to me.  Were you thinking of something along
> the lines of what I have below or perhaps something more
> sophisticated?  I suppose it would be helpful to have the name of the
> lock in addition to the file and line number...

I was thinking of something as simple as:

   #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))

but in truth I'd be happy regardless of the internal implementation.  A note
on names: Linus likes to shout the names of his BUG macros.  I've never been
one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
asserts.  I bet he'd like it more spelled like this though:

   MUST_HOLD(&lock);

And, dare I say it, what I'd *really* like to happen when the thing triggers
is to get dropped into kdb.  Ah well, perhaps in a parallel universe...

When one of these things triggers I do think you want everything to come to
a screeching halt, since, to misquote Matrix, "you're already dead", and you
don't want any one-per-year warnings to slip off into the gloomy depths of
some forgotten log file.

-- 
Daniel

Re: spinlock assertion macros

[george anzinger]

Daniel Phillips wrote:
> 
> On Thursday 11 July 2002 01:36, Jesse Barnes wrote:
> > On Thu, Jul 11, 2002 at 12:24:06AM +0200, Daniel Phillips wrote:
> > > Acme, which is to replace all those above-the-function lock coverage
> > > comments with assert-like thingies:
> > >
> > >    spin_assert(&pagemap_lru_lock);
> > >
> > > And everbody knows what that does: when compiled with no spinlock
> > > debugging it does nothing, but with spinlock debugging enabled, it oopses
> > > unless pagemap_lru_lock is held at that point in the code.  The practical
> > > effect of this is that lots of 3 line comments get replaced with a
> > > one line assert that actually does something useful.  That is, besides
> > > documenting the lock coverage, this thing will actually check to see if
> > > you're telling the truth, if you ask it to.
> > >
> > > Oh, and they will stay up to date much better than the comments do,
> > > because nobody needs to to be an ueber-hacker to turn on the option and
> > > post any resulting oopses to lkml.
> >
> > Sounds like a great idea to me.  Were you thinking of something along
> > the lines of what I have below or perhaps something more
> > sophisticated?  I suppose it would be helpful to have the name of the
> > lock in addition to the file and line number...
> 
> I was thinking of something as simple as:
> 
>    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
> 
> but in truth I'd be happy regardless of the internal implementation.  A note
> on names: Linus likes to shout the names of his BUG macros.  I've never been
> one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> asserts.  I bet he'd like it more spelled like this though:
> 
>    MUST_HOLD(&lock);
> 
> And, dare I say it, what I'd *really* like to happen when the thing triggers
> is to get dropped into kdb.  Ah well, perhaps in a parallel universe...

I should hope that, when BUG executes the unimplemented
instruction, it does go directly to kdb.  It certainly does
with my kgdb, as do all Oops, NULL dereferences, etc., etc.
> 
> When one of these things triggers I do think you want everything to come to
> a screeching halt, since, to misquote Matrix, "you're already dead", and you
> don't want any one-per-year warnings to slip off into the gloomy depths of
> some forgotten log file.
> 
> --
> Daniel
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-- 
George Anzinger   george@mvista.com
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml

Re: BKL removal

[Marco Colombo]

On Wed, 10 Jul 2002, William Lee Irwin III wrote:

> On Wed, Jul 10, 2002 at 12:03:08PM +0200, Marco Colombo wrote:
> >> Larry, there's something I've always wanted to ask you about your
> >> idea of the "locking cliff": when you're counting the number of locks,
> >> are you looking at the running image of an OS or at the source? 
> 
> On Wed, Jul 10, 2002 at 03:40:03PM +0100, Matthew Wilcox wrote:
> > Larry normally talks about the number of conceptual locks.  So in order
> > to manipulate a `struct file', it really doesn't matter whether you have
> > to grab the BKL, the files_struct lock or the filp->lock.  There's a big
> > difference if you have to grab the filp->pos_lock, the filp->ra_lock and
> > the filp->iobuf_lock.  You'd have to know what order to grab them in,
> > for a start.
> 
> This is called "lock depth" and is not related to the total number of
> locks declared in the source. AFAIK no one wants to increase lock depth.

Not directly of course. But with one BKL, depth is limited to one.
With one lock per subsystem, it's hardly more than one. But with 10000
locks spread into the source, it's quite unlikely you can do *anything*
without holding two locks at least. I think one of the point of Larry's
"locking cliff" idea is that when the lock depth grows beyond your
ability (or time) to really handle it, the only solution is to create
"your own" lock, just to play safe. But this way you increase both the
global number of locks *and* the lock depth of your code (by one at least).

I don't fully agree with Larry: I blame the lack of a clean locking model.
If you start from one BKL and push it "down", just increasing the number
of locks everytime you feel you need to, you get a mess. Locking should be
done globally at the same level: either at top (BKL), at the top of
each subsystem, or at "object" level.

But I realize I'm speaking out of imagination, Larry out of experience.
And it really makes a difference (to me, at least).

.TM.

Re: spinlock assertion macros

[Arnd Bergmann]

On Thursday 11 July 2002 01:36, Jesse Barnes wrote:

+#define spin_assert_unlocked(lock) if (spin_is_locked(lock)) { printk("lock assertion failure: lock at %s:%d should be unlocked!\n", __FILE__, __LINE__); }

I suppose what would at least be as helpful is to check if _any_ 
lock is held, e.g. when calling a potentially sleeping function.

Something along these lines:

#ifdef CONFIG_DEBUG_SPINLOCK
extern char *volatile last_spinlock[NR_CPUS];

#define spin_assert_unlocked_all() ({ \
	char *lock = last_spinlock[smp_processor_id()]; \
	if (lock) { \
		printk (KERN_CRIT "%s:%d: lock %s is held\n", \
			__func__, __LINE__, lock); \
		BUG(); \
	} \
})

#define spin_lock(lock) ({ \
	last_spinlock[smp_processor_id()] = __stringify(lock) "@" \
		__FILE__ ":" __stringify(__LINE__); \
	__really_spin_lock(lock); \
})
#endif

probably, a per-cpu lock depth should be used to also catch
spin_lock(foo_lock); 
spin_lock(bar_lock); 
spin_unlock(bar_lock);
spin_assert_unlock_all();

	Arnd <><

Re: spinlock assertion macros

[Oliver Xymoron]

On Thu, 11 Jul 2002, Daniel Phillips wrote:

> I was thinking of something as simple as:
>
>    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
>
> but in truth I'd be happy regardless of the internal implementation.  A note
> on names: Linus likes to shout the names of his BUG macros.  I've never been
> one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> asserts.  I bet he'd like it more spelled like this though:
>
>    MUST_HOLD(&lock);

I prefer that form too.

> And, dare I say it, what I'd *really* like to happen when the thing triggers
> is to get dropped into kdb.  Ah well, perhaps in a parallel universe...

It ought to.

As long as we're talking about spinlock debugging, I've found it extremely
useful to add an entry to the spinlock to record where the spinlock was
taken.

-- 
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: spinlock assertion macros

[Jesse Barnes]

On Thu, Jul 11, 2002 at 07:31:09AM +0200, Daniel Phillips wrote:
> I was thinking of something as simple as:
> 
>    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
> 
> but in truth I'd be happy regardless of the internal implementation.  A note
> on names: Linus likes to shout the names of his BUG macros.  I've never been
> one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> asserts.  I bet he'd like it more spelled like this though:
> 
>    MUST_HOLD(&lock);

I like lowercase better too, but you're right that Linus likes to
shout...

> And, dare I say it, what I'd *really* like to happen when the thing triggers
> is to get dropped into kdb.  Ah well, perhaps in a parallel universe...

As long as you've got kdb patched in, this _should_ happen on BUG().

How about this?  Are there simple *_is_locked() calls for the other
mutex mechanisms?  If so, I could add those too...

Thanks,
Jesse


diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
--- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
+++ linux-2.5.25-spinassert/fs/inode.c	Thu Jul 11 10:59:23 2002
@@ -183,6 +183,8 @@
  */
 void __iget(struct inode * inode)
 {
+	MUST_HOLD(&inode_lock);
+
 	if (atomic_read(&inode->i_count)) {
 		atomic_inc(&inode->i_count);
 		return;
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
--- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
+++ linux-2.5.25-spinassert/include/linux/spinlock.h	Thu Jul 11 11:02:17 2002
@@ -116,7 +116,19 @@
 #define _raw_write_lock(lock)	(void)(lock) /* Not "unused variable". */
 #define _raw_write_unlock(lock)	do { } while(0)
 
-#endif /* !SMP */
+#endif /* !CONFIG_SMP */
+
+/*
+ * Simple lock assertions for debugging and documenting where locks need
+ * to be locked/unlocked.
+ */
+#if defined(CONFIG_DEBUG_SPINLOCK) && defined(CONFIG_SMP)
+#define MUST_HOLD(lock)		BUG_ON(!spin_is_locked(lock))
+#define MUST_NOT_HOLD(lock)	BUG_ON(spin_is_locked(lock))
+#else
+#define MUST_HOLD(lock)		do { } while(0)
+#define MUST_NOT_HOLD(lock)	do { } while(0)
+#endif /* CONFIG_DEBUG_SPINLOCK && CONFIG_SMP */
 
 #ifdef CONFIG_PREEMPT
 

Re: spinlock assertion macros

[Daniel Phillips]

On Thursday 11 July 2002 20:03, Jesse Barnes wrote:
> How about this?

It looks good, the obvious thing we don't get is what the actual lock
count is, and actually, we don't care because we know what it is in
this case.

> Are there simple *_is_locked() calls for the other
> mutex mechanisms?

I didn't look, but my guess is no and you're in for some reverse
engineering, or you could just ask Ben.

> If so, I could add those too...

Definitely needed.  Note there are both counting and mutex forms of
semaphore and they are actually the same primitive - this doesn't mean
the asserts should treat them the same.  That is, it doesn't make
sense to think of the counting form of semaphore in terms of lock
coverage, so actually, we're never interested in semaphore count
values other than 0 and 1,  the simple BUG_ON is all we need.  This
is nice, not only because it reads well, but because it doesn't
generate a lot of code.  This whole feature will be a lot more useful
if code size isn't a problem, in which case I'd tend to run with the
option enabled in the normal course of development.

> Thanks,
> Jesse
> 
> 
> diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
> --- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
> +++ linux-2.5.25-spinassert/fs/inode.c	Thu Jul 11 10:59:23 2002
> @@ -183,6 +183,8 @@
>   */
>  void __iget(struct inode * inode)
>  {
> +	MUST_HOLD(&inode_lock);
> +
>  	if (atomic_read(&inode->i_count)) {
>  		atomic_inc(&inode->i_count);
>  		return;
> diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
> --- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
> +++ linux-2.5.25-spinassert/include/linux/spinlock.h	Thu Jul 11 11:02:17 2002
> @@ -116,7 +116,19 @@
>  #define _raw_write_lock(lock)	(void)(lock) /* Not "unused variable". */
>  #define _raw_write_unlock(lock)	do { } while(0)
>  
> -#endif /* !SMP */
> +#endif /* !CONFIG_SMP */
> +
> +/*
> + * Simple lock assertions for debugging and documenting where locks need
> + * to be locked/unlocked.
> + */
> +#if defined(CONFIG_DEBUG_SPINLOCK) && defined(CONFIG_SMP)
> +#define MUST_HOLD(lock)		BUG_ON(!spin_is_locked(lock))
> +#define MUST_NOT_HOLD(lock)	BUG_ON(spin_is_locked(lock))
> +#else
> +#define MUST_HOLD(lock)		do { } while(0)
> +#define MUST_NOT_HOLD(lock)	do { } while(0)
> +#endif /* CONFIG_DEBUG_SPINLOCK && CONFIG_SMP */
>  
>  #ifdef CONFIG_PREEMPT
>  
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 
> 

-- 
Daniel

Re: spinlock assertion macros

[Sandy Harris]

Oliver Xymoron wrote:
> 
> On Thu, 11 Jul 2002, Daniel Phillips wrote:
> 
> > I was thinking of something as simple as:
> >
> >    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
> >
> > but in truth I'd be happy regardless of the internal implementation.  A note
> > on names: Linus likes to shout the names of his BUG macros.  I've never been
> > one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> > asserts.  I bet he'd like it more spelled like this though:
> >
> >    MUST_HOLD(&lock);
> 
> I prefer that form too.

Is it worth adding MUST_NOT_HOLD(&lock) in an attempt to catch potential
deadlocks?

Say that if two or more of locks A, B and C are to be taken, then
they must be taken in that order. You might then have code like:

	MUST_NOT_HOLD(&lock_B) ;
	MUST_NOT_HOLD(&lock_C) ;
	spinlock(&lock_A) ;

I think you need a separate asertion for this !MUST_NOT_HOLD(&lock)
has different semantics.

Re: spinlock assertion macros

[Daniel Phillips]

On Friday 12 July 2002 01:52, Sandy Harris wrote:
> Oliver Xymoron wrote:
> > 
> > On Thu, 11 Jul 2002, Daniel Phillips wrote:
> > 
> > > I was thinking of something as simple as:
> > >
> > >    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
> > >
> > > but in truth I'd be happy regardless of the internal implementation.  A note
> > > on names: Linus likes to shout the names of his BUG macros.  I've never been
> > > one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> > > asserts.  I bet he'd like it more spelled like this though:
> > >
> > >    MUST_HOLD(&lock);
> > 
> > I prefer that form too.
> 
> Is it worth adding MUST_NOT_HOLD(&lock) in an attempt to catch potential
> deadlocks?
> 
> Say that if two or more of locks A, B and C are to be taken, then
> they must be taken in that order. You might then have code like:
> 
> 	MUST_NOT_HOLD(&lock_B) ;
> 	MUST_NOT_HOLD(&lock_C) ;
> 	spinlock(&lock_A) ;
> 
> I think you need a separate asertion for this !MUST_NOT_HOLD(&lock)
> has different semantics.

MUST_NOT_HOLD is already in Jesse's patch he posted earlier today,
though I imagine it would be used rarely if at all.

!MUST_NOT_HOLD(&lock) is an error, MUST_NOT_HOLD is a statement not a
function.

-- 
Daniel

Re: spinlock assertion macros

[Oliver Xymoron]

On Thu, 11 Jul 2002, Sandy Harris wrote:

> Oliver Xymoron wrote:
> >
> > On Thu, 11 Jul 2002, Daniel Phillips wrote:
> >
> > > I was thinking of something as simple as:
> > >
> > >    #define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
> > >
> > > but in truth I'd be happy regardless of the internal implementation.  A note
> > > on names: Linus likes to shout the names of his BUG macros.  I've never been
> > > one for shouting, but it's not my kernel, and anyway, I'm happy he now likes
> > > asserts.  I bet he'd like it more spelled like this though:
> > >
> > >    MUST_HOLD(&lock);
> >
> > I prefer that form too.
>
> Is it worth adding MUST_NOT_HOLD(&lock) in an attempt to catch potential
> deadlocks?

No, you'd rather do that inside the debugging version of spinlock itself.
I see MUST_HOLD happening inside helper functions that presume a lock is
in effect but don't do any on their own to ensure integrity, while
MUST_NOT_HOLD is a matter of forcing ordering and avoiding deadlocks.
Locking order is larger than functions and should be documented at the
point of declaration of the locks.

You can do lock order checking in the spinlock debugging code something
like this:

struct spinlock
{
	atomic_t val;
#ifdef SPINLOCK_DEBUG
	void *eip;
	struct spinlock *previous;
	struct spinlock *ordering;
};

DECLARE_SPINLOCK(a, 0); /* a is outermost for this group */
DECLARE_SPINLOCK(b, &a); /* b must nest inside a */
DECLARE_SPINLOCK(c, &b);

Each time you take a spinlock, record the eip, stick the address of the
current lock in the task struct, and stick the outer lock in previous.
Then see if the current lock appears anywhere in the previous lock's
ordering chain (it shouldn't). This may be a bit overkill though.

It might make sense to have a MAY_SLEEP assert in a few key places (high
up in the chains of things that rarely sleep or for which the call path to
sleeping isn't obvious).

-- 
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: spinlock assertion macros

[Dave Jones]

On Thu, Jul 11, 2002 at 09:17:44PM +0200, Daniel Phillips wrote:
 > On Thursday 11 July 2002 20:03, Jesse Barnes wrote:
 > > How about this?
 > 
 > It looks good, the obvious thing we don't get is what the actual lock
 > count is, and actually, we don't care because we know what it is in
 > this case.

Something I've been meaning to hack up for a while is some spinlock
debugging code that adds a FUNCTION_SLEEPS() to (ta-da) functions that
may sleep. This macro then checks whether we're currently holding any
locks, and if so printk's the names of locks held, and where they were taken.

When I came up with the idea[1] I envisioned some linked-lists frobbing,
but in more recent times, we can now check the preempt_count for a
quick-n-dirty implementation (without the additional info of which locks
we hold, lock-taker, etc).

        Dave

[1] Not an original idea, in fact I think Ingo came up with an
    implementation back in `98 or so.

-- 
| Dave Jones.        http://www.codemonkey.org.uk
| SuSE Labs

Re: spinlock assertion macros

[Daniel Phillips]

On Friday 12 July 2002 14:07, Dave Jones wrote:
> On Thu, Jul 11, 2002 at 09:17:44PM +0200, Daniel Phillips wrote:
>  > On Thursday 11 July 2002 20:03, Jesse Barnes wrote:
>  > > How about this?
>  > 
>  > It looks good, the obvious thing we don't get is what the actual lock
>  > count is, and actually, we don't care because we know what it is in
>  > this case.
> 
> Something I've been meaning to hack up for a while is some spinlock
> debugging code that adds a FUNCTION_SLEEPS() to (ta-da) functions that
> may sleep.

Yesss.  May I suggest simply SLEEPS()?  (Chances are, we know it's a
function.)

> This macro then checks whether we're currently holding any
> locks, and if so printk's the names of locks held, and where they were taken.

And then oopes?

> When I came up with the idea[1] I envisioned some linked-lists frobbing,
> but in more recent times, we can now check the preempt_count for a
> quick-n-dirty implementation (without the additional info of which locks
> we hold, lock-taker, etc).

Spin_lock just has to store the address/location of the lock in a
per-cpu vector, and the assert prints that out when it oopses.  Such
bugs won't live too long under those conditions.

Any idea how one might implement NEVER_SLEEPS()?  Maybe as:

   NEVER_ [code goes here] _SLEEPS

which inc/dec the preeempt count, triggering a BUG in schedule().

-- 
Daniel

Re: spinlock assertion macros

[Daniel Phillips]

On Friday 12 July 2002 21:24, Arnd Bergmann wrote:
> Daniel Phillips wrote:
> 
> > Any idea how one might implement NEVER_SLEEPS()?  Maybe as:
> 
> Why would you want that? AFAICS there are two kinds of "never
> sleeping" functions: 1. those that don't sleep but don't care
> about it and 2. those that must not sleep because a lock is
> held.
> 
> For 1. no point marking it because it might change without
> being a bug. You also don't want to mark every function
> in the kernel SLEEPS() or NEVER_SLEEPS().
> 
> For 2. we already have MUST_HOLD(foo) or similar, which implicitly 
> means it can never sleep. The same is true for functions
> with spinlocks or preempt_disable around their body.

Thanks for that.

So far, only the MUST_HOLD style of executable locking documentation has 
really survived scrutiny.  It needs some variants: MUST_HOLD_READ, 
MUST_HOLD_WRITE, MUST_HOLD_SEM, MUST_HOLD_READ_SEM and MUST_HOLD_WRITE_SEM, 
or names to that effect.

-- 
Daniel

Re: spinlock assertion macros

[Robert Love]

On Fri, 2002-07-12 at 05:07, Dave Jones wrote:

> When I came up with the idea[1] I envisioned some linked-lists frobbing,
> but in more recent times, we can now check the preempt_count for a
> quick-n-dirty implementation (without the additional info of which locks
> we hold, lock-taker, etc).

Neat idea.  I have seen some other good similar ideas: check
preempt_count on schedule(), check preempt_count in usleep/msleep
(Arjan's idea), and check preempt_count in wakeup/context switch/etc.
code...

Note some of these need one or both of: subtracting out
current->lock_depth+1 since we can sleep with the BKL and NAND'ing out
PREEMPT_ACTIVE as that is set before entering schedule off a preemption.

As we move preempt_count to more of a generic "are we atomic" count in
2.5, these become easier and more useful...

	Robert Love

Re: spinlock assertion macros

[Dave Jones]

On Fri, Jul 12, 2002 at 10:49:42AM -0700, Robert Love wrote:

 > > When I came up with the idea[1] I envisioned some linked-lists frobbing,
 > > but in more recent times, we can now check the preempt_count for a
 > > quick-n-dirty implementation (without the additional info of which locks
 > > we hold, lock-taker, etc).
 > 
 > Neat idea.  I have seen some other good similar ideas: check
 > preempt_count on schedule(), check preempt_count in usleep/msleep
 > (Arjan's idea), and check preempt_count in wakeup/context switch/etc.
 > code...

Sounds sensible. I'd like to see more self-checking bits added for
preemption. It may be the only way we ever pin down some of the
outstanding "don't make any sense" bugs.

        Dave

-- 
| Dave Jones.        http://www.codemonkey.org.uk
| SuSE Labs

Re: spinlock assertion macros

[Arnd Bergmann]

Daniel Phillips wrote:

> Any idea how one might implement NEVER_SLEEPS()?  Maybe as:

Why would you want that? AFAICS there are two kinds of "never
sleeping" functions: 1. those that don't sleep but don't care
about it and 2. those that must not sleep because a lock is
held.

For 1. no point marking it because it might change without
being a bug. You also don't want to mark every function
in the kernel SLEEPS() or NEVER_SLEEPS().

For 2. we already have MUST_HOLD(foo) or similar, which implicitly 
means it can never sleep. The same is true for functions
with spinlocks or preempt_disable around their body.

        Arnd <><

Re: spinlock assertion macros

[Oliver Xymoron]

On Fri, 12 Jul 2002, Daniel Phillips wrote:

> On Friday 12 July 2002 14:07, Dave Jones wrote:
> > On Thu, Jul 11, 2002 at 09:17:44PM +0200, Daniel Phillips wrote:
> >  > On Thursday 11 July 2002 20:03, Jesse Barnes wrote:
> >  > > How about this?
> >  >
> >  > It looks good, the obvious thing we don't get is what the actual lock
> >  > count is, and actually, we don't care because we know what it is in
> >  > this case.
> >
> > Something I've been meaning to hack up for a while is some spinlock
> > debugging code that adds a FUNCTION_SLEEPS() to (ta-da) functions that
> > may sleep.
>
> Yesss.  May I suggest simply SLEEPS()?  (Chances are, we know it's a
> function.)
>
> > This macro then checks whether we're currently holding any
> > locks, and if so printk's the names of locks held, and where they were taken.
>
> And then oopes?
>
> > When I came up with the idea[1] I envisioned some linked-lists frobbing,
> > but in more recent times, we can now check the preempt_count for a
> > quick-n-dirty implementation (without the additional info of which locks
> > we hold, lock-taker, etc).
>
> Spin_lock just has to store the address/location of the lock in a
> per-cpu vector, and the assert prints that out when it oopses.  Such
> bugs won't live too long under those conditions.

Store it in the task struct, and store a pointer to the previous (outer
lock) in that lock, then you've got a linked list of locks per task - very
useful. You'll need a helper function - current() is hard to get at from
spinlock.h due to tangled dependencies. As I mentioned before, it can also
be very handy to stash the address of the code that took the lock in the
lock itself.

> Any idea how one might implement NEVER_SLEEPS()?  Maybe as:
>
>    NEVER_ [code goes here] _SLEEPS
>
> which inc/dec the preeempt count, triggering a BUG in schedule().

NEVER_SLEEPS will only trigger on the rare events that blow up anyway,
while the MAY_SLEEP version catches _potential_ problems even when the
fatal sleep doesn't happen.

-- 
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: spinlock assertion macros

[Daniel Phillips]

On Friday 12 July 2002 22:41, Oliver Xymoron wrote:
> On Fri, 12 Jul 2002, Daniel Phillips wrote:
> > On Friday 12 July 2002 14:07, Dave Jones wrote:
> > > Something I've been meaning to hack up for a while is some spinlock
> > > debugging code that adds a FUNCTION_SLEEPS() to (ta-da) functions that
> > > may sleep.
> >
> > Yesss.  May I suggest simply SLEEPS()?  (Chances are, we know it's a
> > function.)
> >
> > > This macro then checks whether we're currently holding any
> > > locks, and if so printk's the names of locks held, and where they were taken.
> >
> > And then oopes?
> >
> > > When I came up with the idea[1] I envisioned some linked-lists frobbing,
> > > but in more recent times, we can now check the preempt_count for a
> > > quick-n-dirty implementation (without the additional info of which locks
> > > we hold, lock-taker, etc).
> >
> > Spin_lock just has to store the address/location of the lock in a
> > per-cpu vector, and the assert prints that out when it oopses.  Such
> > bugs won't live too long under those conditions.
> 
> Store it in the task struct, and store a pointer to the previous (outer
> lock) in that lock, then you've got a linked list of locks per task - very
> useful.

Yes, thanks, I was in fact feeling a little guilty about proposing that
non-nested solution, even if it would in practice point you at the
correct culprit most of the time.

So in schedule() we check the task struct field and oops if it's non-null.
In other words, one instance of SLEEPS goes in shedule() and others are
sprinkled around the kernel as executable documentation.

> You'll need a helper function - current() is hard to get at from
> spinlock.h due to tangled dependencies.

What is the problem?  It looks like (struct thread_info *) can be forward
declared, and hence current_thread_info and get_current can be defined
early.  Maybe I didn't sniff at enough architectures.

Anyway, if there are nasty dependencies then they are probably similar
to the ones I unravelled with my early-page patch, which allows struct
page to be declared right at the start of mm.h instead of way later,
below a lot of things that want to reference it.

> As I mentioned before, it can also
> be very handy to stash the address of the code that took the lock in the
> lock itself.

And since the stack is chained through the locks, that just works.
 
> > Any idea how one might implement NEVER_SLEEPS()?  Maybe as:
> >
> >    NEVER_ [code goes here] _SLEEPS
> >
> > which inc/dec the preeempt count, triggering a BUG in schedule().
> 
> NEVER_SLEEPS will only trigger on the rare events that blow up anyway,
> while the MAY_SLEEP version catches _potential_ problems even when the
> fatal sleep doesn't happen.

Yes, that one's already been rejected as largely pointless.

-- 
Daniel

Re: BKL removal

[Alexander Hoogerhuis]

Alan Cox <alan@lxorguk.ukuu.org.uk> writes:

> > On Tue, Jul 09, 2002 at 11:21:25PM +0100, Alan Cox wrote:
> > > 
> > > There are lots of them hiding 8)
> > 
> > Just out of curisoty.  If I remember correctly SMP came to Linux when
> > Caldera hired you to make it work.  Did you invent the BKL?
> 
> Caldera bought the hardware, rather than hiring me. Having said that at
> the time the dual P90 board + processors was not exactly cheap. The board
> btw is alive and well and currently owned by Dave Jones.
> 
> As far as the locking goes I invented the big kernel lock, but the basis of
> that is all taken directly from "Unix systems for modern architectures"
> by Schimmel which is required reading for anyone who cares about caches,
> SMP and locking. 
> 
> 	I'd prefer the trees to be separate for testing purposes: it 
> 	doens't	make much sense to have SMP support as a normal kernel 
> 	feature when most people won't have SMP anyway"
> 			-- Linus Torvalds
> 

That takes Linux even one step closer to the big commercial world, we
now have a statement to quialify for membership into the same club as
Mr. Gates' "Who needs more than 640kb anyway?" and Olsen's (Digital?)
"There will only be a handfull of computers in the nation". :)

mvh,
A
-- 
Alexander Hoogerhuis                               | alexh@ihatent.com
CCNP - CCDP - MCNE - CCSE                          | +47 908 21 485
"You have zero privacy anyway. Get over it."  --Scott McNealy

Re: BKL removal

[Rik van Riel]

On 15 Jul 2002, Alexander Hoogerhuis wrote:

> That takes Linux even one step closer to the big commercial world, we
> now have a statement to quialify for membership into the same club as
> Mr. Gates' "Who needs more than 640kb anyway?" and Olsen's (Digital?)
> "There will only be a handfull of computers in the nation". :)

With ongoing miniaturisation, Olsen might just be right again ...

Rik
-- 
Bravely reimplemented by the knights who say "NIH".

http://www.surriel.com/		http://distro.conectiva.com/

Re: BKL removal

[Thunder from the hill]

Hi,

On Mon, 15 Jul 2002, Rik van Riel wrote:
> > "There will only be a handfull of computers in the nation". :)
> 
> With ongoing miniaturisation, Olsen might just be right again ...

Note: a handful of computers, not a handful of computer.

Miniaturization is a Good Thing[tm], IMHO. I've worked on Computers for 
quite a while, and I was quite happy watching them shrink. Remember the 
Honeywell DDP-110, or which was it? The first computer which I managed to 
hide in a single corner of a room. With the incredible amount of 12 kB of 
storage. Were we happy...

Today, I can hide a computer in my pocket, playing mp3 files. No need to 
pull your cupboard behind you. Miniaturization is quite useful when it 
comes to carry things around.

							Regards,
							Thunder
-- 
(Use http://www.ebb.org/ungeek if you can't decode)
------BEGIN GEEK CODE BLOCK------
Version: 3.12
GCS/E/G/S/AT d- s++:-- a? C++$ ULAVHI++++$ P++$ L++++(+++++)$ E W-$
N--- o?  K? w-- O- M V$ PS+ PE- Y- PGP+ t+ 5+ X+ R- !tv b++ DI? !D G
e++++ h* r--- y- 
------END GEEK CODE BLOCK------

Re: spinlock assertion macros

[Jesse Barnes]

On Fri, Jul 12, 2002 at 07:42:09PM +0200, Daniel Phillips wrote:
> So far, only the MUST_HOLD style of executable locking documentation has 
> really survived scrutiny.  It needs some variants: MUST_HOLD_READ, 
> MUST_HOLD_WRITE, MUST_HOLD_SEM, MUST_HOLD_READ_SEM and MUST_HOLD_WRITE_SEM, 
> or names to that effect.

I'm not quite sure where to put the semaphore versions of the MUST_*
macros, I guess they'd have to go in each of the arch-specific header
files?  Anyway, I've got spinlock and rwlock versions of them below,
maybe they're useful enough to go in as a start?  I only coded the
ia64 version of rwlock_is_*_locked since it was easy--the i386
versions were a little intimidating...

I thought Oliver's suggestion for tracking the order of spinlock
acquisition was good, hopefully someone will take a stab at it along
with Dave's FUNCTION_SLEEPS() implementation.

Jesse


diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/fs/inode.c linux-2.5.25-spinassert/fs/inode.c
--- linux-2.5.25/fs/inode.c	Fri Jul  5 16:42:38 2002
+++ linux-2.5.25-spinassert/fs/inode.c	Tue Jul 16 19:04:01 2002
@@ -183,6 +183,8 @@
  */
 void __iget(struct inode * inode)
 {
+	MUST_HOLD_SPIN(&inode_lock);
+
 	if (atomic_read(&inode->i_count)) {
 		atomic_inc(&inode->i_count);
 		return;
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/asm-ia64/spinlock.h linux-2.5.25-spinassert/include/asm-ia64/spinlock.h
--- linux-2.5.25/include/asm-ia64/spinlock.h	Fri Jul  5 16:42:03 2002
+++ linux-2.5.25-spinassert/include/asm-ia64/spinlock.h	Tue Jul 16 18:31:53 2002
@@ -109,6 +109,8 @@
 #define RW_LOCK_UNLOCKED (rwlock_t) { 0, 0 }
 
 #define rwlock_init(x) do { *(x) = RW_LOCK_UNLOCKED; } while(0)
+#define rwlock_is_read_locked(x) ((x)->read_counter != 0 || (x)->write_lock != 0)
+#define rwlock_is_write_locked(x) ((x)->write_lock != 0)
 
 #define _raw_read_lock(rw)							\
 do {										\
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.25/include/linux/spinlock.h linux-2.5.25-spinassert/include/linux/spinlock.h
--- linux-2.5.25/include/linux/spinlock.h	Fri Jul  5 16:42:24 2002
+++ linux-2.5.25-spinassert/include/linux/spinlock.h	Tue Jul 16 18:58:40 2002
@@ -116,7 +116,21 @@
 #define _raw_write_lock(lock)	(void)(lock) /* Not "unused variable". */
 #define _raw_write_unlock(lock)	do { } while(0)
 
-#endif /* !SMP */
+#endif /* !CONFIG_SMP */
+
+/*
+ * Simple lock assertions for debugging and documenting where locks need
+ * to be locked/unlocked.
+ */
+#if defined(CONFIG_DEBUG_SPINLOCK) && defined(CONFIG_SMP)
+#define MUST_HOLD_SPIN(lock)		BUG_ON(!spin_is_locked(lock))
+#define MUST_HOLD_READ(lock)		BUG_ON(!rwlock_is_read_locked(lock))
+#define MUST_HOLD_WRITE(lock)		BUG_ON(!rwlock_is_write_locked(lock))
+#else
+#define MUST_HOLD_SPIN(lock)		do { } while(0)
+#define MUST_HOLD_READ(lock)		do { } while(0)
+#define MUST_HOLD_WRITE(lock)		do { } while(0)
+#endif /* CONFIG_DEBUG_SPINLOCK && CONFIG_SMP */
 
 #ifdef CONFIG_PREEMPT
 

Re: spinlock assertion macros

[Daniel Phillips]

On Wednesday 17 July 2002 04:22, Jesse Barnes wrote:
> On Fri, Jul 12, 2002 at 07:42:09PM +0200, Daniel Phillips wrote:
> > So far, only the MUST_HOLD style of executable locking documentation has 
> > really survived scrutiny.  It needs some variants: MUST_HOLD_READ, 
> > MUST_HOLD_WRITE, MUST_HOLD_SEM, MUST_HOLD_READ_SEM and MUST_HOLD_WRITE_SEM, 
> > or names to that effect.
> 
> I'm not quite sure where to put the semaphore versions of the MUST_*
> macros, I guess they'd have to go in each of the arch-specific header
> files?

You could create linux/semaphore.h which includes asm/semaphore.h, making
the whole arrangement more similar to spinlocks.  That would be the manly
thing to do, however, manliness not necessarily being the fashion at the
moment, putting them in the arch-specific headers seems like the route of
least resistance.  One day, a prince on a white horse will come along and
clean up all the header files...

> Anyway, I've got spinlock and rwlock versions of them below,
> maybe they're useful enough to go in as a start?  I only coded the
> ia64 version of rwlock_is_*_locked since it was easy--the i386
> versions were a little intimidating...
> 
> I thought Oliver's suggestion for tracking the order of spinlock
> acquisition was good, hopefully someone will take a stab at it along
> with Dave's FUNCTION_SLEEPS() implementation.

Indeed, it's a nice realization of Dave's idea, very clever.

On the minor niggle side, I think "MUST_HOLD" scans better than
"MUST_HOLD_SPIN", since the former is closer to the way we say it when
we're talking amongst ourselves.

-- 
Daniel

Re: spinlock assertion macros

[Arnd Bergmann]

On Wednesday 17 July 2002 04:22, Jesse Barnes wrote:
> files?  Anyway, I've got spinlock and rwlock versions of them below,
> maybe they're useful enough to go in as a start?  I only coded the
> ia64 version of rwlock_is_*_locked since it was easy--the i386
> versions were a little intimidating...
>
> I thought Oliver's suggestion for tracking the order of spinlock
> acquisition was good, hopefully someone will take a stab at it along
> with Dave's FUNCTION_SLEEPS() implementation.

I suppose you can simplify your interface when the code tracking the lock 
holder (i.e. the address of the lock call) is there: 

#define MUST_HOLD(lock)		BUG_ON(!(lock)->holder)

is independent of whether lock is a spinlock or an rw_lock, so you
don't need MUST_HOLD_READ anymore. I'd even go as far as dropping 
MUST_HOLD_WRITE as well, since it helps only in the corner case
where the lock is held but only for reading.

	Arnd <><

Re: BKL removal

[David Wagner]

Dave Hansen  wrote:
>The Stanford Checker or something resembling it would be invaluable 
>here.  It would be a hell of a lot better than my litle patch!

Hmm.  There's a chance we might be able to help.  Our group is building
a tool called MOPS that is similar in spirit to the Stanford Checker.
MOPS is work-in-progress and will be open source.  I haven't tried it
yet on the Linux kernel, but this seems like a reasonable thing to try.

What would you want to check?  Track lock_kernel() and unlock_kernel()
and make sure that the BKL is never held when you return from a function?
Something else?

MOPS can handle nested and recursive functions nicely.  However, it has
some important limitations:
 * Useability hasn't been a focus yet; the input language is
   not terribly elegant, and the output language is not exceptionally
   friendly.  (yet)
 * It currently ignores function pointers.  (yet)
 * #ifdefs are trouble; we only analyzed pre-processed C code.
 * It can't reason about data, variables, or values on the heap.
We're working hard on useability.  We may fix the second limitation
in future months.  However, the latter two are unlikely to go away in
the foreseeable future.  Would it still be worth investigating MOPS,
despite these limitations?

The MOPS web page is at
 http://www.cs.berkeley.edu/~daw/mops/
There is an initial release there, though it has some known problems.
We're working hard to making it more usable, and I hope to be able to
report more progress in upcoming months.

Re: BKL removal

[Daniel Phillips]

On Thursday 18 July 2002 02:30, David Wagner wrote:
> Dave Hansen  wrote:
> >The Stanford Checker or something resembling it would be invaluable 
> >here.  It would be a hell of a lot better than my litle patch!
> 
> Hmm.  There's a chance we might be able to help.  Our group is building
> a tool called MOPS that is similar in spirit to the Stanford Checker.
> MOPS is work-in-progress and will be open source.  I haven't tried it
> yet on the Linux kernel, but this seems like a reasonable thing to try.

Excellent, there is an ecological niche ready and waiting for the first
group to do what the Stanford group has done, but open the source.  It's
beyond me why the Stanford group hasn't done so, perhaps it has something
to do with university politics.

-- 
Daniel

[PATCH] spinlock assertion macros for 2.5.26

[Jesse Barnes]

On Wed, Jul 17, 2002 at 08:34:05AM +0200, Daniel Phillips wrote:
> You could create linux/semaphore.h which includes asm/semaphore.h, making
> the whole arrangement more similar to spinlocks.  That would be the manly
> thing to do, however, manliness not necessarily being the fashion at the
> moment, putting them in the arch-specific headers seems like the route of
> least resistance.  One day, a prince on a white horse will come along and
> clean up all the header files...

Well, I'll at least take a stab at it, but I won't have time until
next week.  Here's the current version of the macros against 2.5.26
though, in case someone wants to add support for architectures other
than ia64.

> > I thought Oliver's suggestion for tracking the order of spinlock
> > acquisition was good, hopefully someone will take a stab at it along
> > with Dave's FUNCTION_SLEEPS() implementation.

It doesn't look like it would be too hard to do, but seems like it
should be a seperate patch (maybe with more header file tweaking).

> On the minor niggle side, I think "MUST_HOLD" scans better than
> "MUST_HOLD_SPIN", since the former is closer to the way we say it when
> we're talking amongst ourselves.

Sure thing.  I fixed it up in this version.

Thanks,
Jesse

diff -Naur -X /home/jbarnes/dontdiff linux-2.5.26/fs/inode.c linux-2.5.26-lockassert/fs/inode.c
--- linux-2.5.26/fs/inode.c	Tue Jul 16 16:49:38 2002
+++ linux-2.5.26-lockassert/fs/inode.c	Thu Jul 18 10:21:13 2002
@@ -183,6 +183,8 @@
  */
 void __iget(struct inode * inode)
 {
+	MUST_HOLD(&inode_lock);
+
 	if (atomic_read(&inode->i_count)) {
 		atomic_inc(&inode->i_count);
 		return;
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.26/include/asm-ia64/spinlock.h linux-2.5.26-lockassert/include/asm-ia64/spinlock.h
--- linux-2.5.26/include/asm-ia64/spinlock.h	Tue Jul 16 16:49:25 2002
+++ linux-2.5.26-lockassert/include/asm-ia64/spinlock.h	Thu Jul 18 16:30:49 2002
@@ -109,6 +109,7 @@
 #define RW_LOCK_UNLOCKED (rwlock_t) { 0, 0 }
 
 #define rwlock_init(x) do { *(x) = RW_LOCK_UNLOCKED; } while(0)
+#define rwlock_is_locked(x) ((x)->read_counter != 0 || (x)->write_lock != 0)
 
 #define _raw_read_lock(rw)							\
 do {										\
diff -Naur -X /home/jbarnes/dontdiff linux-2.5.26/include/linux/spinlock.h linux-2.5.26-lockassert/include/linux/spinlock.h
--- linux-2.5.26/include/linux/spinlock.h	Tue Jul 16 16:49:33 2002
+++ linux-2.5.26-lockassert/include/linux/spinlock.h	Thu Jul 18 16:31:13 2002
@@ -116,7 +116,19 @@
 #define _raw_write_lock(lock)	(void)(lock) /* Not "unused variable". */
 #define _raw_write_unlock(lock)	do { } while(0)
 
-#endif /* !SMP */
+#endif /* !CONFIG_SMP */
+
+/*
+ * Simple lock assertions for debugging and documenting where locks need
+ * to be locked/unlocked.
+ */
+#if defined(CONFIG_DEBUG_SPINLOCK) && defined(CONFIG_SMP)
+#define MUST_HOLD(lock)			BUG_ON(!spin_is_locked(lock))
+#define MUST_HOLD_RW(lock)		BUG_ON(!rwlock_is_locked(lock))
+#else
+#define MUST_HOLD(lock)			do { } while(0)
+#define MUST_HOLD_RW(lock)		do { } while(0)
+#endif /* CONFIG_DEBUG_SPINLOCK && CONFIG_SMP */
 
 #ifdef CONFIG_PREEMPT
 

Re: BKL removal

[dan carpenter]

----- Original Message -----
From: Alexander Viro 
To: Arnaldo Carvalho de Melo <acme@conectiva.com.br>
Subject: Re: BKL removal
 
> On Tue, 9 Jul 2002, Arnaldo Carvalho de Melo wrote:
> 
> > Try smatch:
> > 
> > http://smatch.sf.net
> > 
> > And see if you can write a smatch script to get a good broom for this trash 8)
> 

I certainly am flatterred :) 

But basically what Alexander Viro said is all true.  The other problem that he didn't mention was that I don't see how checkers can be built to handle loops.  In writing smatch I just ignore loops altogether.

For now I just take the quick and dirty approach.  Also smatch really isn't finished yet.  I worked on it for a half hour tonight and fixed the bugs with the lock_kernel check.  Tomorrow I'll maybe add support for while, for, switch and break statements.

regards,
dan carpenter


-- 
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup

Save up to $160 by signing up for NetZero Platinum Internet service.
http://www.netzero.net/?refcd=N2P0602NEP8

Re: BKL removal

[Oliver Neukum]

Am Montag, 8. Juli 2002 21:00 schrieb pmenage@ensim.com:
> In article <0C01A29FBAE24448A792F5C68F5EA47D2B0C8A@nasdaq.ms.ensim.com>,
>
> you write:
> >The BKL, unless used unbalanced, can never cause a bug.
> >It could be insufficient or superfluous, but never be really buggy in
> >itself.
>
> Unless you're including incorrect nesting in your definition of
> "unbalanced", that's not really true. E.g. lock_kernel() anywhere that
> dcache_lock is held can deadlock against anywhere that does a path
> lookup with the BKL held (such as do_coredump()).

Yes, for the record. If you mix locking orders you can deadlock, as with any
other lock. And the BKL needs process context. And it doesn't help
against races with interrupts.

	Regards
		Oliver

Re: BKL removal

[pmenage]

In article <0C01A29FBAE24448A792F5C68F5EA47D2B0C8A@nasdaq.ms.ensim.com>,
you write:
>The BKL, unless used unbalanced, can never cause a bug.
>It could be insufficient or superfluous, but never be really buggy in
>itself.

Unless you're including incorrect nesting in your definition of
"unbalanced", that's not really true. E.g. lock_kernel() anywhere that
dcache_lock is held can deadlock against anywhere that does a path
lookup with the BKL held (such as do_coredump()).

Paul

Re: BKL removal

[Dave Hansen]

[-- Attachment #1: Type: text/plain, Size: 148 bytes --]

Just in case your telepathic patch reception isn't working, here's the 
patch with added release-on-sleep fun.

-- 
Dave Hansen
haveblue@us.ibm.com

[-- Attachment #2: bkl_debug-2.5.24-12.patch --]
[-- Type: text/plain, Size: 18973 bytes --]

diff -ur linux-2.5.24-clean/Makefile linux-2.5.24-dirty/Makefile
--- linux-2.5.24-clean/Makefile	Thu Jun 20 15:53:44 2002
+++ linux-2.5.24-dirty/Makefile	Thu Jul  4 11:32:23 2002
@@ -1,7 +1,7 @@
 VERSION = 2
 PATCHLEVEL = 5
 SUBLEVEL = 24
-EXTRAVERSION =
+EXTRAVERSION =-bkldebug12
 
 # We are using a recursive build, so we need to do a little thinking
 # to get the ordering right.
diff -ur linux-2.5.24-clean/arch/i386/Config.help linux-2.5.24-dirty/arch/i386/Config.help
--- linux-2.5.24-clean/arch/i386/Config.help	Thu Jun 20 15:53:44 2002
+++ linux-2.5.24-dirty/arch/i386/Config.help	Thu Jul  4 11:32:07 2002
@@ -932,6 +932,15 @@
   best used in conjunction with the NMI watchdog so that spinlock
   deadlocks are also debuggable.
 
+CONFIG_DEBUG_BKL
+  Say Y here to get interesting information about the Big Kernel
+  Lock's use in dmesg.  
+  Shows information on the following:
+  - nested holds of BKL
+  - releases in schedule (not yet implemented)
+  - use in interrupts (not yet implemented)
+  Send any interesting output to Dave Hansen <haveblue@us.ibm.com>
+
 CONFIG_DEBUG_BUGVERBOSE
   Say Y here to make BUG() panics output the file name and line number
   of the BUG call as well as the EIP and oops trace.  This aids
diff -ur linux-2.5.24-clean/arch/i386/config.in linux-2.5.24-dirty/arch/i386/config.in
--- linux-2.5.24-clean/arch/i386/config.in	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/arch/i386/config.in	Thu Jul  4 11:32:07 2002
@@ -416,6 +416,7 @@
    bool '  Memory mapped I/O debugging' CONFIG_DEBUG_IOVIRT
    bool '  Magic SysRq key' CONFIG_MAGIC_SYSRQ
    bool '  Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+   bool '  Big kernel lock (BKL,kernel_flag) debugging' CONFIG_DEBUG_BKL
    if [ "$CONFIG_HIGHMEM" = "y" ]; then
       bool '  Highmem debugging' CONFIG_DEBUG_HIGHMEM
    fi
diff -ur linux-2.5.24-clean/include/asm-alpha/smplock.h linux-2.5.24-dirty/include/asm-alpha/smplock.h
--- linux-2.5.24-clean/include/asm-alpha/smplock.h	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/include/asm-alpha/smplock.h	Thu Jul  4 11:32:07 2002
@@ -39,13 +39,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-static __inline__ void lock_kernel(void)
+static __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-static __inline__ void unlock_kernel(void)
+static __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-arm/smplock.h linux-2.5.24-dirty/include/asm-arm/smplock.h
--- linux-2.5.24-clean/include/asm-arm/smplock.h	Thu Jun 20 15:53:43 2002
+++ linux-2.5.24-dirty/include/asm-arm/smplock.h	Thu Jul  4 11:32:07 2002
@@ -41,7 +41,7 @@
  * so we only need to worry about other
  * CPU's.
  */
-static inline void lock_kernel(void)
+static inline void __lock_kernel(void)
 {
 #ifdef CONFIG_PREEMPT
 	if (current->lock_depth == -1)
@@ -53,7 +53,7 @@
 #endif
 }
 
-static inline void unlock_kernel(void)
+static inline void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-cris/smp_lock.h linux-2.5.24-dirty/include/asm-cris/smp_lock.h
--- linux-2.5.24-clean/include/asm-cris/smp_lock.h	Thu Jun 20 15:53:44 2002
+++ linux-2.5.24-dirty/include/asm-cris/smp_lock.h	Thu Jul  4 11:32:07 2002
@@ -11,7 +11,7 @@
  *	Locking the kernel 
  */
  
-extern __inline void lock_kernel(void)
+extern __inline void __lock_kernel(void)
 {
 	unsigned long flags;
 	int proc = smp_processor_id();
@@ -49,7 +49,7 @@
 	restore_flags(flags);
 }
 
-extern __inline void unlock_kernel(void)
+extern __inline void __unlock_kernel(void)
 {
 	unsigned long flags;
 	save_flags(flags);
diff -ur linux-2.5.24-clean/include/asm-cris/smplock.h linux-2.5.24-dirty/include/asm-cris/smplock.h
--- linux-2.5.24-clean/include/asm-cris/smplock.h	Thu Jun 20 15:53:52 2002
+++ linux-2.5.24-dirty/include/asm-cris/smplock.h	Thu Jul  4 11:32:07 2002
@@ -11,8 +11,8 @@
 
 #ifndef CONFIG_SMP
 
-#define lock_kernel()                           do { } while(0)
-#define unlock_kernel()                         do { } while(0)
+#define __lock_kernel()                           do { } while(0)
+#define __unlock_kernel()                         do { } while(0)
 #define release_kernel_lock(task, cpu, depth)   ((depth) = 1)
 #define reacquire_kernel_lock(task, cpu, depth) do { } while(0)
 
diff -ur linux-2.5.24-clean/include/asm-generic/smplock.h linux-2.5.24-dirty/include/asm-generic/smplock.h
--- linux-2.5.24-clean/include/asm-generic/smplock.h	Thu Jun 20 15:53:43 2002
+++ linux-2.5.24-dirty/include/asm-generic/smplock.h	Thu Jul  4 11:32:07 2002
@@ -38,13 +38,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-i386/smplock.h linux-2.5.24-dirty/include/asm-i386/smplock.h
--- linux-2.5.24-clean/include/asm-i386/smplock.h	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/include/asm-i386/smplock.h	Thu Jul  4 11:32:07 2002
@@ -54,7 +54,7 @@
  * so we only need to worry about other
  * CPU's.
  */
-static __inline__ void lock_kernel(void)
+static __inline__ void __lock_kernel(void)
 {
 #ifdef CONFIG_PREEMPT
 	if (current->lock_depth == -1)
@@ -76,7 +76,7 @@
 #endif
 }
 
-static __inline__ void unlock_kernel(void)
+static __inline__ void __unlock_kernel(void)
 {
 	if (current->lock_depth < 0)
 		BUG();
diff -ur linux-2.5.24-clean/include/asm-ia64/smplock.h linux-2.5.24-dirty/include/asm-ia64/smplock.h
--- linux-2.5.24-clean/include/asm-ia64/smplock.h	Thu Jun 20 15:53:54 2002
+++ linux-2.5.24-dirty/include/asm-ia64/smplock.h	Thu Jul  4 11:32:07 2002
@@ -51,14 +51,14 @@
  * CPU's.
  */
 static __inline__ void
-lock_kernel(void)
+__lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
 static __inline__ void
-unlock_kernel(void)
+__unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-m68k/smplock.h linux-2.5.24-dirty/include/asm-m68k/smplock.h
--- linux-2.5.24-clean/include/asm-m68k/smplock.h	Thu Jun 20 15:53:48 2002
+++ linux-2.5.24-dirty/include/asm-m68k/smplock.h	Thu Jul  4 11:32:07 2002
@@ -38,13 +38,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-mips/smplock.h linux-2.5.24-dirty/include/asm-mips/smplock.h
--- linux-2.5.24-clean/include/asm-mips/smplock.h	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/include/asm-mips/smplock.h	Thu Jul  4 11:32:07 2002
@@ -41,13 +41,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-mips64/smplock.h linux-2.5.24-dirty/include/asm-mips64/smplock.h
--- linux-2.5.24-clean/include/asm-mips64/smplock.h	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/include/asm-mips64/smplock.h	Thu Jul  4 11:32:07 2002
@@ -41,13 +41,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-static __inline__ void lock_kernel(void)
+static __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-static __inline__ void unlock_kernel(void)
+static __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-parisc/smplock.h linux-2.5.24-dirty/include/asm-parisc/smplock.h
--- linux-2.5.24-clean/include/asm-parisc/smplock.h	Thu Jun 20 15:53:43 2002
+++ linux-2.5.24-dirty/include/asm-parisc/smplock.h	Thu Jul  4 11:32:07 2002
@@ -36,13 +36,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-ppc/smplock.h linux-2.5.24-dirty/include/asm-ppc/smplock.h
--- linux-2.5.24-clean/include/asm-ppc/smplock.h	Thu Jun 20 15:53:48 2002
+++ linux-2.5.24-dirty/include/asm-ppc/smplock.h	Thu Jul  4 11:32:07 2002
@@ -47,7 +47,7 @@
  * so we only need to worry about other
  * CPU's.
  */
-static __inline__ void lock_kernel(void)
+static __inline__ void __lock_kernel(void)
 {
 #ifdef CONFIG_PREEMPT
 	if (current->lock_depth == -1)
@@ -59,7 +59,7 @@
 #endif /* CONFIG_PREEMPT */
 }
 
-static __inline__ void unlock_kernel(void)
+static __inline__ void __unlock_kernel(void)
 {
 	if (--current->lock_depth < 0)
 		spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-ppc64/smplock.h linux-2.5.24-dirty/include/asm-ppc64/smplock.h
--- linux-2.5.24-clean/include/asm-ppc64/smplock.h	Thu Jun 20 15:53:47 2002
+++ linux-2.5.24-dirty/include/asm-ppc64/smplock.h	Thu Jul  4 11:32:07 2002
@@ -43,13 +43,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-static __inline__ void lock_kernel(void)
+static __inline__ void __lock_kernel(void)
 {
 	if (!++current->lock_depth)
 		spin_lock(&kernel_flag);
 }
 
-static __inline__ void unlock_kernel(void)
+static __inline__ void __unlock_kernel(void)
 {
 	if (current->lock_depth < 0)
 		BUG();
diff -ur linux-2.5.24-clean/include/asm-s390/smplock.h linux-2.5.24-dirty/include/asm-s390/smplock.h
--- linux-2.5.24-clean/include/asm-s390/smplock.h	Thu Jun 20 15:53:55 2002
+++ linux-2.5.24-dirty/include/asm-s390/smplock.h	Thu Jul  4 11:32:07 2002
@@ -48,13 +48,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
         if (!++current->lock_depth)
                 spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
         if (--current->lock_depth < 0)
                 spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-s390x/smplock.h linux-2.5.24-dirty/include/asm-s390x/smplock.h
--- linux-2.5.24-clean/include/asm-s390x/smplock.h	Thu Jun 20 15:53:49 2002
+++ linux-2.5.24-dirty/include/asm-s390x/smplock.h	Thu Jul  4 11:32:07 2002
@@ -48,13 +48,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
         if (!++current->lock_depth)
                 spin_lock(&kernel_flag);
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
         if (--current->lock_depth < 0)
                 spin_unlock(&kernel_flag);
diff -ur linux-2.5.24-clean/include/asm-sh/smplock.h linux-2.5.24-dirty/include/asm-sh/smplock.h
--- linux-2.5.24-clean/include/asm-sh/smplock.h	Thu Jun 20 15:53:46 2002
+++ linux-2.5.24-dirty/include/asm-sh/smplock.h	Thu Jul  4 11:32:07 2002
@@ -11,8 +11,8 @@
 
 #ifndef CONFIG_SMP
 
-#define lock_kernel()				do { } while(0)
-#define unlock_kernel()				do { } while(0)
+#define __lock_kernel()				do { } while(0)
+#define __unlock_kernel()			do { } while(0)
 #define release_kernel_lock(task, cpu, depth)	((depth) = 1)
 #define reacquire_kernel_lock(task, cpu, depth)	do { } while(0)
 
diff -ur linux-2.5.24-clean/include/asm-sparc/smplock.h linux-2.5.24-dirty/include/asm-sparc/smplock.h
--- linux-2.5.24-clean/include/asm-sparc/smplock.h	Thu Jun 20 15:53:53 2002
+++ linux-2.5.24-dirty/include/asm-sparc/smplock.h	Thu Jul  4 11:32:07 2002
@@ -42,13 +42,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-#define lock_kernel()				\
+#define __lock_kernel()				\
 do {						\
 	if (!++current->lock_depth)		\
 		spin_lock(&kernel_flag);	\
 } while(0)
 
-#define unlock_kernel()				\
+#define __unlock_kernel()			\
 do {						\
 	if (--current->lock_depth < 0)		\
 		spin_unlock(&kernel_flag);	\
diff -ur linux-2.5.24-clean/include/asm-sparc64/smplock.h linux-2.5.24-dirty/include/asm-sparc64/smplock.h
--- linux-2.5.24-clean/include/asm-sparc64/smplock.h	Thu Jun 20 15:53:56 2002
+++ linux-2.5.24-dirty/include/asm-sparc64/smplock.h	Thu Jul  4 11:32:07 2002
@@ -50,13 +50,13 @@
  * so we only need to worry about other
  * CPU's.
  */
-#define lock_kernel()				\
+#define __lock_kernel()				\
 do {						\
 	if (!++current->lock_depth)		\
 		spin_lock(&kernel_flag);	\
 } while(0)
 
-#define unlock_kernel()				\
+#define __unlock_kernel()			\
 do {						\
 	if (--current->lock_depth < 0)		\
 		spin_unlock(&kernel_flag);	\
diff -ur linux-2.5.24-clean/include/asm-x86_64/smplock.h linux-2.5.24-dirty/include/asm-x86_64/smplock.h
--- linux-2.5.24-clean/include/asm-x86_64/smplock.h	Thu Jun 20 15:53:51 2002
+++ linux-2.5.24-dirty/include/asm-x86_64/smplock.h	Thu Jul  4 11:32:07 2002
@@ -54,7 +54,7 @@
  * so we only need to worry about other
  * CPU's.
  */
-extern __inline__ void lock_kernel(void)
+extern __inline__ void __lock_kernel(void)
 {
 #ifdef CONFIG_PREEMPT
 	if (current->lock_depth == -1)
@@ -76,7 +76,7 @@
 #endif
 }
 
-extern __inline__ void unlock_kernel(void)
+extern __inline__ void __unlock_kernel(void)
 {
 	if (current->lock_depth < 0)
 		BUG();
diff -ur linux-2.5.24-clean/include/linux/sched.h linux-2.5.24-dirty/include/linux/sched.h
--- linux-2.5.24-clean/include/linux/sched.h	Thu Jun 20 15:53:44 2002
+++ linux-2.5.24-dirty/include/linux/sched.h	Thu Jul  4 11:32:07 2002
@@ -28,6 +28,7 @@
 #include <linux/securebits.h>
 #include <linux/fs_struct.h>
 #include <linux/compiler.h>
+#include <linux/spinlock.h>
 
 struct exec_domain;
 
@@ -255,6 +256,8 @@
 	unsigned long ptrace;
 
 	int lock_depth;		/* Lock depth */
+	struct lock_trace lt[MAX_LOCK_TRACE_DEPTH];
+	int lt_dirty; 		/* don't print redundant stuff */
 
 	int prio, static_prio;
 	list_t run_list;
diff -ur linux-2.5.24-clean/include/linux/smp_lock.h linux-2.5.24-dirty/include/linux/smp_lock.h
--- linux-2.5.24-clean/include/linux/smp_lock.h	Thu Jun 20 15:53:48 2002
+++ linux-2.5.24-dirty/include/linux/smp_lock.h	Thu Jul  4 11:32:07 2002
@@ -5,8 +5,8 @@
 
 #if !defined(CONFIG_SMP) && !defined(CONFIG_PREEMPT)
 
-#define lock_kernel()				do { } while(0)
-#define unlock_kernel()				do { } while(0)
+#define __lock_kernel()				do { } while(0)
+#define __unlock_kernel()			do { } while(0)
 #define release_kernel_lock(task, cpu)		do { } while(0)
 #define reacquire_kernel_lock(task)		do { } while(0)
 #define kernel_locked() 1
diff -ur linux-2.5.24-clean/include/linux/spinlock.h linux-2.5.24-dirty/include/linux/spinlock.h
--- linux-2.5.24-clean/include/linux/spinlock.h	Thu Jun 20 15:53:52 2002
+++ linux-2.5.24-dirty/include/linux/spinlock.h	Thu Jul  4 11:38:02 2002
@@ -197,6 +197,105 @@
 #define write_trylock(lock)		_raw_write_trylock(lock)
 #endif
 
+#ifdef CONFIG_DEBUG_BKL
+/*
+ *  This will increase size of task_struct by 
+ *  MAX_LOCK_RECURSION*sizeof(lock_trace)
+ *
+ *  the longest filename that I can find is 28
+ *  KBUILD_BASENAME is 2 shorter than that
+ *  find -name '*.[ch]' | awk -F/ '{print length($(NF)), $NF}' | sort -n
+ */
+#define MAX_LOCK_TRACE_DEPTH 16
+struct lock_trace {
+	char func_name[32];
+	unsigned int line;
+};
+
+#define LT_ENTRY(i) (current->lt[(i)])
+#define LT_DIRTY    (current->lt_dirty)
+#define BKL_DEPTH    (current->lock_depth)
+#define CURR_LT_ENTRY	(LT_ENTRY(current->lock_depth))
+#define LT_LABEL	(__stringify(KBUILD_BASENAME))
+
+#define print_bkl_trace(MESSAGE)			\
+printk( MESSAGE ", depth: %d\n", BKL_DEPTH );		\
+{							\
+	int i;						\
+	for( i=0; LT_DIRTY && i<BKL_DEPTH; i++ ) {	\
+		printk( "[%2d]%s:%d\n", i, 		\
+			LT_ENTRY(i).func_name, 		\
+			LT_ENTRY(i).line );		\
+	}						\
+}							\
+
+#define lock_kernel()						\
+do {								\
+	__lock_kernel();					\
+	if( in_irq() ) {					\
+		printk( "BKL held in irq, %s:%s:%d\n",		\
+                                (__stringify(KBUILD_BASENAME)), \
+                                __FUNCTION__,                   \
+                                __LINE__ );			\
+	} else { 						\
+		strncpy(CURR_LT_ENTRY.func_name,LT_LABEL,32);	\
+		CURR_LT_ENTRY.func_name[31] = '\0';		\
+		CURR_LT_ENTRY.line = __LINE__;			\
+		current->lt_dirty = 1;				\
+	}							\
+} while (0)
+/* 
+ * er == expect recursive hold, print if that isn't found
+ */
+#define er_lock_kernel() er_lock_kernel_c(1)
+#define er_lock_kernel_c(PRINT_COUNT) 				\
+do {								\
+	static int prints_allowed = PRINT_COUNT;		\
+	if( BKL_DEPTH = -1 && (prints_allowed-->0)) {\
+		printk( "BKL not held, %s:%s:%d\n", 		\
+				(__stringify(KBUILD_BASENAME)),	\
+				__FUNCTION__,			\
+				__LINE__ );			\
+	}							\
+	lock_kernel();						\
+} while (0)
+
+/* 
+ * default number of times to print, and allow overriding it
+ */
+#define unlock_kernel()		unlock_kernel_c(1)
+
+#define unlock_kernel_c(PRINT_COUNT)					\
+do {									\
+	static int prints_allowed = PRINT_COUNT;			\
+									\
+	if( !in_irq() &&						\
+	    LT_DIRTY && BKL_DEPTH > 0 && (prints_allowed--) > 0 ) {	\
+	    print_bkl_trace( "release of recursive BKL hold" );		\
+	}								\
+	if( !in_irq() )							\
+		LT_DIRTY = 0;						\
+	__unlock_kernel();						\
+} while (0)
+#define unlock_kernel_quiet() 	\
+do {				\
+	current->lt_dirty = 0;	\
+	__unlock_kernel(); 	\
+} while(0)
+
+#else
+#define MAX_LOCK_TRACE_DEPTH 1
+struct lock_trace {};
+#define lock_kernel() __lock_kernel()
+#define lock_kernel_c(x) __lock_kernel()
+#define er_lock_kernel_c(x) __lock_kernel()
+#define er_lock_kernel() __lock_kernel()
+#define unlock_kernel() __unlock_kernel()
+#define unlock_kernel_c(x) __unlock_kernel()
+#define unlock_kernel_quiet() __unlock_kernel()
+#define print_bkl_trace(x) do {} while(0)
+#endif
+
 /* "lock on reference count zero" */
 #ifndef ATOMIC_DEC_AND_LOCK
 #include <asm/atomic.h>
diff -ur linux-2.5.24-clean/kernel/sched.c linux-2.5.24-dirty/kernel/sched.c
--- linux-2.5.24-clean/kernel/sched.c	Thu Jun 20 15:53:47 2002
+++ linux-2.5.24-dirty/kernel/sched.c	Thu Jul  4 11:32:07 2002
@@ -815,6 +815,9 @@
 	prev = current;
 	rq = this_rq();
 
+	if( kernel_locked() ) {
+		print_bkl_trace("BKL held during sleep");
+	}
 	release_kernel_lock(prev, smp_processor_id());
 	prepare_arch_schedule(prev);
 	prev->sleep_timestamp = jiffies;

Re: BKL removal

[Dave Hansen]

Matthew Wilcox wrote:
> aw.  you implemented the less useful check of the two you mentioned!
> i think the release-on-sleep property of the BKL is far more harmful
> than the recursive-holds.  release-on-sleep means that you probably
> have a race there you didn't know about (eg the one i found in setfl
> earlier this week), and means you need to do some serious work in order
> to redesign your code to eliminate the race.

Be careful what you ask for.  These release-on-sleep calls happen 
quite often, maybe as often as a few a second and I can't think of any 
elegant ways of limiting the number of unique printk()s in schedule(). 
  It was easy to limit the printing for a single un/lock_kernel() call 
with static variables, but the scheduling ones are a bit more 
complicated.  I can think of some convoluted ways of doing this, but 
no simple ones.  If you apply this patch, be ready for a load of stuff 
in dmesg!

> once you've done that redesign, chances are you'll understand the locking
> in that area well enough to know that there are no recursive holds in your
> code and you'll switch to a spinlock.  this will automagically reduce the
> number of recursive-holds simply because fewer places will take the BKL.

Some of the times that I've either broken someone else's code or 
simply pointed it out to them, they've fixed it.

> as an aside, replacing the BKL by a non-recursive spinlock isn't always a
> great idea:
...<snip> look at the original if you want to see the whole call sequence!
> it doesn't look _too_ hard to persuade ext2_new_block (btw, the problem
> also occurs with ext2_free_blocks) to unlock_super and retry, but that's
> slightly more dangerous work than i want to do right now ... particularly
> since some of these interfaces may change dramatically as a result of
> the aio work.

That's icky.  So, was this potential problem introduced during Al's 
BKL replacement in ext2?  The real problem here is the faulting 
operation while holding a spinlock which requires the spinlock to 
resolve, right?  I think that all you can do is release the lock, try 
to get some memory, and start the process over.  This is the kind of 
thing that I hope my patch will help us find so that we don't all need 
to have a Viroesque understanding of VFS :)

BTW, the Brits don't have any big parties today, do they?

-- 
Dave Hansen
haveblue@us.ibm.com

Re: BKL removal

[Matthew Wilcox]

On Thu, Jul 04, 2002 at 12:02:30AM -0700, Dave Hansen wrote:
> I've created a patch that helps find bad uses of the big kernel lock.
>   It is explained in detail here:
> http://marc.theaimsgroup.com/?l=linux-kernel&m=102535814329494&w=2

aw.  you implemented the less useful check of the two you mentioned!
i think the release-on-sleep property of the BKL is far more harmful
than the recursive-holds.  release-on-sleep means that you probably
have a race there you didn't know about (eg the one i found in setfl
earlier this week), and means you need to do some serious work in order
to redesign your code to eliminate the race.

once you've done that redesign, chances are you'll understand the locking
in that area well enough to know that there are no recursive holds in your
code and you'll switch to a spinlock.  this will automagically reduce the
number of recursive-holds simply because fewer places will take the BKL.

as an aside, replacing the BKL by a non-recursive spinlock isn't always a
great idea:

        /*
         * Nasty deadlock avoidance.
         *
         * ext2_new_block->getblk->GFP->shrink_dcache_memory->prune_dcache->
         * prune_one_dentry->dput->dentry_iput->iput->inode->i_sb->s_op->
         * put_inode->ext2_discard_prealloc->ext2_free_blocks->lock_super->
         * DEADLOCK.
         *
         * We should make sure we don't hold the superblock lock over
         * block allocations, but for now:
         */
        if (!(gfp_mask & __GFP_FS))
                return 0;

so we now decline to scavenge memory from the dcache or the icache if a
filesystem causes the system to decide it's low on memory.  this isn't
a good thing.

btw, this comment is somewhat abbreviated.  the sequence is actually:
ext2_new_block->load_block_bitmap->read_block_bitmap->sb_bread->__bread->
__getblk->grow_buffers->grow_dev_page->find_or_create_page->alloc_page->
...

it doesn't look _too_ hard to persuade ext2_new_block (btw, the problem
also occurs with ext2_free_blocks) to unlock_super and retry, but that's
slightly more dangerous work than i want to do right now ... particularly
since some of these interfaces may change dramatically as a result of
the aio work.

-- 
Revolutions do not require corporate support.