From: ori@eigenstate.org
To: 9front@9front.org
Subject: Re: [9front] port/timer: rewrite to use timer wheel
Date: Sun, 11 Sep 2022 13:50:07 -0400 [thread overview]
Message-ID: <B346B9B8EDFBCA3B14DA5D85E88A130C@eigenstate.org> (raw)
In-Reply-To: <A58BA92D9696A98E1E7A96C0506A878C@eigenstate.org>
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<<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,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 <fcall.h>
@@ -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)
prev parent reply other threads:[~2022-09-11 17:54 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-10 17:52 ori
2022-09-11 11:32 ` cinap_lenrek
2022-09-11 17:50 ` ori [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=B346B9B8EDFBCA3B14DA5D85E88A130C@eigenstate.org \
--to=ori@eigenstate.org \
--cc=9front@9front.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).