linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Peter Zijlstra <peterz@infradead.org>
To: Bart Van Assche <bvanassche@acm.org>
Cc: mingo@redhat.com, tj@kernel.org, longman@redhat.com,
	johannes.berg@intel.com, linux-kernel@vger.kernel.org,
	Johannes Berg <johannes@sipsolutions.net>
Subject: Re: [PATCH v3 17/24] locking/lockdep: Free lock classes that are no longer in use
Date: Fri, 7 Dec 2018 13:14:29 +0100	[thread overview]
Message-ID: <20181207121429.GI2237@hirez.programming.kicks-ass.net> (raw)
In-Reply-To: <20181207011148.251812-18-bvanassche@acm.org>

On Thu, Dec 06, 2018 at 05:11:41PM -0800, Bart Van Assche wrote:
> +	if (WARN_ON_ONCE(!hlock_class(prev)->hash_entry.pprev) ||
> +	    WARN_ONCE(!hlock_class(next)->hash_entry.pprev,
> +		      KERN_INFO "Detected use-after-free of lock class %s\n",
> +		      hlock_class(next)->name)) {
> +		return 2;
> +	}

Ah, this is that UaF on ->name, but it only happens when there's already
been a UaF, so that's fine I suppose. Still a note on that earlier
Changelog would've been nice I suppose.

> +/* 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)
 {
> +			memmove(&chain_hlocks[i], &chain_hlocks[i + 1],
> +				(chain->base + chain->depth - i) *
> +				sizeof(chain_hlocks[0]));
 }

Also, I suppose a comment here that notes we 'leak' chain_hlock[]
entries would be appropriate here.

If Waiman cares, it is possible to reclaim then by extending the above
memmove() to cover the _entire_ tail of the array and then going around
and fixing up all the chain->base 'pointers' that are in the moved part.

> +		/*
> +		 * Each lock class occurs at most once in a
> +		 * lock chain so once we found a match we can
> +		 * break out of this loop.
> +		 */
> +		goto recalc;
> +	}
> +	/* Since the chain has not been modified, return. */
> +	return;
> +
> +recalc:
> +	/*
> +	 * 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);
> +	if (chain->chain_key == chain_key)
> +		return;
> +	hlist_del_rcu(&chain->entry);
> +	chain->chain_key = chain_key;
> +	hlist_add_head_rcu(&chain->entry, chainhashentry(chain_key));

I think this is broken; while hlist_del_rcu() and hlist_add_head_rcu()
are individually safe against concurrent hlist_for_each_entry_rcu(),
they cannot be used consecutively like this.

The thing is, hlist_del_rcu() preserves the ->next pointer such that
a concurrent hlist_for_each_entry_rcu() that happens to be at that entry
will be able to continue.

But your hlist_add_head_rcu() will overwrite that, so the concurrent
iterator, which started on one list will continue on another.

There must be an RCU-GP between del_rcu and add_rcu such that the above
situation cannot happen.


> +/*
> + * 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();

If this fails; you must not touch any of the state. You don't hold the
lock after all.

> +	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);
> +}

But I fear this is fundamentally broken too. In exactly the manner I
tried to explain earlier.

(sorry, wide(r) terminal required)

It starts out good:

	CPU0			CPU1				CPU2

	rcu_read_lock()
	// use class
				zap_class()
				schedule_free_zapped_classes();
				  call_rcu();

	rcu_read_lock()

				/* since none of the rcu_read_lock()
				 * sections we started out with are
				 * still active; this is where the
				 * callback _can_ happen */

But then, another user and and removal come in:

	rcu_read_lock();

	// use class						zap_class()
								  list_add(&entry, &zapped_classes)
								schedule_free_zapped_classes()
								  /* no-op, still pending */

				free_zapped_classes()
				  list_splice(&zapped_classes, &free_lock_classes)

				  *whoops* we just splice'd a class
				  onto the free list that is still in
				  use !!


	rcu_read_unlock()


There's two possible solutions:

 - the second schedule_free_zapped_classes() must somehow ensure the
   call_rcu() callback re-queues itself and waits for yet another GP, or

 - you must add classes zapped after the first invocation to a second
   list.



  reply	other threads:[~2018-12-07 12:14 UTC|newest]

