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

(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".