1/* $NetBSD: pdsim.c,v 1.1 2006/10/09 12:32:46 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 38struct vm_page *pages; 39 40struct uvmexp uvmexp; 41 42int npagein; 43int nfault; 44int raio; 45int rahit; 46 47int lastacc[MAXID]; 48int irr[MAXID]; 49int ts; 50 51struct { 52 int fault; 53 int hit; 54} stats[MAXID]; 55 56TAILQ_HEAD(, vm_page) freeq; 57 58struct vm_page * 59pdsim_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 79void 80pdsim_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 109static struct vm_page * 110pdsim_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 119static void 120pdsim_pagemarkreferenced(struct vm_page *pg) 121{ 122 123 pg->_mdflags |= MDPG_REFERENCED; 124} 125 126boolean_t 127pmap_is_referenced(struct vm_page *pg) 128{ 129 130 return pg->_mdflags & MDPG_REFERENCED; 131} 132 133boolean_t 134pmap_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 143static void 144pdsim_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 162static void 163pdsim_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 179static void 180fault(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"); 204retry: 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) { 221ra_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 238struct uvm_object obj; 239 240static void 241test(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) 271static void 272dumpstats(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 285int 286main(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