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_ = ¶ms->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(¤t_cell, bucket_num * kCellsPerBucket + j, i, 992 true); 993 } 994 } else { 995 // All cells on extra buckets have to move. 996 MoveSingleCell(¤t_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 1150