Log in

No account? Create an account

Previous Entry | Next Entry

Suppose that a very long linked list was to be protected with SRCU. Let's also make the presumably unreasonable assumption that this list is so long that we don't want to stay in a single SRCU read-side critical section for the whole traversal.

So why not try hand-over-hand SRCU protection, as shown in the following code fragment?

  1 struct foo {
  2   struct list_head list;
  3   ...
  4 };
  6 LIST_HEAD(mylist);
  7 struct srcu_struct mysrcu;
  9 void process(void)
 10 {
 11   int i1, i2;
 12   struct foo *p;
 14   i1 = srcu_read_lock(&mysrcu);
 15   list_for_each_entry_rcu(p, &mylist, list) {
 16     do_something_with(p);
 17     i2 = srcu_read_lock(&mysrcu);
 18     srcu_read_unlock(&mysrcu, i1);
 19     i1 = i2;
 20   }
 21   srcu_read_unlock(&mysrcu, i1);
 22 }

The trick is that on each pass through the loop, we enter a new SRCU read-side critical section, then exit the old one. That way the entire traversal is protected by SRCU, but each SRCU read-side critical section is quite short, covering traversal of but a single element of the list.

As is customary with SRCU, the list is manipulated using list_add_rcu(), list_del_rcu, and friends.

What are the advantages and disadvantages of this hand-over-hand SRCU list traversal?


( 3 comments — Leave a comment )
Pedro Ramalhete
Sep. 3rd, 2015 12:19 pm (UTC)
Is it possible to free memory with this technique?
Hi Paul,

One question: Is it still possible to remove and free a node as in the usual RCU usage?
I'm wondering whether the usual example for removal is still ok with the hand-over-hand technique:

1 p = search(head, key);
2 if (p != NULL) {
3 list_del_rcu(&p->list);
4 synchronize_rcu();
5 kfree(p);
6 }

Suppose Thread 1 (T1) is calling process() in the example of your post, and T2 is calling
the removal shown above.
- T1 goes to line 16 and calls do_something_with(p);
- T2 goes to line 3 and calls list_del_rcu() then blocks on line 4;
- T1 goes to line 19, but it is still holding a pointer to 'p', which it will use to advance to the next node/foo;
- T2 goes to line 5 and calls kfree(p);
- T1 tries to advance to the next node but crashes when accessing p->list->next because p has been free'd;

Is this a possible scenario?

Sep. 4th, 2015 01:18 am (UTC)
Re: Is it possible to free memory with this technique?
Indeed it is! Feel free to follow the link at the end of the post. :-)
Pedro Ramalhete
Sep. 4th, 2015 01:34 pm (UTC)
Re: Is it possible to free memory with this technique?
Dope.. I missed the link :)

Ok I get it, and because list_add_rcu() can only insert at the beginning (head) of the list, it's safe to do it the way it says on the last example of the link.

Cool trick!

Thanks for the explanation.
( 3 comments — Leave a comment )