filtered wakeups

PATCH In review William Lee Irwin III 2 participants 6 messages May 3, 2004

Subsystems (13)

Memory management Arm (32-bit) VFS Library code +9 more subsystems

lore

Share & tools

lore

William Lee Irwin III

author

2004-05-03 02:17 UTC #0 lore raw

cover filtered wakeups

The thundering herd issue in waitqueue hashing has been seen in practice. In order to preserve the space footprint reduction while improving performance, I wrote "filtered wakeups", which discriminate between waiters based on a key.

The following patch series, vs. 2.6.6-rc3-mm1, drastically reduces the kernel cpu consumption of tiobench --threads 512 --size 16384 (fed to tiotest by hand since apparently the perl script is buggy) on a 6x336MHz UltraSPARC III Sun Enterprise 3000 with 3.5GB RAM, ESP-366HME HBA, 10x10Krpm 18GB U160 SCSI disks configured for dm thusly:

0 355655680 striped 10 64 /dev/sda 0 /dev/sdb 0 /dev/sdc 0 /dev/sdd 0 \
	/dev/sde 0 /dev/sdf 0 /dev/sdg 0 /dev/sdh 0 /dev/sdi 0 /dev/sdj 0

This was mkfs'd freshly to a single 171GB ext2 fs.

1/2, filtered page waitqueues, resolves the thundering herd issue with
hashed page waitqueues.
2/2, filtered buffer_head waitqueues, resolves the thundering herd issue
with hashed buffer_head waitqueues.
Futexes appear to have their own solution to this issue, which is necessarily different from this as it needs to discriminate based on a longer key. They could in principle be consolidated by passing a comparator instead of comparing a key field or some similar strategy at the cost of indirect function calls.

I furthermore instrumented the calls to schedule(), possibly done
indirectly, in patch 0.5/2 of the series, which isn't necessarily meant
to be applied to anything, but merely shows how I collected some of the information in the runtime logs, which for space reasons I've posted as
URL's instead of including them inline. ftp://ftp.kernel.org/pub/linux/kernel/people/wli/vm/filtered_wakeup/virgin_mm.log.tar.bz2 ftp://ftp.kernel.org/pub/linux/kernel/people/wli/vm/filtered_wakeup/filtered_wakeup.log.tar.bz2

Here "cpusec" represents 1 second of actual cpu consumed, counting cpu consumption of both user and kernel. Apart from regular sampling of profile data, no other load was running on the machine.

before:
Tiotest results for 512 concurrent io threads:
,----------------------------------------------------------------------.

| Item                  | Time     | Rate         | Usr CPU  | Sys CPU |
+-----------------------+----------+--------------+----------+---------+
| Write       16384 MBs | 1118.1 s |  14.654 MB/s |   1.6 %  | 280.9 % |
| Random Write 2000 MBs |  336.2 s |   5.950 MB/s |   0.8 %  |  20.4 % |
| Read        16384 MBs | 1717.1 s |   9.542 MB/s |   1.4 %  |  31.8 % |
| Random Read  2000 MBs |  465.2 s |   4.300 MB/s |   1.1 %  |  36.1 % |

`----------------------------------------------------------------------'

Throughput scaled by %cpu:

Write:            5.1873MB/cpusec
Random Write:    28.0660MB/cpusec
Read:            28.7410MB/cpusec
Random Read:     11.5591MB/cpusec

top 10 kernel cpu consumers:
21733 finish_task_switch 113.1927
11976 __wake_up 187.1250
11433 generic_file_aio_write_nolock 5.0321

  9730 read_sched_profile                        43.4375
  9606 file_read_actor                           42.8839
  9116 __do_softirq                              31.6528
  8682 do_anonymous_page                         19.3795
  3635 prepare_to_wait                           28.3984
  2159 kmem_cache_free                           16.8672

1944 buffered_rmqueue 3.3750

top 10 callers of scheduling functions:

9391185 wait_on_page_bit                         32608.2812
7280055 cpu_idle                                 37916.9531
1458446 __lock_page                              5064.0486
258142 __handle_preemption                      16133.8750
134815 worker_thread                            247.8217
 45989 __wait_on_buffer                         205.3080

22294 do_exit 21.7715
22187 generic_file_aio_write_nolock 9.7654
14932 sys_wait4 25.9236
14652 shrink_list 7.8944

after:
Tiotest results for 512 concurrent io threads:
,----------------------------------------------------------------------.

| Item                  | Time     | Rate         | Usr CPU  | Sys CPU |
+-----------------------+----------+--------------+----------+---------+
| Write       16384 MBs | 1099.5 s |  14.901 MB/s |   2.2 %  | 279.3 % |
| Random Write 2000 MBs |  333.8 s |   5.991 MB/s |   1.0 %  |  14.9 % |
| Read        16384 MBs | 1706.3 s |   9.602 MB/s |   1.4 %  |  19.1 % |
| Random Read  2000 MBs |  460.3 s |   4.345 MB/s |   1.1 %  |  14.8 % |

`----------------------------------------------------------------------'

