static Ctlr*
pnpprobe(SDev *sd)
{
	ulong start;
	char *p;
	static int i;

	if(i > nprobe)
		return 0;
	p = probef[i++];
	if(strlen(p) < 2)
		return 0;
	if(p[1] == '!')
		p += 2;

	start = TK2MS(MACHP(0)->ticks);
	if(waserror()){
		print("#æ: pnpprobe failed in %lud ms: %s: %s\n",
			TK2MS(MACHP(0)->ticks) - start, probef[i-1],
			up->errstr);
		return nil;
	}
	sd = aoeprobe(p, sd);			/* does a round of probing */
	poperror();
	print("#æ: pnpprobe established %s in %lud ms\n",
		probef[i-1], TK2MS(MACHP(0)->ticks) - start);
	return sd->ctlr;
}

ulong
procalarm(ulong time)
{
	Proc **l, *f;
	ulong when, old;

	if(up->alarm)
		old = tk2ms(up->alarm - MACHP(0)->ticks);
	else
		old = 0;
	if(time == 0) {
		up->alarm = 0;
		return old;
	}
	when = ms2tk(time)+MACHP(0)->ticks;
	if(when == 0)		/* ticks have wrapped to 0? */
		when = 1;	/* distinguish a wrapped alarm from no alarm */

	qlock(&alarms);
	l = &alarms.head;
	for(f = *l; f; f = f->palarm) {
		if(up == f){
			*l = f->palarm;
			break;
		}
		l = &f->palarm;
	}

	up->palarm = 0;
	if(alarms.head) {
		l = &alarms.head;
		for(f = *l; f; f = f->palarm) {
			if((long)(f->alarm - when) >= 0) {
				up->palarm = f;
				*l = up;
				goto done;
			}
			l = &f->palarm;
		}
		*l = up;
	}
	else
		alarms.head = up;
done:
	up->alarm = when;
	qunlock(&alarms);

	return old;
}

static void
wifitx(Wifi *wifi, Wnode *wn, Block *b)
{
	Wifipkt *w;
	uint seq;

	wn->lastsend = MACHP(0)->ticks;

	seq = incref(&wifi->txseq);
	seq <<= 4;

	w = (Wifipkt*)b->rp;
	w->dur[0] = 0;
	w->dur[1] = 0;
	w->seq[0] = seq;
	w->seq[1] = seq>>8;

	if((w->fc[0] & 0x0c) != 0x00){
		b = wifiencrypt(wifi, wn, b);
		if(b == nil)
			return;
	}

	if((wn->txcount++ & 255) == 255){
		if(wn->actrate != nil && wn->actrate < wn->maxrate)
			wn->actrate++;
	}

	(*wifi->transmit)(wifi, wn, b);
}

void
alarmkproc(void*)
{
	Proc *rp;
	ulong now, when;

	while(waserror())
		;

	for(;;){
		now = MACHP(0)->ticks;
		qlock(&alarms);
		for(rp = alarms.head; rp != nil; rp = rp->palarm){
			if((when = rp->alarm) == 0)
				continue;
			if((long)(now - when) < 0)
				break;
			if(!canqlock(&rp->debug))
				break;
			if(rp->alarm != 0){
				postnote(rp, 0, "alarm", NUser);
				rp->alarm = 0;
			}
			qunlock(&rp->debug);
		}
		alarms.head = rp;
		qunlock(&alarms);

		sleep(&alarmr, return0, 0);
	}
}

/*
 *  Set the time of day struct
 */
void
todset(vlong t, vlong delta, int n)
{
	if(!tod.init)
		todinit();

	ilock(&tod);
	if(t >= 0){
		tod.off = t;
		tod.last = fastticks(nil);
		tod.lasttime = 0;
		tod.delta = 0;
		tod.sstart = tod.send;
	} else {
		if(n <= 0)
			n = 1;
		n *= HZ;
		if(delta < 0 && n > -delta)
			n = -delta;
		if(delta > 0 && n > delta)
			n = delta;
		if (n == 0) {
			iprint("todset: n == 0, delta == %lld\n", delta);
			delta = 0;
		} else
			delta /= n;
		tod.sstart = MACHP(0)->ticks;
		tod.send = tod.sstart + n;
		tod.delta = delta;
	}
	iunlock(&tod);
}

void
alarmkproc(void*)
{
	Proc *rp;
	ulong now;

	for(;;){
		now = MACHP(0)->ticks;
		qlock(&alarms);
		/*
		 * the odd test of now vs. rp->alarm is to cope with
		 * now wrapping around.
		 */
		while((rp = alarms.head) && (long)(now - rp->alarm) >= 0){
			if(rp->alarm != 0L){
				if(canqlock(&rp->debug)){
					if(!waserror()){
						postnote(rp, 0, "alarm", NUser);
						poperror();
					}
					qunlock(&rp->debug);
					rp->alarm = 0L;
				}else
					break;
			}
			alarms.head = rp->palarm;
		}
		qunlock(&alarms);

		sleep(&alarmr, return0, 0);
	}
}

/*
 * Update the cpu time average for this particular process,
 * which is about to change from up -> not up or vice versa.
 * p->lastupdate is the last time an updatecpu happened.
 *
 * The cpu time average is a decaying average that lasts
 * about D clock ticks.  D is chosen to be approximately
 * the cpu time of a cpu-intensive "quick job".  A job has to run
 * for approximately D clock ticks before we home in on its 
 * actual cpu usage.  Thus if you manage to get in and get out
 * quickly, you won't be penalized during your burst.  Once you
 * start using your share of the cpu for more than about D
 * clock ticks though, your p->cpu hits 1000 (1.0) and you end up 
 * below all the other quick jobs.  Interactive tasks, because
 * they basically always use less than their fair share of cpu,
 * will be rewarded.
 *
 * If the process has not been running, then we want to
 * apply the filter
 *
 *	cpu = cpu * (D-1)/D
 *
 * n times, yielding 
 * 
 *	cpu = cpu * ((D-1)/D)^n
 *
 * but D is big enough that this is approximately 
 *
 * 	cpu = cpu * (D-n)/D
 *
 * so we use that instead.
 * 
 * If the process has been running, we apply the filter to
 * 1 - cpu, yielding a similar equation.  Note that cpu is 
 * stored in fixed point (* 1000).
 *
 * Updatecpu must be called before changing up, in order
 * to maintain accurate cpu usage statistics.  It can be called
 * at any time to bring the stats for a given proc up-to-date.
 */
void
updatecpu(Proc *p)
{
	int n, t, ocpu;
	int D = schedgain*HZ*Scaling;

	if(p->edf != nil)
		return;

	t = MACHP(0)->ticks*Scaling + Scaling/2;
	n = t - p->lastupdate;
	p->lastupdate = t;

	if(n == 0)
		return;
	if(n > D)
		n = D;

	ocpu = p->cpu;
	if(p != up)
		p->cpu = (ocpu*(D-n))/D;
	else{
		t = 1000 - ocpu;
		t = (t*(D-n))/D;
		p->cpu = 1000 - t;
	}

//iprint("pid %d %s for %d cpu %d -> %d\n", p->pid,p==up?"active":"inactive",n, ocpu,p->cpu);
}

/*
 *  called every clock tick
 */
void
checkalarms(void)
{
	Proc *p;
	ulong now;

	now = MACHP(0)->ticks;

	if(talarm.list == 0 || canlock(&talarm) == 0)
		return;

	for(;;) {
		p = talarm.list;
		if(p == 0)
			break;

		if(p->twhen == 0) {
			talarm.list = p->tlink;
			p->trend = 0;
			continue;
		}
		if(now < p->twhen)
			break;
		wakeup(p->trend);
		talarm.list = p->tlink;
		p->trend = 0;
	}

	unlock(&talarm);
}

