From nobody Mon Jul 28 13:31:15 2025 X-Original-To: dev-commits-src-all@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 4brKBD4Jhgz634WG; Mon, 28 Jul 2025 13:31: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 "R10" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4brKBD21g9z3tby; Mon, 28 Jul 2025 13:31:16 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1753709476; 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=dVqaGJu2yTtt945uaBEBZS9vxm/WgNIvqrZRivNKHDY=; b=Gc/1vqnEpUq3rBuVCMxs8XZPh17QicW5NOWFw6WAzHFoHrOoxtoUV+uZnYIOSMYJn6wK/u VK7gNOTFxDLPILELTVnU6oy+nJiSCjeTtthz0QJSz4m/3FCDj2sextYrYhXOjtlA4pGanX 3+5FxyhzMmSIhmCmZ8AkIgRHiIBacV3VDX+qAp0NHLeag1BW/95yu4kZ0k7+b/RCIYwunC 4ZmfZ1/Cf7LBQ0hEl7BCEx+rLqh57IO0qjlIWbeZgsux6HH2kG6J07wESZmojghO0ybiQU Hail8eGRQGirl9vyRyPpsACF+8r4TA86TdCm6luxD4eclr0Q3+it+DxAeN6mMQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1753709476; 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=dVqaGJu2yTtt945uaBEBZS9vxm/WgNIvqrZRivNKHDY=; b=S/iatzdrwi+bM4PrJTDnCDsAJOJJBFBMumOJUmDwCjXLE8JqQWRFFj9dswSJ2IbuhV62VP YbwM2qP3hpc0q7i70oC7tYOttwc5GptuU1uxH0MQwY1KhpEWN/9BXNm9aIoDI6+dT6FZf8 EVlgyOWX+X+EPpnPR7dBCgQFRMDPslnirRPJv2IR1tU+eH6YRSXf9zGPx0r2vjNtVV+hAB IUxuAw+mSxt+ccvPRNtZmO44+bZlD1EHPYMNzuLUGt/ow5AaOV7EIjrTZBC0hKAlTgO8Mw NcRArnlOIbHgzLrXJwPbT85ocxKXiAajEaW7r4/vpNJEkjYN/AckEfqpPjODAg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1753709476; a=rsa-sha256; cv=none; b=ZdPFLH5wSsrFu4oY158bMPgA6mPW1ktj4VEy4QRcEyGaXMHqhJXJtmlePBFUIsrbgYbFRV dkZbPiwVG3BGx+zQjkNPIJBPqFZoW2nJkKoDpD6Eo6ms0Fk0reaNLGbnKSN1YU4MmvVFsA /Wt6eNQ5VQlcLpl6rsxpZLEdIzQQYqQj9SEHsjrMHN4SUADHdtQNfhuRmeL6DcQ0wQPs2g BVrrs3sFszUj+62gGEh3o/oq7/ecTLE1tFA1zLzDXON2vBwEudlLZEPVSg0wQ59zItRkqJ TUXgKvVyldk2cg2gdXmo/FX3aQt3dqn3AcSoVl1mKrxi8LkCAez2t8g2Lsot+w== 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 4brKBD0P7zznG1; Mon, 28 Jul 2025 13:31:16 +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 56SDVFUM080121; Mon, 28 Jul 2025 13:31:15 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 56SDVFAk080118; Mon, 28 Jul 2025 13:31:15 GMT (envelope-from git) Date: Mon, 28 Jul 2025 13:31:15 GMT Message-Id: <202507281331.56SDVFAk080118@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Olivier Certner Subject: git: de0e1a3abf8b - stable/14 - runq: Revamp runq_find*(), new runq_find_range() List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-all@freebsd.org Sender: owner-dev-commits-src-all@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/stable/14 X-Git-Reftype: branch X-Git-Commit: de0e1a3abf8b144650173e639337c31a3eaf874f Auto-Submitted: auto-generated The branch stable/14 has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=de0e1a3abf8b144650173e639337c31a3eaf874f commit de0e1a3abf8b144650173e639337c31a3eaf874f Author: Olivier Certner AuthorDate: 2024-02-29 08:57:10 +0000 Commit: Olivier Certner CommitDate: 2025-07-28 13:28:09 +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 (cherry picked from commit 439dc920f2d88e3fe2869a2845f15d8ab44cc051) --- 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"));