/*      $NetBSD: pdsim.c,v 1.2 2006/10/14 04:43:41 yamt Exp $   */

/*-
 * Copyright (c)2006 YAMAMOTO Takashi,
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "pdsim.h"

#define SHOWFAULT
#if defined(SHOWQLEN) || defined(SHOWIRR)
#undef SHOWFAULT
#endif

#undef  READAHEAD

struct vm_page *pages;

struct uvmexp uvmexp;

int npagein;
int nfault;
int raio;
int rahit;

int lastacc[MAXID];
int irr[MAXID];
int ts;

struct {
        int fault;
        int hit;
} stats[MAXID];

TAILQ_HEAD(, vm_page) freeq;

struct vm_page *
pdsim_pagealloc(struct uvm_object *obj, int idx)
{
        struct vm_page *pg;

        pg = TAILQ_FIRST(&freeq);
        if (pg == NULL) {
                return NULL;
        }
        TAILQ_REMOVE(&freeq, pg, pageq);
        pg->offset = idx << PAGE_SHIFT;
        pg->uanon = NULL;
        pg->uobject = obj;
        pg->pqflags = 0;
        obj->pages[idx] = pg;
        uvmexp.free--;
        uvmexp.filepages++;

        return pg;
}

void
pdsim_pagefree(struct vm_page *pg)
{
        struct uvm_object *obj;

        KASSERT(pg != NULL);

#if defined(SHOWFREE)
        if (pg->offset != -1) {
                int idx = pg->offset >> PAGE_SHIFT;
                printf("%d %d   # FREE IRR\n", idx, irr[idx]);
        }
#endif /* defined(SHOWFREE) */

        uvmpdpol_pagedequeue(pg);

        KASSERT(pg->uanon == NULL);
        obj = pg->uobject;
        if (obj != NULL) {
                int idx;

                idx = pg->offset >> PAGE_SHIFT;
                KASSERT(obj->pages[idx] == pg);
                obj->pages[idx] = NULL;
                uvmexp.filepages--;
        }
        TAILQ_INSERT_HEAD(&freeq, pg, pageq);
        uvmexp.free++;
}

static struct vm_page *
pdsim_pagelookup(struct uvm_object *obj, int index)
{
        struct vm_page *pg;

        pg = obj->pages[index];

        return pg;
}

static void
pdsim_pagemarkreferenced(struct vm_page *pg)
{

        pg->_mdflags |= MDPG_REFERENCED;
}

boolean_t
pmap_is_referenced(struct vm_page *pg)
{

        return pg->_mdflags & MDPG_REFERENCED;
}

boolean_t
pmap_clear_reference(struct vm_page *pg)
{
        boolean_t referenced = pmap_is_referenced(pg);

        pg->_mdflags &= ~MDPG_REFERENCED;

        return referenced;
}

static void
pdsim_init(int n)
{
        struct vm_page *pg;
        int i;

        uvmpdpol_init();
        uvmexp.npages = n;
        uvmpdpol_reinit();

        TAILQ_INIT(&freeq);
        pages = calloc(n, sizeof(*pg));
        for (i = 0; i < n; i++) {
                pg = &pages[i];
                pg->offset = -1;
                pdsim_pagefree(pg);
        }
}

static void
pdsim_reclaimone(void)
{
        struct vm_page *pg;

        uvmexp.freetarg = 1;
        while (uvmexp.free < uvmexp.freetarg) {
                uvmpdpol_tune();
                uvmpdpol_scaninit();
                pg = uvmpdpol_selectvictim();
                if (pg != NULL) {
                        pdsim_pagefree(pg);
                }
                uvmpdpol_balancequeue(0);
        }
}

static void
fault(struct uvm_object *obj, int index)
{
        struct vm_page *pg;

        DPRINTF("fault: %d -> ", index);
        nfault++;
        ts++;
        if (lastacc[index]) {
                irr[index] = ts - lastacc[index];
        }
        lastacc[index] = ts;
        stats[index].fault++;
        pg = pdsim_pagelookup(obj, index);
        if (pg) {
                DPRINTF("cached\n");
                pdsim_pagemarkreferenced(pg);
                stats[index].hit++;
                if ((pg->_mdflags & MDPG_SPECULATIVE) != 0) {
                        pg->_mdflags &= ~MDPG_SPECULATIVE;
                        rahit++;
                }
                return;
        }
        DPRINTF("miss\n");
retry:
        pg = pdsim_pagealloc(obj, index);
        if (pg == NULL) {
                pdsim_reclaimone();
                goto retry;
        }
        npagein++;
#if defined(SHOWFAULT)
        printf("%d      # FLT\n", index);
#endif
        pdsim_pagemarkreferenced(pg);
        uvmpdpol_pageactivate(pg);
        uvmpdpol_pageactivate(pg);
        dump("fault");
#if defined(READAHEAD)
        pg = pdsim_pagelookup(obj, index + 1);
        if (pg == NULL) {
ra_retry:
                pg = pdsim_pagealloc(obj, index + 1);
                if (pg == NULL) {
                        pdsim_reclaimone();
                        goto ra_retry;
                }
                raio++;
                pg->_mdflags |= MDPG_SPECULATIVE;
#if defined(SHOWFAULT)
                printf("%d      # READ-AHEAD\n", index + 1);
#endif
        }
        uvmpdpol_pageenqueue(pg);
        dump("read-ahead");
#endif /* defined(READAHEAD) */
}

struct uvm_object obj;

static void
test(void)
{
        memset(&obj, 0, sizeof(obj));
        char *ln;

        for (;; free(ln)) {
                int i;
                int ch;

                ln = fparseln(stdin, NULL, NULL, NULL, 0); 
                if (ln == NULL) {
                        break;
                }
                ch = *ln;
                if (ch == '\0') {
                        break;
                }
                if (ch == 'd') {
                        dump("test");
                        continue;
                }
                i = atoi(ln);
                fault(&obj, i);
#if defined(SHOWQLEN)
                showqlen();
#endif
        }
}

#if defined(DEBUG)
static void
dumpstats(void)
{
        int i;
        for (i = 0; i < MAXID; i++) {
                if (stats[i].fault == 0) {
                        continue;
                }
                DPRINTF("[%d] %d/%d %d\n", i,
                    stats[i].hit, stats[i].fault, irr[i]);
        }
}
#endif /* defined(DEBUG) */

int
main(int argc, char *argv[])
{

        setvbuf(stderr, NULL, _IOFBF, 0); /* XXX */

        pdsim_init(atoi(argv[1]));
        test();
        DPRINTF("io %d (%d + ra %d) / flt %d\n",
            npagein + raio, npagein, raio, nfault);
        DPRINTF("rahit / raio= %d / %d\n", rahit, raio);
#if defined(DEBUG)
        dumpstats();
#endif
        exit(0);
}