Implement a unified run queue and adjust priority levels accordingly.

- All processes go into the same array of queues, with different
  scheduling classes using different portions of the array.  This
  allows user processes to have their priorities propogated up into
  interrupt thread range if need be.
- I chose 64 run queues as an arbitrary number that is greater than
  32.  We used to have 4 separate arrays of 32 queues each, so this
  may not be optimal.  The new run queue code was written with this
  in mind; changing the number of run queues only requires changing
  constants in runq.h and adjusting the priority levels.
- The new run queue code takes the run queue as a parameter.  This
  is intended to be used to create per-cpu run queues.  Implement
  wrappers for compatibility with the old interface which pass in
  the global run queue structure.
- Group the priority level, user priority, native priority (before
  propogation) and the scheduling class into a struct priority.
- Change any hard coded priority levels that I found to use
  symbolic constants (TTIPRI and TTOPRI).
- Remove the curpriority global variable and use that of curproc.
  This was used to detect when a process' priority had lowered and
  it should yield.  We now effectively yield on every interrupt.
- Activate propogate_priority().  It should now have the desired
  effect without needing to also propogate the scheduling class.
- Temporarily comment out the call to vm_page_zero_idle() in the
  idle loop.  It interfered with propogate_priority() because
  the idle process needed to do a non-blocking acquire of Giant
  and then other processes would try to propogate their priority
  onto it.  The idle process should not do anything except idle.
  vm_page_zero_idle() will return in the form of an idle priority
  kernel thread which is woken up at apprioriate times by the vm
  system.
- Update struct kinfo_proc to the new priority interface.  Deliberately
  change its size by adjusting the spare fields.  It remained the same
  size, but the layout has changed, so userland processes that use it
  would parse the data incorrectly.  The size constraint should really
  be changed to an arbitrary version number.  Also add a debug.sizeof
  sysctl node for struct kinfo_proc.

1 files changed, 163 insertions, 181 deletions

diff --git a/sys/kern/kern_switch.c b/sys/kern/kern_switch.c
index 7515ea8b576a..8374048b1d07 100644
--- a/sys/kern/kern_switch.c
+++ b/sys/kern/kern_switch.c
@@ -1,6 +1,8 @@
 /*
  * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>
  * All rights reserved.
+ * Copyright (c) 2001 Jake Burkholder <jake@FreeBSD.org>
+ * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -32,225 +34,205 @@
 #include <sys/ktr.h>
 #include <sys/mutex.h>
 #include <sys/proc.h>
-#include <sys/rtprio.h>
 #include <sys/queue.h>
 
 /*
- * We have NQS (32) run queues per scheduling class.  For the normal
- * class, there are 128 priorities scaled onto these 32 queues.  New
- * processes are added to the last entry in each queue, and processes
- * are selected for running by taking them from the head and maintaining
- * a simple FIFO arrangement.
- *
- * Interrupt, real time and idle priority processes have and explicit
- * 0-31 priority which maps directly onto their class queue index.
- * When a queue has something in it, the corresponding bit is set in
- * the queuebits variable, allowing a single read to determine the
- * state of all 32 queues and then a ffs() to find the first busy
- * queue.
- *
- * XXX This needs fixing.  First, we only have one idle process, so we
- * hardly need 32 queues for it.  Secondly, the number of classes
- * makes things unwieldy.  We should be able to merge them into a
- * single 96 or 128 entry queue.
+ * Global run queue.
  */
-struct rq itqueues[NQS];		/* interrupt threads */
-struct rq rtqueues[NQS];		/* real time processes */
-struct rq queues[NQS];			/* time sharing processes */
-struct rq idqueues[NQS];		/* idle process */
-u_int32_t itqueuebits;
-u_int32_t rtqueuebits;
-u_int32_t queuebits;
-u_int32_t idqueuebits;
+static struct runq runq;
+SYSINIT(runq, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, runq_init, &runq)
 
 /*
- * Initialize the run queues at boot time.
+ * Wrappers which implement old interface; act on global run queue.
  */
-static void
-rqinit(void *dummy)
+
+struct proc *
+chooseproc(void)
 {
-	int i;
+	return runq_choose(&runq);
+}
 
