From b9652b36ff9bfa429ff3e9756e7e43f0da4ea1a7 Mon Sep 17 00:00:00 2001
From: Patrick Williams <iawillia@us.ibm.com>
Date: Fri, 21 May 2010 07:37:12 -0500
Subject: Move pagemgr to generic lock free structure.

---
 src/include/kernel/pagemgr.H      |  5 +++--
 src/include/util/lockfree/stack.H | 47 +++++++++++++++++++++++++++++++++++++++
 src/kernel/pagemgr.C              | 24 +++-----------------
 3 files changed, 53 insertions(+), 23 deletions(-)
 create mode 100644 src/include/util/lockfree/stack.H

diff --git a/src/include/kernel/pagemgr.H b/src/include/kernel/pagemgr.H
index 1d7193b22..b99cedff2 100644
--- a/src/include/kernel/pagemgr.H
+++ b/src/include/kernel/pagemgr.H
@@ -2,6 +2,7 @@
 #define __KERNEL_PAGEMGR_H
 
 #include <stdint.h>
+#include <util/lockfree/stack.H>
 
 /** @class PageManager
  *  @brief Manages the allocation of memory pages.
@@ -31,9 +32,9 @@ class PageManager
 	
 	struct page_t
 	{
-	    page_t* next_page;
+	    page_t* next;
 	};
-	page_t* first_page[BUCKETS];
+	Util::Lockfree::Stack<page_t> first_page[BUCKETS];
 
 	page_t* pop_bucket(size_t);
 	void push_bucket(page_t*, size_t);
diff --git a/src/include/util/lockfree/stack.H b/src/include/util/lockfree/stack.H
new file mode 100644
index 000000000..8f884e072
--- /dev/null
+++ b/src/include/util/lockfree/stack.H
@@ -0,0 +1,47 @@
+#ifndef __UTIL_LOCKFREE_STACK_H
+#define __UTIL_LOCKFREE_STACK_H
+
+#include <stddef.h>
+
+namespace Util
+{
+    namespace Lockfree
+    {
+	template <typename _T>
+	class Stack
+	{
+	    public:
+		Stack() : head(NULL) {};
+		
+		_T* pop();
+		void push(_T*);
+
+	    private:
+		_T* head;
+	};
+
+	template <typename _T>
+	_T* Stack<_T>::pop()
+	{
+	    _T * h = head;
+	    if (NULL == h) return h;
+	    if (!__sync_bool_compare_and_swap(&head,
+					      h,
+					      h->next))
+		return pop();
+	    return h;
+	}
+
+	template <typename _T>
+	void Stack<_T>::push(_T* p)
+	{
+	    p->next = head;
+	    if (!__sync_bool_compare_and_swap(&head,
+					      p->next,
+					      p))
+		push(p);
+	}
+    }
+}
+
+#endif
diff --git a/src/kernel/pagemgr.C b/src/kernel/pagemgr.C
index e5d9ec321..728222a05 100644
--- a/src/kernel/pagemgr.C
+++ b/src/kernel/pagemgr.C
@@ -33,10 +33,6 @@ PageManager::PageManager()
 	   length,
 	   (uint64_t)page);
     
-    // Clear page buckets.
-    for(int i = 0; i < BUCKETS; i++)
-	first_page[i] = NULL;
-
     // Allocate pages to buckets.
     size_t page_length = BUCKETS-1;
     while(length > 0)
@@ -44,8 +40,7 @@ PageManager::PageManager()
 	while (length < (1 << page_length))
 	    page_length--;
 
-	page->next_page = first_page[page_length];
-	first_page[page_length] = page;
+	first_page[page_length].push(page);
 	page = (page_t*)((uint64_t)page + (1 << page_length)*PAGESIZE);
 	length -= (1 << page_length);
     }
@@ -91,7 +86,7 @@ PageManager::page_t* PageManager::pop_bucket(size_t n)
 {
     if (n >= BUCKETS) return NULL;
     
-    page_t* p = first_page[n];
+    page_t* p = first_page[n].pop();
 
     if (NULL == p)
     { 
@@ -101,24 +96,11 @@ PageManager::page_t* PageManager::pop_bucket(size_t n)
 	push_bucket((page_t*) (((uint64_t)p) + (PAGESIZE * (1 << n))),
 		    n);
     }
-    else
-    {
-	// This bucket appears to have items in it, allocate one.
-	if (!__sync_bool_compare_and_swap(&first_page[n],
-					  p,
-					  p->next_page))
-	    return pop_bucket(n);
-    }
     return p;
 }
 
 void PageManager::push_bucket(page_t* p, size_t n)
 {
     if (n >= BUCKETS) return;
-    
-    p->next_page = first_page[n];
-    if (!__sync_bool_compare_and_swap(&first_page[n],
-				      p->next_page,
-				      p))
-	push_bucket(p, n);
+    first_page[n].push(p);
 }
-- 
cgit v1.2.1