ThreadPool

Change-Id: I09bf867a2dbb45e063e4785f5b2b1f705fae72c8
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/680
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Bradley W. Bishop <bradleyb@us.ibm.com>
Reviewed-by: Terry J. Opie <opiet@us.ibm.com>
Reviewed-by: MIKE J. JONES <mjjones@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

6 files changed, 615 insertions, 0 deletions

diff --git a/src/include/algorithm b/src/include/algorithm
index 2537a3b53..0c94c82ae 100644
--- a/src/include/algorithm
+++ b/src/include/algorithm
@@ -176,6 +176,68 @@ namespace std
 
         return last;
     }
+
+
+    /**
+     * Find the minimum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     *
+     * Returns the first element (i) such that (*j) < (*i) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator>
+    inline FwdIterator min_element(FwdIterator first, FwdIterator last)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if ((*first) < (*e)) 
+            {
+                e = first;
+            }
+            first++;
+        }
+        return e;
+    }
+
+    /**
+     * Find the minimum element within a range.
+     * @param[in] first - FwdIterator to the first position in the range.
+     * @param[in] last - FwdIterator to the last position in the range.
+     * @param[in] comp - BinaryPredicate used to perform comparison.
+     *
+     * Returns the first element (i) such that comp(*j,*i) is false for all
+     * other iterators.
+     *
+     * The iterator last is returned only when the range contains no elements.
+     *
+     * @return An iterator in [first, last) containing the minimum element.
+     *
+     */
+    template <typename FwdIterator, typename BinaryPredicate>
+    inline FwdIterator min_element(FwdIterator first, FwdIterator last, 
+                                   BinaryPredicate comp)
+    {
+        if (first == last) return last;
+        FwdIterator e = first++;
+        while(first != last)
+        {
+            if (comp((*first),(*e)))
+            {
+                e = first;
+            }
+            first++;
+        }
+        return e;
+    }
+
 };
 #endif
 
diff --git a/src/include/usr/initservice/initsvcreasoncodes.H b/src/include/usr/initservice/initsvcreasoncodes.H
index 077aedabf..c22e59ffe 100644
--- a/src/include/usr/initservice/initsvcreasoncodes.H
+++ b/src/include/usr/initservice/initsvcreasoncodes.H
@@ -67,6 +67,7 @@ enum    InitServiceModuleID
     START_SPD_ERRL_ID                   =   0x1B,
     START_FAPIPOREVE_ERRL_ID            =   0x1C,
     START_POREVE_ERRL_ID                =   0x1D,
+    START_UTIL_ERRL_ID                  =   0x1E,
 
     //  Internal InitService codes
     INITSVC_START_TASK_MOD_ID           =   0x20,
