[CHECKER] a couple potential deadlocks in 2.4.5-ac8

[CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Dawson Engler]

Hi All,

we're starting to develop a checker that finds deadlocks by (1)
computing all lock acquisition paths and (2) checking if two paths
violate a partial order.

E.g., for two threads T1 and T2:
	T1: foo acquires A --> calls bar which tries to acquire B
	T2: baz acquires B --> calls blah which tries to acquire A
all else being equal, this deadlocks.

The checker is pretty primitive.  In particular:
	- lots of false negatives come from the fact that it does not 
	  track interrupt disabling.  A missed deadlock:
		foo acquires A
		bar interrupts foo, disables interrupts, tries to acquire A
	  (Is this the most common deadlock?)

	- many potential false positives since it does not realize when
	two kernel call traces are mutually exclusive.

To check it's mechanics I've enclosed what look to me to be two potential
deadlocks --- given the limits of the tool and my understanding of what
can happen when, these could be (likely be?) false positive, so I'd
appreciate any corrective feedback.

Dawson
--------------------------------------------------------------------
ERROR: violated partial order [lock_super:sb<--->lock_kernel:$none$]
   path for lock_super:sb -> lock_kernel:$none$

seems reasonable: all contained in the same FS.

       path for lock_super:sb -> lock_kernel:$none$
                sysv_new_inode:100:lock_super(sb) --> 145:sysv_write_inode
                        -->sysv_write_node:1183:lock_kernel

        path for lock_kernel -> lock_super:sb
                sysv_get_block:812:lock_kernel --> 855:block_getblk
                  --> block_getblk:766:sysv_free_block
                  --> sysv_free_block:45:lock_super

--------------------------------------------------------------------
ERROR: violated partial order [lock_super:sb<--->lock_kernel:$none$]
   path for lock_super:sb -> lock_kernel:$none$

[BUG] Unless lock_kernel already held, which is certainly possible...

       path for lock_super:sb -> lock_kernel:$none$
               sysv_new_inode:100:lock_super(sb);
                        --> sysv_write_inode:1134:lock_kernel();

       path for lock_kernel--> lock_super:
                fsync_dev:325:lock_kernel --> sync_supers:599:lock_super

-------------------------------------------------------------------

checker suggestion

[Albert D. Cahalan]

Struct padding is a problem. Really, there shouldn't be any
implicit padding. This causes:

1. security leaks when such structs are copied to userspace
   (the implicit padding is uninitialized, and so may contain
   a chunk of somebody's private key or password)

2. bloat, when struct members could be reordered to eliminate
   the need for padding

Re: checker suggestion

[Dawson Engler]

> Struct padding is a problem. Really, there shouldn't be any
> implicit padding. This causes:
> 
> 1. security leaks when such structs are copied to userspace
>    (the implicit padding is uninitialized, and so may contain
>    a chunk of somebody's private key or password)
> 
> 2. bloat, when struct members could be reordered to eliminate
>    the need for padding

(1) is a great point.   One of the first extensions in our first system
automatically reordered structure fields to minimize padding (your second
point), but we'd totally missed the security point.

Thanks!

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Alexander Viro]

On Sat, 9 Jun 2001, Dawson Engler wrote:

> Hi All,
> 
> we're starting to develop a checker that finds deadlocks by (1)
> computing all lock acquisition paths and (2) checking if two paths
> violate a partial order.
> 
> E.g., for two threads T1 and T2:
> 	T1: foo acquires A --> calls bar which tries to acquire B
> 	T2: baz acquires B --> calls blah which tries to acquire A
> all else being equal, this deadlocks.
> 
> The checker is pretty primitive.  In particular:
> 	- lots of false negatives come from the fact that it does not 
> 	  track interrupt disabling.  A missed deadlock:
> 		foo acquires A
> 		bar interrupts foo, disables interrupts, tries to acquire A
> 	  (Is this the most common deadlock?)
> 
> 	- many potential false positives since it does not realize when
> 	two kernel call traces are mutually exclusive.
> 
> To check it's mechanics I've enclosed what look to me to be two potential
> deadlocks --- given the limits of the tool and my understanding of what
> can happen when, these could be (likely be?) false positive, so I'd
> appreciate any corrective feedback.

BKL is special. It has no nesting constraints wrt. semaphores. It is
a spinlock, but we are allowed to block while holding it - then it will
be released and the next time we get a timeslice we will start with
attempt to reacquire it.

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Linus Torvalds]

