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 uint32 kMaxAddress = 1 << 22;
+
+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;
+
+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;
+}
+
+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.ToIndexEntryAddress() < 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;
+}
+
+void UpdateListWithCell(int bucket_hash,
+                        const disk_cache::EntryCell& cell,
+                        CellList* list,
+                        int* list_time) {
+  if (!list)
+    return;
+
+  int time = cell.GetTimestamp();
+  if (time < *list_time) {
+    *list_time = time;
+    list->clear();
+  }
+  if (time == *list_time) {
+    CellInfo cell_info = { cell.hash(), cell.GetAddress() };
+    list->push_back(cell_info);
+  }
+}
+
+}  // namespace
+
+namespace disk_cache {
+
+EntryCell::~EntryCell() {
+}
+
+bool EntryCell::IsValid() const {
+  return GetCellAddress(cell_) != 0;
+}
+
+Addr EntryCell::GetAddress() const {
+  uint32 address_value = GetAddressValue();
+  if (small_table_) {
+    if (GetGroup() == ENTRY_EVICTED)
+      return Addr(BLOCK_EVICTED, 1, kEvictedEntriesFile, address_value);
+
+    return Addr(BLOCK_ENTRIES, 1, kEntriesFile, address_value);
+  }
+
+  if (GetGroup() == ENTRY_EVICTED)
+    return Addr::FromEvictedAddress(address_value);
+  else
+    return Addr::FromEntryAddress(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 {
+    SetCellAddress(&cell_, address.ToIndexEntryAddress());
+    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 {
+  memcpy(destination, &cell_, sizeof(cell_));

[Randy Smith (Not in Mondays), 2013/11/05 21:58:21]

nit: Why not assignment?  It would seem simpler.

[rvargas (doing something else), 2013/11/05 22:29:12]

no reason

+}
+
+EntrySet::EntrySet() : evicted_count(0), current(0) {
+}
+
+// -----------------------------------------------------------------------
+
+IndexTable::IndexTable(IndexTableBackend* backend)
+    : backend_(backend),
+      header_(NULL),
+      main_table_(NULL),
+      extra_table_(NULL),
+      modified_(false),
+      small_table_(false) {
+}
+
+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_) {

[Randy Smith (Not in Mondays), 2013/11/05 21:58:21]

What's the difference between this case and |growing == true|?  The bits
comparison makes it look like we're confirming that we've just bumped up the
number of bits in the table by one, i.e. that we're growing.  And this function
is the only place we set either main_table_ or header_.  So it would seem that
this is only different from |growing == true| if params was first passed with a
null main_table_.  When can that happen/what does it mean?

[rvargas (doing something else), 2013/11/05 22:29:12]

There are two cases for increasing the size:
- We could be doubling the size of the table (which means changing the mask_
etc)
- We are not extending the main table, just adding more entries to the extra
table.

For example, we can have a 64k main table with maybe 8k entries on the extra
table (max 72k), and we just decided to add another 8k at the end (grow to 80k).
At some point, when we get close to 128k, we double the main table and reset to
a small extra table.

So, |growing| is true every time after the original initialization... but a
main_table will only be passed in when doubling it.

(I'll add a comment with this)

+      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);
+      old_extra_table.reset(new  IndexBucket[extra_size]);

[Randy Smith (Not in Mondays), 2013/11/05 21:58:21]

nit: double whitespace.

[rvargas (doing something else), 2013/11/05 22:29:12]

Done.

+      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_ = base::bits::Log2Floor(header_->table_len) -
+                base::bits::Log2Floor(kBaseTableLen);
+  DCHECK_GE(extra_bits_, 0);
+  DCHECK_LE(extra_bits_, 11);
+  mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1;
+  small_table_ = extra_bits_ < kHashShift - kHashSmallTableShift;
+  if (!small_table_)
+    extra_bits_ -= kHashShift - kHashSmallTableShift;
+
+  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 extra table.
+    int main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32;
+    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);
+    int old_num_words = (backup_header_.get()->table_len + 31) / 32;
+    DCHECK_GT(old_num_words, main_table_bit_words);
+    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);
+    backup_header_->table_len = header_->table_len;
+  } else {
+    backup_bitmap_storage_.reset(params->backup_bitmap.release());
+    backup_header_.reset(params->backup_header.release());
+  }
+
+  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;
+}
+
+EntrySet IndexTable::LookupEntry(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;
+  }
+  return entries;
+}
+
+EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) {
+  DCHECK(IsValidAddress(address));
+  DCHECK(address.ToIndexEntryAddress());
+
+  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;) {
+    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);
+}
+
+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)
+    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);
+  else if (state == ENTRY_USED)
+    DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN);
+
+  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(CellList* no_use, CellList* low_use,
+                           CellList* 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;
+
+  int no_use_time = kint32max;
+  int low_use_time = kint32max;
+  int high_use_time = kint32max;
+  for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
+    int bucket_id = i;
+    IndexBucket* bucket = &main_table_[i];
+    for (;;) {
+      GetOldestFromBucket(bucket, i, no_use, &no_use_time, low_use,
+                          &low_use_time, high_use, &high_use_time);
+
+      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;
+}
+
+bool IndexTable::GetNextCells(IndexIterator* iterator) {
+  int current_time = iterator->timestamp;
+  iterator->cells.clear();
+  iterator->timestamp = iterator->forward ? kint32max : 0;
+
+  for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
+    int bucket_id = i;
+    IndexBucket* bucket = &main_table_[i];
+    for (;;) {
+      GetNewestFromBucket(bucket, i, current_time, iterator);
+
+      bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,

[Randy Smith (Not in Mondays), 2013/11/07 20:25:15]

It took me a bit of time to figure out why the iteration was being done this
way, rather than just hammering through all the buckets in the index.  So I
think there could usefully be a comment somewhere in this file outlining the
algorithm for iterating through the index, given that that algorithm is used in
several places in the file.  (I thought about suggesting we try to abstract that
algorithm in some fashion, but I couldn't come up with anything that didn't
involve function pointers/callbacks, which didn't strike me as worth it).  

[rvargas (doing something else), 2013/11/08 04:22:30]

What do you mean by hammering through all the buckets? I think we are hammering
through all the buckets :). It's just that the structure of the table implies
that to locate something on the extra table one has to start on a given bucket
on the main table. So we could ignore the extra buckets when looking at the main
table, but we really cannot ignore the main table when looking at the extra
table. Is that what you mean?
I think I went through that same phase at some point, but the conclusion was the
same: attempting to generalize the code was not worth it / would just complicate
things.

[Randy Smith (Not in Mondays), 2013/11/11 20:54:54]

Well, what I meant was |for (int i = 0; i < header()->max_bucket(); i++))| and
removing the call to GetNextBucket().  But I think that was based on an
incorrect understanding of the layout (i.e. that everything was contiguous in
main_table_; I hadn't put together the passing of extra_table_ with how
GetNextBucket() works).  Ooops.  Ok, let me reflect back what I now think is
going on:
* main_table_ points to a table of size mask_ + 1.  That grows by doubling only.
* extra_table_ points to growth in the table when we don't need enough extra
entries to double the main table.  This is "easier" growth, since it just means
extending the extra_table file, and everything else (other than the size of that
file/table) stays unaltered.  There's a bit of a change when we switch pointers
from the old mapping of the extra table file to the new mapping, but because
they map the same file, it's fine for them to both be active for a bit.
* All bucket chains start in the main table, but all buckets except the first in
any chain will be in the extra table.
Based on my new understanding I'll modify my thought (not even a suggestion;
just the alternative algorithm I went through in getting to my current
understanding).  Could we write the above loop as?:

for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) 
  GetNewestFromBucket(&main_table_[i], i, current_time, iterator);

