Linux Scalability Effort

On Monday 03 February 2003 06:36 pm, John Hawkes wrote:
> Why isn't this a generic replacement for the current *_lock_irq*
> routines?  Is it simply the extra overhead (and slightly larger size) of
> the looping code?  I'm not seeing any significant performance
> degradation using this friendlier locking scheme.

Have you seen any performance improvements (perhaps in the form of increased 
throughput) with your patch applied?  Is interactivity any better?  Offhand 
it seems like you might be.  You could try running some of the 'sio' tests in 
our linux-noship ism as a test.

> (I should also note that I am employing this scheme concurrent with a
> write_trylock() and a spin_trylock() that gently sniffs at the lock to
> determine its current state, rather than starting off with the relative
> heavyweight cmpxchg.)

This sounds like a reasonable optimization to me, I think you should take it 
to lkml.  Maybe it's simple enough to get in before the freeze?

Jesse

On Mon, Feb 03, 2003 at 06:36:38PM -0800, John Hawkes wrote:
> (I should also note that I am employing this scheme concurrent with a
> write_trylock() and a spin_trylock() that gently sniffs at the lock to
> determine its current state, rather than starting off with the relative
> heavyweight cmpxchg.)
> 
> Comments, please!

I believe the last time this was proposed it was rejected with
"let's fix the algorithm to not use the lock that often instead".

Same was with queued locks: they perform better especially on NUMA
for the congestion case, but are slower for the uncongested case
(= they optimize the wrong thing) 

At least for tasklist_lock i believe the fix was to fix the algorithms
to not walk all processes. A lot of that work got into 2.5.

For runqueue locks :- are you saying you still see significant locking
overhead with the O(1) scheduler?

-Andi

> One thing we're seeing here on systems with lots of CPUs (e.g., 32 or
> 64) and workloads that produce significant contention on some key locks
> (e.g., tasklist_lock in 2.4.19, or one of the runqueue spinlocks, or ...
> pick one) is the unfortunate effect of a spin_lock_irq() or
> write_lock_irq(): disable interrupts, then contend for the lock.  If the
> lock is highly contended and we encounter high wait-times, then
> interrupts are disabled for the entire wait-time, which can be a
> distressingly significant period of time.
> 
> I have observed some interrupts-disabled periods of several hundred
> milliseconds for some locks, and many occurrences of 10-30 milliseconds
> of interrupts-disabled periods for several locks.  (SGI Itanium 2 NUMA
> systems, to be specific.)
> 
> An effective solution is an interrupt-friendly locking scheme, such as:
>   do { disable_interrupts;
>          if (try_to_acquire_lock)
>              break;
>          else
>               enable_interrupts;
>   } while (1)
> 
> Why isn't this a generic replacement for the current *_lock_irq*
> routines?  Is it simply the extra overhead (and slightly larger size) of
> the looping code?  I'm not seeing any significant performance
> degradation using this friendlier locking scheme.

If the lock is that contended, wouldn't you be better off just fixing the
real problem, which is the lock contention? Dipankar is playing with some
RCU stuff for the tasklist lock you might want to talk to him about.

M.

>> Folks,
>> 
>> One thing we're seeing here on systems with lots of CPUs (e.g., 32 or
>> 64) and workloads that produce significant contention on some key locks
>> (e.g., tasklist_lock in 2.4.19, or one of the runqueue spinlocks, or ...
>> pick one) is the unfortunate effect of a spin_lock_irq() or
>> write_lock_irq(): disable interrupts, then contend for the lock.  If the
>> lock is highly contended and we encounter high wait-times, then
>> interrupts are disabled for the entire wait-time, which can be a
>> distressingly significant period of time.
>> 
>> I have observed some interrupts-disabled periods of several hundred
>> milliseconds for some locks, and many occurrences of 10-30 milliseconds
>> of interrupts-disabled periods for several locks.  (SGI Itanium 2 NUMA
>> systems, to be specific.)
>> 
>> An effective solution is an interrupt-friendly locking scheme, such as:
>>   do { disable_interrupts;
>>          if (try_to_acquire_lock)
>>              break;
>>          else
>>               enable_interrupts;
>>   } while (1)
>> 
>> Why isn't this a generic replacement for the current *_lock_irq*
>> routines?  Is it simply the extra overhead (and slightly larger size) of
>> the looping code?  I'm not seeing any significant performance
>> degradation using this friendlier locking scheme.

