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
12using disk_cache::EntryCell;
13using disk_cache::IndexCell;
14using disk_cache::IndexTable;
15using disk_cache::IndexTableInitData;
16
17namespace {
18
19int 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
30class 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
50class 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
71TestCacheTables::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
103void 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
119void 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
148TEST(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.
208TEST(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
266TEST(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.
328TEST(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
419TEST(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.
463TEST(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.
575TEST(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.
616TEST(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.
668TEST(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
689TEST(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