In article <200106090759.AAA15771@csl.Stanford.EDU>,
Dawson Engler  <engler@csl.Stanford.EDU> wrote:
>
>we're starting to develop a checker that finds deadlocks by (1)
>computing all lock acquisition paths and (2) checking if two paths
>violate a partial order.

Looks good. 

>The checker is pretty primitive.  In particular:
>	- lots of false negatives come from the fact that it does not 
>	  track interrupt disabling.  A missed deadlock:
>		foo acquires A
>		bar interrupts foo, disables interrupts, tries to acquire A
>	  (Is this the most common deadlock?)

You actually find something like this at all? I would have assumed that
you would never see this as a path, as interrupts aren't explicit calls.

>	- many potential false positives since it does not realize when
>	two kernel call traces are mutually exclusive.

On the other hand, they should be mutually exclusive only by virtue of
using some kind of locking, so this should show up in your locking order
thing.

The rule is

 - A -> B can deadlock with B -> A

BUT

 - A -> B -> C	cannot deadlock with A -> C -> B

by wirtue of "A" acting as the master lock.  So you should be able to
see these things (arguably the "cannot deadlock" case is still a very
ugly case, and also implies that B and C are irrelevant, as A already
took care of exclusivity.  So getting a warning for this might be fine). 

>To check it's mechanics I've enclosed what look to me to be two potential
>deadlocks --- given the limits of the tool and my understanding of what
>can happen when, these could be (likely be?) false positive, so I'd
>appreciate any corrective feedback.

They are, but for a very special reason: the big kernel lock is special.

The big kernel lock rules are that it's a "normal spinlock" in many
regards, BUT you can block while holding it, and the BKL will magically
be released during the blocking.  This means, for example, that the BKL
can never deadlock with a semaphore - if a BKL holder blocks on sombody
elses semaphore (and that somebody else wants the BKL), then the act of
blocking on the semaphore will release the BKL, and allow the original
semaphore holder to continue. 

The same is currently true of the global irq lock too (with the caveat
that we don't even re-aquire it after a schedule()), but that is going
to change, so I would suggest you _not_ special-case the global irq
lock.

But the big kernel lock is so special that I suspect it needs some
special casing to avoid too many false reports.

			Linus

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Alexander Viro]

On 9 Jun 2001, Linus Torvalds wrote:

> The big kernel lock rules are that it's a "normal spinlock" in many
> regards, BUT you can block while holding it, and the BKL will magically
> be released during the blocking.  This means, for example, that the BKL
> can never deadlock with a semaphore - if a BKL holder blocks on sombody
> elses semaphore (and that somebody else wants the BKL), then the act of
> blocking on the semaphore will release the BKL, and allow the original
> semaphore holder to continue. 

Another difference from spinlocks is that BKL is recursive. I'm
actually surprised that it didn't show up first.

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Linus Torvalds]

On Sat, 9 Jun 2001, Alexander Viro wrote:
> 
> Another difference from spinlocks is that BKL is recursive. I'm
> actually surprised that it didn't show up first.

Good point. Spinlocks (with the exception of read-read locks, of course)
and semaphores will deadlock on recursive use, while the BKL has this
"process usage counter" recursion protection.

I'm not THAT suprised that it didn't show up first - I suspect we are
getting close to the point where we could actually start to remove it. The
big kernel lock is not used that much any more, and there aren't that many
things that are recursively invoced any more. 

The big reason for having a recursive lock for the BKL was because things
like page faults had to nest with other users of the BKL, but since the VM
should be pretty much entirely BKL-free the only real remaining part is
probably small parts of the low-level filesystems (notably things like
"readpage()" calling down to the get_block() functions).

And I suspect that the current checker doesn't realize that any user mode
access is equivalent to calling "do_page_fault()" from a call-chain
standpoint.

Dawson - the user-mode access part is probably _the_ most interesting from
a lock checking standpoint, could you check doing the page fault case?

Anyway, in a 2.5.x timeframe we should probably make sure that we do not
have the need for a recursive BKL any more. That shouldn't be that hard to
fix, especially with help from CHECKER to verify that we didn't forget
some case.

(Even if we were to not need the recursiveness of the BKL, I doubt it
would mean that we'd change the implementation. The "release BKL on
schedule" semantic still means that we'd have to maintain one bit of
"counter", and then we might as well do the full thing. But considering
recursion to be a bug would probably make it easier to continue the
removal of the BKL).

			Linus

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[David Woodhouse]

torvalds@transmeta.com said:
>  Good point. Spinlocks (with the exception of read-read locks, of
> course) and semaphores will deadlock on recursive use, while the BKL
> has this "process usage counter" recursion protection.

