[elements] Enable left-trimming again

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/elements.h"
 
 #include "src/arguments.h"
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/messages.h"
@@ skipping 659 matching lines @@
     return ElementsAccessorSubclass::ShiftImpl(receiver, backing_store);
   }
 
   static Handle<Object> ShiftImpl(Handle<JSArray> receiver,
                                   Handle<FixedArrayBase> backing_store) {
     UNREACHABLE();
     return Handle<Object>();
   }
 
   void SetLength(Handle<JSArray> array, uint32_t length) final {
-    ElementsAccessorSubclass::SetLengthImpl(array, length,
+    ElementsAccessorSubclass::SetLengthImpl(array->GetIsolate(), array, length,
                                             handle(array->elements()));
   }
 
-  static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
+  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
+                            uint32_t length,
                             Handle<FixedArrayBase> backing_store) {
     DCHECK(!array->SetLengthWouldNormalize(length));
     DCHECK(IsFastElementsKind(array->GetElementsKind()));
     uint32_t old_length = 0;
     CHECK(array->length()->ToArrayIndex(&old_length));
 
     if (old_length < length) {
       ElementsKind kind = array->GetElementsKind();
       if (!IsFastHoleyElementsKind(kind)) {
         kind = GetHoleyElementsKind(kind);
         JSObject::TransitionElementsKind(array, kind);
       }
     }
 
     // Check whether the backing store should be shrunk.
     uint32_t capacity = backing_store->length();
+    old_length = Min(old_length, capacity);
     if (length == 0) {
       array->initialize_elements();
     } else if (length <= capacity) {
       if (array->HasFastSmiOrObjectElements()) {
         backing_store = JSObject::EnsureWritableFastElements(array);
       }
       if (2 * length <= capacity) {
         // If more than half the elements won't be used, trim the array.
-        array->GetHeap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(
+        isolate->heap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(
             *backing_store, capacity - length);
       } else {
         // Otherwise, fill the unused tail with holes.
         for (uint32_t i = length; i < old_length; i++) {
           BackingStore::cast(*backing_store)->set_the_hole(i);
         }
       }
     } else {
       // Check whether the backing store should be expanded.
       capacity = Max(length, JSObject::NewElementsCapacity(capacity));
@@ skipping 245 matching lines @@
 
 
 class DictionaryElementsAccessor
     : public ElementsAccessorBase<DictionaryElementsAccessor,
                                   ElementsKindTraits<DICTIONARY_ELEMENTS> > {
  public:
   explicit DictionaryElementsAccessor(const char* name)
       : ElementsAccessorBase<DictionaryElementsAccessor,
                              ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {}
 
-  static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
+  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
+                            uint32_t length,
                             Handle<FixedArrayBase> backing_store) {
     Handle<SeededNumberDictionary> dict =
         Handle<SeededNumberDictionary>::cast(backing_store);
-    Isolate* isolate = array->GetIsolate();
     int capacity = dict->Capacity();
     uint32_t old_length = 0;
     CHECK(array->length()->ToArrayLength(&old_length));
     if (length < old_length) {
       if (dict->requires_slow_elements()) {
         // Find last non-deletable element in range of elements to be
         // deleted and adjust range accordingly.
         for (int entry = 0; entry < capacity; entry++) {
           DisallowHeapAllocation no_gc;
           Object* index = dict->KeyAt(entry);
@@ skipping 355 matching lines @@
                                                       args, push_size, AT_END);
   }
 
   static uint32_t UnshiftImpl(Handle<JSArray> receiver,
                               Handle<FixedArrayBase> backing_store,
                               Arguments* args, uint32_t unshift_size) {
     return FastElementsAccessorSubclass::AddArguments(
         receiver, backing_store, args, unshift_size, AT_START);
   }
 
-  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
-                           int dst_index, int src_index, int len,
-                           int hole_start, int hole_end) {
+  static Handle<FixedArrayBase> MoveElements(
+      Isolate* isolate, Handle<JSArray> receiver,
+      Handle<FixedArrayBase> backing_store, int dst_index, int src_index,
+      int len, int hole_start, int hole_end) {
     UNREACHABLE();
+    return backing_store;
   }
 
   static Handle<JSArray> SliceImpl(Handle<JSObject> receiver,
                                    Handle<FixedArrayBase> backing_store,
                                    uint32_t start, uint32_t end) {
     DCHECK(start < end);
     Isolate* isolate = receiver->GetIsolate();
     int result_len = end - start;
     Handle<JSArray> result_array = isolate->factory()->NewJSArray(
         KindTraits::Kind, result_len, result_len);
@@ skipping 27 matching lines @@
         KindTraits::Kind, delete_count, delete_count);
     if (delete_count > 0) {
       DisallowHeapAllocation no_gc;
       FastElementsAccessorSubclass::CopyElementsImpl(
           *backing_store, start, deleted_elements->elements(), KindTraits::Kind,
           0, kPackedSizeNotKnown, delete_count);
     }
 
     // Delete and move elements to make space for add_count new elements.
     if (add_count < delete_count) {
-      FastElementsAccessorSubclass::SpliceShrinkStep(backing_store, heap, start,
-                                                     delete_count, add_count,
-                                                     length, new_length);
+      backing_store = FastElementsAccessorSubclass::SpliceShrinkStep(
+          isolate, receiver, backing_store, start, delete_count, add_count,
+          length, new_length);
     } else if (add_count > delete_count) {
       backing_store = FastElementsAccessorSubclass::SpliceGrowStep(
-          receiver, backing_store, isolate, heap, start, delete_count,
-          add_count, length, new_length);
+          isolate, receiver, backing_store, start, delete_count, add_count,
+          length, new_length);
     }
 
     // Copy over the arguments.
     FastElementsAccessorSubclass::CopyArguments(args, backing_store, add_count,
                                                 3, start);
 
     receiver->set_length(Smi::FromInt(new_length));
     FastElementsAccessorSubclass::TryTransitionResultArrayToPacked(
         deleted_elements);
     return deleted_elements;
   }
 
  private:
-  static void SpliceShrinkStep(Handle<FixedArrayBase> backing_store, Heap* heap,
-                               uint32_t start, uint32_t delete_count,
-                               uint32_t add_count, uint32_t len,
-                               uint32_t new_length) {
+  static Handle<FixedArrayBase> SpliceShrinkStep(
+      Isolate* isolate, Handle<JSArray> receiver,
+      Handle<FixedArrayBase> backing_store, uint32_t start,
+      uint32_t delete_count, uint32_t add_count, uint32_t len,
+      uint32_t new_length) {
     const int move_left_count = len - delete_count - start;
     const int move_left_dst_index = start + add_count;
-    FastElementsAccessorSubclass::MoveElements(
-        heap, backing_store, move_left_dst_index, start + delete_count,
-        move_left_count, new_length, len);
+    return FastElementsAccessorSubclass::MoveElements(
+        isolate, receiver, backing_store, move_left_dst_index,
+        start + delete_count, move_left_count, new_length, len);
   }
 
 
   static Handle<FixedArrayBase> SpliceGrowStep(
-      Handle<JSArray> receiver, Handle<FixedArrayBase> backing_store,
-      Isolate* isolate, Heap* heap, uint32_t start, uint32_t delete_count,
-      uint32_t add_count, uint32_t length, uint32_t new_length) {
+      Isolate* isolate, Handle<JSArray> receiver,
+      Handle<FixedArrayBase> backing_store, uint32_t start,
+      uint32_t delete_count, uint32_t add_count, uint32_t length,
+      uint32_t new_length) {
     // Check we do not overflow the new_length.
     DCHECK((add_count - delete_count) <= (Smi::kMaxValue - length));
     // Check if backing_store is big enough.
     if (new_length <= static_cast<uint32_t>(backing_store->length())) {
-      FastElementsAccessorSubclass::MoveElements(
-          heap, backing_store, start + add_count, start + delete_count,
-          (length - delete_count - start), 0, 0);
-      return backing_store;
+      return FastElementsAccessorSubclass::MoveElements(
+          isolate, receiver, backing_store, start + add_count,
+          start + delete_count, (length - delete_count - start), 0, 0);
     }
     // New backing storage is needed.
     int capacity = JSObject::NewElementsCapacity(new_length);
     // Partially copy all elements up to start.
     Handle<FixedArrayBase> new_elms =
         FastElementsAccessorSubclass::ConvertElementsWithCapacity(
             receiver, backing_store, KindTraits::Kind, capacity, start);
     // Copy the trailing elements after start + delete_count
     FastElementsAccessorSubclass::CopyElementsImpl(
         *backing_store, start + delete_count, *new_elms, KindTraits::Kind,
         start + add_count, kPackedSizeNotKnown,
         ElementsAccessor::kCopyToEndAndInitializeToHole);
     receiver->set_elements(*new_elms);
     return new_elms;
   }
 
   static Handle<Object> RemoveElement(Handle<JSArray> receiver,
                                       Handle<FixedArrayBase> backing_store,
                                       Where remove_position) {
+    Isolate* isolate = receiver->GetIsolate();
     uint32_t length =
         static_cast<uint32_t>(Smi::cast(receiver->length())->value());
-    Isolate* isolate = receiver->GetIsolate();
     DCHECK(length > 0);
     int new_length = length - 1;
     int remove_index = remove_position == AT_START ? 0 : new_length;
     Handle<Object> result =
         FastElementsAccessorSubclass::GetImpl(backing_store, remove_index);
     if (remove_position == AT_START) {
-      Heap* heap = isolate->heap();
-      FastElementsAccessorSubclass::MoveElements(heap, backing_store, 0, 1,
-                                                 new_length, 0, 0);
+      backing_store = FastElementsAccessorSubclass::MoveElements(
+          isolate, receiver, backing_store, 0, 1, new_length, 0, 0);
     }
-    FastElementsAccessorSubclass::SetLengthImpl(receiver, new_length,
+    FastElementsAccessorSubclass::SetLengthImpl(isolate, receiver, new_length,
                                                 backing_store);
 
     if (IsHoleyElementsKind(KindTraits::Kind) && result->IsTheHole()) {
       return receiver->GetIsolate()->factory()->undefined_value();
     }
     return result;
   }
 
   static uint32_t AddArguments(Handle<JSArray> receiver,
                                Handle<FixedArrayBase> backing_store,
@@ skipping 13 matching lines @@
       int copy_dst_index = remove_position == AT_START ? add_size : 0;
       // Copy over all objects to a new backing_store.
       backing_store = FastElementsAccessorSubclass::ConvertElementsWithCapacity(
           receiver, backing_store, KindTraits::Kind, capacity, 0,
           copy_dst_index, ElementsAccessor::kCopyToEndAndInitializeToHole);
       receiver->set_elements(*backing_store);
     } else if (remove_position == AT_START) {
       // If the backing store has enough capacity and we add elements to the
       // start we have to shift the existing objects.
       Isolate* isolate = receiver->GetIsolate();
-      FastElementsAccessorSubclass::MoveElements(isolate->heap(), backing_store,
-                                                 add_size, 0, length, 0, 0);
+      backing_store = FastElementsAccessorSubclass::MoveElements(
+          isolate, receiver, backing_store, add_size, 0, length, 0, 0);
     }
 
     int insertion_index = remove_position == AT_START ? 0 : length;
     // Copy the arguments to the start.
     FastElementsAccessorSubclass::CopyArguments(args, backing_store, add_size,
                                                 1, insertion_index);
     // Set the length.
     receiver->set_length(Smi::FromInt(new_length));
     return new_length;
   }
@@ skipping 32 matching lines @@
                              Object* value, WriteBarrierMode mode) {
     FixedArray::cast(backing_store)->set(entry, value, mode);
   }
 
   static Object* GetRaw(FixedArray* backing_store, uint32_t entry) {
     uint32_t index = FastElementsAccessorSubclass::GetIndexForEntryImpl(
         backing_store, entry);
     return backing_store->get(index);
   }
 
-  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
-                           int dst_index, int src_index, int len,
-                           int hole_start, int hole_end) {
+  static Handle<FixedArrayBase> MoveElements(
+      Isolate* isolate, Handle<JSArray> receiver,
+      Handle<FixedArrayBase> backing_store, int dst_index, int src_index,
+      int len, int hole_start, int hole_end) {
+    Heap* heap = isolate->heap();
     Handle<FixedArray> dst_elms = Handle<FixedArray>::cast(backing_store);
-    if (len != 0) {
+    if (heap->CanMoveObjectStart(*dst_elms) && dst_index == 0) {
+      dst_elms = Handle<FixedArray>(

[Igor Sheludko, 2015/12/22 10:02:36]

Since
1) the left trimming is not "safe" in a sense that we would crash anyway if we
ever create a handle to untrimmed object before entering elements accessors and
then try to use it after left trimming,
2) the approach to return an updated handle from MoveElements does not solve (1)
in general,
maybe it is better just to update the existing backing_store handle and keep the
signature of MoveElements unchanged.

+          FixedArray::cast(heap->LeftTrimFixedArray(*dst_elms, src_index)),
+          isolate);
+      receiver->set_elements(*dst_elms);
+      hole_end -= src_index;

[Igor Sheludko, 2015/12/22 10:02:36]

Shouldn't we update hole_start here as well?

[Camillo Bruni, 2015/12/22 14:21:01]

I added a DCHECK, the hole_start has to lie within length-removed elements (aka.
in the worst case right at the end of storage if we only trim).

+    } else if (len != 0) {
       DisallowHeapAllocation no_gc;
       heap->MoveElements(*dst_elms, dst_index, src_index, len);
     }
     if (hole_start != hole_end) {
       dst_elms->FillWithHoles(hole_start, hole_end);
     }
+    return dst_elms;
   }
 
   // NOTE: this method violates the handlified function signature convention:
   // raw pointer parameters in the function that allocates.
   // See ElementsAccessor::CopyElements() for details.
   // This method could actually allocate if copying from double elements to
   // object elements.
   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
                                FixedArrayBase* to, ElementsKind from_kind,
                                uint32_t to_start, int packed_size,
@@ skipping 92 matching lines @@
   static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
                              Object* value) {
     FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
   }
 
   static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
                              Object* value, WriteBarrierMode mode) {
     FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
   }
 
