From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AA997191 for ; Wed, 22 Apr 2026 00:04:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1776816261; cv=none; b=MdFLvW+aDS0O/F9DRdr4xbdXbY933HzxJl/nS/gc8yv4JwqG9wdfbF6TZmv7dubX93yPKpVjwrAfJ7vImiOCxloreM9CHy3oXGXIfv4J8pglVeoDmT06hh+B5rrSQnzNqeAGJ2KVuCVBaA/y042TAqo6yelC828eHl1VRnZMhBQ= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1776816261; c=relaxed/simple; bh=9ekNMYG1ueA6DRKcP2+h190TCk2iD3f7GbOIq6R0Rx0=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=MTEQfFajhDchVFNHzCrgssWByJe7kgy8y4Ma6HO8RNZZr+3d3CPCIgWC6yGVGE/WvceNNc6gnXUEKSNWXePXfsqdBuhVciIfM1ot6CYPhxxiWMFiap3HqvhM7PzVaBe3IqaAPIbsn9+Sk0d/9scw7VUp2H5yVPonnklSooewu/c= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=ZBKpq4Ri; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="ZBKpq4Ri" Received: by smtp.kernel.org (Postfix) with ESMTPSA id ED0DBC2BCB0; Wed, 22 Apr 2026 00:04:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1776816261; bh=9ekNMYG1ueA6DRKcP2+h190TCk2iD3f7GbOIq6R0Rx0=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=ZBKpq4Ri8DnC2nEpT43E5G1QGKx9IwTmWUpLqLt1Zk0fbc9m0tAKHCVFd8Jlrj5Yl eR3lU25f8ufT9WVqbi/Xdap79sa7Crhoo0ghFk2EZ2JO22L6ml96mmYWu2WCHYBr1Z JM2Ya3lXweqpAlwVK2rs6xUd4B5umt3HO39yoSYTc0lJpKbVaBaKoXrg/3lYikt9Ih iW2VFh3M9Xs+bm2i5M4L6H64sSWCHVprbEO1ZZgJJTB0RT22npXjbezKHMlN5sMPLC uYcBh+udE9pu3Pbsi4uHRBN87wKn9u+I/WrkoogNx/YhpQ5mPTJXqb44JkHaqFJFjw unMzfm49Pel/g== Date: Tue, 21 Apr 2026 17:04:19 -0700 From: Dennis Zhou To: Joonwon Kang Cc: tj@kernel.org, cl@gentwo.org, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, dodam@google.com Subject: Re: [PATCH v3 3/3] percpu: Fix hint invariant breakage Message-ID: References: <20260410174417.1450834-1-joonwonkang@google.com> <20260410174417.1450834-3-joonwonkang@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260410174417.1450834-3-joonwonkang@google.com> On Fri, Apr 10, 2026 at 05:44:17PM +0000, Joonwon Kang wrote: > 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: > > - Refactor the percpu block update code to make it more visible on > what to consider, e.g. when the new contig overlaps with the old > contig_hint or scan_hint. > Could you please split this up between the fixing the scan_hint issues and then refactoring. That way this commit isn't doing too much. > - 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 > --- > v2 -> 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. > > v1 -> v2: Consider cases where the new contig overlaps with the existing > contig_hint or scan_hint. > > mm/percpu.c | 130 ++++++++++++++++++++++++++++++++++++---------------- > 1 file changed, 90 insertions(+), 40 deletions(-) > > diff --git a/mm/percpu.c b/mm/percpu.c > index f16533ed4a49..d5b0b4863ffe 100644 > --- a/mm/percpu.c > +++ b/mm/percpu.c > @@ -629,7 +629,27 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y) > */ > static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) > { > - int contig = end - start; > + int contig; > + int scan_hint_cand_1 = 0; > + int scan_hint_cand_1_start = 0; > + int scan_hint_cand_2 = 0; > + int scan_hint_cand_2_start = 0; I'm not really a fan of this cand_1 and cand_2. Re-reading all this code. I think I really should have introduced something like: struct pcpu_region { int start; int size; } It's really easy to mix contig_hint and contig_hint_start. If you don't mind, it would be ideal if we could introduce it but it might be a non-trivial amount of refactor. I'd say the shortest path forward would be to do just to fix the scan_hint issues. > + bool overlap_with_contig_hint = pcpu_region_overlap(start, end, > + block->contig_hint_start, > + block->contig_hint_start + block->contig_hint); > + bool overlap_with_scan_hint = pcpu_region_overlap(start, end, > + block->scan_hint_start, > + block->scan_hint_start + block->scan_hint); > + This one isn't used again so we should probably just inline it. > + if (block->contig_hint && overlap_with_contig_hint) { > + start = min(start, block->contig_hint_start); > + end = max(end, block->contig_hint_start + block->contig_hint); > + } > + if (block->scan_hint && overlap_with_scan_hint) { > + start = min(start, block->scan_hint_start); > + end = max(end, block->scan_hint_start + block->scan_hint); > + } > + contig = end - start; > > block->first_free = min(block->first_free, start); > if (start == 0) > @@ -646,56 +666,86 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) > } > > if (contig > block->contig_hint) { > - /* promote the old contig_hint to be the new scan_hint */ > - if (start > block->contig_hint_start) { > - if (block->contig_hint > block->scan_hint) { > - block->scan_hint_start = > - block->contig_hint_start; > - block->scan_hint = block->contig_hint; > - } else if (start < block->scan_hint_start) { > - /* > - * The old contig_hint == scan_hint. But, the > - * new contig is larger so hold the invariant > - * scan_hint_start < contig_hint_start. > - */ > - block->scan_hint = 0; > - } > - } else { > - block->scan_hint = 0; > + if (!overlap_with_contig_hint) { > + scan_hint_cand_1 = block->contig_hint; > + scan_hint_cand_1_start = block->contig_hint_start; > } > - block->contig_hint_start = start; > + > block->contig_hint = contig; > + block->contig_hint_start = start; > } else if (contig == block->contig_hint) { > if (block->contig_hint_start && > (!start || > __ffs(start) > __ffs(block->contig_hint_start))) { > - /* start has a better alignment so use it */ > + scan_hint_cand_1 = block->contig_hint; > + scan_hint_cand_1_start = block->contig_hint_start; > + > + /* Start has a better alignment so use it. */ > block->contig_hint_start = start; > - if (start < block->scan_hint_start && > - block->contig_hint > block->scan_hint) > - block->scan_hint = 0; > - } else if (start > block->scan_hint_start || > - block->contig_hint > block->scan_hint) { > - /* > - * Knowing contig == contig_hint, update the scan_hint > - * if it is farther than or larger than the current > - * scan_hint. > - */ > - block->scan_hint_start = start; > - block->scan_hint = contig; > + } else { > + if (!overlap_with_contig_hint) { > + scan_hint_cand_1 = contig; > + scan_hint_cand_1_start = start; > + } > } > } else { > /* > - * The region is smaller than the contig_hint. So only update > - * the scan_hint if it is larger than or equal and farther than > - * the current scan_hint. > + * Consider only when the new contig is larger than or equal to > + * the old scan hint. > */ > - if ((start < block->contig_hint_start && > - (contig > block->scan_hint || > - (contig == block->scan_hint && > - start > block->scan_hint_start)))) { > - block->scan_hint_start = start; > - block->scan_hint = contig; > + if (contig >= block->scan_hint) { > + scan_hint_cand_1 = contig; > + scan_hint_cand_1_start = start; > + } > + } > + > + if (block->scan_hint && > + !pcpu_region_overlap(start, end, block->scan_hint_start, > + block->scan_hint_start + block->scan_hint)) { > + scan_hint_cand_2 = block->scan_hint; > + scan_hint_cand_2_start = block->scan_hint_start; > + } > + > + /* Make scan_hint_cand_1 be the best candidate for the new scan hint. */ > + if ((scan_hint_cand_2 > scan_hint_cand_1) || > + (scan_hint_cand_2 == scan_hint_cand_1 && > + scan_hint_cand_2_start > scan_hint_cand_1_start)) { > + int tmp_hint = scan_hint_cand_1; > + int tmp_hint_start = scan_hint_cand_1_start; > + > + scan_hint_cand_1 = scan_hint_cand_2; > + scan_hint_cand_1_start = scan_hint_cand_2_start; > + scan_hint_cand_2 = tmp_hint; > + scan_hint_cand_2_start = tmp_hint_start; > + } > + > + /* > + * At this point, it is guaranteed that none of the scan hint > + * candidates overlaps with the new contig hint while they may overlap > + * with the old scan hint, and that the first candidate is larger in > + * size or, it equal, farther than the second one. > + */ > + > + if (block->contig_hint > scan_hint_cand_1) { > + if (scan_hint_cand_1_start < block->contig_hint_start) { > + block->scan_hint = scan_hint_cand_1; > + block->scan_hint_start = scan_hint_cand_1_start; > + } else if (scan_hint_cand_2_start < block->contig_hint_start) { > + block->scan_hint = scan_hint_cand_2; > + block->scan_hint_start = scan_hint_cand_2_start; > + } else { > + block->scan_hint = 0; > + } > + } else if (block->contig_hint == scan_hint_cand_1) { > + if (scan_hint_cand_1_start > block->contig_hint_start) { > + block->scan_hint = scan_hint_cand_1; > + block->scan_hint_start = scan_hint_cand_1_start; > + } else if (scan_hint_cand_2 < block->contig_hint && > + scan_hint_cand_2_start < scan_hint_cand_1_start) { > + block->scan_hint = scan_hint_cand_2; > + block->scan_hint_start = scan_hint_cand_2_start; > + } else { > + block->scan_hint = 0; > } This seems easier to invert and do something like this: Probably something like: bool overlap_contig_hint = pcpu_region_overlap(new_region, scan_hint); bool overlap_scan_hint = pcpu_region_overlap(new_region, scan_hint); if (overlap_scan_hint) { scan_hint = 0; } if (overlap_contig_hint) { contig_hint = new_region; return; } // Now the new_region is distinct from the contig_hint and then can do // the standard logic here. if (new_region > contig_hint) { } else if (new_region == contig_hint) {} else {} What do you think? I think makes cand_1 and cand_2 not necessary. > } > } > -- > 2.53.0.1213.gd9a14994de-goog > Thanks, Dennis