[pidhash] [1/4] Make __do_SAK() use for_each_task_pid().

[pidhash] [1/4] Make __do_SAK() use for_each_task_pid().

[wli]

Kill off the for_each_process() in __do_SAK(): it really just
wants to do a hangup using SIGKILL.

 tty_io.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)


diff -urpN mm1-2.5.50-1/drivers/char/tty_io.c mm1-2.5.50-2/drivers/char/tty_io.c
--- mm1-2.5.50-1/drivers/char/tty_io.c	2002-12-04 12:49:46.000000000 -0800
+++ mm1-2.5.50-2/drivers/char/tty_io.c	2002-12-04 13:06:20.000000000 -0800
@@ -1838,6 +1838,8 @@ static void __do_SAK(void *arg)
 #else
 	struct tty_struct *tty = arg;
 	struct task_struct *p;
+	struct list_head *l;
+	struct pid *pid;
 	int session;
 	int		i;
 	struct file	*filp;
@@ -1850,9 +1852,8 @@ static void __do_SAK(void *arg)
 	if (tty->driver.flush_buffer)
 		tty->driver.flush_buffer(tty);
 	read_lock(&tasklist_lock);
-	for_each_process(p) {
-		if ((p->tty == tty) ||
-		    ((session > 0) && (p->session == session))) {
+	for_each_task_pid(session, PIDTYPE_SID, p, l, pid) {
+		if (p->tty == tty || session > 0) {
 			printk(KERN_NOTICE "SAK: killed process %d"
 			    " (%s): p->session==tty->session\n",
 			    p->pid, p->comm);

[pidhash] [3/4] eliminate proc_fill_super() tasklist iteration

[wli]

Introduce a per-cpu counter for the number of processes on the system,
and use that to set ->i_nlink in proc_fill_super() in constant time.

 fs/proc/inode.c       |    6 +-----
 include/linux/sched.h |    3 +++
 kernel/exit.c         |    2 ++
 kernel/fork.c         |   14 ++++++++++++++
 4 files changed, 20 insertions(+), 5 deletions(-)


diff -urpN mm1-2.5.50-2/fs/proc/inode.c wli-2.5.50-3/fs/proc/inode.c
--- mm1-2.5.50-2/fs/proc/inode.c	2002-11-27 14:36:19.000000000 -0800
+++ wli-2.5.50-3/fs/proc/inode.c	2002-12-04 18:40:59.000000000 -0800
@@ -234,11 +234,7 @@ int proc_fill_super(struct super_block *
 	/*
 	 * Fixup the root inode's nlink value
 	 */
-	read_lock(&tasklist_lock);
-	for_each_process(p)
-		if (p->pid)
-			root_inode->i_nlink++;
-	read_unlock(&tasklist_lock);
+	root_inode->i_nlink += nr_processes();
 	s->s_root = d_alloc_root(root_inode);
 	if (!s->s_root)
 		goto out_no_root;
diff -urpN mm1-2.5.50-2/include/linux/sched.h wli-2.5.50-3/include/linux/sched.h
--- mm1-2.5.50-2/include/linux/sched.h	2002-12-04 12:49:47.000000000 -0800
+++ wli-2.5.50-3/include/linux/sched.h	2002-12-04 18:42:39.000000000 -0800
@@ -27,6 +27,7 @@
 #include <linux/compiler.h>
 #include <linux/completion.h>
 #include <linux/pid.h>
+#include <linux/percpu.h>
 
 struct exec_domain;
 
@@ -87,6 +88,8 @@ extern unsigned long avenrun[];		/* Load
 
 extern int nr_threads;
 extern int last_pid;
+DECLARE_PER_CPU(unsigned long, process_counts);
+extern int nr_processes(void);
 extern unsigned long nr_running(void);
 extern unsigned long nr_uninterruptible(void);
 extern unsigned long nr_iowait(void);
diff -urpN mm1-2.5.50-2/kernel/exit.c wli-2.5.50-3/kernel/exit.c
--- mm1-2.5.50-2/kernel/exit.c	2002-12-04 12:49:47.000000000 -0800
+++ wli-2.5.50-3/kernel/exit.c	2002-12-04 18:57:08.000000000 -0800
@@ -41,6 +41,8 @@ static struct dentry * __unhash_process(
 	if (thread_group_leader(p)) {
 		detach_pid(p, PIDTYPE_PGID);
 		detach_pid(p, PIDTYPE_SID);
+		if (p->pid)
+			per_cpu(process_counts, smp_processor_id())--;
 	}
 
 	REMOVE_LINKS(p);
diff -urpN mm1-2.5.50-2/kernel/fork.c wli-2.5.50-3/kernel/fork.c
--- mm1-2.5.50-2/kernel/fork.c	2002-12-04 12:49:47.000000000 -0800
+++ wli-2.5.50-3/kernel/fork.c	2002-12-04 18:56:55.000000000 -0800
@@ -48,6 +48,8 @@ int nr_threads;
 int max_threads;
 unsigned long total_forks;	/* Handle normal Linux uptimes. */
 
+DEFINE_PER_CPU(unsigned long, process_counts);
+
 rwlock_t tasklist_lock __cacheline_aligned = RW_LOCK_UNLOCKED;  /* outer */
 
 /*
@@ -57,6 +59,16 @@ rwlock_t tasklist_lock __cacheline_align
  */
 static task_t *task_cache[NR_CPUS] __cacheline_aligned;
 
+int nr_processes(void)
+{
+	int cpu;
+	unsigned long total = 0;
+
+	for (cpu = 0; cpu < NR_CPUS; ++cpu)
+		total += per_cpu(process_counts, cpu);
+	return (int)total;
+}
+
 void __put_task_struct(struct task_struct *tsk)
 {
 	if (tsk != current) {
@@ -934,6 +946,8 @@ static struct task_struct *copy_process(
 		attach_pid(p, PIDTYPE_TGID, p->tgid);
 		attach_pid(p, PIDTYPE_PGID, p->pgrp);
 		attach_pid(p, PIDTYPE_SID, p->session);
+		if (p->pid)
+			per_cpu(process_counts, smp_processor_id())++;
 	} else
 		link_pid(p, p->pids + PIDTYPE_TGID, &p->group_leader->pids[PIDTYPE_TGID].pid);
 

[pidhash] [0/4] patch series vs. 2.5.50-mm1

[wli]

This is a series of patches against 2.5.50-mm1. 
They primarily have to do with pidhashing mechanisms, converting
some less-important users to the new API and eliminating some
tasklist iterations not covered by the original pidhash patches.

These should apply to 2.5.50-CURRENT; 2.5.50-mm1 includes bk snapshots.

mm1-2.5.50-2 [1/4] Make __do_SAK() use for_each_task_pid().
	The tty invariant involving ->tty being strictly associated
	with ->session has long been established. This converts
	__do_SAK() to use the pidhashing instead of iteration over
	the global tasklist.
mm1-2.5.50-5 [2/4] cap_set_pg() uses do_each_thread() to search for
	tasks in a given pgrp; convert it to for_each_task_pid()
wli-2.5.50-3 [3/5] eliminate proc_fill_super() tasklist iteration by
	means of introducing a nr_processes() per-cpu counter.
wli-2.5.50-6 [4/4] make get_pid_list() scan the PID bitmap instead of
	the tasklist.

Tested on 16x/16GB NUMA-Q with up to 16384 distinct processes.


Bill

[pidhash] [5/4] make get_pid_list() scan the PID bitmap

[wli]

Make get_pid_list() walk the PID bitmap instead of the tasklist.
This is not quite as good as it could be, because the PID search
structures are not appropriately arranged for range queries.

 fs/proc/base.c |   22 +---------------------
 kernel/pid.c   |   53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 54 insertions(+), 21 deletions(-)


diff -urpN wli-2.5.50-5/fs/proc/base.c wli-2.5.50-6/fs/proc/base.c
--- wli-2.5.50-5/fs/proc/base.c	2002-11-27 14:36:06.000000000 -0800
+++ wli-2.5.50-6/fs/proc/base.c	2002-12-04 19:15:00.000000000 -0800
@@ -1153,28 +1153,8 @@ out:
  * tasklist lock while doing this, and we must release it before
  * we actually do the filldir itself, so we use a temp buffer..
  */
-static int get_pid_list(int index, unsigned int *pids)
-{
-	struct task_struct *p;
-	int nr_pids = 0;
-
-	index--;
-	read_lock(&tasklist_lock);
-	for_each_process(p) {
-		int pid = p->pid;
-		if (!pid)
-			continue;
-		if (--index >= 0)
-			continue;
-		pids[nr_pids] = pid;
-		nr_pids++;
-		if (nr_pids >= PROC_MAXPIDS)
-			break;
-	}
-	read_unlock(&tasklist_lock);
-	return nr_pids;
-}
 
+int get_pid_list(int ordinal_of_pid, unsigned int *pid_buf);
 int proc_pid_readdir(struct file * filp, void * dirent, filldir_t filldir)
 {
 	unsigned int pid_array[PROC_MAXPIDS];
diff -urpN wli-2.5.50-5/kernel/pid.c wli-2.5.50-6/kernel/pid.c
--- wli-2.5.50-5/kernel/pid.c	2002-11-27 14:36:03.000000000 -0800
+++ wli-2.5.50-6/kernel/pid.c	2002-12-04 19:15:59.000000000 -0800
@@ -258,6 +258,59 @@ void switch_exec_pids(task_t *leader, ta
 	attach_pid(leader, PIDTYPE_SID, leader->session);
 }
 
+int get_pid_list(int ordinal, unsigned int *pid_buf)
+{
+	pidmap_t *map = pidmap_array;
+	int count = 0, k = 0, pos = 0;
+
+	BUG_ON(ordinal <= 0);
+	ordinal--;
+
+	while (pos + BITS_PER_PAGE < ordinal && map - pidmap_array < PIDMAP_ENTRIES) {
+		pos += BITS_PER_PAGE - atomic_read(&map->nr_free);
+		++map;
+	}
+
+	if (map - pidmap_array >= PIDMAP_ENTRIES || !map->page)
+		return 0;
+
+	while (pos < ordinal && k < BITS_PER_PAGE) {
+		task_t *task;
+		if (test_bit(k, map->page)
+			&& (map - pidmap_array)*BITS_PER_PAGE + k) {
+			int pid = (map-pidmap_array)*BITS_PER_PAGE + k;
+			read_lock(&tasklist_lock);
+			task = find_task_by_pid(pid);
+			if (task && thread_group_leader(task))
+				++pos;
+			read_unlock(&tasklist_lock);
+		}
+		++k;
+	}
+
+	while (map - pidmap_array < PIDMAP_ENTRIES && map->page && count < 20) {
+		while (k < BITS_PER_PAGE && count < 20) {
+			task_t *task;
+
+			if (test_bit(k, map->page)
+				&& (map - pidmap_array)*BITS_PER_PAGE + k) {
+				int pid = (map-pidmap_array)*BITS_PER_PAGE + k;
+				read_lock(&tasklist_lock);
+				task = find_task_by_pid(pid);
+				if (task && thread_group_leader(task)) {
+					pid_buf[count] = task->pid;
+					++count;
+				}
+				read_unlock(&tasklist_lock);
+			}
+			++k;
+		}
+		++map;
+		k = 0;
+	}
+	return count;
+}
+
 void __init pidhash_init(void)
 {
 	int i, j;

[pidhash] [2/4] make cap_set_pg() use for_each_task_pid()

[wli]

capset_set_pg() hunts for a task with the right pgrp. It neither wants
nor needs to examine all tasks.

 capability.c |   16 +++++++++-------
 1 files changed, 9 insertions(+), 7 deletions(-)


diff -urpN mm1-2.5.50-4/kernel/capability.c mm1-2.5.50-5/kernel/capability.c
--- mm1-2.5.50-4/kernel/capability.c	2002-11-27 14:35:50.000000000 -0800
+++ mm1-2.5.50-5/kernel/capability.c	2002-12-04 14:55:10.000000000 -0800
@@ -84,13 +84,15 @@ static inline void cap_set_pg(int pgrp, 
 			      kernel_cap_t *inheritable,
 			      kernel_cap_t *permitted)
 {
-     task_t *g, *target;
-
-     do_each_thread(g, target) {
-             if (target->pgrp != pgrp)
-                     continue;
-	     security_capset_set(target, effective, inheritable, permitted);
-     } while_each_thread(g, target);
+	task_t *g, *target;
+	struct list_head *l;
+	struct pid *pid;
+
+	for_each_task_pid(pgrp, PIDTYPE_PGID, g, l, pid) {
+		target = g;
+		while_each_thread(g, target)
+			security_capset_set(target, effective, inheritable, permitted);
+	}
 }
 
 /*

Re: [pidhash] [0/4] patch series vs. 2.5.50-mm1

[William Lee Irwin III]

On Wed, Dec 04, 2002 at 11:48:27PM -0800, wli@holomorphy.com wrote:
[...]

Sorry about the misnumbering; there were about half a dozen other
pidhashing related things that didn't make the cut (omitted largely
due to theoretical issues or not having enough testing bandwidth for
tonight's run) along with a fair amount of other non-pidhash-related
fat included in the original numbering scheme before the patch series
got renumbered and refined down to bits relevant to single maintainers.
Some were also excluded due to mutual interference.


Bill