code: plan9front

Info  •  Files  •  Log

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)