mm/cma: fix range selection in cma_declare_contiguous_multi()

These two patches fix two independent bugs in the multi-range selection of cma_declare_contiguous_multi(), found by code inspection with the help of an LLM (both patches carry Assisted-by: LLM).

Patch 1 fixes list_insert_sorted(), which does not actually sort: it stops at the wrong entry and, when no entry matches, inserts before the last entry instead of appending. The caller assumes the list tail is the smallest recorded range and that the list is walked largest first.

Patch 2 fixes sizesum counting the size of ranges that were skipped because the list was full, so the sizesum < total_size check can pass when the recorded ranges cannot cover the request, and the function returns 0 having reserved less than asked for.

Each patch fixes a distinct failure and neither depends on the other. No kernel-level reproducer was produced and nothing was tested beyond compiling; the examples in the commit messages come from a userspace copy of the helper and the selection loop, written from the source.

Changes in v2:
- resend as a series with a cover letter, as requested by Lorenzo
- commit messages now state how the bugs were found and that they were not tested on hardware or in a booted kernel
- add Assisted-by: LLM
- patch 1: correct the sentence about the first inserted range staying at the tail (only until it is evicted)
- rebased on the current akpm/mm-new
- no code changes

v1: https://lore.kernel.org/all/[email protected]/

Ivy Lopez (2):
mm/cma: fix list_insert_sorted() ordering
mm/cma: do not count skipped ranges in cma_declare_contiguous_multi()

 mm/cma.c | 16 ++++++----------
 1 file changed, 6 insertions(+), 10 deletions(-)

2.56.0

cma_declare_contiguous_multi() uses list_insert_sorted() to keep its candidate ranges sorted by size, largest first (revsizecmp()), and by base address, lowest first (basecmp()). Both comparators return true when the first argument sorts before the second.

The helper stops at the first existing entry for which cmp(entry, new) is true and inserts the new range before it, which is the reverse of what is needed. If no entry matches, mlp is left pointing at the last entry and the new range is inserted before it instead of being appended. With revsizecmp(), inserting sizes 1 2 3 4 yields 2 3 4 1 and inserting 4 3 2 1 yields 1 2 3 4. The first range inserted stays at the tail until it is evicted.

The caller relies on list_last_entry() being the smallest recorded range when deciding whether to skip or replace a candidate, and on walking the list largest first when picking the final ranges. With the list misordered, a candidate larger than some recorded ranges can be skipped because it is smaller than the first range found, so the function can fail or reserve less than requested where a valid layout exists. For example, free ranges of 4G, 7 x 1G and 2G, in address order, with a request of 12G: the 2G range is dropped instead of replacing a 1G one.

Insert before the first entry the new range sorts before, and append when there is none.

Found by code inspection with the help of an LLM. No kernel-level reproducer was produced and this was not tested on hardware or in a booted kernel. The example above comes from a userspace copy of the helper and the selection loop, written from the source.

---
 mm/cma.c | 14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)

index a10ea37a261d..527b2d894f3e 100644
@@ -348,16 +348,12 @@ static void __init list_insert_sorted(
 	struct list_head *mp;
 	struct cma_init_memrange *mlp;
 
-	if (list_empty(ranges))
-		list_add(&mrp->list, ranges);
-	else {
-		list_for_each(mp, ranges) {
-			mlp = list_entry(mp, struct cma_init_memrange, list);
-			if (cmp(mlp, mrp))
-				break;
-		}
-		__list_add(&mrp->list, mlp->list.prev, &mlp->list);
+	list_for_each(mp, ranges) {
+		mlp = list_entry(mp, struct cma_init_memrange, list);
+		if (cmp(mrp, mlp))
+			break;
 	}
+	list_add_tail(&mrp->list, mp);
 }
 
 static int __init cma_fixed_reserve(phys_addr_t base, phys_addr_t size)

2.56.0

cma_declare_contiguous_multi() adds the size of every candidate range to sizesum before deciding whether to record it. Once CMA_MAX_RANGES ranges are recorded, a candidate smaller than the last recorded one is skipped, but its size stays in sizesum. The replacement path already subtracts the evicted range, so sizesum is meant to track recorded ranges only.

When more than CMA_MAX_RANGES ranges exist and one is skipped, sizesum can reach total_size while the recorded ranges cannot. The sizesum < total_size check then passes, the reserve loop ends with sizeleft nonzero, and the function returns 0 with fewer pages reserved than requested. cma->count, available_count and totalcma_pages still reflect the full size, and the final message reports it as reserved.

For example, 8 free ranges of 1G followed by one of 512M with a request of 8G + 256M reserves 8G and returns 0.

Only count a range once it is recorded.

Found by code inspection with the help of an LLM. No kernel-level reproducer was produced and this was not tested on hardware or in a booted kernel. The example above comes from a userspace copy of the selection loop, written from the source.

---
Resend: the first attempt of this patch was blocked by Gmail and was not delivered to any recipient.

 mm/cma.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 527b2d894f3e..c2cdef953ee9 100644
@@ -594,7 +594,6 @@ int __init cma_declare_contiguous_multi(phys_addr_t total_size,
 		size = ALIGN_DOWN(size, (PAGE_SIZE << order_per_bit));
 		if (!size)
 			continue;
-		sizesum += size;
 
 		pr_debug("consider %016llx - %016llx\n", (u64)start, (u64)end);
 

@@ -620,6 +619,7 @@ int __init cma_declare_contiguous_multi(phys_addr_t total_size,
 		}
 		mrp->base = start;
 		mrp->size = size;
+		sizesum += size;
 
 		/*
 		 * Now do a sorted insert.

2.56.0

cma_declare_contiguous_multi() seems broken in many ways. I'm working on a patch to rewrite it.

Sincerely yours,
Mike.

Do these two fixes still apply?

Cheers,

David

Yes. I checked against akpm/mm-new at dba8aba0a9a0: both patches still apply (two hunks with a small line offset from the accept_memory() additions) and both problems are still present, since list_insert_sorted() and the sizesum accounting are unchanged there. If Mike's rewrite is going to replace this code soon, dropping them is fine with me. Otherwise I can respin them.

ivy

Sorry, got distracted, here's my version:

https://lore.kernel.org/linux-mm/[email protected]

Sincerely yours,
Mike.