src/net/disk_cache/blockfile/index_table_v3.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/disk_cache/blockfile/index_table_v3.h"
   6
   7 #include <algorithm>
   8 #include <set>
   9 #include <utility>
  10
  11 #include "base/bits.h"
  12 #include "net/base/io_buffer.h"
  13 #include "net/base/net_errors.h"
  14 #include "net/disk_cache/disk_cache.h"
  15
  16 using base::Time;
  17 using base::TimeDelta;
  18 using disk_cache::CellInfo;
  19 using disk_cache::CellList;
  20 using disk_cache::IndexCell;
  21 using disk_cache::IndexIterator;
  22
  23 namespace {
  24
  25 // The following constants describe the bitfields of an IndexCell so they are
  26 // implicitly synchronized with the descrption of IndexCell on file_format_v3.h.
  27 const uint64 kCellLocationMask = (1 << 22) - 1;
  28 const uint64 kCellIdMask = (1 << 18) - 1;
  29 const uint64 kCellTimestampMask = (1 << 20) - 1;
  30 const uint64 kCellReuseMask = (1 << 4) - 1;
  31 const uint8 kCellStateMask = (1 << 3) - 1;
  32 const uint8 kCellGroupMask = (1 << 3) - 1;
  33 const uint8 kCellSumMask = (1 << 2) - 1;
  34
  35 const uint64 kCellSmallTableLocationMask = (1 << 16) - 1;
  36 const uint64 kCellSmallTableIdMask = (1 << 24) - 1;
  37
  38 const int kCellIdOffset = 22;
  39 const int kCellTimestampOffset = 40;
  40 const int kCellReuseOffset = 60;
  41 const int kCellGroupOffset = 3;
  42 const int kCellSumOffset = 6;
  43
  44 const int kCellSmallTableIdOffset = 16;
  45
  46 // The number of bits that a hash has to be shifted to grab the part that
  47 // defines the cell id.
  48 const int kHashShift = 14;
  49 const int kSmallTableHashShift = 8;
  50
  51 // Unfortunately we have to break the abstaction a little here: the file number
  52 // where entries are stored is outside of the control of this code, and it is
  53 // usually part of the stored address. However, for small tables we only store
  54 // 16 bits of the address so the file number is never stored on a cell. We have
  55 // to infere the file number from the type of entry (normal vs evicted), and
  56 // the knowledge that given that the table will not keep more than 64k entries,
  57 // a single file of each type is enough.
  58 const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1;
  59 const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1;
  60 const int kMaxLocation = 1 << 22;
  61 const int kMinFileNumber = 1 << 16;
  62
  63 uint32 GetCellLocation(const IndexCell& cell) {
  64   return cell.first_part & kCellLocationMask;
  65 }
  66
  67 uint32 GetCellSmallTableLocation(const IndexCell& cell) {
  68   return cell.first_part & kCellSmallTableLocationMask;
  69 }
  70
  71 uint32 GetCellId(const IndexCell& cell) {
  72   return (cell.first_part >> kCellIdOffset) & kCellIdMask;
  73 }
  74
  75 uint32 GetCellSmallTableId(const IndexCell& cell) {
  76   return (cell.first_part >> kCellSmallTableIdOffset) &
  77          kCellSmallTableIdMask;
  78 }
  79
  80 int GetCellTimestamp(const IndexCell& cell) {
  81   return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask;
  82 }
  83
  84 int GetCellReuse(const IndexCell& cell) {
  85   return (cell.first_part >> kCellReuseOffset) & kCellReuseMask;
  86 }
  87
  88 int GetCellState(const IndexCell& cell) {
  89   return cell.last_part & kCellStateMask;
  90 }
  91
  92 int GetCellGroup(const IndexCell& cell) {
  93   return (cell.last_part >> kCellGroupOffset) & kCellGroupMask;
  94 }
  95
  96 int GetCellSum(const IndexCell& cell) {
  97   return (cell.last_part >> kCellSumOffset) & kCellSumMask;
  98 }
  99
 100 void SetCellLocation(IndexCell* cell, uint32 address) {
 101   DCHECK_LE(address, static_cast<uint32>(kCellLocationMask));
 102   cell->first_part &= ~kCellLocationMask;
 103   cell->first_part |= address;
 104 }
 105
 106 void SetCellSmallTableLocation(IndexCell* cell, uint32 address) {
 107   DCHECK_LE(address, static_cast<uint32>(kCellSmallTableLocationMask));
 108   cell->first_part &= ~kCellSmallTableLocationMask;
 109   cell->first_part |= address;
 110 }
 111
 112 void SetCellId(IndexCell* cell, uint32 hash) {
 113   DCHECK_LE(hash, static_cast<uint32>(kCellIdMask));
 114   cell->first_part &= ~(kCellIdMask << kCellIdOffset);
 115   cell->first_part |= static_cast<int64>(hash) << kCellIdOffset;
 116 }
 117
 118 void SetCellSmallTableId(IndexCell* cell, uint32 hash) {
 119   DCHECK_LE(hash, static_cast<uint32>(kCellSmallTableIdMask));
 120   cell->first_part &= ~(kCellSmallTableIdMask << kCellSmallTableIdOffset);
 121   cell->first_part |= static_cast<int64>(hash) << kCellSmallTableIdOffset;
 122 }
 123
 124 void SetCellTimestamp(IndexCell* cell, int timestamp) {
 125   DCHECK_LT(timestamp, 1 << 20);
 126   DCHECK_GE(timestamp, 0);
 127   cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset);
 128   cell->first_part |= static_cast<int64>(timestamp) << kCellTimestampOffset;
 129 }
 130
 131 void SetCellReuse(IndexCell* cell, int count) {
 132   DCHECK_LT(count, 16);
 133   DCHECK_GE(count, 0);
 134   cell->first_part &= ~(kCellReuseMask << kCellReuseOffset);
 135   cell->first_part |= static_cast<int64>(count) << kCellReuseOffset;
 136 }
 137
 138 void SetCellState(IndexCell* cell, disk_cache::EntryState state) {
 139   cell->last_part &= ~kCellStateMask;
 140   cell->last_part |= state;
 141 }
 142
 143 void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) {
 144   cell->last_part &= ~(kCellGroupMask << kCellGroupOffset);
 145   cell->last_part |= group << kCellGroupOffset;
 146 }
 147
 148 void SetCellSum(IndexCell* cell, int sum) {
 149   DCHECK_LT(sum, 4);
 150   DCHECK_GE(sum, 0);
 151   cell->last_part &= ~(kCellSumMask << kCellSumOffset);
 152   cell->last_part |= sum << kCellSumOffset;
 153 }
 154
 155 // This is a very particular way to calculate the sum, so it will not match if
 156 // compared a gainst a pure 2 bit, modulo 2 sum.
 157 int CalculateCellSum(const IndexCell& cell) {
 158   uint32* words = bit_cast<uint32*>(&cell);
 159   uint8* bytes = bit_cast<uint8*>(&cell);
 160   uint32 result = words[0] + words[1];
 161   result += result >> 16;
 162   result += (result >> 8) + (bytes[8] & 0x3f);
 163   result += result >> 4;
 164   result += result >> 2;
 165   return result & 3;
 166 }
 167
 168 bool SanityCheck(const IndexCell& cell) {
 169   if (GetCellSum(cell) != CalculateCellSum(cell))
 170     return false;
 171
 172   if (GetCellState(cell) > disk_cache::ENTRY_USED ||
 173       GetCellGroup(cell) == disk_cache::ENTRY_RESERVED ||
 174       GetCellGroup(cell) > disk_cache::ENTRY_EVICTED) {
 175     return false;
 176   }
 177
 178   return true;
 179 }
 180
 181 int FileNumberFromLocation(int location) {
 182   return location / kMinFileNumber;
 183 }
 184
 185 int StartBlockFromLocation(int location) {
 186   return location % kMinFileNumber;
 187 }
 188
 189 bool IsValidAddress(disk_cache::Addr address) {
 190   if (!address.is_initialized() ||
 191       (address.file_type() != disk_cache::BLOCK_EVICTED &&
 192        address.file_type() != disk_cache::BLOCK_ENTRIES)) {
 193     return false;
 194   }
 195
 196   return address.FileNumber() < FileNumberFromLocation(kMaxLocation);
 197 }
 198
 199 bool IsNormalState(const IndexCell& cell) {
 200   disk_cache::EntryState state =
 201       static_cast<disk_cache::EntryState>(GetCellState(cell));
 202   DCHECK_NE(state, disk_cache::ENTRY_FREE);
 203   return state != disk_cache::ENTRY_DELETED &&
 204          state != disk_cache::ENTRY_FIXING;
 205 }
 206
 207 inline int GetNextBucket(int min_bucket_num, int max_bucket_num,
 208                          disk_cache::IndexBucket* table,
 209                          disk_cache::IndexBucket** bucket) {
 210   if (!(*bucket)->next)
 211     return 0;
 212
 213   int bucket_num = (*bucket)->next / disk_cache::kCellsPerBucket;
 214   if (bucket_num < min_bucket_num || bucket_num > max_bucket_num) {
 215     // The next bucket must fall within the extra table. Note that this is not
 216     // an uncommon path as growing the table may not cleanup the link from the
 217     // main table to the extra table, and that cleanup is performed here when
 218     // accessing that bucket for the first time. This behavior has to change if
 219     // the tables are ever shrinked.
 220     (*bucket)->next = 0;
 221     return 0;
 222   }
 223   *bucket = &table[bucket_num - min_bucket_num];
 224   return bucket_num;
 225 }
 226
 227 // Updates the |iterator| with the current |cell|. This cell may cause all
 228 // previous cells to be deleted (when a new target timestamp is found), the cell
 229 // may be added to the list (if it matches the target timestamp), or may it be
 230 // ignored.
 231 void UpdateIterator(const disk_cache::EntryCell& cell,
 232                     int limit_time,
 233                     IndexIterator* iterator) {
 234   int time = cell.GetTimestamp();
 235   // Look for not interesting times.
 236   if (iterator->forward && time <= limit_time)
 237     return;
 238   if (!iterator->forward && time >= limit_time)
 239     return;
 240
 241   if ((iterator->forward && time < iterator->timestamp) ||
 242       (!iterator->forward && time > iterator->timestamp)) {
 243     // This timestamp is better than the one we had.
 244     iterator->timestamp = time;
 245     iterator->cells.clear();
 246   }
 247   if (time == iterator->timestamp) {
 248     CellInfo cell_info = { cell.hash(), cell.GetAddress() };
 249     iterator->cells.push_back(cell_info);
 250   }
 251 }
 252
 253 void InitIterator(IndexIterator* iterator) {
 254   iterator->cells.clear();
 255   iterator->timestamp = iterator->forward ? kint32max : 0;
 256 }
 257
 258 }  // namespace
 259
 260 namespace disk_cache {
 261
 262 EntryCell::~EntryCell() {
 263 }
 264
 265 bool EntryCell::IsValid() const {
 266   return GetCellLocation(cell_) != 0;
 267 }
 268
 269 // This code has to map the cell address (up to 22 bits) to a general cache Addr
 270 // (up to 24 bits of general addressing). It also set the implied file_number
 271 // in the case of small tables. See also the comment by the definition of
 272 // kEntriesFile.
 273 Addr EntryCell::GetAddress() const {
 274   uint32 location = GetLocation();
 275   int file_number = FileNumberFromLocation(location);
 276   if (small_table_) {
 277     DCHECK_EQ(0, file_number);
 278     file_number = (GetGroup() == ENTRY_EVICTED) ? kEvictedEntriesFile :
 279                                                   kEntriesFile;
 280   }
 281   DCHECK_NE(0, file_number);
 282   FileType file_type = (GetGroup() == ENTRY_EVICTED) ? BLOCK_EVICTED :
 283                                                        BLOCK_ENTRIES;
 284   return Addr(file_type, 1, file_number, StartBlockFromLocation(location));
 285 }
 286
 287 EntryState EntryCell::GetState() const {
 288   return static_cast<EntryState>(GetCellState(cell_));
 289 }
 290
 291 EntryGroup EntryCell::GetGroup() const {
 292   return static_cast<EntryGroup>(GetCellGroup(cell_));
 293 }
 294
 295 int EntryCell::GetReuse() const {
 296   return GetCellReuse(cell_);
 297 }
 298
 299 int EntryCell::GetTimestamp() const {
 300   return GetCellTimestamp(cell_);
 301 }
 302
 303 void EntryCell::SetState(EntryState state) {
 304   SetCellState(&cell_, state);
 305 }
 306
 307 void EntryCell::SetGroup(EntryGroup group) {
 308   SetCellGroup(&cell_, group);
 309 }
 310
 311 void EntryCell::SetReuse(int count) {
 312   SetCellReuse(&cell_, count);
 313 }
 314
 315 void EntryCell::SetTimestamp(int timestamp) {
 316   SetCellTimestamp(&cell_, timestamp);
 317 }
 318
 319 // Static.
 320 EntryCell EntryCell::GetEntryCellForTest(int32 cell_num,
 321                                          uint32 hash,
 322                                          Addr address,
 323                                          IndexCell* cell,
 324                                          bool small_table) {
 325   if (cell) {
 326     EntryCell entry_cell(cell_num, hash, *cell, small_table);
 327     return entry_cell;
 328   }
 329
 330   return EntryCell(cell_num, hash, address, small_table);
 331 }
 332
 333 void EntryCell::SerializaForTest(IndexCell* destination) {
 334   FixSum();
 335   Serialize(destination);
 336 }
 337
 338 EntryCell::EntryCell() : cell_num_(0), hash_(0), small_table_(false) {
 339   cell_.Clear();
 340 }
 341
 342 EntryCell::EntryCell(int32 cell_num,
 343                      uint32 hash,
 344                      Addr address,
 345                      bool small_table)
 346     : cell_num_(cell_num),
 347       hash_(hash),
 348       small_table_(small_table) {
 349   DCHECK(IsValidAddress(address) || !address.value());
 350
 351   cell_.Clear();
 352   SetCellState(&cell_, ENTRY_NEW);
 353   SetCellGroup(&cell_, ENTRY_NO_USE);
 354   if (small_table) {
 355     DCHECK(address.FileNumber() == kEntriesFile ||
 356            address.FileNumber() == kEvictedEntriesFile);
 357     SetCellSmallTableLocation(&cell_, address.start_block());
 358     SetCellSmallTableId(&cell_, hash >> kSmallTableHashShift);
 359   } else {
 360     uint32 location = address.FileNumber() << 16 | address.start_block();
 361     SetCellLocation(&cell_, location);
 362     SetCellId(&cell_, hash >> kHashShift);
 363   }
 364 }
 365
 366 EntryCell::EntryCell(int32 cell_num,
 367                      uint32 hash,
 368                      const IndexCell& cell,
 369                      bool small_table)
 370     : cell_num_(cell_num),
 371       hash_(hash),
 372       cell_(cell),
 373       small_table_(small_table) {
 374 }
 375
 376 void EntryCell::FixSum() {
 377   SetCellSum(&cell_, CalculateCellSum(cell_));
 378 }
 379
 380 uint32 EntryCell::GetLocation() const {
 381   if (small_table_)
 382     return GetCellSmallTableLocation(cell_);
 383
 384   return GetCellLocation(cell_);
 385 }
 386
 387 uint32 EntryCell::RecomputeHash() {
 388   if (small_table_) {
 389     hash_ &= (1 << kSmallTableHashShift) - 1;
 390     hash_ |= GetCellSmallTableId(cell_) << kSmallTableHashShift;
 391     return hash_;
 392   }
 393
 394   hash_ &= (1 << kHashShift) - 1;
 395   hash_ |= GetCellId(cell_) << kHashShift;
 396   return hash_;
 397 }
 398
 399 void EntryCell::Serialize(IndexCell* destination) const {
 400   *destination = cell_;
 401 }
 402
 403 EntrySet::EntrySet() : evicted_count(0), current(0) {
 404 }
 405
 406 EntrySet::~EntrySet() {
 407 }
 408
 409 IndexIterator::IndexIterator() {
 410 }
 411
 412 IndexIterator::~IndexIterator() {
 413 }
 414
 415 IndexTableInitData::IndexTableInitData() {
 416 }
 417
 418 IndexTableInitData::~IndexTableInitData() {
 419 }
 420
 421 // -----------------------------------------------------------------------
 422
 423 IndexTable::IndexTable(IndexTableBackend* backend)
 424     : backend_(backend),
 425       header_(NULL),
 426       main_table_(NULL),
 427       extra_table_(NULL),
 428       modified_(false),
 429       small_table_(false) {
 430 }
 431
 432 IndexTable::~IndexTable() {
 433 }
 434
 435 // For a general description of the index tables see:
 436 // http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Index
 437 //
 438 // The index is split between two tables: the main_table_ and the extra_table_.
 439 // The main table can grow only by doubling its number of cells, while the
 440 // extra table can grow slowly, because it only contain cells that overflow
 441 // from the main table. In order to locate a given cell, part of the hash is
 442 // used directly as an index into the main table; once that bucket is located,
 443 // all cells with that partial hash (i.e., belonging to that bucket) are
 444 // inspected, and if present, the next bucket (located on the extra table) is
 445 // then located. For more information on bucket chaining see:
 446 // http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Buckets
 447 //
 448 // There are two cases when increasing the size:
 449 //  - Doubling the size of the main table
 450 //  - Adding more entries to the extra table
 451 //
 452 // For example, consider a 64k main table with 8k cells on the extra table (for
 453 // a total of 72k cells). Init can be called to add another 8k cells at the end
 454 // (grow to 80k cells). When the size of the extra table approaches 64k, Init
 455 // can be called to double the main table (to 128k) and go back to a small extra
 456 // table.
 457 void IndexTable::Init(IndexTableInitData* params) {
 458   bool growing = header_ != NULL;
 459   scoped_ptr<IndexBucket[]> old_extra_table;
 460   header_ = &params->index_bitmap->header;
 461
 462   if (params->main_table) {
 463     if (main_table_) {
 464       // This is doubling the size of main table.
 465       DCHECK_EQ(base::bits::Log2Floor(header_->table_len),
 466                 base::bits::Log2Floor(backup_header_->table_len) + 1);
 467       int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket;
 468       DCHECK_GE(extra_size, 0);
 469
 470       // Doubling the size implies deleting the extra table and moving as many
 471       // cells as we can to the main table, so we first copy the old one. This
 472       // is not required when just growing the extra table because we don't
 473       // move any cell in that case.
 474       old_extra_table.reset(new IndexBucket[extra_size]);
 475       memcpy(old_extra_table.get(), extra_table_,
 476              extra_size * sizeof(IndexBucket));
 477       memset(params->extra_table, 0, extra_size * sizeof(IndexBucket));
 478     }
 479     main_table_ = params->main_table;
 480   }
 481   DCHECK(main_table_);
 482   extra_table_ = params->extra_table;
 483
 484   // extra_bits_ is really measured against table-size specific values.
 485   const int kMaxAbsoluteExtraBits = 12;  // From smallest to largest table.
 486   const int kMaxExtraBitsSmallTable = 6;  // From smallest to 64K table.
 487
 488   extra_bits_ = base::bits::Log2Floor(header_->table_len) -
 489                 base::bits::Log2Floor(kBaseTableLen);
 490   DCHECK_GE(extra_bits_, 0);
 491   DCHECK_LT(extra_bits_, kMaxAbsoluteExtraBits);
 492
 493   // Note that following the previous code the constants could be derived as
 494   // kMaxAbsoluteExtraBits = base::bits::Log2Floor(max table len) -
 495   //                         base::bits::Log2Floor(kBaseTableLen);
 496   //                       = 22 - base::bits::Log2Floor(1024) = 22 - 10;
 497   // kMaxExtraBitsSmallTable = base::bits::Log2Floor(max 16 bit table) - 10.
 498
 499   mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1;
 500   small_table_ = extra_bits_ < kMaxExtraBitsSmallTable;
 501   if (!small_table_)
 502     extra_bits_ -= kMaxExtraBitsSmallTable;
 503
 504   // table_len keeps the max number of cells stored by the index. We need a
 505   // bitmap with 1 bit per cell, and that bitmap has num_words 32-bit words.
 506   int num_words = (header_->table_len + 31) / 32;
 507
 508   if (old_extra_table) {
 509     // All the cells from the extra table are moving to the new tables so before
 510     // creating the bitmaps, clear the part of the bitmap referring to the extra
 511     // table.
 512     int old_main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32;
 513     DCHECK_GT(num_words, old_main_table_bit_words);
 514     memset(params->index_bitmap->bitmap + old_main_table_bit_words, 0,
 515            (num_words - old_main_table_bit_words) * sizeof(int32));
 516
 517     DCHECK(growing);
 518     int old_num_words = (backup_header_.get()->table_len + 31) / 32;
 519     DCHECK_GT(old_num_words, old_main_table_bit_words);
 520     memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0,
 521            (old_num_words - old_main_table_bit_words) * sizeof(int32));
 522   }
 523   bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len,
 524                            num_words));
 525
 526   if (growing) {
 527     int old_num_words = (backup_header_.get()->table_len + 31) / 32;
 528     DCHECK_GE(num_words, old_num_words);
 529     scoped_ptr<uint32[]> storage(new uint32[num_words]);
 530     memcpy(storage.get(), backup_bitmap_storage_.get(),
 531            old_num_words * sizeof(int32));
 532     memset(storage.get() + old_num_words, 0,
 533            (num_words - old_num_words) * sizeof(int32));
 534
 535     backup_bitmap_storage_.swap(storage);
 536     backup_header_->table_len = header_->table_len;
 537   } else {
 538     backup_bitmap_storage_.reset(params->backup_bitmap.release());
 539     backup_header_.reset(params->backup_header.release());
 540   }
 541
 542   num_words = (backup_header_->table_len + 31) / 32;
 543   backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(),
 544                                   backup_header_->table_len, num_words));
 545   if (old_extra_table)
 546     MoveCells(old_extra_table.get());
 547
 548   if (small_table_)
 549     DCHECK(header_->flags & SMALL_CACHE);
 550
 551   // All tables and backups are needed for operation.
 552   DCHECK(main_table_);
 553   DCHECK(extra_table_);
 554   DCHECK(bitmap_.get());
 555 }
 556
 557 void IndexTable::Shutdown() {
 558   header_ = NULL;
 559   main_table_ = NULL;
 560   extra_table_ = NULL;
 561   bitmap_.reset();
 562   backup_bitmap_.reset();
 563   backup_header_.reset();
 564   backup_bitmap_storage_.reset();
 565   modified_ = false;
 566 }
 567
 568 // The general method for locating cells is to:
 569 // 1. Get the first bucket. This usually means directly indexing the table (as
 570 //     this method does), or iterating through all possible buckets.
 571 // 2. Iterate through all the cells in that first bucket.
 572 // 3. If there is a linked bucket, locate it directly in the extra table.
 573 // 4. Go back to 2, as needed.
 574 //
 575 // One consequence of this pattern is that we never start looking at buckets in
 576 // the extra table, unless we are following a link from the main table.
 577 EntrySet IndexTable::LookupEntries(uint32 hash) {
 578   EntrySet entries;
 579   int bucket_num = static_cast<int>(hash & mask_);
 580   IndexBucket* bucket = &main_table_[bucket_num];
 581   do {
 582     for (int i = 0; i < kCellsPerBucket; i++) {
 583       IndexCell* current_cell = &bucket->cells[i];
 584       if (!GetLocation(*current_cell))
 585         continue;
 586       if (!SanityCheck(*current_cell)) {
 587         NOTREACHED();
 588         int cell_num = bucket_num * kCellsPerBucket + i;
 589         current_cell->Clear();
 590         bitmap_->Set(cell_num, false);
 591         backup_bitmap_->Set(cell_num, false);
 592         modified_ = true;
 593         continue;
 594       }
 595       int cell_num = bucket_num * kCellsPerBucket + i;
 596       if (MisplacedHash(*current_cell, hash)) {
 597         HandleMisplacedCell(current_cell, cell_num, hash & mask_);
 598       } else if (IsHashMatch(*current_cell, hash)) {
 599         EntryCell entry_cell(cell_num, hash, *current_cell, small_table_);
 600         CheckState(entry_cell);
 601         if (entry_cell.GetState() != ENTRY_DELETED) {
 602           entries.cells.push_back(entry_cell);
 603           if (entry_cell.GetGroup() == ENTRY_EVICTED)
 604             entries.evicted_count++;
 605         }
 606       }
 607     }
 608     bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
 609                                &bucket);
 610   } while (bucket_num);
 611   return entries;
 612 }
 613
 614 EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) {
 615   DCHECK(IsValidAddress(address));
 616   DCHECK(address.FileNumber() || address.start_block());
 617
 618   int bucket_num = static_cast<int>(hash & mask_);
 619   int cell_num = 0;
 620   IndexBucket* bucket = &main_table_[bucket_num];
 621   IndexCell* current_cell = NULL;
 622   bool found = false;
 623   do {
 624     for (int i = 0; i < kCellsPerBucket && !found; i++) {
 625       current_cell = &bucket->cells[i];
 626       if (!GetLocation(*current_cell)) {
 627         cell_num = bucket_num * kCellsPerBucket + i;
 628         found = true;
 629       }
 630     }
 631     if (found)
 632       break;
 633     bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
 634                                &bucket);
 635   } while (bucket_num);
 636
 637   if (!found) {
 638     bucket_num = NewExtraBucket();
 639     if (bucket_num) {
 640       cell_num = bucket_num * kCellsPerBucket;
 641       bucket->next = cell_num;
 642       bucket = &extra_table_[bucket_num - (mask_ + 1)];
 643       bucket->hash = hash & mask_;
 644       found = true;
 645     } else {
 646       // address 0 is a reserved value, and the caller interprets it as invalid.
 647       address.set_value(0);
 648     }
 649   }
 650
 651   EntryCell entry_cell(cell_num, hash, address, small_table_);
 652   if (address.file_type() == BLOCK_EVICTED)
 653     entry_cell.SetGroup(ENTRY_EVICTED);
 654   else
 655     entry_cell.SetGroup(ENTRY_NO_USE);
 656   Save(&entry_cell);
 657
 658   if (found) {
 659     bitmap_->Set(cell_num, true);
 660     backup_bitmap_->Set(cell_num, true);
 661     header()->used_cells++;
 662     modified_ = true;
 663   }
 664
 665   return entry_cell;
 666 }
 667
 668 EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) {
 669   return FindEntryCellImpl(hash, address, false);
 670 }
 671
 672 int IndexTable::CalculateTimestamp(Time time) {
 673   TimeDelta delta = time - Time::FromInternalValue(header_->base_time);
 674   return std::max(delta.InMinutes(), 0);
 675 }
 676
 677 base::Time IndexTable::TimeFromTimestamp(int timestamp) {
 678   return Time::FromInternalValue(header_->base_time) +
 679          TimeDelta::FromMinutes(timestamp);
 680 }
 681
 682 void IndexTable::SetSate(uint32 hash, Addr address, EntryState state) {
 683   EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE);
 684   if (!cell.IsValid()) {
 685     NOTREACHED();
 686     return;
 687   }
 688
 689   EntryState old_state = cell.GetState();
 690   switch (state) {
 691     case ENTRY_FREE:
 692       DCHECK_EQ(old_state, ENTRY_DELETED);
 693       break;
 694     case ENTRY_NEW:
 695       DCHECK_EQ(old_state, ENTRY_FREE);
 696       break;
 697     case ENTRY_OPEN:
 698       DCHECK_EQ(old_state, ENTRY_USED);
 699       break;
 700     case ENTRY_MODIFIED:
 701       DCHECK_EQ(old_state, ENTRY_OPEN);
 702       break;
 703     case ENTRY_DELETED:
 704       DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
 705              old_state == ENTRY_MODIFIED);
 706       break;
 707     case ENTRY_USED:
 708       DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
 709              old_state == ENTRY_MODIFIED);
 710       break;
 711     case ENTRY_FIXING:
 712       break;
 713   };
 714
 715   modified_ = true;
 716   if (state == ENTRY_DELETED) {
 717     bitmap_->Set(cell.cell_num(), false);
 718     backup_bitmap_->Set(cell.cell_num(), false);
 719   } else if (state == ENTRY_FREE) {
 720     cell.Clear();
 721     Write(cell);
 722     header()->used_cells--;
 723     return;
 724   }
 725   cell.SetState(state);
 726
 727   Save(&cell);
 728 }
 729
 730 void IndexTable::UpdateTime(uint32 hash, Addr address, base::Time current) {
 731   EntryCell cell = FindEntryCell(hash, address);
 732   if (!cell.IsValid())
 733     return;
 734
 735   int minutes = CalculateTimestamp(current);
 736
 737   // Keep about 3 months of headroom.
 738   const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90;
 739   if (minutes > kMaxTimestamp) {
 740     // TODO(rvargas):
 741     // Update header->old_time and trigger a timer
 742     // Rebaseline timestamps and don't update sums
 743     // Start a timer (about 2 backups)
 744     // fix all ckecksums and trigger another timer
 745     // update header->old_time because rebaseline is done.
 746     minutes = std::min(minutes, (1 << 20) - 1);
 747   }
 748
 749   cell.SetTimestamp(minutes);
 750   Save(&cell);
 751 }
 752
 753 void IndexTable::Save(EntryCell* cell) {
 754   cell->FixSum();
 755   Write(*cell);
 756 }
 757
 758 void IndexTable::GetOldest(IndexIterator* no_use,
 759                            IndexIterator* low_use,
 760                            IndexIterator* high_use) {
 761   no_use->forward = true;
 762   low_use->forward = true;
 763   high_use->forward = true;
 764   InitIterator(no_use);
 765   InitIterator(low_use);
 766   InitIterator(high_use);
 767
 768   WalkTables(-1, no_use, low_use, high_use);
 769 }
 770
 771 bool IndexTable::GetNextCells(IndexIterator* iterator) {
 772   int current_time = iterator->timestamp;
 773   InitIterator(iterator);
 774
 775   WalkTables(current_time, iterator, iterator, iterator);
 776   return !iterator->cells.empty();
 777 }
 778
 779 void IndexTable::OnBackupTimer() {
 780   if (!modified_)
 781     return;
 782
 783   int num_words = (header_->table_len + 31) / 32;
 784   int num_bytes = num_words * 4 + static_cast<int>(sizeof(*header_));
 785   scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes));
 786   memcpy(buffer->data(), header_, sizeof(*header_));
 787   memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(),
 788          num_words * 4);
 789   backend_->SaveIndex(buffer, num_bytes);
 790   modified_ = false;
 791 }
 792
 793 // -----------------------------------------------------------------------
 794
 795 EntryCell IndexTable::FindEntryCellImpl(uint32 hash, Addr address,
 796                                         bool allow_deleted) {
 797   int bucket_num = static_cast<int>(hash & mask_);
 798   IndexBucket* bucket = &main_table_[bucket_num];
 799   do {
 800     for (int i = 0; i < kCellsPerBucket; i++) {
 801       IndexCell* current_cell = &bucket->cells[i];
 802       if (!GetLocation(*current_cell))
 803         continue;
 804       DCHECK(SanityCheck(*current_cell));
 805       if (IsHashMatch(*current_cell, hash)) {
 806         // We have a match.
 807         int cell_num = bucket_num * kCellsPerBucket + i;
 808         EntryCell entry_cell(cell_num, hash, *current_cell, small_table_);
 809         if (entry_cell.GetAddress() != address)
 810           continue;
 811
 812         if (!allow_deleted && entry_cell.GetState() == ENTRY_DELETED)
 813           continue;
 814
 815         return entry_cell;
 816       }
 817     }
 818     bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
 819                                &bucket);
 820   } while (bucket_num);
 821   return EntryCell();
 822 }
 823
 824 void IndexTable::CheckState(const EntryCell& cell) {
 825   int current_state = cell.GetState();
 826   if (current_state != ENTRY_FIXING) {
 827     bool present = ((current_state & 3) != 0);  // Look at the last two bits.
 828     if (present != bitmap_->Get(cell.cell_num()) ||
 829         present != backup_bitmap_->Get(cell.cell_num())) {
 830       // There's a mismatch.
 831       if (current_state == ENTRY_DELETED) {
 832         // We were in the process of deleting this entry. Finish now.
 833         backend_->DeleteCell(cell);
 834       } else {
 835         current_state = ENTRY_FIXING;
 836         EntryCell bad_cell(cell);
 837         bad_cell.SetState(ENTRY_FIXING);
 838         Save(&bad_cell);
 839       }
 840     }
 841   }
 842
 843   if (current_state == ENTRY_FIXING)
 844     backend_->FixCell(cell);
 845 }
 846
 847 void IndexTable::Write(const EntryCell& cell) {
 848   IndexBucket* bucket = NULL;
 849   int bucket_num = cell.cell_num() / kCellsPerBucket;
 850   if (bucket_num < static_cast<int32>(mask_ + 1)) {
 851     bucket = &main_table_[bucket_num];
 852   } else {
 853     DCHECK_LE(bucket_num, header()->max_bucket);
 854     bucket = &extra_table_[bucket_num - (mask_ + 1)];
 855   }
 856
 857   int cell_number = cell.cell_num() % kCellsPerBucket;
 858   if (GetLocation(bucket->cells[cell_number]) && cell.GetLocation()) {
 859     DCHECK_EQ(cell.GetLocation(),
 860               GetLocation(bucket->cells[cell_number]));
 861   }
 862   cell.Serialize(&bucket->cells[cell_number]);
 863 }
 864
 865 int IndexTable::NewExtraBucket() {
 866   int safe_window = (header()->table_len < kNumExtraBlocks * 2) ?
 867                     kNumExtraBlocks / 4 : kNumExtraBlocks;
 868   if (header()->table_len - header()->max_bucket * kCellsPerBucket <
 869       safe_window) {
 870     backend_->GrowIndex();
 871   }
 872
 873   if (header()->max_bucket * kCellsPerBucket ==
 874       header()->table_len - kCellsPerBucket) {
 875     return 0;
 876   }
 877
 878   header()->max_bucket++;
 879   return header()->max_bucket;
 880 }
 881
 882 void IndexTable::WalkTables(int limit_time,
 883                             IndexIterator* no_use,
 884                             IndexIterator* low_use,
 885                             IndexIterator* high_use) {
 886   header_->num_no_use_entries = 0;
 887   header_->num_low_use_entries = 0;
 888   header_->num_high_use_entries = 0;
 889   header_->num_evicted_entries = 0;
 890
 891   for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
 892     int bucket_num = i;
 893     IndexBucket* bucket = &main_table_[i];
 894     do {
 895       UpdateFromBucket(bucket, i, limit_time, no_use, low_use, high_use);
 896
 897       bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
 898                                  &bucket);
 899     } while (bucket_num);
 900   }
 901   header_->num_entries = header_->num_no_use_entries +
 902                          header_->num_low_use_entries +
 903                          header_->num_high_use_entries +
 904                          header_->num_evicted_entries;
 905   modified_ = true;
 906 }
 907
 908 void IndexTable::UpdateFromBucket(IndexBucket* bucket, int bucket_hash,
 909                                   int limit_time,
 910                                   IndexIterator* no_use,
 911                                   IndexIterator* low_use,
 912                                   IndexIterator* high_use) {
 913   for (int i = 0; i < kCellsPerBucket; i++) {
 914     IndexCell& current_cell = bucket->cells[i];
 915     if (!GetLocation(current_cell))
 916       continue;
 917     DCHECK(SanityCheck(current_cell));
 918     if (!IsNormalState(current_cell))
 919       continue;
 920
 921     EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
 922                          current_cell, small_table_);
 923     switch (GetCellGroup(current_cell)) {
 924       case ENTRY_NO_USE:
 925         UpdateIterator(entry_cell, limit_time, no_use);
 926         header_->num_no_use_entries++;
 927         break;
 928       case ENTRY_LOW_USE:
 929         UpdateIterator(entry_cell, limit_time, low_use);
 930         header_->num_low_use_entries++;
 931         break;
 932       case ENTRY_HIGH_USE:
 933         UpdateIterator(entry_cell, limit_time, high_use);
 934         header_->num_high_use_entries++;
 935         break;
 936       case ENTRY_EVICTED:
 937         header_->num_evicted_entries++;
 938         break;
 939       default:
 940         NOTREACHED();
 941     }
 942   }
 943 }
 944
 945 // This code is only called from Init() so the internal state of this object is
 946 // in flux (this method is performing the last steps of re-initialization). As
 947 // such, random methods are not supposed to work at this point, so whatever this
 948 // method calls should be relatively well controlled and it may require some
 949 // degree of "stable state faking".
 950 void IndexTable::MoveCells(IndexBucket* old_extra_table) {
 951   int max_hash = (mask_ + 1) / 2;
 952   int max_bucket = header()->max_bucket;
 953   header()->max_bucket = mask_;
 954   int used_cells = header()->used_cells;
 955
 956   // Consider a large cache: a cell stores the upper 18 bits of the hash
 957   // (h >> 14). If the table is say 8 times the original size (growing from 4x),
 958   // the bit that we are interested in would be the 3rd bit of the stored value,
 959   // in other words 'multiplier' >> 1.
 960   uint32 new_bit = (1 << extra_bits_) >> 1;
 961
 962   scoped_ptr<IndexBucket[]> old_main_table;
 963   IndexBucket* source_table = main_table_;
 964   bool upgrade_format = !extra_bits_;
 965   if (upgrade_format) {
 966     // This method should deal with migrating a small table to a big one. Given
 967     // that the first thing to do is read the old table, set small_table_ for
 968     // the size of the old table. Now, when moving a cell, the result cannot be
 969     // placed in the old table or we will end up reading it again and attempting
 970     // to move it, so we have to copy the whole table at once.
 971     DCHECK(!small_table_);
 972     small_table_ = true;
 973     old_main_table.reset(new IndexBucket[max_hash]);
 974     memcpy(old_main_table.get(), main_table_, max_hash * sizeof(IndexBucket));
 975     memset(main_table_, 0, max_hash * sizeof(IndexBucket));
 976     source_table = old_main_table.get();
 977   }
 978
 979   for (int i = 0; i < max_hash; i++) {
 980     int bucket_num = i;
 981     IndexBucket* bucket = &source_table[i];
 982     do {
 983       for (int j = 0; j < kCellsPerBucket; j++) {
 984         IndexCell& current_cell = bucket->cells[j];
 985         if (!GetLocation(current_cell))
 986           continue;
 987         DCHECK(SanityCheck(current_cell));
 988         if (bucket_num == i) {
 989           if (upgrade_format || (GetHashValue(current_cell) & new_bit)) {
 990             // Move this cell to the upper half of the table.
 991             MoveSingleCell(&current_cell, bucket_num * kCellsPerBucket + j, i,
 992                            true);
 993           }
 994         } else {
 995           // All cells on extra buckets have to move.
 996           MoveSingleCell(&current_cell, bucket_num * kCellsPerBucket + j, i,
 997                          true);
 998         }
 999       }
1000
1001       // There is no need to clear the old bucket->next value because if falls
1002       // within the main table so it will be fixed when attempting to follow
1003       // the link.
1004       bucket_num = GetNextBucket(max_hash, max_bucket, old_extra_table,
1005                                  &bucket);
1006     } while (bucket_num);
1007   }
1008
1009   DCHECK_EQ(header()->used_cells, used_cells);
1010
1011   if (upgrade_format) {
1012     small_table_ = false;
1013     header()->flags &= ~SMALL_CACHE;
1014   }
1015 }
1016
1017 void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_num,
1018                                 int main_table_index, bool growing) {
1019   uint32 hash = GetFullHash(*current_cell, main_table_index);
1020   EntryCell old_cell(cell_num, hash, *current_cell, small_table_);
1021
1022   // This method may be called when moving entries from a small table to a
1023   // normal table. In that case, the caller (MoveCells) has to read the old
1024   // table, so it needs small_table_ set to true, but this method needs to
1025   // write to the new table so small_table_ has to be set to false, and the
1026   // value restored to true before returning.
1027   bool upgrade_format = !extra_bits_ && growing;
1028   if (upgrade_format)
1029     small_table_ = false;
1030   EntryCell new_cell = CreateEntryCell(hash, old_cell.GetAddress());
1031
1032   if (!new_cell.IsValid()) {
1033     // We'll deal with this entry later.
1034     if (upgrade_format)
1035       small_table_ = true;
1036     return;
1037   }
1038
1039   new_cell.SetState(old_cell.GetState());
1040   new_cell.SetGroup(old_cell.GetGroup());
1041   new_cell.SetReuse(old_cell.GetReuse());
1042   new_cell.SetTimestamp(old_cell.GetTimestamp());
1043   Save(&new_cell);
1044   modified_ = true;
1045   if (upgrade_format)
1046     small_table_ = true;
1047
1048   if (old_cell.GetState() == ENTRY_DELETED) {
1049     bitmap_->Set(new_cell.cell_num(), false);
1050     backup_bitmap_->Set(new_cell.cell_num(), false);
1051   }
1052
1053   if (!growing || cell_num / kCellsPerBucket == main_table_index) {
1054     // Only delete entries that live on the main table.
1055     if (!upgrade_format) {
1056       old_cell.Clear();
1057       Write(old_cell);
1058     }
1059
1060     if (cell_num != new_cell.cell_num()) {
1061       bitmap_->Set(old_cell.cell_num(), false);
1062       backup_bitmap_->Set(old_cell.cell_num(), false);
1063     }
1064   }
1065   header()->used_cells--;
1066 }
1067
1068 void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_num,
1069                                      int main_table_index) {
1070   NOTREACHED();  // No unit tests yet.
1071
1072   // The cell may be misplaced, or a duplicate cell exists with this data.
1073   uint32 hash = GetFullHash(*current_cell, main_table_index);
1074   MoveSingleCell(current_cell, cell_num, main_table_index, false);
1075
1076   // Now look for a duplicate cell.
1077   CheckBucketList(hash & mask_);
1078 }
1079
1080 void IndexTable::CheckBucketList(int bucket_num) {
1081   typedef std::pair<int, EntryGroup> AddressAndGroup;
1082   std::set<AddressAndGroup> entries;
1083   IndexBucket* bucket = &main_table_[bucket_num];
1084   int bucket_hash = bucket_num;
1085   do {
1086     for (int i = 0; i < kCellsPerBucket; i++) {
1087       IndexCell* current_cell = &bucket->cells[i];
1088       if (!GetLocation(*current_cell))
1089         continue;
1090       if (!SanityCheck(*current_cell)) {
1091         NOTREACHED();
1092         current_cell->Clear();
1093         continue;
1094       }
1095       int cell_num = bucket_num * kCellsPerBucket + i;
1096       EntryCell cell(cell_num, GetFullHash(*current_cell, bucket_hash),
1097                      *current_cell, small_table_);
1098       if (!entries.insert(std::make_pair(cell.GetAddress().value(),
1099                                          cell.GetGroup())).second) {
1100         current_cell->Clear();
1101         continue;
1102       }
1103       CheckState(cell);
1104     }
1105
1106     bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
1107                               &bucket);
1108   } while (bucket_num);
1109 }
1110
1111 uint32 IndexTable::GetLocation(const IndexCell& cell) {
1112   if (small_table_)
1113     return GetCellSmallTableLocation(cell);
1114
1115   return GetCellLocation(cell);
1116 }
1117
1118 uint32 IndexTable::GetHashValue(const IndexCell& cell) {
1119   if (small_table_)
1120     return GetCellSmallTableId(cell);
1121
1122   return GetCellId(cell);
1123 }
1124
1125 uint32 IndexTable::GetFullHash(const IndexCell& cell, uint32 lower_part) {
1126   // It is OK for the high order bits of lower_part to overlap with the stored
1127   // part of the hash.
1128   if (small_table_)
1129     return (GetCellSmallTableId(cell) << kSmallTableHashShift) | lower_part;
1130
1131   return (GetCellId(cell) << kHashShift) | lower_part;
1132 }
1133
1134 // All the bits stored in the cell should match the provided hash.
1135 bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) {
1136   hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift;
1137   return GetHashValue(cell) == hash;
1138 }
1139
1140 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32 hash) {
1141   if (!extra_bits_)
1142     return false;
1143
1144   uint32 mask = (1 << extra_bits_) - 1;
1145   hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift;
1146   return (GetHashValue(cell) & mask) != (hash & mask);
1147 }
1148
1149 }  // namespace disk_cache