Avoid scanning huge freelists for large enough free blocks.

runtime/vm/freelist.cc

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/freelist.h"
 
 #include "vm/bit_set.h"
 #include "vm/hash_map.h"
 #include "vm/lockers.h"
 #include "vm/object.h"
@@ skipping 33 matching lines @@
   ASSERT(OFFSET_OF(FreeListElement, tags_) == Object::tags_offset());
 }
 
 
 intptr_t FreeListElement::HeaderSizeFor(intptr_t size) {
   if (size == 0) return 0;
   return ((size > RawObject::SizeTag::kMaxSizeTag) ? 3 : 2) * kWordSize;
 }
 
 
-FreeList::FreeList() : mutex_(new Mutex()) {
+FreeList::FreeList()
+    : mutex_(new Mutex()), freelist_health_(kMaxFreelistHealth) {
   Reset();
 }
 
 
 FreeList::~FreeList() {
   delete mutex_;
 }
 
 
 uword FreeList::TryAllocate(intptr_t size, bool is_protected) {
@@ skipping 39 matching lines @@
                                    region_size, VirtualMemory::kReadWrite);
         ASSERT(status);
       }
       SplitElementAfterAndEnqueue(element, size, is_protected);
       return reinterpret_cast<uword>(element);
     }
   }
 
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
+  // We are willing to search the freelist further for a big block.
+  intptr_t tries_left = freelist_health_ + (size >> kWordSizeLog2);

[kustermann, 2017/05/10 21:39:40]

Maybe add a more elaborate comment explaining what this does, something like:

"""
For each successful free-list search we:
  * increase the search budget by #allocated-words
  * decrease the search budget by #free-list-entries-traversed
which guarantees us to not waste more than around 1 search step per word of
allocation

Furthermore, to guarantee reasonable allocation latency we limit the number of
searches to be at most kMaxFreelistHealth.

After falling back to allocating a new page, we reset the search budget.
"""

   while (current != NULL) {
     if (current->Size() >= size) {
       // Found an element large enough to hold the requested size. Dequeue,
       // split and enqueue the remainder.
       intptr_t remainder_size = current->Size() - size;
       intptr_t region_size =
           size + FreeListElement::HeaderSizeFor(remainder_size);
       if (is_protected) {
         // Make the allocated block and the header of the remainder element
         // writable.  The remainder will be non-writable if necessary after
@@ skipping 28 matching lines @@
         }
         previous->set_next(current->next());
         if (target_is_protected) {
           bool status =
               VirtualMemory::Protect(reinterpret_cast<void*>(target_address),
                                      kWordSize, VirtualMemory::kReadExecute);
           ASSERT(status);
         }
       }
       SplitElementAfterAndEnqueue(current, size, is_protected);
+      freelist_health_ = Utils::Minimum(tries_left, kMaxFreelistHealth);

[kustermann, 2017/05/10 21:39:40]

The Utils::Minimum is only for reducing allocation latency, right?

We would still get the guarantee to not waste more than 1 free list search per
allocated word if we just set:

freelist_health_ = tries_left;

       return reinterpret_cast<uword>(current);
+    } else if (tries_left-- < 0) {
+      freelist_health_ = kMaxFreelistHealth;
+      return 0;  // Trigger allocation of new page.
     }
     previous = current;
     current = current->next();
   }
   return 0;
 }
 
 
 void FreeList::Free(uword addr, intptr_t size) {
   MutexLocker ml(mutex_);
@@ skipping 202 matching lines @@
   MutexLocker ml(mutex_);
   return TryAllocateLargeLocked(minimum_size);
 }
 
 
 FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) {
   DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread());
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
   // TODO(koda): Find largest.
+  // We are willing to search the freelist further for a big block.
+  intptr_t tries_left = freelist_health_ + (minimum_size >> kWordSizeLog2);
   while (current != NULL) {
     FreeListElement* next = current->next();
     if (current->Size() >= minimum_size) {
       if (previous == NULL) {
         free_lists_[kNumLists] = next;
       } else {
         previous->set_next(next);
       }
+      freelist_health_ = Utils::Minimum(tries_left, kMaxFreelistHealth);
       return current;
+    } else if (tries_left-- < 0) {
+      freelist_health_ = kMaxFreelistHealth;
+      return 0;  // Trigger allocation of new page.
     }
     previous = current;
     current = next;
   }
   return NULL;
 }
 
 
 uword FreeList::TryAllocateSmallLocked(intptr_t size) {
   DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread());
   if (size > last_free_small_size_) {
     return 0;
   }
   int index = IndexForSize(size);
   if (index != kNumLists && free_map_.Test(index)) {
     return reinterpret_cast<uword>(DequeueElement(index));
   }
   if ((index + 1) < kNumLists) {
     intptr_t next_index = free_map_.Next(index + 1);
     if (next_index != -1) {
       FreeListElement* element = DequeueElement(next_index);
       SplitElementAfterAndEnqueue(element, size, false);
       return reinterpret_cast<uword>(element);
     }
   }
   return 0;
 }
 
 }  // namespace dart