You are viewing paulmck

Previous Entry | Next Entry

Stupid RCU Tricks: Bug Hunt Number 1

RCU
The following code fragment contains a bug semi-similar to one recently found in the Linux kernel.

 

 

struct foo {
	struct list_head list;
	int key;
	int data;
};

LIST_HEAD(mylist);
DEFINE_SPINLOCK(mylock);
struct foo *cache;

int search(int key, int *data)
{
	struct foo *p;

	rcu_read_lock();
	p = rcu_dereference(cache);
	if (p != NULL && p->key == key)
		goto found;
	list_for_each_entry_rcu(p, &mylist, list)
		if (p->key == key) {
			rcu_assign_pointer(cache, p);
			goto found;
		}
	rcu_read_unlock();
	return -ENOENT;
found:
	*data = p->data;
	rcu_read_unlock();
	return 0;
}

int insert(int key, int data)
{
	struct foo *p = kmalloc(sizeof(*p), GFP_KERNEL);

	if (p == NULL)
		return -ENOMEM;
	p->key = key;
	p->data = data;
	spin_lock(&mylock);
	list_add_rcu(&p->list, &mylist);
	spin_unlock(&mylock);
}

int delete(int key)
{
	struct foo *p;

	spin_lock(&mylock);
	list_for_each_entry(p, &mylist, list)
		if (p->key == key) {
			list_del_rcu(&p->list);
			spin_unlock(&mylock);
			synchronize_rcu();
			kfree(p);
			return 0;
		}
	spin_unlock(&mylock);
	return -ENOENT;
}


Can you find it and fix it?

Comments

( 4 comments )
(Anonymous)
Jun. 6th, 2011 12:51 am (UTC)
What about the other two....
Apart from the bug you mention there is another ... plus a questionable construct.
	if (cache != NULL) {
		p = rcu_dereference(cache);
		if (p->key == key)

If cache can be NULL, then it could be set to NULL immediately after the first test and before the rcu_dereference which would lead to a NULL deref. Fix would be:
        p = rcu_dereference(cache);
        if (p != NULL) {
                if (p->key == key)


Secondly, the "rcu_assign_pointer(cache,p)" is unnecessary (if I understand its purpose correctly). "cache = p" is sufficient.


You only need rcu_assign_pointer of the referenced structure (*p) is only known to be consistent on the current CPU. Seeing we found p in the list, it must be consistent across all CPUs (at least since list_for_each_entry_rcu called rcu_dereference_raw on it) so there is no need for rcu_assign_pointer. Similarly rcu_assign_pointer(XX, NULL) is always pointless.


Or is it simply considered "good style" to alway use rcu_assign_pointer even when it is not needed? Or did I misunderstand something important?

paulmck
Jun. 6th, 2011 03:09 am (UTC)
Good catch!
Indeed, there is an additional bug and your fix is correct -- as you say, my code is vulnerable to to the double-fetch scenario you call out. Thank you — I am updating the code with the fix you suggest.

However, replacing "rcu_assign_pointer(cache,p)" with "cache=p" could potentially allow aggressive compiler and CPU optimizations to mess things up -- although the "p" depends on the list_for_each_entry_rcu(), the assignment to "cache" does not. The compiler would therefore be within its rights to speculate the value to be stored.

Finally, you are correct that rcu_assign_pointer(XX, NULL) is strictly speaking unnecessary, but sparse will yell at you if you use a simple assignment. And rcu_assign_pointer() does optimize out the memory barrier when you assign NULL, so there is no performance penalty for using it. And it can be a most excellent documentation aid. So, yes, "good style".
axboe
Jun. 6th, 2011 02:59 am (UTC)
Example a bit flawed
Paul, the example should be revised a bit to match the cfq-iosched cache problem. The issue was not forgetting to prune the one-hit cache on deletion. I wish it was, since then it would have been found much sooner! However, the one-hit cache was not properly protected. So when killing the item from the linked list and the radix tree, clearing the cache on match was not done inside the lock protecting the other structures.
paulmck
Jun. 6th, 2011 03:10 am (UTC)
Re: Example a bit flawed
Thank you for keeping me honest, Jens!

I will keep the current example, update the description, and pull yours out in a later posting.
( 4 comments )