//----------------------------------------------------------------------------//
//                           GNU GPL OS/K                                     //
//                                                                            //
//  Authors:    spectral`                                                     //
//              NeoX                                                          //
//                                                                            //
//  Desc:       Scheduling algorithm                                          //
//----------------------------------------------------------------------------//

#include <stdio.h>

typedef unsigned int uint;
typedef unsigned long ulong;

#define printdbg printf
#define _STR(x) #x
#define _XSTR(x) _STR(x)

#define _KALTYPES_H
#include <common/kallist.h>

typedef struct {
    int         pid;
    int         prioClass;
    int         prioLevel;
    int         procState;
    ulong       timeSlice;
    ListNode_t *schedNode;
} Process_t;

//
// States for a process
//
#define STATE_RUNNING  0
#define STATE_RUNNABLE 1
#define STATE_BLOCKED  2

//
// Time in ticks a process should be run
//
#define DEFAULT_PROC_TIMESLICE      5      // 20 ticks
#define TIMECRIT_PROC_TIMESLICE     20000   // 20000 ticks

// XXX per-CPU stuff
Process_t *CurProc = NULL;

#define GetCurProc()     (CurProc)
static inline
void SetCurProc(Process_t *proc)
{
    CurProc = proc;
    if (CurProc != NULL) {
        CurProc->procState = STATE_RUNNING;
    }
}

//
// For test purpose only
//
int       procslen = 9;
Process_t procs[] = {
    {   0,  0,  12, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   1,  2,  16, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   2,  3,  31, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   3,  2,  1,  STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   4,  0,  5,  STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   5,  0,  30, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   6,  1,  19, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   7,  1,  0,  STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
    {   8,  3,  12, STATE_RUNNABLE, DEFAULT_PROC_TIMESLICE, NULL   },
};

//
// Shared lock among all process lists
//
static Lock_t *PrioClassesLock = NULL;

//
// (Un)Lock priority class list heads
// XXX should we disable IRQs?
//

static inline
void SchedLock(void)
{ AquireLock(PrioClassesLock); }

static inline
void SchedUnlock(void)
{ ReleaseLock(PrioClassesLock); }

//
// The four priority classes of OS/2
//
ListHead_t *IdlePrioProcs = NULL,
           *ReglPrioProcs = NULL,
           *ServPrioProcs = NULL,
           *TimeCritProcs = NULL;

char *PrioClassesNames[] = {
            "Idle priority class",
            "Regular priority class",
            "Server priority class",
            "Time-critical class",
};

enum {      IDLE_PRIO_PROC = 0,
            REGL_PRIO_PROC = 1,
            SERV_PRIO_PROC = 2,
            TIME_CRIT_PROC = 3,
};

//
// Get priority class list head
//
ListHead_t *GetPrioClassHead(int prioClass)
{
    switch (prioClass) {
        case TIME_CRIT_PROC: return TimeCritProcs;
        case SERV_PRIO_PROC: return ServPrioProcs;
        case REGL_PRIO_PROC: return ReglPrioProcs;
        case IDLE_PRIO_PROC: return IdlePrioProcs;
        default: KalAssert(FALSE && "Unknown priority class");
    }
}

//
// Determine which process is going to run first
// Returns NULL for "equal" processes
//
Process_t *CompareProcs(Process_t *proc1, Process_t *proc2)
{
    KalAssert(proc1 && proc2);

    if (proc1->prioClass > proc2->prioClass) return proc1;
    if (proc1->prioClass < proc2->prioClass) return proc2;

    if (proc1->prioLevel > proc2->prioLevel) return proc1;
    if (proc1->prioLevel < proc2->prioLevel) return proc2;

    return NULL; // same class and level
}

//
// Add process to schedule lists
//
void SchedThisProc(Process_t *proc)
{
    KalAssert(proc && proc->procState == STATE_RUNNABLE);

    bool found = false;
    ListNode_t *iterNode = NULL;
    ListNode_t *procNode = CreateNode(proc);
    ListHead_t *head = GetPrioClassHead(proc->prioClass);

    KalAssert(procNode && head);

    // XXX double locking
    // SchedLock();

    proc->schedNode = procNode;

    printdbg("Adding process %d to '%s'\n", proc->pid, PrioClassesNames[proc->prioClass]);

    //
    // Find a process with lesser priority
    //
    for (iterNode = head->first; iterNode; iterNode = iterNode->next) {
        if (proc->prioLevel > GetNodeData(iterNode, Process_t *)->prioLevel) {
            AddNodeBefore(head, iterNode, procNode);
            found = true;
            break;
        }
    }

    //
    // Didn't find any process with lesser priority
    //
    if (found == false) {
        AppendNode(head, procNode);
    }

    // SchedUnlock();
}

//
// Selects process to schedule next
//
// WARNING
//      Does not call SchedLock()/SchedUnlock()
//
Process_t *SelectSchedNext(void)
{
    if (TimeCritProcs->length > 0) return GetNodeData(TimeCritProcs->first, Process_t *);
    if (ServPrioProcs->length > 0) return GetNodeData(ServPrioProcs->first, Process_t *);
    if (ReglPrioProcs->length > 0) return GetNodeData(ReglPrioProcs->first, Process_t *);
    if (IdlePrioProcs->length > 0) return GetNodeData(IdlePrioProcs->first, Process_t *);

    return NULL;
}

void PrintList(ListHead_t *head);

//
// Remove running process from schedule lists
// and schedule next runnable process
//
void BlockCurProc(void)
{
    // SchedLock();

    KalAssert(GetCurProc() && GetCurProc()->procState == STATE_RUNNING);

    ListNode_t *procNode = GetCurProc()->schedNode;

    GetCurProc()->procState = STATE_BLOCKED;
    RemoveNode(procNode->head, procNode);

    SetCurProc(SelectSchedNext());

    // SchedUnlock();
}

//
// Should we schedule another process?
// Called at each tick
//
void SchedOnTick(void)
{
    Process_t *procNext;
    Process_t *winner;

    //
    // We're either idle or running something
    //
    KalAssert(GetCurProc() == NULL || GetCurProc()->procState == STATE_RUNNING);

    SchedLock();

    //
    // Has current process spent his timeslice?
    // (To be handled in CPU decisions function)
    //
    if (GetCurProc() != NULL) {
        if (GetCurProc()->timeSlice <= 1) {

            // Update process info
            GetCurProc()->timeSlice = DEFAULT_PROC_TIMESLICE;
            GetCurProc()->procState = STATE_RUNNABLE;

            // Remove from list
            RemoveNode(GetCurProc()->schedNode->head, GetCurProc()->schedNode);

            // Add again to list
            SchedThisProc(GetCurProc());

            // Mark as idle
            SetCurProc(NULL);
        }

        //
        // Otherwise, make him lose a tick
        //
        else {
            GetCurProc()->timeSlice--;
        }
    }

    //
    // Are we idle, or scheduling next process?
    //
    if (GetCurProc() == NULL) {
        SetCurProc(SelectSchedNext());
        goto leave;
    }

    //
    // Is there a higher priority process that is runnable?
    //
    procNext = SelectSchedNext();
    winner = CompareProcs(GetCurProc(), procNext);

    //
    // Yes, procNext should preempt current process
    //
    if (winner == procNext) {
        GetCurProc()->procState = STATE_RUNNABLE;
        SchedThisProc(GetCurProc());
        SetCurProc(procNext);
    }

    //
    // Current process won't be preempted and has time remaining
    //
leave:
    SchedUnlock();
}

#define PrintProc(proc) printdbg("{ %d, '%s', %d , %d}\n", (proc)->pid, \
                                 PrioClassesNames[(proc)->prioClass], (proc)->prioLevel, (proc)->timeSlice);

