15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// found in the LICENSE file. 45d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/index_table_v3.h" 65d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 75d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <algorithm> 85d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <set> 95d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <utility> 105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/bits.h" 125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "net/base/io_buffer.h" 135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "net/base/net_errors.h" 145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "net/disk_cache/disk_cache.h" 155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using base::Time; 175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using base::TimeDelta; 185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using disk_cache::CellInfo; 195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using disk_cache::CellList; 205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using disk_cache::IndexCell; 215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)using disk_cache::IndexIterator; 225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace { 245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// The following constants describe the bitfields of an IndexCell so they are 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// implicitly synchronized with the descrption of IndexCell on file_format_v3.h. 275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellLocationMask = (1 << 22) - 1; 285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellIdMask = (1 << 18) - 1; 295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellTimestampMask = (1 << 20) - 1; 305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellReuseMask = (1 << 4) - 1; 315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint8 kCellStateMask = (1 << 3) - 1; 325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint8 kCellGroupMask = (1 << 3) - 1; 335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint8 kCellSumMask = (1 << 2) - 1; 345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellSmallTableLocationMask = (1 << 16) - 1; 365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const uint64 kCellSmallTableIdMask = (1 << 24) - 1; 375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellIdOffset = 22; 395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellTimestampOffset = 40; 405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellReuseOffset = 60; 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellGroupOffset = 3; 425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellSumOffset = 6; 435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellSmallTableIdOffset = 16; 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// The number of bits that a hash has to be shifted to grab the part that 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// defines the cell id. 485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kHashShift = 14; 495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kSmallTableHashShift = 8; 505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Unfortunately we have to break the abstaction a little here: the file number 525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// where entries are stored is outside of the control of this code, and it is 535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// usually part of the stored address. However, for small tables we only store 545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 16 bits of the address so the file number is never stored on a cell. We have 555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// to infere the file number from the type of entry (normal vs evicted), and 565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// the knowledge that given that the table will not keep more than 64k entries, 575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// a single file of each type is enough. 585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kEntriesFile = disk_cache::BLOCK_ENTRIES - 1; 595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kEvictedEntriesFile = disk_cache::BLOCK_EVICTED - 1; 605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kMaxLocation = 1 << 22; 615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kMinFileNumber = 1 << 16; 625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 GetCellLocation(const IndexCell& cell) { 645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return cell.first_part & kCellLocationMask; 655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 GetCellSmallTableLocation(const IndexCell& cell) { 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return cell.first_part & kCellSmallTableLocationMask; 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 GetCellId(const IndexCell& cell) { 725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.first_part >> kCellIdOffset) & kCellIdMask; 735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 GetCellSmallTableId(const IndexCell& cell) { 765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.first_part >> kCellSmallTableIdOffset) & 775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) kCellSmallTableIdMask; 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int GetCellTimestamp(const IndexCell& cell) { 815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.first_part >> kCellTimestampOffset) & kCellTimestampMask; 825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int GetCellReuse(const IndexCell& cell) { 855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.first_part >> kCellReuseOffset) & kCellReuseMask; 865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int GetCellState(const IndexCell& cell) { 895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return cell.last_part & kCellStateMask; 905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int GetCellGroup(const IndexCell& cell) { 935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.last_part >> kCellGroupOffset) & kCellGroupMask; 945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int GetCellSum(const IndexCell& cell) { 975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (cell.last_part >> kCellSumOffset) & kCellSumMask; 985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellLocation(IndexCell* cell, uint32 address) { 1015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(address, static_cast<uint32>(kCellLocationMask)); 1025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~kCellLocationMask; 1035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= address; 1045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellSmallTableLocation(IndexCell* cell, uint32 address) { 1075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(address, static_cast<uint32>(kCellSmallTableLocationMask)); 1085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~kCellSmallTableLocationMask; 1095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= address; 1105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellId(IndexCell* cell, uint32 hash) { 1135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(hash, static_cast<uint32>(kCellIdMask)); 1145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~(kCellIdMask << kCellIdOffset); 1155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= static_cast<int64>(hash) << kCellIdOffset; 1165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellSmallTableId(IndexCell* cell, uint32 hash) { 1195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(hash, static_cast<uint32>(kCellSmallTableIdMask)); 1205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~(kCellSmallTableIdMask << kCellSmallTableIdOffset); 1215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= static_cast<int64>(hash) << kCellSmallTableIdOffset; 1225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellTimestamp(IndexCell* cell, int timestamp) { 1255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(timestamp, 1 << 20); 1265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(timestamp, 0); 1275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~(kCellTimestampMask << kCellTimestampOffset); 1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= static_cast<int64>(timestamp) << kCellTimestampOffset; 1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellReuse(IndexCell* cell, int count) { 1325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(count, 16); 1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(count, 0); 1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part &= ~(kCellReuseMask << kCellReuseOffset); 1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->first_part |= static_cast<int64>(count) << kCellReuseOffset; 1365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellState(IndexCell* cell, disk_cache::EntryState state) { 1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part &= ~kCellStateMask; 1405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part |= state; 1415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellGroup(IndexCell* cell, disk_cache::EntryGroup group) { 1445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part &= ~(kCellGroupMask << kCellGroupOffset); 1455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part |= group << kCellGroupOffset; 1465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void SetCellSum(IndexCell* cell, int sum) { 1495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(sum, 4); 1505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(sum, 0); 1515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part &= ~(kCellSumMask << kCellSumOffset); 1525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->last_part |= sum << kCellSumOffset; 1535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// This is a very particular way to calculate the sum, so it will not match if 1565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// compared a gainst a pure 2 bit, modulo 2 sum. 1575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int CalculateCellSum(const IndexCell& cell) { 1585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32* words = bit_cast<uint32*>(&cell); 1595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint8* bytes = bit_cast<uint8*>(&cell); 1605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 result = words[0] + words[1]; 1615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += result >> 16; 1625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += (result >> 8) + (bytes[8] & 0x3f); 1635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += result >> 4; 1645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) result += result >> 2; 1655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return result & 3; 1665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool SanityCheck(const IndexCell& cell) { 1695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (GetCellSum(cell) != CalculateCellSum(cell)) 1705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return false; 1715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (GetCellState(cell) > disk_cache::ENTRY_USED || 1735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) GetCellGroup(cell) == disk_cache::ENTRY_RESERVED || 1745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) GetCellGroup(cell) > disk_cache::ENTRY_EVICTED) { 1755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return false; 1765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return true; 1795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int FileNumberFromLocation(int location) { 1825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return location / kMinFileNumber; 1835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int StartBlockFromLocation(int location) { 1865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return location % kMinFileNumber; 1875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool IsValidAddress(disk_cache::Addr address) { 1905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!address.is_initialized() || 1915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (address.file_type() != disk_cache::BLOCK_EVICTED && 1925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) address.file_type() != disk_cache::BLOCK_ENTRIES)) { 1935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return false; 1945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return address.FileNumber() < FileNumberFromLocation(kMaxLocation); 1975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool IsNormalState(const IndexCell& cell) { 2005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) disk_cache::EntryState state = 2015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) static_cast<disk_cache::EntryState>(GetCellState(cell)); 2025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_NE(state, disk_cache::ENTRY_FREE); 2035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return state != disk_cache::ENTRY_DELETED && 2045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) state != disk_cache::ENTRY_FIXING; 2055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)inline int GetNextBucket(int min_bucket_num, int max_bucket_num, 2085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) disk_cache::IndexBucket* table, 2095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) disk_cache::IndexBucket** bucket) { 2105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!(*bucket)->next) 2115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return 0; 2125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = (*bucket)->next / disk_cache::kCellsPerBucket; 2145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (bucket_num < min_bucket_num || bucket_num > max_bucket_num) { 2155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // The next bucket must fall within the extra table. Note that this is not 2165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // an uncommon path as growing the table may not cleanup the link from the 2175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // main table to the extra table, and that cleanup is performed here when 2185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // accessing that bucket for the first time. This behavior has to change if 2195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // the tables are ever shrinked. 2205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (*bucket)->next = 0; 2215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return 0; 2225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *bucket = &table[bucket_num - min_bucket_num]; 2245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return bucket_num; 2255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Updates the |iterator| with the current |cell|. This cell may cause all 2285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// previous cells to be deleted (when a new target timestamp is found), the cell 2295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// may be added to the list (if it matches the target timestamp), or may it be 2305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// ignored. 2315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void UpdateIterator(const disk_cache::EntryCell& cell, 2325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int limit_time, 2335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* iterator) { 2345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int time = cell.GetTimestamp(); 2355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Look for not interesting times. 2365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (iterator->forward && time <= limit_time) 2375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 2385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!iterator->forward && time >= limit_time) 2395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 2405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if ((iterator->forward && time < iterator->timestamp) || 2425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (!iterator->forward && time > iterator->timestamp)) { 2435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // This timestamp is better than the one we had. 2445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) iterator->timestamp = time; 2455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) iterator->cells.clear(); 2465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (time == iterator->timestamp) { 2485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CellInfo cell_info = { cell.hash(), cell.GetAddress() }; 2495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) iterator->cells.push_back(cell_info); 2505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void InitIterator(IndexIterator* iterator) { 2545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) iterator->cells.clear(); 2555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) iterator->timestamp = iterator->forward ? kint32max : 0; 2565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace 2595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace disk_cache { 2615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell::~EntryCell() { 2635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool EntryCell::IsValid() const { 2665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellLocation(cell_) != 0; 2675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// This code has to map the cell address (up to 22 bits) to a general cache Addr 2705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// (up to 24 bits of general addressing). It also set the implied file_number 2715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// in the case of small tables. See also the comment by the definition of 2725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// kEntriesFile. 2735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)Addr EntryCell::GetAddress() const { 2745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 location = GetLocation(); 2755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int file_number = FileNumberFromLocation(location); 2765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) { 2775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0, file_number); 2785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) file_number = (GetGroup() == ENTRY_EVICTED) ? kEvictedEntriesFile : 2795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) kEntriesFile; 2805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_NE(0, file_number); 2825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) FileType file_type = (GetGroup() == ENTRY_EVICTED) ? BLOCK_EVICTED : 2835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) BLOCK_ENTRIES; 2845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return Addr(file_type, 1, file_number, StartBlockFromLocation(location)); 2855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryState EntryCell::GetState() const { 2885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return static_cast<EntryState>(GetCellState(cell_)); 2895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryGroup EntryCell::GetGroup() const { 2925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return static_cast<EntryGroup>(GetCellGroup(cell_)); 2935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int EntryCell::GetReuse() const { 2965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellReuse(cell_); 2975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int EntryCell::GetTimestamp() const { 3005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellTimestamp(cell_); 3015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::SetState(EntryState state) { 3045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellState(&cell_, state); 3055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::SetGroup(EntryGroup group) { 3085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellGroup(&cell_, group); 3095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::SetReuse(int count) { 3125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellReuse(&cell_, count); 3135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::SetTimestamp(int timestamp) { 3165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellTimestamp(&cell_, timestamp); 3175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Static. 3205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell EntryCell::GetEntryCellForTest(int32 cell_num, 3215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 hash, 3225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Addr address, 3235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell* cell, 3245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool small_table) { 3255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (cell) { 3265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell entry_cell(cell_num, hash, *cell, small_table); 3275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return entry_cell; 3285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return EntryCell(cell_num, hash, address, small_table); 3315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::SerializaForTest(IndexCell* destination) { 3345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) FixSum(); 3355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Serialize(destination); 3365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell::EntryCell() : cell_num_(0), hash_(0), small_table_(false) { 3395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell_.Clear(); 3405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell::EntryCell(int32 cell_num, 3435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 hash, 3445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Addr address, 3455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool small_table) 3465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : cell_num_(cell_num), 3475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_(hash), 3485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_(small_table) { 3495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(IsValidAddress(address) || !address.value()); 3505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell_.Clear(); 3525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellState(&cell_, ENTRY_NEW); 3535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellGroup(&cell_, ENTRY_NO_USE); 3545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table) { 3555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(address.FileNumber() == kEntriesFile || 3565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) address.FileNumber() == kEvictedEntriesFile); 3575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellSmallTableLocation(&cell_, address.start_block()); 3585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellSmallTableId(&cell_, hash >> kSmallTableHashShift); 3595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 3605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 location = address.FileNumber() << 16 | address.start_block(); 3615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellLocation(&cell_, location); 3625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellId(&cell_, hash >> kHashShift); 3635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell::EntryCell(int32 cell_num, 3675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 hash, 3685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const IndexCell& cell, 3695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool small_table) 3705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : cell_num_(cell_num), 3715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_(hash), 3725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell_(cell), 3735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_(small_table) { 3745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::FixSum() { 3775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) SetCellSum(&cell_, CalculateCellSum(cell_)); 3785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 EntryCell::GetLocation() const { 3815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) 3825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellSmallTableLocation(cell_); 3835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellLocation(cell_); 3855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 EntryCell::RecomputeHash() { 3885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) { 3895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_ &= (1 << kSmallTableHashShift) - 1; 3905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_ |= GetCellSmallTableId(cell_) << kSmallTableHashShift; 3915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return hash_; 3925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_ &= (1 << kHashShift) - 1; 3955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash_ |= GetCellId(cell_) << kHashShift; 3965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return hash_; 3975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void EntryCell::Serialize(IndexCell* destination) const { 4005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *destination = cell_; 4015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntrySet::EntrySet() : evicted_count(0), current(0) { 4045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntrySet::~EntrySet() { 4075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexIterator::IndexIterator() { 4105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexIterator::~IndexIterator() { 4135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexTableInitData::IndexTableInitData() { 4165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexTableInitData::~IndexTableInitData() { 4195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// ----------------------------------------------------------------------- 4225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexTable::IndexTable(IndexTableBackend* backend) 4245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : backend_(backend), 4255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_(NULL), 4265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) main_table_(NULL), 4275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_table_(NULL), 4285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_(false), 4295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_(false) { 4305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)IndexTable::~IndexTable() { 4335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// For a general description of the index tables see: 4365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Index 4375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 4385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// The index is split between two tables: the main_table_ and the extra_table_. 4395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// The main table can grow only by doubling its number of cells, while the 4405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// extra table can grow slowly, because it only contain cells that overflow 4415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// from the main table. In order to locate a given cell, part of the hash is 4425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// used directly as an index into the main table; once that bucket is located, 4435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// all cells with that partial hash (i.e., belonging to that bucket) are 4445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// inspected, and if present, the next bucket (located on the extra table) is 4455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// then located. For more information on bucket chaining see: 4465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// http://www.chromium.org/developers/design-documents/network-stack/disk-cache/disk-cache-v3#TOC-Buckets 4475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 4485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// There are two cases when increasing the size: 4495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// - Doubling the size of the main table 4505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// - Adding more entries to the extra table 4515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 4525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// For example, consider a 64k main table with 8k cells on the extra table (for 4535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// a total of 72k cells). Init can be called to add another 8k cells at the end 4545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// (grow to 80k cells). When the size of the extra table approaches 64k, Init 4555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// can be called to double the main table (to 128k) and go back to a small extra 4565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// table. 4575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::Init(IndexTableInitData* params) { 4585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool growing = header_ != NULL; 4595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) scoped_ptr<IndexBucket[]> old_extra_table; 4605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_ = ¶ms->index_bitmap->header; 4615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (params->main_table) { 4635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (main_table_) { 4645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // This is doubling the size of main table. 4655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(base::bits::Log2Floor(header_->table_len), 4665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::bits::Log2Floor(backup_header_->table_len) + 1); 4675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int extra_size = (header()->max_bucket - mask_) * kCellsPerBucket; 4685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(extra_size, 0); 4695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Doubling the size implies deleting the extra table and moving as many 4715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // cells as we can to the main table, so we first copy the old one. This 4725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // is not required when just growing the extra table because we don't 4735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // move any cell in that case. 4745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_extra_table.reset(new IndexBucket[extra_size]); 4755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memcpy(old_extra_table.get(), extra_table_, 4765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_size * sizeof(IndexBucket)); 4775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memset(params->extra_table, 0, extra_size * sizeof(IndexBucket)); 4785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) main_table_ = params->main_table; 4805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(main_table_); 4825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_table_ = params->extra_table; 4835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // extra_bits_ is really measured against table-size specific values. 4855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const int kMaxAbsoluteExtraBits = 12; // From smallest to largest table. 4865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const int kMaxExtraBitsSmallTable = 6; // From smallest to 64K table. 4875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_bits_ = base::bits::Log2Floor(header_->table_len) - 4895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::bits::Log2Floor(kBaseTableLen); 4905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(extra_bits_, 0); 4915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(extra_bits_, kMaxAbsoluteExtraBits); 4925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Note that following the previous code the constants could be derived as 4945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // kMaxAbsoluteExtraBits = base::bits::Log2Floor(max table len) - 4955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // base::bits::Log2Floor(kBaseTableLen); 4965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // = 22 - base::bits::Log2Floor(1024) = 22 - 10; 4975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // kMaxExtraBitsSmallTable = base::bits::Log2Floor(max 16 bit table) - 10. 4985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) mask_ = ((kBaseTableLen / kCellsPerBucket) << extra_bits_) - 1; 5005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = extra_bits_ < kMaxExtraBitsSmallTable; 5015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!small_table_) 5025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_bits_ -= kMaxExtraBitsSmallTable; 5035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // table_len keeps the max number of cells stored by the index. We need a 5055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // bitmap with 1 bit per cell, and that bitmap has num_words 32-bit words. 5065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int num_words = (header_->table_len + 31) / 32; 5075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (old_extra_table) { 5095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // All the cells from the extra table are moving to the new tables so before 5105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // creating the bitmaps, clear the part of the bitmap referring to the extra 5115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // table. 5125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int old_main_table_bit_words = ((mask_ >> 1) + 1) * kCellsPerBucket / 32; 5135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GT(num_words, old_main_table_bit_words); 5145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memset(params->index_bitmap->bitmap + old_main_table_bit_words, 0, 5155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (num_words - old_main_table_bit_words) * sizeof(int32)); 5165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(growing); 5185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int old_num_words = (backup_header_.get()->table_len + 31) / 32; 5195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GT(old_num_words, old_main_table_bit_words); 5205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memset(backup_bitmap_storage_.get() + old_main_table_bit_words, 0, 5215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (old_num_words - old_main_table_bit_words) * sizeof(int32)); 5225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 5235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_.reset(new Bitmap(params->index_bitmap->bitmap, header_->table_len, 5245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_words)); 5255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (growing) { 5275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int old_num_words = (backup_header_.get()->table_len + 31) / 32; 5285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(num_words, old_num_words); 5295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) scoped_ptr<uint32[]> storage(new uint32[num_words]); 5305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memcpy(storage.get(), backup_bitmap_storage_.get(), 5315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_num_words * sizeof(int32)); 5325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memset(storage.get() + old_num_words, 0, 5335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) (num_words - old_num_words) * sizeof(int32)); 5345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_storage_.swap(storage); 5365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_header_->table_len = header_->table_len; 5375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 5385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_storage_.reset(params->backup_bitmap.release()); 5395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_header_.reset(params->backup_header.release()); 5405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 5415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_words = (backup_header_->table_len + 31) / 32; 5435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_.reset(new Bitmap(backup_bitmap_storage_.get(), 5445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_header_->table_len, num_words)); 5455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (old_extra_table) 5465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MoveCells(old_extra_table.get()); 5475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) 5495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(header_->flags & SMALL_CACHE); 5505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // All tables and backups are needed for operation. 5525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(main_table_); 5535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(extra_table_); 5545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(bitmap_.get()); 5555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 5565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::Shutdown() { 5585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_ = NULL; 5595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) main_table_ = NULL; 5605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) extra_table_ = NULL; 5615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_.reset(); 5625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_.reset(); 5635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_header_.reset(); 5645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_storage_.reset(); 5655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = false; 5665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 5675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 5685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// The general method for locating cells is to: 5695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 1. Get the first bucket. This usually means directly indexing the table (as 5705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// this method does), or iterating through all possible buckets. 5715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 2. Iterate through all the cells in that first bucket. 5725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 3. If there is a linked bucket, locate it directly in the extra table. 5735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 4. Go back to 2, as needed. 5745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 5755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// One consequence of this pattern is that we never start looking at buckets in 5765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// the extra table, unless we are following a link from the main table. 5775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntrySet IndexTable::LookupEntries(uint32 hash) { 5785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntrySet entries; 5795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = static_cast<int>(hash & mask_); 5805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &main_table_[bucket_num]; 5815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 5825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < kCellsPerBucket; i++) { 5835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell* current_cell = &bucket->cells[i]; 5845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(*current_cell)) 5855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 5865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!SanityCheck(*current_cell)) { 5875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NOTREACHED(); 5885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_num = bucket_num * kCellsPerBucket + i; 5895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_cell->Clear(); 5905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_->Set(cell_num, false); 5915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_->Set(cell_num, false); 5925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = true; 5935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 5945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 5955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_num = bucket_num * kCellsPerBucket + i; 5965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (MisplacedHash(*current_cell, hash)) { 5975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) HandleMisplacedCell(current_cell, cell_num, hash & mask_); 5985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else if (IsHashMatch(*current_cell, hash)) { 5995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell entry_cell(cell_num, hash, *current_cell, small_table_); 6005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CheckState(entry_cell); 6015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (entry_cell.GetState() != ENTRY_DELETED) { 6025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) entries.cells.push_back(entry_cell); 6035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (entry_cell.GetGroup() == ENTRY_EVICTED) 6045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) entries.evicted_count++; 6055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, 6095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 6105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 6115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return entries; 6125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 6135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell IndexTable::CreateEntryCell(uint32 hash, Addr address) { 6155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(IsValidAddress(address)); 6165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(address.FileNumber() || address.start_block()); 6175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = static_cast<int>(hash & mask_); 6195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_num = 0; 6205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &main_table_[bucket_num]; 6215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell* current_cell = NULL; 6225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool found = false; 6235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 6245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < kCellsPerBucket && !found; i++) { 6255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_cell = &bucket->cells[i]; 6265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(*current_cell)) { 6275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell_num = bucket_num * kCellsPerBucket + i; 6285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) found = true; 6295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (found) 6325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 6335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, 6345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 6355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 6365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!found) { 6385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = NewExtraBucket(); 6395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (bucket_num) { 6405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell_num = bucket_num * kCellsPerBucket; 6415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket->next = cell_num; 6425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket = &extra_table_[bucket_num - (mask_ + 1)]; 6435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket->hash = hash & mask_; 6445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) found = true; 6455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 6465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // address 0 is a reserved value, and the caller interprets it as invalid. 6475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) address.set_value(0); 6485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell entry_cell(cell_num, hash, address, small_table_); 6525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (address.file_type() == BLOCK_EVICTED) 6535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) entry_cell.SetGroup(ENTRY_EVICTED); 6545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) else 6555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) entry_cell.SetGroup(ENTRY_NO_USE); 6565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Save(&entry_cell); 6575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (found) { 6595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_->Set(cell_num, true); 6605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_->Set(cell_num, true); 6615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->used_cells++; 6625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = true; 6635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return entry_cell; 6665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 6675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell IndexTable::FindEntryCell(uint32 hash, Addr address) { 6695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return FindEntryCellImpl(hash, address, false); 6705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 6715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int IndexTable::CalculateTimestamp(Time time) { 6735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TimeDelta delta = time - Time::FromInternalValue(header_->base_time); 6745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return std::max(delta.InMinutes(), 0); 6755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 6765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)base::Time IndexTable::TimeFromTimestamp(int timestamp) { 6785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return Time::FromInternalValue(header_->base_time) + 6795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TimeDelta::FromMinutes(timestamp); 6805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 6815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::SetSate(uint32 hash, Addr address, EntryState state) { 6835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell cell = FindEntryCellImpl(hash, address, state == ENTRY_FREE); 6845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!cell.IsValid()) { 6855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NOTREACHED(); 6865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 6875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 6885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 6895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryState old_state = cell.GetState(); 6905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) switch (state) { 6915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_FREE: 6925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(old_state, ENTRY_DELETED); 6935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 6945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_NEW: 6955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(old_state, ENTRY_FREE); 6965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 6975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_OPEN: 6985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(old_state, ENTRY_USED); 6995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 7005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_MODIFIED: 7015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(old_state, ENTRY_OPEN); 7025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 7035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_DELETED: 7045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN || 7055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_state == ENTRY_MODIFIED); 7065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 7075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_USED: 7085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(old_state == ENTRY_NEW || old_state == ENTRY_OPEN || 7095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_state == ENTRY_MODIFIED); 7105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 7115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_FIXING: 7125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 7135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) }; 7145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = true; 7165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (state == ENTRY_DELETED) { 7175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_->Set(cell.cell_num(), false); 7185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_->Set(cell.cell_num(), false); 7195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else if (state == ENTRY_FREE) { 7205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell.Clear(); 7215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Write(cell); 7225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->used_cells--; 7235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 7245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 7255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell.SetState(state); 7265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Save(&cell); 7285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::UpdateTime(uint32 hash, Addr address, base::Time current) { 7315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell cell = FindEntryCell(hash, address); 7325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!cell.IsValid()) 7335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 7345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int minutes = CalculateTimestamp(current); 7365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Keep about 3 months of headroom. 7385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const int kMaxTimestamp = (1 << 20) - 60 * 24 * 90; 7395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (minutes > kMaxTimestamp) { 7405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // TODO(rvargas): 7415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Update header->old_time and trigger a timer 7425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Rebaseline timestamps and don't update sums 7435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Start a timer (about 2 backups) 7445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // fix all ckecksums and trigger another timer 7455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // update header->old_time because rebaseline is done. 7465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) minutes = std::min(minutes, (1 << 20) - 1); 7475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 7485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell.SetTimestamp(minutes); 7505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Save(&cell); 7515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::Save(EntryCell* cell) { 7545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell->FixSum(); 7555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Write(*cell); 7565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::GetOldest(IndexIterator* no_use, 7595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* low_use, 7605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* high_use) { 7615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) no_use->forward = true; 7625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) low_use->forward = true; 7635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) high_use->forward = true; 7645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) InitIterator(no_use); 7655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) InitIterator(low_use); 7665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) InitIterator(high_use); 7675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) WalkTables(-1, no_use, low_use, high_use); 7695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool IndexTable::GetNextCells(IndexIterator* iterator) { 7725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int current_time = iterator->timestamp; 7735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) InitIterator(iterator); 7745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) WalkTables(current_time, iterator, iterator, iterator); 7765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return !iterator->cells.empty(); 7775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::OnBackupTimer() { 7805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!modified_) 7815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 7825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int num_words = (header_->table_len + 31) / 32; 7845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int num_bytes = num_words * 4 + static_cast<int>(sizeof(*header_)); 7855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(num_bytes)); 7865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memcpy(buffer->data(), header_, sizeof(*header_)); 7875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memcpy(buffer->data() + sizeof(*header_), backup_bitmap_storage_.get(), 7885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) num_words * 4); 7895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backend_->SaveIndex(buffer, num_bytes); 7905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = false; 7915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 7925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// ----------------------------------------------------------------------- 7945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 7955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)EntryCell IndexTable::FindEntryCellImpl(uint32 hash, Addr address, 7965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool allow_deleted) { 7975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = static_cast<int>(hash & mask_); 7985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &main_table_[bucket_num]; 7995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 8005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < kCellsPerBucket; i++) { 8015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell* current_cell = &bucket->cells[i]; 8025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(*current_cell)) 8035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 8045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(SanityCheck(*current_cell)); 8055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (IsHashMatch(*current_cell, hash)) { 8065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We have a match. 8075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_num = bucket_num * kCellsPerBucket + i; 8085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell entry_cell(cell_num, hash, *current_cell, small_table_); 8095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (entry_cell.GetAddress() != address) 8105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 8115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!allow_deleted && entry_cell.GetState() == ENTRY_DELETED) 8135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 8145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return entry_cell; 8165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, 8195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 8205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 8215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return EntryCell(); 8225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 8235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::CheckState(const EntryCell& cell) { 8255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int current_state = cell.GetState(); 8265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (current_state != ENTRY_FIXING) { 8275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool present = ((current_state & 3) != 0); // Look at the last two bits. 8285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (present != bitmap_->Get(cell.cell_num()) || 8295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) present != backup_bitmap_->Get(cell.cell_num())) { 8305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // There's a mismatch. 8315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (current_state == ENTRY_DELETED) { 8325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We were in the process of deleting this entry. Finish now. 8335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backend_->DeleteCell(cell); 8345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 8355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_state = ENTRY_FIXING; 8365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell bad_cell(cell); 8375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bad_cell.SetState(ENTRY_FIXING); 8385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Save(&bad_cell); 8395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (current_state == ENTRY_FIXING) 8445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backend_->FixCell(cell); 8455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 8465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::Write(const EntryCell& cell) { 8485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = NULL; 8495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = cell.cell_num() / kCellsPerBucket; 8505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (bucket_num < static_cast<int32>(mask_ + 1)) { 8515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket = &main_table_[bucket_num]; 8525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 8535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(bucket_num, header()->max_bucket); 8545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket = &extra_table_[bucket_num - (mask_ + 1)]; 8555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_number = cell.cell_num() % kCellsPerBucket; 8585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (GetLocation(bucket->cells[cell_number]) && cell.GetLocation()) { 8595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(cell.GetLocation(), 8605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) GetLocation(bucket->cells[cell_number])); 8615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell.Serialize(&bucket->cells[cell_number]); 8635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 8645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)int IndexTable::NewExtraBucket() { 8665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int safe_window = (header()->table_len < kNumExtraBlocks * 2) ? 8675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) kNumExtraBlocks / 4 : kNumExtraBlocks; 8685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (header()->table_len - header()->max_bucket * kCellsPerBucket < 8695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) safe_window) { 8705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backend_->GrowIndex(); 8715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (header()->max_bucket * kCellsPerBucket == 8745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->table_len - kCellsPerBucket) { 8755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return 0; 8765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 8775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->max_bucket++; 8795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return header()->max_bucket; 8805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 8815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::WalkTables(int limit_time, 8835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* no_use, 8845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* low_use, 8855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* high_use) { 8865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_no_use_entries = 0; 8875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_low_use_entries = 0; 8885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_high_use_entries = 0; 8895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_evicted_entries = 0; 8905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < static_cast<int32>(mask_ + 1); i++) { 8925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = i; 8935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &main_table_[i]; 8945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 8955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) UpdateFromBucket(bucket, i, limit_time, no_use, low_use, high_use); 8965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 8975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, 8985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 8995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 9005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_entries = header_->num_no_use_entries + 9025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_low_use_entries + 9035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_high_use_entries + 9045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_evicted_entries; 9055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = true; 9065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 9075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::UpdateFromBucket(IndexBucket* bucket, int bucket_hash, 9095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int limit_time, 9105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* no_use, 9115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* low_use, 9125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexIterator* high_use) { 9135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < kCellsPerBucket; i++) { 9145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell& current_cell = bucket->cells[i]; 9155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(current_cell)) 9165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 9175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(SanityCheck(current_cell)); 9185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!IsNormalState(current_cell)) 9195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 9205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell entry_cell(0, GetFullHash(current_cell, bucket_hash), 9225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_cell, small_table_); 9235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) switch (GetCellGroup(current_cell)) { 9245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_NO_USE: 9255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) UpdateIterator(entry_cell, limit_time, no_use); 9265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_no_use_entries++; 9275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 9285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_LOW_USE: 9295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) UpdateIterator(entry_cell, limit_time, low_use); 9305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_low_use_entries++; 9315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 9325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_HIGH_USE: 9335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) UpdateIterator(entry_cell, limit_time, high_use); 9345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_high_use_entries++; 9355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 9365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) case ENTRY_EVICTED: 9375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header_->num_evicted_entries++; 9385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 9395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) default: 9405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NOTREACHED(); 9415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 9445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// This code is only called from Init() so the internal state of this object is 9465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// in flux (this method is performing the last steps of re-initialization). As 9475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// such, random methods are not supposed to work at this point, so whatever this 9485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// method calls should be relatively well controlled and it may require some 9495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// degree of "stable state faking". 9505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::MoveCells(IndexBucket* old_extra_table) { 9515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int max_hash = (mask_ + 1) / 2; 9525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int max_bucket = header()->max_bucket; 9535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->max_bucket = mask_; 9545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int used_cells = header()->used_cells; 9555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Consider a large cache: a cell stores the upper 18 bits of the hash 9575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // (h >> 14). If the table is say 8 times the original size (growing from 4x), 9585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // the bit that we are interested in would be the 3rd bit of the stored value, 9595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // in other words 'multiplier' >> 1. 9605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 new_bit = (1 << extra_bits_) >> 1; 9615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) scoped_ptr<IndexBucket[]> old_main_table; 9635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* source_table = main_table_; 9645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool upgrade_format = !extra_bits_; 9655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format) { 9665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // This method should deal with migrating a small table to a big one. Given 9675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // that the first thing to do is read the old table, set small_table_ for 9685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // the size of the old table. Now, when moving a cell, the result cannot be 9695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // placed in the old table or we will end up reading it again and attempting 9705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // to move it, so we have to copy the whole table at once. 9715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!small_table_); 9725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = true; 9735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_main_table.reset(new IndexBucket[max_hash]); 9745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memcpy(old_main_table.get(), main_table_, max_hash * sizeof(IndexBucket)); 9755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) memset(main_table_, 0, max_hash * sizeof(IndexBucket)); 9765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) source_table = old_main_table.get(); 9775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 9795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < max_hash; i++) { 9805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_num = i; 9815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &source_table[i]; 9825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 9835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int j = 0; j < kCellsPerBucket; j++) { 9845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell& current_cell = bucket->cells[j]; 9855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(current_cell)) 9865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 9875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(SanityCheck(current_cell)); 9885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (bucket_num == i) { 9895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format || (GetHashValue(current_cell) & new_bit)) { 9905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Move this cell to the upper half of the table. 9915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MoveSingleCell(¤t_cell, bucket_num * kCellsPerBucket + j, i, 9925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) true); 9935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 9955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // All cells on extra buckets have to move. 9965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MoveSingleCell(¤t_cell, bucket_num * kCellsPerBucket + j, i, 9975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) true); 9985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 9995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // There is no need to clear the old bucket->next value because if falls 10025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // within the main table so it will be fixed when attempting to follow 10035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // the link. 10045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(max_hash, max_bucket, old_extra_table, 10055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 10065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 10075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(header()->used_cells, used_cells); 10105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format) { 10125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = false; 10135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->flags &= ~SMALL_CACHE; 10145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 10165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::MoveSingleCell(IndexCell* current_cell, int cell_num, 10185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int main_table_index, bool growing) { 10195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 hash = GetFullHash(*current_cell, main_table_index); 10205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell old_cell(cell_num, hash, *current_cell, small_table_); 10215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // This method may be called when moving entries from a small table to a 10235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // normal table. In that case, the caller (MoveCells) has to read the old 10245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // table, so it needs small_table_ set to true, but this method needs to 10255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // write to the new table so small_table_ has to be set to false, and the 10265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // value restored to true before returning. 10275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool upgrade_format = !extra_bits_ && growing; 10285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format) 10295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = false; 10305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell new_cell = CreateEntryCell(hash, old_cell.GetAddress()); 10315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!new_cell.IsValid()) { 10335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We'll deal with this entry later. 10345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format) 10355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = true; 10365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 10375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) new_cell.SetState(old_cell.GetState()); 10405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) new_cell.SetGroup(old_cell.GetGroup()); 10415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) new_cell.SetReuse(old_cell.GetReuse()); 10425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) new_cell.SetTimestamp(old_cell.GetTimestamp()); 10435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Save(&new_cell); 10445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) modified_ = true; 10455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (upgrade_format) 10465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) small_table_ = true; 10475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (old_cell.GetState() == ENTRY_DELETED) { 10495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_->Set(new_cell.cell_num(), false); 10505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_->Set(new_cell.cell_num(), false); 10515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!growing || cell_num / kCellsPerBucket == main_table_index) { 10545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Only delete entries that live on the main table. 10555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!upgrade_format) { 10565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) old_cell.Clear(); 10575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Write(old_cell); 10585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (cell_num != new_cell.cell_num()) { 10615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bitmap_->Set(old_cell.cell_num(), false); 10625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) backup_bitmap_->Set(old_cell.cell_num(), false); 10635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) header()->used_cells--; 10665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 10675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::HandleMisplacedCell(IndexCell* current_cell, int cell_num, 10695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int main_table_index) { 10705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NOTREACHED(); // No unit tests yet. 10715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // The cell may be misplaced, or a duplicate cell exists with this data. 10735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 hash = GetFullHash(*current_cell, main_table_index); 10745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) MoveSingleCell(current_cell, cell_num, main_table_index, false); 10755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Now look for a duplicate cell. 10775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CheckBucketList(hash & mask_); 10785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 10795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 10805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void IndexTable::CheckBucketList(int bucket_num) { 10815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) typedef std::pair<int, EntryGroup> AddressAndGroup; 10825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::set<AddressAndGroup> entries; 10835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexBucket* bucket = &main_table_[bucket_num]; 10845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int bucket_hash = bucket_num; 10855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 10865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < kCellsPerBucket; i++) { 10875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) IndexCell* current_cell = &bucket->cells[i]; 10885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!GetLocation(*current_cell)) 10895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 10905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!SanityCheck(*current_cell)) { 10915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NOTREACHED(); 10925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_cell->Clear(); 10935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 10945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 10955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) int cell_num = bucket_num * kCellsPerBucket + i; 10965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) EntryCell cell(cell_num, GetFullHash(*current_cell, bucket_hash), 10975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *current_cell, small_table_); 10985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!entries.insert(std::make_pair(cell.GetAddress().value(), 10995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) cell.GetGroup())).second) { 11005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_cell->Clear(); 11015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 11025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 11035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CheckState(cell); 11045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 11055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bucket_num = GetNextBucket(mask_ + 1, header()->max_bucket, extra_table_, 11075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) &bucket); 11085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (bucket_num); 11095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 IndexTable::GetLocation(const IndexCell& cell) { 11125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) 11135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellSmallTableLocation(cell); 11145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellLocation(cell); 11165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 IndexTable::GetHashValue(const IndexCell& cell) { 11195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) 11205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellSmallTableId(cell); 11215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetCellId(cell); 11235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)uint32 IndexTable::GetFullHash(const IndexCell& cell, uint32 lower_part) { 11265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // It is OK for the high order bits of lower_part to overlap with the stored 11275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // part of the hash. 11285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (small_table_) 11295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (GetCellSmallTableId(cell) << kSmallTableHashShift) | lower_part; 11305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (GetCellId(cell) << kHashShift) | lower_part; 11325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// All the bits stored in the cell should match the provided hash. 11355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool IndexTable::IsHashMatch(const IndexCell& cell, uint32 hash) { 11365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; 11375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return GetHashValue(cell) == hash; 11385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool IndexTable::MisplacedHash(const IndexCell& cell, uint32 hash) { 11415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!extra_bits_) 11425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return false; 11435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) uint32 mask = (1 << extra_bits_) - 1; 11455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) hash = small_table_ ? hash >> kSmallTableHashShift : hash >> kHashShift; 11465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return (GetHashValue(cell) & mask) != (hash & mask); 11475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 11485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 11495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace disk_cache 1150