Priority boosting for preemptible RCU

Hello!

This patch is a forward-port of RCU priority boosting (described in
http://lwn.net/Articles/220677/). It applies to 2.6.22 on top of the patches sent in the http://lkml.org/lkml/2007/8/7/276 series and the hotplug patch (http://lkml.org/lkml/2007/8/17/262). Passes several hours of rcutorture on x86_64 and POWER, so OK for experimentation but not ready for inclusion.

...

+#ifdef CONFIG_PREEMPT_RCU_BOOST

+config PREEMPT_RCU_BOOST_STATS_INTERVAL

* PREEMPT_RCU data structures.

kernel/rcupreempt.c +6 -0

@@ -82,6 +83,525 @@ static struct rcu_ctrlblk rcu_ctrlblk = 
 };
 static DEFINE_PER_CPU(int [2], rcu_flipctr) = { 0, 0 };
 
+#ifndef CONFIG_PREEMPT_RCU_BOOST
+static inline void init_rcu_boost_early(void) { }
+static inline void rcu_read_unlock_unboost(void) { }
+#else /* #ifndef CONFIG_PREEMPT_RCU_BOOST */
+
+/* Defines possible event indices for ->rbs_stats[] (first index). */

kernel/rcupreempt.c +5 -0

+	struct list_head rbs_toboost;
+	struct list_head rbs_boosted;
+	unsigned long rbs_blocked;
+	unsigned long rbs_boost_attempt;
+	unsigned long rbs_boost;

kernel/rcupreempt.c +6 -0

+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+
+/*
+ * Function to increment indicated ->rbs_stats[] element.
+ */
+static inline void rcu_boost_dat_stat(struct rcu_boost_dat *rbdp,

kernel/rcupreempt.c +10 -0

+/*
+ * Print out RCU booster task statistics at the specified interval.
+ */
+static void rcu_boost_dat_stat_print(void)
+{
+	/* Three decimal digits per byte plus spacing per number and line. */
+	char buf[N_RCU_BOOST_STATE * (sizeof(long) * 3 + 2) + 2];
+	int cpu;
+	int event;
+	int i;

kernel/rcupreempt.c +20 -0

+	/* Sum up the state/event-independent counters. */
+
+	sum.rbs_blocked = 0;
+	sum.rbs_boost_attempt = 0;
+	sum.rbs_boost = 0;
+	sum.rbs_unlock = 0;
+	sum.rbs_unboosted = 0;
+	for_each_possible_cpu(cpu)
+		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+			rbdp = per_cpu(rcu_boost_dat, cpu);
+			sum.rbs_blocked += rbdp[i].rbs_blocked;
+			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
+			sum.rbs_boost += rbdp[i].rbs_boost;
+			sum.rbs_unlock += rbdp[i].rbs_unlock;
+			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
+		}
+
+	/* Sum up the state/event-dependent counters. */
+
+	for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++)

kernel/rcupreempt.c +20 -0

+	/* Print them out! */
+
+	printk(KERN_ALERT
+	       "rcu_boost_dat: idx=%d "
+	       "b=%lu ul=%lu ub=%lu boost: a=%lu b=%lu\n",
+	       rcu_boost_idx,
+	       sum.rbs_blocked, sum.rbs_unlock, sum.rbs_unboosted,
+	       sum.rbs_boost_attempt, sum.rbs_boost);
+	for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++) {
+		i = 0;
+		for (state = 0; state < N_RCU_BOOST_STATE; state++) {
+			i += sprintf(&buf[i], " %ld%c",
+				     sum.rbs_stats[event][state],
+				     rcu_boost_state_error[event][state]);
+		}
+		printk(KERN_ALERT "rcu_boost_dat %s %s\n",
+		       rcu_boost_state_event[event], buf);
+	}
+
+	/* Go away and don't come back for awhile. */

kernel/rcupreempt.c +6 -0

+#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+
+/*
+ * Initialize RCU-boost state.  This happens early in the boot process,
+ * when the scheduler does not yet exist.  So don't try to use it.
+ */

kernel/rcupreempt.c +19 -0

+			INIT_LIST_HEAD(&rbdp[i].rbs_toboost);
+			INIT_LIST_HEAD(&rbdp[i].rbs_boosted);
+			rbdp[i].rbs_blocked = 0;
+			rbdp[i].rbs_boost_attempt = 0;
+			rbdp[i].rbs_boost = 0;
+			rbdp[i].rbs_unlock = 0;
+			rbdp[i].rbs_unboosted = 0;
+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+			{
+				int j, k;
+
+				for (j = 0; j < N_RCU_BOOST_DAT_EVENTS; j++)
+					for (k = 0; k < N_RCU_BOOST_STATE; k++)
+						rbdp[i].rbs_stats[j][k] = 0;
+			}
+#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+		}
+		smp_wmb();  /* Make sure readers see above initialization. */
+		rcu_boost_idx = 0;  /* Allow readers to access data. */

kernel/rcupreempt.c +21 -0

