When partitioning the work amongst threads, dividing the number of
objects by the number of threads may return 0 when there are less
objects than threads; this will cause the subsequent code to segfault
when accessing list[sub_size-1].  Allow some threads to have
zero objects to work on instead of barfing, while letting others
to have more.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

We somehow called deflateEnd() on a stream that we have called
deflateEnd() on already.

In fact, the second deflateEnd() has always been returning
Z_STREAM_ERROR.  We just never checked the error return from
that particular deflateEnd().

The first one returns 0 for success.  We might want to tighten
the check even more to check that.

Noticed by Marco.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

A NUL byte at beginning of file, or just after a newline
would provoke an invalid buf[-1] access in a few places.

* builtin-grep.c (cmd_grep): Don't access buf[-1].
* builtin-pack-objects.c (get_object_list): Likewise.
* builtin-rev-list.c (read_revisions_from_stdin): Likewise.
* bundle.c (read_bundle_header): Likewise.
* server-info.c (read_pack_info_file): Likewise.
* transport.c (insert_packed_refs): Likewise.
Signed-off-by: NJim Meyering <meyering@redhat.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

A mutex and a condition variable is allocated for each thread and torn
down when the thread terminates. However, for certain workloads it can
happen that some threads are actually not started at all. In this case
we would leak the mutex and condition variable. Now we allocate them only
for those threads that are actually started.
Signed-off-by: NJohannes Sixt <johannes.sixt@telecom.at>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

In the threaded pack-objects code the main thread and the worker threads
must mutually signal that they have assigned a new pack of work or have
completed their work, respectively. Previously, the code used mutexes that
were locked in one thread and unlocked from a different thread, which is
bogus (and happens to work on Linux).

Here we rectify the implementation by using condition variables: There is
one condition variable on which the main thread waits until a thread
requests new work; and each worker thread has its own condition variable
on which it waits until it is assigned new work or signaled to terminate.

As a cleanup, the worker threads are spawned only after the initial work
packages have been assigned.
Signed-off-by: NJohannes Sixt <johannes.sixt@telecom.at>
Acked-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The code that splits the object list amongst work threads tries to do so
on "path" boundaries not to prevent good delta matches.  However, in
some cases, a few paths may largely dominate the hash distribution and
it is not possible to have good load balancing without ignoring those
boundaries.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The current method consists of a master thread serving chunks of objects
to work threads when they're done with their previous chunk.  The issue
is to determine the best chunk size: making it too large creates poor
load balancing, while making it too small has a negative effect on pack
size because of the increased number of chunk boundaries and poor delta
window utilization.

This patch implements a completely different approach by initially
splitting the work in large chunks uniformly amongst all threads, and
whenever a thread is done then it steals half of the remaining work from
another thread with the largest amount of unprocessed objects.

This has the advantage of greatly reducing the number of chunk boundaries
with an almost perfect load balancing.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

It is currently sorted and then walked backward.  Not only this doesn't
feel natural for my poor brain, but it would make the next patch less
obvious as well.

So reverse the sort order, and reverse the list walking direction,
which effectively produce the exact same end result as before.

Also bring the relevant comment nearer the actual code and adjust it
accordingly, with minor additional clarifications.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The wrong value was substracted from delta_cache_size when replacing
a cached delta, as trg_entry->delta_size was used after the old size
had been replaced by the new size.

Noticed by Linus.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The function mark_tree_uninteresting() assumed that the tree entries
are blob when they are not trees.  This is not so.  Since we do
not traverse into submodules (yet), the gitlinks should be ignored.

In general, we should try to start moving away from using the
"S_ISLNK()" like things for internal git state. It was a mistake to
just assume the numbers all were same across all systems in the first
place.  This implementation converts to the "object_type", and then
uses a case statement.

Noticed by Ilari on IRC.
Test script taken from an earlier version by Dscho.
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The function mark_tree_uninteresting() assumed that the tree entries
are blob when they are not trees.  This is not so.  Since we do
not traverse into submodules (yet), the gitlinks should be ignored.

In general, we should try to start moving away from using the
"S_ISLNK()" like things for internal git state. It was a mistake to
just assume the numbers all were same across all systems in the first
place.  This implementation converts to the "object_type", and then
uses a case statement.

Noticed by Ilari on IRC.
Test script taken from an earlier version by Dscho.
Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

... when calling write_idx_file().
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

It is a good idea to use pack index version 2 all the time since it has
proper protection against propagation of certain pack corruptions when
repacking which is not possible with index version 1, as demonstrated
in test t5302.

Hence this config option.

The default is still pack index version 1.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This one triggers only when git-pack-objects is called with
--all-progress and --stdout which is the combination used by
git-push.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Since it is now OK to pass a null pointer to display_progress() and
stop_progress() resulting in a no-op, then we can simplify the code
and remove a bunch of lines by not making those calls conditional all
the time.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This allows for better management of progress "object" existence,
as well as making the progress display implementation more independent
from its callers.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Recently I was referred to the Grammar Police as the git-pack-objects
progress message 'Deltifying %u objects' is considered to be not
proper English to at least some small but vocal segment of the
English speaking population.  Techncially we are applying delta
compression to these objects at this stage, so the new term is
slightly more acceptable to the Grammar Police but is also just
as correct.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>

