1. Check whether we've already added the object to our
packing list.
2. Check whether the object meets our criteria for adding.
3. Actually add the object to our packing list.
It's a little hard to see these three phases, because they
happen linearly in the rather long function. Instead, this
patch breaks them up into three separate helper functions.
The result is a little easier to follow, though it
unfortunately suffers from some optimization
interdependencies between the stages (e.g., during step 3 we
use the packing list index from step 1 and the packfile
information from step 2).
More importantly, though, the various parts can be
composed differently, as they will be in the next patch.
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
A 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 packfile; if it's set to 1, the object is reachable.
By using the bitmaps available in the index, this commit implements
several new functions:
The `prepare_bitmap_walk` 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.
As an extra optimization, when `prepare_bitmap_walk` succeeds, the
`reuse_partial_packfile_from_bitmap` call can be attempted: it will find
the amount of objects at the beginning of the on-disk packfile that can
be reused as-is, and return an offset into the packfile. The source
packfile can then be loaded and the bytes up to `offset` can be written
directly to the result without having to consider the entires inside the
packfile individually.
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 set of functions are a generic API that allows to
perform the equivalent of
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
[jc: stripped debug-only code per Peff's $gmane/239768]
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Helped-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The POSIX standard doesn't currently define a `ntohll`/`htonll`
function pair to perform network-to-host and host-to-network
swaps of 64-bit data. These 64-bit swaps are necessary for the on-disk
storage of EWAH bitmaps if they are not in native byte order.
Many thanks to Ramsay Jones <ramsay@ramsay1.demon.co.uk> and
Torsten Bögershausen <tboegi@web.de> for cygwin/mingw/msvc
portability fixes.
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
This commit enables users of `struct rev_info` to peform custom limiting
during a revision walk (i.e. `get_revision`).
If the field `include_check` has been set to a callback, this callback
will be issued once for each commit before it is added to the "pending"
list of the revwalk. If the include check returns 0, the commit will be
marked as added but won't be pushed to the pending list, effectively
limiting the walk.
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
As the pack-objects system grows beyond the single
pack-objects.c file, more parts (like the soon-to-exist
bitmap code) will need to compute hashes for matching
deltas. Factor out name_hash to make it available to other
files.
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
The hash table that stores the packing list for a given `pack-objects`
run was tightly coupled to the pack-objects code.
In this commit, we refactor the hash table and the underlying storage
array into a `packing_data` struct. The functionality for accessing and
adding entries to the packing list is hence accessible from other parts
of Git besides the `pack-objects` builtin.
This refactoring is a requirement for further patches in this series
that will require accessing the commit packing list from outside of
`pack-objects`.
The hash table implementation has been minimally altered: we now
use table sizes which are always a power of two, to ensure a uniform
index distribution in the array.
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Allow users to efficiently lookup consecutive entries that are expected
to be found on the same revindex by exporting `find_revindex_position`:
this function takes a pointer to revindex itself, instead of looking up
the proper revindex for a given packfile on each call.
Signed-off-by: Vicent Marti <tanoku@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jc/ls-files-killed-optim' into maint
"git ls-files -k" needs to crawl only the part of the working tree
that may overlap the paths in the index to find killed files, but
shared code with the logic to find all the untracked files, which
made it unnecessarily inefficient.
* jc/ls-files-killed-optim:
dir.c::test_one_path(): work around directory_exists_in_index_icase() breakage
t3010: update to demonstrate "ls-files -k" optimization pitfalls
ls-files -k: a directory only can be killed if the index has a non-directory
dir.c: use the cache_* macro to access the current index
Merge branch 'jh/checkout-auto-tracking' into maint
"git branch --track" had a minor regression in v1.8.3.2 and later
that made it impossible to base your local work on anything but a
local branch of the upstream repository you are tracking from.
* jh/checkout-auto-tracking:
t3200: fix failure on case-insensitive filesystems
branch.c: Relax unnecessary requirement on upstream's remote ref name
t3200: Add test demonstrating minor regression in 41c21f2
Refer to branch.<name>.remote/merge when documenting --track
t3200: Minor fix when preparing for tracking failure
t2024: Fix &&-chaining and a couple of typos
When there is no sufficient overlap between old and new history
during a "git fetch" into a shallow repository, objects that the
sending side knows the receiving end has were unnecessarily sent.
* nd/fetch-into-shallow:
Add testcase for needless objects during a shallow fetch
list-objects: mark more commits as edges in mark_edges_uninteresting
list-objects: reduce one argument in mark_edges_uninteresting
upload-pack: delegate rev walking in shallow fetch to pack-objects
shallow: add setup_temporary_shallow()
shallow: only add shallow graft points to new shallow file
move setup_alternate_shallow and write_shallow_commits to shallow.c
Cleanups and tweaks for credential handling to work with ancient versions
of the gnome-keyring library that are still in use.
* bc/gnome-keyring:
contrib/git-credential-gnome-keyring.c: support really ancient gnome-keyring
contrib/git-credential-gnome-keyring.c: support ancient gnome-keyring
contrib/git-credential-gnome-keyring.c: report failure to store password
contrib/git-credential-gnome-keyring.c: use glib messaging functions
contrib/git-credential-gnome-keyring.c: use glib memory allocation functions
contrib/git-credential-gnome-keyring.c: use secure memory for reading passwords
contrib/git-credential-gnome-keyring.c: use secure memory functions for passwds
contrib/git-credential-gnome-keyring.c: use gnome helpers in keyring_object()
contrib/git-credential-gnome-keyring.c: set Gnome application name
contrib/git-credential-gnome-keyring.c: ensure buffer is non-empty before accessing
contrib/git-credential-gnome-keyring.c: strlen() returns size_t, not ssize_t
contrib/git-credential-gnome-keyring.c: exit non-zero when called incorrectly
contrib/git-credential-gnome-keyring.c: add static where applicable
contrib/git-credential-gnome-keyring.c: *style* use "if ()" not "if()" etc.
contrib/git-credential-gnome-keyring.c: remove unused die() function
contrib/git-credential-gnome-keyring.c: remove unnecessary pre-declarations
Make "git grep" and "git show" pay attention to --textconv when
dealing with blob objects.
* mg/more-textconv:
grep: honor --textconv for the case rev:path
grep: allow to use textconv filters
t7008: demonstrate behavior of grep with textconv
cat-file: do not die on --textconv without textconv filters
show: honor --textconv for blobs
diff_opt: track whether flags have been set explicitly
t4030: demonstrate behavior of show with textconv
Document rules to use GIT_REFLOG_ACTION variable in the scripted
Porcelain. git-rebase--interactive locally violates them, but it
is a leaf user that does not call out to or dot-source other
scripts, so it does not urgently need to be fixed.
* jc/reflog-doc:
setup_reflog_action: document the rules for using GIT_REFLOG_ACTION
* sb/repack-in-c:
repack: improve warnings about failure of renaming and removing files
repack: retain the return value of pack-objects
repack: rewrite the shell script in C
Some progress and diagnostic messages from "git clone" were
incorrectly sent to the standard output stream, not to the standard
error stream.
* jk/clone-progress-to-stderr:
clone: always set transport options
clone: treat "checking connectivity" like other progress
clone: send diagnostic messages to stderr
Clean up the internal of the name-hash mechanism used to work
around case insensitivity on some filesystems to cleanly fix a
long-standing API glitch where the caller of cache_name_exists()
that ask about a directory with a counted string was required to
have '/' at one location past the end of the string.
* es/name-hash-no-trailing-slash-in-dirs:
dir: revert work-around for retired dangerous behavior
name-hash: stop storing trailing '/' on paths in index_state.dir_hash
employ new explicit "exists in index?" API
name-hash: refactor polymorphic index_name_exists()
* es/rebase-i-no-abbrev:
rebase -i: fix short SHA-1 collision
t3404: rebase -i: demonstrate short SHA-1 collision
t3404: make tests more self-contained
* git://git.bogomips.org/git-svn:
git-svn: Warn about changing default for --prefix in Git v2.0
Documentation/git-svn: Promote the use of --prefix in docs + examples
git-svn.txt: elaborate on rev_map files
git-svn.txt: replace .git with $GIT_DIR
git-svn.txt: reword description of gc command
git-svn.txt: fix AsciiDoc formatting error
git-svn: fix signed commit parsing
contrib/git-credential-gnome-keyring.c: support really ancient gnome-keyring
The gnome-keyring lib (0.4) distributed with RHEL 4.X is really ancient
and does not provide most of the synchronous functions that even ancient
releases do. Thankfully, we're only using one function that is missing.
Let's emulate gnome_keyring_item_delete_sync() by calling the asynchronous
function and then triggering the event loop processing until our
callback is called.
Signed-off-by: Brandon Casey <drafnel@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib/git-credential-gnome-keyring.c: support ancient gnome-keyring
The gnome-keyring lib distributed with RHEL 5.X is ancient and does
not provide a few of the functions/defines that more recent versions
do, but mostly the API is the same. Let's provide the missing bits
via macro definitions and function implementation.
Signed-off-by: Brandon Casey <drafnel@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib/git-credential-gnome-keyring.c: use secure memory for reading passwords
gnome-keyring provides functions to allocate non-pageable memory (if
possible). Let's use them to allocate memory that may be used to hold
secure data read from the keyring.
Signed-off-by: Brandon Casey <drafnel@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib/git-credential-gnome-keyring.c: use gnome helpers in keyring_object()
Rather than carefully allocating memory for sprintf() to write into,
let's make use of the glib helper function g_strdup_printf(), which
makes things a lot easier and less error-prone.
Signed-off-by: Brandon Casey <drafnel@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib/git-credential-gnome-keyring.c: set Gnome application name
Since this is a Gnome application, let's set the application name to
something reasonable. This will be displayed in Gnome dialog boxes
e.g. the one that prompts for the user's keyring password.
We add an include statement for glib.h and add the glib-2.0 cflags and
libs to the compilation arguments, but both of these are really noops
since glib is already a dependency of gnome-keyring.
Signed-off-by: Brandon Casey <drafnel@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
sparse: suppress some "using sizeof on a function" warnings
Sparse issues an "using sizeof on a function" warning for each
call to curl_easy_setopt() which sets an option that takes a
function pointer parameter. (currently 12 such warnings over 4
files.)
The warnings relate to the use of the "typecheck-gcc.h" header
file which adds a layer of type-checking macros to the curl
function invocations (for gcc >= 4.3 and !__cplusplus). As part
of the type-checking layer, 'sizeof' is applied to the function
parameter of curl_easy_setopt(). Note that, in the context of
sizeof, the function to function pointer conversion is not
performed and that sizeof(f) != sizeof(&f).
A simple solution, therefore, would be to replace the function
name in each such call to curl_easy_setopt() with an explicit
function pointer expression (i.e. replace f with &f).
However, the "typecheck-gcc.h" header file is only conditionally
included, in addition to the gcc and C++ checks mentioned above,
depending on the CURL_DISABLE_TYPECHECK preprocessor variable.
In order to suppress the warnings, we use target-specific variable
assignments to add -DCURL_DISABLE_TYPECHECK to SPARSE_FLAGS for
each file affected (http-push.c, http.c, http-walker.c and
remote-curl.c).
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
The Thunderbird section of the 'MUA-specific hints' contains three
different approaches to setting up the mail client to leave patch
emails unmolested. The second approach (configuration) has a step
missing when configuring the composition window not to wrap. In
particular, the "mailnews.wraplength" configuration variable needs
to be set to zero. Update the documentation to add the missing
setting.
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
gitweb test: fix highlight test hang on Linux Mint
Linux Mint has an implementation of the highlight command (unrelated
to the one from http://www.andre-simon.de) that works as a simple
filter. The script uses 'sed' to add terminal colour escape codes
around text matching a regular expression. When t9500-*.sh attempts
to run "highlight --version", the script simply hangs waiting for
input. (See https://bugs.launchpad.net/linuxmint/+bug/815005).
The tool required by gitweb can be installed from the 'highlight'
package. Unfortunately, given the default $PATH, this leads to the
tool having lower precedence than the script.
In order to avoid hanging the test, add '</dev/null' to the command
line of the highlight invocation. Also, since the 'highlight' tool
requred by gitweb produces '--version' output (and the script does
not), saving the command output allows a simple check for the wrong
'highlight'.
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
When the NO_MKSTEMPS build variable is not set, the gitmkstemps
function is dead code. Use a preprocessor conditional to only include
the definition when needed.
Noticed by sparse. ("'gitmkstemps' was not declared. Should it be
static?")
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
Commit 7192777 refactors git_parse_ulong, which is public, into a more
generic function. But since we kept the git_parse_ulong wrapper, only
that part needs to be public; nobody outside the file calls the
lower-level git_parse_unsigned.
Noticed with sparse. ("'git_parse_unsigned' was not declared. Should
it be static?")
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Explained-by: Jeff King <peff@peff.net> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
config doc: user.signingkey is also used for signed commits
The description of the user.signingkey option only mentioned its use
when creating a signed tag. Make it clear that is is also used when
creating signed commits.
Signed-off-by: Nicolas Vigier <boklm@mars-attacks.org> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
clone --branch: refuse to clone if upstream repo is empty
Since 920b691 (clone: refuse to clone if --branch
points to bogus ref) we refuse to clone with option
"-b" if the specified branch does not exist in the
(non-empty) upstream. If the upstream repository is empty,
the branch doesn't exist, either. So refuse the clone too.
Reported-by: Robert Mitwicki <robert.mitwicki@opensoftware.pl> Signed-off-by: Ralf Thielow <ralf.thielow@gmail.com> Acked-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
git-prompt.sh: optionally show upstream branch name
When working with multiple remotes, it is common to switch the upstream
from a remote to another. Doing so, the prompt may not be the expected
one. Providing an option to display tracking information sounds useful.
Add a "name" option to GIT_PS1_SHOWUPSTREAM which will show the upstream
abbrev name. This option is ignored if "verbose" is false.
Signed-off-by: Julien Carsique <julien.carsique@gmail.com> Improved-by: SZEDER Gábor <szeder@ira.uka.de> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
path-utils test: rename mingw_path function to print_path
mingw_path was introduced in abd4284 to output a mangled path as it is
passed as an argument to main(). But the name is misleading because
mangling does not come from MinGW, but from MSYS [1]. As abd4284 does not
introduce any MSYS or MinGW specific code but just prints out argv[2] as
it is passed to main(), give the function the more generic and less
confusing name "print_path".
Several uses of the '^' operator are being interpreted by asciidoc
as requests to show the following text as a superscript. In order
to fix this problem, use backticks (`) to quote the text of the
affected git command invocations.
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
The text contains two 'grep' invocations which include the 'start
of line' regular expression character '^'. Asciidoc mis-interprets
this use of '^' as a superscript request. In order to fix this
formatting problem, use backticks (`) to quote the text of the
affected 'grep' command invocations.
Signed-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
git-svn: Warn about changing default for --prefix in Git v2.0
In Git v2.0, we will change the default --prefix for init/clone from
none/empty to "origin/" (which causes SVN-tracking branches to be
placed at refs/remotes/origin/* instead of refs/remotes/*).
This patch warns users about the upcoming change, both in the git-svn
manual page, and on stderr when running init/clone in the "multi-mode"
without providing a --prefix.
Cc: Eric Wong <normalperson@yhbt.net> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Eric Wong <normalperson@yhbt.net>
Documentation/git-svn: Promote the use of --prefix in docs + examples
Currently, the git-svn defaults to using an empty prefix, which ends
up placing the SVN-tracking refs directly in refs/remotes/*. This
placement runs counter to Git's convention of placing remote-tracking
branches in refs/remotes/$remote/*.
Furthermore, combining git-svn with "regular" Git remotes run the risk
of clobbering refs under refs/remotes (e.g. if you have a git remote
called "tags" with a "v1" branch, it will overlap with the git-svn's
tracking branch for the "v1" tag from Subversion.
Even though the git-svn refs stored in refs/remotes/* are not "proper"
remote-tracking branches (since they are not covered by a proper git
remote's refspec), they clearly represent a similar concept, and would
benefit from following the same convention.
For example, if git-svn tracks Subversion branch "foo" at
refs/remotes/foo, and you create a local branch refs/heads/foo to add
some commits to be pushed back to Subversion (using "git svn dcommit),
then it is clearly unhelpful of Git to throw
warning: refname 'foo' is ambiguous.
every time you checkout, rebase, or otherwise interact with the branch.
At this time, the user is better off using the --prefix=foo/ (the
trailing slash is important) to git svn init/clone, to cause the
SVN-tracking refs to be placed at refs/remotes/foo/* instead of
refs/remotes/*. This patch updates the documentation to encourage
use of --prefix.
This is also in preparation for changing the default value of --prefix
at some point in the future.
Cc: Eric Wong <normalperson@yhbt.net> Signed-off-by: Johan Herland <johan@herland.net> Signed-off-by: Eric Wong <normalperson@yhbt.net>
Currently, we only try converting argv[1] from "-" into "@{-1}". This
means we do not notice "-" when used together with an option. Worse,
when "git cherry-pick" is run with no options, we segfault. Fix this
by doing the substitution after we have checked that there is
something in argv to cherry-pick and know any remaining options are
meant for the revision-listing machinery.
This still does not handle "-" after the first non-cherry-pick option.
For example,
git cherry-pick foo~2 - bar~5
and
git cherry-pick --no-merges -
will still dump usage.
Reported-by: Stefan Beller <stefanbeller@googlemail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>