kernel analyser to detect sleep under spinlock

kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

 ftp://ųboe.it.uc3m.es/pub/Programs/c-1.2.tgz

To use the application, compile and then use "c" in place of
"gcc" on a typical kernel compile line.

This is currently tested only on kernel 2.4 and probably will need some
slight mods to the parser for kernel 2.6 code, as it has to
inverse engineer some of the assembler produced by macros in kernel
headers.

Here's some typical output ...
 
 % ./c -D__KERNEL__ -DMODULE \
   -I/usr/local/src/linux-2.4.25-xfs/include ../dbr/1/sbull.c 
 *************** sleepy functions *******************************
 *       function                line    calls
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/smb_fs_sb.h
 *       smb_lock_server         63      down
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/fs.h
 *       lock_parent             1624    down
 *       double_down             1647    down
 *       triple_down             1668    down
 *       double_lock             1718    double_down
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/locks.h
 *       lock_super              38      down
 *
 * - ../dbr/1/sbull.c
 *       sbull_ioctl             171     interruptible_sleep_on
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/blk.h
 *       sbull_request           358     interruptible_sleep_on
 *
 * - ../dbr/1/sbull.c
 *       sbull_init              431     kmalloc
 *       sbull_init              431     kfree
 *       sbull_cleanup           542     kfree
 *
 ****************************************************************
 *************** sleep_under_spinlock ****************************
 *       function                line    calls
 *
 * - ../dbr/1/sbull.c
 *       sbull_request           420     interruptible_sleep_on
 *
 *
 * *** found 1 instances of sleep under spinlock ***
 *
 ***********************************************

It's GPL/LGPL.

Peter (ptb@inv.it.uc3m.es)

kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

(corrected url)

 ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.tgz

To use the application, compile and then use "c" in place of
"gcc" on a typical kernel compile line.

This is currently tested only on kernel 2.4 and probably will need some
slight mods to the parser for kernel 2.6 code, as it has to
inverse engineer some of the assembler produced by macros in kernel
headers.

Here's some typical output ...

 % ./c -D__KERNEL__ -DMODULE \
   -I/usr/local/src/linux-2.4.25-xfs/include ../dbr/1/sbull.c
 *************** sleepy functions *******************************
 *       function                line    calls
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/smb_fs_sb.h
 *       smb_lock_server         63      down
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/fs.h
 *       lock_parent             1624    down
 *       double_down             1647    down
 *       triple_down             1668    down
 *       double_lock             1718    double_down
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/locks.h
 *       lock_super              38      down
 *
 * - ../dbr/1/sbull.c
 *       sbull_ioctl             171     interruptible_sleep_on
 *
 * - /usr/local/src/linux-2.4.25-xfs/include/linux/blk.h
 *       sbull_request           358     interruptible_sleep_on
 *
 * - ../dbr/1/sbull.c
 *       sbull_init              431     kmalloc
 *       sbull_init              431     kfree
 *       sbull_cleanup           542     kfree
 *
 ****************************************************************
 *************** sleep_under_spinlock ****************************
 *       function                line    calls
 *
 * - ../dbr/1/sbull.c
 *       sbull_request           420     interruptible_sleep_on
 *
 *
 * *** found 1 instances of sleep under spinlock ***
 *
 ***********************************************

It's GPL/LGPL.

Peter (ptb@inv.it.uc3m.es)

Re: kernel analyser to detect sleep under spinlock

[Randy.Dunlap]

Peter T. Breuer wrote:
>  ftp://ųboe.it.uc3m.es/pub/Programs/c-1.2.tgz

That URL fails for me... is it correct?

> To use the application, compile and then use "c" in place of
> "gcc" on a typical kernel compile line.
> 
> This is currently tested only on kernel 2.4 and probably will need some
> slight mods to the parser for kernel 2.6 code, as it has to
> inverse engineer some of the assembler produced by macros in kernel
> headers.
> 
> Here's some typical output ...


-- 
~Randy

Re: kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

In article <418EC948.2080506@osdl.org> you wrote:
> Peter T. Breuer wrote:
> >  ftp://??boe.it.uc3m.es/pub/Programs/c-1.2.tgz

