From 1d8f576aeea3ee0daeb3d680392a30a05e1c4f48 Mon Sep 17 00:00:00 2001
From: Tsuyoshi Horo <horo@chromium.org>
Date: Sun, 05 Jul 2026 21:30:44 -0700
Subject: [PATCH] net/disk_cache/sql: Re-insert in-memory index entry on kNotFound

BackendShard::DoomEntry optimistically removes the (hash, res_id) pair
from the in-memory index before posting the database update. The
recovery branch re-inserts it on database failure but excluded
Error::kNotFound. kNotFound is returned when the database row was not
modified (e.g. when res_id is present in the index for the key's hash
bucket but the row's cache_key belongs to a different key with a
colliding hash), so the index removal must be rolled back in that case
as well; otherwise the entry stays absent from the index while still
doomed=0 on disk, the kHashNotFound fast paths force a miss for that
key, and SpeculativeCreateEntry can write a duplicate live row for it.

Add unit tests that exercise the hash-collision case at the
SqlPersistentStore and SqlBackendImpl layers.

Bug: 518062961
Change-Id: I5c5413098c646b234addcb61871d8250892f5df2
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/8037960
Commit-Queue: Tsuyoshi Horo <horo@chromium.org>
Reviewed-by: Mingyu Lei <leimy@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1656973}
---

diff --git a/net/disk_cache/sql/sql_backend_impl_unittest.cc b/net/disk_cache/sql/sql_backend_impl_unittest.cc
index 0fc1c454..e36d61a 100644
--- a/net/disk_cache/sql/sql_backend_impl_unittest.cc
+++ b/net/disk_cache/sql/sql_backend_impl_unittest.cc
@@ -2408,6 +2408,73 @@
   EXPECT_THAT(open_result.net_error(), IsError(net::ERR_FAILED));
 }
 