/*
 * On average, p has used p->cpu of a cpu recently.
 * Its fair share is conf.nmach/m->load of a cpu.  If it has been getting
 * too much, penalize it.  If it has been getting not enough, reward it.
 * I don't think you can get much more than your fair share that 
 * often, so most of the queues are for using less.  Having a priority
 * of 3 means you're just right.  Having a higher priority (up to p->basepri) 
 * means you're not using as much as you could.
 */
int
reprioritize(Proc *p)
{
	int fairshare, n, load, ratio;

	load = MACHP(0)->load;
	if(load == 0)
		return p->basepri;

	/*
	 * fairshare = 1.000 * conf.nmach * 1.000/load,
	 * except the decimal point is moved three places
	 * on both load and fairshare.
	 */
	fairshare = (conf.nmach*1000*1000)/load;
	n = p->cpu;
	if(n == 0)
		n = 1;
	ratio = (fairshare+n/2) / n;
	if(ratio > p->basepri)
		ratio = p->basepri;
	if(ratio < 0)
		panic("reprioritize");
//iprint("pid %d cpu %d load %d fair %d pri %d\n", p->pid, p->cpu, load, fairshare, ratio);
	return ratio;
}

/*
 *  ready(p) picks a new priority for a process and sticks it in the
 *  runq for that priority.
 */
void
ready(Proc *p)
{
	int s, pri;
	Schedq *rq;
	void (*pt)(Proc*, int, vlong);

	if(p->state == Ready){
		print("double ready %s %lud pc %p\n", p->text, p->pid, getcallerpc(&p));
		return;
	}

	s = splhi();
	if(edfready(p)){
		splx(s);
		return;
	}

	if(up != p && (p->wired == nil || p->wired == MACHP(m->machno)))
		m->readied = p;	/* group scheduling */

	updatecpu(p);
	pri = reprioritize(p);
	p->priority = pri;
	rq = &runq[pri];
	p->state = Ready;
	queueproc(rq, p);
	pt = proctrace;
	if(pt != nil)
		pt(p, SReady, 0);
	splx(s);
}

/*
 * wire this proc to a machine
 */
void
procwired(Proc *p, int bm)
{
	Proc *pp;
	int i;
	char nwired[MAXMACH];
	Mach *wm;

	if(bm < 0){
		/* pick a machine to wire to */
		memset(nwired, 0, sizeof(nwired));
		p->wired = nil;
		pp = proctab(0);
		for(i=0; i<conf.nproc; i++, pp++){
			wm = pp->wired;
			if(wm != nil && pp->pid)
				nwired[wm->machno]++;
		}
		bm = 0;
		for(i=0; i<conf.nmach; i++)
			if(nwired[i] < nwired[bm])
				bm = i;
	} else {
		/* use the virtual machine requested */
		bm = bm % conf.nmach;
	}

	p->wired = MACHP(bm);
	p->mp = p->wired;
}

static void
rebalance(void)
{
	int pri, npri, t, x;
	Schedq *rq;
	Proc *p;

	t = m->ticks;
	if(t - balancetime < HZ)
		return;
	balancetime = t;

	for(pri=0, rq=runq; pri<Npriq; pri++, rq++){
another:
		p = rq->head;
		if(p == nil)
			continue;
		if(p->mp != MACHP(m->machno))
			continue;
		if(pri == p->basepri)
			continue;
		updatecpu(p);
		npri = reprioritize(p);
		if(npri != pri){
			x = splhi();
			p = dequeueproc(rq, p);
			if(p != nil)
				queueproc(&runq[npri], p);
			splx(x);
			goto another;
		}
	}
}

void
alarmkproc(void*)
{
	Proc *rp;
	ulong now;

	for(;;){
		now = MACHP(0)->ticks;
		qlock(&alarms);
		while((rp = alarms.head) && rp->alarm <= now){
			if(rp->alarm != 0L){
				if(canqlock(&rp->debug)){
					if(!waserror()){
						postnote(rp, 0, "alarm", NUser);
						poperror();
					}
					qunlock(&rp->debug);
					rp->alarm = 0L;
				}else
					break;
			}
			alarms.head = rp->palarm;
		}
		qunlock(&alarms);

		sleep(&alarmr, return0, 0);
	}
}

