1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/transitions.h" 6 7 #include "src/objects-inl.h" 8 #include "src/transitions-inl.h" 9 #include "src/utils.h" 10 11 namespace v8 { 12 namespace internal { 13 14 15 // static 16 void TransitionArray::Insert(Handle<Map> map, Handle<Name> name, 17 Handle<Map> target, SimpleTransitionFlag flag) { 18 Isolate* isolate = map->GetIsolate(); 19 target->SetBackPointer(*map); 20 21 // If the map doesn't have any transitions at all yet, install the new one. 22 if (CanStoreSimpleTransition(map->raw_transitions())) { 23 if (flag == SIMPLE_PROPERTY_TRANSITION) { 24 Handle<WeakCell> cell = Map::WeakCellForMap(target); 25 ReplaceTransitions(map, *cell); 26 return; 27 } 28 // If the flag requires a full TransitionArray, allocate one. 29 Handle<TransitionArray> result = Allocate(isolate, 0, 1); 30 ReplaceTransitions(map, *result); 31 } 32 33 bool is_special_transition = flag == SPECIAL_TRANSITION; 34 // If the map has a simple transition, check if it should be overwritten. 35 if (IsSimpleTransition(map->raw_transitions())) { 36 Map* old_target = GetSimpleTransition(map->raw_transitions()); 37 Name* key = GetSimpleTransitionKey(old_target); 38 PropertyDetails old_details = GetSimpleTargetDetails(old_target); 39 PropertyDetails new_details = is_special_transition 40 ? PropertyDetails::Empty() 41 : GetTargetDetails(*name, *target); 42 if (flag == SIMPLE_PROPERTY_TRANSITION && key->Equals(*name) && 43 old_details.kind() == new_details.kind() && 44 old_details.attributes() == new_details.attributes()) { 45 Handle<WeakCell> cell = Map::WeakCellForMap(target); 46 ReplaceTransitions(map, *cell); 47 return; 48 } 49 // Otherwise allocate a full TransitionArray with slack for a new entry. 50 Handle<TransitionArray> result = Allocate(isolate, 1, 1); 51 // Re-read existing data; the allocation might have caused it to be cleared. 52 if (IsSimpleTransition(map->raw_transitions())) { 53 old_target = GetSimpleTransition(map->raw_transitions()); 54 result->Set(0, GetSimpleTransitionKey(old_target), old_target); 55 } else { 56 result->SetNumberOfTransitions(0); 57 } 58 ReplaceTransitions(map, *result); 59 } 60 61 // At this point, we know that the map has a full TransitionArray. 62 DCHECK(IsFullTransitionArray(map->raw_transitions())); 63 64 int number_of_transitions = 0; 65 int new_nof = 0; 66 int insertion_index = kNotFound; 67 DCHECK_EQ(is_special_transition, IsSpecialTransition(*name)); 68 PropertyDetails details = is_special_transition 69 ? PropertyDetails::Empty() 70 : GetTargetDetails(*name, *target); 71 72 { 73 DisallowHeapAllocation no_gc; 74 TransitionArray* array = TransitionArray::cast(map->raw_transitions()); 75 number_of_transitions = array->number_of_transitions(); 76 new_nof = number_of_transitions; 77 78 int index = 79 is_special_transition 80 ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) 81 : array->Search(details.kind(), *name, details.attributes(), 82 &insertion_index); 83 // If an existing entry was found, overwrite it and return. 84 if (index != kNotFound) { 85 array->SetTarget(index, *target); 86 return; 87 } 88 89 ++new_nof; 90 CHECK(new_nof <= kMaxNumberOfTransitions); 91 DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); 92 93 // If there is enough capacity, insert new entry into the existing array. 94 if (new_nof <= Capacity(array)) { 95 array->SetNumberOfTransitions(new_nof); 96 for (index = number_of_transitions; index > insertion_index; --index) { 97 array->SetKey(index, array->GetKey(index - 1)); 98 array->SetTarget(index, array->GetTarget(index - 1)); 99 } 100 array->SetKey(index, *name); 101 array->SetTarget(index, *target); 102 SLOW_DCHECK(array->IsSortedNoDuplicates()); 103 return; 104 } 105 } 106 107 // We're gonna need a bigger TransitionArray. 108 Handle<TransitionArray> result = Allocate( 109 map->GetIsolate(), new_nof, 110 Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions)); 111 112 // The map's transition array may have shrunk during the allocation above as 113 // it was weakly traversed, though it is guaranteed not to disappear. Trim the 114 // result copy if needed, and recompute variables. 115 DCHECK(IsFullTransitionArray(map->raw_transitions())); 116 DisallowHeapAllocation no_gc; 117 TransitionArray* array = TransitionArray::cast(map->raw_transitions()); 118 if (array->number_of_transitions() != number_of_transitions) { 119 DCHECK(array->number_of_transitions() < number_of_transitions); 120 121 number_of_transitions = array->number_of_transitions(); 122 new_nof = number_of_transitions; 123 124 insertion_index = kNotFound; 125 int index = 126 is_special_transition 127 ? array->SearchSpecial(Symbol::cast(*name), &insertion_index) 128 : array->Search(details.kind(), *name, details.attributes(), 129 &insertion_index); 130 if (index == kNotFound) { 131 ++new_nof; 132 } else { 133 insertion_index = index; 134 } 135 DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions); 136 137 result->Shrink(ToKeyIndex(new_nof)); 138 result->SetNumberOfTransitions(new_nof); 139 } 140 141 if (array->HasPrototypeTransitions()) { 142 result->SetPrototypeTransitions(array->GetPrototypeTransitions()); 143 } 144 145 DCHECK_NE(kNotFound, insertion_index); 146 for (int i = 0; i < insertion_index; ++i) { 147 result->Set(i, array->GetKey(i), array->GetTarget(i)); 148 } 149 result->Set(insertion_index, *name, *target); 150 for (int i = insertion_index; i < number_of_transitions; ++i) { 151 result->Set(i + 1, array->GetKey(i), array->GetTarget(i)); 152 } 153 154 SLOW_DCHECK(result->IsSortedNoDuplicates()); 155 ReplaceTransitions(map, *result); 156 } 157 158 159 // static 160 Map* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name, 161 PropertyAttributes attributes) { 162 DCHECK(name->IsUniqueName()); 163 Object* raw_transitions = map->raw_transitions(); 164 if (IsSimpleTransition(raw_transitions)) { 165 Map* target = GetSimpleTransition(raw_transitions); 166 Name* key = GetSimpleTransitionKey(target); 167 if (key != name) return nullptr; 168 PropertyDetails details = GetSimpleTargetDetails(target); 169 if (details.attributes() != attributes) return nullptr; 170 if (details.kind() != kind) return nullptr; 171 return target; 172 } 173 if (IsFullTransitionArray(raw_transitions)) { 174 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 175 int transition = transitions->Search(kind, name, attributes); 176 if (transition == kNotFound) return nullptr; 177 return transitions->GetTarget(transition); 178 } 179 return NULL; 180 } 181 182 183 // static 184 Map* TransitionArray::SearchSpecial(Map* map, Symbol* name) { 185 Object* raw_transitions = map->raw_transitions(); 186 if (IsFullTransitionArray(raw_transitions)) { 187 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 188 int transition = transitions->SearchSpecial(name); 189 if (transition == kNotFound) return NULL; 190 return transitions->GetTarget(transition); 191 } 192 return NULL; 193 } 194 195 196 // static 197 Handle<Map> TransitionArray::FindTransitionToField(Handle<Map> map, 198 Handle<Name> name) { 199 DCHECK(name->IsUniqueName()); 200 DisallowHeapAllocation no_gc; 201 Map* target = SearchTransition(*map, kData, *name, NONE); 202 if (target == NULL) return Handle<Map>::null(); 203 PropertyDetails details = target->GetLastDescriptorDetails(); 204 DCHECK_EQ(NONE, details.attributes()); 205 if (details.type() != DATA) return Handle<Map>::null(); 206 return Handle<Map>(target); 207 } 208 209 210 // static 211 Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) { 212 DisallowHeapAllocation no_gc; 213 Object* raw_transition = map->raw_transitions(); 214 if (!IsSimpleTransition(raw_transition)) return Handle<String>::null(); 215 Map* target = GetSimpleTransition(raw_transition); 216 PropertyDetails details = GetSimpleTargetDetails(target); 217 if (details.type() != DATA) return Handle<String>::null(); 218 if (details.attributes() != NONE) return Handle<String>::null(); 219 Name* name = GetSimpleTransitionKey(target); 220 if (!name->IsString()) return Handle<String>::null(); 221 return Handle<String>(String::cast(name)); 222 } 223 224 225 // static 226 bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) { 227 if (map->is_dictionary_map()) return false; 228 Object* raw_transitions = map->raw_transitions(); 229 if (IsFullTransitionArray(raw_transitions)) { 230 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 231 return transitions->number_of_transitions() < kMaxNumberOfTransitions; 232 } 233 return true; 234 } 235 236 237 // static 238 bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) { 239 const int header = kProtoTransitionHeaderSize; 240 int number_of_transitions = NumberOfPrototypeTransitions(array); 241 if (number_of_transitions == 0) { 242 // Empty array cannot be compacted. 243 return false; 244 } 245 int new_number_of_transitions = 0; 246 for (int i = 0; i < number_of_transitions; i++) { 247 Object* cell = array->get(header + i); 248 if (!WeakCell::cast(cell)->cleared()) { 249 if (new_number_of_transitions != i) { 250 array->set(header + new_number_of_transitions, cell); 251 } 252 new_number_of_transitions++; 253 } 254 } 255 // Fill slots that became free with undefined value. 256 for (int i = new_number_of_transitions; i < number_of_transitions; i++) { 257 array->set_undefined(header + i); 258 } 259 if (number_of_transitions != new_number_of_transitions) { 260 SetNumberOfPrototypeTransitions(array, new_number_of_transitions); 261 } 262 return new_number_of_transitions < number_of_transitions; 263 } 264 265 266 // static 267 Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray( 268 Handle<FixedArray> array, int new_capacity, Isolate* isolate) { 269 // Grow array by factor 2 up to MaxCachedPrototypeTransitions. 270 int capacity = array->length() - kProtoTransitionHeaderSize; 271 new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity); 272 DCHECK_GT(new_capacity, capacity); 273 int grow_by = new_capacity - capacity; 274 array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED); 275 if (capacity < 0) { 276 // There was no prototype transitions array before, so the size 277 // couldn't be copied. Initialize it explicitly. 278 SetNumberOfPrototypeTransitions(*array, 0); 279 } 280 return array; 281 } 282 283 284 // static 285 int TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) { 286 FixedArray* transitions = GetPrototypeTransitions(map); 287 CompactPrototypeTransitionArray(transitions); 288 return TransitionArray::NumberOfPrototypeTransitions(transitions); 289 } 290 291 292 // static 293 void TransitionArray::PutPrototypeTransition(Handle<Map> map, 294 Handle<Object> prototype, 295 Handle<Map> target_map) { 296 DCHECK(HeapObject::cast(*prototype)->map()->IsMap()); 297 // Don't cache prototype transition if this map is either shared, or a map of 298 // a prototype. 299 if (map->is_prototype_map()) return; 300 if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return; 301 302 const int header = kProtoTransitionHeaderSize; 303 304 Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map); 305 306 Handle<FixedArray> cache(GetPrototypeTransitions(*map)); 307 int capacity = cache->length() - header; 308 int transitions = NumberOfPrototypeTransitions(*cache) + 1; 309 310 if (transitions > capacity) { 311 // Grow the array if compacting it doesn't free space. 312 if (!CompactPrototypeTransitionArray(*cache)) { 313 if (capacity == kMaxCachedPrototypeTransitions) return; 314 cache = GrowPrototypeTransitionArray(cache, 2 * transitions, 315 map->GetIsolate()); 316 SetPrototypeTransitions(map, cache); 317 } 318 } 319 320 // Reload number of transitions as they might have been compacted. 321 int last = NumberOfPrototypeTransitions(*cache); 322 int entry = header + last; 323 324 cache->set(entry, *target_cell); 325 SetNumberOfPrototypeTransitions(*cache, last + 1); 326 } 327 328 329 // static 330 Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map, 331 Handle<Object> prototype) { 332 DisallowHeapAllocation no_gc; 333 FixedArray* cache = GetPrototypeTransitions(*map); 334 int number_of_transitions = NumberOfPrototypeTransitions(cache); 335 for (int i = 0; i < number_of_transitions; i++) { 336 WeakCell* target_cell = 337 WeakCell::cast(cache->get(kProtoTransitionHeaderSize + i)); 338 if (!target_cell->cleared() && 339 Map::cast(target_cell->value())->prototype() == *prototype) { 340 return handle(Map::cast(target_cell->value())); 341 } 342 } 343 return Handle<Map>(); 344 } 345 346 347 // static 348 FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) { 349 Object* raw_transitions = map->raw_transitions(); 350 Heap* heap = map->GetHeap(); 351 if (!IsFullTransitionArray(raw_transitions)) { 352 return heap->empty_fixed_array(); 353 } 354 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 355 if (!transitions->HasPrototypeTransitions()) { 356 return heap->empty_fixed_array(); 357 } 358 return transitions->GetPrototypeTransitions(); 359 } 360 361 362 // static 363 void TransitionArray::SetNumberOfPrototypeTransitions( 364 FixedArray* proto_transitions, int value) { 365 DCHECK(proto_transitions->length() != 0); 366 proto_transitions->set(kProtoTransitionNumberOfEntriesOffset, 367 Smi::FromInt(value)); 368 } 369 370 371 // static 372 int TransitionArray::NumberOfTransitions(Object* raw_transitions) { 373 if (CanStoreSimpleTransition(raw_transitions)) return 0; 374 if (IsSimpleTransition(raw_transitions)) return 1; 375 // Prototype maps don't have transitions. 376 if (raw_transitions->IsPrototypeInfo()) return 0; 377 DCHECK(IsFullTransitionArray(raw_transitions)); 378 return TransitionArray::cast(raw_transitions)->number_of_transitions(); 379 } 380 381 382 // static 383 int TransitionArray::Capacity(Object* raw_transitions) { 384 if (!IsFullTransitionArray(raw_transitions)) return 1; 385 TransitionArray* t = TransitionArray::cast(raw_transitions); 386 if (t->length() <= kFirstIndex) return 0; 387 return (t->length() - kFirstIndex) / kTransitionSize; 388 } 389 390 391 // Private static helper functions. 392 393 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate, 394 int number_of_transitions, 395 int slack) { 396 Handle<FixedArray> array = isolate->factory()->NewTransitionArray( 397 LengthFor(number_of_transitions + slack)); 398 array->set(kPrototypeTransitionsIndex, Smi::FromInt(0)); 399 array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions)); 400 return Handle<TransitionArray>::cast(array); 401 } 402 403 404 // static 405 void TransitionArray::ZapTransitionArray(TransitionArray* transitions) { 406 // Do not zap the next link that is used by GC. 407 STATIC_ASSERT(kNextLinkIndex + 1 == kPrototypeTransitionsIndex); 408 MemsetPointer(transitions->data_start() + kPrototypeTransitionsIndex, 409 transitions->GetHeap()->the_hole_value(), 410 transitions->length() - kPrototypeTransitionsIndex); 411 transitions->SetNumberOfTransitions(0); 412 } 413 414 415 void TransitionArray::ReplaceTransitions(Handle<Map> map, 416 Object* new_transitions) { 417 Object* raw_transitions = map->raw_transitions(); 418 if (IsFullTransitionArray(raw_transitions)) { 419 TransitionArray* old_transitions = TransitionArray::cast(raw_transitions); 420 #ifdef DEBUG 421 CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions); 422 DCHECK(old_transitions != new_transitions); 423 #endif 424 // Transition arrays are not shared. When one is replaced, it should not 425 // keep referenced objects alive, so we zap it. 426 // When there is another reference to the array somewhere (e.g. a handle), 427 // not zapping turns from a waste of memory into a source of crashes. 428 ZapTransitionArray(old_transitions); 429 } 430 map->set_raw_transitions(new_transitions); 431 } 432 433 434 void TransitionArray::SetPrototypeTransitions( 435 Handle<Map> map, Handle<FixedArray> proto_transitions) { 436 EnsureHasFullTransitionArray(map); 437 TransitionArray* transitions = TransitionArray::cast(map->raw_transitions()); 438 transitions->SetPrototypeTransitions(*proto_transitions); 439 } 440 441 442 void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) { 443 Object* raw_transitions = map->raw_transitions(); 444 if (IsFullTransitionArray(raw_transitions)) return; 445 int nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 446 Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof); 447 DisallowHeapAllocation no_gc; 448 // Reload pointer after the allocation that just happened. 449 raw_transitions = map->raw_transitions(); 450 int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 451 if (new_nof != nof) { 452 DCHECK(new_nof == 0); 453 result->Shrink(ToKeyIndex(0)); 454 result->SetNumberOfTransitions(0); 455 } else if (nof == 1) { 456 Map* target = GetSimpleTransition(raw_transitions); 457 Name* key = GetSimpleTransitionKey(target); 458 result->Set(0, key, target); 459 } 460 ReplaceTransitions(map, *result); 461 } 462 463 464 void TransitionArray::TraverseTransitionTreeInternal(Map* map, 465 TraverseCallback callback, 466 void* data) { 467 Object* raw_transitions = map->raw_transitions(); 468 if (IsFullTransitionArray(raw_transitions)) { 469 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 470 if (transitions->HasPrototypeTransitions()) { 471 FixedArray* proto_trans = transitions->GetPrototypeTransitions(); 472 for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) { 473 int index = TransitionArray::kProtoTransitionHeaderSize + i; 474 WeakCell* cell = WeakCell::cast(proto_trans->get(index)); 475 if (!cell->cleared()) { 476 TraverseTransitionTreeInternal(Map::cast(cell->value()), callback, 477 data); 478 } 479 } 480 } 481 for (int i = 0; i < transitions->number_of_transitions(); ++i) { 482 TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data); 483 } 484 } else if (IsSimpleTransition(raw_transitions)) { 485 TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions), 486 callback, data); 487 } 488 callback(map, data); 489 } 490 491 492 #ifdef DEBUG 493 void TransitionArray::CheckNewTransitionsAreConsistent( 494 Handle<Map> map, TransitionArray* old_transitions, Object* transitions) { 495 // This function only handles full transition arrays. 496 DCHECK(IsFullTransitionArray(transitions)); 497 TransitionArray* new_transitions = TransitionArray::cast(transitions); 498 for (int i = 0; i < old_transitions->number_of_transitions(); i++) { 499 Map* target = old_transitions->GetTarget(i); 500 if (target->instance_descriptors() == map->instance_descriptors()) { 501 Name* key = old_transitions->GetKey(i); 502 int new_target_index; 503 if (TransitionArray::IsSpecialTransition(key)) { 504 new_target_index = new_transitions->SearchSpecial(Symbol::cast(key)); 505 } else { 506 PropertyDetails details = 507 TransitionArray::GetTargetDetails(key, target); 508 new_target_index = 509 new_transitions->Search(details.kind(), key, details.attributes()); 510 } 511 DCHECK_NE(TransitionArray::kNotFound, new_target_index); 512 DCHECK_EQ(target, new_transitions->GetTarget(new_target_index)); 513 } 514 } 515 } 516 #endif 517 518 519 // Private non-static helper functions (operating on full transition arrays). 520 521 int TransitionArray::SearchDetails(int transition, PropertyKind kind, 522 PropertyAttributes attributes, 523 int* out_insertion_index) { 524 int nof_transitions = number_of_transitions(); 525 DCHECK(transition < nof_transitions); 526 Name* key = GetKey(transition); 527 for (; transition < nof_transitions && GetKey(transition) == key; 528 transition++) { 529 Map* target = GetTarget(transition); 530 PropertyDetails target_details = GetTargetDetails(key, target); 531 532 int cmp = CompareDetails(kind, attributes, target_details.kind(), 533 target_details.attributes()); 534 if (cmp == 0) { 535 return transition; 536 } else if (cmp < 0) { 537 break; 538 } 539 } 540 if (out_insertion_index != NULL) *out_insertion_index = transition; 541 return kNotFound; 542 } 543 544 545 int TransitionArray::Search(PropertyKind kind, Name* name, 546 PropertyAttributes attributes, 547 int* out_insertion_index) { 548 int transition = SearchName(name, out_insertion_index); 549 if (transition == kNotFound) return kNotFound; 550 return SearchDetails(transition, kind, attributes, out_insertion_index); 551 } 552 } // namespace internal 553 } // namespace v8 554