Throughput scaled by %cpu:

Write:            5.2934MB/cpusec
Random Write:    37.6792MB/cpusec
Read:            46.8390MB/cpusec
Random Read:     27.3270MB/cpusec

top 10 kernel cpu consumers:
11873 generic_file_aio_write_nolock 5.2258

 10245 file_read_actor                           45.7366
 10212 read_sched_profile                        45.5893
 10135 finish_task_switch                        52.7865
  9171 do_anonymous_page                         20.4710
  8619 __do_softirq                              29.9271
  2905 wake_up_filtered                          18.1562
  2325 __get_page_state                          10.3795

2278 del_timer_sync 5.0848
2033 buffered_rmqueue 3.5295

top 10 callers of scheduling functions:
3985424 cpu_idle 20757.4167
2396754 wait_on_page_bit 7489.8562
209453 __handle_preemption 13090.8125
164071 worker_thread 301.6011
24321 do_exit 23.7510
21272 generic_file_aio_write_nolock 9.3627

 16271 sys_wait4                                 28.2483
 11080 pipe_wait                                 86.5625
  9634 compat_sys_nanosleep                      25.0885

7742 shrink_list 4.1713

-- wli

William Lee Irwin III

author

2004-05-03 02:24 UTC #1 lore raw

[0.5/2] scheduler caller profiling

Quoted 4 lines · William Lee Irwin III

The thundering herd issue in waitqueue hashing has been seen in practice. In order to preserve the space footprint reduction while improving performance, I wrote "filtered wakeups", which discriminate between waiters based on a key.

This patch was used to collect the data on the offending callers into the scheduler. It creates a profile buffer completely analogous to its handling to /proc/profile, but registers profile ticks at calls to the various scheduler entry points instead of during timer ticks and rearranges scheduler code for this to be accounted properly. It does not report meaningful statistics in the presence of CONFIG_PREEMPT.

Posting this patch is in order to disclose how I obtained the scheduling statistics reported in the first post. This patch is not intended for inclusion.

-- wli

include/linux/sched.h +4 -0

Index: wli-2.6.6-rc3-mm1/include/linux/sched.h
===================================================================
@@ -189,7 +189,11 @@
 
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
+extern signed long FASTCALL(__schedule_timeout(signed long timeout));
 asmlinkage void schedule(void);
+asmlinkage void __schedule(void);
+void __sched_profile(void *);
+#define sched_profile()		__sched_profile(__builtin_return_address(0))
 
 struct namespace;

include/linux/profile.h +1 -0

Index: wli-2.6.6-rc3-mm1/include/linux/profile.h
===================================================================
@@ -13,6 +13,7 @@
 
 /* init basic kernel profiler */
 void __init profile_init(void);
+void schedprof_init(void);
 
 extern unsigned int * prof_buffer;
 extern unsigned long prof_len;

kernel/sched.c +124 ~~-13~~

225 lines not on this page · raw message

kernel/timer.c +8 -3

Index: wli-2.6.6-rc3-mm1/kernel/timer.c
===================================================================
@@ -1065,7 +1065,7 @@
  *
  * In all cases the return value is guaranteed to be non-negative.
  */
