From nobody Fri Jun 16 06:52:23 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 4Qj8wl3sxxz4fTsR; Fri, 16 Jun 2023 06:52:23 +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 4Qj8wl3Qg6z450p; Fri, 16 Jun 2023 06:52:23 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1686898343; 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=cg4q7W2eVbYHhcWq844DfmLC9GTncWjAnZBobr+y38c=; b=BhL3EsnDRklxtajFJ8zOd5WxN/E1j5Zwh6CdDJDqI5AfSK6vQ6nZTMzOjCapMZwGWSoCMZ U0p/0cIMGR8WKtJgU+bBgG6vGnnAIZywztVy2q38SyAfVAXTZ95FrIq0TBd8r3o24e7MuA 0DYObvyy5ZVDmbUW4khN2jYulub+rCUpsD2P+zCOVJ1zfaxNnvFGQGnyLoxydQbAcB4+fW BO5bWqkbh2xXShvoydW4VI9H8hD+B1+nFEb16WZhZoydvECc5W7xmFknNXwwgaUUWCRpZu M/vFHqbBzFG8tdM/5+Kx+Z+TBGg01O/gyDnyb7Ry6HxXC1egqSKBVyMVnwJnmA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1686898343; 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=cg4q7W2eVbYHhcWq844DfmLC9GTncWjAnZBobr+y38c=; b=U+EDkOsr7EdGaqk5n9M6aq5DzCMFnVuWGJ8I7XdM8qsGO8wnZGcas9fwJxjbgSajul29ZF nF4lKSIoNrl5O2Kr/tPPFIv67+Rgvv6A8stBKbLzJ3w2IXWiSZksMP5oss+64OZu30DsTd 5gYEf+kApmbAiMffE8PHNjSVTmCX+jM/Vypr6NvPpVR7WPIIyLmomQvRf6XNHhhvp4Te9Y CJDAKRavESaCl5TUr/aIEK+wryS+cK3osvl/0JW/Kwog7EqLmsyHmTBWL7BuMg1jfms1ud ZRb9jiO1efSTDvrvVyB2fCtTo1zHaKlz0cfn00PJv03m4sfN4N5urYtM2SXJ6w== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1686898343; a=rsa-sha256; cv=none; b=HQnkEqq5B502JtKEIDWt+COrqrucraFVDj4gM2m5Aec629NaxWeXzXhp0NYKOx3kMqxjpi Y58Jn9I7lhcZEPjduR7djjhr8wt97IuZhyADr837f19JDILNfr1AgtsNhJmTfisup2s/6b O7690uuPCJmi45/ASNXT968XS56osLoxXiZs6+7KFlYBSXgbBVmY+VbB1OVQZB06+JQl+q 9ErAqNRPPX11+s/FQMiXM0ZVs6ARQKLr12KbegRnuKPGosQhsOouTuL8V4UI/+a/b9XKtt P0Yy3W7iPQEVp9NuMurbb6MFpyYh7DDKVw36L88EguP5Anca1rI2vJdbydSxSw== 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 4Qj8wl2W5LzJj2; Fri, 16 Jun 2023 06:52:23 +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 35G6qN0F000191; Fri, 16 Jun 2023 06:52:23 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 35G6qNMd000190; Fri, 16 Jun 2023 06:52:23 GMT (envelope-from git) Date: Fri, 16 Jun 2023 06:52:23 GMT Message-Id: <202306160652.35G6qNMd000190@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 9e8174289236 - main - vm_phys: add binary segment search 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: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 9e8174289236de996199aadc6357c05eafba3b38 Auto-Submitted: auto-generated X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=9e8174289236de996199aadc6357c05eafba3b38 commit 9e8174289236de996199aadc6357c05eafba3b38 Author: Doug Moore AuthorDate: 2023-06-16 06:43:45 +0000 Commit: Doug Moore CommitDate: 2023-06-16 06:43:45 +0000 vm_phys: add binary segment search Replace several sequential searches for a segment that contains a phyiscal address with a call to a function that does it by binary search. In vm_page_reclaim_contig_domain_ext, find the first segment to reclaim from, and reclaim from each subsequent appropriate segment. Eliminate vm_phys_scan_contig. Reviewed by: alc, markj Differential Revision: https://reviews.freebsd.org/D40058 --- sys/arm64/arm64/pmap.c | 10 +++----- sys/vm/vm_page.c | 26 +++++++++---------- sys/vm/vm_page.h | 2 -- sys/vm/vm_phys.c | 69 ++++++++++++++++---------------------------------- sys/vm/vm_phys.h | 48 +++++++++++++++++++++++++++++++++-- 5 files changed, 84 insertions(+), 71 deletions(-) diff --git a/sys/arm64/arm64/pmap.c b/sys/arm64/arm64/pmap.c index 4bd1e86ffd5f..3166b3d7959b 100644 --- a/sys/arm64/arm64/pmap.c +++ b/sys/arm64/arm64/pmap.c @@ -210,14 +210,10 @@ static struct pmap_large_md_page * _pa_to_pmdp(vm_paddr_t pa) { struct vm_phys_seg *seg; - int segind; - for (segind = 0; segind < vm_phys_nsegs; segind++) { - seg = &vm_phys_segs[segind]; - if (pa >= seg->start && pa < seg->end) - return ((struct pmap_large_md_page *)seg->md_first + - pmap_l2_pindex(pa) - pmap_l2_pindex(seg->start)); - } + if ((seg = vm_phys_paddr_to_seg(pa)) != NULL) + return ((struct pmap_large_md_page *)seg->md_first + + pmap_l2_pindex(pa) - pmap_l2_pindex(seg->start)); return (NULL); } diff --git a/sys/vm/vm_page.c b/sys/vm/vm_page.c index 5d822d34ed7c..5e613ff4db4c 100644 --- a/sys/vm/vm_page.c +++ b/sys/vm/vm_page.c @@ -2627,7 +2627,7 @@ vm_page_zone_release(void *arg, void **store, int cnt) * span a hole (or discontiguity) in the physical address space. Both * "alignment" and "boundary" must be a power of two. */ -vm_page_t +static vm_page_t vm_page_scan_contig(u_long npages, vm_page_t m_start, vm_page_t m_end, u_long alignment, vm_paddr_t boundary, int options) { @@ -3028,10 +3028,9 @@ vm_page_reclaim_contig_domain_ext(int domain, int req, u_long npages, int desired_runs) { struct vm_domain *vmd; - vm_paddr_t curr_low; - vm_page_t m_run, _m_runs[NRUNS], *m_runs; + vm_page_t bounds[2], m_run, _m_runs[NRUNS], *m_runs; u_long count, minalign, reclaimed; - int error, i, min_reclaim, nruns, options, req_class; + int error, i, min_reclaim, nruns, options, req_class, segind; bool ret; KASSERT(npages > 0, ("npages is 0")); @@ -3098,16 +3097,17 @@ vm_page_reclaim_contig_domain_ext(int domain, int req, u_long npages, * Find the highest runs that satisfy the given constraints * and restrictions, and record them in "m_runs". */ - curr_low = low; count = 0; - for (;;) { - m_run = vm_phys_scan_contig(domain, npages, curr_low, - high, alignment, boundary, options); - if (m_run == NULL) - break; - curr_low = VM_PAGE_TO_PHYS(m_run) + ptoa(npages); - m_runs[RUN_INDEX(count, nruns)] = m_run; - count++; + segind = vm_phys_lookup_segind(low); + while ((segind = vm_phys_find_range(bounds, segind, domain, + npages, low, high)) != -1) { + while ((m_run = vm_page_scan_contig(npages, bounds[0], + bounds[1], alignment, boundary, options))) { + bounds[0] = m_run + npages; + m_runs[RUN_INDEX(count, nruns)] = m_run; + count++; + } + segind++; } /* diff --git a/sys/vm/vm_page.h b/sys/vm/vm_page.h index 824a853fb0f7..8ac99da21c59 100644 --- a/sys/vm/vm_page.h +++ b/sys/vm/vm_page.h @@ -683,8 +683,6 @@ int vm_page_rename(vm_page_t, vm_object_t, vm_pindex_t); void vm_page_replace(vm_page_t mnew, vm_object_t object, vm_pindex_t pindex, vm_page_t mold); int vm_page_sbusied(vm_page_t m); -vm_page_t vm_page_scan_contig(u_long npages, vm_page_t m_start, - vm_page_t m_end, u_long alignment, vm_paddr_t boundary, int options); vm_page_bits_t vm_page_set_dirty(vm_page_t m); void vm_page_set_valid_range(vm_page_t m, int base, int size); vm_offset_t vm_page_startup(vm_offset_t vaddr); diff --git a/sys/vm/vm_phys.c b/sys/vm/vm_phys.c index 8db6529b8c80..a0b53f0f7c4b 100644 --- a/sys/vm/vm_phys.c +++ b/sys/vm/vm_phys.c @@ -898,13 +898,9 @@ vm_page_t vm_phys_paddr_to_vm_page(vm_paddr_t pa) { struct vm_phys_seg *seg; - int segind; - for (segind = 0; segind < vm_phys_nsegs; segind++) { - seg = &vm_phys_segs[segind]; - if (pa >= seg->start && pa < seg->end) - return (&seg->first_page[atop(pa - seg->start)]); - } + if ((seg = vm_phys_paddr_to_seg(pa)) != NULL) + return (&seg->first_page[atop(pa - seg->start)]); return (NULL); } @@ -1238,55 +1234,34 @@ vm_phys_free_contig(vm_page_t m, u_long npages) } /* - * Scan physical memory between the specified addresses "low" and "high" for a - * run of contiguous physical pages that satisfy the specified conditions, and - * return the lowest page in the run. The specified "alignment" determines - * the alignment of the lowest physical page in the run. If the specified - * "boundary" is non-zero, then the run of physical pages cannot span a - * physical address that is a multiple of "boundary". - * - * "npages" must be greater than zero. Both "alignment" and "boundary" must - * be a power of two. + * Identify the first address range within segment segind or greater + * that matches the domain, lies within the low/high range, and has + * enough pages. Return -1 if there is none. */ -vm_page_t -vm_phys_scan_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high, - u_long alignment, vm_paddr_t boundary, int options) +int +vm_phys_find_range(vm_page_t bounds[], int segind, int domain, + u_long npages, vm_paddr_t low, vm_paddr_t high) { - vm_paddr_t pa_end; - vm_page_t m_end, m_run, m_start; - struct vm_phys_seg *seg; - int segind; + vm_paddr_t pa_end, pa_start; + struct vm_phys_seg *end_seg, *seg; - KASSERT(npages > 0, ("npages is 0")); - KASSERT(powerof2(alignment), ("alignment is not a power of 2")); - KASSERT(powerof2(boundary), ("boundary is not a power of 2")); - if (low >= high) - return (NULL); - for (segind = 0; segind < vm_phys_nsegs; segind++) { - seg = &vm_phys_segs[segind]; + KASSERT(npages > 0, ("npages is zero")); + KASSERT(domain >= 0 && domain < vm_ndomain, ("domain out of range")); + end_seg = &vm_phys_segs[vm_phys_nsegs]; + for (seg = &vm_phys_segs[segind]; seg < end_seg; seg++) { if (seg->domain != domain) continue; if (seg->start >= high) - break; - if (low >= seg->end) - continue; - if (low <= seg->start) - m_start = seg->first_page; - else - m_start = &seg->first_page[atop(low - seg->start)]; - if (high < seg->end) - pa_end = high; - else - pa_end = seg->end; - if (pa_end - VM_PAGE_TO_PHYS(m_start) < ptoa(npages)) + return (-1); + pa_start = MAX(low, seg->start); + pa_end = MIN(high, seg->end); + if (pa_end - pa_start < ptoa(npages)) continue; - m_end = &seg->first_page[atop(pa_end - seg->start)]; - m_run = vm_page_scan_contig(npages, m_start, m_end, - alignment, boundary, options); - if (m_run != NULL) - return (m_run); + bounds[0] = &seg->first_page[atop(pa_start - seg->start)]; + bounds[1] = &seg->first_page[atop(pa_end - seg->start)]; + return (seg - vm_phys_segs); } - return (NULL); + return (-1); } /* diff --git a/sys/vm/vm_phys.h b/sys/vm/vm_phys.h index a294bbaad80a..fed20bbaae1e 100644 --- a/sys/vm/vm_phys.h +++ b/sys/vm/vm_phys.h @@ -42,6 +42,8 @@ #ifdef _KERNEL +#include + extern vm_paddr_t phys_avail[]; /* Domains must be dense (non-sparse) and zero-based. */ @@ -71,14 +73,14 @@ int vm_phys_fictitious_reg_range(vm_paddr_t start, vm_paddr_t end, vm_memattr_t memattr); void vm_phys_fictitious_unreg_range(vm_paddr_t start, vm_paddr_t end); vm_page_t vm_phys_fictitious_to_vm_page(vm_paddr_t pa); +int vm_phys_find_range(vm_page_t bounds[], int segind, int domain, + u_long npages, vm_paddr_t low, vm_paddr_t high); void vm_phys_free_contig(vm_page_t m, u_long npages); void vm_phys_free_pages(vm_page_t m, int order); void vm_phys_init(void); vm_page_t vm_phys_paddr_to_vm_page(vm_paddr_t pa); void vm_phys_register_domains(int ndomains, struct mem_affinity *affinity, int *locality); -vm_page_t vm_phys_scan_contig(int domain, u_long npages, vm_paddr_t low, - vm_paddr_t high, u_long alignment, vm_paddr_t boundary, int options); bool vm_phys_unfree_page(vm_page_t m); int vm_phys_mem_affinity(int f, int t); void vm_phys_early_add_seg(vm_paddr_t start, vm_paddr_t end); @@ -106,5 +108,47 @@ vm_phys_domain(vm_paddr_t pa) #endif } +/* + * Find the segind for the first segment at or after the given physical address. + */ +static inline int +vm_phys_lookup_segind(vm_paddr_t pa) +{ + u_int hi, lo, mid; + + lo = 0; + hi = vm_phys_nsegs; + while (lo != hi) { + /* + * for i in [0, lo), segs[i].end <= pa + * for i in [hi, nsegs), segs[i].end > pa + */ + mid = lo + (hi - lo) / 2; + if (vm_phys_segs[mid].end <= pa) + lo = mid + 1; + else + hi = mid; + } + return (lo); +} + +/* + * Find the segment corresponding to the given physical address. + */ +static inline struct vm_phys_seg * +vm_phys_paddr_to_seg(vm_paddr_t pa) +{ + struct vm_phys_seg *seg; + int segind; + + segind = vm_phys_lookup_segind(pa); + if (segind < vm_phys_nsegs) { + seg = &vm_phys_segs[segind]; + if (pa >= seg->start) + return (seg); + } + return (NULL); +} + #endif /* _KERNEL */ #endif /* !_VM_PHYS_H_ */