Skip to contentSkip to conversation

RCU: the bloatwatch edition

PATCH In review Paul E. McKenney 2 participants 5 messages Jan 13, 2009 – Jan 14, 2009 RCU

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 RCU: the bloatwatch edition

Just FYI, not for inclusion.

This patch is a version of RCU designed for !CONFIG_SMP provided as a proof of concept of a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes moderate rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86.

---

 include/linux/rcupdate.h |    2 
 include/linux/rcutiny.h  |   68 +++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  290 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 372 insertions(+)
include/linux/rcupdate.h +2 -0
index 921340a..06e3909 100644
@@ -58,6 +58,8 @@ struct rcu_head {
 #include <linux/rcutree.h>
 #elif defined(CONFIG_PREEMPT_RCU)
 #include <linux/rcupreempt.h>
+#elif CONFIG_TINY_RCU
+#include <linux/rcutiny.h>
 #else
 #error "Unknown RCU implementation specified to kernel configuration"
 #endif /* #else #if defined(CONFIG_CLASSIC_RCU) */
include/linux/rcutiny.h new file +68 -0

68 lines not on this page · raw message

init/Kconfig +7 -0
index a724a14..bdcee3b 100644
@@ -1004,6 +1004,13 @@ config PREEMPT_RCU
 	  now-naive assumptions about each RCU read-side critical section
 	  remaining on a given CPU through its execution.
 
+config TINY_RCU
+	bool "Tiny-Memory RCU"
+	depends on !SMP
+	help
+	  This option greatly reduces the memory footprint of RCU,
+	  but is usable only on UP systems.
+
 endchoice
 
 config RCU_TRACE
kernel/Makefile +1 -0
index 2921d90..8c1390b 100644
@@ -76,6 +76,7 @@ obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
 obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o
 obj-$(CONFIG_TREE_RCU) += rcutree.o
 obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o
+obj-$(CONFIG_TINY_RCU) += rcutiny.o
 obj-$(CONFIG_TREE_RCU_TRACE) += rcutree_trace.o
 obj-$(CONFIG_PREEMPT_RCU_TRACE) += rcupreempt_trace.o
 obj-$(CONFIG_RELAY) += relay.o
kernel/rcupdate.c +4 -0
index d92a76a..4bb7b0a 100644
@@ -68,6 +68,8 @@ void wakeme_after_rcu(struct rcu_head  *head)
 	complete(&rcu->completion);
 }
 
+#ifndef CONFIG_TINY_RCU
+
 /**
  * synchronize_rcu - wait until a grace period has elapsed.
  *
@@ -88,6 +90,8 @@ void synchronize_rcu(void)
 }
 EXPORT_SYMBOL_GPL(synchronize_rcu);
 
+#endif /* #ifndef CONFIG_TINY_RCU */
+
 static void rcu_barrier_callback(struct rcu_head *notused)
 {
 	if (atomic_dec_and_test(&rcu_barrier_cpu_count))
kernel/rcutiny.c new file +290 -0

290 lines not on this page · raw message

#1 lore raw
Quoted 10 lines · Paul E. McKenney

Just FYI, not for inclusion.

This patch is a version of RCU designed for !CONFIG_SMP provided as a proof of concept of a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes moderate rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86.

maybe it could be included - dependent on PREEMPT, just like we have SLOB?

it would also be rather educative IMO: if someone wants to understand the core concepts of RCU, start with kernel/rcutiny.c. We are getting complaints from academic institutions that the Linux kernel is getting too complex to teach in courses - and that's a pity.

Ingo

#2 lore raw
Quoted 12 lines · Ingo Molnar
Quoted 9 lines · Paul E. McKenney

Just FYI, not for inclusion.

This patch is a version of RCU designed for !CONFIG_SMP provided as a proof of concept of a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes moderate rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86.

Quoted 3 lines
Quoted 1 line

maybe it could be included - dependent on PREEMPT, just like we have SLOB?

I suppose that the fact that it already depends on !SMP should keep it hidden from most people, and it does work just fine for !PREEMPT. My concern is rather that if no one is using it, the code will bitrot rather quickly. None of us needs a broken RCU implementation in mainline, least of all me. ;-)

Quoted 4 lines

it would also be rather educative IMO: if someone wants to understand the core concepts of RCU, start with kernel/rcutiny.c. We are getting complaints from academic institutions that the Linux kernel is getting too complex to teach in courses - and that's a pity.