-fastcall signed long __sched schedule_timeout(signed long timeout)
+fastcall signed long __sched __schedule_timeout(signed long timeout)
 {
 	struct timer_list timer;
 	unsigned long expire;

@@ -1080,7 +1080,7 @@
 		 * but I' d like to return a valid offset (>=0) to allow
 		 * the caller to do everything it want with the retval.
 		 */
-		schedule();
+		__schedule();
 		goto out;
 	default:
 		/*

@@ -1108,7 +1108,7 @@
 	timer.function = process_timeout;
 
 	add_timer(&timer);
-	schedule();
+	__schedule();
 	del_timer_sync(&timer);
 
 	timeout = expire - jiffies;

@@ -1117,6 +1117,11 @@
 	return timeout < 0 ? 0 : timeout;
 }
 
+fastcall signed long __sched schedule_timeout(signed long timeout)
+{
+	sched_profile();
+	return __schedule_timeout(timeout);
+}
 EXPORT_SYMBOL(schedule_timeout);
 
 /* Thread ID - the internal kernel "pid" */

arch/alpha/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/alpha/kernel/semaphore.c
===================================================================
@@ -66,7 +66,6 @@
 {
 	struct task_struct *tsk = current;
 	DECLARE_WAITQUEUE(wait, tsk);
-
 #ifdef CONFIG_DEBUG_SEMAPHORE
 	printk("%s(%d): down failed(%p)\n",
 	       tsk->comm, tsk->pid, sem);

@@ -83,7 +82,8 @@
 	 * that we are asleep, and then sleep.
 	 */
 	while (__sem_update_count(sem, -1) <= 0) {
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}
 	remove_wait_queue(&sem->wait, &wait);

@@ -108,7 +108,6 @@
 	struct task_struct *tsk = current;
 	DECLARE_WAITQUEUE(wait, tsk);
 	long ret = 0;
-
 #ifdef CONFIG_DEBUG_SEMAPHORE
 	printk("%s(%d): down failed(%p)\n",
 	       tsk->comm, tsk->pid, sem);

@@ -129,7 +128,8 @@
 			ret = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_INTERRUPTIBLE);
 	}

arch/arm/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/arm/kernel/semaphore.c
===================================================================
@@ -77,8 +77,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

@@ -127,8 +127,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

arch/arm26/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/arm26/kernel/semaphore.c
===================================================================
@@ -79,8 +79,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

@@ -129,8 +129,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

arch/cris/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/cris/kernel/semaphore.c
===================================================================
@@ -101,7 +101,8 @@
 	DOWN_HEAD(TASK_UNINTERRUPTIBLE)
 	if (waking_non_zero(sem))
 		break;
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_UNINTERRUPTIBLE)
 }

@@ -119,7 +120,8 @@
 			ret = 0;
 		break;
 	}
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_INTERRUPTIBLE)
 	return ret;
 }

arch/h8300/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/h8300/kernel/semaphore.c
===================================================================
@@ -103,7 +103,8 @@
 	DOWN_HEAD(TASK_UNINTERRUPTIBLE)
 	if (waking_non_zero(sem))
 		break;
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_UNINTERRUPTIBLE)
 }

@@ -122,7 +123,8 @@
 			ret = 0;
 		break;
 	}
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_INTERRUPTIBLE)
 	return ret;
 }

arch/i386/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/i386/kernel/semaphore.c
===================================================================
@@ -79,8 +79,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_UNINTERRUPTIBLE;

@@ -132,8 +132,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_INTERRUPTIBLE;

arch/ia64/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/ia64/kernel/semaphore.c
===================================================================
@@ -70,8 +70,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_UNINTERRUPTIBLE;

@@ -123,8 +123,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_INTERRUPTIBLE;

arch/m68k/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/m68k/kernel/semaphore.c
===================================================================
@@ -103,7 +103,8 @@
 	DOWN_HEAD(TASK_UNINTERRUPTIBLE)
 	if (waking_non_zero(sem))
 		break;
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_UNINTERRUPTIBLE)
 }

@@ -122,7 +123,8 @@
 			ret = 0;
 		break;
 	}
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_INTERRUPTIBLE)
 	return ret;
 }

arch/m68knommu/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/m68knommu/kernel/semaphore.c
===================================================================
@@ -104,7 +104,8 @@
 	DOWN_HEAD(TASK_UNINTERRUPTIBLE)
 	if (waking_non_zero(sem))
 		break;
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_UNINTERRUPTIBLE)
 }

@@ -123,7 +124,8 @@
 			ret = 0;
 		break;
 	}
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_INTERRUPTIBLE)
 	return ret;
 }

