regress/sys/uvm/pdsim/lirs.c

   1 /*      $NetBSD: lirs.c,v 1.2 2006/10/09 12:40:00 yamt Exp $    */
   2
   3 /*-
   4  * Copyright (c)2005 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 <sys/queue.h>
  30
  31 #include <assert.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #if defined(DEBUG)
  37 #define DFPRINTF(...)   fprintf(__VA_ARGS__)
  38 #else
  39 #define DFPRINTF(...)   /* nothing */
  40 #endif
  41
  42 #define MAXID   102400
  43
  44 struct buf {
  45         TAILQ_ENTRY(buf) b_s;
  46         TAILQ_ENTRY(buf) b_q;
  47         int b_type;
  48 #define B_L     1
  49 #define B_H     2
  50 #define B_R     4
  51         int b_flags;
  52 #define B_S     8
  53         int b_irr;
  54         int b_lastts;
  55 };
  56
  57 struct buf bufs[MAXID];
  58
  59 TAILQ_HEAD(, buf) q_q;
  60 TAILQ_HEAD(, buf) q_s;
  61
  62 int nlirs_max = 2;
  63 int nbufs_max = 3;
  64 int nlirs;
  65 int nbufs;
  66
  67 void buf_print(struct buf *, char *);
  68
  69 void
  70 buf_print(struct buf *bp, char *s)
  71 {
  72
  73         DFPRINTF(stderr, "%d(%s,%s,%d)%s", (bp - bufs),
  74             (bp->b_type == B_L) ? "L" :
  75             (bp->b_type == (B_H | B_R)) ? "HR" :
  76             (bp->b_type == B_H) ? "H" :
  77             (bp->b_type == 0) ? "free" :
  78             "unknown",
  79             (bp->b_flags & B_S) ? "S" : "",
  80             bp->b_irr,
  81             s);
  82 }
  83
  84 void
  85 dump()
  86 {
  87 #if defined(DEBUG)
  88         struct buf *bp;
  89         int i;
  90
  91         DFPRINTF(stderr, "S: ");
  92         TAILQ_FOREACH(bp, &q_s, b_s) {
  93                 buf_print(bp, " ");
  94         }
  95         DFPRINTF(stderr, "\n");
  96
  97         DFPRINTF(stderr, "Q: ");
  98         TAILQ_FOREACH(bp, &q_q, b_q) {
  99                 buf_print(bp, " ");
 100         }
 101         DFPRINTF(stderr, "\n");
 102
 103 #if 0
 104         for (i = 0; i < 256; i++) {
 105
 106                 bp = &bufs[i];
 107                 if (bufs->b_type == 0) {
 108                         continue;
 109                 }
 110         }
 111 #endif
 112
 113         DFPRINTF(stderr, "nlirs=%d, nbufs=%d\n", nlirs, nbufs);
 114 #endif /* defined(DEBUG) */
 115 }
 116
 117 void
 118 reclaim()
 119 {
 120         struct buf *bp;
 121
 122         if (nbufs <= nbufs_max) {
 123                 return;
 124         }
 125
 126         bp = TAILQ_FIRST(&q_q);
 127         buf_print(bp, ": reclaim\n");
 128         assert(bp->b_type == (B_H | B_R));
 129         TAILQ_REMOVE(&q_q, bp, b_q);
 130         bp->b_type &= ~B_R;
 131         nbufs--;
 132 }
 133
 134 void
 135 prune()
 136 {
 137
 138         while (1) {
 139                 struct buf *bp;
 140
 141                 bp = TAILQ_FIRST(&q_s);
 142                 if (bp->b_type == B_L) {
 143                         break;
 144                 }
 145                 buf_print(bp, ": prune\n");
 146                 TAILQ_REMOVE(&q_s, bp, b_s);
 147                 assert(bp->b_flags & B_S);
 148                 bp->b_flags &= ~B_S;
 149                 if ((bp->b_type & B_R) == 0) {
 150                         bp->b_type &= ~B_H;
 151                 }
 152         }
 153 }
 154
 155 void
 156 reclaim_l()
 157 {
 158         struct buf *bp;
 159
 160         if (nlirs <= nlirs_max) {
 161                 return;
 162         }
 163
 164         bp = TAILQ_FIRST(&q_s);
 165         buf_print(bp, ": reclaim_l\n");
 166         assert(bp->b_type == B_L);
 167         assert(bp->b_flags & B_S);
 168         bp->b_type = B_H | B_R;
 169         bp->b_flags &= ~B_S;
 170         TAILQ_REMOVE(&q_s, bp, b_s);
 171         TAILQ_INSERT_TAIL(&q_q, bp, b_q);
 172         nlirs--;
 173         prune();
 174 }
 175
 176 void
 177 init(int n)
 178 {
 179
 180         TAILQ_INIT(&q_q);
 181         TAILQ_INIT(&q_s);
 182         memset(&bufs, 0, sizeof(bufs));
 183         nbufs_max = n;
 184 #if 0
 185         nlirs_max = nbufs_max * 2 / 3;
 186 #else
 187         nlirs_max = nbufs_max * 90 / 100;
 188 #endif
 189 }
 190
 191 struct object {int dummy;};
 192 int ts = 1;
 193
 194 void
 195 fault(struct object *dummy, int i)
 196 {
 197         struct buf *bp;
 198
 199         DFPRINTF(stderr, "----------\n");
 200         dump();
 201
 202         DFPRINTF(stderr, "---------- ts %d\n", ts);
 203
 204         bp = &bufs[i];
 205         buf_print(bp, ": access\n");
 206         if (bp->b_type == 0) {
 207                 bp->b_irr = -1;
 208         } else {
 209                 bp->b_irr = ts - bp->b_lastts - 1;
 210         }
 211         bp->b_lastts = ts;
 212
 213         if (bp->b_type == B_L) {
 214                 assert(bp->b_flags & B_S);
 215                 TAILQ_REMOVE(&q_s, bp, b_s);
 216                 TAILQ_INSERT_TAIL(&q_s, bp, b_s);
 217                 prune();
 218                 goto done;
 219         }
 220         if (bp->b_type == (B_H | B_R)) {
 221                 if (bp->b_flags & B_S) {
 222                         TAILQ_REMOVE(&q_s, bp, b_s);
 223                         TAILQ_REMOVE(&q_q, bp, b_q);
 224                         bp->b_type = B_L;
 225                         nlirs++;
 226                         reclaim_l();
 227                 } else {
 228                         TAILQ_REMOVE(&q_q, bp, b_q);
 229                         TAILQ_INSERT_TAIL(&q_q, bp, b_q);
 230                 }
 231                 TAILQ_INSERT_TAIL(&q_s, bp, b_s);
 232                 bp->b_flags |= B_S;
 233                 goto done;
 234         }
 235         nbufs++;
 236         reclaim();
 237         if ((bp->b_flags & (B_R | B_L)) == 0) {
 238                 printf("%d\n", i);
 239         }
 240         if (bp->b_type == 0) {
 241                 buf_print(bp, ": new\n");
 242                 if (nlirs < nlirs_max) {
 243                         bp->b_type = B_L;
 244                         TAILQ_INSERT_TAIL(&q_s, bp, b_s);
 245                         bp->b_flags |= B_S;
 246                         nlirs++;
 247                 } else {
 248                         bp->b_type = B_H;
 249                 }
 250         }
 251         if (bp->b_type == B_H) {
 252                 if (bp->b_flags & B_S) {
 253                         TAILQ_REMOVE(&q_s, bp, b_s);
 254                         bp->b_type = B_L;
 255                         nlirs++;
 256                         reclaim_l();
 257                 } else {
 258                         bp->b_type |= B_R;
 259                         TAILQ_INSERT_TAIL(&q_q, bp, b_q);
 260                 }
 261                 TAILQ_INSERT_TAIL(&q_s, bp, b_s);
 262                 bp->b_flags |= B_S;
 263         }
 264 done:
 265         ts++;
 266 }
 267
 268 void
 269 test(void)
 270 {
 271         struct object obj;
 272         memset(&obj, 0, sizeof(obj));
 273         char *ln;
 274
 275         for (;; free(ln)) {
 276                 int i;
 277                 int ch;
 278
 279                 ln = fparseln(stdin, NULL, NULL, NULL, 0);
 280                 if (ln == NULL) {
 281                         break;
 282                 }
 283                 ch = *ln;
 284                 if (ch == '\0') {
 285                         break;
 286                 }
 287 #if 1
 288                 if (ch == 'd') {
 289                         dump();
 290                         continue;
 291                 }
 292 #endif
 293                 i = atoi(ln);
 294                 fault(&obj, i);
 295         }
 296 }
 297
 298 int
 299 main(int argc, char *argv[])
 300 {
 301
 302         init(atoi(argv[1]));
 303         test();
 304         exit(0);
 305 }