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