Disk cache v3: The main index table.

net/disk_cache/v3/index_table.cc

+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/disk_cache/v3/index_table.h"
+
+#include <algorithm>
+#include <set>
+#include <utility>
+
+#include "base/bits.h"
+#include "net/base/io_buffer.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/disk_cache.h"
+
+using base::Time;
+using base::TimeDelta;
+using disk_cache::CellInfo;
+using disk_cache::CellList;
+using disk_cache::IndexCell;
+using disk_cache::IndexIterator;
+
+namespace {
+
+const int kCellHashOffset = 22;
+const int kCellSmallTableHashOffset = 16;
+const int kCellTimestampOffset = 40;
+const int kCellReuseOffset = 60;
+const int kCellGroupOffset = 3;
+const int kCellSumOffset = 6;
+
+const uint64 kCellAddressMask = 0x3FFFFF;
+const uint64 kCellSmallTableAddressMask = 0xFFFF;
+const uint64 kCellHashMask = 0x3FFFF;
+const uint64 kCellSmallTableHashMask = 0xFFFFFF;
+const uint64 kCellTimestampMask = 0xFFFFF;
+const uint64 kCellReuseMask = 0xF;
+const uint8 kCellStateMask = 0x7;
+const uint8 kCellGroupMask = 0x7;
+const uint8 kCellSumMask = 0x3;
+
+const int kHashShift = 14;
+const int kHashSmallTableShift = 8;
+
+// Unfortunately we have to break the abstaction a little here: the file number
+// where entries are stored is outside of the control of this code, and it is
+// usually part of the stored address. However, for small tables we only store
+// 16 bits of the address so the file number is never stored on a cell. We have
+// to infere the file number from the type of entry (normal vs evicted), and
+// the knowledge that given that the table will not keep more than 64k entries,
+// a single file of each type is enough.
+const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1;
+const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1;
+const int kMaxAddress = 1 << 22;
+const int kMinFileNumber = 1 << 16;
+
+uint32 GetCellAddress(const IndexCell& cell) {
+  return cell.first_part & kCellAddressMask;
+}
+
+uint32 GetCellSmallTableAddress(const IndexCell& cell) {
+  return cell.first_part & kCellSmallTableAddressMask;
+}
+
+uint32 GetCellHash(const IndexCell& cell) {
+  return (cell.first_part >> kCellHashOffset) & kCellHashMask;
+}
+
+uint32 GetCellSmallTableHash(const IndexCell& cell) {
+  return (cell.first_part >> kCellSmallTableHashOffset) &
+         kCellSmallTableHashMask;
+}
+
+int GetCellTimestamp(const IndexCell& cell) {
+  return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask;
+}
+
+int GetCellReuse(const IndexCell& cell) {
+  return (cell.first_part >> kCellReuseOffset) & kCellReuseMask;
+}
+
+int GetCellState(const IndexCell& cell) {
+  return cell.last_part & kCellStateMask;
+}
+
+int GetCellGroup(const IndexCell& cell) {
+  return (cell.last_part >> kCellGroupOffset) & kCellGroupMask;
+}
+
+int GetCellSum(const IndexCell& cell) {
+  return (cell.last_part >> kCellSumOffset) & kCellSumMask;
+}
+
+void SetCellAddress(IndexCell* cell, uint32 address) {
+  DCHECK_LE(address, static_cast<uint32>(kCellAddressMask));
+  cell->first_part &= ~kCellAddressMask;
+  cell->first_part |= address;
+}
+
+void SetCellSmallTableAddress(IndexCell* cell, uint32 address) {
+  DCHECK_LE(address, static_cast<uint32>(kCellSmallTableAddressMask));
+  cell->first_part &= ~kCellSmallTableAddressMask;
+  cell->first_part |= address;
+}
+
+void SetCellHash(IndexCell* cell, uint32 hash) {
+  DCHECK_LE(hash, static_cast<uint32>(kCellHashMask));
+  cell->first_part &= ~(kCellHashMask << kCellHashOffset);
+  cell->first_part |= static_cast<int64>(hash) << kCellHashOffset;
+}
+
+void SetCellSmallTableHash(IndexCell* cell, uint32 hash) {
+  DCHECK_LE(hash, static_cast<uint32>(kCellSmallTableHashMask));
+  cell->first_part &= ~(kCellSmallTableHashMask << kCellSmallTableHashOffset);
+  cell->first_part |= static_cast<int64>(hash) << kCellSmallTableHashOffset;
+}
+
+void SetCellTimestamp(IndexCell* cell, int timestamp) {
+  DCHECK_LT(timestamp, 1 << 20);
+  DCHECK_GE(timestamp, 0);
+  cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset);
+  cell->first_part |= static_cast<int64>(timestamp) << kCellTimestampOffset;
+}
+
+void SetCellReuse(IndexCell* cell, int count) {
+  DCHECK_LT(count, 16);
+  DCHECK_GE(count, 0);
+  cell->first_part &= ~(kCellReuseMask << kCellReuseOffset);
+  cell->first_part |= static_cast<int64>(count) << kCellReuseOffset;
+}
+
+void SetCellState(IndexCell* cell, disk_cache::EntryState state) {
+  cell->last_part &= ~kCellStateMask;
+  cell->last_part |= state;
+}
+
+void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) {
+  cell->last_part &= ~(kCellGroupMask << kCellGroupOffset);
+  cell->last_part |= group << kCellGroupOffset;
+}
+
+void SetCellSum(IndexCell* cell, int sum) {
+  DCHECK_LT(sum, 4);
+  DCHECK_GE(sum, 0);
+  cell->last_part &= ~(kCellSumMask << kCellSumOffset);
+  cell->last_part |= sum << kCellSumOffset;
+}
+
+// This is a very particular way to calculate the sum, so it will not match if
+// compared a gainst a pure 2 bit, modulo 2 sum.
+int CalculateCellSum(const IndexCell& cell) {
+  uint32* words = bit_cast<uint32*>(&cell);
+  uint8* bytes = bit_cast<uint8*>(&cell);
+  uint32 result = words[0] + words[1];
+  result += result >> 16;
+  result += (result >> 8) + (bytes[8] & 0x3f);
+  result += result >> 4;
+  result += result >> 2;
+  return result & 3;
+}
+
+bool SanityCheck(const IndexCell& cell) {
+  if (GetCellSum(cell) != CalculateCellSum(cell))
+    return false;
+
+  if (GetCellState(cell) > disk_cache::ENTRY_USED ||
+      GetCellGroup(cell) == disk_cache::ENTRY_RESERVED ||
+      GetCellGroup(cell) > disk_cache::ENTRY_EVICTED) {
+    return false;
+  }
+
+  return true;
+}
+
+int FileNumberFromAddress(int index_address) {
+  return index_address / kMinFileNumber;
+}
+
+int StartBlockFromAddress(int index_address) {
+  return index_address % kMinFileNumber;
+}
+
+bool IsValidAddress(disk_cache::Addr address) {
+  if (!address.is_initialized() ||
+      (address.file_type() != disk_cache::BLOCK_EVICTED &&
+       address.file_type() != disk_cache::BLOCK_ENTRIES)) {
+    return false;
+  }
+
+  return address.FileNumber() < FileNumberFromAddress(kMaxAddress);
+}
+
+bool IsNormalState(const IndexCell& cell) {
+  disk_cache::EntryState state =
+      static_cast<disk_cache::EntryState>(GetCellState(cell));
+  DCHECK_NE(state, disk_cache::ENTRY_FREE);
+  return state != disk_cache::ENTRY_DELETED &&
+         state != disk_cache::ENTRY_FIXING;
+}
+
+inline int GetNextBucket(int min_bucket_id, int max_bucket_id,
+                          disk_cache::IndexBucket* table,
+                          disk_cache::IndexBucket** bucket) {
+  if (!(*bucket)->next)
+    return 0;
+
+  int bucket_id = (*bucket)->next / disk_cache::kCellsPerBucket;
+  if (bucket_id < min_bucket_id || bucket_id > max_bucket_id) {
+    (*bucket)->next = 0;
+    return 0;
+  }
+  *bucket = &table[bucket_id - min_bucket_id];
+  return bucket_id;
+}
+
+// Updates the |iterator| with the current |cell|. This cell may cause all
+// previous cells to be deleted (when a new target timestamp is found), the cell
+// may be added to the list (if it matches the target timestamp), or may it be
+// ignored.
+void UpdateIterator(const disk_cache::EntryCell& cell,
+                    int limit_time,
+                    IndexIterator* iterator) {
+  int time = cell.GetTimestamp();
+  // Look for not interesting times.
+  if (iterator->forward && time <= limit_time)
+    return;
+  if (!iterator->forward && time >= limit_time)
+    return;
+
+  if ((iterator->forward && time < iterator->timestamp) ||
+      (!iterator->forward && time > iterator->timestamp)) {
+    // This timestamp is better than the one we had.
+    iterator->timestamp = time;
+    iterator->cells.clear();
+  }
+  if (time == iterator->timestamp) {
+    CellInfo cell_info = { cell.hash(), cell.GetAddress() };
+    iterator->cells.push_back(cell_info);
+  }
+}
+
+void InitIterator(IndexIterator* iterator) {
+  iterator->cells.clear();
+  iterator->timestamp = iterator->forward ? kint32max : 0;
+}
+
+}  // namespace
+
+namespace disk_cache {
+
+EntryCell::~EntryCell() {
+}
+
+bool EntryCell::IsValid() const {
+  return GetCellAddress(cell_) != 0;
+}
+
+// This code has to map the cell address (up to 22 bits) to a general cache Addr
+// (up to 24 bits of general addressing). It also set the implied file_number
+// in the case of small tables. See also the comment by the definition of
+// kEntriesFile.
+Addr EntryCell::GetAddress() const {
+  uint32 address_value = GetAddressValue();
+  int file_number = FileNumberFromAddress(address_value);
+  if (small_table_) {
+    DCHECK_EQ(0, file_number);
+    file_number = (GetGroup() == ENTRY_EVICTED) ? kEvictedEntriesFile :
+                                                  kEntriesFile;
+  }
+  DCHECK_NE(0, file_number);
+  FileType file_type = (GetGroup() == ENTRY_EVICTED) ? BLOCK_EVICTED :
+                                                       BLOCK_ENTRIES;
+  return Addr(file_type, 1, file_number, StartBlockFromAddress(address_value));
+}
+
+EntryState EntryCell::GetState() const {
+  return static_cast<EntryState>(cell_.last_part & kCellStateMask);
+}
+
+EntryGroup EntryCell::GetGroup() const {
+  return static_cast<EntryGroup>((cell_.last_part >> kCellGroupOffset) &
+                                 kCellGroupMask);
+}
+
+int EntryCell::GetReuse() const {
+  return (cell_.first_part >> kCellReuseOffset) & kCellReuseMask;
+}
+
+int EntryCell::GetTimestamp() const {
+  return GetCellTimestamp(cell_);
+}
+
+void EntryCell::SetState(EntryState state) {
+  SetCellState(&cell_, state);
+}
+
+void EntryCell::SetGroup(EntryGroup group) {
+  SetCellGroup(&cell_, group);
+}
+
+void EntryCell::SetReuse(int count) {
+  SetCellReuse(&cell_, count);
+}
+
+void EntryCell::SetTimestamp(int timestamp) {
+  SetCellTimestamp(&cell_, timestamp);
+}
+
+// Static.
+EntryCell EntryCell::GetEntryCellForTest(int32 cell_id,
+                                         uint32 hash,
+                                         Addr address,
+                                         IndexCell* cell,
+                                         bool small_table) {
+  if (cell) {
+    EntryCell entry_cell(cell_id, hash, *cell, small_table);
+    return entry_cell;
+  }
+
+  return EntryCell(cell_id, hash, address, small_table);
+}
+
+void EntryCell::SerializaForTest(IndexCell* destination) {
+  FixSum();
+  Serialize(destination);
+}
+
+EntryCell::EntryCell() : cell_id_(0), hash_(0), small_table_(false) {
+  cell_.Clear();
+}
+
+EntryCell::EntryCell(int32 cell_id, uint32 hash, Addr address, bool small_table)
+    : cell_id_(cell_id),
+      hash_(hash),
+      small_table_(small_table) {
+  DCHECK(IsValidAddress(address) || !address.value());
+
+  cell_.Clear();
+  SetCellState(&cell_, ENTRY_NEW);
+  SetCellGroup(&cell_, ENTRY_NO_USE);
+  if (small_table) {
+    DCHECK(address.FileNumber() == kEntriesFile ||
+           address.FileNumber() == kEvictedEntriesFile);
+    SetCellSmallTableAddress(&cell_, address.start_block());
+    SetCellSmallTableHash(&cell_, hash >> kHashSmallTableShift);
+  } else {
+    uint32 cell_address = address.FileNumber() << 16 | address.start_block();
+    SetCellAddress(&cell_, cell_address);
+    SetCellHash(&cell_, hash >> kHashShift);
+  }
+}
+
+EntryCell::EntryCell(int32 cell_id,
+                     uint32 hash,
+                     const IndexCell& cell,
+                     bool small_table)
+    : cell_id_(cell_id),
+      hash_(hash),
+      cell_(cell),
+      small_table_(small_table) {
+}
+
+void EntryCell::FixSum() {
+  SetCellSum(&cell_, CalculateCellSum(cell_));
+}
+
+uint32 EntryCell::GetAddressValue() const {
+  if (small_table_)
+    return GetCellSmallTableAddress(cell_);
+
+  return GetCellAddress(cell_);
+}
+
+uint32 EntryCell::RecomputeHash() {
+  if (small_table_) {
+    hash_ &= (1 << kHashSmallTableShift) - 1;
+    hash_ |= GetCellSmallTableHash(cell_) << kHashSmallTableShift;
+    return hash_;
+  }
+
+  hash_ &= (1 << kHashShift) - 1;
+  hash_ |= GetCellHash(cell_) << kHashShift;
+  return hash_;
+}
+
+void EntryCell::Serialize(IndexCell* destination) const {
+  *destination = cell_;
+}
+
+EntrySet::EntrySet() : evicted_count(0), current(0) {
+}
+
+EntrySet::~EntrySet() {
+}
+
+IndexIterator::IndexIterator() {
+}
+
+IndexIterator::~IndexIterator() {
+}
+
+IndexTableInitData::IndexTableInitData() {
+}
+
+IndexTableInitData::~IndexTableInitData() {
+}
+
+// -----------------------------------------------------------------------
+
+IndexTable::IndexTable(IndexTableBackend* backend)
+    : backend_(backend),
+      header_(NULL),
+      main_table_(NULL),
+      extra_table_(NULL),
+      modified_(false),
+      small_table_(false) {
+}
+
+IndexTable::~IndexTable() {
+}
+
+// For a general description of the index tables see:
+// http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Index
+//
+// The index is split between two tables: the main_table_ and the extra_table_.
+// The main table can grow only by doubling its number of cells, while the
+// extra table can grow slowly, because it only contain cells that overflow
+// from the main table. In order to locate a given cell, part of the hash is
+// used directly as an index into the main table; once that bucket is located,
+// all cells with that partial hash (i.e., belonging to that bucket) are
+// inspected, and if present, the next bucket (located on the extra table) is
+// then located. For more information on bucket chaining see:
+// http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Buckets
+//
+// There are two cases when increasing the size:
+//  - Doubling the size of the main table
+//  - Adding more entries to the extra table
+//
+// For example, consider a 64k main table with 8k cells on the extra table (for
+// a total of 72k cells). Init can be called to add another 8k cells at the end
+// (grow to 80k cells). When the size of the extra table approaches 64k, Init
+// can be called to double the main table (to 128k) and go back to a small extra
+// table.
+void IndexTable::Init(IndexTableInitData* params) {
+  bool growing = header_ != NULL;
+  scoped_ptr<IndexBucket[]> old_extra_table;
+  header_ = &params->index_bitmap->header;
+
+  if (params->main_table) {
+    if (main_table_) {
+      // This is doubling the size of main table.
+      DCHECK_EQ(base::bits::Log2Floor(header_->table_len),
+                base::bits::Log2Floor(backup_header_->table_len) + 1);
+      int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket;
+      DCHECK_GE(extra_size, 0);
+
+      // Doubling the size implies deleting the extra table and moving as many
+      // cells as we can to the main table, so we first copy the old one. This
+      // is not required when just growing the extra table because we don't
+      // move any cell in that case.
+      old_extra_table.reset(new IndexBucket[extra_size]);
+      memcpy(old_extra_table.get(), extra_table_,
+             extra_size * sizeof(IndexBucket));
+      memset(params->extra_table, 0, extra_size * sizeof(IndexBucket));
+    }
+    main_table_ = params->main_table;
+  }
+  DCHECK(main_table_);
+  extra_table_ = params->extra_table;
+
+  // extra_bits_ is really measured against table-size specific values.
+  const int kMaxAbsoluteExtraBits = 11;  // From smaller to largest table.
+  const int kMaxExtraBitsSmallTable = 6;
+
+  extra_bits_ = base::bits::Log2Floor(header_->table_len) -
+                base::bits::Log2Floor(kBaseTableLen);
+  DCHECK_GE(extra_bits_, 0);
+  DCHECK_LE(extra_bits_, kMaxAbsoluteExtraBits);
+  mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1;
+  small_table_ = extra_bits_ < kMaxExtraBitsSmallTable;
+  if (!small_table_)
+    extra_bits_ -= kMaxExtraBitsSmallTable;
+
+  // table_len keeps the max number of cells stored by the index. We need a
+  // bitmap with 1 bit per cell, and that bitmap has num_words 32-bit words.
+  int num_words = (header_->table_len + 31) / 32;
+
+  if (old_extra_table) {
+    // All the cells from the extra table are moving to the new tables so before
+    // creating the bitmaps, clear the part of the bitmap referring to the extra
+    // table.
+    int main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32;

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

This looks to be a factor of two off from the size of the new main table
(buckets indexed from 0..mask_, total num buckets = mask_+1, mask_>>1+1 = 1/2
the total number of buckets, multiply by cells per bucket gives you half the
total number of cells), by which I infer it refers to the old main table.  Maybe
change the variable name to old_main_table_bit_words and/or get it from the
backup_header_?

[rvargas (doing something else), 2013/12/04 01:04:17]

Done.

+    DCHECK_GT(num_words, main_table_bit_words);
+    memset(params->index_bitmap->bitmap + main_table_bit_words, 0,
+           (num_words - main_table_bit_words) * sizeof(int32));
+
+    DCHECK(growing);

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

Just confirming that this is redundant with if (old_extra_table) because we
can't be doubling the table if this is the first time Init() is called.  (Not
objecting, just trying to understand the failure mode being guarded against.)

[rvargas (doing something else), 2013/12/04 01:04:17]

correct. Protects against the first part of this function :)

+    int old_num_words = (backup_header_.get()->table_len + 31) / 32;
+    DCHECK_GT(old_num_words, main_table_bit_words);

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

Any reason this couldn't be equal?  (I.e. if we're doubling without having any
extra table in between).

