Documentation/technical/bitmap-format.txt

   1 GIT bitmap v1 format
   2 ====================
   3
   4 == Pack and multi-pack bitmaps
   5
   6 Bitmaps store reachability information about the set of objects in a packfile,
   7 or a multi-pack index (MIDX). The former is defined obviously, and the latter is
   8 defined as the union of objects in packs contained in the MIDX.
   9
  10 A bitmap may belong to either one pack, or the repository's multi-pack index (if
  11 it exists). A repository may have at most one bitmap.
  12
  13 An 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 +
  29 The ordering between packs is done according to the MIDX's .rev file.
  30 Notably, the preferred pack sorts ahead of all other packs.
  31
  32 The on-disk representation (described below) of a bitmap is the same regardless
  33 of whether or not that bitmap belongs to a packfile or a MIDX. The only
  34 difference is the interpretation of the bits, which is described above.
  35
  36 Certain bitmap extensions are supported (see: Appendix B). No extensions are
  37 required for bitmaps corresponding to packfiles. For bitmaps that correspond to
  38 MIDXs, 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         4-byte entry count (network byte order): ::
  76             The total count of entries (bitmapped commits) in this bitmap index.
  77
  78         20-byte checksum: ::
  79             The SHA1 checksum of the pack/MIDX this bitmap index
  80             belongs to.
  81
  82     * 4 EWAH bitmaps that act as type indexes
  83 +
  84 Type indexes are serialized after the hash cache in the shape
  85 of four EWAH bitmaps stored consecutively (see Appendix A for
  86 the serialization format of an EWAH bitmap).
  87 +
  88 There is a bitmap for each Git object type, stored in the following
  89 order:
  90 +
  91     - Commits
  92     - Trees
  93     - Blobs
  94     - Tags
  95
  96 +
  97 In each bitmap, the `n`th bit is set to true if the `n`th object
  98 in the packfile or multi-pack index is of that type.
  99 +
 100 The obvious consequence is that the OR of all 4 bitmaps will result
 101 in a full set (all bits set), and the AND of all 4 bitmaps will
 102 result in an empty bitmap (no bits set).
 103
 104     * N entries with compressed bitmaps, one for each indexed commit
 105 +
 106 Where `N` is the total amount of entries in this bitmap index.
 107 Each entry contains the following:
 108
 109         ** {empty}
 110         4-byte object position (network byte order): ::
 111             The position **in the index for the packfile or
 112             multi-pack index** where the bitmap for this commit is
 113             found.
 114
 115         ** {empty}
 116         1-byte XOR-offset: ::
 117             The xor offset used to compress this bitmap. For an entry
 118             in position `x`, a XOR offset of `y` means that the actual
 119             bitmap representing this commit is composed by XORing the
 120             bitmap for this entry with the bitmap in entry `x-y` (i.e.
 121             the bitmap `y` entries before this one).
 122 +
 123 NOTE: This compression can be recursive. In order to
 124 XOR this entry with a previous one, the previous entry needs
 125 to be decompressed first, and so on.
 126 +
 127 The hard-limit for this offset is 160 (an entry can only be
 128 xor'ed against one of the 160 entries preceding it). This
 129 number is always positive, and hence entries are always xor'ed
 130 with **previous** bitmaps, not bitmaps that will come afterwards
 131 in the index.
 132
 133         ** {empty}
 134         1-byte flags for this bitmap: ::
 135             At the moment the only available flag is `0x1`, which hints
 136             that this bitmap can be re-used when rebuilding bitmap indexes
 137             for the repository.
 138
 139         ** The compressed bitmap itself, see Appendix A.
 140
 141         * {empty}
 142         TRAILER: ::
 143                 Trailing checksum of the preceding contents.
 144
 145 == Appendix A: Serialization format for an EWAH bitmap
 146
 147 Ewah bitmaps are serialized in the same protocol as the JAVAEWAH
 148 library, making them backwards compatible with the JGit
 149 implementation:
 150
 151         - 4-byte number of bits of the resulting UNCOMPRESSED bitmap
 152
 153         - 4-byte number of words of the COMPRESSED bitmap, when stored
 154
 155         - N x 8-byte words, as specified by the previous field
 156 +
 157 This is the actual content of the compressed bitmap.
 158
 159         - 4-byte position of the current RLW for the compressed
 160                 bitmap
 161
 162 All words are stored in network byte order for their corresponding
 163 sizes.
 164
 165 The compressed bitmap is stored in a form of run-length encoding, as
 166 follows.  It consists of a concatenation of an arbitrary number of
 167 chunks.  Each chunk consists of one or more 64-bit words
 168
 169      H  L_1  L_2  L_3 .... L_M
 170
 171 H is called RLW (run length word).  It consists of (from lower to higher
 172 order bits):
 173
 174      - 1 bit: the repeated bit B
 175
 176      - 32 bits: repetition count K (unsigned)
 177
 178      - 31 bits: literal word count M (unsigned)
 179
 180 The bitstream represented by the above chunk is then:
 181
 182      - K repetitions of B
 183
 184      - The bits stored in `L_1` through `L_M`.  Within a word, bits at
 185        lower order come earlier in the stream than those at higher
 186        order.
 187
 188 The next word after `L_M` (if any) must again be a RLW, for the next
 189 chunk.  For efficient appending to the bitstream, the EWAH stores a
 190 pointer to the last RLW in the stream.
 191
 192
 193 == Appendix B: Optional Bitmap Sections
 194
 195 These sections may or may not be present in the `.bitmap` file; their
 196 presence is indicated by the header flags section described above.
 197
 198 Name-hash cache
 199 ---------------
 200
 201 If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
 202 a cache of 32-bit values, one per object in the pack/MIDX. The value at
 203 position `i` is the hash of the pathname at which the `i`th object
 204 (counting in index or multi-pack index order) in the pack/MIDX can be found.
 205 This can be fed into the delta heuristics to compare objects with similar
 206 pathnames.
 207
 208 The hash algorithm used is:
 209
 210     hash = 0;
 211     while ((c = *name++))
 212             if (!isspace(c))
 213                     hash = (hash >> 2) + (c << 24);
 214
 215 Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
 216 If implementations want to choose a different hashing scheme, they are
 217 free to do so, but MUST allocate a new header flag (because comparing
 218 hashes made under two different schemes would be pointless).