diff --git a/src/include/usr/util/impl/threadpool.H b/src/include/usr/util/impl/threadpool.H
new file mode 100644
index 000000000..8490bb5d6
--- /dev/null
+++ b/src/include/usr/util/impl/threadpool.H
@@ -0,0 +1,202 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/impl/threadpool.H $
+//
+//  IBM CONFIDENTIAL
+//
+//  COPYRIGHT International Business Machines Corp. 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
+#ifndef __UTIL_IMPL_THREADPOOL_H
+#define __UTIL_IMPL_THREADPOOL_H
+
+/** @file threadpool.H
+ *
+ *  Contains the (mostly) untemplatized implementation details of the
+ *  threadpool.
+ *
+ *  The idea is that Util::ThreadPool is a templatized class to give the
+ *  user flexibility but most of the details are implemented in a
+ *  non-templatized way to conserve space.  When Util::ThreadPool<T> is
+ *  instantiated there is only a small amount of code that is unique to T.
+ */
+
+#include <list>
+#include <algorithm>
+#include <sys/sync.h>
+#include <sys/task.h>
+
+namespace Util
+{
+
+namespace __Util_ThreadPool_Impl
+{
+    /**
+     *  Export the container types used in the internal ThreadPool
+     *  implementation.
+     *
+     *  The ThreadPoolImpl here is going to operate on a container of void*'s,
+     *  but the templatized code is going to assume it is operating on a
+     *  container of T*'s.  Since an iterator<void*> and iterator<T*> have the
+     *  same behavior, we provide this template here so that the real
+     *  ThreadPool can use the same iterators by typename without knowing if
+     *  they are stored in a list, vector, etc.
+     */
+    template <typename _T>
+    struct ThreadPoolImplContainer
+    {
+        typedef std::list<_T*> worklist_t;
+        typedef typename std::list<_T*>::iterator worklist_itr_t;
+    };
+
+    /**
+     *  Internal implementation of the thread pool.
+     */
+    class ThreadPoolImpl
+    {
+        public:
+                /** Worklist container type. */
+            typedef ThreadPoolImplContainer<void>::worklist_t worklist_t;
+                /** Worklist container iterator type. */
+            typedef ThreadPoolImplContainer<void>::worklist_itr_t
+                        worklist_itr_t;
+
+                /** Typedef of function pointer passed to "start". */
+            typedef void(*start_fn_t)(void*);
+                /** Typedef of function poitner passed to "remove". */
+            typedef
+                worklist_itr_t(*order_fn_t)(worklist_itr_t, worklist_itr_t);
+
+                /** Simple constructor, call __init to avoid the in-charge and
+                 *  not-in-charge construction costs. */
+            ThreadPoolImpl() { __init(); };
+
+        protected:
+                /** Initialize the object. */
+            void __init();
+                /** Insert a work-item onto the work-queue. */
+            void __insert(void*);
+                /** Remove the next work item from the work-queue.
+                 *
+                 *  Called by worker threads to find the next piece of work.
+                 *
+                 *  @param[in] fn - Function to use to order the work by
+                 *                  priority.
+                 */
+            void* __remove(order_fn_t fn);
+
+                /** Start the thread-pool.
+                 *
+                 *  @param[in] fn - Function to use as the thread entry-point.
+                 *  @param[in] instance - "this" to pass to worker threads.
+                 */
+            void __start(start_fn_t fn, void* instance);
+                /** Stop the thread-pool. */
+            void __shutdown();
+
+                /** Outstanding work-list. */
+            worklist_t iv_worklist;
+                /** Mutex to protect insert / remove. */
+            mutex_t iv_mutex;
+                /** Condition variable to block on empty. */
+            sync_cond_t iv_condvar;
+
+                /** List of worker threads created, to use for joining on
+                 *  shutdown */
+            std::list<tid_t> iv_children;
+                /** State of object. */
+            bool iv_shutdown;
+
+    };
+
+        /** Prototype of 'search' functor against a threadpool. */
+    template <typename _T, bool nonfifo> struct ThreadPoolWorklistSearch;
+
+    /**
+     *  Template specialization of the threadpool search functor for FIFO order.
+     */
+    template <typename _T>
+    struct ThreadPoolWorklistSearch<_T, false>
+    {
+        /**
+         * Returns the next workitem out of a threadpool list.
+         *
+         * Since this is the FIFO specialization, this should just return
+         * the next item in the list.
+         *
+         * @param[in] begin - Iterator to the beginning of the list.
+         * @param[in] end - Iterator to the end of the list.
+         *
+         * @return begin
+         */
+        static typename ThreadPoolImplContainer<_T>::worklist_itr_t
+            search(typename ThreadPoolImplContainer<_T>::worklist_itr_t begin,
+                   typename ThreadPoolImplContainer<_T>::worklist_itr_t end)
+        {
+            return begin;
+        }
+    };
+
+    /**
+     * Functor which performs (*a < *b).
+     *
+     * Since the items in a worklist are (WorkItem*)'s, they need to be
+     * dereferenced prior to comparison.  This functor performs the
+     * dereference and comparison operation.
+     */
+    template <typename _T>
+    struct DerefLessCompare
+    {
+        bool operator()(_T* a, _T* b)
+        {
+            return ((*a) < (*b));
+        }
+    };
+
+    /**
+     *  Template specialiation of the threadpool search functor for non-FIFO
+     *  order.
+     */
+    template <typename _T>
+    struct ThreadPoolWorklistSearch<_T, true>
+    {
+        /**
+         * Returns the next workitem out of a threadpool list.
+         *
+         * Since this is the non-FIFO specialization, this should return the
+         * minimum workitem.
+         *
+         * @param[in] begin - Iterator to the beginning of the list.
+         * @param[in] end - Iterator to the end of the list.
+         *
+         * @return Iterator pointing to the minimum entry in the list.
+         */
+        static typename ThreadPoolImplContainer<_T>::worklist_itr_t
+            search(typename ThreadPoolImplContainer<_T>::worklist_itr_t begin,
+                   typename ThreadPoolImplContainer<_T>::worklist_itr_t end)
+        {
+            return std::min_element(begin,end,
+                                    DerefLessCompare<_T>());
+        }
+    };
+
+};
+
+
+};
+
+
+#endif
diff --git a/src/include/usr/util/threadpool.H b/src/include/usr/util/threadpool.H
new file mode 100644
index 000000000..4d28800fb
--- /dev/null
+++ b/src/include/usr/util/threadpool.H
@@ -0,0 +1,178 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/threadpool.H $
+//
+//  IBM CONFIDENTIAL
+//
+//  COPYRIGHT International Business Machines Corp. 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
+#ifndef __UTIL_THREADPOOL_H
+#define __UTIL_THREADPOOL_H
+
+/** @file threadpool.H
+ *  @brief Defines the interfaces for a thread-pool.
+ *
+ *  Provides two classes, one of which is templatized: ThreadPool and
+ *  ThreadPoolManager.
+ *
+ *  ThreadPool is an implementation of a thread-pool.  It accepts a template
+ *  parameter of the class describing the work that can be done by this
+ *  thread-pool.  The only requirement is that this class provides an
+ *  operator().
+ *
+ *  The default behavior of the ThreadPool is to be a FIFO.  If the desire is
+ *  for the ThreadPool to operate in a non-FIFO manner then the work item
+ *  class must support less-than comparison.  The pool will then execute the
+ *  oldest work item (a) such that all other work items (b) have:
+ *      (false == (b < a))
+ *
+ *  Work Item Prototypes:
+ *      void operator()() { ... execute work ... }
+ *      bool operator<(const WorkItem& rhs);
+ *
+ *  ThreadPoolManager can be used to globally control the number of threads
+ *  started when a new thread pool is started.  The intent of this class is
+ *  that the maximum number of threads will be adjusted by an the IPL step
+ *  management based on the phase of the IPL we are in.  When we are cache
+ *  contained the number should be kept lower and when we exit cache contained
+ *  we can allow much more parallelism.
+ *
+ */
+
+#include <stdint.h>
+#include <util/traits/has_lessthan.H>
+#include <util/impl/threadpool.H>
+
+namespace Util
+{
+
+/**
+ * @brief Definition of the thread pool.
+ *
+ * @param[in] WorkItem - The class to accept as the work.
+ *
+ * The thread-pool will execute the operator() on WorkItems.  Work will be done
+ * in a FIFO manner unless the < comparison works on the WorkItems, in which
+ * case the oldest WorkItem for which all other work items fail (b<a) will be
+ * processed.
+ *
+ * The thread-pool will only create worker threads once the 'start' operation
+ * has been called.  When the 'shutdown' operation is called, the thread-pool
+ * will complete its outstanding work and destroy all children worker threads.
+ *
+ * @note The thread-safety of this object ensures that it is self-consistent
+ *       between insert and worker-thread operations but does not protect
+ *       against multiple threads calling the start / shutdown operations.
+ *       Multiple threads may insert safely but only one thread should be
+ *       responsible for the state management.
+ */
+template <typename WorkItem>
+class ThreadPool : public Util::__Util_ThreadPool_Impl::ThreadPoolImpl
+{
+    public:
+            /** Basic Constructor.  Initialize ThreadPool. */
+        ThreadPool() : Util::__Util_ThreadPool_Impl::ThreadPoolImpl() { };
+            /** Basic Destructor.  Ensures pool is properly shut down. */
+        ~ThreadPool() { shutdown(); };
+
+            /** @brief Creates worker threads and begins processing work.
+             */
+        void start()
+            {
+                __start(reinterpret_cast<start_fn_t>(&run), this);
+            };
+            /** @brief Completes outstanding work and destroys worker threads.
+             *
+             *  @note This function will block until all work is completed and
+             *        worker threads are destroyed.
+             */
+        void shutdown()
+            { __shutdown(); };
+
+            /** @brief Insert a work item onto the thread-pool's queue.
+             *
+             *  Ownership of the object is transfered to the thread-pool.
+             *  After completing the work, the thread-pool will delete the
+             *  work item.
+             *
+             *  @param[in] i_workItem - A work item to process.
+             */
+        void insert(WorkItem* i_workitem)
+            { __insert(i_workitem); };
+
+    private:
+            /** Entry point for worker thread. */
+        static void run(ThreadPool*);
+            /** Useful constant to determine FIFO vs non-FIFO behavior. */
+        static const bool has_comparison =
+                Util::Traits::has_lessthan<WorkItem>::value;
+};
+
+/**
+ * @brief Manager of the thread pools.
+ *
+ * When new thread-pools are created, they query the manager to determine
+ * how many worker threads to create.  This should be manipulated by some
+ * higher level service that understands the resources available to
+ * thread-pools and sets the value to balance memory usage and efficiency.
+ */
+class ThreadPoolManager
+{
+    public:
+        /** Query the desired worker-thread count. */
+        static size_t getThreadCount()
+            { return cv_size; };
+        /** Set the desired worker-thread count. */
+        static void setThreadCount(size_t i_size)
+            { cv_size = i_size; };
+    private:
+        static size_t cv_size;
+};
+
+// Implementation of the worker-thread run function.
+template <typename WorkItem>
+void ThreadPool<WorkItem>::run(
+        ThreadPool<WorkItem>* self)
+{
+    while(1)
+    {
+        // Obtain next work item from queue.
+        WorkItem* wi =
+            static_cast<WorkItem*>(
+                self->__remove(
+                    reinterpret_cast<order_fn_t>(
+                        &Util::__Util_ThreadPool_Impl::ThreadPoolWorklistSearch
+                            <WorkItem, has_comparison>::search
+                    )
+                )
+            );
+
+        if (wi) // Work was given, do it.
+        {
+            (*wi)();
+            delete wi;
+        }
+        else // No work item was given, we must be done.
+        {
+            return; // task_end() called automatically by returning.
+        }
+    }
+}
+
+};
+
+#endif
diff --git a/src/include/util/traits/has_lessthan.H b/src/include/util/traits/has_lessthan.H
new file mode 100644
index 000000000..4a96d4ce9
--- /dev/null
+++ b/src/include/util/traits/has_lessthan.H
@@ -0,0 +1,40 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/traits/has_lessthan.H $
+//
+//  IBM CONFIDENTIAL
+//
+//  COPYRIGHT International Business Machines Corp. 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
+
+#ifndef __UTIL_TRAITS_HAS_LESSTHAN
+#define __UTIL_TRAITS_HAS_LESSTHAN
+
+/** @file has_lessthan.H
+ *  Creates a template class has_lessthan<T> who's value variable will tell
+ *  if T has a valid < comparison operation.
+ */
+
+#define UTIL_COMPARISON_OPERATOR <
+#define UTIL_COMPARISON_OPERATOR_NAME lessthan
+
+#include <util/traits/impl/has_comparison.H>
+
+#undef UTIL_COMPARISON_OPERATOR
+#undef UTIL_COMPARISON_OPERATOR_NAME
+
+#endif
diff --git a/src/include/util/traits/impl/has_comparison.H b/src/include/util/traits/impl/has_comparison.H
new file mode 100644
index 000000000..4cc7a84c0
--- /dev/null
+++ b/src/include/util/traits/impl/has_comparison.H
@@ -0,0 +1,132 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/usr/util/traits/impl/has_comparison.H $
+//
+//  IBM CONFIDENTIAL
+//
+//  COPYRIGHT International Business Machines Corp. 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
+
+/** @file has_comparison.H
+ *
+ *  Defines the guts of a has_foo<T> template where 'foo' is a binary
+ *  comparison operator on a type T.  This template can be used for
+ *  template meta-programming purposes.
+ *
+ *  The macros UTIL_COMPARISON_OPERATOR and UTIL_COMPARISON_OPERATOR_NAME
+ *  can be defined to create a template. For instance (<, lessthan) will
+ *  create a template has_lessthan that allows determination to be made on
+ *  if T has a valid < operator.
+ *
+ *  This file purposefully omits an include-guard to allow multiple templates
+ *  to be defined for all the various comparison operators.
+ *
+ *  Notice that a heavy dose of SFINAE techniques follow.
+ */
+
+// Ensure UTIL_COMPARISON_OPERATOR has been defined.
+#ifndef UTIL_COMPARISON_OPERATOR
+    #error Comparison operator is not defined.
+#endif
+
+// Ensure UTIL_COMPARISON_OPERATOR_NAME has been defined.
+#ifndef UTIL_COMPARISON_OPERATOR_NAME
+    #error Comparison operator name is not defined.
+#endif
+
+// Macro magic to make well-formed variable names from existing #defines.
+#define __UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)   X ## Y
+#define _UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)    \
+                __UTIL_TRAIT_COMPARISON_MAKENAME(X,Y)
+#define UTIL_TRAIT_COMPARISON_MAKENAME(X) \
+                _UTIL_TRAIT_COMPARISON_MAKENAME(X,\
+                                                UTIL_COMPARISON_OPERATOR_NAME)
+
+namespace Util
+{
+
+// Creates a namespace of the form Util::__Util_Trait_Impl_OPERATOR_NAME to
+// hide the template implementation in.
+namespace UTIL_TRAIT_COMPARISON_MAKENAME(__Util_Trait_Impl_)
+{
+    // If "T op S" is valid, it is going to return some type (likely bool).  If
+    // it is not valid, we still need it to compile cleanly.  So what we do is
+    // create a type (convert_from_any_type) that causes implicit type
+    // conversion from any other type.  We ensure that the operator against
+    // convert_from_any_type returns a special type (bad_type).
+    //
+    // If "T op S" is valid then the implicit type conversion to
+    // convert_from_any_type will not happen because the native "T op S" takes
+    // precidence.  So "T op S" has type not equal to bad_type.  If "T op S"
+    // is invalid then the implicit type conversion will cause "T op S" to have
+    // type bad_type.
+
+    struct bad_type {};
+    struct convert_from_any_type
+    {
+        template <class C> convert_from_any_type(C const&);
+    };
+    bad_type operator UTIL_COMPARISON_OPERATOR (const convert_from_any_type&,
+                                                const convert_from_any_type&);
+
+
+    // Now, "T op T" is going to return either bad_type or something else.  We
+    // define a function 'has_comparison' that returns a character array of
+    // different size based on the input parameter type.  Then the "sizeof"
+    // can be used to tell if "T op S" returns bad_type or something else.
+    //
+    // The only additional oddity is the get_instance function.  Since some
+    // classes cannot be directly constructed, this is a level of indirection
+    // to get a type of T and S to apply the operator against.
+    template <typename _T, typename _S>
+    struct UTIL_TRAIT_COMPARISON_MAKENAME(has_)
+    {
+        typedef char yes[1];
+        typedef char no[2];
+
+        static no& has_comparison(bad_type);
+        static yes& has_comparison(...);
+
+        template <typename C> static C& get_instance();
+
+        static const bool value =
+            sizeof(has_comparison(get_instance<_T>() UTIL_COMPARISON_OPERATOR
+                                  get_instance<_S>())) == sizeof(yes);
+    };
+
+};
+
+
+// Since the implementation was hidden in a __Util_Trait_Impl_OPERATOR_NAME
+// namespace, we expose just the main comparison class (with the value variable)
+// by defining a class in the Traits namespace that inherits from the one in
+// the __Util_Trait_Impl_OPERATOR_NAME namespace.
+namespace Traits
+{
+    template <typename _T, typename _S = _T>
+    struct UTIL_TRAIT_COMPARISON_MAKENAME(has_) :
+        public UTIL_TRAIT_COMPARISON_MAKENAME(Util::__Util_Trait_Impl_)::
+               UTIL_TRAIT_COMPARISON_MAKENAME(has_)<_T,_S>
+    {};
+};
+
+};
+
+#undef __UTIL_TRAIT_COMPARISON_MAKENAME
+#undef _UTIL_TRAIT_COMPARISON_MAKENAME
+#undef UTIL_TRAIT_COMPARISON_MAKENAME
+