[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 204275ab5979fd17b68d07757470e4903b45df35..f042a8ef7e043b85a257190e53afda0e09535841 100644
--- a/src/heap/spaces.cc
+++ b/src/heap/spaces.cc
@@ -2125,25 +2125,25 @@ 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 &&
-         Page::FromAddress(node->address())->IsEvacuationCandidate()) {
+  Page* page = Page::FromAddress(node->address());
+  while ((node != nullptr) && page->IsEvacuationCandidate()) {
     available_ -= node->Size();
+    page->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 +2153,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 +2164,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()) {
+        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);
+        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;
 }
 
 
@@ -2329,36 +2317,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;
   }
@@ -2586,7 +2566,7 @@ void PagedSpace::RepairFreeListsAfterDeserialization() {
 }
 
 
-void PagedSpace::EvictEvacuationCandidatesFromFreeLists() {
+void PagedSpace::EvictEvacuationCandidatesFromLinearAllocationArea() {
   if (allocation_info_.top() >= allocation_info_.limit()) return;
 
   if (Page::FromAllocationTop(allocation_info_.top())
@@ -2596,8 +2576,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);
   }
 }