arch/mips/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/mips/kernel/semaphore.c
===================================================================
@@ -132,7 +132,8 @@
 	for (;;) {
 		if (waking_non_zero(sem))
 			break;
-		schedule();
+		sched_profile();
+		__schedule();
 		__set_current_state(TASK_UNINTERRUPTIBLE);
 	}
 	__set_current_state(TASK_RUNNING);

@@ -261,7 +262,8 @@
 				ret = 0;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		__set_current_state(TASK_INTERRUPTIBLE);
 	}
 	__set_current_state(TASK_RUNNING);

arch/parisc/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/parisc/kernel/semaphore.c
===================================================================
@@ -68,7 +68,8 @@
 		/* we can _read_ this without the sentry */
 		if (sem->count != -1)
 			break;
- 		schedule();
+		sched_profile();
+ 		__schedule();
  	}
 
 	DOWN_TAIL

@@ -89,7 +90,8 @@
 			ret = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 	}
 
 	DOWN_TAIL

arch/ppc/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/ppc/kernel/semaphore.c
===================================================================
@@ -86,7 +86,8 @@
 	 * that we are asleep, and then sleep.
 	 */
 	while (__sem_update_count(sem, -1) <= 0) {
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 	}
 	remove_wait_queue(&sem->wait, &wait);

@@ -121,7 +122,8 @@
 			retval = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 	}
 	tsk->state = TASK_RUNNING;

arch/ppc64/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/ppc64/kernel/semaphore.c
===================================================================
@@ -86,7 +86,8 @@
 	 * that we are asleep, and then sleep.
 	 */
 	while (__sem_update_count(sem, -1) <= 0) {
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}
 	remove_wait_queue(&sem->wait, &wait);

@@ -120,7 +121,8 @@
 			retval = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_INTERRUPTIBLE);
 	}
 	remove_wait_queue(&sem->wait, &wait);

arch/s390/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/s390/kernel/semaphore.c
===================================================================
@@ -69,7 +69,8 @@
 	__set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	add_wait_queue_exclusive(&sem->wait, &wait);
 	while (__sem_update_count(sem, -1) <= 0) {
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}
 	remove_wait_queue(&sem->wait, &wait);

@@ -97,7 +98,8 @@
 			retval = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		set_task_state(tsk, TASK_INTERRUPTIBLE);
 	}
 	remove_wait_queue(&sem->wait, &wait);

arch/sh/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/sh/kernel/semaphore.c
===================================================================
@@ -110,7 +110,8 @@
 	DOWN_HEAD(TASK_UNINTERRUPTIBLE)
 	if (waking_non_zero(sem))
 		break;
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_UNINTERRUPTIBLE)
 }

@@ -128,7 +129,8 @@
 			ret = 0;
 		break;
 	}
-	schedule();
+	sched_profile();
+	__schedule();
 	DOWN_TAIL(TASK_INTERRUPTIBLE)
 	return ret;
 }

arch/sparc/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/sparc/kernel/semaphore.c
===================================================================
@@ -68,8 +68,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

@@ -118,8 +118,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

arch/sparc64/kernel/semaphore.c +4 -2

Index: wli-2.6.6-rc3-mm1/arch/sparc64/kernel/semaphore.c
===================================================================
@@ -100,7 +100,8 @@
 	add_wait_queue_exclusive(&sem->wait, &wait);
 
 	while (__sem_update_count(sem, -1) <= 0) {
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 	}
 	remove_wait_queue(&sem->wait, &wait);

@@ -208,7 +209,8 @@
 			retval = -EINTR;
 			break;
 		}
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 	}
 	tsk->state = TASK_RUNNING;

arch/v850/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/v850/kernel/semaphore.c
===================================================================
@@ -79,8 +79,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

@@ -129,8 +129,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irq(&semaphore_lock);
-
-		schedule();
+		sched_profile();
+		__schedule();
 		tsk->state = TASK_INTERRUPTIBLE;
 		spin_lock_irq(&semaphore_lock);
 	}

arch/x86_64/kernel/semaphore.c +4 -4

Index: wli-2.6.6-rc3-mm1/arch/x86_64/kernel/semaphore.c
===================================================================
@@ -80,8 +80,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_UNINTERRUPTIBLE;

@@ -133,8 +133,8 @@
 		}
 		sem->sleepers = 1;	/* us - see -1 above */
 		spin_unlock_irqrestore(&sem->wait.lock, flags);
