[RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Gautham R Shenoy]

[-- Attachment #1: Type: text/plain, Size: 165 bytes --]


-- 
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!"

[-- Attachment #2: 3of4.patch --]
[-- Type: text/plain, Size: 8201 bytes --]

This patch provides the (Refcount + Workqueue) implementation for
cpu_hotplug "locking". It is analogous to a unfair rwsem.

Signed-off-by : Gautham R Shenoy <ego@in.ibm.com>

Index: current/kernel/cpu.c
===================================================================
--- current.orig/kernel/cpu.c	2006-08-06 23:50:11.000000000 +0530
+++ current/kernel/cpu.c	2006-08-24 15:00:04.000000000 +0530
@@ -14,50 +14,172 @@
 #include <linux/kthread.h>
 #include <linux/stop_machine.h>
 #include <linux/mutex.h>
-
-/* This protects CPUs going up and down... */
-static DEFINE_MUTEX(cpu_add_remove_lock);
-static DEFINE_MUTEX(cpu_bitmask_lock);
+#include <asm/percpu.h>
+#include <linux/cpumask.h>
+#include <linux/types.h>
+#include <linux/wait.h>
 
 static __cpuinitdata BLOCKING_NOTIFIER_HEAD(cpu_chain);
 
+/************************************************************************
+ *			A FEW CONTEXT SPECIFIC DEFINITIONS		*
+ * ---------------------------------------------------------------------*
+ * - reader : task which tries to *prevent* a cpu hotplug event.	*
+ *									*
+ * - writer : task which tries to *perform* a cpu hotplug event		*
+ *									*
+ * - write-operation: cpu hotplug operation.				*
+ *									*
+ ************************************************************************/
+
+ /***********************************************************************
+ *			THE PROTOCOL					*
+ *----------------------------------------------------------------------*
+ *- Analogous to RWSEM, only not so fair.				*
+ *									*
+ *- Readers assume control iff:						*
+ *	a) No other reader has a reference and no writer is writing.	*
+ *	OR								*
+ *	b) Atleast one reader has a reference.				*
+ *									*
+ *- In any other case, the reader is blocked.				*
+ *									*
+ *- Writer gets to perform a write iff:					*
+ *	*No* reader has a reference and no writer is writing.		*
+ *									*
+ *- In any other case, the writer is blocked.				*
+ *									*
+ *- Writer, on completion would preferable wake up other waiting	*
+ *  writers over the waiting readers.					*
+ *									*
+ *- The *last* writer wakes up all the waiting readers.			*
+ *									*
+ ************************************************************************/
+
+/************************************************************************
+				USEFUL FLAGS
+*************************************************************************/
+/* System has no writers 	*/
+#define NO_WRITERS		0
+
+/* Some writer is waiting */
+#define WRITER_WAITING		1
+
+/* A Writer is performing cpu hotplug*/
+#define CPU_HOTPLUG_ONGOING	2
+
+/*************************************************************************
+		 ( REFCOUNT + WAITQUEUE ) VARIABLES
+**************************************************************************/
+
+static struct {
+	int reader_count; /* Refcount for the Readers*/
+	int status; /* Status of hotplug operation(none,waiting,ongoing) */
+	spinlock_t lock; /* Serializes access to this struct */
+} cpu_hotplug __cacheline_aligned_in_smp =
+		{0, NO_WRITERS, SPIN_LOCK_UNLOCKED};
+
+/* Waitqueues for readers and writers */
+static __cacheline_aligned_in_smp DECLARE_WAIT_QUEUE_HEAD(read_queue);
+static __cacheline_aligned_in_smp DECLARE_WAIT_QUEUE_HEAD(write_queue);
+
+/********************************************************************
+	MAIN CPU_HOTPLUG (ENABLE/ DISABLE/ BEGIN/ DONE) CODE
+*********************************************************************/
 #ifdef CONFIG_HOTPLUG_CPU
 
-/* Crappy recursive lock-takers in cpufreq! Complain loudly about idiots */
-static struct task_struct *recursive;
-static int recursive_depth;
-
+/** lock_cpu_hotplug : Blocks iff
+	- Hotplug operation is underway.
+*/
 void lock_cpu_hotplug(void)
 {
-	struct task_struct *tsk = current;
-
-	if (tsk == recursive) {
-		static int warnings = 10;
-		if (warnings) {
-			printk(KERN_ERR "Lukewarm IQ detected in hotplug locking\n");
-			WARN_ON(1);
-			warnings--;
-		}
-		recursive_depth++;
+	DECLARE_WAITQUEUE(wait, current);
+	spin_lock(&cpu_hotplug.lock);
+	cpu_hotplug.reader_count++;
+	if (cpu_hotplug.status != CPU_HOTPLUG_ONGOING) {
+		spin_unlock(&cpu_hotplug.lock);
 		return;
 	}
-	mutex_lock(&cpu_bitmask_lock);
-	recursive = tsk;
+	add_wait_queue_exclusive(&read_queue, &wait);
+	set_current_state(TASK_UNINTERRUPTIBLE);
+	spin_unlock(&cpu_hotplug.lock);
+	schedule();
+	remove_wait_queue(&read_queue, &wait);
 }
 EXPORT_SYMBOL_GPL(lock_cpu_hotplug);
 
+/** unlock_cpu_hotplug:
+	- Decrements the reader_count.
+	- If no readers are holding reference AND there is a writer
+	waiting, we set the flag to HOTPLUG_ONGOING and wake up
+	one of the waiting writer.
+*/
 void unlock_cpu_hotplug(void)
 {
-	WARN_ON(recursive != current);
-	if (recursive_depth) {
-		recursive_depth--;
-		return;
+	spin_lock(&cpu_hotplug.lock);
+	/* This should not happen, but in case it does... */
+	WARN_ON(!cpu_hotplug.reader_count);
+
+	cpu_hotplug.reader_count--;
+	if (!(cpu_hotplug.reader_count) && \
+			(cpu_hotplug.status == WRITER_WAITING)) {
+		cpu_hotplug.status = CPU_HOTPLUG_ONGOING;
+		wake_up(&write_queue);
 	}
-	mutex_unlock(&cpu_bitmask_lock);
-	recursive = NULL;
+	spin_unlock(&cpu_hotplug.lock);
 }
 EXPORT_SYMBOL_GPL(unlock_cpu_hotplug);
 
+/** cpu_hotplug_begin : Blocks unless
+	No reader has the reference
+	AND
+	Hotplug operation is not ongoing.
+*/
+static void cpu_hotplug_begin(int interruptible)
+{
+	DECLARE_WAITQUEUE(wait, current);
+	spin_lock(&cpu_hotplug.lock);
+	if (!cpu_hotplug.reader_count && \
+			(cpu_hotplug.status != CPU_HOTPLUG_ONGOING)) {
+		cpu_hotplug.status = CPU_HOTPLUG_ONGOING;
+		spin_unlock(&cpu_hotplug.lock);
+		return;
+	}
+	if (cpu_hotplug.status != CPU_HOTPLUG_ONGOING)
+		cpu_hotplug.status = WRITER_WAITING;
+	add_wait_queue_exclusive(&write_queue, &wait);
+	if (interruptible)
+		set_current_state(TASK_INTERRUPTIBLE);
+	else
+		set_current_state(TASK_UNINTERRUPTIBLE);
+	spin_unlock(&cpu_hotplug.lock);
+	schedule();
+	remove_wait_queue(&write_queue, &wait);
+}
+
+/** cpu_hotplug_done : Performs either one of the following:
+	- Wake up the next writer,if any.
+	- reset flag to zero
+	 and wake up all the waiting readers, if any.
+*/
+void cpu_hotplug_done(void)
+{
+	spin_lock(&cpu_hotplug.lock);
+
+	if (!list_empty(&write_queue.task_list))
+		/* Another cpu writer! */
+		wake_up(&write_queue);
+	else {
+		/* This is the last writer. Remove the flag */
+		cpu_hotplug.status = NO_WRITERS;
+
+		if (cpu_hotplug.reader_count)
+			wake_up_all(&read_queue); /* All rise! */
+	}
+
+	spin_unlock(&cpu_hotplug.lock);
+}
+
 #endif	/* CONFIG_HOTPLUG_CPU */
 
 /* Need to know about CPUs going up/down? */
@@ -114,7 +236,7 @@ int cpu_down(unsigned int cpu)
 	struct task_struct *p;
 	cpumask_t old_allowed, tmp;
 
-	mutex_lock(&cpu_add_remove_lock);
+	cpu_hotplug_begin(1);
 	if (num_online_cpus() == 1) {
 		err = -EBUSY;
 		goto out;
@@ -140,9 +262,7 @@ int cpu_down(unsigned int cpu)
 	cpu_clear(cpu, tmp);
 	set_cpus_allowed(current, tmp);
 
-	mutex_lock(&cpu_bitmask_lock);
 	p = __stop_machine_run(take_cpu_down, NULL, cpu);
-	mutex_unlock(&cpu_bitmask_lock);
 
 	if (IS_ERR(p)) {
 		/* CPU didn't die: tell everyone.  Can't complain. */
@@ -180,7 +300,7 @@ out_thread:
 out_allowed:
 	set_cpus_allowed(current, old_allowed);
 out:
-	mutex_unlock(&cpu_add_remove_lock);
+	cpu_hotplug_done();
 	return err;
 }
 #endif /*CONFIG_HOTPLUG_CPU*/
@@ -190,7 +310,7 @@ int __devinit cpu_up(unsigned int cpu)
 	int ret;
 	void *hcpu = (void *)(long)cpu;
 
-	mutex_lock(&cpu_add_remove_lock);
+	cpu_hotplug_begin(1);
 	if (cpu_online(cpu) || !cpu_present(cpu)) {
 		ret = -EINVAL;
 		goto out;
@@ -205,21 +325,18 @@ int __devinit cpu_up(unsigned int cpu)
 	}
 
 	/* Arch-specific enabling code. */
-	mutex_lock(&cpu_bitmask_lock);
 	ret = __cpu_up(cpu);
-	mutex_unlock(&cpu_bitmask_lock);
 	if (ret != 0)
 		goto out_notify;
 	BUG_ON(!cpu_online(cpu));
 
 	/* Now call notifier in preparation. */
 	blocking_notifier_call_chain(&cpu_chain, CPU_ONLINE, hcpu);
-
 out_notify:
 	if (ret != 0)
 		blocking_notifier_call_chain(&cpu_chain,
 				CPU_UP_CANCELED, hcpu);
 out:
-	mutex_unlock(&cpu_add_remove_lock);
+	cpu_hotplug_done();
 	return ret;
 }

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Ingo Molnar]

* Gautham R Shenoy <ego@in.ibm.com> wrote:

>  void lock_cpu_hotplug(void)
>  {

> +	DECLARE_WAITQUEUE(wait, current);
> +	spin_lock(&cpu_hotplug.lock);
> +	cpu_hotplug.reader_count++;

this should be per-CPU - lock_cpu_hotplug() should _not_ be a globally 
synchronized event.

CPU removal is such a rare event that we can easily do something like a 
global read-mostly 'CPU is locked for writes' flag (plus a completion 
queue) that the 'write' side takes atomically - combined with per-CPU 
refcount and a waitqueue that the read side increases/decreases and 
wakes. Read-locking of the CPU is much more common and should be 
fundamentally scalable: it should increase the per-CPU refcount, then 
check the global 'writer active' flag, and if the writer flag is set, it 
should wait on the global completion queue. When a reader drops the 
refcount it should wake up the per-CPU waitqueue. [in which a writer 
might be waiting for the refcount to go down to 0.]

	Ingo

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Gautham R Shenoy]

On Thu, Aug 24, 2006 at 01:14:40PM +0200, Ingo Molnar wrote:
> 
> * Gautham R Shenoy <ego@in.ibm.com> wrote:
> 
> >  void lock_cpu_hotplug(void)
> >  {
> 
> > +	DECLARE_WAITQUEUE(wait, current);
> > +	spin_lock(&cpu_hotplug.lock);
> > +	cpu_hotplug.reader_count++;
> 
> this should be per-CPU - lock_cpu_hotplug() should _not_ be a globally 
> synchronized event.
> CPU removal is such a rare event that we can easily do something like a 
> global read-mostly 'CPU is locked for writes' flag (plus a completion 
> queue) that the 'write' side takes atomically - combined with per-CPU 
> refcount and a waitqueue that the read side increases/decreases and 
> wakes. Read-locking of the CPU is much more common and should be 
> fundamentally scalable: it should increase the per-CPU refcount, then 
> check the global 'writer active' flag, and if the writer flag is set, it 
> should wait on the global completion queue. When a reader drops the 
> refcount it should wake up the per-CPU waitqueue. [in which a writer 
> might be waiting for the refcount to go down to 0.]
This was the approach I tried to make it cache friendly.
These are the problems I faced.

- Reader checks the write_active flag. If set, he waits in the global read
queue. else, he gets the lock and increments percpu refcount.

- the writer would have to check each cpu's read refcount, and ensure that
read refcount =0 on all of them before he sets write_active and 
begins a write operation.
This will create a big race window - a writer is checking
for a refcount on cpu(j), a reader comes on cpu(i) where i<j;
Let's assume the writer checks refcounts in increasing order of cpus.
Should the reader on cpu(i) wait or go ahead? If we use a global
lock to serialize this operation, we the whole purpose of maintaining
per cpu data is lost.

- If the reader decides to wait on cpu(i) and the writer on cpu(j+1) 
finds refcount!=0,do we have both reader and writer waiting?
Or should the writer perform some sort of a rollback, where he wakes up
the readers on all cpus i < j+1?

- When a reader is done, he decrements his percpu refcount. But, a 
percpu refcount = 0 does not mean there are no active readers in the 
system. So the reader too, would have to check for each cpu refcount
before he wakes up the writer in his queue. this would mean 
referencing other cpu's data.

- How do we deal when a reader takes a lock first on cpu(i) gets
migrated to cpu(j) during an unlock. Again, we have to cross-reference 
other cpu's data.

I tried and gave up. But I would love to have this whole thing
implemented in a more cache friendly manner if we can.

Thanks and Regards
ego
-- 
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!"

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Ingo Molnar]

* Gautham R Shenoy <ego@in.ibm.com> wrote:

> This was the approach I tried to make it cache friendly.
> These are the problems I faced.
> 
> - Reader checks the write_active flag. If set, he waits in the global read
> queue. else, he gets the lock and increments percpu refcount.
> 
> - the writer would have to check each cpu's read refcount, and ensure that
> read refcount =0 on all of them before he sets write_active and 
> begins a write operation.
> This will create a big race window - a writer is checking
> for a refcount on cpu(j), a reader comes on cpu(i) where i<j;
> Let's assume the writer checks refcounts in increasing order of cpus.
> Should the reader on cpu(i) wait or go ahead? If we use a global
> lock to serialize this operation, we the whole purpose of maintaining
> per cpu data is lost.

no. The writer first sets the global write_active flag, and _then_ goes 
on to wait for all readers (if any) to get out of their critical 
sections. (That's the purpose of the per-cpu waitqueue that readers use 
to wake up a writer waiting for the refcount to go to 0.)

can you still see problems with this scheme?

(the 'write_active' flag is probably best implemented as a mutex, where 
readers check mutex_is_locked(), and writers try to take it.)

	Ingo

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Srivatsa Vaddagiri]

On Thu, Aug 24, 2006 at 02:25:27PM +0200, Ingo Molnar wrote:
> no. The writer first sets the global write_active flag, and _then_ goes 
> on to wait for all readers (if any) to get out of their critical 
> sections. (That's the purpose of the per-cpu waitqueue that readers use 
> to wake up a writer waiting for the refcount to go to 0.)
> 
> can you still see problems with this scheme?

This can cause a deadlock sometimes, when a thread tries to take the
read_lock() recursively, with a writer having come in between the two
recursive reads:

	Reader1 on CPU0			Writer1 on CPU1

	read_lock() - success

					write_lock() - blocks on Reader1
						  (writer_active = 1)


	read_lock() - blocks on Writer1

The only way to avoid this deadlock is to either keep track of
cpu_hp_lock_count per-task (like the preemption count kept per-task)
or allow read_lock() to succeed if reader_count > 1 (even if
writer_active = 1). The later makes the lock unduely biased towards
readers.


-- 
Regards,
vatsa

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Gautham R Shenoy]

On Thu, Aug 24, 2006 at 06:28:14PM +0530, Srivatsa Vaddagiri wrote:
> On Thu, Aug 24, 2006 at 02:25:27PM +0200, Ingo Molnar wrote:
> > no. The writer first sets the global write_active flag, and _then_ goes 
> > on to wait for all readers (if any) to get out of their critical 
> > sections. (That's the purpose of the per-cpu waitqueue that readers use 
> > to wake up a writer waiting for the refcount to go to 0.)
> > 
> > can you still see problems with this scheme?
> 
> This can cause a deadlock sometimes, when a thread tries to take the
> read_lock() recursively, with a writer having come in between the two
> recursive reads:
> 
> 	Reader1 on CPU0			Writer1 on CPU1
> 
> 	read_lock() - success
> 
> 					write_lock() - blocks on Reader1
> 						  (writer_active = 1)
> 
> 
> 	read_lock() - blocks on Writer1
> 
> The only way to avoid this deadlock is to either keep track of
> cpu_hp_lock_count per-task (like the preemption count kept per-task)
> or allow read_lock() to succeed if reader_count > 1 (even if
> writer_active = 1). The later makes the lock unduely biased towards
> readers.

The reason why recursive read side locking works in the patches I posted, is 
the fact that the _locking_is_unfair_. Which means even when a writer is 
waiting, if there are readers in the system,a new reader will go ahead.

I can try incorporating this unfair model to Ingo's  suggestion 
as follows:
- A writer on arrival sets the global flag to writer_waiting.
- A reader on cpuX checks if global flag = writer_waiting. If yes,
and percpu(refcount) == 0, the reader blocks. if percpu(refcount)!=0,
the reader increments it and goes ahead,because there are readers 
in the system.

This should work, if not for task migration. It may so happen that
a task has already taken a read lock on cpuX, gets migrated to cpuY
where percpu(refcount) = 0. Now a writer arrives, sets the global flag.
The reader tries taking a recursive read lock gets blocked since
percpu(refcount) on cpuY is 0. 

Ingo, I am wondering if lockdep would be of some help here.
Since lockdep already checks for recursive reads, can I use it in
the above case and allow the new reader only if it is recursive?
I don't like the idea of explicitly checking for recursiveness
in the locking schema. Just that I can't think of a better way now.

Thanks and Regards
ego
-- 
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!"

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Nick Piggin]