for (int i = static_cast<int32>(mask_ + 1); i < header()->max_bucket; i++) {
  IndexBucket* bucket = &extra_table_[i - static_cast<int32>(mask_ + 1)];
  GetNewestFromBucket(bucket, bucket->hash, current_time, iterator);
}

??  Not saying we should, just trying to make sure I understand the data
structure format.
Makes sense.  However, if I'm struggling as much as I am with getting solidly on
top of the iteration method and it's rationale, I'd like to have a comment
somewhere that sketches those two things out.  Is there such a comment?  If not,
would you be willing to put one in?

[rvargas (doing something else), 2013/11/12 00:24:04]

Correct
Correct
Will do.

+                                &bucket);
+      if (!bucket_id)
+        break;
+    }
+  }
+  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;
+  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::GetOldestFromBucket(IndexBucket* bucket, int bucket_hash,
+                                     CellList* no_use, int* no_use_time,
+                                     CellList* low_use, int* low_use_time,
+                                     CellList* high_use, int* high_use_time) {
+  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;
+
+    int time = GetCellTimestamp(current_cell);

[Randy Smith (Not in Mondays), 2013/11/05 21:58:21]

nit: This value doesn't seem like it's used?

[rvargas (doing something else), 2013/11/05 22:29:12]

Done.

+    EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
+                         current_cell, small_table_);
+    switch (GetCellGroup(current_cell)) {
+      case ENTRY_NO_USE:
+        UpdateListWithCell(bucket_hash, entry_cell, no_use, no_use_time);
+        header_->num_no_use_entries++;
+        break;
+      case ENTRY_LOW_USE:
+        UpdateListWithCell(bucket_hash, entry_cell, low_use, low_use_time);
+        header_->num_low_use_entries++;
+        break;
+      case ENTRY_HIGH_USE:
+        UpdateListWithCell(bucket_hash, entry_cell, high_use, high_use_time);
+        header_->num_high_use_entries++;
+        break;
+      case ENTRY_EVICTED:
+        header_->num_evicted_entries++;
+        break;
+      default:
+        NOTREACHED();
+    }
+  }
+}
+
+void IndexTable::GetNewestFromBucket(IndexBucket* bucket,
+                                     int bucket_hash,
+                                     int limit_time,
+                                     IndexIterator* iterator) {
+  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;
+
+    int time = GetCellTimestamp(current_cell);
+    switch (GetCellGroup(current_cell)) {
+      case disk_cache::ENTRY_NO_USE:
+      case disk_cache::ENTRY_LOW_USE:
+      case disk_cache::ENTRY_HIGH_USE:
+        if (iterator->forward && time <= limit_time)
+          continue;
+        if (!iterator->forward && time >= limit_time)
+          continue;
+
+        if ((iterator->forward && time < iterator->timestamp) ||
+            (!iterator->forward && time > iterator->timestamp)) {
+          iterator->timestamp = time;
+          iterator->cells.clear();
+        }
+        if (time == iterator->timestamp) {
+          EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
+                               current_cell, small_table_);
+          CellInfo cell_info = {
+            entry_cell.hash(),
+            entry_cell.GetAddress()
+          };
+          iterator->cells.push_back(cell_info);
+        }
+    }
+  }
+}
+
+void IndexTable::MoveCells(IndexBucket* old_extra_table) {
+  int max_hash = (mask_ + 1) / 2;
+  int max_bucket = header()->max_bucket;
+  header()->max_bucket = mask_;
+  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;
+    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