Monthly Archives: July 2014

rcu_assign_pointer()

The time passes so quickly and all the interns have only a few weeks before the end of this internship. Anyway, my work for Linux kernel will continue for sure even after OPW.

In this post I will present two Coccinelle scripts for one of the tasks that I talked about in the previous posts (the one with the “rcu_assign_pointer()” and its replacement with “RCU_INIT_POINTER()” or not).

The following Coccinelle script says when we need to keep the “rcu_assign_pointer()” call (and not replacing it with “RCU_INIT_POINTER()”) for the case when the value that will be assigned to the pointer is updated before the call (by a call to another function that might update it or in other ways):

/* The first rule finds different ways in which the value is updated before the call */

@ value_updated @
identifier upd;
identifier v;
@@
(
 (<+…v…+>) = …;
|
\(memset\|memcpy\)((<+…v…+>), …);
|
upd(v, …);
|
atomic_inc((<+…v…+>));
|
++(<+…v…+>);
)
… when any
rcu_assign_pointer(…, v);

/* This rule sees if the update function found in the previous rule updates the parameter */

@ update_func @
identifier value_updated.upd;
identifier fv;
type t;
@@

upd(t fv,…) {
… when any
(
 (<+…fv…+>) = …;
|
\(memset\|memcpy\)((<+…fv…+>), …);
|
atomic_inc((<+…fv…+>));
)
… when any
}

/* The rule ignores this case because this is a case where we actually can use “RCU_INIT_POINTER()” according to “RCU_INIT_POINTER()’s” block comment, section 3a. */

@ ignore @
identifier value_updated.v;
@@

v = rcu_dereference(…);
… when != rcu_dereference(…);
      when != v = …;
      when != \(memcpy\|memset\)(…);
rcu_assign_pointer(…, v);

/* This rule highlights the pairs “update the value – call of “rcu_assign_pointer()”” because I want to see only these cases and not other uses of “rcu_assign_pointer()” that are not treated in this script */

@ match1 depends on !ignore @
identifier v;
@@

(
* (<+…v…+>) = …;
|
* \(memset\|memcpy\)((<+…v…+>), …);
|
* atomic_inc((<+…v…+>));
|
* ++(<+…v…+>);
)
… when any
* rcu_assign_pointer(…, v);

/* Also, this rule highlights the pairs “function that updates the value – call of “rcu_assign_pointer()”” */

@ print depends on update_func @
identifier v;
identifier value_updated.upd;
@@

* upd(v, …);
… when any
* rcu_assign_pointer(…, v);

 

Let’s see some examples:

-> for the file “block/blk-cgroup.c” the output is:

