git: 13f1d1bd8647 - stable/13 - kern: physmem: improve region coalescing logic

The branch stable/13 has been updated by kevans:

URL: https://cgit.FreeBSD.org/src/commit/?id=13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6

commit 13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6
Author:     Kyle Evans <kevans@FreeBSD.org>
AuthorDate: 2021-10-28 04:40:08 +0000
Commit:     Kyle Evans <kevans@FreeBSD.org>
CommitDate: 2023-02-20 19:58:20 +0000

    kern: physmem: improve region coalescing logic
    
    The existing logic didn't take into account newly inserted mappings
    wholly contained by an existing region (or vice versa), nor did it
    account for weird overlap scenarios.  The latter is probably unlikely
    to happen, but the former may happen in UEFI: BootServicesData allocated
    within a large chunk of ConventionalMemory.  This situation blows up vm
    initialization.
    
    While we're here, remove the "exact match" logic as it's likely wrong;
    if an exact match exists with conflicting flags, for instance, then we
    should probably be doing something else.  The new logic takes into
    account exact matches as part of the overlapping efforts.
    
    Reviewed by:    kib, mhorne (both earlier version)
    Differential Revision:  https://reviews.freebsd.org/D32701
    
    (cherry picked from commit 7771f2a0c94fc2f7b9ce1565a49e52dba1e7381d)
---
 sys/kern/subr_physmem.c | 92 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 86 insertions(+), 6 deletions(-)

diff --git a/sys/kern/subr_physmem.c b/sys/kern/subr_physmem.c
index 99b4c2141612..2c7837019ea2 100644
--- a/sys/kern/subr_physmem.c
+++ b/sys/kern/subr_physmem.c
@@ -295,6 +295,67 @@ regions_to_avail(vm_paddr_t *avail, uint32_t exflags, size_t maxavail,
 	return (acnt);
 }
 
+/*
+ * Check if the region at idx can be merged with the region above it.
+ */
+static size_t
+merge_upper_regions(struct region *regions, size_t rcnt, size_t idx)
+{
+	struct region *lower, *upper;
+	vm_paddr_t lend, uend;
+	size_t i, mergecnt, movecnt;
+
+	lower = &regions[idx];
+	lend = lower->addr + lower->size;
+
+	/*
+	 * Continue merging in upper entries as long as we have entries to
+	 * merge; the new block could have spanned more than one, although one
+	 * is likely the common case.
+	 */
+	for (i = idx + 1; i < rcnt; i++) {
+		upper = &regions[i];
+		if (lend < upper->addr || lower->flags != upper->flags)
+			break;
+
+		uend = upper->addr + upper->size;
+		if (uend > lend) {
+			lower->size += uend - lend;
+			lend = lower->addr + lower->size;
+		}
+
+		if (uend >= lend) {
+			/*
+			 * If we didn't move past the end of the upper region,
+			 * then we don't need to bother checking for another
+			 * merge because it would have been done already.  Just
+			 * increment i once more to maintain the invariant that
+			 * i is one past the last entry merged.
+			 */
+			i++;
+			break;
+		}
+	}
+
+	/*
+	 * We merged in the entries from [idx + 1, i); physically move the tail
+	 * end at [i, rcnt) if we need to.
+	 */
+	mergecnt = i - (idx + 1);
+	if (mergecnt > 0) {
+		movecnt = rcnt - i;
+		if (movecnt == 0) {
+			/* Merged all the way to the end, just decrease rcnt. */
+			rcnt = idx + 1;
+		} else {
+			memmove(&regions[idx + 1], &regions[idx + mergecnt + 1],
+			    movecnt * sizeof(*regions));
+			rcnt -= mergecnt;
+		}
+	}
+	return (rcnt);
+}
+
 /*
  * Insertion-sort a new entry into a regions list; sorted by start address.
  */
@@ -303,19 +364,38 @@ insert_region(struct region *regions, size_t rcnt, vm_paddr_t addr,
     vm_size_t size, uint32_t flags)
 {
 	size_t i;
+	vm_paddr_t nend, rend;
 	struct region *ep, *rp;
 
+	nend = addr + size;
 	ep = regions + rcnt;
 	for (i = 0, rp = regions; i < rcnt; ++i, ++rp) {
-		if (rp->addr == addr && rp->size == size) /* Pure dup. */
-			return (rcnt);
 		if (flags == rp->flags) {
-			if (addr + size == rp->addr) {
+			rend = rp->addr + rp->size;
+			if (addr <= rp->addr && nend >= rp->addr) {
+				/*
+				 * New mapping overlaps at the beginning, shift
+				 * for any difference in the beginning then
+				 * shift if the new mapping extends past.
+				 */
+				rp->size += rp->addr - addr;
 				rp->addr = addr;
-				rp->size += size;
+				if (nend > rend) {
+					rp->size += nend - rend;
+					rcnt = merge_upper_regions(regions,
+					    rcnt, i);
+				}
 				return (rcnt);
-			} else if (rp->addr + rp->size == addr) {
-				rp->size += size;
+			} else if (addr <= rend && nend > rp->addr) {
+				/*
+				 * New mapping is either entirely contained
+				 * within or it's overlapping at the end.
+				 */
+				if (nend > rend) {
+					rp->size += nend - rend;
+					rcnt = merge_upper_regions(regions,
+					    rcnt, i);
+				}
 				return (rcnt);
 			}
 		}