new HEAP manager to reduce fragmentation

Change-Id: Ibe725a43e6366d9113ec99df1cc6aafa7bbb770e
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/431
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>

5 files changed, 339 insertions, 73 deletions

diff --git a/src/include/kernel/barrier.H b/src/include/kernel/barrier.H
new file mode 100644
index 000000000..b5587b4cd
--- /dev/null
+++ b/src/include/kernel/barrier.H
@@ -0,0 +1,76 @@
+//  IBM_PROLOG_BEGIN_TAG
+//  This is an automatically generated prolog.
+//
+//  $Source: src/include/kernel/barrier.H $
+//
+//  IBM CONFIDENTIAL
+//
+//  COPYRIGHT International Business Machines Corp. 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
+#ifndef __KERNEL_BARRIER_H
+#define __KERNEL_BARRIER_H
+
+#include <kernel/spinlock.H>
+#include <stdint.h>
+
+/**
+ * Barrier to be used in kernel space
+ */
+class Barrier
+{
+    public:
+
+        /**
+         * Default Constructor
+         */
+        Barrier() :
+            iv_count(0),
+            iv_event(0),
+            iv_missing(0) {};
+
+        /**
+         * Construct and init a barrier
+         * @param[in] i_count number of cpus to wait on
+         */
+        Barrier(size_t i_count) :
+            iv_count(i_count),
+            iv_event(0),
+            iv_missing(i_count) {}
+        
+        /**
+         * Initialize the barrier
+         * @param[in] i_count number of cpus to wait on
+         */
+        void init(size_t i_count)
+        {
+            iv_count = i_count;
+            iv_missing = i_count;
+        }
+
+        /**
+         * Wait until all threads have been arrived
+         */
+	void wait();
+
+    private:
+
+        Spinlock iv_spinlock;           //!< Spinlock acts as mutex
+        volatile size_t iv_count;       //!< Barrier thread count
+        volatile size_t iv_event;       //!< Barrier event
+        volatile size_t iv_missing;     //!< # of missing threads to wait for
+};
+
+#endif
diff --git a/src/include/kernel/cpu.H b/src/include/kernel/cpu.H
index ac09da288..f308fb4be 100644
--- a/src/include/kernel/cpu.H
+++ b/src/include/kernel/cpu.H
@@ -58,10 +58,13 @@ struct cpu_t
     struct
     {
         /** If the CPU is the master */
-        bool master;
+        bool master:1;
+
+        /** If the CPU is active */
+        bool active:1;
 
         /** Ensure alignment of master attribute for asm code. */
-        uint64_t __reserved_master:24;
+        uint64_t __reserved_master:30;
     } PACKED;
 
     /** Pointer to the scheduler for this CPU (may not be unique) */
diff --git a/src/include/kernel/cpumgr.H b/src/include/kernel/cpumgr.H
index b60c72bc6..78ade4ae3 100644
--- a/src/include/kernel/cpumgr.H
+++ b/src/include/kernel/cpumgr.H
@@ -25,73 +25,86 @@
 
 #include <kernel/types.h>
 #include <kernel/cpu.H>
