1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Use of this source code is governed by a BSD-style license that can be 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// found in the LICENSE file. 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The cache is stored on disk as a collection of block-files, plus an index 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// file plus a collection of external files. 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// separate file named f_xxx where x is a hexadecimal number. Shorter data will 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// be stored as a series of blocks on a block-file. In any case, CacheAddr 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// represents the address of the data inside the cache. 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The index file is just a simple hash table that maps a particular entry to 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// a CacheAddr value. Linking for a given hash bucket is handled internally 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// by the cache entry. 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The last element of the cache is the block-file. A block file is a file 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// designed to store blocks of data of a given size. It is able to store data 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// that spans from one to four consecutive "blocks", and it grows as needed to 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// store up to approximately 65000 blocks. It has a fixed size header used for 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// book keeping such as tracking free of blocks on the file. For example, a 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// block-file for 1KB blocks will grow from 8KB when totally empty to about 64MB 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// when completely full. At that point, data blocks of 1KB will be stored on a 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// second block file that will store the next set of 65000 blocks. The first 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// file contains the number of the second file, and the second file contains the 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// number of a third file, created when the second file reaches its limit. It is 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// important to remember that no matter how long the chain of files is, any 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// given block can be located directly by its address, which contains the file 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// number and starting block inside the file. 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A new cache is initialized with four block files (named data_0 through 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// data_3), each one dedicated to store blocks of a given size. The number at 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the end of the file name is the block file number (in decimal). 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// There are two "special" types of blocks: an entry and a rankings node. An 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// entry keeps track of all the information related to the same cache entry, 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// such as the key, hash value, data pointers etc. A rankings node keeps track 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// of the information that is updated frequently for a given entry, such as its 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// location on the LRU lists, last access time etc. 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The files that store internal information for the cache (blocks and index) 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// are at least partially memory mapped. They have a location that is signaled 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// every time the internal structures are modified, so it is possible to detect 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// (most of the time) when the process dies in the middle of an update. 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// In order to prevent dirty data to be used as valid (after a crash), every 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// cache entry has a dirty identifier. Each running instance of the cache keeps 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// a separate identifier (maintained on the "this_id" header field) that is used 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// to mark every entry that is created or modified. When the entry is closed, 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// and all the data can be trusted, the dirty flag is cleared from the entry. 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// When the cache encounters an entry whose identifier is different than the one 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// being currently used, it means that the entry was not properly closed on a 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// previous run, so it is discarded. 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#ifndef NET_DISK_CACHE_DISK_FORMAT_H_ 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define NET_DISK_CACHE_DISK_FORMAT_H_ 573345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#pragma once 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/basictypes.h" 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace disk_cache { 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scotttypedef uint32 CacheAddr; 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kIndexTablesize = 0x10000; 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst uint32 kIndexMagic = 0xC103CAC3; 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst uint32 kCurrentVersion = 0x20000; // Version 2.0. 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct LruData { 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 pad1[2]; 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 filled; // Flag to tell when we filled the cache. 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 sizes[5]; 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr heads[5]; 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr tails[5]; 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr transaction; // In-flight operation target. 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 operation; // Actual in-flight operation. 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 operation_list; // In-flight operation list. 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 pad2[7]; 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Header for the master index file. 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct IndexHeader { 83731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick IndexHeader(); 84731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 magic; 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 version; 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 num_entries; // Number of entries currently stored. 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 num_bytes; // Total size of the stored data. 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 last_file; // Last external file created. 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 this_id; // Id for all entries being changed (dirty flag). 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr stats; // Storage for usage data. 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 table_len; // Actual size of the table (0 == kIndexTablesize). 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 crash; // Signals a previous crash. 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 experiment; // Id of an ongoing test. 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint64 create_time; // Creation time for this set of files. 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 pad[52]; 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LruData lru; // Eviction control data. 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The structure of the whole index file. 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct Index { 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott IndexHeader header; 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // by header.table_len. 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Main structure for an entry on the backing storage. If the key is longer than 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// what can be stored on this structure, it will be extended on consecutive 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// After that point, the whole key will be stored as a data block or external 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// file. 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct EntryStore { 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 hash; // Full hash of the key. 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr next; // Next entry with the same hash or bucket. 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr rankings_node; // Rankings node for this entry. 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 reuse_count; // How often is this entry used. 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 refetch_count; // How often is this fetched from the net. 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 state; // Current state. 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint64 creation_time; 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 key_len; 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr long_key; // Optional address of a long key. 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 data_size[4]; // We can store up to 4 data streams for each 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr data_addr[4]; // entry. 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 flags; // Any combination of EntryFlags. 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 pad[5]; 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott char key[256 - 24 * 4]; // null terminated 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCOMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott offsetof(EntryStore, key) - 1; 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Possible states for a given entry. 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottenum EntryState { 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ENTRY_NORMAL = 0, 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ENTRY_EVICTED, // The entry was recently evicted from the cache. 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ENTRY_DOOMED // The entry was doomed. 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Flags that can be applied to an entry. 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottenum EntryFlags { 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott PARENT_ENTRY = 1, // This entry has children (sparse) entries. 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#pragma pack(push, 4) 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Rankings information for a given entry. 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct RankingsNode { 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint64 last_used; // LRU info. 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint64 last_modified; // LRU info. 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr next; // LRU list. 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr prev; // LRU list. 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr contents; // Address of the EntryStore. 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 dirty; // The entry is being modifyied. 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 dummy; // Old files may have a pointer here. 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#pragma pack(pop) 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCOMPILE_ASSERT(sizeof(RankingsNode) == 36, bad_RankingsNode); 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst uint32 kBlockMagic = 0xC104CAC3; 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kBlockHeaderSize = 8192; // Two pages: almost 64k entries 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kMaxBlocks = (kBlockHeaderSize - 80) * 8; 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Bitmap to track used blocks on a block-file. 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scotttypedef uint32 AllocBitmap[kMaxBlocks / 32]; 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A block-file is the file used to store information in blocks (could be 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// EntryStore blocks, RankingsNode blocks or user-data blocks). 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// We store entries that can expand for up to 4 consecutive blocks, and keep 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// counters of the number of blocks available for each type of entry. For 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// instance, an entry of 3 blocks is an entry of type 3. We also keep track of 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// where did we find the last entry of that type (to avoid searching the bitmap 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// from the beginning every time). 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This Structure is the header of a block-file: 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct BlockFileHeader { 177731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BlockFileHeader(); 178731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 magic; 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 version; 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int16 this_file; // Index of this file. 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int16 next_file; // Next file when this one is full. 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 entry_size; // Size of the blocks of this file. 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 num_entries; // Number of stored entries. 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 max_entries; // Current maximum number of entries. 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 empty[4]; // Counters of empty entries for each type. 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 hints[4]; // Last used position for each entry type. 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott volatile int32 updating; // Keep track of updates to the header. 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 user[5]; 190c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott AllocBitmap allocation_map; 191c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 192c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCOMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Sparse data support: 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// We keep a two level hierarchy to enable sparse data for an entry: the first 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// level consists of using separate "child" entries to store ranges of 1 MB, 198c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// and the second level stores blocks of 1 KB inside each child entry. 199c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Whenever we need to access a particular sparse offset, we first locate the 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// child entry that stores that offset, so we discard the 20 least significant 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// bits of the offset, and end up with the child id. For instance, the child id 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// to store the first megabyte is 0, and the child that should store offset 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 0x410000 has an id of 4. 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The child entry is stored the same way as any other entry, so it also has a 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// name (key). The key includes a signature to be able to identify children 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// created for different generations of the same resource. In other words, given 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// that a given sparse entry can have a large number of child entries, and the 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// resource can be invalidated and replaced with a new version at any time, it 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// is important to be sure that a given child actually belongs to certain entry. 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The full name of a child entry is composed with a prefix ("Range_"), and two 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// hexadecimal 64-bit numbers at the end, separated by semicolons. The first 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// number is the signature of the parent key, and the second number is the child 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// id as described previously. The signature itself is also stored internally by 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the child and the parent entries. For example, a sparse entry with a key of 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// "sparse entry name", and a signature of 0x052AF76, may have a child entry 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// named "Range_sparse entry name:052af76:4", which stores data in the range 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 0x400000 to 0x4FFFFF. 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Each child entry keeps track of all the 1 KB blocks that have been written 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// to the entry, but being a regular entry, it will happily return zeros for any 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// read that spans data not written before. The actual sparse data is stored in 225c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// one of the data streams of the child entry (at index 1), while the control 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// information is stored in another stream (at index 2), both by parents and 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the children. 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This structure contains the control information for parent and child entries. 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// It is stored at offset 0 of the data stream with index 2. 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// It is possible to write to a child entry in a way that causes the last block 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// to be only partialy filled. In that case, last_block and last_block_len will 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// keep track of that block. 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct SparseHeader { 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int64 signature; // The parent and children signature. 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 magic; // Structure identifier (equal to kIndexMagic). 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 parent_key_len; // Key length for the parent entry. 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 last_block; // Index of the last written block. 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 last_block_len; // Lenght of the last written block. 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int32 dummy[10]; 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The SparseHeader will be followed by a bitmap, as described by this 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// structure. 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct SparseData { 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott SparseHeader header; 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uint32 bitmap[32]; // Bitmap representation of known children (if this 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // is a parent entry), or used blocks (for child 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // entries. The size is fixed for child entries but 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // not for parents; it can be as small as 4 bytes 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // and as large as 8 KB. 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The number of blocks stored by a child entry. 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst int kNumSparseBits = 1024; 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCOMPILE_ASSERT(sizeof(SparseData) == sizeof(SparseHeader) + kNumSparseBits / 8, 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Invalid_SparseData_bitmap); 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 259c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace disk_cache 260c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 261c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif // NET_DISK_CACHE_DISK_FORMAT_H_ 262