ulong
procalarm(ulong time)
{
	Proc **l, *f;
	ulong when, old;

	if(up->alarm)
		old = tk2ms(up->alarm - MACHP(0)->ticks);
	else
		old = 0;
	if(time == 0) {
		up->alarm = 0;
		return old;
	}
	when = ms2tk(time)+MACHP(0)->ticks;

	qlock(&alarms);
	l = &alarms.head;
	for(f = *l; f; f = f->palarm) {
		if(up == f){
			*l = f->palarm;
			break;
		}
		l = &f->palarm;
	}

	up->palarm = 0;
	if(alarms.head) {
		l = &alarms.head;
		for(f = *l; f; f = f->palarm) {
			if(f->alarm > when) {
				up->palarm = f;
				*l = up;
				goto done;
			}
			l = &f->palarm;
		}
		*l = up;
	}
	else
		alarms.head = up;
done:
	up->alarm = when;
	qunlock(&alarms);

	return old;
}

int
nrand(int n)
{
	if(randn == 0)
		seedrand();
	randn = randn*1103515245 + 12345 + MACHP(0)->ticks;
	return (randn>>16) % n;
}

static void
txstart(Ether* ether)
{
	int port;
	Smc91xx* ctlr;
	Block* bp;
	int len, npages;
	int pno;

	/* assumes ctlr is locked and bank 2 is selected */
	/* leaves bank 2 selected on return */
	port = ether->port;
	ctlr = ether->ctlr;

	if (ctlr->txbp) {
		bp = ctlr->txbp;
		ctlr->txbp = 0;
	} else {
		bp = qget(ether->oq);
		if (bp == 0)
			return;

		len = BLEN(bp);
		npages = (len + HdrSize) / PageSize;
		outs(port + MmuCmd, McAlloc | npages);
	}

	pno = inb(port + AllocRes);
	if (pno & ArFailed) {
		outb(port + IntrMask, inb(port + IntrMask) | IntAlloc);
		ctlr->txbp = bp;
		ctlr->txtime = MACHP(0)->ticks;
		return;
	}

	outb(port + PktNo, pno);
	outs(port + Pointer, PtrAutoInc);

	len = BLEN(bp);
	outs(port + Data1, 0);
	outb(port + Data1, (len + HdrSize) & 0xFF);
	outb(port + Data1, (len + HdrSize) >> 8);
	outss(port + Data1, bp->rp, len / 2);
	if ((len & 1) == 0) {
		outs(port + Data1, 0);
	} else {
		outb(port + Data1, bp->rp[len - 1]);
		outb(port + Data1, 0x20);	/* no info what 0x20 means */
	}

	outb(port + IntrMask, inb(port + IntrMask) |
			IntTxError | IntTxEmpty);

	outs(port + MmuCmd, McEnqueue);
	freeb(bp);
}

void
syncclock(void)
{
	uvlong x;

	if(arch->fastclock != tscticks)
		return;

	if(m->machno == 0){
		wrmsr(0x10, 0);
		m->tscticks = 0;
	} else {
		x = MACHP(0)->tscticks;
		while(x == MACHP(0)->tscticks)
			;
		wrmsr(0x10, MACHP(0)->tscticks);
		cycles(&m->tscticks);
	}
}

static void
ethercheck(Ether *ether)
{
	if (ether->starttime != 0 &&
	    TK2MS(MACHP(0)->ticks)/1000 - ether->starttime > Etherstuck) {
		etheractive(ether);
		if (ether->ctlrno == 0)	/* only complain about main ether */
			iprint("#l%d: ethernet stuck\n", ether->ctlrno);
	}
}

static int
tsince(int tag)
{
	int n;

	n = MACHP(0)->ticks & 0xffff;
	n -= tag & 0xffff;
	if(n < 0)
		n += 1<<16;
	return n;
}

static int
newtag(Aoedev *d)
{
	int t;

	do {
		t = ++d->lasttag << 16;
		t |= MACHP(0)->ticks & 0xffff;
	} while (t == Tfree || t == Tmgmt);
	return t;
}