+#include <kernel/barrier.H>
 
 class CpuManager
 {
     public:
-	enum 
+        enum 
         { 
             MAXCPUS = KERNEL_MAX_SUPPORTED_CPUS,
             CPU_PERIODIC_CHECK_MEMORY = 64,
-            CPU_PERIODIC_FLUSH_PAGETABLE = 1024,
+            CPU_PERIODIC_FLUSH_PAGETABLE = 512, //TODO 1024 not currently hit
+            CPU_PERIODIC_DEFRAG = 949,  // TODO Any bigger not currently hit
         };
 
-	/** @fn getCurrentCPU
-	 *  Returns a pointer to the current CPU structure by using the
-	 *  task structure in SPRG3.
-	 */
-	static cpu_t* getCurrentCPU();
-	static cpu_t* getCpu(size_t i) { return cv_cpus[i]; }
+        /** @fn getCurrentCPU
+         *  Returns a pointer to the current CPU structure by using the
+         *  task structure in SPRG3.
+         */
+        static cpu_t* getCurrentCPU();
+        static cpu_t* getCpu(size_t i) { return cv_cpus[i]; }
 
         /** @brief Return pointer to master CPU object.
-         */
+        */
         static cpu_t* getMasterCPU();
 
-	static void init();
-	static void init_slave_smp(cpu_t*);
+        static void init();
+        static void init_slave_smp(cpu_t*);
 
-    /** @fn requestShutdown
-     *  Requests that all CPUs shutdown
-     */
-    static void requestShutdown(uint64_t i_status);
+        /** @fn requestShutdown
+         *  Requests that all CPUs shutdown
+         */
+        static void requestShutdown(uint64_t i_status);
+
+        /** @fn isShutdownRequested
+         *  Returns if a shutdown of all CPUs was requested
+         */
+        static bool isShutdownRequested() { return cv_shutdown_requested; }
 
-    /** @fn isShutdownRequested
-     *  Returns if a shutdown of all CPUs was requested
-     */
-    static bool isShutdownRequested() { return cv_shutdown_requested; }
+        /** @fn getShutdownStatus
+         *  Returns the status code that needs to be posted during shutdown
+         */
+        static uint32_t getShutdownStatus() { return cv_shutdown_status; }
 
-    /** @fn getShutdownStatus
-     *  Returns the status code that needs to be posted during shutdown
-     */
-    static uint32_t getShutdownStatus() { return cv_shutdown_status; }
+        /** @fn executePeriodics
+         * Perform periodic actions
+         * @param[in] cpu_t the CPU
+         */
+        static void executePeriodics(cpu_t * i_cpu);
 
-    /** @fn executePeriodics
-     * Perform periodic actions
-     * @param[in] cpu_t the CPU
-     */
-    static void executePeriodics(cpu_t * i_cpu);
+        /** @fn activateCPU
+         * Activate a cpu to show it is running
+         * @param[in] cpu_t the CPU
+         * @post Active flag on in cpu_t structure
+         */
+        static void activateCPU(cpu_t * i_cpu);
 
 
     protected:
-	CpuManager();
-	~CpuManager() {}
+        CpuManager();
+        ~CpuManager() {}
 
-	/** @fn startCPU
-	 *  Starts the requested CPU. Default of -1 implies current CPU.
-	 */
-	void startCPU(ssize_t i = -1);
-	void startSlaveCPU(cpu_t*);
+        /** @fn startCPU
+         *  Starts the requested CPU. Default of -1 implies current CPU.
+         */
+        void startCPU(ssize_t i = -1);
+        void startSlaveCPU(cpu_t*);
 
     private:
-	static cpu_t* cv_cpus[MAXCPUS]; // Need to be able to access this
-					// from start.S to get initial stacks
-					// of secondary cpus / threads.
+        static cpu_t* cv_cpus[MAXCPUS]; // Need to be able to access this
+                                        // from start.S to get initial stacks
+                                        // of secondary cpus / threads.
+
+        static Barrier cv_barrier;   //!<  barrier for cpus
+        static bool cv_defrag;       //!<  mem heap defrag
+        static size_t cv_cpuCount;   //!<  # of active CPUs
 
-    // If a shutdown of all CPUs is requested
-    static bool cv_shutdown_requested;
+        // If a shutdown of all CPUs is requested
+        static bool cv_shutdown_requested;
 
-    // The status code that needs to be posted during shutdown
-    static uint64_t cv_shutdown_status;
+        // The status code that needs to be posted during shutdown
+        static uint64_t cv_shutdown_status;
 };
 
 #endif
diff --git a/src/include/kernel/heapmgr.H b/src/include/kernel/heapmgr.H
index df52ee068..a2509e060 100644
--- a/src/include/kernel/heapmgr.H
+++ b/src/include/kernel/heapmgr.H
@@ -25,41 +25,194 @@
 
 #include <stdint.h>
 #include <util/lockfree/stack.H>
+#include <builtins.h>
 
