From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pl1-f202.google.com (mail-pl1-f202.google.com [209.85.214.202]) (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 18EA03E3D9C for ; Wed, 13 May 2026 08:51:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.202 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778662289; cv=none; b=llcmth8WxYuhuS9vReVvs9UoMVjyRI+lckNzNYH1rNPCosDFAlJeRM+c2i6TWfWrtuyljJukzMdiflvboHLDfdBOj2jDKuPqURHAb7XiDSUGOOwSoAiKoXnxHJOK6ODBpfecQrCAGoSCdElNkaPgy0Vj5N2bgqFUTyQDIM6ZCNs= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1778662289; c=relaxed/simple; bh=m4RokpakoX98GwpBrD74d1csHBdeyxq9atF2SHwvCqE=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=BFdcJPyd1JPsdUIKYiPrWKWpmcW2rXaC+ajcvmvrI8LvWIUod+adgmlNdsz+GZtRE1vFl6BSVO66e5V0zSu5ukCnvgb9CkbUlrR3aH1o2Ysc3IQ0x5l0bqYiAp8U+RdTf/oaJXQ/orwnNxd3+93HofjL8FfDnM91CTax0T8ecas= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--joonwonkang.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=k8N4m8hz; arc=none smtp.client-ip=209.85.214.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--joonwonkang.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="k8N4m8hz" Received: by mail-pl1-f202.google.com with SMTP id d9443c01a7336-2baf7748d0aso58014815ad.1 for ; Wed, 13 May 2026 01:51:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20251104; t=1778662286; x=1779267086; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=l59ozyFO40IXAoWeYrtUkk6Jpy5oWCUh7Ai4pCgGDq8=; b=k8N4m8hzBdFpvHhSRIHq0QWvZ0KTTqByGtGw3eYftLOtsNZrp18ddW3Ex6hXaSRsHP Ruw9wjOPzqZ2xCSIY337FDuPbFJyf7la0073S+Ce07kxkiLv44PFqDKK/Wgfu06atUa0 cSJVfPsIUyGvP8/LP1xViREOfZ4bmqM3T4bd9eDP6UPK2gVWsatyHHX5tEpOuEFommiL dGUgnyp30KUF3DmiyOsthw444r+KPVkqNUF2ypH2SQ1sCYyK+sDTIaz349AfGHbLdDui AUjyPoFFV8QYvZs9LUZidhQRPASKeO7KMFPP+l7b6NtF9594LxFtumBRCD/NoALyCZcJ k/Iw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1778662286; x=1779267086; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=l59ozyFO40IXAoWeYrtUkk6Jpy5oWCUh7Ai4pCgGDq8=; b=PtfH+w1RhrHueIgTQdliH2nQ05qJVOELA7CpAKSErnyqkdiTaQK5aLlN3nF1Zc1QwE GPDVnuvdf9rOjbw+d4ag2sEJg6NFUetntPWfYjLwdwgCqdhq+eHnmpilLlE+kaTPS8LZ mbrTNkc7SrZR2Jt+lb3TgFB426BSs9vvxET2UtFOsu91F8T9SwE3q9P8EyhsZK7c0sw+ Jz1iH6DBfGj7TonWxD+I1qtVAEwTr9w9e6jNtNLabZCP66OxRXhnFR6+vWiu7x9OE5iN fdRyhik0w25+vn/LVhE1ho9bi6guJvjtgRaFLkSd6i2thToiA9SiuxLYyGwppFl07mIp k+2Q== X-Forwarded-Encrypted: i=1; AFNElJ/MsKz8dQGw0CTVqrmLDKwVG/pGP7BjUSkCDzSm1zZYh03ofDkbqqvI0vRxdZYqDColGpG26BALCOhpBaQ=@vger.kernel.org X-Gm-Message-State: AOJu0YwbUHAmUO44+sLcSidLAR+MnISyYNFxNNq/UY8oyw9CW/GeC7WD bw7rif1ztrWHZ220dkxHN+Ejqyo2Jt6Mc00mVvgsMb2xkUH8WPZbuIoc0PAQiUyTLxteVafUH46 +MC27YbFv0X+5ieQy3bEF/TQfYg== X-Received: from plgq11.prod.google.com ([2002:a17:902:eb8b:b0:2b0:6cdd:87e2]) (user=joonwonkang job=prod-delivery.src-stubby-dispatcher) by 2002:a17:902:8d81:b0:2ba:6ca2:be0 with SMTP id d9443c01a7336-2bd270fbeefmr17510195ad.4.1778662286157; Wed, 13 May 2026 01:51:26 -0700 (PDT) Date: Wed, 13 May 2026 08:51:16 +0000 In-Reply-To: <20260513085117.1024175-1-joonwonkang@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20260513085117.1024175-1-joonwonkang@google.com> X-Mailer: git-send-email 2.54.0.563.g4f69b47b94-goog Message-ID: <20260513085117.1024175-4-joonwonkang@google.com> Subject: [PATCH v6 4/4] percpu: Fix hint invariant breakage From: Joonwon Kang To: dennis@kernel.org, tj@kernel.org, cl@gentwo.org Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, dodam@google.com, joonwonkang@google.com Content-Type: text/plain; charset="UTF-8" The invariant "scan_hint_start > contig_hint_start if and only if scan_hint == contig_hint" should be kept for hint management. However, it could be broken in some cases: - if (new contig == contig_hint == scan_hint) && (contig_hint_start < scan_hint_start < new contig start) && the new contig is to become a new contig_hint due to its better alignment, then scan_hint should be invalidated instead of keeping the old value. - if (new contig == contig_hint > scan_hint) && (new contig start < contig_hint_start) && the new contig is not to become a new contig_hint, then scan_hint should be not updated to the new contig. This commit mainly fixes this invariant breakage and includes more: - Handle the cases where the new contig overlaps with the contig_hint or with scan_hint. - Merge the new contig with other hints when it overlaps with them and treat it as a whole free region instead of a separate small region. - Fix the invariant breakage and also optimizes scan_hint further. Some of the optimization cases when no overlap occurs are: - if (new contig > contig_hint > scan_hint) && (scan_hint_start < new contig start < contig_hint_start), then keep scan_hint instead of invalidating it. - if (new contig > contig_hint == scan_hint) && (contig_hint_start < new contig start < scan_hint_start), then update scan_hint to the old contig_hint instead of invalidating it. - if (new contig == contig_hint > scan_hint) && (new contig start < contig_hint_start) && the new contig is to become a new contig_hint due to its better alignment, then update scan_hint to the old contig_hint instead of invalidating or keeping it. Signed-off-by: Joonwon Kang --- v6: Diverge more when the new contig size is the same as the old contig_hint size but greater than the old scan_hint, does not become a new contig_hint and is before the old contig_hint. v5: No change. v4: Refactor code by removing the scan_hint candidates and handle the overlapping cases where the new contig meets with the hints on the border. v3: Merge the new contig with other hints when it overlaps with them and treat it as a whole free region instead of a separate small region. v2: Consider the cases where the new contig overlaps with the existing contig_hint or scan_hint. Introduce the scan_hint candidates to calculate new scan_hint. v1: Initial version. mm/percpu.c | 118 +++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 93 insertions(+), 25 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index 89b7f33500cf..1a0e1e84d92a 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -616,6 +616,20 @@ static inline bool pcpu_region_overlap(struct pcpu_region a, return (a.start < b.start + b.size) && (b.start < a.start + a.size); } +/* + * pcpu_region_concat - determines if two regions meet on the border + * @a: first region + * @b: second region + * + * This is used to determine if the hint region [a.start, a.start + a.size) + * meets with the allocated region [b.start, b.start + b.size) on the border. + */ +static inline bool pcpu_region_concat(struct pcpu_region a, + struct pcpu_region b) +{ + return (a.start == b.start + b.size) || (b.start == a.start + a.size); +} + /** * pcpu_block_update - updates a block given a free area * @block: block of interest @@ -629,6 +643,40 @@ static inline bool pcpu_region_overlap(struct pcpu_region a, static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) { struct pcpu_region free = { .start = start, .size = end - start }; + bool overlap_with_contig_hint = + block->contig_hint.size && + (pcpu_region_overlap(block->contig_hint, free) || + pcpu_region_concat(block->contig_hint, free)); + + if (block->scan_hint.size && + (pcpu_region_overlap(block->scan_hint, free) || + pcpu_region_concat(block->scan_hint, free))) { + start = min(start, block->scan_hint.start); + end = max(end, block->scan_hint.start + block->scan_hint.size); + free = (struct pcpu_region){ + .start = start, + .size = end - start, + }; + + block->scan_hint.size = 0; + } + + if (overlap_with_contig_hint) { + start = min(start, block->contig_hint.start); + end = max(end, + block->contig_hint.start + block->contig_hint.size); + free = (struct pcpu_region){ + .start = start, + .size = end - start, + }; + + if (block->scan_hint.size && + free.size > block->scan_hint.size && + block->scan_hint.start > free.start) + block->scan_hint.size = 0; + + block->contig_hint = free; + } block->first_free = min(block->first_free, free.start); if (free.start == 0) @@ -637,23 +685,24 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) if (free.start + free.size == block->nr_bits) block->right_free = free.size; + if (overlap_with_contig_hint) + return; + + /* + * At this point, it is guaranteed that the new contig does neither + * overlap with contig_hint nor with scan_hint. + */ + if (free.size > block->contig_hint.size) { /* promote the old contig_hint to be the new scan_hint */ if (block->contig_hint.size && free.start > block->contig_hint.start) { - if (block->contig_hint.size > block->scan_hint.size) { + if (block->contig_hint.size > block->scan_hint.size || + free.start < block->scan_hint.start) block->scan_hint = block->contig_hint; - } else if (block->scan_hint.size && - free.start < block->scan_hint.start) { - /* - * The old contig_hint.size == scan_hint.size. - * But, the new contig is larger so hold the - * invariant scan_hint.start < - * contig_hint.start. - */ - block->scan_hint.size = 0; - } - } else { + } else if (!block->contig_hint.size || + (block->scan_hint.size && + free.start < block->scan_hint.start)) { block->scan_hint.size = 0; } block->contig_hint = free; @@ -661,21 +710,40 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) if (block->contig_hint.start && (!free.start || __ffs(free.start) > __ffs(block->contig_hint.start))) { + if (block->contig_hint.size > block->scan_hint.size) { + if (free.start < block->contig_hint.start) + block->scan_hint = block->contig_hint; + } else if (free.start > block->scan_hint.start) { + /* + * old contig_hint.size == old scan_hint.size + * == new contig size. But, the new contig is + * farther than the old scan_hint so hold the + * invariant scan_hint.start > contig_hint.start + * iff scan_hint.size == contig_hint.size. + */ + block->scan_hint.size = 0; + } + /* new start has a better alignment so use it */ block->contig_hint.start = free.start; - if (block->scan_hint.size && - free.start < block->scan_hint.start && - block->contig_hint.size > block->scan_hint.size) - block->scan_hint.size = 0; - } else if ((block->scan_hint.size && - free.start > block->scan_hint.start) || - block->contig_hint.size > block->scan_hint.size) { - /* - * Knowing new contig size == contig_hint.size, update - * the scan_hint if it is farther than or larger than - * the current scan_hint. - */ - block->scan_hint = free; + } else { + if (block->contig_hint.size > block->scan_hint.size) { + if (free.start > block->contig_hint.start) { + block->scan_hint = free; + } else if (block->scan_hint.size && + free.start < block->scan_hint.start) { + /* + * old scan_hint.size < new contig size + * == old contig_hint.size. But, the new + * contig is before the old scan_hint + * so invalidate the scan_hint to + * protect the contig_hint. + */ + block->scan_hint.size = 0; + } + } else if (free.start > block->scan_hint.start) { + block->scan_hint = free; + } } } else { /* -- 2.54.0.563.g4f69b47b94-goog