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