– blkg = radix_tree_lookup(&blkcg->blkg_tree, q->id);
if (blkg && blkg->q == q) {
if (update_hint) {
lockdep_assert_held(q->queue_lock);
– rcu_assign_pointer(blkcg->blkg_hint, blkg);

 

-> for the file “kernel/workqueue.c”:

– link_pwq(pwq);

old_pwq = rcu_access_pointer(wq->numa_pwq_tbl[node]);
– rcu_assign_pointer(wq->numa_pwq_tbl[node], pwq);

* the function “link_pwd()” updates the parameter “pwq”

-> for the file “drivers/infiniband/hw/qib/qib_qp.c”:

– atomic_inc(&qp->refcount);
spin_lock_irqsave(&dev->qpt_lock, flags);if (qp->ibqp.qp_num == 0)
– rcu_assign_pointer(ibp->qp0, qp);
else if (qp->ibqp.qp_num == 1)
– rcu_assign_pointer(ibp->qp1, qp);
else {
– qp->next = dev->qp_table[n];
– rcu_assign_pointer(dev->qp_table[n], qp);

 

Another Coccinelle semantic patch that actually replaces the function is:

/* “RCU_INIT_POINTER()’s” block comment, section 1 is used for the NULL part and the section 3a is used for “rcu_dereference_protected()” and “rtnl_dereference()” (which actually calls the previous one) */
@ match1 @
@@

– rcu_assign_pointer
+ RCU_INIT_POINTER
(…,
(
NULL
|
rcu_dereference_protected(…)
|
rtnl_dereference(…)
) )

/* Because there are cases where between a “rcu_dereference()” call and a “rcu_assign_pointer()” call can be updates of the value that interests us, we need to ignore them and replace only when the update is not happening */

@ match2 @
identifier v;
@@

v = rcu_dereference(…);
… when != rcu_dereference(…);
      when != v = …;
      when != \(memcpy\|memset\)(…);
(
– rcu_assign_pointer
+ RCU_INIT_POINTER
(…, v);
|
if(…) {
… when != v = …;
– rcu_assign_pointer
+ RCU_INIT_POINTER
(…, v);
… when != v = …;
}
)

 

Some output examples (or parts of examples):

-> for the file “block/genhd.c”:

part = rcu_dereference(ptbl->part[i]);if (part && sector_in_part(part, sector)) {

– rcu_assign_pointer(ptbl->last_lookup, part);
+ RCU_INIT_POINTER(ptbl->last_lookup, part);if (old_ptbl) {

– rcu_assign_pointer(old_ptbl->last_lookup, NULL);
+ RCU_INIT_POINTER(old_ptbl->last_lookup, NULL);

 

-> for the file “drivers/infiniband/ulp/ipoib/ipoib_main.c”:

– rcu_assign_pointer(*np,
+ RCU_INIT_POINTER(*np,
rcu_dereference_protected(neigh->hnext,
lockdep_is_held(&priv->lock)));

 

Also, I have some good news. I successfully ran the kernel with qemu with the help of my mentor 🙂

Advertisements

Coccinelle

In the past couple of weeks I concentrated on Coccinelle, learning its syntax and figure how to write my Coccinelle scripts to do what I want in order to complete my tasks.

Let’s see the cases promised in the previous post where “RCU_INIT_POINTER()” can be replaced with “rcu_assign_pointer()”. These are the cases from “RCU_INIT_POINTER()’s” block comment:

1. This use of RCU_INIT_POINTER() is NULLing out the pointer -or-

2. The caller has taken whatever steps are required to prevent RCU readers from concurrently accessing this pointer -or-

3. The referenced data structure has already been exposed to readers either at compile time or via rcu_assign_pointer() -and-

a. You have not made -any- reader-visible changes to this structure since then -or-

b. It is OK for readers accessing this structure from its new location to see the old state of the structure. (For example, the changes were to statistical counters or to other state where exact synchronization is not required.)

The first case is the most simpler and the Coccinelle semantic patch is very short and easy:

@@ expression E; @@

– rcu_assign_pointer(E, NULL)

+ RCU_INIT_POINTER(E, NULL)

I thought about how I can write a Coccinelle script to detect the next two cases and it was a bit hard to find particular cases that would be worth writing a Coccinelle script and automatize a specific case (that is because of the different cases where “rcu_assign_pointer()” is used). So, together with my mentor, we decided that I should be writing a Coccinelle script which detects when you should keep the call “rcu_assign_pointer()” instead.

Currently, I am trying to detect when the value that is going to be assigned to the pointer is updated before “rcu_assign_pointer()” because this is one common case where “RCU_INIT_POINTER()” isn’t needed. One difficult case is that I have to find the call of the function where “v” is a parameter and after that, to verify if “v” is updated in the code of that function:

function(…) {

func_that_might_update_v(v, …);

rcu_assign_pointer(p, v);

}

I will keep you updated and I am hoping that in the next few days I will complete what I have in my mind.

 

A week ago, I took a pause from the above task. I received an email from my mentor in which he offered me an extra task, if I wanted. The task consists of writing a Coccinelle script that detects use of “alloc_percpu()” that assigns to a global variable without either an “smp_mb()”, “smp_wmb()”, or “smp_store_release()”.

“alloc_percpu()” is a macro and it allocates one instance of the type given as a parameter for every processor on the system (all percpu areas are zeroed on allocation). There are cases where is the need for barriers to prevent one or more CPU’s to see garbage values.

I started by finding the calls “alloc_percpu()”. After that, I verified if the variable that the call assigns is a local or global variable. A variable which is not local, it is global. I used the metavariable type “position” offered by Coccinelle:

@ locally @
local idexpression l;
position p;
@@

(<+…l…+>) =@p alloc_percpu(…)

@ globally @
expression g;
position p != locally.p;
@@

g@p = alloc_percpu(…)

Practically, I located all local variables and after that, I excluded them in order to remain with the global ones.

I encountered problems when I tested because in some cases the output said that a certain variable was global when it was not. Even with this problem, during one online meeting with my mentor we realised that harder things are to come. The detection of the barrier and if that barrier is what we are looking for or not, is not easy and maybe not suitable for a Coccinelle script.

So, after a little talking, we decided to change the way in which we approach this problem. We know for sure that if the variable that “alloc_percpu()” assigns is updated after that call we need a barrier.

I will make a Coccinelle script that detects if a global variable that receives memory through the call “alloc_percpu()” is initialized after the allocation.

In a few days, I will come up with the final results for these tasks . Also, I will tell you about my adventure with qemu, trying to run the kernel.