sometimes a rcu callback is just calling kfree() to free a struct's memory
(we say this callback is a trivial callback.).
this patch introduce kfree_rcu() to do these things directly, easily.

There are 4 reasons that we need kfree_rcu():

1) unloadable modules:
   a module(rcu callback is defined in this module) using rcu must
   call rcu_barrier() when unload. rcu_barrier() will increase
   the system's overhead(the more cpus the worse) and
   rcu_barrier() is very time-consuming. if all rcu callback defined
   in this module are trivial callback, we can just call kfree_rcu()
   instead, save a rcu_barrier() when unload.

2) duplicate code:
   all trivial callback are duplicate code though the structs to be freed
   are different. it's just a container_of() and a kfree().
   There are about 50% callbacks are trivial callbacks for call_rcu() in
   current kernel code.

3) cache:
   the instructions of trivial callback is not in the cache supposedly.
   calling a trivial callback will let to cache missing very likely.
   the more trivial callback the more cache missing. OK, this is
   not a problem now or in a few days: Only less than 1% trivial callback
   are called in running kernel.

4) future:
   the number of user of rcu is increasing. new code for rcu is
   trivial callback very likely. it means more modules using rcu
   and more duplicate code(may come to 90% of callbacks is trivial
   callbacks) and more cache missing.

Implementation:
   there were a lot of ideas came out when i implemented kfree_rcu().
   I chose the simplest one as this patch shows. but these implementation
   may cannot be used for to free a struct larger than 16KBytes.

kfree_rcu_bh()? kfree_rcu_sched()?
   these two are not need current. call_rcu_bh() & call_rcu_sched()
   are hardly be called(and hardly be called for trivial callback).

vfree_rcu()?
   No, vfree() is not atomic function, will not be called in softirq.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
diff ...
[ message continues ]

All the above could do with some comments explaining what it does.

Please use checkpatch.

Surely it cannot be resirable to have a "function" which can call kfree
either synchronously or asynchronously depending upon the size of the
object which was passed to it?  If the caller wants rcu treatment of
the freeing then that is what the caller must be given.  I mean, if the
caller can tolerate a synchrnous call to kfree() then the caller should
have directly called kfree?

I think (and pray) that the above could have been implemented as an


How can this work?  We take the difference between two pointers, divide
that by 4 or 8, then treat the resulting number as the address of an
RCU callback function.

--

[ message continues ]

__rcu_reclaim either treats head->func as an offset for kfree or as a 
Here it's used:
the softirq that is called after the grace period calls kfree directly 
I'd try to make that a compile time error. Is that possible? perhaps 
with some __builtin_constant_p (head-ptr) or something like that. Or 
__rcu_reclaim() knows that function pointers < 4096 are actually offsets 
for kfree.


I like the idea:
- the call to list->func() is probably very difficult to predict for a 
branch target predictor.
- it's just a waste not to call kfree directly.
- I'm not sure about the implementation.

--
    Manfred
--

[ message continues ]

__rcu_reclaim(head) is called when @head 's grace period had completed.

__rcu_reclaim(head) uses "if (__offset <= __KFREE_RCU_MAX_OFFSET)" to
check whether @head is queued by kfree_rcu() or normal call_rcu().

if @head is queued by kfree_rcu(), ((void *)head - sizeof(void *) * __offset)
is the pointer that the memory chunk need to be freed.

otherwise call head->func(head) as original code.

__rcu_reclaim has __prefix, will not be used by user, it is a helper
for rcu-machine. it is always called asynchronously. sorry for not comments


We will use __rcu_reclaim(head) sort it out when it's grace period has


--

[ message continues ]

You lost me on this one.  Suppose that the following sequence of
events occurred:

a.	The module invokes call_rcu() or kfree_rcu().  The callback
	is queued on CPU 0.

b.	Perhaps a grace period completes, and the callback is therefore
	moved to CPU 0's donelist.  But CPU 0 is busy, so doesn't get
	around to invoking the callback.  (For example, ksoftirqd.)

c.	The module is unloaded, and uses kfree_rcu() instead of
	rcu_barrier().  The callback is queued on CPU 1.

d.	A grace period completes, and CPU 1 is relatively idle, so
	invokes its callback quickly.  The module is therefore unloaded.

e.	CPU 0 finally gets around to executing its callback, but the
	module has been unloaded, so there is nothingness where the
	callback function used to be.  We get an oops.


