BKL removal
Subsystems (2)
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
<copied to lkml, as people there deserve to also see this>
Quoted 13 lines · Dave Hansen
Quoted 12 lines · Rik van Riel
Quoted 9 lines · Dave Hansen
Quoted 4 lines · Greg KH
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.
Quoted 7 lines
Quoted 1 line
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.
Quoted 4 lines
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 :)
Quoted 7 lines
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.
Quoted 4 lines
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
[..]
Quoted 4 lines
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.
[..]
Quoted 11 lines
Quoted 4 lines
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.
Quoted 5 lines
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
Quoted 12 lines · Oliver Neukum
Quoted 12 lines
Quoted 4 lines
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.
Quoted 8 lines
Quoted 5 lines
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.
Quoted 2 lines
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.
Quoted 4 lines
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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 6 lines
Quoted 3 lines
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.
Quoted 3 lines
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.
Quoted 7 lines
Quoted 2 lines
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?
Quoted 7 lines
Quoted 4 lines
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
Quoted 6 lines · Greg KH
Quoted 1 line
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.
Quoted 6 lines
Quoted 1 line
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.
Quoted 7 lines
Quoted 1 line
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.
Quoted 5 lines
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.
Signature · 2 lines
Dave Hansen [email protected]
Hi,
Quoted 6 lines · Dave Hansen
"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
Signature · 7 lines
(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------
Quoted 10 lines · Thunder from the hill
Quoted 6 lines
"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;}
Signature · 2 lines
Dave Hansen [email protected]
Hi,
Quoted 1 line · Dave Hansen
Old Blue? 23 isn't _that_ old!
Obviously, you never read that book about the IBM s/370 named "Old Blue"...
Quoted 10 lines
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
Signature · 7 lines
(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------
Quoted 6 lines · Thunder from the hill
Quoted 1 line · Dave Hansen
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?"
Quoted 5 lines
Quoted 3 lines
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.
Quoted 1 line
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.
Quoted 1 line
You're possibly right about this one. What did Greg K-H say?
Only time will tell...
Signature · 2 lines
Dave Hansen [email protected]
Hi,
Quoted 2 lines · Dave Hansen
Nope. I missed that one. Something like "The Little Mainfraime that could?"
It was "The Y2K bug - the last day" by some Marc.
Quoted 4 lines
Quoted 1 line
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?!
Quoted 5 lines
Quoted 2 lines
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
Signature · 7 lines
(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------
commence Thunder from the hill quotation:
Quoted 3 lines
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).
Signature · 4 lines
/ | [|] Sean Neakums | Questions are a burden to others; [|] <[email protected]> | answers a prison for oneself. \ |
Quoted 8 lines
Quoted 6 lines
"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.
Quoted 4 lines
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
Quoted 10 lines · Oliver Neukum
Quoted 7 lines
Quoted 5 lines
"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?
Quoted 10 lines
Quoted 4 lines
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_ATOMICunder 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.
Quoted 1 line
This should have been posted on linux-usb long ago.
I just pulled it out of thin air 10 minutes ago!
Signature · 2 lines
Dave Hansen [email protected]
Quoted 5 lines · Dave Hansen
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_dataeither 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.
Signature · 1 line
Revolutions do not require corporate support.
Quoted 9 lines · Matthew Wilcox
Quoted 2 lines · Dave Hansen
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 thefile->private_dataeither 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?
Quoted 7 lines
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
Quoted 2 lines
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).
Signature · 2 lines
Dave Hansen [email protected]
Quoted 6 lines · Dave Hansen
Quoted 3 lines
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_dataduring 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.
Quoted 7 lines
Quoted 7 lines
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...
Quoted 8 lines · Alexander Viro
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.
Signature · 1 line
Revolutions do not require corporate support.
Quoted 11 lines · Matthew Wilcox
Quoted 8 lines · Alexander Viro
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...
Quoted 4 lines
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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 4 lines · Dave Hansen
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".
Signature · 1 line
Revolutions do not require corporate support.
Quoted 4 lines · Matthew Wilcox
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.
Quoted 10 lines · Alexander Viro
Quoted 4 lines · Matthew Wilcox
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
Signature · 2 lines
Dave Hansen [email protected]
Quoted 7 lines · Alexander Viro
Quoted 4 lines · Matthew Wilcox
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...
Signature · 1 line
Revolutions do not require corporate support.
Quoted 4 lines
Quoted 2 lines
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.
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
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?
Quoted 7 lines
Quoted 5 lines
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_ATOMICunder 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.
Quoted 4 lines
over a schedule()able operation. If I remember right, there is no real protection needed for the
file->private_dataeither 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.
Quoted 3 lines
Quoted 1 line
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
Quoted 5 lines
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
Quoted 9 lines · Oliver Neukum
Quoted 4 lines
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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 10 lines · Dave Hansen
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
Quoted 19 lines · Greg KH
Quoted 3 lines · Dave Hansen
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 filedrivers/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 thekmalloc()call. But since I don't understand all of the different locking rules inside theuhci-hcd.cdriver, I'm not going to do this. I'll
Quoted 8 lines
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.
Quoted 4 lines
- 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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 5 lines · Dave Hansen
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 :)
Quoted 9 lines
Quoted 4 lines
- 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
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
Quoted 11 lines · 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)?
{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.)
Quoted 7 lines
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.
Quoted 4 lines
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
Quoted 7 lines · 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
Quoted 3 lines · Rick Lindsley
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
Quoted 3 lines · 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
Quoted 3 lines · Rick Lindsley
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
Quoted 2 lines · William Lee Irwin III
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
Quoted 7 lines · Robert Love
Quoted 2 lines · William Lee Irwin III
This is an ugly aspect. But AFAICT the most that's needed to clean it up is an explicit release before potentially sleeping.
Quoted 6 lines
Yep that is all we need... remove the
release_kernel_lock()andreacquire_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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 8 lines · Dave Hansen
Quoted 2 lines · Robert Love
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
Quoted 4 lines · Robert Love
Quoted 2 lines · Dave Hansen
Robert Love wrote:
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
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!
Signature · 2 lines
Dave Hansen [email protected]
Quoted 2 lines · Dave Hansen
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
Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
Quoted 9 lines · Dave Hansen
Quoted 3 lines
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:
And see if you can write a smatch script to get a good broom for this trash 8)
- Arnaldo
Quoted 10 lines · Arnaldo Carvalho de Melo
Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
Quoted 9 lines · Dave Hansen
Quoted 3 lines
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.
Quoted 5 lines
Try smatch:
And see if you can write a smatch script to get a good broom for this trash 8)
Quoted 14 lines · Alexander Viro
Quoted 10 lines · Arnaldo Carvalho de Melo
Em Tue, Jul 09, 2002 at 02:47:49PM -0700, Robert Love escreveu:
Quoted 8 lines · Dave Hansen
Quoted 2 lines
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.
Quoted 7 lines
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.
Quoted 3 lines
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.
Signature · 2 lines
Dave Hansen [email protected]
Quoted 5 lines · Dave Hansen
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.
Quoted 6 lines
Quoted 3 lines
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...
Quoted 9 lines · Alexander Viro
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
Quoted 2 lines · Dave Hansen
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.
Quoted 8 lines · David Wagner
Quoted 2 lines · Dave Hansen
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.
Signature · 1 line
Daniel
Quoted 4 lines
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 allcond_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)
Quoted 2 lines
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
Quoted 2 lines · Alan Cox
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
Quoted 6 lines · Alan Cox
Quoted 2 lines
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
Quoted 16 lines · Alan Cox
Quoted 6 lines · Alan Cox
Quoted 2 lines
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.
Quoted 5 lines
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
Signature · 3 lines
Alexander Hoogerhuis | [email protected] CCNP - CCDP - MCNE - CCSE | +47 908 21 485 "You have zero privacy anyway. Get over it." --Scott McNealy
Quoted 4 lines · Alexander Hoogerhuis
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
Signature · 3 lines
Bravely reimplemented by the knights who say "NIH". http://www.surriel.com/ http://distro.conectiva.com/
Hi,
Quoted 3 lines · Rik van Riel
Quoted 1 line
"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
Signature · 7 lines
(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------
Quoted 2 lines · Robert Love
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
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
Quoted 8 lines · 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.
[ ... ]
Quoted 8 lines
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
_actuallybeentested_.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.
Quoted 1 line
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 :)
Quoted 2 lines
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
Quoted 9 lines
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
Quoted 5 lines · Drew P. Vogel
Quoted 5 lines
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.
Quoted 8 lines
Quoted 4 lines
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.
Quoted 7 lines
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 takelock_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.
Quoted 2 lines
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 :)
Signature · 2 lines
Dave Hansen [email protected]
Quoted 4 lines
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
Quoted 1 line
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.
Quoted 2 lines
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.
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm
Hi,
Quoted 6 lines · Larry McVoy
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
[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:
[...]
Quoted 5 lines
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.
[...]
Quoted 2 lines
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.
Signature · 5 lines
____/ ____/ /
/ / / Marco Colombo
___/ ___ / / Technical Manager
/ / / ESI s.r.l.
_____/ _____/ _/ [email protected]Quoted 3 lines · Marco Colombo
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.
Signature · 1 line
Revolutions do not require corporate support.
Quoted 3 lines · Marco Colombo
Quoted 3 lines
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?
Quoted 6 lines · Matthew Wilcox
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_structlock or thefilp->lock. There's a big difference if you have to grab thefilp->pos_lock, thefilp->ra_lockand thefilp->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
Quoted 13 lines · William Lee Irwin III
Quoted 3 lines · Marco Colombo
Quoted 3 lines
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?
Quoted 6 lines · Matthew Wilcox
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_structlock or thefilp->lock. There's a big difference if you have to grab thefilp->pos_lock, thefilp->ra_lockand thefilp->iobuf_lock. You'd have to know what order to grab them in, for a start.
Quoted 2 lines
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.
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.
Quoted 2 lines
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
Quoted 6 lines · Rick Lindsley
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.
Quoted 4 lines
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.
Signature · 1 line
Daniel
Re: spinlock assertion macros
Quoted 13 lines · Daniel Phillips
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_lockis 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.
Quoted 3 lines
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
fs/inode.c +2 -0
@@ -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 ;
include/linux/spinlock.h +12 -0
@@ -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
Quoted 24 lines · Jesse Barnes
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/dontdifflinux-2.5.25/fs/inode.clinux-2.5.25-spinassert/fs/inode.cfs/inode.c +2
-0@@ -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/dontdifflinux-2.5.25/include/linux/spinlock.hlinux-2.5.25-spinassert/include/linux/spinlock.h
include/linux/spinlock.h line 126
Quoted 9 lines
include/linux/spinlock.h +6
-0@@ -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
Quoted 9 lines · Andreas Dilger
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
fs/inode.c +2 -0
@@ -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 ;
include/linux/spinlock.h +16 -0
@@ -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
In reply to Jesse BarnesQuoted 14 lines · Jesse Barnes
Quoted 13 lines · Daniel Phillips
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_lockis 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.
Quoted 8 lines
Quoted 3 lines
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.
Signature · 1 line
Daniel
Re: spinlock assertion macros
Quoted 34 lines · Daniel Phillips
Quoted 14 lines · Jesse Barnes
Quoted 13 lines · Daniel Phillips
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_lockis 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.Quoted 8 lines
Quoted 3 lines
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:
Quoted 4 lines
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.
Quoted 13 lines
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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 6 lines
George Anzinger [email protected] 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: spinlock assertion macros
In reply to Daniel PhillipsQuoted 10 lines · Daniel Phillips
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.
Quoted 2 lines
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.
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
Re: spinlock assertion macros
Quoted 7 lines · Oliver Xymoron
Quoted 4 lines · Daniel Phillips
I was thinking of something as simple as:
#define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))
Quoted 8 lines
Quoted 6 lines
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
Quoted 23 lines · Sandy Harris
Quoted 7 lines · Oliver Xymoron
Quoted 4 lines · Daniel Phillips
I was thinking of something as simple as:
#define spin_assert_locked(LOCK) BUG_ON(!spin_is_locked(LOCK))Quoted 8 lines
Quoted 6 lines
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:
Quoted 6 lines
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.
Signature · 1 line
Daniel
Re: spinlock assertion macros
In reply to Sandy HarrisQuoted 13 lines · Sandy Harris
Quoted 12 lines · Oliver Xymoron
Quoted 9 lines · Daniel Phillips
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:
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
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).
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
Re: spinlock assertion macros
In reply to Daniel PhillipsQuoted 10 lines · Daniel Phillips
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...
Quoted 2 lines
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
fs/inode.c +2 -0
@@ -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 ;
include/linux/spinlock.h +13 -1
@@ -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
Quoted 1 line · Jesse Barnes
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.
Quoted 2 lines
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.
Quoted 1 line
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.
Quoted 47 lines
Thanks,
Jessediff -Naur -X
/home/jbarnes/dontdifflinux-2.5.25/fs/inode.clinux-2.5.25-spinassert/fs/inode.cfs/inode.c +2
-0@@ -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/dontdifflinux-2.5.25/include/linux/spinlock.hlinux-2.5.25-spinassert/include/linux/spinlock.hinclude/linux/spinlock.h +13
-2@@ -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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 1 line
Daniel
Re: spinlock assertion macros
Quoted 6 lines · Daniel Phillips
Quoted 1 line · Jesse Barnes
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.
Signature · 2 lines
| Dave Jones. http://www.codemonkey.org.uk | SuSE Labs
Re: spinlock assertion macros
Quoted 11 lines · Dave Jones
Quoted 6 lines · Daniel Phillips
Quoted 1 line · Jesse Barnes
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.)
Quoted 2 lines
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?
Quoted 4 lines
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_countfor 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().
Signature · 1 line
Daniel
Re: spinlock assertion macros
Quoted 1 line · Daniel Phillips
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
Quoted 9 lines · Arnd Bergmann
Quoted 1 line · Daniel Phillips
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.
Quoted 7 lines
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()orNEVER_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 orpreempt_disablearound 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.
Signature · 1 line
Daniel
Re: spinlock assertion macros
Quoted 4 lines · Daniel Phillips
So far, only the
MUST_HOLDstyle of executable locking documentation has really survived scrutiny. It needs some variants:MUST_HOLD_READ,MUST_HOLD_WRITE,MUST_HOLD_SEM,MUST_HOLD_READ_SEMandMUST_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
fs/inode.c +2 -0
@@ -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 ;
include/asm-ia64/spinlock.h +2 -0
@@ -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 { \
include/linux/spinlock.h +15 -1
@@ -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
Quoted 9 lines · Jesse Barnes
Quoted 4 lines · Daniel Phillips
So far, only the
MUST_HOLDstyle of executable locking documentation has really survived scrutiny. It needs some variants:MUST_HOLD_READ,MUST_HOLD_WRITE,MUST_HOLD_SEM,MUST_HOLD_READ_SEMandMUST_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...
Quoted 8 lines
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.
Signature · 1 line
Daniel
PATCH 1/1 spinlock assertion macros for 2.5.26
Quoted 6 lines · Daniel Phillips
You could create
linux/semaphore.hwhich includesasm/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.
Quoted 3 lines
Quoted 3 lines
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).
Quoted 3 lines
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
fs/inode.c +2 -0
@@ -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 ;
include/asm-ia64/spinlock.h +1 -0
@@ -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 { \
include/linux/spinlock.h +13 -1
@@ -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: spinlock assertion macros
In reply to Jesse BarnesQuoted 8 lines · Jesse Barnes
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: spinlock assertion macros
In reply to Daniel PhillipsQuoted 21 lines · Daniel Phillips
Quoted 11 lines · Dave Jones
Quoted 6 lines · Daniel Phillips
Quoted 1 line · Jesse Barnes
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.)Quoted 2 lines
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?
Quoted 8 lines
Quoted 4 lines
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_countfor a quick-n-dirty implementation (without the additional info of which locks we hold, lock-taker, etc).
Spin_lockjust 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.
Quoted 5 lines
Any idea how one might implement
NEVER_SLEEPS()? Maybe as:
NEVER_[code goes here]_SLEEPSwhich 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.
Signature · 1 line
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."
Re: spinlock assertion macros
Quoted 19 lines · Oliver Xymoron
Quoted 18 lines · Daniel Phillips
Quoted 3 lines · Dave Jones
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.)Quoted 2 lines
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?
Quoted 4 lines
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_countfor a quick-n-dirty implementation (without the additional info of which locks we hold, lock-taker, etc).
Quoted 7 lines
Quoted 3 lines
Spin_lockjust 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.
Quoted 2 lines
You'll need a helper function -
current()is hard to get at fromspinlock.hdue 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.
Quoted 3 lines
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.
Quoted 9 lines
Quoted 5 lines
Any idea how one might implement
NEVER_SLEEPS()? Maybe as:
NEVER_[code goes here]_SLEEPSwhich inc/dec the preeempt count, triggering a BUG in
schedule().
NEVER_SLEEPSwill only trigger on the rare events that blow up anyway, while theMAY_SLEEPversion catches _potential_ problems even when the fatal sleep doesn't happen.
Yes, that one's already been rejected as largely pointless.
Signature · 1 line
Daniel
Re: spinlock assertion macros
In reply to Dave JonesQuoted 4 lines · Dave Jones
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_countfor 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
Quoted 9 lines · Robert Love
Quoted 4 lines
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_countfor 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_countonschedule(), checkpreempt_countin usleep/msleep (Arjan's idea), and checkpreempt_countin 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
Signature · 2 lines
| Dave Jones. http://www.codemonkey.org.uk | SuSE Labs
Re: spinlock assertion macros
In reply to Jesse BarnesOn 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 <><
Quoted 7 lines · Dave Hansen
"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.
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
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?
Quoted 8 lines
Quoted 4 lines
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.)
Quoted 2 lines
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? :)
Quoted 11 lines
Quoted 10 lines
Quoted 4 lines
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.
Quoted 5 lines
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
Quoted 3 lines · In article <[email protected]> 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
Hi!
Quoted 11 lines
Quoted 4 lines
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.
Quoted 3 lines
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
Signature · 2 lines
Worst form of spam? Adding advertisment signatures ala sourceforge.net. What goes next? Inserting advertisment *into* email?