Thread overview: 49+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-07  1:11 [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 01/24] lockdep tests: Display compiler warning and error messages Bart Van Assche
2018-12-11 15:22   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 02/24] lockdep tests: Fix shellcheck warnings Bart Van Assche
2018-12-11 15:23   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 03/24] lockdep tests: Improve testing accuracy Bart Van Assche
2018-12-11 15:23   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 04/24] lockdep tests: Run lockdep tests a second time under Valgrind Bart Van Assche
2018-12-11 15:24   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 05/24] liblockdep: Rename "trywlock" into "trywrlock" Bart Van Assche
2018-12-11 15:24   ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-11 17:19   ` [PATCH v3 05/24] liblockdep: " Sasha Levin
2018-12-11 17:38     ` Bart Van Assche
2018-12-13 19:41       ` Sasha Levin
2018-12-07  1:11 ` [PATCH v3 06/24] liblockdep: Add dummy print_irqtrace_events() implementation Bart Van Assche
2018-12-11 15:25   ` [tip:locking/core] tools/lib/lockdep: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 07/24] lockdep tests: Test the lockdep_reset_lock() implementation Bart Van Assche
2018-12-11 15:26   ` [tip:locking/core] tools/lib/lockdep/tests: " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 08/24] locking/lockdep: Declare local symbols static Bart Van Assche
2018-12-11 15:26   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 09/24] locking/lockdep: Inline __lockdep_init_map() Bart Van Assche
2018-12-11 15:27   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 10/24] locking/lockdep: Introduce lock_class_cache_is_registered() Bart Van Assche
2018-12-11 15:27   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 11/24] locking/lockdep: Remove a superfluous INIT_LIST_HEAD() statement Bart Van Assche
2018-12-11 15:28   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 12/24] locking/lockdep: Make concurrent lockdep_reset_lock() calls safe Bart Van Assche
2018-12-11 15:29   ` [tip:locking/core] " tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 13/24] locking/lockdep: Stop using RCU primitives to access all_lock_classes Bart Van Assche
2018-12-11 15:29   ` [tip:locking/core] locking/lockdep: Stop using RCU primitives to access 'all_lock_classes' tip-bot for Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 14/24] locking/lockdep: Make zap_class() remove all matching lock order entries Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 15/24] locking/lockdep: Reorder struct lock_class members Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 16/24] locking/lockdep: Retain the class key and name while freeing a lock class Bart Van Assche
2018-12-07 10:21   ` Peter Zijlstra
2018-12-07 14:50     ` Waiman Long
2018-12-07 16:23       ` Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 17/24] locking/lockdep: Free lock classes that are no longer in use Bart Van Assche
2018-12-07 12:14   ` Peter Zijlstra [this message]
2018-12-07 16:27     ` Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 18/24] locking/lockdep: Reuse list entries " Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 19/24] locking/lockdep: Check data structure consistency Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 20/24] locking/lockdep: Introduce __lockdep_free_key_range() Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 21/24] locking/lockdep: Verify whether lock objects are small enough to be used as class keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 22/24] locking/lockdep: Add support for dynamic keys Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 23/24] kernel/workqueue: Use dynamic lockdep keys for workqueues Bart Van Assche
2018-12-07  1:11 ` [PATCH v3 24/24] lockdep tests: Test dynamic key registration Bart Van Assche
2018-12-07 12:23 ` [PATCH v3 00/24] locking/lockdep: Add support for dynamic keys Peter Zijlstra
2018-12-07 16:35   ` Bart Van Assche
2018-12-08 10:26     ` Peter Zijlstra

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20181207121429.GI2237@hirez.programming.kicks-ass.net \
    --to=peterz@infradead.org \
    --cc=bvanassche@acm.org \
    --cc=johannes.berg@intel.com \
    --cc=johannes@sipsolutions.net \
    --cc=linux-kernel@vger.kernel.org \
    --cc=longman@redhat.com \
    --cc=mingo@redhat.com \
    --cc=tj@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).