summaryrefslogtreecommitdiff
path: root/cache.h
AgeCommit message (Collapse)AuthorFilesLines
2014-07-22Merge branch 'jk/alloc-commit-id'Libravatar Junio C Hamano1-0/+1
Make sure all in-core commit objects are assigned a unique number so that they can be annotated using the commit-slab API. * jk/alloc-commit-id: diff-tree: avoid lookup_unknown_object object_as_type: set commit index alloc: factor out commit index add object_as_type helper for casting objects parse_object_buffer: do not set object type move setting of object->type to alloc_* functions alloc: write out allocator definitions alloc.c: remove the alloc_raw_commit_node() function
2014-07-22Merge branch 'kb/perf-trace'Libravatar Junio C Hamano1-11/+2
* kb/perf-trace: api-trace.txt: add trace API documentation progress: simplify performance measurement by using getnanotime() wt-status: simplify performance measurement by using getnanotime() git: add performance tracing for git's main() function to debug scripts trace: add trace_performance facility to debug performance issues trace: add high resolution timer function to debug performance issues trace: add 'file:line' to all trace output trace: move code around, in preparation to file:line output trace: add current timestamp to all trace output trace: disable additional trace output for unit tests trace: add infrastructure to augment trace output with additional info sha1_file: change GIT_TRACE_PACK_ACCESS logging to use trace API Documentation/git.txt: improve documentation of 'GIT_TRACE*' variables trace: improve trace performance trace: remove redundant printf format attribute trace: consistently name the format parameter trace: move trace declarations from cache.h to new trace.h
2014-07-21Merge branch 'rs/ref-transaction-0'Libravatar Junio C Hamano1-1/+3
Early part of the "ref transaction" topic. * rs/ref-transaction-0: refs.c: change ref_transaction_update() to do error checking and return status refs.c: remove the onerr argument to ref_transaction_commit update-ref: use err argument to get error from ref_transaction_commit refs.c: make update_ref_write update a strbuf on failure refs.c: make ref_update_reject_duplicates take a strbuf argument for errors refs.c: log_ref_write should try to return meaningful errno refs.c: make resolve_ref_unsafe set errno to something meaningful on error refs.c: commit_packed_refs to return a meaningful errno on failure refs.c: make remove_empty_directories always set errno to something sane refs.c: verify_lock should set errno to something meaningful refs.c: make sure log_ref_setup returns a meaningful errno refs.c: add an err argument to repack_without_refs lockfile.c: make lock_file return a meaningful errno on failurei lockfile.c: add a new public function unable_to_lock_message refs.c: add a strbuf argument to ref_transaction_commit for error logging refs.c: allow passing NULL to ref_transaction_free refs.c: constify the sha arguments for ref_transaction_create|delete|update refs.c: ref_transaction_commit should not free the transaction refs.c: remove ref_transaction_rollback
2014-07-16Merge branch 'kb/path-max-must-go'Libravatar Junio C Hamano1-1/+1
* kb/path-max-must-go: cache.h: rename cache_def_free to cache_def_clear
2014-07-16Merge branch 'nd/split-index'Libravatar Junio C Hamano1-4/+23
An experiment to use two files (the base file and incremental changes relative to it) to represent the index to reduce I/O cost of rewriting a large index when only small part of the working tree changes. * nd/split-index: (32 commits) t1700: new tests for split-index mode t2104: make sure split index mode is off for the version test read-cache: force split index mode with GIT_TEST_SPLIT_INDEX read-tree: note about dropping split-index mode or index version read-tree: force split-index mode off on --index-output rev-parse: add --shared-index-path to get shared index path update-index --split-index: do not split if $GIT_DIR is read only update-index: new options to enable/disable split index mode split-index: strip pathname of on-disk replaced entries split-index: do not invalidate cache-tree at read time split-index: the reading part split-index: the writing part read-cache: mark updated entries for split index read-cache: save deleted entries in split index read-cache: mark new entries for split index read-cache: split-index mode read-cache: save index SHA-1 after reading entry.c: update cache_changed if refresh_cache is set in checkout_entry() cache-tree: mark istate->cache_changed on prime_cache_tree() cache-tree: mark istate->cache_changed on cache tree update ...
2014-07-14refs.c: make resolve_ref_unsafe set errno to something meaningful on errorLibravatar Ronnie Sahlberg1-1/+1
Making errno when returning from resolve_ref_unsafe() meaningful, which should fix * a bug in lock_ref_sha1_basic, where it assumes EISDIR means it failed due to a directory being in the way Signed-off-by: Ronnie Sahlberg <sahlberg@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> Acked-by: Michael Haggerty <mhagger@alum.mit.edu>
2014-07-14lockfile.c: add a new public function unable_to_lock_messageLibravatar Ronnie Sahlberg1-0/+2
Introducing a new unable_to_lock_message helper, which has nicer semantics than unable_to_lock_error and cleans up lockfile.c a little. Signed-off-by: Ronnie Sahlberg <sahlberg@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com> Acked-by: Michael Haggerty <mhagger@alum.mit.edu>
2014-07-13alloc: factor out commit indexLibravatar Jeff King1-0/+1
We keep a static counter to set the commit index on newly allocated objects. However, since we also need to set the index on any_objects which are converted to commits, let's make the counter available as a public function. While we're moving it, let's make sure the counter is allocated as an unsigned integer to match the index field in "struct commit". Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-07-13cache.h: rename cache_def_free to cache_def_clearLibravatar Karsten Blees1-1/+1
Rename cache_def_free to cache_def_clear as it doesn't free the struct cache_def, but just clears its content. Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-07-10Merge branch 'kb/path-max-must-go'Libravatar Junio C Hamano1-2/+6
* kb/path-max-must-go: symlinks: remove PATH_MAX limitation
2014-07-07symlinks: remove PATH_MAX limitationLibravatar Karsten Blees1-2/+6
'git checkout' fails if a directory is longer than PATH_MAX, because the lstat_cache in symlinks.c checks if the leading directory exists using PATH_MAX-bounded string operations. Remove the limitation by using strbuf instead. Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-25Merge branch 'ym/fix-opportunistic-index-update-race' into maintLibravatar Junio C Hamano1-0/+3
"git status", even though it is a read-only operation, tries to update the index with refreshed lstat(2) info to optimize future accesses to the working tree opportunistically, but this could race with a "read-write" operation that modify the index while it is running. Detect such a race and avoid overwriting the index. * ym/fix-opportunistic-index-update-race: read-cache.c: verify index file before we opportunistically update it wrapper.c: add xpread() similar to xread()
2014-06-20cleanup duplicate name_compare() functionsLibravatar Jeremiah Mahler1-1/+1
We often represent our strings as a counted string, i.e. a pair of the pointer to the beginning of the string and its length, and the string may not be NUL terminated to that length. To compare a pair of such counted strings, unpack-trees.c and read-cache.c implement their own name_compare() functions identically. In addition, the cache_name_compare() function in read-cache.c is nearly identical. The only difference is when one string is the prefix of the other string, in which case name_compare() returns -1/+1 to show which one is longer, and cache_name_compare() returns the difference of the lengths to show the same information. Unify these three functions by using the implementation from cache_name_compare(). This does not make any difference to the existing and future callers, as they must be paying attention only to the sign of the returned value (and not the magnitude) because the original implementations of these two functions return values returned by memcmp(3) when the one string is not a prefix of the other string, and the only thing memcmp(3) guarantees its callers is the sign of the returned value, not the magnitude. Signed-off-by: Jeremiah Mahler <jmmahler@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-17trace: move trace declarations from cache.h to new trace.hLibravatar Karsten Blees1-11/+2
Also include direct dependencies (strbuf.h and git-compat-util.h for __attribute__) so that trace.h can be used independently of cache.h, e.g. in test programs. Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-16Merge branch 'sk/windows-unc-path'Libravatar Junio C Hamano1-1/+0
* sk/windows-unc-path: Windows: allow using UNC path for git repository
2014-06-13t1700: new tests for split-index modeLibravatar Nguyễn Thái Ngọc Duy1-0/+2
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13update-index: new options to enable/disable split index modeLibravatar Nguyễn Thái Ngọc Duy1-0/+1
If you have a large work tree but only make changes in a subset, then $GIT_DIR/index's size should be stable after a while. If you change branches that touch something else, $GIT_DIR/index's size may grow large that it becomes as slow as the unified index. Do --split-index again occasionally to force all changes back to the shared index and keep $GIT_DIR/index small. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13split-index: strip pathname of on-disk replaced entriesLibravatar Nguyễn Thái Ngọc Duy1-0/+1
We know the positions of replaced entries via the replace bitmap in "link" extension, so the "name" path does not have to be stored (it's still in the shared index). With this, we also have a way to distinguish additions vs replacements at load time and can catch broken "link" extensions. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13split-index: do not invalidate cache-tree at read timeLibravatar Nguyễn Thái Ngọc Duy1-0/+1
We are sure that after merge_base_index() is done. cache-tree can still be used with the final index. So don't destroy cache tree. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: mark updated entries for split indexLibravatar Nguyễn Thái Ngọc Duy1-0/+2
The large part of this patch just follows CE_ENTRY_CHANGED marks. replace_index_entry() is updated to update split_index->base->cache[] as well so base->cache[] does not reference to a freed entry. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: split-index modeLibravatar Nguyễn Thái Ngọc Duy1-0/+3
This split-index mode is designed to keep write cost proportional to the number of changes the user has made, not the size of the work tree. (Read cost is another matter, to be dealt separately.) This mode stores index info in a pair of $GIT_DIR/index and $GIT_DIR/sharedindex.<SHA-1>. sharedindex is large and unchanged over time while "index" is smaller and updated often. Format details are in index-format.txt, although not everything is implemented in this patch. Shared indexes are not automatically removed, because it's unclear if the shared index is needed by any (even temporary) indexes by just looking at it. After a while you'll collect stale shared indexes. The good news is one shared index is useable for long, until $GIT_DIR/index becomes too big and sluggish that the new shared index must be created. The safest way to clean shared indexes is to turn off split index mode, so shared files are all garbage, delete them all, then turn on split index mode again. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: save index SHA-1 after readingLibravatar Nguyễn Thái Ngọc Duy1-0/+1
Also update SHA-1 after writing. If we do not do that, the second read_index() will see "initialized" variable already set and not read .git/index again, which is fine, except istate->sha1 now has a stale value. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13entry.c: update cache_changed if refresh_cache is set in checkout_entry()Libravatar Nguyễn Thái Ngọc Duy1-0/+1
Other fill_stat_cache_info() is on new entries, which should set CE_ENTRY_ADDED in cache_changed, so we're safe. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13cache-tree: mark istate->cache_changed on cache tree invalidationLibravatar Nguyễn Thái Ngọc Duy1-0/+1
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13resolve-undo: be specific what part of the index has changedLibravatar Nguyễn Thái Ngọc Duy1-0/+1
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: be specific what part of the index has changedLibravatar Nguyễn Thái Ngọc Duy1-0/+5
cache entry additions, removals and modifications are separated out. The rest of changes are still in the catch-all flag SOMETHING_CHANGED, which would be more specific later. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: store in-memory flags in the first 12 bits of ce_flagsLibravatar Nguyễn Thái Ngọc Duy1-1/+1
We're running out of room for in-memory flags. But since b60e188 (Strip namelen out of ce_flags into a ce_namelen field - 2012-07-11), we copy the namelen (first 12 bits) to ce_namelen field. So those bits are free to use. Just make sure we do not accidentally write any in-memory flags back. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: relocate and unexport commit_locked_index()Libravatar Nguyễn Thái Ngọc Duy1-1/+0
This function is now only used by write_locked_index(). Move it to read-cache.c (because read-cache.c will need to be aware of alternate_index_output later) and unexport it. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-13read-cache: new API write_locked_index instead of write_index/write_cacheLibravatar Nguyễn Thái Ngọc Duy1-2/+4
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-10Windows: allow using UNC path for git repositoryLibravatar Cezary Zawadka1-1/+0
[efl: moved MinGW-specific part to compat/] [jes: fixed compilation on non-Windows] Eric Sunshine fixed mingw_offset_1st_component() to return consistently "foo" for UNC "//machine/share/foo", cf http://groups.google.com/group/msysgit/browse_thread/thread/c0af578549b5dda0 Author: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Cezary Zawadka <czawadka@gmail.com> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com> Signed-off-by: Erik Faye-Lund <kusmabite@gmail.com> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Stepan Kasal <kasal@ucw.cz> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-06Merge branch 'nd/status-auto-comment-char'Libravatar Junio C Hamano1-0/+1
* nd/status-auto-comment-char: commit: allow core.commentChar=auto for character auto selection config: be strict on core.commentChar
2014-06-06Merge branch 'jk/squelch-compiler-warning-from-funny-error-macro'Libravatar Junio C Hamano1-2/+2
* jk/squelch-compiler-warning-from-funny-error-macro: let clang use the constant-return error() macro inline constant return from error() function
2014-06-03Merge branch 'jk/commit-date-approxidate'Libravatar Junio C Hamano1-0/+7
* jk/commit-date-approxidate: commit: accept more date formats for "--date" commit: print "Date" line when the user has set date pretty: make show_ident_date public commit: use split_ident_line to compare author/committer
2014-06-03Merge branch 'ym/fix-opportunistic-index-update-race'Libravatar Junio C Hamano1-0/+3
Read-only operations such as "git status" that internally refreshes the index write out the refreshed index to the disk to optimize future accesses to the working tree, but this could race with a "read-write" operation that modify the index while it is running. Detect such a race and avoid overwriting the index. Duy raised a good point that we may need to do the same for the normal writeout codepath, not just the "opportunistic" update codepath. While that is true, nobody sane would be running two simultaneous operations that are clearly write-oriented competing with each other against the same index file. So in that sense that can be done as a less urgent follow-up for this topic. * ym/fix-opportunistic-index-update-race: read-cache.c: verify index file before we opportunistically update it wrapper.c: add xpread() similar to xread()
2014-06-03Merge branch 'ks/tree-diff-nway'Libravatar Junio C Hamano1-0/+15
Instead of running N pair-wise diff-trees when inspecting a N-parent merge, find the set of paths that were touched by walking N+1 trees in parallel. These set of paths can then be turned into N pair-wise diff-tree results to be processed through rename detections and such. And N=2 case nicely degenerates to the usual 2-way diff-tree, which is very nice. * ks/tree-diff-nway: mingw: activate alloca combine-diff: speed it up, by using multiparent diff tree-walker directly tree-diff: rework diff_tree() to generate diffs for multiparent cases as well Portable alloca for Git tree-diff: reuse base str(buf) memory on sub-tree recursion tree-diff: no need to call "full" diff_tree_sha1 from show_path() tree-diff: rework diff_tree interface to be sha1 based tree-diff: diff_tree() should now be static tree-diff: remove special-case diff-emitting code for empty-tree cases tree-diff: simplify tree_entry_pathcmp tree-diff: show_path prototype is not needed anymore tree-diff: rename compare_tree_entry -> tree_entry_pathcmp tree-diff: move all action-taking code out of compare_tree_entry() tree-diff: don't assume compare_tree_entry() returns -1,0,1 tree-diff: consolidate code for emitting diffs and recursion in one place tree-diff: show_tree() is not needed tree-diff: no need to pass match to skip_uninteresting() tree-diff: no need to manually verify that there is no mode change for a path combine-diff: move changed-paths scanning logic into its own function combine-diff: move show_log_first logic/action out of paths scanning
2014-05-19commit: allow core.commentChar=auto for character auto selectionLibravatar Nguyễn Thái Ngọc Duy1-0/+1
When core.commentChar is "auto", the comment char starts with '#' as in default but if it's already in the prepared message, find another char in a small subset. This should stop surprises because git strips some lines unexpectedly. Note that git is not smart enough to recognize '#' as the comment char in custom templates and convert it if the final comment char is different. It thinks '#' lines in custom templates as part of the commit message. So don't use this with custom templates. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-05-06let clang use the constant-return error() macroLibravatar Jeff King1-1/+1
Commit e208f9c converted error() into a macro to make its constant return value more apparent to calling code. Commit 5ded807 prevents us using this macro with clang, since clang's -Wunused-value is smart enough to realize that the constant "-1" is useless in some contexts. However, since the last commit puts the constant behind an inline function call, this is enough to prevent the -Wunused-value warning on both modern gcc and clang. So we can now re-enable the macro when compiling with clang. Tested with clang 3.3, 3.4, and 3.5. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-05-06inline constant return from error() functionLibravatar Jeff King1-1/+1
Commit e208f9c introduced a macro to turn error() calls into: (error(), -1) to make the constant return value more visible to the calling code (and thus let the compiler make better decisions about the code). This works well for code like: return error(...); but the "-1" is superfluous in code that just calls error() without caring about the return value. In older versions of gcc, that was fine, but gcc 4.9 complains with -Wunused-value. We can work around this by encapsulating the constant return value in a static inline function, as gcc specifically avoids complaining about unused function returns unless the function has been specifically marked with the warn_unused_result attribute. We also use the same trick for config_error_nonbool and opterror, which learned the same error technique in a469a10. Reported-by: Felipe Contreras <felipe.contreras@gmail.com> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-05-02pretty: make show_ident_date publicLibravatar Jeff King1-0/+7
We use this function internally to format "Date" lines in commit logs, but other parts of the code will want it, too. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-04-10read-cache.c: verify index file before we opportunistically update itLibravatar Yiannis Marangos1-0/+3
Before we proceed to opportunistically update the index (often done by an otherwise read-only operation like "git status" and "git diff" that internally refreshes the index), we must verify that the current index file is the same as the one that we read earlier before we took the lock on it, in order to avoid a possible race. In the example below git-status does "opportunistic update" and git-rebase updates the index, but the race can happen in general. 1. process A calls git-rebase (or does anything that uses the index) 2. process A applies 1st commit 3. process B calls git-status (or does anything that updates the index) 4. process B reads index 5. process A applies 2nd commit 6. process B takes the lock, then overwrites process A's changes. 7. process A applies 3rd commit As an end result the 3rd commit will have a revert of the 2nd commit. When process B takes the lock, it needs to make sure that the index hasn't changed since step 4. Signed-off-by: Yiannis Marangos <yiannis.marangos@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-04-07tree-diff: rework diff_tree() to generate diffs for multiparent cases as wellLibravatar Kirill Smelkov1-0/+15
Previously diff_tree(), which is now named ll_diff_tree_sha1(), was generating diff_filepair(s) for two trees t1 and t2, and that was usually used for a commit as t1=HEAD~, and t2=HEAD - i.e. to see changes a commit introduces. In Git, however, we have fundamentally built flexibility in that a commit can have many parents - 1 for a plain commit, 2 for a simple merge, but also more than 2 for merging several heads at once. For merges there is a so called combine-diff, which shows diff, a merge introduces by itself, omitting changes done by any parent. That works through first finding paths, that are different to all parents, and then showing generalized diff, with separate columns for +/- for each parent. The code lives in combine-diff.c . There is an impedance mismatch, however, in that a commit could generally have any number of parents, and that while diffing trees, we divide cases for 2-tree diffs and more-than-2-tree diffs. I mean there is no special casing for multiple parents commits in e.g. revision-walker . That impedance mismatch *hurts* *performance* *badly* for generating combined diffs - in "combine-diff: optimize combine_diff_path sets intersection" I've already removed some slowness from it, but from the timings provided there, it could be seen, that combined diffs still cost more than an order of magnitude more cpu time, compared to diff for usual commits, and that would only be an optimistic estimate, if we take into account that for e.g. linux.git there is only one merge for several dozens of plain commits. That slowness comes from the fact that currently, while generating combined diff, a lot of time is spent computing diff(commit,commit^2) just to only then intersect that huge diff to almost small set of files from diff(commit,commit^1). That's because at present, to compute combine-diff, for first finding paths, that "every parent touches", we use the following combine-diff property/definition: D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn) (w.r.t. paths) where D(A,P1...Pn) is combined diff between commit A, and parents Pi and D(A,Pi) is usual two-tree diff Pi..A So if any of that D(A,Pi) is huge, tracting 1 n-parent combine-diff as n 1-parent diffs and intersecting results will be slow. And usually, for linux.git and other topic-based workflows, that D(A,P2) is huge, because, if merge-base of A and P2, is several dozens of merges (from A, via first parent) below, that D(A,P2) will be diffing sum of merges from several subsystems to 1 subsystem. The solution is to avoid computing n 1-parent diffs, and to find changed-to-all-parents paths via scanning A's and all Pi's trees simultaneously, at each step comparing their entries, and based on that comparison, populate paths result, and deduce we could *skip* *recursing* into subdirectories, if at least for 1 parent, sha1 of that dir tree is the same as in A. That would save us from doing significant amount of needless work. Such approach is very similar to what diff_tree() does, only there we deal with scanning only 2 trees simultaneously, and for n+1 tree, the logic is a bit more complex: D(T,P1...Pn) calculation scheme ------------------------------- D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set) D(T,Pj) - diff between T..Pj D(T,P1...Pn) - combined diff from T to parents P1,...,Pn We start from all trees, which are sorted, and compare their entries in lock-step: T P1 Pn - - - |t| |p1| |pn| |-| |--| ... |--| imin = argmin(p1...pn) | | | | | | |-| |--| |--| |.| |. | |. | . . . . . . at any time there could be 3 cases: 1) t < p[imin]; 2) t > p[imin]; 3) t = p[imin]. Schematic deduction of what every case means, and what to do, follows: 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓ 2) t > p[imin] 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀ pi=p[imin] pi↓ 2.2) ∀i pi = p[imin] -> pi ∉ T -> "-pi" ∈ D(T,Pi) -> D += "-p[imin]"; ∀i pi↓ 3) t = p[imin] 3.1) ∃j: pj > p[imin] -> "+t" ∈ D(T,Pj) -> only pi=p[imin] remains to investigate 3.2) pi = p[imin] -> investigate δ(t,pi) | | v 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø -> ⎧δ(t,pi) - if pi=p[imin] -> D += ⎨ ⎩"+t" - if pi>p[imin] in any case t↓ ∀ pi=p[imin] pi↓ ~ For comparison, here is how diff_tree() works: D(A,B) calculation scheme ------------------------- A B - - |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓ |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓ | | | | a = b -> investigate δ(a,b) a↓ b↓ |-| |-| |.| |.| . . . . ~~~~~~~~ This patch generalizes diff tree-walker to work with arbitrary number of parents as described above - i.e. now there is a resulting tree t, and some parents trees tp[i] i=[0..nparent). The generalization builds on the fact that usual diff D(A,B) is by definition the same as combined diff D(A,[B]), so if we could rework the code for common case and make it be not slower for nparent=1 case, usual diff(t1,t2) generation will not be slower, and multiparent diff tree-walker would greatly benefit generating combine-diff. What we do is as follows: 1) diff tree-walker ll_diff_tree_sha1() is internally reworked to be a paths generator (new name diff_tree_paths()), with each generated path being `struct combine_diff_path` with info for path, new sha1,mode and for every parent which sha1,mode it was in it. 2) From that info, we can still generate usual diff queue with struct diff_filepairs, via "exporting" generated combine_diff_path, if we know we run for nparent=1 case. (see emit_diff() which is now named emit_diff_first_parent_only()) 3) In order for diff_can_quit_early(), which checks DIFF_OPT_TST(opt, HAS_CHANGES)) to work, that exporting have to be happening not in bulk, but incrementally, one diff path at a time. For such consumers, there is a new callback in diff_options introduced: ->pathchange(opt, struct combine_diff_path *) which, if set to !NULL, is called for every generated path. (see new compat ll_diff_tree_sha1() wrapper around new paths generator for setup) 4) The paths generation itself, is reworked from previous ll_diff_tree_sha1() code according to "D(A,P1...Pn) calculation scheme" provided above: On the start we allocate [nparent] arrays in place what was earlier just for one parent tree. then we just generalize loops, and comparison according to the algorithm. Some notes(*): 1) alloca(), for small arrays, is used for "runs not slower for nparent=1 case than before" goal - if we change it to xmalloc()/free() the timings get ~1% worse. For alloca() we use just-introduced xalloca/xalloca_free compatibility wrappers, so it should not be a portability problem. 2) For every parent tree, we need to keep a tag, whether entry from that parent equals to entry from minimal parent. For performance reasons I'm keeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ. Not doing so, we'd need to alloca another [nparent] array, which hurts performance. 3) For emitted paths, memory could be reused, if we know the path was processed via callback and will not be needed later. We use efficient hand-made realloc-style path_appendnew(), that saves us from ~1-1.5% of potential additional slowdown. 4) goto(s) are used in several places, as the code executes a little bit faster with lowered register pressure. Also - we should now check for FIND_COPIES_HARDER not only when two entries names are the same, and their hashes are equal, but also for a case, when a path was removed from some of all parents having it. The reason is, if we don't, that path won't be emitted at all (see "a > xi" case), and we'll just skip it, and FIND_COPIES_HARDER wants all paths - with diff or without - to be emitted, to be later analyzed for being copies sources. The new check is only necessary for nparent >1, as for nparent=1 case xmin_eqtotal always =1 =nparent, and a path is always added to diff as removal. ~~~~~~~~ Timings for # without -c, i.e. testing only nparent=1 case `git log --raw --no-abbrev --no-renames` before and after the patch are as follows: navy.git linux.git v3.10..v3.11 before 0.611s 1.889s after 0.619s 1.907s slowdown 1.3% 0.9% This timings show we did no harm to usual diff(tree1,tree2) generation. From the table we can see that we actually did ~1% slowdown, but I think I've "earned" that 1% in the previous patch ("tree-diff: reuse base str(buf) memory on sub-tree recursion", HEAD~~) so for nparent=1 case, net timings stays approximately the same. The output also stayed the same. (*) If we revert 1)-4) to more usual techniques, for nparent=1 case, we'll get ~2-2.5% of additional slowdown, which I've tried to avoid, as "do no harm for nparent=1 case" rule. For linux.git, combined diff will run an order of magnitude faster and appropriate timings will be provided in the next commit, as we'll be taking advantage of the new diff tree-walker for combined-diff generation there. P.S. and combined diff is not some exotic/for-play-only stuff - for example for a program I write to represent Git archives as readonly filesystem, there is initial scan with `git log --reverse --raw --no-abbrev --no-renames -c` to extract log of what was created/changed when, as a result building a map {} sha1 -> in which commit (and date) a content was added that `-c` means also show combined diff for merges, and without them, if a merge is non-trivial (merges changes from two parents with both having separate changes to a file), or an evil one, the map will not be full, i.e. some valid sha1 would be absent from it. That case was my initial motivation for combined diffs speedup. Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-03-21Merge branch 'nd/tag-version-sort'Libravatar Junio C Hamano1-0/+2
Allow v1.9.0 sorted before v1.10.0 in "git tag --list" output. * nd/tag-version-sort: tag: support --sort=<spec>
2014-03-18Merge branch 'jk/commit-dates-parsing-fix' into maintLibravatar Junio C Hamano1-0/+1
Codepaths that parse timestamps in commit objects have been tightened. * jk/commit-dates-parsing-fix: show_ident_date: fix tz range check log: do not segfault on gmtime errors log: handle integer overflow in timestamps date: check date overflow against time_t fsck: report integer overflow in author timestamps t4212: test bogus timestamps with git-log
2014-03-18Merge branch 'bk/refresh-missing-ok-in-merge-recursive' into maintLibravatar Junio C Hamano1-1/+5
"merge-recursive" was broken in 1.7.7 era and stopped working in an empty (temporary) working tree, when there are renames involved. This has been corrected. * bk/refresh-missing-ok-in-merge-recursive: merge-recursive.c: tolerate missing files while refreshing index read-cache.c: extend make_cache_entry refresh flag with options read-cache.c: refactor --ignore-missing implementation t3030-merge-recursive: test known breakage with empty work tree
2014-03-14Merge branch 'mh/replace-refs-variable-rename'Libravatar Junio C Hamano1-2/+25
* mh/replace-refs-variable-rename: Document some functions defined in object.c Add docstrings for lookup_replace_object() and do_lookup_replace_object() rename read_replace_refs to check_replace_refs
2014-03-14Merge branch 'mh/object-code-cleanup'Libravatar Junio C Hamano1-4/+64
* mh/object-code-cleanup: sha1_file.c: document a bunch of functions defined in the file sha1_file_name(): declare to return a const string find_pack_entry(): document last_found_pack replace_object: use struct members instead of an array
2014-03-14Merge branch 'jk/commit-dates-parsing-fix'Libravatar Junio C Hamano1-0/+1
Tighten codepaths that parse timestamps in commit objects. * jk/commit-dates-parsing-fix: show_ident_date: fix tz range check log: do not segfault on gmtime errors log: handle integer overflow in timestamps date: check date overflow against time_t fsck: report integer overflow in author timestamps t4212: test bogus timestamps with git-log
2014-03-14Merge branch 'ks/config-file-stdin'Libravatar Junio C Hamano1-2/+7
"git config" learned to read from the standard input when "-" is given as the value to its "--file" parameter (attempting an operation to update the configuration in the standard input of course is rejected). * ks/config-file-stdin: config: teach "git config --file -" to read from the standard input config: change git_config_with_options() interface builtin/config.c: rename check_blob_write() -> check_write() config: disallow relative include paths from blobs
2014-03-07Merge branch 'jn/add-2.0-u-A-sans-pathspec'Libravatar Junio C Hamano1-1/+0
"git add -u" and "git add -A" without any pathspec is a tree-wide operation now, even when they are run in a subdirectory of the working tree.
2014-03-05Merge branch 'nd/daemonize-gc'Libravatar Junio C Hamano1-0/+1
Allow running "gc --auto" in the background. * nd/daemonize-gc: gc: config option for running --auto in background daemon: move daemonize() to libgit.a