-	for (i = 0; i < NQS; i++) {
-		TAILQ_INIT(&itqueues[i]);
-		TAILQ_INIT(&rtqueues[i]);
-		TAILQ_INIT(&queues[i]);
-		TAILQ_INIT(&idqueues[i]);
-	}
+int
+procrunnable(void)
+{
+	return runq_check(&runq);
+}
+
+void
+remrunqueue(struct proc *p)
+{
+	runq_remove(&runq, p);
 }
-SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
 
-/*
- * setrunqueue() examines a process priority and class and inserts it on
- * the tail of it's appropriate run queue (based on class and priority).
- * This sets the queue busy bit.
- * The process must be runnable.
- * This must be called at splhigh().
- */
 void
 setrunqueue(struct proc *p)
 {
-	struct rq *q;
-	u_int8_t pri;
+	runq_add(&runq, p);
+}
 
-	mtx_assert(&sched_lock, MA_OWNED);
-	KASSERT(p->p_stat == SRUN, ("setrunqueue: proc %p (%s) not SRUN", p, \
-	    p->p_comm));
+/*
+ * Clear the status bit of the queue corresponding to priority level pri,
+ * indicating that it is empty.
+ */
+static __inline void
+runq_clrbit(struct runq *rq, int pri)
+{
+	struct rqbits *rqb;
 
-	/*
-	 * Decide which class we want to run.  We now have four
-	 * queues, and this is becoming ugly.  We should be able to
-	 * collapse the first three classes into a single contiguous
-	 * queue.  XXX FIXME.
-	 */
-	CTR4(KTR_PROC, "setrunqueue: proc %p (pid %d, %s), schedlock %lx",
-		p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock);
-	if (p->p_rtprio.type == RTP_PRIO_ITHREAD) {	/* interrupt thread */
-		pri = p->p_rtprio.prio;
-		q = &itqueues[pri];
-		itqueuebits |= 1 << pri;
-	} else if (p->p_rtprio.type == RTP_PRIO_REALTIME || /* real time */
-		   p->p_rtprio.type == RTP_PRIO_FIFO) {
-		pri = p->p_rtprio.prio;
-		q = &rtqueues[pri];
-		rtqueuebits |= 1 << pri;
-	} else if (p->p_rtprio.type == RTP_PRIO_NORMAL) {   /* time sharing */
-		pri = p->p_priority >> 2;
-		q = &queues[pri];
-		queuebits |= 1 << pri;
-	} else if (p->p_rtprio.type == RTP_PRIO_IDLE) {	    /* idle proc */
-		pri = p->p_rtprio.prio;
-		q = &idqueues[pri];
-		idqueuebits |= 1 << pri;
-	} else {
-		panic("setrunqueue: invalid rtprio type %d", p->p_rtprio.type);
-	}
-	p->p_rqindex = pri;		/* remember the queue index */
-	TAILQ_INSERT_TAIL(q, p, p_procq);
+	rqb = &rq->rq_status;
+	CTR4(KTR_RUNQ, "runq_clrbit: bits=%#x %#x bit=%#x word=%d",
+	    rqb->rqb_bits[RQB_WORD(pri)],
+	    rqb->rqb_bits[RQB_WORD(pri)] & ~RQB_BIT(pri),
+	    RQB_BIT(pri), RQB_WORD(pri));
+	rqb->rqb_bits[RQB_WORD(pri)] &= ~RQB_BIT(pri);
+}
+
+/*
+ * Find the index of the first non-empty run queue.  This is done by
+ * scanning the status bits, a set bit indicates a non-empty queue.
+ */
+static __inline int
+runq_findbit(struct runq *rq)
+{
+	struct rqbits *rqb;
+	int pri;
+	int i;
+
+	rqb = &rq->rq_status;
+	for (i = 0; i < RQB_LEN; i++)
+		if (rqb->rqb_bits[i]) {
+			pri = (RQB_FFS(rqb->rqb_bits[i]) - 1) +
+			    (i << RQB_L2BPW);
+			CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d pri=%d",
+			    rqb->rqb_bits[i], i, pri);
+			return (pri);
+		}
+
+	return (-1);
+}
+
+/*
+ * Set the status bit of the queue corresponding to priority level pri,
+ * indicating that it is non-empty.
+ */
+static __inline void
+runq_setbit(struct runq *rq, int pri)
+{
+	struct rqbits *rqb;
+
+	rqb = &rq->rq_status;
+	CTR4(KTR_RUNQ, "runq_setbit: bits=%#x %#x bit=%#x word=%d",
+	    rqb->rqb_bits[RQB_WORD(pri)],
+	    rqb->rqb_bits[RQB_WORD(pri)] | RQB_BIT(pri),
+	    RQB_BIT(pri), RQB_WORD(pri));
+	rqb->rqb_bits[RQB_WORD(pri)] |= RQB_BIT(pri);
 }
 
 /*
- * remrunqueue() removes a given process from the run queue that it is on,
- * clearing the queue busy bit if it becomes empty.
- * This must be called at splhigh().
+ * Add the process to the queue specified by its priority, and set the
+ * corresponding status bit.
  */
 void
-remrunqueue(struct proc *p)
+runq_add(struct runq *rq, struct proc *p)
 {
-	struct rq *q;
-	u_int32_t *which;
-	u_int8_t pri;
+	struct rqhead *rqh;
+	int pri;
 
-	CTR4(KTR_PROC, "remrunqueue: proc %p (pid %d, %s), schedlock %lx",
-		p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock);
 	mtx_assert(&sched_lock, MA_OWNED);
-	pri = p->p_rqindex;
-	if (p->p_rtprio.type == RTP_PRIO_ITHREAD) {
-		q = &itqueues[pri];
-		which = &itqueuebits;
-	} else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
-		   p->p_rtprio.type == RTP_PRIO_FIFO) {
-		q = &rtqueues[pri];
-		which = &rtqueuebits;
-	} else if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
-		q = &queues[pri];
-		which = &queuebits;
-	} else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
-		q = &idqueues[pri];
-		which = &idqueuebits;
-	} else {
-		panic("remrunqueue: invalid rtprio type");
-	}
-	TAILQ_REMOVE(q, p, p_procq);
-	if (TAILQ_EMPTY(q)) {
-		KASSERT((*which & (1 << pri)) != 0,
-			("remrunqueue: remove from empty queue"));
-		*which &= ~(1 << pri);
-	}
+	KASSERT(p->p_stat == SRUN, ("runq_add: proc %p (%s) not SRUN",
+	    p, p->p_comm));
+	pri = p->p_pri.pri_level / RQ_PPQ;
+	p->p_rqindex = pri;
+	runq_setbit(rq, pri);
+	rqh = &rq->rq_queues[pri];
+	CTR4(KTR_RUNQ, "runq_add: p=%p pri=%d %d rqh=%p",
+	    p, p->p_pri.pri_level, pri, rqh);
+	TAILQ_INSERT_TAIL(rqh, p, p_procq);
 }
 
 /*
- * procrunnable() returns a boolean true (non-zero) value if there are
- * any runnable processes.  This is intended to be called from the idle
- * loop to avoid the more expensive (and destructive) chooseproc().
- *
- * MP SAFE.  CALLED WITHOUT THE MP LOCK
- *
- * XXX I doubt this.  It's possibly fail-safe, but there's obviously
- * the case here where one of the bits words gets loaded, the
- * processor gets preempted, and by the time it returns from this
- * function, some other processor has picked the runnable process.
- * What am I missing?  (grog, 23 July 2000).
+ * Return true if there are runnable processes of any priority on the run
+ * queue, false otherwise.  Has no side effects, does not modify the run
+ * queue structure.
  */
-u_int32_t
-procrunnable(void)
+int
+runq_check(struct runq *rq)
 {
-	return (itqueuebits || rtqueuebits || queuebits || idqueuebits);
+	struct rqbits *rqb;
+	int i;
+
+	rqb = &rq->rq_status;
+	for (i = 0; i < RQB_LEN; i++)
+		if (rqb->rqb_bits[i]) {
+			CTR2(KTR_RUNQ, "runq_check: bits=%#x i=%d",
+			    rqb->rqb_bits[i], i);
+			return (1);
+		}
+	CTR0(KTR_RUNQ, "runq_check: empty");
+
+	return (0);
 }
 
 /*
- * chooseproc() selects the next process to run.  Ideally, cpu_switch()
- * would have determined that there is a process available before calling
- * this, but it is not a requirement.  The selected process is removed
- * from it's queue, and the queue busy bit is cleared if it becomes empty.
- * This must be called at splhigh().
- *
- * For SMP, trivial affinity is implemented by locating the first process
- * on the queue that has a matching lastcpu id.  Since normal priorities
- * are mapped four priority levels per queue, this may allow the cpu to
- * choose a slightly lower priority process in order to preserve the cpu
- * caches.
+ * Find and remove the highest priority process from the run queue.
+ * If there are no runnable processes, the per-cpu idle process is
+ * returned.  Will not return NULL under any circumstances.
  */
 struct proc *
