How to explain to lock validator: locking inodes in inode order

How to explain to lock validator: locking inodes in inode order

[Joshua Hudson]

Code does this:

/* Lock two items. See locking.txt */
static inline void kb0_lock2m(struct kb0_idata *m1, struct kb0_idata *m2)
{
        if (m1->vi.i_ino > m2->vi.i_ino)
                mutex_lock(&m2->k_mutex);
        mutex_lock(&m1->k_mutex);
        if (m1->vi.i_ino < m2->vi.i_ino)
                mutex_lock(&m2->k_mutex);
}

Not sure how to explain to the lock validator that this code can never deadlock.

Note struct kb0_idata has an element of struct inode called vi.

Re: How to explain to lock validator: locking inodes in inode order

[Arjan van de Ven]

On Mon, 2006-07-17 at 19:24 -0700, Joshua Hudson wrote:
> Code does this:
> 
> /* Lock two items. See locking.txt */
> static inline void kb0_lock2m(struct kb0_idata *m1, struct kb0_idata *m2)
> {
>         if (m1->vi.i_ino > m2->vi.i_ino)
>                 mutex_lock(&m2->k_mutex);
>         mutex_lock(&m1->k_mutex);
>         if (m1->vi.i_ino < m2->vi.i_ino)
>                 mutex_lock(&m2->k_mutex);
> }
> 
> Not sure how to explain to the lock validator that this code can never deadlock.

you're sure it can;t? (which fs is this btw?)

all places in the kernel that take this mutex in that order only do it
in i_ino order, including all directory operations like cross directory
rename?

(if so you can explain normal parent/child nesting, but only if so)

Re: How to explain to lock validator: locking inodes in inode order

[Joshua Hudson]

On 7/17/06, Arjan van de Ven <arjan@infradead.org> wrote:
> On Mon, 2006-07-17 at 19:24 -0700, Joshua Hudson wrote:
> > Code does this:
> >
> > /* Lock two items. See locking.txt */
> > static inline void kb0_lock2m(struct kb0_idata *m1, struct kb0_idata *m2)
> > {
> >         if (m1->vi.i_ino > m2->vi.i_ino)
> >                 mutex_lock(&m2->k_mutex);
> >         mutex_lock(&m1->k_mutex);
> >         if (m1->vi.i_ino < m2->vi.i_ino)
> >                 mutex_lock(&m2->k_mutex);
> > }
> >
> > Not sure how to explain to the lock validator that this code can never deadlock.
>
> you're sure it can;t?
Yes. It never takes a lock on any higher inode without holding the lock on a
lower inode first. I have a full proof across the VFS+FS [see below].

>
> all places in the kernel that take this mutex in that order only do it
> in i_ino order, including all directory operations like cross directory
> rename?

I had to disable the kernel's locking of multiple objects in namei.c using a
new FS_ flag because it would actually deadlock for this filesystem.

> (which fs is this btw?)
Custom filesystem (kb0), not in any tree but mine. I am in progress
with syncing it up
to the latest kernel.

If anybody really wants it, it is 70-odd K of bzip2-compressed code of
filesystem + utilities. It's not ready for non-acedemic use though.

Re: How to explain to lock validator: locking inodes in inode order

[Arjan van de Ven]

Hi,

> Yes. It never takes a lock on any higher inode without holding the lock on a
> lower inode first. I have a full proof across the VFS+FS [see below].

ok just checking. The reason this is important is that once you tell
lockdep this is a special situation, it better be that, since you're
losing any checking for the "but what if not" case. 
> 
> >
> > all places in the kernel that take this mutex in that order only do it
> > in i_ino order, including all directory operations like cross directory
> > rename?
> 
> I had to disable the kernel's locking of multiple objects in namei.c using a
> new FS_ flag because it would actually deadlock for this filesystem.

ok fun ;) It might be interesting to talk to Al Viro about this at some
point, maybe there is something interesting in your locking that could
improve the linux VFS locking scheme

To annotate for lockdep,  you probably can use the same constants as we
used for inodes (after all you're sort of doing the same anyway); so
your code can be made to look roughly like this: 

if ( < ) {
   mutex_lock_nested( ..... , I_MUTEX_PARENT);
   mutex_lock_nested( ..... , I_MUTEX_CHILD);
} else {
   mutex_lock_nested( ..... , I_MUTEX_PARENT);
   mutex_lock_nested( ..... , I_MUTEX_CHILD);
}

this means that you tell that the first mutex taken is the parent in a
parent-child relationship which is hierarchical for "external" reasons
(in this case your sorting).

Greetings,
    Arjan van de Ven