/*
 * Copyright (c) 1986 Regents of the University of California.
 * All rights reserved.  The Berkeley software License Agreement
 * specifies the terms and conditions for redistribution.
 *
 *	@(#)vm_sched.c	1.2 (2.11BSD) 1999/9/10
 */

#include "param.h"
#include "user.h"
#include "proc.h"
#include "text.h"
#include "vm.h"
#include "kernel.h"
#include "systm.h"

#define	MINFINITY	-32767		/* minus infinity */

int	maxslp = MAXSLP;

/*
 * The main loop of the scheduling (swapping) process.
 * The basic idea is:
 *	see if anyone wants to be swapped in
 *	swap out processes until there is room
 *	swap him in
 *	repeat
 * The runout flag is set whenever someone is swapped out.  Sched sleeps on
 * it awaiting work.  Sched sleeps on runin whenever it cannot find enough
 * core (by swapping out or otherwise) to fit the selected swapped process.
 * It is awakened when the core situation changes and in any case once per
 * second.
 */
sched()
{
	register struct proc *rp;
	struct proc *p;
	int inage, maxsize, outpri;

    /* Find user to swap in; of users ready, select one out longest. */
    for (;;) {
	(void)_splhigh();
	{
	register int l_outpri, rppri;

	l_outpri = -20000;
	for (rp = allproc; rp; rp = rp->p_nxt) {
		if (rp->p_stat != SRUN || rp->p_flag & SLOAD)
			continue;
		rppri = rp->p_time - rp->p_nice * 8;

		/*
		 * Always bring in parents ending a vfork,
		 * to avoid deadlock
		 */
		if (rppri > l_outpri || rp->p_flag & SVFPRNT) {
			p = rp;
			l_outpri = rppri;
			if (rp->p_flag & SVFPRNT)
				break;
		}
	}

	/* If there is no one there, wait. */
	if (l_outpri == -20000) {
		++runout;
		sleep((caddr_t)&runout, PSWP);
		continue;
	}
	outpri = l_outpri;
	}

	(void)_spl0();

	/* See if there is core for that process, if so, swap it in. */
	if (swapin(p))
		continue;

	/*
	 * None found.  Look around for core: 1) kick out dead wood
	 * (processes asleep longer than maxslp+10); or 2) select out
	 * of the processes sleeping interruptibly the process with
	 * maximum f(size, slptime); or 3) if none, select the oldest.
	 * If we can find someone to swap out we try to swap someone
	 * else (hopefully) in, possibly causing someone else to get
	 * swapped out.
	 *
	 * f(size, slptime) = size + (slptime - maxslp) * 16
	 *
	 * This weighting is designed to penalize linearly for size
	 * and excessive slptime, but to reward processes which are
	 * executing or have executed recently.
	 */
	{
	register int l_maxsize;

	(void)_splhigh();
	l_maxsize = MINFINITY;
	inage = -1;
	for (rp = allproc; rp != NULL; rp = rp->p_nxt) {
		if (rp->p_stat == SZOMB ||
		    (rp->p_flag & (SSYS|SLOCK|SULOCK|SLOAD)) != SLOAD)
			continue;
		if (rp->p_textp && rp->p_textp->x_flag & XLOCK)
			continue;
		if (rp->p_stat == SSLEEP &&
		    (rp->p_flag & P_SINTR) || rp->p_stat == SSTOP) {
			register int size;

			if (rp->p_slptime > maxslp+10) {
				p = rp;
				l_maxsize = 1;
				break;
			}
			size = rp->p_dsize + rp->p_ssize
			    + (rp->p_slptime - maxslp << 4);
			if (l_maxsize < size) {
				p = rp;
				l_maxsize = size;
			}
		}
		else if (l_maxsize == MINFINITY &&
		    (rp->p_stat == SRUN || rp->p_stat == SSLEEP)) {
			register int rppri;

			rppri = rp->p_time + rp->p_nice;
			if (rppri > inage) {
				p = rp;
				inage = rppri;
			}
		}
	}
	maxsize = l_maxsize;
	}

	(void)_spl0();
	noop();
	(void)_splhigh();
	/*
	 * Swap found user out if sleeping interruptibly, or if he has spent at
	 * least 1 second in core and the swapped-out process has spent at
	 * least 2 seconds out.  Otherwise wait a bit and try again.
	 */
	if (maxsize != MINFINITY || outpri >= 2 && inage >= 1) {
		p->p_flag &= ~SLOAD;
		if (p->p_stat == SRUN)
			remrq(p);
		(void)_spl0();
		swapout(p, X_FREECORE, X_OLDSIZE, X_OLDSIZE);
	}
	else {
		++runin;
		sleep((caddr_t)&runin, PSWP);
	}
    }
}

/*
 * Count up various things once a second
 */
vmmeter()
{
#ifdef UCB_METER
	register u_short *cp, *rp;
	register long *sp;

	ave(avefree, freemem, 5);
	ave(avefree30, freemem, 30);
	cp = &cnt.v_first; rp = &rate.v_first; sp = &sum.v_first;
	while (cp <= &cnt.v_last) {
		ave(*rp, *cp, 5);
		*sp += *cp;
		*cp = 0;
		rp++, cp++, sp++;
	}
#endif

	if (time.tv_sec % 5 == 0) {
		vmtotal();
#ifdef UCB_METER
		rate.v_swpin = cnt.v_swpin;
		sum.v_swpin += cnt.v_swpin;
		cnt.v_swpin = 0;
		rate.v_swpout = cnt.v_swpout;
		sum.v_swpout += cnt.v_swpout;
		cnt.v_swpout = 0;
#endif
	}
}

