regress/sys/uvm/pdsim/pdsim.c

   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
  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 *
  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
  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 *
 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
 120 pdsim_pagemarkreferenced(struct vm_page *pg)
 121 {
 122
 123         pg->_mdflags |= MDPG_REFERENCED;
 124 }
 125
 126 boolean_t
 127 pmap_is_referenced(struct vm_page *pg)
 128 {
 129
 130         return pg->_mdflags & MDPG_REFERENCED;
 131 }
 132
 133 boolean_t
 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
 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
 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
 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
 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
 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
 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 }