Most spinlocks _should_ not be heavily contended. For these locks, adding
a "sniff" of the lock before trying to do a "cmpxchg" will frequently cause an
additional coherency transaction on the bus. The cacheline that contains
the lock will be fetched "shared" for the sniff, then refetched exclusive
for the cmpxchg. This assumes the common case where the lock was last 
held by a different cpu. If the lock were last held by the SAME cpu,
no additional bus transactions are needed.

A second consideration applies to NUMA systems. Depending on the hardware,
cpus that are located further from the memory that contain the lock frequently 
are at a disadvantage in trying to set the lock in a remote node. As you add 
cycles between the "sniff" & the cmpxchg, the disadvantage increases. In
the code above, you are adding an enable/disable interrupt.
Do you have any data that indicates if this results in additional
unfairness. 

Note that the unfairness does not necessarily result in a performance 
degradation. If you are using AIM7 to measure performance, you may not
see a decrease in throughput. However, the JTI value decreases (JTI is an 
AIM measure of "unfairness". The unfairness is typically a scheduler anomaly 
but can also be caused by any factor that causes variations in the amount 
of time required to do a fixed amount of work).


I wonder if a better algorithm might be one that disabled interrupts,
then spun in a tight loop trying to set the lock.
Periodically, enable/disable interrupts. For example:

	disable_ints
	do {
		if (cmpxchg successful)
			break

		i=0
		while(lock is set) {
			if (i++ == XXX) { 	// pick XXX so that interrupts are 
				enable_ints	//   enabled every few usec
				i=0
				disable_ints
			}
		}
	}
				




>> 
>> (I should also note that I am employing this scheme concurrent with a
>> write_trylock() and a spin_trylock() that gently sniffs at the lock to
>> determine its current state, rather than starting off with the relative
>> heavyweight cmpxchg.)
>> 
>> Comments, please!
>> 
>> John Hawkes
>> hawkes@...
>>

>> One thing we're seeing here on systems with lots of CPUs (e.g., 32 or
>> 64) and workloads that produce significant contention on some key locks
>> (e.g., tasklist_lock in 2.4.19, or one of the runqueue spinlocks, or ...
>> pick one) is the unfortunate effect of a spin_lock_irq() or
>> write_lock_irq(): disable interrupts, then contend for the lock.  If the
>> lock is highly contended and we encounter high wait-times, then
>> interrupts are disabled for the entire wait-time, which can be a
>> distressingly significant period of time.

BTW, are you running O(1) scheduler already? If so, and you're still seeing
runqueue contention, you might want to backport the 2.5 NUMA scheduler
stuff, it's much lighter on other runqueues (even than the 2.4 NUMA sched
stuff from Erich).

M.

From: "Jesse Barnes" <jbarnes@...>
> Have you seen any performance improvements (perhaps in the form of
increased
> throughput) with your patch applied?  Is interactivity any better?

The AIM7 throughput peak is slightly higher with the "friendlier"
relaxing of interrupts-disabled -- about 1%, which is in the noise level
(32p).  The throughput degradation is less, i.e., somewhat flatter,
beyond the peak throughput.  I didn't notice any improvement in
interactivity.  It did, however, eliminate the 800 msec
interrupts-disabled periods due to the write_lock_irq(&tasklist_lock)
calls -- again, this is in 2.4.19.

John Hawkes

From: "Andi Kleen" <ak@...>
...
> At least for tasklist_lock i believe the fix was to fix the algorithms
> to not walk all processes. A lot of that work got into 2.5.

I understand that.  I'm wrestling with a 2.4.19-based kernel now, not
2.5.

I do understand that the general answer to locking problems is that it
is always prefereable to spend energy reducing the frequency of usage
and the hold-times of the locks, not in making the locking code itself
more efficient (or to trick it up in various other ways).  I'm just
trying to work with the 2.4.19 cards that I've been dealt, and the
tasklist_lock is an especially bad problem in 2.4.19.

> For runqueue locks :- are you saying you still see significant locking
> overhead with the O(1) scheduler?

I am not seeing significant locking overhead, although I am seeing some
contention, presumably on the "busiest" lock.  I've already reduced this
by doing some things that aren't yet in 2.5, such as throttling the
thundering herd of idle CPUs going after the "busiest" lock every
millisecond (for ia64), and staggering the non-idle CPUs that call
load_balance() every 200-250 milliseconds.  (Yes, these are problems
that appear with 64 CPUs that you're just not going to see at 8p.)

John Hawkes

From: "Martin J. Bligh" <mbligh@...>
> BTW, are you running O(1) scheduler already? If so, and you're still
seeing
> runqueue contention, you might want to backport the 2.5 NUMA scheduler
> stuff, it's much lighter on other runqueues (even than the 2.4 NUMA
sched
> stuff from Erich).

