[9front] timers: one more revision

[ori@eigenstate.org]

there was a bug in the previous version of the patch that
didn't seem to trigger the timers on cpu0 for the pi; this
fixes the issue: a misoptimization to avoid scannning the
timers for the next one meant that we skipped scanning the
timers at all.

that optimization has been removed (no more tsched)

I'd appreciate some people banging on this a bit.

diff eb458c463b1dfc12233d49a870baf31049085655 uncommitted
--- 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,26 @@
 #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;
+	Wheel	wheels[NWHEEL];
 };
 
 static Timers timers[MAXMACH];
@@ -18,13 +34,96 @@
 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;
+
+	dt = 1;
+	for(i = 0; i < NWHEEL; i++){
+		w = &tt->wheels[i];
+		s = w->idx;
+		tk = tt->tnow;
+		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;
+	}
+	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 +135,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 +162,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 +184,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 +195,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 +227,6 @@
 	if(active.exiting)
 		exit(0);
 
-	if(m->machno == 0)
-		checkalarms();
-
 	if(up && up->state == Running){
 		if(userureg(ur)){
 			/* user profiling clock */
@@ -184,47 +242,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 +352,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)