Date: Wed, 18 Jun 2025 02:13:20 GMT From: Olivier Certner <olce@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 9c3f4682bb90 - main - runq: New runq_findq(), common low-level search implementation Message-ID: <202506180213.55I2DKu0024301@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=9c3f4682bb90eeb85b0bbe8728a493e7d2ffece3 commit 9c3f4682bb90eeb85b0bbe8728a493e7d2ffece3 Author: Olivier Certner <olce@FreeBSD.org> AuthorDate: 2024-04-26 01:57:25 +0000 Commit: Olivier Certner <olce@FreeBSD.org> CommitDate: 2025-06-18 02:08:00 +0000 runq: New runq_findq(), common low-level search implementation That new runq_findq(), based on the implementation of the former runq_findq_range(), is intended to become the foundation and unique low-level implementation for all searches in a runqueue. In addition to a range of queues' indices, it takes a predicate function, allowing to: - Possibly skip a non-empty queue with higher priority (numerically lower index) on some criteria. This is not yet used but will be in a subsequent commit revising ULE's stealing machinery. - Choose a specific thread in the queue, not necessarily the first. - Return whatever information is deemed necessary. It helps to remove duplicated boilerplate code, including redundant assertions, and generally makes things much clearer. These effects will be even greater in a subsequent commit modifying ULE to use it. runq_first_thread_range() replaces the old runq_findq_range() (returns the first thread of the highest priority queue in the requested range), and runq_first_thread() the old runq_findq() (same, but considering all queues). Reviewed by: kib MFC after: 1 month Event: Kitchener-Waterloo Hackathon 202506 Sponsored by: The FreeBSD Foundation Differential Revision: https://reviews.freebsd.org/D45387 --- sys/kern/kern_switch.c | 203 ++++++++++++++++++++++++++++++------------------- sys/sys/runq.h | 13 +++- 2 files changed, 135 insertions(+), 81 deletions(-) diff --git a/sys/kern/kern_switch.c b/sys/kern/kern_switch.c index b23dfa162c4f..9a05f3c90a80 100644 --- a/sys/kern/kern_switch.c +++ b/sys/kern/kern_switch.c @@ -445,15 +445,44 @@ runq_remove(struct runq *rq, struct thread *td) return (false); } +static inline int +runq_findq_status_word(struct runq *const rq, const int w_idx, + const rqsw_t w, runq_pred_t *const pred, void *const pred_data) +{ + struct rq_queue *q; + rqsw_t tw = w; + int idx, b_idx; + + while (tw != 0) { + b_idx = RQSW_BSF(tw); + idx = RQSW_TO_QUEUE_IDX(w_idx, b_idx); + q = &rq->rq_queues[idx]; + KASSERT(!TAILQ_EMPTY(q), + ("runq_findq(): No thread on non-empty queue with idx=%d", + idx)); + if (pred(idx, q, pred_data)) + return (idx); + tw &= ~RQSW_BIT(idx); + } + + return (-1); +} + /* - * Find the index of the first (i.e., having lower index) non-empty queue in the - * passed range (bounds included). This is done by scanning the status bits, - * a set bit indicating a non-empty queue. Returns -1 if all queues in the range - * are empty. + * Find in the passed range (bounds included) the index of the first (i.e., + * having lower index) non-empty queue that passes pred(). + * + * Considered queues are those with index 'lvl_min' up to 'lvl_max' (bounds + * included). If no queue matches, returns -1. + * + * This is done by scanning the status words (a set bit indicates a non-empty + * queue) and calling pred() with corresponding queue indices. pred() must + * return whether the corresponding queue is accepted. It is passed private + * data through 'pred_data', which can be used both for extra input and output. */ -static int -runq_findq_range(const struct runq *const rq, const int lvl_min, - const int lvl_max) +int +runq_findq(struct runq *const rq, const int lvl_min, const int lvl_max, + runq_pred_t *const pred, void *const pred_data) { rqsw_t const (*const rqsw)[RQSW_NB] = &rq->rq_status.rq_sw; rqsw_t w; @@ -470,12 +499,14 @@ runq_findq_range(const struct runq *const rq, const int lvl_min, w = (*rqsw)[i] & ~(RQSW_BIT(lvl_min) - 1); if (i == last) goto last_mask; - if (w != 0) + idx = runq_findq_status_word(rq, i, w, pred, pred_data); + if (idx != -1) goto return_idx; for (++i; i < last; ++i) { w = (*rqsw)[i]; - if (w != 0) + idx = runq_findq_status_word(rq, i, w, pred, pred_data); + if (idx != -1) goto return_idx; } @@ -484,34 +515,45 @@ runq_findq_range(const struct runq *const rq, const int lvl_min, last_mask: /* Clear bits for runqueues above 'lvl_max'. */ w &= (RQSW_BIT(lvl_max) - 1) | RQSW_BIT(lvl_max); - if (w != 0) + idx = runq_findq_status_word(rq, i, w, pred, pred_data); + if (idx != -1) goto return_idx; - return (-1); return_idx: - idx = RQSW_FIRST_QUEUE_IDX(i, w); - CTR4(KTR_RUNQ, "runq_findq_range: bits=%#x->%#x i=%d idx=%d", + CTR4(KTR_RUNQ, "runq_findq: bits=%#x->%#x i=%d idx=%d", (*rqsw)[i], w, i, idx); return (idx); } -static __inline int -runq_findq_circular(struct runq *const rq, int start_idx) +static bool +runq_first_thread_pred(const int idx, struct rq_queue *const q, void *const data) { - int idx; + struct thread **const tdp = data; + struct thread *const td = TAILQ_FIRST(q); - idx = runq_findq_range(rq, start_idx, RQ_NQS - 1); - if (idx != -1 || start_idx == 0) - return (idx); + *tdp = td; + return (true); +} - return (runq_findq_range(rq, 0, start_idx - 1)); +/* + * Inline this function for the benefit of this file's internal uses, but make + * sure it has an external definition as it is exported. + */ +extern inline struct thread * +runq_first_thread_range(struct runq *const rq, const int lvl_min, + const int lvl_max) +{ + struct thread *td = NULL; + + (void)runq_findq(rq, lvl_min, lvl_max, runq_first_thread_pred, &td); + return (td); } -static __inline int -runq_findq(struct runq *const rq) +static inline struct thread * +runq_first_thread(struct runq *const rq) { - return (runq_findq_range(rq, 0, RQ_NQS - 1)); + return (runq_first_thread_range(rq, 0, RQ_NQS - 1)); } /* @@ -521,11 +563,11 @@ runq_findq(struct runq *const rq) bool runq_not_empty(struct runq *rq) { - int idx; + struct thread *const td = runq_first_thread(rq); - idx = runq_findq(rq); - if (idx != -1) { - CTR1(KTR_RUNQ, "runq_not_empty: idx=%d", idx); + if (td != NULL) { + CTR2(KTR_RUNQ, "runq_not_empty: idx=%d, td=%p", + td->td_rqindex, td); return (true); } @@ -539,84 +581,85 @@ runq_not_empty(struct runq *rq) struct thread * runq_choose(struct runq *rq) { - struct rq_queue *rqq; struct thread *td; - int idx; - idx = runq_findq(rq); - if (idx != -1) { - rqq = &rq->rq_queues[idx]; - td = TAILQ_FIRST(rqq); - KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); - CTR3(KTR_RUNQ, - "runq_choose: idx=%d thread=%p rqq=%p", idx, td, rqq); + td = runq_first_thread(rq); + if (td != NULL) { + CTR2(KTR_RUNQ, "runq_choose: idx=%d td=%p", td->td_rqindex, td); return (td); } - CTR1(KTR_RUNQ, "runq_choose: idlethread idx=%d", idx); + CTR0(KTR_RUNQ, "runq_choose: idlethread"); return (NULL); } +struct runq_fuzz_pred_data { + int fuzz; + struct thread *td; +}; + +static bool +runq_fuzz_pred(const int idx, struct rq_queue *const q, void *const data) +{ + struct runq_fuzz_pred_data *const d = data; + const int fuzz = d->fuzz; + struct thread *td; + + td = TAILQ_FIRST(q); + + if (fuzz > 1) { + /* + * In the first couple of entries, check if + * there is one for our CPU as a preference. + */ + struct thread *td2 = td; + int count = fuzz; + int cpu = PCPU_GET(cpuid); + + while (count-- != 0 && td2 != NULL) { + if (td2->td_lastcpu == cpu) { + td = td2; + break; + } + td2 = TAILQ_NEXT(td2, td_runq); + } + } + + d->td = td; + return (true); +} + /* * Find the highest priority process on the run queue. */ struct thread * runq_choose_fuzz(struct runq *rq, int fuzz) { - struct rq_queue *rqq; - struct thread *td; + struct runq_fuzz_pred_data data = { + .fuzz = fuzz, + .td = NULL + }; int idx; - idx = runq_findq(rq); + idx = runq_findq(rq, 0, RQ_NQS - 1, runq_fuzz_pred, &data); if (idx != -1) { - rqq = &rq->rq_queues[idx]; - /* fuzz == 1 is normal.. 0 or less are ignored */ - if (fuzz > 1) { - /* - * In the first couple of entries, check if - * there is one for our CPU as a preference. - */ - int count = fuzz; - int cpu = PCPU_GET(cpuid); - struct thread *td2; - td2 = td = TAILQ_FIRST(rqq); - - while (count-- && td2) { - if (td2->td_lastcpu == cpu) { - td = td2; - break; - } - td2 = TAILQ_NEXT(td2, td_runq); - } - } else - td = TAILQ_FIRST(rqq); - KASSERT(td != NULL, ("runq_choose_fuzz: no proc on busy queue")); - CTR3(KTR_RUNQ, - "runq_choose_fuzz: idx=%d thread=%p rqq=%p", idx, td, rqq); - return (td); + MPASS(data.td != NULL); + CTR2(KTR_RUNQ, "runq_choose_fuzz: idx=%d td=%p", idx, data.td); + return (data.td); } - CTR1(KTR_RUNQ, "runq_choose_fuzz: idleproc idx=%d", idx); + MPASS(data.td == NULL); + CTR0(KTR_RUNQ, "runq_choose_fuzz: idlethread"); return (NULL); } struct thread * -runq_choose_from(struct runq *rq, int from_idx) +runq_choose_from(struct runq *const rq, int from_idx) { - struct rq_queue *rqq; struct thread *td; - int idx; - if ((idx = runq_findq_circular(rq, from_idx)) != -1) { - rqq = &rq->rq_queues[idx]; - td = TAILQ_FIRST(rqq); - KASSERT(td != NULL, ("runq_choose: no thread on busy queue")); - CTR4(KTR_RUNQ, - "runq_choose_from: idx=%d thread=%p idx=%d rqq=%p", - idx, td, td->td_rqindex, rqq); + td = runq_first_thread_range(rq, from_idx, RQ_NQS - 1); + if (td != NULL || from_idx == 0) return (td); - } - CTR1(KTR_RUNQ, "runq_choose_from: idlethread idx=%d", idx); - - return (NULL); + return (runq_first_thread_range(rq, 0, from_idx - 1)); } diff --git a/sys/sys/runq.h b/sys/sys/runq.h index 5156a7d8c307..0a7f70fcfa16 100644 --- a/sys/sys/runq.h +++ b/sys/sys/runq.h @@ -103,7 +103,18 @@ void runq_add(struct runq *, struct thread *, int _flags); void runq_add_idx(struct runq *, struct thread *, int _idx, int _flags); bool runq_remove(struct runq *, struct thread *); -bool runq_not_empty(struct runq *); +/* + * Implementation helpers for common and scheduler-specific runq_choose*() + * functions. + */ +typedef bool runq_pred_t(int _idx, struct rq_queue *, void *_data); +int runq_findq(struct runq *const rq, const int lvl_min, + const int lvl_max, + runq_pred_t *const pred, void *const pred_data); +struct thread *runq_first_thread_range(struct runq *const rq, + const int lvl_min, const int lvl_max); + +bool runq_not_empty(struct runq *); struct thread *runq_choose(struct runq *); struct thread *runq_choose_fuzz(struct runq *, int _fuzz); struct thread *runq_choose_from(struct runq *, int _idx);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202506180213.55I2DKu0024301>