1// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// The cache is stored on disk as a collection of block-files, plus an index
6// plus a collection of external files.
7//
8// Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in
9// a separate file named f_xxx where x is a hexadecimal number. Shorter data
10// will be stored as a series of blocks on a block-file. In any case, CacheAddr
11// represents the address of the data inside the cache.
12//
13// The index is actually a collection of four files that store a hash table with
14// allocation bitmaps and backup data. Hash collisions are handled directly by
15// the table, which from some point of view behaves like a 4-way associative
16// cache with overflow buckets (so not really open addressing).
17//
18// Basically the hash table is a collection of buckets. The first part of the
19// table has a fixed number of buckets and it is directly addressed by the hash,
20// while the second part of the table (stored on a second file) has a variable
21// number of buckets. Each bucket stores up to four cells (each cell represents
22// a possibl entry). The index bitmap tracks the state of individual cells.
23//
24// The last element of the cache is the block-file. A block file is a file
25// designed to store blocks of data of a given size. For more details see
26// disk_cache/disk_format_base.h
27//
28// A new cache is initialized with a set of block files (named data_0 through
29// data_6), each one dedicated to store blocks of a given size or function. The
30// number at the end of the file name is the block file number (in decimal).
31//
32// There are three "special" types of blocks: normal entries, evicted entries
33// and control data for external files.
34//
35// The files that store internal information for the cache (blocks and index)
36// are memory mapped. They have a location that is signaled every time the
37// internal structures are modified, so it is possible to detect (most of the
38// time) when the process dies in the middle of an update. There are dedicated
39// backup files for cache bitmaps, used to detect entries out of date.
40
41#ifndef NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_
42#define NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_
43
44#include "base/basictypes.h"
45#include "net/disk_cache/disk_format_base.h"
46
47namespace disk_cache {
48
49const int kBaseTableLen = 0x10000;
50const uint32 kIndexMagicV3 = 0xC103CAC3;
51const uint32 kVersion3 = 0x30000;  // Version 3.0.
52
53// Flags for a given cache.
54enum CacheFlags {
55  CACHE_EVICTION_2 = 1,      // Keep multiple lists for eviction.
56  CACHE_EVICTED = 1 << 1     // Already evicted at least one entry.
57};
58
59// Header for the master index file.
60struct IndexHeaderV3 {
61  uint32      magic;
62  uint32      version;
63  int32       num_entries;   // Number of entries currently stored.
64  int32       num_bytes;     // Total size of the stored data.
65  int32       last_file;     // Last external file created.
66  int32       reserved1;
67  CacheAddr   stats;         // Storage for usage data.
68  int32       table_len;     // Actual size of the table.
69  int32       crash;         // Signals a previous crash.
70  int32       experiment;    // Id of an ongoing test.
71  int32       max_bytes;     // Total maximum size of the stored data.
72  uint32      flags;
73  int32       used_cells;
74  int32       max_bucket;
75  uint64      create_time;   // Creation time for this set of files.
76  uint64      base_time;     // Current base for timestamps.
77  uint64      old_time;      // Previous time used for timestamps.
78  int32       max_block_file;
79  int32       num_no_use_entries;
80  int32       num_low_use_entries;
81  int32       num_high_use_entries;
82  int32       reserved;
83  int32       num_evicted_entries;
84  int32       pad[6];
85};
86
87const int kBaseBitmapBytes = 3968;
88// The IndexBitmap is directly saved to a file named index. The file grows in
89// page increments (4096 bytes), but all bits don't have to be in use at any
90// given time. The required file size can be computed from header.table_len.
91struct IndexBitmap {
92  IndexHeaderV3   header;
93  uint32          bitmap[kBaseBitmapBytes / 4];  // First page of the bitmap.
94};
95COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader);
96
97// Possible states for a given entry.
98enum EntryState {
99  ENTRY_FREE = 0,   // Available slot.
100  ENTRY_NEW,        // The entry is being created.
101  ENTRY_OPEN,       // The entry is being accessed.
102  ENTRY_MODIFIED,   // The entry is being modified.
103  ENTRY_DELETED,    // The entry is being deleted.
104  ENTRY_FIXING,     // Inconsistent state. The entry is being verified.
105  ENTRY_USED        // The slot is in use (entry is present).
106};
107COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits);
108
109enum EntryGroup {
110  ENTRY_NO_USE = 0,   // The entry has not been reused.
111  ENTRY_LOW_USE,      // The entry has low reuse.
112  ENTRY_HIGH_USE,     // The entry has high reuse.
113  ENTRY_RESERVED,     // Reserved for future use.
114  ENTRY_EVICTED       // The entry was deleted.
115};
116COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits);
117
118#pragma pack(push, 1)
119struct IndexCell {
120  void Clear() { memset(this, 0, sizeof(*this)); }
121
122  uint64      address : 22;
123  uint64      hash : 18;
124  uint64      timestamp : 20;
125  uint64      reuse : 4;
126  uint8       state : 3;
127  uint8       group : 3;
128  uint8       sum : 2;
129};
130COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell);
131
132struct IndexBucket {
133  IndexCell   cells[4];
134  int32       next;
135  uint32      hash : 24;      // The last byte is only defined for buckets of
136  uint32      reserved : 8;   // the extra table.
137};
138COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket);
139const int kBytesPerCell = 44 / 4;
140
141// The main cache index. Backed by a file named index_tb1.
142// The extra table (index_tb2) has a similar format, but different size.
143struct Index {
144  // Default size. Actual size controlled by header.table_len.
145  IndexBucket table[kBaseTableLen / 4];
146};
147#pragma pack(pop)
148
149// Flags that can be applied to an entry.
150enum EntryFlags {
151  PARENT_ENTRY = 1,         // This entry has children (sparse) entries.
152  CHILD_ENTRY = 1 << 1      // Child entry that stores sparse data.
153};
154
155struct EntryRecord {
156  uint32      hash;
157  uint32      pad1;
158  uint8       reuse_count;
159  uint8       refetch_count;
160  int8        state;              // Current EntryState.
161  uint8       flags;              // Any combination of EntryFlags.
162  int32       key_len;
163  int32       data_size[4];       // We can store up to 4 data streams for each
164  CacheAddr   data_addr[4];       // entry.
165  uint32      data_hash[4];
166  uint64      creation_time;
167  uint64      last_modified_time;
168  uint64      last_access_time;
169  int32       pad[3];
170  uint32      self_hash;
171};
172COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord);
173
174struct ShortEntryRecord {
175  uint32      hash;
176  uint32      pad1;
177  uint8       reuse_count;
178  uint8       refetch_count;
179  int8        state;              // Current EntryState.
180  uint8       flags;
181  int32       key_len;
182  uint64      last_access_time;
183  uint32      long_hash[5];
184  uint32      self_hash;
185};
186COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord);
187
188}  // namespace disk_cache
189
190#endif  // NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_
191