ref: 7f835e03809b48139026dead0ad0ae21092a6e60
parent: 957863b064ed01ebb1297ddd368ce5a78c957f5e
author: Ori Bernstein <ori@eigenstate.org>
date: Sat Sep 24 15:21:27 EDT 2022
9/port: reimplement timers to use timer wheel when many processes go to sleep, our old timer would slow to a crawl; this new implementation does not.
--- a/sys/src/9/port/alarm.c
+++ b/sys/src/9/port/alarm.c
@@ -3,109 +3,91 @@
#include "mem.h"
#include "dat.h"
#include "fns.h"
+#include "error.h"
-static Alarms alarms;
+static Proc *tripped;
static Rendez alarmr;
+static Lock triplk;
+static int
+tfn(void *)
+{
+ int t;
+
+ ilock(&triplk);
+ t = (tripped != nil);
+ iunlock(&triplk);
+ return t;
+}
+
+/*
+ * called every clock tick on cpu0
+ */
+static void
+tripalarm(Ureg*, Timer *t)
+{
+ ilock(&triplk);
+ t->p->palarm = tripped;
+ tripped = t->p;
+ iunlock(&triplk);
+
+ wakeup(&alarmr);
+}
+
void
alarmkproc(void*)
{
- Proc *rp;
- ulong now, when;
+ static Note alarmnote = {
+ "alarm",
+ NUser,
+ 1,
+ };
+ Proc *p, *n;
+ Timer *a;
while(waserror())
;
- for(;;){
- now = MACHP(0)->ticks;
- qlock(&alarms);
- for(rp = alarms.head; rp != nil; rp = rp->palarm){
- if((when = rp->alarm) == 0)
+ while(1){
+ ilock(&triplk);
+ p = tripped;
+ tripped = nil;
+ iunlock(&triplk);
+
+ for(; p != nil; p = n){
+ n = p->palarm;
+ a = &p->alarm;
+ if(!canqlock(&p->debug)){
+ a->tns = MS2NS(10);
+ timeradd(a);
continue;
- if((long)(now - when) < 0)
- break;
- if(!canqlock(&rp->debug))
- break;
- if(rp->alarm != 0){
- static Note alarm = {
- "alarm",
- NUser,
- 1,
- };
- incref(&alarm);
- pushnote(rp, &alarm);
- rp->alarm = 0;
}
- qunlock(&rp->debug);
+ incref(&alarmnote);
+ pushnote(p, &alarmnote);
+ qunlock(&p->debug);
}
- alarms.head = rp;
- qunlock(&alarms);
-
- sleep(&alarmr, return0, 0);
+ sleep(&alarmr, tfn, nil);
}
}
-/*
- * called every clock tick on cpu0
- */
-void
-checkalarms(void)
-{
- Proc *p;
- ulong now, when;
-
- p = alarms.head;
- if(p != nil){
- now = MACHP(0)->ticks;
- when = p->alarm;
- if(when == 0 || (long)(now - when) >= 0)
- wakeup(&alarmr);
- }
-}
-
ulong
procalarm(ulong time)
{
- Proc **l, *f;
- ulong when, old;
+ uvlong old;
+ Timer *a;
- when = MACHP(0)->ticks;
- old = up->alarm;
- if(old) {
- old -= when;
- if((long)old > 0)
- old = tk2ms(old);
- else
- old = 0;
- }
- if(time == 0) {
- up->alarm = 0;
- return old;
- }
- when += ms2tk(time);
- if(when == 0)
- when = 1;
+ a = &up->alarm;
+ old = a->tns;
+ timerdel(a);
- qlock(&alarms);
- l = &alarms.head;
- for(f = *l; f; f = f->palarm) {
- if(up == f){
- *l = f->palarm;
- break;
- }
- l = &f->palarm;
- }
- l = &alarms.head;
- for(f = *l; f; f = f->palarm) {
- time = f->alarm;
- if(time != 0 && (long)(time - when) >= 0)
- break;
- l = &f->palarm;
- }
- up->palarm = f;
- *l = up;
- up->alarm = when;
- qunlock(&alarms);
-
- return old;
+ lock(a);
+ a->tns = MS2NS(time);
+ a->tf = tripalarm;
+ a->tmode = Trelative;
+ a->p = up;
+ a->ta = nil;
+ unlock(a);
+ if(time != 0)
+ timeradd(a);
+ return NS2MS(old);
}
--- a/sys/src/9/port/portclock.c
+++ b/sys/src/9/port/portclock.c
@@ -7,10 +7,27 @@
#include "ureg.h"
#include "tos.h"
-struct Timers
-{
+typedef struct Timers Timers;
+typedef struct Wheel Wheel;
+
+enum {
+ WSHIFT = 5,
+ NWHEEL = 6,
+ NSLOT = 1<<WSHIFT,
+ SMASK = NSLOT-1,
+ TMAX = 1<<(WSHIFT*(NWHEEL-1)),
+};
+
+struct Wheel {
+ Timer *slots[NSLOT];
+ int idx;
+};
+
+struct Timers {
Lock;
- Timer *head;
+ uvlong tnow;
+ uvlong tsched;
+ Wheel wheels[NWHEEL];
};
static Timers timers[MAXMACH];
@@ -18,13 +35,102 @@
ulong intrcount[MAXMACH];
ulong fcallcount[MAXMACH];
-static vlong
-tadd(Timers *tt, Timer *nt)
+#define slot(tt, i, j) ((tt)->wheels[(i)].slots[(j) & SMASK])
+#define slotp(tt, i, j) (&(tt)->wheels[(i)].slots[(j) & SMASK])
+
+static void
+tins(Timers *tt, Timer *t)
{
- Timer *t, **last;
+ Timer *n, **p;
+ uvlong dt;
+ int i;
- /* Called with tt locked */
+ dt = t->twhen - tt->tnow;
+ assert((vlong)dt >= 0);
+ for(i = 0; dt >= NSLOT && i < NWHEEL-1; i++)
+ dt = (dt + tt->wheels[i].idx) >> WSHIFT;
+ dt = (dt + tt->wheels[i].idx) & SMASK;
+
+ p = &tt->wheels[i].slots[dt];
+ n = *p;
+ t->tt = tt;
+ t->tnext = n;
+ t->tlink = p;
+ if(n != nil)
+ n->tlink = &t->tnext;
+ *p = t;
+}
+
+static void
+tdel(Timer *dt)
+{
+ if(dt->tt == nil)
+ return;
+ if(dt->tnext != nil)
+ dt->tnext->tlink = dt->tlink;
+ *dt->tlink = dt->tnext;
+ dt->tlink = nil;
+ dt->tnext = nil;
+ dt->tt = nil;
+}
+
+/* look for another timer at same frequency for combining */
+static uvlong
+tcombine(Timers *tt, Timer *nt, uvlong now)
+{
+ int i, j, s;
+ Timer *t;
+
+ for(i = 0; i < NWHEEL; i++){
+ s = tt->wheels[i].idx;
+ for(j = s; j < s+NSLOT; j++)
+ for(t = slot(tt, i, j); t != nil && t->tns < nt->tns; t = t->tnext)
+ if(t->tmode == Tperiodic && t->twhen > now && t->tns == nt->tns)
+ return t->twhen;
+ }
+ return fastticks(nil);
+}
+
+/* approximate time of the next timer to schedule, or 0 if there's already one scheduled */
+static uvlong
+tnext(Timers *tt, uvlong when)
+{
+ uvlong tk, dt;
+ int i, j, s;
+ Wheel *w;
+
+ if(when > tt->tsched)
+ return 0;
+
+ dt = 1;
+ for(i = 0; i < NWHEEL; i++){
+ w = &tt->wheels[i];
+ s = w->idx+1;
+ tk = tt->tnow;
+ /* the current slot should always already be processed, and thus empty */
+ assert(slot(tt, i, w->idx) == nil);
+ for(j = s; j < s+NSLOT-1; j++){
+ tk += dt;
+ if(tk >= when || slot(tt, i, j) != nil)
+ break;
+ }
+ if(tk < when)
+ when = tk;
+ dt <<= WSHIFT;
+ }
+ tt->tsched = when;
+ return when;
+
+}
+
+/* Called with tt locked */
+static void
+tadd(Timers *tt, Timer *nt)
+{
assert(nt->tt == nil);
+ nt->tt = tt;
+ nt->tnext = nil;
+ nt->tlink = nil;
switch(nt->tmode){
default:
panic("timer");
@@ -36,66 +142,27 @@
break;
case Tperiodic:
assert(nt->tns >= 100000); /* At least 100 µs period */
- if(nt->twhen == 0){
- /* look for another timer at same frequency for combining */
- for(t = tt->head; t; t = t->tnext){
- if(t->tmode == Tperiodic && t->tns == nt->tns)
- break;
- }
- if (t)
- nt->twhen = t->twhen;
- else
- nt->twhen = fastticks(nil);
- }
+ if(0 && nt->twhen == 0)
+ nt->twhen = tcombine(tt, nt, tt->tnow);
+ else
+ nt->twhen = fastticks(nil);
nt->twhen += ns2fastticks(nt->tns);
break;
}
-
- for(last = &tt->head; t = *last; last = &t->tnext){
- if(t->twhen > nt->twhen)
- break;
- }
- nt->tnext = *last;
- *last = nt;
- nt->tt = tt;
- if(last == &tt->head)
- return nt->twhen;
- return 0;
+ tins(tt, nt);
}
-static uvlong
-tdel(Timer *dt)
-{
-
- Timer *t, **last;
- Timers *tt;
-
- tt = dt->tt;
- if (tt == nil)
- return 0;
- for(last = &tt->head; t = *last; last = &t->tnext){
- if(t == dt){
- assert(dt->tt);
- dt->tt = nil;
- *last = t->tnext;
- break;
- }
- }
- if(last == &tt->head && tt->head)
- return tt->head->twhen;
- return 0;
-}
-
/* add or modify a timer */
void
timeradd(Timer *nt)
{
Timers *tt;
- vlong when;
+ uvlong when;
/* Must lock Timer struct before Timers struct */
ilock(nt);
- if(tt = nt->tt){
+ tt = nt->tt;
+ if(tt != nil){
ilock(tt);
tdel(nt);
iunlock(tt);
@@ -102,7 +169,8 @@
}
tt = &timers[m->machno];
ilock(tt);
- when = tadd(tt, nt);
+ tadd(tt, nt);
+ when = tnext(tt, nt->twhen);
if(when)
timerset(when);
iunlock(tt);
@@ -123,9 +191,10 @@
ilock(dt);
if(tt = dt->tt){
ilock(tt);
- when = tdel(dt);
+ tdel(dt);
+ when = tnext(tt, dt->twhen);
if(when && tt == &timers[m->machno])
- timerset(tt->head->twhen);
+ timerset(when);
iunlock(tt);
}
if((mp = dt->tactive) == nil || mp->machno == m->machno){
@@ -133,7 +202,6 @@
return;
}
iunlock(dt);
-
/* rare, but tf can still be active on another cpu */
while(dt->tactive == mp && dt->tt == nil)
if(up->nlocks == 0 && islo())
@@ -166,9 +234,6 @@
if(active.exiting)
exit(0);
- if(m->machno == 0)
- checkalarms();
-
if(up && up->state == Running){
if(userureg(ur)){
/* user profiling clock */
@@ -184,47 +249,77 @@
void
timerintr(Ureg *u, Tval)
{
- Timer *t;
+ uvlong dt, when, now;
+ int i, j, s, hz;
+ Timer *t, *n;
Timers *tt;
- uvlong when, now;
- int callhzclock;
+ Wheel *w;
intrcount[m->machno]++;
- callhzclock = 0;
tt = &timers[m->machno];
now = fastticks(nil);
+
ilock(tt);
- while(t = tt->head){
- /*
- * No need to ilock t here: any manipulation of t
- * requires tdel(t) and this must be done with a
- * lock to tt held. We have tt, so the tdel will
- * wait until we're done
- */
- when = t->twhen;
- if(when > now){
- timerset(when);
- iunlock(tt);
- if(callhzclock)
- hzclock(u);
- return;
+ hz = 0;
+ dt = now - tt->tnow;
+ tt->tnow = now;
+ /*
+ * We need to look at all the wheels.
+ */
+ for(i = 0; i < NWHEEL; i++){
+ w = &tt->wheels[i];
+ s = w->idx;
+ w->idx = (s+dt)&SMASK;
+ for(j = s; j <= s+dt && j < s+NSLOT; j++){
+ for(t = slot(tt, i, j); t != nil; t = n){
+ assert(t->tt == tt);
+ n = t->tnext;
+ /*
+ * The last wheel can contain timers that are
+ * expiring both before and after now.
+ * Cascade the future ones, and expire the current
+ * ones.
+ */
+ if(t->twhen > now+TMAX)
+ continue;
+ /*
+ * Otherwise, we cascade this timer into a new slot
+ * in a closer wheel.
+ */
+ tdel(t);
+ if(t->twhen > now){
+ tins(tt, t);
+ continue;
+ }
+ /*
+ * No need to ilock t here: any manipulation of t
+ * requires tdel(t) and this must be done with a
+ * lock to tt held. We have tt, so the tdel will
+ * wait until we're done
+ */
+ t->tactive = MACHP(m->machno);
+ fcallcount[m->machno]++;
+ iunlock(tt);
+ if(t->tf)
+ t->tf(u, t);
+ else
+ hz = 1;
+ t->tactive = nil;
+ ilock(tt);
+ if(t->tmode == Tperiodic)
+ tadd(tt, t);
+ }
}
- tt->head = t->tnext;
- assert(t->tt == tt);
- t->tt = nil;
- t->tactive = MACHP(m->machno);
- fcallcount[m->machno]++;
- iunlock(tt);
- if(t->tf)
- (*t->tf)(u, t);
- else
- callhzclock++;
- t->tactive = nil;
- ilock(tt);
- if(t->tmode == Tperiodic)
- tadd(tt, t);
+ dt += s;
+ dt >>= WSHIFT;
}
+ when = tnext(tt, ~0);
+
+ if(when != 0)
+ timerset(when);
iunlock(tt);
+ if(hz)
+ hzclock(u);
}
void
@@ -264,7 +359,8 @@
nt->tf = (void (*)(Ureg*, Timer*))f;
ilock(&timers[0]);
- when = tadd(&timers[0], nt);
+ tadd(&timers[0], nt);
+ when = tnext(&timers[0], nt->twhen);
if(when)
timerset(when);
iunlock(&timers[0]);
--- a/sys/src/9/port/portdat.h
+++ b/sys/src/9/port/portdat.h
@@ -1,4 +1,3 @@
-typedef struct Alarms Alarms;
typedef struct Block Block;
typedef struct Chan Chan;
typedef struct Cmdbuf Cmdbuf;
@@ -98,12 +97,6 @@
int writer; /* number of writers */
};
-struct Alarms
-{
- QLock;
- Proc *head;
-};
-
struct Sargs
{
uchar args[MAXSYSARG*BY2WD];
@@ -575,6 +568,7 @@
Tval tticks; /* tns converted to ticks */
Tval twhen; /* ns represented in fastticks */
Timer *tnext;
+ Timer **tlink; /* a pointer to the prev nodes's next */
};
enum
@@ -720,8 +714,8 @@
Rendez sleep; /* place for syssleep/debug */
int notepending; /* note issued but not acted on */
int kp; /* true if a kernel process */
- Proc *palarm; /* Next alarm time */
- ulong alarm; /* Time of call */
+ Proc *palarm; /* triggered alarm chain */
+ Timer alarm; /* alarm context */
int newtlb; /* Pager has changed my pte's, I must flush */
uintptr rendtag; /* Tag for rendezvous */
--- a/sys/src/9/port/portfns.h
+++ b/sys/src/9/port/portfns.h
@@ -26,7 +26,6 @@
void chandevreset(void);
void chandevshutdown(void);
void chanfree(Chan*);
-void checkalarms(void);
void checkb(Block*, char*);
void cinit(void);
Chan* cclone(Chan*);
@@ -176,6 +175,7 @@
Cmdtab* lookupcmd(Cmdbuf*, Cmdtab*, int);
Page* lookpage(Image*, uintptr);
#define MS2NS(n) (((vlong)(n))*1000000LL)
+#define NS2MS(n) (((vlong)(n)+500000LL)/100000LL)
void machinit(void);
void* mallocz(ulong, int);
void* malloc(ulong);
--- a/sys/src/9/port/proc.c
+++ b/sys/src/9/port/proc.c
@@ -1203,7 +1203,7 @@
void (*pt)(Proc*, int, vlong);
up->fpstate &= ~FPillegal;
- up->alarm = 0;
+ procalarm(0);
timerdel(up);
pt = proctrace;
if(pt != nil)