If a repository ever gets in a situation where there are too many
packs (more than 60 or so), perhaps because of frequent use of
git-fetch -k or incremental git-repack, then it becomes impossible to
fully repack the repository with git-repack -a.  That command just
dies with the cryptic message

    fatal: too many internal rev-list options

This message comes from git-pack-objects, which is passed one command
line option like --unpacked=pack-<SHA1>.pack for each pack file to be
repacked.  However, the current code has a static limit of 64 command
line arguments and just aborts if more arguments are passed to it.

Fix this by dynamically allocating the array of command line
arguments, and doubling the size each time it overflows.
Signed-off-by: NRoland Dreier <roland@digitalvampire.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Previous step converted use of strncmp() with literal string
mechanically even when the result is only used as a boolean:

    if (!strncmp("foo", arg, 3)) ==> if (!(-prefixcmp(arg, "foo")))

This step manually cleans them up to read:

    if (!prefixcmp(arg, "foo"))
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This mechanically converts strncmp() to use prefixcmp(), but only when
the parameters match specific patterns, so that they can be verified
easily.  Leftover from this will be fixed in a separate step, including
idiotic conversions like

    if (!strncmp("foo", arg, 3))

  =>

    if (!(-prefixcmp(arg, "foo")))

This was done by using this script in px.perl

   #!/usr/bin/perl -i.bak -p
   if (/strncmp\(([^,]+), "([^\\"]*)", (\d+)\)/ && (length($2) == $3)) {
           s|strncmp\(([^,]+), "([^\\"]*)", (\d+)\)|prefixcmp($1, "$2")|;
   }
   if (/strncmp\("([^\\"]*)", ([^,]+), (\d+)\)/ && (length($1) == $3)) {
           s|strncmp\("([^\\"]*)", ([^,]+), (\d+)\)|(-prefixcmp($2, "$1"))|;
   }

and running:

   $ git grep -l strncmp -- '*.c' | xargs perl px.perl
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This attempts to finish what Simon started in the previous commit.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The code calls use_pack() to make that the variably encoded
offset fits in the mmap'ed window, but it forgot that the
operation gives the pointer to the beginning of the asked
region.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Junio noticed that 'non-trivial' pushes were failing if executed
using the sliding window mmap changes.  This was somewhat difficult
to track down as the failure was appearing randomly.

It turns out this was a failure caused by the delta base reference
(either ref or offset format) spanning over the end of a mmap window.

The error in pack-objects was we were not recalling use_pack
after the object header was unpacked, and therefore we did not
get the promise of at least 20 bytes in the buffer for the delta
base parsing.  This would case later memcmp() calls to walk into
unassigned address space at the end of the window.

The reason Junio and I had hard time tracking this down in current
Git repositories is we were both probably packing with offset deltas,
which minimized the odds of the delta base reference spanning over
the end of the mmap window.  Stepping back and repacking with
version 1.3.3 (which only supported reference deltas) increased
the likelyhood of seeing the bug.

The correct technique (as used in sha1_file.c) is to invoke
use_pack() after unpack_object_header_gently to ensure we have
enough data available for the delta base decoding.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When multiple mmaps start getting used for all pack file access it
is not possible to get all data associated with a specific object
in one contiguous memory region.  This limitation prevents simply
passing a single address and length to SHA1_Update or to inflate.

Instead we need to loop until we have processed all data of interest.

As we loop over the data we are always interested in reusing the same
window 'cursor', as the prior window will no longer be of any use
to us.  This allows the use_pack() call to automatically decrement
the use count of the prior window before setting up access for us
to the next window.

Within each loop we need to make use of the available length output
parameter of use_pack() to tell us how many bytes are available in
the current memory region, as we cannot tell otherwise.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Part of the implementation concept of the sliding mmap window for
pack access is to permit multiple windows per pack to be mapped
independently.  Since the inuse_cnt is associated with the mmap and
not with the file, this value is in struct pack_window and needs to
be incremented/decremented for each pack_window accessed by any code.

To faciliate that implementation we need to replace all uses of
use_packed_git() and unuse_packed_git() with a different API that
follows struct pack_window objects rather than struct packed_git.

The way this works is when we need to start accessing a pack for
the first time we should setup a new window 'cursor' by declaring
a local and setting it to NULL:

  struct pack_windows *w_curs = NULL;

To obtain the memory region which contains a specific section of
the pack file we invoke use_pack(), supplying the address of our
current window cursor:

  unsigned int len;
  unsigned char *addr = use_pack(p, &w_curs, offset, &len);

