External string table.

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 715 matching lines @@
   //
   // There is guaranteed to be enough room at the top of the to space
   // for the addresses of promoted objects: every object promoted
   // frees up its size in bytes from the top of the new space, and
   // 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);
+  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.
   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_);
   while (cell_iterator.has_next()) {
     HeapObject* 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));
     }
   }
 
+  new_space_front = DoScavenge(&scavenge_visitor, new_space_front);
+
+  ScavengeExternalStringTable();
+  ASSERT(new_space_front == new_space_.top());
+
+  // Set age mark.
+  new_space_.set_age_mark(new_space_.top());
+
+  // Update how much has survived scavenge.
+  survived_since_last_expansion_ +=
+      (PromotedSpaceSize() - survived_watermark) + new_space_.Size();
+
+  LOG(ResourceEvent("scavenge", "end"));
+
+  gc_state_ = NOT_IN_GC;
+}
+
+
+void Heap::ScavengeExternalStringTable() {
+  ExternalStringTable::Verify();
+
+  if (ExternalStringTable::new_space_strings_.is_empty()) return;
+
+  Object** start = &ExternalStringTable::new_space_strings_[0];
+  Object** end = start + ExternalStringTable::new_space_strings_.length();
+  Object** last = start;
+
+  for (Object** p = start; p < end; ++p) {
+    ASSERT(Heap::InFromSpace(*p));
+    MapWord first_word = HeapObject::cast(*p)->map_word();
+
+    if (!first_word.IsForwardingAddress()) {
+      // Unreachable external string can be finalized.
+      FinalizeExternalString(String::cast(*p));
+      continue;
+    }
+
+    // String is still reachable.
+    String* target = String::cast(first_word.ToForwardingAddress());
+    ASSERT(target->IsExternalString());
+
+    if (Heap::InNewSpace(target)) {
+      // String is still in new space.  Update the table entry.
+      *last = target;
+      ++last;
+    } else {
+      // String got promoted.  Move it to the old string list.
+      ExternalStringTable::AddOldString(target);
+    }
+  }
+
+  ExternalStringTable::ShrinkNewStrings(last - start);
+}
+
+
+Address Heap::DoScavenge(ObjectVisitor* scavenge_visitor,
+                         Address new_space_front) {
   do {
     ASSERT(new_space_front <= new_space_.top());
 
     // The addresses new_space_front and new_space_.top() define a
     // queue of unprocessed copied objects.  Process them until the
     // queue is empty.
     while (new_space_front < new_space_.top()) {
       HeapObject* object = HeapObject::FromAddress(new_space_front);
-      object->Iterate(&scavenge_visitor);
+      object->Iterate(scavenge_visitor);
       new_space_front += object->Size();
     }
 
     // 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();
       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.
-      target->Iterate(&scavenge_visitor);
+      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());
 
-  // Set age mark.
-  new_space_.set_age_mark(new_space_.top());
-
-  // Update how much has survived scavenge.
-  survived_since_last_expansion_ +=
-      (PromotedSpaceSize() - survived_watermark) + new_space_.Size();
-
-  LOG(ResourceEvent("scavenge", "end"));
-
-  gc_state_ = NOT_IN_GC;
+  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,
@@ skipping 2354 matching lines @@
       StatsTable::AddHistogramSample(paged_rset_histogram, count);
     }
   }
 }
 
 
 void Heap::IterateRoots(ObjectVisitor* v, VisitMode mode) {
   IterateStrongRoots(v, mode);
   v->VisitPointer(reinterpret_cast<Object**>(&roots_[kSymbolTableRootIndex]));
   v->Synchronize("symbol_table");
+  if (mode != VISIT_ALL_IN_SCAVENGE) {
+    // Scavenge collections have special processing for this.
+    ExternalStringTable::Iterate(v);
+  }
+  v->Synchronize("external_string_table");
 }
 
 
 void Heap::IterateStrongRoots(ObjectVisitor* v, VisitMode mode) {
   v->VisitPointers(&roots_[0], &roots_[kStrongRootListLength]);
   v->Synchronize("strong_root_list");
 
   v->VisitPointer(bit_cast<Object**, String**>(&hidden_symbol_));
   v->Synchronize("symbol");
 
   Bootstrapper::Iterate(v);
   v->Synchronize("bootstrapper");
   Top::Iterate(v);
   v->Synchronize("top");
   Relocatable::Iterate(v);
   v->Synchronize("relocatable");
 
 #ifdef ENABLE_DEBUGGER_SUPPORT
   Debug::Iterate(v);
 #endif
   v->Synchronize("debug");
   CompilationCache::Iterate(v);
   v->Synchronize("compilationcache");
 
   // Iterate over local handles in handle scopes.
   HandleScopeImplementer::Iterate(v);
   v->Synchronize("handlescope");
 
-  // Iterate over the builtin code objects and code stubs in the heap. Note
-  // that it is not strictly necessary to iterate over code objects on
-  // scavenge collections.  We still do it here because this same function
-  // is used by the mark-sweep collector and the deserializer.
-  Builtins::IterateBuiltins(v);
+  // Iterate over the builtin code objects and code stubs in the
+  // heap. Note that it is not necessary to iterate over code objects
+  // on scavenge collections.
+  if (mode != VISIT_ALL_IN_SCAVENGE) {
+    Builtins::IterateBuiltins(v);
+  }
   v->Synchronize("builtins");
 
   // Iterate over global handles.
   if (mode == VISIT_ONLY_STRONG) {
     GlobalHandles::IterateStrongRoots(v);
   } else {
     GlobalHandles::IterateAllRoots(v);
   }
   v->Synchronize("globalhandles");
 
@@ skipping 196 matching lines @@
           (StackGuard::jslimit() & ~kSmiTagMask) | kSmiTag);
   roots_[kRealStackLimitRootIndex] =
       reinterpret_cast<Object*>(
           (StackGuard::real_jslimit() & ~kSmiTagMask) | kSmiTag);
 }
 
 
 void Heap::TearDown() {
   GlobalHandles::TearDown();
 
+  ExternalStringTable::TearDown();
+
   new_space_.TearDown();
 
   if (old_pointer_space_ != NULL) {
     old_pointer_space_->TearDown();
     delete old_pointer_space_;
     old_pointer_space_ = NULL;
   }
 
   if (old_data_space_ != NULL) {
     old_data_space_->TearDown();
@@ skipping 395 matching lines @@
     for (Object** p = start; p < end; p++) {
       if ((*p)->IsHeapObject())
         MarkRootObjectRecursively(p);
     }
   }
 };
 
 
 // Triggers a depth-first traversal of reachable objects from roots
 // and finds a path to a specific heap object and prints it.
