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
16using base::Time;
17using base::TimeDelta;
18using disk_cache::CellInfo;
19using disk_cache::CellList;
20using disk_cache::IndexCell;
21using disk_cache::IndexIterator;
22
23namespace {
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.
27const uint64 kCellLocationMask = (1 << 22) - 1;
28const uint64 kCellIdMask = (1 << 18) - 1;
29const uint64 kCellTimestampMask = (1 << 20) - 1;
30const uint64 kCellReuseMask = (1 << 4) - 1;
31const uint8 kCellStateMask = (1 << 3) - 1;
32const uint8 kCellGroupMask = (1 << 3) - 1;
33const uint8 kCellSumMask = (1 << 2) - 1;
34
35const uint64 kCellSmallTableLocationMask = (1 << 16) - 1;
36const uint64 kCellSmallTableIdMask = (1 << 24) - 1;
37
38const int kCellIdOffset = 22;
39const int kCellTimestampOffset = 40;
40const int kCellReuseOffset = 60;
41const int kCellGroupOffset = 3;
42const int kCellSumOffset = 6;
43
44const 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.
48const int kHashShift = 14;
49const 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.
58const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1;
59const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1;
60const int kMaxLocation = 1 << 22;
61const int kMinFileNumber = 1 << 16;
62
63uint32 GetCellLocation(const IndexCell& cell) {
64  return cell.first_part & kCellLocationMask;
65}
66
67uint32 GetCellSmallTableLocation(const IndexCell& cell) {
68  return cell.first_part & kCellSmallTableLocationMask;
69}
70
71uint32 GetCellId(const IndexCell& cell) {
72  return (cell.first_part >> kCellIdOffset) & kCellIdMask;
73}
74
75uint32 GetCellSmallTableId(const IndexCell& cell) {
76  return (cell.first_part >> kCellSmallTableIdOffset) &
77         kCellSmallTableIdMask;
78}
79
80int GetCellTimestamp(const IndexCell& cell) {
81  return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask;
82}
83
84int GetCellReuse(const IndexCell& cell) {
85  return (cell.first_part >> kCellReuseOffset) & kCellReuseMask;
86}
87
88int GetCellState(const IndexCell& cell) {
89  return cell.last_part & kCellStateMask;
90}
91
92int GetCellGroup(const IndexCell& cell) {
93  return (cell.last_part >> kCellGroupOffset) & kCellGroupMask;
94}
95
96int GetCellSum(const IndexCell& cell) {
97  return (cell.last_part >> kCellSumOffset) & kCellSumMask;
98}
99
100void 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
106void 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
112void 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
118void 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
124void 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
131void 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
138void SetCellState(IndexCell* cell, disk_cache::EntryState state) {
139  cell->last_part &= ~kCellStateMask;
140  cell->last_part |= state;
141}
142
143void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) {
144  cell->last_part &= ~(kCellGroupMask << kCellGroupOffset);
145  cell->last_part |= group << kCellGroupOffset;
146}
147
148void 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.
157int 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
168bool 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
181int FileNumberFromLocation(int location) {
182  return location / kMinFileNumber;
183}
184
185int StartBlockFromLocation(int location) {
186  return location % kMinFileNumber;
187}
188
189bool 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
199bool 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
207inline 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.
231void 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
253void InitIterator(IndexIterator* iterator) {
254  iterator->cells.clear();
255  iterator->timestamp = iterator->forward ? kint32max : 0;
256}
257
258}  // namespace
259
260namespace disk_cache {
261
262EntryCell::~EntryCell() {
263}
264
265bool 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.
273Addr 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
287EntryState EntryCell::GetState() const {
288  return static_cast<EntryState>(GetCellState(cell_));
289}
290
291EntryGroup EntryCell::GetGroup() const {
292  return static_cast<EntryGroup>(GetCellGroup(cell_));
293}
294
295int EntryCell::GetReuse() const {
296  return GetCellReuse(cell_);
297}
298
299int EntryCell::GetTimestamp() const {
300  return GetCellTimestamp(cell_);
301}
302
303void EntryCell::SetState(EntryState state) {
304  SetCellState(&cell_, state);
305}
306
307void EntryCell::SetGroup(EntryGroup group) {
308  SetCellGroup(&cell_, group);
309}
310
311void EntryCell::SetReuse(int count) {
312  SetCellReuse(&cell_, count);
313}
314
315void EntryCell::SetTimestamp(int timestamp) {
316  SetCellTimestamp(&cell_, timestamp);
317}
318
319// Static.
320EntryCell 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
333void EntryCell::SerializaForTest(IndexCell* destination) {
334  FixSum();
335  Serialize(destination);
336}
337
338EntryCell::EntryCell() : cell_num_(0), hash_(0), small_table_(false) {
339  cell_.Clear();
340}
341
342EntryCell::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
366EntryCell::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
376void EntryCell::FixSum() {
377  SetCellSum(&cell_, CalculateCellSum(cell_));
378}
379
380uint32 EntryCell::GetLocation() const {
381  if (small_table_)
382    return GetCellSmallTableLocation(cell_);
383
384  return GetCellLocation(cell_);
385}
386
387uint32 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
399void EntryCell::Serialize(IndexCell* destination) const {
400  *destination = cell_;
401}
402
403EntrySet::EntrySet() : evicted_count(0), current(0) {
404}
405
406EntrySet::~EntrySet() {
407}
408
409IndexIterator::IndexIterator() {
410}
411
412IndexIterator::~IndexIterator() {
413}
414
415IndexTableInitData::IndexTableInitData() {
416}
417
418IndexTableInitData::~IndexTableInitData() {
419}
420
421// -----------------------------------------------------------------------
422
423IndexTable::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
432IndexTable::~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.
457void 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
557void 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.
577EntrySet 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
614EntryCell 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
668EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) {
669  return FindEntryCellImpl(hash, address, false);
670}
671
672int IndexTable::CalculateTimestamp(Time time) {
673  TimeDelta delta = time - Time::FromInternalValue(header_->base_time);
674  return std::max(delta.InMinutes(), 0);
675}
676
677base::Time IndexTable::TimeFromTimestamp(int timestamp) {
678  return Time::FromInternalValue(header_->base_time) +
679         TimeDelta::FromMinutes(timestamp);
680}
681
682void 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
730void 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
753void IndexTable::Save(EntryCell* cell) {
754  cell->FixSum();
755  Write(*cell);
756}
757
758void 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
771bool 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
779void 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.get(), num_bytes);
790  modified_ = false;
791}
792
793// -----------------------------------------------------------------------
794
795EntryCell 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
824void 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
847void 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
865int 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
882void 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
908void 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".
950void 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
1017void 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
1068void 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
1080void 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
1111uint32 IndexTable::GetLocation(const IndexCell& cell) {
1112  if (small_table_)
1113    return GetCellSmallTableLocation(cell);
1114
1115  return GetCellLocation(cell);
1116}
1117
1118uint32 IndexTable::GetHashValue(const IndexCell& cell) {
1119  if (small_table_)
1120    return GetCellSmallTableId(cell);
1121
1122  return GetCellId(cell);
1123}
1124
1125uint32 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.
1135bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) {
1136  hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift;
1137  return GetHashValue(cell) == hash;
1138}
1139
1140bool 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
1150