Merge 10601,10602,10616,10625,10647 from the bleeding edge to the 3.8 branch.

src/mark-compact.cc

 // Copyright 2012 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 212 matching lines @@
 }
 #endif
 
 
 void MarkCompactCollector::AddEvacuationCandidate(Page* p) {
   p->MarkEvacuationCandidate();
   evacuation_candidates_.Add(p);
 }
 
 
-bool MarkCompactCollector::StartCompaction() {
+static void TraceFragmentation(PagedSpace* space) {
+  int number_of_pages = space->CountTotalPages();
+  intptr_t reserved = (number_of_pages * space->AreaSize());
+  intptr_t free = reserved - space->SizeOfObjects();
+  PrintF("[%s]: %d pages, %d (%.1f%%) free\n",
+         AllocationSpaceName(space->identity()),
+         number_of_pages,
+         static_cast<int>(free),
+         static_cast<double>(free) * 100 / reserved);
+}
+
+
+bool MarkCompactCollector::StartCompaction(CompactionMode mode) {
   if (!compacting_) {
     ASSERT(evacuation_candidates_.length() == 0);
 
     CollectEvacuationCandidates(heap()->old_pointer_space());
     CollectEvacuationCandidates(heap()->old_data_space());
 
-    if (FLAG_compact_code_space) {
+    if (mode == NON_INCREMENTAL_COMPACTION) {
       CollectEvacuationCandidates(heap()->code_space());
+    } else if (FLAG_trace_fragmentation) {
+      TraceFragmentation(heap()->code_space());
+    }
+
+    if (FLAG_trace_fragmentation) {
+      TraceFragmentation(heap()->map_space());
+      TraceFragmentation(heap()->cell_space());
     }
 
     heap()->old_pointer_space()->EvictEvacuationCandidatesFromFreeLists();
     heap()->old_data_space()->EvictEvacuationCandidatesFromFreeLists();
     heap()->code_space()->EvictEvacuationCandidatesFromFreeLists();
 
     compacting_ = evacuation_candidates_.length() > 0;
   }
 
   return compacting_;
@@ skipping 155 matching lines @@
     case CELL_SPACE: return "CELL_SPACE";
     case LO_SPACE: return "LO_SPACE";
     default:
       UNREACHABLE();
   }
 
   return NULL;
 }
 
 
+// Returns zero for pages that have so little fragmentation that it is not
+// worth defragmenting them.  Otherwise a positive integer that gives an
+// estimate of fragmentation on an arbitrary scale.
+static int FreeListFragmentation(PagedSpace* space, Page* p) {
+  // If page was not swept then there are no free list items on it.
+  if (!p->WasSwept()) {
+    if (FLAG_trace_fragmentation) {
+      PrintF("%p [%s]: %d bytes live (unswept)\n",
+             reinterpret_cast<void*>(p),
+             AllocationSpaceName(space->identity()),
+             p->LiveBytes());
+    }
+    return 0;
+  }
+
+  FreeList::SizeStats sizes;
+  space->CountFreeListItems(p, &sizes);
+
+  intptr_t ratio;
+  intptr_t ratio_threshold;
+  int area_size = space->AreaSize();
+  if (space->identity() == CODE_SPACE) {
+    ratio = (sizes.medium_size_ * 10 + sizes.large_size_ * 2) * 100 /
+        area_size;
+    ratio_threshold = 10;
+  } else {
+    ratio = (sizes.small_size_ * 5 + sizes.medium_size_) * 100 /
+        area_size;
+    ratio_threshold = 15;
+  }
+
+  if (FLAG_trace_fragmentation) {
+    PrintF("%p [%s]: %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %s\n",
+           reinterpret_cast<void*>(p),
+           AllocationSpaceName(space->identity()),
+           static_cast<int>(sizes.small_size_),
+           static_cast<double>(sizes.small_size_ * 100) /
+           area_size,
+           static_cast<int>(sizes.medium_size_),
+           static_cast<double>(sizes.medium_size_ * 100) /
+           area_size,
+           static_cast<int>(sizes.large_size_),
+           static_cast<double>(sizes.large_size_ * 100) /
+           area_size,
+           static_cast<int>(sizes.huge_size_),
+           static_cast<double>(sizes.huge_size_ * 100) /
+           area_size,
+           (ratio > ratio_threshold) ? "[fragmented]" : "");
+  }
+
+  if (FLAG_always_compact && sizes.Total() != area_size) {
+    return 1;
+  }
+
+  if (ratio <= ratio_threshold) return 0;  // Not fragmented.
+
+  return static_cast<int>(ratio - ratio_threshold);
+}
+
+
 void MarkCompactCollector::CollectEvacuationCandidates(PagedSpace* space) {
   ASSERT(space->identity() == OLD_POINTER_SPACE ||
          space->identity() == OLD_DATA_SPACE ||
          space->identity() == CODE_SPACE);
 
   int number_of_pages = space->CountTotalPages();
 
-  PageIterator it(space);
   const int kMaxMaxEvacuationCandidates = 1000;
   int max_evacuation_candidates = Min(
     kMaxMaxEvacuationCandidates,
     static_cast<int>(sqrt(static_cast<double>(number_of_pages / 2)) + 1));
 
   if (FLAG_stress_compaction || FLAG_always_compact) {
     max_evacuation_candidates = kMaxMaxEvacuationCandidates;
   }
 
   class Candidate {
    public:
     Candidate() : fragmentation_(0), page_(NULL) { }
     Candidate(int f, Page* p) : fragmentation_(f), page_(p) { }
 
     int fragmentation() { return fragmentation_; }
     Page* page() { return page_; }
 
    private:
     int fragmentation_;
     Page* page_;
   };
 
+  enum CompactionMode {
+    COMPACT_FREE_LISTS,
+    REDUCE_MEMORY_FOOTPRINT
+  };
+
+  CompactionMode mode = COMPACT_FREE_LISTS;
+
+  intptr_t reserved = number_of_pages * space->AreaSize();
+  intptr_t over_reserved = reserved - space->SizeOfObjects();
+  static const intptr_t kFreenessThreshold = 50;
+
+  if (over_reserved >= 2 * space->AreaSize() &&
+      reduce_memory_footprint_) {
+    mode = REDUCE_MEMORY_FOOTPRINT;
+
+    // We expect that empty pages are easier to compact so slightly bump the
+    // limit.
+    max_evacuation_candidates += 2;
+
+    if (FLAG_trace_fragmentation) {
+      PrintF("Estimated over reserved memory: %.1f MB (setting threshold %d)\n",
+             static_cast<double>(over_reserved) / MB,
+             static_cast<int>(kFreenessThreshold));
+    }
+  }
+
+  intptr_t estimated_release = 0;
+
   Candidate candidates[kMaxMaxEvacuationCandidates];
 
   int count = 0;
-  if (it.has_next()) it.next();  // Never compact the first page.
   int fragmentation = 0;
   Candidate* least = NULL;
+
+  PageIterator it(space);
+  if (it.has_next()) it.next();  // Never compact the first page.
+
   while (it.has_next()) {
     Page* p = it.next();
     p->ClearEvacuationCandidate();
+
     if (FLAG_stress_compaction) {
       int counter = space->heap()->ms_count();
       uintptr_t page_number = reinterpret_cast<uintptr_t>(p) >> kPageSizeBits;
       if ((counter & 1) == (page_number & 1)) fragmentation = 1;
+    } else if (mode == REDUCE_MEMORY_FOOTPRINT) {
+      // Don't try to release too many pages.
+      if (estimated_release >= ((over_reserved * 3) / 4)) {
+        continue;
+      }
+
+      intptr_t free_bytes = 0;
+
+      if (!p->WasSwept()) {
+        free_bytes = (p->size() - p->LiveBytes());
+      } else {
+        FreeList::SizeStats sizes;
+        space->CountFreeListItems(p, &sizes);
+        free_bytes = sizes.Total();
+      }
+
+      int free_pct = static_cast<int>(free_bytes * 100 / p->area_size());
+
+      if (free_pct >= kFreenessThreshold) {
+        estimated_release += p->area_size() +
+            (p->area_size() - free_bytes);
+        fragmentation = free_pct;
+      } else {
+        fragmentation = 0;
+      }
+
+      if (FLAG_trace_fragmentation) {
+        PrintF("%p [%s]: %d (%.2f%%) free %s\n",
+               reinterpret_cast<void*>(p),
+               AllocationSpaceName(space->identity()),
+               static_cast<int>(free_bytes),
+               static_cast<double>(free_bytes * 100) / p->area_size(),
+               (fragmentation > 0) ? "[fragmented]" : "");
+      }
     } else {
-      fragmentation = space->Fragmentation(p);
+      fragmentation = FreeListFragmentation(space, p);
     }
+
     if (fragmentation != 0) {
       if (count < max_evacuation_candidates) {
         candidates[count++] = Candidate(fragmentation, p);
       } else {
         if (least == NULL) {
           for (int i = 0; i < max_evacuation_candidates; i++) {
             if (least == NULL ||
                 candidates[i].fragmentation() < least->fragmentation()) {
               least = candidates + i;
             }
           }
         }
         if (least->fragmentation() < fragmentation) {
           *least = Candidate(fragmentation, p);
           least = NULL;
         }
       }
     }
   }
+
   for (int i = 0; i < count; i++) {
     AddEvacuationCandidate(candidates[i].page());
   }
 
   if (count > 0 && FLAG_trace_fragmentation) {
     PrintF("Collected %d evacuation candidates for space %s\n",
            count,
            AllocationSpaceName(space->identity()));
   }
 }
@@ skipping 53 matching lines @@
   if (was_marked_incrementally_ && PreciseSweepingRequired()) {
     heap()->incremental_marking()->Abort();
     ClearMarkbits();
     AbortCompaction();
     was_marked_incrementally_ = false;
   }
 
   // Don't start compaction if we are in the middle of incremental
   // marking cycle. We did not collect any slots.
   if (!FLAG_never_compact && !was_marked_incrementally_) {
-    StartCompaction();
+    StartCompaction(NON_INCREMENTAL_COMPACTION);
   }
 
   PagedSpaces spaces;
   for (PagedSpace* space = spaces.next();
        space != NULL;
        space = spaces.next()) {
     space->PrepareForMarkCompact();
   }
 
 #ifdef DEBUG
@@ skipping 91 matching lines @@
         candidate->set_code(shared->code());
       }
 
       // We are in the middle of a GC cycle so the write barrier in the code
       // setter did not record the slot update and we have to do that manually.
       Address slot = candidate->address() + JSFunction::kCodeEntryOffset;
       Code* target = Code::cast(Code::GetObjectFromEntryAddress(slot));
       isolate_->heap()->mark_compact_collector()->
           RecordCodeEntrySlot(slot, target);
 