Gautham R Shenoy wrote:
> On Thu, Aug 24, 2006 at 06:28:14PM +0530, Srivatsa Vaddagiri wrote:
> 
>>On Thu, Aug 24, 2006 at 02:25:27PM +0200, Ingo Molnar wrote:
>>
>>>no. The writer first sets the global write_active flag, and _then_ goes 
>>>on to wait for all readers (if any) to get out of their critical 
>>>sections. (That's the purpose of the per-cpu waitqueue that readers use 
>>>to wake up a writer waiting for the refcount to go to 0.)
>>>
>>>can you still see problems with this scheme?
>>
>>This can cause a deadlock sometimes, when a thread tries to take the
>>read_lock() recursively, with a writer having come in between the two
>>recursive reads:
>>
>>	Reader1 on CPU0			Writer1 on CPU1
>>
>>	read_lock() - success
>>
>>					write_lock() - blocks on Reader1
>>						  (writer_active = 1)
>>
>>
>>	read_lock() - blocks on Writer1
>>
>>The only way to avoid this deadlock is to either keep track of
>>cpu_hp_lock_count per-task (like the preemption count kept per-task)
>>or allow read_lock() to succeed if reader_count > 1 (even if
>>writer_active = 1). The later makes the lock unduely biased towards
>>readers.
> 
> 
> The reason why recursive read side locking works in the patches I posted, is 
> the fact that the _locking_is_unfair_. Which means even when a writer is 
> waiting, if there are readers in the system,a new reader will go ahead.
> 
> I can try incorporating this unfair model to Ingo's  suggestion 
> as follows:
> - A writer on arrival sets the global flag to writer_waiting.
> - A reader on cpuX checks if global flag = writer_waiting. If yes,
> and percpu(refcount) == 0, the reader blocks. if percpu(refcount)!=0,
> the reader increments it and goes ahead,because there are readers 
> in the system.
> 
> This should work, if not for task migration. It may so happen that
> a task has already taken a read lock on cpuX, gets migrated to cpuY
> where percpu(refcount) = 0. Now a writer arrives, sets the global flag.
> The reader tries taking a recursive read lock gets blocked since
> percpu(refcount) on cpuY is 0. 

This could easily block hotplug forever though, if you have lots of
tasks in the system.

> 
> Ingo, I am wondering if lockdep would be of some help here.
> Since lockdep already checks for recursive reads, can I use it in
> the above case and allow the new reader only if it is recursive?
> I don't like the idea of explicitly checking for recursiveness
> in the locking schema. Just that I can't think of a better way now.

Well you would just have a depth count in the task_struct... in fact that
could *be* the read lock (ie. writer traverses all tasks instead of all
CPU locks), and would save a cacheline in the read path...

But I think the point was that we didn't want to add yet another field
to task_struct. Maybe it is acceptable... one day it will be like
page_flags though ;)


-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [RFC][PATCH 3/4] (Refcount + Waitqueue) implementation for cpu_hotplug "locking"

[Srivatsa Vaddagiri]

On Fri, Aug 25, 2006 at 04:19:29PM +1000, Nick Piggin wrote:
> Well you would just have a depth count in the task_struct... 

That (if can have) would make life so easy :)

-- 
Regards,
vatsa