[9front] port/timer: rewrite to use timer wheel

[ori@eigenstate.org]

Then many processes start and sleep, our timer implementation falls over.
This makes it fall over less, though I still see a bunch of slowness when
many procs are sleeping, and I'm not sure why.

(I measured the amount of time it takes to tick timers, so it's not that)

diff e7f003c9207082d683575f48c92e40a44b7d04ae uncommitted
--- a/sys/src/9/port/alarm.c
+++ b/sys/src/9/port/alarm.c
@@ -3,109 +3,106 @@
 #include	"mem.h"
 #include	"dat.h"
 #include	"fns.h"
+#include	"error.h"
 
-static Alarms	alarms;
+struct Alarm {
+	Timer;
+	Proc	*p;
+	Alarm	*next;
+};
+
+static Alarm	*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)
+{
+	Alarm *a;
+
+	a = t->ta;
+
+	ilock(&triplk);
+	a->next = tripped;
+	tripped = a;
+	a->p->alarm = nil;
+	iunlock(&triplk);
+
+	wakeup(&alarmr);
+}
+
 void
 alarmkproc(void*)
 {
-	Proc *rp;
-	ulong now, when;
+	Alarm *a, *n;
 
 	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);
+		a = tripped;
+		tripped = nil;
+		iunlock(&triplk);
+		for(; a != nil; a = n){
+			n = a->next;
+			if(!canqlock(&a->p->debug)){
+				a->tns = MS2NS(10); /* try again later */
+				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);
+			postnote(a->p, 0, "alarm", NUser);
+			qunlock(&a->p->debug);
+			free(a);
 		}
-		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;
+	Alarm *a;
 
-	when = MACHP(0)->ticks;
-	old = up->alarm;
-	if(old) {
-		old -= when;
-		if((long)old > 0)
-			old = tk2ms(old);
-		else
-			old = 0;
+	a = up->alarm;
+	old = 0;
+	if(a != nil){
+		old = a->tns;
+		timerdel(a);
 	}
-	if(time == 0) {
-		up->alarm = 0;
-		return old;
-	}
-	when += ms2tk(time);
-	if(when == 0)
-		when = 1;
-
-	qlock(&alarms);
-	l = &alarms.head;
-	for(f = *l; f; f = f->palarm) {
-		if(up == f){
-			*l = f->palarm;
-			break;
+	if(time == 0){
+		up->alarm = nil;
+		free(a);
+	}else{
+		if(a == nil){
+			if((a = malloc(sizeof(Alarm))) == nil)
+				error(Enomem);
+			a->next = nil;
 		}
-		l = &f->palarm;
+		ilock(&triplk);
+		up->alarm = a;
+		iunlock(&triplk);
+		a->tns = MS2NS(time);
+		a->tf = tripalarm;
+		a->tmode = Trelative;
+		a->p = up;
+		a->ta = a;
+		timeradd(a);
 	}
-	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;
+	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,101 @@
 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;
+	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 +141,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(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 +168,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 +190,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 +201,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 +233,6 @@
 	if(active.exiting)
 		exit(0);
 
-	if(m->machno == 0)
-		checkalarms();
-
 	if(up && up->state == Running){
 		if(userureg(ur)){
 			/* user profiling clock */
@@ -184,47 +248,78 @@
 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 = (dt + s)&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 bucket 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
+				 */
+				n = t->tnext;
+				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,4 @@
-typedef struct Alarms	Alarms;
+typedef struct Alarm	Alarm;
 typedef struct Block	Block;
 typedef struct Chan	Chan;
 typedef struct Cmdbuf	Cmdbuf;
@@ -59,6 +59,7 @@
 #pragma incomplete Mntrpc
 #pragma incomplete Queue
 #pragma incomplete Timers
+#pragma incomplete Alarm
 
 #include <fcall.h>
 
@@ -98,12 +99,6 @@
 	int	writer;		/* number of writers */
 };
 
-struct Alarms
-{
-	QLock;
-	Proc	*head;
-};
-
 struct Sargs
 {
 	uchar	args[MAXSYSARG*BY2WD];
@@ -575,6 +570,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 +716,7 @@
 	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 */
+	Alarm	*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);