From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-ej1-f51.google.com (mail-ej1-f51.google.com [209.85.218.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4411735CB68 for ; Mon, 23 Feb 2026 10:57:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=pass smtp.client-ip=209.85.218.51 ARC-Seal:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771844225; cv=pass; b=AQlw8ukV6Z71wuL6bjYWv2PZEy8tkS4TumKTjgvW6RJTTlqCyoRDXz5DcAC37ClGnyc71JEDVAVN8u1KKneSBIFbug5B/R3I7LoTEPHR9aXC0x27ll8Otcg0oXiytUAxtR2sEmINTRkkA6dhd5I7vq8Ogb1kPZzXFeBSXajJr8s= ARC-Message-Signature:i=2; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1771844225; c=relaxed/simple; bh=ypl1Upe7++IddcT19GiLU+gMB9RANeQ1lFnu5nLTrw8=; h=MIME-Version:References:In-Reply-To:From:Date:Message-ID:Subject: To:Cc:Content-Type; b=PecMLGPN6Cc96e75jjDdvtomhPpp+K6RorxoDWhSnHEahbwSbZoy7KFc+r8+pGSIWjexvZXj9NFuDzDtt3tj/18ANqW6vMA4YLY1DG7F22DJPQxLFogrYjCDnanHI0LLeWAmoKlDCizimHPWLdzYChtbQI2l9TzKjiRDi6olD30= ARC-Authentication-Results:i=2; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linaro.org; spf=pass smtp.mailfrom=linaro.org; dkim=pass (2048-bit key) header.d=linaro.org header.i=@linaro.org header.b=ysk5FYyU; arc=pass smtp.client-ip=209.85.218.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linaro.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=linaro.org header.i=@linaro.org header.b="ysk5FYyU" Received: by mail-ej1-f51.google.com with SMTP id a640c23a62f3a-b8f992167dcso513884266b.1 for ; Mon, 23 Feb 2026 02:57:03 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1771844222; cv=none; d=google.com; s=arc-20240605; b=ZxprnHQkudPEUmT2cT+rlE99jTrCTn9n8Vw4XUVKQ6kPwUjSGvGwLo5Hui0GclYGzA H5jpSeTNJe90MiR/i6nFILX3xQToaBKjQjj0Dg/1rv6wbj+aSL2324DIe8TBD3Dln8qv W9BMhCs9GLpnxavbQrpE/PivSchPDVJ/wPzTjO3hgnIzClx9oybm9ECiCqR7XrWfnfml h1j11sDlQin/KXVu8c2BfW0MeMSQ88zp4ir1dKDo8ht/z2iPxGprEiL6sieR163XXo4e ZkKP3P7xpH6W60KO5uZrytMMh8yUBFsIi6RgBbokZDRWn6u+PcvYnl+21SfTO0SL6E/u bX2w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=nFwNXdqwmOz1TqGDICK93bUJHx0ep9AYeBomcEn3yoo=; fh=M9IoI+JefN9gNJy9Yow5nmVM2h1qSIgfJa4BRRXlPZ0=; b=NkjPeJah3JhlXua1ME869kqaR6g4IIq/AUMXmiaUA4RBNB6PW2QZJsGHIOhAWDaek4 CMjKyDRMZosZCx9xMiQLxw9qa3crxJiAVNnCVol9hw8q+5AHeZs1fuyliC/mu/T9N0GO CXSEh+nS9T3NYTw8nMwjaKhN9iElKLD+/HeFQ94PmtZ1E5+ntRucBXhn8cyoWSv6rFdo YNNHIXkcx7iXvW0B3Nst4x9F3gkiUN9Fho88G76UglOPAZEDpzgSsk4uh8IwvtzgwaKY fIO+S4BjLjN89sQrJQlpAM5up7Uxig1Z2PJuydSsFa27qUj5Gf+2F26NEoerR4rg0qbN fYCg==; darn=vger.kernel.org ARC-Authentication-Results: i=1; mx.google.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1771844222; x=1772449022; darn=vger.kernel.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=nFwNXdqwmOz1TqGDICK93bUJHx0ep9AYeBomcEn3yoo=; b=ysk5FYyUeN71wME6cpLdUClgbrUTIcYbvSU6zsJx1EaFrufM7FmNBr+LvG00qZvRwd mD231DMJZm871Hc0IX+ozt98d2W7kegLNPyPiX4K0Co/SDY6jR6F+HQb5WzVpkQdf1JN SkKVg1AbrgVIkUbG1aTwGwwhEmwksysIgmW4e7ZvK3WhVhceb+qm/PKB54mKAETKMhoP U6wHRqREwxipKQBvps0X86xvN84Z6hEDXU3x02pMVqf16BQBfq2/TAgyBCPj9RrCiPt6 NDq6ezz44dEZP345UwrZUL2ot6u5eSB0ejfSvXphjfT5tGmNHFuWLum9noTjBxxtIK5u XK/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1771844222; x=1772449022; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=nFwNXdqwmOz1TqGDICK93bUJHx0ep9AYeBomcEn3yoo=; b=RMpLqbw2xtMM307TFLb/RUG/FPrh2W2BE1PIspxo3sDMH8ku+77J+RAW+VcoEyewYV ZTNYCYZPZ1yCG011TqBu7btWl2Of2AnnoUvEjQDFGDkh3NedBasxH6L6r273ZdkPvA4B hd7XX+xksu1puL0KXVoCYrIkxAQ7pahB8xz8Rejgqchr8xQFOoaDdHTLxjODYq1atDnZ xjc0lJ9RxS7GpWMJI7jdORFe3+u5OC2+wTBnAfb3Rz8oEL001+PattrDIDvCMIbVP54e yKuuz+nhxNkyiZa1mmFj0Jjd8qdGTHxOMDfPquLpQ7LVkFwBZJRXTHnKTdvZ2oDXKX8b 0IeA== X-Forwarded-Encrypted: i=1; AJvYcCXC1hMkTDM7U7AaVaSxyLvHFTIWPbiXrHkRC+CBXISrfoR09JQ7wTW+d/TYodVgBE+6M8HLqld0gxBL5GE=@vger.kernel.org X-Gm-Message-State: AOJu0YwzjglN7IcRgJsS13bVyi3TLRtW0VI3BEBNfang9Rob9Q0icVUU NIE2RDqcK5JFz5J8I9Qg0a7pgimFOdWl+GStJrI65Ojbo0RpX7h0rXYqh/NQVqGZ5AmhhMxDiI2 Chlf0Xadgj7abvDYtzl+77Ny6YjB2r7IsjKA3AYx8qw== X-Gm-Gg: AZuq6aL76W+F8tJt8qjSNyr899bpizNfhxwwMZD3lcPrm41vBP9SpxX2x4HNE85kSRv ZiR2n5EnsgpxEljyt39mKjx8NxI5PXPvwQ0lQekUek0C+dLIaHnopeUXR/9amNFrrjFGRn2dVdF vRaBrrr9qMwnr4mBcSR7oDeXKMDXNPx/L9Wqy8Em2EDvyKTA0jbdqfYnvRIPpvCM/HeR4xeZfM3 Vx9/HuDXoH06knggHvduo2eeRbkPxlJHezTt5JwzDzJ/78RLHH3pOM231nRpIQoLhMThqlnPGIZ i21R8ZiCLqRY2yULeYDpKKn5EKC23OFLE/0d X-Received: by 2002:a17:907:7211:b0:b88:4fc9:a196 with SMTP id a640c23a62f3a-b9081b23d0cmr503881066b.34.1771844221444; Mon, 23 Feb 2026 02:57:01 -0800 (PST) Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 References: <20260219075840.162631716@infradead.org> <20260219080624.438854780@infradead.org> In-Reply-To: <20260219080624.438854780@infradead.org> From: Vincent Guittot Date: Mon, 23 Feb 2026 11:56:48 +0100 X-Gm-Features: AaiRm53y0JMGPLMb4x8TqH3aRQivRJOJoMy75EUeXQU6WxgM27spzcaPwHjRr8g Message-ID: Subject: Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking To: Peter Zijlstra Cc: mingo@kernel.org, juri.lelli@redhat.com, dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de, vschneid@redhat.com, linux-kernel@vger.kernel.org, wangtao554@huawei.com, quzicheng@huawei.com, kprateek.nayak@amd.com, dsmythies@telus.net, shubhang@os.amperecomputing.com Content-Type: text/plain; charset="UTF-8" On Thu, 19 Feb 2026 at 09:10, Peter Zijlstra wrote: > > It turns out that zero_vruntime tracking is broken when there is but a single > task running. Current update paths are through __{en,de}queue_entity(), and > when there is but a single task, pick_next_task() will always return that one > task, and put_prev_set_next_task() will end up in neither function. > > This can cause entity_key() to grow indefinitely large and cause overflows, > leading to much pain and suffering. > > Furtermore, doing update_zero_vruntime() from __{de,en}queue_entity(), which > are called from {set_next,put_prev}_entity() has problems because: > > - set_next_entity() calls __dequeue_entity() before it does cfs_rq->curr = se. > This means the avg_vruntime() will see the removal but not current, missing > the entity for accounting. > > - put_prev_entity() calls __enqueue_entity() before it does cfs_rq->curr = > NULL. This means the avg_vruntime() will see the addition *and* current, > leading to double accounting. > > Both cases are incorrect/inconsistent. > > Noting that avg_vruntime is already called on each {en,de}queue, remove the > explicit avg_vruntime() calls (which removes an extra 64bit division for each > {en,de}queue) and have avg_vruntime() update zero_vruntime itself. > > Additionally, have the tick call avg_vruntime() -- discarding the result, but > for the side-effect of updating zero_vruntime. > > While there, optimize avg_vruntime() by noting that the average of one value is > rather trivial to compute. > > Test case: > # taskset -c -p 1 $$ > # taskset -c 2 bash -c 'while :; do :; done&' > # cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>" > > PRE: > .zero_vruntime : 31316.407903 > >R bash 487 50787.345112 E 50789.145972 2.800000 50780.298364 16 120 0.000000 0.000000 0.000000 / > .zero_vruntime : 382548.253179 > >R bash 487 427275.204288 E 427276.003584 2.800000 427268.157540 23 120 0.000000 0.000000 0.000000 / > > POST: > .zero_vruntime : 17259.709467 > >R bash 526 17259.709467 E 17262.509467 2.800000 16915.031624 9 120 0.000000 0.000000 0.000000 / > .zero_vruntime : 18702.723356 > >R bash 526 18702.723356 E 18705.523356 2.800000 18358.045513 9 120 0.000000 0.000000 0.000000 / > > Fixes: 79f3f9bedd14 ("sched/eevdf: Fix min_vruntime vs avg_vruntime") > Reported-by: K Prateek Nayak > Signed-off-by: Peter Zijlstra (Intel) > Tested-by: K Prateek Nayak > Tested-by: Shubhang Kaushik Reviewed-by: Vincent Guittot > --- > kernel/sched/fair.c | 84 +++++++++++++++++++++++++++++++++++----------------- > 1 file changed, 57 insertions(+), 27 deletions(-) > > --- a/kernel/sched/fair.c > +++ b/kernel/sched/fair.c > @@ -589,6 +589,21 @@ static inline bool entity_before(const s > return vruntime_cmp(a->deadline, "<", b->deadline); > } > > +/* > + * Per avg_vruntime() below, cfs_rq::zero_vruntime is only slightly stale > + * and this value should be no more than two lag bounds. Which puts it in the > + * general order of: > + * > + * (slice + TICK_NSEC) << NICE_0_LOAD_SHIFT > + * > + * which is around 44 bits in size (on 64bit); that is 20 for > + * NICE_0_LOAD_SHIFT, another 20 for NSEC_PER_MSEC and then a handful for > + * however many msec the actual slice+tick ends up begin. > + * > + * (disregarding the actual divide-by-weight part makes for the worst case > + * weight of 2, which nicely cancels vs the fuzz in zero_vruntime not actually > + * being the zero-lag point). > + */ > static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se) > { > return vruntime_op(se->vruntime, "-", cfs_rq->zero_vruntime); > @@ -676,39 +691,61 @@ sum_w_vruntime_sub(struct cfs_rq *cfs_rq > } > > static inline > -void sum_w_vruntime_update(struct cfs_rq *cfs_rq, s64 delta) > +void update_zero_vruntime(struct cfs_rq *cfs_rq, s64 delta) > { > /* > - * v' = v + d ==> sum_w_vruntime' = sum_runtime - d*sum_weight > + * v' = v + d ==> sum_w_vruntime' = sum_w_vruntime - d*sum_weight > */ > cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta; > + cfs_rq->zero_vruntime += delta; > } > > /* > - * Specifically: avg_runtime() + 0 must result in entity_eligible() := true > + * Specifically: avg_vruntime() + 0 must result in entity_eligible() := true > * For this to be so, the result of this function must have a left bias. > + * > + * Called in: > + * - place_entity() -- before enqueue > + * - update_entity_lag() -- before dequeue > + * - entity_tick() > + * > + * This means it is one entry 'behind' but that puts it close enough to where > + * the bound on entity_key() is at most two lag bounds. > */ > u64 avg_vruntime(struct cfs_rq *cfs_rq) > { > struct sched_entity *curr = cfs_rq->curr; > - s64 avg = cfs_rq->sum_w_vruntime; > - long load = cfs_rq->sum_weight; > + long weight = cfs_rq->sum_weight; > + s64 delta = 0; > > - if (curr && curr->on_rq) { > - unsigned long weight = scale_load_down(curr->load.weight); > + if (curr && !curr->on_rq) > + curr = NULL; > > - avg += entity_key(cfs_rq, curr) * weight; > - load += weight; > - } > + if (weight) { > + s64 runtime = cfs_rq->sum_w_vruntime; > + > + if (curr) { > + unsigned long w = scale_load_down(curr->load.weight); > + > + runtime += entity_key(cfs_rq, curr) * w; > + weight += w; > + } > > - if (load) { > /* sign flips effective floor / ceiling */ > - if (avg < 0) > - avg -= (load - 1); > - avg = div_s64(avg, load); > + if (runtime < 0) > + runtime -= (weight - 1); > + > + delta = div_s64(runtime, weight); > + } else if (curr) { > + /* > + * When there is but one element, it is the average. > + */ > + delta = curr->vruntime - cfs_rq->zero_vruntime; > } > > - return cfs_rq->zero_vruntime + avg; > + update_zero_vruntime(cfs_rq, delta); > + > + return cfs_rq->zero_vruntime; > } > > /* > @@ -777,16 +814,6 @@ int entity_eligible(struct cfs_rq *cfs_r > return vruntime_eligible(cfs_rq, se->vruntime); > } > > -static void update_zero_vruntime(struct cfs_rq *cfs_rq) > -{ > - u64 vruntime = avg_vruntime(cfs_rq); > - s64 delta = vruntime_op(vruntime, "-", cfs_rq->zero_vruntime); > - > - sum_w_vruntime_update(cfs_rq, delta); > - > - cfs_rq->zero_vruntime = vruntime; > -} > - > static inline u64 cfs_rq_min_slice(struct cfs_rq *cfs_rq) > { > struct sched_entity *root = __pick_root_entity(cfs_rq); > @@ -856,7 +883,6 @@ RB_DECLARE_CALLBACKS(static, min_vruntim > static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) > { > sum_w_vruntime_add(cfs_rq, se); > - update_zero_vruntime(cfs_rq); > se->min_vruntime = se->vruntime; > se->min_slice = se->slice; > rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline, > @@ -868,7 +894,6 @@ static void __dequeue_entity(struct cfs_ > rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline, > &min_vruntime_cb); > sum_w_vruntime_sub(cfs_rq, se); > - update_zero_vruntime(cfs_rq); > } > > struct sched_entity *__pick_root_entity(struct cfs_rq *cfs_rq) > @@ -5524,6 +5549,11 @@ entity_tick(struct cfs_rq *cfs_rq, struc > update_load_avg(cfs_rq, curr, UPDATE_TG); > update_cfs_group(curr); > > + /* > + * Pulls along cfs_rq::zero_vruntime. > + */ > + avg_vruntime(cfs_rq); > + > #ifdef CONFIG_SCHED_HRTICK > /* > * queued ticks are scheduled to match the slice, so don't bother > >