-
-		schedule();
+		sched_profile();
+		__schedule();
 
 		spin_lock_irqsave(&sem->wait.lock, flags);
 		tsk->state = TASK_INTERRUPTIBLE;

lib/rwsem.c +3 -3

Index: wli-2.6.6-rc3-mm1/lib/rwsem.c
===================================================================
@@ -150,7 +150,7 @@
 	for (;;) {
 		if (!waiter->flags)
 			break;
-		schedule();
+		__schedule();
 		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
 	}

@@ -165,7 +165,7 @@
 struct rw_semaphore fastcall __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
 {
 	struct rwsem_waiter waiter;
-
+	sched_profile();
 	rwsemtrace(sem,"Entering rwsem_down_read_failed");
 
 	waiter.flags = RWSEM_WAITING_FOR_READ;

@@ -181,7 +181,7 @@
 struct rw_semaphore fastcall __sched *rwsem_down_write_failed(struct rw_semaphore *sem)
 {
 	struct rwsem_waiter waiter;
-
+	sched_profile();
 	rwsemtrace(sem,"Entering rwsem_down_write_failed");
 
 	waiter.flags = RWSEM_WAITING_FOR_WRITE;

init/main.c +1 -0

Index: wli-2.6.6-rc3-mm1/init/main.c
===================================================================
@@ -486,6 +486,7 @@
 	if (panic_later)
 		panic(panic_later, panic_param);
 	profile_init();
+	schedprof_init();
 	local_irq_enable();
 #ifdef CONFIG_BLK_DEV_INITRD
 	if (initrd_start && !initrd_below_start_ok &&

William Lee Irwin III

author

2004-05-03 02:29 UTC #2 lore raw

Re: [0.5/2] scheduler caller profiling

Quoted 2 lines · William Lee Irwin III

This patch was used to collect the data on the offending callers into the scheduler. It creates a profile buffer completely analogous to its

This patch creates a new scheduling entrypoint, wake_up_filtered(), and uses it in page waitqueue hashing to discriminate between the waiters on various pages. One of the sources of the thundering herds was identified as the page waitqueue hashing by a priori methods and empirically confirmed using the scheduler caller profiling patch.

-- wli

include/linux/wait.h +16 -0

Index: wli-2.6.6-rc3-mm1/include/linux/wait.h
===================================================================
@@ -28,6 +28,11 @@
 	struct list_head task_list;
 };
 
+struct filtered_wait_queue {
+	void *key;
+	wait_queue_t wait;
+};
+
 struct __wait_queue_head {
 	spinlock_t lock;
 	struct list_head task_list;

@@ -104,6 +109,7 @@
 	list_del(&old->task_list);
 }
 
+void FASTCALL(wake_up_filtered(wait_queue_head_t *, void *));
 extern void FASTCALL(__wake_up(wait_queue_head_t *q, unsigned int mode, int nr));
 extern void FASTCALL(__wake_up_locked(wait_queue_head_t *q, unsigned int mode));
 extern void FASTCALL(__wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr));

@@ -257,6 +263,16 @@
 		wait->func = autoremove_wake_function;			\
 		INIT_LIST_HEAD(&wait->task_list);			\
 	} while (0)
+
+#define DEFINE_FILTERED_WAIT(name, p)					\
+	struct filtered_wait_queue name = {				\
+		.key	= p,						\
+		.wait	=	{					\
+			.task	= current,				\
+			.func	= autoremove_wake_function,		\
+			.task_list = LIST_HEAD_INIT(name.wait.task_list),\
+		},							\
+	}
 	
 #endif /* __KERNEL__ */

kernel/sched.c +13 -0

Index: wli-2.6.6-rc3-mm1/kernel/sched.c
===================================================================
@@ -2524,6 +2524,19 @@
 	}
 }
 
