[heap] Fix searching for a node in FreeListCategory

src/heap/spaces.cc

Index: src/heap/spaces.cc
diff --git a/src/heap/spaces.cc b/src/heap/spaces.cc
index 50a213e8ae4f582a3a684b4639c73894616fb851..ac7fdf4d8165028d1f96653f867f5eb868d6d784 100644
--- a/src/heap/spaces.cc
+++ b/src/heap/spaces.cc
@@ -2125,25 +2125,26 @@ bool FreeListCategory::ContainsPageFreeListItemsInList(Page* p) {
 
 FreeSpace* FreeListCategory::PickNodeFromList(int* node_size) {
   FreeSpace* node = top();
+  if (node == nullptr) return nullptr;
 
-  if (node == NULL) return NULL;
-
-  while (node != NULL &&
+  while ((node != nullptr) &&
          Page::FromAddress(node->address())->IsEvacuationCandidate()) {

[Hannes Payer (out of office), 2015/10/15 12:45:10]

Let's re-write this piece of code.
Create a local variable page to avoid two times
Page::FromAddress(node->address()).

while (node != nullptr) {
  Page* page = Page::FromAddress(node->address());
  if (!page->IsEvacuationCandidate()) break;
  ...

[Michael Lippautz, 2015/10/15 12:53:21]

Done.

     available_ -= node->Size();
+    Page::FromAddress(node->address())

[Michael Lippautz, 2015/10/15 12:23:32]

This was a bug, as we did not remove the size when removing evacuation candidate
nodes.

[Hannes Payer (out of office), 2015/10/15 12:45:10]

Acknowledged.

+        ->add_available_in_free_list(type_, -(node->Size()));
     node = node->next();
   }
 
-  if (node != NULL) {
+  if (node != nullptr) {
     set_top(node->next());
     *node_size = node->Size();
     available_ -= *node_size;
   } else {
-    set_top(NULL);
+    set_top(nullptr);
   }
 
-  if (top() == NULL) {
-    set_end(NULL);
+  if (top() == nullptr) {
+    set_end(nullptr);
   }
 
   return node;
@@ -2153,10 +2154,10 @@ FreeSpace* FreeListCategory::PickNodeFromList(int* node_size) {
 FreeSpace* FreeListCategory::PickNodeFromList(int size_in_bytes,
                                               int* node_size) {
   FreeSpace* node = PickNodeFromList(node_size);
-  if (node != NULL && *node_size < size_in_bytes) {
+  if ((node != nullptr) && (*node_size < size_in_bytes)) {
     Free(node, *node_size);
     *node_size = 0;
-    return NULL;
+    return nullptr;
   }
   return node;
 }
@@ -2164,50 +2165,38 @@ FreeSpace* FreeListCategory::PickNodeFromList(int size_in_bytes,
 
 FreeSpace* FreeListCategory::SearchForNodeInList(int size_in_bytes,
                                                  int* node_size) {
-  FreeSpace* return_node = nullptr;
-  FreeSpace* top_node = top();
-
-  for (FreeSpace** node_it = &top_node; *node_it != NULL;
-       node_it = (*node_it)->next_address()) {
-    FreeSpace* cur_node = *node_it;
-    while (cur_node != NULL &&
-           Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
-      int size = cur_node->Size();
+  FreeSpace* prev_non_evac_node = nullptr;
+  for (FreeSpace* cur_node = top(); cur_node != nullptr;
+       cur_node = cur_node->next()) {
+    int size = cur_node->size();
+    Page* page_for_node = Page::FromAddress(cur_node->address());
+
+    if ((size >= size_in_bytes) || page_for_node->IsEvacuationCandidate()) {
+      // The node is either large enough or contained in an evacuation
+      // candidate. In both cases we need to unlink it from the list.
       available_ -= size;
-      Page::FromAddress(cur_node->address())
-          ->add_available_in_free_list(type_, -size);
-      cur_node = cur_node->next();
-    }
-
-    // Update iterator.
-    *node_it = cur_node;
-
-    if (cur_node == nullptr) {
-      set_end(nullptr);
-      break;
-    }
-
-    int size = cur_node->Size();
-    if (size >= size_in_bytes) {
-      // Large enough node found.  Unlink it from the list.
-      return_node = cur_node;
-      *node_it = cur_node->next();
+      if (cur_node == top()) {
+        set_top(cur_node->next());
+      }
+      if (cur_node == end()) {

[Michael Lippautz, 2015/10/15 12:23:32]

Bug: end() was not handled properly. The bug flushed out when nodes were skipped
(as sizes were too small) and the last node was a match.

[Hannes Payer (out of office), 2015/10/15 12:45:10]

Acknowledged.

+        set_end(prev_non_evac_node);
+      }
+      if (prev_non_evac_node != nullptr) {
+        prev_non_evac_node->set_next(cur_node->next());
+      }
+      // For evacuation candidates we continue.
+      if (page_for_node->IsEvacuationCandidate()) {
+        page_for_node->add_available_in_free_list(type_, -size);

[Hannes Payer (out of office), 2015/10/15 12:45:10]

I like it that this counter is updated here, since this is the place where the
node is removed from the free-list. We should have a look if we can do the
counter update in all cases right after removing/adding the node. We can do that
in a follow-up cl.

[Michael Lippautz, 2015/10/15 12:53:21]

Acknowledged.

+        continue;
+      }
+      // Otherwise we have a large enough node and can return.
       *node_size = size;
-      available_ -= size;
-      Page::FromAddress(return_node->address())
-          ->add_available_in_free_list(type_, -size);
-      break;
+      return cur_node;
     }
-  }
 
-  // Top could've changed if we took the first node. Update top and end
-  // accordingly.
-  set_top(top_node);
-  if (top() == nullptr) {
-    set_end(nullptr);
+    prev_non_evac_node = cur_node;
   }
-
-  return return_node;
+  return nullptr;
 }
 
 
@@ -2330,36 +2319,28 @@ FreeSpace* FreeList::FindNodeIn(FreeListCategoryType category, int* node_size) {
 
 
 FreeSpace* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
-  FreeSpace* node = NULL;
-  Page* page = NULL;
+  FreeSpace* node = nullptr;
+  Page* page = nullptr;
 
   if (size_in_bytes <= kSmallAllocationMax) {
     node = FindNodeIn(kSmall, node_size);
-    if (node != NULL) {
-      DCHECK(IsVeryLong() || available() == SumFreeLists());
-      return node;
-    }
+    if (node != nullptr) return node;
   }
 
   if (size_in_bytes <= kMediumAllocationMax) {
     node = FindNodeIn(kMedium, node_size);
-    if (node != NULL) {
-      DCHECK(IsVeryLong() || available() == SumFreeLists());
-      return node;
-    }
+    if (node != nullptr) return node;
   }
 
   if (size_in_bytes <= kLargeAllocationMax) {
     node = FindNodeIn(kLarge, node_size);
-    if (node != NULL) {
-      DCHECK(IsVeryLong() || available() == SumFreeLists());
-      return node;
-    }
+    if (node != nullptr) return node;
   }
 
   node = huge_list_.SearchForNodeInList(size_in_bytes, node_size);
-
-  if (node != NULL) {
+  if (node != nullptr) {
+    page = Page::FromAddress(node->address());
+    page->add_available_in_large_free_list(-(*node_size));
     DCHECK(IsVeryLong() || available() == SumFreeLists());
     return node;
   }
@@ -2588,7 +2569,7 @@ void PagedSpace::RepairFreeListsAfterDeserialization() {
 }
 
 
-void PagedSpace::EvictEvacuationCandidatesFromFreeLists() {
+void PagedSpace::EvictEvacuationCandidatesFromLinearAllocationArea() {
   if (allocation_info_.top() >= allocation_info_.limit()) return;
 
   if (Page::FromAllocationTop(allocation_info_.top())
@@ -2598,8 +2579,8 @@ void PagedSpace::EvictEvacuationCandidatesFromFreeLists() {
         static_cast<int>(allocation_info_.limit() - allocation_info_.top());
     heap()->CreateFillerObjectAt(allocation_info_.top(), remaining);
 
-    allocation_info_.set_top(NULL);
-    allocation_info_.set_limit(NULL);
+    allocation_info_.set_top(nullptr);
+    allocation_info_.set_limit(nullptr);
   }
 }