From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 45A704E379B for ; Thu, 3 Sep 2026 16:17:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=217.140.110.172 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788452262; cv=none; b=kbwYOjJ8hzgj0JDcYYkDIInvMSOC01HIMhb/9JnI7zuBn9dHFddwePRs1453UhHUPTX9knXOEcPOy1qhGeQnNT6DKNXka5Qs9o3K86H7200B9O5RyzEucsKRN5Pbd/TZp7dwPlINlW1SgRu93Lxs8uiqZYl1+9VqEQwdOHgKysA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788452262; c=relaxed/simple; bh=IGCjKrKbxdeYpXYZSvcnw7WtqBMc/XxE/M/sNq1isXU=; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From: In-Reply-To:Content-Type; b=bVg2mk7odNazLev0Xgc2HT3BjCUzKHJMZWPcm439KaY7yv7wYXnj9SKR8Vz8ZIJ2IFl0ftHqQlNCKwJwXZf1BFnOiP4Po2uch8Io6LYlwfG2XGnmVQ4f7ThzeaFI+1vmLSKA4wYKrEet3r/NUa74Wa5C71Dn/8lktAApKP9Puvs= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com; spf=pass smtp.mailfrom=arm.com; dkim=pass (1024-bit key) header.d=arm.com header.i=@arm.com header.b=WQPzl4p+; arc=none smtp.client-ip=217.140.110.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=arm.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=arm.com header.i=@arm.com header.b="WQPzl4p+" Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id BCDBD1596; Thu, 3 Sep 2026 09:17:36 -0700 (PDT) Received: from [10.163.139.221] (unknown [10.163.139.221]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id BE5C93F673; Thu, 3 Sep 2026 09:17:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=arm.com; s=foss; t=1788452260; bh=IGCjKrKbxdeYpXYZSvcnw7WtqBMc/XxE/M/sNq1isXU=; h=Date:Subject:To:Cc:References:From:In-Reply-To:From; b=WQPzl4p+HAJJT3jsTl/2zRjvDVPFttOla1UX2/d2fnrmHSi/X9XHK6EUHX86G52sl aFC0pXXEixydbGJmrY7+FmHm2AJEi6SywD11/HP5SrdlLNCzmEuNeuiY+f242VepQL LXKrXyZOLn3ldtBr3xwOJPf52LEwEBXJ/ZMDjR0s= Message-ID: <925c45d9-91dc-406a-9ff5-8c16f3ee0d9f@arm.com> Date: Thu, 3 Sep 2026 21:47:34 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH] memblock: use binary search to locate candidate regions To: Tarun Sahu , dmatlack@google.com, Pasha Tatashin , Mike Rapoport , Andrew Morton , Pratyush Yadav Cc: linux-kernel@vger.kernel.org, kexec@lists.infradead.org, linux-mm@kvack.org References: <20260903155907.1065681-1-tarunsahu@google.com> Content-Language: en-US From: Dev Jain In-Reply-To: <20260903155907.1065681-1-tarunsahu@google.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit On 03/09/26 9:29 pm, Tarun Sahu wrote: > Use binary search (memblock_bsearch_start) in memblock_add_range() and > memblock_isolate_range() to locate candidate regions instead of linearly > scanning from index 0. > > Under heavy memory fragmentation (such as KHO page preservation registering > hundreds of thousands of disjoint folios), scanning from index 0 on every > insertion and isolation results in O(N^2) complexity, causing boot-time > memory retrieval to take several minutes (~268s for 393k pages). > > Using binary search reduces the worst-case complexity to O(N log N) > (and O(N) for sequential appends), cutting KHO memory retrieval time > from ~268s to ~50ms. > > Signed-off-by: Tarun Sahu > --- I recall noticing this 2 years ago : ) but then abandoned because I couldn't think of a usecase. I have forgotten memblock and no idea on KHO, but are you sure this patch won't have negative consequence for the usual cases? In other words is this something KHO specific, and in the usual cases a linear search is more cache/CPU friendly? Also below I see you have implemented a custom binary search helper. I recall a generic one is there in some .h file somewhere in the codebase, perhaps that may be useful, just FYI, ignore if already tried that. > mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++-- > 1 file changed, 36 insertions(+), 2 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index 9ce86349a29f..88940474b020 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -160,6 +160,11 @@ static __refdata struct memblock_type *memblock_memory = &memblock.memory; > i < memblock_type->cnt; \ > i++, rgn = &memblock_type->regions[i]) > > +#define for_each_memblock_type_from(i, memblock_type, rgn, start) \ > + for (i = (start), rgn = &memblock_type->regions[i]; \ > + i < memblock_type->cnt; \ > + i++, rgn = &memblock_type->regions[i]) > + > #define memblock_dbg(fmt, ...) \ > do { \ > if (memblock_debug) \ > @@ -591,6 +596,33 @@ static void __init_memblock memblock_insert_region(struct memblock_type *type, > type->total_size += size; > } > > +/** > + * memblock_bsearch_start - Find the first region index where rend > base > + * @type: memblock type to search > + * @base: base physical address of the candidate range > + * > + * Returns the first region index that could potentially overlap @base. > + */ > +static int __init_memblock memblock_bsearch_start(struct memblock_type *type, > + phys_addr_t base) > +{ > + int mid, low = 0; > + int high = type->cnt; > + > + if (type->cnt && base >= type->regions[type->cnt - 1].base + > + type->regions[type->cnt - 1].size) > + return type->cnt; > + > + while (low < high) { > + mid = (low + high) / 2; > + if (type->regions[mid].base + type->regions[mid].size <= base) > + low = mid + 1; > + else > + high = mid; > + } > + return low; > +} > + > /** > * memblock_add_range - add new memblock region > * @type: memblock type to add new region into > @@ -651,7 +683,8 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > base = obase; > nr_new = 0; > > - for_each_memblock_type(idx, type, rgn) { > + for_each_memblock_type_from(idx, type, rgn, > + memblock_bsearch_start(type, base)) { > phys_addr_t rbase = rgn->base; > phys_addr_t rend = rbase + rgn->size; > > @@ -827,7 +860,8 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, > if (memblock_double_array(type, base, size) < 0) > return -ENOMEM; > > - for_each_memblock_type(idx, type, rgn) { > + for_each_memblock_type_from(idx, type, rgn, > + memblock_bsearch_start(type, base)) { > phys_addr_t rbase = rgn->base; > phys_addr_t rend = rbase + rgn->size; >