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