/*
 * Copyright (C) 1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * Copyright (C) 1998 Digital Equipment Corporation
 *
 * This file is part of the SimOS distribution.
 * See LICENSE file for terms of the license.
 *
 */


#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#include "icode.h"
#include "globals.h"
#include "task.h"
#include "wheel.h"
#include "symtab.h"
#include "hash.h"

/* This points to the current position withing the tim ewheel */
wheel_task_ptr current_ptr;

/* The time wheel is an array of head-nodes to doubly linked lists.
 * The array is indexed by the time value of a task. If the time
 * value is too large, then a task is added to a future queue
 * and processed when the current index into the time wheel wraps around.
 * current_ptr is a pointer to the head node for the current time wheel entry.
 * When all the tasks for the current time have been executed, current_ptr is 
 * incremented to the next time wheel entry.
 */
wheel_task_ptr wheel;

/* end_ptr pointes past the end of the time wheel. Once initialized, this
 * cariable never changes
 */
wheel_task_ptr end_ptr;

aint_time_t start_time;
aint_time_t end_time;

/* future_q stores tasks that are scheduled for too far in the future */
task_ptr future_q;
static task_t future_q_head;
static task_t dummy_task;

/* used in wheel_ptrin() to lookup function names */
extern hash_tab_ptr func_hash_tab;
extern int num_tasks;

/* if more than this number of tasks is allocated, it is probably a mistake */
#define TOO_MANY_TASKS 10000

/* use a global variable that can be changed by the backend */
int too_many_tasks = TOO_MANY_TASKS;

int ckpoint_event (task_ptr ptask);

void
wheel_init ()
{
    int i;

    start_time = 0;
    end_time = WHEEL_SIZE - 1;

    wheel = (wheel_task_ptr) (long) calloc (sizeof (wheel_task_t),
					    WHEEL_SIZE + 1);
    if (wheel == NULL)
	fatal ("wheel_init: cannot allocate %d bytes for the time wheel.\n",
	       sizeof (wheel_task_t) * (WHEEL_SIZE + 1));

    for (i = 0; i < WHEEL_SIZE + 1; i++) {
	INLINE_INIT_Q ((task_ptr) & wheel[i]);
	wheel[i].priority = PRIORITY_HIGH;
	wheel[i].time = MAXTIME;
    }

    current_ptr = &wheel[0];
    end_ptr = &wheel[WHEEL_SIZE];

    /* add a dummy item to the last (unused) queue in the time wheel */
    INLINE_ENQUEUE ((task_ptr) & wheel[WHEEL_SIZE], &dummy_task);
    future_q = &future_q_head;
    INLINE_INIT_Q (future_q);
    future_q->time = MAXTIME;
    dummy_task.pid = -2;	/* An unused pid */
    future_q_head.pid = -2;

    if (ckpoint_freq > 0)
	pri_sched_task (&dummy_task,
			ckpoint_event,
			ckpoint_freq,
			PRIORITY_LOW);
}


int
ckpoint_event (task_ptr ptask)
{
    int i;

    /* if there are no scheduled tasks then all are blocked */
    for (i = 0; i < WHEEL_SIZE; i++)
	if (wheel[i].next != (task_ptr) & wheel[i])
	    break;
    if (i == WHEEL_SIZE) {
	/* check the future queue */
	if (future_q->next == future_q) {
	    sim_deadlock ();
	}
    }

    sim_checkpoint (ptask);

    if (ckpoint_freq > 0)
	pri_sched_task (&dummy_task, ckpoint_event, ptask->time + ckpoint_freq,
			PRIORITY_LOW);
    return (T_NO_ADVANCE);
}

/* Returns true if time wheel is empty (not counting the checkpoint task) */
int
wheel_empty ()
{
    int i;
    task_ptr pnew;

    for (i = 0; i < WHEEL_SIZE; i++) {
	pnew = wheel[i].next;
	if (pnew->ufunc == ckpoint_event)
	    pnew = pnew->next;
	if (pnew != (task_ptr) & wheel[i])
	    return (0);
    }
    pnew = future_q->next;
    if (pnew->ufunc == ckpoint_event)
	pnew = pnew->next;
    if (pnew != future_q)
	return (0);
    return (1);
}