+extern "C"
+void kernel_execute_decrementer();
+
+/**
+ * A class to manage the dynamic memory allocation heap.
+ * <p>There is a small allocation heap and a large heap.
+ * The Small allocation heap is a Fibonacci buddy system divided into the
+ * following bucket sizes: 16,32,48,80,128,208,336,544,880,1424,2304,3728.
+ * Eight bytes is used for overhead in each allocation making the effective
+ * bucket sizes  8,24,40,72,120,200,328,536,872,1416,2296, and 3720.
+ * The small heap increases one page at a time as allocations are needed.
+ * A 4k pages is initially divided into buckes of size 3728,336, and 32.
+ * Pages can't be recovered once assinged to the small heap.</p>
+ * 
+ * <p>Anthing larger than 3720 goes into the large allocation heap.
+ * Memory in the large allocation heap are assigned as integral pages.
+ * When memory is released from the large allocation heap, it is returned
+ * to the system page manager.</p>
+ */
 class HeapManager
 {
     public:
-	static void init();
+        enum
+        {
+            BUCKETS             = 12,   //!< number of buckets
+            MIN_BUCKET_SIZE     = 16,   //!< Smallest bucket size
+            FIB_START_INCR      = 16,   //!< Seed for the Fibonacci series
+            BUCKET_SIZE0        = MIN_BUCKET_SIZE,
+            BUCKET_SIZE1        = BUCKET_SIZE0 + FIB_START_INCR,
+            BUCKET_SIZE2        = BUCKET_SIZE1 + BUCKET_SIZE0,
+            BUCKET_SIZE3        = BUCKET_SIZE2 + BUCKET_SIZE1,
+            BUCKET_SIZE4        = BUCKET_SIZE3 + BUCKET_SIZE2,
+            BUCKET_SIZE5        = BUCKET_SIZE4 + BUCKET_SIZE3,
+            BUCKET_SIZE6        = BUCKET_SIZE5 + BUCKET_SIZE4,
+            BUCKET_SIZE7        = BUCKET_SIZE6 + BUCKET_SIZE5,
+            BUCKET_SIZE8        = BUCKET_SIZE7 + BUCKET_SIZE6,
+            BUCKET_SIZE9        = BUCKET_SIZE8 + BUCKET_SIZE7,
+            BUCKET_SIZE10       = BUCKET_SIZE9 + BUCKET_SIZE8,
+            BUCKET_SIZE11       = BUCKET_SIZE10 + BUCKET_SIZE9,
+
+            MAX_SMALL_ALLOC_SIZE      = BUCKET_SIZE11 - 8,// last bucket size-8
+        };
+
+        friend class CpuManager;
+        friend void kernel_execute_decrementer();
+
+        /**
+         * Initalize the HeapManager
+         */
+        static void init();
+
+        /**
+         * Reqest an allocation of heap memory
+         * @param[in] i_sz  requested memory size in bytes
+         * @return a pointer to allocated memory
+         */
+        static void* allocate(size_t i_sz);
 
-	static void* allocate(size_t n);
-	static void  free(void *);
+        /**
+         * Request a change in allocation size
+         * @param[in] i_ptr The memory allocation
+         * @param[in] i_sz  The new size
+         * @return a pointer to allocated memory
+         * @post Memory may have been moved
+         */
+        static void* realloc(void * i_ptr, size_t i_sz);
 
-	enum
-	{
-	    BUCKETS = 8,
+        /**
+         * Return an allocation to the heap.
+         * @param[in] The allocation
+         */
+        static void  free(void * i_ptr);
 
-	    MAX_ALLOC_SIZE = (1 << (BUCKETS + 3)) - 8,
-	};
 
     protected:
-	HeapManager() {};
-	~HeapManager() {};
+
+        /**
+         * ctor
+         */
+        HeapManager() {};
+
+        /**
+         * dtor
+         */
+        ~HeapManager() {};
+
+        /**
+         * Coalesce unallocated memory chucks
+         * @pre This function can only be called from kernel space and
+         * requires that all other processes are quiesced
+         */
+        static void coalesce( void );
+
+        /**
+         * Print some stats to printkd
+         * @pre system quiesced, This function can only be called from
+         *      kernel space.
+         * @post coalesce() called
+         */
+        static void stats( void );
 
     private:
-	void* _allocate(size_t);
-	void _free(void*);
 
-	struct chunk_t
-	{
-	    size_t len;
-	    chunk_t* next;
-	};
-	Util::Lockfree::Stack<chunk_t> first_chunk[BUCKETS];
+        struct chunk_t
+        {
+            struct
+            {
+                bool    free:1;         //!< Is chunck free
+                uint64_t bucket:63;     //!< Which bucket this chunk belongs to
+            } PACKED;
+            
+            chunk_t* next;      //!< Next chunk (for unallocated chunks only)
+        };
 
-	chunk_t* pop_bucket(size_t);
-	void push_bucket(chunk_t*, size_t);
+        /**
+         * big chunk directory entry
+         */
+        struct big_chunk_t
+        {
+            void * addr;        //!< Allocated address
+            size_t page_count;  //!< Number of pages used
+            big_chunk_t * next; //!< Next allocation
 
-	void newPage();
-};
+            big_chunk_t(void * i_ptr, size_t i_pages) 
+                : addr(i_ptr), page_count(i_pages), next(NULL) {}
+        };
 
