Reduce timeslice for idle task based on wake time of sleeping tasks

RTC: 43738
Change-Id: I91c2bfe57bba04a02dd5169542de8e76e1654ae8
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/1387
Tested-by: Jenkins Server
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

5 files changed, 344 insertions, 226 deletions

diff --git a/src/include/kernel/timemgr.H b/src/include/kernel/timemgr.H
index 96950b928..3f6d658d7 100644
--- a/src/include/kernel/timemgr.H
+++ b/src/include/kernel/timemgr.H
@@ -1,25 +1,26 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/include/kernel/timemgr.H $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/*  IBM_PROLOG_BEGIN_TAG
+ *  This is an automatically generated prolog.
+ *
+ *  $Source: src/include/kernel/timemgr.H $
+ *
+ *  IBM CONFIDENTIAL
+ *
+ *  COPYRIGHT International Business Machines Corp. 2010-2012
+ *
+ *  p1
+ *
+ *  Object Code Only (OCO) source materials
+ *  Licensed Internal Code Source Materials
+ *  IBM HostBoot Licensed Internal Code
+ *
+ *  The source code for this program is not published or other-
+ *  wise divested of its trade secrets, irrespective of what has
+ *  been deposited with the U.S. Copyright Office.
+ *
+ *  Origin: 30
+ *
+ *  IBM_PROLOG_END_TAG
+ */
 #ifndef __KERNEL_TIMEMGR_H
 #define __KERNEL_TIMEMGR_H
 
@@ -48,13 +49,22 @@ class TimeManager
 {
     public:
         enum
-            {
-                /** Number of time-slices to allow per second.
-                 *
-                 *  Context length becomes (1/TIMESLICE_PER_SECOND) sec.
-                 */
-                TIMESLICE_PER_SEC = 1000,
-            };
+        {
+            /** Number of time-slices to allow per second.
+             *
+             *  Context length becomes (1/TIMESLICE_PER_SECOND) sec.
+             */
+            TIMESLICE_PER_SEC = 1000,
+
+            /** Yield Threshold per timeslice
+             *
+             * @note At 512MHZ clock and TIMESLICE_PER_SEC = 1000,
+             *   Timeslice = 512000 ticks.
+             * If threshold/slice = 100 then threhold = 5120 ticks
+             * FYI, a Context switch ~ 476 ticks
+             */
+            YIELD_THRESHOLD_PER_SLICE = 100,    // 1%
+        };
 
             /** Initialize the time subsystem. */
         static void init();
@@ -68,6 +78,21 @@ class TimeManager
                 return iv_timebaseFreq / TIMESLICE_PER_SEC;
             };
 
