| 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 <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.get(), 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master