[rvargas (doing something else), 2013/12/04 01:04:17]

An extra table is always required.

[Randy Smith (Not in Mondays), 2013/12/05 19:17:48]

Reasonable to have a DCHECK that we're getting an extra table, maybe with a
quick comment that we always need a little bit of space in the extra table?

[rvargas (doing something else), 2013/12/07 02:13:45]

Done.

+    memset(backup_bitmap_storage_.get() + main_table_bit_words, 0,
+           (old_num_words - main_table_bit_words) * sizeof(int32));
+  }
+  bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len,
+                           num_words));
+
+  if (growing) {
+    int old_num_words = (backup_header_.get()->table_len + 31) / 32;
+    DCHECK_GE(num_words, old_num_words);
+    scoped_ptr<uint32[]> storage(new uint32[num_words]);
+    memcpy(storage.get(), backup_bitmap_storage_.get(),
+           old_num_words * sizeof(int32));
+    memset(storage.get() + old_num_words, 0,
+           (num_words - old_num_words) * sizeof(int32));
+
+    backup_bitmap_storage_.swap(storage);

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

What failure is being guarded against by copying and swapping instead of editing
in place?

[rvargas (doing something else), 2013/12/04 01:04:17]

The bitmap itself is supposed to be growing so we need a bigger backup

+    backup_header_->table_len = header_->table_len;
+  } else {
+    backup_bitmap_storage_.reset(params->backup_bitmap.release());
+    backup_header_.reset(params->backup_header.release());

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

What's the context for these parameters?  They're only used on the first call to
Init(); are they defined on other calls?  And where do they come from on the
first call to Init()?  What do they contain?  It feels a bit weird to have this
function responsible for allocating storage on growing, but not on first
initialization.

[rvargas (doing something else), 2013/12/04 01:04:17]

There are dedicated files to store the backups. When the cache starts, those
files are read and the contents are provided to this method, so that we can
check the backup against the mmaped bitmap. When growing, there is no need to
read any file because the up to date version is already in memory, owned by this
object.

[Randy Smith (Not in Mondays), 2013/12/05 19:17:48]

So that means at some point in the future there will be code checking the backup
bitmaps against the current bitmaps on first load?

Also, what's the allocation behavior for params->backup_header and backup_bitmap
on calls to Init() after the first?  There's not a code correctness issue, but
it's sorta a shame if they keep getting allocated and then deleted without being
examined.

[rvargas (doing something else), 2013/12/07 02:13:45]

Checking against the backup is already in place. It is performed on demand by
CheckState()
The caller doesn't pass them. That would require reading the files, and that
doesn't happen for reinit.

[Randy Smith (Not in Mondays), 2013/12/26 21:45:49]

Clarifying comment, either on IndexTableInitData or Init()?  

(Side note: I've been on-and-off tempted reading this code to suggest that it be
pulled out into three separate functions for the three separate things that
could be happening: initialization, re-init without doubling (increase in the
extra table), and re-init with doubling, because as I've read the function I've
had to spend some mental energy tracking those three pathways and make sure each
is clean.  But I haven't been able to convince myself that the code would
actually be cleaner and more maintainable that way; it would involve a lot more
functions that each branch would call, and the obvious way to implement it would
be for Init() to branch when first entered, so I haven't brought it up.  I'm
just mentioning it now in case the various requests I'm making for comments to
help keep those three things straight are onerous enough that the alternative
has appeal :-}.)

