From nobody Mon Jul 28 13:31:21 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 4brKBL1lWWz634qb; Mon, 28 Jul 2025 13:31:22 +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 4brKBK54hZz3tnX; Mon, 28 Jul 2025 13:31:21 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1753709481; 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=mCzAcl5Q4kw+TEPeKwZWW65fYBnqtQX3NuF6DwxCC9c=; b=lM9ZDuNVXQGNR0/rWdVDqHAq2nq9AxWY5ApQqJgSarA6awtaYc0NlRxMkkxvxWygMcqgwT EiecPLKXmdWrAwHb2h2Af/civep94UgX11f4hjr5FOTSpMGi0pixycdyzEQ+g3CLCa6vPM bGUrC+kasbT2z7F25Ii+kH6GSU9MLbvAFdDLQh0RV+wbpjD0EMA9xWKxQIcCaWEoKm9Vth L9a0BFep6pkYdienaGQYkuFjzmrMfLAL9o+7lbWOl7uzEGECLOcIbmwEHVYibf/E3NkXWZ Cg7UFMHDdzqiTQi7BoytAEU67LKL3P0sfSE8AycQ57p60WO/tVbML4zb9B3Slw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1753709481; 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=mCzAcl5Q4kw+TEPeKwZWW65fYBnqtQX3NuF6DwxCC9c=; b=fn8Djj/SUbAMiZzCpiwpjIaqUbRqScemaEazEjNvZSHOUTisam6t5PPN0TZaQVOoa1MkDd VzzD4JVdZ2Nz1thsGIWP5rDxfaeUcIoud2baFZrbtoYYNaXDiJX9JDKiQOLrnjD+YUsaor bdGR8lFnZi5dSDcYnik6WSPvGkKQoSfmsgkjpKrADLDWSXZdhanc8ULv4ouJg3bzaYj4lW R8uNUDnlRRKAsRuudUvRRMFUfnuAvTUugLrqoqT+P6Q4Fd2TBuyMYC70qoFVfe1e8sLTap U99m74Xh8kSyXEe9fkvuP924YcSei4PXA/75ZL5Jl4kbcFP5+2KvgYrTZ+UD+w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1753709481; a=rsa-sha256; cv=none; b=G/lT8m8gpE0EIOlqLQdJEp9RwhvcTb4VY+J5nBk+I1foQ7ejbgtjmzvcdqraes9n2TYKgz qQY+u0BBwU3upfvFlYTqhnAfNP/RiRDWLvZvLU+Lag0Dt40bPX60T+QE/kD4ejbsmE3Qu2 xZBwZ21jHFIPobkf9uDNai6ssclCPv1nxRr4g8XOzp+Ncza5VJUXlncGbFTVPweSFRAxPW Mj0U8m48RsTmYmVy8NArTB5oE8BFsry3cm+SOGoa7wvI97TGL9W/KM7rK/g4CkKHFq1Wsk AbzRxtOTPEzJAOdePlZsciTJZOJc2CK2sKwcYPl3nZaYpwLU7yVI+fhbZoZ6EA== 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 4brKBK4P1pznNs; Mon, 28 Jul 2025 13:31:21 +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 56SDVLRQ080294; Mon, 28 Jul 2025 13:31:21 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 56SDVLg3080291; Mon, 28 Jul 2025 13:31:21 GMT (envelope-from git) Date: Mon, 28 Jul 2025 13:31:21 GMT Message-Id: <202507281331.56SDVLg3080291@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: 952ccda22e27 - stable/14 - sched_ule: Re-implement stealing on top of runq common-code 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: 952ccda22e27a7321d07814bd19d2c407c366cd4 Auto-Submitted: auto-generated The branch stable/14 has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=952ccda22e27a7321d07814bd19d2c407c366cd4 commit 952ccda22e27a7321d07814bd19d2c407c366cd4 Author: Olivier Certner AuthorDate: 2024-04-29 00:55:40 +0000 Commit: Olivier Certner CommitDate: 2025-07-28 13:28:17 +0000 sched_ule: Re-implement stealing on top of runq common-code Stop using internal knowledge of runqueues. Remove duplicate boilerplate parts. Concretely, runq_steal() and runq_steal_from() are now implemented on top of runq_findq(). Besides considerably simplifying the code, this change also brings an algorithmic improvement since, previously, set bits in the runqueue's status words were found by testing each bit individually in a loop instead of using ffsl()/bsfl() (except for the first set bit per status word). This change also makes it more apparent that runq_steal_from() treats the first thread with highest priority specifically (which runq_steal() does not). MFC after: 1 month Event: Kitchener-Waterloo Hackathon 202506 Sponsored by: The FreeBSD Foundation Differential Revision: https://reviews.freebsd.org/D45388 (cherry picked from commit f4be333bc56759d33dca49ab4d19eaf22134e844) --- sys/kern/sched_ule.c | 124 ++++++++++++++++++++++++++++----------------------- 1 file changed, 68 insertions(+), 56 deletions(-) diff --git a/sys/kern/sched_ule.c b/sys/kern/sched_ule.c index d8abb911a887..2e01cf6c2484 100644 --- a/sys/kern/sched_ule.c +++ b/sys/kern/sched_ule.c @@ -1183,51 +1183,68 @@ tdq_notify(struct tdq *tdq, int lowpri) ipi_cpu(cpu, IPI_PREEMPT); } -/* - * Steals load from a timeshare queue. Honors the rotating queue head - * index. - */ -static struct thread * -runq_steal_from(struct runq *rq, int cpu, u_char start) +struct runq_steal_pred_data { + struct thread *td; + struct thread *first; + int cpu; + bool use_first_last; +}; + +static bool +runq_steal_pred(const int idx, struct rq_queue *const q, void *const data) { - struct rq_status *rqs; - struct rq_queue *rqq; - struct thread *td, *first; - int bit; - int i; + struct runq_steal_pred_data *const d = data; + struct thread *td; - rqs = &rq->rq_status; - bit = RQSW_BIT_IDX(start); - first = NULL; -again: - for (i = RQSW_IDX(start); i < RQSW_NB; bit = 0, i++) { - if (rqs->rq_sw[i] == 0) + TAILQ_FOREACH(td, q, td_runq) { + if (d->use_first_last && d->first == NULL) { + d->first = td; continue; - if (bit == 0) - bit = RQSW_BSF(rqs->rq_sw[i]); - for (; bit < RQSW_BPW; bit++) { - if ((rqs->rq_sw[i] & (1ul << bit)) == 0) - continue; - rqq = &rq->rq_queues[RQSW_TO_QUEUE_IDX(i, bit)]; - TAILQ_FOREACH(td, rqq, td_runq) { - if (first) { - if (THREAD_CAN_MIGRATE(td) && - THREAD_CAN_SCHED(td, cpu)) - return (td); - } else - first = td; - } + } + + if (THREAD_CAN_MIGRATE(td) && THREAD_CAN_SCHED(td, d->cpu)) { + d->td = td; + return (true); } } - if (start != 0) { - start = 0; - goto again; + + return (false); +} + +/* + * Steals load from a timeshare queue. Honors the rotating queue head + * index. + */ +static inline struct thread * +runq_steal_from(struct runq *const rq, int cpu, int start_idx) +{ + struct runq_steal_pred_data data = { + .td = NULL, + .first = NULL, + .cpu = cpu, + .use_first_last = true + }; + int idx; + + idx = runq_findq(rq, start_idx, RQ_NQS - 1, &runq_steal_pred, &data); + if (idx != -1) + goto found; + + MPASS(data.td == NULL); + if (start_idx != 0) { + idx = runq_findq(rq, 0, start_idx - 1, &runq_steal_pred, &data); + if (idx != -1) + goto found; } - if (first && THREAD_CAN_MIGRATE(first) && - THREAD_CAN_SCHED(first, cpu)) - return (first); + MPASS(idx == -1 && data.td == NULL); + if (data.first != NULL && THREAD_CAN_MIGRATE(data.first) && + THREAD_CAN_SCHED(data.first, cpu)) + return (data.first); return (NULL); +found: + MPASS(data.td != NULL); + return (data.td); } /* @@ -1236,26 +1253,21 @@ again: static struct thread * runq_steal(struct runq *rq, int cpu) { - struct rq_queue *rqq; - struct rq_status *rqs; - struct thread *td; - int word; - int bit; - - rqs = &rq->rq_status; - for (word = 0; word < RQSW_NB; word++) { - if (rqs->rq_sw[word] == 0) - continue; - for (bit = 0; bit < RQSW_BPW; bit++) { - if ((rqs->rq_sw[word] & (1ul << bit)) == 0) - continue; - rqq = &rq->rq_queues[RQSW_TO_QUEUE_IDX(word, bit)]; - TAILQ_FOREACH(td, rqq, td_runq) - if (THREAD_CAN_MIGRATE(td) && - THREAD_CAN_SCHED(td, cpu)) - return (td); - } + struct runq_steal_pred_data data = { + .td = NULL, + .first = NULL, + .cpu = cpu, + .use_first_last = false + }; + int idx; + + idx = runq_findq(rq, 0, RQ_NQS - 1, &runq_steal_pred, &data); + if (idx != -1) { + MPASS(data.td != NULL); + return (data.td); } + + MPASS(data.td == NULL); return (NULL); }