/* scheduler.c - Scheduler implementation.
   Copyright (C) 2009 Free Software Foundation, Inc.
   Written by Neal H. Walfield <neal@gnu.org>.

   This file is part of the GNU Hurd.

   The GNU Hurd is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 3 of the
   License, or (at your option) any later version.

   The GNU Hurd is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see
   <http://www.gnu.org/licenses/>.  */

#include "scheduler.h"
#include "thread.h"
#include "vm.h"
#include "debug.h"
#include "timer.h"

/* Set to 0 to show the thread state transitions.  */
#define SHOW_THREAD_STATE_TRANSITIONS 5

/* 100 milliseconds.  */
#define TS (100 * 1000 * 1000)

struct thread *current_thread;
/* When CURRENT_THREAD was scheduled.  */
static uint64_t quantum_start;

static struct thread_queue_list run_queue;
static struct thread_queue_list no_time_queue;

static void
thread_remove_from_run_queue (struct thread *thread)
{
  assertx (thread->state == THREAD_RUNNABLE,
	   "%s", thread_state_string (thread->state));

  if (thread->time > 0)
    thread_queue_list_unlink (&run_queue, thread);
  else
    thread_queue_list_unlink (&no_time_queue, thread);
}

static void
thread_add_to_run_queue (struct thread *thread)
{
  assert (thread->state != THREAD_RUNNABLE);

  if (thread->time > 0)
    thread_queue_list_enqueue (&run_queue, thread);
  else
    thread_queue_list_enqueue (&no_time_queue, thread);

  thread->state = THREAD_RUNNABLE;
}

/* The tick the last time allowances were distributed.  */
static uint64_t last_payout;

static void
deschedule_current_thread (bool suspend)
{
  assert (current_thread);
  assert (current_thread->state == THREAD_RUNNING
	  || current_thread->state == THREAD_SUSPENDED);

  int delta = time_data.ns_since_boot - quantum_start;
  current_thread->time -= delta;
  current_thread->total_time += delta;
  if (suspend || current_thread->state == THREAD_SUSPENDED)
    {
      debug (SHOW_THREAD_STATE_TRANSITIONS, OBJECT_NAME_FMT ": %s -> %s",
	     OBJECT_NAME_PRINTF ((struct vg_object *) current_thread),
	     thread_state_string (current_thread->state),
	     thread_state_string (THREAD_SUSPENDED));

      current_thread->state = THREAD_SUSPENDED;
    }
  else if (current_thread->state == THREAD_RUNNING)
    {
      debug (SHOW_THREAD_STATE_TRANSITIONS, OBJECT_NAME_FMT ": %s -> %s",
	     OBJECT_NAME_PRINTF ((struct vg_object *) current_thread),
	     thread_state_string (current_thread->state),
	     thread_state_string (THREAD_RUNNABLE));

      thread_add_to_run_queue (current_thread);
    }

  current_thread = NULL;
}