+        /**
+         * Return the number of ticks for an idle time-slice
+         */
+        static uint64_t getIdleTimeSliceCount();
+
+        /**
+         * Perform a simple delay if the time is below the yield threshold.
+         *
+         * @param[in] sec, Delay time in seconds
+         * @param[in] nsec, Delay time in nano seconds
+         * @return false if the delay requires a task yield | true - The
+         * requested delay was performed by this routine.
+         */
+        static bool simpleDelay(uint64_t sec, uint64_t nsec);
+
             /** Returns the value of the processor timebase register. */
         static uint64_t getCurrentTimeBase()
             {
@@ -117,7 +142,7 @@ class TimeManager
         void _init_cpu(cpu_t* cpu);
         void _delayTask(task_t* t, uint64_t i_sec, uint64_t i_nsec);
         void _checkReleaseTasks(Scheduler* s);
-        inline delaylist_t* _get_delaylist();
+        static delaylist_t* _get_delaylist();
 
         /** Frequency of the timebase register in Hz. (ticks per second) */
         static uint64_t iv_timebaseFreq;
diff --git a/src/include/util/locked/pqueue.H b/src/include/util/locked/pqueue.H
index 8e21a01d8..2a6324fe6 100644
--- a/src/include/util/locked/pqueue.H
+++ b/src/include/util/locked/pqueue.H
@@ -1,25 +1,26 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/include/util/locked/pqueue.H $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/*  IBM_PROLOG_BEGIN_TAG
+ *  This is an automatically generated prolog.
+ *
+ *  $Source: src/include/util/locked/pqueue.H $
+ *
+ *  IBM CONFIDENTIAL
+ *
+ *  COPYRIGHT International Business Machines Corp. 2010-2012
+ *
+ *  p1
+ *
+ *  Object Code Only (OCO) source materials
+ *  Licensed Internal Code Source Materials
+ *  IBM HostBoot Licensed Internal Code
+ *
+ *  The source code for this program is not published or other-
+ *  wise divested of its trade secrets, irrespective of what has
+ *  been deposited with the U.S. Copyright Office.
+ *
+ *  Origin: 30
+ *
+ *  IBM_PROLOG_END_TAG
+ */
 #ifndef __UTIL_LOCKED_PQUEUE_H
 #define __UTIL_LOCKED_PQUEUE_H
 
@@ -29,108 +30,146 @@ namespace Util
 {
     namespace Locked
     {
-	template <typename _T, typename _K,
-		  bool locked = false, typename _S = int>
-	class PQueue : public Queue<_T, locked, _S>
-	{
-	    public:
-		void insert(_T*);
-		_T* remove_if(_K&);
-
-	    private:
-		void bubbleUp(_T*);
-	};
-
-	template <typename _T, typename _K, bool locked, typename _S>
-	void PQueue<_T,_K,locked,_S>::insert(_T* item)
-	{
-	    this->__lock();
-
-	    if (this->head == NULL)
-	    {
-		item->next = item->prev = NULL;
-		this->head = this->tail = item;
-	    }
-	    else
-	    {
-		item->prev = NULL;
-		item->next = this->head;
-		this->head = this->head->prev = item;
-
-		bubbleUp(item);
-	    }
-
-	    this->__unlock();
-	}
-
-	template <typename _T, typename _K, bool locked, typename _S>
-	_T* PQueue<_T,_K,locked,_S>::remove_if(_K& key)
-	{
-	    _T* item = NULL;
-
-	    this->__lock();
-
-	    if ((this->tail != NULL) && (this->tail->key <= key))
-	    {
-		item = this->tail;
-		if (this->head == this->tail)
-		    this->head = this->tail = NULL;
-		else
-		    this->tail = item->prev;
+        template <typename _T, typename _K,
+                 bool locked = false, typename _S = int>
+            class PQueue : public Queue<_T, locked, _S>
+            {
+                public:
+                    void insert(_T*);
+                    _T* remove_if(_K&);
+                    _T* front();
+
+                private:
+                    void bubbleUp(_T*);
+            };
+
+        // SFINAE template to ensure compile fails if functions which are not
+        // SMP-safe are used on a 'locked' instance.
+        template<bool locked>
+            class __verify_pqueue_is_smp_safe
+            {
+                public:
+                    __verify_pqueue_is_smp_safe()
+                    {
+                        class __util_locked_pqueue_is_not_smp_safe;
+                        __util_locked_pqueue_is_not_smp_safe();
+                    }
+            };
+
+        // SFINAE template implementation to allow certain functions when the
+        // instance is not 'locked', assuming that caller is ensuring safety
+        // in some other way.
+        template<>
+            class __verify_pqueue_is_smp_safe<false>
+            {
+                public:
+                    __verify_pqueue_is_smp_safe()
+                    {
+                    }
+            };
+
+
+        template <typename _T, typename _K, bool locked, typename _S>
+            void PQueue<_T,_K,locked,_S>::insert(_T* item)
+            {
+                this->__lock();
+
+                if (this->head == NULL)
+                {
+                    item->next = item->prev = NULL;
+                    this->head = this->tail = item;
+                }
+                else
+                {
+                    item->prev = NULL;
+                    item->next = this->head;
+                    this->head = this->head->prev = item;
+
+                    bubbleUp(item);
+                }
+
+                this->__unlock();
+            }
+
+        template <typename _T, typename _K, bool locked, typename _S>
+            _T* PQueue<_T,_K,locked,_S>::remove_if(_K& key)
+            {
+                _T* item = NULL;
+
+                this->__lock();
+
+                if ((this->tail != NULL) && (this->tail->key <= key))
+                {
+                    item = this->tail;
+                    if (this->head == this->tail)
+                        this->head = this->tail = NULL;
+                    else
+                        this->tail = item->prev;
+
+                    if (item->prev)
+                        item->prev->next = NULL;
+                }
+
+                this->__unlock();
+
+                return item;
+            }
+
+
+        template <typename _T, typename _K, bool locked, typename _S>
+            void PQueue<_T,_K,locked,_S>::bubbleUp(_T* item)
+            {
+                if (!item->next)
+                    return;
+
+                if (item->next->key <= item->key)
+                    return;
+
+                if (this->head == item)
+                    this->head = item->next;
+                if (this->tail == item->next)
+                    this->tail = item;
+
+                _T* temp = item->next;
+
+                if (temp->next)
+                {
+                    temp->next->prev = item;
+                    item->next = item->next->next;
+                }
+                else
+                {
+                    item->next = NULL;
+                }
 
                 if (item->prev)
-                    item->prev->next = NULL;
-	    }
-
-	    this->__unlock();
-
-	    return item;
-	}
-
-
-	template <typename _T, typename _K, bool locked, typename _S>
-	void PQueue<_T,_K,locked,_S>::bubbleUp(_T* item)
-	{
-	    if (!item->next)
-		return;
-
-	    if (item->next->key <= item->key)
-		return;
-
-	    if (this->head == item)
-		this->head = item->next;
-	    if (this->tail == item->next)
-		this->tail = item;
-
-	    _T* temp = item->next;
-
-	    if (temp->next)
-	    {
-		temp->next->prev = item;
-		item->next = item->next->next;
-	    }
-	    else
-	    {
-		item->next = NULL;
-	    }
-
-	    if (item->prev)
-	    {
-		item->prev->next = temp;
-		temp->prev = item->prev;
-	    }
-	    else
-	    {
-		temp->prev = NULL;
-	    }
-
-	    temp->next = item;
-	    item->prev = temp;
-
-	    bubbleUp(item);
-	}
-
-
+                {
+                    item->prev->next = temp;
+                    temp->prev = item->prev;
+                }
+                else
+                {
+                    temp->prev = NULL;
+                }
+
+                temp->next = item;
+                item->prev = temp;
+
+                bubbleUp(item);
+            }
+
+
+        template <typename _T, typename _K, bool locked, typename _S>
+        _T* PQueue<_T, _K,locked,_S>::front()
+        {
+            // Entirely not SMP-safe to return a pointer to a node if
+            // we are a locking instance.  If we aren't locking we
+            // have to assume that the caller is ensuring SMP-safety
+            // globally in some other way.  Use SFINAE technique to
+            // ensure front() fails on locked lists.
+            __verify_pqueue_is_smp_safe<locked>();
+            return this->tail;
+        }
     };
 };
 
diff --git a/src/kernel/scheduler.C b/src/kernel/scheduler.C
index 10dda6708..c545eb45a 100644
--- a/src/kernel/scheduler.C
+++ b/src/kernel/scheduler.C
@@ -1,25 +1,26 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/kernel/scheduler.C $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/*  IBM_PROLOG_BEGIN_TAG
+ *  This is an automatically generated prolog.
+ *
+ *  $Source: src/kernel/scheduler.C $
+ *
+ *  IBM CONFIDENTIAL
+ *
+ *  COPYRIGHT International Business Machines Corp. 2010-2012
+ *
+ *  p1
+ *
+ *  Object Code Only (OCO) source materials
+ *  Licensed Internal Code Source Materials
+ *  IBM HostBoot Licensed Internal Code
+ *
+ *  The source code for this program is not published or other-
+ *  wise divested of its trade secrets, irrespective of what has
+ *  been deposited with the U.S. Copyright Office.
+ *
+ *  Origin: 30
+ *
+ *  IBM_PROLOG_END_TAG
+ */
 #include <kernel/task.H>
 #include <kernel/scheduler.H>
 #include <kernel/taskmgr.H>
@@ -39,8 +40,8 @@ void Scheduler::addTask(task_t* t)
         if (0 != t->affinity_pinned)
         {
             // Allocate a per-CPU queue if this is the first pinning to CPU.
-            Util::Lockfree::atomic_construct(
-                    reinterpret_cast<Runqueue_t**>(&t->cpu->scheduler_extra));
+            Util::Lockfree::atomic_construct
+                (reinterpret_cast<Runqueue_t**>(&t->cpu->scheduler_extra));
 
             // Insert into queue.
             static_cast<Runqueue_t*>(t->cpu->scheduler_extra)->insert(t);
@@ -48,7 +49,7 @@ void Scheduler::addTask(task_t* t)
         // Not pinned, add to global run-queue.
         else
         {
-	    iv_taskList.insert(t);
+            iv_taskList.insert(t);
         }
     }
 }