+// Tests that dooming a non-existent key whose hash collides with an existing
+// entry's key does not affect the existing entry. The in-memory index is keyed
+// by hash only, so a single-entry hash bucket may resolve to a different key's
+// `res_id`; the backend must still keep the existing entry openable and avoid
+// creating duplicate rows for it.
+TEST_F(SqlBackendImplTest, DoomEntryWithInMemoryIndexHashCollision) {
+  // Two distinct keys with the same `CacheEntryKey::hash()`.
+  const std::string kExistingKey = "colliding-key-2018";
+  const std::string kCollidingKey = "colliding-key-3000";
+  const CacheEntryKey kExistingEntryKey(kExistingKey);
+  ASSERT_EQ(kExistingEntryKey.hash(), CacheEntryKey(kCollidingKey).hash());
+
+  auto backend = CreateBackendAndInit();
+
+  // 1. Create an entry for `kExistingKey` and close it so it is no longer
+  //    active.
+  TestEntryResultCompletionCallback cb_create;
+  disk_cache::EntryResult create_result = cb_create.GetResult(
+      backend->CreateEntry(kExistingKey, net::HIGHEST, cb_create.callback()));
+  ASSERT_THAT(create_result.net_error(), IsOk());
+  create_result.ReleaseEntry()->Close();
+  backend->RunUntilAllTasksCompleteForTest();
+
+  // 2. Load the in-memory index. `kExistingKey` is the sole occupant of its
+  //    hash bucket.
+  ASSERT_TRUE(LoadInMemoryIndex(*backend));
+  ASSERT_EQ(backend->GetSqlStoreForTest()->GetIndexStateForHash(
+                kExistingEntryKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // 3. Doom `kCollidingKey`, which does not exist but shares its hash with
+  //    `kExistingKey`.
+  net::TestCompletionCallback cb_doom;
+  EXPECT_THAT(cb_doom.GetResult(backend->DoomEntry(kCollidingKey, net::HIGHEST,
+                                                   cb_doom.callback())),
+              IsOk());
+  backend->RunUntilAllTasksCompleteForTest();
+
+  // 4. The existing entry must remain in the in-memory index.
+  EXPECT_EQ(backend->GetSqlStoreForTest()->GetIndexStateForHash(
+                kExistingEntryKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // 5. Opening `kExistingKey` must still succeed.
+  TestEntryResultCompletionCallback cb_open;
+  disk_cache::EntryResult open_result = cb_open.GetResult(
+      backend->OpenEntry(kExistingKey, net::HIGHEST, cb_open.callback()));
+  ASSERT_THAT(open_result.net_error(), IsOk());
+  open_result.ReleaseEntry()->Close();
+
+  // 6. OpenOrCreateEntry must open the existing entry rather than creating a
+  //    duplicate row.
+  TestEntryResultCompletionCallback cb_ooc;
+  disk_cache::EntryResult ooc_result =
+      cb_ooc.GetResult(backend->OpenOrCreateEntry(kExistingKey, net::HIGHEST,
+                                                  cb_ooc.callback()));
+  ASSERT_THAT(ooc_result.net_error(), IsOk());
+  EXPECT_TRUE(ooc_result.opened());
+  ooc_result.ReleaseEntry()->Close();
+  backend->RunUntilAllTasksCompleteForTest();
+
+  base::test::TestFuture<int32_t> count_future;
+  EXPECT_EQ(backend->GetEntryCount(count_future.GetCallback()),
+            base::unexpected(net::ERR_IO_PENDING));
+  EXPECT_EQ(count_future.Get(), 1);
+}
+
 TEST_F(SqlBackendImplTest, SetDataHintsAndDoomAndWriteOptimistically) {
   auto backend = CreateBackendAndInit();
   const std::string kKey = "my-key";
diff --git a/net/disk_cache/sql/sql_persistent_store_backend_shard.cc b/net/disk_cache/sql/sql_persistent_store_backend_shard.cc
index 99ac962..7db97f3 100644
--- a/net/disk_cache/sql/sql_persistent_store_backend_shard.cc
+++ b/net/disk_cache/sql/sql_persistent_store_backend_shard.cc
@@ -122,15 +122,17 @@
              bool need_recovery_on_failure, CacheEntryKey::Hash hash,
              ResId res_id, ErrorCallback callback, ErrorAndStoreStatus result) {
             if (weak_ptr) {
-              // If the DoomEntry operation fails in the database, the entry
-              // needs to be re-inserted into the in-memory index to maintain
-              // consistency.
+              // If the DoomEntry operation did not mark the row as doomed in
+              // the database (including `kNotFound`, which can occur when the
+              // `res_id` belongs to a different `cache_key` whose hash
+              // collides with `key`'s hash), the entry needs to be re-inserted
+              // into the in-memory index so that the index remains consistent
+              // with the unchanged database state.
               // Note: Optimistic write failure may trigger a call to DoomEntry,
               // which occurs without exclusive control. In this case, if
               // eviction runs immediately after Backend::DoomEntry, the index
               // might be missing.
               if (need_recovery_on_failure && result.result != Error::kOk &&
-                  result.result != Error::kNotFound &&
                   weak_ptr->index_.has_value()) {
                 weak_ptr->index_->Insert(hash, res_id);
               }
diff --git a/net/disk_cache/sql/sql_persistent_store_unittest.cc b/net/disk_cache/sql/sql_persistent_store_unittest.cc
index 15fe60f6..42cdece 100644
--- a/net/disk_cache/sql/sql_persistent_store_unittest.cc
+++ b/net/disk_cache/sql/sql_persistent_store_unittest.cc
@@ -5727,6 +5727,43 @@
   EXPECT_FALSE(open_result->has_value());
 }
 
+// Tests that when `DoomEntry` is called with a `res_id` that is present in the
+// in-memory index for the key's hash bucket but belongs to a different
+// `cache_key` in the database (so the operation returns `kNotFound`), the
+// optimistic in-memory index removal is rolled back to keep the index
+// consistent with the database.
+TEST_P(SqlPersistentStoreTest, DoomEntryRecoversIndexOnNotFound) {
+  CreateAndInitStore();
+  ASSERT_TRUE(LoadInMemoryIndex());
+
+  // Two distinct keys with the same `CacheEntryKey::hash()`.
+  const CacheEntryKey kExistingKey("colliding-key-2018");
+  const CacheEntryKey kCollidingKey("colliding-key-3000");
+  ASSERT_NE(kExistingKey, kCollidingKey);
+  ASSERT_EQ(kExistingKey.hash(), kCollidingKey.hash());
+
+  const auto res_id = CreateEntryAndGetResId(kExistingKey);
+  ASSERT_EQ(store_->GetIndexStateForHash(kExistingKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // Attempt to doom `kCollidingKey` using `kExistingKey`'s `res_id`. The
+  // database row's `cache_key` does not match, so the operation must report
+  // `kNotFound` without modifying the database.
+  EXPECT_EQ(DoomEntry(kCollidingKey, res_id),
+            SqlPersistentStore::Error::kNotFound);
+
+  // The existing entry must remain in the in-memory index.
+  EXPECT_EQ(store_->GetIndexStateForHash(kExistingKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // The existing entry must remain unaffected in the database as well.
+  EXPECT_EQ(GetEntryCount(), 1);
+  auto open_result = OpenEntry(kExistingKey);
+  ASSERT_TRUE(open_result.has_value());
+  ASSERT_TRUE(open_result->has_value());
+  EXPECT_EQ((*open_result)->res_id, res_id);
+}
+
 TEST_P(SqlPersistentStoreTest,
        DoomedEntryDuringEvictionRemovedFromIndexAfterReturn) {
   const int64_t kMaxBytes = 10000;

diff --git a/net/disk_cache/sql/sql_backend_impl_unittest.cc b/net/disk_cache/sql/sql_backend_impl_unittest.cc
index 0fc1c454..e36d61a 100644
--- a/net/disk_cache/sql/sql_backend_impl_unittest.cc
+++ b/net/disk_cache/sql/sql_backend_impl_unittest.cc
@@ -2408,6 +2408,73 @@
   EXPECT_THAT(open_result.net_error(), IsError(net::ERR_FAILED));
 }
 
+// Tests that dooming a non-existent key whose hash collides with an existing
+// entry's key does not affect the existing entry. The in-memory index is keyed
+// by hash only, so a single-entry hash bucket may resolve to a different key's
+// `res_id`; the backend must still keep the existing entry openable and avoid
+// creating duplicate rows for it.
+TEST_F(SqlBackendImplTest, DoomEntryWithInMemoryIndexHashCollision) {
+  // Two distinct keys with the same `CacheEntryKey::hash()`.
+  const std::string kExistingKey = "colliding-key-2018";
+  const std::string kCollidingKey = "colliding-key-3000";
+  const CacheEntryKey kExistingEntryKey(kExistingKey);
+  ASSERT_EQ(kExistingEntryKey.hash(), CacheEntryKey(kCollidingKey).hash());
+
+  auto backend = CreateBackendAndInit();
+
+  // 1. Create an entry for `kExistingKey` and close it so it is no longer
+  //    active.
+  TestEntryResultCompletionCallback cb_create;
+  disk_cache::EntryResult create_result = cb_create.GetResult(
+      backend->CreateEntry(kExistingKey, net::HIGHEST, cb_create.callback()));
+  ASSERT_THAT(create_result.net_error(), IsOk());
+  create_result.ReleaseEntry()->Close();
+  backend->RunUntilAllTasksCompleteForTest();
+
+  // 2. Load the in-memory index. `kExistingKey` is the sole occupant of its
+  //    hash bucket.
+  ASSERT_TRUE(LoadInMemoryIndex(*backend));
+  ASSERT_EQ(backend->GetSqlStoreForTest()->GetIndexStateForHash(
+                kExistingEntryKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // 3. Doom `kCollidingKey`, which does not exist but shares its hash with
+  //    `kExistingKey`.
+  net::TestCompletionCallback cb_doom;
+  EXPECT_THAT(cb_doom.GetResult(backend->DoomEntry(kCollidingKey, net::HIGHEST,
+                                                   cb_doom.callback())),
+              IsOk());
+  backend->RunUntilAllTasksCompleteForTest();
+
+  // 4. The existing entry must remain in the in-memory index.
+  EXPECT_EQ(backend->GetSqlStoreForTest()->GetIndexStateForHash(
+                kExistingEntryKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // 5. Opening `kExistingKey` must still succeed.
+  TestEntryResultCompletionCallback cb_open;
+  disk_cache::EntryResult open_result = cb_open.GetResult(
+      backend->OpenEntry(kExistingKey, net::HIGHEST, cb_open.callback()));
+  ASSERT_THAT(open_result.net_error(), IsOk());
+  open_result.ReleaseEntry()->Close();
+
+  // 6. OpenOrCreateEntry must open the existing entry rather than creating a
+  //    duplicate row.
+  TestEntryResultCompletionCallback cb_ooc;
+  disk_cache::EntryResult ooc_result =
+      cb_ooc.GetResult(backend->OpenOrCreateEntry(kExistingKey, net::HIGHEST,
+                                                  cb_ooc.callback()));
+  ASSERT_THAT(ooc_result.net_error(), IsOk());
+  EXPECT_TRUE(ooc_result.opened());
+  ooc_result.ReleaseEntry()->Close();
+  backend->RunUntilAllTasksCompleteForTest();
+
+  base::test::TestFuture<int32_t> count_future;
+  EXPECT_EQ(backend->GetEntryCount(count_future.GetCallback()),
+            base::unexpected(net::ERR_IO_PENDING));
+  EXPECT_EQ(count_future.Get(), 1);
+}
+
 TEST_F(SqlBackendImplTest, SetDataHintsAndDoomAndWriteOptimistically) {
   auto backend = CreateBackendAndInit();
   const std::string kKey = "my-key";
diff --git a/net/disk_cache/sql/sql_persistent_store_unittest.cc b/net/disk_cache/sql/sql_persistent_store_unittest.cc
index 15fe60f6..42cdece 100644
--- a/net/disk_cache/sql/sql_persistent_store_unittest.cc
+++ b/net/disk_cache/sql/sql_persistent_store_unittest.cc
@@ -5727,6 +5727,43 @@
   EXPECT_FALSE(open_result->has_value());
 }
 
+// Tests that when `DoomEntry` is called with a `res_id` that is present in the
+// in-memory index for the key's hash bucket but belongs to a different
+// `cache_key` in the database (so the operation returns `kNotFound`), the
+// optimistic in-memory index removal is rolled back to keep the index
+// consistent with the database.
+TEST_P(SqlPersistentStoreTest, DoomEntryRecoversIndexOnNotFound) {
+  CreateAndInitStore();
+  ASSERT_TRUE(LoadInMemoryIndex());
+
+  // Two distinct keys with the same `CacheEntryKey::hash()`.
+  const CacheEntryKey kExistingKey("colliding-key-2018");
+  const CacheEntryKey kCollidingKey("colliding-key-3000");
+  ASSERT_NE(kExistingKey, kCollidingKey);
+  ASSERT_EQ(kExistingKey.hash(), kCollidingKey.hash());
+
+  const auto res_id = CreateEntryAndGetResId(kExistingKey);
+  ASSERT_EQ(store_->GetIndexStateForHash(kExistingKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // Attempt to doom `kCollidingKey` using `kExistingKey`'s `res_id`. The
+  // database row's `cache_key` does not match, so the operation must report
+  // `kNotFound` without modifying the database.
+  EXPECT_EQ(DoomEntry(kCollidingKey, res_id),
+            SqlPersistentStore::Error::kNotFound);
+
+  // The existing entry must remain in the in-memory index.
+  EXPECT_EQ(store_->GetIndexStateForHash(kExistingKey.hash()),
+            SqlPersistentStore::IndexState::kHashFound);
+
+  // The existing entry must remain unaffected in the database as well.
+  EXPECT_EQ(GetEntryCount(), 1);
+  auto open_result = OpenEntry(kExistingKey);
+  ASSERT_TRUE(open_result.has_value());
+  ASSERT_TRUE(open_result->has_value());
+  EXPECT_EQ((*open_result)->res_id, res_id);
+}
+
 TEST_P(SqlPersistentStoreTest,
        DoomedEntryDuringEvictionRemovedFromIndexAfterReturn) {
   const int64_t kMaxBytes = 10000;