clockintr: add a priority queue

- Add cq_pend to struct clockintr_queue.  cq_pend is the list of clock
  interrupts pending to run, sorted in ascending order by cl_expiration
  (earliest deadline first; EDF).  If the cl_expiration of two
  clockintrs is equal, the first clock interrupt scheduled has priority
  (FIFO).

  We may need to switch to an RB tree or a min-heap in the future.
  For now, there are only three clock interrupts, so a linked list
  is fine.

- Add cl_flags to struct clockintr.  We have one flag, CLST_PENDING.
  It indicates whether the given clockintr is enqueued on cq_pend.

- Rewrite clockintr_dispatch() to operate on cq_pend.  Clock
  interrupts are run in EDF order until the most imminent clockintr
  expires in the future.

- Add code to clockintr_establish(), clockintr_advance() and
  clockintr_schedule() to enqueue/dequeue the given clockintr
  on cq_est and cq_pend as needed.

- Add cq_est to struct clockintr_queue.  cq_est is the list of all
  clockintrs established on a clockintr_queue.

- Add a new counter, cs_spurious, to clockintr_stat.  A dispatch is
  "spurious" if no clockintrs are on cq_pend when we call
  clockintr_dispatch().

With input from aisha@.  Heavily tested by mlarkin@.  Shared with
hackers@.

ok aisha@ mlarkin@

1 files changed, 81 insertions, 48 deletions

diff --git a/sys/kern/kern_clockintr.c b/sys/kern/kern_clockintr.c
index 13dbb4e928e..718d39e31cc 100644
--- a/sys/kern/kern_clockintr.c
+++ b/sys/kern/kern_clockintr.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: kern_clockintr.c,v 1.3 2023/02/26 23:00:42 cheloha Exp $ */
+/* $OpenBSD: kern_clockintr.c,v 1.4 2023/03/09 03:50:38 cheloha Exp $ */
 /*
  * Copyright (c) 2003 Dale Rahn <drahn@openbsd.org>
  * Copyright (c) 2020 Mark Kettenis <kettenis@openbsd.org>
@@ -24,6 +24,7 @@
 #include <sys/kernel.h>
 #include <sys/malloc.h>
 #include <sys/mutex.h>
+#include <sys/queue.h>
 #include <sys/stdint.h>
 #include <sys/sysctl.h>
 #include <sys/time.h>
@@ -62,6 +63,7 @@ void clockintr_schedclock(struct clockintr *, void *);
 void clockintr_schedule(struct clockintr *, uint64_t);
 void clockintr_statclock(struct clockintr *, void *);
 void clockintr_statvar_init(int, uint32_t *, uint32_t *, uint32_t *);
+uint64_t clockqueue_next(const struct clockintr_queue *);
 uint64_t nsec_advance(uint64_t *, uint64_t, uint64_t);
 
 /*
@@ -109,7 +111,8 @@ clockintr_cpu_init(const struct intrclock *ic)
 	KASSERT(ISSET(clockintr_flags, CL_INIT));
 
 	if (!ISSET(cq->cq_flags, CL_CPU_INIT)) {
-		cq->cq_next = 0;
+		TAILQ_INIT(&cq->cq_est);
+		TAILQ_INIT(&cq->cq_pend);
 		cq->cq_hardclock = clockintr_establish(cq, clockintr_hardclock);
 		if (cq->cq_hardclock == NULL)
 			panic("%s: failed to establish hardclock", __func__);
@@ -191,6 +194,7 @@ clockintr_dispatch(void *frame)
 {
 	uint64_t lateness, run = 0, start;
 	struct cpu_info *ci = curcpu();
+	struct clockintr *cl;
 	struct clockintr_queue *cq = &ci->ci_queue;
 	u_int ogen;
 
@@ -202,58 +206,52 @@ clockintr_dispatch(void *frame)
 	KASSERT(ISSET(cq->cq_flags, CL_CPU_INIT));
 
 	/*
-	 * If we arrived too early we have nothing to do.
+	 * If nothing is scheduled or we arrived too early, we have
+	 * nothing to do.
 	 */
 	start = nsecuptime();
 	cq->cq_uptime = start;
