Skip to contentSkip to conversation

v2 RCU: the bloatwatch edition

PATCH New Paul E. McKenney 7 participants 15 messages Feb 3, 2009 – Apr 29, 2009 RCU

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 v2 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

	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

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/rcupdate.h |    2 
 include/linux/rcutiny.h  |   68 +++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  289 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 371 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 2aebc4c..62d3e58 100644
@@ -80,6 +80,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 +289 -0

289 lines not on this page · raw message

#1 lore raw

PATCH 1/1 v3 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

	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

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/rcupdate.h |    2 
 include/linux/rcutiny.h  |   68 +++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  288 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 370 insertions(+)
include/linux/rcupdate.h +2 -0
index 528343e..19966aa 100644
@@ -61,6 +61,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 +68 -0

68 lines not on this page · raw message

init/Kconfig +7 -0
index f068071..9404637 100644
@@ -271,6 +271,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 e4791b3..7a8c7c5 100644
@@ -80,6 +80,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 cae8a05..3a5bd43 100644
@@ -70,6 +70,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.
  *
@@ -94,6 +96,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 +288 -0

288 lines not on this page · raw message

#2 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 50 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

	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

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.

Quoted 5 lines

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.

Andrew, what do you think?

A worry is yet another RCU variant - we already have 3.

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

Ingo

#3 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 20 lines · Ingo Molnar
Quoted 8 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

Andrew, what do you think?

A worry is yet another RCU variant - we already have 3.

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

Quoted 4 lines

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

A similar argument could have been used for tiny-shmem when it was first integrated. As this is hiding behind CONFIG_EMBEDDED, most users are not going to run in to it, so the confusion of 1 more RCU variant is not likely to be a problem for those that aren't actively seeking it out.

So, personally I think it is a good idea, and I have no reservations about default enabling it for a number of more constrained SH platforms.

#4 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 31 lines · Paul Mundt
Quoted 20 lines · Ingo Molnar
Quoted 8 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

Andrew, what do you think?

A worry is yet another RCU variant - we already have 3.

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

Quoted 3 lines

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

A similar argument could have been used for tiny-shmem when it was first integrated. As this is hiding behind CONFIG_EMBEDDED, most users are not going to run in to it, so the confusion of 1 more RCU variant is not likely to be a problem for those that aren't actively seeking it out.

Quoted 3 lines

So, personally I think it is a good idea, and I have no reservations about default enabling it for a number of more constrained SH platforms.

but at least tiny-shmem is now nicely hidden in mm/shmem.c, in an unintrusive !CONFIG_SHMEM branch. There's no CONFIG_TINY_SHMEM option anymore - it's all done in the !CONFIG_SHMEM case.

Is tiny-RCU in the same category?

Ingo

#5 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 34 lines · Ingo Molnar
Quoted 31 lines · Paul Mundt
Quoted 20 lines · Ingo Molnar
Quoted 8 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

Andrew, what do you think?

A worry is yet another RCU variant - we already have 3.

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

Quoted 3 lines

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

A similar argument could have been used for tiny-shmem when it was first integrated. As this is hiding behind CONFIG_EMBEDDED, most users are not going to run in to it, so the confusion of 1 more RCU variant is not likely to be a problem for those that aren't actively seeking it out.

Quoted 8 lines
Quoted 3 lines

So, personally I think it is a good idea, and I have no reservations about default enabling it for a number of more constrained SH platforms.

but at least tiny-shmem is now nicely hidden in mm/shmem.c, in an unintrusive !CONFIG_SHMEM branch. There's no CONFIG_TINY_SHMEM option anymore - it's all done in the !CONFIG_SHMEM case.

Now it is, yes, but it was not originally, and it was still useful when it was split out. If we are going to tolerate multiple RCU implementations in the kernel, then I see no reason to not include tiny-RCU in the same category. Even in the case where some of the other RCU variants go away, tiny-RCU remains a viable option for simple platforms that are more concerned about memory than anything else, so it's always a valid alternative.

If in the future things are more consolidated and the config option goes away then great, but that hardly seems like a sane prerequisite for merging it. CONFIG_EMBEDDED handles this just fine. You don't need to enable it if you don't wish to, but it's certainly measurable enough to be useful for those of us that have no problems enabling it ;-)

#6 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 51 lines · Paul Mundt
Quoted 34 lines · Ingo Molnar
Quoted 31 lines · Paul Mundt
Quoted 20 lines · Ingo Molnar
Quoted 8 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

Andrew, what do you think?

A worry is yet another RCU variant - we already have 3.

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

Quoted 3 lines

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

A similar argument could have been used for tiny-shmem when it was first integrated. As this is hiding behind CONFIG_EMBEDDED, most users are not going to run in to it, so the confusion of 1 more RCU variant is not likely to be a problem for those that aren't actively seeking it out.