Indeed!  There was something similar to kfree_rcu() proposed some
years back, but it was rejected because it contained more code than
did the trivial callbacks.  :-/

But there are more such callbacks these days, so might be worth

Reducing code footprint would be a good thing.  Do you have stats on


OK, so the idea is that structures whose rcu_head is near the front
of the structure have the offset of the rcu_head put into the
->func field instead of a pointer to the callback function?

Of course, it doesn't need to be too near the beginning of the
function...

All arches are guaranteed not to have kernel text in the low 16K


OK, so we pass in the pointer to the rcu_head structure, followed
by the offset in pointer-sized units, but with the latter cast to
a pointer to a callback function?  Hmmm....  Kinky....

Then after the grace period completes, the __rcu_reclaim() sorts

--

[ message continues ]

How to usage kfree_rcu:

struct my_struct {
	int data;
	struct rcu_head rcu;
};

----------------original code:--------------------------
void my_struct_release_rcu(struct rcu_head *rcu)
{
	struct my_struct *p;

	item = container_of(rcu, struct my_struct, rcu);
	kfree(p);
}

void some_fuction()
{
	struct my_struct *p;
	.....;
	call_rcu(&p->rcu, my_struct_release_rcu);
	.....;
}
---end---

-----------------after use kfree_rcu:--------------------

/* my_struct_release_rcu() was removed */

void some_fuction()
{
	struct my_struct *p;
	.....;
	kfree_rcu(p, &p->rcu);
	.....;
}
---end---

1) unloadable modules:
   A) use my_struct_release_rcu():
      when we unload this modules, we need call rcu_barrier() to wait
      all my_struct_release_rcu() had called.
   B) use kfree_rcu():
      if all trivial callback are removed and kfree_rcu() are used instead,
      we do not need to wait anything. just quick finish unloading.

2) duplicate code:
   A) use my_struct_release_rcu():
      All trivial callback are very like my_struct_release_rcu(),
      all are duplicate code.
   B) use kfree_rcu():
      all trivial callback are removed, not duplicate code like
      my_struct_release_rcu().

3) cache:
   A) use my_struct_release_rcu():
      my_struct_release_rcu() is called rarely, when my_struct_release_rcu()
      is being called, cache missing will occur.
   B) use kfree_rcu():
      my_struct_release_rcu() is removed, not such cache missing.

4) future:
   A) use my_struct_release_rcu():
      when new user use rcu, the most callback is trivial callback
      like my_struct_release_rcu(). this is the common of using rcu.
      so the problems of above are more and more heavy.
   B) use kfree_rcu():
      fix these problems for ever.





--

[ message continues ]

On Thu, Sep 18, 2008 at 04:59:33PM +0800, Lai Jiangshan wrote:


OK, so the trick is that the module -never- uses call_rcu()
directly, instead using -only- kfree_rcu(), along perhaps also with
synchronize_rcu().  Because kfree_rcu() does not reference module text,
you then don't need to wait at all.  Good point!

							Thanx, Paul
--

[ message continues ]

Hmm: why is rcu_barrier() sufficient to prevent races?
Offlining a cpu reorders rcu callbacks - rcu_barrier() can return before 
all previous call_rcu() callbacks were called.

--
    Manfred

--

[ message continues ]

The rcu_barrier() family of functions registers a callback on each CPU,
and waits until all these callbacks have been invoked.  The CPU offlining
process preserves the order of the callbacks that were registered on a
given CPU.  Thus, when rcu_barrier() returns, all RCU callbacks previously
registered are guaranteed to have already been invoked, regardless of
what CPUs might have been offlined and onlined in the meantime.

							Thanx, Paul
--

[ message continues ]

You are right: I mixed up rcu_barrier() and synchronize_rcu().

--
    Manfred
--

[ message continues ]

We save a rcu_barrier() only when all rcu callback defined in this
module are trivial callback and we use kfree_rcu to instead them.

trivial callbacks are the most common callbacks, so some module may used

I did not have stats on the kernel text size, I think these cache
missing are caused by lots of different trivial callbacks in everywhere,

(unsigned long)head->func is always <= 4095, not 14K or 32K.
we just guaranteed not to have kernel text in the low 4k of memory.

the real offset is (sizeof(void *) * (unsigned long)head->func),

Yes, kernel pointers have redundant information, we use the low 4k
as offset. when ->func < 4k, it stand for offset, when ->func >= 4k,


--

[ message continues ]

The Tiny Linux guys might be interested in even a small reduction in

Good point!

--

[ message continues ]