+void fastcall wake_up_filtered(wait_queue_head_t *q, void *key)
+{
+	unsigned long flags;
+	unsigned int mode = TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE;
+	struct filtered_wait_queue *wait, *save;
+	spin_lock_irqsave(&q->lock, flags);
+	list_for_each_entry_safe(wait, save, &q->task_list, wait.task_list) {
+		if (wait->key == key)
+			wait->wait.func(&wait->wait, mode, 0);
+	}
+	spin_unlock_irqrestore(&q->lock, flags);
+}
+
 /**
  * __wake_up - wake up threads blocked on a waitqueue.
  * @q: the waitqueue

mm/filemap.c +8 -8

Index: wli-2.6.6-rc3-mm1/mm/filemap.c
===================================================================
@@ -307,16 +307,16 @@
 void fastcall wait_on_page_bit(struct page *page, int bit_nr)
 {
 	wait_queue_head_t *waitqueue = page_waitqueue(page);
-	DEFINE_WAIT(wait);
+	DEFINE_FILTERED_WAIT(wait, page);
 
 	do {
-		prepare_to_wait(waitqueue, &wait, TASK_UNINTERRUPTIBLE);
+		prepare_to_wait(waitqueue, &wait.wait, TASK_UNINTERRUPTIBLE);
 		if (test_bit(bit_nr, &page->flags)) {
 			sync_page(page);
 			io_schedule();
 		}
 	} while (test_bit(bit_nr, &page->flags));
-	finish_wait(waitqueue, &wait);
+	finish_wait(waitqueue, &wait.wait);
 }
 
 EXPORT_SYMBOL(wait_on_page_bit);

@@ -344,7 +344,7 @@
 		BUG();
 	smp_mb__after_clear_bit(); 
 	if (waitqueue_active(waitqueue))
-		wake_up_all(waitqueue);
+		wake_up_filtered(waitqueue, page);
 }
 
 EXPORT_SYMBOL(unlock_page);

@@ -363,7 +363,7 @@
 		smp_mb__after_clear_bit();
 	}
 	if (waitqueue_active(waitqueue))
-		wake_up_all(waitqueue);
+		wake_up_filtered(waitqueue, page);
 }
 
 EXPORT_SYMBOL(end_page_writeback);

@@ -379,16 +379,16 @@
 void fastcall __lock_page(struct page *page)
 {
 	wait_queue_head_t *wqh = page_waitqueue(page);
-	DEFINE_WAIT(wait);
+	DEFINE_FILTERED_WAIT(wait, page);
 
 	while (TestSetPageLocked(page)) {
-		prepare_to_wait(wqh, &wait, TASK_UNINTERRUPTIBLE);
+		prepare_to_wait(wqh, &wait.wait, TASK_UNINTERRUPTIBLE);
 		if (PageLocked(page)) {
 			sync_page(page);
 			io_schedule();
 		}
 	}
-	finish_wait(wqh, &wait);
+	finish_wait(wqh, &wait.wait);
 }
 
 EXPORT_SYMBOL(__lock_page);

William Lee Irwin III

author

2004-05-03 02:32 UTC #3 lore raw

PATCH 2/2 filtered buffer_head wakeups

Quoted 5 lines · William Lee Irwin III

This patch creates a new scheduling entrypoint, wake_up_filtered(), and uses it in page waitqueue hashing to discriminate between the waiters on various pages. One of the sources of the thundering herds was identified as the page waitqueue hashing by a priori methods and empirically confirmed using the scheduler caller profiling patch.

It turned out there were still thundering herds after the page waitqueue hashtable. The scheduler caller profiling patch identified this as the buffer_head waitqueue hashtable. This patch teaches the buffer_head waitqueue hashing to use filtered wakeups.

-- wli

fs/buffer.c +4 -4

Index: wli-2.6.6-rc3-mm1/fs/buffer.c
===================================================================
@@ -74,7 +74,7 @@
 
 	smp_mb();
 	if (waitqueue_active(wq))
-		wake_up_all(wq);
+		wake_up_filtered(wq, bh);
 }
 EXPORT_SYMBOL(wake_up_buffer);

@@ -93,10 +93,10 @@
 void __wait_on_buffer(struct buffer_head * bh)
 {
 	wait_queue_head_t *wqh = bh_waitq_head(bh);
-	DEFINE_WAIT(wait);
+	DEFINE_FILTERED_WAIT(wait, bh);
 
 	do {
-		prepare_to_wait(wqh, &wait, TASK_UNINTERRUPTIBLE);
+		prepare_to_wait(wqh, &wait.wait, TASK_UNINTERRUPTIBLE);
 		if (buffer_locked(bh)) {
 			struct block_device *bd;
 			smp_mb();

@@ -106,7 +106,7 @@
 			io_schedule();
 		}
 	} while (buffer_locked(bh));
-	finish_wait(wqh, &wait);
+	finish_wait(wqh, &wait.wait);
 }
 
 static void

fs/jbd/transaction.c +1 -1

Index: wli-2.6.6-rc3-mm1/fs/jbd/transaction.c
===================================================================
@@ -638,7 +638,7 @@
 			jbd_unlock_bh_state(bh);
 			/* commit wakes up all shadow buffers after IO */
 			wqh = bh_waitq_head(jh2bh(jh));