Quoted 8 lines
Quoted 3 lines

So, personally I think it is a good idea, and I have no reservations about default enabling it for a number of more constrained SH platforms.

but at least tiny-shmem is now nicely hidden in mm/shmem.c, in an unintrusive !CONFIG_SHMEM branch. There's no CONFIG_TINY_SHMEM option anymore - it's all done in the !CONFIG_SHMEM case.

Now it is, yes, but it was not originally, and it was still useful when it was split out. If we are going to tolerate multiple RCU implementations in the kernel, then I see no reason to not include tiny-RCU in the same category. Even in the case where some of the other RCU variants go away, tiny-RCU remains a viable option for simple platforms that are more concerned about memory than anything else, so it's always a valid alternative.

Quoted 7 lines

If in the future things are more consolidated and the config option goes away then great, but that hardly seems like a sane prerequisite for merging it. CONFIG_EMBEDDED handles this just fine. You don't need to enable it if you don't wish to, but it's certainly measurable enough to be useful for those of us that have no problems enabling it ;-)

From a kernel-size viewpoint:

788 kernel/rcuclassic.c
190 include/linux/rcuclassic.h
978 total

288 kernel/rcutiny.c
68 include/linux/rcutiny.h
356 total

Almost a 3x decrease in lines of code. So, Seems to me that dropping rcuclassic (as rcutree proves itself) and taking up rcutiny instead is a good step forward. ;-)

Thanx, Paul

#7 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

In reply to Ingo Molnar
Quoted 2 lines · On Fri, 3 Apr 2009 00:36:05 +0200 Ingo Molnar <[email protected]> wrote:

Andrew, what do you think?

I'm really struggling to see how the 900-odd bytes saved justifies creating (yet another) variant of core kernel machinery.

Quoted 1 line

A worry is yet another RCU variant - we already have 3.

That would make four?

I wonder if that was sane of us.

Quoted 10 lines

A trick we could use would be to put it into Documentation/rcu/, linked in via some clever Makefile magic and only usable if a ultra-embedded developer does a build with something like CONFIG_RCU_TINY=y. That way there's no real maintenance and testing overhead.

It _does_ have documentation value beyond the ~900 bytes: it's the simplest and smallest possible still-working UP RCU implementation so it would be easy to teach RCU concepts via that, gradually.

hm.

#8 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 4 lines · Andrew Morton
Quoted 1 line · On Fri, 3 Apr 2009 00:36:05 +0200 Ingo Molnar <[email protected]> wrote:
Quoted 8 lines
Quoted 1 line

Andrew, what do you think?

I'm really struggling to see how the 900-odd bytes saved justifies creating (yet another) variant of core kernel machinery.

Quoted 1 line

A worry is yet another RCU variant - we already have 3.

That would make four?

Three, once treercu is deemed stable enough to permit dropping Classic RCU.

Thanx, Paul

#9 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

In reply to Andrew Morton
Quoted 8 lines · Andrew Morton
Quoted 2 lines · On Fri, 3 Apr 2009 00:36:05 +0200 Ingo Molnar <[email protected]> wrote:

Andrew, what do you think?

I'm really struggling to see how the 900-odd bytes saved justifies creating (yet another) variant of core kernel machinery.

Also it's unclear if anything special cased !SMP is worth it for the future. After all multi core or SMT is becoming more and more common even in the embedded world.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#10 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 8 lines · Andi Kleen
Quoted 4 lines
Quoted 1 line

Andrew, what do you think?

I'm really struggling to see how the 900-odd bytes saved justifies creating (yet another) variant of core kernel machinery.

Also it's unclear if anything special cased !SMP is worth it for the future. After all multi core or SMT is becoming more and more common even in the embedded world.