Yes, I'm running the O(1) scheduler -- and the IBM MQ scheduler
previously.  I'm not running with any NUMA-aware niceties yet.  Yes, I'm
sure those will help, and we definitely need NUMA-awareness on our NUMA
system.  One problem is that I need to backport the cpu-to-node mapping
code from 2.5. to 2.4.19.

load_balance() holds locks for fairly short durations -- I'm seeing mean
hold-times of 7-15 microsecs, and "usage" (according to Lockmeter) close
to zero -- but I'm seeing contention at almost 70% with some workloads,
with some observed max wait-time of 3 millisecs.  The trick is to
stagger when load_balance() executes across the CPUs so as to reduce
contention.  When there is a lot of context-switching going on, each CPU
is going after its own runqueue lock fairly frequently, and
load_balance() just intrudes and causes most of the contention.

John Hawkes

> Yes, I'm running the O(1) scheduler -- and the IBM MQ scheduler
> previously.  I'm not running with any NUMA-aware niceties yet.  Yes, I'm
> sure those will help, and we definitely need NUMA-awareness on our NUMA
> system.  One problem is that I need to backport the cpu-to-node mapping
> code from 2.5. to 2.4.19.

You'll also need half the other code in 2.5, eg the per-zone LRU lists.
So you can either spend the next 10 years backporting all the 2.5
scalability improvements to 2.4 or just use 2.5 ;-) If you're running the
tree of code I think you're running, you're so far divorced from mainline
that it's not like it matters much.

> load_balance() holds locks for fairly short durations -- I'm seeing mean
> hold-times of 7-15 microsecs, and "usage" (according to Lockmeter) close
> to zero -- but I'm seeing contention at almost 70% with some workloads,
> with some observed max wait-time of 3 millisecs.  The trick is to
> stagger when load_balance() executes across the CPUs so as to reduce
> contention.  When there is a lot of context-switching going on, each CPU
> is going after its own runqueue lock fairly frequently, and
> load_balance() just intrudes and causes most of the contention.

I disagree. The trick is to stop globally load-balancing. It's insane
on that size of system. And I wouldn't bother trying most of the runqueues
half the time .... take the system load average, divide by nr_cpus, and if
you're close enough just leave it the hell alone. Similarly for idle
balancing, just find a nearby cpu that's busy enough (according to the
global or node-kept averages) and just steal something off that. There's a
tendency to try for too much perfection in the scheduler on that size of
machine, rather than just "good enough". Getting that last 1% in perfection
is far too expensive.

M.

On Mon, Feb 03, 2003 at 06:36:38PM -0800, John Hawkes wrote:
> Folks,
> 
> One thing we're seeing here on systems with lots of CPUs (e.g., 32 or
> 64) and workloads that produce significant contention on some key locks
> (e.g., tasklist_lock in 2.4.19, or one of the runqueue spinlocks, or ...
> pick one) is the unfortunate effect of a spin_lock_irq() or
> write_lock_irq(): disable interrupts, then contend for the lock.  If the
> lock is highly contended and we encounter high wait-times, then
> interrupts are disabled for the entire wait-time, which can be a
> distressingly significant period of time.

John,

You need to backport some of the tasklist_lock-abuse-prevention work
in 2.5. The one that comes to the top of my mind is proc_read_super()
that walked the entire tasklist to count the number of tasks. That was
fixed in 2.5 using a per-cpu task counter. If you get_pid_list() is a
problem, you could try out the patch attached below (you need RCU).
I am interested in looking at other potential problems with large
tasklist.

Could you publish your lockmeter results ? Some of these problems may
have been solved in 2.5.

Thanks
Dipankar



diff -urN linux-2.5.59-base/fs/proc/base.c linux-2.5.59-tasks_rcu/fs/proc/base.c
--- linux-2.5.59-base/fs/proc/base.c	2003-01-17 07:52:19.000000000 +0530
+++ linux-2.5.59-tasks_rcu/fs/proc/base.c	2003-01-22 11:21:05.000000000 +0530
@@ -31,6 +31,7 @@
 #include <linux/kallsyms.h>
 #include <linux/mount.h>
 #include <linux/security.h>
