[BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Hi all, 

We are a group of researchers at Stanford working on program analysis
algorithms.  We have been building a precision enhanced program analysis
engine at Stanford, and our first application was to derive mutex/lock
behavior in the linux kernel. In the process, we found 99 likely
synchronization errors in linux kernel version 2.6.5:

    http://glide.stanford.edu/linux-lock/err1.html (69 errors)
    http://glide.stanford.edu/linux-lock/err2.html (30 errors)

err1.html consists of potential double locks/unlocks. Acquiring a lock
twice in a row may result in a system hang, and releasing a lock more than
once with certain mutex functions (e.g. up) may cause critical section
violations.

err2.html consists of reports on inconsistent output lock states on
function exit. These errors usually correspond to missed lock operations
on error paths. (filenames in this report correspond to where a function
is declared, so CTAGS may come in handy to find the actual implementation
of the function).

In the error reports, functions are hyperlinked to their derived
summaries, and those of their callees (since the analysis spans function
calls, the error condition of a particular function usually depend on the
locking behavior of its callees).

For example, in function "radeon_pm_program_v2clk" (first error report in
err1.html), the tool flagged an error at line 323 of
"drivers/video/aty/radeon_pm.c". Line 323 invokes two macros, OUTPLL, and
INPLL. OUTPLL acquires "rinfo->reg_lock", and then evaluates "addr", which
is calculated, in this case, by calling _INPLL. By clicking on the link
"drivers/video/aty/radeon_pm.c:radeon_pm_program_v2clk", we can see that
_INPLL requires "rinfo->reg_lock" be unheld on entry (confirmed by looking
at its definition), which is not satisfied in this example. So this is a
double lock error and could potentially lead to a deadlock on MP systems.

We also have a separate web interface to the summary database at:

	http://glide.stanford.edu/linux-lock/

For example, typing "fh_put" in the input box gives

=========
 SUMMARY 
=========
FUNCTION SUMMARY: 'include/linux/nfsd/nfsfh.h:fh_put'
{
  dcache_lock(global): [unlocked -> unlocked]
  fhp(param#0)->fh_dentry->d_lock: [unlocked -> unlocked]
  fhp(param#0)->fh_dentry->d_inode->i_sem: [locked -> unlocked]
}

Each line in the function summary correspond to the requirements and
effects on one particular lock. For example, fh_put requires that the
global lock variable dcache_lock be unheld on entry, and it'll remain
unheld on exit. It also requires fhp->fh_dentry->d_inode->i_sem be held on
entry and it'll release it on exit. (note: please ignore summaries for
lock premitives like spin_lock or down_interruptible; models for these
functions are built into the checker and the derived summaries are not
used).

We have found that some modules in the kernel has functions with
complicated synchronization behavior (esp. in filesystems), and we hope
summaries generated by this tool could be useful not only for bug finding,
but also for documentation purposes as well.

The analysis is intraprocedurally "path sensitive", so it won't be fooled
by cases like

     if (flag & BLOCKING) spin_lock(&l);
     ...
     if (flag & BLOCKING) spin_unlock(&l);

or

     if (!spin_trylock(&l))
	return -EAGAIN;
     ...
     spin_unlock(&l);

The analysis algorithm models values (down to individual bits) and
pointers in the program with a boolean satisfiability solver with high
precision, and we're actively looking for other properties involving
(heavy) data dependencies where naive analysis would fail. Suggestions and
insights from the linux kernel community will be more than welcome!

As always, feedbacks and confirmations will be greatly appreciated!

Best regards,
Yichen Xie
<yxie@cs.stanford.edu>

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Nathan Scott]

On Thu, Jul 01, 2004 at 06:01:00PM -0700, Yichen Xie wrote:
> Hi all, 

Hi there,

> We are a group of researchers at Stanford working on program analysis
> algorithms.  We have been building a precision enhanced program analysis
> engine at Stanford, and our first application was to derive mutex/lock
> behavior in the linux kernel. In the process, we found 99 likely
> synchronization errors in linux kernel version 2.6.5:
> 
>     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
>     http://glide.stanford.edu/linux-lock/err2.html (30 errors)
> 
>  ...
> 
> As always, feedbacks and confirmations will be greatly appreciated!

>From looking through the XFS reports, I suspect your tools aren't
following the sv_wait semantics correctly (or else I'm misreading
the code).  Many of the reported XFS items stem from this - e.g.
this one...
[NOTE] BUG forgot to unlock before "goto try_again" (line 2293)
ERROR: fs/xfs/xfs_log.c:2948: lock check failed!
ERROR: fs/xfs/xfs_log.c:xlog_state_sync

the code in question does this:

  try_again:
	s = LOG_LOCK(log); /* spin_lock(&log->l_icloglock); */
	    ...
		sv_wait(&iclog->ic_prev->ic_writesema, PSWP,
			&log->l_icloglock, s);
		already_slept = 1;
		goto try_again;

and the tools seem to be missing that the log->l_icloglock is
unlocked by the sv_wait routine.  Well, that or I've overlooked
something that the tools have not. :)