//
// Print out process list
//
void PrintList(ListHead_t *head)
{
    KalAssert(head);

    Process_t *proc;
    ListNode_t *node = head->first;

    printdbg("len: %d\n", head->length);

    while (node) {
        proc = GetNodeData(node, Process_t *);

        PrintProc(proc);

        node = node->next;
    }

    puts("");
}

//
// Initialize scheduler
//
void InitSched(void)
{
    int pid;
    Process_t *proc;

    PrioClassesLock = malloc(sizeof(Lock_t));
    InitLock(PrioClassesLock, KLOCK_SPINLOCK);

    TimeCritProcs = CreateListHeadWithLock(PrioClassesLock, 0);
    ServPrioProcs = CreateListHeadWithLock(PrioClassesLock, 0);
    ReglPrioProcs = CreateListHeadWithLock(PrioClassesLock, 0);
    IdlePrioProcs = CreateListHeadWithLock(PrioClassesLock, 0);

    for (pid = 0; pid < procslen; pid++) {
        if (procs[pid].procState == STATE_RUNNABLE) {
            SchedThisProc(&procs[pid]);
        }
    }
}

//
// Shutdown scheduler
//
void FiniSched(void)
{
    KalAssert(IdlePrioProcs && ReglPrioProcs && ServPrioProcs && TimeCritProcs);

    while (IdlePrioProcs->length > 0) RemoveNode(IdlePrioProcs, IdlePrioProcs->first);
    while (ReglPrioProcs->length > 0) RemoveNode(ReglPrioProcs, ReglPrioProcs->first);
    while (ServPrioProcs->length > 0) RemoveNode(ServPrioProcs, ServPrioProcs->first);
    while (TimeCritProcs->length > 0) RemoveNode(TimeCritProcs, TimeCritProcs->first);

    DestroyListHead(IdlePrioProcs); IdlePrioProcs = NULL;
    DestroyListHead(ReglPrioProcs); ReglPrioProcs = NULL;
    DestroyListHead(ServPrioProcs); ServPrioProcs = NULL;
    DestroyListHead(TimeCritProcs); TimeCritProcs = NULL;

    free((void *)PrioClassesLock);
}

#ifndef _KALEID_KERNEL
int main(void)
{
    InitSched();

    puts("---------------");

    puts("Time Critical:");
    PrintList(TimeCritProcs);

    puts("Server:");
    PrintList(ServPrioProcs);

    puts("Regular:");
    PrintList(ReglPrioProcs);

    puts("Idle:");
    PrintList(IdlePrioProcs);

    puts("---------------");

    getchar();

    int tick = 0;

    while (tick < 20) {
        printf("\nTick %d\n", tick);

        if (GetCurProc() == NULL) {
            puts("Currently IDLE");
        }

        else {
            puts("Currently running process:");
            PrintProc(GetCurProc());
        }

        if (tick == 9 || tick == 14) {
            puts("\nBlocking current process");
            BlockCurProc();
        }

        SchedOnTick();

        puts("\n---------------");
        tick++;
    }

    FiniSched();

    return 0;
}
#endif