Re: [PATCH v2 17/24] locking/lockdep: Free lock classes that are no longer in use

[Waiman Long]

On 12/03/2018 07:28 PM, Bart Van Assche wrote:
> Instead of leaving lock classes that are no longer in use in the
> lock_classes array, reuse entries from that array that are no longer
> in use. Maintain a linked list of free lock classes with list head
> 'free_lock_class'. Initialize that list from inside register_lock_class()
> instead of from inside lockdep_init() because register_lock_class() can
> be called before lockdep_init() has been called. Only add freed lock
> classes to the free_lock_classes list after a grace period to avoid that
> a lock_classes[] element would be reused while an RCU reader is
> accessing it.
>
> Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> Cc: Waiman Long <longman@xxxxxxxxxx>
> Cc: Johannes Berg <johannes@xxxxxxxxxxxxxxxx>
> Signed-off-by: Bart Van Assche <bvanassche@xxxxxxx>
> ---
>  include/linux/lockdep.h  |   9 +-
>  kernel/locking/lockdep.c | 237 ++++++++++++++++++++++++++++++++-------
>  2 files changed, 205 insertions(+), 41 deletions(-)
>
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 9421f028c26c..02a1469c46e1 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> ...
>  
> +/* Must be called with the graph lock held. */
> +static void remove_class_from_lock_chain(struct lock_chain *chain,
> +					 struct lock_class *class)
> +{
> +	u64 chain_key;
> +	int i;
> +
> +#ifdef CONFIG_PROVE_LOCKING
> +	for (i = chain->base; i < chain->base + chain->depth; i++) {
> +		if (chain_hlocks[i] != class - lock_classes)
> +			continue;
> +		if (--chain->depth == 0)
> +			break;
> +		memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
> +			(chain->base + chain->depth - i) *
> +			sizeof(chain_hlocks[0]));
> +		/*
> +		 * Each lock class occurs at most once in a
> +		 * lock chain so once we found a match we can
> +		 * break out of this loop.
> +		 */
> +		break;
> +	}
> +	/*
> +	 * Note: calling hlist_del_rcu() from inside a
> +	 * hlist_for_each_entry_rcu() loop is safe.
> +	 */
> +	if (chain->depth == 0) {
> +		/* To do: decrease chain count. See also inc_chains(). */
> +		hlist_del_rcu(&chain->entry);
> +		return;
> +	}
> +	chain_key = 0;
> +	for (i = chain->base; i < chain->base + chain->depth; i++)
> +		chain_key = iterate_chain_key(chain_key, chain_hlocks[i] + 1);

Do you need to recompute the chain_key if no entry in the chain is removed?

>  
> @@ -4141,14 +4253,31 @@ static void zap_class(struct lock_class *class)
>  	for (i = 0, entry = list_entries; i < nr_list_entries; i++, entry++) {
>  		if (entry->class != class && entry->links_to != class)
>  			continue;
> +		links_to = entry->links_to;
> +		WARN_ON_ONCE(entry->class == links_to);
>  		list_del_rcu(&entry->entry);
> +		check_free_class(class);

Is the check_free_class() call redundant? You are going to call it near
the end below.
>  	}
> -	/*
> -	 * Unhash the class and remove it from the all_lock_classes list:
> -	 */
> -	hlist_del_rcu(&class->hash_entry);
> -	class->hash_entry.pprev = NULL;
> -	list_del(&class->lock_entry);
> +	check_free_class(class);
> +	WARN_ONCE(class->hash_entry.pprev,
> +		  KERN_INFO "%s() failed for class %s\n", __func__,
> +		  class->name);
> +
> +	remove_class_from_lock_chains(class);
> +}

