From nobody Mon Feb 20 19:58:50 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 4PLCsk3ldrz3rbLw; Mon, 20 Feb 2023 19:58:50 +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 4PLCsk3FPhz3J38; Mon, 20 Feb 2023 19:58:50 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1676923130; 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=iuTkFG1j9ApwVCORuQsTdiZtPrzzVlWMrpwqpG4VUZ8=; b=kYyYOQB0K4XFfxxXZ622X4LYLSQflPtmugWqMgseTb9H0ovSZnL1h9O1hmjb3MsDlLQSRP nMsV/4iEAuTv3AWFXI/Cg7SYws0qqqxjUphDPvx9cz52zSucbLZCzzIp7skTzyadK0KBNP qNn8fwmnaBDNbWIKiPJOQabl0neHL0vhQ38e+Nv/s+zPeDQp/5fy+tU2I9kjWmzH7SQzl1 zIK1sqnFTD1mYUIqp9EfEfnwxi0gi3Px/Xji3VqJKqn0cxePZbFFUAoQjQxKqRgu3kOzy2 5cO1YIpzOjo4dqT/a46NnNj45wLB72/X3el1QcowWpcJTuX0/qSW+SQoPdGw/Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1676923130; 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=iuTkFG1j9ApwVCORuQsTdiZtPrzzVlWMrpwqpG4VUZ8=; b=YNzlZ+5gf0CyMOqSROAXUHjehj/U8GaoZaADmMw9dF8HSlGTGgSZ9KrN9yoKgt8c2ZZEh2 kgltpOgwgduTNOGk+eMkfDs9BZwHPEysdPu4gRjeV0Fp+h9GCLbJUY1XEZsEtGV7sLOdmM WFV7ZhVcjT09cwXtWuz50mo7TcNIXfb0l+twz20A2FFAVV40g4qfZoYVu77LwoyafxvVjX j24cjLQZgacOXilf38IugkpRfUO8kJV+ImQqi2WmeTEk+xBhPbKkW9STRbqx4aW8WfwIKn Fl1Q4rjWSDDJUCh977XF+NTnGfNbyaR2lt833khWtUqQgYR82pk1kXWbBDw1Ww== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1676923130; a=rsa-sha256; cv=none; b=fvf/CX5OdD0eQXH6qnjUlNAqJ3k3ylDWWijylEU6Sd1p5r5FFAa15NGh6+bjF01KGVJUfv ve6yYbikjfuGEymmX/+S/NjTMHHm9R3xwsvNl4LWY5ZRa9WXPmlvMrgc2JpmbBSasiykW2 O/fFdeTg2Sf55BmlPdPEleD0CbL+2gLXPPg0gUNlzIvaCXTVM4Th36OQpxw2uaGC/bve9f xGWt3HMP3B/NFRGFTfHVIxKTLjW3R+ZlMoAIat653EzOkFRNCTnVTNVfx7247oJjYjy8Bf mh5ZJJqOO4o+PUEo/+9nXzAHDkYaou92fwJdNxB4eQtXm15L35UzV8adJ1xBIw== 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 4PLCsk2JzTztXW; Mon, 20 Feb 2023 19:58:50 +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 31KJwoO1065865; Mon, 20 Feb 2023 19:58:50 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 31KJwodl065864; Mon, 20 Feb 2023 19:58:50 GMT (envelope-from git) Date: Mon, 20 Feb 2023 19:58:50 GMT Message-Id: <202302201958.31KJwodl065864@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: 13f1d1bd8647 - stable/13 - 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/stable/13 X-Git-Reftype: branch X-Git-Commit: 13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by kevans: URL: https://cgit.FreeBSD.org/src/commit/?id=13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6 commit 13f1d1bd86476393b8a2ec2c79cb0b1637fcdec6 Author: Kyle Evans AuthorDate: 2021-10-28 04:40:08 +0000 Commit: Kyle Evans 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); } }