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 {
+    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 {
+  *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);

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

Does this mean we always have to incrementally grow the extra table in between
doublings of the main table?  Why put that restriction on it?

[rvargas (doing something else), 2013/11/26 00:32:41]

Nope. It can be zero.

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

Huh.  I guess I had a braino; dunno why I thought it was GT.

+
+      // 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));

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

It feels to me like there are assumptions in this code about aliasing, but I'm
not certain what they are.   Let me go over what I believe the context for this
code is and make comments conditional on that.  

I believe that this function will be called in only three situations:
* First initialization.  main_table_ will be null, params->main_table will point
to memory mapped from a file, and params->extra_table will be null.
* Growth of extra table.  params->main_table will be NULL.   params->extra_table
!= extra_table_, but will point to a memory mapped region of the same file, only
larger.  Thus any changes made to params->extra_table will be reflected in
extra_table_ and vice versa (for the length that extra_table_ is mapped for). 
extra_table_ will be unmapped after this function returns (does the calling code
have it's own pointer to extra_table_?)
* Doubling of main table.  params->main_table != main_table_, but will point to
a memory mapped region of the same file, only doubled in size. 
params->extra_table will point to a section of memory mapped to the extra table
file, that hasn't changed in size any.  params->extra_table != extra_table_ and
the location pointed to by extra_table_ will be unmapped after this routine
finishes (??), but the two memory regions will be direct aliases to one another.
 

(I'll probably want a comment clarifying these assumptions somewhere, but I'll
wait to suggest what until I'm certain I understand it all. :-})

Assuming that that's correct, why refer to the same data through two different
points (extra_table_ and params->extra_table)?  It seems like it's just going to
generate confusion.  

[rvargas (doing something else), 2013/11/26 00:32:41]

params->extra_table should not be null.
Yes, someone will know how to unmap the old table after this method returns.
sounds correct.

The underlying assumption is that the index is memory mapped and follows the
format (and files) described in disk_format_v3.h, so the act of re-initializing
the IndexTable is a consequence of growing some file and creating another map of
the new extension. As such, we should never receive the same pointer that we are
currently using (but there's no check for that, because it shouldn't really
matter), and we deal with pointers not mapped sections (in fact all the unit
tests just allocate memory, never map anything).

Aliasing is important in that we don't memcpy data from the old mapping to the
new mapping when the file just grows, as that would be a waste of time. So yes,
this has a memory interface, but expects the caller to deal with the files as
defined by the file format, not just random pointers (hence
TestCacheTables::CopyFrom simulating that behavior)

But that should be clear from the comment at the top of index_table.h, right?
Do I? I try to refer to the data that logically is being accessed... so for
instance line 461 copies the old data somewhere safe and line 463 clears the
storage for the new data. Production code could copy the new data and clear the
old data, but that would confuse the reader and prevent the unit tests from
working :)

I mean, the whole thing requires mapping (or a judicious emulation from the
caller), but if this code is misusing source or destination somewhere assuming
that they are the same, let me know so that it's fixed.

So, conceptually, the caller could suspend all requests to this class, copy the
file to another file and map the new file (so that there is no aliasing) before
calling into this class again asking for re-init.

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

So what's the size of the extra_table on init?  Just the header?
Re-reading that comment, I find it more abstract that I'd like; I'd rather the
aliasing assumptions were made explicit, either in the comment to this function
or in the comments to IndexTableInitData.  But see later. 
Ah!  Thank you.  That's a (hypothetical) use case that's very useful for me. 
Can we put in a comment (before this function or in IndexTableInitData) that if
this function is being called a second time, the caller of Init guarantees that
the data pointed to by params->main_table will be an improper (i.e. possibly
identical) super-set of what was previously passed, and that if main_table isn't
being grown, params->extra_table will similarly be a super-set of what was
previously passed?  

I'd also like to have the callers responsibility to deallocate the memory that
main_table_ and extra_table_ used to point to made explicit.  If one isn't
thinking about this function in terms of memory mapped files, it's somewhat
surprising; it effectively means that the caller owns that memory, which I don't
think is the default assumption one would have looking at the call.

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

There is no header on the extra table, but it has to have some space there to be
able to store something. The reason is that no matter how big the main table is,
it may take as little as 5 entries to require space on the extra table. Backend
unit tests start with something like 8 cells, and production code starts with
1/8th of the main table.
I'm a little worried about this comment. The header mentions multiple files that
can be remapped while the cache is working and that management is external to
this file, so it looks pretty concrete to me. Without the files being mmapped,
the whole IndexTable would 
be completely impractical so that's not exactly a detail.

I'll extend the comment for Init()
The memory ownership should be clear by the definition of IndexTableInitData.
There is ownership transfer for the backups, but not for the bitmap or tables.
That's the (relatively new) coding standard so it feels a little weird if that
is repeated by comments.

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

I'm good with the IndexTable code explicitly relying on the memory mapping.  My
preference would be that that memory mapping and the aliasing it implies was
called out actually in a comment near the code, but if you'd prefer a pointer to
the design doc I'm ok with that.
Ok, that makes sense.

+    }
+    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);

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

