/* Copyright (C) 2004 David Decotigny
 
    This program 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 2
    of the License, or (at your option) any later version.
    
    This program 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, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    USA. 
 */
 
 #include <sos/errno.h>
 #include <sos/klibc.h>
 #include <sos/assert.h>
 #include <sos/list.h>
 #include <sos/calcload.h>
 
 #include "sched.h"
 
 
 /**
  * The definition of the scheduler queue. We could have used a normal
  * kwaitq here, it would have had the same properties (regarding
  * priority ordering mainly). But we don't bother with size
  * considerations here (in kwaitq, we had better make the kwaitq
  * structure as small as possible because there are a lot of kwaitq in
  * the system: at least 1 per opened file), so that we can implement a
  * much faster way of handling the prioritized jobs.
  */
 struct sos_sched_queue
 {
   unsigned int nr_threads;
   struct sos_thread *thread_list[SOS_SCHED_NUM_PRIO];
 };
 
 
 /**
  * We manage 2 queues: a queue being scanned for ready threads
  * (active_queue) and a queue to store the threads the threads having
  * expired their time quantuum.
  */
 static struct sos_sched_queue *active_queue, *expired_queue;
 
 
 /**
  * The instances for the active/expired queues
  */
 static struct sos_sched_queue sched_queue[2];
 
 
 /**
  * The array giving the timeslice corresponding to each priority level
  */
 struct sos_time time_slice[SOS_SCHED_NUM_PRIO];
 
 
 sos_ret_t sos_sched_subsystem_setup()
 {
   sos_sched_priority_t prio;
 
   memset(sched_queue, 0x0, sizeof(sched_queue));
   active_queue  = & sched_queue[0];
   expired_queue = & sched_queue[1];
 
   /* pre-compute time slices */
   for (prio = SOS_SCHED_PRIO_TS_HIGHEST ;
        prio <= SOS_SCHED_PRIO_TS_LOWEST ;
        prio ++)
     {
       unsigned int ms;
       ms = SOS_TIME_SLICE_MIN
            + (SOS_TIME_SLICE_MAX - SOS_TIME_SLICE_MIN)
              * (prio - SOS_SCHED_PRIO_TS_HIGHEST)
              / (SOS_SCHED_PRIO_TS_LOWEST - SOS_SCHED_PRIO_TS_HIGHEST);
       time_slice[prio].sec     = ms / 1000;
       time_slice[prio].nanosec = 1000000UL * (ms % 1000);
     }
 
   return SOS_OK;
 }
 
 
 /**
  * Helper function to add a thread in a ready queue AND to change the
  * state of the given thread to "READY".
  *
  * @param insert_at_tail TRUE to tell to add the thread at the end of
  * the ready list. Otherwise it is added at the head of it.
  */
 static sos_ret_t add_in_ready_queue(struct sos_sched_queue *q,
                                     struct sos_thread *thr,
                                     sos_bool_t insert_at_tail)
 {
   sos_sched_priority_t prio;
 
   SOS_ASSERT_FATAL( (SOS_THR_CREATED == thr->state)
                     || (SOS_THR_RUNNING == thr->state) /* Yield */
                     || (SOS_THR_BLOCKED == thr->state) );
 
   /* Add the thread to the CPU queue */
   prio = sos_thread_get_priority(thr);
   if (insert_at_tail)
     list_add_tail_named(q->thread_list[prio], thr,
                         ready.rdy_prev, ready.rdy_next);
   else
     list_add_head_named(q->thread_list[prio], thr,
                         ready.rdy_prev, ready.rdy_next);
   thr->ready.rdy_queue = q;
   q->nr_threads ++;
 
   /* Ok, thread is now really ready to be (re)started */
   thr->state = SOS_THR_READY;
 
   return SOS_OK;
 }
 
 
 sos_ret_t sos_sched_set_ready(struct sos_thread *thr)
 {
   sos_ret_t retval;
 
   /* Don't do anything for already ready threads */
   if (SOS_THR_READY == thr->state)
     return SOS_OK;
 
   /* Reset the CPU time used in the quantuum */
   memset(& thr->user_time_spent_in_slice, 0x0, sizeof(struct sos_time));
 
   if (SOS_SCHED_PRIO_IS_RT(sos_thread_get_priority(thr)))
     {
       /* Real-time thread: schedule it for the present turn */
       retval = add_in_ready_queue(active_queue, thr, TRUE);
     }
   else
     {
       /* Non real-time thread: schedule it for next turn */
       retval = add_in_ready_queue(expired_queue, thr, TRUE);
     }
 
   return retval;
 }
 
 
 sos_ret_t sos_sched_change_priority(struct sos_thread *thr,
                                     sos_sched_priority_t priority)
 {
   struct sos_thread *thread_list;
   SOS_ASSERT_FATAL(SOS_THR_READY == thr->state);
 
   /* Temp variable */
   thread_list
     = thr->ready.rdy_queue->thread_list[sos_thread_get_priority(thr)];
 
   list_delete_named(thread_list, thr, ready.rdy_prev, ready.rdy_next);
 
   /* Update lists */
   thread_list = thr->ready.rdy_queue->thread_list[priority];
   list_add_tail_named(thread_list, thr, ready.rdy_prev, ready.rdy_next);
   thr->ready.rdy_queue->thread_list[priority] = thread_list;
 
   return SOS_OK;
 }
 
 
 /**
  * Helper function to determine whether the current thread expired its
  * time quantuum
  */
 static sos_bool_t
 thread_expired_its_quantuum(struct sos_thread *thr)
 {
   sos_sched_priority_t prio = sos_thread_get_priority(thr);
 
   /* No timesharing/round-robin for "real-time" threads */
   if (SOS_SCHED_PRIO_IS_RT(prio))
     return FALSE;
 
   /* Current (user) thread expired its time quantuum ?  A kernel
      thread never expires because sos_sched_do_timer_tick() below
      won't update its user_time_spent_in_slice */
   if (sos_time_cmp(& thr->user_time_spent_in_slice,
                    & time_slice[prio]) >= 0)
       return TRUE;
 
   return FALSE;
 }
 
 
 struct sos_thread * sos_reschedule(struct sos_thread *current_thread,
                                    sos_bool_t do_yield)
 {
   sos_sched_priority_t prio;
 
   /* Force the current thread to release the CPU if it expired its
      quantuum */
   if (thread_expired_its_quantuum(current_thread))
     {
       /* Reset the CPU time used in the quantuum */
       memset(& current_thread->user_time_spent_in_slice,
              0x0, sizeof(struct sos_time));
 
       do_yield = TRUE;
     }
 
   if (SOS_THR_ZOMBIE == current_thread->state)
     {
       /* Don't think of returning to this thread since it is
          terminated */
       /* Nop */
     }
   else if (SOS_THR_BLOCKED != current_thread->state)
     {
       /* Take into account the current executing thread unless it is
          marked blocked */
       if (do_yield)
         {
           /* Ok, reserve it for next turn */
           if (SOS_SCHED_PRIO_IS_RT(sos_thread_get_priority(current_thread)))
             add_in_ready_queue(active_queue, current_thread, TRUE);
           else
             add_in_ready_queue(expired_queue, current_thread, TRUE);
         }
       else
         {
           /* Put it at the head of the active list */
           add_in_ready_queue(active_queue, current_thread, FALSE);
         }
     }
 
 
   /* Active queue is empty ? */
   if (active_queue->nr_threads <= 0)
     {
       /* Yes: Exchange it with the expired queue */
       struct sos_sched_queue *q;
       q = active_queue;
       active_queue = expired_queue;
       expired_queue = q;
     }
 
   /* Now loop over the priorities in the active queue, looking for a
      non-empty queue */
   for (prio = SOS_SCHED_PRIO_HIGHEST ; prio <= SOS_SCHED_PRIO_LOWEST ; prio ++)
     {
       struct sos_thread *next_thr;
 
       if (list_is_empty_named(active_queue->thread_list[prio],
                               ready.rdy_prev, ready.rdy_next))
         continue;
       
       /* Queue is not empty: take the thread at its head */
       next_thr = list_pop_head_named(active_queue->thread_list[prio],
                                      ready.rdy_prev, ready.rdy_next);
       active_queue->nr_threads --;
 
       return next_thr;
     }
 
 
   SOS_FATAL_ERROR("No kernel thread ready ?!");
   return NULL;
 }
 
 
 sos_ret_t sos_sched_do_timer_tick()
 {
   struct sos_thread *interrupted_thread = sos_thread_get_current();
   struct sos_time tick_duration;
   sos_bool_t cur_is_user;
   sos_ui32_t nb_user_ready = 0;
   sos_ui32_t nb_kernel_ready = 0;
   int prio;
 
   sos_time_get_tick_resolution(& tick_duration);
 
   /* Update the timing statistics */
   if (sos_cpu_context_is_in_user_mode(interrupted_thread->cpu_state))
     {
       cur_is_user = TRUE;
 
       /* User time */
       sos_time_inc(& interrupted_thread->rusage.ru_utime,
                    & tick_duration);
 
       /* Update time spent is current timeslice ONLY for a user thread */
       sos_time_inc(& interrupted_thread->user_time_spent_in_slice,
                    & tick_duration);
     }
   else
     {
       cur_is_user = FALSE;
 
       /* System time */
       sos_time_inc(& interrupted_thread->rusage.ru_stime,
                    & tick_duration);
     }
 
 
   /* Update load stats */
   for (prio = SOS_SCHED_PRIO_HIGHEST ; prio <= SOS_SCHED_PRIO_LOWEST ; prio ++)
     {
       struct sos_thread *thr;
       int nb_thrs;
 
       list_foreach_forward_named(active_queue->thread_list[prio],
                                  thr, nb_thrs,
                                  ready.rdy_prev, ready.rdy_next)
         {
           if (sos_cpu_context_is_in_user_mode(thr->cpu_state))
             nb_user_ready ++;
           else
             nb_kernel_ready ++;
         }
 
       list_foreach_forward_named(expired_queue->thread_list[prio],
                                  thr, nb_thrs,
                                  ready.rdy_prev, ready.rdy_next)
         {
           if (sos_cpu_context_is_in_user_mode(thr->cpu_state))
             nb_user_ready ++;
           else
             nb_kernel_ready ++;
         }
     }
 
   sos_load_do_timer_tick(cur_is_user,
                          nb_user_ready,
                          nb_kernel_ready);
 
   return SOS_OK;
 }