8-CPU (SMP) #s for lockfree rtcache

Hi Dave,

Here are the SMP numbers that you had asked for. They were measured on an 8-CPU SMP box (PIII Xeon 700 MHz processors, 1MB L2 cache and 6GB RAM).

The test was as per your suggestion. rt_rcu is a patch that uses RCU to do lockfree lookup of ipv4 route cache.

The basic test sends a fixed number of packets to random destination addresses repeating every dest for 5 packets. We tried two configurations of this test - 8-1-32 where 32 test processes simultaneosly uses 32 different random seeds to generate different dest addreses and 8-4-8 where 8 sets, each consisting 4 processes all of whom use the same random seed generating the same dst addresses, send packets to the dest addresses repeating dest for every 5 packets.

With these basic tests, we measured under several other conditions - avoid forced neighbor table garbage collection by increasing the threshold and interval (to 31048576 and
60) and slowing the packet rate by introducing a delay of 2ms between bursts of 5 packets.

Here are the results in terms of profile counts in ip_route_output_key() - gc stands for neighbor table garbage collection adjustment and u2000 stands for 2ms packet rate delay. All measurements where done based on 2.5.3 kernel.

Test                            base    rtrcu    speedup
----                            ----    -----    -------
8-1-32                          2358    1655     29.8%
8-1-32-gc                       4486    2176     51.4%
8-1-32-u2000                    2990    1942     35.0%
8-1-32-u2000-gc                 4047    2029     49.8%

8-4-8                           2870    1965     31.5%
8-4-8-gc                        3389    2083     38.5%
8-4-8-u2000                     3459    2373     31.3%
8-4-8-u2000-gc                  4686    2603     44.4%

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

From: Dipankar Sarma <[email protected]>
Date: Tue, 28 May 2002 17:11:04 +0530

Here are the results in terms of profile counts in ip_route_output_key() - gc stands for neighbor table garbage collection adjustment and u2000 stands for 2ms packet rate delay. All measurements where done based on 2.5.3 kernel.

Thanks, I am convinced RCU is the way to go.

Once the generic RCU bits are in the 2.5.x tree, feel free to send me your ipv4 routing cache changes.

Well, the last time RCU was discussed, Linus said that he would like to see someplace where RCU clearly helps.

Linus, would you consider this to be such a case and consider including the rcu_poll patch from aa series of kernels ? It has been a part of aa kernels for quite a while now. The latest RCU patches support preemption and AFAICS, new module unloading and cpu hotplug frameworks can use the RCU synchronize_kernel() interface.

Or atleast, we can perhaps discuss RCU and see if there are potential issues that have not been disected so far.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

From: Dipankar Sarma <[email protected]>
Date: Tue, 28 May 2002 18:28:06 +0530

Well, the last time RCU was discussed, Linus said that he would like to see someplace where RCU clearly helps.

Alexey and I are in firm agreement that the routing cache clearly benefits from RCU.

I am not. :P

I agree the numbers posted are nice, but I remain skeptical like Linus. Sure, the locking overhead is nearly gone in the profiled function where RCU is used. But the overhead has just been _moved_ to wherever the RCU work is now done. Any benchmark needs to include the damage done there, too.

I also balk at implicit locking...

Robert Love

Hello!

rcu is not implicit. At least in the only demo, which I have read i.e. in routing cache, it is more explicit than spinlocks are. :-)

I also strongly dislike any kind of implicit serialization and even not standard serialization. So, rcu used in route.c is supposed to be cleaned of assembly style code and converted to something more intelligible.

Alexey

