Prepare FreeList for parallel and concurrent sweeping.

src/spaces.cc

Index: src/spaces.cc
diff --git a/src/spaces.cc b/src/spaces.cc
index 0ac23d279db6d5c13e3d9b0b67206cdd7f983ce0..66307f6c5df0fca8e35019fa1073dfc4f617c2f4 100644
--- a/src/spaces.cc
+++ b/src/spaces.cc
@@ -1937,10 +1937,67 @@ FreeList::FreeList(PagedSpace* owner)
 
 void FreeList::Reset() {
   available_ = 0;
-  small_list_ = NULL;
-  medium_list_ = NULL;
-  large_list_ = NULL;
-  huge_list_ = NULL;
+  Reset(&small_list_);
+  Reset(&medium_list_);
+  Reset(&large_list_);
+  Reset(&huge_list_);
+}
+
+
+void FreeList::Reset(FreeListCategorie *categorie) {
+  categorie->top = NULL;
+  categorie->end = NULL;
+}
+
+
+void FreeList::GetList(struct FreeListCategorie *categorie,
+                       FreeListNode** top,
+                       FreeListNode** end) {
+  *top = categorie->top;
+  *end = categorie->end;
+  categorie->top = NULL;
+  categorie->end = NULL;
+}
+
+
+void AddList(struct FreeListCategorie *categorie,
+             FreeListNode* top,
+             FreeListNode* end) {
+  end->set_next(categorie->top);
+  categorie->top = top;
+}
+
+
+void FreeList::ConcurrentGetList(struct FreeListCategorie *categorie,
+                                 FreeListNode** top,
+                                 FreeListNode** end) {
+  do {
+    *top = categorie->top;
+    *end = categorie->end;
+  } while (*top != categorie->top ||
+           NoBarrier_CompareAndSwap(
+               reinterpret_cast<AtomicWord*>(&categorie->top), 
+               reinterpret_cast<AtomicWord>(*top), 0) != 
+               reinterpret_cast<AtomicWord>(*top));
+  NoBarrier_CompareAndSwap(
+      reinterpret_cast<AtomicWord*>(&categorie->end), 
+      reinterpret_cast<AtomicWord>(*end), 0);
+}
+
+
+void ConcurrentAddList(struct FreeListCategorie *categorie,
+                       FreeListNode* top,
+                       FreeListNode* end) {
+  FreeListNode* current_top;
+  do {
+    current_top = categorie->top;
+    end->set_next(current_top);
+  } while(current_top != categorie->top ||
+          NoBarrier_CompareAndSwap(
+              reinterpret_cast<AtomicWord*>(&categorie->top),
+              reinterpret_cast<AtomicWord>(current_top), 
+              reinterpret_cast<AtomicWord>(top)) != 
+              reinterpret_cast<AtomicWord>(current_top));
 }
 
 
