Skip to contentSkip to conversation

v5 RCU: the bloatwatch edition

PATCH In review Paul E. McKenney 5 participants 10 messages Jun 23, 2009 RCU

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 v5 RCU: the bloatwatch edition

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

	CONFIG_CLASSIC_RCU:

	   text	   data	    bss	    dec	    filename
	    544	     32	     16	    592	    kernel/rcupdate.o
	   1495	    200	      0	   1695	    kernel/rcuclassic.o
				   2287 Total (vs 2112 for v4)

	CONFIG_TREE_RCU:

	   text	   data	    bss	    dec	    filename
	    544	     32	     16	    592	    kernel/rcupdate.o
	   3005	    448	      0	   3453	    kernel/rcutree.o
	   			   4045 Total (vs 3622 for v4)

	CONFIG_TINY_RCU:

	   text	   data	    bss	    dec	    filename
	    506	     32	     16	    554	    kernel/rcupdate.o
	    442	     28	      0	    470	    kernel/rcutiny.o
	    			   1024 Total (vs 1041 for v4)

The above is for x86. Your mileage may vary on other platforms.

Changes from v4 (http://lkml.org/lkml/2009/5/2/91) include:

o Squeeze the size down a bit further by removing the

	->completed field from struct rcu_ctrlblk.

o This permits synchronize_rcu() to become the empty function.
Previous concerns about rcutorture were unfounded, as rcutorture correctly handles a constant value from rcu_batches_completed() and rcu_batches_completed_bh().

Changes from v3 (http://lkml.org/lkml/2009/3/29/221) include:

o Changed rcu_batches_completed(), rcu_batches_completed_bh()
rcu_enter_nohz(), rcu_exit_nohz(), rcu_nmi_enter(), and rcu_nmi_exit(), to be static inlines, as suggested by David Howells. Doing this saves about 100 bytes from rcutiny.o. (The numbers between v3 and this v4 of the patch are not directly comparable, since they are against different versions of Linux.)

Changes from v2 (http://lkml.org/lkml/2009/2/3/333) include:

o Fix whitespace issues.

o Change short-circuit "||" operator to instead be "+" in order to

	fix performance bug noted by "kraai" on LWN.

		(http://lwn.net/Articles/324348/)

Changes from v1 (http://lkml.org/lkml/2009/1/13/440) include:

o This version depends on EMBEDDED as well as !SMP, as suggested
by Ingo.

o Updated rcu_needs_cpu() to unconditionally return zero,
permitting the CPU to enter dynticks-idle mode at any time. This works because callbacks can be invoked upon entry to dynticks-idle mode.

o I am now OK with this being included, based on a poll at the
Kernel Miniconf at linux.conf.au, where about ten people said that they cared about saving 900 bytes on single-CPU systems.

o Applies to both mainline and tip/core/rcu.

---

 include/linux/hardirq.h  |   52 +++++++++-
 include/linux/rcupdate.h |    2 
 include/linux/rcutiny.h  |  102 +++++++++++++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  227 +++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 388 insertions(+), 7 deletions(-)
include/linux/hardirq.h +45 -7
index 4525747..b0d1e83 100644
@@ -130,17 +130,55 @@ static inline void account_system_vtime(struct task_struct *tsk)
 }
 #endif
 
-#if defined(CONFIG_NO_HZ) && !defined(CONFIG_CLASSIC_RCU)
+#if !defined(CONFIG_NO_HZ) || defined(CONFIG_CLASSIC_RCU)
+
+static inline void rcu_irq_enter(void)
+{
+}
+
+static inline void rcu_irq_exit(void)
+{
+}
+
+static inline void rcu_nmi_enter(void)
+{
+}
+
+static inline void rcu_nmi_exit(void)
+{
+}
+
+#elif defined(CONFIG_TINY_RCU)
+
+extern void rcu_enter_nohz(void);
+extern void rcu_exit_nohz(void);
+
+static inline void rcu_irq_enter(void)
+{
+	rcu_exit_nohz();
+}
+
+static inline void rcu_irq_exit(void)
+{
+	rcu_enter_nohz();
+}
+
+static inline void rcu_nmi_enter(void)
+{
+}
+
+static inline void rcu_nmi_exit(void)
+{
+}
+
+#else
+
 extern void rcu_irq_enter(void);
 extern void rcu_irq_exit(void);
 extern void rcu_nmi_enter(void);
 extern void rcu_nmi_exit(void);
-#else
-# define rcu_irq_enter() do { } while (0)
-# define rcu_irq_exit() do { } while (0)
-# define rcu_nmi_enter() do { } while (0)
-# define rcu_nmi_exit() do { } while (0)
-#endif /* #if defined(CONFIG_NO_HZ) && !defined(CONFIG_CLASSIC_RCU) */
+
+#endif
 
 /*
  * It is safe to do non-atomic ops on ->hardirq_context,
include/linux/rcupdate.h +2 -0
index 15fbb3c..bd91ffa 100644
@@ -60,6 +60,8 @@ extern int rcu_scheduler_active;
 #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 +102 -0

102 lines not on this page · raw message

init/Kconfig +7 -0
index 7be4d38..f088d51 100644
@@ -337,6 +337,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 4242366..c76518c 100644
@@ -81,6 +81,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 a967c9f..a866940 100644
@@ -74,6 +74,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.
  *
@@ -98,6 +100,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 +227 -0

227 lines not on this page · raw message

Acked-by on v1 1/1
#1 lore raw
Quoted 7 lines · Paul E. McKenney

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

On FRV:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   2616     184       0    2800     af0 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   4068     384       0    4452    1164 kernel/rcutree.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    836      32      20     888     378 kernel/rcupdate.o
	    816      24       0     840     348 kernel/rcutiny.o

On MN10300:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   1777     184       0    1961     7a9 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   2733     384       0    3117     c2d kernel/rcutree.o

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     hex filename
	    961      28      48    1037     40d kernel/rcupdate.o
	   3314     128       8    3450     d7a kernel/rcupreempt.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    865      28      48     941     3ad kernel/rcupdate.o
	    500      24       0     524     20c kernel/rcutiny.o
Quoted 1 line
#2 lore raw
Quoted 56 lines · David Howells
Quoted 7 lines · Paul E. McKenney

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

On FRV:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   2616     184       0    2800     af0 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   4068     384       0    4452    1164 kernel/rcutree.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    836      32      20     888     378 kernel/rcupdate.o
	    816      24       0     840     348 kernel/rcutiny.o

On MN10300:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   1777     184       0    1961     7a9 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   2733     384       0    3117     c2d kernel/rcutree.o

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     hex filename
	    961      28      48    1037     40d kernel/rcupdate.o
	   3314     128       8    3450     d7a kernel/rcupreempt.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    865      28      48     941     3ad kernel/rcupdate.o
	    500      24       0     524     20c kernel/rcutiny.o
Quoted 3 lines
Quoted 1 line

Ok, that's more convincing than 900 bytes on x86.

Paul, i guess this is .32 material anyway, right?

Since there's plenty of time, could we perhaps also do the classic-rcu removal and integrate-rcupreempt-into-tree-rcu steps, to reduce the (significant) config complexity perhaps?

Ingo

#3 lore raw
Quoted 59 lines · Ingo Molnar
Quoted 56 lines · David Howells
Quoted 7 lines · Paul E. McKenney

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

On FRV:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   2616     184       0    2800     af0 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   4068     384       0    4452    1164 kernel/rcutree.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    836      32      20     888     378 kernel/rcupdate.o
	    816      24       0     840     348 kernel/rcutiny.o

On MN10300:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   1777     184       0    1961     7a9 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   2733     384       0    3117     c2d kernel/rcutree.o

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     hex filename
	    961      28      48    1037     40d kernel/rcupdate.o
	   3314     128       8    3450     d7a kernel/rcupreempt.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    865      28      48     941     3ad kernel/rcupdate.o
	    500      24       0     524     20c kernel/rcutiny.o
Quoted 5 lines
Quoted 3 lines
Quoted 1 line

Ok, that's more convincing than 900 bytes on x86.

It used to be 900 bytes. In 2.6.30, it is 1263 bytes. ;-)

That said, I agree that FRV and MN10300 savings are more impressive.

Quoted 1 line

Paul, i guess this is .32 material anyway, right?

I am personally OK with it being .32, as long as David Howells, Lennert Buytenhek, and Paul Mundt are OK with that schedule.

Quoted 3 lines

Since there's plenty of time, could we perhaps also do the classic-rcu removal and integrate-rcupreempt-into-tree-rcu steps, to reduce the (significant) config complexity perhaps?

Classic-RCU removal most certainly. I am hoping to get the integrate-rcupreempt-into-tree-rcu piece done in .32 timeframe, but there is a chance that it may be a bit later.

Thanx, Paul

#4 lore raw
Quoted 6 lines · Paul E. McKenney
Quoted 1 line · Ingo Molnar

Paul, i guess this is .32 material anyway, right?

I am personally OK with it being .32, as long as David Howells, Lennert Buytenhek, and Paul Mundt are OK with that schedule.

It's hard to see how this is going to cause any regressions, so I don't see any problem with this going in to 2.6.31. OTOH, it's not too pressing, so 2.6.32 is ok for me too.

#5 lore raw
In reply to Paul E. McKenney
Quoted 2 lines · Paul E. McKenney

I am personally OK with it being .32, as long as David Howells, Lennert Buytenhek, and Paul Mundt are OK with that schedule.

Whilst it might be nice to get it in .31, I don't mind it being lodged in linux-next till .32.

David

#6 lore raw
In reply to Paul E. McKenney
Quoted 60 lines · Paul E. McKenney
Quoted 54 lines
Quoted 54 lines
Quoted 7 lines

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

On FRV:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   2616     184       0    2800     af0 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   4068     384       0    4452    1164 kernel/rcutree.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    836      32      20     888     378 kernel/rcupdate.o
	    816      24       0     840     348 kernel/rcutiny.o

On MN10300:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   1777     184       0    1961     7a9 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   2733     384       0    3117     c2d kernel/rcutree.o

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     hex filename
	    961      28      48    1037     40d kernel/rcupdate.o
	   3314     128       8    3450     d7a kernel/rcupreempt.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    865      28      48     941     3ad kernel/rcupdate.o
	    500      24       0     524     20c kernel/rcutiny.o
Quoted 5 lines
Quoted 3 lines
Quoted 1 line

Ok, that's more convincing than 900 bytes on x86.

Quoted 8 lines

It used to be 900 bytes. In 2.6.30, it is 1263 bytes. ;-)

That said, I agree that FRV and MN10300 savings are more impressive.

Quoted 1 line

Paul, i guess this is .32 material anyway, right?

I am personally OK with it being .32, as long as David Howells, Lennert Buytenhek, and Paul Mundt are OK with that schedule.

I like the patch, as nearly all ARM systems in the field right now are non-SMP. Russell King (CCd) is the ARM maintainer, so he should comment on the proposed timeline.

#7 lore raw
Quoted 66 lines · Lennert Buytenhek
Quoted 64 lines · Paul E. McKenney
Quoted 54 lines
Quoted 54 lines
Quoted 7 lines

This patch is a version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

On FRV:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   2616     184       0    2800     af0 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    884      32      20     936     3a8 kernel/rcupdate.o
	   4068     384       0    4452    1164 kernel/rcutree.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    836      32      20     888     378 kernel/rcupdate.o
	    816      24       0     840     348 kernel/rcutiny.o

On MN10300:

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   1777     184       0    1961     7a9 kernel/rcuclassic.o

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     hex filename
	    900      28      48     976     3d0 kernel/rcupdate.o
	   2733     384       0    3117     c2d kernel/rcutree.o

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     hex filename
	    961      28      48    1037     40d kernel/rcupdate.o
	   3314     128       8    3450     d7a kernel/rcupreempt.o

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     hex filename
	    865      28      48     941     3ad kernel/rcupdate.o
	    500      24       0     524     20c kernel/rcutiny.o
Quoted 5 lines
Quoted 3 lines
Quoted 1 line

Ok, that's more convincing than 900 bytes on x86.

It used to be 900 bytes. In 2.6.30, it is 1263 bytes. ;-)

That said, I agree that FRV and MN10300 savings are more impressive.

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

Paul, i guess this is .32 material anyway, right?

I am personally OK with it being .32, as long as David Howells, Lennert Buytenhek, and Paul Mundt are OK with that schedule.

I like the patch, as nearly all ARM systems in the field right now are non-SMP. Russell King (CCd) is the ARM maintainer, so he should comment on the proposed timeline.

OK, I will submit a patch against -tip. If Russell needs Bloatwatch RCU more quickly, we still have my earlier v5 patch against 2.6.30.

Thanx, Paul

#8 lore raw

PATCH 1/1 v5 RCU: the bloatwatch edition

In reply to Paul E. McKenney

This patch is a -tip version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

	CONFIG_CLASSIC_RCU:

	   text	   data	    bss	    dec	    filename
	    544	     32	     16	    592	    kernel/rcupdate.o
	   1495	    200	      0	   1695	    kernel/rcuclassic.o
				   2287 Total (vs 2112 for v4)

	CONFIG_TREE_RCU:

	   text	   data	    bss	    dec	    filename
	    544	     32	     16	    592	    kernel/rcupdate.o
	   3005	    448	      0	   3453	    kernel/rcutree.o
	   			   4045 Total (vs 3622 for v4)

	CONFIG_TINY_RCU:

	   text	   data	    bss	    dec	    filename
	    506	     32	     16	    554	    kernel/rcupdate.o
	    442	     28	      0	    470	    kernel/rcutiny.o
	    			   1024 Total (vs 1041 for v4)
				   	      1263 savings vs Classic

The above is for x86. Your mileage may vary on other platforms.

On FRV (courtesy of David Howells):

CONFIG_CLASSIC_RCU=y

text data bss dec filename
884 32 20 936 kernel/rcupdate.o
2616 184 0 2800 kernel/rcuclassic.o
3736 Total

CONFIG_TREE_RCU=y

text data bss dec filename
884 32 20 936 kernel/rcupdate.o
4068 384 0 4452 kernel/rcutree.o
5388 Total

CONFIG_TINY_RCU=y

text data bss dec filename
836 32 20 888 kernel/rcupdate.o
816 24 0 840 kernel/rcutiny.o
1728 Total, 2008 bytes saved vs Classic

On MN10300 (also courtesy of David Howells):

	CONFIG_CLASSIC_RCU=y

	   text    data     bss     dec     filename
	    900      28      48     976     kernel/rcupdate.o
	   1777     184       0    1961     kernel/rcuclassic.o
				   2937 Total

	CONFIG_TREE_RCU=y

	   text    data     bss     dec     filename
	    900      28      48     976     kernel/rcupdate.o
	   2733     384       0    3117     kernel/rcutree.o
	   			   4093 Total

	CONFIG_PREEMPT_RCU=y

	   text    data     bss     dec     filename
	    961      28      48    1037     kernel/rcupdate.o
	   3314     128       8    3450     kernel/rcupreempt.o
	   			   4487 Total

	CONFIG_TINY_RCU=y

	   text    data     bss     dec     filename
	    865      28      48     941     kernel/rcupdate.o
	    500      24       0     524     kernel/rcutiny.o
	    			   1465 Total, 1472 savings vs Classic

Ingo, please include in -tip slating for 2.6.32.

Changes from v4 (http://lkml.org/lkml/2009/5/2/91) include:

o Squeeze the size down a bit further by removing the

	->completed field from struct rcu_ctrlblk.

o This permits synchronize_rcu() to become the empty function.
Previous concerns about rcutorture were unfounded, as rcutorture correctly handles a constant value from rcu_batches_completed() and rcu_batches_completed_bh().

Changes from v3 (http://lkml.org/lkml/2009/3/29/221) include:

o Changed rcu_batches_completed(), rcu_batches_completed_bh()
rcu_enter_nohz(), rcu_exit_nohz(), rcu_nmi_enter(), and rcu_nmi_exit(), to be static inlines, as suggested by David Howells. Doing this saves about 100 bytes from rcutiny.o. (The numbers between v3 and this v4 of the patch are not directly comparable, since they are against different versions of Linux.)

Changes from v2 (http://lkml.org/lkml/2009/2/3/333) include:

o Fix whitespace issues.

o Change short-circuit "||" operator to instead be "+" in order to

	fix performance bug noted by "kraai" on LWN.

		(http://lwn.net/Articles/324348/)

Changes from v1 (http://lkml.org/lkml/2009/1/13/440) include:

o This version depends on EMBEDDED as well as !SMP, as suggested
by Ingo.

o Updated rcu_needs_cpu() to unconditionally return zero,
permitting the CPU to enter dynticks-idle mode at any time. This works because callbacks can be invoked upon entry to dynticks-idle mode.

o I am now OK with this being included, based on a poll at the
Kernel Miniconf at linux.conf.au, where about ten people said that they cared about saving 900 bytes on single-CPU systems.

o Applies to both mainline and tip/core/rcu.

[ Impact: reduce kernel size for UP builds ]

---

 include/linux/hardirq.h  |   52 +++++++++-
 include/linux/rcupdate.h |    2 
 include/linux/rcutiny.h  |  102 +++++++++++++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  227 +++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 388 insertions(+), 7 deletions(-)
include/linux/hardirq.h +45 -7
index 4525747..b0d1e83 100644
@@ -130,17 +130,55 @@ static inline void account_system_vtime(struct task_struct *tsk)
 }
 #endif
 
-#if defined(CONFIG_NO_HZ) && !defined(CONFIG_CLASSIC_RCU)
+#if !defined(CONFIG_NO_HZ) || defined(CONFIG_CLASSIC_RCU)
+
+static inline void rcu_irq_enter(void)
+{
+}
+
+static inline void rcu_irq_exit(void)
+{
+}
+
+static inline void rcu_nmi_enter(void)
+{
+}
+
+static inline void rcu_nmi_exit(void)
+{
+}
+
+#elif defined(CONFIG_TINY_RCU)
+
+extern void rcu_enter_nohz(void);
+extern void rcu_exit_nohz(void);
+
+static inline void rcu_irq_enter(void)
+{
+	rcu_exit_nohz();
+}
+
+static inline void rcu_irq_exit(void)
+{
+	rcu_enter_nohz();
+}
+
+static inline void rcu_nmi_enter(void)
+{
+}
+
+static inline void rcu_nmi_exit(void)
+{
+}
+
+#else
+
 extern void rcu_irq_enter(void);
 extern void rcu_irq_exit(void);
 extern void rcu_nmi_enter(void);
 extern void rcu_nmi_exit(void);
-#else
-# define rcu_irq_enter() do { } while (0)
-# define rcu_irq_exit() do { } while (0)
-# define rcu_nmi_enter() do { } while (0)
-# define rcu_nmi_exit() do { } while (0)
-#endif /* #if defined(CONFIG_NO_HZ) && !defined(CONFIG_CLASSIC_RCU) */
+
+#endif
 
 /*
  * It is safe to do non-atomic ops on ->hardirq_context,
include/linux/rcupdate.h +2 -0
index 15fbb3c..bd91ffa 100644
@@ -60,6 +60,8 @@ extern int rcu_scheduler_active;
 #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 +102 -0

102 lines not on this page · raw message

init/Kconfig +7 -0
index 7be4d38..f088d51 100644
@@ -337,6 +337,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 4242366..c76518c 100644
@@ -81,6 +81,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 a967c9f..a866940 100644
@@ -74,6 +74,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.
  *
@@ -98,6 +100,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 +227 -0

227 lines not on this page · raw message

Acked-by on v1 1/1
#9 lore raw
Quoted 8 lines · Paul E. McKenney

This patch is a -tip version of RCU designed for (!SMP && EMBEDDED) 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 rcutorture testing in each of the four relevant configurations (combinations of NO_HZ and PREEMPT) on x86. This saves 1263 bytes compared to Classic RCU, and more than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):

[snip]

Quoted 2 lines