What results in this 11?  This seems like you're simply saying that you can't
have a table_len greater than 32 bits, in which case don't you want to just say
that?  (I.e. IIRTCC the 11 is dependent on a specific value of kBaseTableLen,
and that dependency should be explicit in the DCHECK).

[rvargas (doing something else), 2013/11/26 00:32:41]

This is just saying that the table can be doubled 11 times from the smaller
table  to the biggest table. Yes, the value (11) is derived from kBaseTableLen
and maybe kMaxAddress or kCellAddressMask, but I thought it was clearer to have
the number of bits here (right when we are saying "how many extra bits can we
have") rather to come out with a probably cryptic formula that derives the
proper value from other numbers. The cost is of course less flexibility if the
format change, but at least it will fail right when it is needed. When I was
writing the code this value changed right here multiple times depending on what
I had implemented (and was ready to test) so it seemed better to keep it that
way instead of tying it to other constants.

I can define a local constant here if you don't like it.

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

Huh.  I don't particularly care about future flexibility (I mean, future
flexibility is good, just not my highest current priority :-}).  But from my
perspective in reading the code, having the cryptic formulas calls out to the
reader what the dependencies between the different constants are.  I had been
thinking of asking if we could have constants defined in disk_format_v3.h for
the different pieces of the IndexCell, and then define the other constants that
need to match those based on those constants.  It means if you're tracing the
"Why is this number this value?" question, you get roadsigns.  

Can you say more about why having an 11 is clearer?  I'm not getting it.  It
doesn't feel like it tells the code reader/maintainer/debugger anything.
 
I'm not interested in "const uint32 kExtraBitsLimit = 11;", if that's what
you're offering; I don't find that any more useful than just using 11.  But I'd
be interested in your thoughts about my general argument above.

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

My best example would be the failure of the formula two lines below this one.

I can come up with something like the log of the largest table divided by the
smallest table, but then that rises the issue of deriving the largest table. I
hear what you are saying and I generally agree, to the point of having a bunch
of constants with meaningful names whose values can be derived easily by just
inspection (the reason for the constants here).

In this particular case, we have a line that calculates a number from the
comparison of the current table versus the smallest table. The first check says
we cannot have a negative number (a table smaller than the smallest), the second
line checks the value against an upper bound, and that should tell right away
that we are checking for the largest possible table (right?)

The only question is then why the largest table is 11 times larger than the
smallest table, or in other words, what is the size of the largest table.
Honestly, if I'm reading some code that I didn't write, I would not care much
about the value of that number (the actual limit for the test): I would mostly
care for some limit being there, either on a check, or in the code that uses
that number. In this case, it would mean to me the same if that value is 8 or
15, or derived from a formula. 8 could be wrong, the formula could be off by one
and in any case I would not spend time looking at the value unless I'm actually
trying to debug a problem and I have reason to suspect that the max value could
be at fault. And if I'm doing that, I would probably ignore the formula, figure
out what the value should be and compare that against what the code says (number
of bits on an address = 22, so 21 of them go to the main table; smaller table =
1024 (10 bits), so delta = 21 - 10)

And that's why I prefer a plain number here rather than a formula... given that
too much may be read from the formula (as in the check against 6). What I think
it matters is not the value, but the check itself (double check an upper limit,
whatever that is)

I hope I don't sound combative, that's not my intention. I just want to answer
the question before we setup in what to do.

I'm up for moving relevant constants to the file format header. That's why
kBaseTableLen is there. Shifts and masks I'm not so sure as they make more sense
with the code that uses them, and I don't want to make them visible to any code
outside this file.

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

Nope, you don't sound combative, and I appreciate the detailed explanation.
I think most of my feeling on this topic would be addressed by making explicit
the relationships between the different constants--I don't have strong general
feelings about either where the constants are declared or this particular
location being a number rather than a constant 11.  But I would like constants
that are used in multiple places in the code and do have a relationship to each
other to be expressed in terms of each other.  So for instance, disk_format_v3.h
would have k{SmallTable,}HashOffset and k{SmallTable,}HashLength, and
kHash{SmallTable,}Shift and kCell{SmallTable,}HashMask would be defined from
those values (probably in index_table.cc).  Would you be good with that?