+#include <linux/rcupdate.h>
 
 /*
  * For hysterical raisins we keep the same inumbers as in the old procfs.
@@ -1160,7 +1161,7 @@
 	int nr_pids = 0;
 
 	index--;
-	read_lock(&tasklist_lock);
+	rcu_read_lock();
 	for_each_process(p) {
 		int pid = p->pid;
 		if (!pid)
@@ -1172,7 +1173,7 @@
 		if (nr_pids >= PROC_MAXPIDS)
 			break;
 	}
-	read_unlock(&tasklist_lock);
+	rcu_read_unlock();
 	return nr_pids;
 }
 
diff -urN linux-2.5.59-base/include/linux/sched.h linux-2.5.59-tasks_rcu/include/linux/sched.h
--- linux-2.5.59-base/include/linux/sched.h	2003-01-17 07:51:38.000000000 +0530
+++ linux-2.5.59-tasks_rcu/include/linux/sched.h	2003-02-01 00:31:17.000000000 +0530
@@ -28,6 +28,7 @@
 #include <linux/completion.h>
 #include <linux/pid.h>
 #include <linux/percpu.h>
+#include <linux/rcupdate.h>
 
 struct exec_domain;
 
@@ -400,12 +401,17 @@
 	struct backing_dev_info *backing_dev_info;
 
 	unsigned long ptrace_message;
+	struct rcu_head rcu;
 };
 
 extern void __put_task_struct(struct task_struct *tsk);
 #define get_task_struct(tsk) do { atomic_inc(&(tsk)->usage); } while(0)
-#define put_task_struct(tsk) \
-do { if (atomic_dec_and_test(&(tsk)->usage)) __put_task_struct(tsk); } while(0)
+static inline void put_task_struct(struct task_struct *tsk)
+{
+	if (atomic_dec_and_test(&tsk->usage))
+		call_rcu(&tsk->rcu, (void (*)(void *))__put_task_struct, tsk);
+}
+
 
 /*
  * Per process flags
@@ -607,13 +613,13 @@
 
 #define REMOVE_LINKS(p) do {					\
 	if (thread_group_leader(p))				\
-		list_del_init(&(p)->tasks);			\
+		list_del_rcu(&(p)->tasks);			\
 	remove_parent(p);					\
 	} while (0)
 
 #define SET_LINKS(p) do {					\
 	if (thread_group_leader(p))				\
-		list_add_tail(&(p)->tasks,&init_task.tasks);	\
+		list_add_tail_rcu(&(p)->tasks,&init_task.tasks);	\
 	add_parent(p, (p)->parent);				\
 	} while (0)
 
@@ -621,7 +627,7 @@
 #define prev_task(p)	list_entry((p)->tasks.prev, struct task_struct, tasks)
 
 #define for_each_process(p) \
-	for (p = &init_task ; (p = next_task(p)) != &init_task ; )
+	for (p = &init_task ; (p = next_task(p)),({ read_barrier_depends(); 0;}),p != &init_task ; )
 
 /*
  * Careful: do_each_thread/while_each_thread is a double loop so

From: "Dipankar Sarma" <dipankar@...>
> You need to backport some of the tasklist_lock-abuse-prevention work
> in 2.5. The one that comes to the top of my mind is proc_read_super()
> that walked the entire tasklist to count the number of tasks.

The tasklist_lock contention problems I'm seeing for ["modified"] AIM7
are the write_lock_irq(&tasklist_lock) in do_fork(), exit_notify(), and
release_task().  The underlying root of the problem isn't the
write-lock, per se, but the fact that the write-lock is being starved by
all the read-lockers (not all of whom are searching the entire task
list, BTW).  AIM7 is particularly nasty in this way because of the
"signal_test" subtest that uses a flurry of kill() signals and keeps
kill_something_info/kill_proc_info busy holding the tasklist_lock.  It
will be interesting to see how much of the contention is improved in
2.5.  You won't see this level of contention until you get well above
8p.

> Could you publish your lockmeter results ? Some of these problems may
> have been solved in 2.5.

This is the interesting parts of Lockmeter for "modified AIM7" (the
"workfile.shared" workload, minus the sync_* subtests and a few other
subtests that tend to saturate disk spindles, thus making this
"modified" workload compute-bound on a single-disk system), 1000 tasks,
32p, 2.4.19 + O(1) + various other spinlock improvements (e.g.,
"bkl_rollup"):

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - -
SPINLOCKS         HOLD            WAIT
  UTIL  CON    MEAN(  MAX )   MEAN(  MAX )(% CPU)     TOTAL NOWAIT SPIN
RJECT  NAME

        5.3%  4.9us( 579ms)  160us( 575ms)(17.2%) 970466006 94.7%  5.3%
0.00%  *TOTAL*

  4.6%  5.9%  2.6us(6964us)   17us(6257us)(0.06%)  26894060 94.1%  5.9%
0%  dcache_lock
18.0% 14.3%   20us( 579ms)  303us( 575ms)( 1.2%)  13159144 85.7% 14.3%
0%  kernel_flag
 18.6% 41.0%  3.4us(1888us)  190us(  13ms)(13.4%)  82406044 59.0% 41.0%
0%  pagecache_lock_cacheline
 0.02% 0.80%  6.9us( 169us)    0us                    50433 99.2%    0%
0.80%  load_balance+0x4c0
 0.00% 68.2%   14us( 315us)  105us(3151us)(0.00%)       170 31.8% 68.2%
0%  load_balance+0x510
 0.00%  2.4%   16us(  90us)   14us(  29us)(0.00%)       170 97.6%  2.4%
0%  load_balance+0x520
 0.00% 67.1%  7.2us(  50us)   66us(3295us)(0.00%)       231 32.9% 67.1%
0%  load_balance+0x5a0

- - - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - -
 - - - - - - - - - - - - - - - - - - - - - -
RWLOCK READS   HOLD    MAX  RDR BUSY PERIOD      WAIT
  UTIL  CON    MEAN   RDRS   MEAN(  MAX )   MEAN(  MAX )( %CPU)
TOTAL NOWAIT SPIN  NAME

       0.53%                                17us(4367us)(0.02%)
112496247 99.5% 0.53%  *TOTAL*

 27.1%  6.5% 379.2us??  26  116us( 461ms)   22us(4367us)(0.02%)
5647362 93.5%  6.5%  tasklist_lock
        1.1%                                32us(3603us)(0.00%)
447617 98.9%  1.1%    exit_notify+0x30
          0%                                 0us
2  100%    0%    exit_notify+0x260
        3.9%                                18us(  88us)(0.00%)
620 96.1%  3.9%    get_pid+0xe0
        1.4%                                20us(  77us)(0.00%)
2782 98.6%  1.4%    get_pid_list+0x30
        1.7%                                21us(2856us)(0.00%)
3719000 98.3%  1.7%    kill_something_info+0x220
        1.7%                                28us(2554us)(0.00%)
91057 98.3%  1.7%    proc_pid_lookup+0x230
        1.5%                                23us(1015us)(0.00%)
53727 98.5%  1.5%    proc_pid_stat+0x2d0
        9.1%                               2.6us( 2.6us)(0.00%)
11 90.9%  9.1%    session_of_pgrp+0x30
          0%                                 0us
4  100%    0%    sys_setpgid+0x70
        2.7%                                38us(  38us)(0.00%)
37 97.3%  2.7%    sys_setsid+0x30
       22.2%                                22us(4367us)(0.01%)
1332503 77.8% 22.2%    sys_wait4+0xc0
       50.0%                                11us(  11us)(0.00%)
2 50.0% 50.0%    will_become_orphaned_pgrp+0x20

- - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - - -
 - - - - - - - - - - - - - - - - - - - - - - - - - -
RWLOCK WRITES     HOLD           WAIT (ALL)           WAIT (WW)
  UTIL  CON    MEAN(  MAX )   MEAN(  MAX )( %CPU)   MEAN(  MAX )
TOTAL NOWAIT SPIN(  WW )  NAME

        4.4%  2.6us(  23ms)  865us( 461ms)( 1.5%)   60us(  12ms)
18497446 95.6%  3.3%( 1.1%)  *TOTAL*

 0.92% 45.8%   10us(4364us) 1138us( 461ms)( 1.5%)   69us(  12ms)
1341482 54.2% 32.4%(13.4%)  tasklist_lock
 0.18% 28.9%  6.1us( 158us) 1595us( 461ms)(0.43%)   34us(  12ms)
446225 71.1% 25.0%( 3.9%)    do_fork+0xf50
 0.62% 80.4%   21us(4364us) 1076us( 460ms)(0.81%)   83us(8920us)
447618 19.6% 55.2%(25.2%)    exit_notify+0x450
 0.11% 28.0%  3.8us( 192us)  847us( 434ms)(0.22%)   49us(9584us)
447639 72.0% 16.9%(11.1%)    release_task+0x1d0


John Hawkes

>> You need to backport some of the tasklist_lock-abuse-prevention work
>> in 2.5. The one that comes to the top of my mind is proc_read_super()
>> that walked the entire tasklist to count the number of tasks.
> 
> The tasklist_lock contention problems I'm seeing for ["modified"] AIM7
> are the write_lock_irq(&tasklist_lock) in do_fork(), exit_notify(), and
> release_task().  The underlying root of the problem isn't the
> write-lock, per se, but the fact that the write-lock is being starved by
> all the read-lockers (not all of whom are searching the entire task
> list, BTW).  AIM7 is particularly nasty in this way because of the
> "signal_test" subtest that uses a flurry of kill() signals and keeps
> kill_something_info/kill_proc_info busy holding the tasklist_lock.  It
> will be interesting to see how much of the contention is improved in
> 2.5.  You won't see this level of contention until you get well above
> 8p.

Could you modify the rwlock implementation to be fair in queuing readers
and writers, rather than reader-favouring? (solving the contention is
better still ;-))

M.

On Tue, Feb 04, 2003 at 09:15:48AM -0800, John Hawkes wrote:
> The tasklist_lock contention problems I'm seeing for ["modified"] AIM7
> are the write_lock_irq(&tasklist_lock) in do_fork(), exit_notify(), and
> release_task().  The underlying root of the problem isn't the
> write-lock, per se, but the fact that the write-lock is being starved by
> all the read-lockers (not all of whom are searching the entire task
> list, BTW).  AIM7 is particularly nasty in this way because of the
> "signal_test" subtest that uses a flurry of kill() signals and keeps
> kill_something_info/kill_proc_info busy holding the tasklist_lock.  It
> will be interesting to see how much of the contention is improved in
> 2.5.  You won't see this level of contention until you get well above
> 8p.

How realistic is a workload that sends a signal to every task in
the system ? Do we really want to optimize for such a thing ?

I am running SDET on a 16-processor NUMA-Q and I don't see a
contention problem with tasklist_lock.

> - - - - - - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - -
>  - - - - - - - - - - - - - - - - - - - - - -
> RWLOCK READS   HOLD    MAX  RDR BUSY PERIOD      WAIT
>   UTIL  CON    MEAN   RDRS   MEAN(  MAX )   MEAN(  MAX )( %CPU)
> TOTAL NOWAIT SPIN  NAME
> 
>        0.53%                                17us(4367us)(0.02%)
> 112496247 99.5% 0.53%  *TOTAL*
> 
>  27.1%  6.5% 379.2us??  26  116us( 461ms)   22us(4367us)(0.02%)
> 5647362 93.5%  6.5%  tasklist_lock
>         1.1%                                32us(3603us)(0.00%)
> 447617 98.9%  1.1%    exit_notify+0x30
>           0%                                 0us
> 2  100%    0%    exit_notify+0x260
>         3.9%                                18us(  88us)(0.00%)
> 620 96.1%  3.9%    get_pid+0xe0
>         1.4%                                20us(  77us)(0.00%)
> 2782 98.6%  1.4%    get_pid_list+0x30
>         1.7%                                21us(2856us)(0.00%)
> 3719000 98.3%  1.7%    kill_something_info+0x220
>         1.7%                                28us(2554us)(0.00%)
> 91057 98.3%  1.7%    proc_pid_lookup+0x230
>         1.5%                                23us(1015us)(0.00%)
> 53727 98.5%  1.5%    proc_pid_stat+0x2d0
>         9.1%                               2.6us( 2.6us)(0.00%)
> 11 90.9%  9.1%    session_of_pgrp+0x30
>           0%                                 0us
> 4  100%    0%    sys_setpgid+0x70
>         2.7%                                38us(  38us)(0.00%)
> 37 97.3%  2.7%    sys_setsid+0x30
>        22.2%                                22us(4367us)(0.01%)
> 1332503 77.8% 22.2%    sys_wait4+0xc0
>        50.0%                                11us(  11us)(0.00%)
> 2 50.0% 50.0%    will_become_orphaned_pgrp+0x20

Your mailer is mangling them :(
I am not sure I am getting the numbers right.

Thanks
Dipankar

On Monday 03 February 2003 07:36 pm, Jack Steiner wrote:
> I wonder if a better algorithm might be one that disabled interrupts,
> then spun in a tight loop trying to set the lock.
> Periodically, enable/disable interrupts. For example:
>
> 	disable_ints
> 	do {
> 		if (cmpxchg successful)
> 			break
>
> 		i=0
> 		while(lock is set) {
> 			if (i++ == XXX) { 	// pick XXX so that interrupts are
> 				enable_ints	//   enabled every few usec
> 				i=0
> 				disable_ints
> 			}
> 		}
> 	}

This is the part of John's patch that I liked, enabling interrupts for 
spinlock_irq().  Of course, trying removing lock contention in the first 
place is a good thing, but that doesn't seem sufficient all by itself.  For 
some workloads, some locks are going to be subject to heavy contention even 
if the algorithms are well designed, and having interrupts periodically 
enabled seems like a win for those cases.

Jesse

From: "Martin J. Bligh" <mbligh@...>
> Could you modify the rwlock implementation to be fair in queuing
readers
> and writers, rather than reader-favouring? (solving the contention is
> better still ;-))

I tried that (the former, not the latter).  It didn't make much
difference, at least for the algorithm I tried.  I had the first writer
set a flag in the rwlock to indicate that it wanted to acquire for
write-access, then subsequently arriving read-lockers would spin waiting
for the writer to acquire-then-release, instead of piggybacking on the
other readers, and subsequently arriving write-lockers would also spin
(as they do with the traditional write_lock).  When the current readers
all unlocked, then that initial write-locker gets the lock, does its
work, then unlocks -- and everyone, writers and readers alike, become a
thundering herd again, trying to acquire the rwlock.

Perhaps a better algorithm would be to implement a true queue of
waiters, but that imposes a lot of overhead.  I agree that the best
strategy is to reduce the usage and hold-times, rather than fussing with
fairness algorithms.

John Hawkes

> How realistic is a workload that sends a signal to every task in
> the system ? Do we really want to optimize for such a thing ?

It's not "every task in the system", but that's a quibble.  Think of it
as "every task in the multithreaded application."  But your point still
stands.  No, we don't want to optimize for pathological cases, though
the usefulness of some of these pathological workloads is to illuminate
problems.

John Hawkes

Hi,

> I tried that (the former, not the latter).  It didn't make much
> difference, at least for the algorithm I tried.  I had the first writer
> set a flag in the rwlock to indicate that it wanted to acquire for
> write-access, then subsequently arriving read-lockers would spin waiting
> for the writer to acquire-then-release, instead of piggybacking on the
> other readers, and subsequently arriving write-lockers would also spin
> (as they do with the traditional write_lock).  When the current readers
> all unlocked, then that initial write-locker gets the lock, does its
> work, then unlocks -- and everyone, writers and readers alike, become a
> thundering herd again, trying to acquire the rwlock.

There is code in the kernel that relies on recursive readers working. If
writers set a pending bit to prevent new readers from getting the lock bad
things could happen.

I hunted down a lockup in sparc64 ages ago that was caused by our rwlocks
being fair.

Anton

From: "Anton Blanchard" <anton@...>
> There is code in the kernel that relies on recursive readers working.
If
> writers set a pending bit to prevent new readers from getting the lock
bad
> things could happen.

Some rwlocks require recursive read-lock capability, though others
don't.  I'll agree that all rwlocks cannot be altered to block readers
once a write declares its intention to write-lock.

John Hawkes

Martin J. Bligh wrote:
>>>You need to backport some of the tasklist_lock-abuse-prevention work
>>>in 2.5. The one that comes to the top of my mind is proc_read_super()
>>>that walked the entire tasklist to count the number of tasks.
>>
>>The tasklist_lock contention problems I'm seeing for ["modified"] AIM7
>>are the write_lock_irq(&tasklist_lock) in do_fork(), exit_notify(), and
>>release_task().  The underlying root of the problem isn't the
>>write-lock, per se, but the fact that the write-lock is being starved by
>>all the read-lockers (not all of whom are searching the entire task
>>list, BTW).  AIM7 is particularly nasty in this way because of the
>>"signal_test" subtest that uses a flurry of kill() signals and keeps
>>kill_something_info/kill_proc_info busy holding the tasklist_lock.  It
>>will be interesting to see how much of the contention is improved in
>>2.5.  You won't see this level of contention until you get well above
>>8p.
> 
> 
> Could you modify the rwlock implementation to be fair in queuing readers
> and writers, rather than reader-favouring? (solving the contention is
> better still ;-))
> 
I can think of some cases where favouring the writer is the better 
thing (the xtime lock comes to mind).
-g
> M.
> 
> 
> 
> -------------------------------------------------------
> This SF.NET email is sponsored by:
> SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See!
> http://www.vasoftware.com
> _______________________________________________
> Lse-tech mailing list
> Lse-tech@...
> https://lists.sourceforge.net/lists/listinfo/lse-tech
> 
> 

-- 
George Anzinger   george@...
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

From: "george anzinger" <george@...>
> I can think of some cases where favouring the writer is the better
> thing (the xtime lock comes to mind).

We have had great success in converting the xtime_lock into an frlock --
a lockless read.  We're playing with the memory barriers in
include/linux/frlock.h, though, beyond what was recently posted to
linux-kernel.

John Hawkes

>>>> You need to backport some of the tasklist_lock-abuse-prevention work
>>>> in 2.5. The one that comes to the top of my mind is proc_read_super()
>>>> that walked the entire tasklist to count the number of tasks.
>>> 
>>> The tasklist_lock contention problems I'm seeing for ["modified"] AIM7
>>> are the write_lock_irq(&tasklist_lock) in do_fork(), exit_notify(), and
>>> release_task().  The underlying root of the problem isn't the
>>> write-lock, per se, but the fact that the write-lock is being starved by
>>> all the read-lockers (not all of whom are searching the entire task
>>> list, BTW).  AIM7 is particularly nasty in this way because of the
>>> "signal_test" subtest that uses a flurry of kill() signals and keeps
>>> kill_something_info/kill_proc_info busy holding the tasklist_lock.  It
>>> will be interesting to see how much of the contention is improved in
>>> 2.5.  You won't see this level of contention until you get well above
>>> 8p.
>> 
>> 
>> Could you modify the rwlock implementation to be fair in queuing readers
>> and writers, rather than reader-favouring? (solving the contention is
>> better still ;-))
>> 
> I can think of some cases where favouring the writer is the better thing (the xtime lock comes to mind).

I was really thinking of just for that instance, ie you'd have a choice
of fair and unfair versions ... but my comment was poorly enough phrased,
it's very hard to tell that's what I meant ;-)

M.

On Wed, 2003-02-05 at 17:15, John Hawkes wrote:
> From: "george anzinger" <george@...>
> > I can think of some cases where favouring the writer is the better
> > thing (the xtime lock comes to mind).
>=20
> We have had great success in converting the xtime_lock into an frlock -=
-
> a lockless read.  We're playing with the memory barriers in
> include/linux/frlock.h, though, beyond what was recently posted to
> linux-kernel.

Seqlock (n=C3=A9e frlock) is now in 2.5.59 bitkeeper tree.
The barriers used has been through much scrutiny and review (including
disasembly) but if you see anything, let me know.

John Hawkes wrote:
> 
> 
> I have observed some interrupts-disabled periods of several hundred
> milliseconds for some locks, and many occurrences of 10-30 milliseconds
> of interrupts-disabled periods for several locks.  (SGI Itanium 2 NUMA
> systems, to be specific.)
> 
> An effective solution is an interrupt-friendly locking scheme, such as:
>   do { disable_interrupts;
>          if (try_to_acquire_lock)
>              break;
>          else
>               enable_interrupts;
>   } while (1)
> 

Fixing the source of the lock contention is the "right" approach. 

But, spinning with ints disabled is "wasted" CPU when there
may be external ints pending.

spin_lock_irqsave() can reenable ints if the lock is owned
and ints were enabled when the lock was attempted.  There
would be no code growth in some cases because (2) pad bytes
could be replaced with a push <register> and popf to restore
the state of the int flag.

dumpobj -d sched.o

Here is some code from __wake_up_sync on ia32 :

void __wake_up_sync ...

spin_lock_irqsave(&q->lock, flags);
...

140b:   9c                pushf  
140c:   5e                pop %esi
140d:   fa                cli    
140e:   fo fe 0b          lock decb (%ebx)
1411:   0f 88 09 17 00 00 js     2b20 <.text.lock.sched+0xc4>

remove the (2) pad bytes at 2b20
2b20:   f3 90             repz nop  <-- remove this

replace with the next (2) opcodes
2b20    56                push esi  <-- add this
2b21    9d                popf      <-- add this

2b22:   80 3b 00          cmpb   $0x0,(%ebx)
2b25:   0f 8e f5 ff ff ff jle    2b20 <.text.lock.sched+0xc4>

change the following to jmp to 140d instead of 140e
2b2b:   e9 de e8 ff ff    jmp    140e <__wake_up_sync+0xe>

-Bill