-void Heap::TracePathToObject() {
-  search_target = NULL;
+void Heap::TracePathToObject(Object* target) {
+  search_target = target;
   search_for_any_global = false;
 
   MarkRootVisitor root_visitor;
   IterateRoots(&root_visitor, VISIT_ONLY_STRONG);
 }
 
 
 // Triggers a depth-first traversal of reachable objects from roots
 // and finds a path to any global object and prints it. Useful for
 // determining the source for leaks of global objects.
@@ skipping 130 matching lines @@
 void TranscendentalCache::Clear() {
   for (int i = 0; i < kNumberOfCaches; i++) {
     if (caches_[i] != NULL) {
       delete caches_[i];
       caches_[i] = NULL;
     }
   }
 }
 
 
+void ExternalStringTable::CleanUp() {
+  CleanUpList(true);
+  CleanUpList(false);
+  Verify();
+}
+
+
+void ExternalStringTable::CleanUpList(bool new_to_old) {
+  List<Object*>& source = new_to_old ? new_space_strings_ : old_space_strings_;
+  if (source.is_empty()) return;
+  List<Object*>& target = new_to_old ? old_space_strings_ : new_space_strings_;

[Mads Ager (chromium), 2009/12/08 16:18:40]

Use old_space_strings_ as the target always?  It should be completely clear that
this can only ever move from the new space list to the old space list.

It might be clearer to remove the bool parameter and just iterate
new_space_strings first and then iterate old_space_strings?  It is a bit more
code, but I think it would be clearer and it would remove checking for new space
for old_space_strings.

[Vitaly Repeshko, 2009/12/09 14:33:23]

Makes sense. Done.

+  int last = 0;
+  for (int i = 0; i < source.length(); ++i) {
+    if (source[i] == Heap::raw_unchecked_null_value()) continue;
+    if (Heap::InNewSpace(source[i]) == new_to_old) {
+      source[last++] = source[i];
+    } else {
+      target.Add(source[i]);
+    }
+  }
+  source.Rewind(last);
+}
+
+
+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