From nobody Wed Jun 18 02:13:21 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 4bMS2T4plkz5q6gv; Wed, 18 Jun 2025 02:13:21 +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 4bMS2T3sFlz41L4; Wed, 18 Jun 2025 02:13:21 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212801; 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=sSTmiR34rUXyI2EpJ8as+RGW3qYST71OME/t09MO2s4=; b=Anj+j9M2P/8aknRujeSo71VZNxd+Z9BbN9gCEv+Le/hhG1DchBONDIxUpy1/0LN+NDrPwL iWWeaFPP5YZ+GRslsE+jAfHMNXPjZNxDQFQAhbkH8hHM7yeK8hBRr0JSUIG1vxfUVc+oVy R+8jULBvvauPquidx7CPzKFewGudG+EOpjUZMFmcmpMyCBT0j934FWsXTH6Q6Q9ZszGMLM zk0w3unrqTSdV0RZoHgKthU289JhlHXZkUQaFMmmemW2f6bwSmBE+Hkm/3Q4HtTDO1mMyo lYyuHoft/tUqfsyRjQQb1fTUs/7WIxnsOmrm1xAI5qkoIsPOCR56cAzV7zv99g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1750212801; 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=sSTmiR34rUXyI2EpJ8as+RGW3qYST71OME/t09MO2s4=; b=wbtS6OH0dM2aUZC+lim9KXzkYl7Nq8Gw8YVxFLTJo520PkrXyBVllrozcjKTD2m9rQWRnD YSH8vMONIValZ0M0CXMW8injHxFxa0Yr4AGYU3xaxGybAujqoGWUqn96Sju8QuKgRxiDog rUwmIZXu+CMzKFhUy2Y1Wq9QaQS5VVZ1XbtfKJ3M74TwxQmcTNDKuW5LbmB+2FJ/LHPRAE BjRgTS8x25UEMgAlpMjIBTB1kuFiqbV6NOofSuov5iESRL3nG08+9+ms6DtfVo0QMYRiOy SBRwYTCngaqyV4vkxb6Jh0WaBUg3rwbdWQa1wZNzaIN0swh1GgThA3WN3y+NCQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1750212801; a=rsa-sha256; cv=none; b=cktWb3ZPrZKMve6PqVsUGFo0wW0johZ6i5y7+EVtk2RT+3mb3LhxiFJphRwnPEIGUx9byM UJl9PAcpl1wL0tEneHRnR3DCSX6UHnfuRh/eLxOs5BEVmCVWmLeSqLEyqiVTFPsACKfTdA QzDiBcSW+boY/i6wSFK/n0xCuf9//4j/9ANjFQB0T01kFswv5Rul3iJXr7cwgEcHfJ1Nnr BCIDOE50SWM9rjQqVljqIL89f0n0IDz7wf7eSrsTNjdV4/ETgJBKkgsgtcNzkV8gk0Wznl x+UojAsH7SvKjQw9UUMJeahZTWfrUBLyp16LWU79c64ioGH9AT+icik3RXFCQg== 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 4bMS2T2hnxz18V2; Wed, 18 Jun 2025 02:13: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 55I2DL9D024337; Wed, 18 Jun 2025 02:13:21 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 55I2DLlc024334; Wed, 18 Jun 2025 02:13:21 GMT (envelope-from git) Date: Wed, 18 Jun 2025 02:13:21 GMT Message-Id: <202506180213.55I2DLlc024334@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: f4be333bc567 - main - sched_ule: Re-implement stealing on top of runq common-code 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: f4be333bc56759d33dca49ab4d19eaf22134e844 Auto-Submitted: auto-generated The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=f4be333bc56759d33dca49ab4d19eaf22134e844 commit f4be333bc56759d33dca49ab4d19eaf22134e844 Author: Olivier Certner AuthorDate: 2024-04-29 00:55:40 +0000 Commit: Olivier Certner CommitDate: 2025-06-18 02:08:01 +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 --- 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 c23d00fd6049..5c7665eb7add 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); }