Obtaining a read lock twice can deadlock too, can't it?

	A		B
	read_lock()
			write_lock()
			...sleeps...
	read_lock()
	...sleeps...

Or do we not make new readers sleep if there's a writer waiting?

--
dwmw2

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Linus Torvalds]

In article <19317.992115181@redhat.com>,
David Woodhouse  <dwmw2@infradead.org> wrote:
>
>Obtaining a read lock twice can deadlock too, can't it?

If it does (with spinlocks), then that's an implementation bug (which
might well be there).  We depend on the read-lock being recursive in a
lot of places, notably the fact that we don't disable interrupts while
holding read-locks if we know that the interrupt routines only take a
read-lock. 

>	A		B
>	read_lock()
>			write_lock()
>			...sleeps...
>	read_lock()
>	...sleeps...
>
>Or do we not make new readers sleep if there's a writer waiting?

The writer-waiter should not be spinning with the write lock held.

Note that the blocking versions are different, and I explicitly meant
only the read-spinlocks, not read-semaphores. For the semaphores I think
your schenario is indeed correct.

		Linus

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Rusty Russell]

In message <19317.992115181@redhat.com> you write:
> 
> torvalds@transmeta.com said:
> >  Good point. Spinlocks (with the exception of read-read locks, of
> > course) and semaphores will deadlock on recursive use, while the BKL
> > has this "process usage counter" recursion protection.
> 
> Obtaining a read lock twice can deadlock too, can't it?
> 
> 	A		B
> 	read_lock()
> 			write_lock()
> 			...sleeps...
> 	read_lock()
> 	...sleeps...
> 
> Or do we not make new readers sleep if there's a writer waiting?

We can never[1] make new readers sleep if there's a writer waiting, as
Linus guaranteed that an IRQ handler which only ever grabs a read lock
means the rest of the code doesn't need to block interrupts on its
read locks (see Documentation/spinlock.txt IIRC).

Also, netfilter will break (brlocks inherit this property from
their spinlocks constituents).

Rusty.
[1] Well, we could, but we'd have to do a special "same CPU?" check,
    which would suck badly.
--
Premature optmztion is rt of all evl. --DK

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[David Woodhouse]

rusty@rustcorp.com.au said:
> In message <19317.992115181@redhat.com> you write:
> > torvalds@transmeta.com said:
> > >  Good point. Spinlocks (with the exception of read-read locks, of
> > > course) and semaphores will deadlock on recursive use, while the BKL
> > > has this "process usage counter" recursion protection.
> > 
> > Obtaining a read lock twice can deadlock too, can't it
> > Or do we not make new readers sleep if there's a writer waiting?
>
> We can never[1] make new readers sleep if there's a writer waiting, as
> Linus guaranteed that an IRQ handler which only ever grabs a read lock
> means the rest of the code doesn't need to block interrupts on its
> read locks (see Documentation/spinlock.txt IIRC).

You're right. Despite the fact that upon closer examination it's obvious
that Linus was only referring to rw-spinlocks as safe, I was actually
thinking of rw-semaphores. 

--
dwmw2

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Alexander Viro]

On Sat, 9 Jun 2001, Linus Torvalds wrote:

> Anyway, in a 2.5.x timeframe we should probably make sure that we do not
> have the need for a recursive BKL any more. That shouldn't be that hard to
> fix, especially with help from CHECKER to verify that we didn't forget
> some case.

True, but... I can easily see the situation when ->foo() and ->bar()
both call a helper function which needs BKL for a small piece of code.
->foo() callers take BKL (and it's choke-full of places that still need
BKL, anyway). ->bar() is called without BKL. Moreover, grabbing BKL
over the whole helper is a massive overkill.

ObUnrelated: fs/super.c is getting to the point where it naturally
falls into two files - one that deals with mount cache and all things
vfsmount-related, mount tree manipulations, etc. and another that deals
with superblocks. Mind if I split the thing?

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Linus Torvalds]

On Sat, 9 Jun 2001, Alexander Viro wrote:
> 
> True, but... I can easily see the situation when ->foo() and ->bar()
> both call a helper function which needs BKL for a small piece of code.

I'd hope that we can fix the small helper functions to not need BKL -
there are already many circumstances where you can't use the BKL anyway
(ie you already hold a spinlock - I'd really like to have the rule that
the BKL is the "outermost" of all spinlocks, as we could in theory some
day use it as a point to schedule away on BKL contention).

> ObUnrelated: fs/super.c is getting to the point where it naturally
> falls into two files - one that deals with mount cache and all things
> vfsmount-related, mount tree manipulations, etc. and another that deals
> with superblocks. Mind if I split the thing?

