Skip to contentSkip to conversation

memblock: use binary search to locate candidate regions

PATCH In review Tarun Sahu 4 participants 7 messages Sep 3 – Sep 7

Subsystems (4)
lore
Share & tools
lore

Tarun Sahu

author
#0 lore raw

PATCH 1/1 memblock: use binary search to locate candidate regions

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.

---
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +36 -2
index 9ce86349a29f..88940474b020 100644
@@ -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;
 
Signature · 1 line
2.55.0.970.g62bdec98f9-goog
#1 lore raw
Quoted 9 lines · Tarun Sahu

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).

Quoted 6 lines

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.

---

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.

Quoted 73 lines
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +36 -2
index 9ce86349a29f..88940474b020 100644
@@ -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;
 
#2 lore raw
Quoted 17 lines · Dev Jain
Quoted 9 lines · Tarun Sahu

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).

Quoted 6 lines

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.

---

Quoted 8 lines

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?

Linear search on very large list: A very big problem Linear search on small list (< 100): Good and almost 100% cache hit because of next memory prediction by CPU.

Binary Search on very large list: very good thing
Binary search on small list (< 100): Algorithm anyway faster (worst case cycle 3-4 vs 100 in linear search), yes cache miss is problem but IIUC, To contribute to latency significantly, the quantity of such cache misses is very less. Binary search uses more instruction per loop than linear search, so of course linear search is better in this case, But that micro/nano seconds latency affect is really an issue here? because memblock is boot time initialization code. (Except memory hotplug) So No userspace application like HFT or gaming will be affected by this.

So I believe, binary search wins here. Let me know your thoughts?

Quoted 4 lines

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.

This one does lower bound serach: To find the first element where the addition can be done instead of trying to find the exact match.

This one has a fast-path unlike to general binary search:

+ if (type->cnt && base >= type->regions[type->cnt - 1].base +
+ type->regions[type->cnt - 1].size)
+ return type->cnt;

Also, I followed what memblock_search already does, Having its own binary search.

~Tarun

Quoted 74 lines
Quoted 74 lines
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +36 -2
index 9ce86349a29f..88940474b020 100644
@@ -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;
 
#3 lore raw
In reply to Tarun Sahu
Quoted 4 lines · Tarun Sahu

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.

Quoted 8 lines

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.

I encountered this issue with my workload. Initially, it was because I forgot to set THP to "always", As a result, there were many 4K pages even though they were contiguous.

Indeed, I noticed some delays or hiccups with my workload even with THP set to "always".

In the past month, I used something like what I attached at the end of my reply to reduce the number of memblock_reserve() calls. I never realized the poor performance was caused by memblock_reserve() itself.

[    0.231623] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
--> delay
[   38.587378] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1

With your patch, I ran several rounds of tests with THP set to "never" (4K pages) and no longer noticed any hiccups or delays with my workload.

[    0.247746] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
[    0.512019] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1

Thanks to this patch, I no longer have to put up with the delays or hiccups in my workload!

Thank you very much!

Dongli Zhang

kernel/liveupdate/kexec_handover.c +0 -0
index 7c4d86daf86d..03e1f914c800 100644
@@ -67,6 +67,8 @@ union kho_page_info {
 static_assert(sizeof(union kho_page_info) == sizeof(((struct page *)0)->private));
 
 static bool kho_enable __ro_after_init =

IS_ENABLED(CONFIG_KEXEC_HANDOVER_ENABLE_DEFAULT); +static phys_addr_t kho_preserved_batch_start __initdata; +static phys_addr_t kho_preserved_batch_end __initdata;

bool kho_is_enabled(void)
{
@@ -610,25 +612,58 @@ static struct page *__init
kho_get_preserved_page(phys_addr_t phys,
return pfn_to_page(pfn);
}

+static void __init kho_preserved_memory_batch_flush(void)
+{
+ phys_addr_t size;
+
+ if (kho_preserved_batch_start == kho_preserved_batch_end)
+ return;
+
+ size = kho_preserved_batch_end - kho_preserved_batch_start;
+ memblock_reserve(kho_preserved_batch_start, size);
+ memblock_reserved_mark_noinit(kho_preserved_batch_start, size);
+
+ kho_preserved_batch_start = 0;
+ kho_preserved_batch_end = 0;
+}
+
+static void __init kho_preserved_memory_batch_add(phys_addr_t phys,
+ unsigned int order)
+{
+ phys_addr_t size = 1ULL << (order + PAGE_SHIFT);
+ phys_addr_t end = phys + size;
+
+ if (kho_preserved_batch_start == kho_preserved_batch_end) {
+ kho_preserved_batch_start = phys;
+ kho_preserved_batch_end = end;
+ return;
+ }
+
+ if (phys == kho_preserved_batch_end) {
+ kho_preserved_batch_end = end;
+ return;
+ }
+
+ kho_preserved_memory_batch_flush();
+ kho_preserved_batch_start = phys;
+ kho_preserved_batch_end = end;
+}
+
static int __init kho_preserved_memory_reserve(unsigned long key, void *data) {
union kho_page_info info;
struct page *page;
unsigned int order;
phys_addr_t phys;
- u64 sz;

phys = kho_decode_radix_key(key, &order);

- sz = 1UL << (order + PAGE_SHIFT);
page = kho_get_preserved_page(phys, order);

- /* Reserve the memory preserved in KHO in memblock */
- memblock_reserve(phys, sz);
- memblock_reserved_mark_noinit(phys, sz);
info.magic = KHO_PAGE_MAGIC;
info.order = order;
page->private = info.page_private;
+ kho_preserved_memory_batch_add(phys, order);

return 0;
}
@@ -1687,8 +1722,13 @@ static void __init kho_mem_retrieve(void)
.leaf = kho_preserved_memory_reserve,
};

- if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL))
+ kho_preserved_batch_start = 0;
+ kho_preserved_batch_end = 0;
+ if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL)) {
+ kho_preserved_memory_batch_flush();
goto err;
+ }
+ kho_preserved_memory_batch_flush();

