Home | History | Annotate | Line # | Download | only in pdsim 
      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