Re: [PATCH] lockdep: Speed up lockdep_unregister_key() with expedited RCU synchronization

Boqun Feng
2025-03-26T05:25:33Z

On Tue, Mar 25, 2025 at 07:20:44PM -0400, Waiman Long wrote:
> On 3/25/25 3:42 PM, Boqun Feng wrote:
> > On Tue, Mar 25, 2025 at 03:23:30PM -0400, Waiman Long wrote:
> > [...]
> > > > > > That commit seemed fixing a race between disabling lockdep and
> > > > > > unregistering key, and most importantly, call zap_class() for the
> > > > > > unregistered key even if lockdep is disabled (debug_locks = 0). It might
> > > > > > be related, but I'm not sure that's the reason of putting
> > > > > > synchronize_rcu() there. Say you want to synchronize between
> > > > > > /proc/lockdep and lockdep_unregister_key(), and you have
> > > > > > synchronize_rcu() in lockdep_unregister_key(), what's the RCU read-side
> > > > > > critical section at /proc/lockdep?
> > > > > I agree that the commit that I mentioned is not relevant to the current
> > > > > case. You are right that is_dynamic_key() is the only function that is
> > > > > problematic, the other two are protected by the lockdep_lock. So they are
> > > > > safe. Anyway, I believe that the actual race happens in the iteration of the
> > > > > hashed list in is_dynamic_key(). The key that you save in the
> > > > > lockdep_key_hazptr in your proposed patch should never be the key (dead_key)
> > > > The key stored in lockdep_key_hazptr is the one that the rest of the
> > > > function will use after is_dynamic_key() return true. That is,
> > > >
> > > > CPU 0 CPU 1
> > > > ===== =====
> > > > WRITE_ONCE(*lockdep_key_hazptr, key);
> > > > smp_mb();
> > > >
> > > > is_dynamic_key():
> > > > hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
> > > > if (k == key) {
> > > > found = true;
> > > > break;
> > > > }
> > > > }
> > > > lockdep_unregister_key():
> > > > hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
> > > > if (k == key) {
> > > > hlist_del_rcu(&k->hash_entry);
> > > > found = true;
> > > > break;
> > > > }
> > > > }
> > > >
> > > > smp_mb();
> > > >
> > > > synchronize_lockdep_key_hazptr():
> > > > for_each_possible_cpu(cpu) {
> > > > <wait for the hazptr slot on
> > > > that CPU to be not equal to
> > > > the removed key>
> > > > }
> > > >
> > > >
> > > > , so that if is_dynamic_key() finds a key was in the hash, even though
> > > > later on the key would be removed by lockdep_unregister_key(), the
> > > > hazard pointers guarantee lockdep_unregister_key() would wait for the
> > > > hazard pointer to release.
> > > >
> > > > > that is passed to lockdep_unregister_key(). In is_dynamic_key():
> > > > >
> > > > >     hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
> > > > >                 if (k == key) {
> > > > >                         found = true;
> > > > >                         break;
> > > > >                 }
> > > > >         }
> > > > >
> > > > > key != k (dead_key), but before accessing its content to get to hash_entry,
> > > > It is the dead_key.
> > > >
> > > > > an interrupt/NMI can happen. In the mean time, the structure holding the key
> > > > > is freed and its content can be overwritten with some garbage. When
> > > > > interrupt/NMI returns, hash_entry can point to anything leading to crash or
> > > > > an infinite loop.  Perhaps we can use some kind of synchronization mechanism
> > > > No, hash_entry cannot be freed or overwritten because the user has
> > > > protect the key with hazard pointers, only when the user reset the
> > > > hazard pointer to NULL, lockdep_unregister_key() can then return and the
> > > > key can be freed.
> > > >
> > > > > between is_dynamic_key() and lockdep_unregister_key() to prevent this kind
> > > > > of racing. For example, we can have an atomic counter associated with each
> > > > The hazard pointer I proposed provides the exact synchronization ;-)
> > > What I am saying is that register_lock_class() is trying to find a newkey
> > > while lockdep_unregister_key() is trying to take out an oldkey (newkey !=
> > > oldkey). If they happens in the same hash list, register_lock_class() will
> > > put newkey into the hazard pointer, but synchronize_lockdep_key_hazptr()
> > > call from lockdep_unregister_key() is checking for oldkey which is not the
> > > one saved in the hazard pointer. So lockdep_unregister_key() will return and
> > > the key will be freed and reused while is_dynamic_key() may just have a
> > > reference to the oldkey and trying to access its content which is invalid. I
> > > think this is a possible scenario.
> > >
> > Oh, I see. And yes, the hazard pointers I proposed cannot prevent this
> > race unfortunately. (Well, technically we can still use an extra slot to
> > hold the key in the hash list iteration, but that would generates a lot
> > of stores, so it won't be ideal). But...
> >
> > [...]
> > > > > head of the hashed table. is_dynamic_key() can increment the counter if it
> > > > > is not zero to proceed and lockdep_unregister_key() have to make sure it can
> > > > > safely decrement the counter to 0 before going ahead. Just a thought!
> > > > >
> > Your idea inspires another solution with hazard pointers, we can
> > put the pointer of the hash_head into the hazard pointer slot ;-)
> >
> > in register_lock_class():
> >
> > /* hazptr: protect the key */
> > WRITE_ONCE(*key_hazptr, keyhashentry(lock->key));
> >
> > /* Synchronizes with the smp_mb() in synchronize_lockdep_key_hazptr() */
> > smp_mb();
> >
> > if (!static_obj(lock->key) && !is_dynamic_key(lock->key)) {
> > return NULL;
> > }
> >
> > in lockdep_unregister_key():
> >
> > /* Wait until register_lock_class() has finished accessing k->hash_entry. */
> > synchronize_lockdep_key_hazptr(keyhashentry(key));
> >
> >
> > which is more space efficient than per hash list atomic or lock unless
> > you have 1024 or more CPUs.
>
> It looks like you are trying hard to find a use case for hazard pointer in
> the kernel :-)
>

