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
44struct 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
57struct buf bufs[MAXID];
58
59TAILQ_HEAD(, buf) q_q;
60TAILQ_HEAD(, buf) q_s;
61
62int nlirs_max = 2;
63int nbufs_max = 3;
64int nlirs;
65int nbufs;
66
67void buf_print(struct buf *, char *);
68
69void
70buf_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
84void
85dump()
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
117void
118reclaim()
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
134void
135prune()
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
155void
156reclaim_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
176void
177init(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
191struct object {int dummy;};
192int ts = 1;
193
194void
195fault(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	}
264done:
265	ts++;
266}
267
268void
269test(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
298int
299main(int argc, char *argv[])
300{
301
302	init(atoi(argv[1]));
303	test();
304	exit(0);
305}
306