A couple of the others were definately missed unlocks on error
paths though (fixed now) - thanks!

cheers.

-- 
Nathan

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
>     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
>      http://glide.stanford.edu/linux-lock/err2.html (30 errors)

ugh.  Most of these look real.

AFAICT fs/sysv/itree.c:find_shared is innocent.

fs/nfsd/nfsproc.c:nfsd_proc_link is a bit obscure.  There's a bug in a
callee of nfsd_proc_link(): nfsd_link() can forget to do an fh_unlock() on
an error path (the goto out_nfserr).  Is that what the tool is referring
to?

Anyway, I've enumerated these 109 bugs and placed a couple of text files at

   ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/stanford-locking-bugs/

so we can keep track of which of these possible bugs has been fixed or
otherwise disposed of.

If people could track the bugs by those identifiers, that would help.  I
fixed err1-10 and err1-25.

If someone wants to volunteer to maintain this list, that would be nice.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Hi Nathan, thanks for the feedback! This is indeed a false alarm. The tool
was able to infer the semantics of _sv_wait, but failed to used it due to
a bug in my checker... Problem fixed now and I will rerun the checker
tonight. I will update the error reports when the results are ready. 
Best,
Yichen

On Fri, 2 Jul 2004, Nathan Scott wrote:

> On Thu, Jul 01, 2004 at 06:01:00PM -0700, Yichen Xie wrote:
> > Hi all, 
> 
> Hi there,
> 
> > We are a group of researchers at Stanford working on program analysis
> > algorithms.  We have been building a precision enhanced program analysis
> > engine at Stanford, and our first application was to derive mutex/lock
> > behavior in the linux kernel. In the process, we found 99 likely
> > synchronization errors in linux kernel version 2.6.5:
> > 
> >     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
> >     http://glide.stanford.edu/linux-lock/err2.html (30 errors)
> > 
> >  ...
> > 
> > As always, feedbacks and confirmations will be greatly appreciated!
> 
> >From looking through the XFS reports, I suspect your tools aren't
> following the sv_wait semantics correctly (or else I'm misreading
> the code).  Many of the reported XFS items stem from this - e.g.
> this one...
> [NOTE] BUG forgot to unlock before "goto try_again" (line 2293)
> ERROR: fs/xfs/xfs_log.c:2948: lock check failed!
> ERROR: fs/xfs/xfs_log.c:xlog_state_sync
> 
> the code in question does this:
> 
>   try_again:
> 	s = LOG_LOCK(log); /* spin_lock(&log->l_icloglock); */
> 	    ...
> 		sv_wait(&iclog->ic_prev->ic_writesema, PSWP,
> 			&log->l_icloglock, s);
> 		already_slept = 1;
> 		goto try_again;
> 
> and the tools seem to be missing that the log->l_icloglock is
> unlocked by the sv_wait routine.  Well, that or I've overlooked
> something that the tools have not. :)
> 
> A couple of the others were definately missed unlocks on error
> paths though (fixed now) - thanks!
> 
> cheers.
> 
> 

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

> AFAICT fs/sysv/itree.c:find_shared is innocent.

I guess here's what has triggered the warning by the tool:

get_branch may try to acquire pointers_lock (itree.c:103) on one of its
paths, which was held (line 287) by find_shared...

> fs/nfsd/nfsproc.c:nfsd_proc_link is a bit obscure.  There's a bug in a
> callee of nfsd_proc_link(): nfsd_link() can forget to do an fh_unlock() on
> an error path (the goto out_nfserr).  Is that what the tool is referring
> to?

fh_put calls fh_unlock(fhp), which "up"s fhp->fh_dentry->d_inode->i_sem. 
two calls in a row "up"s that semaphore twice, which upset the tool and 
triggered the warning.

