OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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/object_id_ring.h" |
| 6 |
5 #include "platform/assert.h" | 7 #include "platform/assert.h" |
6 #include "vm/dart_api_state.h" | 8 #include "vm/dart_api_state.h" |
7 #include "vm/json_stream.h" | 9 #include "vm/json_stream.h" |
8 #include "vm/object_id_ring.h" | |
9 | 10 |
10 namespace dart { | 11 namespace dart { |
11 | 12 |
12 #ifndef PRODUCT | 13 #ifndef PRODUCT |
13 | 14 |
14 void ObjectIdRing::Init(Isolate* isolate, int32_t capacity) { | 15 void ObjectIdRing::Init(Isolate* isolate, int32_t capacity) { |
15 ObjectIdRing* ring = new ObjectIdRing(isolate, capacity); | 16 ObjectIdRing* ring = new ObjectIdRing(isolate, capacity); |
16 isolate->set_object_id_ring(ring); | 17 isolate->set_object_id_ring(ring); |
17 } | 18 } |
18 | 19 |
19 | |
20 ObjectIdRing::~ObjectIdRing() { | 20 ObjectIdRing::~ObjectIdRing() { |
21 ASSERT(table_ != NULL); | 21 ASSERT(table_ != NULL); |
22 free(table_); | 22 free(table_); |
23 table_ = NULL; | 23 table_ = NULL; |
24 if (isolate_ != NULL) { | 24 if (isolate_ != NULL) { |
25 isolate_->set_object_id_ring(NULL); | 25 isolate_->set_object_id_ring(NULL); |
26 isolate_ = NULL; | 26 isolate_ = NULL; |
27 } | 27 } |
28 } | 28 } |
29 | 29 |
30 | |
31 int32_t ObjectIdRing::GetIdForObject(RawObject* object, IdPolicy policy) { | 30 int32_t ObjectIdRing::GetIdForObject(RawObject* object, IdPolicy policy) { |
32 // We do not allow inserting null because null is how we detect as entry was | 31 // We do not allow inserting null because null is how we detect as entry was |
33 // reclaimed by the GC. | 32 // reclaimed by the GC. |
34 ASSERT(object != Object::null()); | 33 ASSERT(object != Object::null()); |
35 if (policy == kAllocateId) { | 34 if (policy == kAllocateId) { |
36 return AllocateNewId(object); | 35 return AllocateNewId(object); |
37 } | 36 } |
38 ASSERT(policy == kReuseId); | 37 ASSERT(policy == kReuseId); |
39 int32_t id = FindExistingIdForObject(object); | 38 int32_t id = FindExistingIdForObject(object); |
40 if (id != kInvalidId) { | 39 if (id != kInvalidId) { |
41 // Return a previous id for |object|. | 40 // Return a previous id for |object|. |
42 return id; | 41 return id; |
43 } | 42 } |
44 return AllocateNewId(object); | 43 return AllocateNewId(object); |
45 } | 44 } |
46 | 45 |
47 | |
48 int32_t ObjectIdRing::FindExistingIdForObject(RawObject* raw_obj) { | 46 int32_t ObjectIdRing::FindExistingIdForObject(RawObject* raw_obj) { |
49 for (int32_t i = 0; i < capacity_; i++) { | 47 for (int32_t i = 0; i < capacity_; i++) { |
50 if (table_[i] == raw_obj) { | 48 if (table_[i] == raw_obj) { |
51 return IdOfIndex(i); | 49 return IdOfIndex(i); |
52 } | 50 } |
53 } | 51 } |
54 return kInvalidId; | 52 return kInvalidId; |
55 } | 53 } |
56 | 54 |
57 | |
58 RawObject* ObjectIdRing::GetObjectForId(int32_t id, LookupResult* kind) { | 55 RawObject* ObjectIdRing::GetObjectForId(int32_t id, LookupResult* kind) { |
59 int32_t index = IndexOfId(id); | 56 int32_t index = IndexOfId(id); |
60 if (index == kInvalidId) { | 57 if (index == kInvalidId) { |
61 *kind = kExpired; | 58 *kind = kExpired; |
62 return Object::null(); | 59 return Object::null(); |
63 } | 60 } |
64 ASSERT(index >= 0); | 61 ASSERT(index >= 0); |
65 ASSERT(index < capacity_); | 62 ASSERT(index < capacity_); |
66 if (table_[index] == Object::null()) { | 63 if (table_[index] == Object::null()) { |
67 *kind = kCollected; | 64 *kind = kCollected; |
68 return Object::null(); | 65 return Object::null(); |
69 } | 66 } |
70 *kind = kValid; | 67 *kind = kValid; |
71 ASSERT(IdOfIndex(index) == id); | 68 ASSERT(IdOfIndex(index) == id); |
72 return table_[index]; | 69 return table_[index]; |
73 } | 70 } |
74 | 71 |
75 | |
76 void ObjectIdRing::VisitPointers(ObjectPointerVisitor* visitor) { | 72 void ObjectIdRing::VisitPointers(ObjectPointerVisitor* visitor) { |
77 ASSERT(table_ != NULL); | 73 ASSERT(table_ != NULL); |
78 visitor->VisitPointers(table_, capacity_); | 74 visitor->VisitPointers(table_, capacity_); |
79 } | 75 } |
80 | 76 |
81 | |
82 void ObjectIdRing::PrintJSON(JSONStream* js) { | 77 void ObjectIdRing::PrintJSON(JSONStream* js) { |
83 Thread* thread = Thread::Current(); | 78 Thread* thread = Thread::Current(); |
84 Zone* zone = thread->zone(); | 79 Zone* zone = thread->zone(); |
85 ASSERT(zone != NULL); | 80 ASSERT(zone != NULL); |
86 JSONObject jsobj(js); | 81 JSONObject jsobj(js); |
87 jsobj.AddProperty("type", "_IdZone"); | 82 jsobj.AddProperty("type", "_IdZone"); |
88 jsobj.AddProperty("name", "default"); | 83 jsobj.AddProperty("name", "default"); |
89 { | 84 { |
90 JSONArray objects(&jsobj, "objects"); | 85 JSONArray objects(&jsobj, "objects"); |
91 Object& obj = Object::Handle(); | 86 Object& obj = Object::Handle(); |
92 for (int32_t i = 0; i < capacity_; i++) { | 87 for (int32_t i = 0; i < capacity_; i++) { |
93 obj = table_[i]; | 88 obj = table_[i]; |
94 if (obj.IsNull()) { | 89 if (obj.IsNull()) { |
95 // Collected object. | 90 // Collected object. |
96 continue; | 91 continue; |
97 } | 92 } |
98 objects.AddValue(obj, false); | 93 objects.AddValue(obj, false); |
99 } | 94 } |
100 } | 95 } |
101 } | 96 } |
102 | 97 |
103 | |
104 ObjectIdRing::ObjectIdRing(Isolate* isolate, int32_t capacity) { | 98 ObjectIdRing::ObjectIdRing(Isolate* isolate, int32_t capacity) { |
105 ASSERT(capacity > 0); | 99 ASSERT(capacity > 0); |
106 isolate_ = isolate; | 100 isolate_ = isolate; |
107 serial_num_ = 0; | 101 serial_num_ = 0; |
108 wrapped_ = false; | 102 wrapped_ = false; |
109 table_ = NULL; | 103 table_ = NULL; |
110 SetCapacityAndMaxSerial(capacity, kMaxId); | 104 SetCapacityAndMaxSerial(capacity, kMaxId); |
111 } | 105 } |
112 | 106 |
113 | |
114 void ObjectIdRing::SetCapacityAndMaxSerial(int32_t capacity, | 107 void ObjectIdRing::SetCapacityAndMaxSerial(int32_t capacity, |
115 int32_t max_serial) { | 108 int32_t max_serial) { |
116 ASSERT(max_serial <= kMaxId); | 109 ASSERT(max_serial <= kMaxId); |
117 capacity_ = capacity; | 110 capacity_ = capacity; |
118 if (table_ != NULL) { | 111 if (table_ != NULL) { |
119 free(table_); | 112 free(table_); |
120 } | 113 } |
121 table_ = reinterpret_cast<RawObject**>(calloc(capacity_, kWordSize)); | 114 table_ = reinterpret_cast<RawObject**>(calloc(capacity_, kWordSize)); |
122 for (int32_t i = 0; i < capacity_; i++) { | 115 for (int32_t i = 0; i < capacity_; i++) { |
123 table_[i] = Object::null(); | 116 table_[i] = Object::null(); |
124 } | 117 } |
125 // The maximum serial number is a multiple of the capacity, so that when | 118 // The maximum serial number is a multiple of the capacity, so that when |
126 // the serial number wraps, the index into table_ wraps with it. | 119 // the serial number wraps, the index into table_ wraps with it. |
127 max_serial_ = max_serial - (max_serial % capacity_); | 120 max_serial_ = max_serial - (max_serial % capacity_); |
128 } | 121 } |
129 | 122 |
130 | |
131 int32_t ObjectIdRing::NextSerial() { | 123 int32_t ObjectIdRing::NextSerial() { |
132 int32_t r = serial_num_; | 124 int32_t r = serial_num_; |
133 serial_num_++; | 125 serial_num_++; |
134 if (serial_num_ >= max_serial_) { | 126 if (serial_num_ >= max_serial_) { |
135 serial_num_ = 0; | 127 serial_num_ = 0; |
136 wrapped_ = true; | 128 wrapped_ = true; |
137 } | 129 } |
138 return r; | 130 return r; |
139 } | 131 } |
140 | 132 |
141 | |
142 int32_t ObjectIdRing::AllocateNewId(RawObject* raw_obj) { | 133 int32_t ObjectIdRing::AllocateNewId(RawObject* raw_obj) { |
143 ASSERT(raw_obj->IsHeapObject()); | 134 ASSERT(raw_obj->IsHeapObject()); |
144 int32_t id = NextSerial(); | 135 int32_t id = NextSerial(); |
145 ASSERT(id != kInvalidId); | 136 ASSERT(id != kInvalidId); |
146 int32_t index = IndexOfId(id); | 137 int32_t index = IndexOfId(id); |
147 ASSERT(index != kInvalidId); | 138 ASSERT(index != kInvalidId); |
148 table_[index] = raw_obj; | 139 table_[index] = raw_obj; |
149 return id; | 140 return id; |
150 } | 141 } |
151 | 142 |
152 | |
153 int32_t ObjectIdRing::IndexOfId(int32_t id) { | 143 int32_t ObjectIdRing::IndexOfId(int32_t id) { |
154 if (!IsValidId(id)) { | 144 if (!IsValidId(id)) { |
155 return kInvalidId; | 145 return kInvalidId; |
156 } | 146 } |
157 ASSERT((id >= 0) && (id < max_serial_)); | 147 ASSERT((id >= 0) && (id < max_serial_)); |
158 return id % capacity_; | 148 return id % capacity_; |
159 } | 149 } |
160 | 150 |
161 | |
162 int32_t ObjectIdRing::IdOfIndex(int32_t index) { | 151 int32_t ObjectIdRing::IdOfIndex(int32_t index) { |
163 if (index < 0) { | 152 if (index < 0) { |
164 return kInvalidId; | 153 return kInvalidId; |
165 } | 154 } |
166 if (index >= capacity_) { | 155 if (index >= capacity_) { |
167 return kInvalidId; | 156 return kInvalidId; |
168 } | 157 } |
169 int32_t id = kInvalidId; | 158 int32_t id = kInvalidId; |
170 if (wrapped_) { | 159 if (wrapped_) { |
171 // Serial numbers have wrapped around 0. | 160 // Serial numbers have wrapped around 0. |
(...skipping 21 matching lines...) Expand all Loading... |
193 // serial_num_ - split_point - capacity_. | 182 // serial_num_ - split_point - capacity_. |
194 int bottom = serial_num_ - capacity_ - split_point; | 183 int bottom = serial_num_ - capacity_ - split_point; |
195 ASSERT(bottom >= 0); | 184 ASSERT(bottom >= 0); |
196 id = bottom + index; | 185 id = bottom + index; |
197 } | 186 } |
198 } | 187 } |
199 ASSERT(!IsValidId(id) || (IndexOfId(id) == index)); | 188 ASSERT(!IsValidId(id) || (IndexOfId(id) == index)); |
200 return id; | 189 return id; |
201 } | 190 } |
202 | 191 |
203 | |
204 bool ObjectIdRing::IsValidContiguous(int32_t id) { | 192 bool ObjectIdRing::IsValidContiguous(int32_t id) { |
205 ASSERT(id != kInvalidId); | 193 ASSERT(id != kInvalidId); |
206 ASSERT((id >= 0) && (id < max_serial_)); | 194 ASSERT((id >= 0) && (id < max_serial_)); |
207 if (id >= serial_num_) { | 195 if (id >= serial_num_) { |
208 // Too large. | 196 // Too large. |
209 return false; | 197 return false; |
210 } | 198 } |
211 int32_t bottom = 0; | 199 int32_t bottom = 0; |
212 if (serial_num_ >= capacity_) { | 200 if (serial_num_ >= capacity_) { |
213 bottom = serial_num_ - capacity_; | 201 bottom = serial_num_ - capacity_; |
214 } | 202 } |
215 return id >= bottom; | 203 return id >= bottom; |
216 } | 204 } |
217 | 205 |
218 | |
219 bool ObjectIdRing::IsValidId(int32_t id) { | 206 bool ObjectIdRing::IsValidId(int32_t id) { |
220 if (id == kInvalidId) { | 207 if (id == kInvalidId) { |
221 return false; | 208 return false; |
222 } | 209 } |
223 if (id < 0) { | 210 if (id < 0) { |
224 return false; | 211 return false; |
225 } | 212 } |
226 if (id >= max_serial_) { | 213 if (id >= max_serial_) { |
227 return false; | 214 return false; |
228 } | 215 } |
(...skipping 22 matching lines...) Expand all Loading... |
251 return id >= bottom && bottom < max_serial_num; | 238 return id >= bottom && bottom < max_serial_num; |
252 } | 239 } |
253 } | 240 } |
254 ASSERT(wrapped_ == false); | 241 ASSERT(wrapped_ == false); |
255 return IsValidContiguous(id); | 242 return IsValidContiguous(id); |
256 } | 243 } |
257 | 244 |
258 #endif // !PRODUCT | 245 #endif // !PRODUCT |
259 | 246 |
260 } // namespace dart | 247 } // namespace dart |
OLD | NEW |