On-the-fly bookkeeping of PagedSpace memory kept in free-lists.

src/spaces.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 449 matching lines @@
   chunk->area_end_ = area_end;
   chunk->flags_ = 0;
   chunk->set_owner(owner);
   chunk->InitializeReservedMemory();
   chunk->slots_buffer_ = NULL;
   chunk->skip_list_ = NULL;
   chunk->write_barrier_counter_ = kWriteBarrierCounterGranularity;
   chunk->progress_bar_ = 0;
   chunk->high_water_mark_ = static_cast<int>(area_start - base);
   chunk->parallel_sweeping_ = 0;
+  chunk->available_in_small_free_list_ = 0;
+  chunk->available_in_medium_free_list_ = 0;
+  chunk->available_in_large_free_list_ = 0;
+  chunk->available_in_huge_free_list_ = 0;
+  chunk->non_available_small_blocks_ = 0;
   chunk->ResetLiveBytes();
   Bitmap::Clear(chunk);
   chunk->initialize_scan_on_scavenge(false);
   chunk->SetFlag(WAS_SWEPT_PRECISELY);
 
   ASSERT(OFFSET_OF(MemoryChunk, flags_) == kFlagsOffset);
   ASSERT(OFFSET_OF(MemoryChunk, live_byte_count_) == kLiveBytesOffset);
 
   if (executable == EXECUTABLE) {
     chunk->SetFlag(IS_EXECUTABLE);
@@ skipping 210 matching lines @@
                                                 chunk_size,
                                                 area_start,
                                                 area_end,
                                                 executable,
                                                 owner);
   result->set_reserved_memory(&reservation);
   return result;
 }
 
 
+void Page::ResetFreeListStatistics() {
+  non_available_small_blocks_ = 0;
+  available_in_small_free_list_ = 0;
+  available_in_medium_free_list_ = 0;
+  available_in_large_free_list_ = 0;
+  available_in_huge_free_list_ = 0;
+}
+
+
 Page* MemoryAllocator::AllocatePage(intptr_t size,
                                     PagedSpace* owner,
                                     Executability executable) {
   MemoryChunk* chunk = AllocateChunk(size, size, executable, owner);
 
   if (chunk == NULL) return NULL;
 
   return Page::Initialize(isolate_->heap(), chunk, executable, owner);
 }
 
@@ skipping 340 matching lines @@
   PageIterator it(this);
   int count = 0;
   while (it.has_next()) {
     it.next();
     count++;
   }
   return count;
 }
 
 
