a couple potential deadlocks in 2.4.5-ac8

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

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

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!

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.

In article <[email protected]>,

Looks good.

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.

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

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

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

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

In message <[email protected]> you write:

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

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

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?

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

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

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

In article <[email protected]>,

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.

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

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

Sure.

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

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