ewah: compressed bitmap implementation

EWAH is a word-aligned compressed variant of a bitset (i.e. a data
structure that acts as a 0-indexed boolean array for many entries).

It uses a 64-bit run-length encoding (RLE) compression scheme,
trading some compression for better processing speed.

The goal of this word-aligned implementation is not to achieve
the best compression, but rather to improve query processing time.
As it stands right now, this EWAH implementation will always be more
efficient storage-wise than its uncompressed alternative.

EWAH arrays will be used as the on-disk format to store reachability
bitmaps for all objects in a repository while keeping reasonable sizes,
in the same way that JGit does.

This EWAH implementation is a mostly straightforward port of the
original `javaewah` library that JGit currently uses. The library is
self-contained and has been embedded whole (4 files) inside the `ewah`
folder to ease redistribution.

The library is re-licensed under the GPLv2 with the permission of Daniel
Lemire, the original author. The source code for the C version can
be found on GitHub:

	https://github.com/vmg/libewok

The original Java implementation can also be found on GitHub:

	https://github.com/lemire/javaewah

Signed-off-by: Vicent Marti <tanoku@gmail.com>
documentation: add documentation for the bitmap format

This is the technical documentation and design rationale for the new
Bitmap v2 on-disk format.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
pack-objects: use bitmaps when packing objects

A bitmap index is used, if available, to speed up the Counting Objects
phase during `pack-objects`.

The bitmap index is a `.bitmap` file that can be found inside
`$GIT_DIR/objects/pack/`, next to its corresponding packfile, and
contains precalculated reachability information for selected commits.
The full specification of the format for these bitmap indexes can be found
in `Documentation/technical/bitmap-format.txt`.

For a given commit SHA1, if it happens to be available in the bitmap
index, its bitmap will represent every single object that is reachable
from the commit itself. The nth bit in the bitmap is the nth object in
the index of the packfile; if it's set to 1, the object is reachable.

By using the bitmaps available in the index, this commit implements a new
pair of functions:

	- `prepare_bitmap_walk`
	- `traverse_bitmap_commit_list`

This first function tries to build a bitmap of all the objects that can be
reached from the commit roots of a given `rev_info` struct by using
the following algorithm:

- If all the interesting commits for a revision walk are available in
the index, the resulting reachability bitmap is the bitwise OR of all
the individual bitmaps.

- When the full set of WANTs is not available in the index, we perform a
partial revision walk using the commits that don't have bitmaps as
roots, and limiting the revision walk as soon as we reach a commit that
has a corresponding bitmap. The earlier OR'ed bitmap with all the
indexed commits can now be completed as this walk progresses, so the end
result is the full reachability list.

- For revision walks with a HAVEs set (a set of commits that are deemed
uninteresting), first we perform the same method as for the WANTs, but
using our HAVEs as roots, in order to obtain a full reachability bitmap
of all the uninteresting commits. This bitmap then can be used to:

	a) limit the subsequent walk when building the WANTs bitmap
	b) finding the final set of interesting commits by performing an
	   AND-NOT of the WANTs and the HAVEs.

If `prepare_bitmap_walk` runs successfully, the resulting bitmap is
stored and the equivalent of a `traverse_commit_list` call can be
performed by using `traverse_bitmap_commit_list`; the bitmap version
of this call yields the objects straight from the packfile index
(without having to look them up or parse them) and hence is several
orders of magnitude faster.

If the `prepare_bitmap_walk` call fails (e.g. because no bitmap files
are available), the `rev_info` struct is left untouched, and can be used
to perform a manual rev-walk using `traverse_commit_list`.

Hence, this new pair of functions are a generic API that allows to
perform the equivalent of

	git rev-list --objects [roots...] [^uninteresting...]

for any set of commits, even if they don't have specific bitmaps
generated for them.

In this specific commit, we use the API to perform the
`Counting Objects` phase in `builtin/pack-objects.c`, although it could
be used to speed up other parts of Git that use the same mechanism.