> +
> +static void reinit_class(struct lock_class *class)
> +{
> +	void *const p = class;
> +	const unsigned int offset = offsetof(struct lock_class, key);
> +
> +	WARN_ON_ONCE(!class->lock_entry.next);
> +	WARN_ON_ONCE(!list_empty(&class->locks_after));
> +	WARN_ON_ONCE(!list_empty(&class->locks_before));
> +	memset(p + offset, 0, sizeof(*class) - offset);
> +	WARN_ON_ONCE(!class->lock_entry.next);
> +	WARN_ON_ONCE(!list_empty(&class->locks_after));
> +	WARN_ON_ONCE(!list_empty(&class->locks_before));
>  }

Is it safer to just reinit those fields before "key" instead of using
memset()? Lockdep is slow anyway, doing that individually won't
introduce any noticeable slowdown.

>  
>  static inline int within(const void *addr, void *start, unsigned long size)
> @@ -4156,6 +4285,38 @@ static inline int within(const void *addr, void *start, unsigned long size)
>  	return addr >= start && addr < start + size;
>  }
>  
> +/*
> + * Free all lock classes that are on the zapped_classes list. Called as an
> + * RCU callback function.
> + */
> +static void free_zapped_classes(struct callback_head *ch)
> +{
> +	struct lock_class *class;
> +	unsigned long flags;
> +	int locked;
> +
> +	raw_local_irq_save(flags);
> +	locked = graph_lock();
> +	rcu_callback_scheduled = false;
> +	list_for_each_entry(class, &zapped_classes, lock_entry) {
> +		reinit_class(class);
> +		nr_lock_classes--;
> +	}
> +	list_splice_init(&zapped_classes, &free_lock_classes);
> +	if (locked)
> +		graph_unlock();
> +	raw_local_irq_restore(flags);
> +}
> +
> +/* Must be called with the graph lock held. */
> +static void schedule_free_zapped_classes(void)
> +{
> +	if (rcu_callback_scheduled)
> +		return;
> +	rcu_callback_scheduled = true;
> +	call_rcu(&free_zapped_classes_rcu_head, free_zapped_classes);
> +}
> +
>  /*
>   * Used in module.c to remove lock classes from memory that is going to be
>   * freed; and possibly re-used by other modules.
> @@ -4181,10 +4342,11 @@ void lockdep_free_key_range(void *start, unsigned long size)
>  	for (i = 0; i < CLASSHASH_SIZE; i++) {
>  		head = classhash_table + i;
>  		hlist_for_each_entry_rcu(class, head, hash_entry) {
> -			if (within(class->key, start, size))
> -				zap_class(class);
> -			else if (within(class->name, start, size))
> -				zap_class(class);
> +			if (!class->hash_entry.pprev ||
> +			    (!within(class->key, start, size) &&
> +			     !within(class->name, start, size)))
> +				continue;
> +			zap_class(class);
>  		}
>  	}
>  
> @@ -4193,18 +4355,14 @@ void lockdep_free_key_range(void *start, unsigned long size)
>  	raw_local_irq_restore(flags);
>  
>  	/*
> -	 * Wait for any possible iterators from look_up_lock_class() to pass
> -	 * before continuing to free the memory they refer to.
> -	 *
> -	 * sync_sched() is sufficient because the read-side is IRQ disable.
> +	 * Do not wait for concurrent look_up_lock_class() calls. If any such
> +	 * concurrent call would return a pointer to one of the lock classes
> +	 * freed by this function then that means that there is a race in the
> +	 * code that calls look_up_lock_class(), namely concurrently accessing
> +	 * and freeing a synchronization object.
>  	 */
> -	synchronize_sched();
>  
> -	/*
> -	 * XXX at this point we could return the resources to the pool;
> -	 * instead we leak them. We would need to change to bitmap allocators
> -	 * instead of the linear allocators we have now.
> -	 */
> +	schedule_free_zapped_classes();

Should you move the graph_unlock() and raw_lock_irq_restore() down to
after this? The schedule_free_zapped_classes must be called with
graph_lock held. Right?

Cheers,
Longman