the returned address `addr` will be the first byte at `offset`
within the pack file.  The optional variable len will also be
updated with the number of bytes remaining following the address.

Multiple calls to use_pack() with the same window cursor will
update the window cursor, moving it from one window to another
when necessary.  In this way each window cursor variable maintains
only one struct pack_window inuse at a time.

Finally before exiting the scope which originally declared the window
cursor we must invoke unuse_pack() to unuse the current window (which
may be different from the one that was first obtained from use_pack):

  unuse_pack(&w_curs);

This implementation is still not complete with regards to multiple
windows, as only one window per pack file is supported right now.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The idea behind the sliding mmap window pack reader implementation
is to have multiple mmap regions active against the same pack file,
thereby allowing the process to mmap in only the active/hot sections
of the pack and reduce overall virtual address space usage.

To implement this we need to refactor the mmap related data
(pack_base, pack_use_cnt) out of struct packed_git and move them
into a new struct pack_window.

We are refactoring the code to support a single struct pack_window
per packfile, thereby emulating the prior behavior of mmap'ing the
entire pack file.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This adds a new option --reflog to pack-objects and revision
machinery; do not bother documenting it for now, since this is
only useful for local repacking.

When the option is passed, objects reachable from reflog entries
are marked as interesting while computing the set of objects to
pack.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This is a mechanical clean-up of the way *.c files include
system header files.

 (1) sources under compat/, platform sha-1 implementations, and
     xdelta code are exempt from the following rules;

 (2) the first #include must be "git-compat-util.h" or one of
     our own header file that includes it first (e.g. config.h,
     builtin.h, pkt-line.h);

 (3) system headers that are included in "git-compat-util.h"
     need not be included in individual C source files.

 (4) "git-compat-util.h" does not have to include subsystem
     specific header files (e.g. expat.h).
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The final 'nr_result' and 'written' values must always be the same
otherwise we're in deep trouble.  So let's remove a redundent report.

And for paranoia sake let's make sure those two variables are actually
equal after all objects are written (one never knows).
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The heuristics to give up deltification when both the source and the
target are both in the same pack affects negatively when we are
repacking the subset of objects in the existing pack.  This caused
any incremental updates to use suboptimal packs.  Tweak the heuristics
to avoid this problem.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This adds documentation for --progress and --all-progress, remove a
duplicate --progress handling and make usage string more readable.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Currently git-push displays progress status for the local packing of
objects to send, but nothing once it starts to push it over the
connection.  Having progress status in that later case is especially
nice when pushing lots of objects over a slow network link.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This is the missing part to git-pack-objects allowing it to reuse delta
data to/from any of the two delta types.  It can reuse delta from any
type, and it outputs base offsets when --allow-delta-base-offset is
provided and the base is also included in the pack.  Otherwise it
outputs base sha1 references just like it always did.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This is enabled with --delta-base-offset only, and doesn't work with
pack data reuse yet.

The idea is to allow for the fetch protocol to use an extension flag
to notify the remote end that --delta-base-offset can be used with
git-pack-objects. Eventually git-repack will always provide this flag.

With this, all delta base objects are now pushed before deltas that depend
on them.  This is a requirements for OBJ_OFS_DELTA.  This is not a
requirement for OBJ_REF_DELTA but always doing so makes the code simpler.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This adds a new object, namely OBJ_OFS_DELTA, renames OBJ_DELTA to
OBJ_REF_DELTA to better make the distinction between those two delta
objects, and adds support for the handling of those new delta objects
in sha1_file.c only.

The OBJ_OFS_DELTA contains a relative offset from the delta object's
position in a pack instead of the 20-byte SHA1 reference to identify
the base object.  Since the base is likely to be not so far away, the
relative offset is more likely to have a smaller encoding on average
than an absolute offset.  And for those delta objects the base must
always be stored first because there is no way to know the distance of
later objects when streaming a pack.  Hence this relative offset is
always meant to be negative.

The offset encoding is slightly denser than the one used for object
size -- credits to <linux@horizon.com> (whoever this is) for bringing
it to my attention.

This allows for pack size reduction between 3.2% (Linux-2.6) to over 5%
(linux-historic).  Runtime pack access should be faster too since delta
replay does skip a search in the pack index for each delta in a chain.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Those cleanups are mainly to set the table for the support of deltas
with base objects referenced by offsets instead of sha1.  This means
that many pack lookup functions are converted to take a pack/offset
tuple instead of a sha1.