@@ -96,9 +97,8 @@ void Scheduler::setNextRunnable()
     // Choose idle task if no other ready task is available.
     if (NULL == t)
     {
-	t = cpu->idle_task;
-	// TODO: Set short decrementer.
-        setDEC(TimeManager::getTimeSliceCount());
+        t = cpu->idle_task;
+        setDEC(TimeManager::getIdleTimeSliceCount());
     }
     else // Set normal timeslice to decrementer.
     {
diff --git a/src/kernel/timemgr.C b/src/kernel/timemgr.C
index 36d89ee30..32ffa4a68 100644
--- a/src/kernel/timemgr.C
+++ b/src/kernel/timemgr.C
@@ -1,25 +1,26 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/kernel/timemgr.C $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/*  IBM_PROLOG_BEGIN_TAG
+ *  This is an automatically generated prolog.
+ *
+ *  $Source: src/kernel/timemgr.C $
+ *
+ *  IBM CONFIDENTIAL
+ *
+ *  COPYRIGHT International Business Machines Corp. 2010-2012
+ *
+ *  p1
+ *
+ *  Object Code Only (OCO) source materials
+ *  Licensed Internal Code Source Materials
+ *  IBM HostBoot Licensed Internal Code
+ *
+ *  The source code for this program is not published or other-
+ *  wise divested of its trade secrets, irrespective of what has
+ *  been deposited with the U.S. Copyright Office.
+ *
+ *  Origin: 30
+ *
+ *  IBM_PROLOG_END_TAG
+ */
 #include <kernel/timemgr.H>
 #include <kernel/scheduler.H>
 #include <util/singleton.H>
@@ -105,7 +106,55 @@ void TimeManager::_checkReleaseTasks(Scheduler* s)
     }
 }
 
