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.location() != kField) return Handle<Map>::null(); 206 DCHECK_EQ(kData, details.kind()); 207 return Handle<Map>(target); 208 } 209 210 211 // static 212 Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) { 213 DisallowHeapAllocation no_gc; 214 Object* raw_transition = map->raw_transitions(); 215 if (!IsSimpleTransition(raw_transition)) return Handle<String>::null(); 216 Map* target = GetSimpleTransition(raw_transition); 217 PropertyDetails details = GetSimpleTargetDetails(target); 218 if (details.location() != kField) return Handle<String>::null(); 219 DCHECK_EQ(kData, details.kind()); 220 if (details.attributes() != NONE) return Handle<String>::null(); 221 Name* name = GetSimpleTransitionKey(target); 222 if (!name->IsString()) return Handle<String>::null(); 223 return Handle<String>(String::cast(name)); 224 } 225 226 227 // static 228 bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) { 229 if (map->is_dictionary_map()) return false; 230 Object* raw_transitions = map->raw_transitions(); 231 if (IsFullTransitionArray(raw_transitions)) { 232 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 233 return transitions->number_of_transitions() < kMaxNumberOfTransitions; 234 } 235 return true; 236 } 237 238 239 // static 240 bool TransitionArray::CompactPrototypeTransitionArray(FixedArray* array) { 241 const int header = kProtoTransitionHeaderSize; 242 int number_of_transitions = NumberOfPrototypeTransitions(array); 243 if (number_of_transitions == 0) { 244 // Empty array cannot be compacted. 245 return false; 246 } 247 int new_number_of_transitions = 0; 248 for (int i = 0; i < number_of_transitions; i++) { 249 Object* cell = array->get(header + i); 250 if (!WeakCell::cast(cell)->cleared()) { 251 if (new_number_of_transitions != i) { 252 array->set(header + new_number_of_transitions, cell); 253 } 254 new_number_of_transitions++; 255 } 256 } 257 // Fill slots that became free with undefined value. 258 for (int i = new_number_of_transitions; i < number_of_transitions; i++) { 259 array->set_undefined(header + i); 260 } 261 if (number_of_transitions != new_number_of_transitions) { 262 SetNumberOfPrototypeTransitions(array, new_number_of_transitions); 263 } 264 return new_number_of_transitions < number_of_transitions; 265 } 266 267 268 // static 269 Handle<FixedArray> TransitionArray::GrowPrototypeTransitionArray( 270 Handle<FixedArray> array, int new_capacity, Isolate* isolate) { 271 // Grow array by factor 2 up to MaxCachedPrototypeTransitions. 272 int capacity = array->length() - kProtoTransitionHeaderSize; 273 new_capacity = Min(kMaxCachedPrototypeTransitions, new_capacity); 274 DCHECK_GT(new_capacity, capacity); 275 int grow_by = new_capacity - capacity; 276 array = isolate->factory()->CopyFixedArrayAndGrow(array, grow_by, TENURED); 277 if (capacity < 0) { 278 // There was no prototype transitions array before, so the size 279 // couldn't be copied. Initialize it explicitly. 280 SetNumberOfPrototypeTransitions(*array, 0); 281 } 282 return array; 283 } 284 285 286 // static 287 int TransitionArray::NumberOfPrototypeTransitionsForTest(Map* map) { 288 FixedArray* transitions = GetPrototypeTransitions(map); 289 CompactPrototypeTransitionArray(transitions); 290 return TransitionArray::NumberOfPrototypeTransitions(transitions); 291 } 292 293 294 // static 295 void TransitionArray::PutPrototypeTransition(Handle<Map> map, 296 Handle<Object> prototype, 297 Handle<Map> target_map) { 298 DCHECK(HeapObject::cast(*prototype)->map()->IsMap()); 299 // Don't cache prototype transition if this map is either shared, or a map of 300 // a prototype. 301 if (map->is_prototype_map()) return; 302 if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return; 303 304 const int header = kProtoTransitionHeaderSize; 305 306 Handle<WeakCell> target_cell = Map::WeakCellForMap(target_map); 307 308 Handle<FixedArray> cache(GetPrototypeTransitions(*map)); 309 int capacity = cache->length() - header; 310 int transitions = NumberOfPrototypeTransitions(*cache) + 1; 311 312 if (transitions > capacity) { 313 // Grow the array if compacting it doesn't free space. 314 if (!CompactPrototypeTransitionArray(*cache)) { 315 if (capacity == kMaxCachedPrototypeTransitions) return; 316 cache = GrowPrototypeTransitionArray(cache, 2 * transitions, 317 map->GetIsolate()); 318 SetPrototypeTransitions(map, cache); 319 } 320 } 321 322 // Reload number of transitions as they might have been compacted. 323 int last = NumberOfPrototypeTransitions(*cache); 324 int entry = header + last; 325 326 cache->set(entry, *target_cell); 327 SetNumberOfPrototypeTransitions(*cache, last + 1); 328 } 329 330 331 // static 332 Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map, 333 Handle<Object> prototype) { 334 DisallowHeapAllocation no_gc; 335 FixedArray* cache = GetPrototypeTransitions(*map); 336 int number_of_transitions = NumberOfPrototypeTransitions(cache); 337 for (int i = 0; i < number_of_transitions; i++) { 338 WeakCell* target_cell = 339 WeakCell::cast(cache->get(kProtoTransitionHeaderSize + i)); 340 if (!target_cell->cleared() && 341 Map::cast(target_cell->value())->prototype() == *prototype) { 342 return handle(Map::cast(target_cell->value())); 343 } 344 } 345 return Handle<Map>(); 346 } 347 348 349 // static 350 FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) { 351 Object* raw_transitions = map->raw_transitions(); 352 Heap* heap = map->GetHeap(); 353 if (!IsFullTransitionArray(raw_transitions)) { 354 return heap->empty_fixed_array(); 355 } 356 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 357 if (!transitions->HasPrototypeTransitions()) { 358 return heap->empty_fixed_array(); 359 } 360 return transitions->GetPrototypeTransitions(); 361 } 362 363 364 // static 365 void TransitionArray::SetNumberOfPrototypeTransitions( 366 FixedArray* proto_transitions, int value) { 367 DCHECK(proto_transitions->length() != 0); 368 proto_transitions->set(kProtoTransitionNumberOfEntriesOffset, 369 Smi::FromInt(value)); 370 } 371 372 373 // static 374 int TransitionArray::NumberOfTransitions(Object* raw_transitions) { 375 if (CanStoreSimpleTransition(raw_transitions)) return 0; 376 if (IsSimpleTransition(raw_transitions)) return 1; 377 // Prototype maps don't have transitions. 378 if (raw_transitions->IsPrototypeInfo()) return 0; 379 DCHECK(IsFullTransitionArray(raw_transitions)); 380 return TransitionArray::cast(raw_transitions)->number_of_transitions(); 381 } 382 383 384 // static 385 int TransitionArray::Capacity(Object* raw_transitions) { 386 if (!IsFullTransitionArray(raw_transitions)) return 1; 387 TransitionArray* t = TransitionArray::cast(raw_transitions); 388 if (t->length() <= kFirstIndex) return 0; 389 return (t->length() - kFirstIndex) / kTransitionSize; 390 } 391 392 393 // Private static helper functions. 394 395 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate, 396 int number_of_transitions, 397 int slack) { 398 Handle<FixedArray> array = isolate->factory()->NewTransitionArray( 399 LengthFor(number_of_transitions + slack)); 400 array->set(kPrototypeTransitionsIndex, Smi::kZero); 401 array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions)); 402 return Handle<TransitionArray>::cast(array); 403 } 404 405 406 // static 407 void TransitionArray::ZapTransitionArray(TransitionArray* transitions) { 408 // Do not zap the next link that is used by GC. 409 STATIC_ASSERT(kNextLinkIndex + 1 == kPrototypeTransitionsIndex); 410 MemsetPointer(transitions->data_start() + kPrototypeTransitionsIndex, 411 transitions->GetHeap()->the_hole_value(), 412 transitions->length() - kPrototypeTransitionsIndex); 413 transitions->SetNumberOfTransitions(0); 414 } 415 416 417 void TransitionArray::ReplaceTransitions(Handle<Map> map, 418 Object* new_transitions) { 419 Object* raw_transitions = map->raw_transitions(); 420 if (IsFullTransitionArray(raw_transitions)) { 421 TransitionArray* old_transitions = TransitionArray::cast(raw_transitions); 422 #ifdef DEBUG 423 CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions); 424 DCHECK(old_transitions != new_transitions); 425 #endif 426 // Transition arrays are not shared. When one is replaced, it should not 427 // keep referenced objects alive, so we zap it. 428 // When there is another reference to the array somewhere (e.g. a handle), 429 // not zapping turns from a waste of memory into a source of crashes. 430 ZapTransitionArray(old_transitions); 431 } 432 map->set_raw_transitions(new_transitions); 433 } 434 435 436 void TransitionArray::SetPrototypeTransitions( 437 Handle<Map> map, Handle<FixedArray> proto_transitions) { 438 EnsureHasFullTransitionArray(map); 439 TransitionArray* transitions = TransitionArray::cast(map->raw_transitions()); 440 transitions->SetPrototypeTransitions(*proto_transitions); 441 } 442 443 444 void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) { 445 Object* raw_transitions = map->raw_transitions(); 446 if (IsFullTransitionArray(raw_transitions)) return; 447 int nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 448 Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof); 449 DisallowHeapAllocation no_gc; 450 // Reload pointer after the allocation that just happened. 451 raw_transitions = map->raw_transitions(); 452 int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0; 453 if (new_nof != nof) { 454 DCHECK(new_nof == 0); 455 result->Shrink(ToKeyIndex(0)); 456 result->SetNumberOfTransitions(0); 457 } else if (nof == 1) { 458 Map* target = GetSimpleTransition(raw_transitions); 459 Name* key = GetSimpleTransitionKey(target); 460 result->Set(0, key, target); 461 } 462 ReplaceTransitions(map, *result); 463 } 464 465 466 void TransitionArray::TraverseTransitionTreeInternal(Map* map, 467 TraverseCallback callback, 468 void* data) { 469 Object* raw_transitions = map->raw_transitions(); 470 if (IsFullTransitionArray(raw_transitions)) { 471 TransitionArray* transitions = TransitionArray::cast(raw_transitions); 472 if (transitions->HasPrototypeTransitions()) { 473 FixedArray* proto_trans = transitions->GetPrototypeTransitions(); 474 for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) { 475 int index = TransitionArray::kProtoTransitionHeaderSize + i; 476 WeakCell* cell = WeakCell::cast(proto_trans->get(index)); 477 if (!cell->cleared()) { 478 TraverseTransitionTreeInternal(Map::cast(cell->value()), callback, 479 data); 480 } 481 } 482 } 483 for (int i = 0; i < transitions->number_of_transitions(); ++i) { 484 TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data); 485 } 486 } else if (IsSimpleTransition(raw_transitions)) { 487 TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions), 488 callback, data); 489 } 490 callback(map, data); 491 } 492 493 494 #ifdef DEBUG 495 void TransitionArray::CheckNewTransitionsAreConsistent( 496 Handle<Map> map, TransitionArray* old_transitions, Object* transitions) { 497 // This function only handles full transition arrays. 498 DCHECK(IsFullTransitionArray(transitions)); 499 TransitionArray* new_transitions = TransitionArray::cast(transitions); 500 for (int i = 0; i < old_transitions->number_of_transitions(); i++) { 501 Map* target = old_transitions->GetTarget(i); 502 if (target->instance_descriptors() == map->instance_descriptors()) { 503 Name* key = old_transitions->GetKey(i); 504 int new_target_index; 505 if (TransitionArray::IsSpecialTransition(key)) { 506 new_target_index = new_transitions->SearchSpecial(Symbol::cast(key)); 507 } else { 508 PropertyDetails details = 509 TransitionArray::GetTargetDetails(key, target); 510 new_target_index = 511 new_transitions->Search(details.kind(), key, details.attributes()); 512 } 513 DCHECK_NE(TransitionArray::kNotFound, new_target_index); 514 DCHECK_EQ(target, new_transitions->GetTarget(new_target_index)); 515 } 516 } 517 } 518 #endif 519 520 521 // Private non-static helper functions (operating on full transition arrays). 522 523 int TransitionArray::SearchDetails(int transition, PropertyKind kind, 524 PropertyAttributes attributes, 525 int* out_insertion_index) { 526 int nof_transitions = number_of_transitions(); 527 DCHECK(transition < nof_transitions); 528 Name* key = GetKey(transition); 529 for (; transition < nof_transitions && GetKey(transition) == key; 530 transition++) { 531 Map* target = GetTarget(transition); 532 PropertyDetails target_details = GetTargetDetails(key, target); 533 534 int cmp = CompareDetails(kind, attributes, target_details.kind(), 535 target_details.attributes()); 536 if (cmp == 0) { 537 return transition; 538 } else if (cmp < 0) { 539 break; 540 } 541 } 542 if (out_insertion_index != NULL) *out_insertion_index = transition; 543 return kNotFound; 544 } 545 546 547 int TransitionArray::Search(PropertyKind kind, Name* name, 548 PropertyAttributes attributes, 549 int* out_insertion_index) { 550 int transition = SearchName(name, out_insertion_index); 551 if (transition == kNotFound) return kNotFound; 552 return SearchDetails(transition, kind, attributes, out_insertion_index); 553 } 554 } // namespace internal 555 } // namespace v8 556