If the pack-objects invocation is being piped to `stdout` (like a normal
`pack-objects` from `upload-pack` would be used) and bitmaps are
enabled, the new `bitmap_walk` API will be used instead of
`traverse_commit_list`.

There are two ways to enable bitmaps for pack-objecs:

	- Pass the `--use-bitmaps` flag when calling `pack-objects`
	- Set `pack.usebitmaps` to `true` in the git config for the
	repository.

Of course, simply enabling the bitmaps is not enought to perform the
optimization: a bitmap index must be available on disk. If no bitmap
index can be found, we'll silently fall back to the slow counting
objects phase.

The point of speeding up the Counting Objects phase of `pack-objects` is
to reduce fetch and clone times for big repositories, which right now
are definitely dominated by the rev-walk algorithm during the Counting
Objects phase.

Here are some sample timings from a full pack of `torvalds/linux` (i.e.
something very similar to what would be generated for a clone of the
repository):

	$ time ../git/git pack-objects --all --stdout
	Counting objects: 3053537, done.
	Compressing objects: 100% (495706/495706), done.
	Total 3053537 (delta 2529614), reused 3053537 (delta 2529614)

	real    0m36.686s
	user    0m34.440s
	sys     0m2.184s

	$ time ../git/git pack-objects --all --stdout
	Counting objects: 3053537, done.
	Compressing objects: 100% (495706/495706), done.
	Total 3053537 (delta 2529614), reused 3053537 (delta 2529614)

	real    0m7.255s
	user    0m6.892s
	sys     0m0.444s

From a hotspot profiling run, we can see how the counting
objects phase has been reduced to about 400ms (down from 28s).
The remaining time is spent finding deltas and writing the packfile, the
optimization of which is out of the scope of this topic.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
rev-list: add bitmap mode to speed up lists

The bitmap reachability index used to speed up the counting objects
phase during `pack-objects` can also be used to optimize a normal
rev-list if the only thing required are the SHA1s of the objects during
the list.

Calling `git rev-list --use-bitmaps [committish]` is the equivalent
of `git rev-list --objects`, but the rev list is performed based on
a bitmap result instead of using a manual counting objects phase.

These are some example timings for `torvalds/linux`:

	$ time ../git/git rev-list --objects master > /dev/null

	real    0m25.567s
	user    0m25.148s
	sys     0m0.384s

	$ time ../git/git rev-list --use-bitmaps master > /dev/null

	real    0m0.393s
	user    0m0.356s
	sys     0m0.036s

Additionally, a `--test-bitmap` flag has been added that will perform
the same rev-list manually (i.e. using a normal revwalk) and using
bitmaps, and verify that the results are the same.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
pack-objects: implement bitmap writing

This commit extends more the functionality of `pack-objects` by allowing
it to write out a `.bitmap` index next to any written packs, together
with the `.idx` index that currently gets written.

If bitmaps are enabled for a given repository (either by calling
`pack-objects` with the `--use-bitmaps` flag or by having
`pack.usebitmaps` set to `true` in the config) and pack-objects is
writing a packfile that would normally be indexed (i.e. not piping to
stdout), we will attempt to write the corresponding bitmap index for the
packfile.

