From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.0 required=5.0 tests=T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 8385 invoked from network); 10 Sep 2022 17:53:56 -0000 Received: from 9front.inri.net (168.235.81.73) by inbox.vuxu.org with ESMTPUTF8; 10 Sep 2022 17:53:56 -0000 Received: from mimir.eigenstate.org ([206.124.132.107]) by 9front; Sat Sep 10 13:52:23 -0400 2022 Received: from abbatoir.myfiosgateway.com (pool-74-108-56-137.nycmny.fios.verizon.net [74.108.56.137]) by mimir.eigenstate.org (OpenSMTPD) with ESMTPSA id 6693f456 (TLSv1.2:ECDHE-RSA-AES256-SHA:256:NO) for <9front@9front.org>; Sat, 10 Sep 2022 10:52:14 -0700 (PDT) Message-ID: To: 9front@9front.org Date: Sat, 10 Sep 2022 13:52:13 -0400 From: ori@eigenstate.org MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: stateless HTTP grid-based configuration high-performance optimizer Subject: [9front] port/timer: rewrite to use timer wheel Reply-To: 9front@9front.org Precedence: bulk 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<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 @@ -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);