+	return &per_cpu(rcu_boost_dat, cpu)[idx];
+}
+
+/*
+ * Return the list from which to boost target tasks.
+ * May only be invoked by the booster task, so guaranteed to
+ * already be initialized.  Use rcu_boost_dat element least recently
+ * the destination for task blocking in RCU read-side critical sections.
+ */
+static inline struct rcu_boost_dat *rcu_rbd_boosting(int cpu)
+{
+	int idx = (rcu_boost_idx + 1) & (RCU_BOOST_ELEMENTS - 1);
+
+	return &per_cpu(rcu_boost_dat, cpu)[idx];
+}
+
+#define PREEMPT_RCU_BOOSTER_PRIO 49  /* Match curr_irq_prio manually. */
+			             /*  Administrators can always adjust */
+				     /*  via the /proc interface. */
+
+/*

kernel/rcupreempt.c +5 -0

+	if (taskp->rcu_prio != rcuprio) {
+		taskp->rcu_prio = rcuprio;
+		if (taskp->rcu_prio != taskp->prio)
+			rt_mutex_setprio(taskp, taskp->rcu_prio);
+	}

kernel/rcupreempt.c +8 -0

+	spin_lock_irqsave(&taskp->pi_lock, oldirq);
+	taskp->rcu_prio = MAX_PRIO;
+	nprio = rt_mutex_getprio(taskp);
+	if (nprio > taskp->prio)
+		rt_mutex_setprio(taskp, nprio);
+	spin_unlock_irqrestore(&taskp->pi_lock, oldirq);
+}
+
 
...
 

kernel/rcupreempt.c +25 -0

+	sched_setscheduler(current, SCHED_RR, &sp);
+	current->flags |= PF_NOFREEZE;
+
+	do {
+
+		/* Advance the lists of tasks. */
+
+		rcu_boost_idx = (rcu_boost_idx + 1) % RCU_BOOST_ELEMENTS;
+		for_each_possible_cpu(cpu) {
+
+			/*
+			 * Boost all sufficiently aged readers.
+			 * Readers must first be preempted or block
+			 * on a mutex in an RCU read-side critical section,
+			 * then remain in that critical section for
+			 * RCU_BOOST_ELEMENTS-1 time intervals.
+			 * So most of the time we should end up doing
+			 * nothing.
+			 */
+
+			rcu_boost_one_reader_list(rcu_rbd_boosting(cpu));
+
+			/*
+			 * Large SMP systems may need to sleep sometimes
+			 * in this loop.  Or have multiple RCU-boost tasks.

kernel/rcupreempt.c +21 -0

+		/* Print stats if enough time has passed. */
+
+		rcu_boost_dat_stat_print();
+
+	} while (!kthread_should_stop());
+
+	return 0;
+}
+
+/*
+ * Perform the portions of RCU-boost initialization that require the
+ * scheduler to be up and running.
+ */
+void init_rcu_boost_late(void)
+{
+
+	/* Spawn RCU-boost task. */
+
+	printk(KERN_INFO "Starting RCU priority booster\n");
+	rcu_boost_task = kthread_run(rcu_booster, NULL, "RCU Prio Booster");
+	if (IS_ERR(rcu_boost_task)) {

kernel/rcupreempt.c +55 -0

+		rcu_boost_task = NULL;
+	}
+}
+
+/*
+ * Update task's RCU-boost state to reflect blocking in RCU read-side
+ * critical section, so that the RCU-boost task can find it in case it
+ * later needs its priority boosted.
+ */
+void __rcu_preempt_boost(void)
+{
+	struct rcu_boost_dat *rbdp;
+	unsigned long oldirq;
+
+	/* Identify list to place task on for possible later boosting. */
+
+	local_irq_save(oldirq);
+	rbdp = rcu_rbd_new();
+	if (rbdp == NULL) {
+		local_irq_restore(oldirq);
+		printk(KERN_ALERT
+		       "Preempted RCU read-side critical section too early.\n");
+		return;
+	}
+	spin_lock(&rbdp->rbs_mutex);
+	rbdp->rbs_blocked++;
+
+	/*
+	 * Update state.  We hold the lock and aren't yet on the list,
+	 * so the booster cannot mess with us yet.
+	 */
+
+	rcu_boost_dat_stat_block(rbdp, current->rcub_state);
+	if (current->rcub_state != RCU_BOOST_IDLE) {
+
+		/*
+		 * We have been here before, so just update stats.
+		 * It may seem strange to do all this work just to
+		 * accumulate statistics, but this is such a
+		 * low-probability code path that we shouldn't care.
+		 * If it becomes a problem, it can be fixed.
+		 */
+
+		spin_unlock_irqrestore(&rbdp->rbs_mutex, oldirq);
+		return;
+	}
+	current->rcub_state = RCU_BOOST_BLOCKED;
+
+	/* Now add ourselves to the list so that the booster can find us. */
+
+	list_add_tail(&current->rcub_entry, &rbdp->rbs_toboost);
+	current->rcub_rbdp = rbdp;
+	spin_unlock_irqrestore(&rbdp->rbs_mutex, oldirq);
+}
+

Quoted 6 lines · On Wed, 22 Aug 2007 12:02:54 -0700 "Paul E. McKenney"…

This patch is a forward-port of RCU priority boosting (described in
http://lwn.net/Articles/220677/). It applies to 2.6.22 on top of the patches sent in the http://lkml.org/lkml/2007/8/7/276 series and the hotplug patch (http://lkml.org/lkml/2007/8/17/262). Passes several hours of rcutorture on x86_64 and POWER, so OK for experimentation but not ready for inclusion.

It'd be nice to have a brief summary of why we might want this code in Linux.

Quoted 1 line

+#ifdef CONFIG_PREEMPT_RCU_BOOST

Do we really need this? Why not just enable the feature all the time?

Quoted 1 line

+config PREEMPT_RCU_BOOST_STATS_INTERVAL

Four new config options? Sob. Zero would be preferable.

Quoted 9 lines

kernel/rcupreempt.c +9 -0

+	struct list_head rbs_toboost;
+	struct list_head rbs_boosted;
+	unsigned long rbs_blocked;
+	unsigned long rbs_boost_attempt;
+	unsigned long rbs_boost;
+	unsigned long rbs_unlock;
+	unsigned long rbs_unboosted;
+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+	unsigned long rbs_stats[N_RCU_BOOST_DAT_EVENTS][N_RCU_BOOST_STATE];

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 116

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+};
+#define RCU_BOOST_ELEMENTS 4
+
+int rcu_boost_idx = -1; /* invalid value in case someone uses RCU early. */
+DEFINE_PER_CPU(struct rcu_boost_dat, rcu_boost_dat[RCU_BOOST_ELEMENTS]);

Do these need global scope?

Quoted 15 lines

kernel/rcupreempt.c +15 -0