Bitmap index writing happens after the packfile and its index has been
successfully written to disk (`finish_tmp_packfile`). The process is
performed in several steps:

	1. `bitmap_writer_build_type_index`: this call uses the array of
	`struct object_entry`es that has just been sorted when writing out
	the actual packfile index to disk to generate 4 type-index bitmaps
	(one for each object type).

	These bitmaps have their nth bit set if the given object is of the
	bitmap's type. E.g. the nth bit of the Commits bitmap will be 1 if
	the nth object in the packfile index is a commit.

	This is a very cheap operation because the bitmap writing code has
	access to the metadata stored in the `struct object_entry` array,
	and hence the real type for each object in the packfile.

	2. `bitmap_writer_select_commits`: if bitmap writing is enabled for
	a given `pack-objects` run, the sequence of commits generated during
	the Counting Objects phase will be stored in an array.

	We then use that array to build up the list of selected commits.
	Writing a bitmap in the index for each object in the repository
	would be cost-prohibitive, so we use a simple heuristic to pick the
	commits that will be indexed with bitmaps.

	The current heuristics are a simplified version of JGit's original
	implementation. We select a higher density of commits depending on
	their age: the 100 most recent commits are always selected, after
	that we pick 1 commit of each 100, and the gap increases as the
	commits grow older. On top of that, we make sure that every single
	branch that has not been merged (all the tips that would be required
	from a clone) gets their own bitmap, and when selecting commits
	between a gap, we tend to prioritize the commit with the most
	parents.

	Do note that there is no right/wrong way to perform commit selection;
	different selection algorithms will result in different commits
	being selected, but there's no such thing as "missing a commit". The
	bitmap walker algorithm implemented in `prepare_bitmap_walk` is able
	to adapt to missing bitmaps by performing manual walks that complete
	the bitmap: the ideal selection algorithm, however, would select
	the commits that are more likely to be used as roots for a walk in
	the future (e.g. the tips of each branch, and so on) to ensure a
	bitmap for them is always available.

	3. `bitmap_writer_build`: this is the computationally expensive part
	of bitmap generation. Based on the list of commits that were
	selected in the previous step, we perform several incremental walks
	to generate the bitmap for each commit.

	The walks begin from the oldest commit, and are built up
	incrementally for each branch. E.g. consider this dag where A, B, C,
	D, E, F are the selected commits, and a, b, c, e are a chunk of
	simplified history that will not receive bitmaps.

		A---a---B--b--C--c--D
		         \
		          E--e--F

	We start by building the bitmap for A, using A as the root for a
	revision walk and marking all the objects that are reachable until
	the walk is over. Once this bitmap is stored, we reuse the bitmap
	walker to perform the walk for B, assuming that once we reach A
	again, the walk will be terminated because A has already been SEEN
	on the previous walk.

	This process is repeated for C, and D, but when we try to generate
	the bitmaps for E, we cannot reuse neither the current walk nor the
	bitmap we have generated so far.

	What we do now is resetting both the walk and clearing the bitmap,
	and performing the walk from scratch using E as the origin. This new
	walk, however, does not need to be completed. Once we hit B, we can
	lookup the bitmap we have already stored for that commit and OR it
	with the existing bitmap we've composed so far, allowing us to limit
	the walk early.

	After all the bitmaps have been generated, another iteration through
	the list of commits is performed to find the best XOR offsets for
	compression before writing them to disk. Because of the incremental
	nature of these bitmaps, XORing one of them with its predecesor
	results in a minimal "bitmap delta" most of the time. We can write
	this delta to the on-disk bitmap index, and then re-compose the
	original bitmaps by XORing them again when loaded.

	This is a phase very similar to pack-object's `find_delta` (using
	bitmaps instead of objects, of course), except the heuristics have
	been greatly simplified: we only check the 10 bitmaps before any
	given one to find best compressing one. This operation gives optimal
	results (again, because of the incremental nature of the bitmaps)
	and has a very good runtime performance because of the way EWAH
	bitmaps are implemented.

	3. `bitmap_writer_finish`: the last step in the process is
	serializing to disk all the bitmap data that has been generated in
	the two previous steps.

	The bitmap is written to a tmp file and then moved atomically to its
	final destination, using the same process as `pack-write.c:write_idx_file`.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
repack: consider bitmaps when performing repacks

Since `pack-objects` will write a `.bitmap` file next to the `.pack` and
`.idx` files, this commit teaches `git-repack` to consider the new
bitmap indexes (if they exist) when performing repack operations.

This implies moving old bitmap indexes out of the way if we are
repacking a repository that already has them, and moving the newly
generated bitmap indexes into the `objects/pack` directory, next to
their corresponding packfiles.