> That URL fails for me... is it correct?

Well, it is, if you guess that's an "oboe". I don't know why the
original came out with a pair of question marks. Sorry.

  ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.tgz


Peter

Re: kernel analyser to detect sleep under spinlock

[Randy.Dunlap]

Peter T. Breuer wrote:
> In article <418EC948.2080506@osdl.org> you wrote:
> 
>>Peter T. Breuer wrote:
>>
>>> ftp://??boe.it.uc3m.es/pub/Programs/c-1.2.tgz
> 
> 
>>That URL fails for me... is it correct?
> 
> 
> Well, it is, if you guess that's an "oboe". I don't know why the
> original came out with a pair of question marks. Sorry.
> 
>   ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.tgz

Thanks, that works now.
The original was not ??, my mail client did that on reply.

The original was
   ftp://%c5%b3boe.it.uc3m.es/pub/Programs/c-1.2.tgz
whatever those are...


-- 
~Randy

Re: kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

"Peter T. Breuer" <ptb@inv.it.uc3m.es> wrote in message news:<2Y9DE-4Tb-7@gated-at.bofh.it>...

(scanning for abuses of spinlocks in the kernel source)

>  ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.tgz
> 
> To use the application, compile and then use "c" in place of
> "gcc" on a typical kernel compile line.

I've added some extra support for gcc 3.4.0 (which seems to use some
special builtin types such as __builtin_va_list that gcc 2.95.4 does
not generate) and put up the new archive at
    
  ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.1.tgz

Please tell me of any parse rejects with 2.4 kernel files. I'll be very
happy to make the usually trivial parser additions required to scan the
gnuish C involved! I simply have only tried a few dozen kernel source
files myself and so don't have a complete picture of every weird extension
usage out there in the source.

I'll also start going through 2.6 kernel files to see if anything more is
needed for those. 

To remind you what this utility detects:

> Here's some typical output ...
> 
>  % ./c -D__KERNEL__ -DMODULE \
>    -I/usr/local/src/linux-2.4.25-xfs/include ../dbr/1/sbull.c
>  *************** sleepy functions *******************************
>  *       function                line    calls
>  *
>  * - /usr/local/src/linux-2.4.25-xfs/include/linux/smb_fs_sb.h
>  *       smb_lock_server         63      down
>  *
>  * - /usr/local/src/linux-2.4.25-xfs/include/linux/fs.h
>  *       lock_parent             1624    down
>  *       double_down             1647    down
>  *       triple_down             1668    down
>  *       double_lock             1718    double_down
>  *
>  * - /usr/local/src/linux-2.4.25-xfs/include/linux/locks.h
>  *       lock_super              38      down
>  *
>  * - ../dbr/1/sbull.c
>  *       sbull_ioctl             171     interruptible_sleep_on
>  *
>  * - /usr/local/src/linux-2.4.25-xfs/include/linux/blk.h
>  *       sbull_request           358     interruptible_sleep_on
>  *
>  * - ../dbr/1/sbull.c
>  *       sbull_init              431     kmalloc
>  *       sbull_init              431     kfree
>  *       sbull_cleanup           542     kfree
>  *
>  ****************************************************************
>  *************** sleep_under_spinlock ****************************
>  *       function                line    calls
>  *
>  * - ../dbr/1/sbull.c
>  *       sbull_request           420     interruptible_sleep_on
>  *
>  *
>  * *** found 1 instances of sleep under spinlock ***
>  *
>  ***********************************************
> 
> It's GPL/LGPL.
 

Peter (ptb@inv.it.uc3m.es)

Re: kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

Peter T. Breuer <ptb (at) inv.it.uc3m.es> writes:
 
> I've added some extra support for gcc 3.4.0 [...]

And now kernel 2.6 files seem to be being parsed OK too.