-	if (cq->cq_uptime < cq->cq_next)
-		goto done;
-	lateness = start - cq->cq_next;
+	if (TAILQ_EMPTY(&cq->cq_pend))
+		goto stats;
+	if (cq->cq_uptime < clockqueue_next(cq))
+		goto rearm;
+	lateness = start - clockqueue_next(cq);
 
 	/*
 	 * Dispatch expired events.
 	 */
-again:
-	/* hardclock */
-	if (cq->cq_hardclock->cl_expiration <= cq->cq_uptime) {
-		cq->cq_hardclock->cl_func(cq->cq_hardclock, frame);
-		run++;
-	}
-
-	/* statclock */
-	if (cq->cq_statclock->cl_expiration <= cq->cq_uptime) {
-		cq->cq_statclock->cl_func(cq->cq_statclock, frame);
-		run++;
-	}
-
-	/* schedclock */
-	if (ISSET(clockintr_flags, CL_SCHEDCLOCK)) {
-		if (cq->cq_schedclock->cl_expiration <= cq->cq_uptime) {
-			cq->cq_schedclock->cl_func(cq->cq_schedclock, frame);
-			run++;
+	for (;;) {
+		cl = TAILQ_FIRST(&cq->cq_pend);
+		if (cl == NULL)
+			break;
+		if (cq->cq_uptime < cl->cl_expiration) {
+			/* Double-check the time before giving up. */
+			cq->cq_uptime = nsecuptime();
+			if (cq->cq_uptime < cl->cl_expiration)
+				break;
 		}
-	}
+		TAILQ_REMOVE(&cq->cq_pend, cl, cl_plink);
+		CLR(cl->cl_flags, CLST_PENDING);
+		cq->cq_running = cl;
 
-	/* Run the dispatch again if the next event has already expired. */
-	cq->cq_next = cq->cq_hardclock->cl_expiration;
-	if (cq->cq_statclock->cl_expiration < cq->cq_next)
-		cq->cq_next = cq->cq_statclock->cl_expiration;
-	if (ISSET(clockintr_flags, CL_SCHEDCLOCK)) {
-		if (cq->cq_schedclock->cl_expiration < cq->cq_next)
-			cq->cq_next = cq->cq_schedclock->cl_expiration;
+		cl->cl_func(cl, frame);
+
+		cq->cq_running = NULL;
+		run++;
 	}
-	cq->cq_uptime = nsecuptime();
-	if (cq->cq_next <= cq->cq_uptime)
-		goto again;
 
 	/*
 	 * Dispatch complete.
 	 */
-done:
+rearm:
 	/* Rearm the interrupt clock if we have one. */
-	if (ISSET(cq->cq_flags, CL_CPU_INTRCLOCK))
-		intrclock_rearm(&cq->cq_intrclock, cq->cq_next - cq->cq_uptime);
-
+	if (ISSET(cq->cq_flags, CL_CPU_INTRCLOCK)) {
+		if (!TAILQ_EMPTY(&cq->cq_pend)) {
+			intrclock_rearm(&cq->cq_intrclock,
+			    clockqueue_next(cq) - cq->cq_uptime);
+		}
+	}
+stats:
 	/* Update our stats. */
 	ogen = cq->cq_gen;
 	cq->cq_gen = 0;
@@ -263,10 +261,11 @@ done:
 		cq->cq_stat.cs_lateness += lateness;
 		cq->cq_stat.cs_prompt++;
 		cq->cq_stat.cs_run += run;
-	} else {
+	} else if (!TAILQ_EMPTY(&cq->cq_pend)) {
 		cq->cq_stat.cs_early++;
-		cq->cq_stat.cs_earliness += cq->cq_next - cq->cq_uptime;
-	}
+		cq->cq_stat.cs_earliness += clockqueue_next(cq) - cq->cq_uptime;
+	} else
+		cq->cq_stat.cs_spurious++;
 	membar_producer();
 	cq->cq_gen = MAX(1, ogen + 1);
 
