From e0b31bdbe9144f084915122cb63eed91a6581203 Mon Sep 17 00:00:00 2001
From: Anton Bikineev <[email protected]>
Date: Wed, 09 Sep 2026 03:46:22 -0700
Subject: [PATCH] [wtf] Allocate VectorBackedLinkedList anchor lazily

VectorBackedLinkedList previously allocated its out-of-line vector
backing during default construction to store the list's anchor node.
Consequently, when HeapLinkedHashSet was used as an inline value type
in HeapHashMap, empty buckets held default-constructed sets with
backing buffers that were not visited during tracing.

This change defers anchor node allocation until the first call to
insert(), ensuring default-constructed instances own no out-of-line
storage, and updates traversal and cleanup methods to handle the
unallocated state. A unit test covering this scenario is added.

Regression test: https://crbug.com/497112470
TAG=agy

Bug: 499571442
Change-Id: I2482e6ab2724235f2c5475eaefee03b6c11b5b88
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/8372183
Commit-Queue: Anton Bikineev <[email protected]>
Reviewed-by: Michael Lippautz <[email protected]>
Auto-Submit: Anton Bikineev <[email protected]>
Cr-Commit-Position: refs/heads/main@{#1694478}
---
diff --git a/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h b/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h
index 8303f0bb..ac98671 100644
--- a/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h
+++ b/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h
@@ -199,7 +199,9 @@
   using const_reverse_iterator =
       VectorBackedLinkedListConstReverseIterator<VectorBackedLinkedList>;
 
-  VectorBackedLinkedList();
+  // The anchor node is allocated lazily on the first call to insert() so that
+  // a default-constructed list does not own an out-of-line buffer.
+  VectorBackedLinkedList() = default;
   ~VectorBackedLinkedList() = default;
 
   void swap(VectorBackedLinkedList&);
@@ -264,6 +266,9 @@
 
   // Removes all elements in a linked list.
   void clear() {
+    if (nodes_.empty()) {
+      return;
+    }
     // Keep anchor so that we can insert elements after this operation.
     nodes_.ShrinkCapacity(1);
     nodes_[kAnchorIndex].prev_index_ = kAnchorIndex;
@@ -291,8 +296,12 @@
 
   bool IsFreeListEmpty() const { return free_head_index_ == kAnchorIndex; }
 
-  wtf_size_t UsedFirstIndex() const { return nodes_[kAnchorIndex].next_index_; }
-  wtf_size_t UsedLastIndex() const { return nodes_[kAnchorIndex].prev_index_; }
+  wtf_size_t UsedFirstIndex() const {
+    return nodes_.empty() ? kAnchorIndex : nodes_[kAnchorIndex].next_index_;
+  }
+  wtf_size_t UsedLastIndex() const {
+    return nodes_.empty() ? kAnchorIndex : nodes_[kAnchorIndex].prev_index_;
+  }
 
   const_iterator MakeConstIterator(wtf_size_t index) const {
     return const_iterator(index, this);
@@ -644,13 +653,6 @@
 };
 
 template <typename T, typename Allocator>
-VectorBackedLinkedList<T, Allocator>::VectorBackedLinkedList() {
-  // First inserts anchor, which serves as the beginning and the end of
-  // the used list.
-  nodes_.push_back(Node(kAnchorIndex, kAnchorIndex));
-}
-
-template <typename T, typename Allocator>
 inline void VectorBackedLinkedList<T, Allocator>::swap(
     VectorBackedLinkedList& other) {
   nodes_.swap(other.nodes_);
@@ -687,6 +689,11 @@
 typename VectorBackedLinkedList<T, Allocator>::iterator
 VectorBackedLinkedList<T, Allocator>::insert(const_iterator position,
                                              IncomingValueType&& value) {
+  if (nodes_.empty()) {
+    // Lazily insert the anchor, which serves as the beginning and the end of
+    // the used list.
+    nodes_.push_back(Node(kAnchorIndex, kAnchorIndex));
+  }
   wtf_size_t position_index = position.GetIndex();
   wtf_size_t prev_index = nodes_[position_index].prev_index_;
 
diff --git a/third_party/blink/renderer/platform/heap/test/heap_test.cc b/third_party/blink/renderer/platform/heap/test/heap_test.cc
index c205e1e..76a9b01 100644
--- a/third_party/blink/renderer/platform/heap/test/heap_test.cc
+++ b/third_party/blink/renderer/platform/heap/test/heap_test.cc
@@ -1631,6 +1631,31 @@
   ClearInWeakProcessingHelper<HeapLinkedHashSet<WeakMember<IntWrapper>>>();
 }
 
+TEST_F(HeapTest, HeapHashMapWithHeapLinkedHashSetValue) {
+  // HeapLinkedHashSet may be used as the inline value type of a HeapHashMap.
+  // Empty buckets in the map's backing are not visited during tracing, so a
+  // default-constructed value must not own any out-of-line allocations.
+  ClearOutOldGarbage();
+
+  using InnerSet = HeapLinkedHashSet<Member<IntWrapper>>;
+  using Map = GCedHeapHashMap<Member<IntWrapper>, InnerSet>;
+  Persistent<Map> map = MakeGarbageCollected<Map>();
+  Persistent<IntWrapper> key1 = MakeGarbageCollected<IntWrapper>(1);
+  Persistent<IntWrapper> key2 = MakeGarbageCollected<IntWrapper>(2);
+
+  map->ReserveCapacityForSize(8);
+  PreciselyCollectGarbage();
+
+  map->insert(key1.Get(), InnerSet()).stored_value->value.insert(key1.Get());
+  PreciselyCollectGarbage();
+  map->insert(key2.Get(), InnerSet()).stored_value->value.insert(key2.Get());
+  PreciselyCollectGarbage();
+
+  EXPECT_EQ(2u, map->size());
+  EXPECT_TRUE(map->find(key1.Get())->value.Contains(key1.Get()));
+  EXPECT_TRUE(map->find(key2.Get())->value.Contains(key2.Get()));
+}
+
 namespace {
 class ThingWithDestructor {
   DISALLOW_NEW();

diff --git a/third_party/blink/renderer/platform/heap/test/heap_test.cc b/third_party/blink/renderer/platform/heap/test/heap_test.cc
index c205e1e..76a9b01 100644
--- a/third_party/blink/renderer/platform/heap/test/heap_test.cc
+++ b/third_party/blink/renderer/platform/heap/test/heap_test.cc
@@ -1631,6 +1631,31 @@
   ClearInWeakProcessingHelper<HeapLinkedHashSet<WeakMember<IntWrapper>>>();
 }
 
+TEST_F(HeapTest, HeapHashMapWithHeapLinkedHashSetValue) {
+  // HeapLinkedHashSet may be used as the inline value type of a HeapHashMap.
+  // Empty buckets in the map's backing are not visited during tracing, so a
+  // default-constructed value must not own any out-of-line allocations.
+  ClearOutOldGarbage();
+
+  using InnerSet = HeapLinkedHashSet<Member<IntWrapper>>;
+  using Map = GCedHeapHashMap<Member<IntWrapper>, InnerSet>;
+  Persistent<Map> map = MakeGarbageCollected<Map>();
+  Persistent<IntWrapper> key1 = MakeGarbageCollected<IntWrapper>(1);
+  Persistent<IntWrapper> key2 = MakeGarbageCollected<IntWrapper>(2);
+
+  map->ReserveCapacityForSize(8);
+  PreciselyCollectGarbage();
+
+  map->insert(key1.Get(), InnerSet()).stored_value->value.insert(key1.Get());
+  PreciselyCollectGarbage();
+  map->insert(key2.Get(), InnerSet()).stored_value->value.insert(key2.Get());
+  PreciselyCollectGarbage();
+
+  EXPECT_EQ(2u, map->size());
+  EXPECT_TRUE(map->find(key1.Get())->value.Contains(key1.Get()));
+  EXPECT_TRUE(map->find(key2.Get())->value.Contains(key2.Get()));
+}
+
 namespace {
 class ThingWithDestructor {
   DISALLOW_NEW();