return;

Quoted 80 lines
---
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +36 -2
index 9ce86349a29f..88940474b020 100644
@@ -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;
 
Signature · 1 line
2.55.0.970.g62bdec98f9-goog
#4 lore raw
Quoted 32 lines · Dongli Zhang
Quoted 4 lines · Tarun Sahu

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.

Quoted 8 lines

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.

I encountered this issue with my workload. Initially, it was because I forgot to set THP to "always", As a result, there were many 4K pages even though they were contiguous.

Indeed, I noticed some delays or hiccups with my workload even with THP set to "always".

In the past month, I used something like what I attached at the end of my reply to reduce the number of memblock_reserve() calls. I never realized the poor performance was caused by memblock_reserve() itself.

[    0.231623] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
--> delay
[   38.587378] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1

With your patch, I ran several rounds of tests with THP set to "never" (4K pages) and no longer noticed any hiccups or delays with my workload.

Quoted 8 lines
[    0.247746] mem auto-init: stack:all(zero), heap alloc:off, heap free:off
[    0.512019] SLUB: HWalign=64, Order=0-3, MinObjects=0, CPUs=32, Nodes=1

Thanks to this patch, I no longer have to put up with the delays or hiccups in my workload!

Thank you very much!

Glad to know it helped and thanks for testing this.

Quoted 23 lines

Dongli Zhang

kernel/liveupdate/kexec_handover.c +2 -0
index 7c4d86daf86d..03e1f914c800 100644
@@ -67,6 +67,8 @@ union kho_page_info {
 static_assert(sizeof(union kho_page_info) == sizeof(((struct page *)0)->private));
 
 static bool kho_enable __ro_after_init =
 IS_ENABLED(CONFIG_KEXEC_HANDOVER_ENABLE_DEFAULT);
+static phys_addr_t kho_preserved_batch_start __initdata;
+static phys_addr_t kho_preserved_batch_end __initdata;
 
 bool kho_is_enabled(void)

{

kernel/liveupdate/kexec_handover.c +0 -0
@@ -610,25 +612,58 @@ static struct page *__init
 kho_get_preserved_page(phys_addr_t phys,
 	return pfn_to_page(pfn);
 }
 

kernel/liveupdate/kexec_handover.c static struct page *__init · line 625

Quoted 10 lines
kernel/liveupdate/kexec_handover.c +10 -0
+static void __init kho_preserved_memory_batch_flush(void)
+{
+	phys_addr_t size;
+
+	if (kho_preserved_batch_start == kho_preserved_batch_end)
+		return;
+
+	size = kho_preserved_batch_end - kho_preserved_batch_start;
+	memblock_reserve(kho_preserved_batch_start, size);
+	memblock_reserved_mark_noinit(kho_preserved_batch_start, size);

We can also combine these two function. IIUC, kho_preserved_batch_start does not overlap with other reserved regions so, they will be mutually exclusives ranges and can directly be marked noinit while adding to reserved list.

~Tarun

Quoted 145 lines
kernel/liveupdate/kexec_handover.c +28 -5
+
+	kho_preserved_batch_start = 0;
+	kho_preserved_batch_end = 0;
+}
+
+static void __init kho_preserved_memory_batch_add(phys_addr_t phys,
+						  unsigned int order)
+{
+	phys_addr_t size = 1ULL << (order + PAGE_SHIFT);
+	phys_addr_t end = phys + size;
+
+	if (kho_preserved_batch_start == kho_preserved_batch_end) {
+		kho_preserved_batch_start = phys;
+		kho_preserved_batch_end = end;
+		return;
+	}
+
+	if (phys == kho_preserved_batch_end) {
+		kho_preserved_batch_end = end;
+		return;
+	}
+
+	kho_preserved_memory_batch_flush();
+	kho_preserved_batch_start = phys;
+	kho_preserved_batch_end = end;
+}
+
 static int __init kho_preserved_memory_reserve(unsigned long key, void *data)
 {
 	union kho_page_info info;
 	struct page *page;
 	unsigned int order;
 	phys_addr_t phys;
-	u64 sz;
 
 	phys = kho_decode_radix_key(key, &order);
 
-	sz = 1UL << (order + PAGE_SHIFT);
 	page = kho_get_preserved_page(phys, order);
 
-	/* Reserve the memory preserved in KHO in memblock */
-	memblock_reserve(phys, sz);
-	memblock_reserved_mark_noinit(phys, sz);
 	info.magic = KHO_PAGE_MAGIC;
 	info.order = order;
 	page->private = info.page_private;
+	kho_preserved_memory_batch_add(phys, order);
 
 	return 0;

}

kernel/liveupdate/kexec_handover.c +6 -1
@@ -1687,8 +1722,13 @@ static void __init kho_mem_retrieve(void)
 		.leaf = kho_preserved_memory_reserve,
 	};
 
-	if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL))
+	kho_preserved_batch_start = 0;
+	kho_preserved_batch_end = 0;
+	if (kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL)) {
+		kho_preserved_memory_batch_flush();
 		goto err;
+	}
+	kho_preserved_memory_batch_flush();
 
 	return;
 