Two functions, namely write_idx_file() and open_pack_file(), currently
return a const pointer.  However that pointer is either a copy of the
first argument, or set to a malloc'd buffer when that first argument
is null.  In the later case it is wrong to qualify that pointer as const
since ownership of the buffer is transferred to the caller to dispose of,
and obviously the free() function is not meant to be passed const
pointers.

Making the return pointer not const causes a warning when the first
argument is returned since that argument is also marked const.

The correct thing to do is therefore to remove the const qualifiers,
avoiding the need for ugly casts only to silence some warnings.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>

To keep things well layered, sha1close() now returns the file descriptor
when it doesn't close the file.

An ugly cast was added to the return of write_idx_file() to avoid a
warning.  A proper fix will come separately.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>

... so don't even try in that case, and save another useless line of
progress display.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>

Each progress can be on a single line instead of two.

[sp: Changed "Checking files out" to "Checking out files" at
     Johannes Sixt's suggestion as it better explains the
	 action that is taking place]
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>

This new option is meant to be used in conjunction with the
options "git repack -a -d" usually invokes the underlying
pack-objects with.  When this option is given, objects unreachable
from the refs in packs named with --unpacked= option are added
to the resulting pack, in addition to the reachable objects that
are not in packs marked with *.keep files.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

These empty statement marcos can solicit bogus "statement with no effect"
warnings; squelch them.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Found by Jeff King.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This adds a --threads=<n> parameter to 'git pack-objects' with
documentation.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Try to keep object with the same name hash together.

Suggested by Martin Koegler.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

With this, each thread get repeatedly assigned the next available chunk of
objects to process until the whole list is done.  The idea is to have
reasonably small chunks so that all CPUs remain busy with a minimum
number of threads for as long as there is data to process.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

this is still rough, hence it is disabled by default.  You need to compile
with "make THREADED_DELTA_SEARCH=1 ..." at the moment.

Threading is done on different portions of the object list to be
deltified. This is currently done by spliting the list into n parts and
then a thread is spawned for each of them.  A better method would consist
of spliting the list into more smaller parts and have the n threads
pick the next part available.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This is to help threadification of the delta search code, with a bonus
consistency check.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This is to help threadification of delta searching.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Not all objects are subject to deltification, so avoid carrying those
along, and provide the real count to progress display.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This is based on Martin Koegler's idea to keep the object that
was successfully used as the base of the delta when it is about
to fall off the edge of the window.  Instead of doing so only
for the objects at the edge of the window, this makes the window
a lru eviction mechanism.  If an entry is used as a base, it is
moved to the last of the queue to be evicted.

This is a quick-and-dirty implementation, as it keeps the original
implementation of the data structure used for the window.  This
originally was done as an array, not as an array of pointers,
because it was meant to be used as a cyclic FIFO buffer and a
plain array avoids an extra pointer indirection, while its FIFOness
eant that we are not "moving" the entries like this patch does.

The runtime from three versions were comparable.  It seems to
make the resulting chain even shorter, which can only be good.

(stock "master") 15782196 bytes
chain length = 1: 2972 objects
chain length = 2: 2651 objects
chain length = 3: 2369 objects
chain length = 4: 2121 objects
chain length = 5: 1877 objects
...
chain length = 46: 490 objects
chain length = 47: 515 objects
chain length = 48: 527 objects
chain length = 49: 570 objects
chain length = 50: 408 objects

(with your patch) 15745736 bytes (0.23% smaller)
chain length = 1: 3137 objects
chain length = 2: 2688 objects
chain length = 3: 2322 objects
chain length = 4: 2146 objects
chain length = 5: 1824 objects
...
chain length = 46: 503 objects
chain length = 47: 509 objects
chain length = 48: 536 objects
chain length = 49: 588 objects
chain length = 50: 357 objects

(with this patch) 15612086 bytes (1.08% smaller)
chain length = 1: 4831 objects
chain length = 2: 3811 objects
chain length = 3: 2964 objects
chain length = 4: 2352 objects
chain length = 5: 1944 objects
...
chain length = 46: 327 objects
chain length = 47: 353 objects
chain length = 48: 304 objects
chain length = 49: 298 objects
chain length = 50: 135 objects

[jc: this is with code simplification follow-up from Nico]
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The code favoring shallower deltas when size is equal was triggered
only when previous delta was also cached.  There should be no relation
between cached deltas and same sized deltas.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NJunio C Hamano <gitster@pobox.com>

When a thin pack wants to send a tree object at "sub/dir", and
the commit that is common between the sender and the receiver
that is used as the base object has a subproject at that path,
we should not try to use the data at "sub/dir" of the base tree
as a tree object.  It is not a tree to begin with, and more
importantly, the commit object there does not have to even
exist.
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Not only are they unused, but the order in the function declaration
and the actual usage don't match.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

xmkstemp() performs error checking and prints a standard error message when
an error occur.
Signed-off-by: NLuiz Fernando N. Capitulino <lcapitulino@mandriva.com.br>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Commit 5a235b5e was missing this little detail.  Otherwise your pack
will explode.

Problem noted by Brian Downing.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>