[heap] Fix searching for a node in FreeListCategory

src/heap/spaces.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/heap/spaces.h"
 
 #include "src/base/bits.h"
 #include "src/base/platform/platform.h"
 #include "src/full-codegen/full-codegen.h"
 #include "src/heap/slots-buffer.h"
@@ skipping 2107 matching lines @@
   while (node != NULL) {
     if (Page::FromAddress(node->address()) == p) return true;
     node = node->next();
   }
   return false;
 }
 
 
 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;
 }
 
 
 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;
 }
 
 
 FreeSpace* FreeListCategory::SearchForNodeInList(int size_in_bytes,
                                                  int* node_size) {
-  FreeSpace* return_node = nullptr;
-  FreeSpace* top_node = top();
+  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());
 
-  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();
+    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();
+      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;
+      return cur_node;
     }
 
-    // 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();
-      *node_size = size;
-      available_ -= size;
-      Page::FromAddress(return_node->address())
-          ->add_available_in_free_list(type_, -size);
-      break;
-    }
+    prev_non_evac_node = 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);
-  }
-
-  return return_node;
+  return nullptr;
 }
 
 
 void FreeListCategory::Free(FreeSpace* free_space, int size_in_bytes) {
   free_space->set_next(top());
   set_top(free_space);
   if (end_ == NULL) {
     end_ = free_space;
   }
   available_ += size_in_bytes;
@@ skipping 102 matching lines @@
   if (node != nullptr) {
     Page::FromAddress(node->address())
         ->add_available_in_free_list(category, -(*node_size));
     DCHECK(IsVeryLong() || available() == SumFreeLists());
   }
   return node;
 }
 
 
 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;
   }
 
   if (size_in_bytes <= kSmallListMax) {
     node = small_list_.PickNodeFromList(size_in_bytes, node_size);
     if (node != NULL) {
       DCHECK(size_in_bytes <= *node_size);
       page = Page::FromAddress(node->address());
       page->add_available_in_small_free_list(-(*node_size));
@@ skipping 208 matching lines @@
   while (iterator.has_next()) {
     Page* page = iterator.next();
     int size = static_cast<int>(page->non_available_small_blocks());
     if (size == 0) continue;
     Address address = page->OffsetToAddress(Page::kPageSize - size);
     heap()->CreateFillerObjectAt(address, size);
   }
 }
 
 
-void PagedSpace::EvictEvacuationCandidatesFromFreeLists() {
+void PagedSpace::EvictEvacuationCandidatesFromLinearAllocationArea() {
   if (allocation_info_.top() >= allocation_info_.limit()) return;
 
   if (Page::FromAllocationTop(allocation_info_.top())
           ->IsEvacuationCandidate()) {
     // Create filler object to keep page iterable if it was iterable.
     int remaining =
         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);
   }
 }
 
 
 HeapObject* PagedSpace::WaitForSweeperThreadsAndRetryAllocation(
     int size_in_bytes) {
   MarkCompactCollector* collector = heap()->mark_compact_collector();
   if (collector->sweeping_in_progress()) {
     // Wait for the sweeper threads here and complete the sweeping phase.
     collector->EnsureSweepingCompleted();
@@ skipping 545 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8