Simple BlinkGC heap compaction.

third_party/WebKit/Source/wtf/LinkedHashSet.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights
  * reserved.
  * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
@@ skipping 281 matching lines @@
   void remove(iterator);
   void clear() { m_impl.clear(); }
   template <typename Collection>
   void removeAll(const Collection& other) {
     WTF::removeAll(*this, other);
   }
 
   template <typename VisitorDispatcher>
   void trace(VisitorDispatcher visitor) {
     m_impl.trace(visitor);
+    // Should the underlying table be moved by GC, register a callback
+    // that fixes up the interior pointers that the (Heap)LinkedHashSet keeps.
+    if (m_impl.m_table) {
+      Allocator::registerBackingStoreCallback(
+          visitor, m_impl.m_table, moveBackingCallback,
+          reinterpret_cast<void*>(&m_anchor));
+    }
   }
 
   int64_t modifications() const { return m_impl.modifications(); }
   void checkModifications(int64_t mods) const {
     m_impl.checkModifications(mods);
   }
 
  private:
   Node* anchor() { return reinterpret_cast<Node*>(&m_anchor); }
   const Node* anchor() const {
@@ skipping 14 matching lines @@
   const_iterator makeConstIterator(const Node* position) const {
     return const_iterator(position, this);
   }
   reverse_iterator makeReverseIterator(const Node* position) {
     return reverse_iterator(position, this);
   }
   const_reverse_iterator makeConstReverseIterator(const Node* position) const {
     return const_reverse_iterator(position, this);
   }
 
+  static void moveBackingCallback(void* anchor,
+                                  void* from,
+                                  void* to,
+                                  size_t size) {
+    // Note: the hash table move may have been overlapping; linearly scan the
+    // entire table and fixup interior pointers into the old region with
+    // correspondingly offset ones into the new.
+    size_t tableSize = size / sizeof(Node);
+    Node* table = reinterpret_cast<Node*>(to);
+    NodeBase* fromStart = reinterpret_cast<NodeBase*>(from);
+    NodeBase* fromEnd =
+        reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(from) + size);
+    for (Node* element = table + tableSize - 1; element >= table; element--) {
+      Node& node = *element;
+      if (ImplType::isEmptyOrDeletedBucket(node))
+        continue;
+      if (node.m_next >= fromStart && node.m_next <= fromEnd) {

[haraken, 2016/12/09 07:25:56]

node.m_next < fromEnd ?

The same comment for other comparisons below.

[sof, 2016/12/09 21:44:05]

Yes, the range of these internal pointers is [fromStart, fromEnd), not
[fromStart, fromEnd]. Good catch.

+        size_t diff = reinterpret_cast<uintptr_t>(node.m_next) -
+                      reinterpret_cast<uintptr_t>(from);
+        node.m_next =
+            reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
+      }
+      if (node.m_prev >= fromStart && node.m_prev <= fromEnd) {
+        size_t diff = reinterpret_cast<uintptr_t>(node.m_prev) -
+                      reinterpret_cast<uintptr_t>(from);
+        node.m_prev =
+            reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
+      }
+    }
+    NodeBase* anchorNode = reinterpret_cast<NodeBase*>(anchor);
+    if (anchorNode->m_next >= fromStart && anchorNode->m_next <= fromEnd) {
+      size_t diff = reinterpret_cast<uintptr_t>(anchorNode->m_next) -
+                    reinterpret_cast<uintptr_t>(from);
+      anchorNode->m_next =
+          reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
+    }
+    if (anchorNode->m_prev >= fromStart && anchorNode->m_prev <= fromEnd) {
+      size_t diff = reinterpret_cast<uintptr_t>(anchorNode->m_prev) -
+                    reinterpret_cast<uintptr_t>(from);
+      anchorNode->m_prev =
+          reinterpret_cast<NodeBase*>(reinterpret_cast<uintptr_t>(to) + diff);
+    }
+  }
+
   ImplType m_impl;
   NodeBase m_anchor;
 };
 
 template <typename Value, typename HashFunctions, typename Allocator>
 struct LinkedHashSetTranslator {
   STATIC_ONLY(LinkedHashSetTranslator);
   typedef LinkedHashSetNode<Value, Allocator> Node;
   typedef LinkedHashSetNodeBase NodeBase;
   typedef typename HashTraits<Value>::PeekInType ValuePeekInType;
@@ skipping 522 matching lines @@
   swap(static_cast<Base&>(a), static_cast<Base&>(b));
   swap(a.m_value, b.m_value);
   Allocator::leaveGCForbiddenScope();
 }
 
 }  // namespace WTF
 
 using WTF::LinkedHashSet;
 
 #endif /* WTF_LinkedHashSet_h */