[rvargas (doing something else), 2013/12/27 19:31:46]

Done.

+  }
+
+  num_words = (backup_header_->table_len + 31) / 32;
+  backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(),
+                                  backup_header_->table_len, num_words));
+  if (old_extra_table)
+    MoveCells(old_extra_table.get());
+
+  if (small_table_)
+    DCHECK(header_->flags & SMALL_CACHE);
+}
+
+void IndexTable::Reset() {
+  header_ = NULL;
+  main_table_ = NULL;
+  extra_table_ = NULL;
+  bitmap_.reset();
+  backup_bitmap_.reset();
+  backup_header_.reset();
+  backup_bitmap_storage_.reset();
+  modified_ = false;
+}
+
+// The general method for locating cells is to:
+// 1. Get the first bucket. This usually means directly indexing the table (as
+//     this method does), or iterating through all possible buckets.
+// 2. Iterate through all the cells in that first bucket.
+// 3. If there is a linked bucket, locate it directly in the extra table.
+// 4. Go back to 2, as needed.
+//
+// One consequence of this pattern is that we never start looking at buckets in
+// the extra table, unless we are following a link from the main table.
+EntrySet IndexTable::LookupEntries(uint32 hash) {
+  EntrySet entries;
+  int bucket_id = static_cast<int>(hash & mask_);
+  IndexBucket* bucket = &main_table_[bucket_id];
+  for (;;) {
+    for (int i = 0; i < kCellsPerBucket; i++) {
+      IndexCell* current_cell = &bucket->cells[i];
+      if (!GetAddressValue(*current_cell))
+        continue;
+      if (!SanityCheck(*current_cell)) {
+        NOTREACHED();
+        int cell_id = bucket_id * kCellsPerBucket + i;
+        current_cell->Clear();
+        bitmap_->Set(cell_id, false);
+        backup_bitmap_->Set(cell_id, false);
+        modified_ = true;
+        continue;
+      }
+      int cell_id = bucket_id * kCellsPerBucket + i;
+      if (MisplacedHash(*current_cell, hash)) {
+        HandleMisplacedCell(current_cell, cell_id, hash & mask_);
+      } else if (IsHashMatch(*current_cell, hash)) {
+        EntryCell entry_cell(cell_id, hash, *current_cell, small_table_);
+        CheckState(entry_cell);
+        if (entry_cell.GetState() != ENTRY_DELETED) {
+          entries.cells.push_back(entry_cell);
+          if (entry_cell.GetGroup() == ENTRY_EVICTED)
+            entries.evicted_count++;
+        }
+      }
+    }
+    bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
+                              &bucket);
+    if (!bucket_id)
+      break;

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

nit, suggestion: do { } while(bucket_id); would communicate this loop's purpose
to me a bit more clearly.

[rvargas (doing something else), 2013/12/04 01:04:17]

Done.

+  }
+  return entries;
+}
+
+EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) {
+  DCHECK(IsValidAddress(address));
+  DCHECK(address.FileNumber() || address.start_block());
+
+  int bucket_id = static_cast<int>(hash & mask_);
+  int cell_id = 0;
+  IndexBucket* bucket = &main_table_[bucket_id];
+  IndexCell* current_cell = NULL;
+  bool found = false;
+  for (; !found;) {

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

This looks redundant with the "if (found) break;" below; I don't think you need
both.  (My nit/suggestion above about do/while would also apply here  if you
liked it above.)

[rvargas (doing something else), 2013/12/04 01:04:17]

Done.

+    for (int i = 0; i < kCellsPerBucket && !found; i++) {
+      current_cell = &bucket->cells[i];
+      if (!GetAddressValue(*current_cell)) {
+        cell_id = bucket_id * kCellsPerBucket + i;
+        found = true;
+      }
+    }
+    if (found)
+      break;
+    bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
+                              &bucket);
+    if (!bucket_id)
+      break;
+  }
+
+  if (!found) {
+    bucket_id = NewExtraBucket();
+    if (bucket_id) {
+      cell_id = bucket_id * kCellsPerBucket;
+      bucket->next = cell_id;
+      bucket = &extra_table_[bucket_id - (mask_ + 1)];
+      bucket->hash = hash & mask_;
+      found = true;
+    } else {
+      // address 0 is a reserved value, and the caller interprets it as invalid.
+      address.set_value(0);
+    }
+  }
+
+  EntryCell entry_cell(cell_id, hash, address, small_table_);
+  if (address.file_type() == BLOCK_EVICTED)
+    entry_cell.SetGroup(ENTRY_EVICTED);
+  else
+    entry_cell.SetGroup(ENTRY_NO_USE);
+  Save(&entry_cell);
+
+  if (found) {
+    bitmap_->Set(cell_id, true);
+    backup_bitmap_->Set(cell_id, true);
+    header()->used_cells++;
+    modified_ = true;
+  }
+
+  return entry_cell;
+}
+
+EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) {
+  return FindEntryCellImpl(hash, address, false);
+}
+
+int IndexTable::CalculateTimestamp(Time time) {
+  TimeDelta delta = time - Time::FromInternalValue(header_->base_time);
+  return std::max(delta.InMinutes(), 0);
+}
+
+base::Time IndexTable::TimeFromTimestamp(int timestamp) {
+  return Time::FromInternalValue(header_->base_time) +
+         TimeDelta::FromMinutes(timestamp);
+}
+
+void IndexTable::SetSate(uint32 hash, Addr address, EntryState state) {
+  EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE);
+  if (!cell.IsValid()) {
+    NOTREACHED();
+    return;
+  }
+
+  EntryState old_state = cell.GetState();
+  if (state == ENTRY_FREE) {

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

Nit, suggestion: If this is a switch statement without a default: label, the
compiler will automatically warn if there isn't a label for each entry in the
enum.  I've found this a useful technique for making sure as code evolves that
all appropriate state conditionals are tested.

[rvargas (doing something else), 2013/12/04 01:04:17]

Done.

+    DCHECK_EQ(old_state, ENTRY_DELETED);
+  } else if (state == ENTRY_NEW) {
+    DCHECK_EQ(old_state, ENTRY_FREE);
+  } else if (state == ENTRY_OPEN) {
+    DCHECK_EQ(old_state, ENTRY_USED);
+  } else if (state == ENTRY_MODIFIED) {
+    DCHECK_EQ(old_state, ENTRY_OPEN);
+  } else if (state == ENTRY_DELETED) {
+    DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
+           old_state == ENTRY_MODIFIED);
+  } else if (state == ENTRY_USED) {
+    DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
+           old_state == ENTRY_MODIFIED);
+  }
+
+  modified_ = true;
+  if (state == ENTRY_DELETED) {
+    bitmap_->Set(cell.cell_id(), false);
+    backup_bitmap_->Set(cell.cell_id(), false);
+  } else if (state == ENTRY_FREE) {
+    cell.Clear();
+    Write(cell);
+    header()->used_cells--;
+    return;
+  }
+  cell.SetState(state);
+
+  Save(&cell);
+}
+
+void IndexTable::UpdateTime(uint32 hash, Addr address, base::Time current) {
+  EntryCell cell = FindEntryCell(hash, address);
+  if (!cell.IsValid())
+    return;
+
+  int minutes = CalculateTimestamp(current);
+
+  // Keep about 3 months of headroom.
+  const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90;
+  if (minutes > kMaxTimestamp) {
+    // TODO(rvargas):
+    // Update header->old_time and trigger a timer
+    // Rebaseline timestamps and don't update sums
+    // Start a timer (about 2 backups)
+    // fix all ckecksums and trigger another timer
+    // update header->old_time because rebaseline is done.
+    minutes = std::min(minutes, (1 << 20) - 1);
+  }
+
+  cell.SetTimestamp(minutes);
+  Save(&cell);
+}
+
+void IndexTable::Save(EntryCell* cell) {
+  cell->FixSum();
+  Write(*cell);
+}
+
+void IndexTable::GetOldest(IndexIterator* no_use,
+                           IndexIterator* low_use,
+                           IndexIterator* high_use) {
+  no_use->forward = true;
+  low_use->forward = true;
+  high_use->forward = true;
+  InitIterator(no_use);
+  InitIterator(low_use);
+  InitIterator(high_use);
+
+  WalkTables(-1, no_use, low_use, high_use);
+}
+
+bool IndexTable::GetNextCells(IndexIterator* iterator) {
+  int current_time = iterator->timestamp;
+  InitIterator(iterator);
+
+  WalkTables(current_time, iterator, iterator, iterator);
+  return !iterator->cells.empty();
+}
+
+void IndexTable::OnBackupTimer() {
+  if (!modified_)
+    return;
+
+  int num_words = (header_->table_len + 31) / 32;
+  int num_bytes = num_words * 4 + static_cast<int>(sizeof(*header_));
+  scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes));
+  memcpy(buffer->data(), header_, sizeof(*header_));
+  memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(),
+         num_words * 4);
+  backend_->SaveIndex(buffer, num_bytes);
+  modified_ = false;
+}
+
+// -----------------------------------------------------------------------
+
+EntryCell IndexTable::FindEntryCellImpl(uint32 hash, Addr address,
+                                        bool allow_deleted) {
+  int bucket_id = static_cast<int>(hash & mask_);
+  IndexBucket* bucket = &main_table_[bucket_id];
+  for (;;) {
+    for (int i = 0; i < kCellsPerBucket; i++) {
+      IndexCell* current_cell = &bucket->cells[i];
+      if (!GetAddressValue(*current_cell))
+        continue;
+      DCHECK(SanityCheck(*current_cell));
+      if (IsHashMatch(*current_cell, hash)) {
+        // We have a match.
+        int cell_id = bucket_id * kCellsPerBucket + i;
+        EntryCell entry_cell(cell_id, hash, *current_cell, small_table_);
+        if (entry_cell.GetAddress() != address)
+          continue;
+
+        if (!allow_deleted && entry_cell.GetState() == ENTRY_DELETED)
+          continue;
+
+        return entry_cell;
+      }
+    }
+    bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
+                              &bucket);
+    if (!bucket_id)
+      break;
+  }
+  return EntryCell();
+}
+
+void IndexTable::CheckState(const EntryCell& cell) {
+  int current_state = cell.GetState();
+  if (current_state != ENTRY_FIXING) {
+    bool present = ((current_state & 3) != 0);  // Look at the last two bits.
+    if (present != bitmap_->Get(cell.cell_id()) ||
+        present != backup_bitmap_->Get(cell.cell_id())) {
+      // There's a mismatch.
+      if (current_state == ENTRY_DELETED) {
+        // We were in the process of deleting this entry. Finish now.
+        backend_->DeleteCell(cell);
+      } else {
+        current_state = ENTRY_FIXING;
+        EntryCell bad_cell(cell);
+        bad_cell.SetState(ENTRY_FIXING);
+        Save(&bad_cell);
+      }
+    }
+  }
+
+  if (current_state == ENTRY_FIXING)
+    backend_->FixCell(cell);
+}
+
+void IndexTable::Write(const EntryCell& cell) {
+  IndexBucket* bucket = NULL;
+  int bucket_id = cell.cell_id() / kCellsPerBucket;
+  if (bucket_id < static_cast<int32>(mask_ + 1)) {
+    bucket = &main_table_[bucket_id];
+  } else {
+    DCHECK_LE(bucket_id, header()->max_bucket);
+    bucket = &extra_table_[bucket_id - (mask_ + 1)];
+  }
+
+  int cell_number = cell.cell_id() % kCellsPerBucket;
+  if (GetAddressValue(bucket->cells[cell_number]) && cell.GetAddressValue()) {
+    DCHECK_EQ(cell.GetAddressValue(),
+              GetAddressValue(bucket->cells[cell_number]));
+  }
+  cell.Serialize(&bucket->cells[cell_number]);
+}
+
+int IndexTable::NewExtraBucket() {
+  int safe_window = (header()->table_len < kNumExtraBlocks * 2) ?
+                    kNumExtraBlocks / 4 : kNumExtraBlocks;

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

What is kNumExtraBlocks?  I didn't see any comment at the definition site, and
it's only used there and here.  Any rational for the /4 or =, or is that
arbitrary?

[rvargas (doing something else), 2013/12/04 01:04:17]

Completely arbitrary (well, /4 is tied to *2). kNumExtraBlocks is just how many
extra blocks should be allocated each time the extra table grows. So this says,
for tables larger than 2048, add 256 bloacks each time. Otherwise, add 1024
blocks.

So this means the tables total size goes 1024 - 1024+256 - 1024+512 - 1024+768 -
2048 - 3072 - 4096... or something like that (because extra doesn't really start
at 0)

btw, kNumExtraBlocks also directs how slowly each block file grows.

+  if (header()->table_len - header()->max_bucket * kCellsPerBucket <
+      safe_window) {
+    backend_->GrowIndex();
+  }
+
+  if (header()->max_bucket * kCellsPerBucket ==
+      header()->table_len - kCellsPerBucket) {
+    return 0;
+  }
+
+  header()->max_bucket++;
+  return header()->max_bucket;
+}
+
+void IndexTable::WalkTables(int limit_time,
+                            IndexIterator* no_use,
+                            IndexIterator* low_use,
+                            IndexIterator* high_use) {
+  header_->num_no_use_entries = 0;
+  header_->num_low_use_entries = 0;
+  header_->num_high_use_entries = 0;
+  header_->num_evicted_entries = 0;
+
+  for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
+    int bucket_id = i;
+    IndexBucket* bucket = &main_table_[i];
+    for (;;) {
+      UpdateFromBucket(bucket, i, limit_time, no_use, low_use, high_use);
+
+      bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
+                                &bucket);
+      if (!bucket_id)
+        break;
+    }
+  }
+  header_->num_entries = header_->num_no_use_entries +
+                         header_->num_low_use_entries +
+                         header_->num_high_use_entries +
+                         header_->num_evicted_entries;
+  modified_ = true;
+}
+
+void IndexTable::UpdateFromBucket(IndexBucket* bucket, int bucket_hash,
+                                  int limit_time,
+                                  IndexIterator* no_use,
+                                  IndexIterator* low_use,
+                                  IndexIterator* high_use) {
+  for (int i = 0; i < kCellsPerBucket; i++) {
+    IndexCell& current_cell = bucket->cells[i];
+    if (!GetAddressValue(current_cell))
+      continue;
+    DCHECK(SanityCheck(current_cell));
+    if (!IsNormalState(current_cell))
+      continue;
+
+    EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
+                         current_cell, small_table_);
+    switch (GetCellGroup(current_cell)) {
+      case ENTRY_NO_USE:
+        UpdateIterator(entry_cell, limit_time, no_use);
+        header_->num_no_use_entries++;
+        break;
+      case ENTRY_LOW_USE:
+        UpdateIterator(entry_cell, limit_time, low_use);
+        header_->num_low_use_entries++;
+        break;
+      case ENTRY_HIGH_USE:
+        UpdateIterator(entry_cell, limit_time, high_use);
+        header_->num_high_use_entries++;
+        break;
+      case ENTRY_EVICTED:
+        header_->num_evicted_entries++;
+        break;
+      default:
+        NOTREACHED();
+    }
+  }
+}
+
+void IndexTable::MoveCells(IndexBucket* old_extra_table) {
+  int max_hash = (mask_ + 1) / 2;
+  int max_bucket = header()->max_bucket;
+  header()->max_bucket = mask_;

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

nit: This seems like a strange place to do this assignment.  My assumption, when
I saw the call to MoveCells() in Init(), was that all it did was move the cells,
but this is a global state change.  To me, it would more naturally be paired
with the zeroing of extra_table; that's the point at which the extra_table
entries become unavailable to the normal lookup (to be made available again in
this routine as the cells are put in one at a time).

Also, it occurs to me reading this code: Where do we fix up the bucket chains
that are left dangling by folding the extra table into the main table on a
doubling?

[rvargas (doing something else), 2013/12/04 01:04:17]

Sort of. The state of this object is in flux while Init is running, and this
method only runs inside Init, so is not like the internal state should be
consistent when this method starts. This method receives a pointer to the extra
table because the core of Init is switching tables and bitmaps and clearing
buffers for this method. But it seems a little silly to clear a member in Init
only to pass its value as an explicit argument somewhere else that would be in
charge of setting the final value for the member. I mean, the final value of
max_bucket is only stable when MoveCells completes so it seemed better to
delegate all actions related to that field to this method. (as always, let me
know if you feel strongly about doing that on Init)
I don't follow the question. We take a chain one at a time and follow it to the
end, moving some entries from the main table and all entries from the extra
table (to the new extra table)

[Randy Smith (Not in Mondays), 2013/12/05 19:17:48]

Fair, though also tricky to realize for a code reader, since MoveCells() is
neither next to Init() nor commented to be only a subroutine of Init(). 
Explanatory comment?
So to be clear, the image in my mind was of setting header()->max_bucket =
mask_; in Init() after the call to MoveCells().  I don't see any dependencies on
header()->max_bucket in this routine, so I don't think any explicit arguments
would be required.  It might be worth a comment in Init() that "MoveCells()
depends on the pre-doubling values of header()->max_bucket", but what's really
true is that MoveCells() needs to be understood in the context of Init(); there
isn't a good interface contract between the two routines.
I don't care strongly; I think at base what I'm reacting to is that MoveCells()
doesn't make sense without knowing the particular point in Init() when it's
called (i.e. it's not particularly easy to define an interface contract).   But
I don't see a way to fix that; I do think pulling it out as a subroutine makes
sense just to keep Init() from being a very long function, but it only sorta
helps on the abstraction level.
I was wondering when the value of bucket->next was updated for the buckets in
the main table.  It looks to me as if the only two places where the next field
is set are in CreateEntryCell() and in GetNextBucket().  Naively, that would
seem to imply to me that after moving all the cells from the extra table to the
main table in MoveCells(), we've got pointers into invalid parts of the extra
table still dangling from the main table buckets.  If GetNextBucket() is called
on those buckets before any buckets are added to the extra table, that function
will fix/zero that pointer.  But if we add an extra bucket to the extra table
before calling GetNextBucket() on the main table bucket that used to point to
that extra table, we'll have an incorrect pointer into that bucket.  Am I
confused?

[rvargas (doing something else), 2013/12/07 02:13:45]

done
If I understand correctly, that would fail. The act of writing new cells into
the tables (and that happens when old cells are moved), changes max_bucket, as
that is just the last used cell from the extra table (or more exactly, the first
unused bucket). A write to the main table is fine, but any write to the extra
table may move max_bucket forward.
yeah, I added a comment on MoveCells; let me know if that's not enough.
Exactly. It is more a "now we need to sit down and move stuff, but we are not
really done with init"
That sounds correct (seems like there's a bug there).

[rvargas (doing something else), 2013/12/19 23:51:24]

There was actually no bug because the old value will point to the main table
(and not the extra table) so it will be ignored by GetNextBucket. I added a
comment and another unit test.

+  int used_cells = header()->used_cells;
+
+  // Consider a large cache: a cell stores the upper 18 bits of the hash
+  // (h >> 14). If the table is say 8 times the original size (growing from 4x),
+  // the bit that we are interested in would be the 3rd bit of the stored value,
+  // in other words 'multiplier' >> 1.
+  uint32 new_bit = (1 << extra_bits_) >> 1;
+
+  scoped_ptr<IndexBucket[]> old_main_table;
+  IndexBucket* source_table = main_table_;
+  bool upgrade_format = !extra_bits_;
+  if (upgrade_format) {
+    // This method should deal with migrating a small table to a big one. Given
+    // that the first thing to do is read the old table, set small_table_ for
+    // the size of the old table. Now, when moving a cell, the result cannot be
+    // placed in the old table or we will end up reading it again and attempting
+    // to move it, so we have to copy the whole table at once.
+    DCHECK(!small_table_);
+    small_table_ = true;
+    old_main_table.reset(new IndexBucket[max_hash]);
+    memcpy(old_main_table.get(), main_table_, max_hash * sizeof(IndexBucket));
+    memset(main_table_, 0, max_hash * sizeof(IndexBucket));
+    source_table = old_main_table.get();
+  }
+
+  for (int i = 0; i < max_hash; i++) {
+    int bucket_id = i;
+    IndexBucket* bucket = &source_table[i];
+    for (;;) {
+      for (int j = 0; j < kCellsPerBucket; j++) {
+        IndexCell& current_cell = bucket->cells[j];
+        if (!GetAddressValue(current_cell))
+          continue;
+        DCHECK(SanityCheck(current_cell));
+        if (bucket_id == i) {
+          if (upgrade_format || (GetHashValue(current_cell) & new_bit)) {
+            // Move this cell to the upper half of the table.
+            MoveSingleCell(&current_cell, bucket_id * kCellsPerBucket + j, i,
+                           true);
+          }
+        } else {
+          // All cells on extra buckets have to move.
+          MoveSingleCell(&current_cell, bucket_id * kCellsPerBucket + j, i,
+                         true);
+        }
+      }
+
+      bucket_id = GetNextBucket(max_hash, max_bucket, old_extra_table, &bucket);
+      if (!bucket_id)
+        break;
+    }
+  }
+
+  DCHECK_EQ(header()->used_cells, used_cells);
+
+  if (upgrade_format) {
+    small_table_ = false;
+    header()->flags &= ~SMALL_CACHE;
+  }
+}
+
+void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_id,
+                                int main_table_index, bool growing) {
+  uint32 hash = GetFullHash(*current_cell, main_table_index);
+  EntryCell old_cell(cell_id, hash, *current_cell, small_table_);
+
+  bool upgrade_format = !extra_bits_ && growing;
+  if (upgrade_format)
+    small_table_ = false;
+  EntryCell new_cell = CreateEntryCell(hash, old_cell.GetAddress());
+
+  if (!new_cell.IsValid()) {
+    // We'll deal with this entry later.
+    if (upgrade_format)
+      small_table_ = true;

[Randy Smith (Not in Mondays), 2013/12/02 21:48:06]

Willing to put a comment in here somewhere about why the flipping back and forth
of small_table_ over the course of this algorithm?

[rvargas (doing something else), 2013/12/04 01:04:17]

yeah, not so happy about having to do that. Added a comment.

[Randy Smith (Not in Mondays), 2013/12/05 19:17:48]

I'm not sure I like this suggestion, but: You could make the small/large table
distinction be based on the small_table_ variable in EntryCell, and pass that
bit directly to CreateEntryCell.  The minus of this, of course, is that it loses
an assertion opportunity that EntryCells and the table they are being saved into
have the same value.  You could (again not sure I like the suggestion, just
thinking it through) have small_table_ in IndexTable be a tri-state, with a
"transitioning" value, and only do the assertion when you aren't transitioning
(or assert as if its a large table on writing, but treat it like a small table
on reading, though I'm not 100% sure that would work).  Just a thought; up to
you what, if anything, you do with it.

[rvargas (doing something else), 2013/12/07 02:13:45]

thx

+    return;
+  }
+
+  new_cell.SetState(old_cell.GetState());
+  new_cell.SetGroup(old_cell.GetGroup());
+  new_cell.SetReuse(old_cell.GetReuse());
+  new_cell.SetTimestamp(old_cell.GetTimestamp());
+  Save(&new_cell);
+  modified_ = true;
+  if (upgrade_format)
+    small_table_ = true;
+
+  if (old_cell.GetState() == ENTRY_DELETED) {
+    bitmap_->Set(new_cell.cell_id(), false);
+    backup_bitmap_->Set(new_cell.cell_id(), false);
+  }
+
+  if (!growing || cell_id / kCellsPerBucket == main_table_index) {
+    // Only delete entries that live on the main table.
+    if (!upgrade_format) {
+      old_cell.Clear();
+      Write(old_cell);
+    }
+
+    if (cell_id != new_cell.cell_id()) {
+      bitmap_->Set(old_cell.cell_id(), false);
+      backup_bitmap_->Set(old_cell.cell_id(), false);
+    }
+  }
+  header()->used_cells--;
+}
+
+void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_id,
+                                     int main_table_index) {
+  // The cell may be misplaced, or a duplicate cell exists with this data.
+  uint32 hash = GetFullHash(*current_cell, main_table_index);
+  MoveSingleCell(current_cell, cell_id, main_table_index, false);
+
+  // Now look for a duplicate cell.
+  CheckBucketList(hash & mask_);
+}
+
+void IndexTable::CheckBucketList(int bucket_id) {
+  typedef std::pair<int, EntryGroup> AddressAndGroup;
+  std::set<AddressAndGroup> entries;
+  IndexBucket* bucket = &main_table_[bucket_id];
+  int bucket_hash = bucket_id;
+  for (;;) {
+    for (int i = 0; i < kCellsPerBucket; i++) {
+      IndexCell* current_cell = &bucket->cells[i];
+      if (!GetAddressValue(*current_cell))
+        continue;
+      if (!SanityCheck(*current_cell)) {
+        NOTREACHED();
+        current_cell->Clear();
+        continue;
+      }
+      int cell_id = bucket_id * kCellsPerBucket + i;
+      EntryCell cell(cell_id, GetFullHash(*current_cell, bucket_hash),
+                     *current_cell, small_table_);
+      if (!entries.insert(std::make_pair(cell.GetAddress().value(),
+                                         cell.GetGroup())).second) {
+        current_cell->Clear();
+        continue;
+      }
+      CheckState(cell);
+    }
+
+    bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
+                              &bucket);
+    if (!bucket_id)
+      break;
+  }
+}
+
+uint32 IndexTable::GetAddressValue(const IndexCell& cell) {
+  if (small_table_)
+    return GetCellSmallTableAddress(cell);
+
+  return GetCellAddress(cell);
+}
+
+uint32 IndexTable::GetHashValue(const IndexCell& cell) {
+  if (small_table_)
+    return GetCellSmallTableHash(cell);
+
+  return GetCellHash(cell);
+}
+
+uint32 IndexTable::GetFullHash(const IndexCell& cell, uint32 lower_part) {
+  // It is OK for the high order bits of lower_part to overlap with the stored
+  // part of the hash.
+  if (small_table_)
+    return (GetCellSmallTableHash(cell) << kHashSmallTableShift) | lower_part;
+
+  return (GetCellHash(cell) << kHashShift) | lower_part;
+}
+
+// All the bits stored in the cell should match the provided hash.
+bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) {
+  hash = small_table_ ? hash >> kHashSmallTableShift : hash >> kHashShift;
+  return GetHashValue(cell) == hash;
+}
+
+bool IndexTable::MisplacedHash(const IndexCell& cell, uint32 hash) {
+  if (!extra_bits_)
+    return false;
+
+  uint32 mask = (1 << extra_bits_) - 1;
+  hash = small_table_ ? hash >> kHashSmallTableShift : hash >> kHashShift;
+  return (GetHashValue(cell) & mask) != (hash & mask);
+}
+
+}  // namespace disk_cache