1 /* $NetBSD: pdsim.c,v 1.2 2006/10/14 04:43:41 yamt Exp $ */
2
3 /*-
4 * Copyright (c)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 #include "pdsim.h"
30
31 #define SHOWFAULT
32 #if defined(SHOWQLEN) || defined(SHOWIRR)
33 #undef SHOWFAULT
34 #endif
35
36 #undef READAHEAD
37
38 struct vm_page *pages;
39
40 struct uvmexp uvmexp;
41
42 int npagein;
43 int nfault;
44 int raio;
45 int rahit;
46
47 int lastacc[MAXID];
48 int irr[MAXID];
49 int ts;
50
51 struct {
52 int fault;
53 int hit;
54 } stats[MAXID];
55
56 TAILQ_HEAD(, vm_page) freeq;
57
58 struct vm_page *
pdsim_pagealloc(struct uvm_object * obj,int idx)59 pdsim_pagealloc(struct uvm_object *obj, int idx)
60 {
61 struct vm_page *pg;
62
63 pg = TAILQ_FIRST(&freeq);
64 if (pg == NULL) {
65 return NULL;
66 }
67 TAILQ_REMOVE(&freeq, pg, pageq);
68 pg->offset = idx << PAGE_SHIFT;
69 pg->uanon = NULL;
70 pg->uobject = obj;
71 pg->pqflags = 0;
72 obj->pages[idx] = pg;
73 uvmexp.free--;
74 uvmexp.filepages++;
75
76 return pg;
77 }
78
79 void
pdsim_pagefree(struct vm_page * pg)80 pdsim_pagefree(struct vm_page *pg)
81 {
82 struct uvm_object *obj;
83
84 KASSERT(pg != NULL);
85
86 #if defined(SHOWFREE)
87 if (pg->offset != -1) {
88 int idx = pg->offset >> PAGE_SHIFT;
89 printf("%d %d # FREE IRR\n", idx, irr[idx]);
90 }
91 #endif /* defined(SHOWFREE) */
92
93 uvmpdpol_pagedequeue(pg);
94
95 KASSERT(pg->uanon == NULL);
96 obj = pg->uobject;
97 if (obj != NULL) {
98 int idx;
99
100 idx = pg->offset >> PAGE_SHIFT;
101 KASSERT(obj->pages[idx] == pg);
102 obj->pages[idx] = NULL;
103 uvmexp.filepages--;
104 }
105 TAILQ_INSERT_HEAD(&freeq, pg, pageq);
106 uvmexp.free++;
107 }
108
109 static struct vm_page *
pdsim_pagelookup(struct uvm_object * obj,int index)110 pdsim_pagelookup(struct uvm_object *obj, int index)
111 {
112 struct vm_page *pg;
113
114 pg = obj->pages[index];
115
116 return pg;
117 }
118
119 static void
pdsim_pagemarkreferenced(struct vm_page * pg)120 pdsim_pagemarkreferenced(struct vm_page *pg)
121 {
122
123 pg->_mdflags |= MDPG_REFERENCED;
124 }
125
126 boolean_t
pmap_is_referenced(struct vm_page * pg)127 pmap_is_referenced(struct vm_page *pg)
128 {
129
130 return pg->_mdflags & MDPG_REFERENCED;
131 }
132
133 boolean_t
pmap_clear_reference(struct vm_page * pg)134 pmap_clear_reference(struct vm_page *pg)
135 {
136 boolean_t referenced = pmap_is_referenced(pg);
137
138 pg->_mdflags &= ~MDPG_REFERENCED;
139
140 return referenced;
141 }
142
143 static void
pdsim_init(int n)144 pdsim_init(int n)
145 {
146 struct vm_page *pg;
147 int i;
148
149 uvmpdpol_init();
150 uvmexp.npages = n;
151 uvmpdpol_reinit();
152
153 TAILQ_INIT(&freeq);
154 pages = calloc(n, sizeof(*pg));
155 for (i = 0; i < n; i++) {
156 pg = &pages[i];
157 pg->offset = -1;
158 pdsim_pagefree(pg);
159 }
160 }
161
162 static void
pdsim_reclaimone(void)163 pdsim_reclaimone(void)
164 {
165 struct vm_page *pg;
166
167 uvmexp.freetarg = 1;
168 while (uvmexp.free < uvmexp.freetarg) {
169 uvmpdpol_tune();
170 uvmpdpol_scaninit();
171 pg = uvmpdpol_selectvictim();
172 if (pg != NULL) {
173 pdsim_pagefree(pg);
174 }
175 uvmpdpol_balancequeue(0);
176 }
177 }
178
179 static void
fault(struct uvm_object * obj,int index)180 fault(struct uvm_object *obj, int index)
181 {
182 struct vm_page *pg;
183
184 DPRINTF("fault: %d -> ", index);
185 nfault++;
186 ts++;
187 if (lastacc[index]) {
188 irr[index] = ts - lastacc[index];
189 }
190 lastacc[index] = ts;
191 stats[index].fault++;
192 pg = pdsim_pagelookup(obj, index);
193 if (pg) {
194 DPRINTF("cached\n");
195 pdsim_pagemarkreferenced(pg);
196 stats[index].hit++;
197 if ((pg->_mdflags & MDPG_SPECULATIVE) != 0) {
198 pg->_mdflags &= ~MDPG_SPECULATIVE;
199 rahit++;
200 }
201 return;
202 }
203 DPRINTF("miss\n");
204 retry:
205 pg = pdsim_pagealloc(obj, index);
206 if (pg == NULL) {
207 pdsim_reclaimone();
208 goto retry;
209 }
210 npagein++;
211 #if defined(SHOWFAULT)
212 printf("%d # FLT\n", index);
213 #endif
214 pdsim_pagemarkreferenced(pg);
215 uvmpdpol_pageactivate(pg);
216 uvmpdpol_pageactivate(pg);
217 dump("fault");
218 #if defined(READAHEAD)
219 pg = pdsim_pagelookup(obj, index + 1);
220 if (pg == NULL) {
221 ra_retry:
222 pg = pdsim_pagealloc(obj, index + 1);
223 if (pg == NULL) {
224 pdsim_reclaimone();
225 goto ra_retry;
226 }
227 raio++;
228 pg->_mdflags |= MDPG_SPECULATIVE;
229 #if defined(SHOWFAULT)
230 printf("%d # READ-AHEAD\n", index + 1);
231 #endif
232 }
233 uvmpdpol_pageenqueue(pg);
234 dump("read-ahead");
235 #endif /* defined(READAHEAD) */
236 }
237
238 struct uvm_object obj;
239
240 static void
test(void)241 test(void)
242 {
243 memset(&obj, 0, sizeof(obj));
244 char *ln;
245
246 for (;; free(ln)) {
247 int i;
248 int ch;
249
250 ln = fparseln(stdin, NULL, NULL, NULL, 0);
251 if (ln == NULL) {
252 break;
253 }
254 ch = *ln;
255 if (ch == '\0') {
256 break;
257 }
258 if (ch == 'd') {
259 dump("test");
260 continue;
261 }
262 i = atoi(ln);
263 fault(&obj, i);
264 #if defined(SHOWQLEN)
265 showqlen();
266 #endif
267 }
268 }
269
270 #if defined(DEBUG)
271 static void
dumpstats(void)272 dumpstats(void)
273 {
274 int i;
275 for (i = 0; i < MAXID; i++) {
276 if (stats[i].fault == 0) {
277 continue;
278 }
279 DPRINTF("[%d] %d/%d %d\n", i,
280 stats[i].hit, stats[i].fault, irr[i]);
281 }
282 }
283 #endif /* defined(DEBUG) */
284
285 int
main(int argc,char * argv[])286 main(int argc, char *argv[])
287 {
288
289 setvbuf(stderr, NULL, _IOFBF, 0); /* XXX */
290
291 pdsim_init(atoi(argv[1]));
292 test();
293 DPRINTF("io %d (%d + ra %d) / flt %d\n",
294 npagein + raio, npagein, raio, nfault);
295 DPRINTF("rahit / raio= %d / %d\n", rahit, raio);
296 #if defined(DEBUG)
297 dumpstats();
298 #endif
299 exit(0);
300 }
301