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