+void PagedSpace::ObtainFreeListStatistics(Page* page, SizeStats* sizes) {
+  sizes->huge_size_ = page->available_in_huge_free_list();
+  sizes->small_size_ = page->available_in_small_free_list();
+  sizes->medium_size_ = page->available_in_medium_free_list();
+  sizes->large_size_ = page->available_in_large_free_list();
+}
+
+
+void PagedSpace::ResetFreeListStatistics() {
+  PageIterator page_iterator(this);
+  while (page_iterator.has_next()) {
+    Page* page = page_iterator.next();
+    page->ResetFreeListStatistics();
+  }
+}
+
+
 void PagedSpace::ReleasePage(Page* page, bool unlink) {
   ASSERT(page->LiveBytes() == 0);
   ASSERT(AreaSize() == page->area_size());
 
   // Adjust list of unswept pages if the page is the head of the list.
   if (first_unswept_page_ == page) {
     first_unswept_page_ = page->next_page();
     if (first_unswept_page_ == anchor()) {
       first_unswept_page_ = Page::FromAddress(NULL);
     }
@@ skipping 979 matching lines @@
 }
 
 
 void FreeListCategory::Reset() {
   top_ = NULL;
   end_ = NULL;
   available_ = 0;
 }
 
 
-intptr_t FreeListCategory::CountFreeListItemsInList(Page* p) {
-  int sum = 0;
-  FreeListNode* n = top_;
-  while (n != NULL) {
-    if (Page::FromAddress(n->address()) == p) {
-      FreeSpace* free_space = reinterpret_cast<FreeSpace*>(n);
-      sum += free_space->Size();
-    }
-    n = n->next();
-  }
-  return sum;
-}
-
-
 intptr_t FreeListCategory::EvictFreeListItemsInList(Page* p) {
   int sum = 0;
   FreeListNode** n = &top_;
   while (*n != NULL) {
     if (Page::FromAddress((*n)->address()) == p) {
       FreeSpace* free_space = reinterpret_cast<FreeSpace*>(*n);
       sum += free_space->Size();
       *n = (*n)->next();
     } else {
       n = (*n)->next_address();
@@ skipping 80 matching lines @@
   large_list_.Reset();
   huge_list_.Reset();
 }
 
 
 int FreeList::Free(Address start, int size_in_bytes) {
   if (size_in_bytes == 0) return 0;
 
   FreeListNode* node = FreeListNode::FromAddress(start);
   node->set_size(heap_, size_in_bytes);
+  Page* page = Page::FromAddress(start);
 
   // Early return to drop too-small blocks on the floor.
-  if (size_in_bytes < kSmallListMin) return size_in_bytes;
+  if (size_in_bytes < kSmallListMin) {
+    page->add_non_available_small_blocks(size_in_bytes);
+    return size_in_bytes;
+  }
 
   // Insert other blocks at the head of a free list of the appropriate
   // magnitude.
   if (size_in_bytes <= kSmallListMax) {
     small_list_.Free(node, size_in_bytes);
+    page->add_available_in_small_free_list(size_in_bytes);
   } else if (size_in_bytes <= kMediumListMax) {
     medium_list_.Free(node, size_in_bytes);
+    page->add_available_in_medium_free_list(size_in_bytes);
   } else if (size_in_bytes <= kLargeListMax) {
     large_list_.Free(node, size_in_bytes);
+    page->add_available_in_large_free_list(size_in_bytes);
   } else {
     huge_list_.Free(node, size_in_bytes);
+    page->add_available_in_huge_free_list(size_in_bytes);
   }
 
   ASSERT(IsVeryLong() || available() == SumFreeLists());
   return 0;
 }
 
 
 FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
   FreeListNode* node = NULL;
+  Page* page = NULL;
 
   if (size_in_bytes <= kSmallAllocationMax) {
     node = small_list_.PickNodeFromList(node_size);
-    if (node != NULL) return node;
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_small_free_list(-(*node_size));
+      return node;
+    }
   }
 
   if (size_in_bytes <= kMediumAllocationMax) {
     node = medium_list_.PickNodeFromList(node_size);
-    if (node != NULL) return node;
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_medium_free_list(-(*node_size));
+      return node;
+    }
   }
 
   if (size_in_bytes <= kLargeAllocationMax) {
     node = large_list_.PickNodeFromList(node_size);
-    if (node != NULL) return node;
+    if (node != NULL) {
+      page = Page::FromAddress(node->address());
+      page->add_available_in_large_free_list(-(*node_size));
+      return node;
+    }
   }
 
   int huge_list_available = huge_list_.available();
   for (FreeListNode** cur = huge_list_.GetTopAddress();
        *cur != NULL;
        cur = (*cur)->next_address()) {
     FreeListNode* cur_node = *cur;
     while (cur_node != NULL &&
            Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
-      huge_list_available -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
+      int size = reinterpret_cast<FreeSpace*>(cur_node)->Size();
+      huge_list_available -= size;
+      page = Page::FromAddress(cur_node->address());
+      page->add_available_in_huge_free_list(-size);
       cur_node = cur_node->next();
     }
 
     *cur = cur_node;
     if (cur_node == NULL) {
       huge_list_.set_end(NULL);
       break;
     }
 
     ASSERT((*cur)->map() == heap_->raw_unchecked_free_space_map());
     FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
     int size = cur_as_free_space->Size();
     if (size >= size_in_bytes) {
       // Large enough node found.  Unlink it from the list.
       node = *cur;
       *cur = node->next();
       *node_size = size;
       huge_list_available -= size;
+      page = Page::FromAddress(node->address());
+      page->add_available_in_huge_free_list(-size);
       break;
     }
   }
 
   if (huge_list_.top() == NULL) {
     huge_list_.set_end(NULL);
   }
 
   huge_list_.set_available(huge_list_available);
   ASSERT(IsVeryLong() || available() == SumFreeLists());
@@ skipping 67 matching lines @@
   } else {
     // TODO(gc) Try not freeing linear allocation region when bytes_left
     // are zero.
     owner_->SetTop(NULL, NULL);
   }
 
   return new_node;
 }
 
 
-void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
-  sizes->huge_size_ = huge_list_.CountFreeListItemsInList(p);
-  if (sizes->huge_size_ < p->area_size()) {
-    sizes->small_size_ = small_list_.CountFreeListItemsInList(p);
-    sizes->medium_size_ = medium_list_.CountFreeListItemsInList(p);
-    sizes->large_size_ = large_list_.CountFreeListItemsInList(p);
-  } else {
-    sizes->small_size_ = 0;
-    sizes->medium_size_ = 0;
-    sizes->large_size_ = 0;
-  }
-}
-
-
 intptr_t FreeList::EvictFreeListItems(Page* p) {
   intptr_t sum = huge_list_.EvictFreeListItemsInList(p);
+  p->set_available_in_huge_free_list(0);
 
   if (sum < p->area_size()) {
     sum += small_list_.EvictFreeListItemsInList(p) +
         medium_list_.EvictFreeListItemsInList(p) +
         large_list_.EvictFreeListItemsInList(p);
+    p->set_available_in_small_free_list(0);
+    p->set_available_in_medium_free_list(0);
+    p->set_available_in_large_free_list(0);
   }
 
   return sum;
 }
 
 
 void FreeList::RepairLists(Heap* heap) {
   small_list_.RepairFreeList(heap);
   medium_list_.RepairFreeList(heap);
   large_list_.RepairFreeList(heap);
@@ skipping 787 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 
 } }  // namespace v8::internal