-chooseproc(void)
+runq_choose(struct runq *rq)
 {
+	struct rqhead *rqh;
 	struct proc *p;
-	struct rq *q;
-	u_int32_t *which;
-	u_int32_t pri;
-#ifdef SMP
-	u_char id;
-#endif
+	int pri;
 
 	mtx_assert(&sched_lock, MA_OWNED);
-	if (itqueuebits) {
-		pri = ffs(itqueuebits) - 1;
-		q = &itqueues[pri];
-		which = &itqueuebits;
-	} else if (rtqueuebits) {
-		pri = ffs(rtqueuebits) - 1;
-		q = &rtqueues[pri];
-		which = &rtqueuebits;
-	} else if (queuebits) {
-		pri = ffs(queuebits) - 1;
-		q = &queues[pri];
-		which = &queuebits;
-	} else if (idqueuebits) {
-		pri = ffs(idqueuebits) - 1;
-		q = &idqueues[pri];
-		which = &idqueuebits;
-	} else {
-		CTR1(KTR_PROC, "chooseproc: idleproc, schedlock %lx",
-			(long)sched_lock.mtx_lock);
-		return PCPU_GET(idleproc);
-	}
-	p = TAILQ_FIRST(q);
-#ifdef SMP
-	/* wander down the current run queue for this pri level for a match */
-	id = PCPU_GET(cpuid);
-	while (p->p_lastcpu != id) {
-		p = TAILQ_NEXT(p, p_procq);
-		if (p == NULL) {
-			p = TAILQ_FIRST(q);
-			break;
+	if ((pri = runq_findbit(rq)) != -1) {
+		rqh = &rq->rq_queues[pri];
+		p = TAILQ_FIRST(rqh);
+		CTR3(KTR_RUNQ, "runq_choose: pri=%d p=%p rqh=%p", pri, p, rqh);
+		TAILQ_REMOVE(rqh, p, p_procq);
+		if (TAILQ_EMPTY(rqh)) {
+			CTR0(KTR_RUNQ, "runq_choose: empty");
+			runq_clrbit(rq, pri);
 		}
+		return (p);
+	}
+	CTR1(KTR_RUNQ, "runq_choose: idleproc pri=%d", pri);
+
+	return (PCPU_GET(idleproc));
+}
+
+/*
+ * Initialize a run structure.
+ */
+void
+runq_init(struct runq *rq)
+{
+	int i;
+
+	for (i = 0; i < RQ_NQS; i++)
+		TAILQ_INIT(&rq->rq_queues[i]);
+}
+
+/*
+ * Remove the process from the queue specified by its priority, and clear the
+ * corresponding status bit if the queue becomes empty.
+ */
+void
+runq_remove(struct runq *rq, struct proc *p)
+{
+	struct rqhead *rqh;
+	int pri;
+
+	mtx_assert(&sched_lock, MA_OWNED);
+	pri = p->p_rqindex;
+	rqh = &rq->rq_queues[pri];
+	CTR4(KTR_RUNQ, "runq_remove: p=%p pri=%d %d rqh=%p",
+	    p, p->p_pri.pri_level, pri, rqh);
+	KASSERT(p != NULL, ("runq_remove: no proc on busy queue"));
+	TAILQ_REMOVE(rqh, p, p_procq);
+	if (TAILQ_EMPTY(rqh)) {
+		CTR0(KTR_RUNQ, "runq_remove: empty");
+		runq_clrbit(rq, pri);
 	}
-#endif
-	CTR4(KTR_PROC, "chooseproc: proc %p (pid %d, %s), schedlock %lx",
-		p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock);
-	KASSERT(p, ("chooseproc: no proc on busy queue"));
-	TAILQ_REMOVE(q, p, p_procq);
-	if (TAILQ_EMPTY(q))
-		*which &= ~(1 << pri);
-	return p;
 }