yichen

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
>  > AFAICT fs/sysv/itree.c:find_shared is innocent.
> 
>  I guess here's what has triggered the warning by the tool:
> 
>  get_branch may try to acquire pointers_lock (itree.c:103) on one of its
>  paths, which was held (line 287) by find_shared...

OK, that's certainly very broken.   I'll fix that one up.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Martin Diehl]

On Thu, 1 Jul 2004, Andrew Morton wrote:

>    ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/stanford-locking-bugs/
> 
> so we can keep track of which of these possible bugs has been fixed or
> otherwise disposed of.

---
err2-4
[NOTE] BUG (line 182)
ERROR: AMBIGUOUS OUTSTATE:
drivers/net/irda/sir-dev.h:sirdev_write_complete
<http://glide.stanford.edu/cgi-bin/linux-lock/findsum.pl?
function=drivers/net/irda/sir-dev.h:sirdev_write_complete>:
*param_0(dev).tx_lock
---

Was real bug. Already fixed in 2.6.7.

Thanks,
Martin

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
> I will update the error reports when the results are ready. 

Do you plan to run this tool and generate reports against the 2.6 kernel on
a regular basis?

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
>     http://glide.stanford.edu/linux-lock/err1.html (69 errors)

ipc/sem.c:find_undo() seems to be a false positive.  That function calls
sem_revalidate() which may or may not require a sem_unlock() afterwards,
depending on what value it returned.

I'm not sure it's worth teaching the tool about this - I'd refer to
strangle the IPC code.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
>     http://glide.stanford.edu/linux-lock/err1.html (69 errors)

nfsd4_open_confirm() looks to be a false positive - judging by the comment:

/*
 * nfs4_unlock_state(); called in encode
 */

the caller of this function is supposed to do nfs4_unlock_state() later on.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[YOSHIFUJI Hideaki / 吉藤英明]

Hello.

In article <Pine.LNX.4.44.0407011747040.4015-100000@kaki.stanford.edu> (at Thu, 1 Jul 2004 18:01:00 -0700 (PDT)), Yichen Xie <yxie@cs.stanford.edu> says:

>     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
:
> err1.html consists of potential double locks/unlocks. Acquiring a lock
> twice in a row may result in a system hang, and releasing a lock more than
> once with certain mutex functions (e.g. up) may cause critical section
> violations.

Well,
lapb_iface.c:lapb_unregister() has typo and we failed to get lapb_list_lock.
rose_route.c:rose_remove_node()'s caller has rose_node_list_lock; so, this is 
dead lock.

Here's the fix.

===== net/lapb/lapb_iface.c 1.14 vs edited =====
--- 1.14/net/lapb/lapb_iface.c	2004-01-11 08:39:04 +09:00
+++ edited/net/lapb/lapb_iface.c	2004-07-02 17:23:27 +09:00
@@ -176,7 +176,7 @@
 	struct lapb_cb *lapb;
 	int rc = LAPB_BADTOKEN;
 
-	write_unlock_bh(&lapb_list_lock);
+	write_lock_bh(&lapb_list_lock);
 	lapb = __lapb_devtostruct(dev);
 	if (!lapb)
 		goto out;
