Annotation of src/sys/uvm/uvm_pdpolicy_clockpro.c, Revision 1.23
1.23 ! ad 1: /* $NetBSD: uvm_pdpolicy_clockpro.c,v 1.22 2019/12/31 22:42:51 ad Exp $ */
1.2 yamt 2:
3: /*-
4: * Copyright (c)2005, 2006 YAMAMOTO Takashi,
5: * All rights reserved.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: * 1. Redistributions of source code must retain the above copyright
11: * notice, this list of conditions and the following disclaimer.
12: * 2. Redistributions in binary form must reproduce the above copyright
13: * notice, this list of conditions and the following disclaimer in the
14: * documentation and/or other materials provided with the distribution.
15: *
16: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26: * SUCH DAMAGE.
27: */
28:
29: /*
30: * CLOCK-Pro replacement policy:
31: * http://www.cs.wm.edu/hpcs/WWW/HTML/publications/abs05-3.html
32: *
33: * approximation of the list of non-resident pages using hash:
34: * http://linux-mm.org/ClockProApproximation
35: */
36:
37: /* #define CLOCKPRO_DEBUG */
38:
39: #if defined(PDSIM)
40:
41: #include "pdsim.h"
42:
43: #else /* defined(PDSIM) */
44:
45: #include <sys/cdefs.h>
1.23 ! ad 46: __KERNEL_RCSID(0, "$NetBSD: uvm_pdpolicy_clockpro.c,v 1.22 2019/12/31 22:42:51 ad Exp $");
1.2 yamt 47:
48: #include "opt_ddb.h"
49:
50: #include <sys/param.h>
51: #include <sys/proc.h>
52: #include <sys/systm.h>
53: #include <sys/kernel.h>
54: #include <sys/hash.h>
55:
56: #include <uvm/uvm.h>
1.17 yamt 57: #include <uvm/uvm_pdaemon.h> /* for uvmpd_trylockowner */
1.2 yamt 58: #include <uvm/uvm_pdpolicy.h>
59: #include <uvm/uvm_pdpolicy_impl.h>
60:
61: #if ((__STDC_VERSION__ - 0) >= 199901L)
62: #define DPRINTF(...) /* nothing */
63: #define WARN(...) printf(__VA_ARGS__)
64: #else /* ((__STDC_VERSION__ - 0) >= 199901L) */
65: #define DPRINTF(a...) /* nothing */ /* GCC */
66: #define WARN(a...) printf(a)
67: #endif /* ((__STDC_VERSION__ - 0) >= 199901L) */
68:
69: #define dump(a) /* nothing */
70:
71: #undef USEONCE2
72: #define LISTQ
73: #undef ADAPTIVE
74:
75: #endif /* defined(PDSIM) */
76:
77: #if !defined(CLOCKPRO_COLDPCT)
78: #define CLOCKPRO_COLDPCT 10
79: #endif /* !defined(CLOCKPRO_COLDPCT) */
80:
81: #define CLOCKPRO_COLDPCTMAX 90
82:
83: #if !defined(CLOCKPRO_HASHFACTOR)
84: #define CLOCKPRO_HASHFACTOR 2
85: #endif /* !defined(CLOCKPRO_HASHFACTOR) */
86:
87: #define CLOCKPRO_NEWQMIN ((1024 * 1024) >> PAGE_SHIFT) /* XXX */
88:
89: int clockpro_hashfactor = CLOCKPRO_HASHFACTOR;
90:
91: PDPOL_EVCNT_DEFINE(nresrecordobj)
92: PDPOL_EVCNT_DEFINE(nresrecordanon)
1.9 yamt 93: PDPOL_EVCNT_DEFINE(nreslookupobj)
94: PDPOL_EVCNT_DEFINE(nreslookupanon)
1.2 yamt 95: PDPOL_EVCNT_DEFINE(nresfoundobj)
96: PDPOL_EVCNT_DEFINE(nresfoundanon)
97: PDPOL_EVCNT_DEFINE(nresanonfree)
98: PDPOL_EVCNT_DEFINE(nresconflict)
99: PDPOL_EVCNT_DEFINE(nresoverwritten)
100: PDPOL_EVCNT_DEFINE(nreshandhot)
101:
102: PDPOL_EVCNT_DEFINE(hhottakeover)
103: PDPOL_EVCNT_DEFINE(hhotref)
104: PDPOL_EVCNT_DEFINE(hhotunref)
105: PDPOL_EVCNT_DEFINE(hhotcold)
106: PDPOL_EVCNT_DEFINE(hhotcoldtest)
107:
108: PDPOL_EVCNT_DEFINE(hcoldtakeover)
109: PDPOL_EVCNT_DEFINE(hcoldref)
110: PDPOL_EVCNT_DEFINE(hcoldunref)
111: PDPOL_EVCNT_DEFINE(hcoldreftest)
112: PDPOL_EVCNT_DEFINE(hcoldunreftest)
113: PDPOL_EVCNT_DEFINE(hcoldunreftestspeculative)
114: PDPOL_EVCNT_DEFINE(hcoldhot)
115:
116: PDPOL_EVCNT_DEFINE(speculativeenqueue)
117: PDPOL_EVCNT_DEFINE(speculativehit1)
118: PDPOL_EVCNT_DEFINE(speculativehit2)
119: PDPOL_EVCNT_DEFINE(speculativemiss)
120:
1.17 yamt 121: PDPOL_EVCNT_DEFINE(locksuccess)
122: PDPOL_EVCNT_DEFINE(lockfail)
123:
1.22 ad 124: #define PQ_REFERENCED 0x000000010
125: #define PQ_HOT 0x000000020
126: #define PQ_TEST 0x000000040
127: #define PQ_INITIALREF 0x000000080
128: #define PQ_QMASK 0x000000700
129: #define PQ_QFACTOR 0x000000100
130: #define PQ_SPECULATIVE 0x000000800
1.2 yamt 131:
132: #define CLOCKPRO_NOQUEUE 0
133: #define CLOCKPRO_NEWQ 1 /* small queue to clear initial ref. */
134: #if defined(LISTQ)
135: #define CLOCKPRO_COLDQ 2
136: #define CLOCKPRO_HOTQ 3
137: #else /* defined(LISTQ) */
138: #define CLOCKPRO_COLDQ (2 + coldqidx) /* XXX */
139: #define CLOCKPRO_HOTQ (3 - coldqidx) /* XXX */
140: #endif /* defined(LISTQ) */
141: #define CLOCKPRO_LISTQ 4
142: #define CLOCKPRO_NQUEUE 4
143:
1.22 ad 144: static bool uvmpdpol_pagerealize_locked(struct vm_page *);
145:
1.2 yamt 146: static inline void
147: clockpro_setq(struct vm_page *pg, int qidx)
148: {
149: KASSERT(qidx >= CLOCKPRO_NOQUEUE);
150: KASSERT(qidx <= CLOCKPRO_NQUEUE);
151:
152: pg->pqflags = (pg->pqflags & ~PQ_QMASK) | (qidx * PQ_QFACTOR);
153: }
154:
155: static inline int
156: clockpro_getq(struct vm_page *pg)
157: {
158: int qidx;
159:
160: qidx = (pg->pqflags & PQ_QMASK) / PQ_QFACTOR;
161: KASSERT(qidx >= CLOCKPRO_NOQUEUE);
162: KASSERT(qidx <= CLOCKPRO_NQUEUE);
163: return qidx;
164: }
165:
166: typedef struct {
167: struct pglist q_q;
168: int q_len;
169: } pageq_t;
170:
171: struct clockpro_state {
1.18 ad 172: kmutex_t lock;
1.2 yamt 173: int s_npages;
174: int s_coldtarget;
175: int s_ncold;
176:
177: int s_newqlenmax;
178: pageq_t s_q[CLOCKPRO_NQUEUE];
179:
180: struct uvm_pctparam s_coldtargetpct;
181: };
182:
183: static pageq_t *
184: clockpro_queue(struct clockpro_state *s, int qidx)
185: {
186:
187: KASSERT(CLOCKPRO_NOQUEUE < qidx);
188: KASSERT(qidx <= CLOCKPRO_NQUEUE);
189:
190: return &s->s_q[qidx - 1];
191: }
192:
193: #if !defined(LISTQ)
194:
195: static int coldqidx;
196:
197: static void
198: clockpro_switchqueue(void)
199: {
200:
201: coldqidx = 1 - coldqidx;
202: }
203:
204: #endif /* !defined(LISTQ) */
205:
1.18 ad 206: static struct clockpro_state clockpro __cacheline_aligned;
1.2 yamt 207: static struct clockpro_scanstate {
208: int ss_nscanned;
209: } scanstate;
210:
211: /* ---------------------------------------- */
212:
213: static void
214: pageq_init(pageq_t *q)
215: {
216:
217: TAILQ_INIT(&q->q_q);
218: q->q_len = 0;
219: }
220:
221: static int
222: pageq_len(const pageq_t *q)
223: {
224:
225: return q->q_len;
226: }
227:
228: static struct vm_page *
229: pageq_first(const pageq_t *q)
230: {
231:
232: return TAILQ_FIRST(&q->q_q);
233: }
234:
235: static void
236: pageq_insert_tail(pageq_t *q, struct vm_page *pg)
237: {
238:
1.19 ad 239: TAILQ_INSERT_TAIL(&q->q_q, pg, pdqueue);
1.2 yamt 240: q->q_len++;
241: }
242:
1.14 bjs 243: #if defined(LISTQ)
1.2 yamt 244: static void
245: pageq_insert_head(pageq_t *q, struct vm_page *pg)
246: {
247:
1.19 ad 248: TAILQ_INSERT_HEAD(&q->q_q, pg, pdqueue);
1.2 yamt 249: q->q_len++;
250: }
1.14 bjs 251: #endif
1.2 yamt 252:
253: static void
254: pageq_remove(pageq_t *q, struct vm_page *pg)
255: {
256:
257: #if 1
258: KASSERT(clockpro_queue(&clockpro, clockpro_getq(pg)) == q);
259: #endif
260: KASSERT(q->q_len > 0);
1.19 ad 261: TAILQ_REMOVE(&q->q_q, pg, pdqueue);
1.2 yamt 262: q->q_len--;
263: }
264:
265: static struct vm_page *
266: pageq_remove_head(pageq_t *q)
267: {
268: struct vm_page *pg;
269:
270: pg = TAILQ_FIRST(&q->q_q);
271: if (pg == NULL) {
272: KASSERT(q->q_len == 0);
273: return NULL;
274: }
275: pageq_remove(q, pg);
276: return pg;
277: }
278:
279: /* ---------------------------------------- */
280:
281: static void
282: clockpro_insert_tail(struct clockpro_state *s, int qidx, struct vm_page *pg)
283: {
284: pageq_t *q = clockpro_queue(s, qidx);
285:
286: clockpro_setq(pg, qidx);
287: pageq_insert_tail(q, pg);
288: }
289:
1.14 bjs 290: #if defined(LISTQ)
1.5 christos 291: static void
1.2 yamt 292: clockpro_insert_head(struct clockpro_state *s, int qidx, struct vm_page *pg)
293: {
294: pageq_t *q = clockpro_queue(s, qidx);
295:
296: clockpro_setq(pg, qidx);
297: pageq_insert_head(q, pg);
298: }
299:
1.14 bjs 300: #endif
1.2 yamt 301: /* ---------------------------------------- */
302:
303: typedef uint32_t nonres_cookie_t;
304: #define NONRES_COOKIE_INVAL 0
305:
306: typedef uintptr_t objid_t;
307:
308: /*
309: * XXX maybe these hash functions need reconsideration,
310: * given that hash distribution is critical here.
311: */
312:
313: static uint32_t
314: pageidentityhash1(objid_t obj, off_t idx)
315: {
316: uint32_t hash = HASH32_BUF_INIT;
317:
318: #if 1
319: hash = hash32_buf(&idx, sizeof(idx), hash);
320: hash = hash32_buf(&obj, sizeof(obj), hash);
321: #else
322: hash = hash32_buf(&obj, sizeof(obj), hash);
323: hash = hash32_buf(&idx, sizeof(idx), hash);
324: #endif
325: return hash;
326: }
327:
328: static uint32_t
329: pageidentityhash2(objid_t obj, off_t idx)
330: {
331: uint32_t hash = HASH32_BUF_INIT;
332:
333: hash = hash32_buf(&obj, sizeof(obj), hash);
334: hash = hash32_buf(&idx, sizeof(idx), hash);
335: return hash;
336: }
337:
338: static nonres_cookie_t
339: calccookie(objid_t obj, off_t idx)
340: {
341: uint32_t hash = pageidentityhash2(obj, idx);
342: nonres_cookie_t cookie = hash;
343:
344: if (__predict_false(cookie == NONRES_COOKIE_INVAL)) {
345: cookie++; /* XXX */
346: }
347: return cookie;
348: }
349:
350: #define BUCKETSIZE 14
351: struct bucket {
352: int cycle;
353: int cur;
354: nonres_cookie_t pages[BUCKETSIZE];
355: };
356: static int cycle_target;
357: static int cycle_target_frac;
358:
359: static struct bucket static_bucket;
360: static struct bucket *buckets = &static_bucket;
361: static size_t hashsize = 1;
362:
363: static int coldadj;
364: #define COLDTARGET_ADJ(d) coldadj += (d)
365:
366: #if defined(PDSIM)
367:
368: static void *
369: clockpro_hashalloc(int n)
370: {
371: size_t allocsz = sizeof(*buckets) * n;
372:
373: return malloc(allocsz);
374: }
375:
376: static void
377: clockpro_hashfree(void *p, int n)
378: {
379:
380: free(p);
381: }
382:
383: #else /* defined(PDSIM) */
384:
385: static void *
386: clockpro_hashalloc(int n)
387: {
388: size_t allocsz = round_page(sizeof(*buckets) * n);
389:
390: return (void *)uvm_km_alloc(kernel_map, allocsz, 0, UVM_KMF_WIRED);
391: }
392:
393: static void
394: clockpro_hashfree(void *p, int n)
395: {
396: size_t allocsz = round_page(sizeof(*buckets) * n);
397:
398: uvm_km_free(kernel_map, (vaddr_t)p, allocsz, UVM_KMF_WIRED);
399: }
400:
401: #endif /* defined(PDSIM) */
402:
403: static void
404: clockpro_hashinit(uint64_t n)
405: {
406: struct bucket *newbuckets;
407: struct bucket *oldbuckets;
408: size_t sz;
409: size_t oldsz;
410: int i;
411:
412: sz = howmany(n, BUCKETSIZE);
413: sz *= clockpro_hashfactor;
414: newbuckets = clockpro_hashalloc(sz);
415: if (newbuckets == NULL) {
416: panic("%s: allocation failure", __func__);
417: }
418: for (i = 0; i < sz; i++) {
419: struct bucket *b = &newbuckets[i];
420: int j;
421:
422: b->cycle = cycle_target;
423: b->cur = 0;
424: for (j = 0; j < BUCKETSIZE; j++) {
425: b->pages[j] = NONRES_COOKIE_INVAL;
426: }
427: }
428: /* XXX lock */
429: oldbuckets = buckets;
430: oldsz = hashsize;
431: buckets = newbuckets;
432: hashsize = sz;
433: /* XXX unlock */
434: if (oldbuckets != &static_bucket) {
435: clockpro_hashfree(oldbuckets, oldsz);
436: }
437: }
438:
439: static struct bucket *
440: nonresident_getbucket(objid_t obj, off_t idx)
441: {
442: uint32_t hash;
443:
444: hash = pageidentityhash1(obj, idx);
445: return &buckets[hash % hashsize];
446: }
447:
448: static void
449: nonresident_rotate(struct bucket *b)
450: {
1.13 yamt 451: const int target = cycle_target;
452: const int cycle = b->cycle;
1.11 yamt 453: int cur;
1.13 yamt 454: int todo;
1.2 yamt 455:
1.13 yamt 456: todo = target - cycle;
457: if (todo >= BUCKETSIZE * 2) {
458: todo = (todo % BUCKETSIZE) + BUCKETSIZE;
459: }
1.11 yamt 460: cur = b->cur;
1.13 yamt 461: while (todo > 0) {
1.11 yamt 462: if (b->pages[cur] != NONRES_COOKIE_INVAL) {
1.2 yamt 463: PDPOL_EVCNT_INCR(nreshandhot);
464: COLDTARGET_ADJ(-1);
465: }
1.11 yamt 466: b->pages[cur] = NONRES_COOKIE_INVAL;
467: cur++;
468: if (cur == BUCKETSIZE) {
469: cur = 0;
470: }
1.13 yamt 471: todo--;
1.2 yamt 472: }
1.13 yamt 473: b->cycle = target;
1.11 yamt 474: b->cur = cur;
1.2 yamt 475: }
476:
1.7 thorpej 477: static bool
1.2 yamt 478: nonresident_lookupremove(objid_t obj, off_t idx)
479: {
480: struct bucket *b = nonresident_getbucket(obj, idx);
481: nonres_cookie_t cookie = calccookie(obj, idx);
482: int i;
483:
484: nonresident_rotate(b);
485: for (i = 0; i < BUCKETSIZE; i++) {
486: if (b->pages[i] == cookie) {
487: b->pages[i] = NONRES_COOKIE_INVAL;
1.8 thorpej 488: return true;
1.2 yamt 489: }
490: }
1.8 thorpej 491: return false;
1.2 yamt 492: }
493:
494: static objid_t
495: pageobj(struct vm_page *pg)
496: {
497: const void *obj;
498:
499: /*
500: * XXX object pointer is often freed and reused for unrelated object.
501: * for vnodes, it would be better to use something like
502: * a hash of fsid/fileid/generation.
503: */
504:
505: obj = pg->uobject;
506: if (obj == NULL) {
507: obj = pg->uanon;
508: KASSERT(obj != NULL);
509: }
510: return (objid_t)obj;
511: }
512:
513: static off_t
514: pageidx(struct vm_page *pg)
515: {
516:
517: KASSERT((pg->offset & PAGE_MASK) == 0);
518: return pg->offset >> PAGE_SHIFT;
519: }
520:
1.7 thorpej 521: static bool
1.2 yamt 522: nonresident_pagelookupremove(struct vm_page *pg)
523: {
1.7 thorpej 524: bool found = nonresident_lookupremove(pageobj(pg), pageidx(pg));
1.2 yamt 525:
1.9 yamt 526: if (pg->uobject) {
527: PDPOL_EVCNT_INCR(nreslookupobj);
528: } else {
529: PDPOL_EVCNT_INCR(nreslookupanon);
530: }
1.2 yamt 531: if (found) {
532: if (pg->uobject) {
533: PDPOL_EVCNT_INCR(nresfoundobj);
534: } else {
535: PDPOL_EVCNT_INCR(nresfoundanon);
536: }
537: }
538: return found;
539: }
540:
541: static void
542: nonresident_pagerecord(struct vm_page *pg)
543: {
544: objid_t obj = pageobj(pg);
545: off_t idx = pageidx(pg);
546: struct bucket *b = nonresident_getbucket(obj, idx);
547: nonres_cookie_t cookie = calccookie(obj, idx);
548:
549: #if defined(DEBUG)
550: int i;
551:
552: for (i = 0; i < BUCKETSIZE; i++) {
553: if (b->pages[i] == cookie) {
554: PDPOL_EVCNT_INCR(nresconflict);
555: }
556: }
557: #endif /* defined(DEBUG) */
558:
559: if (pg->uobject) {
560: PDPOL_EVCNT_INCR(nresrecordobj);
561: } else {
562: PDPOL_EVCNT_INCR(nresrecordanon);
563: }
564: nonresident_rotate(b);
565: if (b->pages[b->cur] != NONRES_COOKIE_INVAL) {
566: PDPOL_EVCNT_INCR(nresoverwritten);
567: COLDTARGET_ADJ(-1);
568: }
569: b->pages[b->cur] = cookie;
570: b->cur = (b->cur + 1) % BUCKETSIZE;
571: }
572:
573: /* ---------------------------------------- */
574:
575: #if defined(CLOCKPRO_DEBUG)
576: static void
577: check_sanity(void)
578: {
579: }
580: #else /* defined(CLOCKPRO_DEBUG) */
581: #define check_sanity() /* nothing */
582: #endif /* defined(CLOCKPRO_DEBUG) */
583:
584: static void
585: clockpro_reinit(void)
586: {
587:
1.18 ad 588: KASSERT(mutex_owned(&clockpro.lock));
589:
1.2 yamt 590: clockpro_hashinit(uvmexp.npages);
591: }
592:
593: static void
594: clockpro_init(void)
595: {
596: struct clockpro_state *s = &clockpro;
597: int i;
598:
1.18 ad 599: mutex_init(&s->lock, MUTEX_DEFAULT, IPL_NONE);
1.2 yamt 600: for (i = 0; i < CLOCKPRO_NQUEUE; i++) {
601: pageq_init(&s->s_q[i]);
602: }
603: s->s_newqlenmax = 1;
604: s->s_coldtarget = 1;
605: uvm_pctparam_init(&s->s_coldtargetpct, CLOCKPRO_COLDPCT, NULL);
606: }
607:
608: static void
609: clockpro_tune(void)
610: {
611: struct clockpro_state *s = &clockpro;
612: int coldtarget;
613:
1.18 ad 614: KASSERT(mutex_owned(&s->lock));
615:
1.2 yamt 616: #if defined(ADAPTIVE)
617: int coldmax = s->s_npages * CLOCKPRO_COLDPCTMAX / 100;
618: int coldmin = 1;
619:
620: coldtarget = s->s_coldtarget;
621: if (coldtarget + coldadj < coldmin) {
622: coldadj = coldmin - coldtarget;
623: } else if (coldtarget + coldadj > coldmax) {
624: coldadj = coldmax - coldtarget;
625: }
626: coldtarget += coldadj;
627: #else /* defined(ADAPTIVE) */
628: coldtarget = UVM_PCTPARAM_APPLY(&s->s_coldtargetpct, s->s_npages);
629: if (coldtarget < 1) {
630: coldtarget = 1;
631: }
632: #endif /* defined(ADAPTIVE) */
633:
634: s->s_coldtarget = coldtarget;
635: s->s_newqlenmax = coldtarget / 4;
636: if (s->s_newqlenmax < CLOCKPRO_NEWQMIN) {
637: s->s_newqlenmax = CLOCKPRO_NEWQMIN;
638: }
639: }
640:
641: static void
1.17 yamt 642: clockpro_movereferencebit(struct vm_page *pg, bool locked)
1.2 yamt 643: {
1.17 yamt 644: kmutex_t *lock;
1.7 thorpej 645: bool referenced;
1.2 yamt 646:
1.18 ad 647: KASSERT(mutex_owned(&clockpro.lock));
1.21 ad 648: KASSERT(!locked || uvm_page_owner_locked_p(pg));
1.17 yamt 649: if (!locked) {
1.18 ad 650: /*
651: * acquire interlock to stablize page identity.
652: * if we have caught the page in a state of flux
653: * and it should be dequeued, abort. it will be
654: * dequeued later.
655: */
656: mutex_enter(&pg->interlock);
657: if ((pg->uobject == NULL && pg->uanon == NULL) ||
658: pg->wire_count > 0) {
659: mutex_exit(&pg->interlock);
660: PDPOL_EVCNT_INCR(lockfail);
661: return;
662: }
663: mutex_exit(&clockpro.lock); /* XXX */
1.17 yamt 664: lock = uvmpd_trylockowner(pg);
1.18 ad 665: /* pg->interlock now dropped */
666: mutex_enter(&clockpro.lock); /* XXX */
1.17 yamt 667: if (lock == NULL) {
668: /*
669: * XXXuvmplock
670: */
671: PDPOL_EVCNT_INCR(lockfail);
672: return;
673: }
674: PDPOL_EVCNT_INCR(locksuccess);
675: }
1.2 yamt 676: referenced = pmap_clear_reference(pg);
1.17 yamt 677: if (!locked) {
678: mutex_exit(lock);
679: }
1.2 yamt 680: if (referenced) {
681: pg->pqflags |= PQ_REFERENCED;
682: }
683: }
684:
685: static void
1.17 yamt 686: clockpro_clearreferencebit(struct vm_page *pg, bool locked)
1.2 yamt 687: {
688:
1.18 ad 689: KASSERT(mutex_owned(&clockpro.lock));
690:
1.17 yamt 691: clockpro_movereferencebit(pg, locked);
1.2 yamt 692: pg->pqflags &= ~PQ_REFERENCED;
693: }
694:
695: static void
696: clockpro___newqrotate(int len)
697: {
698: struct clockpro_state * const s = &clockpro;
699: pageq_t * const newq = clockpro_queue(s, CLOCKPRO_NEWQ);
700: struct vm_page *pg;
701:
1.18 ad 702: KASSERT(mutex_owned(&s->lock));
703:
1.2 yamt 704: while (pageq_len(newq) > len) {
705: pg = pageq_remove_head(newq);
706: KASSERT(pg != NULL);
707: KASSERT(clockpro_getq(pg) == CLOCKPRO_NEWQ);
708: if ((pg->pqflags & PQ_INITIALREF) != 0) {
1.17 yamt 709: clockpro_clearreferencebit(pg, false);
1.2 yamt 710: pg->pqflags &= ~PQ_INITIALREF;
711: }
712: /* place at the list head */
713: clockpro_insert_tail(s, CLOCKPRO_COLDQ, pg);
714: }
715: }
716:
717: static void
718: clockpro_newqrotate(void)
719: {
720: struct clockpro_state * const s = &clockpro;
721:
1.18 ad 722: KASSERT(mutex_owned(&s->lock));
723:
1.2 yamt 724: check_sanity();
725: clockpro___newqrotate(s->s_newqlenmax);
726: check_sanity();
727: }
728:
729: static void
730: clockpro_newqflush(int n)
731: {
732:
1.18 ad 733: KASSERT(mutex_owned(&clockpro.lock));
734:
1.2 yamt 735: check_sanity();
736: clockpro___newqrotate(n);
737: check_sanity();
738: }
739:
740: static void
741: clockpro_newqflushone(void)
742: {
743: struct clockpro_state * const s = &clockpro;
744:
1.18 ad 745: KASSERT(mutex_owned(&s->lock));
746:
1.2 yamt 747: clockpro_newqflush(
748: MAX(pageq_len(clockpro_queue(s, CLOCKPRO_NEWQ)) - 1, 0));
749: }
750:
751: /*
752: * our "tail" is called "list-head" in the paper.
753: */
754:
755: static void
756: clockpro___enqueuetail(struct vm_page *pg)
757: {
758: struct clockpro_state * const s = &clockpro;
759:
1.18 ad 760: KASSERT(mutex_owned(&s->lock));
1.2 yamt 761: KASSERT(clockpro_getq(pg) == CLOCKPRO_NOQUEUE);
762:
763: check_sanity();
764: #if !defined(USEONCE2)
765: clockpro_insert_tail(s, CLOCKPRO_NEWQ, pg);
766: clockpro_newqrotate();
767: #else /* !defined(USEONCE2) */
768: #if defined(LISTQ)
769: KASSERT((pg->pqflags & PQ_REFERENCED) == 0);
770: #endif /* defined(LISTQ) */
771: clockpro_insert_tail(s, CLOCKPRO_COLDQ, pg);
772: #endif /* !defined(USEONCE2) */
773: check_sanity();
774: }
775:
776: static void
777: clockpro_pageenqueue(struct vm_page *pg)
778: {
779: struct clockpro_state * const s = &clockpro;
1.7 thorpej 780: bool hot;
781: bool speculative = (pg->pqflags & PQ_SPECULATIVE) != 0; /* XXX */
1.2 yamt 782:
783: KASSERT((~pg->pqflags & (PQ_INITIALREF|PQ_SPECULATIVE)) != 0);
1.18 ad 784: KASSERT(mutex_owned(&s->lock));
1.2 yamt 785: check_sanity();
786: KASSERT(clockpro_getq(pg) == CLOCKPRO_NOQUEUE);
787: s->s_npages++;
788: pg->pqflags &= ~(PQ_HOT|PQ_TEST);
789: if (speculative) {
1.8 thorpej 790: hot = false;
1.2 yamt 791: PDPOL_EVCNT_INCR(speculativeenqueue);
792: } else {
793: hot = nonresident_pagelookupremove(pg);
794: if (hot) {
795: COLDTARGET_ADJ(1);
796: }
797: }
798:
799: /*
800: * consider mmap'ed file:
801: *
802: * - read-ahead enqueues a page.
803: *
804: * - on the following read-ahead hit, the fault handler activates it.
805: *
806: * - finally, the userland code which caused the above fault
807: * actually accesses the page. it makes its reference bit set.
808: *
809: * we want to count the above as a single access, rather than
810: * three accesses with short reuse distances.
811: */
812:
813: #if defined(USEONCE2)
814: pg->pqflags &= ~PQ_INITIALREF;
815: if (hot) {
816: pg->pqflags |= PQ_TEST;
817: }
818: s->s_ncold++;
1.17 yamt 819: clockpro_clearreferencebit(pg, false);
1.2 yamt 820: clockpro___enqueuetail(pg);
821: #else /* defined(USEONCE2) */
822: if (speculative) {
823: s->s_ncold++;
824: } else if (hot) {
825: pg->pqflags |= PQ_HOT;
826: } else {
827: pg->pqflags |= PQ_TEST;
828: s->s_ncold++;
829: }
830: clockpro___enqueuetail(pg);
831: #endif /* defined(USEONCE2) */
832: KASSERT(s->s_ncold <= s->s_npages);
833: }
834:
835: static pageq_t *
836: clockpro_pagequeue(struct vm_page *pg)
837: {
838: struct clockpro_state * const s = &clockpro;
839: int qidx;
840:
1.18 ad 841: KASSERT(mutex_owned(&s->lock));
842:
1.2 yamt 843: qidx = clockpro_getq(pg);
844: KASSERT(qidx != CLOCKPRO_NOQUEUE);
845:
846: return clockpro_queue(s, qidx);
847: }
848:
849: static void
850: clockpro_pagedequeue(struct vm_page *pg)
851: {
852: struct clockpro_state * const s = &clockpro;
853: pageq_t *q;
854:
1.18 ad 855: KASSERT(mutex_owned(&s->lock));
856:
1.2 yamt 857: KASSERT(s->s_npages > 0);
858: check_sanity();
859: q = clockpro_pagequeue(pg);
860: pageq_remove(q, pg);
861: check_sanity();
862: clockpro_setq(pg, CLOCKPRO_NOQUEUE);
863: if ((pg->pqflags & PQ_HOT) == 0) {
864: KASSERT(s->s_ncold > 0);
865: s->s_ncold--;
866: }
867: KASSERT(s->s_npages > 0);
868: s->s_npages--;
869: check_sanity();
870: }
871:
872: static void
873: clockpro_pagerequeue(struct vm_page *pg)
874: {
875: struct clockpro_state * const s = &clockpro;
876: int qidx;
877:
1.18 ad 878: KASSERT(mutex_owned(&s->lock));
879:
1.2 yamt 880: qidx = clockpro_getq(pg);
881: KASSERT(qidx == CLOCKPRO_HOTQ || qidx == CLOCKPRO_COLDQ);
882: pageq_remove(clockpro_queue(s, qidx), pg);
883: check_sanity();
884: clockpro_setq(pg, CLOCKPRO_NOQUEUE);
885:
886: clockpro___enqueuetail(pg);
887: }
888:
889: static void
890: handhot_endtest(struct vm_page *pg)
891: {
892:
1.18 ad 893: KASSERT(mutex_owned(&clockpro.lock));
894:
1.2 yamt 895: KASSERT((pg->pqflags & PQ_HOT) == 0);
896: if ((pg->pqflags & PQ_TEST) != 0) {
897: PDPOL_EVCNT_INCR(hhotcoldtest);
898: COLDTARGET_ADJ(-1);
899: pg->pqflags &= ~PQ_TEST;
900: } else {
901: PDPOL_EVCNT_INCR(hhotcold);
902: }
903: }
904:
905: static void
906: handhot_advance(void)
907: {
908: struct clockpro_state * const s = &clockpro;
909: struct vm_page *pg;
910: pageq_t *hotq;
911: int hotqlen;
912:
1.18 ad 913: KASSERT(mutex_owned(&s->lock));
914:
1.2 yamt 915: clockpro_tune();
916:
917: dump("hot called");
918: if (s->s_ncold >= s->s_coldtarget) {
919: return;
920: }
921: hotq = clockpro_queue(s, CLOCKPRO_HOTQ);
922: again:
923: pg = pageq_first(hotq);
924: if (pg == NULL) {
925: DPRINTF("%s: HHOT TAKEOVER\n", __func__);
926: dump("hhottakeover");
927: PDPOL_EVCNT_INCR(hhottakeover);
928: #if defined(LISTQ)
929: while (/* CONSTCOND */ 1) {
930: pageq_t *coldq = clockpro_queue(s, CLOCKPRO_COLDQ);
931:
932: pg = pageq_first(coldq);
933: if (pg == NULL) {
934: clockpro_newqflushone();
935: pg = pageq_first(coldq);
936: if (pg == NULL) {
937: WARN("hhot: no page?\n");
938: return;
939: }
940: }
941: KASSERT(clockpro_pagequeue(pg) == coldq);
942: pageq_remove(coldq, pg);
943: check_sanity();
944: if ((pg->pqflags & PQ_HOT) == 0) {
945: handhot_endtest(pg);
946: clockpro_insert_tail(s, CLOCKPRO_LISTQ, pg);
947: } else {
948: clockpro_insert_head(s, CLOCKPRO_HOTQ, pg);
949: break;
950: }
951: }
952: #else /* defined(LISTQ) */
953: clockpro_newqflush(0); /* XXX XXX */
954: clockpro_switchqueue();
955: hotq = clockpro_queue(s, CLOCKPRO_HOTQ);
956: goto again;
957: #endif /* defined(LISTQ) */
958: }
959:
960: KASSERT(clockpro_pagequeue(pg) == hotq);
961:
962: /*
963: * terminate test period of nonresident pages by cycling them.
964: */
965:
966: cycle_target_frac += BUCKETSIZE;
967: hotqlen = pageq_len(hotq);
968: while (cycle_target_frac >= hotqlen) {
969: cycle_target++;
970: cycle_target_frac -= hotqlen;
971: }
972:
973: if ((pg->pqflags & PQ_HOT) == 0) {
974: #if defined(LISTQ)
975: panic("cold page in hotq: %p", pg);
976: #else /* defined(LISTQ) */
977: handhot_endtest(pg);
978: goto next;
979: #endif /* defined(LISTQ) */
980: }
981: KASSERT((pg->pqflags & PQ_TEST) == 0);
982: KASSERT((pg->pqflags & PQ_INITIALREF) == 0);
983: KASSERT((pg->pqflags & PQ_SPECULATIVE) == 0);
984:
985: /*
986: * once we met our target,
987: * stop at a hot page so that no cold pages in test period
988: * have larger recency than any hot pages.
989: */
990:
991: if (s->s_ncold >= s->s_coldtarget) {
992: dump("hot done");
993: return;
994: }
1.17 yamt 995: clockpro_movereferencebit(pg, false);
1.2 yamt 996: if ((pg->pqflags & PQ_REFERENCED) == 0) {
997: PDPOL_EVCNT_INCR(hhotunref);
998: uvmexp.pddeact++;
999: pg->pqflags &= ~PQ_HOT;
1000: clockpro.s_ncold++;
1001: KASSERT(s->s_ncold <= s->s_npages);
1002: } else {
1003: PDPOL_EVCNT_INCR(hhotref);
1004: }
1005: pg->pqflags &= ~PQ_REFERENCED;
1006: #if !defined(LISTQ)
1007: next:
1008: #endif /* !defined(LISTQ) */
1009: clockpro_pagerequeue(pg);
1010: dump("hot");
1011: goto again;
1012: }
1013:
1014: static struct vm_page *
1015: handcold_advance(void)
1016: {
1017: struct clockpro_state * const s = &clockpro;
1018: struct vm_page *pg;
1019:
1.18 ad 1020: KASSERT(mutex_owned(&s->lock));
1021:
1.2 yamt 1022: for (;;) {
1.3 yamt 1023: #if defined(LISTQ)
1.2 yamt 1024: pageq_t *listq = clockpro_queue(s, CLOCKPRO_LISTQ);
1.3 yamt 1025: #endif /* defined(LISTQ) */
1.2 yamt 1026: pageq_t *coldq;
1027:
1028: clockpro_newqrotate();
1029: handhot_advance();
1030: #if defined(LISTQ)
1031: pg = pageq_first(listq);
1032: if (pg != NULL) {
1033: KASSERT(clockpro_getq(pg) == CLOCKPRO_LISTQ);
1034: KASSERT((pg->pqflags & PQ_TEST) == 0);
1035: KASSERT((pg->pqflags & PQ_HOT) == 0);
1036: KASSERT((pg->pqflags & PQ_INITIALREF) == 0);
1037: pageq_remove(listq, pg);
1038: check_sanity();
1039: clockpro_insert_head(s, CLOCKPRO_COLDQ, pg); /* XXX */
1040: goto gotcold;
1041: }
1042: #endif /* defined(LISTQ) */
1043: check_sanity();
1044: coldq = clockpro_queue(s, CLOCKPRO_COLDQ);
1045: pg = pageq_first(coldq);
1046: if (pg == NULL) {
1047: clockpro_newqflushone();
1048: pg = pageq_first(coldq);
1049: }
1050: if (pg == NULL) {
1051: DPRINTF("%s: HCOLD TAKEOVER\n", __func__);
1052: dump("hcoldtakeover");
1053: PDPOL_EVCNT_INCR(hcoldtakeover);
1054: KASSERT(
1055: pageq_len(clockpro_queue(s, CLOCKPRO_NEWQ)) == 0);
1056: #if defined(LISTQ)
1057: KASSERT(
1058: pageq_len(clockpro_queue(s, CLOCKPRO_HOTQ)) == 0);
1059: #else /* defined(LISTQ) */
1060: clockpro_switchqueue();
1061: coldq = clockpro_queue(s, CLOCKPRO_COLDQ);
1062: pg = pageq_first(coldq);
1063: #endif /* defined(LISTQ) */
1064: }
1065: if (pg == NULL) {
1066: WARN("hcold: no page?\n");
1067: return NULL;
1068: }
1069: KASSERT((pg->pqflags & PQ_INITIALREF) == 0);
1070: if ((pg->pqflags & PQ_HOT) != 0) {
1071: PDPOL_EVCNT_INCR(hcoldhot);
1072: pageq_remove(coldq, pg);
1073: clockpro_insert_tail(s, CLOCKPRO_HOTQ, pg);
1074: check_sanity();
1075: KASSERT((pg->pqflags & PQ_TEST) == 0);
1076: uvmexp.pdscans++;
1077: continue;
1078: }
1079: #if defined(LISTQ)
1080: gotcold:
1081: #endif /* defined(LISTQ) */
1082: KASSERT((pg->pqflags & PQ_HOT) == 0);
1083: uvmexp.pdscans++;
1.17 yamt 1084: clockpro_movereferencebit(pg, false);
1.2 yamt 1085: if ((pg->pqflags & PQ_SPECULATIVE) != 0) {
1086: KASSERT((pg->pqflags & PQ_TEST) == 0);
1087: if ((pg->pqflags & PQ_REFERENCED) != 0) {
1088: PDPOL_EVCNT_INCR(speculativehit2);
1089: pg->pqflags &= ~(PQ_SPECULATIVE|PQ_REFERENCED);
1090: clockpro_pagedequeue(pg);
1091: clockpro_pageenqueue(pg);
1092: continue;
1093: }
1094: PDPOL_EVCNT_INCR(speculativemiss);
1095: }
1096: switch (pg->pqflags & (PQ_REFERENCED|PQ_TEST)) {
1097: case PQ_TEST:
1098: PDPOL_EVCNT_INCR(hcoldunreftest);
1099: nonresident_pagerecord(pg);
1100: goto gotit;
1101: case 0:
1102: PDPOL_EVCNT_INCR(hcoldunref);
1103: gotit:
1104: KASSERT(s->s_ncold > 0);
1105: clockpro_pagerequeue(pg); /* XXX */
1106: dump("cold done");
1107: /* XXX "pg" is still in queue */
1108: handhot_advance();
1109: goto done;
1110:
1111: case PQ_REFERENCED|PQ_TEST:
1112: PDPOL_EVCNT_INCR(hcoldreftest);
1113: s->s_ncold--;
1114: COLDTARGET_ADJ(1);
1115: pg->pqflags |= PQ_HOT;
1116: pg->pqflags &= ~PQ_TEST;
1117: break;
1118:
1119: case PQ_REFERENCED:
1120: PDPOL_EVCNT_INCR(hcoldref);
1121: pg->pqflags |= PQ_TEST;
1122: break;
1123: }
1124: pg->pqflags &= ~PQ_REFERENCED;
1125: uvmexp.pdreact++;
1126: /* move to the list head */
1127: clockpro_pagerequeue(pg);
1128: dump("cold");
1129: }
1130: done:;
1131: return pg;
1132: }
1133:
1.22 ad 1134: static void
1135: uvmpdpol_pageactivate_locked(struct vm_page *pg)
1.2 yamt 1136: {
1137:
1138: if (!uvmpdpol_pageisqueued_p(pg)) {
1139: KASSERT((pg->pqflags & PQ_SPECULATIVE) == 0);
1140: pg->pqflags |= PQ_INITIALREF;
1141: clockpro_pageenqueue(pg);
1142: } else if ((pg->pqflags & PQ_SPECULATIVE)) {
1143: PDPOL_EVCNT_INCR(speculativehit1);
1144: pg->pqflags &= ~PQ_SPECULATIVE;
1145: pg->pqflags |= PQ_INITIALREF;
1146: clockpro_pagedequeue(pg);
1147: clockpro_pageenqueue(pg);
1148: }
1149: pg->pqflags |= PQ_REFERENCED;
1150: }
1151:
1152: void
1.22 ad 1153: uvmpdpol_pageactivate(struct vm_page *pg)
1154: {
1155:
1156: uvmpdpol_set_intent(pg, PQ_INTENT_A);
1157: }
1158:
1159: static void
1160: uvmpdpol_pagedeactivate_locked(struct vm_page *pg)
1.2 yamt 1161: {
1162:
1.17 yamt 1163: clockpro_clearreferencebit(pg, true);
1.2 yamt 1164: }
1165:
1166: void
1.22 ad 1167: uvmpdpol_pagedeactivate(struct vm_page *pg)
1168: {
1169:
1170: uvmpdpol_set_intent(pg, PQ_INTENT_I);
1171: }
1172:
1173: static void
1174: uvmpdpol_pagedequeue_locked(struct vm_page *pg)
1.2 yamt 1175: {
1176:
1177: if (!uvmpdpol_pageisqueued_p(pg)) {
1178: return;
1179: }
1180: clockpro_pagedequeue(pg);
1.6 yamt 1181: pg->pqflags &= ~(PQ_INITIALREF|PQ_SPECULATIVE);
1.2 yamt 1182: }
1183:
1184: void
1.22 ad 1185: uvmpdpol_pagedequeue(struct vm_page *pg)
1186: {
1187:
1188: uvmpdpol_set_intent(pg, PQ_INTENT_D);
1189: }
1190:
1191: static void
1192: uvmpdpol_pageenqueue_locked(struct vm_page *pg)
1.2 yamt 1193: {
1194:
1195: #if 1
1196: if (uvmpdpol_pageisqueued_p(pg)) {
1197: return;
1198: }
1.17 yamt 1199: clockpro_clearreferencebit(pg, true);
1.2 yamt 1200: pg->pqflags |= PQ_SPECULATIVE;
1201: clockpro_pageenqueue(pg);
1202: #else
1.22 ad 1203: uvmpdpol_pageactivate_locked(pg);
1.2 yamt 1204: #endif
1205: }
1206:
1207: void
1.22 ad 1208: uvmpdpol_pageenqueue(struct vm_page *pg)
1209: {
1210:
1211: uvmpdpol_set_intent(pg, PQ_INTENT_D);
1212: }
1213:
1214: static bool
1215: uvmpdpol_pagerealize_locked(struct vm_page *pg)
1216: {
1217: uint32_t pqflags;
1218:
1219: KASSERT(mutex_owned(&clockpro.lock));
1220: KASSERT(mutex_owned(&pg->interlock));
1221:
1222: /* XXX this needs to be called from elsewhere, like uvmpdpol_clock. */
1223:
1224: pqflags = pg->pqflags;
1225: pq->pqflags &= ~(PQ_INTENT_SET | PQ_INTENT_QUEUED);
1226: switch (pqflags & (PQ_INTENT_MASK | PQ_INTENT_SET)) {
1227: case PQ_INTENT_A | PQ_INTENT_SET:
1228: uvmpdpol_pageactivate_locked(pg);
1229: return true;
1230: case PQ_INTENT_E | PQ_INTENT_SET:
1231: uvmpdpol_pageenqueue_locked(pg);
1232: return true;
1233: case PQ_INTENT_I | PQ_INTENT_SET:
1234: uvmpdpol_pagedeactivate_locked(pg);
1235: return true;
1236: case PQ_INTENT_D | PQ_INTENT_SET:
1237: uvmpdpol_pagedequeue_locked(pg);
1238: return true;
1239: default:
1240: return false;
1241: }
1242: }
1243:
1244: void
1245: uvmpdpol_pagerealize(struct vm_page *pg)
1246: {
1247: struct clockpro_state * const s = &clockpro;
1248:
1249: mutex_enter(&s->lock);
1250: uvmpdpol_pagerealize_locked(pg);
1251: mutex_exit(&s->lock);
1252: }
1253:
1254: void
1.2 yamt 1255: uvmpdpol_anfree(struct vm_anon *an)
1256: {
1.18 ad 1257: struct clockpro_state * const s = &clockpro;
1.2 yamt 1258:
1259: KASSERT(an->an_page == NULL);
1.18 ad 1260: mutex_enter(&s->lock);
1.2 yamt 1261: if (nonresident_lookupremove((objid_t)an, 0)) {
1262: PDPOL_EVCNT_INCR(nresanonfree);
1263: }
1.18 ad 1264: mutex_exit(&s->lock);
1.2 yamt 1265: }
1266:
1267: void
1268: uvmpdpol_init(void)
1269: {
1270:
1271: clockpro_init();
1272: }
1273:
1274: void
1275: uvmpdpol_reinit(void)
1276: {
1.18 ad 1277: struct clockpro_state * const s = &clockpro;
1.2 yamt 1278:
1.18 ad 1279: mutex_enter(&s->lock);
1.2 yamt 1280: clockpro_reinit();
1.18 ad 1281: mutex_exit(&s->lock);
1.2 yamt 1282: }
1283:
1284: void
1285: uvmpdpol_estimatepageable(int *active, int *inactive)
1286: {
1287: struct clockpro_state * const s = &clockpro;
1288:
1.23 ! ad 1289: /*
! 1290: * Don't take any locks here. This can be called from DDB, and in
! 1291: * any case the numbers are stale the instant the lock is dropped,
! 1292: * so it just doesn't matter.
! 1293: */
1.2 yamt 1294: if (active) {
1295: *active = s->s_npages - s->s_ncold;
1296: }
1297: if (inactive) {
1298: *inactive = s->s_ncold;
1299: }
1300: }
1301:
1.7 thorpej 1302: bool
1.2 yamt 1303: uvmpdpol_pageisqueued_p(struct vm_page *pg)
1304: {
1305:
1.18 ad 1306: /* Unlocked check OK due to page lifecycle. */
1.2 yamt 1307: return clockpro_getq(pg) != CLOCKPRO_NOQUEUE;
1308: }
1309:
1310: void
1311: uvmpdpol_scaninit(void)
1312: {
1.18 ad 1313: struct clockpro_state * const s = &clockpro;
1.2 yamt 1314: struct clockpro_scanstate * const ss = &scanstate;
1315:
1.18 ad 1316: mutex_enter(&s->lock);
1.2 yamt 1317: ss->ss_nscanned = 0;
1.18 ad 1318: mutex_exit(&s->lock);
1.2 yamt 1319: }
1320:
1.20 ad 1321: void
1322: uvmpdpol_scanfini(void)
1323: {
1324:
1325: }
1326:
1.2 yamt 1327: struct vm_page *
1.18 ad 1328: uvmpdpol_selectvictim(kmutex_t **plock)
1.2 yamt 1329: {
1330: struct clockpro_state * const s = &clockpro;
1331: struct clockpro_scanstate * const ss = &scanstate;
1332: struct vm_page *pg;
1.18 ad 1333: kmutex_t *lock = NULL;
1.2 yamt 1334:
1.18 ad 1335: do {
1336: mutex_enter(&s->lock);
1337: if (ss->ss_nscanned > s->s_npages) {
1338: DPRINTF("scan too much\n");
1339: mutex_exit(&s->lock);
1340: return NULL;
1341: }
1342: pg = handcold_advance();
1343: if (pg == NULL) {
1344: mutex_exit(&s->lock);
1345: break;
1346: }
1347: ss->ss_nscanned++;
1348: /*
1349: * acquire interlock to stablize page identity.
1350: * if we have caught the page in a state of flux
1351: * and it should be dequeued, do it now and then
1352: * move on to the next.
1353: */
1354: mutex_enter(&pg->interlock);
1355: if ((pg->uobject == NULL && pg->uanon == NULL) ||
1356: pg->wire_count > 0) {
1357: mutex_exit(&pg->interlock);
1358: clockpro_pagedequeue(pg);
1359: pg->pqflags &= ~(PQ_INITIALREF|PQ_SPECULATIVE);
1360: continue;
1361: }
1362: mutex_exit(&s->lock);
1363: lock = uvmpd_trylockowner(pg);
1364: /* pg->interlock now dropped */
1365: } while (lock == NULL);
1366: *plock = lock;
1.2 yamt 1367: return pg;
1368: }
1369:
1370: static void
1371: clockpro_dropswap(pageq_t *q, int *todo)
1372: {
1373: struct vm_page *pg;
1.20 ad 1374: kmutex_t *lock;
1.2 yamt 1375:
1.18 ad 1376: KASSERT(mutex_owned(&clockpro.lock));
1377:
1.19 ad 1378: TAILQ_FOREACH_REVERSE(pg, &q->q_q, pglist, pdqueue) {
1.2 yamt 1379: if (*todo <= 0) {
1380: break;
1381: }
1382: if ((pg->pqflags & PQ_HOT) == 0) {
1383: continue;
1384: }
1.18 ad 1385: mutex_enter(&pg->interlock);
1386: if ((pg->flags & PG_SWAPBACKED) == 0) {
1387: mutex_exit(&pg->interlock);
1.2 yamt 1388: continue;
1389: }
1.20 ad 1390:
1391: /*
1392: * try to lock the object that owns the page.
1393: */
1394: mutex_exit(&clockpro.lock);
1395: lock = uvmpd_trylockowner(pg);
1396: /* pg->interlock now released */
1397: mutex_enter(&clockpro.lock);
1398: if (lock == NULL) {
1399: /* didn't get it - try the next page. */
1400: /* XXXAD lost position in queue */
1401: continue;
1402: }
1403:
1404: /*
1405: * if there's a shortage of swap slots, try to free it.
1406: */
1407: if ((pg->flags & PG_SWAPBACKED) != 0 &&
1408: (pg->flags & PG_BUSY) == 0) {
1409: if (uvmpd_dropswap(pg)) {
1410: (*todo)--;
1411: }
1.2 yamt 1412: }
1.20 ad 1413: mutex_exit(lock);
1.2 yamt 1414: }
1415: }
1416:
1417: void
1418: uvmpdpol_balancequeue(int swap_shortage)
1419: {
1420: struct clockpro_state * const s = &clockpro;
1421: int todo = swap_shortage;
1422:
1423: if (todo == 0) {
1424: return;
1425: }
1426:
1427: /*
1428: * reclaim swap slots from hot pages
1429: */
1430:
1431: DPRINTF("%s: swap_shortage=%d\n", __func__, swap_shortage);
1432:
1.18 ad 1433: mutex_enter(&s->lock);
1.2 yamt 1434: clockpro_dropswap(clockpro_queue(s, CLOCKPRO_NEWQ), &todo);
1435: clockpro_dropswap(clockpro_queue(s, CLOCKPRO_COLDQ), &todo);
1436: clockpro_dropswap(clockpro_queue(s, CLOCKPRO_HOTQ), &todo);
1.18 ad 1437: mutex_exit(&s->lock);
1.2 yamt 1438:
1439: DPRINTF("%s: done=%d\n", __func__, swap_shortage - todo);
1440: }
1441:
1.7 thorpej 1442: bool
1.2 yamt 1443: uvmpdpol_needsscan_p(void)
1444: {
1445: struct clockpro_state * const s = &clockpro;
1446:
1.18 ad 1447: /* This must be an unlocked check: can be called from interrupt. */
1448: return s->s_ncold < s->s_coldtarget;
1.2 yamt 1449: }
1450:
1451: void
1452: uvmpdpol_tune(void)
1453: {
1.18 ad 1454: struct clockpro_state * const s = &clockpro;
1.2 yamt 1455:
1.18 ad 1456: mutex_enter(&s->lock);
1.2 yamt 1457: clockpro_tune();
1.18 ad 1458: mutex_exit(&s->lock);
1.2 yamt 1459: }
1460:
1.22 ad 1461: void
1462: uvmpdpol_idle(void)
1463: {
1464:
1465: }
1466:
1.2 yamt 1467: #if !defined(PDSIM)
1468:
1469: #include <sys/sysctl.h> /* XXX SYSCTL_DESCR */
1470:
1471: void
1472: uvmpdpol_sysctlsetup(void)
1473: {
1474: #if !defined(ADAPTIVE)
1475: struct clockpro_state * const s = &clockpro;
1476:
1477: uvm_pctparam_createsysctlnode(&s->s_coldtargetpct, "coldtargetpct",
1478: SYSCTL_DESCR("Percentage cold target queue of the entire queue"));
1479: #endif /* !defined(ADAPTIVE) */
1480: }
1481:
1482: #endif /* !defined(PDSIM) */
1483:
1484: #if defined(DDB)
1485:
1.17 yamt 1486: #if 0 /* XXXuvmplock */
1487: #define _pmap_is_referenced(pg) pmap_is_referenced(pg)
1488: #else
1489: #define _pmap_is_referenced(pg) false
1490: #endif
1491:
1.2 yamt 1492: void clockpro_dump(void);
1493:
1494: void
1495: clockpro_dump(void)
1496: {
1497: struct clockpro_state * const s = &clockpro;
1498:
1499: struct vm_page *pg;
1500: int ncold, nhot, ntest, nspeculative, ninitialref, nref;
1501: int newqlen, coldqlen, hotqlen, listqlen;
1502:
1503: newqlen = coldqlen = hotqlen = listqlen = 0;
1504: printf("npages=%d, ncold=%d, coldtarget=%d, newqlenmax=%d\n",
1505: s->s_npages, s->s_ncold, s->s_coldtarget, s->s_newqlenmax);
1506:
1507: #define INITCOUNT() \
1508: ncold = nhot = ntest = nspeculative = ninitialref = nref = 0
1509:
1510: #define COUNT(pg) \
1511: if ((pg->pqflags & PQ_HOT) != 0) { \
1512: nhot++; \
1513: } else { \
1514: ncold++; \
1515: if ((pg->pqflags & PQ_TEST) != 0) { \
1516: ntest++; \
1517: } \
1518: if ((pg->pqflags & PQ_SPECULATIVE) != 0) { \
1519: nspeculative++; \
1520: } \
1521: if ((pg->pqflags & PQ_INITIALREF) != 0) { \
1522: ninitialref++; \
1523: } else if ((pg->pqflags & PQ_REFERENCED) != 0 || \
1.17 yamt 1524: _pmap_is_referenced(pg)) { \
1.2 yamt 1525: nref++; \
1526: } \
1527: }
1528:
1529: #define PRINTCOUNT(name) \
1530: printf("%s hot=%d, cold=%d, test=%d, speculative=%d, initialref=%d, " \
1531: "nref=%d\n", \
1532: (name), nhot, ncold, ntest, nspeculative, ninitialref, nref)
1533:
1534: INITCOUNT();
1.19 ad 1535: TAILQ_FOREACH(pg, &clockpro_queue(s, CLOCKPRO_NEWQ)->q_q, pdqueue) {
1.2 yamt 1536: if (clockpro_getq(pg) != CLOCKPRO_NEWQ) {
1537: printf("newq corrupt %p\n", pg);
1538: }
1539: COUNT(pg)
1540: newqlen++;
1541: }
1542: PRINTCOUNT("newq");
1543:
1544: INITCOUNT();
1.19 ad 1545: TAILQ_FOREACH(pg, &clockpro_queue(s, CLOCKPRO_COLDQ)->q_q, pdqueue) {
1.2 yamt 1546: if (clockpro_getq(pg) != CLOCKPRO_COLDQ) {
1547: printf("coldq corrupt %p\n", pg);
1548: }
1549: COUNT(pg)
1550: coldqlen++;
1551: }
1552: PRINTCOUNT("coldq");
1553:
1554: INITCOUNT();
1.19 ad 1555: TAILQ_FOREACH(pg, &clockpro_queue(s, CLOCKPRO_HOTQ)->q_q, pdqueue) {
1.2 yamt 1556: if (clockpro_getq(pg) != CLOCKPRO_HOTQ) {
1557: printf("hotq corrupt %p\n", pg);
1558: }
1559: #if defined(LISTQ)
1560: if ((pg->pqflags & PQ_HOT) == 0) {
1561: printf("cold page in hotq: %p\n", pg);
1562: }
1563: #endif /* defined(LISTQ) */
1564: COUNT(pg)
1565: hotqlen++;
1566: }
1567: PRINTCOUNT("hotq");
1568:
1569: INITCOUNT();
1.19 ad 1570: TAILQ_FOREACH(pg, &clockpro_queue(s, CLOCKPRO_LISTQ)->q_q, pdqueue) {
1.2 yamt 1571: #if !defined(LISTQ)
1.14 bjs 1572: printf("listq %p\n", pg);
1.2 yamt 1573: #endif /* !defined(LISTQ) */
1574: if (clockpro_getq(pg) != CLOCKPRO_LISTQ) {
1575: printf("listq corrupt %p\n", pg);
1576: }
1577: COUNT(pg)
1578: listqlen++;
1579: }
1580: PRINTCOUNT("listq");
1581:
1582: printf("newqlen=%d/%d, coldqlen=%d/%d, hotqlen=%d/%d, listqlen=%d/%d\n",
1583: newqlen, pageq_len(clockpro_queue(s, CLOCKPRO_NEWQ)),
1584: coldqlen, pageq_len(clockpro_queue(s, CLOCKPRO_COLDQ)),
1585: hotqlen, pageq_len(clockpro_queue(s, CLOCKPRO_HOTQ)),
1586: listqlen, pageq_len(clockpro_queue(s, CLOCKPRO_LISTQ)));
1587: }
1588:
1589: #endif /* defined(DDB) */
1590:
1591: #if defined(PDSIM)
1.3 yamt 1592: #if defined(DEBUG)
1.2 yamt 1593: static void
1594: pdsim_dumpq(int qidx)
1595: {
1596: struct clockpro_state * const s = &clockpro;
1597: pageq_t *q = clockpro_queue(s, qidx);
1598: struct vm_page *pg;
1599:
1.19 ad 1600: TAILQ_FOREACH(pg, &q->q_q, pdqueue) {
1.2 yamt 1601: DPRINTF(" %" PRIu64 "%s%s%s%s%s%s",
1602: pg->offset >> PAGE_SHIFT,
1603: (pg->pqflags & PQ_HOT) ? "H" : "",
1604: (pg->pqflags & PQ_TEST) ? "T" : "",
1605: (pg->pqflags & PQ_REFERENCED) ? "R" : "",
1.17 yamt 1606: _pmap_is_referenced(pg) ? "r" : "",
1.2 yamt 1607: (pg->pqflags & PQ_INITIALREF) ? "I" : "",
1608: (pg->pqflags & PQ_SPECULATIVE) ? "S" : ""
1609: );
1610: }
1611: }
1.3 yamt 1612: #endif /* defined(DEBUG) */
1.2 yamt 1613:
1614: void
1615: pdsim_dump(const char *id)
1616: {
1617: #if defined(DEBUG)
1618: struct clockpro_state * const s = &clockpro;
1619:
1620: DPRINTF(" %s L(", id);
1621: pdsim_dumpq(CLOCKPRO_LISTQ);
1622: DPRINTF(" ) H(");
1623: pdsim_dumpq(CLOCKPRO_HOTQ);
1624: DPRINTF(" ) C(");
1625: pdsim_dumpq(CLOCKPRO_COLDQ);
1626: DPRINTF(" ) N(");
1627: pdsim_dumpq(CLOCKPRO_NEWQ);
1628: DPRINTF(" ) ncold=%d/%d, coldadj=%d\n",
1629: s->s_ncold, s->s_coldtarget, coldadj);
1630: #endif /* defined(DEBUG) */
1631: }
1632: #endif /* defined(PDSIM) */
CVSweb <webmaster@jp.NetBSD.org>