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>

2 files changed, 57 insertions, 40 deletions

diff --git a/src/include/util/align.H b/src/include/util/align.H
index 7ff67ba38..55073256d 100644
--- a/src/include/util/align.H
+++ b/src/include/util/align.H
@@ -28,6 +28,9 @@
 // Return a number >= input that is aligned on a 4-byte boundary
 #define ALIGN_4(u) ((u + 0x3ull) & ~0x3ull)
 
+// Return a number >= input that is aligned on a 8-byte bounday
+#define ALIGN_8(u) ((u + 0x7ull) & ~0x7ull)
+
 // Return a number >= input that is aligned on a page boundary
 #define ALIGN_PAGE(u) ((u + (PAGESIZE-1)) & ~(PAGESIZE-1))
 
diff --git a/src/include/util/lockfree/stack.H b/src/include/util/lockfree/stack.H
index 8e549df12..61120364b 100644
--- a/src/include/util/lockfree/stack.H
+++ b/src/include/util/lockfree/stack.H
@@ -29,50 +29,64 @@ namespace Util
 {
     namespace Lockfree
     {
-	template <typename _T>
-	class Stack
-	{
-	    public:
-		Stack() : head(NULL) {};
-		
-		_T* pop();
-		void push(_T*);
+        template <typename _T>
+            class Stack
+            {
+                public:
+                    Stack() : head(NULL) {};
 
-	    private:
-		_T* head;
-	};
+                    _T* pop();
+                    void push(_T*);
 
-	template <typename _T>
-	_T* Stack<_T>::pop()
-	{
-	    _T * _head = head;
-	    _T * h = (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
-	    if (NULL == h) return h;	    
-	    uint64_t token = ((uint64_t)_head) >> 32;
-	    token++;
-	    _T * h_next = (_T*) (((uint64_t)(h->next)) | (token << 32));
-	    if (!__sync_bool_compare_and_swap(&head,
-					      _head,
-					      h_next))
-		return pop();
-	    return h;
-	}
+                    /**
+                     * Get a pointer to the first element in the stack
+                     * @return the pointer to the first element
+                     * @Note:  SMP safety of this pointer is not guaranteed.
+                     */
+                    _T* first();
 
-	template <typename _T>
-	void Stack<_T>::push(_T* p)
-	{
-	    _T* _head = head;
-	    p->next = (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
-	    uint64_t token = ((uint64_t)_head) >> 32;
-	    token++;
+                private:
+                    _T* head;
+            };
 
-	    _T* _p = (_T*) (((uint64_t)p) | (token << 32));
-	    	    
-	    if (!__sync_bool_compare_and_swap(&head,
-					      _head,
-					      _p))
-		push(p);
-	}
+        template <typename _T>
+            _T* Stack<_T>::first()
+            {
+                _T * _head = head;
+                return (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
+            }
+
+        template <typename _T>
+            _T* Stack<_T>::pop()
+            {
+                _T * _head = head;
+                _T * h = (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
+                if (NULL == h) return h;	    
+                uint64_t token = ((uint64_t)_head) >> 32;
+                token++;
+                _T * h_next = (_T*) (((uint64_t)(h->next)) | (token << 32));
+                if (!__sync_bool_compare_and_swap(&head,
+                                                  _head,
+                                                  h_next))
+                    return pop();
+                return h;
+            }
+
+        template <typename _T>
+            void Stack<_T>::push(_T* p)
+            {
+                _T* _head = head;
+                p->next = (_T*) (((uint64_t)_head) & 0x00000000FFFFFFFF);
+                uint64_t token = ((uint64_t)_head) >> 32;
+                token++;
+
+                _T* _p = (_T*) (((uint64_t)p) | (token << 32));
+
+                if (!__sync_bool_compare_and_swap(&head,
+                                                  _head,
+                                                  _p))
+                    push(p);
+            }
     }
 }