Well, if it does the job, why not use it ;-) Also this shows how
flexible hazard pointers can be.

At least when using hazard pointers, the reader side of the hash list
iteration is still lockless. Plus, since the synchronization part
doesn't need to wait for the RCU readers in the whole system, it will be
faster (I tried with the protecting-the-whole-hash-list approach as
well, it's the same result on the tc command). This is why I choose to
look into hazard pointers. Another mechanism can achieve the similar
behavior is SRCU, but SRCU is slightly heavier compared to hazard
pointers in this case (of course SRCU has more functionalities).

We can provide a lockdep_unregister_key_nosync() without the
synchronize_rcu() in it and let users do the synchronization, but it's
going to be hard to enforce and review, especially when someone
refactors the code and move the free code to somewhere else.

> Anyway, that may work. The only problem that I see is the issue of nesting
> of an interrupt context on top of a task context. It is possible that the
> first use of a raw_spinlock may happen in an interrupt context. If the
> interrupt happens when the task has set the hazard pointer and iterating the
> hash list, the value of the hazard pointer may be overwritten. Alternatively
> we could have multiple slots for the hazard pointer, but that will make the
> code more complicated. Or we could disable interrupt before setting the
> hazard pointer.

Or we can use lockdep_recursion:

preempt_disable();
lockdep_recursion_inc();
barrier();

WRITE_ONCE(*hazptr, ...);

, it should prevent the re-entrant of lockdep in irq.

>
> The solution that I am thinking about is to have a simple unfair rwlock to
> protect just the hash list iteration. lockdep_unregister_key() and
> lockdep_register_key() take the write lock with interrupt disabled. While
> is_dynamic_key() takes the read lock. Nesting in this case isn't a problem
> and we don't need RCU to protect the iteration process and so the last
> synchronize_rcu() call isn't needed. The level of contention should be low
> enough that live lock isn't an issue.
>

This could work, one thing though is that locks don't compose. Using a
hash write_lock in lockdep_unregister_key() will create a lockdep_lock()
-> "hash write_lock" dependency, and that means you cannot
lockdep_lock() while you're holding a hash read_lock, although it's
not the case today, but it certainly complicates the locking design
inside lockdep where there's no lockdep to help ;-)

Regards,
Boqun

> Cheers,
> Longman
>
>