Having said all that, the place I diverge from you in modeling this code being
read by someone who doesn't know it is, if they suspected the max value would be
at fault, the formula would give them a hint as to how that max was derived. 
That hint might be wrong, but it's structure that would lead them further into
the code, and point at the logic that they would need to vet.  But as I say, I
more care about the relationship between the defined constants being clear than
about this particular number being a formula.

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

Any thoughts on this request?

An extreme example that I don't think I've previously mentioned: kBaseTableLen
is defined in three different places (backend_impl.cc, backend_impl_v3.cc, and
backend_worker.cc, disk_format_v3.h), and the definition in the .h file looks to
contradict the common definition in the .cc files.  

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

I tried to move the conversation to the latest version of the code, where I
added comments about it.
That is just a transient detail...
- backend_impl.cc: nothing to do about it (old format)
- backend_impl_v3.cc: old, unused code
- backend_worker.cc: either old, unused code, or using the value from
disk_format_v3.h
- disk_format_v3.h: definition for the new format.

+  mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1;
+  small_table_ = extra_bits_ < kHashShift - kHashSmallTableShift;

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

In other words, while the number of bits that are thrown away before making the
comparison between the hash and the IndexCell partial hash is greater than the
number of bits used to index into the table, leave the table small, but when we
start using all those thrown-away bits and crowding into the comparison section,
switch to the large table?  

(I'll note that this seems like a different metric for the small/large table
distinction that I'd previously understood--I thought it was about whether or
not the entries will always be stored in one file.  But looking at
disk_format_v3.h, it seems like the distinction is specified purely by the
number of entries.  If there's a subtle background connection between these
three things, it should probably be made explicit, or if one of them isn't
relevant, that should be made clear too.  

Based on how much pain it took me to figure out, I'll probably also want an
explanatory comment about what hashes mean (in the different contexts)
somewhere, but I'll ask for that once I'm confident I actually understand how
they're used.)

[rvargas (doing something else), 2013/11/26 00:32:41]

I didn't intend to make a strong statement about what this means. It really just
means extra_bits_ < 6, as in the table can be doubled 6 times before reaching
the 64k border between the two formats.

It's just that those two values are tightly related to each other, and the only
difference between them is the table type (small or large), and subtracting them
gives me the 6 that I need. Somewhat similar to the previous '11' but this time
I'm tying it to other constants that change accordingly (and as far as I
remember I use this same formula in other places).
The distinction between small and large is basically arbitrary. 64K is an
interesting number, and it is the base table size of V2, so it was just natural
to keep using it. A small table is a new feature of V3, so it covers tables
smaller than 64K.

The maximum number of blocks on a block file also happens to be 64k mostly
because 64k is an interesting number (and it doesn't yield files that are too
big with the largest block file), and it requires two standard pages (4k each)
to hold the bitmap. 

That results in being able to store up to 64k entries on a single file (in fact,
slightly less than that). And that just fits in that it allows the implied file
feature of small tables, but it is not the cause of the border (although it
would be hard to move that border somewhere else).

So things fit, but the "real" distinction between small and large tables is
arbitrarily a 64k table. That's why some numbers are really "count how many
times we can do foo", given the arbitrary limits of the format (start at 1k,
switch at 64k, up to 22 bits)

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

This makes sense, but mostly comes down to my wanting to be able to trace
dependencies between constants/distinctions.  I.e. if the defining difference
between a small and a large table is the 64K boundary, I'd love to have (e.g.) a
constant somewhere kMaxSmallTableSize = 64K, and have (e.g.) the difference
between kHashShift and kHashSmallTable shift defined in terms of it.  (I.e. this
is the same comment as the previous.)

+  if (!small_table_)
+    extra_bits_ -= kHashShift - kHashSmallTableShift;
+
+  // 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 extra table.

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

nit, suggestion: "clear the part of the bitmap referring to the extra table"?

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

Done.

+    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);

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

Under what circumstances will they be equal?  Does that imply that we could be
doubling table size in a situation where the extra_table is the same size as the
added main table size?

[rvargas (doing something else), 2013/11/26 00:32:41]

Mostly a check for not getting a negative index below.

We could be doing that, or maybe growing the extra table by 16 entries (so that
the number of words doesn't change). Backend tests grow the table really slowly
:)

+    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;
+}
+
+// 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;
+  }
+  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);
+}
+
+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) {
+    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;
+  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_;
+  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