Rehash and clear deleted entries in weak collections during GC

jeisinger · Commit bot · commit e093a047796d · 2016-04-15T10:21:40.000Z
Otherwise, they'll just keep growing until we run out of memory or hit the FixedArray's maximum capacity. BUG=v8:4909 R=hpayer@chromium.org LOG=n Review URL: https://codereview.chromium.org/1877233005 Cr-Commit-Position: refs/heads/master@{#35514}
diff --git a/src/heap/mark-compact.cc b/src/heap/mark-compact.cc
@@ -2572,6 +2572,13 @@ void MarkCompactCollector::ClearWeakCollections() {
           table->RemoveEntry(i);
         }
       }
+      // Rehash if more than 25% of the entries are deleted entries.
+      // TODO(jochen): Consider to shrink the fixed array in place.
+      if ((table->NumberOfDeletedElements() << kJSWeakCollectionLoadFactorExp) >
+          table->NumberOfElements()) {
+        HandleScope scope(heap()->isolate());
+        table->Rehash(heap()->isolate()->factory()->undefined_value());
+      }
     }
     weak_collection_obj = weak_collection->next();
     weak_collection->set_next(heap()->undefined_value());
diff --git a/src/heap/mark-compact.h b/src/heap/mark-compact.h
@@ -512,6 +512,10 @@ class MarkCompactCollector {
   static const uint32_t kSingleFreeEncoding = 0;
   static const uint32_t kMultiFreeEncoding = 1;
 
+  // If the number of deleted slots in a JSWeakCollection exceeds the number
+  // of entries / 2^(factor), we rehash the table.
+  static const int kJSWeakCollectionLoadFactorExp = 1;
+
   static inline bool IsMarked(Object* obj);
   static bool IsUnmarkedHeapObjectWithHeap(Heap* heap, Object** p);
 
diff --git a/src/objects.cc b/src/objects.cc
@@ -16860,6 +16860,16 @@ void HashTable<Derived, Shape, Key>::Rehash(Key key) {
       }
     }
   }
+  // Wipe deleted entries.
+  Heap* heap = GetHeap();
+  Object* the_hole = heap->the_hole_value();
+  Object* undefined = heap->undefined_value();
+  for (uint32_t current = 0; current < capacity; current++) {
+    if (get(EntryToIndex(current)) == the_hole) {
+      set(EntryToIndex(current), undefined);
+    }
+  }
+  SetNumberOfDeletedElements(0);
 }
 
 
diff --git a/test/cctest/test-weakmaps.cc b/test/cctest/test-weakmaps.cc
@@ -124,7 +124,7 @@ TEST(Weakness) {
   heap->CollectAllGarbage(false);
   CHECK_EQ(1, NumberOfWeakCalls);
   CHECK_EQ(0, ObjectHashTable::cast(weakmap->table())->NumberOfElements());
-  CHECK_EQ(2,
+  CHECK_EQ(0,
            ObjectHashTable::cast(weakmap->table())->NumberOfDeletedElements());
 }
 
diff --git a/test/cctest/test-weaksets.cc b/test/cctest/test-weaksets.cc
@@ -123,8 +123,8 @@ TEST(WeakSet_Weakness) {
   heap->CollectAllGarbage(false);
   CHECK_EQ(1, NumberOfWeakCalls);
   CHECK_EQ(0, ObjectHashTable::cast(weakset->table())->NumberOfElements());
-  CHECK_EQ(
-      1, ObjectHashTable::cast(weakset->table())->NumberOfDeletedElements());
+  CHECK_EQ(0,
+           ObjectHashTable::cast(weakset->table())->NumberOfDeletedElements());
 }
 
 

Original file line number	Diff line number	Diff line change
`@@ -2572,6 +2572,13 @@ void MarkCompactCollector::ClearWeakCollections() {`
`2572`	`2572`	`table->RemoveEntry(i);`
`2573`	`2573`	`}`
`2574`	`2574`	`}`
	`2575`	`+ // Rehash if more than 25% of the entries are deleted entries.`
	`2576`	`+ // TODO(jochen): Consider to shrink the fixed array in place.`
	`2577`	`+ if ((table->NumberOfDeletedElements() << kJSWeakCollectionLoadFactorExp) >`
	`2578`	`+ table->NumberOfElements()) {`
	`2579`	`+ HandleScope scope(heap()->isolate());`
	`2580`	`+ table->Rehash(heap()->isolate()->factory()->undefined_value());`
	`2581`	`+ }`
`2575`	`2582`	`}`
`2576`	`2583`	`weak_collection_obj = weak_collection->next();`
`2577`	`2584`	`weak_collection->set_next(heap()->undefined_value());`
Original file line number	Diff line number	Diff line change
`@@ -16860,6 +16860,16 @@ void HashTable<Derived, Shape, Key>::Rehash(Key key) {`
`16860`	`16860`	`}`
`16861`	`16861`	`}`
`16862`	`16862`	`}`
	`16863`	`+ // Wipe deleted entries.`
	`16864`	`+ Heap* heap = GetHeap();`
	`16865`	`+ Object* the_hole = heap->the_hole_value();`
	`16866`	`+ Object* undefined = heap->undefined_value();`
	`16867`	`+ for (uint32_t current = 0; current < capacity; current++) {`
	`16868`	`+ if (get(EntryToIndex(current)) == the_hole) {`
	`16869`	`+ set(EntryToIndex(current), undefined);`
	`16870`	`+ }`
	`16871`	`+ }`
	`16872`	`+ SetNumberOfDeletedElements(0);`
`16863`	`16873`	`}`
`16864`	`16874`
`16865`	`16875`
Original file line number	Diff line number	Diff line change
`@@ -124,7 +124,7 @@ TEST(Weakness) {`
`124`	`124`	`heap->CollectAllGarbage(false);`
`125`	`125`	`CHECK_EQ(1, NumberOfWeakCalls);`
`126`	`126`	`CHECK_EQ(0, ObjectHashTable::cast(weakmap->table())->NumberOfElements());`
`127`		`- CHECK_EQ(2,`
	`127`	`+ CHECK_EQ(0,`
`128`	`128`	`ObjectHashTable::cast(weakmap->table())->NumberOfDeletedElements());`
`129`	`129`	`}`
`130`	`130`
Original file line number	Diff line number	Diff line change
`@@ -123,8 +123,8 @@ TEST(WeakSet_Weakness) {`
`123`	`123`	`heap->CollectAllGarbage(false);`
`124`	`124`	`CHECK_EQ(1, NumberOfWeakCalls);`
`125`	`125`	`CHECK_EQ(0, ObjectHashTable::cast(weakset->table())->NumberOfElements());`
`126`		`- CHECK_EQ(`
`127`		`- 1, ObjectHashTable::cast(weakset->table())->NumberOfDeletedElements());`
	`126`	`+ CHECK_EQ(0,`
	`127`	`+ ObjectHashTable::cast(weakset->table())->NumberOfDeletedElements());`
`128`	`128`	`}`
`129`	`129`
`130`	`130`