Revert r4715.

src/heap.cc

 // Copyright 2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 308 matching lines @@
   unflattened_strings_length_ = 0;
 #ifdef DEBUG
   ASSERT(allocation_allowed_ && gc_state_ == NOT_IN_GC);
   allow_allocation(false);
 
   if (FLAG_verify_heap) {
     Verify();
   }
 
   if (FLAG_gc_verbose) Print();
+
+  if (FLAG_print_rset) {
+    // Not all spaces have remembered set bits that we care about.
+    old_pointer_space_->PrintRSet();
+    map_space_->PrintRSet();
+    lo_space_->PrintRSet();
+  }
 #endif
 
 #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
   ReportStatisticsBeforeGC();
 #endif
 }
 
 int Heap::SizeOfObjects() {
   int total = 0;
   AllSpaces spaces;
@@ skipping 166 matching lines @@
       gc_performed = true;
     }
     if (!(map_space->ReserveSpace(map_space_size))) {
       Heap::CollectGarbage(map_space_size, MAP_SPACE);
       gc_performed = true;
     }
     if (!(cell_space->ReserveSpace(cell_space_size))) {
       Heap::CollectGarbage(cell_space_size, CELL_SPACE);
       gc_performed = true;
     }
-    // We add a slack-factor of 2 in order to have space for a series of
-    // large-object allocations that are only just larger than the page size.
+    // We add a slack-factor of 2 in order to have space for the remembered
+    // set and a series of large-object allocations that are only just larger
+    // than the page size.
     large_object_size *= 2;
     // The ReserveSpace method on the large object space checks how much
     // we can expand the old generation.  This includes expansion caused by
     // allocation in the other spaces.
     large_object_size += cell_space_size + map_space_size + code_space_size +
         data_space_size + pointer_space_size;
     if (!(lo_space->ReserveSpace(large_object_size))) {
       Heap::CollectGarbage(large_object_size, LO_SPACE);
       gc_performed = true;
     }
@@ skipping 30 matching lines @@
 };
 
 
 void Heap::ClearJSFunctionResultCaches() {
   if (Bootstrapper::IsActive()) return;
   ClearThreadJSFunctionResultCachesVisitor visitor;
   ThreadManager::IterateThreads(&visitor);
 }
 
 
-#ifdef DEBUG
-
-enum PageWatermarkValidity {
-  ALL_VALID,
-  ALL_INVALID
-};
-
-static void VerifyPageWatermarkValidity(PagedSpace* space,
-                                        PageWatermarkValidity validity) {
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
-  bool expected_value = (validity == ALL_VALID);
-  while (it.has_next()) {
-    Page* page = it.next();
-    ASSERT(page->IsWatermarkValid() == expected_value);
-  }
-}
-#endif
-
-
 void Heap::PerformGarbageCollection(AllocationSpace space,
                                     GarbageCollector collector,
                                     GCTracer* tracer) {
   VerifySymbolTable();
   if (collector == MARK_COMPACTOR && global_gc_prologue_callback_) {
     ASSERT(!allocation_allowed_);
     GCTracer::Scope scope(tracer, GCTracer::Scope::EXTERNAL);
     global_gc_prologue_callback_();
   }
 
@@ skipping 224 matching lines @@
 }
 
 
 void Heap::Scavenge() {
 #ifdef DEBUG
   if (FLAG_enable_slow_asserts) VerifyNonPointerSpacePointers();
 #endif
 
   gc_state_ = SCAVENGE;
 
-  Page::FlipMeaningOfInvalidatedWatermarkFlag();
-#ifdef DEBUG
-  VerifyPageWatermarkValidity(old_pointer_space_, ALL_VALID);
-  VerifyPageWatermarkValidity(map_space_, ALL_VALID);
-#endif
-
-  // We do not update an allocation watermark of the top page during linear
-  // allocation to avoid overhead. So to maintain the watermark invariant
-  // we have to manually cache the watermark and mark the top page as having an
-  // invalid watermark. This guarantees that dirty regions iteration will use a
-  // correct watermark even if a linear allocation happens.
-  old_pointer_space_->FlushTopPageWatermark();
-  map_space_->FlushTopPageWatermark();
-
   // Implements Cheney's copying algorithm
   LOG(ResourceEvent("scavenge", "begin"));
 
   // Clear descriptor cache.
   DescriptorLookupCache::Clear();
 
   // Used for updating survived_since_last_expansion_ at function end.
   int survived_watermark = PromotedSpaceSize();
 
   CheckNewSpaceExpansionCriteria();
@@ skipping 22 matching lines @@
   // objects are at least one pointer in size.
   Address new_space_front = new_space_.ToSpaceLow();
   promotion_queue.Initialize(new_space_.ToSpaceHigh());
 
   ScavengeVisitor scavenge_visitor;
   // Copy roots.
   IterateRoots(&scavenge_visitor, VISIT_ALL_IN_SCAVENGE);
 
   // Copy objects reachable from the old generation.  By definition,
   // there are no intergenerational pointers in code or data spaces.
-  IterateDirtyRegions(old_pointer_space_,
-                      &IteratePointersInDirtyRegion,
-                      &ScavengePointer,
-                      WATERMARK_CAN_BE_INVALID);
-
-  IterateDirtyRegions(map_space_,
-                      &IteratePointersInDirtyMapsRegion,
-                      &ScavengePointer,
-                      WATERMARK_CAN_BE_INVALID);
-
-  lo_space_->IterateDirtyRegions(&ScavengePointer);
+  IterateRSet(old_pointer_space_, &ScavengePointer);
+  IterateRSet(map_space_, &ScavengePointer);
+  lo_space_->IterateRSet(&ScavengePointer);
 
   // Copy objects reachable from cells by scavenging cell values directly.
   HeapObjectIterator cell_iterator(cell_space_);
   for (HeapObject* cell = cell_iterator.next();
        cell != NULL; cell = cell_iterator.next()) {
     if (cell->IsJSGlobalPropertyCell()) {
       Address value_address =
           reinterpret_cast<Address>(cell) +
           (JSGlobalPropertyCell::kValueOffset - kHeapObjectTag);
       scavenge_visitor.VisitPointer(reinterpret_cast<Object**>(value_address));
@@ skipping 82 matching lines @@
     }
 
     // Promote and process all the to-be-promoted objects.
     while (!promotion_queue.is_empty()) {
       HeapObject* source;
       Map* map;
       promotion_queue.remove(&source, &map);
       // Copy the from-space object to its new location (given by the
       // forwarding address) and fix its map.
       HeapObject* target = source->map_word().ToForwardingAddress();
-      int size = source->SizeFromMap(map);
-      CopyBlock(target->address(), source->address(), size);
+      CopyBlock(reinterpret_cast<Object**>(target->address()),
+                reinterpret_cast<Object**>(source->address()),
+                source->SizeFromMap(map));
       target->set_map(map);
 
 #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
       // Update NewSpace stats if necessary.
       RecordCopiedObject(target);
 #endif
       // Visit the newly copied object for pointers to new space.
-      ASSERT(!target->IsMap());
-      IterateAndMarkPointersToNewSpace(target->address(),
-                                       target->address() + size,
-                                       &ScavengePointer);
+      target->Iterate(scavenge_visitor);
+      UpdateRSet(target);
     }
 
     // Take another spin if there are now unswept objects in new space
     // (there are currently no more unswept promoted objects).
   } while (new_space_front < new_space_.top());
 
   return new_space_front;
 }
 
 