Sure. As long as there is some sane naming and not too many new non-static
functions. Maybe just "fs/mount.c" for the vfsmount caches etc.

		Linus

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Alexander Viro]

On Sat, 9 Jun 2001, Linus Torvalds wrote:

> On Sat, 9 Jun 2001, Alexander Viro wrote:
> > 
> > True, but... I can easily see the situation when ->foo() and ->bar()
> > both call a helper function which needs BKL for a small piece of code.
> 
> I'd hope that we can fix the small helper functions to not need BKL -
> there are already many circumstances where you can't use the BKL anyway
> (ie you already hold a spinlock - I'd really like to have the rule that
> the BKL is the "outermost" of all spinlocks, as we could in theory some
> day use it as a point to schedule away on BKL contention).
> 
> > ObUnrelated: fs/super.c is getting to the point where it naturally
> > falls into two files - one that deals with mount cache and all things
> > vfsmount-related, mount tree manipulations, etc. and another that deals
> > with superblocks. Mind if I split the thing?
> 
> Sure. As long as there is some sane naming and not too many new non-static
> functions. Maybe just "fs/mount.c" for the vfsmount caches etc.

Umm... In the final variant of patch all interaction is done by
alloc_vfsmnt() and set_devname() on one side and kill_super(),
do_kern_mount() and do_remount_sb() on another. That is, aside
of the currently public functions (actually, some of them are
gone - kern_umount is #defined to mntput and kern_mount became
a trivial inlined wrapper around do_kern_mount, change_root is
gone, etc.).

In my variant it was called fs/namespace.c, basically since I prefer
the names along the line "what does it deal with" (answer: user-visible
namespace) to "what action is done here" ones, especially since mount(2)
is not the only syscall exported (pivot_root(2) and umount(2) are also
handled here).

After all, inode.c, dcache.c, buffer.c, locks.c, devices.c, etc. are named
that way. OTOH, open.c and namei.c are not, so... Up to you - my preference
would be a noun and namespace looks better than next contender (mntcache),
but that's your call - filenames in core kernel...

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Dawson Engler]

> On Sat, 9 Jun 2001, Alexander Viro wrote:
> > 
> > Another difference from spinlocks is that BKL is recursive. I'm
> > actually surprised that it didn't show up first.
> 
> Good point. Spinlocks (with the exception of read-read locks, of course)
> and semaphores will deadlock on recursive use, while the BKL has this
> "process usage counter" recursion protection.

Actually, it did show up all over the place --- I'd just selected two
candidates to examine out of hundreds.  (Checking call chains is
strenous, even when you know what you're looking for.)

> And I suspect that the current checker doesn't realize that any user mode
> access is equivalent to calling "do_page_fault()" from a call-chain
> standpoint.
>
> Dawson - the user-mode access part is probably _the_ most interesting from
> a lock checking standpoint, could you check doing the page fault case?

Sure, it's a pretty interaction.  To be sure about the rule: any *_user
call can be treated as an implicit invocation of do_page_fault?  

Dawson

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Linus Torvalds]

On Sat, 9 Jun 2001, Dawson Engler wrote:
> > 
> > Good point. Spinlocks (with the exception of read-read locks, of course)
> > and semaphores will deadlock on recursive use, while the BKL has this
> > "process usage counter" recursion protection.
> 
> Actually, it did show up all over the place --- I'd just selected two
> candidates to examine out of hundreds.  (Checking call chains is
> strenous, even when you know what you're looking for.)

Sure.

> > Dawson - the user-mode access part is probably _the_ most interesting from
> > a lock checking standpoint, could you check doing the page fault case?
> 
> Sure, it's a pretty interaction.  To be sure about the rule: any *_user
> call can be treated as an implicit invocation of do_page_fault?  

As a first approximation, yes. The exception cases are certain callers
that use kernel addresses and set_fs(KERNEL_DS) in order to "fake"
arguments to system calls etc, but I doubt they should need any
special-casing.

		Linus

Re: [CHECKER] a couple potential deadlocks in 2.4.5-ac8

[Dawson Engler]

> > Sure, it's a pretty interaction.  To be sure about the rule: any *_user
> > call can be treated as an implicit invocation of do_page_fault?  
> 
> As a first approximation, yes. The exception cases are certain callers
> that use kernel addresses and set_fs(KERNEL_DS) in order to "fake"
> arguments to system calls etc, but I doubt they should need any
> special-casing.

I already have to special case the set_fs calls for the user-pointer
security checker.  It shouldn't be too much trouble to reuse the code.
Thanks for the early warning.

Dawson