1 /* $NetBSD: lirs.c,v 1.3 2006/10/09 12:43:32 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 } 306