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
38struct vm_page *pages;
39
40struct uvmexp uvmexp;
41
42int npagein;
43int nfault;
44int raio;
45int rahit;
46
47int lastacc[MAXID];
48int irr[MAXID];
49int ts;
50
51struct {
52	int fault;
53	int hit;
54} stats[MAXID];
55
56TAILQ_HEAD(, vm_page) freeq;
57
58struct vm_page *
59pdsim_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
79void
80pdsim_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
109static struct vm_page *
110pdsim_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
119static void
120pdsim_pagemarkreferenced(struct vm_page *pg)
121{
122
123	pg->_mdflags |= MDPG_REFERENCED;
124}
125
126boolean_t
127pmap_is_referenced(struct vm_page *pg)
128{
129
130	return pg->_mdflags & MDPG_REFERENCED;
131}
132
133boolean_t
134pmap_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
143static void
144pdsim_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
162static void
163pdsim_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
179static void
180fault(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");
204retry:
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) {
221ra_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
238struct uvm_object obj;
239
240static void
241test(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)
271static void
272dumpstats(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
285int
286main(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}
301