git: 9e8174289236 - main - vm_phys: add binary segment search
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Fri, 16 Jun 2023 06:52:23 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=9e8174289236de996199aadc6357c05eafba3b38
commit 9e8174289236de996199aadc6357c05eafba3b38
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2023-06-16 06:43:45 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
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 <vm/_vm_phys.h>
+
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_ */