freshlybakedca.ke
Git fork
1GIT bitmap v1 format
2====================
3
4== Pack and multi-pack bitmaps
5
6Bitmaps store reachability information about the set of objects in a packfile,
7or a multi-pack index (MIDX). The former is defined obviously, and the latter is
8defined as the union of objects in packs contained in the MIDX.
9
10A bitmap may belong to either one pack, or the repository's multi-pack index (if
11it exists). A repository may have at most one bitmap.
12
13An object is uniquely described by its bit position within a bitmap:
14
15 - If the bitmap belongs to a packfile, the __n__th bit corresponds to
16 the __n__th object in pack order. For a function `offset` which maps
17 objects to their byte offset within a pack, pack order is defined as
18 follows:
19
20 o1 <= o2 <==> offset(o1) <= offset(o2)
21
22 - If the bitmap belongs to a MIDX, the __n__th bit corresponds to the
23 __n__th object in MIDX order. With an additional function `pack` which
24 maps objects to the pack they were selected from by the MIDX, MIDX order
25 is defined as follows:
26
27 o1 <= o2 <==> pack(o1) <= pack(o2) /\ offset(o1) <= offset(o2)
28+
29The ordering between packs is done according to the MIDX's .rev file.
30Notably, the preferred pack sorts ahead of all other packs.
31
32The on-disk representation (described below) of a bitmap is the same regardless
33of whether or not that bitmap belongs to a packfile or a MIDX. The only
34difference is the interpretation of the bits, which is described above.
35
36Certain bitmap extensions are supported (see: Appendix B). No extensions are
37required for bitmaps corresponding to packfiles. For bitmaps that correspond to
38MIDXs, both the bit-cache and rev-cache extensions are required.
39
40== On-disk format
41
42 * A header appears at the beginning:
43
44 4-byte signature: :: {'B', 'I', 'T', 'M'}
45
46 2-byte version number (network byte order): ::
47
48 The current implementation only supports version 1
49 of the bitmap index (the same one as JGit).
50
51 2-byte flags (network byte order): ::
52
53 The following flags are supported:
54
55 ** {empty}
56 BITMAP_OPT_FULL_DAG (0x1) REQUIRED: :::
57
58 This flag must always be present. It implies that the
59 bitmap index has been generated for a packfile or
60 multi-pack index (MIDX) with full closure (i.e. where
61 every single object in the packfile/MIDX can find its
62 parent links inside the same packfile/MIDX). This is a
63 requirement for the bitmap index format, also present in
64 JGit, that greatly reduces the complexity of the
65 implementation.
66
67 ** {empty}
68 BITMAP_OPT_HASH_CACHE (0x4): :::
69
70 If present, the end of the bitmap file contains
71 `N` 32-bit name-hash values, one per object in the
72 pack/MIDX. The format and meaning of the name-hash is
73 described below.
74
75 ** {empty}
76 BITMAP_OPT_LOOKUP_TABLE (0x10): :::
77 If present, the end of the bitmap file contains a table
78 containing a list of `N` <commit_pos, offset, xor_row>
79 triplets. The format and meaning of the table is described
80 below.
81+
82NOTE: Unlike the xor_offset used to compress an individual bitmap,
83`xor_row` stores an *absolute* index into the lookup table, not a location
84relative to the current entry.
85
86 4-byte entry count (network byte order): ::
87 The total count of entries (bitmapped commits) in this bitmap index.
88
89 20-byte checksum: ::
90 The SHA1 checksum of the pack/MIDX this bitmap index
91 belongs to.
92
93 * 4 EWAH bitmaps that act as type indexes
94+
95Type indexes are serialized after the hash cache in the shape
96of four EWAH bitmaps stored consecutively (see Appendix A for
97the serialization format of an EWAH bitmap).
98+
99There is a bitmap for each Git object type, stored in the following
100order:
101+
102 - Commits
103 - Trees
104 - Blobs
105 - Tags
106
107+
108In each bitmap, the `n`th bit is set to true if the `n`th object
109in the packfile or multi-pack index is of that type.
110+
111The obvious consequence is that the OR of all 4 bitmaps will result
112in a full set (all bits set), and the AND of all 4 bitmaps will
113result in an empty bitmap (no bits set).
114
115 * N entries with compressed bitmaps, one for each indexed commit
116+
117Where `N` is the total number of entries in this bitmap index.
118Each entry contains the following:
119
120 ** {empty}
121 4-byte object position (network byte order): ::
122 The position **in the index for the packfile or
123 multi-pack index** where the bitmap for this commit is
124 found.
125
126 ** {empty}
127 1-byte XOR-offset: ::
128 The xor offset used to compress this bitmap. For an entry
129 in position `x`, an XOR offset of `y` means that the actual
130 bitmap representing this commit is composed by XORing the
131 bitmap for this entry with the bitmap in entry `x-y` (i.e.
132 the bitmap `y` entries before this one).
133+
134NOTE: This compression can be recursive. In order to
135XOR this entry with a previous one, the previous entry needs
136to be decompressed first, and so on.
137+
138The hard-limit for this offset is 160 (an entry can only be
139xor'ed against one of the 160 entries preceding it). This
140number is always positive, and hence entries are always xor'ed
141with **previous** bitmaps, not bitmaps that will come afterwards
142in the index.
143
144 ** {empty}
145 1-byte flags for this bitmap: ::
146 At the moment the only available flag is `0x1`, which hints
147 that this bitmap can be re-used when rebuilding bitmap indexes
148 for the repository.
149
150 ** The compressed bitmap itself, see Appendix A.
151
152 * {empty}
153 TRAILER: ::
154 Trailing checksum of the preceding contents.
155
156== Appendix A: Serialization format for an EWAH bitmap
157
158Ewah bitmaps are serialized in the same protocol as the JAVAEWAH
159library, making them backwards compatible with the JGit
160implementation:
161
162 - 4-byte number of bits of the resulting UNCOMPRESSED bitmap
163
164 - 4-byte number of words of the COMPRESSED bitmap, when stored
165
166 - N x 8-byte words, as specified by the previous field
167+
168This is the actual content of the compressed bitmap.
169
170 - 4-byte position of the current RLW for the compressed
171 bitmap
172
173All words are stored in network byte order for their corresponding
174sizes.
175
176The compressed bitmap is stored in a form of run-length encoding, as
177follows. It consists of a concatenation of an arbitrary number of
178chunks. Each chunk consists of one or more 64-bit words
179
180 H L_1 L_2 L_3 .... L_M
181
182H is called RLW (run length word). It consists of (from lower to higher
183order bits):
184
185 - 1 bit: the repeated bit B
186
187 - 32 bits: repetition count K (unsigned)
188
189 - 31 bits: literal word count M (unsigned)
190
191The bitstream represented by the above chunk is then:
192
193 - K repetitions of B
194
195 - The bits stored in `L_1` through `L_M`. Within a word, bits at
196 lower order come earlier in the stream than those at higher
197 order.
198
199The next word after `L_M` (if any) must again be a RLW, for the next
200chunk. For efficient appending to the bitstream, the EWAH stores a
201pointer to the last RLW in the stream.
202
203
204== Appendix B: Optional Bitmap Sections
205
206These sections may or may not be present in the `.bitmap` file; their
207presence is indicated by the header flags section described above.
208
209Name-hash cache
210---------------
211
212If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
213a cache of 32-bit values, one per object in the pack/MIDX. The value at
214position `i` is the hash of the pathname at which the `i`th object
215(counting in index or multi-pack index order) in the pack/MIDX can be found.
216This can be fed into the delta heuristics to compare objects with similar
217pathnames.
218
219The hash algorithm used is:
220
221 hash = 0;
222 while ((c = *name++))
223 if (!isspace(c))
224 hash = (hash >> 2) + (c << 24);
225
226Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
227If implementations want to choose a different hashing scheme, they are
228free to do so, but MUST allocate a new header flag (because comparing
229hashes made under two different schemes would be pointless).
230
231Commit lookup table
232-------------------
233
234If the BITMAP_OPT_LOOKUP_TABLE flag is set, the last `N * (4 + 8 + 4)`
235bytes (preceding the name-hash cache and trailing hash) of the `.bitmap`
236file contains a lookup table specifying the information needed to get
237the desired bitmap from the entries without parsing previous unnecessary
238bitmaps.
239
240For a `.bitmap` containing `nr_entries` reachability bitmaps, the table
241contains a list of `nr_entries` <commit_pos, offset, xor_row> triplets
242(sorted in the ascending order of `commit_pos`). The content of the i'th
243triplet is -
244
245 * {empty}
246 commit_pos (4 byte integer, network byte order): ::
247 It stores the object position of a commit (in the midx or pack
248 index).
249
250 * {empty}
251 offset (8 byte integer, network byte order): ::
252 The offset from which that commit's bitmap can be read.
253
254 * {empty}
255 xor_row (4 byte integer, network byte order): ::
256 The position of the triplet whose bitmap is used to compress
257 this one, or `0xffffffff` if no such bitmap exists.
258
259Pseudo-merge bitmaps
260--------------------
261
262If the `BITMAP_OPT_PSEUDO_MERGES` flag is set, a variable number of
263bytes (preceding the name-hash cache, commit lookup table, and trailing
264checksum) of the `.bitmap` file is used to store pseudo-merge bitmaps.
265
266For more information on what pseudo-merges are, why they are useful, and
267how to configure them, see the information in linkgit:gitpacking[7].
268
269=== File format
270
271If enabled, pseudo-merge bitmaps are stored in an optional section at
272the end of a `.bitmap` file. The format is as follows:
273
274....
275+-------------------------------------------+
276| .bitmap File |
277+-------------------------------------------+
278| |
279| Pseudo-merge bitmaps (Variable Length) |
280| +---------------------------+ |
281| | commits_bitmap (EWAH) | |
282| +---------------------------+ |
283| | merge_bitmap (EWAH) | |
284| +---------------------------+ |
285| |
286+-------------------------------------------+
287| |
288| Lookup Table |
289| +---------------------------+ |
290| | commit_pos (4 bytes) | |
291| +---------------------------+ |
292| | offset (8 bytes) | |
293| +------------+--------------+ |
294| |
295| Offset Cases: |
296| ------------- |
297| |
298| 1. MSB Unset: single pseudo-merge bitmap |
299| + offset to pseudo-merge bitmap |
300| |
301| 2. MSB Set: multiple pseudo-merges |
302| + offset to extended lookup table |
303| |
304+-------------------------------------------+
305| |
306| Extended Lookup Table (Optional) |
307| +----+----------+----------+----------+ |
308| | N | Offset 1 | .... | Offset N | |
309| +----+----------+----------+----------+ |
310| | | 8 bytes | .... | 8 bytes | |
311| +----+----------+----------+----------+ |
312| |
313+-------------------------------------------+
314| |
315| Pseudo-merge position table |
316| +----+----------+----------+----------+ |
317| | N | Offset 1 | .... | Offset N | |
318| +----+----------+----------+----------+ |
319| | | 8 bytes | .... | 8 bytes | |
320| +----+----------+----------+----------+ |
321| |
322+-------------------------------------------+
323| |
324| Pseudo-merge Metadata |
325| +-----------------------------------+ |
326| | # pseudo-merges (4 bytes) | |
327| +-----------------------------------+ |
328| | # commits (4 bytes) | |
329| +-----------------------------------+ |
330| | Lookup offset (8 bytes) | |
331| +-----------------------------------+ |
332| | Extension size (8 bytes) | |
333| +-----------------------------------+ |
334| |
335+-------------------------------------------+
336....
337
338* One or more pseudo-merge bitmaps, each containing:
339
340 ** `commits_bitmap`, an EWAH-compressed bitmap describing the set of
341 commits included in the this psuedo-merge.
342
343 ** `merge_bitmap`, an EWAH-compressed bitmap describing the union of
344 the set of objects reachable from all commits listed in the
345 `commits_bitmap`.
346
347* A lookup table, mapping pseudo-merged commits to the pseudo-merges
348 they belong to. Entries appear in increasing order of each commit's
349 bit position. Each entry is 12 bytes wide, and is comprised of the
350 following:
351
352 ** `commit_pos`, a 4-byte unsigned value (in network byte-order)
353 containing the bit position for this commit.
354
355 ** `offset`, an 8-byte unsigned value (also in network byte-order)
356 containing either one of two possible offsets, depending on whether or
357 not the most-significant bit is set.
358
359 *** If unset (i.e. `offset & ((uint64_t)1<<63) == 0`), the offset
360 (relative to the beginning of the `.bitmap` file) at which the
361 pseudo-merge bitmap for this commit can be read. This indicates
362 only a single pseudo-merge bitmap contains this commit.
363
364 *** If set (i.e. `offset & ((uint64_t)1<<63) != 0`), the offset
365 (again relative to the beginning of the `.bitmap` file) at which
366 the extended offset table can be located describing the set of
367 pseudo-merge bitmaps which contain this commit. This indicates
368 that multiple pseudo-merge bitmaps contain this commit.
369
370* An (optional) extended lookup table (written if and only if there is
371 at least one commit which appears in more than one pseudo-merge).
372 There are as many entries as commits which appear in multiple
373 pseudo-merges. Each entry contains the following:
374
375 ** `N`, a 4-byte unsigned value equal to the number of pseudo-merges
376 which contain a given commit.
377
378 ** An array of `N` 8-byte unsigned values, each of which is
379 interpreted as an offset (relative to the beginning of the
380 `.bitmap` file) at which a pseudo-merge bitmap for this commit can
381 be read. These values occur in no particular order.
382
383* Positions for all pseudo-merges, each stored as an 8-byte unsigned
384 value (in network byte-order) containing the offset (relative to the
385 beginning of the `.bitmap` file) of each consecutive pseudo-merge.
386
387* A 4-byte unsigned value (in network byte-order) equal to the number of
388 pseudo-merges.
389
390* A 4-byte unsigned value (in network byte-order) equal to the number of
391 unique commits which appear in any pseudo-merge.
392
393* An 8-byte unsigned value (in network byte-order) equal to the number
394 of bytes between the start of the pseudo-merge section and the
395 beginning of the lookup table.
396
397* An 8-byte unsigned value (in network byte-order) equal to the number
398 of bytes in the pseudo-merge section (including this field).