This eliminates many struct pack_entry usages since this structure
carried redundent information in many cases, and it increased stack
footprint needlessly for a couple recursively called functions that used
to declare a local copy of it for every recursion loop.

In the process, packed_object_info_detail() has been reorganized as well
so to look much saner and more amenable to deltas with offset support.

Finally the appropriate adjustments have been made to functions that
depend on the above changes.  But there is no functionality changes yet
simply some code refactoring at this point.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NJunio C Hamano <junkio@cox.net>

This teaches the internal rev-list logic to understand options
that are needed for pack handling: --all, --unpacked, and --thin.

It also moves two functions from builtin-rev-list to list-objects
so that the two programs can share more code.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Instead of piping the rev-list output from its standard input,
you can say:

	pack-objects --all --unpacked --revs pack

and feed the rev parameters you would otherwise give the
rev-list on its command line from the standard input.
In other words:

	echo 'master..next' | pack-objects --revs pack

and

	rev-list --objects master..next | pack-objects pack

are equivalent.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When copying from an existing pack and when copying from a loose
object with new style header, the code makes sure that the piece
we are going to copy out inflates well and inflate() consumes
the data in full while doing so.

The check to see if the xdelta really apply is quite expensive
as you described, because you would need to have the image of
the base object which can be represented as a delta against
something else.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When revalidating an entry from an existing pack entry->size and
entry->type are not necessarily the size of the final object
when the entry is deltified, but for base objects they must
match.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When reusing data from an existing pack and from a new style
loose objects, we used to just copy it staight into the
resulting pack.  Instead make sure they are not corrupt, but
do so only when we are not streaming to stdout, in which case
the receiving end will do the validation either by unpacking
the stream or by constructing the .idx file.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This abstracts away the size of the hash values when copying them
from memory location to memory location, much as the introduction
of hashcmp abstracted away hash value comparsion.

A few call sites were using char* rather than unsigned char* so
I added the cast rather than open hashcpy to be void*.  This is a
reasonable tradeoff as most call sites already use unsigned char*
and the existing hashcmp is also declared to be unsigned char*.

[jc: Splitted the patch to "master" part, to be followed by a
 patch for merge-recursive.c which is not in "master" yet.

 Fixed the cast in the latter hunk to combine-diff.c which was
 wrong in the original.

 Also converted ones left-over in combine-diff.c, diff-lib.c and
 upload-pack.c ]
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Introduces global inline:

	hashcmp(const unsigned char *sha1, const unsigned char *sha2)

Uses memcmp for comparison and returns the result based on the length of
the hash name (a future runtime decision).
Acked-by: NAlex Riesen <raa.lkml@gmail.com>
Signed-off-by: NDavid Rientjes <rientjes@google.com>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

[jc: I needed to hand merge the changes to the updated codebase,
 so the result needs to be checked.]
Signed-off-by: NDavid Rientjes <rientjes@google.com>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NMatthias Kestenholz <matthias@spinlock.ch>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When packing an object without deltifying, if the data is stored in
a loose object that is encoded with a new style header, copy it without
inflating and deflating.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

For some repositories, deltas simply don't make sense. One can disable
them for git-repack by adding --window, but git-push insists on making
the deltas which can be very CPU-intensive for little benefit.
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The only visible change is that git-blame doesn't understand
"--compability" anymore, but it does accept "--compatibility" instead,
which is already documented.
Signed-off-by: NPavel Roskin <proski@gnu.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

If no delta is attempted on some objects then it is useless to load them
in memory, neither create any delta index for them.  The best thing to
do is therefore to load and index them only when really needed.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Without this there would never be a chance to improve packing for
previously undeltified objects.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

In the repacking window, if both objects we are looking at already came
from the same (old) pack-file, don't bother delta'ing them against each
other.

That means that we'll still always check for better deltas for (and
against!) _unpacked_ objects, but assuming incremental repacks, you'll
avoid the delta creation 99% of the time.
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This does not implement sideband for propagating the status to
the downloader yet, but add code to capture the standard error
output from the pack-objects process in preparation for sending
it off to the client when the protocol extension allows us to do
so.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

ANSI C99 doesn't allow void-pointer arithmetic. This patch fixes this in
various ways. Usually the strategy that required the least changes was used.
Signed-off-by: NFlorian Forster <octo@verplant.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>