@@ -1955,17 +2012,29 @@ int FreeList::Free(Address start, int size_in_bytes) {
   // Insert other blocks at the head of a free list of the appropriate
   // magnitude.
   if (size_in_bytes <= kSmallListMax) {
-    node->set_next(small_list_);
-    small_list_ = node;
+    node->set_next(small_list_.top);
+    small_list_.top = node;
+    if (small_list_.end == NULL) {
+      small_list_.end = node;
+    }
   } else if (size_in_bytes <= kMediumListMax) {
-    node->set_next(medium_list_);
-    medium_list_ = node;
+    node->set_next(medium_list_.top);
+    medium_list_.top = node;
+    if (medium_list_.end == NULL) {
+      medium_list_.end = node;
+    }
   } else if (size_in_bytes <= kLargeListMax) {
-    node->set_next(large_list_);
-    large_list_ = node;
+    node->set_next(large_list_.top);
+    large_list_.top = node;
+    if (large_list_.end == NULL) {
+      large_list_.end = node;
+    }
   } else {
-    node->set_next(huge_list_);
-    huge_list_ = node;
+    node->set_next(huge_list_.top);
+    huge_list_.top = node;
+    if (huge_list_.end == NULL) {
+      huge_list_.end = node;
+    }
   }
   available_ += size_in_bytes;
   ASSERT(IsVeryLong() || available_ == SumFreeLists());
@@ -1973,8 +2042,9 @@ int FreeList::Free(Address start, int size_in_bytes) {
 }
 
 
-FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int* node_size) {
-  FreeListNode* node = *list;
+FreeListNode* FreeList::PickNodeFromList(FreeListCategorie* categorie,
+                                         int* node_size) {
+  FreeListNode* node = categorie->top;
 
   if (node == NULL) return NULL;
 
@@ -1986,9 +2056,13 @@ FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int* node_size) {
 
   if (node != NULL) {
     *node_size = node->Size();
-    *list = node->next();
+    categorie->top = node->next();
   } else {
-    *list = NULL;
+    categorie->top = NULL;
+  }
+
+  if (categorie->top == NULL) {
+    categorie->end = NULL;
   }
 
   return node;
@@ -2013,7 +2087,7 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
     if (node != NULL) return node;
   }
 
-  for (FreeListNode** cur = &huge_list_;
+  for (FreeListNode** cur = &(huge_list_.top);
        *cur != NULL;
        cur = (*cur)->next_address()) {
     FreeListNode* cur_node = *cur;
@@ -2024,7 +2098,10 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
     }
 
     *cur = cur_node;
-    if (cur_node == NULL) break;
+    if (cur_node == NULL) { 
+      huge_list_.end = NULL;
+      break;
+    }
 
     ASSERT((*cur)->map() == HEAP->raw_unchecked_free_space_map());
     FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
@@ -2116,8 +2193,10 @@ HeapObject* FreeList::Allocate(int size_in_bytes) {
 }
 
 
-static intptr_t CountFreeListItemsInList(FreeListNode* n, Page* p) {
+static intptr_t CountFreeListItemsInList(FreeListCategorie* categorie,

[Michael Starzinger, 2012/11/27 13:51:53]

I think the code would be easier to read if the static helpers would still be
based on the FreeListNode and you would just pass in foo_list_.top into the
static helper. Same applies to the functions below.

[Hannes Payer (out of office), 2012/11/29 13:17:42]

Done. Now we just call the method on the given object.

+                                         Page* p) {
   intptr_t sum = 0;
+  FreeListNode* n = categorie->top;
   while (n != NULL) {
     if (Page::FromAddress(n->address()) == p) {
       FreeSpace* free_space = reinterpret_cast<FreeSpace*>(n);
@@ -2130,11 +2209,11 @@ static intptr_t CountFreeListItemsInList(FreeListNode* n, Page* p) {
 
 
 void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
-  sizes->huge_size_ = CountFreeListItemsInList(huge_list_, p);
+  sizes->huge_size_ = CountFreeListItemsInList(&huge_list_, p);
   if (sizes->huge_size_ < p->area_size()) {
-    sizes->small_size_ = CountFreeListItemsInList(small_list_, p);
-    sizes->medium_size_ = CountFreeListItemsInList(medium_list_, p);
-    sizes->large_size_ = CountFreeListItemsInList(large_list_, p);
+    sizes->small_size_ = CountFreeListItemsInList(&small_list_, p);
+    sizes->medium_size_ = CountFreeListItemsInList(&medium_list_, p);
+    sizes->large_size_ = CountFreeListItemsInList(&large_list_, p);
   } else {
     sizes->small_size_ = 0;
     sizes->medium_size_ = 0;
@@ -2143,8 +2222,10 @@ void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
 }
 
 
-static intptr_t EvictFreeListItemsInList(FreeListNode** n, Page* p) {
+static intptr_t EvictFreeListItemsInList(FreeListCategorie* categorie,
+                                         Page* p) {
   intptr_t sum = 0;
+  FreeListNode** n = &(categorie->top);
   while (*n != NULL) {
     if (Page::FromAddress((*n)->address()) == p) {
       FreeSpace* free_space = reinterpret_cast<FreeSpace*>(*n);
@@ -2174,8 +2255,9 @@ intptr_t FreeList::EvictFreeListItems(Page* p) {
 
 
 #ifdef DEBUG
-intptr_t FreeList::SumFreeList(FreeListNode* cur) {
+intptr_t FreeList::SumFreeList(FreeListCategorie* categorie) {
   intptr_t sum = 0;
+  FreeListNode* cur = categorie->top;
   while (cur != NULL) {
     ASSERT(cur->map() == HEAP->raw_unchecked_free_space_map());
     FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(cur);
@@ -2189,8 +2271,9 @@ intptr_t FreeList::SumFreeList(FreeListNode* cur) {
 static const int kVeryLongFreeList = 500;
 
 
-int FreeList::FreeListLength(FreeListNode* cur) {
+int FreeList::FreeListLength(FreeListCategorie* categorie) {
   int length = 0;
+  FreeListNode* cur = categorie->top;
   while (cur != NULL) {
     length++;
     cur = cur->next();
@@ -2201,10 +2284,10 @@ int FreeList::FreeListLength(FreeListNode* cur) {
 
 
 bool FreeList::IsVeryLong() {
-  if (FreeListLength(small_list_) == kVeryLongFreeList) return  true;
-  if (FreeListLength(medium_list_) == kVeryLongFreeList) return  true;
-  if (FreeListLength(large_list_) == kVeryLongFreeList) return  true;
-  if (FreeListLength(huge_list_) == kVeryLongFreeList) return  true;
+  if (FreeListLength(&small_list_) == kVeryLongFreeList) return  true;
+  if (FreeListLength(&medium_list_) == kVeryLongFreeList) return  true;
+  if (FreeListLength(&large_list_) == kVeryLongFreeList) return  true;
+  if (FreeListLength(&huge_list_) == kVeryLongFreeList) return  true;
   return false;
 }
 
@@ -2213,10 +2296,10 @@ bool FreeList::IsVeryLong() {
 // on the free list, so it should not be called if FreeListLength returns
 // kVeryLongFreeList.
 intptr_t FreeList::SumFreeLists() {
-  intptr_t sum = SumFreeList(small_list_);
-  sum += SumFreeList(medium_list_);
-  sum += SumFreeList(large_list_);
-  sum += SumFreeList(huge_list_);
+  intptr_t sum = SumFreeList(&small_list_);
+  sum += SumFreeList(&medium_list_);
+  sum += SumFreeList(&large_list_);
+  sum += SumFreeList(&huge_list_);
   return sum;
 }
 #endif
@@ -2318,10 +2401,10 @@ static void RepairFreeList(Heap* heap, FreeListNode* n) {
 
 
 void FreeList::RepairLists(Heap* heap) {
-  RepairFreeList(heap, small_list_);
-  RepairFreeList(heap, medium_list_);
-  RepairFreeList(heap, large_list_);
-  RepairFreeList(heap, huge_list_);
+  RepairFreeList(heap, small_list_.top);
+  RepairFreeList(heap, medium_list_.top);
+  RepairFreeList(heap, large_list_.top);
+  RepairFreeList(heap, huge_list_.top);
 }