[PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[Andreea-Cristina Bernat]

* The function "assoc_array_apply_edit()" passes "edit->rcu" to "call_rcu()".
* "assoc_array_apply_edit()'s" callers do not call it under an RCU
read-side critical section.
* The function "assoc_array_gc()" could be preempted between the call to
"assoc_array_apply_edit()" call and the assignment
"edit->array->nr_leaves_on_tree = nr_leaves_on_tree;", so the grace
period could complete.
* The problem is that the assignment could access the freelist.
* Solution:
 Put the call to the "assoc_array_apply_edit()" function and the
 assignment between "rcu_read_lock()" and "rcu_read_unlock()". In this
 way, the callback function provided by the "call_rcu()" call will be
 invoked after all pre-existing critical sections end which means after
 the added critical section.

The first step to detect this was made with the following Coccinelle
semantic patch which looks for calls of functions which have in their bodies a
call to "call_rcu()" with a global first parameter:

@ locally @
identifier l;
type t;
position p;
@@

t l;
... when any
call_rcu@p((<+...l...+>), ...);

@ globally @
identifier fn;
identifier g != locally.l;
position p2 != locally.p;
@@

fn(...) {
... when any
call_rcu@p2((<+...g...+>), ...);
... when any
}

@ other_func @
identifier globally.fn, ff;
@@

ff(...) {
... when any
* fn(...)
... when any
}

The second step was looking at the uses of the functions found and see if the
parameter of interest is used after the call of the function.

Signed-off-by: Andreea-Cristina Bernat <bernat.ada@gmail.com>
---
 lib/assoc_array.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index c0b1007..45d11c0 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -1734,8 +1734,10 @@ ascend_old_tree:
 
 gc_complete:
 	edit->set[0].to = new_root;
+	rcu_read_lock();
 	assoc_array_apply_edit(edit);
 	edit->array->nr_leaves_on_tree = nr_leaves_on_tree;
+	rcu_read_unlock();
 	return 0;
 
 enomem:
-- 
1.9.1

Re: [PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[David Howells]

Andreea-Cristina Bernat <bernat.ada@gmail.com> wrote:

> * The function "assoc_array_gc()" could be preempted between the call to
> "assoc_array_apply_edit()" call and the assignment
> "edit->array->nr_leaves_on_tree = nr_leaves_on_tree;", so the grace
> period could complete.

The bug is real, but this patch isn't the right solution.

The edit script should be considered inaccessible to a function the moment it
calls assoc_array_apply_edit() or assoc_array_cancel_edit().  I think this is
a better way.

David
---
 assoc_array.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

commit 10c26fcc224c0515e15272515e7b9006cb08adc8
Author: David Howells <dhowells@redhat.com>
Date:   Wed Aug 27 18:39:44 2014 +0100

    KEYS: Fix use-after-free in assoc_array_gc()
    
    An edit script should be considered inaccessible by a function once it has
    called assoc_array_apply_edit() or assoc_array_cancel_edit().
    
    However, assoc_array_gc() is accessing the edit script just after the
    gc_complete: label.
    
    Reported-by: Andreea-Cristina Bernat <bernat.ada@gmail.com>
    Signed-off-by: David Howells <dhowells@redhat.com>

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index c0b1007011e1..ae146f0734eb 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -1735,7 +1735,7 @@ ascend_old_tree:
 gc_complete:
 	edit->set[0].to = new_root;
 	assoc_array_apply_edit(edit);
-	edit->array->nr_leaves_on_tree = nr_leaves_on_tree;
+	array->nr_leaves_on_tree = nr_leaves_on_tree;
 	return 0;
 
 enomem:

Re: [PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[Andreea Bernat]

On Thu, Aug 28, 2014 at 12:32:31PM +0100, David Howells wrote:
> Andreea-Cristina Bernat <bernat.ada@gmail.com> wrote:
> 
> > * The function "assoc_array_gc()" could be preempted between the call to
> > "assoc_array_apply_edit()" call and the assignment
> > "edit->array->nr_leaves_on_tree = nr_leaves_on_tree;", so the grace
> > period could complete.
> 
> The bug is real, but this patch isn't the right solution.
> 
> The edit script should be considered inaccessible to a function the moment it
> calls assoc_array_apply_edit() or assoc_array_cancel_edit().  I think this is
> a better way.
> 
> David
> ---
>  assoc_array.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> commit 10c26fcc224c0515e15272515e7b9006cb08adc8
> Author: David Howells <dhowells@redhat.com>
> Date:   Wed Aug 27 18:39:44 2014 +0100
> 
>     KEYS: Fix use-after-free in assoc_array_gc()
>     
>     An edit script should be considered inaccessible by a function once it has
>     called assoc_array_apply_edit() or assoc_array_cancel_edit().
>     
>     However, assoc_array_gc() is accessing the edit script just after the
>     gc_complete: label.
>     
>     Reported-by: Andreea-Cristina Bernat <bernat.ada@gmail.com>
>     Signed-off-by: David Howells <dhowells@redhat.com>
> 
> diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> index c0b1007011e1..ae146f0734eb 100644
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -1735,7 +1735,7 @@ ascend_old_tree:
>  gc_complete:
>  	edit->set[0].to = new_root;
>  	assoc_array_apply_edit(edit);
> -	edit->array->nr_leaves_on_tree = nr_leaves_on_tree;
> +	array->nr_leaves_on_tree = nr_leaves_on_tree;
>  	return 0;

Looks good to me.

Regards,
Andreea

>  
>  enomem:

Re: [PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[David Howells]

Andreea Bernat <bernat.ada@gmail.com> wrote:

> Looks good to me.

Can I put that down as a Reviewed-by?

Thanks,
David

Re: [PATCH RFC] rcu: assoc_array: Add critical section to avoid a bug

[Andreea Bernat]

On Fri, Aug 29, 2014 at 11:49:04PM +0100, David Howells wrote:
> Andreea Bernat <bernat.ada@gmail.com> wrote:
> 
> > Looks good to me.
> 
> Can I put that down as a Reviewed-by?

Yes, it is OK.

Regards,
Andreea

> 
> Thanks,
> David