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=none autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 17056 invoked from network); 25 Sep 2022 16:16:45 -0000 Received: from 9front.inri.net (168.235.81.73) by inbox.vuxu.org with ESMTPUTF8; 25 Sep 2022 16:16:45 -0000 Received: from mimir.eigenstate.org ([206.124.132.107]) by 9front; Sun Sep 25 12:14:22 -0400 2022 Received: from stockyard.myfiosgateway.com (pool-108-41-152-182.nycmny.fios.verizon.net [108.41.152.182]) by mimir.eigenstate.org (OpenSMTPD) with ESMTPSA id 0b1d7434 (TLSv1.2:ECDHE-RSA-AES256-SHA:256:NO) for <9front@9front.org>; Sun, 25 Sep 2022 09:14:20 -0700 (PDT) Message-ID: To: 9front@9front.org Date: Sun, 25 Sep 2022 12:14:18 -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: progressive software-aware storage generator Subject: [9front] timers: one more revision Reply-To: 9front@9front.org Precedence: bulk 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<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)