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 31472 invoked from network); 11 Sep 2022 17:54:21 -0000 Received: from 9front.inri.net (168.235.81.73) by inbox.vuxu.org with ESMTPUTF8; 11 Sep 2022 17:54:21 -0000 Received: from mimir.eigenstate.org ([206.124.132.107]) by 9front; Sun Sep 11 13:50:20 -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 c117bfa0 (TLSv1.2:ECDHE-RSA-AES256-SHA:256:NO) for <9front@9front.org>; Sun, 11 Sep 2022 10:50:08 -0700 (PDT) Message-ID: To: 9front@9front.org Date: Sun, 11 Sep 2022 13:50:07 -0400 From: ori@eigenstate.org In-Reply-To: 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: agile stable package rails SSL over SVG framework database Subject: Re: [9front] port/timer: rewrite to use timer wheel Reply-To: 9front@9front.org Precedence: bulk Quoth ori@eigenstate.org: > 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. v2 of this patch, which fixes the jank -- it was a copy paste error that would set the next node in the list to nil, and thus would break out of processing a bucket early, which would lead to us It also changes a few other things: - malloc becomes smalloc, so that alarm won't error with oom - fixes the memory leak - makes the alarm note static - asserts that timers are in the future diff e7f003c9207082d683575f48c92e40a44b7d04ae uncommitted --- a/sys/src/9/port/alarm.c +++ b/sys/src/9/port/alarm.c @@ -3,109 +3,114 @@ #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; + static Note alarmnote = { + "alarm", + NUser, + 1, + }; + 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); + incref(&alarmnote); + pushnote(a->p, &alarmnote); + 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 = smalloc(sizeof(Alarm))) == nil) + error(Enomem); + a->next = nil; } - 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; + 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); + } + return NS2MS(old); } --- a/sys/src/9/port/devuart.c +++ b/sys/src/9/port/devuart.c @@ -753,6 +753,7 @@ Uart *p; ilock(&uartalloc); +outb(0x88, '-'); for(p = uartalloc.elist; p; p = p->elist){ /* this hopefully amortizes cost of qproduce to many chars */ --- 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; + 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,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); --- 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)