1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// found in the LICENSE file. 4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// For a general description of the files used by the cache see file_format.h. 6868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// A block file is a file designed to store blocks of data of a given size. It 8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// is able to store data that spans from one to four consecutive "blocks", and 9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// it grows as needed to store up to approximately 65000 blocks. It has a fixed 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// size header used for book keeping such as tracking free of blocks on the 11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// file. For example, a block-file for 1KB blocks will grow from 8KB when 12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// totally empty to about 64MB when completely full. At that point, data blocks 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// of 1KB will be stored on a second block file that will store the next set of 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 65000 blocks. The first file contains the number of the second file, and the 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// second file contains the number of a third file, created when the second file 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// reaches its limit. It is important to remember that no matter how long the 17868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// chain of files is, any given block can be located directly by its address, 18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// which contains the file number and starting block inside the file. 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 20868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#ifndef NET_DISK_CACHE_DISK_FORMAT_BASE_H_ 21868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#define NET_DISK_CACHE_DISK_FORMAT_BASE_H_ 22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/basictypes.h" 24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "net/base/net_export.h" 25868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 26868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)namespace disk_cache { 27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 28868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)typedef uint32 CacheAddr; 29868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 30868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const uint32 kBlockVersion2 = 0x20000; // Version 2.0. 31d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)const uint32 kBlockCurrentVersion = 0x30000; // Version 3.0. 32868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const uint32 kBlockMagic = 0xC104CAC3; 34868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kBlockHeaderSize = 8192; // Two pages: almost 64k entries 35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kMaxBlocks = (kBlockHeaderSize - 80) * 8; 36868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 37868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Bitmap to track used blocks on a block-file. 38868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)typedef uint32 AllocBitmap[kMaxBlocks / 32]; 39868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 40868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// A block-file is the file used to store information in blocks (could be 41868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// EntryStore blocks, RankingsNode blocks or user-data blocks). 42868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// We store entries that can expand for up to 4 consecutive blocks, and keep 43868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// counters of the number of blocks available for each type of entry. For 44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// instance, an entry of 3 blocks is an entry of type 3. We also keep track of 45868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// where did we find the last entry of that type (to avoid searching the bitmap 46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// from the beginning every time). 47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// This Structure is the header of a block-file: 48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)struct BlockFileHeader { 49868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) uint32 magic; 50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) uint32 version; 51868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int16 this_file; // Index of this file. 52868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int16 next_file; // Next file when this one is full. 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 entry_size; // Size of the blocks of this file. 54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 num_entries; // Number of stored entries. 55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 max_entries; // Current maximum number of entries. 56868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 empty[4]; // Counters of empty entries for each type. 57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 hints[4]; // Last used position for each entry type. 58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) volatile int32 updating; // Keep track of updates to the header. 59868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 user[5]; 60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) AllocBitmap allocation_map; 61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}; 62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); 64868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 65868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Sparse data support: 66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// We keep a two level hierarchy to enable sparse data for an entry: the first 67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// level consists of using separate "child" entries to store ranges of 1 MB, 68868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// and the second level stores blocks of 1 KB inside each child entry. 69868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 70868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Whenever we need to access a particular sparse offset, we first locate the 71868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// child entry that stores that offset, so we discard the 20 least significant 72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// bits of the offset, and end up with the child id. For instance, the child id 73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// to store the first megabyte is 0, and the child that should store offset 74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 0x410000 has an id of 4. 75868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 76868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The child entry is stored the same way as any other entry, so it also has a 77868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// name (key). The key includes a signature to be able to identify children 78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// created for different generations of the same resource. In other words, given 79868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// that a given sparse entry can have a large number of child entries, and the 80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// resource can be invalidated and replaced with a new version at any time, it 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// is important to be sure that a given child actually belongs to certain entry. 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 83868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The full name of a child entry is composed with a prefix ("Range_"), and two 84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// hexadecimal 64-bit numbers at the end, separated by semicolons. The first 85868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// number is the signature of the parent key, and the second number is the child 86868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// id as described previously. The signature itself is also stored internally by 87868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// the child and the parent entries. For example, a sparse entry with a key of 88868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// "sparse entry name", and a signature of 0x052AF76, may have a child entry 89868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// named "Range_sparse entry name:052af76:4", which stores data in the range 90868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 0x400000 to 0x4FFFFF. 91868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 92868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Each child entry keeps track of all the 1 KB blocks that have been written 93868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// to the entry, but being a regular entry, it will happily return zeros for any 94868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// read that spans data not written before. The actual sparse data is stored in 95868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// one of the data streams of the child entry (at index 1), while the control 96868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// information is stored in another stream (at index 2), both by parents and 97868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// the children. 98868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 99868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// This structure contains the control information for parent and child entries. 100868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// It is stored at offset 0 of the data stream with index 2. 101868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// It is possible to write to a child entry in a way that causes the last block 102868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// to be only partialy filled. In that case, last_block and last_block_len will 103868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// keep track of that block. 104868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)struct SparseHeader { 105868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int64 signature; // The parent and children signature. 106868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) uint32 magic; // Structure identifier (equal to kIndexMagic). 107868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 parent_key_len; // Key length for the parent entry. 108868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 last_block; // Index of the last written block. 109868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 last_block_len; // Lenght of the last written block. 110868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) int32 dummy[10]; 111868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}; 112868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 113868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The SparseHeader will be followed by a bitmap, as described by this 114868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// structure. 115868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)struct SparseData { 116868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) SparseHeader header; 117868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) uint32 bitmap[32]; // Bitmap representation of known children (if this 118868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // is a parent entry), or used blocks (for child 119868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // entries. The size is fixed for child entries but 120868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // not for parents; it can be as small as 4 bytes 121868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // and as large as 8 KB. 122868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}; 123868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 124868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The number of blocks stored by a child entry. 125868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)const int kNumSparseBits = 1024; 126868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)COMPILE_ASSERT(sizeof(SparseData) == sizeof(SparseHeader) + kNumSparseBits / 8, 127868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Invalid_SparseData_bitmap); 128868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 129868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} // namespace disk_cache 130868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 131868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#endif // NET_DISK_CACHE_DISK_FORMAT_BASE_H_ 132