summaryrefslogtreecommitdiffstats
path: root/sys
diff options
context:
space:
mode:
authorsilby <silby@FreeBSD.org>2002-02-27 18:03:02 +0000
committersilby <silby@FreeBSD.org>2002-02-27 18:03:02 +0000
commit230f96f3ce0496343800b107e3e952de9d7747de (patch)
treec901dac940b687287b5e926cf9d3fee071a8a002 /sys
parent62c8af563fb2047ffe16514abfeef77eea1691b8 (diff)
downloadFreeBSD-src-230f96f3ce0496343800b107e3e952de9d7747de.zip
FreeBSD-src-230f96f3ce0496343800b107e3e952de9d7747de.tar.gz
Fix a horribly suboptimal algorithm in the vm_daemon.
In order to determine what to page out, the vm_daemon checks reference bits on all pages belonging to all processes. Unfortunately, the algorithm used reacted badly with shared pages; each shared page would be checked once per process sharing it; this caused an O(N^2) growth of tlb invalidations. The algorithm has been changed so that each page will be checked only 16 times. Prior to this change, a fork/sleepbomb of 1300 processes could cause the vm_daemon to take over 60 seconds to complete, effectively freezing the system for that time period. With this change in place, the vm_daemon completes in less than a second. Any system with hundreds of processes sharing pages should benefit from this change. Note that the vm_daemon is only run when the system is under extreme memory pressure. It is likely that many people with loaded systems saw no symptoms of this problem until they reached the point where swapping began. Special thanks go to dillon, peter, and Chuck Cranor, who helped me get up to speed with vm internals. PR: 33542, 20393 Reviewed by: dillon MFC after: 1 week
Diffstat (limited to 'sys')
-rw-r--r--sys/alpha/alpha/pmap.c24
-rw-r--r--sys/amd64/amd64/pmap.c27
-rw-r--r--sys/i386/i386/pmap.c27
-rw-r--r--sys/ia64/ia64/pmap.c25
-rw-r--r--sys/powerpc/aim/mmu_oea.c22
-rw-r--r--sys/powerpc/powerpc/mmu_oea.c22
-rw-r--r--sys/powerpc/powerpc/pmap.c22
-rw-r--r--sys/sparc64/sparc64/pmap.c21
-rw-r--r--sys/sparc64/sparc64/pv.c9
-rw-r--r--sys/vm/pmap.h2
-rw-r--r--sys/vm/vm_pageout.c2
11 files changed, 169 insertions, 34 deletions
diff --git a/sys/alpha/alpha/pmap.c b/sys/alpha/alpha/pmap.c
index e628d14..1bee3dd 100644
--- a/sys/alpha/alpha/pmap.c
+++ b/sys/alpha/alpha/pmap.c
@@ -2745,15 +2745,19 @@ pmap_pageable(pmap, sva, eva, pageable)
}
/*
- * this routine returns true if a physical page resides
- * in the given pmap.
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
*/
boolean_t
-pmap_page_exists(pmap, m)
+pmap_page_exists_quick(pmap, m)
pmap_t pmap;
vm_page_t m;
{
- register pv_entry_t pv;
+ pv_entry_t pv;
+ int loops = 0;
int s;
if (!pmap_initialized || (m->flags & PG_FICTITIOUS))
@@ -2769,6 +2773,9 @@ pmap_page_exists(pmap, m)
splx(s);
return TRUE;
}
+ loops++;
+ if (loops >= 16)
+ break;
}
splx(s);
return (FALSE);
@@ -2932,7 +2939,14 @@ pmap_phys_address(ppn)
/*
* pmap_ts_referenced:
*
- * Return the count of reference bits for a page, clearing all of them.
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
*/
int
pmap_ts_referenced(vm_page_t m)
diff --git a/sys/amd64/amd64/pmap.c b/sys/amd64/amd64/pmap.c
index f12cb0b..353e9a3 100644
--- a/sys/amd64/amd64/pmap.c
+++ b/sys/amd64/amd64/pmap.c
@@ -2933,15 +2933,19 @@ pmap_pageable(pmap, sva, eva, pageable)
}
/*
- * this routine returns true if a physical page resides
- * in the given pmap.
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
*/
boolean_t
-pmap_page_exists(pmap, m)
+pmap_page_exists_quick(pmap, m)
pmap_t pmap;
vm_page_t m;
{
- register pv_entry_t pv;
+ pv_entry_t pv;
+ int loops = 0;
int s;
if (!pmap_initialized || (m->flags & PG_FICTITIOUS))
@@ -2949,14 +2953,14 @@ pmap_page_exists(pmap, m)
s = splvm();
- /*
- * Not found, check current mappings returning immediately if found.
- */
TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
if (pv->pv_pmap == pmap) {
splx(s);
return TRUE;
}
+ loops++;
+ if (loops >= 16)
+ break;
}
splx(s);
return (FALSE);
@@ -3186,7 +3190,14 @@ pmap_phys_address(ppn)
/*
* pmap_ts_referenced:
*
- * Return the count of reference bits for a page, clearing all of them.
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
*/
int
pmap_ts_referenced(vm_page_t m)
diff --git a/sys/i386/i386/pmap.c b/sys/i386/i386/pmap.c
index f12cb0b..353e9a3 100644
--- a/sys/i386/i386/pmap.c
+++ b/sys/i386/i386/pmap.c
@@ -2933,15 +2933,19 @@ pmap_pageable(pmap, sva, eva, pageable)
}
/*
- * this routine returns true if a physical page resides
- * in the given pmap.
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
*/
boolean_t
-pmap_page_exists(pmap, m)
+pmap_page_exists_quick(pmap, m)
pmap_t pmap;
vm_page_t m;
{
- register pv_entry_t pv;
+ pv_entry_t pv;
+ int loops = 0;
int s;
if (!pmap_initialized || (m->flags & PG_FICTITIOUS))
@@ -2949,14 +2953,14 @@ pmap_page_exists(pmap, m)
s = splvm();
- /*
- * Not found, check current mappings returning immediately if found.
- */
TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
if (pv->pv_pmap == pmap) {
splx(s);
return TRUE;
}
+ loops++;
+ if (loops >= 16)
+ break;
}
splx(s);
return (FALSE);
@@ -3186,7 +3190,14 @@ pmap_phys_address(ppn)
/*
* pmap_ts_referenced:
*
- * Return the count of reference bits for a page, clearing all of them.
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
*/
int
pmap_ts_referenced(vm_page_t m)
diff --git a/sys/ia64/ia64/pmap.c b/sys/ia64/ia64/pmap.c
index e92f320..9a33f87 100644
--- a/sys/ia64/ia64/pmap.c
+++ b/sys/ia64/ia64/pmap.c
@@ -2152,13 +2152,17 @@ pmap_pageable(pmap_t pmap, vm_offset_t sva, vm_offset_t eva,
}
/*
- * this routine returns true if a physical page resides
- * in the given pmap.
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
*/
boolean_t
-pmap_page_exists(pmap_t pmap, vm_page_t m)
+pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
{
- register pv_entry_t pv;
+ pv_entry_t pv;
+ int loops = 0;
int s;
if (!pmap_initialized || (m->flags & PG_FICTITIOUS))
@@ -2174,6 +2178,9 @@ pmap_page_exists(pmap_t pmap, vm_page_t m)
splx(s);
return TRUE;
}
+ loops++;
+ if (loops >= 16)
+ break;
}
splx(s);
return (FALSE);
@@ -2269,8 +2276,14 @@ pmap_phys_address(int ppn)
/*
* pmap_ts_referenced:
*
- * Return the count of reference bits for a page, clearing all of them.
- *
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
*/
int
pmap_ts_referenced(vm_page_t m)
diff --git a/sys/powerpc/aim/mmu_oea.c b/sys/powerpc/aim/mmu_oea.c
index 0ba2131..2bd4633 100644
--- a/sys/powerpc/aim/mmu_oea.c
+++ b/sys/powerpc/aim/mmu_oea.c
@@ -936,6 +936,19 @@ pmap_clear_reference(vm_page_t m)
TODO;
}
+/*
+ * pmap_ts_referenced:
+ *
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
+ */
+
int
pmap_ts_referenced(vm_page_t m)
{
@@ -1160,8 +1173,15 @@ pmap_pageable(pmap_t pmap, vm_offset_t sva, vm_offset_t eva,
{
}
+/*
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
+ */
boolean_t
-pmap_page_exists(pmap_t pmap, vm_page_t m)
+pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
{
TODO;
return (0);
diff --git a/sys/powerpc/powerpc/mmu_oea.c b/sys/powerpc/powerpc/mmu_oea.c
index 0ba2131..2bd4633 100644
--- a/sys/powerpc/powerpc/mmu_oea.c
+++ b/sys/powerpc/powerpc/mmu_oea.c
@@ -936,6 +936,19 @@ pmap_clear_reference(vm_page_t m)
TODO;
}
+/*
+ * pmap_ts_referenced:
+ *
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
+ */
+
int
pmap_ts_referenced(vm_page_t m)
{
@@ -1160,8 +1173,15 @@ pmap_pageable(pmap_t pmap, vm_offset_t sva, vm_offset_t eva,
{
}
+/*
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
+ */
boolean_t
-pmap_page_exists(pmap_t pmap, vm_page_t m)
+pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
{
TODO;
return (0);
diff --git a/sys/powerpc/powerpc/pmap.c b/sys/powerpc/powerpc/pmap.c
index 0ba2131..2bd4633 100644
--- a/sys/powerpc/powerpc/pmap.c
+++ b/sys/powerpc/powerpc/pmap.c
@@ -936,6 +936,19 @@ pmap_clear_reference(vm_page_t m)
TODO;
}
+/*
+ * pmap_ts_referenced:
+ *
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
+ */
+
int
pmap_ts_referenced(vm_page_t m)
{
@@ -1160,8 +1173,15 @@ pmap_pageable(pmap_t pmap, vm_offset_t sva, vm_offset_t eva,
{
}
+/*
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
+ */
boolean_t
-pmap_page_exists(pmap_t pmap, vm_page_t m)
+pmap_page_exists_quick(pmap_t pmap, vm_page_t m)
{
TODO;
return (0);
diff --git a/sys/sparc64/sparc64/pmap.c b/sys/sparc64/sparc64/pmap.c
index 9285ff9..4836d78 100644
--- a/sys/sparc64/sparc64/pmap.c
+++ b/sys/sparc64/sparc64/pmap.c
@@ -1602,10 +1602,14 @@ pmap_pageable(pmap_t pmap, vm_offset_t sva, vm_offset_t eva,
}
/*
- * Return true of a physical page resided in the given pmap.
+ * Returns true if the pmap's pv is one of the first
+ * 16 pvs linked to from this page. This count may
+ * be changed upwards or downwards in the future; it
+ * is only necessary that true be returned for a small
+ * subset of pmaps for proper page aging.
*/
boolean_t
-pmap_page_exists(pmap_t pm, vm_page_t m)
+pmap_page_exists_quick(pmap_t pm, vm_page_t m)
{
if (m->flags & PG_FICTITIOUS)
@@ -1682,6 +1686,19 @@ pmap_phys_address(int ppn)
return (sparc64_ptob(ppn));
}
+/*
+ * pmap_ts_referenced:
+ *
+ * Return a count of reference bits for a page, clearing those bits.
+ * It is not necessary for every reference bit to be cleared, but it
+ * is necessary that 0 only be returned when there are truly no
+ * reference bits set.
+ *
+ * XXX: The exact number of bits to check and clear is a matter that
+ * should be tested and standardized at some point in the future for
+ * optimal aging of shared pages.
+ */
+
int
pmap_ts_referenced(vm_page_t m)
{
diff --git a/sys/sparc64/sparc64/pv.c b/sys/sparc64/sparc64/pv.c
index e17699d03..ae7ad61 100644
--- a/sys/sparc64/sparc64/pv.c
+++ b/sys/sparc64/sparc64/pv.c
@@ -215,15 +215,24 @@ pv_bit_test(vm_page_t m, u_long bits)
return (FALSE);
}
+/*
+ * See pmap_page_exists_quick for operational explanation of
+ * pv_page_exists.
+ */
+
int
pv_page_exists(pmap_t pm, vm_page_t m)
{
pv_entry_t pv;
+ int loops = 0;
TAILQ_FOREACH(pv, &m->md.pv_list, pv_list) {
if (pv->pv_pmap == pm) {
return (TRUE);
}
+ loops++;
+ if (loops >= 16)
+ break;
}
return (FALSE);
}
diff --git a/sys/vm/pmap.h b/sys/vm/pmap.h
index 89432aa..fea4b0f 100644
--- a/sys/vm/pmap.h
+++ b/sys/vm/pmap.h
@@ -115,7 +115,7 @@ vm_offset_t pmap_map __P((vm_offset_t *, vm_offset_t, vm_offset_t, int));
void pmap_object_init_pt __P((pmap_t pmap, vm_offset_t addr,
vm_object_t object, vm_pindex_t pindex, vm_offset_t size,
int pagelimit));
-boolean_t pmap_page_exists __P((pmap_t pmap, vm_page_t m));
+boolean_t pmap_page_exists_quick __P((pmap_t pmap, vm_page_t m));
void pmap_page_protect __P((vm_page_t m, vm_prot_t prot));
void pmap_pageable __P((pmap_t, vm_offset_t, vm_offset_t,
boolean_t));
diff --git a/sys/vm/vm_pageout.c b/sys/vm/vm_pageout.c
index 657f5e7..62a527d 100644
--- a/sys/vm/vm_pageout.c
+++ b/sys/vm/vm_pageout.c
@@ -494,7 +494,7 @@ vm_pageout_object_deactivate_pages(map, object, desired, map_remove_only)
p->hold_count != 0 ||
p->busy != 0 ||
(p->flags & (PG_BUSY|PG_UNMANAGED)) ||
- !pmap_page_exists(vm_map_pmap(map), p)) {
+ !pmap_page_exists_quick(vm_map_pmap(map), p)) {
p = next;
continue;
}
OpenPOWER on IntegriCloud