From nobody Wed Nov 03 07:34:12 2021 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 95CA318387B7; Wed, 3 Nov 2021 07:34:12 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4HkdnJ3hhpz4lKP; Wed, 3 Nov 2021 07:34:12 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 54132145F6; Wed, 3 Nov 2021 07:34:12 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 1A37YCSL002282; Wed, 3 Nov 2021 07:34:12 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 1A37YChn002281; Wed, 3 Nov 2021 07:34:12 GMT (envelope-from git) Date: Wed, 3 Nov 2021 07:34:12 GMT Message-Id: <202111030734.1A37YChn002281@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Kyle Evans Subject: git: 7771f2a0c94f - main - kern: physmem: improve region coalescing logic List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: kevans X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 7771f2a0c94fc2f7b9ce1565a49e52dba1e7381d Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by kevans: URL: https://cgit.FreeBSD.org/src/commit/?id=7771f2a0c94fc2f7b9ce1565a49e52dba1e7381d commit 7771f2a0c94fc2f7b9ce1565a49e52dba1e7381d Author: Kyle Evans AuthorDate: 2021-10-28 04:40:08 +0000 Commit: Kyle Evans CommitDate: 2021-11-03 07:32:46 +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 --- 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 ea1ec12dd065..1cff1eb062c6 100644 --- a/sys/kern/subr_physmem.c +++ b/sys/kern/subr_physmem.c @@ -270,6 +270,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. */ @@ -278,19 +339,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); } }