-  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
-                           int dst_index, int src_index, int len,
-                           int hole_start, int hole_end) {
+  static Handle<FixedArrayBase> MoveElements(
+      Isolate* isolate, Handle<JSArray> receiver,
+      Handle<FixedArrayBase> backing_store, int dst_index, int src_index,
+      int len, int hole_start, int hole_end) {
+    Heap* heap = isolate->heap();
     Handle<FixedDoubleArray> dst_elms =
         Handle<FixedDoubleArray>::cast(backing_store);
-    if (len != 0) {
+    if (heap->CanMoveObjectStart(*dst_elms) && dst_index == 0) {
+      dst_elms = Handle<FixedDoubleArray>(

[Igor Sheludko, 2015/12/22 10:02:36]

Ditto...

+          FixedDoubleArray::cast(
+              heap->LeftTrimFixedArray(*dst_elms, src_index)),
+          isolate);
+      receiver->set_elements(*dst_elms);
+      hole_end -= src_index;

[Igor Sheludko, 2015/12/22 10:02:36]

Ditto...

+    } else if (len != 0) {
       MemMove(dst_elms->data_start() + dst_index,
               dst_elms->data_start() + src_index, len * kDoubleSize);
     }
     if (hole_start != hole_end) {
       dst_elms->FillWithHoles(hole_start, hole_end);
     }
+    return dst_elms;
   }
 
   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
                                FixedArrayBase* to, ElementsKind from_kind,
                                uint32_t to_start, int packed_size,
                                int copy_size) {
     DisallowHeapAllocation no_allocation;
     switch (from_kind) {
       case FAST_SMI_ELEMENTS:
         CopyPackedSmiToDoubleElements(from, from_start, to, to_start,
@@ skipping 79 matching lines @@
                                 uint32_t entry) {
     uint32_t index = GetIndexForEntryImpl(*backing_store, entry);
     return BackingStore::get(Handle<BackingStore>::cast(backing_store), index);
   }
 
   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
                                         uint32_t entry) {
     return PropertyDetails(DONT_DELETE, DATA, 0, PropertyCellType::kNoCell);
   }
 
-  static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
+  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
+                            uint32_t length,
                             Handle<FixedArrayBase> backing_store) {
     // External arrays do not support changing their length.
     UNREACHABLE();
   }
 
   static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
     UNREACHABLE();
   }
 
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
@@ skipping 93 matching lines @@
         Context* context = Context::cast(parameter_map->get(0));
         int context_entry = alias->aliased_context_slot();
         DCHECK(!context->get(context_entry)->IsTheHole());
         context->set(context_entry, value);
       } else {
         ArgumentsAccessor::SetImpl(arguments, entry - length, value);
       }
     }
   }
 
-  static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
+  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
+                            uint32_t length,
                             Handle<FixedArrayBase> parameter_map) {
     // Sloppy arguments objects are not arrays.
     UNREACHABLE();
   }
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
     FixedArray* parameter_map = FixedArray::cast(backing_store);
     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
     return parameter_map->length() - 2 +
@@ skipping 456 matching lines @@
     }
   }
 
   DCHECK(j == result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8