-inline TimeManager::delaylist_t* TimeManager::_get_delaylist()
+TimeManager::delaylist_t* TimeManager::_get_delaylist()
 {
     return static_cast<delaylist_t*>(CpuManager::getCurrentCPU()->delay_list);
 }
+
+uint64_t TimeManager::getIdleTimeSliceCount()
+{
+    uint64_t sliceCount = getTimeSliceCount();
+
+    // Get a delayed task, if there is one
+    _TimeManager_Delay_t* node = _get_delaylist()->front();
+
+    if(node)
+    {
+        uint64_t currentTime = getCurrentTimeBase();
+        if(currentTime < node->key)
+        {
+            uint64_t diffTime = node->key - currentTime;
+            if(diffTime < sliceCount)
+            {
+                sliceCount = diffTime;
+            }
+        }
+        else  // ready to run now! Minimum delay
+        {
+            sliceCount = 1;
+        }
+    }
+    return sliceCount;
+}
+
+bool TimeManager::simpleDelay(uint64_t i_sec, uint64_t i_nsec)
+{
+    bool result = false;
+
+    uint64_t threshold = getTimeSliceCount()/YIELD_THRESHOLD_PER_SLICE;
+    uint64_t delay = convertSecToTicks(i_sec, i_nsec);
+
+    if(delay < threshold)
+    {
+        uint64_t expire = getCurrentTimeBase() + delay;
+        while(getCurrentTimeBase() < expire)
+        {
+            setThreadPriorityLow();
+        }
+        setThreadPriorityHigh();
+        result = true;
+    }
+
+    return result;
+}
+
diff --git a/src/lib/syscall_time.C b/src/lib/syscall_time.C
index 819b605b0..2fb56cb68 100644
--- a/src/lib/syscall_time.C
+++ b/src/lib/syscall_time.C
@@ -1,25 +1,26 @@
-//  IBM_PROLOG_BEGIN_TAG
-//  This is an automatically generated prolog.
-//
-//  $Source: src/lib/syscall_time.C $
-//
-//  IBM CONFIDENTIAL
-//
-//  COPYRIGHT International Business Machines Corp. 2010 - 2011
-//
-//  p1
-//
-//  Object Code Only (OCO) source materials
-//  Licensed Internal Code Source Materials
-//  IBM HostBoot Licensed Internal Code
-//
-//  The source code for this program is not published or other-
-//  wise divested of its trade secrets, irrespective of what has
-//  been deposited with the U.S. Copyright Office.
-//
-//  Origin: 30
-//
-//  IBM_PROLOG_END
+/*  IBM_PROLOG_BEGIN_TAG
+ *  This is an automatically generated prolog.
+ *
+ *  $Source: src/lib/syscall_time.C $
+ *
+ *  IBM CONFIDENTIAL
+ *
+ *  COPYRIGHT International Business Machines Corp. 2010-2012
+ *
+ *  p1
+ *
+ *  Object Code Only (OCO) source materials
+ *  Licensed Internal Code Source Materials
+ *  IBM HostBoot Licensed Internal Code
+ *
+ *  The source code for this program is not published or other-
+ *  wise divested of its trade secrets, irrespective of what has
+ *  been deposited with the U.S. Copyright Office.
+ *
+ *  Origin: 30
+ *
+ *  IBM_PROLOG_END_TAG
+ */
 #include <time.h>
 #include <sys/time.h>
 #include <sys/syscall.h>
@@ -30,7 +31,11 @@ using namespace Systemcalls;
 
 void nanosleep(uint64_t sec, uint64_t nsec)
 {
-    _syscall2(TIME_NANOSLEEP, (void*)sec, (void*)nsec);
+    // If the delay is short then simpleDelay() will perform the delay
+    if(unlikely(!TimeManager::simpleDelay(sec, nsec)))
+    {
+        _syscall2(TIME_NANOSLEEP, (void*)sec, (void*)nsec);
+    }
 }
 
 int clock_gettime(clockid_t clk_id, timespec_t* tp)