void
schedule (struct thread *thread)
{
  if (likely (current_thread))
    /* See if the current thread has exceeded its allowance.  */
    {
      if (current_thread->state == THREAD_SUSPENDED)
	deschedule_current_thread (true);
      else if (unlikely ((int64_t) time_data.ns_since_boot - quantum_start
			 >= (int64_t) current_thread->time))
	{
	  assert (current_thread->state == THREAD_RUNNING);

	  debug (5, OBJECT_NAME_FMT ": Quantum up.",
		 OBJECT_NAME_PRINTF ((struct vg_object *) current_thread));
	  deschedule_current_thread (false);
	}
    }

  if (likely (! thread && current_thread))
    /* We don't have to switch and the current thread hasn't exceed
       its allowance.  Keep it on the CPU.  */
    return;

  if (thread)
    /* The caller specified a thread to run.  Use it.  */
    {
      assert (thread->state == THREAD_RUNNABLE
	      || thread->state == THREAD_SUSPENDED);

      if (thread->state == THREAD_RUNNABLE)
	thread_remove_from_run_queue (thread);
    }

  if (! thread)
    /* The caller didn't specify a thread to run.  Dequeue the next
       thread thread from the run queue.  */
    {
      thread = thread_queue_list_dequeue (&run_queue);
      if (thread)
	assert (thread->state == THREAD_RUNNABLE);
    }

  if (! thread)
    /* It seems that there are no threads on the run queue.  Refill
       all ready threads' allowances and move them to the run
       queue.  */
    {
      debug (5, "Allocating time at %ld.", time_data.ns_since_boot);

      assert (! current_thread);
      assert (! thread_queue_list_head (&run_queue));

      last_payout = time_data.ns_since_boot;

      struct thread *t;
      for (t = thread_queue_list_head (&no_time_queue);
	   t;
	   t = thread_queue_list_next (t))
	{
	  assert (t->state == THREAD_RUNNABLE);

	  assert (t->time <= 0);

	  t->time += TS;
	  if (t->time > TS + TS / 2)
	    /* Can hold over at most half a time slice.  */
	    t->time = TS + TS / 2;
	  if (t->time < TS / 10)
	    /* The minimum is a tenth of a slice. */
	    t->time = TS / 10;

	  t->last_payout = last_payout;
	}

      thread_queue_list_move (&run_queue, &no_time_queue);

      thread = thread_queue_list_dequeue (&run_queue);
    }

  /* Remove the current thread from the CPU.  */
  if (current_thread)
    {
      assert (thread);

      deschedule_current_thread (false);
    }

  if (! thread)
    return;

  if (thread->state != THREAD_RUNNING)
    {
      debug (SHOW_THREAD_STATE_TRANSITIONS, OBJECT_NAME_FMT ": %s -> %s",
	     OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	     thread_state_string (thread->state),
	     thread_state_string (THREAD_RUNNING));

      debug (5, OBJECT_NAME_FMT ": Scheduling (ip: %p) (%d ready).",
	     OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	     thread_ip (thread),
	     thread_queue_list_count (&run_queue)
	     + thread_queue_list_count (&no_time_queue));
    }

  quantum_start = time_data.ns_since_boot;

  /* Mark THREAD as running.  */
  thread->state = THREAD_RUNNING;

  vm_as_install (thread);
  current_thread = thread;
}

void
thread_make_runnable (struct thread *thread)
{
  if (thread->state == THREAD_RUNNABLE
      || thread->state == THREAD_RUNNING)
    return;
  assert (thread->state == THREAD_SUSPENDED);

  enum thread_state new
    = thread == current_thread ? THREAD_RUNNING : THREAD_RUNNABLE;
  debug (SHOW_THREAD_STATE_TRANSITIONS, OBJECT_NAME_FMT ": %s -> %s",
	 OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	 thread_state_string (thread->state),
	 thread_state_string (new));

  if (thread == current_thread)
    thread->state = THREAD_RUNNING;
  else
    {
      if (thread->last_payout != last_payout)
	{
	  thread->time = TS;
	  thread->last_payout = last_payout;
	}

      thread_add_to_run_queue (thread);
    }
}

void
thread_suspend (struct thread *thread)
{
  if (thread->state == THREAD_SUSPENDED)
    return;
  assert (thread->state == THREAD_RUNNABLE
	  || thread->state == THREAD_RUNNING);

  debug (SHOW_THREAD_STATE_TRANSITIONS, OBJECT_NAME_FMT ": %s -> %s",
	 OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	 thread_state_string (thread->state),
	 thread_state_string (THREAD_SUSPENDED));

  switch (thread->state)
    {
    case THREAD_RUNNING:
      assert (current_thread == thread);
      /* Mark it as suspended.  At the next reschedule, it will be
	 really removed from the CPU (unless it is not marked as
	 runnable in the mean time!).  */
      break;

    case THREAD_RUNNABLE:
      assert (current_thread != thread);
      thread_remove_from_run_queue (thread);
      break;
    }

  thread->state = THREAD_SUSPENDED;
}

static void
run_queue_dump (int argc, char *argv[])
{
  printf ("Current thread: ");
  if (current_thread)
    printf (OBJECT_NAME_FMT,
	    OBJECT_NAME_PRINTF ((struct vg_object *) current_thread));
  else
    printf ("NULL");
  putchar ('\n');

  struct thread *thread;
  for (thread = thread_queue_list_head (&run_queue);
       thread;
       thread = thread_queue_list_next (thread))
    printf (OBJECT_NAME_FMT"%s",
	    OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	    thread_queue_list_next (thread) ? ", " : "\n");

  for (thread = thread_queue_list_head (&no_time_queue);
       thread;
       thread = thread_queue_list_next (thread))
    printf (OBJECT_NAME_FMT"%s",
	    OBJECT_NAME_PRINTF ((struct vg_object *) thread),
	    thread_queue_list_next (thread) ? ", " : "\n");
}

static struct debug_command debug_command =
  {
    "run-queue",
    'q',
    "Print the threads on the run queue.",
    run_queue_dump,
  };

void
scheduler_bootstrap (void)
{
  debug_register (&debug_command);
}