| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "net/disk_cache/blockfile/index_table_v3.h" | |
| 6 | |
| 7 #include <stdint.h> | |
| 8 #include <utility> | |
| 9 | |
| 10 #include "base/logging.h" | |
| 11 #include "base/macros.h" | |
| 12 #include "net/disk_cache/blockfile/addr.h" | |
| 13 #include "net/disk_cache/blockfile/disk_format_v3.h" | |
| 14 #include "testing/gtest/include/gtest/gtest.h" | |
| 15 | |
| 16 using disk_cache::EntryCell; | |
| 17 using disk_cache::IndexCell; | |
| 18 using disk_cache::IndexTable; | |
| 19 using disk_cache::IndexTableInitData; | |
| 20 | |
| 21 namespace { | |
| 22 | |
| 23 int GetChecksum(const IndexCell& source) { | |
| 24 // Only the cell pointer is relevant. | |
| 25 disk_cache::Addr addr; | |
| 26 IndexCell* cell = const_cast<IndexCell*>(&source); | |
| 27 EntryCell entry = EntryCell::GetEntryCellForTest(0, 0, addr, cell, false); | |
| 28 | |
| 29 IndexCell result; | |
| 30 entry.SerializaForTest(&result); | |
| 31 return result.last_part >> 6; | |
| 32 } | |
| 33 | |
| 34 class MockIndexBackend : public disk_cache::IndexTableBackend { | |
| 35 public: | |
| 36 MockIndexBackend() : grow_called_(false), buffer_len_(-1) {} | |
| 37 ~MockIndexBackend() override {} | |
| 38 | |
| 39 bool grow_called() const { return grow_called_; } | |
| 40 int buffer_len() const { return buffer_len_; } | |
| 41 | |
| 42 void GrowIndex() override { grow_called_ = true; } | |
| 43 void SaveIndex(net::IOBuffer* buffer, int buffer_len) override { | |
| 44 buffer_len_ = buffer_len; | |
| 45 } | |
| 46 void DeleteCell(EntryCell cell) override {} | |
| 47 void FixCell(EntryCell cell) override {} | |
| 48 | |
| 49 private: | |
| 50 bool grow_called_; | |
| 51 int buffer_len_; | |
| 52 }; | |
| 53 | |
| 54 class TestCacheTables { | |
| 55 public: | |
| 56 // |num_entries| is the capacity of the main table. The extra table is half | |
| 57 // the size of the main table. | |
| 58 explicit TestCacheTables(int num_entries); | |
| 59 ~TestCacheTables() {} | |
| 60 | |
| 61 void GetInitData(IndexTableInitData* result); | |
| 62 void CopyFrom(const TestCacheTables& other); | |
| 63 base::Time start_time() const { return start_time_; } | |
| 64 | |
| 65 private: | |
| 66 std::unique_ptr<uint64_t[]> main_bitmap_; | |
| 67 std::unique_ptr<disk_cache::IndexBucket[]> main_table_; | |
| 68 std::unique_ptr<disk_cache::IndexBucket[]> extra_table_; | |
| 69 base::Time start_time_; | |
| 70 int num_bitmap_bytes_; | |
| 71 | |
| 72 DISALLOW_COPY_AND_ASSIGN(TestCacheTables); | |
| 73 }; | |
| 74 | |
| 75 TestCacheTables::TestCacheTables(int num_entries) { | |
| 76 DCHECK_GE(num_entries, 1024); | |
| 77 DCHECK_EQ(num_entries, num_entries / 1024 * 1024); | |
| 78 main_table_.reset(new disk_cache::IndexBucket[num_entries]); | |
| 79 extra_table_.reset(new disk_cache::IndexBucket[num_entries / 2]); | |
| 80 memset(main_table_.get(), 0, num_entries * sizeof(*main_table_.get())); | |
| 81 memset(extra_table_.get(), 0, num_entries / 2 * sizeof(*extra_table_.get())); | |
| 82 | |
| 83 // We allow IndexBitmap smaller than a page because the code should not really | |
| 84 // depend on that. | |
| 85 num_bitmap_bytes_ = (num_entries + num_entries / 2) / 8; | |
| 86 size_t required_size = sizeof(disk_cache::IndexHeaderV3) + num_bitmap_bytes_; | |
| 87 main_bitmap_.reset(new uint64_t[required_size / sizeof(uint64_t)]); | |
| 88 memset(main_bitmap_.get(), 0, required_size); | |
| 89 | |
| 90 disk_cache::IndexHeaderV3* header = | |
| 91 reinterpret_cast<disk_cache::IndexHeaderV3*>(main_bitmap_.get()); | |
| 92 | |
| 93 header->magic = disk_cache::kIndexMagicV3; | |
| 94 header->version = disk_cache::kVersion3; | |
| 95 header->table_len = num_entries + num_entries / 2; | |
| 96 header->max_bucket = num_entries / 4 - 1; | |
| 97 | |
| 98 start_time_ = base::Time::Now(); | |
| 99 header->create_time = start_time_.ToInternalValue(); | |
| 100 header->base_time = | |
| 101 (start_time_ - base::TimeDelta::FromDays(20)).ToInternalValue(); | |
| 102 | |
| 103 if (num_entries < 64 * 1024) | |
| 104 header->flags = disk_cache::SMALL_CACHE; | |
| 105 } | |
| 106 | |
| 107 void TestCacheTables::GetInitData(IndexTableInitData* result) { | |
| 108 result->index_bitmap = | |
| 109 reinterpret_cast<disk_cache::IndexBitmap*>(main_bitmap_.get()); | |
| 110 | |
| 111 result->main_table = main_table_.get(); | |
| 112 result->extra_table = extra_table_.get(); | |
| 113 | |
| 114 result->backup_header.reset(new disk_cache::IndexHeaderV3); | |
| 115 memcpy(result->backup_header.get(), result->index_bitmap, | |
| 116 sizeof(result->index_bitmap->header)); | |
| 117 | |
| 118 result->backup_bitmap.reset( | |
| 119 new uint32_t[num_bitmap_bytes_ / sizeof(uint32_t)]); | |
| 120 memcpy(result->backup_bitmap.get(), result->index_bitmap->bitmap, | |
| 121 num_bitmap_bytes_); | |
| 122 } | |
| 123 | |
| 124 void TestCacheTables::CopyFrom(const TestCacheTables& other) { | |
| 125 disk_cache::IndexBitmap* this_bitmap = | |
| 126 reinterpret_cast<disk_cache::IndexBitmap*>(main_bitmap_.get()); | |
| 127 disk_cache::IndexBitmap* other_bitmap = | |
| 128 reinterpret_cast<disk_cache::IndexBitmap*>(other.main_bitmap_.get()); | |
| 129 | |
| 130 DCHECK_GE(this_bitmap->header.table_len, other_bitmap->header.table_len); | |
| 131 DCHECK_GE(num_bitmap_bytes_, other.num_bitmap_bytes_); | |
| 132 | |
| 133 memcpy(this_bitmap->bitmap, other_bitmap->bitmap, other.num_bitmap_bytes_); | |
| 134 | |
| 135 int main_table_buckets = (other_bitmap->header.table_len * 2 / 3) / 4; | |
| 136 int extra_table_buckets = (other_bitmap->header.table_len * 1 / 3) / 4; | |
| 137 memcpy(main_table_.get(), other.main_table_.get(), | |
| 138 main_table_buckets * sizeof(disk_cache::IndexBucket)); | |
| 139 memcpy(extra_table_.get(), other.extra_table_.get(), | |
| 140 extra_table_buckets * sizeof(disk_cache::IndexBucket)); | |
| 141 | |
| 142 this_bitmap->header.num_entries = other_bitmap->header.num_entries; | |
| 143 this_bitmap->header.used_cells = other_bitmap->header.used_cells; | |
| 144 this_bitmap->header.max_bucket = other_bitmap->header.max_bucket; | |
| 145 this_bitmap->header.create_time = other_bitmap->header.create_time; | |
| 146 this_bitmap->header.base_time = other_bitmap->header.base_time; | |
| 147 this_bitmap->header.flags = other_bitmap->header.flags; | |
| 148 start_time_ = other.start_time_; | |
| 149 } | |
| 150 | |
| 151 } // namespace | |
| 152 | |
| 153 TEST(DiskCacheIndexTable, EntryCell) { | |
| 154 uint32_t hash = 0x55aa6699; | |
| 155 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, 0x4531); | |
| 156 bool small_table = true; | |
| 157 int cell_num = 88; | |
| 158 int reuse = 6; | |
| 159 int timestamp = 123456; | |
| 160 disk_cache::EntryState state = disk_cache::ENTRY_MODIFIED; | |
| 161 disk_cache::EntryGroup group = disk_cache::ENTRY_HIGH_USE; | |
| 162 | |
| 163 for (int i = 0; i < 4; i++) { | |
| 164 SCOPED_TRACE(i); | |
| 165 EntryCell entry = EntryCell::GetEntryCellForTest(cell_num, hash, addr, NULL, | |
| 166 small_table); | |
| 167 EXPECT_EQ(disk_cache::ENTRY_NO_USE, entry.GetGroup()); | |
| 168 EXPECT_EQ(disk_cache::ENTRY_NEW, entry.GetState()); | |
| 169 | |
| 170 entry.SetGroup(group); | |
| 171 entry.SetState(state); | |
| 172 entry.SetReuse(reuse); | |
| 173 entry.SetTimestamp(timestamp); | |
| 174 | |
| 175 EXPECT_TRUE(entry.IsValid()); | |
| 176 EXPECT_EQ(hash, entry.hash()); | |
| 177 EXPECT_EQ(cell_num, entry.cell_num()); | |
| 178 EXPECT_EQ(addr.value(), entry.GetAddress().value()); | |
| 179 | |
| 180 EXPECT_EQ(group, entry.GetGroup()); | |
| 181 EXPECT_EQ(state, entry.GetState()); | |
| 182 EXPECT_EQ(reuse, entry.GetReuse()); | |
| 183 EXPECT_EQ(timestamp, entry.GetTimestamp()); | |
| 184 | |
| 185 // Store the data and read it again. | |
| 186 IndexCell cell; | |
| 187 entry.SerializaForTest(&cell); | |
| 188 | |
| 189 EntryCell entry2 = EntryCell::GetEntryCellForTest(cell_num, hash, addr, | |
| 190 &cell, small_table); | |
| 191 | |
| 192 EXPECT_EQ(addr.value(), entry2.GetAddress().value()); | |
| 193 | |
| 194 EXPECT_EQ(group, entry2.GetGroup()); | |
| 195 EXPECT_EQ(state, entry2.GetState()); | |
| 196 EXPECT_EQ(reuse, entry2.GetReuse()); | |
| 197 EXPECT_EQ(timestamp, entry2.GetTimestamp()); | |
| 198 | |
| 199 small_table = !small_table; | |
| 200 if (i == 1) { | |
| 201 hash = ~hash; | |
| 202 cell_num *= 5; | |
| 203 state = disk_cache::ENTRY_USED; | |
| 204 group = disk_cache::ENTRY_EVICTED; | |
| 205 addr = disk_cache::Addr(disk_cache::BLOCK_EVICTED, 1, 6, 0x18a5); | |
| 206 reuse = 15; // 4 bits | |
| 207 timestamp = 0xfffff; // 20 bits. | |
| 208 } | |
| 209 } | |
| 210 } | |
| 211 | |
| 212 // Goes over some significant values for a cell's sum. | |
| 213 TEST(DiskCacheIndexTable, EntryCellSum) { | |
| 214 IndexCell source; | |
| 215 source.Clear(); | |
| 216 EXPECT_EQ(0, GetChecksum(source)); | |
| 217 | |
| 218 source.first_part++; | |
| 219 EXPECT_EQ(1, GetChecksum(source)); | |
| 220 | |
| 221 source.Clear(); | |
| 222 source.last_part = 0x80; | |
| 223 EXPECT_EQ(0, GetChecksum(source)); | |
| 224 | |
| 225 source.last_part = 0x55; | |
| 226 EXPECT_EQ(3, GetChecksum(source)); | |
| 227 | |
| 228 source.first_part = 0x555555; | |
| 229 EXPECT_EQ(2, GetChecksum(source)); | |
| 230 | |
| 231 source.last_part = 0; | |
| 232 EXPECT_EQ(1, GetChecksum(source)); | |
| 233 | |
| 234 source.first_part = UINT64_C(0x8000000080000000); | |
| 235 EXPECT_EQ(0, GetChecksum(source)); | |
| 236 | |
| 237 source.first_part = UINT64_C(0x4000000040000000); | |
| 238 EXPECT_EQ(2, GetChecksum(source)); | |
| 239 | |
| 240 source.first_part = UINT64_C(0x200000020000000); | |
| 241 EXPECT_EQ(1, GetChecksum(source)); | |
| 242 | |
| 243 source.first_part = UINT64_C(0x100000010010000); | |
| 244 EXPECT_EQ(3, GetChecksum(source)); | |
| 245 | |
| 246 source.first_part = 0x80008000; | |
| 247 EXPECT_EQ(0, GetChecksum(source)); | |
| 248 | |
| 249 source.first_part = UINT64_C(0x800000008000); | |
| 250 EXPECT_EQ(1, GetChecksum(source)); | |
| 251 | |
| 252 source.first_part = 0x8080; | |
| 253 EXPECT_EQ(0, GetChecksum(source)); | |
| 254 | |
| 255 source.first_part = 0x800080; | |
| 256 EXPECT_EQ(1, GetChecksum(source)); | |
| 257 | |
| 258 source.first_part = 0x88; | |
| 259 EXPECT_EQ(0, GetChecksum(source)); | |
| 260 | |
| 261 source.first_part = 0x808; | |
| 262 EXPECT_EQ(1, GetChecksum(source)); | |
| 263 | |
| 264 source.first_part = 0xA; | |
| 265 EXPECT_EQ(0, GetChecksum(source)); | |
| 266 | |
| 267 source.first_part = 0x22; | |
| 268 EXPECT_EQ(1, GetChecksum(source)); | |
| 269 } | |
| 270 | |
| 271 TEST(DiskCacheIndexTable, Basics) { | |
| 272 TestCacheTables cache(1024); | |
| 273 IndexTableInitData init_data; | |
| 274 cache.GetInitData(&init_data); | |
| 275 | |
| 276 IndexTable index(NULL); | |
| 277 index.Init(&init_data); | |
| 278 | |
| 279 // Write some entries. | |
| 280 disk_cache::CellList entries; | |
| 281 for (int i = 0; i < 250; i++) { | |
| 282 SCOPED_TRACE(i); | |
| 283 uint32_t hash = i * i * 1111 + i * 11; | |
| 284 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 285 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 286 EXPECT_TRUE(entry.IsValid()); | |
| 287 | |
| 288 disk_cache::CellInfo info = { hash, addr }; | |
| 289 entries.push_back(info); | |
| 290 } | |
| 291 | |
| 292 // Read them back. | |
| 293 for (size_t i = 0; i < entries.size(); i++) { | |
| 294 SCOPED_TRACE(i); | |
| 295 uint32_t hash = entries[i].hash; | |
| 296 disk_cache::Addr addr = entries[i].address; | |
| 297 | |
| 298 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 299 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 300 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 301 EXPECT_EQ(hash, found_entries.cells[0].hash()); | |
| 302 EXPECT_EQ(addr.value(), found_entries.cells[0].GetAddress().value()); | |
| 303 | |
| 304 EntryCell entry = index.FindEntryCell(hash, addr); | |
| 305 EXPECT_TRUE(entry.IsValid()); | |
| 306 EXPECT_EQ(hash, entry.hash()); | |
| 307 EXPECT_EQ(addr.value(), entry.GetAddress().value()); | |
| 308 | |
| 309 // Delete the first 100 entries. | |
| 310 if (i < 100) | |
| 311 index.SetSate(hash, addr, disk_cache::ENTRY_DELETED); | |
| 312 } | |
| 313 | |
| 314 // See what we have now. | |
| 315 for (size_t i = 0; i < entries.size(); i++) { | |
| 316 SCOPED_TRACE(i); | |
| 317 uint32_t hash = entries[i].hash; | |
| 318 disk_cache::Addr addr = entries[i].address; | |
| 319 | |
| 320 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 321 if (i < 100) { | |
| 322 EXPECT_EQ(0u, found_entries.cells.size()); | |
| 323 } else { | |
| 324 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 325 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 326 EXPECT_EQ(hash, found_entries.cells[0].hash()); | |
| 327 EXPECT_EQ(addr.value(), found_entries.cells[0].GetAddress().value()); | |
| 328 } | |
| 329 } | |
| 330 } | |
| 331 | |
| 332 // Tests handling of multiple entries with the same hash. | |
| 333 TEST(DiskCacheIndexTable, SameHash) { | |
| 334 TestCacheTables cache(1024); | |
| 335 IndexTableInitData init_data; | |
| 336 cache.GetInitData(&init_data); | |
| 337 | |
| 338 IndexTable index(NULL); | |
| 339 index.Init(&init_data); | |
| 340 | |
| 341 disk_cache::CellList entries; | |
| 342 uint32_t hash = 0x55aa55bb; | |
| 343 for (int i = 0; i < 6; i++) { | |
| 344 SCOPED_TRACE(i); | |
| 345 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 346 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 347 EXPECT_TRUE(entry.IsValid()); | |
| 348 | |
| 349 disk_cache::CellInfo info = { hash, addr }; | |
| 350 entries.push_back(info); | |
| 351 } | |
| 352 | |
| 353 disk_cache::EntrySet found_entries = index.LookupEntries(hash); | |
| 354 EXPECT_EQ(0, found_entries.evicted_count); | |
| 355 ASSERT_EQ(6u, found_entries.cells.size()); | |
| 356 | |
| 357 for (size_t i = 0; i < found_entries.cells.size(); i++) { | |
| 358 SCOPED_TRACE(i); | |
| 359 EXPECT_EQ(entries[i].address, found_entries.cells[i].GetAddress()); | |
| 360 } | |
| 361 | |
| 362 // Now verify handling of entries on different states. | |
| 363 index.SetSate(hash, entries[0].address, disk_cache::ENTRY_DELETED); | |
| 364 index.SetSate(hash, entries[1].address, disk_cache::ENTRY_DELETED); | |
| 365 index.SetSate(hash, entries[2].address, disk_cache::ENTRY_USED); | |
| 366 index.SetSate(hash, entries[3].address, disk_cache::ENTRY_USED); | |
| 367 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_USED); | |
| 368 | |
| 369 found_entries = index.LookupEntries(hash); | |
| 370 EXPECT_EQ(0, found_entries.evicted_count); | |
| 371 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 372 | |
| 373 index.SetSate(hash, entries[3].address, disk_cache::ENTRY_OPEN); | |
| 374 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_OPEN); | |
| 375 | |
| 376 found_entries = index.LookupEntries(hash); | |
| 377 EXPECT_EQ(0, found_entries.evicted_count); | |
| 378 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 379 | |
| 380 index.SetSate(hash, entries[4].address, disk_cache::ENTRY_MODIFIED); | |
| 381 | |
| 382 found_entries = index.LookupEntries(hash); | |
| 383 EXPECT_EQ(0, found_entries.evicted_count); | |
| 384 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 385 | |
| 386 index.SetSate(hash, entries[1].address, disk_cache::ENTRY_FREE); | |
| 387 | |
| 388 found_entries = index.LookupEntries(hash); | |
| 389 EXPECT_EQ(0, found_entries.evicted_count); | |
| 390 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 391 | |
| 392 // FindEntryCell should not see deleted entries. | |
| 393 EntryCell entry = index.FindEntryCell(hash, entries[0].address); | |
| 394 EXPECT_FALSE(entry.IsValid()); | |
| 395 | |
| 396 // A free entry is gone. | |
| 397 entry = index.FindEntryCell(hash, entries[1].address); | |
| 398 EXPECT_FALSE(entry.IsValid()); | |
| 399 | |
| 400 // Locate a used entry, and evict it. This is not really a correct operation | |
| 401 // in that an existing cell doesn't transition to evicted; instead a new cell | |
| 402 // for the evicted entry (on a different block file) should be created. Still, | |
| 403 // at least evicted_count would be valid. | |
| 404 entry = index.FindEntryCell(hash, entries[2].address); | |
| 405 EXPECT_TRUE(entry.IsValid()); | |
| 406 entry.SetGroup(disk_cache::ENTRY_EVICTED); | |
| 407 index.Save(&entry); | |
| 408 | |
| 409 found_entries = index.LookupEntries(hash); | |
| 410 EXPECT_EQ(1, found_entries.evicted_count); | |
| 411 ASSERT_EQ(4u, found_entries.cells.size()); | |
| 412 | |
| 413 // Now use the proper way to get an evicted entry. | |
| 414 disk_cache::Addr addr2(disk_cache::BLOCK_EVICTED, 1, 6, 6); // Any address. | |
| 415 entry = index.CreateEntryCell(hash, addr2); | |
| 416 EXPECT_TRUE(entry.IsValid()); | |
| 417 EXPECT_EQ(disk_cache::ENTRY_EVICTED, entry.GetGroup()); | |
| 418 | |
| 419 found_entries = index.LookupEntries(hash); | |
| 420 EXPECT_EQ(2, found_entries.evicted_count); | |
| 421 ASSERT_EQ(5u, found_entries.cells.size()); | |
| 422 } | |
| 423 | |
| 424 TEST(DiskCacheIndexTable, Timestamps) { | |
| 425 TestCacheTables cache(1024); | |
| 426 IndexTableInitData init_data; | |
| 427 cache.GetInitData(&init_data); | |
| 428 | |
| 429 IndexTable index(NULL); | |
| 430 index.Init(&init_data); | |
| 431 | |
| 432 // The granularity should be 1 minute. | |
| 433 int timestamp1 = index.CalculateTimestamp(cache.start_time()); | |
| 434 int timestamp2 = index.CalculateTimestamp(cache.start_time() + | |
| 435 base::TimeDelta::FromSeconds(59)); | |
| 436 EXPECT_EQ(timestamp1, timestamp2); | |
| 437 | |
| 438 int timestamp3 = index.CalculateTimestamp(cache.start_time() + | |
| 439 base::TimeDelta::FromSeconds(61)); | |
| 440 EXPECT_EQ(timestamp1 + 1, timestamp3); | |
| 441 | |
| 442 int timestamp4 = index.CalculateTimestamp(cache.start_time() + | |
| 443 base::TimeDelta::FromSeconds(119)); | |
| 444 EXPECT_EQ(timestamp1 + 1, timestamp4); | |
| 445 | |
| 446 int timestamp5 = index.CalculateTimestamp(cache.start_time() + | |
| 447 base::TimeDelta::FromSeconds(121)); | |
| 448 EXPECT_EQ(timestamp1 + 2, timestamp5); | |
| 449 | |
| 450 int timestamp6 = index.CalculateTimestamp(cache.start_time() - | |
| 451 base::TimeDelta::FromSeconds(30)); | |
| 452 EXPECT_EQ(timestamp1 - 1, timestamp6); | |
| 453 | |
| 454 // The base should be 20 days in the past. | |
| 455 int timestamp7 = index.CalculateTimestamp(cache.start_time() - | |
| 456 base::TimeDelta::FromDays(20)); | |
| 457 int timestamp8 = index.CalculateTimestamp(cache.start_time() - | |
| 458 base::TimeDelta::FromDays(35)); | |
| 459 EXPECT_EQ(timestamp7, timestamp8); | |
| 460 EXPECT_EQ(0, timestamp8); | |
| 461 | |
| 462 int timestamp9 = index.CalculateTimestamp(cache.start_time() - | |
| 463 base::TimeDelta::FromDays(19)); | |
| 464 EXPECT_NE(0, timestamp9); | |
| 465 } | |
| 466 | |
| 467 // Tests GetOldest and GetNextCells. | |
| 468 TEST(DiskCacheIndexTable, Iterations) { | |
| 469 TestCacheTables cache(1024); | |
| 470 IndexTableInitData init_data; | |
| 471 cache.GetInitData(&init_data); | |
| 472 | |
| 473 IndexTable index(NULL); | |
| 474 index.Init(&init_data); | |
| 475 | |
| 476 base::Time time = cache.start_time(); | |
| 477 | |
| 478 // Write some entries. | |
| 479 disk_cache::CellList entries; | |
| 480 for (int i = 0; i < 44; i++) { | |
| 481 SCOPED_TRACE(i); | |
| 482 uint32_t hash = i; // The entries will be ordered on the table. | |
| 483 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 13 + 1); | |
| 484 if (i < 10 || i == 40) | |
| 485 addr = disk_cache::Addr(disk_cache::BLOCK_EVICTED, 1, 6, i * 13 + 1); | |
| 486 | |
| 487 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 488 EXPECT_TRUE(entry.IsValid()); | |
| 489 | |
| 490 disk_cache::CellInfo info = { hash, addr }; | |
| 491 entries.push_back(info); | |
| 492 | |
| 493 if (i < 10 || i == 40) { | |
| 494 // Do nothing. These are ENTRY_EVICTED by default. | |
| 495 } else if (i < 20 || i == 41) { | |
| 496 entry.SetGroup(disk_cache::ENTRY_HIGH_USE); | |
| 497 index.Save(&entry); | |
| 498 } else if (i < 30 || i == 42) { | |
| 499 entry.SetGroup(disk_cache::ENTRY_LOW_USE); | |
| 500 index.Save(&entry); | |
| 501 } | |
| 502 | |
| 503 // Entries [30,39] and 43 are marked as ENTRY_NO_USE (the default). | |
| 504 | |
| 505 if (!(i % 10)) | |
| 506 time += base::TimeDelta::FromMinutes(1); | |
| 507 | |
| 508 index.UpdateTime(hash, addr, time); | |
| 509 } | |
| 510 | |
| 511 // Get the oldest entries of each group. | |
| 512 disk_cache::IndexIterator no_use, low_use, high_use; | |
| 513 index.GetOldest(&no_use, &low_use, &high_use); | |
| 514 ASSERT_EQ(10u, no_use.cells.size()); | |
| 515 ASSERT_EQ(10u, low_use.cells.size()); | |
| 516 ASSERT_EQ(10u, high_use.cells.size()); | |
| 517 | |
| 518 EXPECT_EQ(entries[10].hash, high_use.cells[0].hash); | |
| 519 EXPECT_EQ(entries[19].hash, high_use.cells[9].hash); | |
| 520 EXPECT_EQ(entries[20].hash, low_use.cells[0].hash); | |
| 521 EXPECT_EQ(entries[29].hash, low_use.cells[9].hash); | |
| 522 EXPECT_EQ(entries[30].hash, no_use.cells[0].hash); | |
| 523 EXPECT_EQ(entries[39].hash, no_use.cells[9].hash); | |
| 524 | |
| 525 // Now start an iteration from the head (most recent entry). | |
| 526 disk_cache::IndexIterator iterator; | |
| 527 iterator.timestamp = index.CalculateTimestamp(time) + 1; | |
| 528 iterator.forward = false; // Back in time. | |
| 529 | |
| 530 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 531 ASSERT_EQ(3u, iterator.cells.size()); | |
| 532 EXPECT_EQ(entries[41].hash, iterator.cells[0].hash); | |
| 533 EXPECT_EQ(entries[42].hash, iterator.cells[1].hash); | |
| 534 EXPECT_EQ(entries[43].hash, iterator.cells[2].hash); | |
| 535 | |
| 536 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 537 ASSERT_EQ(10u, iterator.cells.size()); | |
| 538 EXPECT_EQ(entries[30].hash, iterator.cells[0].hash); | |
| 539 EXPECT_EQ(entries[39].hash, iterator.cells[9].hash); | |
| 540 | |
| 541 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 542 ASSERT_EQ(10u, iterator.cells.size()); | |
| 543 EXPECT_EQ(entries[20].hash, iterator.cells[0].hash); | |
| 544 EXPECT_EQ(entries[29].hash, iterator.cells[9].hash); | |
| 545 | |
| 546 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 547 ASSERT_EQ(10u, iterator.cells.size()); | |
| 548 EXPECT_EQ(entries[10].hash, iterator.cells[0].hash); | |
| 549 EXPECT_EQ(entries[19].hash, iterator.cells[9].hash); | |
| 550 | |
| 551 ASSERT_FALSE(index.GetNextCells(&iterator)); | |
| 552 | |
| 553 // Now start an iteration from the tail (oldest entry). | |
| 554 iterator.timestamp = 0; | |
| 555 iterator.forward = true; | |
| 556 | |
| 557 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 558 ASSERT_EQ(10u, iterator.cells.size()); | |
| 559 EXPECT_EQ(entries[10].hash, iterator.cells[0].hash); | |
| 560 EXPECT_EQ(entries[19].hash, iterator.cells[9].hash); | |
| 561 | |
| 562 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 563 ASSERT_EQ(10u, iterator.cells.size()); | |
| 564 EXPECT_EQ(entries[20].hash, iterator.cells[0].hash); | |
| 565 EXPECT_EQ(entries[29].hash, iterator.cells[9].hash); | |
| 566 | |
| 567 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 568 ASSERT_EQ(10u, iterator.cells.size()); | |
| 569 EXPECT_EQ(entries[30].hash, iterator.cells[0].hash); | |
| 570 EXPECT_EQ(entries[39].hash, iterator.cells[9].hash); | |
| 571 | |
| 572 ASSERT_TRUE(index.GetNextCells(&iterator)); | |
| 573 ASSERT_EQ(3u, iterator.cells.size()); | |
| 574 EXPECT_EQ(entries[41].hash, iterator.cells[0].hash); | |
| 575 EXPECT_EQ(entries[42].hash, iterator.cells[1].hash); | |
| 576 EXPECT_EQ(entries[43].hash, iterator.cells[2].hash); | |
| 577 } | |
| 578 | |
| 579 // Tests doubling of the table. | |
| 580 TEST(DiskCacheIndexTable, Doubling) { | |
| 581 IndexTable index(NULL); | |
| 582 int size = 1024; | |
| 583 std::unique_ptr<TestCacheTables> cache(new TestCacheTables(size)); | |
| 584 int entry_id = 0; | |
| 585 disk_cache::CellList entries; | |
| 586 | |
| 587 // Go from 1024 to 256k cells. | |
| 588 for (int resizes = 0; resizes <= 8; resizes++) { | |
| 589 std::unique_ptr<TestCacheTables> old_cache(std::move(cache)); | |
| 590 cache.reset(new TestCacheTables(size)); | |
| 591 cache.get()->CopyFrom(*old_cache.get()); | |
| 592 | |
| 593 IndexTableInitData init_data; | |
| 594 cache.get()->GetInitData(&init_data); | |
| 595 index.Init(&init_data); | |
| 596 | |
| 597 // Write some entries. | |
| 598 for (int i = 0; i < 250; i++, entry_id++) { | |
| 599 SCOPED_TRACE(entry_id); | |
| 600 uint32_t hash = entry_id * i * 321 + entry_id * 13; | |
| 601 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, entry_id * 17 + 1); | |
| 602 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 603 EXPECT_TRUE(entry.IsValid()); | |
| 604 | |
| 605 disk_cache::CellInfo info = { hash, addr }; | |
| 606 entries.push_back(info); | |
| 607 } | |
| 608 size *= 2; | |
| 609 } | |
| 610 | |
| 611 // Access all the entries. | |
| 612 for (size_t i = 0; i < entries.size(); i++) { | |
| 613 SCOPED_TRACE(i); | |
| 614 disk_cache::EntrySet found_entries = index.LookupEntries(entries[i].hash); | |
| 615 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 616 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 617 } | |
| 618 } | |
| 619 | |
| 620 // Tests bucket chaining when growing the index. | |
| 621 TEST(DiskCacheIndexTable, BucketChains) { | |
| 622 IndexTable index(NULL); | |
| 623 int size = 1024; | |
| 624 std::unique_ptr<TestCacheTables> cache(new TestCacheTables(size)); | |
| 625 disk_cache::CellList entries; | |
| 626 | |
| 627 IndexTableInitData init_data; | |
| 628 cache.get()->GetInitData(&init_data); | |
| 629 index.Init(&init_data); | |
| 630 | |
| 631 // Write some entries. | |
| 632 for (int i = 0; i < 8; i++) { | |
| 633 SCOPED_TRACE(i); | |
| 634 uint32_t hash = i * 256; | |
| 635 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 7 + 1); | |
| 636 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 637 EXPECT_TRUE(entry.IsValid()); | |
| 638 | |
| 639 disk_cache::CellInfo info = { hash, addr }; | |
| 640 entries.push_back(info); | |
| 641 } | |
| 642 | |
| 643 // Double the size. | |
| 644 std::unique_ptr<TestCacheTables> old_cache(std::move(cache)); | |
| 645 cache.reset(new TestCacheTables(size * 2)); | |
| 646 cache.get()->CopyFrom(*old_cache.get()); | |
| 647 | |
| 648 cache.get()->GetInitData(&init_data); | |
| 649 index.Init(&init_data); | |
| 650 | |
| 651 // Write more entries, starting with the upper half of the table. | |
| 652 for (int i = 9; i < 11; i++) { | |
| 653 SCOPED_TRACE(i); | |
| 654 uint32_t hash = i * 256; | |
| 655 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i * 7 + 1); | |
| 656 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 657 EXPECT_TRUE(entry.IsValid()); | |
| 658 | |
| 659 disk_cache::CellInfo info = { hash, addr }; | |
| 660 entries.push_back(info); | |
| 661 } | |
| 662 | |
| 663 // Access all the entries. | |
| 664 for (size_t i = 0; i < entries.size(); i++) { | |
| 665 SCOPED_TRACE(i); | |
| 666 disk_cache::EntrySet found_entries = index.LookupEntries(entries[i].hash); | |
| 667 ASSERT_EQ(1u, found_entries.cells.size()); | |
| 668 EXPECT_TRUE(found_entries.cells[0].IsValid()); | |
| 669 } | |
| 670 } | |
| 671 | |
| 672 // Tests that GrowIndex is called. | |
| 673 TEST(DiskCacheIndexTable, GrowIndex) { | |
| 674 TestCacheTables cache(1024); | |
| 675 IndexTableInitData init_data; | |
| 676 cache.GetInitData(&init_data); | |
| 677 MockIndexBackend backend; | |
| 678 | |
| 679 IndexTable index(&backend); | |
| 680 index.Init(&init_data); | |
| 681 | |
| 682 // Write some entries. | |
| 683 for (int i = 0; i < 512; i++) { | |
| 684 SCOPED_TRACE(i); | |
| 685 uint32_t hash = 0; | |
| 686 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, i + 1); | |
| 687 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 688 EXPECT_TRUE(entry.IsValid()); | |
| 689 } | |
| 690 | |
| 691 EXPECT_TRUE(backend.grow_called()); | |
| 692 } | |
| 693 | |
| 694 TEST(DiskCacheIndexTable, SaveIndex) { | |
| 695 TestCacheTables cache(1024); | |
| 696 IndexTableInitData init_data; | |
| 697 cache.GetInitData(&init_data); | |
| 698 MockIndexBackend backend; | |
| 699 | |
| 700 IndexTable index(&backend); | |
| 701 index.Init(&init_data); | |
| 702 | |
| 703 uint32_t hash = 0; | |
| 704 disk_cache::Addr addr(disk_cache::BLOCK_ENTRIES, 1, 5, 6); | |
| 705 EntryCell entry = index.CreateEntryCell(hash, addr); | |
| 706 EXPECT_TRUE(entry.IsValid()); | |
| 707 | |
| 708 index.OnBackupTimer(); | |
| 709 int expected = (1024 + 512) / 8 + sizeof(disk_cache::IndexHeaderV3); | |
| 710 EXPECT_EQ(expected, backend.buffer_len()); | |
| 711 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1910023002:
Remove partial blockfile v3 disk_cache implementation. (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master