task_ptr
task_pull_from_future ()
{
    task_ptr pnew, tptr, next;

    while (1) {
	/*
	 * Search the queues until we get to the end. Since we put a dummy item
	 * in the last (unused) queue, we don't need to check for overflow of
	 * the current_ptr in each iteration
	 */
	do {
	    current_ptr++;
	    pnew = current_ptr->next;
	} while (pnew == (task_ptr) current_ptr);

	/* if we found a tsk, remove it and return */
	if (current_ptr != end_ptr) {
	    INLINE_REMOVE (pnew);
	    return (pnew);
	}

	/* Wrap around processing */
	current_ptr = &wheel[0];
	end_time += WHEEL_SIZE;
	start_time += WHEEL_SIZE;
	pnew = future_q->next;
	if (pnew == future_q)
	    return NULL;

	for (; pnew != future_q; pnew = next) {
	    int diff = pnew->time - start_time;
	    next = pnew->next;

	    if (diff < WHEEL_SIZE) {
		/* insert in priority order */
		for (tptr = wheel[diff].prev; tptr->priority < pnew->priority;
		     tptr = tptr->prev);

		INLINE_REMOVE (pnew);
		INLINE_INSERT_AFTER (tptr, pnew);
	    }
	}

	pnew = current_ptr->next;
	if (pnew != (task_ptr) current_ptr) {
	    INLINE_REMOVE (pnew);
	    return pnew;
	}
    }
}


/*
 * task_cleanup ensures that all the scheduled tasks for a process have
 * executed before sim_terminate is called
 */
int
task_cleanup (task_ptr ptask)
{
    int i;
    task_ptr pnew;
    /* search the future queue first */
    for (pnew = future_q->next; pnew != future_q; pnew = pnew->next) {
	if (pnew->pid == ptask->pid)
	    break;
    }

    /*
     * If we found a task for this process, wait for it to execute, then
     * check the wheel again at that time.
     */
    if (pnew != future_q) {
	pri_sched_task (ptask, task_cleanup, pnew->time, PRIORITY_LOW);
	return (T_NO_ADVANCE);
    }

    /* search backwards, starting at the end of the wheel */
    for (i = WHEEL_SIZE - 1; i >= 0; i--) {
	pnew = wheel[i].prev;
	/* if the queue is empty, continue with the next queue */
	if (pnew == (task_ptr) & wheel[i])
	    continue;
	while (pnew != (task_ptr) & wheel[i]) {
	    if (pnew->pid == ptask->pid)
		break;
	    pnew = pnew->prev;
	}

	/*
	 * If we found a task for this process, wait for it to execute,
	 * then check the wheel at that time.
	 */
	if (pnew != (task_ptr) & wheel[i]) {
	    pri_sched_task (ptask, task_cleanup, pnew->time, PRIORITY_LOW);
	    return T_NO_ADVANCE;
	}
    }
    return T_CONTINUE;
}

/*
 * This routine prints out the entries in the time wheel. It uses the
 * symbol table information to lookup the names of functions corresponding
 * to function addresses.
 */
void
wheel_print ()
{
    task_ptr pnew;
    int pos;

    fprintf (stderr, "End_time = %.1f, Start_time = %.1f\n",
             end_time, start_time);

    for (pos = 0; pos < WHEEL_SIZE; pos++) {
        pnew = wheel[pos].next;
        if (pnew != (task_ptr) & wheel[pos]) {
            fprintf (stderr, "%d:", pos);
            while (pnew != (task_ptr) & wheel[pos]) {
                fprintf (stderr, "\tp%d time %.1f, pri %d, func 0x%x \n",
                         pnew->pid, pnew->time, pnew->priority, pnew->ufunc);
                pnew = pnew->next;
            }
            fprintf (stderr, "\n");
        }
    }
    pnew = future_q->next;
    if (pnew == future_q)
        return;
    fprintf (stderr, "Future_q:\n");
    for (; pnew != future_q; pnew = pnew->next) {
        fprintf (stderr, "\tp%d time %.1f, pri %d, func 0x%x \n",
                 pnew->pid, pnew->time, pnew->priority, pnew->ufunc);
    }
}