Yeah, I have had to refer a number of institutions to various LWN articles. I think that it is safe to say that LWN is not on every university's normal reading list. ;-) One (surprisingly prominent) institution that -does- read LWN unfortunately chose "The design of preemptible read-copy-update" to introduce themselves to RCU
(http://lwn.net/Articles/253651/), and, needless to say, found it tough going. I offered my sympathies and pointed them at the "What is RCU?" LWN series.

So it might well be good to have simplified implementations for academic study and perhaps also for deep embedded use. Sort of like the approach for designing video games -- easy first level, second level is a bit harder, and so on.

Thanx, Paul

#3 lore raw
In reply to Ingo Molnar
Quoted 12 lines · Ingo Molnar
Quoted 9 lines · Paul E. McKenney

Just FYI, not for inclusion.

This patch is a version of RCU designed for !CONFIG_SMP provided as a proof of concept of a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes moderate rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86.

Quoted 3 lines
Quoted 1 line

maybe it could be included - dependent on PREEMPT, just like we have SLOB?

s/PREEMPT/EMBEDDED

Ingo

#4 lore raw
Quoted 15 lines · Ingo Molnar
Quoted 12 lines · Ingo Molnar
Quoted 9 lines · Paul E. McKenney

Just FYI, not for inclusion.

This patch is a version of RCU designed for !CONFIG_SMP provided as a proof of concept of a small-footprint RCU implementation. In particular, the implementation of synchronize_rcu() is extremely lightweight and high performance. It passes moderate rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86.

Quoted 5 lines
Quoted 3 lines
Quoted 1 line

maybe it could be included - dependent on PREEMPT, just like we have SLOB?

s/PREEMPT/EMBEDDED

Ah! That works better, as I suspect that people do test with EMBEDDED, which addresses my bitrot objection. I don't immediately see how to make the default for the "RCU implementation" choice depend on what other settings there are, but I would guess that the embedded guys would grep the Kconfig files for settings that depend on EMBEDDED, which would lead them to TINY_RCU.

Anyway, here is the patch updated as you suggest. Binary sizes are as follows, all collected with !SMP and EMBEDDED, which interestingly enough shrinks rcutree significantly but has little effect on rcuclassic and rcutiny:

	CONFIG_CLASSIC_RCU:

	   text	   data	    bss	    dec	    hex	filename
	    363	     12	     24	    399	    18f	kernel/rcupdate.o
	   1237	     64	    124	   1425	    591	kernel/rcuclassic.o
				   1824 Total

	CONFIG_TREE_RCU:

	   text	   data	    bss	    dec	    hex	filename
	    363	     12	     24	    399	    18f	kernel/rcupdate.o
	   2344	    240	    184	   2768	    ad0	kernel/rcutree.o
				   3167 Total

	CONFIG_TINY_RCU:

	   text	   data	    bss	    dec	    hex	filename
	    294	     12	     24	    330	    14a	kernel/rcupdate.o
	    563	     36	      0	    599	    257	kernel/rcutiny.o
				    929 Total

So rcutiny saves about 900 bytes compared to rcuclassic.

---

 include/linux/rcupdate.h |    2 
 include/linux/rcutiny.h  |   68 +++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  290 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 372 insertions(+)
include/linux/rcupdate.h +2 -0
index 921340a..06e3909 100644
@@ -58,6 +58,8 @@ struct rcu_head {
 #include <linux/rcutree.h>
 #elif defined(CONFIG_PREEMPT_RCU)
 #include <linux/rcupreempt.h>
+#elif CONFIG_TINY_RCU
+#include <linux/rcutiny.h>
 #else
 #error "Unknown RCU implementation specified to kernel configuration"
 #endif /* #else #if defined(CONFIG_CLASSIC_RCU) */
include/linux/rcutiny.h new file +68 -0

68 lines not on this page · raw message

init/Kconfig +7 -0
index a724a14..5188f27 100644
@@ -1004,6 +1004,13 @@ config PREEMPT_RCU
 	  now-naive assumptions about each RCU read-side critical section
 	  remaining on a given CPU through its execution.
 
+config TINY_RCU
+	bool "Tiny-Memory RCU"
+	depends on !SMP && EMBEDDED
+	help
+	  This option greatly reduces the memory footprint of RCU,
+	  but is usable only on UP systems.
+
 endchoice
 
 config RCU_TRACE
kernel/Makefile +1 -0
index 2921d90..8c1390b 100644
@@ -76,6 +76,7 @@ obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
 obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o
 obj-$(CONFIG_TREE_RCU) += rcutree.o
 obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o
+obj-$(CONFIG_TINY_RCU) += rcutiny.o
 obj-$(CONFIG_TREE_RCU_TRACE) += rcutree_trace.o
 obj-$(CONFIG_PREEMPT_RCU_TRACE) += rcupreempt_trace.o
 obj-$(CONFIG_RELAY) += relay.o
kernel/rcupdate.c +4 -0
index d92a76a..4bb7b0a 100644
@@ -68,6 +68,8 @@ void wakeme_after_rcu(struct rcu_head  *head)
 	complete(&rcu->completion);
 }
 
+#ifndef CONFIG_TINY_RCU
+
 /**
  * synchronize_rcu - wait until a grace period has elapsed.
  *
@@ -88,6 +90,8 @@ void synchronize_rcu(void)
 }
 EXPORT_SYMBOL_GPL(synchronize_rcu);
 
+#endif /* #ifndef CONFIG_TINY_RCU */
+
 static void rcu_barrier_callback(struct rcu_head *notused)
 {
 	if (atomic_dec_and_test(&rcu_barrier_cpu_count))
kernel/rcutiny.c new file +290 -0

290 lines not on this page · raw message