##// END OF EJS Templates
help: don't let tools reflow revlog flags list...
Martin von Zweigbergk -
r30828:0b792507 default
parent child Browse files
Show More
@@ -1,210 +1,212 b''
1 1 Revision logs - or *revlogs* - are an append only data structure for
2 2 storing discrete entries, or *revisions*. They are the primary storage
3 3 mechanism of repository data.
4 4
5 5 Revlogs effectively model a directed acyclic graph (DAG). Each node
6 6 has edges to 1 or 2 *parent* nodes. Each node contains metadata and
7 7 the raw value for that node.
8 8
9 9 Revlogs consist of entries which have metadata and revision data.
10 10 Metadata includes the hash of the revision's content, sizes, and
11 11 links to its *parent* entries. The collective metadata is referred
12 12 to as the *index* and the revision data is the *data*.
13 13
14 14 Revision data is stored as a series of compressed deltas against previous
15 15 revisions.
16 16
17 17 Revlogs are written in an append-only fashion. We never need to rewrite
18 18 a file to insert nor do we need to remove data. Rolling back in-progress
19 19 writes can be performed by truncating files. Read locks can be avoided
20 20 using simple techniques. This means that references to other data in
21 21 the same revlog *always* refer to a previous entry.
22 22
23 23 Revlogs can be modeled as 0-indexed arrays. The first revision is
24 24 revision #0 and the second is revision #1. The revision -1 is typically
25 25 used to mean *does not exist* or *not defined*.
26 26
27 27 File Format
28 28 ===========
29 29
30 30 A revlog begins with a 32-bit big endian integer holding version info
31 31 and feature flags. This integer is shared with the first revision
32 32 entry.
33 33
34 34 This integer is logically divided into 2 16-bit shorts. The least
35 35 significant half of the integer is the format/version short. The other
36 36 short holds feature flags that dictate behavior of the revlog.
37 37
38 38 Only 1 bit of the format/version short is currently used. Remaining
39 39 bits are reserved for future use.
40 40
41 41 The following values for the format/version short are defined:
42 42
43 43 0
44 44 The original revlog version.
45 45 1
46 46 RevlogNG (*next generation*). It replaced version 0 when it was
47 47 implemented in 2006.
48 48
49 49 The feature flags short consists of bit flags. Where 0 is the least
50 50 significant bit, the following bit offsets define flags:
51 51
52 52 0
53 53 Store revision data inline.
54 54 1
55 55 Generaldelta encoding.
56 56
57 57 2-15
58 58 Reserved for future use.
59 59
60 60 The following header values are common:
61 61
62 62 00 00 00 01
63 63 RevlogNG
64 64 00 01 00 01
65 65 RevlogNG + inline
66 66 00 02 00 01
67 67 RevlogNG + generaldelta
68 68 00 03 00 01
69 69 RevlogNG + inline + generaldelta
70 70
71 71 Following the 32-bit header is the remainder of the first index entry.
72 72 Following that are remaining *index* data. Inlined revision data is
73 73 possibly located between index entries. More on this layout is described
74 74 below.
75 75
76 76 RevlogNG Format
77 77 ===============
78 78
79 79 RevlogNG (version 1) begins with an index describing the revisions in
80 80 the revlog. If the ``inline`` flag is set, revision data is stored inline,
81 81 or between index entries (as opposed to in a separate container).
82 82
83 83 Each index entry is 64 bytes. The byte layout of each entry is as
84 84 follows, with byte 0 being the first byte (all data stored as big endian):
85 85
86 86 0-3 (4 bytes) (rev 0 only)
87 87 Revlog header
88 88
89 89 0-5 (6 bytes)
90 90 Absolute offset of revision data from beginning of revlog.
91 91
92 92 6-7 (2 bytes)
93 93 Bit flags impacting revision behavior. The following bit offsets define:
94
94 95 0: REVIDX_ISCENSORED revision has censor metadata, must be verified.
96
95 97 1: REVIDX_EXTSTORED revision data is stored externally.
96 98
97 99 8-11 (4 bytes)
98 100 Compressed length of revision data / chunk as stored in revlog.
99 101
100 102 12-15 (4 bytes)
101 103 Uncompressed length of revision data. This is the size of the full
102 104 revision data, not the size of the chunk post decompression.
103 105
104 106 16-19 (4 bytes)
105 107 Base or previous revision this revision's delta was produced against.
106 108 -1 means this revision holds full text (as opposed to a delta).
107 109 For generaldelta repos, this is the previous revision in the delta
108 110 chain. For non-generaldelta repos, this is the base or first
109 111 revision in the delta chain.
110 112
111 113 20-23 (4 bytes)
112 114 A revision this revision is *linked* to. This allows a revision in
113 115 one revlog to be forever associated with a revision in another
114 116 revlog. For example, a file's revlog may point to the changelog
115 117 revision that introduced it.
116 118
117 119 24-27 (4 bytes)
118 120 Revision of 1st parent. -1 indicates no parent.
119 121
120 122 28-31 (4 bytes)
121 123 Revision of 2nd parent. -1 indicates no 2nd parent.
122 124
123 125 32-63 (32 bytes)
124 126 Hash of revision's full text. Currently, SHA-1 is used and only
125 127 the first 20 bytes of this field are used. The rest of the bytes
126 128 are ignored and should be stored as \0.
127 129
128 130 If inline revision data is being stored, the compressed revision data
129 131 (of length from bytes offset 8-11 from the index entry) immediately
130 132 follows the index entry. There is no header on the revision data. There
131 133 is no padding between it and the index entries before and after.
132 134
133 135 If revision data is not inline, then raw revision data is stored in a
134 136 separate byte container. The offsets from bytes 0-5 and the compressed
135 137 length from bytes 8-11 define how to access this data.
136 138
137 139 The first 4 bytes of the revlog are shared between the revlog header
138 140 and the 6 byte absolute offset field from the first revlog entry.
139 141
140 142 Delta Chains
141 143 ============
142 144
143 145 Revision data is encoded as a chain of *chunks*. Each chain begins with
144 146 the compressed original full text for that revision. Each subsequent
145 147 *chunk* is a *delta* against the previous revision. We therefore call
146 148 these chains of chunks/deltas *delta chains*.
147 149
148 150 The full text for a revision is reconstructed by loading the original
149 151 full text for the base revision of a *delta chain* and then applying
150 152 *deltas* until the target revision is reconstructed.
151 153
152 154 *Delta chains* are limited in length so lookup time is bound. They are
153 155 limited to ~2x the length of the revision's data. The linear distance
154 156 between the base chunk and the final chunk is also limited so the
155 157 amount of read I/O to load all chunks in the delta chain is bound.
156 158
157 159 Deltas and delta chains are either computed against the previous
158 160 revision in the revlog or another revision (almost certainly one of
159 161 the parents of the revision). Historically, deltas were computed against
160 162 the previous revision. The *generaldelta* revlog feature flag (enabled
161 163 by default in Mercurial 3.7) activates the mode where deltas are
162 164 computed against an arbitrary revision (almost certainly a parent revision).
163 165
164 166 File Storage
165 167 ============
166 168
167 169 Revlogs logically consist of an index (metadata of entries) and
168 170 revision data. This data may be stored together in a single file or in
169 171 separate files. The mechanism used is indicated by the ``inline`` feature
170 172 flag on the revlog.
171 173
172 174 Mercurial's behavior is to use inline storage until a revlog reaches a
173 175 certain size, at which point it will be converted to non-inline. The
174 176 reason there is a size limit on inline storage is to establish an upper
175 177 bound on how much data must be read to load the index. It would be a waste
176 178 to read tens or hundreds of extra megabytes of data just to access the
177 179 index data.
178 180
179 181 The actual layout of revlog files on disk is governed by the repository's
180 182 *store format*. Typically, a ``.i`` file represents the index revlog
181 183 (possibly containing inline data) and a ``.d`` file holds the revision data.
182 184
183 185 Revision Entries
184 186 ================
185 187
186 188 Revision entries consist of an optional 1 byte header followed by an
187 189 encoding of the revision data. The headers are as follows:
188 190
189 191 \0 (0x00)
190 192 Revision data is the entirety of the entry, including this header.
191 193 u (0x75)
192 194 Raw revision data follows.
193 195 x (0x78)
194 196 zlib (RFC 1950) data.
195 197
196 198 The 0x78 value is actually the first byte of the zlib header (CMF byte).
197 199
198 200 Hash Computation
199 201 ================
200 202
201 203 The hash of the revision is stored in the index and is used both as a primary
202 204 key and for data integrity verification.
203 205
204 206 Currently, SHA-1 is the only supported hashing algorithm. To obtain the SHA-1
205 207 hash of a revision:
206 208
207 209 1. Hash the parent nodes
208 210 2. Hash the fulltext of the revision
209 211
210 212 The 20 byte node ids of the parents are fed into the hasher in ascending order.
General Comments 0
You need to be logged in to leave comments. Login now