deps/v8/src/transitions.cc

   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/v8.h"
   6
   7 #include "src/objects.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->NoIncrementalWriteBarrierSet(
  55           0, GetSimpleTransitionKey(old_target), old_target);
  56     } else {
  57       result->SetNumberOfTransitions(0);
  58     }
  59     ReplaceTransitions(map, *result);
  60   }
  61
  62   // At this point, we know that the map has a full TransitionArray.
  63   DCHECK(IsFullTransitionArray(map->raw_transitions()));
  64
  65   int number_of_transitions = 0;
  66   int new_nof = 0;
  67   int insertion_index = kNotFound;
  68   DCHECK_EQ(is_special_transition, IsSpecialTransition(*name));
  69   PropertyDetails details = is_special_transition
  70                                 ? PropertyDetails::Empty()
  71                                 : GetTargetDetails(*name, *target);
  72
  73   {
  74     DisallowHeapAllocation no_gc;
  75     TransitionArray* array = TransitionArray::cast(map->raw_transitions());
  76     number_of_transitions = array->number_of_transitions();
  77     new_nof = number_of_transitions;
  78
  79     int index =
  80         is_special_transition
  81             ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
  82             : array->Search(details.kind(), *name, details.attributes(),
  83                             &insertion_index);
  84     // If an existing entry was found, overwrite it and return.
  85     if (index != kNotFound) {
  86       array->SetTarget(index, *target);
  87       return;
  88     }
  89
  90     ++new_nof;
  91     CHECK(new_nof <= kMaxNumberOfTransitions);
  92     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
  93
  94     // If there is enough capacity, insert new entry into the existing array.
  95     if (new_nof <= Capacity(array)) {
  96       array->SetNumberOfTransitions(new_nof);
  97       for (index = number_of_transitions; index > insertion_index; --index) {
  98         array->SetKey(index, array->GetKey(index - 1));
  99         array->SetTarget(index, array->GetTarget(index - 1));
 100       }
 101       array->SetKey(index, *name);
 102       array->SetTarget(index, *target);
 103       SLOW_DCHECK(array->IsSortedNoDuplicates());
 104       return;
 105     }
 106   }
 107
 108   // We're gonna need a bigger TransitionArray.
 109   Handle<TransitionArray> result = Allocate(
 110       map->GetIsolate(), new_nof,
 111       Map::SlackForArraySize(number_of_transitions, kMaxNumberOfTransitions));
 112
 113   // The map's transition array may have shrunk during the allocation above as
 114   // it was weakly traversed, though it is guaranteed not to disappear. Trim the
 115   // result copy if needed, and recompute variables.
 116   DCHECK(IsFullTransitionArray(map->raw_transitions()));
 117   DisallowHeapAllocation no_gc;
 118   TransitionArray* array = TransitionArray::cast(map->raw_transitions());
 119   if (array->number_of_transitions() != number_of_transitions) {
 120     DCHECK(array->number_of_transitions() < number_of_transitions);
 121
 122     number_of_transitions = array->number_of_transitions();
 123     new_nof = number_of_transitions;
 124
 125     insertion_index = kNotFound;
 126     int index =
 127         is_special_transition
 128             ? array->SearchSpecial(Symbol::cast(*name), &insertion_index)
 129             : array->Search(details.kind(), *name, details.attributes(),
 130                             &insertion_index);
 131     if (index == kNotFound) {
 132       ++new_nof;
 133     } else {
 134       insertion_index = index;
 135     }
 136     DCHECK(insertion_index >= 0 && insertion_index <= number_of_transitions);
 137
 138     result->Shrink(ToKeyIndex(new_nof));
 139     result->SetNumberOfTransitions(new_nof);
 140   }
 141
 142   if (array->HasPrototypeTransitions()) {
 143     result->SetPrototypeTransitions(array->GetPrototypeTransitions());
 144   }
 145
 146   DCHECK_NE(kNotFound, insertion_index);
 147   for (int i = 0; i < insertion_index; ++i) {
 148     result->NoIncrementalWriteBarrierCopyFrom(array, i, i);
 149   }
 150   result->NoIncrementalWriteBarrierSet(insertion_index, *name, *target);
 151   for (int i = insertion_index; i < number_of_transitions; ++i) {
 152     result->NoIncrementalWriteBarrierCopyFrom(array, i, i + 1);
 153   }
 154
 155   SLOW_DCHECK(result->IsSortedNoDuplicates());
 156   ReplaceTransitions(map, *result);
 157 }
 158
 159
 160 // static
 161 Map* TransitionArray::SearchTransition(Map* map, PropertyKind kind, Name* name,
 162                                        PropertyAttributes attributes) {
 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->Equals(name)) return NULL;
 168     PropertyDetails details = GetSimpleTargetDetails(target);
 169     if (details.attributes() != attributes) return NULL;
 170     if (details.kind() != kind) return NULL;
 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 NULL;
 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   DisallowHeapAllocation no_gc;
 200   Map* target = SearchTransition(*map, kData, *name, NONE);
 201   if (target == NULL) return Handle<Map>::null();
 202   PropertyDetails details = target->GetLastDescriptorDetails();
 203   DCHECK_EQ(NONE, details.attributes());
 204   if (details.type() != DATA) return Handle<Map>::null();
 205   return Handle<Map>(target);
 206 }
 207
 208
 209 // static
 210 Handle<String> TransitionArray::ExpectedTransitionKey(Handle<Map> map) {
 211   DisallowHeapAllocation no_gc;
 212   Object* raw_transition = map->raw_transitions();
 213   if (!IsSimpleTransition(raw_transition)) return Handle<String>::null();
 214   Map* target = GetSimpleTransition(raw_transition);
 215   PropertyDetails details = GetSimpleTargetDetails(target);
 216   if (details.type() != DATA) return Handle<String>::null();
 217   if (details.attributes() != NONE) return Handle<String>::null();
 218   Name* name = GetSimpleTransitionKey(target);
 219   if (!name->IsString()) return Handle<String>::null();
 220   return Handle<String>(String::cast(name));
 221 }
 222
 223
 224 // static
 225 bool TransitionArray::CanHaveMoreTransitions(Handle<Map> map) {
 226   Object* raw_transitions = map->raw_transitions();
 227   if (IsFullTransitionArray(raw_transitions)) {
 228     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
 229     return transitions->number_of_transitions() < kMaxNumberOfTransitions;
 230   }
 231   return true;
 232 }
 233
 234
 235 // static
 236 Handle<Map> TransitionArray::PutPrototypeTransition(Handle<Map> map,
 237                                                     Handle<Object> prototype,
 238                                                     Handle<Map> target_map) {
 239   DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
 240   // Don't cache prototype transition if this map is either shared, or a map of
 241   // a prototype.
 242   if (map->is_prototype_map()) return map;
 243   if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return map;
 244
 245   const int header = kProtoTransitionHeaderSize;
 246
 247   Handle<FixedArray> cache(GetPrototypeTransitions(*map));
 248   int capacity = cache->length() - header;
 249   int transitions = NumberOfPrototypeTransitions(*cache) + 1;
 250
 251   if (transitions > capacity) {
 252     // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
 253     int new_capacity = Min(kMaxCachedPrototypeTransitions, transitions * 2);
 254     if (new_capacity == capacity) return map;
 255
 256     cache = FixedArray::CopySize(cache, header + new_capacity);
 257     if (capacity < 0) {
 258       // There was no prototype transitions array before, so the size
 259       // couldn't be copied. Initialize it explicitly.
 260       SetNumberOfPrototypeTransitions(*cache, 0);
 261     }
 262
 263     SetPrototypeTransitions(map, cache);
 264   }
 265
 266   // Reload number of transitions as GC might shrink them.
 267   int last = NumberOfPrototypeTransitions(*cache);
 268   int entry = header + last;
 269
 270   cache->set(entry, *target_map);
 271   SetNumberOfPrototypeTransitions(*cache, last + 1);
 272
 273   return map;
 274 }
 275
 276
 277 // static
 278 Handle<Map> TransitionArray::GetPrototypeTransition(Handle<Map> map,
 279                                                     Handle<Object> prototype) {
 280   DisallowHeapAllocation no_gc;
 281   FixedArray* cache = GetPrototypeTransitions(*map);
 282   int number_of_transitions = NumberOfPrototypeTransitions(cache);
 283   for (int i = 0; i < number_of_transitions; i++) {
 284     Map* target = Map::cast(cache->get(kProtoTransitionHeaderSize + i));
 285     if (target->prototype() == *prototype) return handle(target);
 286   }
 287   return Handle<Map>();
 288 }
 289
 290
 291 // static
 292 FixedArray* TransitionArray::GetPrototypeTransitions(Map* map) {
 293   Object* raw_transitions = map->raw_transitions();
 294   Heap* heap = map->GetHeap();
 295   if (!IsFullTransitionArray(raw_transitions)) {
 296     return heap->empty_fixed_array();
 297   }
 298   TransitionArray* transitions = TransitionArray::cast(raw_transitions);
 299   if (!transitions->HasPrototypeTransitions()) {
 300     return heap->empty_fixed_array();
 301   }
 302   return transitions->GetPrototypeTransitions();
 303 }
 304
 305
 306 // static
 307 void TransitionArray::SetNumberOfPrototypeTransitions(
 308     FixedArray* proto_transitions, int value) {
 309   DCHECK(proto_transitions->length() != 0);
 310   proto_transitions->set(kProtoTransitionNumberOfEntriesOffset,
 311                          Smi::FromInt(value));
 312 }
 313
 314
 315 // static
 316 int TransitionArray::NumberOfTransitions(Object* raw_transitions) {
 317   if (CanStoreSimpleTransition(raw_transitions)) return 0;
 318   if (IsSimpleTransition(raw_transitions)) return 1;
 319   DCHECK(IsFullTransitionArray(raw_transitions));
 320   return TransitionArray::cast(raw_transitions)->number_of_transitions();
 321 }
 322
 323
 324 // static
 325 int TransitionArray::Capacity(Object* raw_transitions) {
 326   if (!IsFullTransitionArray(raw_transitions)) return 1;
 327   TransitionArray* t = TransitionArray::cast(raw_transitions);
 328   if (t->length() <= kFirstIndex) return 0;
 329   return (t->length() - kFirstIndex) / kTransitionSize;
 330 }
 331
 332
 333 // Private static helper functions.
 334
 335 Handle<TransitionArray> TransitionArray::Allocate(Isolate* isolate,
 336                                                   int number_of_transitions,
 337                                                   int slack) {
 338   Handle<FixedArray> array = isolate->factory()->NewFixedArray(
 339       LengthFor(number_of_transitions + slack));
 340   array->set(kPrototypeTransitionsIndex, Smi::FromInt(0));
 341   array->set(kTransitionLengthIndex, Smi::FromInt(number_of_transitions));
 342   return Handle<TransitionArray>::cast(array);
 343 }
 344
 345
 346 void TransitionArray::NoIncrementalWriteBarrierCopyFrom(TransitionArray* origin,
 347                                                         int origin_transition,
 348                                                         int target_transition) {
 349   NoIncrementalWriteBarrierSet(target_transition,
 350                                origin->GetKey(origin_transition),
 351                                origin->GetTarget(origin_transition));
 352 }
 353
 354
 355 static void ZapTransitionArray(TransitionArray* transitions) {
 356   MemsetPointer(transitions->data_start(),
 357                 transitions->GetHeap()->the_hole_value(),
 358                 transitions->length());
 359 }
 360
 361
 362 void TransitionArray::ReplaceTransitions(Handle<Map> map,
 363                                          Object* new_transitions) {
 364   Object* raw_transitions = map->raw_transitions();
 365   if (IsFullTransitionArray(raw_transitions)) {
 366     TransitionArray* old_transitions = TransitionArray::cast(raw_transitions);
 367 #ifdef DEBUG
 368     CheckNewTransitionsAreConsistent(map, old_transitions, new_transitions);
 369     DCHECK(old_transitions != new_transitions);
 370 #endif
 371     // Transition arrays are not shared. When one is replaced, it should not
 372     // keep referenced objects alive, so we zap it.
 373     // When there is another reference to the array somewhere (e.g. a handle),
 374     // not zapping turns from a waste of memory into a source of crashes.
 375     ZapTransitionArray(old_transitions);
 376   }
 377   map->set_raw_transitions(new_transitions);
 378 }
 379
 380
 381 static void ZapPrototypeTransitions(Object* raw_transitions) {
 382   DCHECK(TransitionArray::IsFullTransitionArray(raw_transitions));
 383   TransitionArray* transitions = TransitionArray::cast(raw_transitions);
 384   if (!transitions->HasPrototypeTransitions()) return;
 385   FixedArray* proto_transitions = transitions->GetPrototypeTransitions();
 386   MemsetPointer(proto_transitions->data_start(),
 387                 proto_transitions->GetHeap()->the_hole_value(),
 388                 proto_transitions->length());
 389 }
 390
 391
 392 void TransitionArray::SetPrototypeTransitions(
 393     Handle<Map> map, Handle<FixedArray> proto_transitions) {
 394   EnsureHasFullTransitionArray(map);
 395   if (Heap::ShouldZapGarbage()) {
 396     Object* raw_transitions = map->raw_transitions();
 397     DCHECK(raw_transitions != *proto_transitions);
 398     ZapPrototypeTransitions(raw_transitions);
 399   }
 400   TransitionArray* transitions = TransitionArray::cast(map->raw_transitions());
 401   transitions->SetPrototypeTransitions(*proto_transitions);
 402 }
 403
 404
 405 void TransitionArray::EnsureHasFullTransitionArray(Handle<Map> map) {
 406   Object* raw_transitions = map->raw_transitions();
 407   if (IsFullTransitionArray(raw_transitions)) return;
 408   int nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
 409   Handle<TransitionArray> result = Allocate(map->GetIsolate(), nof);
 410   DisallowHeapAllocation no_gc;
 411   // Reload pointer after the allocation that just happened.
 412   raw_transitions = map->raw_transitions();
 413   int new_nof = IsSimpleTransition(raw_transitions) ? 1 : 0;
 414   if (new_nof != nof) {
 415     DCHECK(new_nof == 0);
 416     result->Shrink(ToKeyIndex(0));
 417     result->SetNumberOfTransitions(0);
 418   } else if (nof == 1) {
 419     Map* target = GetSimpleTransition(raw_transitions);
 420     Name* key = GetSimpleTransitionKey(target);
 421     result->NoIncrementalWriteBarrierSet(0, key, target);
 422   }
 423   ReplaceTransitions(map, *result);
 424 }
 425
 426
 427 void TransitionArray::TraverseTransitionTreeInternal(Map* map,
 428                                                      TraverseCallback callback,
 429                                                      void* data) {
 430   Object* raw_transitions = map->raw_transitions();
 431   if (IsFullTransitionArray(raw_transitions)) {
 432     TransitionArray* transitions = TransitionArray::cast(raw_transitions);
 433     if (transitions->HasPrototypeTransitions()) {
 434       FixedArray* proto_trans = transitions->GetPrototypeTransitions();
 435       for (int i = 0; i < NumberOfPrototypeTransitions(proto_trans); ++i) {
 436         int index = TransitionArray::kProtoTransitionHeaderSize + i;
 437         TraverseTransitionTreeInternal(Map::cast(proto_trans->get(index)),
 438                                        callback, data);
 439       }
 440     }
 441     for (int i = 0; i < transitions->number_of_transitions(); ++i) {
 442       TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
 443     }
 444   } else if (IsSimpleTransition(raw_transitions)) {
 445     TraverseTransitionTreeInternal(GetSimpleTransition(raw_transitions),
 446                                    callback, data);
 447   }
 448   callback(map, data);
 449 }
 450
 451
 452 #ifdef DEBUG
 453 void TransitionArray::CheckNewTransitionsAreConsistent(
 454     Handle<Map> map, TransitionArray* old_transitions, Object* transitions) {
 455   // This function only handles full transition arrays.
 456   DCHECK(IsFullTransitionArray(transitions));
 457   TransitionArray* new_transitions = TransitionArray::cast(transitions);
 458   for (int i = 0; i < old_transitions->number_of_transitions(); i++) {
 459     Map* target = old_transitions->GetTarget(i);
 460     if (target->instance_descriptors() == map->instance_descriptors()) {
 461       Name* key = old_transitions->GetKey(i);
 462       int new_target_index;
 463       if (TransitionArray::IsSpecialTransition(key)) {
 464         new_target_index = new_transitions->SearchSpecial(Symbol::cast(key));
 465       } else {
 466         PropertyDetails details =
 467             TransitionArray::GetTargetDetails(key, target);
 468         new_target_index =
 469             new_transitions->Search(details.kind(), key, details.attributes());
 470       }
 471       DCHECK_NE(TransitionArray::kNotFound, new_target_index);
 472       DCHECK_EQ(target, new_transitions->GetTarget(new_target_index));
 473     }
 474   }
 475 }
 476 #endif
 477
 478
 479 // Private non-static helper functions (operating on full transition arrays).
 480
 481 int TransitionArray::SearchDetails(int transition, PropertyKind kind,
 482                                    PropertyAttributes attributes,
 483                                    int* out_insertion_index) {
 484   int nof_transitions = number_of_transitions();
 485   DCHECK(transition < nof_transitions);
 486   Name* key = GetKey(transition);
 487   for (; transition < nof_transitions && GetKey(transition) == key;
 488        transition++) {
 489     Map* target = GetTarget(transition);
 490     PropertyDetails target_details = GetTargetDetails(key, target);
 491
 492     int cmp = CompareDetails(kind, attributes, target_details.kind(),
 493                              target_details.attributes());
 494     if (cmp == 0) {
 495       return transition;
 496     } else if (cmp < 0) {
 497       break;
 498     }
 499   }
 500   if (out_insertion_index != NULL) *out_insertion_index = transition;
 501   return kNotFound;
 502 }
 503
 504
 505 int TransitionArray::Search(PropertyKind kind, Name* name,
 506                             PropertyAttributes attributes,
 507                             int* out_insertion_index) {
 508   int transition = SearchName(name, out_insertion_index);
 509   if (transition == kNotFound) {
 510     return kNotFound;
 511   }
 512   return SearchDetails(transition, kind, attributes, out_insertion_index);
 513 }
 514 } }  // namespace v8::internal