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 "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   ~MockIndexBackend() override {}
  34
  35   bool grow_called() const { return grow_called_; }
  36   int buffer_len() const { return buffer_len_; }
  37
  38   void GrowIndex() override { grow_called_ = true; }
  39   void SaveIndex(net::IOBuffer* buffer, int buffer_len) override {
  40     buffer_len_ = buffer_len;
  41   }
  42   void DeleteCell(EntryCell cell) override {}
  43   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 }