(Refcount + Waitqueue) implementation for cpu_hotplug "locking"
RFC PATCH 3/4 (Refcount + Waitqueue) implementation for cpu_hotplug "locking"
Signature · 6 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!"
This patch provides the (Refcount + Workqueue) implementation for cpu_hotplug "locking". It is analogous to a unfair rwsem.
kernel/cpu.c +152 -35
@@ -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; }
kernel/cpu.c line 98
Quoted 6 lines · Gautham R Shenoy
void
lock_cpu_hotplug(void)
{kernel/cpu.c +3
-0+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
Quoted 6 lines · Ingo Molnar
Quoted 2 lines · Gautham R Shenoy
void
lock_cpu_hotplug(void)
{
Quoted 16 lines
kernel/cpu.c line 98
Quoted 3 lines
kernel/cpu.c +3
-0+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
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 6 lines · Gautham R Shenoy
This was the approach I tried to make it cache friendly. These are the problems I faced.
- Reader checks the
write_activeflag. If set, he waits in the global read queue. else, he gets the lock and increments percpu refcount.
Quoted 9 lines
- 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_activeand 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
Quoted 6 lines · Ingo Molnar
no. The writer first sets the global
write_activeflag, 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.
Signature · 2 lines
Regards, vatsa
Quoted 20 lines · Srivatsa Vaddagiri
Quoted 6 lines · Ingo Molnar
no. The writer first sets the global
write_activeflag, 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)
Quoted 7 lines
read_lock()- blocks on Writer1The only way to avoid this deadlock is to either keep track of
cpu_hp_lock_countper-task (like the preemption count kept per-task) or allowread_lock()to succeed ifreader_count> 1 (even ifwriter_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
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 37 lines · Gautham R Shenoy
Quoted 18 lines · Srivatsa Vaddagiri
Quoted 3 lines · Ingo Molnar
no. The writer first sets the global
write_activeflag, 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)Quoted 7 lines
read_lock()- blocks on Writer1The only way to avoid this deadlock is to either keep track of
cpu_hp_lock_countper-task (like the preemption count kept per-task) or allowread_lock()to succeed ifreader_count> 1 (even ifwriter_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 towriter_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.
Quoted 5 lines
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.
Quoted 6 lines
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 ;)
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 1 line · Nick Piggin
Well you would just have a depth count in the
task_struct...
That (if can have) would make life so easy :)
Signature · 2 lines
Regards, vatsa