+void init_rcu_boost_late(void)
+{
+
+	/* Spawn RCU-boost task. */
+
+	printk(KERN_INFO "Starting RCU priority booster\n");
+	rcu_boost_task = kthread_run(rcu_booster, NULL, "RCU Prio Booster");
+	if (IS_ERR(rcu_boost_task)) {
+		printk(KERN_ALERT
+		       "Unable to create RCU Priority Booster, errno %ld\n",
+		       -PTR_ERR(rcu_boost_task));
+
+		/*
+		 * Continue running, but tasks permanently blocked
+		 * in RCU read-side critical sections will be able

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 501

Quoted 3 lines

kernel/rcupreempt.c +3 -0

+		 * to stall grace-period processing, potentially
+		 * OOMing the machine.
+		 */

I don't think we want to try to struggle along like that. This thread is a piece of core infrastructure: if we couldn't start it then just panic rather than trying to run the kernel in unknown and untested regions of operation.

Quoted 2 lines · On Wed, 22 Aug 2007 12:02:54 -0700 "Paul E. McKenney"…

Hello!

Quoted 6 lines

This patch is a forward-port of RCU priority boosting (described in
http://lwn.net/Articles/220677/). It applies to 2.6.22 on top of the patches sent in the http://lkml.org/lkml/2007/8/7/276 series and the hotplug patch (http://lkml.org/lkml/2007/8/17/262). Passes several hours of rcutorture on x86_64 and POWER, so OK for experimentation but not ready for inclusion.

It'd be nice to have a brief summary of why we might want this code in Linux.

Quoted 3 lines

...

+#ifdef CONFIG_PREEMPT_RCU_BOOST

Do we really need this? Why not just enable the feature all the time?

include/linux/rcupdate.h static inline void rcu_qsctr_inc(int cpu · line 262

Quoted 10 lines

...

include/linux/rcupdate.h +8 -0

+#ifdef CONFIG_PREEMPT_RCU_BOOST
+extern void init_rcu_boost_late(void);
+extern void __rcu_preempt_boost(void);
+#define rcu_preempt_boost() \
+	do { \
+		if (unlikely(current->rcu_read_lock_nesting > 0)) \
+			__rcu_preempt_boost(); \
+	} while (0)

This could be a C function, couldn't it? Probably an inlined one.

include/linux/rcupdate.h static inline void rcu_qsctr_inc(int cpu · line 265

Quoted 3 lines

include/linux/rcupdate.h +3 -0

+#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST */
+#define init_rcu_boost_late()
+#define rcu_preempt_boost()

These need the `do {} while(0)' thing. I don't immediately recall why, but trust me ;) At least to avoid "empty body in an else-statement" warnings.

But, again, the rule should be: only code in cpp when it is not possible to code in C. These could be coded in C.

include/linux/sched.h struct signal_struct { · line 555

Quoted 7 lines

include/linux/sched.h +7 -0

+#ifdef CONFIG_PREEMPT_RCU_BOOST
+#define set_rcu_prio(p, prio)  ((p)->rcu_prio = (prio))
+#define get_rcu_prio(p) ((p)->rcu_prio)
+#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST */
+#define set_rcu_prio(p, prio)  do { } while (0)
+#define get_rcu_prio(p) MAX_PRIO
+#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST */

More macros-which-don't-need-to-be-macros.

Quoted 1 line

+config PREEMPT_RCU_BOOST_STATS_INTERVAL

Four new config options? Sob. Zero would be preferable.

Quoted 15 lines

* PREEMPT_RCU data structures.

kernel/rcupreempt.c +10 -0

@@ -82,6 +83,525 @@ static struct rcu_ctrlblk rcu_ctrlblk = 
 };
 static DEFINE_PER_CPU(int [2], rcu_flipctr) = { 0, 0 };
 
+#ifndef CONFIG_PREEMPT_RCU_BOOST
+static inline void init_rcu_boost_early(void) { }
+static inline void rcu_read_unlock_unboost(void) { }
+#else /* #ifndef CONFIG_PREEMPT_RCU_BOOST */
+
+/* Defines possible event indices for ->rbs_stats[] (first index). */
+
+#define RCU_BOOST_DAT_BLOCK	0
+#define RCU_BOOST_DAT_BOOST	1
+#define RCU_BOOST_DAT_UNLOCK	2

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 101

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#define N_RCU_BOOST_DAT_EVENTS	3
+
+/* RCU-boost per-CPU array element. */
+
+struct rcu_boost_dat {
+	spinlock_t rbs_mutex;

It would be more conventional to name this rbs_lock.

Quoted 9 lines

kernel/rcupreempt.c +9 -0

+	struct list_head rbs_toboost;
+	struct list_head rbs_boosted;
+	unsigned long rbs_blocked;
+	unsigned long rbs_boost_attempt;
+	unsigned long rbs_boost;
+	unsigned long rbs_unlock;
+	unsigned long rbs_unboosted;
+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+	unsigned long rbs_stats[N_RCU_BOOST_DAT_EVENTS][N_RCU_BOOST_STATE];

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 116

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+};
+#define RCU_BOOST_ELEMENTS 4
+
+int rcu_boost_idx = -1; /* invalid value in case someone uses RCU early. */
+DEFINE_PER_CPU(struct rcu_boost_dat, rcu_boost_dat[RCU_BOOST_ELEMENTS]);

Do these need global scope?

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 117

Quoted 1 line

kernel/rcupreempt.c +1 -0

+static struct task_struct *rcu_boost_task = NULL;

Please always pass all patches through scripts/checkpatch.pl

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+
+/*
+ * Function to increment indicated ->rbs_stats[] element.
+ */
+static inline void rcu_boost_dat_stat(struct rcu_boost_dat *rbdp,

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 134

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+				      int event,
+				      enum rcu_boost_state oldstate)
+{
+	if (oldstate >= RCU_BOOST_IDLE &&
+	    oldstate <= RCU_BOOSTED) {
+		rbdp->rbs_stats[event][oldstate]++;
+	} else {
+		rbdp->rbs_stats[event][RCU_BOOST_INVALID]++;
+	}
+}

	if (oldstate >= RCU_BOOST_IDLE && oldstate <= RCU_BOOSTED)
		rbdp->rbs_stats[event][oldstate]++;
	else
		rbdp->rbs_stats[event][RCU_BOOST_INVALID]++;

Much less fuss, no?

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 141

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#define rcu_boost_dat_stat_block(rbdp, oldstate) \
+	rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_BLOCK, oldstate)
+#define rcu_boost_dat_stat_boost(rbdp, oldstate) \
+	rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_BOOST, oldstate)
+#define rcu_boost_dat_stat_unlock(rbdp, oldstate) \
+	rcu_boost_dat_stat(rbdp, RCU_BOOST_DAT_UNLOCK, oldstate)

c-not-cpp.

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+/*
+ * Print out RCU booster task statistics at the specified interval.
+ */
+static void rcu_boost_dat_stat_print(void)
+{
+	/* Three decimal digits per byte plus spacing per number and line. */
+	char buf[N_RCU_BOOST_STATE * (sizeof(long) * 3 + 2) + 2];
+	int cpu;
+	int event;
+	int i;

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 183

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+	static time_t lastprint = 0;
+	struct rcu_boost_dat *rbdp;
+	int state;
+	struct rcu_boost_dat sum;
+
+	/* Wait a graceful interval between printk spamming. */
+
+	if (xtime.tv_sec - lastprint <
+	    CONFIG_PREEMPT_RCU_BOOST_STATS_INTERVAL)
+		return;

	if (xtime.tv_sec - lastprint < CONFIG_PREEMPT_RCU_BOOST_STATS_INTERVAL)
		return;

or even time_after()..

Quoted 25 lines

kernel/rcupreempt.c +25 -0

+	/* Sum up the state/event-independent counters. */
+
+	sum.rbs_blocked = 0;
+	sum.rbs_boost_attempt = 0;
+	sum.rbs_boost = 0;
+	sum.rbs_unlock = 0;
+	sum.rbs_unboosted = 0;
+	for_each_possible_cpu(cpu)
+		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+			rbdp = per_cpu(rcu_boost_dat, cpu);
+			sum.rbs_blocked += rbdp[i].rbs_blocked;
+			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
+			sum.rbs_boost += rbdp[i].rbs_boost;
+			sum.rbs_unlock += rbdp[i].rbs_unlock;
+			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
+		}
+
+	/* Sum up the state/event-dependent counters. */
+
+	for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++)
+		for (state = 0; state < N_RCU_BOOST_STATE; state++) {
+			sum.rbs_stats[event][state] = 0;
+			for_each_possible_cpu(cpu) {
+				for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+					sum.rbs_stats[event][state]

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 214

Quoted 5 lines

kernel/rcupreempt.c +5 -0

+					    += per_cpu(rcu_boost_dat,
+						       cpu)[i].rbs_stats[event][state];
+				}
+			}
+		}

for_each_possible_cpu() can sometimes do a *lot* more work than for_each_online_cpu(). And even for_each_present_cpu().

Quoted 24 lines

kernel/rcupreempt.c +24 -0

+	/* Print them out! */
+
+	printk(KERN_ALERT
+	       "rcu_boost_dat: idx=%d "
+	       "b=%lu ul=%lu ub=%lu boost: a=%lu b=%lu\n",
+	       rcu_boost_idx,
+	       sum.rbs_blocked, sum.rbs_unlock, sum.rbs_unboosted,
+	       sum.rbs_boost_attempt, sum.rbs_boost);
+	for (event = 0; event < N_RCU_BOOST_DAT_EVENTS; event++) {
+		i = 0;
+		for (state = 0; state < N_RCU_BOOST_STATE; state++) {
+			i += sprintf(&buf[i], " %ld%c",
+				     sum.rbs_stats[event][state],
+				     rcu_boost_state_error[event][state]);
+		}
+		printk(KERN_ALERT "rcu_boost_dat %s %s\n",
+		       rcu_boost_state_event[event], buf);
+	}
+
+	/* Go away and don't come back for awhile. */
+
+	lastprint = xtime.tv_sec;
+}
+

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 245

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+#else /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+
+#define rcu_boost_dat_stat_block(rbdp, oldstate)
+#define rcu_boost_dat_stat_boost(rbdp, oldstate)
+#define rcu_boost_dat_stat_unlock(rbdp, oldstate)
+#define rcu_boost_dat_stat_print()

argh.

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+#endif /* #else #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+
+/*
+ * Initialize RCU-boost state.  This happens early in the boot process,
+ * when the scheduler does not yet exist.  So don't try to use it.
+ */
+static void init_rcu_boost_early(void)
+{
+	struct rcu_boost_dat *rbdp;
+	int cpu;

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 262

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+	int i;
+
+	for_each_possible_cpu(cpu) {
+		rbdp = per_cpu(rcu_boost_dat, cpu);
+		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+			rbdp[i].rbs_mutex = SPIN_LOCK_UNLOCKED;

Doesn't this confound lockdep? We're supposed to use spin_lock_init().

Andy, can we have a checkpatch rule for SPIN_LOCK_UNLOCKED please? It's basically always wrong.

Quoted 23 lines

kernel/rcupreempt.c +23 -0

+			INIT_LIST_HEAD(&rbdp[i].rbs_toboost);
+			INIT_LIST_HEAD(&rbdp[i].rbs_boosted);
+			rbdp[i].rbs_blocked = 0;
+			rbdp[i].rbs_boost_attempt = 0;
+			rbdp[i].rbs_boost = 0;
+			rbdp[i].rbs_unlock = 0;
+			rbdp[i].rbs_unboosted = 0;
+#ifdef CONFIG_PREEMPT_RCU_BOOST_STATS
+			{
+				int j, k;
+
+				for (j = 0; j < N_RCU_BOOST_DAT_EVENTS; j++)
+					for (k = 0; k < N_RCU_BOOST_STATE; k++)
+						rbdp[i].rbs_stats[j][k] = 0;
+			}
+#endif /* #ifdef CONFIG_PREEMPT_RCU_BOOST_STATS */
+		}
+		smp_wmb();  /* Make sure readers see above initialization. */
+		rcu_boost_idx = 0;  /* Allow readers to access data. */
+	}
+}
+
+/*

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 291

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+ * Return the list on which the calling task should add itself, or
+ * NULL if too early during initialization.
+ */
+static inline struct rcu_boost_dat *rcu_rbd_new(void)
+{
+	int cpu = raw_smp_processor_id();  /* locks used, so preemption OK. */

plain old smp_processor_id() could have been used here.

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 294

Quoted 3 lines

kernel/rcupreempt.c +3 -0

+	int idx = rcu_boost_idx;
+
+	smp_read_barrier_depends(); barrier(); /* rmb() on Alpha for idx. */

newline, please.

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 296

Quoted 2 lines

kernel/rcupreempt.c +2 -0

+	if (unlikely(idx < 0))
+		return (NULL);

return-is-not-a-function

Quoted 25 lines

kernel/rcupreempt.c +25 -0

+	return &per_cpu(rcu_boost_dat, cpu)[idx];
+}
+
+/*
+ * Return the list from which to boost target tasks.
+ * May only be invoked by the booster task, so guaranteed to
+ * already be initialized.  Use rcu_boost_dat element least recently
+ * the destination for task blocking in RCU read-side critical sections.
+ */
+static inline struct rcu_boost_dat *rcu_rbd_boosting(int cpu)
+{
+	int idx = (rcu_boost_idx + 1) & (RCU_BOOST_ELEMENTS - 1);
+
+	return &per_cpu(rcu_boost_dat, cpu)[idx];
+}
+
+#define PREEMPT_RCU_BOOSTER_PRIO 49  /* Match curr_irq_prio manually. */
+			             /*  Administrators can always adjust */
+				     /*  via the /proc interface. */
+
+/*
+ * Boost the specified task from an RCU viewpoint.
+ * Boost the target task to a priority just a bit less-favored than
+ * that of the RCU-boost task, but boost to a realtime priority even
+ * if the RCU-boost task is running at a non-realtime priority.

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 327

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+ * We check the priority of the RCU-boost task each time we boost
+ * in case the sysadm manually changes the priority.
+ */
+static void rcu_boost_prio(struct task_struct *taskp)
+{
+	unsigned long oldirq;

It's conventional to name this "flags".

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 335

Quoted 8 lines

kernel/rcupreempt.c +8 -0

+	int rcuprio;
+
+	spin_lock_irqsave(&current->pi_lock, oldirq);
+	rcuprio = rt_mutex_getprio(current) + 1;
+	if (rcuprio >= MAX_USER_RT_PRIO)
+		rcuprio = MAX_USER_RT_PRIO - 1;
+	spin_unlock_irqrestore(&current->pi_lock, oldirq);
+	spin_lock_irqsave(&taskp->pi_lock, oldirq);

Sometimes we'll just do spin_unlock+spin_lock here and leave irqs disabled. Saves a few cycles.

Quoted 9 lines

kernel/rcupreempt.c +9 -0

+	if (taskp->rcu_prio != rcuprio) {
+		taskp->rcu_prio = rcuprio;
+		if (taskp->rcu_prio != taskp->prio)
+			rt_mutex_setprio(taskp, taskp->rcu_prio);
+	}
+	spin_unlock_irqrestore(&taskp->pi_lock, oldirq);
+}
+
+/*

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 350

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+ * Unboost the specified task from an RCU viewpoint.
+ */
+static void rcu_unboost_prio(struct task_struct *taskp)
+{
+	int nprio;
+	unsigned long oldirq;

`flags' would reduce the surprise factor a bit.

Quoted 11 lines

kernel/rcupreempt.c +8 -0

+	spin_lock_irqsave(&taskp->pi_lock, oldirq);
+	taskp->rcu_prio = MAX_PRIO;
+	nprio = rt_mutex_getprio(taskp);
+	if (nprio > taskp->prio)
+		rt_mutex_setprio(taskp, nprio);
+	spin_unlock_irqrestore(&taskp->pi_lock, oldirq);
+}
+
 
...
 

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk =

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+/*
+ * Priority-boost tasks stuck in RCU read-side critical sections as
+ * needed (presumably rarely).
+ */
+static int rcu_booster(void *arg)
+{
+	int cpu;
+	struct sched_param sp;
+
+	sp.sched_priority = PREEMPT_RCU_BOOSTER_PRIO;

I suppose using

	struct sched_param sp = { .sched_priority = PREEMPT_RCU_BOOSTER_PRIO, };

would provide a bit of future-safety here.

Quoted 29 lines

kernel/rcupreempt.c +29 -0

+	sched_setscheduler(current, SCHED_RR, &sp);
+	current->flags |= PF_NOFREEZE;
+
+	do {
+
+		/* Advance the lists of tasks. */
+
+		rcu_boost_idx = (rcu_boost_idx + 1) % RCU_BOOST_ELEMENTS;
+		for_each_possible_cpu(cpu) {
+
+			/*
+			 * Boost all sufficiently aged readers.
+			 * Readers must first be preempted or block
+			 * on a mutex in an RCU read-side critical section,
+			 * then remain in that critical section for
+			 * RCU_BOOST_ELEMENTS-1 time intervals.
+			 * So most of the time we should end up doing
+			 * nothing.
+			 */
+
+			rcu_boost_one_reader_list(rcu_rbd_boosting(cpu));
+
+			/*
+			 * Large SMP systems may need to sleep sometimes
+			 * in this loop.  Or have multiple RCU-boost tasks.
+			 */
+		}
+
+		/*

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 469

Quoted 6 lines

kernel/rcupreempt.c +6 -0

+		 * Sleep to allow any unstalled RCU read-side critical
+		 * sections to age out of the list.  @@@ FIXME: reduce,
+		 * adjust, or eliminate in case of OOM.
+		 */
+
+		schedule_timeout_uninterruptible(HZ / 100);

Boy, that's a long time.

Quoted 28 lines

kernel/rcupreempt.c +28 -0

+		/* Print stats if enough time has passed. */
+
+		rcu_boost_dat_stat_print();
+
+	} while (!kthread_should_stop());
+
+	return 0;
+}
+
+/*
+ * Perform the portions of RCU-boost initialization that require the
+ * scheduler to be up and running.
+ */
+void init_rcu_boost_late(void)
+{
+
+	/* Spawn RCU-boost task. */
+
+	printk(KERN_INFO "Starting RCU priority booster\n");
+	rcu_boost_task = kthread_run(rcu_booster, NULL, "RCU Prio Booster");
+	if (IS_ERR(rcu_boost_task)) {
+		printk(KERN_ALERT
+		       "Unable to create RCU Priority Booster, errno %ld\n",
+		       -PTR_ERR(rcu_boost_task));
+
+		/*
+		 * Continue running, but tasks permanently blocked
+		 * in RCU read-side critical sections will be able

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 501

Quoted 3 lines

kernel/rcupreempt.c +3 -0

+		 * to stall grace-period processing, potentially
+		 * OOMing the machine.
+		 */

I don't think we want to try to struggle along like that. This thread is a piece of core infrastructure: if we couldn't start it then just panic rather than trying to run the kernel in unknown and untested regions of operation.

Quoted 55 lines

kernel/rcupreempt.c +55 -0

+		rcu_boost_task = NULL;
+	}
+}
+
+/*
+ * Update task's RCU-boost state to reflect blocking in RCU read-side
+ * critical section, so that the RCU-boost task can find it in case it
+ * later needs its priority boosted.
+ */
+void __rcu_preempt_boost(void)
+{
+	struct rcu_boost_dat *rbdp;
+	unsigned long oldirq;
+
+	/* Identify list to place task on for possible later boosting. */
+
+	local_irq_save(oldirq);
+	rbdp = rcu_rbd_new();
+	if (rbdp == NULL) {
+		local_irq_restore(oldirq);
+		printk(KERN_ALERT
+		       "Preempted RCU read-side critical section too early.\n");
+		return;
+	}
+	spin_lock(&rbdp->rbs_mutex);
+	rbdp->rbs_blocked++;
+
+	/*
+	 * Update state.  We hold the lock and aren't yet on the list,
+	 * so the booster cannot mess with us yet.
+	 */
+
+	rcu_boost_dat_stat_block(rbdp, current->rcub_state);
+	if (current->rcub_state != RCU_BOOST_IDLE) {
+
+		/*
+		 * We have been here before, so just update stats.
+		 * It may seem strange to do all this work just to
+		 * accumulate statistics, but this is such a
+		 * low-probability code path that we shouldn't care.
+		 * If it becomes a problem, it can be fixed.
+		 */
+
+		spin_unlock_irqrestore(&rbdp->rbs_mutex, oldirq);
+		return;
+	}
+	current->rcub_state = RCU_BOOST_BLOCKED;
+
+	/* Now add ourselves to the list so that the booster can find us. */
+
+	list_add_tail(&current->rcub_entry, &rbdp->rbs_toboost);
+	current->rcub_rbdp = rbdp;
+	spin_unlock_irqrestore(&rbdp->rbs_mutex, oldirq);
+}
+

Quoted 5 lines · Andrew Morton

Quoted 2 lines · On Wed, 22 Aug 2007 12:02:54 -0700 "Paul E. McKenney"…

Hello!

Quoted 8 lines

Quoted 6 lines

This patch is a forward-port of RCU priority boosting (described in
http://lwn.net/Articles/220677/). It applies to 2.6.22 on top of the patches sent in the http://lkml.org/lkml/2007/8/7/276 series and the hotplug patch (http://lkml.org/lkml/2007/8/17/262). Passes several hours of rcutorture on x86_64 and POWER, so OK for experimentation but not ready for inclusion.

It'd be nice to have a brief summary of why we might want this code in Linux.

Good point -- will add something like the following in the next rev:

RCU priority boosting is needed when running a workload that might include CPU-bound user tasks running at realtime priorities with a CONFIG_PREEMPT build of the kernel. In this situation, RCU priority boosting is needed to avoid OOM.

Does that cover it?

Quoted 3 lines

Quoted 1 line

+config PREEMPT_RCU_BOOST_STATS_INTERVAL

Four new config options? Sob. Zero would be preferable.

Hmmm... I should be able to fold this into PREEMPT_RCU_BOOST_STATS, now that you mention it. Zero to disable, other number to specify interval. And I should move this to the kernel-hacking group as well. Would that help?

Quoted 2 lines

for_each_possible_cpu() can sometimes do a *lot* more work than for_each_online_cpu(). And even for_each_present_cpu().

for_each_online_cpu() would not cut it here, but for_each_present_cpu() might -- as long as no platforms physically hotplug the CPUs.

Quoted 3 lines

Andy, can we have a checkpatch rule for SPIN_LOCK_UNLOCKED please? It's basically always wrong.

Even for static initializers for top-level variables?

Quoted 4 lines

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 296

Quoted 2 lines

kernel/rcupreempt.c +2 -0

+	if (unlikely(idx < 0))
+		return (NULL);

return-is-not-a-function

You lost me on this one... You presumably aren't asking it to be converted to a macro. You want it manually inlined where called?

Quoted 15 lines · On Wed, 22 Aug 2007 14:22:16 -0700 "Paul E. McKenney"…

Quoted 5 lines · Andrew Morton

Quoted 2 lines · On Wed, 22 Aug 2007 12:02:54 -0700 "Paul E. McKenney"…

Hello!

Quoted 8 lines

Quoted 6 lines

This patch is a forward-port of RCU priority boosting (described in
http://lwn.net/Articles/220677/). It applies to 2.6.22 on top of the patches sent in the http://lkml.org/lkml/2007/8/7/276 series and the hotplug patch (http://lkml.org/lkml/2007/8/17/262). Passes several hours of rcutorture on x86_64 and POWER, so OK for experimentation but not ready for inclusion.

It'd be nice to have a brief summary of why we might want this code in Linux.

Quoted 8 lines

Good point -- will add something like the following in the next rev:

RCU priority boosting is needed when running a workload that might include CPU-bound user tasks running at realtime priorities with a CONFIG_PREEMPT build of the kernel. In this situation, RCU priority boosting is needed to avoid OOM.

Does that cover it?

yup

Quoted 8 lines

Quoted 3 lines

Quoted 1 line

+config PREEMPT_RCU_BOOST_STATS_INTERVAL

Four new config options? Sob. Zero would be preferable.

Hmmm... I should be able to fold this into PREEMPT_RCU_BOOST_STATS, now that you mention it. Zero to disable, other number to specify interval. And I should move this to the kernel-hacking group as well. Would that help?

The fewer the better.

We want to avoid options which some people might want to enable in normal production and which other people might want to disable in normal production. Because most people don't build custom kernels and the person who builds their kernels for them needs to make a decision for them. We don't want to force the person who configures others' kernels to have to make nasty compromises.

Config options which are clearly kernel-devleoper-only are fine: people can just turn them off for production.

Quoted 5 lines

Quoted 2 lines

for_each_possible_cpu() can sometimes do a *lot* more work than for_each_online_cpu(). And even for_each_present_cpu().

for_each_online_cpu() would not cut it here, but for_each_present_cpu() might -- as long as no platforms physically hotplug the CPUs.

Platforms do physically hotplug cpus. All the hotplug notifier stuff is there so that code such as yours can synchronise against that.

Quoted 4 lines

Quoted 2 lines

Andy, can we have a checkpatch rule for SPIN_LOCK_UNLOCKED please? It's basically always wrong.

Even for static initializers for top-level variables?

Yes. For those, use DEFINE_SPINLOCK().

Quoted 7 lines

Quoted 4 lines

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 296

Quoted 2 lines

kernel/rcupreempt.c +2 -0

+	if (unlikely(idx < 0))
+		return (NULL);

return-is-not-a-function

You lost me on this one... You presumably aren't asking it to be converted to a macro. You want it manually inlined where called?

Do return foo;', not return (foo);' ;)

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 262

Quoted 4 lines

kernel/rcupreempt.c +4 -0

+	for_each_possible_cpu(cpu) {
+		rbdp = per_cpu(rcu_boost_dat, cpu);
+		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+			rbdp[i].rbs_mutex = SPIN_LOCK_UNLOCKED;

Doesn't this confound lockdep? We're supposed to use spin_lock_init().

Andy, can we have a checkpatch rule for SPIN_LOCK_UNLOCKED please? It's basically always wrong.

kernel/rcupreempt.c +27 -0

+/*
+ * Print out RCU booster task statistics at the specified interval.
+ */
+static void rcu_boost_dat_stat_print(void)
+{
+	/* Three decimal digits per byte plus spacing per number and line. */
+	char buf[N_RCU_BOOST_STATE * (sizeof(long) * 3 + 2) + 2];
+	int cpu;
+	int event;
+	int i;
+	static time_t lastprint = 0;
+	struct rcu_boost_dat *rbdp;
+	int state;
+	struct rcu_boost_dat sum;
+
+	/* Wait a graceful interval between printk spamming. */
+
+	if (xtime.tv_sec - lastprint <
+	    CONFIG_PREEMPT_RCU_BOOST_STATS_INTERVAL)
+		return;
+
+	/* Sum up the state/event-independent counters. */
+
+	sum.rbs_blocked = 0;
+	sum.rbs_boost_attempt = 0;
+	sum.rbs_boost = 0;
+	sum.rbs_unlock = 0;

Hi Paul,

Quoted 27 lines · Paul E. McKenney

kernel/rcupreempt.c +27 -0

+/*
+ * Print out RCU booster task statistics at the specified interval.
+ */
+static void rcu_boost_dat_stat_print(void)
+{
+	/* Three decimal digits per byte plus spacing per number and line. */
+	char buf[N_RCU_BOOST_STATE * (sizeof(long) * 3 + 2) + 2];
+	int cpu;
+	int event;
+	int i;
+	static time_t lastprint = 0;
+	struct rcu_boost_dat *rbdp;
+	int state;
+	struct rcu_boost_dat sum;
+
+	/* Wait a graceful interval between printk spamming. */
+
+	if (xtime.tv_sec - lastprint <
+	    CONFIG_PREEMPT_RCU_BOOST_STATS_INTERVAL)
+		return;
+
+	/* Sum up the state/event-independent counters. */
+
+	sum.rbs_blocked = 0;
+	sum.rbs_boost_attempt = 0;
+	sum.rbs_boost = 0;
+	sum.rbs_unlock = 0;

kernel/rcupreempt.c static struct rcu_ctrlblk rcu_ctrlblk = · line 200

Quoted 10 lines

kernel/rcupreempt.c +10 -0

+	sum.rbs_unboosted = 0;
+	for_each_possible_cpu(cpu)
+		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
+			rbdp = per_cpu(rcu_boost_dat, cpu);
+			sum.rbs_blocked += rbdp[i].rbs_blocked;
+			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
+			sum.rbs_boost += rbdp[i].rbs_boost;
+			sum.rbs_unlock += rbdp[i].rbs_unlock;
+			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
+		}

I feel we should still be able to use for_each_online_cpu(cpu) instead of for_each_possible_cpu. Again, there's a good chance that I might be mistaken!

How about the following ?

	preempt_disable(); /* We Dont want cpus going down here */
	for_each_online_cpu(cpu) 
		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
			rbdp = per_cpu(rcu_boost_dat, cpu);
			sum.rbs_blocked += rbdp[i].rbs_blocked;
			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
			sum.rbs_boost += rbdp[i].rbs_boost;
			sum.rbs_unlock += rbdp[i].rbs_unlock;
			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
		}
	preempt_enable(); 


	static int rcu_boost_cpu_callback(struct notifier_bloack *nb, 
					unsigned long action, void *hcpu) 
	{
		int this_cpu, cpu;
		rcu_boost_data *rbdp, *this_rbdp;

		switch (action) {
		case CPU_DEAD:
			this_cpu = get_cpu();
			cpu = (long)hcpu;
			this_cpu = smp_processor_id();
			rbdp = per_cpu(rcu_boost_dat, cpu);
			this_rbdp = per_cpu(rcu_boost_dat, cpu);
			/* 
			 *  Transfer all of rbdp's statistics to
			 *  this_rbdp here.
			 */	
			 put_cpu();
	
			return NOTIFY_OK;
		}
	}

Won't this work in this case?

Quoted 44 lines · Gautham R Shenoy

I feel we should still be able to use for_each_online_cpu(cpu) instead of for_each_possible_cpu. Again, there's a good chance that I might be mistaken!

How about the following ?

	preempt_disable(); /* We Dont want cpus going down here */
	for_each_online_cpu(cpu) 
		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
			rbdp = per_cpu(rcu_boost_dat, cpu);
			sum.rbs_blocked += rbdp[i].rbs_blocked;
			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
			sum.rbs_boost += rbdp[i].rbs_boost;
			sum.rbs_unlock += rbdp[i].rbs_unlock;
			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
		}
	preempt_enable(); 


	static int rcu_boost_cpu_callback(struct notifier_bloack *nb, 
					unsigned long action, void *hcpu) 
	{
		int this_cpu, cpu;
		rcu_boost_data *rbdp, *this_rbdp;

		switch (action) {
		case CPU_DEAD:
			this_cpu = get_cpu();
			cpu = (long)hcpu;
			this_cpu = smp_processor_id();
			rbdp = per_cpu(rcu_boost_dat, cpu);
			this_rbdp = per_cpu(rcu_boost_dat, cpu);
			/* 
			 *  Transfer all of rbdp's statistics to
			 *  this_rbdp here.
			 */	
			 put_cpu();
	
			return NOTIFY_OK;
		}
	}

Quoted 1 line

Won't this work in this case?

Hello, Gautham,

We could do something similar. If there was a global rcu_boost_data variable that held the sums of the fields of the rcu_boost_data structures for all offline CPUs, and if we used a new lock to protect that global rcu_boost data variable (both when reading and when CPU hotplugging), then we could indeed scan only the online CPUs' rcu_boost_data elements.

We would also have to maintain a cpumask_t for this purpose, and we would need to add a CPU's contribution when it went offline and subtract it when that CPU came back online.

The lock should not be a problem even on very large systems because of the low frequency of statistics printing -- and of hotplug operations, for that matter.

Thanx, Paul

Quoted 56 lines · Paul E. McKenney

Quoted 44 lines · Gautham R Shenoy

I feel we should still be able to use for_each_online_cpu(cpu) instead of for_each_possible_cpu. Again, there's a good chance that I might be mistaken!

How about the following ?

	preempt_disable(); /* We Dont want cpus going down here */
	for_each_online_cpu(cpu) 
		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
			rbdp = per_cpu(rcu_boost_dat, cpu);
			sum.rbs_blocked += rbdp[i].rbs_blocked;
			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
			sum.rbs_boost += rbdp[i].rbs_boost;
			sum.rbs_unlock += rbdp[i].rbs_unlock;
			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
		}
	preempt_enable(); 


	static int rcu_boost_cpu_callback(struct notifier_bloack *nb, 
					unsigned long action, void *hcpu) 
	{
		int this_cpu, cpu;
		rcu_boost_data *rbdp, *this_rbdp;

		switch (action) {
		case CPU_DEAD:
			this_cpu = get_cpu();
			cpu = (long)hcpu;
			this_cpu = smp_processor_id();
			rbdp = per_cpu(rcu_boost_dat, cpu);
			this_rbdp = per_cpu(rcu_boost_dat, cpu);
			/* 
			 *  Transfer all of rbdp's statistics to
			 *  this_rbdp here.
			 */	
			 put_cpu();
	
			return NOTIFY_OK;
		}
	}

Quoted 1 line

Won't this work in this case?

Hello, Gautham,

We could do something similar. If there was a global rcu_boost_data variable that held the sums of the fields of the rcu_boost_data structures for all offline CPUs, and if we used a new lock to protect that global rcu_boost data variable (both when reading and when CPU hotplugging), then we could indeed scan only the online CPUs' rcu_boost_data elements.

Quoted 3 lines

We would also have to maintain a cpumask_t for this purpose, and we would need to add a CPU's contribution when it went offline and subtract it when that CPU came back online.

The additional cpumask_t beats me though! Doesn't the cpu_online_map suffice here?
The addition and subtraction of a hotplugged cpu's contribution from the global rcu_boost_data could be done while handling the CPU_ONLINE and CPU_DEAD (or CPU_UP_PREPARE and CPU_DOWN_PREPARE, whichever suits better), in the cpu hotplug callback.

Am I missing something ?

Quoted 3 lines

The lock should not be a problem even on very large systems because of the low frequency of statistics printing -- and of hotplug operations, for that matter.

The lock is not a problem, so long as somebody else doesn't call the function taking the lock from their cpu-hotplug callback path :-) Though I don't see it happening here.

Thanks and Regards
gautham.

Signature · 5 lines

Gautham R Shenoy
Linux Technology Center
IBM India.
"Freedom comes with a price tag of responsibility, which is still a bargain,
because Freedom is priceless!"

Quoted 69 lines · Gautham R Shenoy

Quoted 56 lines · Paul E. McKenney

Quoted 44 lines · Gautham R Shenoy

I feel we should still be able to use for_each_online_cpu(cpu) instead of for_each_possible_cpu. Again, there's a good chance that I might be mistaken!

How about the following ?

	preempt_disable(); /* We Dont want cpus going down here */
	for_each_online_cpu(cpu) 
		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
			rbdp = per_cpu(rcu_boost_dat, cpu);
			sum.rbs_blocked += rbdp[i].rbs_blocked;
			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
			sum.rbs_boost += rbdp[i].rbs_boost;
			sum.rbs_unlock += rbdp[i].rbs_unlock;
			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
		}
	preempt_enable(); 


	static int rcu_boost_cpu_callback(struct notifier_bloack *nb, 
					unsigned long action, void *hcpu) 
	{
		int this_cpu, cpu;
		rcu_boost_data *rbdp, *this_rbdp;

		switch (action) {
		case CPU_DEAD:
			this_cpu = get_cpu();
			cpu = (long)hcpu;
			this_cpu = smp_processor_id();
			rbdp = per_cpu(rcu_boost_dat, cpu);
			this_rbdp = per_cpu(rcu_boost_dat, cpu);
			/* 
			 *  Transfer all of rbdp's statistics to
			 *  this_rbdp here.
			 */	
			 put_cpu();
	
			return NOTIFY_OK;
		}
	}

Quoted 1 line

Won't this work in this case?

Hello, Gautham,

We could do something similar. If there was a global rcu_boost_data variable that held the sums of the fields of the rcu_boost_data structures for all offline CPUs, and if we used a new lock to protect that global rcu_boost data variable (both when reading and when CPU hotplugging), then we could indeed scan only the online CPUs' rcu_boost_data elements.

Quoted 3 lines

We would also have to maintain a cpumask_t for this purpose, and we would need to add a CPU's contribution when it went offline and subtract it when that CPU came back online.

The additional cpumask_t beats me though! Doesn't the cpu_online_map suffice here?
The addition and subtraction of a hotplugged cpu's contribution from the global rcu_boost_data could be done while handling the CPU_ONLINE and CPU_DEAD (or CPU_UP_PREPARE and CPU_DOWN_PREPARE, whichever suits better), in the cpu hotplug callback.

Quoted 1 line

Am I missing something ?

Don't we need to synchronize the manipulation of the hotplugged CPU's contribution and the manipulation of cpu_online_map? Otherwise, if stats are called for just before (or just after, depending on the ordering of hotplug operations) the invocation will get the wrong statistics.

Quoted 8 lines

Quoted 4 lines

The lock should not be a problem even on very large systems because of the low frequency of statistics printing -- and of hotplug operations, for that matter.

The lock is not a problem, so long as somebody else doesn't call the function taking the lock from their cpu-hotplug callback path :-) Though I don't see it happening here.

There are some ways to decrease its utilization if it should become a problem in any case.

Thanx, Paul

Quoted 70 lines · Paul E. McKenney

Quoted 69 lines · Gautham R Shenoy

Quoted 56 lines · Paul E. McKenney

Quoted 44 lines · Gautham R Shenoy

I feel we should still be able to use for_each_online_cpu(cpu) instead of for_each_possible_cpu. Again, there's a good chance that I might be mistaken!

How about the following ?

	preempt_disable(); /* We Dont want cpus going down here */
	for_each_online_cpu(cpu) 
		for (i = 0; i < RCU_BOOST_ELEMENTS; i++) {
			rbdp = per_cpu(rcu_boost_dat, cpu);
			sum.rbs_blocked += rbdp[i].rbs_blocked;
			sum.rbs_boost_attempt += rbdp[i].rbs_boost_attempt;
			sum.rbs_boost += rbdp[i].rbs_boost;
			sum.rbs_unlock += rbdp[i].rbs_unlock;
			sum.rbs_unboosted += rbdp[i].rbs_unboosted;
		}
	preempt_enable(); 


	static int rcu_boost_cpu_callback(struct notifier_bloack *nb, 
					unsigned long action, void *hcpu) 
	{
		int this_cpu, cpu;
		rcu_boost_data *rbdp, *this_rbdp;

		switch (action) {
		case CPU_DEAD:
			this_cpu = get_cpu();
			cpu = (long)hcpu;
			this_cpu = smp_processor_id();
			rbdp = per_cpu(rcu_boost_dat, cpu);
			this_rbdp = per_cpu(rcu_boost_dat, cpu);
			/* 
			 *  Transfer all of rbdp's statistics to
			 *  this_rbdp here.
			 */	
			 put_cpu();
	
			return NOTIFY_OK;
		}
	}

Quoted 1 line

Won't this work in this case?

Hello, Gautham,

We could do something similar. If there was a global rcu_boost_data variable that held the sums of the fields of the rcu_boost_data structures for all offline CPUs, and if we used a new lock to protect that global rcu_boost data variable (both when reading and when CPU hotplugging), then we could indeed scan only the online CPUs' rcu_boost_data elements.

Quoted 3 lines

We would also have to maintain a cpumask_t for this purpose, and we would need to add a CPU's contribution when it went offline and subtract it when that CPU came back online.

The additional cpumask_t beats me though! Doesn't the cpu_online_map suffice here?
The addition and subtraction of a hotplugged cpu's contribution from the global rcu_boost_data could be done while handling the CPU_ONLINE and CPU_DEAD (or CPU_UP_PREPARE and CPU_DOWN_PREPARE, whichever suits better), in the cpu hotplug callback.

Quoted 7 lines

Quoted 1 line

Am I missing something ?

Don't we need to synchronize the manipulation of the hotplugged CPU's contribution and the manipulation of cpu_online_map? Otherwise, if stats are called for just before (or just after, depending on the ordering of hotplug operations) the invocation will get the wrong statistics.

Oh, yes we need to synchronize that :-)

Can't we use lock_cpu_hotplug/unlock_cpu_hotplug (or it's variant when it is available) around any access to cpu_online_map ? With that, it's guaranteed that no cpu-hotplug operation will be permitted while you're iterating over the cpu_online_map, and hence you have a consistent view of global rcu_boost_data.

Even if we use another cpumask_t, whenever a cpu goes down or comes up, that will be reflected in this map, no? So what's the additional advantage of using it?

Quoted 10 lines

Quoted 7 lines

Quoted 3 lines

The lock should not be a problem even on very large systems because of the low frequency of statistics printing -- and of hotplug operations, for that matter.

The lock is not a problem, so long as somebody else doesn't call the function taking the lock from their cpu-hotplug callback path :-) Though I don't see it happening here.

There are some ways to decrease its utilization if it should become a problem in any case.

Cool!

Quoted 3 lines

Thanx, Paul

Thanks and Regards
gautham.

Signature · 5 lines

Gautham R Shenoy
Linux Technology Center
IBM India.
"Freedom comes with a price tag of responsibility, which is still a bargain,
because Freedom is priceless!"

Quoted 3 lines

Even if we use another cpumask_t, whenever a cpu goes down or comes up, that will be reflected in this map, no? So what's the additional advantage of using it?

The additional map allows the code to use something other than the lock_cpu_hotplug/unlock_cpu_hotplug, and also is robust against any changes to the hotplug synchronization mechanism. Might well be better just to use the current hotplug synchronization mechanism, but I was feeling paranoid. ;-)

Thanx, Paul

Quoted 9 lines · Paul E. McKenney

Quoted 3 lines

Even if we use another cpumask_t, whenever a cpu goes down or comes up, that will be reflected in this map, no? So what's the additional advantage of using it?

The additional map allows the code to use something other than the lock_cpu_hotplug/unlock_cpu_hotplug, and also is robust against any changes to the hotplug synchronization mechanism. Might well be better just to use the current hotplug synchronization mechanism, but I was feeling paranoid. ;-)

If it was doing something more complicated in the critical section other than summing stuff up, I would probably recommend going for another map instead of using the current hotplug synchronization. But for this case the current hotplug synchronization would work just fine.

I can very well understand your paranoia, but let me assure you, you are not the only one ;-)