From nobody Tue Feb 21 17:03:12 2023 X-Original-To: dev-commits-src-all@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 4PLlwc4spJz3stKR; Tue, 21 Feb 2023 17:03: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 4PLlwc2fXrz3Pv8; Tue, 21 Feb 2023 17:03:12 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1676998992; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9qW3a3hZsk63AFz9VfU6/Kx+s1SWHCbGbShKpVbqyDo=; b=jZcNKsxUOEuYzLTrGxaJAO73KORHI0yhelmUGh2cP/A8AYvOv2uaw6lZUuQpPskeTgha5W bnG6NTpl68qZGfMDjqraGgAdT6gtOjZBchEEhX0AxYvM9VM7xnuynBkFxfvMulyEOkyfOs PriMD5/cvZVcL5Bnl475wfizr4+yM3xMIPNQVUcZcqhoGEynpNy1BNXr9HjlyGdMXSMs3o G7uaESOTQejGmuK5+ElVEYF8MZxgJmzGVrgJ7nkBE8+fX8IkUlTT/pBG9ER0uwvIKhffe7 f58qJf3z+GGpXe6DSHgr4nEscNGUvAkA/I2pu+BkZ6ZVpyWqhfUBPUQ/JraAdQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1676998992; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9qW3a3hZsk63AFz9VfU6/Kx+s1SWHCbGbShKpVbqyDo=; b=PpDQ8TTPPq4iiPXmwOQoE6M2/wPFbBBYW4O2jcMFn/15+mqQYeDNEqvD2YCPsoa/zGLAOi FlQk4SK5mgEwDZfuJJnIlyu6R/4nWnavqJIzI27Il7EMamtpu+vE5va76NO/PFF4+DWWbH O/R4Rk/3a4jwv6VOBIa/GzqQbIZhwW0tnCEVRcLzRbcTFU6dqQb/1ImyMECGN2VO4OMZpw s3tcJ97Ti5RBBgElrqUdyYMLq7XJSZ+0IOYUhjtv+KYHk3LDK8mSQP/4tRe0ELOlxrMxPW wECI84MX/FGUGMRxuoOtsqcPv3t7qNMREmsbEl5b/DgyqCqwyjDxAsJR1G5RFw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1676998992; a=rsa-sha256; cv=none; b=wyK/h76/+4yRPyvWEwdSMQlYvLMGG0mjePYVMZ+5JynLAVegBElptppr8cF0OPQ9z7Tj3J RoFiZJZXsOnXq3j5Z2t23H+UbXVMsGCcO0nOKigQOXYyqRYvgrTtzj5RJW0tyDt5gx+sFb EOFC9HpGzgcdl3PHhYxT8vBXCHW6mmjDzuHj+hGMTGgRv3C+REwM+TmOFPd3Ak2y6SB2zD awub+02ymZ92Ym0NRF5QvLYHZyVnrcyFhtiZrdbQl1WMGjUF+AFG+ANodB6gZyf0QpLL59 UD3EDNR+YSR1cTfhZw7RkgaO5OtP1h3VYrvQ5JJWBaGqLWA728cmPWhOZcW7bg== 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 4PLlwc1kZ8zSdL; Tue, 21 Feb 2023 17:03: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 31LH3C7B079728; Tue, 21 Feb 2023 17:03:12 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 31LH3CnE079727; Tue, 21 Feb 2023 17:03:12 GMT (envelope-from git) Date: Tue, 21 Feb 2023 17:03:12 GMT Message-Id: <202302211703.31LH3CnE079727@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Kyle Evans Subject: git: 42657d65d8aa - releng/13.2 - kern: physmem: improve region coalescing logic List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@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/releng/13.2 X-Git-Reftype: branch X-Git-Commit: 42657d65d8aabf201209b8472ef664c6dba5b6ca Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch releng/13.2 has been updated by kevans: URL: https://cgit.FreeBSD.org/src/commit/?id=42657d65d8aabf201209b8472ef664c6dba5b6ca commit 42657d65d8aabf201209b8472ef664c6dba5b6ca Author: Kyle Evans AuthorDate: 2021-10-28 04:40:08 +0000 Commit: Kyle Evans CommitDate: 2023-02-21 17:02:49 +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) Approved by: re (cperciva) (cherry picked from commit 7771f2a0c94fc2f7b9ce1565a49e52dba1e7381d) (cherry picked from commit 13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6) --- 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); } }