Date: Mon, 20 Feb 2023 19:58:50 GMT From: Kyle Evans <kevans@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org Subject: git: 13f1d1bd8647 - stable/13 - kern: physmem: improve region coalescing logic Message-ID: <202302201958.31KJwodl065864@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 = ®ions[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 = ®ions[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(®ions[idx + 1], ®ions[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); } }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202302201958.31KJwodl065864>