From nobody Wed Jun 18 02:13:15 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 4bMS2N2Smvz5q6fk; Wed, 18 Jun 2025 02:13:16 +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 4bMS2M6Rlrz41SF; Wed, 18 Jun 2025 02:13:15 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212795; 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=lyhFAhPJJBIwSaSvrZBaVHbcKIENMd+xEMq6YmSIldo=; b=HDn1pYUVEd20H0FFo468cPuGROhZ+Cd83aj5ahSy+wMi1YQX5GjJnWxtg7FRis7EDvKaGO m3KA4Z0ELbpraHghyetQfH0DA4U9LmUCZ6GdIO9wZHG10qIeCwOcMhCWz/iNkZUkh6IKhl VZSnS3IkrosJE3KkK6prJVBfjmDUqH+Q4mjbK7VeQuZOle0ZeZfkY6p+b9OqcSxIQPfX20 KPV2S7qlWy2gLNhnWHpZw4477ivNRetDDdW352LSEvb8JQ4RLGi1mlDKR0ARKsqO4hcXtF xDcEjChvgKZFVbFF6tlmmQx6mOrk9xDKTSP5k96zZpXtkzLn0quJ9PAXtTUlQQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212795; 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=lyhFAhPJJBIwSaSvrZBaVHbcKIENMd+xEMq6YmSIldo=; b=xBqJLNEIO8YPJnckp4zVVgiE+g7qNe8oGmzuP/YML6Ln6YcDdKSVHQ9jaqDm7vVnMkBU87 3l4GE5NNyG9QZacInnmdbCU+66Eb0hmLh2HiKs4gCNL257DUyYh36qdg//D81eYRA1sNU4 53bGe+PHRy8rkH3C70WcssnoXpcqwzZs2zTR8rE+pUN6Ga0w5nZyFG3Btmyi9hOcXrB21i PE7fGnScCUecd0pwxskZzfx+ONTdeypeWPqUge4Ke0hq1s5M/WJDZa7JKVf/emqyysU1ot fnmwMC32l0qVYbPSGD2n4HO0n3bg7+pHPTqCInfDyHvBqprI8++88PeDjHxnzA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1750212795; a=rsa-sha256; cv=none; b=HI0ekzBDRwQrYypD7zqlPFl+O90aHykfNtFfWfPYSZXTNu3l633m8SVfbL74ou5vOtJ0kD sueJ7n3UZJnx05oaKdclc0PyjttlBIglFhnB3aEruFQVvGYBCv3zzXaMcRUOFgVqxlkQU2 FMo0dcXleT7WMOjaqwNx3KkAILgoT/pLWvZkVvhInPeoFbrLeTvAhNNAFlNvT+OmSZ9T74 BrNmzGTWfFggNZODNtAjaEQwyBOoCTnJ0M8dIc9Jax9jMSbfXjtYycMM5FY4Um48R5aY9V SpS4L3rx5/WumZPpAzzwVPMwW//4uqPlAeLj5tjNnnvOfi/ZPNrCbhBk00buEg== 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 4bMS2M5hv0z18Qp; Wed, 18 Jun 2025 02:13:15 +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 55I2DFwN024169; Wed, 18 Jun 2025 02:13:15 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 55I2DFJs024166; Wed, 18 Jun 2025 02:13:15 GMT (envelope-from git) Date: Wed, 18 Jun 2025 02:13:15 GMT Message-Id: <202506180213.55I2DFJs024166@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: 439dc920f2d8 - main - runq: Revamp runq_find*(), new runq_find_range() 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: 439dc920f2d88e3fe2869a2845f15d8ab44cc051 Auto-Submitted: auto-generated The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=439dc920f2d88e3fe2869a2845f15d8ab44cc051 commit 439dc920f2d88e3fe2869a2845f15d8ab44cc051 Author: Olivier Certner AuthorDate: 2024-02-29 08:57:10 +0000 Commit: Olivier Certner CommitDate: 2025-06-18 02:07:59 +0000 runq: Revamp runq_find*(), new runq_find_range() Rename existing functions to use the simpler prefix 'runq_findq' instead of 'runq_findbit' (that they work on top of bit runs is an implementation detail). Add runq_findq_range(), which takes a range of indices to operate on (bounds included). This is in preparation for changing ULE to use a single runqueue, since it needs to treat the timesharing range differently. Rename runq_findbit_from() to runq_findq_circular(), which is more descriptive. To reduce code duplication, have runq_findq() and runq_findq_circular() leverage runq_findq_range() internally. For the latter, this also brings a small algorithmic improvement, since previously the second pass (from queue 0) would cover the whole runqueue if it was completely empty, scanning again empty queues after the start index. 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 | 101 ++++++++++++++++++++++++++++--------------------- 1 file changed, 58 insertions(+), 43 deletions(-) diff --git a/sys/kern/kern_switch.c b/sys/kern/kern_switch.c index 69e6f4818e40..a321aecc55fb 100644 --- a/sys/kern/kern_switch.c +++ b/sys/kern/kern_switch.c @@ -370,57 +370,72 @@ runq_remove(struct runq *rq, struct thread *td) } /* - * Find the index of the first non-empty run queue. This is done by - * scanning the status bits, a set bit indicating a non-empty queue. + * 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. */ -static __inline int -runq_findbit(struct runq *rq) +static int +runq_findq_range(const struct runq *const rq, const int lvl_min, + const int lvl_max) { - struct rq_status *rqs; - int idx; + rqsw_t const (*const rqsw)[RQSW_NB] = &rq->rq_status.rq_sw; + rqsw_t w; + int i, last, idx; + + CHECK_IDX(lvl_min); + CHECK_IDX(lvl_max); + KASSERT(lvl_min <= lvl_max, + ("lvl_min: %d > lvl_max: %d!", lvl_min, lvl_max)); + + i = RQSW_IDX(lvl_min); + last = RQSW_IDX(lvl_max); + /* Clear bits for runqueues below 'lvl_min'. */ + w = (*rqsw)[i] & ~(RQSW_BIT(lvl_min) - 1); + if (i == last) + goto last_mask; + if (w != 0) + goto return_idx; + + for (++i; i < last; ++i) { + w = (*rqsw)[i]; + if (w != 0) + goto return_idx; + } - rqs = &rq->rq_status; - for (int i = 0; i < RQSW_NB; i++) - if (rqs->rq_sw[i] != 0) { - idx = RQSW_FIRST_QUEUE_IDX(i, rqs->rq_sw[i]); - CHECK_IDX(idx); - CTR3(KTR_RUNQ, "runq_findbit: bits=%#x i=%d idx=%d", - rqs->rq_sw[i], i, idx); - return (idx); - } + MPASS(i == last); + w = (*rqsw)[i]; +last_mask: + /* Clear bits for runqueues above 'lvl_max'. */ + w &= (RQSW_BIT(lvl_max) - 1) | RQSW_BIT(lvl_max); + if (w != 0) + 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", + (*rqsw)[i], w, i, idx); + return (idx); } static __inline int -runq_findbit_from(struct runq *rq, int idx) +runq_findq_circular(struct runq *const rq, int start_idx) { - struct rq_status *rqs; - rqsw_t mask; - int i; + int idx; - CHECK_IDX(idx); - /* Set the mask for the first word so we ignore indices before 'idx'. */ - mask = (rqsw_t)-1 << RQSW_BIT_IDX(idx); - rqs = &rq->rq_status; -again: - for (i = RQSW_IDX(idx); i < RQSW_NB; mask = -1, i++) { - mask = rqs->rq_sw[i] & mask; - if (mask == 0) - continue; - idx = RQSW_FIRST_QUEUE_IDX(i, mask); - CTR3(KTR_RUNQ, "runq_findbit_from: bits=%#x i=%d idx=%d", - mask, i, idx); + idx = runq_findq_range(rq, start_idx, RQ_NQS - 1); + if (idx != -1 || start_idx == 0) return (idx); - } - if (idx == 0) - return (-1); - /* - * Wrap back around to the beginning of the list just once so we - * scan the whole thing. - */ - idx = 0; - goto again; + + return (runq_findq_range(rq, 0, start_idx - 1)); +} + +static __inline int +runq_findq(struct runq *const rq) +{ + + return (runq_findq_range(rq, 0, RQ_NQS - 1)); } /* @@ -454,7 +469,7 @@ runq_choose(struct runq *rq) struct thread *td; int idx; - idx = runq_findbit(rq); + idx = runq_findq(rq); if (idx != -1) { rqq = &rq->rq_queues[idx]; td = TAILQ_FIRST(rqq); @@ -478,7 +493,7 @@ runq_choose_fuzz(struct runq *rq, int fuzz) struct thread *td; int idx; - idx = runq_findbit(rq); + idx = runq_findq(rq); if (idx != -1) { rqq = &rq->rq_queues[idx]; /* fuzz == 1 is normal.. 0 or less are ignored */ @@ -518,7 +533,7 @@ runq_choose_from(struct runq *rq, int from_idx) struct thread *td; int idx; - if ((idx = runq_findbit_from(rq, from_idx)) != -1) { + 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"));