Quoted 80 lines
---
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +36 -2
index 9ce86349a29f..88940474b020 100644
@@ -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;
 
Signature · 1 line
2.55.0.970.g62bdec98f9-goog
maintainer
#5 lore raw
In reply to Tarun Sahu

Hi Tarun,

Quoted 38 lines · Tarun Sahu

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.

---
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +5 -0
index 9ce86349a29f..88940474b020 100644
@@ -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;
 }
 

mm/memblock.c static void __init_memblock memblock_insert_region(struct memblock_type *type, · line 608

Quoted 10 lines
mm/memblock.c +10 -0
+/**
+ * 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)
+{

We already have memblock_search() ;-)

Quoted 21 lines
mm/memblock.c +17 -0
+	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

mm/memblock.c static int __init_memblock memblock_add_range(struct memblock_type *type, · line 687

Quoted 6 lines
mm/memblock.c +2 -1
@@ -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)) {

I think we can just kill for_each_memblock_type() and open code all loops that use it and make memblock_add_range() and memblock_isolate_range() use binary search.

Quoted 16 lines
mm/memblock.c +2 -1
 		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;
 
Signature · 1 line
2.55.0.970.g62bdec98f9-goog
Signature · 2 lines
Sincerely yours,
Mike.
#6 lore raw
Quoted 41 lines · Mike Rapoport

Hi Tarun,

Quoted 38 lines · Tarun Sahu

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.

---
 mm/memblock.c | 38 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 36 insertions(+), 2 deletions(-)
mm/memblock.c +5 -0
index 9ce86349a29f..88940474b020 100644
@@ -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;
 }
 
Quoted 12 lines

mm/memblock.c static void __init_memblock memblock_insert_region(struct memblock_type *type, · line 608

Quoted 10 lines
mm/memblock.c +10 -0
+/**
+ * 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)
+{

We already have memblock_search() ;-)

Yes, I preferred to have saperate function because we need to search lower bound but not the exact match, as new entry might not exist and memblock_search will return -1 in that case.

To not duplicate the binary search code, we can update the memblock_search as the wrapper of memblock_bsearch_start (Approach 1):

mm/memblock.c +5 -14
index 88940474b020..d9a71234abcd 100644
@@ -2096,17 +2096,10 @@ static void __init_memblock memblock_dump(struct memblock_type *type)
 static int __init_memblock memblock_search(struct memblock_type *type, phys_addr_t addr)
 {
-	unsigned int left = 0, right = type->cnt;
-
-	do {
-		unsigned int mid = (right + left) / 2;
-
-		if (addr < type->regions[mid].base)
-			right = mid;
-		else if (addr >= (type->regions[mid].base +
-				  type->regions[mid].size))
-			left = mid + 1;
-		else
-			return mid;
-	} while (left < right);
-	return -1;
+	int idx = memblock_bsearch_start(type, addr);
+
+	if (idx < type->cnt && addr >= type->regions[idx].base)
+		return idx;
+	return -1;
 }

OR Approach 2:

The above approach still introduce two function for doing the search. So, I thought of updating the memblock_search(..., enum search_type) but this will require changes to all the places of memblock_search also.

I prefer approach 1, As it will keep the binary_search code within single function and have two function for two different type return values.

WDYT?

Quoted 25 lines
Quoted 25 lines
mm/memblock.c +17 -0
+	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;
 
Quoted 7 lines

mm/memblock.c static int __init_memblock memblock_add_range(struct memblock_type *type, · line 687

Quoted 3 lines
mm/memblock.c +2 -1
-	for_each_memblock_type(idx, type, rgn) {
+	for_each_memblock_type_from(idx, type, rgn,
+				    memblock_bsearch_start(type, base)) {

I think we can just kill for_each_memblock_type() and open code all loops that use it and make memblock_add_range() and memblock_isolate_range() use binary search.

Agree, there were three places memblock_add_range, memblock_dump, memblock_isolate_range, This patch already updating two of them. The for loop is not complex to be part of the macro, Open code sounds good to me.

~Tarun

Quoted 21 lines
Quoted 17 lines
mm/memblock.c +2 -1
 		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;
 
Signature · 1 line
2.55.0.970.g62bdec98f9-goog
Signature · 2 lines
Sincerely yours,
Mike.