Array of TAILQs in kern_synch.c

[Michal Mazurek]

There is what appears to be a sensless hash in kern_synch.c. It's an
array of 128 TAILQs which are hashed according to the high bits of the
wchan. It's possible to write a program that adds kern.maxthread entries
to one of those TAILQs. Just running chrome with 11 tabs open adds 35
entries to one TAILQ, while leaving others empty.

If it doesn't matter that a user program can make a TAILQ very long,
then the hash is senseless (diff below).

If it does matter, then it's broken, and a different data structure
needs to be used. Currently RB trees require all element values to be unique,
but a version of RB trees with non-unique element values is possible.

Any thoughts?

Index: sys/kern/kern_synch.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_synch.c,v
retrieving revision 1.133
diff -u -p -r1.133 kern_synch.c
--- sys/kern/kern_synch.c       6 Jul 2016 15:53:01 -0000       1.133
+++ sys/kern/kern_synch.c       31 Aug 2016 12:54:40 -0000
@@ -61,22 +61,12 @@
 int    thrsleep(struct proc *, struct sys___thrsleep_args *);
 int    thrsleep_unlock(void *, int);
 
-/*
- * We're only looking at 7 bits of the address; everything is
- * aligned to 4, lots of things are aligned to greater powers
- * of 2.  Shift right by 8, i.e. drop the bottom 256 worth.
- */
-#define TABLESIZE      128
-#define LOOKUP(x)      (((long)(x) >> 8) & (TABLESIZE - 1))
-TAILQ_HEAD(slpque,proc) slpque[TABLESIZE];
+TAILQ_HEAD(slpque,proc) slpque;
 
 void
 sleep_queue_init(void)
 {
-       int i;
-
-       for (i = 0; i < TABLESIZE; i++)
-               TAILQ_INIT(&slpque[i]);
+       TAILQ_INIT(&slpque);
 }
 
 
@@ -251,7 +241,7 @@ sleep_setup(struct sleep_state *sls, con
        p->p_wmesg = wmesg;
        p->p_slptime = 0;
        p->p_priority = prio & PRIMASK;
-       TAILQ_INSERT_TAIL(&slpque[LOOKUP(ident)], p, p_runq);
+       TAILQ_INSERT_TAIL(&slpque, p, p_runq);
 }
 
 void
@@ -385,7 +375,7 @@ unsleep(struct proc *p)
        SCHED_ASSERT_LOCKED();
 
        if (p->p_wchan) {
-               TAILQ_REMOVE(&slpque[LOOKUP(p->p_wchan)], p, p_runq);
+               TAILQ_REMOVE(&slpque, p, p_runq);
                p->p_wchan = NULL;
        }
 }
@@ -396,14 +386,12 @@ unsleep(struct proc *p)
 void
 wakeup_n(const volatile void *ident, int n)
 {
-       struct slpque *qp;
        struct proc *p;
        struct proc *pnext;
        int s;
 
        SCHED_LOCK(s);
-       qp = &slpque[LOOKUP(ident)];
-       for (p = TAILQ_FIRST(qp); p != NULL && n != 0; p = pnext) {
+       for (p = TAILQ_FIRST(&slpque); p != NULL && n != 0; p = pnext) {
                pnext = TAILQ_NEXT(p, p_runq);
 #ifdef DIAGNOSTIC
                if (p->p_stat != SSLEEP && p->p_stat != SSTOP)
@@ -412,7 +400,7 @@ wakeup_n(const volatile void *ident, int
                if (p->p_wchan == ident) {
                        --n;
                        p->p_wchan = 0;
-                       TAILQ_REMOVE(qp, p, p_runq);
+                       TAILQ_REMOVE(&slpque, p, p_runq);
                        if (p->p_stat == SSLEEP)
                                setrunnable(p);
                }

-- 
Michal Mazurek