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.

1 files changed, 66 insertions, 84 deletions

diff --git a/sys/src/9/port/alarm.c b/sys/src/9/port/alarm.c
index 49dec2ccb..95516222f 100644
--- 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;
 
-void
-alarmkproc(void*)
+static int
+tfn(void *)
 {
-	Proc *rp;
-	ulong now, when;
-
-	while(waserror())
-		;
-
-	for(;;){
-		now = MACHP(0)->ticks;
-		qlock(&alarms);
-		for(rp = alarms.head; rp != nil; rp = rp->palarm){
-			if((when = rp->alarm) == 0)
-				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);
-		}
-		alarms.head = rp;
-		qunlock(&alarms);
+	int t;
 
-		sleep(&alarmr, return0, 0);
-	}
+	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
-checkalarms(void)
+alarmkproc(void*)
 {
-	Proc *p;
-	ulong now, when;
+	static Note alarmnote = {
+		"alarm",
+		NUser,
+		1,
+	};
+	Proc *p, *n;
+	Timer *a;
+
+	while(waserror())
+		;
 
-	p = alarms.head;
-	if(p != nil){
-		now = MACHP(0)->ticks;
-		when = p->alarm;
-		if(when == 0 || (long)(now - when) >= 0)
-			wakeup(&alarmr);
+	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;
+			}
+			incref(&alarmnote);
+			pushnote(p, &alarmnote);
+			qunlock(&p->debug);
+		}
+		sleep(&alarmr, tfn, nil);
 	}
 }
 
 ulong
 procalarm(ulong time)
 {
-	Proc **l, *f;
-	ulong when, old;
-
-	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;
+	uvlong old;
+	Timer *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);
+	a = &up->alarm;
+	old = a->tns;
+	timerdel(a);
 
-	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);
 }