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