===== net/rose/rose_route.c 1.12 vs edited =====
--- 1.12/net/rose/rose_route.c	2004-06-04 09:11:24 +09:00
+++ edited/net/rose/rose_route.c	2004-07-02 17:26:08 +09:00
@@ -206,7 +206,6 @@
 {
 	struct rose_node *s;
 
-	spin_lock_bh(&rose_node_list_lock);
 	if ((s = rose_node_list) == rose_node) {
 		rose_node_list = rose_node->next;
 		kfree(rose_node);

Thanks.

-- 
Hideaki YOSHIFUJI @ USAGI Project <yoshfuji@linux-ipv6.org>
GPG FP: 9022 65EB 1ECF 3AD1 0BDF  80D8 4807 F894 E062 0EEA

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Matthias Urlichs]

Hi, Andrew Morton wrote:

> If someone wants to volunteer to maintain this list, that would be nice.

I can do that.

-- 
Matthias Urlichs

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

indeed, the code looks different in 2.6.7. definitely not a double unlock
any more, but it seems the new version exit w/ client_sema unheld at line
1616, and w/ the lock held at line 1625. is there a correlation between
the return value with the lock state? -yichen

On Fri, 2 Jul 2004, Andrew Morton wrote:

> Yichen Xie <yxie@cs.stanford.edu> wrote:
> >
> >     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
> 
> nfsd4_open_confirm() looks to be a false positive - judging by the comment:
> 
> /*
>  * nfs4_unlock_state(); called in encode
>  */
> 
> the caller of this function is supposed to do nfs4_unlock_state() later on.
> 

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

I'd be happy to! -yichen

On Fri, 2 Jul 2004, Andrew Morton wrote:

> Yichen Xie <yxie@cs.stanford.edu> wrote:
> >
> > I will update the error reports when the results are ready. 
> 
> Do you plan to run this tool and generate reports against the 2.6 kernel
> on a regular basis?
> 

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Indeed, it missed the locking semantics of sem_revalidate. I'll look into
designing a spec language to teach the tool about simple cases like this..
-yichen

On Fri, 2 Jul 2004, Andrew Morton wrote:

> Yichen Xie <yxie@cs.stanford.edu> wrote:
> >
> >     http://glide.stanford.edu/linux-lock/err1.html (69 errors)
> 
> ipc/sem.c:find_undo() seems to be a false positive.  That function calls
> sem_revalidate() which may or may not require a sem_unlock() afterwards,
> depending on what value it returned.
> 
> I'm not sure it's worth teaching the tool about this - I'd refer to
> strangle the IPC code.
> 

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[J. Bruce Fields]

On Fri, Jul 02, 2004 at 09:39:40AM -0700, Yichen Xie wrote:
> indeed, the code looks different in 2.6.7. definitely not a double unlock
> any more, but it seems the new version exit w/ client_sema unheld at line
> 1616, and w/ the lock held at line 1625. is there a correlation between
> the return value with the lock state? -yichen

Yes.  The unlock happens at either nfs4xdr.c:1280 (ENCODE_SEQID_OP_TAIL)
or nfs4xdr.c:2534 (nfsd4_encode_replay()), and in the former case the
unlock is conditional on the value of the oc_stateowner field that's set
before the nfs4_lock_state() in nfsd4_open_confirm().

So while I believe the code as it stands is correct, it's not just your
checker that's going to find this confusing!  I'll work on a fix....--b.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
> I will update the error reports when the results are ready. 

err1.html updated. -yichen

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Yichen Xie <yxie@cs.stanford.edu> wrote:
>
> I will update the error reports when the results are ready. 

err2.html now updated. -yichen

 

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Andrew Morton]

Matthias Urlichs <smurf@smurf.noris.de> wrote:
>
> Hi, Andrew Morton wrote:
> 
> > If someone wants to volunteer to maintain this list, that would be nice.
> 
> I can do that.
> 

Thanks.  But if Yichen is able to perform regular (say, weekly) runs of the
tool against the latest kernel tree there shouldn't be a need for this.  I
expect the list will shrink fairly quickly at least initially.

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[J. Bruce Fields]

On Fri, Jul 02, 2004 at 02:12:39PM -0700, Yichen Xie wrote:
> Yichen Xie <yxie@cs.stanford.edu> wrote:
> >
> > I will update the error reports when the results are ready. 
> 
> err2.html now updated. -yichen

Are you planning to run it on a more recent kernel too?  Some of the
nfsd reports clearly good finds (thanks, I'll make patches), but a lot
of them are in bits of the code that have changed recently (from a quick
check, I think that at least err1-32, err1-33, err1-42, from Andrew
Morton's list, have been fixed).

--Bruce Fields

Re: [BUGS] [CHECKER] 99 synchronization bugs and a lock summary database

[Yichen Xie]

Hi Bruce, thanks for the feedback! I kept pounding on 2.6.5 (then current
branch when I got started) to be able to tune the tool on one single code
base. Once it gets stabalized I hope to be able to automate the run
process and run it on a regular basis on the latest trees. -yichen

On Fri, 2 Jul 2004, J. Bruce Fields wrote:

> On Fri, Jul 02, 2004 at 02:12:39PM -0700, Yichen Xie wrote:
> > Yichen Xie <yxie@cs.stanford.edu> wrote:
> > >
> > > I will update the error reports when the results are ready. 
> > 
> > err2.html now updated. -yichen
> 
> Are you planning to run it on a more recent kernel too?  Some of the
> nfsd reports clearly good finds (thanks, I'll make patches), but a lot
> of them are in bits of the code that have changed recently (from a quick
> check, I think that at least err1-32, err1-33, err1-42, from Andrew
> Morton's list, have been fixed).
> 
> --Bruce Fields
>