rcu: Implement RCU
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 26 Apr 2018 19:57:09 +0000 (15:57 -0400)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 30 Apr 2018 18:41:01 +0000 (14:41 -0400)
commit54a1d3c18f8a556a2d4caf7f4c74b4682efd15a7
tree538ea8e59b4298f94e8a35e31d516fb8b7d91586
parentf84f414f82bb2f680c1427eb2d445cdc8a2c3931
rcu: Implement RCU

Our RCU is similar to Linux's rcu_sched - we don't do the same things they
do with CONFIG_PREEMPT.

A lot of the changes to the Linux headers were me removing things I'm
fairly sure we won't need, so don't worry about that.  The bulk of this
commit is rcu.c, which implements call_rcu() and rcu_barrier() - which is
the heart of any RCU implementation.

Though note the locations in the rest of the kernel where we call
rcu_report_qs() - those are the locations where we know we aren't in a
read-side critical section.

The big difference between our RCU and Linux's implementation is that we do
not interfere with the CG cores.  We do not use softirq processing or timer
ticks for either callbacks or reporting quiescent states.

call_rcu() callbacks from CG cores do not run on the cores where they were
queued up.  There is a penalty for cache misses for this, but it prevents
us from interfering with the app.  Otherwise, once a grace period elapses,
we'd either have to wait for the user to enter the kernel or we'd have to
force them to.  You could imagine a middle ground where we let a callback
sit for a while or try to work-steal it.

We can check from a management core (core 0) to see if a CG core is in
userspace or idle.  This is similar to what Linux does with dynticks, I
think.  We also expedite the grace periods, though we can change that.

We use Linux's tree structure for tracking quiescent states, but all cores
use the global gpnum to find out which gpnum we're dealing with.  If that
turns out to be a scalability problem, then we can deal with it later.  I
didn't want to deal with certain cores having old gps.

As far as the timing parameters, I went with 25 msec since it wasn't a
multiple of the kernel scheduler tick.  If it is having an effect on FTQ
numbers, being at another frequency will make it stand out.

This hasn't been tested heavily; there are mostly likely bugs and almost
surely memory barrier problems that might require another architectures.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
14 files changed:
kern/include/linux_compat.h
kern/include/rbtree.h
kern/include/rcu.h
kern/include/rcu_helper.h
kern/include/rculist.h
kern/include/rcupdate.h
kern/src/Kbuild
kern/src/init.c
kern/src/process.c
kern/src/rcu.c [new file with mode: 0644]
kern/src/rcu_tree_helper.c
kern/src/smp.c
kern/src/syscall.c
kern/src/trap.c