Since `git repack` is now capable of handling these `.bitmap` files,
a normal `git gc` run on a repository that has `pack.usebitmaps` set
to true in its config file will generate bitmap indexes as part of the
garbage collection process.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
sha1_file: implement `nth_packed_object_info`

A new helper function allows to efficiently query the size and real type
of an object in a packfile based on its position on the packfile index.

This is particularly useful when trying to parse all the information of
an index in memory.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
write-bitmap: implement new git command to write bitmaps

The `pack-objects` builtin is capable of writing out bitmap indexes
(.bitmap) next to the their corresponding packfile, as part of the
process of actually generating the packfile.

This is a very efficient operation because all the required data for
writing the bitmap index (commit traversal list, list of all objects in
a packfile, sorted index for the packfile, and types for all objects in
the packfile) is readily available in memory as part of the process of
building the packfile itself.

There are however cases when we want to generate a bitmap index for a
packfile that already exists on disk (i.e. one we're not writing from
scratch). This new git builtin implements the bitmap index equivalent of
`git index-pack`: it writes a `.bitmap` file given a pair of existing
`.pack` and `.idx` files.

	NOTE that `write-bitmap` requires the packfile to have been indexed
	beforehand. If the packfile doesn't have its corresponding `.idx`
	file, `git index-pack` must be called before `write-bitmap` can
	work.

The process of generating bitmaps for an existing packfile is as
follows:

	1. Load the existing pack index in memory. The `.idx` for the
	packfile is loaded into a hash table in mememory so it can be
	efficiently queried. As part of this loading process, the real type
	for each object in the packfile is resolved (this implies resolving
	deltas, which can make this process rather expensive).

	2. Find the full closure for the packfile. All the objects from the
	packfile that have been loaded in memory are iterated, looking for
	commits. These commits are parsed, and their parents are marked as
	such to ensure that

		a) there is a full closure in the packfile, and no commit has a
		dangling parent pointer

		b) we can find the set of "tips" for the packfile, i.e., the set
		of commits that don't have any commits pointing to them

	3. The "tips" of the packfile are then used as the roots to perform a
	normal revision walk. The result of this revision walk is the list
	of commits that will be used by `bitmap_writer_select_commits` when
	selecting which commits are going to be bitmapped.

	4. We build and write the bitmap index in the same way that
	`pack-objects` does, given that we have all the required metadata:

		- an array of all the objects in the packfile, in index order
		- the types of all these objects
		- an array with a walk-ordering of all the commits in the
			packfile, which will be used for selection
		- a hash table to efficiently look up objects in the index

	See the previous patch "pack-objects: implement bitmap writing" for
	details on how the bitmap computation happens.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
rev-list: Optimize --count using bitmaps too

If bitmap indexes are available, the process of counting reachable
commits with `git rev-list --count` can be greatly sped up. Instead of
having to use callbacks that yield each object in the revision list, we
can build the reachable bitmap for the list and then use an efficient
popcount to find the number of bits set in the bitmap.

This commit implements a `count_bitmap_commit_list` that can be used
after `prepare_bitmap_walk` has returned successfully to return the
number of commits, trees, blobs or tags that have been found to be
reachable during the walk.

`git rev-list` is taught to use this function call when bitmaps are
enabled instead of going through the old rev-list machinery. Do note,
however, that counts with `left_right` and `cherry_mark` are not
optimized by this patch.

Here are some sample timings of different ways to count commits in
`torvalds/linux`:

	$ time ../git/git rev-list master | wc -l
	376549

	real    0m6.973s
	user    0m3.216s
	sys     0m5.316s

	$ time ../git/git rev-list --count master
	376549

	real    0m1.933s
	user    0m1.744s
	sys     0m0.188s

	$ time ../git/git rev-list --use-bitmaps --count master
	376549

	real    0m0.005s
	user    0m0.000s
	sys     0m0.004s

Note that the time in the `--use-bitmaps` invocation is basically noise.
In my machine it ranges from 2ms to 6ms.

Signed-off-by: Vicent Marti <tanoku@gmail.com>