vmtotal()
{
	register struct proc *p;
	register nrun = 0;
#ifdef UCB_METER
	char textcounted[100];

	total.t_vmtxt = 0;
	total.t_avmtxt = 0;
	total.t_rmtxt = 0;
	total.t_armtxt = 0;
{
	register struct text *xp;

	for (xp = text; xp < textNTEXT; xp++)
		if (xp->x_iptr) {
			total.t_vmtxt += xp->x_size;
			if (xp->x_ccount)
				total.t_rmtxt += xp->x_size;
		}
}
	total.t_vm = 0;
	total.t_avm = 0;
	total.t_rm = 0;
	total.t_arm = 0;
	total.t_rq = 0;
	total.t_dw = 0;
	total.t_sl = 0;
	total.t_sw = 0;
	bzero(textcounted, ntext * sizeof(char));
#endif
	for (p = allproc; p != NULL; p = p->p_nxt) {
		if (p->p_flag & SSYS)
			continue;
		if (p->p_stat) {
#ifdef UCB_METER
			if (p->p_stat != SZOMB) {
				total.t_vm += p->p_dsize + p->p_ssize + USIZE;
				if (p->p_flag & SLOAD)
					total.t_rm += p->p_dsize + p->p_ssize
					    + USIZE;
			}
#endif
			switch (p->p_stat) {

			case SSLEEP:
			case SSTOP:
				if (!(p->p_flag & P_SINTR) && p->p_stat == SSLEEP)
					nrun++;
#ifdef UCB_METER
				if (p->p_flag & SLOAD) {
					if	(!(p->p_flag & P_SINTR))
						total.t_dw++;
					else if (p->p_slptime < maxslp)
						total.t_sl++;
				} else if (p->p_slptime < maxslp)
					total.t_sw++;
				if (p->p_slptime < maxslp)
					goto active;
#endif
				break;

			case SRUN:
			case SIDL:
				nrun++;
#ifdef UCB_METER
				if (p->p_flag & SLOAD)
					total.t_rq++;
				else
					total.t_sw++;
active:
				total.t_avm += p->p_dsize + p->p_ssize + USIZE;
				if (p->p_flag & SLOAD)
					total.t_arm += p->p_dsize + p->p_ssize
					    + USIZE;
				if (p->p_textp) switch (p->p_stat) {

				case SSTOP:
				case SSLEEP:
					if (p->p_slptime >= maxslp)
						break;
					/* fall into... */

				case SRUN:
				case SIDL:
				{	register int nt;

					total.t_avmtxt += p->p_textp->x_size;
					nt = p->p_textp - text;
					if (!textcounted[nt]) {
						textcounted[nt] = 1;
						if (p->p_textp->x_ccount)
							total.t_armtxt +=
							    p->p_textp->x_size;
					}
				}
				}
#endif
				break;
			}
		}
	}
#ifdef UCB_METER
	total.t_vm += total.t_vmtxt;
	total.t_avm += total.t_avmtxt;
	total.t_rm += total.t_rmtxt;
	total.t_arm += total.t_armtxt;
	total.t_free = avefree;
#endif
	loadav(avenrun, nrun);
}

/*
 * Compute Tenex style load average.  This code is adapted from similar code
 * by Bill Joy on the Vax system.  The major change is that we avoid floating
 * point since not all pdp-11's have it.  This makes the code quite hard to
 * read - it was derived with some algebra.
 *
 * "floating point" numbers here are stored in a 16 bit short, with 8 bits on
 * each side of the decimal point.  Some partial products will have 16 bits to
 * the right.
 *
 * The Vax algorithm is:
 *
 * /*
 *  * Constants for averages over 1, 5, and 15 minutes
 *  * when sampling at 5 second intervals.
 *  * /
 * double	cexp[3] = {
 * 	0.9200444146293232,	/* exp(-1/12) * /
 * 	0.9834714538216174,	/* exp(-1/60) * /
 * 	0.9944598480048967,	/* exp(-1/180) * /
 * };
 * 
 * /*
 *  * Compute a tenex style load average of a quantity on
 *  * 1, 5 and 15 minute intervals.
 *  * /
 * loadav(avg, n)
 * 	register double *avg;
 * 	int n;
 * {
 * 	register int i;
 * 
 * 	for (i = 0; i < 3; i++)
 * 		avg[i] = cexp[i] * avg[i] + n * (1.0 - cexp[i]);
 * }
 */

long cexp[3] = {
	0353,	/* 256 * exp(-1/12)  */
	0373,	/* 256 * exp(-1/60)  */
	0376,	/* 256 * exp(-1/180) */
};

loadav(avg, n)
	register short	*avg;
	register int	n;
{
	register int	i;

	for (i = 0; i < 3; i++)
		avg[i] = (cexp[i] * (avg[i]-(n<<8)) + (((long)n)<<16)) >> 8;
}