lkml.org 
[lkml]   [2009]   [Oct]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH RFC tip/core/rcu 1/3] rcu: The Bloatwatch Edition, v7


Paul E. McKenney wrote:
> This patch is a version of RCU designed for !SMP provided for 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 1K bytes
> compared to old Classic RCU (which is no longer in mainline), and more
> than three kilobytes compared to Hierarchical RCU (updated to 2.6.30):
>
> CONFIG_TREE_RCU:
>
> text data bss dec filename
> 663 32 20 715 kernel/rcupdate.o
> 3278 528 44 3850 kernel/rcutree.o
> 4565 Total (vs 4045 for v4)
>
> CONFIG_TREE_PREEMPT_RCU:
>
> text data bss dec filename
> 743 32 20 795 kernel/rcupdate.o
> 4548 752 60 5360 kernel/rcutree.o
> 6155 Total (N/A for v4)
>
> CONFIG_TINY_RCU:
>
> text data bss dec filename
> 96 4 0 100 kernel/rcupdate.o
> 720 28 0 748 kernel/rcutiny.o
> 848 Total (vs 1140 for v6)
>
> The above is for x86. Your mileage may vary on other platforms.
> Further compression is possible, but is being procrastinated.
>
> Changes from v6 (http://lkml.org/lkml/2009/9/23/293).
>
> o Forward ported to put it into the 2.6.33 stream.
>
> o Added lockdep support.
>
> o Make lightweight rcu_barrier.
>
> Changes from v5 (http://lkml.org/lkml/2009/6/23/12).
>
> o Ported to latest pre-2.6.32 merge window kernel.
>
> - Renamed rcu_qsctr_inc() to rcu_sched_qs().
> - Renamed rcu_bh_qsctr_inc() to rcu_bh_qs().
> - Provided trivial rcu_cpu_notify().
> - Provided trivial exit_rcu().
> - Provided trivial rcu_needs_cpu().
> - Fixed up the rcu_*_enter/exit() functions in linux/hardirq.h.
>
> o Removed the dependence on EMBEDDED, with a view to making
> TINY_RCU default for !SMP at some time in the future.
>
> o Added (trivial) support for expedited grace periods.
>
> 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 Paul is 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.
>
> Signed-off-by: David Howells <dhowells@redhat.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
> include/linux/hardirq.h | 24 ++++
> include/linux/rcupdate.h | 6 +
> include/linux/rcutiny.h | 103 +++++++++++++++++
> init/Kconfig | 9 ++
> kernel/Makefile | 1 +
> kernel/rcupdate.c | 4 +
> kernel/rcutiny.c | 281 ++++++++++++++++++++++++++++++++++++++++++++++
> 7 files changed, 428 insertions(+), 0 deletions(-)
> create mode 100644 include/linux/rcutiny.h
> create mode 100644 kernel/rcutiny.c
>
> diff --git a/include/linux/hardirq.h b/include/linux/hardirq.h
> index 6d527ee..d5b3876 100644
> --- a/include/linux/hardirq.h
> +++ b/include/linux/hardirq.h
> @@ -139,10 +139,34 @@ static inline void account_system_vtime(struct task_struct *tsk)
> #endif
>
> #if defined(CONFIG_NO_HZ)
> +#if 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);
> +#endif
> #else
> # define rcu_irq_enter() do { } while (0)
> # define rcu_irq_exit() do { } while (0)
> diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h
> index 3ebd0b7..6dd71fa 100644
> --- a/include/linux/rcupdate.h
> +++ b/include/linux/rcupdate.h
> @@ -68,11 +68,17 @@ extern int sched_expedited_torture_stats(char *page);
> /* Internal to kernel */
> extern void rcu_init(void);
> extern void rcu_scheduler_starting(void);
> +#ifndef CONFIG_TINY_RCU
> extern int rcu_needs_cpu(int cpu);
> +#else
> +static inline int rcu_needs_cpu(int cpu) { return 0; }
> +#endif
> extern int rcu_scheduler_active;
>
> #if defined(CONFIG_TREE_RCU) || defined(CONFIG_TREE_PREEMPT_RCU)
> #include <linux/rcutree.h>
> +#elif CONFIG_TINY_RCU
> +#include <linux/rcutiny.h>
> #else
> #error "Unknown RCU implementation specified to kernel configuration"
> #endif
> diff --git a/include/linux/rcutiny.h b/include/linux/rcutiny.h
> new file mode 100644
> index 0000000..08f17ab
> --- /dev/null
> +++ b/include/linux/rcutiny.h
> @@ -0,0 +1,103 @@
> +/*
> + * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition.
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * This program is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
> + *
> + * Copyright IBM Corporation, 2008
> + *
> + * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> + *
> + * For detailed explanation of Read-Copy Update mechanism see -
> + * Documentation/RCU
> + */
> +
> +#ifndef __LINUX_TINY_H
> +#define __LINUX_TINY_H
> +
> +#include <linux/cache.h>
> +
> +/* Global control variables for rcupdate callback mechanism. */
> +struct rcu_ctrlblk {
> + struct rcu_head *rcucblist; /* List of pending callbacks (CBs). */
> + struct rcu_head **donetail; /* ->next pointer of last "done" CB. */
> + struct rcu_head **curtail; /* ->next pointer of last CB. */
> +};
> +
> +extern struct rcu_ctrlblk rcu_ctrlblk;
> +extern struct rcu_ctrlblk rcu_bh_ctrlblk;
> +
> +void rcu_sched_qs(int cpu);
> +void rcu_bh_qs(int cpu);
> +
> +#define __rcu_read_lock() preempt_disable()
> +#define __rcu_read_unlock() preempt_enable()
> +#define __rcu_read_lock_bh() local_bh_disable()
> +#define __rcu_read_unlock_bh() local_bh_enable()
> +#define call_rcu_sched call_rcu
> +
> +#define rcu_init_sched() do { } while (0)
> +extern void rcu_check_callbacks(int cpu, int user);
> +extern void __rcu_init(void);
> +/* extern void rcu_restart_cpu(int cpu); */
> +
> +/*
> + * Return the number of grace periods.
> + */
> +static inline long rcu_batches_completed(void)
> +{
> + return 0;
> +}
> +
> +/*
> + * Return the number of bottom-half grace periods.
> + */
> +static inline long rcu_batches_completed_bh(void)
> +{
> + return 0;
> +}
> +
> +extern int rcu_expedited_torture_stats(char *page);
> +
> +static inline int rcu_pending(int cpu)
> +{
> + return 1;
> +}
> +
> +struct notifier_block;
> +extern int rcu_cpu_notify(struct notifier_block *self,
> + unsigned long action, void *hcpu);
> +
> +#ifdef CONFIG_NO_HZ
> +
> +extern void rcu_enter_nohz(void);
> +extern void rcu_exit_nohz(void);
> +
> +#else /* #ifdef CONFIG_NO_HZ */
> +
> +static inline void rcu_enter_nohz(void)
> +{
> +}
> +
> +static inline void rcu_exit_nohz(void)
> +{
> +}
> +
> +#endif /* #else #ifdef CONFIG_NO_HZ */
> +
> +static inline void exit_rcu(void)
> +{
> +}
> +
> +#endif /* __LINUX_RCUTINY_H */
> diff --git a/init/Kconfig b/init/Kconfig
> index 0121c0e..4fecb53 100644
> --- a/init/Kconfig
> +++ b/init/Kconfig
> @@ -334,6 +334,15 @@ config TREE_PREEMPT_RCU
> is also required. It also scales down nicely to
> smaller systems.
>
> +config TINY_RCU
> + bool "UP-only small-memory-footprint RCU"
> + depends on !SMP
> + help
> + This option selects the RCU implementation that is
> + designed for UP systems from which real-time response
> + is not required. This option greatly reduces the
> + memory footprint of RCU.
> +
> endchoice
>
> config RCU_TRACE
> diff --git a/kernel/Makefile b/kernel/Makefile
> index 7c9b0a5..0098bcf 100644
> --- a/kernel/Makefile
> +++ b/kernel/Makefile
> @@ -83,6 +83,7 @@ obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o
> obj-$(CONFIG_TREE_RCU) += rcutree.o
> obj-$(CONFIG_TREE_PREEMPT_RCU) += rcutree.o
> obj-$(CONFIG_TREE_RCU_TRACE) += rcutree_trace.o
> +obj-$(CONFIG_TINY_RCU) += rcutiny.o
> obj-$(CONFIG_RELAY) += relay.o
> obj-$(CONFIG_SYSCTL) += utsname_sysctl.o
> obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o
> diff --git a/kernel/rcupdate.c b/kernel/rcupdate.c
> index 4001833..7625f20 100644
> --- a/kernel/rcupdate.c
> +++ b/kernel/rcupdate.c
> @@ -67,6 +67,8 @@ void wakeme_after_rcu(struct rcu_head *head)
> complete(&rcu->completion);
> }
>
> +#ifndef CONFIG_TINY_RCU
> +
> #ifdef CONFIG_TREE_PREEMPT_RCU
>
> /**
> @@ -157,6 +159,8 @@ void synchronize_rcu_bh(void)
> }
> EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
>
> +#endif /* #ifndef CONFIG_TINY_RCU */
> +
> static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self,
> unsigned long action, void *hcpu)
> {
> diff --git a/kernel/rcutiny.c b/kernel/rcutiny.c
> new file mode 100644
> index 0000000..89124b0
> --- /dev/null
> +++ b/kernel/rcutiny.c
> @@ -0,0 +1,281 @@
> +/*
> + * Read-Copy Update mechanism for mutual exclusion, the Bloatwatch edition.
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * This program is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
> + *
> + * Copyright IBM Corporation, 2008
> + *
> + * Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> + *
> + * For detailed explanation of Read-Copy Update mechanism see -
> + * Documentation/RCU
> + */
> +
> +#include <linux/types.h>
> +#include <linux/kernel.h>
> +#include <linux/init.h>
> +#include <linux/rcupdate.h>
> +#include <linux/interrupt.h>
> +#include <linux/sched.h>
> +#include <linux/module.h>
> +#include <linux/completion.h>
> +#include <linux/moduleparam.h>
> +#include <linux/notifier.h>
> +#include <linux/cpu.h>
> +#include <linux/mutex.h>
> +#include <linux/time.h>
> +
> +/* Definition for rcupdate control block. */
> +struct rcu_ctrlblk rcu_ctrlblk = {
> + .rcucblist = NULL,
> + .donetail = &rcu_ctrlblk.rcucblist,
> + .curtail = &rcu_ctrlblk.rcucblist,
> +};
> +EXPORT_SYMBOL_GPL(rcu_ctrlblk);
> +struct rcu_ctrlblk rcu_bh_ctrlblk = {
> + .rcucblist = NULL,
> + .donetail = &rcu_bh_ctrlblk.rcucblist,
> + .curtail = &rcu_bh_ctrlblk.rcucblist,
> +};
> +EXPORT_SYMBOL_GPL(rcu_bh_ctrlblk);
> +
> +#ifdef CONFIG_NO_HZ
> +
> +static long rcu_dynticks_nesting = 1;
> +
> +/*
> + * Enter dynticks-idle mode, which is an extended quiescent state
> + * if we have fully entered that mode (i.e., if the new value of
> + * dynticks_nesting is zero).
> + */
> +void rcu_enter_nohz(void)
> +{
> + if (--rcu_dynticks_nesting == 0)
> + rcu_sched_qs(0); /* implies rcu_bh_qsctr_inc(0) */
> +}
> +
> +/*
> + * Exit dynticks-idle mode, so that we are no longer in an extended
> + * quiescent state.
> + */
> +void rcu_exit_nohz(void)
> +{
> + rcu_dynticks_nesting++;
> +}
> +
> +#endif /* #ifdef CONFIG_NO_HZ */
> +
> +/*
> + * Helper function for rcu_qsctr_inc() and rcu_bh_qsctr_inc().
> + */
> +static int rcu_qsctr_help(struct rcu_ctrlblk *rcp)
> +{
> + if (rcp->rcucblist != NULL &&
> + rcp->donetail != rcp->curtail) {
> + rcp->donetail = rcp->curtail;
> + return 1;
> + }
> + return 0;
> +}
> +
> +/*
> + * Record an rcu quiescent state. And an rcu_bh quiescent state while we
> + * are at it, given that any rcu quiescent state is also an rcu_bh
> + * quiescent state. Use "+" instead of "||" to defeat short circuiting.
> + */
> +void rcu_sched_qs(int cpu)
> +{
> + if (rcu_qsctr_help(&rcu_ctrlblk) + rcu_qsctr_help(&rcu_bh_ctrlblk))
> + raise_softirq(RCU_SOFTIRQ);


local_irq_disable()(better) or local_bh_disable() is needed here.

see here:
schedule() {
...
preempt_disable();
....
rcu_sched_qs(cpu); /* nothing to proctect accessing rcp->donetail */
.....
}

> +}
> +
> +/*
> + * Record an rcu_bh quiescent state.
> + */
> +void rcu_bh_qs(int cpu)
> +{
> + if (rcu_qsctr_help(&rcu_bh_ctrlblk))
> + raise_softirq(RCU_SOFTIRQ);


It doesn't need local_irq_disable() nor local_bh_disable().
It's only called at __do_softirq(), but maybe a comment is needed.

> +}
> +
> +/*
> + * Check to see if the scheduling-clock interrupt came from an extended
> + * quiescent state, and, if so, tell RCU about it.
> + */
> +void rcu_check_callbacks(int cpu, int user)
> +{
> + if (!rcu_needs_cpu(0))
> + return; /* RCU doesn't need anything to be done. */

rcu_needs_cpu(0) always returns 0 ......
The next statements will not be executed .....

> + if (user ||
> + (idle_cpu(cpu) &&
> + !in_softirq() &&
> + hardirq_count() <= (1 << HARDIRQ_SHIFT)))
> + rcu_sched_qs(cpu);
> + else if (!in_softirq())
> + rcu_bh_qs(cpu);
> +}
> +
> +/*
> + * Helper function for rcu_process_callbacks() that operates on the
> + * specified rcu_ctrlkblk structure.
> + */
> +static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
> +{
> + unsigned long flags;
> + struct rcu_head *next, *list;
> +
> + /* If no RCU callbacks ready to invoke, just return. */
> + if (&rcp->rcucblist == rcp->donetail)
> + return;
> +
> + /* Move the ready-to-invoke callbacks to a local list. */
> + local_irq_save(flags);
> + list = rcp->rcucblist;
> + rcp->rcucblist = *rcp->donetail;
> + *rcp->donetail = NULL;
> + if (rcp->curtail == rcp->donetail)
> + rcp->curtail = &rcp->rcucblist;
> + rcp->donetail = &rcp->rcucblist;
> + local_irq_restore(flags);
> +
> + /* Invoke the callbacks on the local list. */
> + while (list) {
> + next = list->next;
> + prefetch(next);
> + list->func(list);
> + list = next;
> + }
> +}
> +
> +/*
> + * Invoke any callbacks whose grace period has completed.
> + */
> +static void rcu_process_callbacks(struct softirq_action *unused)
> +{
> + __rcu_process_callbacks(&rcu_ctrlblk);
> + __rcu_process_callbacks(&rcu_bh_ctrlblk);
> +}
> +
> +/*
> + * Null function to handle CPU being onlined. Longer term, we want to
> + * make TINY_RCU avoid using rcupdate.c, but later...
> + */
> +int rcu_cpu_notify(struct notifier_block *self,
> + unsigned long action, void *hcpu)
> +{
> + return NOTIFY_OK;
> +}
> +
> +/*
> + * Wait for a grace period to elapse. But it is illegal to invoke
> + * synchronize_sched() from within an RCU read-side critical section.
> + * Therefore, any legal call to synchronize_sched() is a quiescent
> + * state, and so on a UP system, synchronize_sched() need do nothing.
> + * Ditto for synchronize_rcu_bh().
> + *
> + * Cool, huh? (Due to Josh Triplett.)
> + *
> + * But we want to make this a static inline later.
> + */
> +void synchronize_sched(void)
> +{

I stubbornly recommend adding a cond_resched()/might_sleep() here.

It reduces latency. (for !CONFIG_PREEMPT)
It prevents someone calls it on nonsleepable context.

> +}
> +EXPORT_SYMBOL_GPL(synchronize_sched);
> +
> +void synchronize_rcu_bh(void)
> +{

Ditto.

> +}
> +EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
> +
> +/*
> + * Helper function for call_rcu() and call_rcu_bh().
> + */
> +static void __call_rcu(struct rcu_head *head,
> + void (*func)(struct rcu_head *rcu),
> + struct rcu_ctrlblk *rcp)
> +{
> + unsigned long flags;
> +
> + head->func = func;
> + head->next = NULL;
> + local_irq_save(flags);
> + *rcp->curtail = head;
> + rcp->curtail = &head->next;
> + local_irq_restore(flags);
> +}
> +
> +/*
> + * Post an RCU callback to be invoked after the end of an RCU grace
> + * period. But since we have but one CPU, that would be after any
> + * quiescent state.
> + */
> +void call_rcu(struct rcu_head *head,
> + void (*func)(struct rcu_head *rcu))
> +{
> + __call_rcu(head, func, &rcu_ctrlblk);
> +}
> +EXPORT_SYMBOL_GPL(call_rcu);
> +
> +/*
> + * Post an RCU bottom-half callback to be invoked after any subsequent
> + * quiescent state.
> + */
> +void call_rcu_bh(struct rcu_head *head,
> + void (*func)(struct rcu_head *rcu))
> +{
> + __call_rcu(head, func, &rcu_bh_ctrlblk);
> +}
> +EXPORT_SYMBOL_GPL(call_rcu_bh);
> +
> +void rcu_barrier(void)
> +{
> + struct rcu_synchronize rcu;
> +
> + init_completion(&rcu.completion);
> + /* Will wake me after RCU finished. */
> + call_rcu(&rcu.head, wakeme_after_rcu);
> + /* Wait for it. */
> + wait_for_completion(&rcu.completion);
> +}
> +EXPORT_SYMBOL_GPL(rcu_barrier);
> +
> +void rcu_barrier_bh(void)
> +{
> + struct rcu_synchronize rcu;
> +
> + init_completion(&rcu.completion);
> + /* Will wake me after RCU finished. */
> + call_rcu_bh(&rcu.head, wakeme_after_rcu);
> + /* Wait for it. */
> + wait_for_completion(&rcu.completion);
> +}
> +EXPORT_SYMBOL_GPL(rcu_barrier_bh);
> +
> +void rcu_barrier_sched(void)
> +{
> + struct rcu_synchronize rcu;
> +
> + init_completion(&rcu.completion);
> + /* Will wake me after RCU finished. */
> + call_rcu_sched(&rcu.head, wakeme_after_rcu);
> + /* Wait for it. */
> + wait_for_completion(&rcu.completion);


alternative implementation(nonsleep implementation)

{
cond_resched();

rcp = &rcu_ctrlblk;
local_irq_save(flags);
if (rcp->rcucblist != NULL) {
rcp->donetail = rcp->curtail;
local_irq_restore(flags);

local_bh_disable();
__rcu_process_callbacks(rcp);
local_bh_enable();
} else
local_irq_restore(flags);
}

Ditto for other rcu_barrier*()

> +}
> +EXPORT_SYMBOL_GPL(rcu_barrier_sched);
> +
> +void __rcu_init(void)
> +{
> + open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
> +}



\
 
 \ /
  Last update: 2009-10-12 11:35    [W:0.145 / U:3.372 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site