@@ -280,8 +279,12 @@ done:
 uint64_t
 clockintr_advance(struct clockintr *cl, uint64_t period)
 {
-	return nsec_advance(&cl->cl_expiration, period,
-	    cl->cl_queue->cq_uptime);
+	uint64_t count, expiration;
+
+	expiration = cl->cl_expiration;
+	count = nsec_advance(&expiration, period, cl->cl_queue->cq_uptime);
+	clockintr_schedule(cl, expiration);
+	return count;
 }
 
 struct clockintr *
@@ -295,6 +298,7 @@ clockintr_establish(struct clockintr_queue *cq,
 		return NULL;
 	cl->cl_func = func;
 	cl->cl_queue = cq;
+	TAILQ_INSERT_TAIL(&cq->cq_est, cl, cl_elink);
 	return cl;
 }
 
@@ -307,7 +311,24 @@ clockintr_expiration(const struct clockintr *cl)
 void
 clockintr_schedule(struct clockintr *cl, uint64_t expiration)
 {
+	struct clockintr *elm;
+	struct clockintr_queue *cq = cl->cl_queue;
+
+	if (ISSET(cl->cl_flags, CLST_PENDING)) {
+		TAILQ_REMOVE(&cq->cq_pend, cl, cl_plink);
+		CLR(cl->cl_flags, CLST_PENDING);
+	}
+
 	cl->cl_expiration = expiration;
+	TAILQ_FOREACH(elm, &cq->cq_pend, cl_plink) {
+		if (cl->cl_expiration < elm->cl_expiration)
+			break;
+	}
+	if (elm == NULL)
+		TAILQ_INSERT_TAIL(&cq->cq_pend, cl, cl_plink);
+	else
+		TAILQ_INSERT_BEFORE(elm, cl, cl_plink);
+	SET(cl->cl_flags, CLST_PENDING);
 }
 
 /*
@@ -435,6 +456,12 @@ clockintr_statclock(struct clockintr *cl, void *frame)
 		statclock(frame);
 }
 
+uint64_t
+clockqueue_next(const struct clockintr_queue *cq)
+{
+	return TAILQ_FIRST(&cq->cq_pend)->cl_expiration;
+}
+
 /*
  * Advance *next in increments of period until it exceeds now.
  * Returns the number of increments *next was advanced.
@@ -492,6 +519,7 @@ sysctl_clockintr(int *name, u_int namelen, void *oldp, size_t *oldlenp,
 			sum.cs_lateness += tmp.cs_lateness;
 			sum.cs_prompt += tmp.cs_prompt;
 			sum.cs_run += tmp.cs_run;
+			sum.cs_spurious += tmp.cs_spurious;
 		}
 		return sysctl_rdstruct(oldp, oldlenp, newp, &sum, sizeof sum);
 	default:
@@ -533,13 +561,18 @@ db_show_all_clockintr(db_expr_t addr, int haddr, db_expr_t count, char *modif)
 void
 db_show_clockintr_cpu(struct cpu_info *ci)
 {
+	struct clockintr *elm;
 	struct clockintr_queue *cq = &ci->ci_queue;
 	u_int cpu = CPU_INFO_UNIT(ci);
 
-	db_show_clockintr(cq->cq_hardclock, cpu);
-	db_show_clockintr(cq->cq_statclock, cpu);
-	if (cq->cq_schedclock != NULL)
-		db_show_clockintr(cq->cq_schedclock, cpu);
+	if (cq->cq_running != NULL)
+		db_show_clockintr(cq->cq_running, cpu);
+	TAILQ_FOREACH(elm, &cq->cq_pend, cl_plink)
+		db_show_clockintr(elm, cpu);
+	TAILQ_FOREACH(elm, &cq->cq_est, cl_elink) {
+		if (!ISSET(elm->cl_flags, CLST_PENDING))
+			db_show_clockintr(elm, cpu);
+	}
 }
 
 void