+      RecordSharedFunctionInfoCodeSlot(shared);
+
       candidate = next_candidate;
     }
 
     jsfunction_candidates_head_ = NULL;
   }
 
 
   void ProcessSharedFunctionInfoCandidates() {
     Code* lazy_compile = isolate_->builtins()->builtin(Builtins::kLazyCompile);
 
     SharedFunctionInfo* candidate = shared_function_info_candidates_head_;
     SharedFunctionInfo* next_candidate;
     while (candidate != NULL) {
       next_candidate = GetNextCandidate(candidate);
       SetNextCandidate(candidate, NULL);
 
       Code* code = candidate->code();
       MarkBit code_mark = Marking::MarkBitFrom(code);
       if (!code_mark.Get()) {
         candidate->set_code(lazy_compile);
       }
 
+      RecordSharedFunctionInfoCodeSlot(candidate);
+
       candidate = next_candidate;
     }
 
     shared_function_info_candidates_head_ = NULL;
   }
 
+  void RecordSharedFunctionInfoCodeSlot(SharedFunctionInfo* shared) {
+    Object** slot = HeapObject::RawField(shared,
+                                         SharedFunctionInfo::kCodeOffset);
+    isolate_->heap()->mark_compact_collector()->
+        RecordSlot(slot, slot, HeapObject::cast(*slot));
+  }
+
   static JSFunction** GetNextCandidateField(JSFunction* candidate) {
     return reinterpret_cast<JSFunction**>(
         candidate->address() + JSFunction::kCodeEntryOffset);
   }
 
   static JSFunction* GetNextCandidate(JSFunction* candidate) {
     return *GetNextCandidateField(candidate);
   }
 
   static void SetNextCandidate(JSFunction* candidate,
@@ skipping 456 matching lines @@
     // Make sure this is a RegExp that actually contains code.
     if (re->TypeTagUnchecked() != JSRegExp::IRREGEXP) return;
 
     Object* code = re->DataAtUnchecked(JSRegExp::code_index(is_ascii));
     if (!code->IsSmi() &&
         HeapObject::cast(code)->map()->instance_type() == CODE_TYPE) {
       // Save a copy that can be reinstated if we need the code again.
       re->SetDataAtUnchecked(JSRegExp::saved_code_index(is_ascii),
                              code,
                              heap);
+
+      // Saving a copy might create a pointer into compaction candidate
+      // that was not observed by marker.  This might happen if JSRegExp data
+      // was marked through the compilation cache before marker reached JSRegExp
+      // object.
+      FixedArray* data = FixedArray::cast(re->data());
+      Object** slot = data->data_start() + JSRegExp::saved_code_index(is_ascii);
+      heap->mark_compact_collector()->
+          RecordSlot(slot, slot, code);
+
       // Set a number in the 0-255 range to guarantee no smi overflow.
       re->SetDataAtUnchecked(JSRegExp::code_index(is_ascii),
                              Smi::FromInt(heap->sweep_generation() & 0xff),
                              heap);
     } else if (code->IsSmi()) {
       int value = Smi::cast(code)->value();
       // The regexp has not been compiled yet or there was a compilation error.
       if (value == JSRegExp::kUninitializedValue ||
           value == JSRegExp::kCompilationErrorValue) {
         return;
@@ skipping 2063 matching lines @@
   slots_buffer_allocator_.DeallocateChain(&migration_slots_buffer_);
   ASSERT(migration_slots_buffer_ == NULL);
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     if (!p->IsEvacuationCandidate()) continue;
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
     space->Free(p->area_start(), p->area_size());
     p->set_scan_on_scavenge(false);
     slots_buffer_allocator_.DeallocateChain(p->slots_buffer_address());
     p->ClearEvacuationCandidate();
+    p->ResetLiveBytes();
+    space->ReleasePage(p);
   }
   evacuation_candidates_.Rewind(0);
   compacting_ = false;
 }
 
 
 static const int kStartTableEntriesPerLine = 5;
 static const int kStartTableLines = 171;
 static const int kStartTableInvalidLine = 127;
 static const int kStartTableUnusedEntry = 126;
@@ skipping 688 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal