Bump allocation for promotion

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 <map>
 
 #include "vm/bit_set.h"
 #include "vm/lockers.h"
@@ skipping 178 matching lines @@
   intptr_t index = IndexForSize(size);
   FreeListElement* element = FreeListElement::AsElement(addr, size);
   EnqueueElement(element, index);
   // Postcondition: the (page containing the) header is left writable.
 }
 
 
 void FreeList::Reset() {
   MutexLocker ml(mutex_);
   free_map_.Reset();
+  last_free_small_size_ = -1;
   for (int i = 0; i < (kNumLists + 1); i++) {
     free_lists_[i] = NULL;
   }
 }
 
 
 intptr_t FreeList::IndexForSize(intptr_t size) {
   ASSERT(size >= kObjectAlignment);
   ASSERT(Utils::IsAligned(size, kObjectAlignment));
 
-  intptr_t index = size / kObjectAlignment;
+  intptr_t index = size >> kObjectAlignmentLog2;
   if (index >= kNumLists) {
     index = kNumLists;
   }
   return index;
 }
 
 
 void FreeList::EnqueueElement(FreeListElement* element, intptr_t index) {
   FreeListElement* next = free_lists_[index];
   if (next == NULL && index != kNumLists) {
     free_map_.Set(index, true);
+    last_free_small_size_ = Utils::Maximum(last_free_small_size_,
+                                           index << kObjectAlignmentLog2);
   }
   element->set_next(next);
   free_lists_[index] = element;
 }
 
 
 FreeListElement* FreeList::DequeueElement(intptr_t index) {
   FreeListElement* result = free_lists_[index];
   FreeListElement* next = result->next();
   if (next == NULL && index != kNumLists) {
     free_map_.Set(index, false);
+    intptr_t size = index << kObjectAlignmentLog2;
+    if (size == last_free_small_size_) {
+      // Note: Last() returns -1 if none are set; avoid shift of negative.
+      last_free_small_size_ = free_map_.Last() * kObjectAlignment;
+      // TODO(koda): Consider adding BitSet::Previous(i).
+    }
   }
   free_lists_[index] = next;
   return result;
 }
 
 
 intptr_t FreeList::LengthLocked(int index) const {
   DEBUG_ASSERT(mutex_->Owner() == Isolate::Current());
   ASSERT(index >= 0);
   ASSERT(index < kNumLists);
@@ skipping 95 matching lines @@
         VirtualMemory::Protect(reinterpret_cast<void*>(remainder_address),
                                remainder_size,
                                VirtualMemory::kReadExecute);
     ASSERT(status);
   }
 }
 
 
 FreeListElement* FreeList::TryAllocateLarge(intptr_t minimum_size) {
   MutexLocker ml(mutex_);
+  return TryAllocateLargeLocked(minimum_size);
+}
+
+
+FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) {
+  DEBUG_ASSERT(mutex_->Owner() == Isolate::Current());
   FreeListElement* previous = NULL;
   FreeListElement* current = free_lists_[kNumLists];
   // TODO(koda): Find largest.
   while (current != NULL) {
     FreeListElement* next = current->next();
     if (current->Size() >= minimum_size) {
       if (previous == NULL) {
         free_lists_[kNumLists] = next;
       } else {
         previous->set_next(next);
       }
       return current;
     }
     previous = current;
     current = next;
   }
   return NULL;
 }
 
+
+uword FreeList::TryAllocateSmallLocked(intptr_t size) {
+  DEBUG_ASSERT(mutex_->Owner() == Isolate::Current());
+  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