+        void* _allocate(size_t);        //!< see allocate
+        void* _allocateBig(size_t);     //!< see allocate
+        void* _realloc(void*,size_t);   //!< see realloc
+        void* _reallocBig(void*,size_t);//!< see realloc
+        void _free(void*);              //!< see free
+        bool _freeBig(void*);           //!< see free
+        void _coalesce(void);           //!< see coalesce
+
+        /**
+         * Get a chunk of free memory from the given bucket
+         * @param[in] The bucket index
+         * @return  a chunk
+         */
+        chunk_t* pop_bucket(size_t);
+
+        /**
+         * Push a free chunk onto the free bucket stack
+         * @param[in] the chunk
+         * @param[in] the bucket index
+         */
+        void push_bucket(chunk_t*, size_t);
+
+        /**
+         * Get a new page from the page manager, set it up, and addit it to the
+         * free pool
+         */
+        void newPage();
+
+        /**
+         * Get the bytesize of the given bucket
+         * @param[in] The bucket index
+         * @return the bytesize of the bucket
+         */
+        ALWAYS_INLINE
+            size_t bucketByteSize(size_t i_bucketIndex)
+            {
+                return cv_chunk_size[i_bucketIndex];
+            }
+
+        /**
+         * Get the bucket index for a given size
+         * @param[in] The bytesize
+         * @return the smallest bucket index that the given size will fit into
+         */
+        size_t bucketIndex(size_t i_sz);
+
+        /**
+         * Walk through all the allocated pages and verify coherency
+         */
+        void test_pages();
+
+    private: // data
+
+        Util::Lockfree::Stack<chunk_t> first_chunk[BUCKETS]; //!< free pool
+        Util::Lockfree::Stack<big_chunk_t> big_chunk_stack;  //!< big chunk dir
+
+        static const size_t cv_chunk_size[BUCKETS];//!< The bucket sizes
+        static size_t cv_coalesce_count;       //!< coalesced chunk count
+        static size_t cv_free_bytes;           //!< Only valid after coalesce()
+        static size_t cv_free_chunks;          //!< Only valid after coalesce()
+};
 #endif
diff --git a/src/include/kernel/pagemgr.H b/src/include/kernel/pagemgr.H
index 6cb6fefc4..3ed2c1b34 100644
--- a/src/include/kernel/pagemgr.H
+++ b/src/include/kernel/pagemgr.H
@@ -29,6 +29,8 @@
 #include <kernel/vmmmgr.H>
 #include <builtins.h>
 #include <kernel/console.H>
+#include <util/align.H>
+#include <sys/vfs.h>
 
 /** @class PageManager
  *  @brief Manages the allocation of memory pages.
@@ -37,10 +39,10 @@
 class PageManager
 {
     public:
-	static void init();
+        static void init();
 
-	static void* allocatePage(size_t n = 1);
-	static void freePage(void*, size_t n = 1);
+        static void* allocatePage(size_t n = 1);
+        static void freePage(void*, size_t n = 1);
 
         /**
          * Query state for available memory
@@ -48,9 +50,16 @@ class PageManager
          */
         static uint64_t queryAvail();
 
-	enum 
-	{ 
-	    MEMLEN = VmmManager::HTABORG,
+        /**
+         * Coalesce adjacent free memory blocks
+         * @pre This function can only be called from kernel space and
+         * requires that all other processes are quiesced
+         */
+        static void coalesce( void );
+
+        enum 
+        { 
+            MEMLEN = VmmManager::HTABORG,
 
 	    BUCKETS = 16,
 	};
@@ -62,6 +71,7 @@ class PageManager
     private:
 	void* _allocatePage(size_t);
 	void _freePage(void*, size_t);
+        void _coalesce( void );         //!< see coalesce()
 
         /** see queryAvail() */
         ALWAYS_INLINE
@@ -70,6 +80,13 @@ class PageManager
             return (100*iv_pagesAvail)/iv_pagesTotal;
         }
 
+        ALWAYS_INLINE
+        uint64_t firstPageAddr( void )
+        {
+            return ALIGN_PAGE(VFS_LAST_ADDRESS);
+        }
+            
+
             /** Statistics on number of free pages (for debug) */
         uint64_t iv_pagesAvail;
             /** Total number of pages */
@@ -77,12 +94,16 @@ class PageManager
 
 	struct page_t
 	{
-	    page_t* next;
+	    page_t* next;       //!< Next block of pages
+            page_t* prev;       //!< Prev block of pages
+            page_t* key;        //!< Key for pqueue
 	};
 	Util::Lockfree::Stack<page_t> first_page[BUCKETS];
 
 	page_t* pop_bucket(size_t);
 	void push_bucket(page_t*, size_t);
+
+        static size_t cv_coalesce_count;        //!< running coalesced counter
 };
 
 #endif