% ./c -nostdinc -iwithprefix include -D__KERNEL__ -I/usr/local/src/linux-2.6.3/include -D__KERNEL__ -Wall -Wstrict-prototypes -Wno-trigraphs -I/usr/local/src/linux-2.6.3/include/asm-i386/mach-default -O2 -DMODULE -DKBUILD_BASENAME=nbd -DKBUILD_MODNAME=nbd /usr/local/src/linux-2.6.3/drivers/block/nbd.c
*************** sleep calls ************************************
*  function                     line    calls (locks)
*
* - /usr/local/src/linux-2.6.3/include/linux/fs.h
*  lock_super                   741     down (0)
*
* - /usr/local/src/linux-2.6.3/include/net/sock.h
*  sk_filter_release            710     kfree (0)
*
* - /usr/local/src/linux-2.6.3/drivers/block/nbd.c
*  nbd_send_req                 264     down (0)
*  do_nbd_request               510     nbd_send_req (-1)
*  nbd_ioctl                    569     nbd_send_req (-1)
*  nbd_ioctl                    574     down (0)
*
*
* *** found 0 instances of sleep under spinlock ***
*
***************************************************************




Archive at:

   ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.2.tgz


GPL, LGPL, etc.

This is also useful for locating functions which can sleep, though of
course that can be done in other ways.

This utility works by applying a programming logic to the code semantics.
That bit's fine. What it's not so great at is resolving C references back
to the correct declaration, which results in under-reporting. I'll improve
that (mumbles, register actions to be carried out whenever anything
changes in the fact database instead of coding the inferences by hand). 

I'll undertake a survey of the current kernel.

Peter (ptb (at) inv.it.uc3m.es)
 
 

Re: kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

Peter T. Breuer <ptb@inv.it.uc3m.es> wrote:
> I'll undertake a survey of the current kernel.

Just for kicks, I started with the DAC960.c driver (alphabet ..), and
it registered 6 alarms!

   Linux Driver for Mylex DAC960/AcceleRAID/eXtremeRAID PCI RAID Controllers

     Copyright 1998-2001 by Leonard N. Zubkoff <lnz@dandelion.com>

*  function                     line    calls (locks)
* - /usr/local/src/linux-2.6.3/drivers/block/DAC960.c
!! DAC960_BA_InterruptHandler   5219 DAC960_V2_ProcessCompletedCommand (1)
!! DAC960_LP_InterruptHandler   5262 DAC960_V2_ProcessCompletedCommand (1)
!! DAC960_V1_ExecuteUserCommand 5869    DAC960_WaitForCommand (1)
!! DAC960_V2_ExecuteUserCommand 6132    DAC960_WaitForCommand (1)
!! DAC960_gam_ioctl             6663    DAC960_WaitForCommand (1)
!! DAC960_gam_ioctl             6688    DAC960_WaitForCommand (1)

The ProcessCompletedCommand thing really is called under spinlock, but
it appears to be detected as sleepy because it calls kmalloc (and
kfree), however it calls kmalloc with GFP_ATOMIC, so it's not sleepy
and that's a false alarm. Ho hum ... I'll have to detect that.

The WaitForCommand is also definitely called under spinlock ... and is
thought to be sleepy because it calls schedule! Well, it calls
__wait_event(Controller->CommandWaitQueue, Controller->FreeCommands);
Is that going to schedule?  I suppose logically it should.

Anyway, that looks a legitimate complaint:

  spin_lock_irqsave(&Controller->queue_lock, flags);
  while ((Command = DAC960_AllocateCommand(Controller)) == NULL)
    DAC960_WaitForCommand(Controller);
  spin_unlock_irqrestore(&Controller->queue_lock, flags);

Looks like it waits under spinlock to me!

I'll go write the generic inference engine required to make this a bit
more accurate still.



Peter

Re: kernel analyser to detect sleep under spinlock

[Jens Axboe]

