net/disk_cache/blockfile/index_table_v3_unittest.cc

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