+void Heap::ClearRSetRange(Address start, int size_in_bytes) {
+  uint32_t start_bit;
+  Address start_word_address =
+      Page::ComputeRSetBitPosition(start, 0, &start_bit);
+  uint32_t end_bit;
+  Address end_word_address =
+      Page::ComputeRSetBitPosition(start + size_in_bytes - kIntSize,
+                                   0,
+                                   &end_bit);
+
+  // We want to clear the bits in the starting word starting with the
+  // first bit, and in the ending word up to and including the last
+  // bit.  Build a pair of bitmasks to do that.
+  uint32_t start_bitmask = start_bit - 1;
+  uint32_t end_bitmask = ~((end_bit << 1) - 1);
+
+  // If the start address and end address are the same, we mask that
+  // word once, otherwise mask the starting and ending word
+  // separately and all the ones in between.
+  if (start_word_address == end_word_address) {
+    Memory::uint32_at(start_word_address) &= (start_bitmask | end_bitmask);
+  } else {
+    Memory::uint32_at(start_word_address) &= start_bitmask;
+    Memory::uint32_at(end_word_address) &= end_bitmask;
+    start_word_address += kIntSize;
+    memset(start_word_address, 0, end_word_address - start_word_address);
+  }
+}
+
+
+class UpdateRSetVisitor: public ObjectVisitor {
+ public:
+
+  void VisitPointer(Object** p) {
+    UpdateRSet(p);
+  }
+
+  void VisitPointers(Object** start, Object** end) {
+    // Update a store into slots [start, end), used (a) to update remembered
+    // set when promoting a young object to old space or (b) to rebuild
+    // remembered sets after a mark-compact collection.
+    for (Object** p = start; p < end; p++) UpdateRSet(p);
+  }
+ private:
+
+  void UpdateRSet(Object** p) {
+    // The remembered set should not be set.  It should be clear for objects
+    // newly copied to old space, and it is cleared before rebuilding in the
+    // mark-compact collector.
+    ASSERT(!Page::IsRSetSet(reinterpret_cast<Address>(p), 0));
+    if (Heap::InNewSpace(*p)) {
+      Page::SetRSet(reinterpret_cast<Address>(p), 0);
+    }
+  }
+};
+
+
+int Heap::UpdateRSet(HeapObject* obj) {
+  ASSERT(!InNewSpace(obj));
+  // Special handling of fixed arrays to iterate the body based on the start
+  // address and offset.  Just iterating the pointers as in UpdateRSetVisitor
+  // will not work because Page::SetRSet needs to have the start of the
+  // object for large object pages.
+  if (obj->IsFixedArray()) {
+    FixedArray* array = FixedArray::cast(obj);
+    int length = array->length();
+    for (int i = 0; i < length; i++) {
+      int offset = FixedArray::kHeaderSize + i * kPointerSize;
+      ASSERT(!Page::IsRSetSet(obj->address(), offset));
+      if (Heap::InNewSpace(array->get(i))) {
+        Page::SetRSet(obj->address(), offset);
+      }
+    }
+  } else if (!obj->IsCode()) {
+    // Skip code object, we know it does not contain inter-generational
+    // pointers.
+    UpdateRSetVisitor v;
+    obj->Iterate(&v);
+  }
+  return obj->Size();
+}
+
+
+void Heap::RebuildRSets() {
+  // By definition, we do not care about remembered set bits in code,
+  // data, or cell spaces.
+  map_space_->ClearRSet();
+  RebuildRSets(map_space_);
+
+  old_pointer_space_->ClearRSet();
+  RebuildRSets(old_pointer_space_);
+
+  Heap::lo_space_->ClearRSet();
+  RebuildRSets(lo_space_);
+}
+
+
+void Heap::RebuildRSets(PagedSpace* space) {
+  HeapObjectIterator it(space);
+  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next())
+    Heap::UpdateRSet(obj);
+}
+
+
+void Heap::RebuildRSets(LargeObjectSpace* space) {
+  LargeObjectIterator it(space);
+  for (HeapObject* obj = it.next(); obj != NULL; obj = it.next())
+    Heap::UpdateRSet(obj);
+}
+
+
 #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
 void Heap::RecordCopiedObject(HeapObject* obj) {
   bool should_record = false;
 #ifdef DEBUG
   should_record = FLAG_heap_stats;
 #endif
 #ifdef ENABLE_LOGGING_AND_PROFILING
   should_record = should_record || FLAG_log_gc;
 #endif
   if (should_record) {
     if (new_space_.Contains(obj)) {
       new_space_.RecordAllocation(obj);
     } else {
       new_space_.RecordPromotion(obj);
     }
   }
 }
 #endif  // defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
 
 
 
 HeapObject* Heap::MigrateObject(HeapObject* source,
                                 HeapObject* target,
                                 int size) {
   // Copy the content of source to target.
-  CopyBlock(target->address(), source->address(), size);
+  CopyBlock(reinterpret_cast<Object**>(target->address()),
+            reinterpret_cast<Object**>(source->address()),
+            size);
 
   // Set the forwarding address.
   source->set_map_word(MapWord::FromForwardingAddress(target));
 
 #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
   // Update NewSpace stats if necessary.
   RecordCopiedObject(target);
 #endif
 
   return target;
@@ skipping 34 matching lines @@
   // so we can store the from-space address and map pointer of promoted
   // objects in the to space.
   ASSERT(object_size >= 2 * kPointerSize);
 
   // If the object should be promoted, we try to copy it to old space.
   if (ShouldBePromoted(object->address(), object_size)) {
     Object* result;
     if (object_size > MaxObjectSizeInPagedSpace()) {
       result = lo_space_->AllocateRawFixedArray(object_size);
       if (!result->IsFailure()) {
+        // Save the from-space object pointer and its map pointer at the
+        // top of the to space to be swept and copied later.  Write the
+        // forwarding address over the map word of the from-space
+        // object.
         HeapObject* target = HeapObject::cast(result);
+        promotion_queue.insert(object, first_word.ToMap());
+        object->set_map_word(MapWord::FromForwardingAddress(target));
 
-        if (object->IsFixedArray()) {
-          // Save the from-space object pointer and its map pointer at the
-          // top of the to space to be swept and copied later.  Write the
-          // forwarding address over the map word of the from-space
-          // object.
-          promotion_queue.insert(object, first_word.ToMap());
-          object->set_map_word(MapWord::FromForwardingAddress(target));
+        // Give the space allocated for the result a proper map by
+        // treating it as a free list node (not linked into the free
+        // list).
+        FreeListNode* node = FreeListNode::FromAddress(target->address());
+        node->set_size(object_size);
 
-          // Give the space allocated for the result a proper map by
-          // treating it as a free list node (not linked into the free
-          // list).
-          FreeListNode* node = FreeListNode::FromAddress(target->address());
-          node->set_size(object_size);
-
-          *p = target;
-        } else {
-          // In large object space only fixed arrays might possibly contain
-          // intergenerational references.
-          // All other objects can be copied immediately and not revisited.
-          *p = MigrateObject(object, target, object_size);
-        }
-
+        *p = target;
         tracer()->increment_promoted_objects_size(object_size);
         return;
       }
     } else {
       OldSpace* target_space = Heap::TargetSpace(object);
       ASSERT(target_space == Heap::old_pointer_space_ ||
              target_space == Heap::old_data_space_);
       result = target_space->AllocateRaw(object_size);
       if (!result->IsFailure()) {
         HeapObject* target = HeapObject::cast(result);
@@ skipping 469 matching lines @@
     if (obj->IsFailure()) return false;
     roots_[constant_symbol_table[i].index] = String::cast(obj);
   }
 
   // Allocate the hidden symbol which is used to identify the hidden properties
   // in JSObjects. The hash code has a special value so that it will not match
   // the empty string when searching for the property. It cannot be part of the
   // loop above because it needs to be allocated manually with the special
   // hash code in place. The hash code for the hidden_symbol is zero to ensure
   // that it will always be at the first entry in property descriptors.
-  obj = AllocateSymbol(CStrVector(""), 0, String::kZeroHash);
+  obj = AllocateSymbol(CStrVector(""), 0, String::kHashComputedMask);
   if (obj->IsFailure()) return false;
   hidden_symbol_ = String::cast(obj);
 
   // Allocate the proxy for __proto__.
   obj = AllocateProxy((Address) &Accessors::ObjectPrototype);
   if (obj->IsFailure()) return false;
   set_prototype_accessors(Proxy::cast(obj));
 
   // Allocate the code_stubs dictionary. The initial size is set to avoid
   // expanding the dictionary during bootstrapping.
@@ skipping 215 matching lines @@
   share->set_formal_parameter_count(0);
   share->set_instance_class_name(Object_symbol());
   share->set_function_data(undefined_value());
   share->set_script(undefined_value());
   share->set_start_position_and_type(0);
   share->set_debug_info(undefined_value());
   share->set_inferred_name(empty_string());
   share->set_compiler_hints(0);
   share->set_this_property_assignments_count(0);
   share->set_this_property_assignments(undefined_value());
-  share->set_num_literals(0);
-  share->set_end_position(0);
-  share->set_function_token_position(0);
   return result;
 }
 
 
 // Returns true for a character in a range.  Both limits are inclusive.
 static inline bool Between(uint32_t character, uint32_t from, uint32_t to) {
   // This makes uses of the the unsigned wraparound.
   return character - from <= to - from;
 }
 
@@ skipping 241 matching lines @@
   }
   if (pretenure == NOT_TENURED) {
     return AllocateByteArray(length);
   }
   int size = ByteArray::SizeFor(length);
   Object* result = (size <= MaxObjectSizeInPagedSpace())
       ? old_data_space_->AllocateRaw(size)
       : lo_space_->AllocateRaw(size);
   if (result->IsFailure()) return result;
 
-  reinterpret_cast<ByteArray*>(result)->set_map(byte_array_map());
-  reinterpret_cast<ByteArray*>(result)->set_length(length);
+  reinterpret_cast<Array*>(result)->set_map(byte_array_map());
+  reinterpret_cast<Array*>(result)->set_length(length);
   return result;
 }
 
 
 Object* Heap::AllocateByteArray(int length) {
   if (length < 0 || length > ByteArray::kMaxLength) {
     return Failure::OutOfMemoryException();
   }
   int size = ByteArray::SizeFor(length);
   AllocationSpace space =
       (size > MaxObjectSizeInPagedSpace()) ? LO_SPACE : NEW_SPACE;
   Object* result = AllocateRaw(size, space, OLD_DATA_SPACE);
   if (result->IsFailure()) return result;
 
-  reinterpret_cast<ByteArray*>(result)->set_map(byte_array_map());
-  reinterpret_cast<ByteArray*>(result)->set_length(length);
+  reinterpret_cast<Array*>(result)->set_map(byte_array_map());
+  reinterpret_cast<Array*>(result)->set_length(length);
   return result;
 }
 
 
 void Heap::CreateFillerObjectAt(Address addr, int size) {
   if (size == 0) return;
   HeapObject* filler = HeapObject::FromAddress(addr);
   if (size == kPointerSize) {
     filler->set_map(one_pointer_filler_map());
   } else if (size == 2 * kPointerSize) {
@@ skipping 95 matching lines @@
     result = lo_space_->AllocateRawCode(obj_size);
   } else {
     result = code_space_->AllocateRaw(obj_size);
   }
 
   if (result->IsFailure()) return result;
 
   // Copy code object.
   Address old_addr = code->address();
   Address new_addr = reinterpret_cast<HeapObject*>(result)->address();
-  CopyBlock(new_addr, old_addr, obj_size);
+  CopyBlock(reinterpret_cast<Object**>(new_addr),
+            reinterpret_cast<Object**>(old_addr),
+            obj_size);
   // Relocate the copy.
   Code* new_code = Code::cast(result);
   ASSERT(!CodeRange::exists() || CodeRange::contains(code->address()));
   new_code->Relocate(new_addr - old_addr);
   return new_code;
 }
 
 
 Object* Heap::CopyCode(Code* code, Vector<byte> reloc_info) {
   int new_body_size = RoundUp(code->instruction_size() + reloc_info.length(),
@@ skipping 125 matching lines @@
   ASSERT(kArgumentsObjectSize == boilerplate->map()->instance_size());
 
   // Do the allocation.
   Object* result =
       AllocateRaw(kArgumentsObjectSize, NEW_SPACE, OLD_POINTER_SPACE);
   if (result->IsFailure()) return result;
 
   // Copy the content. The arguments boilerplate doesn't have any
   // fields that point to new space so it's safe to skip the write
   // barrier here.
-  CopyBlock(HeapObject::cast(result)->address(),
-            boilerplate->address(),
+  CopyBlock(reinterpret_cast<Object**>(HeapObject::cast(result)->address()),
+            reinterpret_cast<Object**>(boilerplate->address()),
             kArgumentsObjectSize);
 
   // Set the two properties.
   JSObject::cast(result)->InObjectPropertyAtPut(arguments_callee_index,
                                                 callee);
   JSObject::cast(result)->InObjectPropertyAtPut(arguments_length_index,
                                                 Smi::FromInt(length),
                                                 SKIP_WRITE_BARRIER);
 
   // Check the state of the object
@@ skipping 201 matching lines @@
   Map* map = source->map();
   int object_size = map->instance_size();
   Object* clone;
 
   // If we're forced to always allocate, we use the general allocation
   // functions which may leave us with an object in old space.
   if (always_allocate()) {
     clone = AllocateRaw(object_size, NEW_SPACE, OLD_POINTER_SPACE);
     if (clone->IsFailure()) return clone;
     Address clone_address = HeapObject::cast(clone)->address();
-    CopyBlock(clone_address,
-              source->address(),
+    CopyBlock(reinterpret_cast<Object**>(clone_address),
+              reinterpret_cast<Object**>(source->address()),
               object_size);
     // Update write barrier for all fields that lie beyond the header.
     RecordWrites(clone_address,
                  JSObject::kHeaderSize,
                  (object_size - JSObject::kHeaderSize) / kPointerSize);
   } else {
     clone = new_space_.AllocateRaw(object_size);
     if (clone->IsFailure()) return clone;
     ASSERT(Heap::InNewSpace(clone));
     // Since we know the clone is allocated in new space, we can copy
     // the contents without worrying about updating the write barrier.
-    CopyBlock(HeapObject::cast(clone)->address(),
-              source->address(),
+    CopyBlock(reinterpret_cast<Object**>(HeapObject::cast(clone)->address()),
+              reinterpret_cast<Object**>(source->address()),
               object_size);
   }
 
   FixedArray* elements = FixedArray::cast(source->elements());
   FixedArray* properties = FixedArray::cast(source->properties());
   // Update elements if necessary.
   if (elements->length() > 0) {
     Object* elem = CopyFixedArray(elements);
     if (elem->IsFailure()) return elem;
     JSObject::cast(clone)->set_elements(FixedArray::cast(elem));
@@ skipping 250 matching lines @@
   ASSERT_EQ(size, HeapObject::cast(result)->Size());
   return result;
 }
 
 
 Object* Heap::AllocateEmptyFixedArray() {
   int size = FixedArray::SizeFor(0);
   Object* result = AllocateRaw(size, OLD_DATA_SPACE, OLD_DATA_SPACE);
   if (result->IsFailure()) return result;
   // Initialize the object.
-  reinterpret_cast<FixedArray*>(result)->set_map(fixed_array_map());
-  reinterpret_cast<FixedArray*>(result)->set_length(0);
+  reinterpret_cast<Array*>(result)->set_map(fixed_array_map());
+  reinterpret_cast<Array*>(result)->set_length(0);
   return result;
 }
 
 
 Object* Heap::AllocateRawFixedArray(int length) {
   if (length < 0 || length > FixedArray::kMaxLength) {
     return Failure::OutOfMemoryException();
   }
   // Use the general function if we're forced to always allocate.
   if (always_allocate()) return AllocateFixedArray(length, TENURED);
   // Allocate the raw data for a fixed array.
   int size = FixedArray::SizeFor(length);
   return size <= kMaxObjectSizeInNewSpace
       ? new_space_.AllocateRaw(size)
       : lo_space_->AllocateRawFixedArray(size);
 }
 
 
 Object* Heap::CopyFixedArray(FixedArray* src) {
   int len = src->length();
   Object* obj = AllocateRawFixedArray(len);
   if (obj->IsFailure()) return obj;
   if (Heap::InNewSpace(obj)) {
     HeapObject* dst = HeapObject::cast(obj);
-    CopyBlock(dst->address(), src->address(), FixedArray::SizeFor(len));
+    CopyBlock(reinterpret_cast<Object**>(dst->address()),
+              reinterpret_cast<Object**>(src->address()),
+              FixedArray::SizeFor(len));
     return obj;
   }
   HeapObject::cast(obj)->set_map(src->map());
   FixedArray* result = FixedArray::cast(obj);
   result->set_length(len);
 
   // Copy the content
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
   for (int i = 0; i < len; i++) result->set(i, src->get(i), mode);
   return result;
 }
 
 
 Object* Heap::AllocateFixedArray(int length) {
   ASSERT(length >= 0);
   if (length == 0) return empty_fixed_array();
   Object* result = AllocateRawFixedArray(length);
   if (!result->IsFailure()) {
     // Initialize header.
-    FixedArray* array = reinterpret_cast<FixedArray*>(result);
-    array->set_map(fixed_array_map());
+    reinterpret_cast<Array*>(result)->set_map(fixed_array_map());
+    FixedArray* array = FixedArray::cast(result);
     array->set_length(length);
     // Initialize body.
     ASSERT(!Heap::InNewSpace(undefined_value()));
     MemsetPointer(array->data_start(), undefined_value(), length);
   }
   return result;
 }
 
 
 Object* Heap::AllocateRawFixedArray(int length, PretenureFlag pretenure) {
   if (length < 0 || length > FixedArray::kMaxLength) {
     return Failure::OutOfMemoryException();
   }
 
   AllocationSpace space =
       (pretenure == TENURED) ? OLD_POINTER_SPACE : NEW_SPACE;
   int size = FixedArray::SizeFor(length);
   if (space == NEW_SPACE && size > kMaxObjectSizeInNewSpace) {
     // Too big for new space.
     space = LO_SPACE;
   } else if (space == OLD_POINTER_SPACE &&
              size > MaxObjectSizeInPagedSpace()) {
     // Too big for old pointer space.
     space = LO_SPACE;
   }
 
-  AllocationSpace retry_space =
-      (size <= MaxObjectSizeInPagedSpace()) ? OLD_POINTER_SPACE : LO_SPACE;
-
-  return AllocateRaw(size, space, retry_space);
+  // Specialize allocation for the space.
+  Object* result = Failure::OutOfMemoryException();
+  if (space == NEW_SPACE) {
+    // We cannot use Heap::AllocateRaw() because it will not properly
+    // allocate extra remembered set bits if always_allocate() is true and
+    // new space allocation fails.
+    result = new_space_.AllocateRaw(size);
+    if (result->IsFailure() && always_allocate()) {
+      if (size <= MaxObjectSizeInPagedSpace()) {
+        result = old_pointer_space_->AllocateRaw(size);
+      } else {
+        result = lo_space_->AllocateRawFixedArray(size);
+      }
+    }
+  } else if (space == OLD_POINTER_SPACE) {
+    result = old_pointer_space_->AllocateRaw(size);
+  } else {
+    ASSERT(space == LO_SPACE);
+    result = lo_space_->AllocateRawFixedArray(size);
+  }
+  return result;
 }
 
 
 static Object* AllocateFixedArrayWithFiller(int length,
                                             PretenureFlag pretenure,
                                             Object* filler) {
   ASSERT(length >= 0);
   ASSERT(Heap::empty_fixed_array()->IsFixedArray());
   if (length == 0) return Heap::empty_fixed_array();
 
@@ skipping 27 matching lines @@
 
   reinterpret_cast<FixedArray*>(obj)->set_map(fixed_array_map());
   FixedArray::cast(obj)->set_length(length);
   return obj;
 }
 
 
 Object* Heap::AllocateHashTable(int length, PretenureFlag pretenure) {
   Object* result = Heap::AllocateFixedArray(length, pretenure);
   if (result->IsFailure()) return result;
-  reinterpret_cast<HeapObject*>(result)->set_map(hash_table_map());
+  reinterpret_cast<Array*>(result)->set_map(hash_table_map());
   ASSERT(result->IsHashTable());
   return result;
 }
 
 
 Object* Heap::AllocateGlobalContext() {
   Object* result = Heap::AllocateFixedArray(Context::GLOBAL_CONTEXT_SLOTS);
   if (result->IsFailure()) return result;
   Context* context = reinterpret_cast<Context*>(result);
   context->set_map(global_context_map());
@@ skipping 231 matching lines @@
       return cell_space_->Contains(addr);
     case LO_SPACE:
       return lo_space_->SlowContains(addr);
   }
 
   return false;
 }
 
 
 #ifdef DEBUG
-static void DummyScavengePointer(HeapObject** p) {
-}
-
-
-static void VerifyPointersUnderWatermark(
-    PagedSpace* space,
-    DirtyRegionCallback visit_dirty_region) {
-  PageIterator it(space, PageIterator::PAGES_IN_USE);
-
-  while (it.has_next()) {
-    Page* page = it.next();
-    Address start = page->ObjectAreaStart();
-    Address end = page->AllocationWatermark();
-
-    Heap::IterateDirtyRegions(Page::kAllRegionsDirtyMarks,
-                              start,
-                              end,
-                              visit_dirty_region,
-                              &DummyScavengePointer);
-  }
-}
-
-
-static void VerifyPointersUnderWatermark(LargeObjectSpace* space) {
-  LargeObjectIterator it(space);
-  for (HeapObject* object = it.next(); object != NULL; object = it.next()) {
-    if (object->IsFixedArray()) {
-      Address slot_address = object->address();
-      Address end = object->address() + object->Size();
-
-      while (slot_address < end) {
-        HeapObject** slot = reinterpret_cast<HeapObject**>(slot_address);
-        // When we are not in GC the Heap::InNewSpace() predicate
-        // checks that pointers which satisfy predicate point into
-        // the active semispace.
-        Heap::InNewSpace(*slot);
-        slot_address += kPointerSize;
-      }
-    }
-  }
-}
-
-
 void Heap::Verify() {
   ASSERT(HasBeenSetup());
 
   VerifyPointersVisitor visitor;
   IterateRoots(&visitor, VISIT_ONLY_STRONG);
 
   new_space_.Verify();
 
-  VerifyPointersAndDirtyRegionsVisitor dirty_regions_visitor;
-  old_pointer_space_->Verify(&dirty_regions_visitor);
-  map_space_->Verify(&dirty_regions_visitor);
+  VerifyPointersAndRSetVisitor rset_visitor;
+  old_pointer_space_->Verify(&rset_visitor);
+  map_space_->Verify(&rset_visitor);
 
-  VerifyPointersUnderWatermark(old_pointer_space_,
-                               &IteratePointersInDirtyRegion);
-  VerifyPointersUnderWatermark(map_space_,
-                               &IteratePointersInDirtyMapsRegion);
-  VerifyPointersUnderWatermark(lo_space_);
-
-  VerifyPageWatermarkValidity(old_pointer_space_, ALL_INVALID);
-  VerifyPageWatermarkValidity(map_space_, ALL_INVALID);
-
-  VerifyPointersVisitor no_dirty_regions_visitor;
-  old_data_space_->Verify(&no_dirty_regions_visitor);
-  code_space_->Verify(&no_dirty_regions_visitor);
-  cell_space_->Verify(&no_dirty_regions_visitor);
+  VerifyPointersVisitor no_rset_visitor;
+  old_data_space_->Verify(&no_rset_visitor);
+  code_space_->Verify(&no_rset_visitor);
+  cell_space_->Verify(&no_rset_visitor);
 
   lo_space_->Verify();
 }
 #endif  // DEBUG
 
 
 Object* Heap::LookupSymbol(Vector<const char> string) {
   Object* symbol = NULL;
   Object* new_table = symbol_table()->LookupSymbol(string, &symbol);
   if (new_table->IsFailure()) return new_table;
@@ skipping 32 matching lines @@
   ASSERT(reinterpret_cast<Object*>(kFromSpaceZapValue)->IsHeapObject());
   for (Address a = new_space_.FromSpaceLow();
        a < new_space_.FromSpaceHigh();
        a += kPointerSize) {
     Memory::Address_at(a) = kFromSpaceZapValue;
   }
 }
 #endif  // DEBUG
 
 
-bool Heap::IteratePointersInDirtyRegion(Address start,
-                                        Address end,
-                                        ObjectSlotCallback copy_object_func) {
-  Address slot_address = start;
-  bool pointers_to_new_space_found = false;
+int Heap::IterateRSetRange(Address object_start,
+                           Address object_end,
+                           Address rset_start,
+                           ObjectSlotCallback copy_object_func) {
+  Address object_address = object_start;
+  Address rset_address = rset_start;
+  int set_bits_count = 0;
 
-  while (slot_address < end) {
-    Object** slot = reinterpret_cast<Object**>(slot_address);
-    if (Heap::InNewSpace(*slot)) {
-      ASSERT((*slot)->IsHeapObject());
-      copy_object_func(reinterpret_cast<HeapObject**>(slot));
-      if (Heap::InNewSpace(*slot)) {
-        ASSERT((*slot)->IsHeapObject());
-        pointers_to_new_space_found = true;
+  // Loop over all the pointers in [object_start, object_end).
+  while (object_address < object_end) {
+    uint32_t rset_word = Memory::uint32_at(rset_address);
+    if (rset_word != 0) {
+      uint32_t result_rset = rset_word;
+      for (uint32_t bitmask = 1; bitmask != 0; bitmask = bitmask << 1) {
+        // Do not dereference pointers at or past object_end.
+        if ((rset_word & bitmask) != 0 && object_address < object_end) {
+          Object** object_p = reinterpret_cast<Object**>(object_address);
+          if (Heap::InNewSpace(*object_p)) {
+            copy_object_func(reinterpret_cast<HeapObject**>(object_p));
+          }
+          // If this pointer does not need to be remembered anymore, clear
+          // the remembered set bit.
+          if (!Heap::InNewSpace(*object_p)) result_rset &= ~bitmask;
+          set_bits_count++;
+        }
+        object_address += kPointerSize;
       }
+      // Update the remembered set if it has changed.
+      if (result_rset != rset_word) {
+        Memory::uint32_at(rset_address) = result_rset;
+      }
+    } else {
+      // No bits in the word were set.  This is the common case.
+      object_address += kPointerSize * kBitsPerInt;
     }
-    slot_address += kPointerSize;
+    rset_address += kIntSize;
   }
-  return pointers_to_new_space_found;
+  return set_bits_count;
 }
 
 
-// Compute start address of the first map following given addr.
-static inline Address MapStartAlign(Address addr) {
-  Address page = Page::FromAddress(addr)->ObjectAreaStart();
-  return page + (((addr - page) + (Map::kSize - 1)) / Map::kSize * Map::kSize);
-}
+void Heap::IterateRSet(PagedSpace* space, ObjectSlotCallback copy_object_func) {
+  ASSERT(Page::is_rset_in_use());
+  ASSERT(space == old_pointer_space_ || space == map_space_);
 
-
-// Compute end address of the first map preceding given addr.
-static inline Address MapEndAlign(Address addr) {
-  Address page = Page::FromAllocationTop(addr)->ObjectAreaStart();
-  return page + ((addr - page) / Map::kSize * Map::kSize);
-}
-
-
-static bool IteratePointersInDirtyMaps(Address start,
-                                       Address end,
-                                       ObjectSlotCallback copy_object_func) {
-  ASSERT(MapStartAlign(start) == start);
-  ASSERT(MapEndAlign(end) == end);
-
-  Address map_address = start;
-  bool pointers_to_new_space_found = false;
-
-  while (map_address < end) {
-    ASSERT(!Heap::InNewSpace(Memory::Object_at(map_address)));
-    ASSERT(Memory::Object_at(map_address)->IsMap());
-
-    Address pointer_fields_start = map_address + Map::kPointerFieldsBeginOffset;
-    Address pointer_fields_end = map_address + Map::kPointerFieldsEndOffset;
-
-    if (Heap::IteratePointersInDirtyRegion(pointer_fields_start,
-                                           pointer_fields_end,
-                                           copy_object_func)) {
-      pointers_to_new_space_found = true;
-    }
-
-    map_address += Map::kSize;
-  }
-
-  return pointers_to_new_space_found;
-}
-
-
-bool Heap::IteratePointersInDirtyMapsRegion(
-    Address start,
-    Address end,
-    ObjectSlotCallback copy_object_func) {
-  Address map_aligned_start = MapStartAlign(start);
-  Address map_aligned_end   = MapEndAlign(end);
-
-  bool contains_pointers_to_new_space = false;
-
-  if (map_aligned_start != start) {
-    Address prev_map = map_aligned_start - Map::kSize;
-    ASSERT(Memory::Object_at(prev_map)->IsMap());
-
-    Address pointer_fields_start =
-        Max(start, prev_map + Map::kPointerFieldsBeginOffset);
-
-    Address pointer_fields_end =
-        Min(prev_map + Map::kCodeCacheOffset + kPointerSize, end);
-
-    contains_pointers_to_new_space =
-      IteratePointersInDirtyRegion(pointer_fields_start,
-                                   pointer_fields_end,
-                                   copy_object_func)
-        || contains_pointers_to_new_space;
-  }
-
-  contains_pointers_to_new_space =
-    IteratePointersInDirtyMaps(map_aligned_start,
-                               map_aligned_end,
-                               copy_object_func)
-      || contains_pointers_to_new_space;
-
-  if (map_aligned_end != end) {
-    ASSERT(Memory::Object_at(map_aligned_end)->IsMap());
-
-    Address pointer_fields_start = map_aligned_end + Map::kPrototypeOffset;
-
-    Address pointer_fields_end =
-        Min(end, map_aligned_end + Map::kCodeCacheOffset + kPointerSize);
-
-    contains_pointers_to_new_space =
-      IteratePointersInDirtyRegion(pointer_fields_start,
-                                   pointer_fields_end,
-                                   copy_object_func)
-        || contains_pointers_to_new_space;
-  }
-
-  return contains_pointers_to_new_space;
-}
-
-
-void Heap::IterateAndMarkPointersToNewSpace(Address start,
-                                            Address end,
-                                            ObjectSlotCallback callback) {
-  Address slot_address = start;
-  Page* page = Page::FromAddress(start);
-
-  uint32_t marks = page->GetRegionMarks();
-
-  while (slot_address < end) {
-    Object** slot = reinterpret_cast<Object**>(slot_address);
-    if (Heap::InNewSpace(*slot)) {
-      ASSERT((*slot)->IsHeapObject());
-      callback(reinterpret_cast<HeapObject**>(slot));
-      if (Heap::InNewSpace(*slot)) {
-        ASSERT((*slot)->IsHeapObject());
-        marks |= page->GetRegionMaskForAddress(slot_address);
-      }
-    }
-    slot_address += kPointerSize;
-  }
-
-  page->SetRegionMarks(marks);
-}
-
-
-uint32_t Heap::IterateDirtyRegions(
-    uint32_t marks,
-    Address area_start,
-    Address area_end,
-    DirtyRegionCallback visit_dirty_region,
-    ObjectSlotCallback copy_object_func) {
-  uint32_t newmarks = 0;
-  uint32_t mask = 1;
-
-  if (area_start >= area_end) {
-    return newmarks;
-  }
-
-  Address region_start = area_start;
-
-  // area_start does not necessarily coincide with start of the first region.
-  // Thus to calculate the beginning of the next region we have to align
-  // area_start by Page::kRegionSize.
-  Address second_region =
-      reinterpret_cast<Address>(
-          reinterpret_cast<intptr_t>(area_start + Page::kRegionSize) &
-          ~Page::kRegionAlignmentMask);
-
-  // Next region might be beyond area_end.
-  Address region_end = Min(second_region, area_end);
-
-  if (marks & mask) {
-    if (visit_dirty_region(region_start, region_end, copy_object_func)) {
-      newmarks |= mask;
-    }
-  }
-  mask <<= 1;
-
-  // Iterate subsequent regions which fully lay inside [area_start, area_end[.
-  region_start = region_end;
-  region_end = region_start + Page::kRegionSize;
-
-  while (region_end <= area_end) {
-    if (marks & mask) {
-      if (visit_dirty_region(region_start, region_end, copy_object_func)) {
-        newmarks |= mask;
-      }
-    }
-
-    region_start = region_end;
-    region_end = region_start + Page::kRegionSize;
-
-    mask <<= 1;
-  }
-
-  if (region_start != area_end) {
-    // A small piece of area left uniterated because area_end does not coincide
-    // with region end. Check whether region covering last part of area is
-    // dirty.
-    if (marks & mask) {
-      if (visit_dirty_region(region_start, area_end, copy_object_func)) {
-        newmarks |= mask;
-      }
-    }
-  }
-
-  return newmarks;
-}
-
-
-
-void Heap::IterateDirtyRegions(
-    PagedSpace* space,
-    DirtyRegionCallback visit_dirty_region,
-    ObjectSlotCallback copy_object_func,
-    ExpectedPageWatermarkState expected_page_watermark_state) {
+  static void* paged_rset_histogram = StatsTable::CreateHistogram(
+      "V8.RSetPaged",
+      0,
+      Page::kObjectAreaSize / kPointerSize,
+      30);
 
   PageIterator it(space, PageIterator::PAGES_IN_USE);
-
   while (it.has_next()) {
     Page* page = it.next();
-    uint32_t marks = page->GetRegionMarks();
-
-    if (marks != Page::kAllRegionsCleanMarks) {
-      Address start = page->ObjectAreaStart();
-
-      // Do not try to visit pointers beyond page allocation watermark.
-      // Page can contain garbage pointers there.
-      Address end;
-
-      if ((expected_page_watermark_state == WATERMARK_SHOULD_BE_VALID) ||
-          page->IsWatermarkValid()) {
-        end = page->AllocationWatermark();
-      } else {
-        end = page->CachedAllocationWatermark();
-      }
-
-      ASSERT(space == old_pointer_space_ ||
-             (space == map_space_ &&
-              ((page->ObjectAreaStart() - end) % Map::kSize == 0)));
-
-      page->SetRegionMarks(IterateDirtyRegions(marks,
-                                               start,
-                                               end,
-                                               visit_dirty_region,
-                                               copy_object_func));
+    int count = IterateRSetRange(page->ObjectAreaStart(), page->AllocationTop(),
+                                 page->RSetStart(), copy_object_func);
+    if (paged_rset_histogram != NULL) {
+      StatsTable::AddHistogramSample(paged_rset_histogram, count);
     }
-
-    // Mark page watermark as invalid to maintain watermark validity invariant.
-    // See Page::FlipMeaningOfInvalidatedWatermarkFlag() for details.
-    page->InvalidateWatermark(true);
   }
 }
 
 
 void Heap::IterateRoots(ObjectVisitor* v, VisitMode mode) {
   IterateStrongRoots(v, mode);
   IterateWeakRoots(v, mode);
 }
 
 
@@ skipping 996 matching lines @@
 void ExternalStringTable::TearDown() {
   new_space_strings_.Free();
   old_space_strings_.Free();
 }
 
 
 List<Object*> ExternalStringTable::new_space_strings_;
 List<Object*> ExternalStringTable::old_space_strings_;
 
 } }  // namespace v8::internal