On Sat, Nov 13 2004, Peter T. Breuer wrote:
> Peter T. Breuer <ptb@inv.it.uc3m.es> wrote:
> > I'll undertake a survey of the current kernel.
> 
> Just for kicks, I started with the DAC960.c driver (alphabet ..), and
> it registered 6 alarms!
> 
>    Linux Driver for Mylex DAC960/AcceleRAID/eXtremeRAID PCI RAID Controllers
> 
>      Copyright 1998-2001 by Leonard N. Zubkoff <lnz@dandelion.com>
> 
> *  function                     line    calls (locks)
> * - /usr/local/src/linux-2.6.3/drivers/block/DAC960.c
> !! DAC960_BA_InterruptHandler   5219 DAC960_V2_ProcessCompletedCommand (1)
> !! DAC960_LP_InterruptHandler   5262 DAC960_V2_ProcessCompletedCommand (1)
> !! DAC960_V1_ExecuteUserCommand 5869    DAC960_WaitForCommand (1)
> !! DAC960_V2_ExecuteUserCommand 6132    DAC960_WaitForCommand (1)
> !! DAC960_gam_ioctl             6663    DAC960_WaitForCommand (1)
> !! DAC960_gam_ioctl             6688    DAC960_WaitForCommand (1)
> 
> The ProcessCompletedCommand thing really is called under spinlock, but
> it appears to be detected as sleepy because it calls kmalloc (and
> kfree), however it calls kmalloc with GFP_ATOMIC, so it's not sleepy
> and that's a false alarm. Ho hum ... I'll have to detect that.
> 
> The WaitForCommand is also definitely called under spinlock ... and is
> thought to be sleepy because it calls schedule! Well, it calls
> __wait_event(Controller->CommandWaitQueue, Controller->FreeCommands);
> Is that going to schedule?  I suppose logically it should.
> 
> Anyway, that looks a legitimate complaint:
> 
>   spin_lock_irqsave(&Controller->queue_lock, flags);
>   while ((Command = DAC960_AllocateCommand(Controller)) == NULL)
>     DAC960_WaitForCommand(Controller);
>   spin_unlock_irqrestore(&Controller->queue_lock, flags);
> 
> Looks like it waits under spinlock to me!

static void DAC960_WaitForCommand(DAC960_Controller_T *Controller)
{
  spin_unlock_irq(&Controller->queue_lock);
  __wait_event(Controller->CommandWaitQueue, Controller->FreeCommands);
  spin_lock_irq(&Controller->queue_lock);
}

Looks alright to me, I don't understand your confusion. One thing you
could say is that either the path to DAC960_WaitForCommand should not
save interrupt flags, _or_ it's a bug to use spin_unlock_irq() if
interrutps could already be disabled at that point.

-- 
Jens Axboe

Re: kernel analyser to detect sleep under spinlock

[Peter T. Breuer]

Another minor functional update to the kernel source code analysis tool,
though actually I reorganised it thoroughly internally in order to run
off externally defined trigger-action rules instead of a mess of gunky C
code.

   ftp://oboe.it.uc3m.es/pub/Programs/c-1.2.3.tgz

This tool locates "sleep under spinlock" abuses in the kernel.

The latest revision eliminates some false positives, by taking notice of
the second argument to kmalloc where it can.

% ./c -nostdinc -iwithprefix include -D__KERNEL__
 -I/usr/local/src/linux-2.6.3/include -D__KERNEL__ -Wall
 -Wstrict-prototypes -Wno-trigraphs
 -I/usr/local/src/linux-2.6.8.1-uml/include/asm-i386/mach-default -O2
 -DMODULE /usr/local/src/linux-2.6.8.1-uml/drivers/block/nbd.c
 /usr/local/src/linux-2.6.8.1-uml/drivers/block/nbd.c
/************** sleep calls ************************************
 *  function                     line    calls (locks)
 *
 * - /usr/local/src/linux-2.6.3/include/linux/slab.h
 *  kmalloc                      98      __kmalloc (0)
 *
 * - /usr/local/src/linux-2.6.3/include/linux/fs.h
 *  lock_super                   741     down (0)
 *
 * - /usr/local/src/linux-2.6.8.1-uml/drivers/block/nbd.c
 *  nbd_send_req                 245     down (0)
 *  nbd_ioctl                    548     down (0)
 *
 *
 * *** found 0 instances of sleep under spinlock ***
 *
 **************************************************************/



GPL, LGPL, etc.

This is also useful for locating functions which can sleep, though of
course that can be done in other ways.


Peter (ptb (at) inv.it.uc3m.es)