Re: Array of TAILQs in kern_synch.c

[Mathieu -]

Ted Unangst wrote:
> Michal Mazurek wrote:
> > 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?
> 
> I don't think this is a good change. it's going backwards. even if there's 100
> things waiting on the same thing, there are other procs that aren't waiting on
> it.

Yeah, if anything, we might want a better distribution. FreeBSD XOR the
shifted bits with the wait channel (and uses a 256 bucket table).
In my limited testing it doesn't seem to make much of a difference
thoughm, I need to come up with a better workload for this.

Re: Array of TAILQs in kern_synch.c

[Ted Unangst]

Michal Mazurek wrote:
> 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?

I don't think this is a good change. it's going backwards. even if there's 100
things waiting on the same thing, there are other procs that aren't waiting on
it.

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 -   1.133
+++ sys/kern/kern_synch.c   31 Aug 2016 12:54:40 -
@@ -61,22 +61,12 @@
 intthrsleep(struct proc *, struct sys___thrsleep_args *);
 intthrsleep_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