Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(202)

Side by Side Diff: net/disk_cache/v3/index_table.cc

Issue 53313004: Disk cache v3: The main index table. (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src/
Patch Set: Created 7 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
Property Changes:
Added: svn:eol-style
+ LF
OLDNEW
(Empty)
1 // Copyright (c) 2013 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/v3/index_table.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 const uint32 kMaxAddress = 1 << 22;
26
27 const int kCellHashOffset = 22;
28 const int kCellSmallTableHashOffset = 16;
29 const int kCellTimestampOffset = 40;
30 const int kCellReuseOffset = 60;
31 const int kCellGroupOffset = 3;
32 const int kCellSumOffset = 6;
33
34 const uint64 kCellAddressMask = 0x3FFFFF;
35 const uint64 kCellSmallTableAddressMask = 0xFFFF;
36 const uint64 kCellHashMask = 0x3FFFF;
37 const uint64 kCellSmallTableHashMask = 0xFFFFFF;
38 const uint64 kCellTimestampMask = 0xFFFFF;
39 const uint64 kCellReuseMask = 0xF;
40 const uint8 kCellStateMask = 0x7;
41 const uint8 kCellGroupMask = 0x7;
42 const uint8 kCellSumMask = 0x3;
43
44 const int kHashShift = 14;
45 const int kHashSmallTableShift = 8;
46
47 // Unfortunately we have to break the abstaction a little here: the file number
48 // where entries are stored is outside of the control of this code, and it is
49 // usually part of the stored address. However, for small tables we only store
50 // 16 bits of the address so the file number is never stored on a cell. We have
51 // to infere the file number from the type of entry (normal vs evicted), and
52 // the knowledge that given that the table will not keep more than 64k entries,
53 // a single file of each type is enough.
54 const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1;
55 const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1;
56
57 uint32 GetCellAddress(const IndexCell& cell) {
58 return cell.first_part & kCellAddressMask;
59 }
60
61 uint32 GetCellSmallTableAddress(const IndexCell& cell) {
62 return cell.first_part & kCellSmallTableAddressMask;
63 }
64
65 uint32 GetCellHash(const IndexCell& cell) {
66 return (cell.first_part >> kCellHashOffset) & kCellHashMask;
67 }
68
69 uint32 GetCellSmallTableHash(const IndexCell& cell) {
70 return (cell.first_part >> kCellSmallTableHashOffset) &
71 kCellSmallTableHashMask;
72 }
73
74 int GetCellTimestamp(const IndexCell& cell) {
75 return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask;
76 }
77
78 int GetCellReuse(const IndexCell& cell) {
79 return (cell.first_part >> kCellReuseOffset) & kCellReuseMask;
80 }
81
82 int GetCellState(const IndexCell& cell) {
83 return cell.last_part & kCellStateMask;
84 }
85
86 int GetCellGroup(const IndexCell& cell) {
87 return (cell.last_part >> kCellGroupOffset) & kCellGroupMask;
88 }
89
90 int GetCellSum(const IndexCell& cell) {
91 return (cell.last_part >> kCellSumOffset) & kCellSumMask;
92 }
93
94 void SetCellAddress(IndexCell* cell, uint32 address) {
95 DCHECK_LE(address, static_cast<uint32>(kCellAddressMask));
96 cell->first_part &= ~kCellAddressMask;
97 cell->first_part |= address;
98 }
99
100 void SetCellSmallTableAddress(IndexCell* cell, uint32 address) {
101 DCHECK_LE(address, static_cast<uint32>(kCellSmallTableAddressMask));
102 cell->first_part &= ~kCellSmallTableAddressMask;
103 cell->first_part |= address;
104 }
105
106 void SetCellHash(IndexCell* cell, uint32 hash) {
107 DCHECK_LE(hash, static_cast<uint32>(kCellHashMask));
108 cell->first_part &= ~(kCellHashMask << kCellHashOffset);
109 cell->first_part |= static_cast<int64>(hash) << kCellHashOffset;
110 }
111
112 void SetCellSmallTableHash(IndexCell* cell, uint32 hash) {
113 DCHECK_LE(hash, static_cast<uint32>(kCellSmallTableHashMask));
114 cell->first_part &= ~(kCellSmallTableHashMask << kCellSmallTableHashOffset);
115 cell->first_part |= static_cast<int64>(hash) << kCellSmallTableHashOffset;
116 }
117
118 void SetCellTimestamp(IndexCell* cell, int timestamp) {
119 DCHECK_LT(timestamp, 1 << 20);
120 DCHECK_GE(timestamp, 0);
121 cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset);
122 cell->first_part |= static_cast<int64>(timestamp) << kCellTimestampOffset;
123 }
124
125 void SetCellReuse(IndexCell* cell, int count) {
126 DCHECK_LT(count, 16);
127 DCHECK_GE(count, 0);
128 cell->first_part &= ~(kCellReuseMask << kCellReuseOffset);
129 cell->first_part |= static_cast<int64>(count) << kCellReuseOffset;
130 }
131
132 void SetCellState(IndexCell* cell, disk_cache::EntryState state) {
133 cell->last_part &= ~kCellStateMask;
134 cell->last_part |= state;
135 }
136
137 void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) {
138 cell->last_part &= ~(kCellGroupMask << kCellGroupOffset);
139 cell->last_part |= group << kCellGroupOffset;
140 }
141
142 void SetCellSum(IndexCell* cell, int sum) {
143 DCHECK_LT(sum, 4);
144 DCHECK_GE(sum, 0);
145 cell->last_part &= ~(kCellSumMask << kCellSumOffset);
146 cell->last_part |= sum << kCellSumOffset;
147 }
148
149 // This is a very particular way to calculate the sum, so it will not match if
150 // compared a gainst a pure 2 bit, modulo 2 sum.
151 int CalculateCellSum(const IndexCell& cell) {
152 uint32* words = bit_cast<uint32*>(&cell);
153 uint8* bytes = bit_cast<uint8*>(&cell);
154 uint32 result = words[0] + words[1];
155 result += result >> 16;
156 result += (result >> 8) + (bytes[8] & 0x3f);
157 result += result >> 4;
158 result += result >> 2;
159 return result & 3;
160 }
161
162 bool SanityCheck(const IndexCell& cell) {
163 if (GetCellSum(cell) != CalculateCellSum(cell))
164 return false;
165
166 if (GetCellState(cell) > disk_cache::ENTRY_USED ||
167 GetCellGroup(cell) == disk_cache::ENTRY_RESERVED ||
168 GetCellGroup(cell) > disk_cache::ENTRY_EVICTED) {
169 return false;
170 }
171
172 return true;
173 }
174
175 bool IsValidAddress(disk_cache::Addr address) {
176 if (!address.is_initialized() ||
177 (address.file_type() != disk_cache::BLOCK_EVICTED &&
178 address.file_type() != disk_cache::BLOCK_ENTRIES)) {
179 return false;
180 }
181
182 return address.ToIndexEntryAddress() < kMaxAddress;
183 }
184
185 bool IsNormalState(const IndexCell& cell) {
186 disk_cache::EntryState state =
187 static_cast<disk_cache::EntryState>(GetCellState(cell));
188 DCHECK_NE(state, disk_cache::ENTRY_FREE);
189 return state != disk_cache::ENTRY_DELETED &&
190 state != disk_cache::ENTRY_FIXING;
191 }
192
193 inline int GetNextBucket(int min_bucket_id, int max_bucket_id,
194 disk_cache::IndexBucket* table,
195 disk_cache::IndexBucket** bucket) {
196 if (!(*bucket)->next)
197 return 0;
198
199 int bucket_id = (*bucket)->next / disk_cache::kCellsPerBucket;
200 if (bucket_id < min_bucket_id || bucket_id > max_bucket_id) {
201 (*bucket)->next = 0;
202 return 0;
203 }
204 *bucket = &table[bucket_id - min_bucket_id];
205 return bucket_id;
206 }
207
208 void UpdateListWithCell(int bucket_hash,
209 const disk_cache::EntryCell& cell,
210 CellList* list,
211 int* list_time) {
212 if (!list)
213 return;
214
215 int time = cell.GetTimestamp();
216 if (time < *list_time) {
217 *list_time = time;
218 list->clear();
219 }
220 if (time == *list_time) {
221 CellInfo cell_info = { cell.hash(), cell.GetAddress() };
222 list->push_back(cell_info);
223 }
224 }
225
226 } // namespace
227
228 namespace disk_cache {
229
230 EntryCell::~EntryCell() {
231 }
232
233 bool EntryCell::IsValid() const {
234 return GetCellAddress(cell_) != 0;
235 }
236
237 Addr EntryCell::GetAddress() const {
238 uint32 address_value = GetAddressValue();
239 if (small_table_) {
240 if (GetGroup() == ENTRY_EVICTED)
241 return Addr(BLOCK_EVICTED, 1, kEvictedEntriesFile, address_value);
242
243 return Addr(BLOCK_ENTRIES, 1, kEntriesFile, address_value);
244 }
245
246 if (GetGroup() == ENTRY_EVICTED)
247 return Addr::FromEvictedAddress(address_value);
248 else
249 return Addr::FromEntryAddress(address_value);
250 }
251
252 EntryState EntryCell::GetState() const {
253 return static_cast<EntryState>(cell_.last_part & kCellStateMask);
254 }
255
256 EntryGroup EntryCell::GetGroup() const {
257 return static_cast<EntryGroup>((cell_.last_part >> kCellGroupOffset) &
258 kCellGroupMask);
259 }
260
261 int EntryCell::GetReuse() const {
262 return (cell_.first_part >> kCellReuseOffset) & kCellReuseMask;
263 }
264
265 int EntryCell::GetTimestamp() const {
266 return GetCellTimestamp(cell_);
267 }
268
269 void EntryCell::SetState(EntryState state) {
270 SetCellState(&cell_, state);
271 }
272
273 void EntryCell::SetGroup(EntryGroup group) {
274 SetCellGroup(&cell_, group);
275 }
276
277 void EntryCell::SetReuse(int count) {
278 SetCellReuse(&cell_, count);
279 }
280
281 void EntryCell::SetTimestamp(int timestamp) {
282 SetCellTimestamp(&cell_, timestamp);
283 }
284
285 // Static.
286 EntryCell EntryCell::GetEntryCellForTest(int32 cell_id,
287 uint32 hash,
288 Addr address,
289 IndexCell* cell,
290 bool small_table) {
291 if (cell) {
292 EntryCell entry_cell(cell_id, hash, *cell, small_table);
293 return entry_cell;
294 }
295
296 return EntryCell(cell_id, hash, address, small_table);
297 }
298
299 void EntryCell::SerializaForTest(IndexCell* destination) {
300 FixSum();
301 Serialize(destination);
302 }
303
304 EntryCell::EntryCell() : cell_id_(0), hash_(0), small_table_(false) {
305 cell_.Clear();
306 }
307
308 EntryCell::EntryCell(int32 cell_id, uint32 hash, Addr address, bool small_table)
309 : cell_id_(cell_id),
310 hash_(hash),
311 small_table_(small_table) {
312 DCHECK(IsValidAddress(address) || !address.value());
313
314 cell_.Clear();
315 SetCellState(&cell_, ENTRY_NEW);
316 SetCellGroup(&cell_, ENTRY_NO_USE);
317 if (small_table) {
318 DCHECK(address.FileNumber() == kEntriesFile ||
319 address.FileNumber() == kEvictedEntriesFile);
320 SetCellSmallTableAddress(&cell_, address.start_block());
321 SetCellSmallTableHash(&cell_, hash >> kHashSmallTableShift);
322 } else {
323 SetCellAddress(&cell_, address.ToIndexEntryAddress());
324 SetCellHash(&cell_, hash >> kHashShift);
325 }
326 }
327
328 EntryCell::EntryCell(int32 cell_id,
329 uint32 hash,
330 const IndexCell& cell,
331 bool small_table)
332 : cell_id_(cell_id),
333 hash_(hash),
334 cell_(cell),
335 small_table_(small_table) {
336 }
337
338 void EntryCell::FixSum() {
339 SetCellSum(&cell_, CalculateCellSum(cell_));
340 }
341
342 uint32 EntryCell::GetAddressValue() const {
343 if (small_table_)
344 return GetCellSmallTableAddress(cell_);
345
346 return GetCellAddress(cell_);
347 }
348
349 uint32 EntryCell::RecomputeHash() {
350 if (small_table_) {
351 hash_ &= (1 << kHashSmallTableShift) - 1;
352 hash_ |= GetCellSmallTableHash(cell_) << kHashSmallTableShift;
353 return hash_;
354 }
355
356 hash_ &= (1 << kHashShift) - 1;
357 hash_ |= GetCellHash(cell_) << kHashShift;
358 return hash_;
359 }
360
361 void EntryCell::Serialize(IndexCell* destination) const {
362 memcpy(destination, &cell_, sizeof(cell_));
363 }
364
365 EntrySet::EntrySet() : evicted_count(0), current(0) {
366 }
367
368 // -----------------------------------------------------------------------
369
370 IndexTable::IndexTable(IndexTableBackend* backend)
371 : backend_(backend),
372 header_(NULL),
373 main_table_(NULL),
374 extra_table_(NULL),
375 modified_(false),
376 small_table_(false) {
377 }
378
379 void IndexTable::Init(IndexTableInitData* params) {
380 bool growing = header_ != NULL;
381 scoped_ptr<IndexBucket[]> old_extra_table;
382 header_ = &params->index_bitmap->header;
383
384 if (params->main_table) {
385 if (main_table_) {
386 DCHECK_EQ(base::bits::Log2Floor(header_->table_len),
387 base::bits::Log2Floor(backup_header_->table_len) + 1);
388 int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket;
389 DCHECK_GE(extra_size, 0);
390 old_extra_table.reset(new IndexBucket[extra_size]);
391 memcpy(old_extra_table.get(), extra_table_,
392 extra_size * sizeof(IndexBucket));
393 memset(params->extra_table, 0, extra_size * sizeof(IndexBucket));
394 }
395 main_table_ = params->main_table;
396 }
397 DCHECK(main_table_);
398 extra_table_ = params->extra_table;
399
400 extra_bits_ = base::bits::Log2Floor(header_->table_len) -
401 base::bits::Log2Floor(kBaseTableLen);
402 DCHECK_GE(extra_bits_, 0);
403 DCHECK_LE(extra_bits_, 11);
404 mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1;
405 small_table_ = extra_bits_ < kHashShift - kHashSmallTableShift;
406 if (!small_table_)
407 extra_bits_ -= kHashShift - kHashSmallTableShift;
408
409 int num_words = (header_->table_len + 31) / 32;
410
411 if (old_extra_table) {
412 // All the cells from the extra table are moving to the new tables so before
413 // creating the bitmaps, clear the part of the extra table.
414 int main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32;
415 DCHECK_GT(num_words, main_table_bit_words);
416 memset(params->index_bitmap->bitmap + main_table_bit_words, 0,
417 (num_words - main_table_bit_words) * sizeof(int32));
418
419 DCHECK(growing);
420 int old_num_words = (backup_header_.get()->table_len + 31) / 32;
421 DCHECK_GT(old_num_words, main_table_bit_words);
422 memset(backup_bitmap_storage_.get() + main_table_bit_words, 0,
423 (old_num_words - main_table_bit_words) * sizeof(int32));
424 }
425 bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len,
426 num_words));
427
428 if (growing) {
429 int old_num_words = (backup_header_.get()->table_len + 31) / 32;
430 DCHECK_GE(num_words, old_num_words);
431 scoped_ptr<uint32[]> storage(new uint32[num_words]);
432 memcpy(storage.get(), backup_bitmap_storage_.get(),
433 old_num_words * sizeof(int32));
434 memset(storage.get() + old_num_words, 0,
435 (num_words - old_num_words) * sizeof(int32));
436
437 backup_bitmap_storage_.swap(storage);
438 backup_header_->table_len = header_->table_len;
439 } else {
440 backup_bitmap_storage_.reset(params->backup_bitmap.release());
441 backup_header_.reset(params->backup_header.release());
442 }
443
444 num_words = (backup_header_->table_len + 31) / 32;
445 backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(),
446 backup_header_->table_len, num_words));
447 if (old_extra_table)
448 MoveCells(old_extra_table.get());
449
450 if (small_table_)
451 DCHECK(header_->flags & SMALL_CACHE);
452 }
453
454 void IndexTable::Reset() {
455 header_ = NULL;
456 main_table_ = NULL;
457 extra_table_ = NULL;
458 bitmap_.reset();
459 backup_bitmap_.reset();
460 backup_header_.reset();
461 backup_bitmap_storage_.reset();
462 modified_ = false;
463 }
464
465 EntrySet IndexTable::LookupEntry(uint32 hash) {
466 EntrySet entries;
467 int bucket_id = static_cast<int>(hash & mask_);
468 IndexBucket* bucket = &main_table_[bucket_id];
469 for (;;) {
470 for (int i = 0; i < kCellsPerBucket; i++) {
471 IndexCell* current_cell = &bucket->cells[i];
472 if (!GetAddressValue(*current_cell))
473 continue;
474 if (!SanityCheck(*current_cell)) {
475 NOTREACHED();
476 int cell_id = bucket_id * kCellsPerBucket + i;
477 current_cell->Clear();
478 bitmap_->Set(cell_id, false);
479 backup_bitmap_->Set(cell_id, false);
480 modified_ = true;
481 continue;
482 }
483 int cell_id = bucket_id * kCellsPerBucket + i;
484 if (MisplacedHash(*current_cell, hash)) {
485 HandleMisplacedCell(current_cell, cell_id, hash & mask_);
486 } else if (IsHashMatch(*current_cell, hash)) {
487 EntryCell entry_cell(cell_id, hash, *current_cell, small_table_);
488 CheckState(entry_cell);
489 if (entry_cell.GetState() != ENTRY_DELETED) {
490 entries.cells.push_back(entry_cell);
491 if (entry_cell.GetGroup() == ENTRY_EVICTED)
492 entries.evicted_count++;
493 }
494 }
495 }
496 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
497 &bucket);
498 if (!bucket_id)
499 break;
500 }
501 return entries;
502 }
503
504 EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) {
505 DCHECK(IsValidAddress(address));
506 DCHECK(address.ToIndexEntryAddress());
507
508 int bucket_id = static_cast<int>(hash & mask_);
509 int cell_id = 0;
510 IndexBucket* bucket = &main_table_[bucket_id];
511 IndexCell* current_cell = NULL;
512 bool found = false;
513 for (; !found;) {
514 for (int i = 0; i < kCellsPerBucket && !found; i++) {
515 current_cell = &bucket->cells[i];
516 if (!GetAddressValue(*current_cell)) {
517 cell_id = bucket_id * kCellsPerBucket + i;
518 found = true;
519 }
520 }
521 if (found)
522 break;
523 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
524 &bucket);
525 if (!bucket_id)
526 break;
527 }
528
529 if (!found) {
530 bucket_id = NewExtraBucket();
531 if (bucket_id) {
532 cell_id = bucket_id * kCellsPerBucket;
533 bucket->next = cell_id;
534 bucket = &extra_table_[bucket_id - (mask_ + 1)];
535 bucket->hash = hash & mask_;
536 found = true;
537 } else {
538 // address 0 is a reserved value, and the caller interprets it as invalid.
539 address.set_value(0);
540 }
541 }
542
543 EntryCell entry_cell(cell_id, hash, address, small_table_);
544 if (address.file_type() == BLOCK_EVICTED)
545 entry_cell.SetGroup(ENTRY_EVICTED);
546 else
547 entry_cell.SetGroup(ENTRY_NO_USE);
548 Save(&entry_cell);
549
550 if (found) {
551 bitmap_->Set(cell_id, true);
552 backup_bitmap_->Set(cell_id, true);
553 header()->used_cells++;
554 modified_ = true;
555 }
556
557 return entry_cell;
558 }
559
560 EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) {
561 return FindEntryCellImpl(hash, address, false);
562 }
563
564 int IndexTable::CalculateTimestamp(Time time) {
565 TimeDelta delta = time - Time::FromInternalValue(header_->base_time);
566 return std::max(delta.InMinutes(), 0);
567 }
568
569 void IndexTable::SetSate(uint32 hash, Addr address, EntryState state) {
570 EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE);
571 if (!cell.IsValid()) {
572 NOTREACHED();
573 return;
574 }
575
576 EntryState old_state = cell.GetState();
577 if (state == ENTRY_FREE) {
578 DCHECK_EQ(old_state, ENTRY_DELETED);
579 } else if (state == ENTRY_NEW) {
580 DCHECK_EQ(old_state, ENTRY_FREE);
581 } else if (state == ENTRY_OPEN) {
582 DCHECK_EQ(old_state, ENTRY_USED);
583 } else if (state == ENTRY_MODIFIED) {
584 DCHECK_EQ(old_state, ENTRY_OPEN);
585 } else if (state == ENTRY_DELETED) {
586 DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
587 old_state == ENTRY_MODIFIED);
588 } else if (state == ENTRY_USED) {
589 DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN ||
590 old_state == ENTRY_MODIFIED);
591 }
592
593 modified_ = true;
594 if (state == ENTRY_DELETED) {
595 bitmap_->Set(cell.cell_id(), false);
596 backup_bitmap_->Set(cell.cell_id(), false);
597 } else if (state == ENTRY_FREE) {
598 cell.Clear();
599 Write(cell);
600 header()->used_cells--;
601 return;
602 }
603 cell.SetState(state);
604
605 Save(&cell);
606 }
607
608 void IndexTable::UpdateTime(uint32 hash, Addr address, base::Time current) {
609 EntryCell cell = FindEntryCell(hash, address);
610 if (!cell.IsValid())
611 return;
612
613 int minutes = CalculateTimestamp(current);
614
615 // Keep about 3 months of headroom.
616 const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90;
617 if (minutes > kMaxTimestamp) {
618 // TODO(rvargas):
619 // Update header->old_time and trigger a timer
620 // Rebaseline timestamps and don't update sums
621 // Start a timer (about 2 backups)
622 // fix all ckecksums and trigger another timer
623 // update header->old_time because rebaseline is done.
624 minutes = std::min(minutes, (1 << 20) - 1);
625 }
626
627 cell.SetTimestamp(minutes);
628 Save(&cell);
629 }
630
631 void IndexTable::Save(EntryCell* cell) {
632 cell->FixSum();
633 Write(*cell);
634 }
635
636 void IndexTable::GetOldest(CellList* no_use, CellList* low_use,
637 CellList* high_use) {
638 header_->num_no_use_entries = 0;
639 header_->num_low_use_entries = 0;
640 header_->num_high_use_entries = 0;
641 header_->num_evicted_entries = 0;
642
643 int no_use_time = kint32max;
644 int low_use_time = kint32max;
645 int high_use_time = kint32max;
646 for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
647 int bucket_id = i;
648 IndexBucket* bucket = &main_table_[i];
649 for (;;) {
650 GetOldestFromBucket(bucket, i, no_use, &no_use_time, low_use,
651 &low_use_time, high_use, &high_use_time);
652
653 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
654 &bucket);
655 if (!bucket_id)
656 break;
657 }
658 }
659 header_->num_entries = header_->num_no_use_entries +
660 header_->num_low_use_entries +
661 header_->num_high_use_entries +
662 header_->num_evicted_entries;
663 modified_ = true;
664 }
665
666 bool IndexTable::GetNextCells(IndexIterator* iterator) {
667 int current_time = iterator->timestamp;
668 iterator->cells.clear();
669 iterator->timestamp = iterator->forward ? kint32max : 0;
670
671 for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) {
672 int bucket_id = i;
673 IndexBucket* bucket = &main_table_[i];
674 for (;;) {
675 GetNewestFromBucket(bucket, i, current_time, iterator);
676
677 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
678 &bucket);
679 if (!bucket_id)
680 break;
681 }
682 }
683 return !iterator->cells.empty();
684 }
685
686 void IndexTable::OnBackupTimer() {
687 if (!modified_)
688 return;
689
690 int num_words = (header_->table_len + 31) / 32;
691 int num_bytes = num_words * 4 + static_cast<int>(sizeof(*header_));
692 scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes));
693 memcpy(buffer->data(), header_, sizeof(*header_));
694 memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(),
695 num_words * 4);
696 backend_->SaveIndex(buffer, num_bytes);
697 modified_ = false;
698 }
699
700 // -----------------------------------------------------------------------
701
702 EntryCell IndexTable::FindEntryCellImpl(uint32 hash, Addr address,
703 bool allow_deleted) {
704 int bucket_id = static_cast<int>(hash & mask_);
705 IndexBucket* bucket = &main_table_[bucket_id];
706 for (;;) {
707 for (int i = 0; i < kCellsPerBucket; i++) {
708 IndexCell* current_cell = &bucket->cells[i];
709 if (!GetAddressValue(*current_cell))
710 continue;
711 DCHECK(SanityCheck(*current_cell));
712 if (IsHashMatch(*current_cell, hash)) {
713 // We have a match.
714 int cell_id = bucket_id * kCellsPerBucket + i;
715 EntryCell entry_cell(cell_id, hash, *current_cell, small_table_);
716 if (entry_cell.GetAddress() != address)
717 continue;
718
719 if (!allow_deleted && entry_cell.GetState() == ENTRY_DELETED)
720 continue;
721
722 return entry_cell;
723 }
724 }
725 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
726 &bucket);
727 if (!bucket_id)
728 break;
729 }
730 return EntryCell();
731 }
732
733 void IndexTable::CheckState(const EntryCell& cell) {
734 int current_state = cell.GetState();
735 if (current_state != ENTRY_FIXING) {
736 bool present = ((current_state & 3) != 0); // Look at the last two bits.
737 if (present != bitmap_->Get(cell.cell_id()) ||
738 present != backup_bitmap_->Get(cell.cell_id())) {
739 // There's a mismatch.
740 if (current_state == ENTRY_DELETED) {
741 // We were in the process of deleting this entry. Finish now.
742 backend_->DeleteCell(cell);
743 } else {
744 current_state = ENTRY_FIXING;
745 EntryCell bad_cell(cell);
746 bad_cell.SetState(ENTRY_FIXING);
747 Save(&bad_cell);
748 }
749 }
750 }
751
752 if (current_state == ENTRY_FIXING)
753 backend_->FixCell(cell);
754 }
755
756 void IndexTable::Write(const EntryCell& cell) {
757 IndexBucket* bucket = NULL;
758 int bucket_id = cell.cell_id() / kCellsPerBucket;
759 if (bucket_id < static_cast<int32>(mask_ + 1)) {
760 bucket = &main_table_[bucket_id];
761 } else {
762 DCHECK_LE(bucket_id, header()->max_bucket);
763 bucket = &extra_table_[bucket_id - (mask_ + 1)];
764 }
765
766 int cell_number = cell.cell_id() % kCellsPerBucket;
767 if (GetAddressValue(bucket->cells[cell_number]) && cell.GetAddressValue()) {
768 DCHECK_EQ(cell.GetAddressValue(),
769 GetAddressValue(bucket->cells[cell_number]));
770 }
771 cell.Serialize(&bucket->cells[cell_number]);
772 }
773
774 int IndexTable::NewExtraBucket() {
775 int safe_window = (header()->table_len < kNumExtraBlocks * 2) ?
776 kNumExtraBlocks / 4 : kNumExtraBlocks;
777 if (header()->table_len - header()->max_bucket * kCellsPerBucket <
778 safe_window) {
779 backend_->GrowIndex();
780 }
781
782 if (header()->max_bucket * kCellsPerBucket ==
783 header()->table_len - kCellsPerBucket) {
784 return 0;
785 }
786
787 header()->max_bucket++;
788 return header()->max_bucket;
789 }
790
791 void IndexTable::GetOldestFromBucket(IndexBucket* bucket, int bucket_hash,
792 CellList* no_use, int* no_use_time,
793 CellList* low_use, int* low_use_time,
794 CellList* high_use, int* high_use_time) {
795 for (int i = 0; i < kCellsPerBucket; i++) {
796 IndexCell& current_cell = bucket->cells[i];
797 if (!GetAddressValue(current_cell))
798 continue;
799 DCHECK(SanityCheck(current_cell));
800 if (!IsNormalState(current_cell))
801 continue;
802
803 EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
804 current_cell, small_table_);
805 switch (GetCellGroup(current_cell)) {
806 case ENTRY_NO_USE:
807 UpdateListWithCell(bucket_hash, entry_cell, no_use, no_use_time);
808 header_->num_no_use_entries++;
809 break;
810 case ENTRY_LOW_USE:
811 UpdateListWithCell(bucket_hash, entry_cell, low_use, low_use_time);
812 header_->num_low_use_entries++;
813 break;
814 case ENTRY_HIGH_USE:
815 UpdateListWithCell(bucket_hash, entry_cell, high_use, high_use_time);
816 header_->num_high_use_entries++;
817 break;
818 case ENTRY_EVICTED:
819 header_->num_evicted_entries++;
820 break;
821 default:
822 NOTREACHED();
823 }
824 }
825 }
826
827 void IndexTable::GetNewestFromBucket(IndexBucket* bucket,
828 int bucket_hash,
829 int limit_time,
830 IndexIterator* iterator) {
831 for (int i = 0; i < kCellsPerBucket; i++) {
832 IndexCell& current_cell = bucket->cells[i];
833 if (!GetAddressValue(current_cell))
834 continue;
835 DCHECK(SanityCheck(current_cell));
836 if (!IsNormalState(current_cell))
837 continue;
838
839 int time = GetCellTimestamp(current_cell);
840 switch (GetCellGroup(current_cell)) {
841 case disk_cache::ENTRY_NO_USE:
842 case disk_cache::ENTRY_LOW_USE:
843 case disk_cache::ENTRY_HIGH_USE:
844 if (iterator->forward && time <= limit_time)
845 continue;
846 if (!iterator->forward && time >= limit_time)
847 continue;
848
849 if ((iterator->forward && time < iterator->timestamp) ||
850 (!iterator->forward && time > iterator->timestamp)) {
851 iterator->timestamp = time;
852 iterator->cells.clear();
853 }
854 if (time == iterator->timestamp) {
855 EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash),
856 current_cell, small_table_);
857 CellInfo cell_info = {
858 entry_cell.hash(),
859 entry_cell.GetAddress()
860 };
861 iterator->cells.push_back(cell_info);
862 }
863 }
864 }
865 }
866
867 void IndexTable::MoveCells(IndexBucket* old_extra_table) {
868 int max_hash = (mask_ + 1) / 2;
869 int max_bucket = header()->max_bucket;
870 header()->max_bucket = mask_;
871 int used_cells = header()->used_cells;
872
873 // Consider a large cache: a cell stores the upper 18 bits of the hash
874 // (h >> 14). If the table is say 8 times the original size (growing from 4x),
875 // the bit that we are interested in would be the 3rd bit of the stored value,
876 // in other words 'multiplier' >> 1.
877 uint32 new_bit = (1 << extra_bits_) >> 1;
878
879 scoped_ptr<IndexBucket[]> old_main_table;
880 IndexBucket* source_table = main_table_;
881 bool upgrade_format = !extra_bits_;
882 if (upgrade_format) {
883 // This method should deal with migrating a small table to a big one. Given
884 // that the first thing to do is read the old table, set small_table_ for
885 // the size of the old table. Now, when moving a cell, the result cannot be
886 // placed in the old table or we will end up reading it again and attempting
887 // to move it, so we have to copy the whole table at once.
888 DCHECK(!small_table_);
889 small_table_ = true;
890 old_main_table.reset(new IndexBucket[max_hash]);
891 memcpy(old_main_table.get(), main_table_, max_hash * sizeof(IndexBucket));
892 memset(main_table_, 0, max_hash * sizeof(IndexBucket));
893 source_table = old_main_table.get();
894 }
895
896 for (int i = 0; i < max_hash; i++) {
897 int bucket_id = i;
898 IndexBucket* bucket = &source_table[i];
899 for (;;) {
900 for (int j = 0; j < kCellsPerBucket; j++) {
901 IndexCell& current_cell = bucket->cells[j];
902 if (!GetAddressValue(current_cell))
903 continue;
904 DCHECK(SanityCheck(current_cell));
905 if (bucket_id == i) {
906 if (upgrade_format || (GetHashValue(current_cell) & new_bit)) {
907 // Move this cell to the upper half of the table.
908 MoveSingleCell(&current_cell, bucket_id * kCellsPerBucket + j, i,
909 true);
910 }
911 } else {
912 // All cells on extra buckets have to move.
913 MoveSingleCell(&current_cell, bucket_id * kCellsPerBucket + j, i,
914 true);
915 }
916 }
917
918 bucket_id = GetNextBucket(max_hash, max_bucket, old_extra_table, &bucket);
919 if (!bucket_id)
920 break;
921 }
922 }
923
924 DCHECK_EQ(header()->used_cells, used_cells);
925
926 if (upgrade_format) {
927 small_table_ = false;
928 header()->flags &= ~SMALL_CACHE;
929 }
930 }
931
932 void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_id,
933 int main_table_index, bool growing) {
934 uint32 hash = GetFullHash(*current_cell, main_table_index);
935 EntryCell old_cell(cell_id, hash, *current_cell, small_table_);
936
937 bool upgrade_format = !extra_bits_ && growing;
938 if (upgrade_format)
939 small_table_ = false;
940 EntryCell new_cell = CreateEntryCell(hash, old_cell.GetAddress());
941
942 if (!new_cell.IsValid()) {
943 // We'll deal with this entry later.
944 if (upgrade_format)
945 small_table_ = true;
946 return;
947 }
948
949 new_cell.SetState(old_cell.GetState());
950 new_cell.SetGroup(old_cell.GetGroup());
951 new_cell.SetReuse(old_cell.GetReuse());
952 new_cell.SetTimestamp(old_cell.GetTimestamp());
953 Save(&new_cell);
954 modified_ = true;
955 if (upgrade_format)
956 small_table_ = true;
957
958 if (old_cell.GetState() == ENTRY_DELETED) {
959 bitmap_->Set(new_cell.cell_id(), false);
960 backup_bitmap_->Set(new_cell.cell_id(), false);
961 }
962
963 if (!growing || cell_id / kCellsPerBucket == main_table_index) {
964 // Only delete entries that live on the main table.
965 if (!upgrade_format) {
966 old_cell.Clear();
967 Write(old_cell);
968 }
969
970 if (cell_id != new_cell.cell_id()) {
971 bitmap_->Set(old_cell.cell_id(), false);
972 backup_bitmap_->Set(old_cell.cell_id(), false);
973 }
974 }
975 header()->used_cells--;
976 }
977
978 void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_id,
979 int main_table_index) {
980 // The cell may be misplaced, or a duplicate cell exists with this data.
981 uint32 hash = GetFullHash(*current_cell, main_table_index);
982 MoveSingleCell(current_cell, cell_id, main_table_index, false);
983
984 // Now look for a duplicate cell.
985 CheckBucketList(hash & mask_);
986 }
987
988 void IndexTable::CheckBucketList(int bucket_id) {
989 typedef std::pair<int, EntryGroup> AddressAndGroup;
990 std::set<AddressAndGroup> entries;
991 IndexBucket* bucket = &main_table_[bucket_id];
992 int bucket_hash = bucket_id;
993 for (;;) {
994 for (int i = 0; i < kCellsPerBucket; i++) {
995 IndexCell* current_cell = &bucket->cells[i];
996 if (!GetAddressValue(*current_cell))
997 continue;
998 if (!SanityCheck(*current_cell)) {
999 NOTREACHED();
1000 current_cell->Clear();
1001 continue;
1002 }
1003 int cell_id = bucket_id * kCellsPerBucket + i;
1004 EntryCell cell(cell_id, GetFullHash(*current_cell, bucket_hash),
1005 *current_cell, small_table_);
1006 if (!entries.insert(std::make_pair(cell.GetAddress().value(),
1007 cell.GetGroup())).second) {
1008 current_cell->Clear();
1009 continue;
1010 }
1011 CheckState(cell);
1012 }
1013
1014 bucket_id = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_,
1015 &bucket);
1016 if (!bucket_id)
1017 break;
1018 }
1019 }
1020
1021 uint32 IndexTable::GetAddressValue(const IndexCell& cell) {
1022 if (small_table_)
1023 return GetCellSmallTableAddress(cell);
1024
1025 return GetCellAddress(cell);
1026 }
1027
1028 uint32 IndexTable::GetHashValue(const IndexCell& cell) {
1029 if (small_table_)
1030 return GetCellSmallTableHash(cell);
1031
1032 return GetCellHash(cell);
1033 }
1034
1035 uint32 IndexTable::GetFullHash(const IndexCell& cell, uint32 lower_part) {
1036 // It is OK for the high order bits of lower_part to overlap with the stored
1037 // part of the hash.
1038 if (small_table_)
1039 return (GetCellSmallTableHash(cell) << kHashSmallTableShift) | lower_part;
1040
1041 return (GetCellHash(cell) << kHashShift) | lower_part;
1042 }
1043
1044 // All the bits stored in the cell should match the provided hash.
1045 bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) {
1046 hash = small_table_ ? hash >> kHashSmallTableShift : hash >> kHashShift;
1047 return GetHashValue(cell) == hash;
1048 }
1049
1050 bool IndexTable::MisplacedHash(const IndexCell& cell, uint32 hash) {
1051 if (!extra_bits_)
1052 return false;
1053
1054 uint32 mask = (1 << extra_bits_) - 1;
1055 hash = small_table_ ? hash >> kHashSmallTableShift : hash >> kHashShift;
1056 return (GetHashValue(cell) & mask) != (hash & mask);
1057 }
1058
1059 } // namespace disk_cache
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698