At least for ARM, >99% of the dual core CPUs out there are non-SMP. (With one core typically running Linux and another core typically not running an OS at all: packet processing, DSP things, baseband stack, etc. That second CPU core often doesn't even have an MMU.) I don't think any SMP ARMs have been widely deployed yet.

Even if SMP ARM chips become widely available: the die area size of a chip alone pretty much tells you the cost of that chip, and in a world where every sub-mm^2 reduction in area matters a _lot_, I doubt ARM CPU manufacturers will start including second CPU cores in chips meant for things like cell phones, wireless access points and broadband routers (ARM CPUs tend to be highly application-specific) just because they can.

Acked-by on v1 1/1
#11 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

In reply to Paul E. McKenney
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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

On FRV, CLASSIC_RCU:

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

TREE_RCU:

3940 328 0 4268 10ac kernel/rcutree.o

    884      32      20     936     3a8 kernel/rcupdate.o

TINY_RCU:

   1152      32       0    1184     4a0 kernel/rcutiny.o
    836      32      20     888     378 kernel/rcupdate.o

It works on my FRV board.

Possibly TINY_RCU could be shrunk a bit more by a judicious bit of inlining of some of the very small functions.

#12 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 26 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 about 900 bytes compared to Classic RCU, and a couple kilobytes compared to Hierarchical RCU:

On FRV, CLASSIC_RCU:

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

TREE_RCU:

   3940     328       0    4268    10ac kernel/rcutree.o
    884      32      20     936     3a8 kernel/rcupdate.o

TINY_RCU:

   1152      32       0    1184     4a0 kernel/rcutiny.o
    836      32      20     888     378 kernel/rcupdate.o
Quoted 6 lines

It works on my FRV board.

Possibly TINY_RCU could be shrunk a bit more by a judicious bit of inlining of some of the very small functions.

Thank you for looking this over!

Your thought is that some of the functions could be moved to tinyrcu.h? Indeed, some of them would be smaller if inlined than even the call sequence. For example, rcu_needs_cpu() should remove code from the dynticks implementation given that it always returns zero.

Thanx, Paul

#13 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 4 lines · Paul E. McKenney

Your thought is that some of the functions could be moved to tinyrcu.h? Indeed, some of them would be smaller if inlined than even the call sequence. For example, rcu_needs_cpu() should remove code from the dynticks implementation given that it always returns zero.

tinyrcu.h is probably not a bad idea. Some of the functions are trivial, and the code to do a function call is bigger than the body of the function itself.

rcu_exit_nohz(), rcu_nmi_enter/exit(), rcu_batches_completed[_bh](), for example. Even call_rcu() and call_rcu_bh() might perhaps benefit from inlining.

David

#14 lore raw

Re: [PATCH] v3 RCU: the bloatwatch edition

Quoted 7 lines · David Howells
Quoted 4 lines · Paul E. McKenney

Your thought is that some of the functions could be moved to tinyrcu.h? Indeed, some of them would be smaller if inlined than even the call sequence. For example, rcu_needs_cpu() should remove code from the dynticks implementation given that it always returns zero.

Quoted 6 lines

tinyrcu.h is probably not a bad idea. Some of the functions are trivial, and the code to do a function call is bigger than the body of the function itself.

rcu_exit_nohz(), rcu_nmi_enter/exit(), rcu_batches_completed[_bh](), for example. Even call_rcu() and call_rcu_bh() might perhaps benefit from inlining.

Well, here is something that should knock off an additional 100 bytes or so. Untested, probably does not compile. I skipped putting call_rcu() in tinyrcu.h because it is called so many times that the extra argument would probably bite harder than the current code + export.

---

 include/linux/hardirq.h  |   19 ++--
 include/linux/rcupdate.h |    2 
 include/linux/rcutiny.h  |  112 ++++++++++++++++++++++++
 init/Kconfig             |    7 +
 kernel/Makefile          |    1 
 kernel/rcupdate.c        |    4 
 kernel/rcutiny.c         |  214 +++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 352 insertions(+), 7 deletions(-)
include/linux/hardirq.h +12 -7
diff -urpNa -X dontdiff linux-2.6.30-rc2-rcu/include/linux/hardirq.h linux-2.6.29-tinyrcu/include/linux/hardirq.h
@@ -119,17 +119,22 @@ static inline void account_system_vtime(
 }
 #endif
 
-#if defined(CONFIG_NO_HZ) && !defined(CONFIG_CLASSIC_RCU)
+#if !defined(CONFIG_NO_HZ) || defined(CONFIG_CLASSIC_RCU)
+# 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)
+#elif defined(CONFIG_RCU_TINY)
+# define rcu_irq_enter		rcu_exit_nohz
+# define rcu_irq_exit		rcu_enter_nohz
+# define rcu_nmi_enter()	do { } while (0)
+# define rcu_nmi_exit()		do { } while (0)
+#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
diff -urpNa -X dontdiff linux-2.6.30-rc2-rcu/include/linux/rcupdate.h linux-2.6.29-tinyrcu/include/linux/rcupdate.h
@@ -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 +112 -0

112 lines not on this page · raw message

init/Kconfig +7 -0
diff -urpNa -X dontdiff linux-2.6.30-rc2-rcu/init/Kconfig linux-2.6.29-tinyrcu/init/Kconfig
@@ -271,6 +271,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
diff -urpNa -X dontdiff linux-2.6.30-rc2-rcu/kernel/Makefile linux-2.6.29-tinyrcu/kernel/Makefile
@@ -80,6 +80,7 @@ obj-$(CONFIG_RCU_TORTURE_TEST) += rcutor
 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
diff -urpNa -X dontdiff linux-2.6.30-rc2-rcu/kernel/rcupdate.c linux-2.6.29-tinyrcu/kernel/rcupdate.c
@@ -74,6 +74,8 @@ void wakeme_after_rcu(struct rcu_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 +214 -0

214 lines not on this page · raw message