From nobody Wed Jun 18 02:13:20 2025 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4bMS2S6dtTz5q6W4; Wed, 18 Jun 2025 02:13:20 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R11" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4bMS2S2QB2z41WM; Wed, 18 Jun 2025 02:13:20 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212800; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=V1NJhVAvG2Tk9UVUR6jaPgfHPoz3MGqLZEHB1dA2NV0=; b=qHloo9a86G2rucTy1b4+sXzuz6B+ALTy7+pZNWdihmSmfl5SA4E6OMA+bEI4hy8nRegug/ AOCUBZtlnau4qprifrkhVJJ2YYA4NAvdySyPsNxsnCLHPj93qgkAvLtttJJ7HdEb5e92Hc NIfXEGYk5l1wzymPiWw1yyqF6kb0KziIKiXJjdZRhkwITa121tmJIo0Qewejo2YlkTf40Q IyQxhLiLIvrnN4XLark60Y1zsJb3AslojomYucjhL1wXsQEfKlK0HCAL95JHlcGtBIINQK E8sAX6KVZoNZZ4boQ7a04KLtJuYNKcbXMd7vE2U12J/R17wuCVicXyDSBzC7lw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212800; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=V1NJhVAvG2Tk9UVUR6jaPgfHPoz3MGqLZEHB1dA2NV0=; b=mv3Vq5v2ynNTtnK9GHoHlLsAVaQijF5VaV8qH/On/mbSflbjM/tHGI1y9xahmpruEnO4gz 8OfFlVkpHvBpQlN+rqueoJEF02WBdfQeMlU1mkuX8ub+xGsOwC/+ScRtyn+YMUU9mu0Xzl LShTirElOAQIZ6S7lq8WDEHrQDFajk+b63GP+VuA/2Igz3XCyk1CyIKxIPHsYy+/IgcHjw OqGv/5U6YGoD5qDU3XGE5FD71xuX2/0mCN9ihYPh6DNH1QubT1uL55fJry7y5PaxqYy7B6 r8z9+FlE37D4u6LBq9hsiIhx3hUU4dYgB+fI1b5d0Mg8Jw2nriKPpV8QKRgtjw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1750212800; a=rsa-sha256; cv=none; b=azph5PY93B8/PXnzMH3YxM+SLd3wvt0yF21XWjbp8+oomKC/cqX9JDVih+1T9CO/mnvcfU GOrZ+BqgA2RuGXL9AE9eO9W2mfWOwIpZsDiUDlUQaceJHA01owjeMYaUVzZWSjyPY2B9B2 y36F/FuUAL1exmClA2zucR2QdQzEV46SYz05eX1f1P6yWfJHPeItT6szodvFpLWyvflkCw klA6cHYLU8wfVgzos/IHTnhB+FgM4DKPjBJAuWzWyBL76qBFcEmm3SZUP+oBMSpqTj66ix IhTzyq4L2jHkuqHO/rPH4A15F7nn9iLJcUkAPu9Qz/YfPJuO06LPOVIuyxNJ4Q== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4bMS2S1qfcz17pr; Wed, 18 Jun 2025 02:13:20 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.18.1/8.18.1) with ESMTP id 55I2DK2B024304; Wed, 18 Jun 2025 02:13:20 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 55I2DKu0024301; Wed, 18 Jun 2025 02:13:20 GMT (envelope-from git) Date: Wed, 18 Jun 2025 02:13:20 GMT Message-Id: <202506180213.55I2DKu0024301@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Olivier Certner Subject: git: 9c3f4682bb90 - main - runq: New runq_findq(), common low-level search implementation List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: olce X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 9c3f4682bb90eeb85b0bbe8728a493e7d2ffece3 Auto-Submitted: auto-generated The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=9c3f4682bb90eeb85b0bbe8728a493e7d2ffece3 commit 9c3f4682bb90eeb85b0bbe8728a493e7d2ffece3 Author: Olivier Certner AuthorDate: 2024-04-26 01:57:25 +0000 Commit: Olivier Certner 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);