-			wait_event(*wqh, (jh->b_jlist != BJ_Shadow));
+			wait_event_filtered(*wqh, jh2bh(jh), (jh->b_jlist != BJ_Shadow));
 			goto repeat;
 		}

include/linux/wait.h +22 -2

Index: wli-2.6.6-rc3-mm1/include/linux/wait.h
===================================================================
@@ -146,7 +146,6 @@
 		break;							\
 	__wait_event(wq, condition);					\
 } while (0)
-
 #define __wait_event_interruptible(wq, condition, ret)			\
 do {									\
 	wait_queue_t __wait;						\

@@ -273,7 +272,28 @@
 			.task_list = LIST_HEAD_INIT(name.wait.task_list),\
 		},							\
 	}
-	
+
+#define __wait_event_filtered(wq, key, condition) 			\
+do {									\
+	DEFINE_FILTERED_WAIT(__wait, key);				\
+	add_wait_queue(&(wq), &__wait.wait);				\
+	for (;;) {							\
+		set_current_state(TASK_UNINTERRUPTIBLE);		\
+		if (condition)						\
+			break;						\
+		schedule();						\
+	}								\
+	current->state = TASK_RUNNING;					\
+	remove_wait_queue(&(wq), &__wait.wait);				\
+} while (0)
+
+
+#define wait_event_filtered(wq, key, condition)				\
+do {									\
+	if (!(condition))						\
+		__wait_event_filtered(wq, key, condition);		\
+} while (0)
+
 #endif /* __KERNEL__ */
 
 #endif

David Mosberger

2004-05-03 18:52 UTC #4 lore raw

Re: [0.5/2] scheduler caller profiling

In reply to William Lee Irwin III

Bill> On Sun, May 02, 2004 at 07:17:09PM -0700, William Lee Irwin

Quoted 4 lines · Bill> III wrote:

Quoted 4 lines
The thundering herd issue in waitqueue hashing has been seen in practice. In order to preserve the space footprint reduction while improving performance, I wrote "filtered wakeups", which discriminate between waiters based on a key.

Bill> This patch was used to collect the data on the offending Bill> callers into the scheduler. It creates a profile buffer Bill> completely analogous to its handling to /proc/profile, but Bill> registers profile ticks at calls to the various scheduler Bill> entry points instead of during timer ticks and rearranges Bill> scheduler code for this to be accounted properly. It does not Bill> report meaningful statistics in the presence of Bill> CONFIG_PREEMPT.

Bill> Posting this patch is in order to disclose how I obtained the Bill> scheduling statistics reported in the first post. This patch Bill> is not intended for inclusion.

Note that on ia64, you can use q-syscollect/q-view to collect call-counts statistically (with zero intrusion to the monitored program, so it's safe for the kernel). While the call-graph/counts won't be perfectly accurate, this has proven to work extremely well in practice. In fact, it would be nice if other arches could support the same. All you really need for this to work is the ability to count N call (or return) instructions and record the source and destination address of the N-th call somewhere (registers or memory). I looked at the P4 performance-monitor briefly but I couldn't quite figure out whether it supports the required functionality (it seemed like it could only record _all_ branches, which would be a problem). If a P4-expert is interested in pursuing this, let me know. I'd be happy to help/advise with some of the more subtle issues that need to be address to get this to work correctly.

	--david

William Lee Irwin III

author

2004-05-03 02:48 UTC #5 lore raw

In reply to William Lee Irwin III

Quoted 2 lines · William Lee Irwin III

before:
Tiotest results for 512 concurrent io threads:

Parting shot: I also used time(1):

before:
tiotest -t 512 -f 32 -b 4096 -d . 14337.17s user 3931.52s system 301% cpu 1:40:51.08 total

after:
tiotest -t 512 -f 32 -b 4096 -d . 10985.23s user 3524.50s system 266% cpu 1:30:48.80 total

i.e. it sped up the run by 10 minutes, or 10% of the total execution time.

-- wli