9/port: revert timer wheel change, breaks pi4 boot, needs more time investigating

1 files changed, 94 insertions, 190 deletions

diff --git a/sys/src/9/port/portclock.c b/sys/src/9/port/portclock.c
index 5f7a498e9..e12938bc3 100644
--- a/sys/src/9/port/portclock.c
+++ b/sys/src/9/port/portclock.c
@@ -7,27 +7,10 @@
 #include "ureg.h"
 #include "tos.h"
 
-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 {
+struct Timers
+{
 	Lock;
-	uvlong	tnow;
-	uvlong	tsched;
-	Wheel	wheels[NWHEEL];
+	Timer	*head;
 };
 
 static Timers timers[MAXMACH];
@@ -35,102 +18,13 @@ static Timers timers[MAXMACH];
 ulong intrcount[MAXMACH];
 ulong fcallcount[MAXMACH];
 
-#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 *n, **p;
-	uvlong dt;
-	int i;
-
-	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
+static vlong
 tadd(Timers *tt, Timer *nt)
 {
+	Timer *t, **last;
+
+	/* Called with tt locked */
 	assert(nt->tt == nil);
-	nt->tt = tt;
-	nt->tnext = nil;
-	nt->tlink = nil;
 	switch(nt->tmode){
 	default:
 		panic("timer");
@@ -142,14 +36,54 @@ tadd(Timers *tt, Timer *nt)
 		break;
 	case Tperiodic:
 		assert(nt->tns >= 100000);	/* At least 100 µs period */
-		if(0 && nt->twhen == 0)
-			nt->twhen = tcombine(tt, nt, tt->tnow);
-		else
-			nt->twhen = fastticks(nil);
+		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);
+		}
 		nt->twhen += ns2fastticks(nt->tns);
 		break;
 	}
-	tins(tt, nt);
+
+	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;
+}
+
+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 */
@@ -157,20 +91,18 @@ void
 timeradd(Timer *nt)
 {
 	Timers *tt;
-	uvlong when;
+	vlong when;
 
 	/* Must lock Timer struct before Timers struct */
 	ilock(nt);
-	tt = nt->tt;
-	if(tt != nil){
+	if(tt = nt->tt){
 		ilock(tt);
 		tdel(nt);
 		iunlock(tt);
 	}
 	tt = &timers[m->machno];
 	ilock(tt);
-	tadd(tt, nt);
-	when = tnext(tt, nt->twhen);
+	when = tadd(tt, nt);
 	if(when)
 		timerset(when);
 	iunlock(tt);
@@ -191,10 +123,9 @@ timerdel(Timer *dt)
 	ilock(dt);
 	if(tt = dt->tt){
 		ilock(tt);
-		tdel(dt);
-		when = tnext(tt, dt->twhen);
+		when = tdel(dt);
 		if(when && tt == &timers[m->machno])
-			timerset(when);
+			timerset(tt->head->twhen);
 		iunlock(tt);
 	}
 	if((mp = dt->tactive) == nil || mp->machno == m->machno){
@@ -202,6 +133,7 @@ timerdel(Timer *dt)
 		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())
@@ -234,6 +166,9 @@ hzclock(Ureg *ur)
 	if(active.exiting)
 		exit(0);
 
+	if(m->machno == 0)
+		checkalarms();
+
 	if(up && up->state == Running){
 		if(userureg(ur)){
 			/* user profiling clock */
@@ -249,77 +184,47 @@ hzclock(Ureg *ur)
 void
 timerintr(Ureg *u, Tval)
 {
-	uvlong dt, when, now;
-	int i, j, s, hz;
-	Timer *t, *n;
+	Timer *t;
 	Timers *tt;
-	Wheel *w;
+	uvlong when, now;
+	int callhzclock;
 
 	intrcount[m->machno]++;
+	callhzclock = 0;
 	tt = &timers[m->machno];
 	now = fastticks(nil);
-
 	ilock(tt);
-	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);
-			}
+	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;
 		}
-		dt += s;
-		dt >>= WSHIFT;
+		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);
 	}
-	when = tnext(tt, ~0);
-
-	if(when != 0)
-		timerset(when);
 	iunlock(tt);
-	if(hz)
-		hzclock(u);
 }
 
 void
@@ -359,8 +264,7 @@ addclock0link(void (*f)(void), int ms)
 	nt->tf = (void (*)(Ureg*, Timer*))f;
 
 	ilock(&timers[0]);
-	tadd(&timers[0], nt);
-	when = tnext(&timers[0], nt->twhen);
+	when = tadd(&timers[0], nt);
 	if(when)
 		timerset(when);
 	iunlock(&timers[0]);