OLD | NEW |
1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // The cache is stored on disk as a collection of block-files, plus an index | 5 // The cache is stored on disk as a collection of block-files, plus an index |
6 // file plus a collection of external files. | 6 // file plus a collection of external files. |
7 // | 7 // |
8 // Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a | 8 // Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a |
9 // separate file named f_xxx where x is a hexadecimal number. Shorter data will | 9 // separate file named f_xxx where x is a hexadecimal number. Shorter data will |
10 // be stored as a series of blocks on a block-file. In any case, CacheAddr | 10 // be stored as a series of blocks on a block-file. In any case, CacheAddr |
(...skipping 18 matching lines...) Expand all Loading... |
29 // number and starting block inside the file. | 29 // number and starting block inside the file. |
30 // | 30 // |
31 // A new cache is initialized with four block files (named data_0 through | 31 // A new cache is initialized with four block files (named data_0 through |
32 // data_3), each one dedicated to store blocks of a given size. The number at | 32 // data_3), each one dedicated to store blocks of a given size. The number at |
33 // the end of the file name is the block file number (in decimal). | 33 // the end of the file name is the block file number (in decimal). |
34 // | 34 // |
35 // There are two "special" types of blocks: an entry and a rankings node. An | 35 // There are two "special" types of blocks: an entry and a rankings node. An |
36 // entry keeps track of all the information related to the same cache entry, | 36 // entry keeps track of all the information related to the same cache entry, |
37 // such as the key, hash value, data pointers etc. A rankings node keeps track | 37 // such as the key, hash value, data pointers etc. A rankings node keeps track |
38 // of the information that is updated frequently for a given entry, such as its | 38 // of the information that is updated frequently for a given entry, such as its |
39 // location on the LRU list, last access time etc. | 39 // location on the LRU lists, last access time etc. |
40 // | 40 // |
41 // The files that store internal information for the cache (blocks and index) | 41 // The files that store internal information for the cache (blocks and index) |
42 // are at least partially memory mapped. They have a location that is signaled | 42 // are at least partially memory mapped. They have a location that is signaled |
43 // every time the internal structures are modified, so it is possible to detect | 43 // every time the internal structures are modified, so it is possible to detect |
44 // (most of the time) when the process dies in the middle of an update. | 44 // (most of the time) when the process dies in the middle of an update. |
45 // | 45 // |
46 // In order to prevent dirty data to be used as valid (after a crash), every | 46 // In order to prevent dirty data to be used as valid (after a crash), every |
47 // cache entry has a dirty identifier. Each running instance of the cache keeps | 47 // cache entry has a dirty identifier. Each running instance of the cache keeps |
48 // a separate identifier (maintained on the "this_id" header field) that is used | 48 // a separate identifier (maintained on the "this_id" header field) that is used |
49 // to mark every entry that is created or modified. When the entry is closed, | 49 // to mark every entry that is created or modified. When the entry is closed, |
50 // and all the data can be trusted, the dirty flag is cleared from the entry. | 50 // and all the data can be trusted, the dirty flag is cleared from the entry. |
51 // When the cache encounters an entry whose identifier is different than the one | 51 // When the cache encounters an entry whose identifier is different than the one |
52 // being currently used, it means that the entry was not properly closed on a | 52 // being currently used, it means that the entry was not properly closed on a |
53 // previous run, so it is discarded. | 53 // previous run, so it is discarded. |
54 | 54 |
55 #ifndef NET_DISK_CACHE_DISK_FORMAT_H__ | 55 #ifndef NET_DISK_CACHE_DISK_FORMAT_H__ |
56 #define NET_DISK_CACHE_DISK_FORMAT_H__ | 56 #define NET_DISK_CACHE_DISK_FORMAT_H__ |
57 | 57 |
58 #include "base/basictypes.h" | 58 #include "base/basictypes.h" |
59 | 59 |
60 namespace disk_cache { | 60 namespace disk_cache { |
61 | 61 |
62 typedef uint32 CacheAddr; | 62 typedef uint32 CacheAddr; |
63 | 63 |
64 const int kIndexTablesize = 0x10000; | 64 const int kIndexTablesize = 0x10000; |
65 const uint32 kIndexMagic = 0xC103CAC3; | 65 const uint32 kIndexMagic = 0xC103CAC3; |
66 const uint32 kCurrentVersion = 0x10003; // Version 1.3. | 66 const uint32 kCurrentVersion = 0x20000; // Version 2.0. |
| 67 |
| 68 struct LruData { |
| 69 CacheAddr heads[5]; |
| 70 CacheAddr tails[5]; |
| 71 CacheAddr transaction; // In-flight operation target. |
| 72 int32 operation; // Actual in-flight operation. |
| 73 int32 operation_list; // In-flight operation list. |
| 74 int32 pad[7]; |
| 75 }; |
67 | 76 |
68 // Header for the master index file. | 77 // Header for the master index file. |
69 struct IndexHeader { | 78 struct IndexHeader { |
70 uint32 magic; | 79 uint32 magic; |
71 uint32 version; | 80 uint32 version; |
72 int32 num_entries; // Number of entries currently stored. | 81 int32 num_entries; // Number of entries currently stored. |
73 int32 num_bytes; // Total size of the stored data. | 82 int32 num_bytes; // Total size of the stored data. |
74 int32 last_file; // Last external file created. | 83 int32 last_file; // Last external file created. |
75 int32 this_id; // Id for all entries being changed (dirty flag). | 84 int32 this_id; // Id for all entries being changed (dirty flag). |
76 CacheAddr stats; // Storage for usage data. | 85 CacheAddr stats; // Storage for usage data. |
77 int32 table_len; // Actual size of the table (0 == kIndexTablesize). | 86 int32 table_len; // Actual size of the table (0 == kIndexTablesize). |
78 int32 pad[8]; | 87 int32 pad[64]; |
| 88 LruData lru; // Eviction control data. |
79 IndexHeader() { | 89 IndexHeader() { |
80 memset(this, 0, sizeof(*this)); | 90 memset(this, 0, sizeof(*this)); |
81 magic = kIndexMagic; | 91 magic = kIndexMagic; |
82 version = kCurrentVersion; | 92 version = kCurrentVersion; |
83 }; | 93 }; |
84 }; | 94 }; |
85 | 95 |
86 // The structure of the whole index file. | 96 // The structure of the whole index file. |
87 struct Index { | 97 struct Index { |
88 IndexHeader header; | 98 IndexHeader header; |
89 CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled | 99 CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled |
90 // by header.table_len. | 100 // by header.table_len. |
91 }; | 101 }; |
92 | 102 |
93 // Main structure for an entry on the backing storage. If the key is longer than | 103 // Main structure for an entry on the backing storage. If the key is longer than |
94 // what can be stored on this structure, it will be extended on consecutive | 104 // what can be stored on this structure, it will be extended on consecutive |
95 // blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). | 105 // blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). |
96 // After that point, the whole key will be stored as a data block or external | 106 // After that point, the whole key will be stored as a data block or external |
97 // file. | 107 // file. |
98 struct EntryStore { | 108 struct EntryStore { |
99 uint32 hash; // Full hash of the key. | 109 uint32 hash; // Full hash of the key. |
100 CacheAddr next; // Next entry with the same hash or bucket. | 110 CacheAddr next; // Next entry with the same hash or bucket. |
101 CacheAddr rankings_node; // Rankings node for this entry. | 111 CacheAddr rankings_node; // Rankings node for this entry. |
| 112 int32 reuse_count; // How often is this entry used. |
| 113 int32 refetch_count; // How often is this fetched from the net. |
| 114 int32 state; // Current state. |
| 115 uint64 creation_time; |
102 int32 key_len; | 116 int32 key_len; |
103 CacheAddr long_key; // Optional address of a long key. | 117 CacheAddr long_key; // Optional address of a long key. |
104 int32 data_size[2]; // We can store up to 2 data chunks for each | 118 int32 data_size[4]; // We can store up to 4 data streams for each |
105 CacheAddr data_addr[2]; // entry. | 119 CacheAddr data_addr[4]; // entry. |
106 char key[256 - 9 * 4]; // null terminated | 120 int32 pad[6]; |
| 121 char key[256 - 24 * 4]; // null terminated |
107 }; | 122 }; |
108 | 123 |
109 COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); | 124 COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); |
110 const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - | 125 const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - |
111 offsetof(EntryStore, key) - 1; | 126 offsetof(EntryStore, key) - 1; |
112 | 127 |
| 128 // Possible states for a given entry. |
| 129 enum EntryState { |
| 130 ENTRY_NORMAL = 0, |
| 131 ENTRY_EVICTED, // The entry was recently evicted from the cache. |
| 132 ENTRY_DOOMED // The entry was doomed. |
| 133 }; |
| 134 |
113 #pragma pack(push, old, 4) | 135 #pragma pack(push, old, 4) |
114 // Rankings information for a given entry. | 136 // Rankings information for a given entry. |
115 struct RankingsNode { | 137 struct RankingsNode { |
116 uint64 last_used; // LRU info. | 138 uint64 last_used; // LRU info. |
117 uint64 last_modified; // LRU info. | 139 uint64 last_modified; // LRU info. |
118 CacheAddr next; // LRU list. | 140 CacheAddr next; // LRU list. |
119 CacheAddr prev; // LRU list. | 141 CacheAddr prev; // LRU list. |
120 CacheAddr contents; // Address of the EntryStore. | 142 CacheAddr contents; // Address of the EntryStore. |
121 int32 dirty; // The entry is being modifyied. | 143 int32 dirty; // The entry is being modifyied. |
122 void* pointer; // Pointer to the in-memory entry. | 144 void* pointer; // Pointer to the in-memory entry. |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
159 version = kCurrentVersion; | 181 version = kCurrentVersion; |
160 }; | 182 }; |
161 }; | 183 }; |
162 | 184 |
163 COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); | 185 COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); |
164 | 186 |
165 } // namespace disk_cache | 187 } // namespace disk_cache |
166 | 188 |
167 #endif // NET_DISK_CACHE_DISK_FORMAT_H__ | 189 #endif // NET_DISK_CACHE_DISK_FORMAT_H__ |
168 | 190 |
OLD | NEW |