Instead of using a fixed size hash table for procs, use an rb tree.
Makes thread/process lookup even more web scale.
Index: kern/init_main.c
===================================================================
RCS file: /cvs/src/sys/kern/init_main.c,v
retrieving revision 1.189
diff -u -p -r1.189 init_main.c
--- kern/init_main.c 3 Jun 2013 16:55:22 -0000 1.189
+++ kern/init_main.c 5 Jun 2013 02:36:56 -0000
@@ -274,7 +274,7 @@ main(void *framep)
LIST_INSERT_HEAD(&allproc, p, p_list);
pr->ps_pgrp = &pgrp0;
- LIST_INSERT_HEAD(PIDHASH(0), p, p_hash);
+ RB_INSERT(proc_rb_procs, &proc_rb_root, p);
LIST_INSERT_HEAD(PGRPHASH(0), &pgrp0, pg_hash);
LIST_INIT(&pgrp0.pg_members);
LIST_INSERT_HEAD(&pgrp0.pg_members, pr, ps_pglist);
Index: kern/kern_exit.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_exit.c,v
retrieving revision 1.125
diff -u -p -r1.125 kern_exit.c
--- kern/kern_exit.c 5 Jun 2013 00:53:26 -0000 1.125
+++ kern/kern_exit.c 5 Jun 2013 02:40:47 -0000
@@ -254,7 +254,7 @@ exit1(struct proc *p, int rv, int flags)
* Remove proc from pidhash chain so looking it up won't
* work. Move it from allproc to zombproc, but do not yet
* wake up the reaper. We will put the proc on the
- * deadproc list later (using the p_hash member), and
+ * deadproc list later (using the p_rbtree member), and
* wake up the reaper when we do.
*/
/*
@@ -262,7 +262,7 @@ exit1(struct proc *p, int rv, int flags)
*/
p->p_stat = SDEAD;
- LIST_REMOVE(p, p_hash);
+ RB_REMOVE(proc_rb_procs, &proc_rb_root, p);
LIST_REMOVE(p, p_list);
LIST_INSERT_HEAD(&zombproc, p, p_list);
@@ -366,10 +366,10 @@ exit1(struct proc *p, int rv, int flags)
* critical section of process exit, and thus locking it can't
* modify interrupt state. We use a simple spin lock for this
* proclist. Processes on this proclist are also on zombproc;
- * we use the p_hash member to linkup to deadproc.
+ * we use the p_rbtree member to linkup to deadproc.
*/
struct mutex deadproc_mutex = MUTEX_INITIALIZER(IPL_NONE);
-struct proclist deadproc = LIST_HEAD_INITIALIZER(deadproc);
+struct proc_rb_procs deadproc = RB_INITIALIZER(&deadproc);
/*
* We are called from cpu_exit() once it is safe to schedule the
@@ -380,13 +380,13 @@ struct proclist deadproc = LIST_HEAD_INI
* we should refrain from changing any interrupt state.
*
* We lock the deadproc list, place the proc on that list (using
- * the p_hash member), and wake up the reaper.
+ * the p_rbtree member), and wake up the reaper.
*/
void
exit2(struct proc *p)
{
mtx_enter(&deadproc_mutex);
- LIST_INSERT_HEAD(&deadproc, p, p_hash);
+ RB_INSERT(proc_rb_procs, &deadproc, p);
mtx_leave(&deadproc_mutex);
wakeup(&deadproc);
@@ -408,11 +408,11 @@ reaper(void)
for (;;) {
mtx_enter(&deadproc_mutex);
- while ((p = LIST_FIRST(&deadproc)) == NULL)
+ while ((p = RB_ROOT(&deadproc)) == NULL)
msleep(&deadproc, &deadproc_mutex, PVM, "reaper", 0);
/* Remove us from the deadproc list. */
- LIST_REMOVE(p, p_hash);
+ RB_REMOVE(proc_rb_procs, &deadproc, p);
mtx_leave(&deadproc_mutex);
KERNEL_LOCK();
Index: kern/kern_fork.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_fork.c,v
retrieving revision 1.150
diff -u -p -r1.150 kern_fork.c
--- kern/kern_fork.c 5 Jun 2013 00:53:26 -0000 1.150
+++ kern/kern_fork.c 5 Jun 2013 02:24:32 -0000
@@ -438,7 +438,7 @@ fork1(struct proc *curp, int exitsig, in
p->p_pid = allocpid();
LIST_INSERT_HEAD(&allproc, p, p_list);
- LIST_INSERT_HEAD(PIDHASH(p->p_pid), p, p_hash);
+ RB_INSERT(proc_rb_procs, &proc_rb_root, p);
if ((flags & FORK_THREAD) == 0) {
LIST_INSERT_AFTER(curpr, pr, ps_pglist);
LIST_INSERT_HEAD(&curpr->ps_children, pr, ps_sibling);
Index: kern/kern_proc.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_proc.c,v
retrieving revision 1.50
diff -u -p -r1.50 kern_proc.c
--- kern/kern_proc.c 17 Feb 2013 17:39:29 -0000 1.50
+++ kern/kern_proc.c 5 Jun 2013 02:54:12 -0000
@@ -56,8 +56,9 @@ u_long uihash; /* size of hash table -
/*
* Other process lists
*/
-struct pidhashhead *pidhashtbl;
-u_long pidhash;
+int rb_proc_compare(struct proc *, struct proc *);
+RB_GENERATE(proc_rb_procs, proc, p_rbtree, rb_proc_compare);
+struct proc_rb_procs proc_rb_root;
struct pgrphashhead *pgrphashtbl;
u_long pgrphash;
struct proclist allproc;
@@ -84,12 +85,11 @@ procinit(void)
{
LIST_INIT(&allproc);
LIST_INIT(&zombproc);
+ RB_INIT(&proc_rb_root);
-
- pidhashtbl = hashinit(maxthread / 4, M_PROC, M_NOWAIT, &pidhash);
pgrphashtbl = hashinit(maxprocess / 4, M_PROC, M_NOWAIT, &pgrphash);
uihashtbl = hashinit(maxprocess / 16, M_PROC, M_NOWAIT, &uihash);
- if (!pidhashtbl || !pgrphashtbl || !uihashtbl)
+ if (!pgrphashtbl || !uihashtbl)
panic("procinit: malloc");
pool_init(&proc_pool, sizeof(struct proc), 0, 0, 0, "procpl",
@@ -166,15 +166,23 @@ inferior(struct process *pr, struct proc
/*
* Locate a proc (thread) by number
*/
+int
+rb_proc_compare(struct proc *a, struct proc *b)
+{
+ if (a->p_pid < b->p_pid)
+ return -1;
+ if (a->p_pid > b->p_pid)
+ return 1;
+ return 0;
+}
+
struct proc *
pfind(pid_t pid)
{
- struct proc *p;
+ struct proc q;
- LIST_FOREACH(p, PIDHASH(pid), p_hash)
- if (p->p_pid == pid)
- return (p);
- return (NULL);
+ q.p_pid = pid;
+ return RB_FIND(proc_rb_procs, &proc_rb_root, &q);
}
/*
@@ -184,10 +192,12 @@ struct process *
prfind(pid_t pid)
{
struct proc *p;
+ struct proc q;
- LIST_FOREACH(p, PIDHASH(pid), p_hash)
- if (p->p_pid == pid)
- return (p->p_flag & P_THREAD ? NULL : p->p_p);
+ q.p_pid = pid;
+ p = RB_FIND(proc_rb_procs, &proc_rb_root, &q);
+ if (p && !(p->p_flag & P_THREAD))
+ return (p->p_p);
return (NULL);
}
Index: kern/kern_sched.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_sched.c,v
retrieving revision 1.29
diff -u -p -r1.29 kern_sched.c
--- kern/kern_sched.c 3 Jun 2013 16:55:22 -0000 1.29
+++ kern/kern_sched.c 5 Jun 2013 02:50:35 -0000
@@ -88,7 +88,7 @@ sched_init_cpu(struct cpu_info *ci)
kthread_create_deferred(sched_kthreads_create, ci);
- LIST_INIT(&spc->spc_deadproc);
+ RB_INIT(&spc->spc_deadproc);
/*
* Slight hack here until the cpuset code handles cpu_info
@@ -148,8 +148,9 @@ sched_idle(void *v)
mi_switch();
SCHED_UNLOCK(s);
- while ((dead = LIST_FIRST(&spc->spc_deadproc))) {
- LIST_REMOVE(dead, p_hash);
+ while ((dead = RB_ROOT(&spc->spc_deadproc))) {
+ RB_REMOVE(proc_rb_procs, &spc->spc_deadproc,
+ dead);
exit2(dead);
}
}
@@ -198,7 +199,7 @@ sched_exit(struct proc *p)
timespecsub(&ts, &spc->spc_runtime, &ts);
timespecadd(&p->p_rtime, &ts, &p->p_rtime);
- LIST_INSERT_HEAD(&spc->spc_deadproc, p, p_hash);
+ RB_INSERT(proc_rb_procs, &spc->spc_deadproc, p);
/* This process no longer needs to hold the kernel lock. */
KERNEL_UNLOCK();
Index: sys/proc.h
===================================================================
RCS file: /cvs/src/sys/sys/proc.h,v
retrieving revision 1.167
diff -u -p -r1.167 proc.h
--- sys/proc.h 5 Jun 2013 00:53:27 -0000 1.167
+++ sys/proc.h 5 Jun 2013 03:00:09 -0000
@@ -43,6 +43,7 @@
#include <machine/proc.h> /* Machine-dependent proc substruct. */
#include <sys/selinfo.h> /* For struct selinfo */
#include <sys/queue.h>
+#include <sys/tree.h>
#include <sys/timeout.h> /* For struct timeout */
#include <sys/event.h> /* For struct klist */
#include <sys/mutex.h> /* For struct mutex */
@@ -270,7 +271,7 @@ struct proc {
u_char p_descfd; /* if not 255, fdesc permits this fd */
pid_t p_pid; /* Process identifier. */
- LIST_ENTRY(proc) p_hash; /* Hash chain. */
+ RB_ENTRY(proc) p_rbtree; /* RB tree by pid. */
/* The following fields are all zeroed upon creation in fork. */
#define p_startzero p_dupfd
@@ -484,9 +485,8 @@ struct uidinfo *uid_find(uid_t);
#define EXIT_THREAD 0x00000002
#define EXIT_THREAD_NOCHECK 0x00000003
-#define PIDHASH(pid) (&pidhashtbl[(pid) & pidhash])
-extern LIST_HEAD(pidhashhead, proc) *pidhashtbl;
-extern u_long pidhash;
+RB_PROTOTYPE(proc_rb_procs, proc, p_rbtree, rb_proc_compare);
+extern struct proc_rb_procs proc_rb_root;
#define PGRPHASH(pgid) (&pgrphashtbl[(pgid) & pgrphash])
extern LIST_HEAD(pgrphashhead, pgrp) *pgrphashtbl;
Index: sys/sched.h
===================================================================
RCS file: /cvs/src/sys/sys/sched.h,v
retrieving revision 1.33
diff -u -p -r1.33 sched.h
--- sys/sched.h 4 Jun 2013 22:17:34 -0000 1.33
+++ sys/sched.h 5 Jun 2013 02:50:30 -0000
@@ -70,6 +70,7 @@
#define _SYS_SCHED_H_
#include <sys/queue.h>
+#include <sys/tree.h>
/*
* Posix defines a <sched.h> which may want to include <sys/sched.h>
@@ -113,7 +114,7 @@ struct schedstate_percpu {
#ifdef notyet
struct proc *spc_reaper; /* dead proc reaper */
#endif
- LIST_HEAD(,proc) spc_deadproc;
+ RB_HEAD(proc_rb_procs,proc) spc_deadproc;
};
#ifdef _KERNEL
