clockintr: add a priority queue
authorcheloha <cheloha@openbsd.org>
Thu, 9 Mar 2023 03:50:38 +0000 (03:50 +0000)
committercheloha <cheloha@openbsd.org>
Thu, 9 Mar 2023 03:50:38 +0000 (03:50 +0000)
commitf95e54362089898edf0aad9b7a7e5cbf9bb6f2b0
tree62648d9f25dccb88281b35afc0c055c85b3dfc81
parenteb7cd0035470442bb2d6a5b4fe84b701cfeb379a
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@
sys/kern/kern_clockintr.c
sys/sys/clockintr.h