OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/freelist.h" | 5 #include "vm/freelist.h" |
6 | 6 |
7 #include "vm/object.h" | 7 #include "vm/object.h" |
8 #include "vm/raw_object.h" | 8 #include "vm/raw_object.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
11 | 11 |
12 // Allocate a fake class to be used as the class for elements of the free list. | |
13 // These raw classes are only used to identify free list elements in the heap. | |
14 // These classes cannot be allocated in the heap as the elements of the free | |
15 // list are not live objects and their class references would not be updated | |
16 // during a moving collection. In the general case these classes are also used | |
17 // to implement RawObject::Size() to allow other code to safely traverse | |
18 // the heap without any knowledge of the embedded free list elements. | |
19 RawClass* AllocateFakeClass() { | |
20 RawClass* result = | |
21 reinterpret_cast<RawClass*>(calloc(1, Class::InstanceSize())); | |
22 result->instance_kind_ = kFreeListElement; | |
23 return reinterpret_cast<RawClass*>(RawObject::FromAddr( | |
24 reinterpret_cast<uword>(result))); | |
25 } | |
26 | |
27 | |
28 RawClass* FreeListElement::minimal_element_class_ = NULL; | |
29 RawClass* FreeListElement::element_class_ = NULL; | |
30 | |
31 | 12 |
32 FreeListElement* FreeListElement::AsElement(uword addr, intptr_t size) { | 13 FreeListElement* FreeListElement::AsElement(uword addr, intptr_t size) { |
33 ASSERT(size >= kObjectAlignment); | 14 ASSERT(size >= kObjectAlignment); |
34 ASSERT(Utils::IsAligned(size, kObjectAlignment)); | 15 ASSERT(Utils::IsAligned(size, kObjectAlignment)); |
35 | 16 |
36 FreeListElement* result = reinterpret_cast<FreeListElement*>(addr); | 17 FreeListElement* result = reinterpret_cast<FreeListElement*>(addr); |
37 if (size == kObjectAlignment) { | 18 result->size_ = size; |
38 result->class_ = minimal_element_class_; | |
39 } else { | |
40 result->class_ = element_class_; | |
41 *result->SizeAddress() = size; | |
42 } | |
43 result->set_next(NULL); | 19 result->set_next(NULL); |
44 ASSERT(result->Size() == size); | |
45 return result; | 20 return result; |
46 } | 21 } |
47 | 22 |
48 | 23 |
49 void FreeListElement::InitOnce() { | 24 void FreeListElement::InitOnce() { |
50 ASSERT(sizeof(FreeListElement) == kObjectAlignment); | 25 ASSERT(sizeof(FreeListElement) == kObjectAlignment); |
51 ASSERT(minimal_element_class_ == NULL); | 26 ASSERT(OFFSET_OF(FreeListElement, next_) == Object::tags_offset()); |
52 ASSERT(element_class_ == NULL); | |
53 minimal_element_class_ = AllocateFakeClass(); | |
54 element_class_ = AllocateFakeClass(); | |
55 } | 27 } |
56 | 28 |
57 | 29 |
58 FreeList::FreeList() { | 30 FreeList::FreeList() { |
59 Reset(); | 31 Reset(); |
60 } | 32 } |
61 | 33 |
62 | 34 |
63 FreeList::~FreeList() { | 35 FreeList::~FreeList() { |
64 // Nothing to release. | 36 // Nothing to release. |
(...skipping 16 matching lines...) Expand all Loading... |
81 SplitElementAfterAndEnqueue(element, size); | 53 SplitElementAfterAndEnqueue(element, size); |
82 return reinterpret_cast<uword>(element); | 54 return reinterpret_cast<uword>(element); |
83 } | 55 } |
84 index++; | 56 index++; |
85 } | 57 } |
86 } | 58 } |
87 | 59 |
88 FreeListElement* previous = NULL; | 60 FreeListElement* previous = NULL; |
89 FreeListElement* current = free_lists_[kNumLists]; | 61 FreeListElement* current = free_lists_[kNumLists]; |
90 while (current != NULL) { | 62 while (current != NULL) { |
91 if (current->Size() >= size) { | 63 if (current->size() >= size) { |
92 // Found an element large enough to hold the requested size. Dequeue, | 64 // Found an element large enough to hold the requested size. Dequeue, |
93 // split and enqueue the remainder. | 65 // split and enqueue the remainder. |
94 if (previous == NULL) { | 66 if (previous == NULL) { |
95 free_lists_[kNumLists] = current->next(); | 67 free_lists_[kNumLists] = current->next(); |
96 } else { | 68 } else { |
97 previous->set_next(current->next()); | 69 previous->set_next(current->next()); |
98 } | 70 } |
99 SplitElementAfterAndEnqueue(current, size); | 71 SplitElementAfterAndEnqueue(current, size); |
100 return reinterpret_cast<uword>(current); | 72 return reinterpret_cast<uword>(current); |
101 } | 73 } |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
139 | 111 |
140 FreeListElement* FreeList::DequeueElement(intptr_t index) { | 112 FreeListElement* FreeList::DequeueElement(intptr_t index) { |
141 FreeListElement* result = free_lists_[index]; | 113 FreeListElement* result = free_lists_[index]; |
142 free_lists_[index] = result->next(); | 114 free_lists_[index] = result->next(); |
143 return result; | 115 return result; |
144 } | 116 } |
145 | 117 |
146 | 118 |
147 void FreeList::SplitElementAfterAndEnqueue(FreeListElement* element, | 119 void FreeList::SplitElementAfterAndEnqueue(FreeListElement* element, |
148 intptr_t size) { | 120 intptr_t size) { |
149 intptr_t remainder_size = element->Size() - size; | 121 intptr_t remainder_size = element->size() - size; |
150 if (remainder_size == 0) return; | 122 if (remainder_size == 0) return; |
151 | 123 |
152 element = FreeListElement::AsElement(reinterpret_cast<uword>(element) + size, | 124 element = FreeListElement::AsElement(reinterpret_cast<uword>(element) + size, |
153 remainder_size); | 125 remainder_size); |
154 intptr_t remainder_index = IndexForSize(remainder_size); | 126 intptr_t remainder_index = IndexForSize(remainder_size); |
155 EnqueueElement(element, remainder_index); | 127 EnqueueElement(element, remainder_index); |
156 } | 128 } |
157 | 129 |
158 } // namespace dart | 130 } // namespace dart |
OLD | NEW |