Revision: 13198
Author: [email protected]
Date: Tue Dec 11 09:45:01 2012
Log: Prepare FreeList for parallel and concurrent sweeping.
BUG=
Review URL: https://codereview.chromium.org/11348174
http://code.google.com/p/v8/source/detail?r=13198
Modified:
/branches/bleeding_edge/src/spaces.cc
/branches/bleeding_edge/src/spaces.h
=======================================
--- /branches/bleeding_edge/src/spaces.cc Mon Dec 10 03:09:12 2012
+++ /branches/bleeding_edge/src/spaces.cc Tue Dec 11 09:45:01 2012
@@ -1927,6 +1927,98 @@
reinterpret_cast<Address>(next);
}
}
+
+
+void FreeListCategory::Reset() {
+ top_ = NULL;
+ end_ = NULL;
+ available_ = 0;
+}
+
+
+intptr_t FreeListCategory::CountFreeListItemsInList(Page* p) {
+ intptr_t 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) {
+ intptr_t 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();
+ }
+ }
+ if (top_ == NULL) {
+ end_ = NULL;
+ }
+ available_ -= sum;
+ return sum;
+}
+
+
+FreeListNode* FreeListCategory::PickNodeFromList(int *node_size) {
+ FreeListNode* node = top_;
+
+ if (node == NULL) return NULL;
+
+ while (node != NULL &&
+ Page::FromAddress(node->address())->IsEvacuationCandidate()) {
+ available_ -= node->Size();
+ node = node->next();
+ }
+
+ if (node != NULL) {
+ set_top(node->next());
+ *node_size = node->Size();
+ available_ -= *node_size;
+ } else {
+ set_top(NULL);
+ }
+
+ if (top() == NULL) {
+ set_end(NULL);
+ }
+
+ return node;
+}
+
+
+void FreeListCategory::Free(FreeListNode* node, int size_in_bytes) {
+ node->set_next(top_);
+ top_ = node;
+ if (end_ == NULL) {
+ end_ = node;
+ }
+ available_ += size_in_bytes;
+}
+
+
+void FreeListCategory::RepairFreeList(Heap* heap) {
+ FreeListNode* n = top_;
+ while (n != NULL) {
+ Map** map_location = reinterpret_cast<Map**>(n->address());
+ if (*map_location == NULL) {
+ *map_location = heap->free_space_map();
+ } else {
+ ASSERT(*map_location == heap->free_space_map());
+ }
+ n = n->next();
+ }
+}
FreeList::FreeList(PagedSpace* owner)
@@ -1936,16 +2028,16 @@
void FreeList::Reset() {
- available_ = 0;
- small_list_ = NULL;
- medium_list_ = NULL;
- large_list_ = NULL;
- huge_list_ = NULL;
+ small_list_.Reset();
+ medium_list_.Reset();
+ 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);
@@ -1955,76 +2047,54 @@
// Insert other blocks at the head of a free list of the appropriate
// magnitude.
if (size_in_bytes <= kSmallListMax) {
- node->set_next(small_list_);
- small_list_ = node;
+ small_list_.Free(node, size_in_bytes);
} else if (size_in_bytes <= kMediumListMax) {
- node->set_next(medium_list_);
- medium_list_ = node;
+ medium_list_.Free(node, size_in_bytes);
} else if (size_in_bytes <= kLargeListMax) {
- node->set_next(large_list_);
- large_list_ = node;
+ large_list_.Free(node, size_in_bytes);
} else {
- node->set_next(huge_list_);
- huge_list_ = node;
+ huge_list_.Free(node, size_in_bytes);
}
- available_ += size_in_bytes;
- ASSERT(IsVeryLong() || available_ == SumFreeLists());
+
+ ASSERT(IsVeryLong() || available() == SumFreeLists());
return 0;
}
-
-
-FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int*
node_size) {
- FreeListNode* node = *list;
-
- if (node == NULL) return NULL;
-
- while (node != NULL &&
- Page::FromAddress(node->address())->IsEvacuationCandidate()) {
- available_ -= node->Size();
- node = node->next();
- }
-
- if (node != NULL) {
- *node_size = node->Size();
- *list = node->next();
- } else {
- *list = NULL;
- }
-
- return node;
-}
FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
FreeListNode* node = NULL;
if (size_in_bytes <= kSmallAllocationMax) {
- node = PickNodeFromList(&small_list_, node_size);
+ node = small_list_.PickNodeFromList(node_size);
if (node != NULL) return node;
}
if (size_in_bytes <= kMediumAllocationMax) {
- node = PickNodeFromList(&medium_list_, node_size);
+ node = medium_list_.PickNodeFromList(node_size);
if (node != NULL) return node;
}
if (size_in_bytes <= kLargeAllocationMax) {
- node = PickNodeFromList(&large_list_, node_size);
+ node = large_list_.PickNodeFromList(node_size);
if (node != NULL) return node;
}
- for (FreeListNode** cur = &huge_list_;
+ 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()) {
- available_ -= reinterpret_cast<FreeSpace*>(cur_node)->Size();
+ huge_list_available -=
reinterpret_cast<FreeSpace*>(cur_node)->Size();
cur_node = cur_node->next();
}
*cur = cur_node;
- if (cur_node == NULL) break;
+ 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);
@@ -2032,11 +2102,19 @@
if (size >= size_in_bytes) {
// Large enough node found. Unlink it from the list.
node = *cur;
+ *cur = node->next();
*node_size = size;
- *cur = node->next();
+ huge_list_available -= size;
break;
}
}
+
+ if (huge_list_.top() == NULL) {
+ huge_list_.set_end(NULL);
+ }
+
+ huge_list_.set_available(huge_list_available);
+ ASSERT(IsVeryLong() || available() == SumFreeLists());
return node;
}
@@ -2057,8 +2135,6 @@
FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
if (new_node == NULL) return NULL;
- available_ -= new_node_size;
- ASSERT(IsVeryLong() || available_ == SumFreeLists());
int bytes_left = new_node_size - size_in_bytes;
ASSERT(bytes_left >= 0);
@@ -2114,68 +2190,47 @@
return new_node;
}
-
-
-static intptr_t CountFreeListItemsInList(FreeListNode* n, Page* p) {
- intptr_t sum = 0;
- 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;
-}
void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) {
- sizes->huge_size_ = CountFreeListItemsInList(huge_list_, p);
+ sizes->huge_size_ = huge_list_.CountFreeListItemsInList(p);
if (sizes->huge_size_ < p->area_size()) {
- sizes->small_size_ = CountFreeListItemsInList(small_list_, p);
- sizes->medium_size_ = CountFreeListItemsInList(medium_list_, p);
- sizes->large_size_ = CountFreeListItemsInList(large_list_, p);
+ 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;
}
-}
-
-
-static intptr_t EvictFreeListItemsInList(FreeListNode** n, Page* p) {
- intptr_t sum = 0;
- 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();
- }
- }
- return sum;
}
intptr_t FreeList::EvictFreeListItems(Page* p) {
- intptr_t sum = EvictFreeListItemsInList(&huge_list_, p);
+ intptr_t sum = huge_list_.EvictFreeListItemsInList(p);
if (sum < p->area_size()) {
- sum += EvictFreeListItemsInList(&small_list_, p) +
- EvictFreeListItemsInList(&medium_list_, p) +
- EvictFreeListItemsInList(&large_list_, p);
+ sum += small_list_.EvictFreeListItemsInList(p) +
+ medium_list_.EvictFreeListItemsInList(p) +
+ large_list_.EvictFreeListItemsInList(p);
}
- available_ -= static_cast<int>(sum);
+ return sum;
+}
+
- return sum;
+void FreeList::RepairLists(Heap* heap) {
+ small_list_.RepairFreeList(heap);
+ medium_list_.RepairFreeList(heap);
+ large_list_.RepairFreeList(heap);
+ huge_list_.RepairFreeList(heap);
}
#ifdef DEBUG
-intptr_t FreeList::SumFreeList(FreeListNode* cur) {
+intptr_t FreeListCategory::SumFreeList() {
intptr_t sum = 0;
+ FreeListNode* cur = top_;
while (cur != NULL) {
ASSERT(cur->map() == HEAP->raw_unchecked_free_space_map());
FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(cur);
@@ -2189,8 +2244,9 @@
static const int kVeryLongFreeList = 500;
-int FreeList::FreeListLength(FreeListNode* cur) {
+int FreeListCategory::FreeListLength() {
int length = 0;
+ FreeListNode* cur = top_;
while (cur != NULL) {
length++;
cur = cur->next();
@@ -2201,10 +2257,10 @@
bool FreeList::IsVeryLong() {
- if (FreeListLength(small_list_) == kVeryLongFreeList) return true;
- if (FreeListLength(medium_list_) == kVeryLongFreeList) return true;
- if (FreeListLength(large_list_) == kVeryLongFreeList) return true;
- if (FreeListLength(huge_list_) == kVeryLongFreeList) return true;
+ if (small_list_.FreeListLength() == kVeryLongFreeList) return true;
+ if (medium_list_.FreeListLength() == kVeryLongFreeList) return true;
+ if (large_list_.FreeListLength() == kVeryLongFreeList) return true;
+ if (huge_list_.FreeListLength() == kVeryLongFreeList) return true;
return false;
}
@@ -2213,10 +2269,10 @@
// on the free list, so it should not be called if FreeListLength returns
// kVeryLongFreeList.
intptr_t FreeList::SumFreeLists() {
- intptr_t sum = SumFreeList(small_list_);
- sum += SumFreeList(medium_list_);
- sum += SumFreeList(large_list_);
- sum += SumFreeList(huge_list_);
+ intptr_t sum = small_list_.SumFreeList();
+ sum += medium_list_.SumFreeList();
+ sum += large_list_.SumFreeList();
+ sum += huge_list_.SumFreeList();
return sum;
}
#endif
@@ -2302,27 +2358,6 @@
SetTop(new_area->address(), new_area->address() + size_in_bytes);
return true;
}
-
-
-static void RepairFreeList(Heap* heap, FreeListNode* n) {
- while (n != NULL) {
- Map** map_location = reinterpret_cast<Map**>(n->address());
- if (*map_location == NULL) {
- *map_location = heap->free_space_map();
- } else {
- ASSERT(*map_location == heap->free_space_map());
- }
- n = n->next();
- }
-}
-
-
-void FreeList::RepairLists(Heap* heap) {
- RepairFreeList(heap, small_list_);
- RepairFreeList(heap, medium_list_);
- RepairFreeList(heap, large_list_);
- RepairFreeList(heap, huge_list_);
-}
// After we have booted, we have created a map which represents free space
=======================================
--- /branches/bleeding_edge/src/spaces.h Thu Nov 29 07:13:49 2012
+++ /branches/bleeding_edge/src/spaces.h Tue Dec 11 09:45:01 2012
@@ -1381,6 +1381,50 @@
};
+// The free list category holds a pointer to the top element and a pointer
to
+// the end element of the linked list of free memory blocks.
+class FreeListCategory {
+ public:
+ FreeListCategory() : top_(NULL), end_(NULL), available_(0) {}
+
+ void Reset();
+
+ void Free(FreeListNode* node, int size_in_bytes);
+
+ FreeListNode* PickNodeFromList(int *node_size);
+
+ intptr_t CountFreeListItemsInList(Page* p);
+
+ intptr_t EvictFreeListItemsInList(Page* p);
+
+ void RepairFreeList(Heap* heap);
+
+ FreeListNode** GetTopAddress() { return &top_; }
+ FreeListNode* top() const { return top_; }
+ void set_top(FreeListNode* top) { top_ = top; }
+
+ FreeListNode** GetEndAddress() { return &end_; }
+ FreeListNode* end() const { return end_; }
+ void set_end(FreeListNode* end) { end_ = end; }
+
+ int* GetAvailableAddress() { return &available_; }
+ int available() const { return available_; }
+ void set_available(int available) { available_ = available; }
+
+#ifdef DEBUG
+ intptr_t SumFreeList();
+ int FreeListLength();
+#endif
+
+ private:
+ FreeListNode* top_;
+ FreeListNode* end_;
+
+ // Total available bytes in all blocks of this free list category.
+ int available_;
+};
+
+
// The free list for the old space. The free list is organized in such a
way
// as to encourage objects allocated around the same time to be near each
// other. The normal way to allocate is intended to be by bumping a 'top'
@@ -1412,7 +1456,10 @@
void Reset();
// Return the number of bytes available on the free list.
- intptr_t available() { return available_; }
+ intptr_t available() {
+ return small_list_.available() + medium_list_.available() +
+ large_list_.available() + huge_list_.available();
+ }
// Place a node on the free list. The block of size 'size_in_bytes'
// starting at 'start' is placed on the free list. The return value is
the
@@ -1430,8 +1477,6 @@
#ifdef DEBUG
void Zap();
- static intptr_t SumFreeList(FreeListNode* node);
- static int FreeListLength(FreeListNode* cur);
intptr_t SumFreeLists();
bool IsVeryLong();
#endif
@@ -1459,16 +1504,11 @@
static const int kMinBlockSize = 3 * kPointerSize;
static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize;
- FreeListNode* PickNodeFromList(FreeListNode** list, int* node_size);
-
FreeListNode* FindNodeFor(int size_in_bytes, int* node_size);
PagedSpace* owner_;
Heap* heap_;
- // Total available bytes in all blocks on this free list.
- int available_;
-
static const int kSmallListMin = 0x20 * kPointerSize;
static const int kSmallListMax = 0xff * kPointerSize;
static const int kMediumListMax = 0x7ff * kPointerSize;
@@ -1476,10 +1516,10 @@
static const int kSmallAllocationMax = kSmallListMin - kPointerSize;
static const int kMediumAllocationMax = kSmallListMax;
static const int kLargeAllocationMax = kMediumListMax;
- FreeListNode* small_list_;
- FreeListNode* medium_list_;
- FreeListNode* large_list_;
- FreeListNode* huge_list_;
+ FreeListCategory small_list_;
+ FreeListCategory medium_list_;
+ FreeListCategory large_list_;
+ FreeListCategory huge_list_;
DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
};
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
