Lockdep question regarding two-level locks

Lockdep question regarding two-level locks

[Michel Lespinasse]

Hi,

I am wondering about how to describe the following situation to lockdep:

- lock A would be something that's already implemented (a mutex or
possibly a spinlock).
- lock B is a range lock, which I would be writing the code for
(including lockdep hooks). I do not expect lockdep to know about range
locking, but I want it to treat lock B like any other and detect lock
ordering issues related to it.
- lock A protects a number of structures, including lock B's list of
locked ranges, but other structures as well.
- lock A is intended to be held for only short periods of time, lock
B's ranges might be held for longer.

Usage would be along the following lines:

acquire:
A_lock();
// might access data protected by A here
bool blocked = B_lock(range); // must be called under lock A; will
release lock A if blocking on B.
// might access data protected by A here (especially to re-validate in
case A was released while blocking on B...)
A_unlock()

release:
A_lock()
// might access data protected by A here
A_B_unlock(range); // must be called under lock A; releases locks A and B.

There might also be other places that need to lock A for a short time,
either inside and outside of lock B.

The correct lock ordering here is that lock A can be acquired while
holding lock B. However, the acquire sequence here seems to violate
that, as A must be locked before B there. In reality, the usage
pattern does not create circular dependencies, because lock A would be
released if blocking on lock B. However, I am not sure how to convey
that usage pattern to lockdep.


A few options I am considering:

- Is there a way to indicate to lockdep, in B's locking function
definition, that I am acquiring B after A but really want the lock
order to be registered as A after B, since I know how to avoid the
circular dependency issue by releasing A if blocking on B ?

- B's locking function definition could tell lockdep that B was
acquired with a trylock. This avoids lockdep reporting a lock ordering
issue between A and B, but also will make lockdep ignore lock ordering
issues between any other lock and B. So this is not a proper solution,
as we may just as well not implement lockdep support in lock B in that
case.

- B's implementation could, when lockdep is enabled, always release
lock A before acquiring lock B. This is not ideal though, since this
would hinder testing of the not-blocked code path in the acquire
sequence.

Would the lockdep maintainers have any guidance as to how to handle
this locking case ?

Thanks,

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: Lockdep question regarding two-level locks

[peterz]

On Sat, Aug 22, 2020 at 09:04:09AM -0700, Michel Lespinasse wrote:
> Hi,
> 
> I am wondering about how to describe the following situation to lockdep:
> 
> - lock A would be something that's already implemented (a mutex or
> possibly a spinlock).
> - lock B is a range lock, which I would be writing the code for
> (including lockdep hooks). I do not expect lockdep to know about range
> locking, but I want it to treat lock B like any other and detect lock
> ordering issues related to it.
> - lock A protects a number of structures, including lock B's list of
> locked ranges, but other structures as well.
> - lock A is intended to be held for only short periods of time, lock
> B's ranges might be held for longer.

That's the 'normal' state for blocking locks, no?

See how both struct mutex and struct rw_semaphore have internal locks.

> Usage would be along the following lines:
> 
> acquire:
> A_lock();
> // might access data protected by A here
> bool blocked = B_lock(range); // must be called under lock A; will
> release lock A if blocking on B.
> // might access data protected by A here (especially to re-validate in
> case A was released while blocking on B...)
> A_unlock()
> 
> release:
> A_lock()
> // might access data protected by A here
> A_B_unlock(range); // must be called under lock A; releases locks A and B.

up_{read,write}() / mutex_unlock() release 'B', the actual lock, early,
and then take 'A', the internal lock, to actually implement the release.

That way lockdep doesn't see the B-A order :-)

> There might also be other places that need to lock A for a short time,
> either inside and outside of lock B.

Any cases that aren't covered by the current implementation of rwsems ?

Re: Lockdep question regarding two-level locks

[Michel Lespinasse]

On Sat, Aug 22, 2020 at 9:39 AM <peterz@infradead.org> wrote:
> On Sat, Aug 22, 2020 at 09:04:09AM -0700, Michel Lespinasse wrote:
> > Hi,
> >
> > I am wondering about how to describe the following situation to lockdep:
> >
> > - lock A would be something that's already implemented (a mutex or
> > possibly a spinlock).
> > - lock B is a range lock, which I would be writing the code for
> > (including lockdep hooks). I do not expect lockdep to know about range
> > locking, but I want it to treat lock B like any other and detect lock
> > ordering issues related to it.
> > - lock A protects a number of structures, including lock B's list of
> > locked ranges, but other structures as well.
> > - lock A is intended to be held for only short periods of time, lock
> > B's ranges might be held for longer.
>
> That's the 'normal' state for blocking locks, no?
>
> See how both struct mutex and struct rw_semaphore have internal locks.

Right (note that I already have an implementation of my range lock
('B') along these lines, with a low-level lock ('A') tucked into it
and all the expected lockdep support).

> > Usage would be along the following lines:
> >
> > acquire:
> > A_lock();
> > // might access data protected by A here
> > bool blocked = B_lock(range); // must be called under lock A; will
> > release lock A if blocking on B.
> > // might access data protected by A here (especially to re-validate in
> > case A was released while blocking on B...)
> > A_unlock()
> >
> > release:
> > A_lock()
> > // might access data protected by A here
> > A_B_unlock(range); // must be called under lock A; releases locks A and B.
>
> up_{read,write}() / mutex_unlock() release 'B', the actual lock, early,
> and then take 'A', the internal lock, to actually implement the release.
>
> That way lockdep doesn't see the B-A order :-)
>
> > There might also be other places that need to lock A for a short time,
> > either inside and outside of lock B.
>
> Any cases that aren't covered by the current implementation of rwsems ?

My issue is that I have other data, unrelated to B, which frequently
needs to be accessed or updated at just the same points where we are
acquiring or releasing B.

(to go into use cases: that data would be the vma rbtree and per-MM
statistics; one may want to find a free gap between vmas before range
locking it, or take vmas in and out of the rbtree as we acquire or
release a lock on the corresponding address range, etc...)

As the accesses to that data tend to naturally align with the places
where we take or release the B lock, it is tempting to expose A to the
caller so that A can protect additional data not directly related to
B. It seems like changing B's internal lock into a public one which
the caller would take and release explicitly around B calls would be
straighforward, but it causes issues as lockdep doesn't understand
that construct...

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: Lockdep question regarding two-level locks

[Michel Lespinasse]

On Sat, Aug 22, 2020 at 9:04 AM Michel Lespinasse <walken@google.com> wrote:
> - B's implementation could, when lockdep is enabled, always release
> lock A before acquiring lock B. This is not ideal though, since this
> would hinder testing of the not-blocked code path in the acquire
> sequence.

Actually, this may be an acceptable way to handle my issue. In the
non-blocking case, B's implementation does not have to actually
release A, but it could tell lockdep that it's released A, acquired B
and acquired A again. Kinda ugly but should work...

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.