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
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/object_id_ring.h"
6
7#include "platform/assert.h"
8#include "vm/dart_api_state.h"
9#include "vm/json_stream.h"
10
11namespace dart {
12
13#ifndef PRODUCT
14
15ObjectIdRing::~ObjectIdRing() {
16 ASSERT(table_ != NULL);
17 free(table_);
18 table_ = NULL;
19}
20
21int32_t ObjectIdRing::GetIdForObject(ObjectPtr object, IdPolicy policy) {
22 // We do not allow inserting null because null is how we detect as entry was
23 // reclaimed by the GC.
24 ASSERT(object != Object::null());
25 if (policy == kAllocateId) {
26 return AllocateNewId(object);
27 }
28 ASSERT(policy == kReuseId);
29 int32_t id = FindExistingIdForObject(object);
30 if (id != kInvalidId) {
31 // Return a previous id for |object|.
32 return id;
33 }
34 return AllocateNewId(object);
35}
36
37int32_t ObjectIdRing::FindExistingIdForObject(ObjectPtr raw_obj) {
38 for (int32_t i = 0; i < capacity_; i++) {
39 if (table_[i] == raw_obj) {
40 return IdOfIndex(i);
41 }
42 }
43 return kInvalidId;
44}
45
46ObjectPtr ObjectIdRing::GetObjectForId(int32_t id, LookupResult* kind) {
47 int32_t index = IndexOfId(id);
48 if (index == kInvalidId) {
49 *kind = kExpired;
50 return Object::null();
51 }
52 ASSERT(index >= 0);
53 ASSERT(index < capacity_);
54 if (table_[index] == Object::null()) {
55 *kind = kCollected;
56 return Object::null();
57 }
58 *kind = kValid;
59 ASSERT(IdOfIndex(index) == id);
60 return table_[index];
61}
62
63void ObjectIdRing::VisitPointers(ObjectPointerVisitor* visitor) {
64 ASSERT(table_ != NULL);
65 visitor->VisitPointers(table_, capacity_);
66}
67
68void ObjectIdRing::PrintJSON(JSONStream* js) {
69 Thread* thread = Thread::Current();
70 Zone* zone = thread->zone();
71 ASSERT(zone != NULL);
72 JSONObject jsobj(js);
73 jsobj.AddProperty("type", "_IdZone");
74 jsobj.AddProperty("name", "default");
75 {
76 JSONArray objects(&jsobj, "objects");
77 Object& obj = Object::Handle();
78 for (int32_t i = 0; i < capacity_; i++) {
79 obj = table_[i];
80 if (obj.IsNull()) {
81 // Collected object.
82 continue;
83 }
84 objects.AddValue(obj, false);
85 }
86 }
87}
88
89ObjectIdRing::ObjectIdRing() {
90 serial_num_ = 0;
91 wrapped_ = false;
92 table_ = NULL;
93 SetCapacityAndMaxSerial(kDefaultCapacity, kMaxId);
94}
95
96void ObjectIdRing::SetCapacityAndMaxSerial(int32_t capacity,
97 int32_t max_serial) {
98 ASSERT(capacity > 0);
99 ASSERT(max_serial <= kMaxId);
100 capacity_ = capacity;
101 if (table_ != NULL) {
102 free(table_);
103 }
104 table_ = reinterpret_cast<ObjectPtr*>(calloc(capacity_, kWordSize));
105 for (int32_t i = 0; i < capacity_; i++) {
106 table_[i] = Object::null();
107 }
108 // The maximum serial number is a multiple of the capacity, so that when
109 // the serial number wraps, the index into table_ wraps with it.
110 max_serial_ = max_serial - (max_serial % capacity_);
111}
112
113int32_t ObjectIdRing::NextSerial() {
114 int32_t r = serial_num_;
115 serial_num_++;
116 if (serial_num_ >= max_serial_) {
117 serial_num_ = 0;
118 wrapped_ = true;
119 }
120 return r;
121}
122
123int32_t ObjectIdRing::AllocateNewId(ObjectPtr raw_obj) {
124 ASSERT(raw_obj->IsHeapObject());
125 int32_t id = NextSerial();
126 ASSERT(id != kInvalidId);
127 int32_t index = IndexOfId(id);
128 ASSERT(index != kInvalidId);
129 table_[index] = raw_obj;
130 return id;
131}
132
133int32_t ObjectIdRing::IndexOfId(int32_t id) {
134 if (!IsValidId(id)) {
135 return kInvalidId;
136 }
137 ASSERT((id >= 0) && (id < max_serial_));
138 return id % capacity_;
139}
140
141int32_t ObjectIdRing::IdOfIndex(int32_t index) {
142 if (index < 0) {
143 return kInvalidId;
144 }
145 if (index >= capacity_) {
146 return kInvalidId;
147 }
148 int32_t id = kInvalidId;
149 if (wrapped_) {
150 // Serial numbers have wrapped around 0.
151 ASSERT(serial_num_ < capacity_);
152 if (index < serial_num_) {
153 // index < serial_num_ have been handed out and are sequential starting
154 // at 0.
155 id = index;
156 } else {
157 // the other end of the array has the high ids.
158 const int32_t bottom = max_serial_ - capacity_;
159 id = bottom + index;
160 }
161 } else if (index < serial_num_) {
162 // Index into the array where id range splits.
163 int32_t split_point = serial_num_ % capacity_;
164 if (index < split_point) {
165 // index < split_point has serial_numbers starting at
166 // serial_num_ - split_point.
167 int bottom = serial_num_ - split_point;
168 ASSERT(bottom >= 0);
169 id = bottom + index;
170 } else {
171 // index >= split_point has serial_numbers starting at
172 // serial_num_ - split_point - capacity_.
173 int bottom = serial_num_ - capacity_ - split_point;
174 ASSERT(bottom >= 0);
175 id = bottom + index;
176 }
177 }
178 ASSERT(!IsValidId(id) || (IndexOfId(id) == index));
179 return id;
180}
181
182bool ObjectIdRing::IsValidContiguous(int32_t id) {
183 ASSERT(id != kInvalidId);
184 ASSERT((id >= 0) && (id < max_serial_));
185 if (id >= serial_num_) {
186 // Too large.
187 return false;
188 }
189 int32_t bottom = 0;
190 if (serial_num_ >= capacity_) {
191 bottom = serial_num_ - capacity_;
192 }
193 return id >= bottom;
194}
195
196bool ObjectIdRing::IsValidId(int32_t id) {
197 if (id == kInvalidId) {
198 return false;
199 }
200 if (id < 0) {
201 return false;
202 }
203 if (id >= max_serial_) {
204 return false;
205 }
206 ASSERT((id >= 0) && (id < max_serial_));
207 if (wrapped_) {
208 // Serial number has wrapped around to 0.
209 if (serial_num_ >= capacity_) {
210 // Serial number is larger than capacity, the serial
211 // numbers are contiguous again.
212 wrapped_ = false;
213 return IsValidContiguous(id);
214 } else {
215 // When the serial number first wraps, the valid serial number range
216 // spans two intervals:
217 // #1 [0, serial_num_)
218 // #2 [max_serial_ - (capacity_ - serial_num), max_serial_)
219 //
220 // Check for both.
221 if (id < serial_num_) {
222 // Interval #1
223 return true;
224 }
225 // Interval #2
226 const int32_t max_serial_num = max_serial_;
227 const int32_t bottom = max_serial_num - (capacity_ - serial_num_);
228 return id >= bottom && bottom < max_serial_num;
229 }
230 }
231 ASSERT(wrapped_ == false);
232 return IsValidContiguous(id);
233}
234
235#endif // !PRODUCT
236
237} // namespace dart
238