Index: src/spaces.cc |
diff --git a/src/spaces.cc b/src/spaces.cc |
index cacd9691501c10428a7a2b97d3a810cfd683789a..afe2b5284079483d6b609ceb5779f61e2e82c60e 100644 |
--- a/src/spaces.cc |
+++ b/src/spaces.cc |
@@ -1929,52 +1929,106 @@ void FreeListNode::set_next(FreeListNode* next) { |
} |
-FreeList::FreeList(PagedSpace* owner) |
- : owner_(owner), heap_(owner->heap()) { |
- Reset(); |
+void FreeListCategory::Reset() { |
+ top_ = NULL; |
+ end_ = NULL; |
+ available_ = 0; |
} |
-void FreeList::Reset() { |
- available_ = 0; |
- small_list_ = NULL; |
- medium_list_ = NULL; |
- large_list_ = NULL; |
- huge_list_ = NULL; |
+void FreeListCategory:: |
+ ConcatenateListsConcurrentAdd(FreeListCategory* category) { |
Michael Starzinger
2012/11/29 14:31:20
Let's break the line after the opening parenthesis
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ FreeListNode* current_top; |
+ FreeListNode* category_top = category->top(); |
+ FreeListNode* category_end = category->end(); |
+ |
+ do { |
+ current_top = top_; |
+ if (current_top == NULL) { |
+ end_ = category_end; |
+ top_ = category_top; |
+ break; |
+ } |
Michael Starzinger
2012/11/29 14:31:20
The adjustment category_end->next to current_top i
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ } while (current_top != top_ || |
+ NoBarrier_CompareAndSwap( |
+ reinterpret_cast<AtomicWord*>(&top_), |
+ reinterpret_cast<AtomicWord>(current_top), |
+ reinterpret_cast<AtomicWord>(category_top)) != |
+ reinterpret_cast<AtomicWord>(current_top)); |
+ NoBarrier_AtomicIncrement(reinterpret_cast<AtomicWord*>(&available_), |
+ category->available()); |
+ category->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); |
+void FreeListCategory:: |
+ ConcatenateListsConcurrentRemove(FreeListCategory* category) { |
Michael Starzinger
2012/11/29 14:31:20
Likewise.
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ if (category->top() == NULL) { |
+ return; |
+ } |
- // Early return to drop too-small blocks on the floor. |
- if (size_in_bytes < kSmallListMin) return size_in_bytes; |
+ FreeListNode* category_top; |
+ FreeListNode* category_end; |
+ FreeListNode** category_top_address = category->GetTopAddress(); |
+ FreeListNode** category_end_address = category->GetEndAddress(); |
+ int* category_available_address = category->GetAvailableAddress(); |
+ int category_available; |
- // 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; |
- } else if (size_in_bytes <= kMediumListMax) { |
- node->set_next(medium_list_); |
- medium_list_ = node; |
- } else if (size_in_bytes <= kLargeListMax) { |
- node->set_next(large_list_); |
- large_list_ = node; |
- } else { |
- node->set_next(huge_list_); |
- huge_list_ = node; |
+ do { |
+ category_top = category->top(); |
Michael Starzinger
2012/11/29 14:31:20
This requires the memory model to ensure that we d
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ category_end = category->end(); |
+ category_available = category->available(); |
+ } while (category_top != category->top() || |
+ NoBarrier_CompareAndSwap( |
+ reinterpret_cast<AtomicWord*>(category_top_address), |
+ reinterpret_cast<AtomicWord>(category_top), 0) != |
+ reinterpret_cast<AtomicWord>(category_top)); |
+ NoBarrier_CompareAndSwap( |
+ reinterpret_cast<AtomicWord*>(category_end_address), |
+ reinterpret_cast<AtomicWord>(category_end), 0); |
Michael Starzinger
2012/11/29 14:31:20
Since we don't need the category->end to be in a c
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ NoBarrier_AtomicIncrement( |
+ reinterpret_cast<AtomicWord*>(category_available_address), |
+ -category_available); |
+ |
+ category_end->set_next(top_); |
+ top_ = category_top; |
+ available_ += category_available; |
+} |
+ |
+ |
+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(); |
} |
- available_ += size_in_bytes; |
- ASSERT(IsVeryLong() || available_ == SumFreeLists()); |
- return 0; |
+ 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(); |
+ } |
+ } |
Michael Starzinger
2012/11/29 14:31:20
We need to adjust the end pointer in case you evic
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ available_ -= sum; |
+ return sum; |
} |
-FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int* node_size) { |
- FreeListNode* node = *list; |
+FreeListNode* FreeListCategory::PickNodeFromList(int *node_size) { |
+ FreeListNode* node = top_; |
if (node == NULL) return NULL; |
@@ -1985,46 +2039,119 @@ FreeListNode* FreeList::PickNodeFromList(FreeListNode** list, int* node_size) { |
} |
if (node != NULL) { |
+ set_top(node->next()); |
*node_size = node->Size(); |
- *list = node->next(); |
+ available_ -= *node_size; |
} else { |
- *list = NULL; |
+ 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) |
+ : owner_(owner), heap_(owner->heap()) { |
+ Reset(); |
+} |
+ |
+ |
+void FreeList::Reset() { |
+ 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); |
+ |
+ // Early return to drop too-small blocks on the floor. |
+ if (size_in_bytes < kSmallListMin) 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); |
+ } else if (size_in_bytes <= kMediumListMax) { |
+ medium_list_.Free(node, size_in_bytes); |
+ } else if (size_in_bytes <= kLargeListMax) { |
+ large_list_.Free(node, size_in_bytes); |
+ } else { |
+ huge_list_.Free(node, size_in_bytes); |
+ } |
+ |
+ ASSERT(IsVeryLong() || available() == SumFreeLists()); |
+ return 0; |
+} |
+ |
+ |
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,12 +2159,16 @@ FreeListNode* FreeList::FindNodeFor(int size_in_bytes, int* node_size) { |
if (size >= size_in_bytes) { |
// Large enough node found. Unlink it from the list. |
node = *cur; |
- *node_size = size; |
*cur = node->next(); |
Michael Starzinger
2012/11/29 14:31:20
We also need to reset the end pointer in case we p
Hannes Payer (out of office)
2012/11/29 15:55:02
Done.
|
+ *node_size = size; |
+ huge_list_available -= size; |
break; |
} |
} |
+ huge_list_.set_available(huge_list_available); |
+ ASSERT(IsVeryLong() || available() == SumFreeLists()); |
+ |
return node; |
} |
@@ -2057,8 +2188,6 @@ HeapObject* FreeList::Allocate(int size_in_bytes) { |
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); |
@@ -2116,25 +2245,12 @@ HeapObject* FreeList::Allocate(int size_in_bytes) { |
} |
-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; |
@@ -2143,39 +2259,31 @@ void FreeList::CountFreeListItems(Page* p, SizeStats* sizes) { |
} |
-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; |
} |
+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 +2297,9 @@ intptr_t FreeList::SumFreeList(FreeListNode* cur) { |
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 +2310,10 @@ int FreeList::FreeListLength(FreeListNode* cur) { |
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 +2322,10 @@ bool FreeList::IsVeryLong() { |
// 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 |
@@ -2304,27 +2413,6 @@ bool PagedSpace::ReserveSpace(int size_in_bytes) { |
} |
-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 |
// on the heap. If there was already a free list then the elements on it |
// were created with the wrong FreeSpaceMap (normally NULL), so we need to |