The next obvious benefitor IMHO is module unloading. Just putting a synchronize_kernel() somewhere at the end of sys_delete_modules() after the destructor makes module unloading much less nasty than it used to be (yes it doesn't fix all possible module unload races, but a large share of them and it makes the problem much more controllable)

-Andi

For 2.5 it would be much more productive to make sys_delete_module memset the entire vmalloced space of the module to an illegal instruction before returning

There is a much bigger question here, which is "are modules first class citizens"? Doing it properly turns us into a poor-man's microkernel. We would standardize our registration interfaces (similar to the standard notifier.h), and have them all do the inc and decs.

OTOH, if you treat module removal as a CONFIG_DEBUG_KERNEL thing, life becomes much much simpler.

I have the code, I'll be serious about it in ~2 months. Rusty.

   there are those who do and those who hang on and you don't see too
   many doers quoting their contemporaries.  -- Larry McVoy

Hi Robert,

Have you looked at the rt_rcu patch ? Where do you think there is overhead compared to what route cache alread does ? In my profiles, rcu routines and kernel mechanisms that it uses don't show high up. If you have any suggestions, then I can do an investigation.

I agree that it is better to keep things simple and RCU isn't a replacement for locking. However the route cache hash table with refcount is a relatively simpler use of RCU and since it has benefits, we shouldn't shy away from using it if it is useful.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

And gain tons of new atomic_incs and decs everywhere in the process? I would prefer RCU.

-Andi

RCU is a great way to make sure people get module unloading *wrong*. It has to be simple for the driver authors. The odd locked operation on things like open() of a device file is not a performance issue, not remotely.

Lots of people write drivers, many of them not SMP kernel locking gurus who have time to understand RCU and when they can or cannot sleep, and what happens if their unload is pre-empted and RCU is in use. The kernel core has to provide a clean easy interface. The network code is a superb example of this. All the hard thinking is done outside of the driver, at least unless you choose to join in that thinking to get the last scraps of performance.

Alan

Hi Robert,

While we are at it, I think this is good point to analyze. So here is an brief analysis of rt_rcu patch from the overhead standpoint -

1. Read side has no overhead, we just don't take the per-bucket lock.
2. For just the route cache portion of code, RCU comes into picture only when dst entries are deleted. This however has two issues - a> expiry of dst entries is checked through a non-frequent timer b>lease for recently used dst entries are extended. So we don't do frequent RCU based deletion of dst entries. Periodically a set of dst entries expire and instead of freeing them immediately, we just put them in RCU queue(s) for freeing after the grace period (call_rcu() in rt_free()).

Coming to the RCU mechanism -

1. Grace period detection : Different RCU algorithms do it differently, however if there is no RCU pending *nothing* is done regarding this. One rcu implementation uses
a 10ms timer to check for grace period completion and another rcu_poll uses a repeating tasklet to poll for it. The grace period detection is based on a per-cpu context switch counter. I have not seen signficant profile counts for grace period detection scheme, but nevertheless I will put up the profile counts for Dave's test at the LSE website.

2. Actual update : RCU processes the batched update callbacks from tasklet context. The rt_rcu callbacks don't do anything other than call dst_free(), which would have been called by non-RCU code under lock in any case. I am not sure doing this from tasklet context adds any overhead and I suspect that it doesn't.

Comments/suggestions ?

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

open() of device file is not the problem. The problem are lots of other data structures that gain module owners and atomic counters all the time.

The current RCU patch doesn't kick in for preemption, so preemption is a non issue.

They have to understand when things can or cannot sleep. Without that I think they shouldn't write linux drivers, because they will get many things wrong (like spinlocks or even interrupt disabling in 2.5)

With the "simple" module unload RCU variant you just stick a synchronize_kernel() after the module destructor call

It's also no problem for them to sleep in the destructor, the simple variant obviously makes no difference here. It also doesn't change any sleeping rules; or at least they are not different than in 2.0/2.2.

Just this simple variant plugs a lot of the races and would allow dropping some module counts. It also makes all the nasty "cannot do MOD_*USE_COUNT in the driver code itself" issues go away.

The remaining hole is driver reentering while the cleanup runs. The simple rcu unload assumes that open and cleanup are atomic to each other, which is usually not true. Fixing that properly likely requires two stage cleanup as proposed by Rusty/Kaos.

Still given that the simple variant is not a complete solution, just making the issue of not being able to do MOD_*_COUNT in driver code go away would be imho a bit step forward. In fact following your initial point it would make some code much more obvious to device driver writers.

-Andi

Hi Robert,

I did a crude analysis of RCU overhead for rt_rcu-2.5.3-1.patch and the corresponding RCU infrastructure patch rcu_ltimer-2.5.3-1.patch.
(http://prdownloads.sourceforge.net/lse/rcu_ltimer-2.5.3-1.patch).
The rcu_ltimer patch uses the local timer interrupt handler to check if there is any RCU pending for that that CPU. The smp_local_timer_interrupt() routine is never counted for profiling, but it happens every 10ms and the RCU overhead is limited
to checking a few CPU-local things and scheduling the per-CPU RCU tasklet. The rest of the RCU code is entirely in rcupdate.c and were measured in kernel profiling.

Here is an analysis of what we can measure -

1. rt_rcu with neighbor table garbage collection threshold increased prevent frequent overflow (due to random dest addresses). (8-1-32-gc31048576gcint60 configuration in earlier published results).

Function                              2.5.3              rt_rcu-2.5.3
--------                              ------             ------------

ip_route_output_key [c0214470]: 4486 2026

call_rcu [c0125f40]:                   N/A                 11
rcu_process_callbacks [c01261d0]:      N/A                 4
rcu_invoke_callbacks [c0125fc0]:       N/A                 4

So with infrequent updates, clearly RCU overheads are practically negligible.

2. rt_rcu with frequent neighbor table overflow (due to random dest addresses) (8-1-32 configuration in earlier published results).

Function                              2.5.3              rt_rcu-2.5.3
--------                              ------             ------------
ip_route_output_key [c0214470]:       2358                 1646

call_rcu [c0125f40]:                  N/A                  262
rcu_invoke_callbacks [c0125fc0]:      N/A                  57
rcu_process_callbacks [c01261d0]:     N/A                  49
rcu_check_quiescent_state [c0126030]: N/A                  27
rcu_check_callbacks [c01260d0]:       N/A                  24
rcu_reg_batch [c0125ff0]:             N/A                  3

This shows that with very frequent RCU updates, the real gains made in ip_route_output_key() is less but still outweighs RCU overhead. I suspect that such frequent update is not a common occurrence, but Davem can confirm that.

The bottom line is that RCU overhead is tolerable where we know that updates are not going to be frequent. Also different RCU algorithms are likely to have different overheads. We will present analysis for these algorithms as we go along.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.