Prepare FreeList for parallel and concurrent sweeping.

src/spaces.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1919 matching lines @@
 
 
 FreeList::FreeList(PagedSpace* owner)
     : owner_(owner), heap_(owner->heap()) {
   Reset();
 }
 
 
 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));
+}
+
+
 int FreeList::Free(Address start, int size_in_bytes) {
   if (size_in_bytes == 0) return 0;
   FreeListNode* node = FreeListNode::FromAddress(start);
   node->set_size(heap_, size_in_bytes);
 
   // Early return to drop too-small blocks on the floor.
   if (size_in_bytes < kSmallListMin) return 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());
   return 0;
 }
 
 
-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;
 
   while (node != NULL &&
          Page::FromAddress(node->address())->IsEvacuationCandidate()) {
     available_ -= node->Size();
     node = node->next();
   }
 
   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;
 }
 
 
 FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
   FreeListNode* node = NULL;
 
   if (size_in_bytes <= kSmallAllocationMax) {
     node = PickNodeFromList(&small_list_, node_size);
     if (node != NULL) return node;
   }
 
   if (size_in_bytes <= kMediumAllocationMax) {
     node = PickNodeFromList(&medium_list_, node_size);
     if (node != NULL) return node;
   }
 
   if (size_in_bytes <= kLargeAllocationMax) {
     node = PickNodeFromList(&large_list_, 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;
     while (cur_node != NULL &&
            Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
       available_ -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
       cur_node = cur_node->next();
     }
 
     *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);
     int size = cur_as_free_space->Size();
     if (size >= size_in_bytes) {
       // Large enough node found.  Unlink it from the list.
       node = *cur;
       *node_size = size;
       *cur = node->next();
       break;
@@ skipping 71 matching lines @@
   } else {
     // TODO(gc) Try not freeing linear allocation region when bytes_left
     // are zero.
     owner_->SetTop(NULL, NULL);
   }
 
   return new_node;
 }
 
 
-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);
       sum += free_space->Size();
     }
     n = n->next();
   }
   return sum;
 }
 
 
 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;
     sizes->large_size_ = 0;
   }
 }
 
 
-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);
       sum += free_space->Size();
       *n = (*n)->next();
     } else {
       n = (*n)->next_address();
     }
   }
   return sum;
 }
 
 
 intptr_t FreeList::EvictFreeListItems(Page* p) {
   intptr_t sum = EvictFreeListItemsInList(&huge_list_, p);
 
   if (sum < p->area_size()) {
     sum += EvictFreeListItemsInList(&small_list_, p) +
         EvictFreeListItemsInList(&medium_list_, p) +
         EvictFreeListItemsInList(&large_list_, p);
   }
 
   available_ -= static_cast<int>(sum);
 
   return sum;
 }
 
 
 #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);
     sum += cur_as_free_space->Size();
     cur = cur->next();
   }
   return sum;
 }
 
 
 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();
     if (length == kVeryLongFreeList) return length;
   }
   return length;
 }
 
 
 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;
 }
 
 
 // This can take a very long time because it is linear in the number of entries
 // 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
 
 
 // -----------------------------------------------------------------------------
 // OldSpace implementation
 
 bool NewSpace::ReserveSpace(int bytes) {
   // We can't reliably unpack a partial snapshot that needs more new space
@@ skipping 81 matching lines @@
       *map_location = heap->free_space_map();
     } else {
       ASSERT(*map_location == heap->free_space_map());
     }
     n = n->next();
   }
 }
 
 
 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);
 }
 
 
 // After we have booted, we have created a map which represents free space
 // on the heap.  If there was already a free list then the elements on it
 // were created with the wrong FreeSpaceMap (normally NULL), so we need to
 // fix them.
 void PagedSpace::RepairFreeListsAfterBoot() {
   free_list_.RepairLists(heap());
 }
@@ skipping 612 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal