* Re: [PATCH 00/48] Handling more corner cases in merge-recursive.c
From: Elijah Newren @ 2011-08-04 17:26 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, jgfouca
In-Reply-To: <7v4o1y81sv.fsf@alter.siamese.dyndns.org>
On Wed, Aug 3, 2011 at 6:20 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Unfortunately I seem to have found a regression that manifests in the real
> life.
>
> When this series is merged to 'next', it mismerges a trivial renamed path.
I know the problem, and can think of a couple potential solutions but
I'm not sure which one of those (if any) should be used. I may need
advice from an unpack_trees expert.
This breakage was introduced in d487486 (merge-recursive: When we
detect we can skip an update, actually skip it 2011-06-08), and the
reason for the breakage is that was_tracked(path) is lying to us. Let
me explain...
If you run with GIT_MERGE_VERBOSITY=3, you'll note that you get the message
"Skipped two (merged same as existing)"
which is NOT the path it should be taking. The reason for this is
that the call to was_tracked('two') just before that is returning true
for us when the correct answer is false. Explaining why we get the
wrong answer requires understanding a couple things.
Using your simple reproduction recipe as an example to explain this,
the sha1sums and paths for your merge case are:
Base commit: d00491f... one
HEAD commit: 0cfbf08... one
side commit: d00491f... two
In other words, 'one' is modified in HEAD, and unchanged other than
being renamed (to 'two') on side.
Now, was_tracked() simply checks whether there is a cache entry in the
current index with either stage 0 or stage 2. Clearly, I was
expecting 'two' to only appear with stage 3, but that's not what
happened.
When unpacking these trees, we got three cache entries: one for path
'one' at stage 1, one for path 'one' at stage 2, and one for path
'two' at stage 0. Yes, stage 0 and not stage 3. The reason for this
is that this is case 2ALT from
Documentation/technical/trivial-merge.txt:
case ancest head remote result
----------------------------------------
...
2ALT (empty)+ *empty* remote remote
This means the threeway_merge code considers it a clean merge and
calls merged_entry on it, which clears the CE_STAGEMASK bits from the
cache entry flags.
Since the cache entry for path 'two' has the CE_STAGEMASK bits
cleared, when we call was_tracked on that path, we get back the answer
true. 'two' was not tracked in HEAD, though, so this is the wrong
answer and the source of the bug.
Now, the question is...how do we fix the was_tracked function? It
would be nice to make use of the original index we had before
unpacking, but that is overwritten at the end of unpack_trees. Should
we save it somewhere? Or should we save off all the tracked filenames
before unpacking into a linked list and then have was_tracked() use
that instead of looking it up in the current cache? (I'm slightly
worried that may be slow given the number of lookups that exist).
Thoughts?
Elijah
^ permalink raw reply
* (unknown)
From: Hin-Tak Leung @ 2011-08-04 17:27 UTC (permalink / raw)
To: Jeff King; +Cc: git, rene.scharfe
--- On Thu, 4/8/11, Jeff King <peff@peff.net> wrote:
> On Wed, Aug 03, 2011 at 11:17:59PM
> +0100, Hin-Tak Leung wrote:
>
> > The summary of the problem is that, git-archive's
> "--format=tar"
> > option really write the pax format most of the time,
> and some
> > cross-platform archive extraction library (rather than
> the
> > all-powerful GNU tar) really does not think that's the
> tar format and
> > bail out.
>
> Out of curiosity, what is the library? Putting pax headers
> into ustar
> format has been standardized in POSIX since 2001.
The R people wrote their own in the R language (and the person who responded to my post in that R-devel thread was possibly the one who wrote that part, I believe) - The main reason is probably cross-platform-ness and independence from other programming languages - they are gradually moving away from invoking system() (because they need to run on windows and they used to require many cygwin/mingw tools to build add-on packages).
The R code which does that, scan for certain patterns after seek() into the gunzip'ed stream after 512(?) bytes. It is in a file
R/src/library/utils/R/tar.R under the source repository.
> That header contains useful information (the commit id from
> which the
> archive was generated). And there is a way to turn it off:
> give a tree
> id instead of a commit id. There is an example in the
> git-archive
> manpage that does exactly this already. Look for the
> example mentioning
> "pax header" here:
>
> http://www.kernel.org/pub/software/scm/git/docs/git-archive.html
>
> It might be a bit more obvious to find if we actually had
> a
> --no-pax-header option, though.
>
> -Peff
>
I think I tried the tree example and the R code also didn't like it much... may be I'll give it another try.
^ permalink raw reply
* Re: Branch dependencies
From: Nicolas Sebrecht @ 2011-08-04 17:38 UTC (permalink / raw)
To: martin f krafft
Cc: Bert Wesarg, git discussion list, Petr Baudis, Nicolas Sebrecht
In-Reply-To: <20110802190806.GA16674@fishbowl.rw.madduck.net>
The 02/08/11, martin f krafft wrote:
> also sprach Bert Wesarg <bert.wesarg@googlemail.com> [2011.08.02.1506 +0200]:
> > For my first mentioned problem, I think a new 'system' needs to be
> > 'rebase' based, not merge based like TopGit.
>
> The problem with rebasing is that you cannot publish the branches.
But you may make public the way to set up the builded branch. Say you
share A and B branches and you build M branch on top of them. You are
able to build M as long as others know M rely on A and B.
In a situation like
a--+ (A)
M--y--z (M)
b--+ (B)
or
a--+ (A)
b--+ (B)
M--y--z (M)
M is the builded branch. Commits y and z should not be public, IMHO.
--
Nicolas Sebrecht
^ permalink raw reply
* Re: git-archive's wrong documentation: really write pax rather than tar
From: René Scharfe @ 2011-08-04 17:39 UTC (permalink / raw)
To: Jeff King; +Cc: Junio C Hamano, Hin-Tak Leung, git
In-Reply-To: <20110804022903.GA3388@sigill.intra.peff.net>
Am 04.08.2011 04:29, schrieb Jeff King:
> On Wed, Aug 03, 2011 at 07:25:32PM -0700, Junio C Hamano wrote:
>
>>> Actually, it is relevant for zip, too. The option should really be
>>> called "--no-commit-id" or something similar. I don't think it's as big
>>> a deal with zip (because there is no compatibility issue), but you may
>>> want to omit the header for other reasons (e.g., because you know it
>>> doesn't point to a commit that is public).
>>
>> Hmm, perhaps. It indeed is an implementation detail of the tar backend
>> that the commit object name is stored in pax header, so --no-commit-id
>> might make sense from "git" point of view, but from the point of view of
>> OP that started this thread, he wouldn't care what that extra information
>> is --- it can be a commit object name or it can be phase of the moon when
>> the archive was made --- he just wants the extra header dropped.
>>
>> So I dunno.
>
> If the intent of the option is "write plain-vanilla ustar" (I really
> hope it doesn't need to be "plain-vanilla 4.3BSD tar"), then I think we
> would do better to have a new --format type. Because from the OP's
> perspective, it's not "drop this header that I don't like" but "make
> something compatible with older versions of tar".
Yes, the commit ID header is just one part of this. Extended pax
headers are also used to store file names or symlink targets that are
too long. If none of this applies, the output should be pure ustar, though.
POSIX says that programs should treat unknown entry types just like
plain files and print an error message. You'd get an extra file named
pax_global_header, containing only the commit ID, and for long file
names extra files that contain them (and your original files would get
short names based on their object ID).
Looking at the web page linked to in the original post, the problem
seems to be that R (probably http://www.r-project.org/) uses "tar" as a
package format, seems to accept the ustar format but refuses pax
extended headers and thus is incompatible with "POSIX tar" and also
doesn't follow the suggestion to treat unknown entries as plain files.
We could add a "ustar" format that doesn't write commit ID comments and
errors out on file names that are too long.
René
^ permalink raw reply
* Re: tracking submodules out of main directory.
From: Jens Lehmann @ 2011-08-04 17:45 UTC (permalink / raw)
To: henri GEIST
Cc: Junio C Hamano, Heiko Voigt, Alexei Sholik, git, Sverre Rabbelier
In-Reply-To: <1312410562.3261.1030.camel@Naugrim.eriador.com>
Am 04.08.2011 00:29, schrieb henri GEIST:
> Le mercredi 03 août 2011 à 23:30 +0200, Jens Lehmann a écrit :
>> Am 03.08.2011 21:41, schrieb Junio C Hamano:
>>> Jens Lehmann <Jens.Lehmann@web.de> writes:
>> But when you fetch a new version of Gimp into your submodule, it would be
>> really nice if the superproject could be notified that the Gimp developers
>> updated to 1.2.4 of Glib and inform you that an update of Glib might be
>> appropriate. That could avoid having you to dig through compiler errors to
>> find out that the new foobar() function from Glib 1.2.4 is needed (and if
>> you need to pull in a bugfix in Glib, you might notice that *a lot* later
>> when you forget to do that).
>>
>
> Exact, I am really happy to read this.
> And better do not bother to have the suproject.
I don't get this, you can't get rid of the superproject.
> cd to gimp directory, type git status it can tell you every thing and
> when your satisfied you just have to type make.
> At this point the superproject have not any use.
"git status" inside the submodule won't tell you anything about the
dependencies, but a "git status" in the superproject should. The submodule
shouldn't know where exactly the submodules it depends on lives, that is
the decision of the superproject, not the submodule.
>>>> In addition to that, it can (but mustn't) specify any of the following:
>>>
>>> I am guessing you meant "does not have to", instead of mustn't, here...
>>
>> Sure, thanks for deciphering that.
>>
>>>> a) Of this submodule "foo" I need at least that version because I won't
>>>> compile/work with older versions of that. (this can be tightened to
>>>> "exactly that version" to give henri the behavior he wants, but that
>>>> should be policy, not mandatory)
>>>
>>> The "loose collection of projects" approach like that has its uses, and it
>>> is called "repo". Why re-invent it? The behaviour Henri wants to specify
>>> the exact version is how git submodules work already, so I do not see
>>> there is anything to be done here.
>>
>> Let me make this clear: this is not about changing how submodules are
>> committed in a superproject. It is not about having a loose collection of
>> projects, they stay tied together in a defined state by the superproject.
>>
>
> Yes but for me, from when I started this this topic, it was all about
> having a loose collection of project with dependency references between
> them. And get rid of the superproject.
> It is my first and only goal.
But I fail to see how that would improve anything.
>> Henri wanted it a bit upside down: any submodule could request a certain
>> version of another submodule somewhere else in the repo. And he wanted to
>> use gitlinks from one submodule to another for that, which I - hopefully -
>> convinced him was no good idea.
>>
>
> You just convince me that submodules are more than I need and to make a
> lighter independent version of submodules which will never been followed
> by git commands.
Submodules are what you need, but it's no use to implement dependencies by
using gitlinks that point outside of their repositories.
>>>> b) And if you don't know where to get it, use this url
>>>
>>> Again that is the job of .gitmodules in the superproject.
>>
>> Yes. But this idea is about how the url could get into the .gitmodules of
>> the superproject in the first place. That can make it easier for the
>> superproject's developer to import a submodule into his repo and much more
>> important: it makes it possible to pull in submodule dependencies
>> automatically e.g. when running "git submodule add --resolve-dependencies
>> Gimp".
>
> Only if you have a superproject.
> If not do the same thing from the gimp repository, now it contain all
> necessary infos to do the job.
No, it doesn't. Apart from the Gimp project telling you what version it
wants, you need to have a place to record the version that the user really
used. And that won't work without a superproject.
>>>> That is all stuff the submodule knows better than the superproject.
>>>
>>> Not necessarily. The version A0 of submodule A may depend on submodule B
>>> and may also know it must have at least version B0 of that submodule, but
>>> the superproject would know other constraints, e.g. the superproject
>>> itself also calls into submodule B and wants a newer version B1 of it.
>>
>> Right. That's what I tried to explain to Henri, the superproject ties it all
>> together. But I also like his idea to add a way to communicate information
>> from the submodule to the superproject, and give the superproject a choice
>> if it wants to use it.
>>
>
> yes but the superproject contain no code in your design.
> Then it will never need anything by itself.
> It is only a container which you will inform with data already known by
> the submodules I do not see any value to it.
But being the container that ties it all together is more than enough value.
^ permalink raw reply
* Re: git-archive's wrong documentation: really write pax rather than tar
From: René Scharfe @ 2011-08-04 17:54 UTC (permalink / raw)
To: htl10; +Cc: Jeff King, git
In-Reply-To: <1312478843.69439.YahooMailClassic@web29510.mail.ird.yahoo.com>
Am 04.08.2011 19:27, schrieb Hin-Tak Leung:
> --- On Thu, 4/8/11, Jeff King <peff@peff.net> wrote:
>> Out of curiosity, what is the library? Putting pax headers into
>> ustar format has been standardized in POSIX since 2001.
>
> The R people wrote their own in the R language (and the person who
> responded to my post in that R-devel thread was possibly the one who
> wrote that part, I believe) - The main reason is probably
> cross-platform-ness and independence from other programming languages
> - they are gradually moving away from invoking system() (because they
> need to run on windows and they used to require many cygwin/mingw
> tools to build add-on packages).
>
> The R code which does that, scan for certain patterns after seek()
> into the gunzip'ed stream after 512(?) bytes. It is in a file
> R/src/library/utils/R/tar.R under the source repository.
Ah, here it is:
https://svn.r-project.org/R/trunk/src/library/utils/R/tar.R
It's the ctype handling in function untar2 that rejects unknown entry types.
For reference, the documentation of the pax format including a
suggestion to treat unknown types like regular files can be found here
(search for "typename"):
http://pubs.opengroup.org/onlinepubs/9699919799/utilities/pax.html
> I think I tried the tree example and the R code also didn't like it
> much... may be I'll give it another try.
Did you try adding a ":" to the tree argument, e.g. this:
$ git archive HEAD:
instead of this?
$ git archive HEAD
René
^ permalink raw reply
* Re: git-fast-export is returning streams with source code inside
From: Jeff King @ 2011-08-04 18:32 UTC (permalink / raw)
To: James Gregory; +Cc: git
In-Reply-To: <CAFC9htxRD0z3O_k_OLp08KZFUOL_T3AryCXD+OqqXx9ZYeRutg@mail.gmail.com>
On Thu, Aug 04, 2011 at 10:08:43AM +0100, James Gregory wrote:
> Thanks for your reply. I'm afraid I won't be able to allow you access
> to repo as it is for a business project and covered by NDAs, etc. If I
> can do anything to help with diagnosing the problem (debug logs, more
> excerpts from the stream, etc.) then that shouldn't be a problem.
Since it seems like blob data is making it into the stream in an odd
place, my first guess would be a memory problem. Can you try installing
valgrind (since you are on Ubuntu, there should be a package), and then
running:
valgrind git fast-export --all >/dev/null 2>valgrind.out
and then sharing the results of valgrind.out?
-Peff
^ permalink raw reply
* Re: git-archive's wrong documentation: really write pax rather than tar
From: Hin-Tak Leung @ 2011-08-04 18:33 UTC (permalink / raw)
To: René Scharfe; +Cc: Jeff King, git
In-Reply-To: <4E3ADCCB.6080206@lsrfire.ath.cx>
--- On Thu, 4/8/11, René Scharfe <rene.scharfe@lsrfire.ath.cx> wrote:
> From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
<snipped>
> Ah, here it is:
>
> https://svn.r-project.org/R/trunk/src/library/utils/R/tar.R
>
> It's the ctype handling in function untar2 that rejects
> unknown entry types.
>
> For reference, the documentation of the pax format
> including a
> suggestion to treat unknown types like regular files can be
> found here
> (search for "typename"):
>
> http://pubs.opengroup.org/onlinepubs/9699919799/utilities/pax.html
>
> > I think I tried the tree example and the R code also
> didn't like it
> > much... may be I'll give it another try.
>
> Did you try adding a ":" to the tree argument, e.g. this:
>
> $ git archive HEAD:
>
> instead of this?
>
> $ git archive HEAD
>
> René
That's better! With a HEAD: , that code does a lot of:
Warning in untar2(tarfile, files, list, exdir) :
checksum error for entry 'file...'
for each file it tries to extract, but at least it is extracting the files. I wasn't entirely sure about the notation used in the man page - is
"v1.4.0^{tree}" same as "v1.4.0:" ? "HEAD:" is clearer, as most people has a HEAD...
^ permalink raw reply
* [PATCH] diff -c/--cc: do not mistake "resolved as deletion" as "use working tree"
From: Junio C Hamano @ 2011-08-04 18:58 UTC (permalink / raw)
To: git; +Cc: Johan Herland
In-Reply-To: <7vsjph6g4j.fsf@alter.siamese.dyndns.org>
The combined diff machinery can be used to compare:
- a merge commit with its parent commits;
- a working-tree file with multiple stages in an unmerged index; or
- a working-tree file with the HEAD and the index.
The internal function combine-diff.c:show_patch_diff() checked if it needs
to read the "result" from the working tree by looking at the object name
of the result --- if it is null_sha1, it read from the working tree.
This mistook a merge that records a deletion as the conflict resolution
as if it is a cue to read from the working tree. Pass this information
explicitly from the caller instead.
Noticed and reported by Johan Herland.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
* The patch is based on a bit older maintenance branch but will be queued
in 'pu'.
combine-diff.c | 14 ++++++++++----
1 files changed, 10 insertions(+), 4 deletions(-)
diff --git a/combine-diff.c b/combine-diff.c
index 655fa89..360b816 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -682,7 +682,8 @@ static void dump_quoted_path(const char *head,
}
static void show_patch_diff(struct combine_diff_path *elem, int num_parent,
- int dense, struct rev_info *rev)
+ int dense, int working_tree_file,
+ struct rev_info *rev)
{
struct diff_options *opt = &rev->diffopt;
unsigned long result_size, cnt, lno;
@@ -691,7 +692,6 @@ static void show_patch_diff(struct combine_diff_path *elem, int num_parent,
struct sline *sline; /* survived lines */
int mode_differs = 0;
int i, show_hunks;
- int working_tree_file = is_null_sha1(elem->sha1);
int abbrev = DIFF_OPT_TST(opt, FULL_INDEX) ? 40 : DEFAULT_ABBREV;
const char *a_prefix, *b_prefix;
mmfile_t result_file;
@@ -954,6 +954,12 @@ static void show_raw_diff(struct combine_diff_path *p, int num_parent, struct re
write_name_quoted(p->path, stdout, line_termination);
}
+/*
+ * The result (p->elem) is from the working tree and their
+ * parents are typically from multiple stages during a merge
+ * (i.e. diff-files) or the state in HEAD and in the index
+ * (i.e. diff-index).
+ */
void show_combined_diff(struct combine_diff_path *p,
int num_parent,
int dense,
@@ -967,7 +973,7 @@ void show_combined_diff(struct combine_diff_path *p,
DIFF_FORMAT_NAME_STATUS))
show_raw_diff(p, num_parent, rev);
else if (opt->output_format & DIFF_FORMAT_PATCH)
- show_patch_diff(p, num_parent, dense, rev);
+ show_patch_diff(p, num_parent, dense, 1, rev);
}
void diff_tree_combined(const unsigned char *sha1,
@@ -1035,7 +1041,7 @@ void diff_tree_combined(const unsigned char *sha1,
for (p = paths; p; p = p->next) {
if (p->len)
show_patch_diff(p, num_parent, dense,
- rev);
+ 0, rev);
}
}
}
--
1.7.6.401.g6a319
^ permalink raw reply related
* Re: [PATCH 00/48] Handling more corner cases in merge-recursive.c
From: Junio C Hamano @ 2011-08-04 19:03 UTC (permalink / raw)
To: Elijah Newren; +Cc: git, jgfouca
In-Reply-To: <CABPp-BE=9r+upGUD45J7fPshqQE97UMZzaA+cu_WJ1A2p_Bigg@mail.gmail.com>
Elijah Newren <newren@gmail.com> writes:
> ... It
> would be nice to make use of the original index we had before
> unpacking, but that is overwritten at the end of unpack_trees.
I somehow thought that we can give separate src and dst index
to the unpack_tree() machinery these days. Aren't you using it?
^ permalink raw reply
* Re: [PATCH 00/48] Handling more corner cases in merge-recursive.c
From: Elijah Newren @ 2011-08-04 19:16 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git, jgfouca
In-Reply-To: <7vpqkl3sok.fsf@alter.siamese.dyndns.org>
On Thu, Aug 4, 2011 at 1:03 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Elijah Newren <newren@gmail.com> writes:
>
>> ... It
>> would be nice to make use of the original index we had before
>> unpacking, but that is overwritten at the end of unpack_trees.
>
> I somehow thought that we can give separate src and dst index
> to the unpack_tree() machinery these days. Aren't you using it?
Ah, yes, it appears to be possible. I have not touched that part of
merge-recursive, so it still reads:
opts.fn = threeway_merge;
opts.src_index = &the_index;
opts.dst_index = &the_index;
setup_unpack_trees_porcelain(&opts, "merge");
I'll take that route to fix this.
Thanks.
^ permalink raw reply
* Re: [PATCH] rebase -i: fix has_action
From: Junio C Hamano @ 2011-08-04 19:34 UTC (permalink / raw)
To: Noe Rubinstein; +Cc: git
In-Reply-To: <1312450780-5021-1-git-send-email-nrubinstein@proformatique.com>
Noe Rubinstein <nrubinstein@proformatique.com> writes:
> When doing git rebase -i, removing all actions in the todo list is
> supposed to result in aborting the rebase.
I thought it was meant to be more like "removing all _lines_", and the
grep was a half-assed attempt to ignore lines that are clearly comments.
Checking the size of the insn sheet might be a better change in that
sense, as that would not leave any ambiguity:
has_action () {
test -s "$1"
}
> This patch fixes the bug by changing has_action to grep any line
> containing anything that is not a space nor a #.
First of all, I do not think it is a "fixes the bug". I can buy "makes
things safer by detecting user errors", of course.
More importantly, I do not think you are grepping "any line containing
anything that is not a space nor a hash". You are instead grepping lines
that do not begin with a hash or a whitespace, no?
> has_action () {
> - sane_grep '^[^#]' "$1" >/dev/null
> + sane_grep '^[^#[:space:]]' "$1" >/dev/null
> }
We tend to avoid [:character class:] to accomodate older implementations
of grep.
We earlier asked "do we have any line that begins with a character that is
not a hash '#'?" but now we say "do we have any line that begins with a
character that is not a hash nor a space?".
If a user fat-fingers an unnecessary space into a blank line, that line
certainly will be excluded. But if the user fat-fingers ^X^I (or >> for vi
users), all lines begin with whitespace and they now get ignored?
How about removing the unnecessary negation from the logic and directly
ask what we really want to know?
That is, "Do we have a line that is _not_ comment?"
has_action () {
sane_grep -v -e '^#' -e '^[ ]*$' "$1" >/dev/null
}
Hmm?
^ permalink raw reply
* Re: tracking submodules out of main directory.
From: Heiko Voigt @ 2011-08-04 20:05 UTC (permalink / raw)
To: henri GEIST
Cc: Jens Lehmann, Junio C Hamano, Alexei Sholik, git,
Sverre Rabbelier
In-Reply-To: <1312410562.3261.1030.camel@Naugrim.eriador.com>
Hi,
On Thu, Aug 04, 2011 at 12:29:22AM +0200, henri GEIST wrote:
> Le mercredi 03 ao??t 2011 ?? 23:30 +0200, Jens Lehmann a ??crit :
> > Let me make this clear: this is not about changing how submodules are
> > committed in a superproject. It is not about having a loose collection of
> > projects, they stay tied together in a defined state by the superproject.
> >
>
> Yes but for me, from when I started this this topic, it was all about
> having a loose collection of project with dependency references between
> them. And get rid of the superproject.
> It is my first and only goal.
In that case maybe what you want is your own completely independent
implementation of a tool which manages a collection of submodules. I
doubt that tracking of submodules outside of the worktree will ever be
accepted inside core git. Some dependency scheme which makes use of the
current submodule implementation could be a feasible way but you can not
get rid of the superproject.
Your approach introduces many problems which you were not able to
present solutions for. So if you really want to work on this I suggest
you try to implement your solution outside of core git first. If you can
prove that you can solve all the immanent problems we can discuss
integrating it into git again.
> > Henri wanted it a bit upside down: any submodule could request a certain
> > version of another submodule somewhere else in the repo. And he wanted to
> > use gitlinks from one submodule to another for that, which I - hopefully -
> > convinced him was no good idea.
> >
>
> You just convince me that submodules are more than I need and to make a
> lighter independent version of submodules which will never been followed
> by git commands.
As described above this is probably the best way for you. Maybe you can
prove that such a tool works but git's submodules implementation can
currently not really assist you with your approach.
Cheers Heiko
^ permalink raw reply
* [RFC/PATCH 0/5] macro-based key/value maps
From: Jeff King @ 2011-08-04 22:43 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vipr4373f.fsf@alter.siamese.dyndns.org>
On Thu, Jul 14, 2011 at 02:06:28PM -0700, Junio C Hamano wrote:
> Jeff King <peff@peff.net> writes:
>
> > Doing macro meta-programming like this makes me feel a little dirty, but
> > I actually think the result is more readable.
> >
> > [1/3]: implement generic key/value map
> > [2/3]: fast-export: use object to uint32 map instead of "decorate"
> > [3/3]: decorate: use "map" for the underlying implementation
> >
> > What do you think?
>
> Yeah, dirty but nice ;-)
Well, if you like that, then here is the end-result of what the
persistent version would look like. It's quite convenient to use, but an
awful pain to debug. It's done entirely in the preprocessor; I suspect
if I wrote the code generation externally, that would be easier and more
readable (and there are one or two places where we could be slightly
more efficient, that are just difficult to implement via the
preprocessor).
[1/5]: implement generic key/value map
[2/5]: fast-export: use object to uint32 map instead of "decorate"
[3/5]: decorate: use "map" for the underlying implementation
[4/5]: map: implement persistent maps
[5/5]: implement metadata cache subsystem
-Peff
^ permalink raw reply
* [PATCH 1/5] implement generic key/value map
From: Jeff King @ 2011-08-04 22:45 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:
1. The key type must always be a "struct object *".
2. The value type is a void pointer, which means it is
inefficient and cumbersome for storing small values.
One must either encode their value inside the void
pointer, or allocate additional storage for the pointer
to point to.
This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.
One possible strategy for implementation is to have a struct
that points to a sequence of bytes for each of the key and
the value, and to try to treat them as opaque in the code.
However, this code gets complex, has a lot of casts, and
runs afoul of violating alignment and strict aliasing rules.
This patch takes a different approach. We parameterize the
types in each map by putting the declarations and
implementations inside macros, and expand the macros with
the correct types. This lets the compiler see the actual
code, with its real types, and figure out things like struct
packing and alignment itself.
Signed-off-by: Jeff King <peff@peff.net>
---
Documentation/technical/api-map.txt | 160 +++++++++++++++++++++++++++++++++++
Makefile | 2 +
map.c | 86 +++++++++++++++++++
map.h | 26 ++++++
4 files changed, 274 insertions(+), 0 deletions(-)
create mode 100644 Documentation/technical/api-map.txt
create mode 100644 map.c
create mode 100644 map.h
diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
new file mode 100644
index 0000000..4153ef1
--- /dev/null
+++ b/Documentation/technical/api-map.txt
@@ -0,0 +1,160 @@
+map API
+=======
+
+The map API is a system for efficiently mapping keys to values in memory. Items
+are stored in a hash table for fast lookup; storage efficiency is achieved
+through macro-based code generation, which lets the compiler store values
+compactly in memory.
+
+Due to the code generation, there are two different facets of this API: macros
+to build new types of mappings (i.e., generate new function and struct
+definitions), and generated functions to store and retrieve values from a
+particular mapping.
+
+
+Related APIs
+------------
+
+The hash API provides a similar key/value store. However, it does not deal with
+hash collisions itself, leaving the caller to handle bucket management (but
+this is a feature if you are interested in using the collisions as part of an
+algorithm). Furthermore, it can store only void pointers, making storage of
+small values inefficient and cumbersome.
+
+The decorate API provides a similar interface to map, but is restricted to
+using "struct object" as the key, and a void pointer as the value.
+
+
+Defining New Map Types
+----------------------
+
+A map type is uniquely defined by the pair of its key and value types. To
+define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
+`IMPLEMENT_MAP` macro in `map.c`. Their usage is described below:
+
+`DECLARE_MAP`::
+
+ Declare a new type of map, including the struct definition and
+ declarations of access functions. The `name` parameter should describe
+ the types (e.g., `object_uint32` to map objects to 32-bit integers).
+ The `ktype` parameter specifies the C type of the key (e.g.,
+ `struct object *`) and the `vtype` parameter specifies the C type of
+ the value (e.g., `uint32_t`).
+
+`IMPLEMENT_MAP`::
+
+ Create function definitions for a map type. The `name` parameter should
+ match one given to `DECLARE_MAP`. The `equal_fun` parameter should
+ specify a function that, when given two items of type `ktype`, will
+ return a non-zero value if they are equal. The `hash_fun` parameter
+ should specify a function that will convert an object of type `ktype`
+ into an integer hash value.
+
+Several convenience functions are provided to fill in macro parameters:
+
+`hash_obj`::
+
+ Suitable for `hash_fun` when the key type is `struct object *`.
+
+`obj_equal`::
+
+ Suitable for `equal_fun` when the key type is `struct object *`.
+
+
+Data Structures
+---------------
+
+Each defined map type will have its own structure (e.g., `map_object_uint32`).
+
+`struct map_NAME`::
+
+ A single map object. This struct should be initialized to all-zeroes.
+ The `nr` field specifies the number of items stored in the map. The
+ `size` field specifies the number of hash buckets allocated. The `hash`
+ field stores the actual data. Callers should never need to look at
+ these fields unless they are enumerating all elements of the map (see
+ the example below).
+
+`struct map_entry_NAME`::
+
+ A single entry in the hash, which may or may not contain a value. If
+ the `used` field is false, the `key` and `value` fields should not be
+ examined at all. Otherwise, the `key` and `value` fields represent a
+ single mapped pair. You should never need to use this type directly,
+ unless you are enumerating all elements of a map.
+
+
+Functions
+---------
+
+Each defined map type will have its own set of access function (e.g.,
+`map_get_object_uint32`).
+
+`map_get_NAME(struct map_NAME *, const ktype key, vtype *value)`::
+
+ Retrieve the value corresponding to `key`, returning it via the pointer
+ `value`. Returns 1 if an item was found, zero otherwise (in which case
+ `value` is unchanged).
+
+`map_set_NAME(struct map_NAME *, const ktype key, vtype value, vtype *old)`::
+
+ Insert a mapping from `key` to `value`. If a mapping for `key` already
+ existed, the previous value is copied into `old` (if it is non-NULL)
+ and the function returns 1. Otherwise, the function returns 0.
+
+
+Examples
+--------
+
+Create a new mapping type of objects to integers:
+
+-------------------------------------------------------------------
+/* in map.h */
+DECLARE_MAP(object_int, struct object *, int)
+
+/* in map.c */
+IMPLEMENT_MAP(object_int, struct object *, int, obj_equal, hash_obj)
+-------------------------------------------------------------------
+
+Store and retrieve integers by object key:
+
+-------------------------------------------------------------------
+static struct map_object_int foos;
+
+void store_foo(const struct commit *c, int foo)
+{
+ int old;
+ if (map_set_object_uint32(&foos, &c->object, foo, &old))
+ printf("old value was %d\n", old);
+}
+
+void print_foo(const struct commit *c)
+{
+ int v;
+
+ if (map_get_object_int(&foos, &c->object, &v))
+ printf("foo: %d\n", v);
+ else
+ printf("no such foo\n");
+}
+-------------------------------------------------------------------
+
+Iterate over all map entries:
+
+-------------------------------------------------------------------
+void dump_foos(void)
+{
+ int i;
+
+ printf("there are %u foos:\n", foos.nr);
+
+ for (i = 0; i < foos.size; i++) {
+ struct map_entry_object_int *e = foos.hash[i];
+
+ if (!e->used)
+ continue;
+
+ printf("%s -> %d\n", sha1_to_hex(e->key->sha1), e->value);
+ }
+}
+-------------------------------------------------------------------
diff --git a/Makefile b/Makefile
index 4ed7996..acda5b8 100644
--- a/Makefile
+++ b/Makefile
@@ -533,6 +533,7 @@ LIB_H += list-objects.h
LIB_H += ll-merge.h
LIB_H += log-tree.h
LIB_H += mailmap.h
+LIB_H += map.h
LIB_H += merge-file.h
LIB_H += merge-recursive.h
LIB_H += notes.h
@@ -624,6 +625,7 @@ LIB_OBJS += ll-merge.o
LIB_OBJS += lockfile.o
LIB_OBJS += log-tree.o
LIB_OBJS += mailmap.o
+LIB_OBJS += map.o
LIB_OBJS += match-trees.o
LIB_OBJS += merge-file.o
LIB_OBJS += merge-recursive.o
diff --git a/map.c b/map.c
new file mode 100644
index 0000000..35f300e
--- /dev/null
+++ b/map.c
@@ -0,0 +1,86 @@
+#include "cache.h"
+#include "map.h"
+#include "object.h"
+
+static unsigned int hash_obj(const struct object *obj, unsigned int n)
+{
+ unsigned int hash;
+
+ memcpy(&hash, obj->sha1, sizeof(unsigned int));
+ return hash % n;
+}
+
+static int obj_equal(const struct object *a, const struct object *b)
+{
+ return a == b;
+}
+
+#define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
+static int map_insert_##name(struct map_##name *m, \
+ const map_ktype_##name key, \
+ map_vtype_##name value, \
+ map_vtype_##name *old) \
+{ \
+ unsigned int j; \
+\
+ for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+ if (equal_fun(m->hash[j].key, key)) { \
+ if (old) \
+ *old = m->hash[j].value; \
+ m->hash[j].value = value; \
+ return 1; \
+ } \
+ } \
+\
+ m->hash[j].key = key; \
+ m->hash[j].value = value; \
+ m->hash[j].used = 1; \
+ m->nr++; \
+ return 0; \
+} \
+\
+static void map_grow_##name(struct map_##name *m) \
+{ \
+ struct map_entry_##name *old_hash = m->hash; \
+ unsigned int old_size = m->size; \
+ unsigned int i; \
+\
+ m->size = (old_size + 1000) * 3 / 2; \
+ m->hash = xcalloc(m->size, sizeof(*m->hash)); \
+ m->nr = 0; \
+\
+ for (i = 0; i < old_size; i++) { \
+ if (!old_hash[i].used) \
+ continue; \
+ map_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \
+ } \
+ free(old_hash); \
+} \
+\
+int map_set_##name(struct map_##name *m, \
+ const map_ktype_##name key, \
+ map_vtype_##name value, \
+ map_vtype_##name *old) \
+{ \
+ if (m->nr >= m->size * 2 / 3) \
+ map_grow_##name(m); \
+ return map_insert_##name(m, key, value, old); \
+} \
+\
+int map_get_##name(struct map_##name *m, \
+ const map_ktype_##name key, \
+ map_vtype_##name *value) \
+{ \
+ unsigned int j; \
+\
+ if (!m->size) \
+ return 0; \
+\
+ for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+ if (equal_fun(m->hash[j].key, key)) { \
+ *value = m->hash[j].value; \
+ return 1; \
+ } \
+ } \
+ return 0; \
+}
diff --git a/map.h b/map.h
new file mode 100644
index 0000000..cb2d4e2
--- /dev/null
+++ b/map.h
@@ -0,0 +1,26 @@
+#ifndef MAP_H
+#define MAP_H
+
+#define DECLARE_MAP(name, key_type, value_type) \
+typedef key_type map_ktype_##name; \
+typedef value_type map_vtype_##name; \
+struct map_entry_##name { \
+ map_ktype_##name key; \
+ map_vtype_##name value; \
+ unsigned used:1; \
+}; \
+\
+struct map_##name { \
+ unsigned int size, nr; \
+ struct map_entry_##name *hash; \
+}; \
+\
+extern int map_get_##name(struct map_##name *, \
+ const map_ktype_##name key, \
+ map_vtype_##name *value); \
+extern int map_set_##name(struct map_##name *, \
+ const map_ktype_##name key, \
+ map_vtype_##name value, \
+ map_vtype_##name *old);
+
+#endif /* MAP_H */
--
1.7.6.34.g86521e
^ permalink raw reply related
* [PATCH 2/5] fast-export: use object to uint32 map instead of "decorate"
From: Jeff King @ 2011-08-04 22:46 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
Previously we encoded the "mark" mapping inside the "void *"
field of a "struct decorate". It's a little more natural for
us to do so using a data structure made for holding actual
values.
Signed-off-by: Jeff King <peff@peff.net>
---
Documentation/technical/api-map.txt | 2 +-
builtin/fast-export.c | 36 ++++++++++------------------------
map.c | 2 +
map.h | 2 +
4 files changed, 16 insertions(+), 26 deletions(-)
diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
index 4153ef1..97e5a32 100644
--- a/Documentation/technical/api-map.txt
+++ b/Documentation/technical/api-map.txt
@@ -149,7 +149,7 @@ void dump_foos(void)
printf("there are %u foos:\n", foos.nr);
for (i = 0; i < foos.size; i++) {
- struct map_entry_object_int *e = foos.hash[i];
+ struct map_entry_object_int *e = foos.hash + i;
if (!e->used)
continue;
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index becef85..9247871 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -12,7 +12,7 @@
#include "diffcore.h"
#include "log-tree.h"
#include "revision.h"
-#include "decorate.h"
+#include "map.h"
#include "string-list.h"
#include "utf8.h"
#include "parse-options.h"
@@ -60,7 +60,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,
return 0;
}
-static struct decoration idnums;
+static struct map_object_uint32 idnums;
static uint32_t last_idnum;
static int has_unshown_parent(struct commit *commit)
@@ -74,20 +74,9 @@ static int has_unshown_parent(struct commit *commit)
return 0;
}
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
- return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
- return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
static inline void mark_object(struct object *object, uint32_t mark)
{
- add_decoration(&idnums, object, mark_to_ptr(mark));
+ map_set_object_uint32(&idnums, object, mark, NULL);
}
static inline void mark_next_object(struct object *object)
@@ -97,10 +86,9 @@ static inline void mark_next_object(struct object *object)
static int get_object_mark(struct object *object)
{
- void *decoration = lookup_decoration(&idnums, object);
- if (!decoration)
- return 0;
- return ptr_to_mark(decoration);
+ uint32_t ret = 0;
+ map_get_object_uint32(&idnums, object, &ret);
+ return ret;
}
static void show_progress(void)
@@ -538,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)
static void export_marks(char *file)
{
unsigned int i;
- uint32_t mark;
- struct object_decoration *deco = idnums.hash;
FILE *f;
int e = 0;
@@ -548,15 +534,15 @@ static void export_marks(char *file)
die_errno("Unable to open marks file %s for writing.", file);
for (i = 0; i < idnums.size; i++) {
- if (deco->base && deco->base->type == 1) {
- mark = ptr_to_mark(deco->decoration);
- if (fprintf(f, ":%"PRIu32" %s\n", mark,
- sha1_to_hex(deco->base->sha1)) < 0) {
+ const struct map_entry_object_uint32 *m = idnums.hash + i;
+
+ if (m->used && m->key->type == 1) {
+ if (fprintf(f, ":%"PRIu32" %s\n", m->value,
+ sha1_to_hex(m->key->sha1)) < 0) {
e = 1;
break;
}
}
- deco++;
}
e |= ferror(f);
diff --git a/map.c b/map.c
index 35f300e..1fdd1aa 100644
--- a/map.c
+++ b/map.c
@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \
} \
return 0; \
}
+
+IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index cb2d4e2..7449593 100644
--- a/map.h
+++ b/map.h
@@ -23,4 +23,6 @@ extern int map_set_##name(struct map_##name *, \
map_vtype_##name value, \
map_vtype_##name *old);
+DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+
#endif /* MAP_H */
--
1.7.6.34.g86521e
^ permalink raw reply related
* [PATCH 3/5] decorate: use "map" for the underlying implementation
From: Jeff King @ 2011-08-04 22:46 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
The decoration API maps objects to void pointers. This is a
subset of what the map API is capable of, so let's get rid
of the duplicate implementation.
We could just fix all callers of decorate to call the map
API directly. However, the map API is very generic since it
is meant to handle any type. In particular, it can't use
sentinel values like "NULL" to indicate "entry not found"
(since it doesn't know whether the type can represent such a
sentinel value), which makes the interface slightly more
complicated.
Instead, let's keep the existing decorate API as a wrapper
on top of map. No callers need to be updated at all.
Signed-off-by: Jeff King <peff@peff.net>
---
Documentation/technical/api-decorate.txt | 38 +++++++++++++-
decorate.c | 85 +++---------------------------
decorate.h | 10 +---
map.c | 1 +
map.h | 1 +
5 files changed, 48 insertions(+), 87 deletions(-)
diff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt
index 1d52a6c..3c1197a 100644
--- a/Documentation/technical/api-decorate.txt
+++ b/Documentation/technical/api-decorate.txt
@@ -1,6 +1,40 @@
decorate API
============
-Talk about <decorate.h>
+The decorate API is a system for efficiently mapping objects to values
+in memory. It is slightly slower than an actual member of an object
+struct (because it incurs a hash lookup), but it uses less memory when
+the mapping is not in use, or when the number of decorated objects is
+small compared to the total number of objects.
-(Linus)
+The decorate API is a special form of the `map` link:api-map.html[map
+API]. It has slightly simpler calling conventions, but only use objects
+as keys, and can only store void pointers as values.
+
+
+Data Structures
+---------------
+
+`struct decoration`::
+
+ This structure represents a single mapping of objects to values.
+ The `name` field is not used by the decorate API itself, but may
+ be used by calling code. The `map` field represents the actual
+ mapping of objects to void pointers (see the
+ link:api-map.html[map API] for details).
+
+
+Functions
+---------
+
+`add_decoration`::
+
+ Add a mapping from an object to a void pointer. If there was a
+ previous value for this object, the function returns this value;
+ otherwise, the function returns NULL.
+
+`lookup_decoration`::
+
+ Retrieve the stored value pointer for an object from the
+ mapping. The return value is the value pointer, or `NULL` if
+ there is no value for this object.
diff --git a/decorate.c b/decorate.c
index 2f8a63e..31e9656 100644
--- a/decorate.c
+++ b/decorate.c
@@ -1,88 +1,17 @@
-/*
- * decorate.c - decorate a git object with some arbitrary
- * data.
- */
#include "cache.h"
-#include "object.h"
#include "decorate.h"
-static unsigned int hash_obj(const struct object *obj, unsigned int n)
-{
- unsigned int hash;
-
- memcpy(&hash, obj->sha1, sizeof(unsigned int));
- return hash % n;
-}
-
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
-{
- int size = n->size;
- struct object_decoration *hash = n->hash;
- unsigned int j = hash_obj(base, size);
-
- while (hash[j].base) {
- if (hash[j].base == base) {
- void *old = hash[j].decoration;
- hash[j].decoration = decoration;
- return old;
- }
- if (++j >= size)
- j = 0;
- }
- hash[j].base = base;
- hash[j].decoration = decoration;
- n->nr++;
- return NULL;
-}
-
-static void grow_decoration(struct decoration *n)
-{
- int i;
- int old_size = n->size;
- struct object_decoration *old_hash = n->hash;
-
- n->size = (old_size + 1000) * 3 / 2;
- n->hash = xcalloc(n->size, sizeof(struct object_decoration));
- n->nr = 0;
-
- for (i = 0; i < old_size; i++) {
- const struct object *base = old_hash[i].base;
- void *decoration = old_hash[i].decoration;
-
- if (!base)
- continue;
- insert_decoration(n, base, decoration);
- }
- free(old_hash);
-}
-
-/* Add a decoration pointer, return any old one */
void *add_decoration(struct decoration *n, const struct object *obj,
- void *decoration)
+ void *decoration)
{
- int nr = n->nr + 1;
-
- if (nr > n->size * 2 / 3)
- grow_decoration(n);
- return insert_decoration(n, obj, decoration);
+ void *ret = NULL;
+ map_set_object_void(&n->map, obj, decoration, &ret);
+ return ret;
}
-/* Lookup a decoration pointer */
void *lookup_decoration(struct decoration *n, const struct object *obj)
{
- unsigned int j;
-
- /* nothing to lookup */
- if (!n->size)
- return NULL;
- j = hash_obj(obj, n->size);
- for (;;) {
- struct object_decoration *ref = n->hash + j;
- if (ref->base == obj)
- return ref->decoration;
- if (!ref->base)
- return NULL;
- if (++j == n->size)
- j = 0;
- }
+ void *ret = NULL;
+ map_get_object_void(&n->map, obj, &ret);
+ return ret;
}
diff --git a/decorate.h b/decorate.h
index e732804..6a3adcd 100644
--- a/decorate.h
+++ b/decorate.h
@@ -1,15 +1,11 @@
#ifndef DECORATE_H
#define DECORATE_H
-struct object_decoration {
- const struct object *base;
- void *decoration;
-};
+#include "map.h"
struct decoration {
- const char *name;
- unsigned int size, nr;
- struct object_decoration *hash;
+ char *name;
+ struct map_object_void map;
};
extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
diff --git a/map.c b/map.c
index 1fdd1aa..73f45e0 100644
--- a/map.c
+++ b/map.c
@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \
}
IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
+IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index 7449593..cb9aea6 100644
--- a/map.h
+++ b/map.h
@@ -24,5 +24,6 @@ extern int map_set_##name(struct map_##name *, \
map_vtype_##name *old);
DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+DECLARE_MAP(object_void, const struct object *, void *)
#endif /* MAP_H */
--
1.7.6.34.g86521e
^ permalink raw reply related
* [PATCH 4/5] map: implement persistent maps
From: Jeff King @ 2011-08-04 22:46 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
It's sometimes useful to keep a mapping across program
invocations (e.g., because a space/time tradeoff makes it
worth keeping a cache of calculated metadata for some
objects).
This adds a persistent version of the map API which can be
backed by a flat memory store (like an mmap'd file). By
itself, it's not very pleasant to use, as the caller is
responsible for actually opening and mapping files. But it
provides the building blocks for disk caches, which will
come in the next patch.
Signed-off-by: Jeff King <peff@peff.net>
---
Documentation/technical/api-map.txt | 132 +++++++++++++++++++++++++++++
map.c | 157 +++++++++++++++++++++++++++++++++++
map.h | 17 ++++
3 files changed, 306 insertions(+), 0 deletions(-)
diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
index 97e5a32..8ac0cc0 100644
--- a/Documentation/technical/api-map.txt
+++ b/Documentation/technical/api-map.txt
@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to
using "struct object" as the key, and a void pointer as the value.
+Persistent Maps
+---------------
+
+Maps come in two flavors: persistent and in-core. In-core maps are
+represented by a hash table, and can contain any C type. Persistent maps
+are backed by flat storage, such as an mmap'd file, and store values
+between program runs. Key and value types must be serializable to
+fixed-width byte values.
+
+The flat storage is a sorted array of key/value pairs, with no
+delimiters between pairs or between elements of a pair. Persistent maps
+uses an in-core map for newly-added values, and then merge the new
+values into the flat storage on request.
+
+
Defining New Map Types
----------------------
@@ -50,6 +65,32 @@ define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
should specify a function that will convert an object of type `ktype`
into an integer hash value.
+To define a persistent map, use these macros instead:
+
+`DECLARE_MAP_PERSIST`::
+
+ Declare a new persistent map. The `name` parameter must match a
+ map declared already with `DECLARE_MAP`.
+
+`IMPLEMENT_MAP_PERSIST`::
+
+ Create function definitions for a persistent map. The `name`
+ parameter must match one given to `DECLARE_MAP_PERSIST`. The
+ `ksize` and `vsize` parameters indicate the size, in bytes, of
+ serialized keys and values.
++
+ The `k_to_disk` and `v_to_disk` parameters specify functions to
+ convert keys and values to their serialized formats; they take a
+ key (or value), and a pointer to memory of at least `ksize` (or
+ `vsize`) bytes to write into. The `disk_to_v` parameter
+ specifies a function to convert a pointer to `vsize` bytes of
+ serialized value into a `vtype`.
++
+ The `disk_lookup_fun` parameter should specify a function for
+ performing a search of the sorted flat disk array (it is given
+ the array, the number of elements, the size of the key and
+ value, and the key to lookup).
+
Several convenience functions are provided to fill in macro parameters:
`hash_obj`::
@@ -60,6 +101,26 @@ Several convenience functions are provided to fill in macro parameters:
Suitable for `equal_fun` when the key type is `struct object *`.
+`obj_to_disk`::
+
+ Suitable for `k_to_disk` when the key type is `struct object *`.
+
+`uint32_to_disk`::
+
+ Suitable for `k_to_disk` or `v_to_disk` when the type is
+ `uint32_t`. Integers are serialized in network byte order for
+ portability.
+
+`disk_to_uint32`::
+
+ Suitable for `disk_to_v` when the value type is `uint32_t`.
+ Integers are converted back to host byte order.
+
+`disk_lookup_sha1`::
+
+ Suitable for disk_lookup_fun when the serialized keys are sha1
+ hashes.
+
Data Structures
---------------
@@ -83,6 +144,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`).
single mapped pair. You should never need to use this type directly,
unless you are enumerating all elements of a map.
+`struct map_persist_NAME`::
+
+ A persistent map. This struct should be initialized to
+ all-zeroes. The `map` field contains a complete in-core map. The
+ `disk_entries` and `disk_nr` fields specify the flat storage.
+ These should not be set directly, but rather through the
+ `attach` function.
+
Functions
---------
@@ -102,6 +171,27 @@ Each defined map type will have its own set of access function (e.g.,
existed, the previous value is copied into `old` (if it is non-NULL)
and the function returns 1. Otherwise, the function returns 0.
+`map_persist_get_NAME(struct map_persist_NAME *, const ktype key, vtype *value)`::
+
+ Same as `map_get_NAME`, but for a persistent map.
+
+`map_persist_set_NAME(struct map_persist_NAME *, const ktype key, vtype value)`::
+
+ Same as `map_set_name`, but for a persistent map. It also does
+ not provide the "old" value for the key.
+
+`map_persist_attach_NAME`::
+
+ Attach storage from `buf` of size `len` bytes as the flat
+ backing store for the map. The map does not copy the storage;
+ the caller is responsible for making sure it stays around as
+ long as the map does.
+
+`map_persist_flush_NAME`::
+
+ Merge in-core entries with those found in the backing store, and
+ write the result to `fd`. Returns 0 for success, -1 for failure.
+
Examples
--------
@@ -158,3 +248,45 @@ void dump_foos(void)
}
}
-------------------------------------------------------------------
+
+Open and close a disk-backed persistent map of objects to 32-bit
+integers:
+
+-------------------------------------------------------------------
+static int fd;
+static const unsigned char *buf;
+static unsigned len;
+static struct map_persist_object_uint32 map;
+
+void open_map(const char *path)
+{
+ struct stat sb;
+ const unsigned char *p;
+
+ fd = open(path, O_RDONLY);
+ /* it's ok not to attach any backing store at all */
+ if (fd < 0)
+ return;
+
+ fstat(fd, &sb);
+ len = sb.st_size;
+ buf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
+
+ map_persist_attach_object_uint32(&map, buf, len);
+}
+
+/* other functions call "get" and "set" */
+
+void close_map(const char *path, const char *tmp)
+{
+ int tmpfd;
+
+ tmpfd = open(tmp, O_RDONLY);
+ if (map_persist_flush_object_uint32(&map, tmpfd) < 0)
+ die_errno("unable to write new map");
+ close(tmpfd);
+ rename(tmp, path);
+
+ munmap(buf, len);
+ close(fd);
+}
diff --git a/map.c b/map.c
index 73f45e0..bb0d60a 100644
--- a/map.c
+++ b/map.c
@@ -1,6 +1,7 @@
#include "cache.h"
#include "map.h"
#include "object.h"
+#include "sha1-lookup.h"
static unsigned int hash_obj(const struct object *obj, unsigned int n)
{
@@ -15,6 +16,74 @@ static int obj_equal(const struct object *a, const struct object *b)
return a == b;
}
+static void obj_to_disk(const struct object *obj, unsigned char *out)
+{
+ hashcpy(out, obj->sha1);
+}
+
+static void uint32_to_disk(uint32_t v, unsigned char *out)
+{
+ v = htonl(v);
+ memcpy(out, &v, 4);
+}
+
+static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
+{
+ memcpy(out, disk, 4);
+ *out = ntohl(*out);
+}
+
+static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
+ unsigned nr,
+ unsigned ksize, unsigned vsize,
+ const unsigned char *key)
+{
+ int pos;
+
+ pos = sha1_entry_pos(buf, ksize + vsize, 0, 0, nr, nr, key);
+ if (pos < 0)
+ return NULL;
+ return buf + (pos * (ksize + vsize)) + ksize;
+}
+
+static int merge_entries(int fd, int ksize, int vsize,
+ const unsigned char *left, unsigned nr_left,
+ const unsigned char *right, unsigned nr_right)
+{
+#define ADVANCE(name) \
+ do { \
+ name += ksize + vsize; \
+ nr_##name--; \
+ } while (0)
+#define WRITE_ENTRY(name) \
+ do { \
+ if (write_in_full(fd, name, ksize + vsize) < 0) \
+ return -1; \
+ ADVANCE(name); \
+ } while (0)
+
+ while (nr_left && nr_right) {
+ int cmp = memcmp(left, right, ksize);
+
+ /* skip duplicates, preferring left to right */
+ if (cmp == 0)
+ ADVANCE(right);
+ else if (cmp < 0)
+ WRITE_ENTRY(left);
+ else
+ WRITE_ENTRY(right);
+ }
+ while (nr_left)
+ WRITE_ENTRY(left);
+ while (nr_right)
+ WRITE_ENTRY(right);
+
+#undef WRITE_ENTRY
+#undef ADVANCE
+
+ return 0;
+}
+
#define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
static int map_insert_##name(struct map_##name *m, \
const map_ktype_##name key, \
@@ -85,5 +154,93 @@ int map_get_##name(struct map_##name *m, \
return 0; \
}
+#define IMPLEMENT_MAP_PERSIST(name, \
+ ksize, k_to_disk, \
+ vsize, v_to_disk, disk_to_v, \
+ disk_lookup_fun) \
+int map_persist_get_##name(struct map_persist_##name *m, \
+ const map_ktype_##name key, \
+ map_vtype_##name *value) \
+{ \
+ unsigned char disk_key[ksize]; \
+ const unsigned char *disk_value; \
+\
+ if (map_get_##name(&m->mem, key, value)) \
+ return 1; \
+\
+ if (!m->disk_entries) \
+ return 0; \
+\
+ k_to_disk(key, disk_key); \
+ disk_value = disk_lookup_fun(m->disk_entries, m->disk_nr, \
+ ksize, vsize, disk_key); \
+ if (disk_value) { \
+ disk_to_v(disk_value, value); \
+ return 1; \
+ } \
+\
+ return 0; \
+} \
+\
+int map_persist_set_##name(struct map_persist_##name *m, \
+ const map_ktype_##name key, \
+ map_vtype_##name value) \
+{ \
+ return map_set_##name(&m->mem, key, value, NULL); \
+} \
+\
+static unsigned char *flatten_mem_entries_##name(struct map_persist_##name *m) \
+{ \
+ unsigned char *ret, *out; \
+ int i, nr; \
+\
+ out = ret = xmalloc(m->mem.nr * (ksize + vsize)); \
+ nr = 0; \
+ for (i = 0; i < m->mem.size; i++) { \
+ struct map_entry_##name *e = m->mem.hash + i; \
+\
+ if (!e->used) \
+ continue; \
+\
+ if (nr == m->mem.nr) \
+ die("BUG: map hash contained extra values"); \
+\
+ k_to_disk(e->key, out); \
+ out += ksize; \
+ v_to_disk(e->value, out); \
+ out += vsize; \
+ } \
+\
+ return ret; \
+} \
+\
+void map_persist_attach_##name(struct map_persist_##name *m, \
+ const unsigned char *buf, \
+ unsigned int len) \
+{ \
+ m->disk_entries = buf; \
+ m->disk_nr = len / (ksize + vsize); \
+} \
+\
+static int keycmp_##name(const void *a, const void *b) \
+{ \
+ return memcmp(a, b, ksize); \
+} \
+\
+int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
+{ \
+ unsigned char *mem_entries; \
+ int r; \
+\
+ mem_entries = flatten_mem_entries_##name(m); \
+ qsort(mem_entries, m->mem.nr, ksize + vsize, keycmp_##name); \
+\
+ r = merge_entries(fd, ksize, vsize, \
+ mem_entries, m->mem.nr, \
+ m->disk_entries, m->disk_nr); \
+ free(mem_entries); \
+ return r; \
+}
+
IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index cb9aea6..ceddc14 100644
--- a/map.h
+++ b/map.h
@@ -23,6 +23,23 @@ extern int map_set_##name(struct map_##name *, \
map_vtype_##name value, \
map_vtype_##name *old);
+#define DECLARE_MAP_PERSIST(name) \
+struct map_persist_##name { \
+ struct map_##name mem; \
+ const unsigned char *disk_entries; \
+ unsigned int disk_nr; \
+}; \
+extern int map_persist_get_##name(struct map_persist_##name *, \
+ const map_ktype_##name key, \
+ map_vtype_##name *value); \
+extern int map_persist_set_##name(struct map_persist_##name *, \
+ const map_ktype_##name key, \
+ map_vtype_##name value); \
+extern void map_persist_attach_##name(struct map_persist_##name *, \
+ const unsigned char *buf, \
+ unsigned int len); \
+extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
+
DECLARE_MAP(object_uint32, const struct object *, uint32_t)
DECLARE_MAP(object_void, const struct object *, void *)
--
1.7.6.34.g86521e
^ permalink raw reply related
* [PATCH 5/5] implement metadata cache subsystem
From: Jeff King @ 2011-08-04 22:46 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
There are some calculations that git makes repeatedly, even
though the results are invariant for a certain input (e.g.,
the patch-id of a certain commit). We can make a space/time
tradeoff by caching these on disk between runs.
Even though these may be immutable for a certain commit, we
don't want to directly store the results in the commit
objects themselves, for a few reasons:
1. They are not necessarily used by all algorithms, so
bloating the commit object might slow down other
algorithms.
2. Because they can be calculated from the existing
commits, they are redundant with the existing
information. Thus they are an implementation detail of
our current algorithms, and should not be cast in stone
by including them in the commit sha1.
3. They may only be immutable under a certain set of
conditions (e.g., which grafts or replace refs we are
using). Keeping the storage external means we can
invalidate and regenerate the cache whenever those
conditions change.
The persistent map API already provides the storage we need.
This new API takes care of the details of opening and
closing the cache files automatically. Callers need only get
and set values as they see fit.
Signed-off-by: Jeff King <peff@peff.net>
---
Documentation/technical/api-metadata-cache.txt | 67 +++++++++++++
Makefile | 2 +
metadata-cache.c | 126 ++++++++++++++++++++++++
metadata-cache.h | 10 ++
4 files changed, 205 insertions(+), 0 deletions(-)
create mode 100644 Documentation/technical/api-metadata-cache.txt
create mode 100644 metadata-cache.c
create mode 100644 metadata-cache.h
diff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt
new file mode 100644
index 0000000..5f4422d
--- /dev/null
+++ b/Documentation/technical/api-metadata-cache.txt
@@ -0,0 +1,67 @@
+metadata cache API
+==================
+
+The metadata cache API provides simple-to-use, persistent key/value
+storage. It is built on the link:api-map.html[map API], so keys and
+values can have any serializable type.
+
+Caches are statically allocated, and no explicit initialization is
+required. Callers can simply call the "get" and "set" functions for a
+given cache. At program exit, any new entries in the cache are flushed
+to disk.
+
+
+Defining a New Cache
+--------------------
+
+You need to provide three pieces of information to define a new cache:
+
+name::
+ This name will be used both as part of the C identifier and as
+ part of the filename under which the cache is stored. Restrict
+ the characters used to alphanumerics and underscore.
+
+map::
+ The type of map (declared by `DECLARE_MAP`) that this cache will
+ store.
+
+validity::
+ A function that will generate a 20-byte "validity token"
+ representing the conditions under which the cache is valid.
+ For example, a cache that depended on the structure of the
+ history graph would be valid only under a given set of grafts
+ and replace refs. That set could be stirred into a sha1 and used
+ as a validity token.
+
+You must declare the cache in metadata-cache.h using
+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c
+using `IMPLEMENT_METADATA_CACHE`.
+
+
+Using a Cache
+-------------
+
+Interaction with a cache consists entirely of getting and setting
+values. No initialization or cleanup is required. The get and set
+functions mirror their "map" counterparts; see the
+link:api-map.html[map API] for details.
+
+
+File Format
+-----------
+
+Cache files are stored in the $GIT_DIR/cache directory. Each cache gets
+its own directory, named after the `name` parameter in the cache
+definition. Within each directory is a set of files, one cache per file,
+named after their validity tokens. Caches for multiple sets of
+conditions can simultaneously exist, and git will use whichever is
+appropriate.
+
+The files themselves consist of an 8-byte header. The first four bytes
+are the magic sequence "MTAC" (for "MeTA Cache"), followed by a 4-byte
+version number, in network byte order. This document describes version
+1.
+
+The rest of the file consists of the persistent map data. This is a
+compact, sorted list of keys and values; see the link:api-map.html[map
+API] for details.
diff --git a/Makefile b/Makefile
index acda5b8..3b39538 100644
--- a/Makefile
+++ b/Makefile
@@ -536,6 +536,7 @@ LIB_H += mailmap.h
LIB_H += map.h
LIB_H += merge-file.h
LIB_H += merge-recursive.h
+LIB_H += metadata-cache.h
LIB_H += notes.h
LIB_H += notes-cache.h
LIB_H += notes-merge.h
@@ -629,6 +630,7 @@ LIB_OBJS += map.o
LIB_OBJS += match-trees.o
LIB_OBJS += merge-file.o
LIB_OBJS += merge-recursive.o
+LIB_OBJS += metadata-cache.o
LIB_OBJS += name-hash.o
LIB_OBJS += notes.o
LIB_OBJS += notes-cache.o
diff --git a/metadata-cache.c b/metadata-cache.c
new file mode 100644
index 0000000..e217db1
--- /dev/null
+++ b/metadata-cache.c
@@ -0,0 +1,126 @@
+#include "cache.h"
+#include "metadata-cache.h"
+#include "map.h"
+
+static const char *metadata_cache_path(const char *name,
+ void (*validity)(unsigned char [20]))
+{
+ unsigned char token[20];
+
+ if (validity)
+ validity(token);
+ else
+ hashcpy(token, null_sha1);
+ return git_path("cache/%s/%s", name, sha1_to_hex(token));
+}
+
+#define IMPLEMENT_METADATA_CACHE(name, map, validity) \
+static struct map_persist_##map name##_map; \
+static int name##_fd; \
+static unsigned char *name##_buf; \
+static unsigned long name##_len; \
+\
+static void write_##name##_cache(void) \
+{ \
+ const char *path; \
+ struct strbuf tempfile = STRBUF_INIT; \
+ int fd = -1; \
+\
+ if (!name##_map.mem.nr) \
+ return; \
+\
+ path = metadata_cache_path(#name, validity); \
+ strbuf_addf(&tempfile, "%s.XXXXXX", path); \
+\
+ if (safe_create_leading_directories(tempfile.buf) < 0) \
+ goto fail; \
+ fd = git_mkstemp_mode(tempfile.buf, 0444); \
+ if (fd < 0) \
+ goto fail; \
+\
+ if (write_in_full(fd, "MTAC\x00\x00\x00\x01", 8) < 0) \
+ goto fail; \
+ if (map_persist_flush_##map(&name##_map, fd) < 0) \
+ goto fail; \
+ if (close(fd) < 0) \
+ goto fail; \
+ if (rename(tempfile.buf, path) < 0) \
+ goto fail; \
+\
+ strbuf_release(&tempfile); \
+ return; \
+\
+fail: \
+ close(fd); \
+ unlink(tempfile.buf); \
+ strbuf_release(&tempfile); \
+} \
+\
+static void init_##name##_cache(void) \
+{ \
+ static int initialized; \
+ const char *path; \
+ struct stat sb; \
+ const unsigned char *p; \
+ uint32_t version; \
+\
+ if (initialized) \
+ return; \
+\
+ atexit(write_##name##_cache); \
+ initialized = 1; \
+\
+ path = metadata_cache_path(#name, validity); \
+ name##_fd = open(path, O_RDONLY); \
+ if (name##_fd < 0) \
+ return; \
+\
+ if (fstat(name##_fd, &sb) < 0) \
+ goto fail; \
+ name##_len = sb.st_size; \
+ name##_buf = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, \
+ name##_fd, 0); \
+\
+ if (name##_len < 8) { \
+ warning("cache '%s' is missing header", path); \
+ goto fail; \
+ } \
+ p = name##_buf; \
+ if (memcmp(p, "MTAC", 4)) { \
+ warning("cache '%s' has invalid magic: %c%c%c%c", \
+ path, p[0], p[1], p[2], p[3]); \
+ goto fail; \
+ } \
+ p += 4; \
+ memcpy(&version, p, 4); \
+ version = ntohl(version); \
+ if (version != 1) { \
+ warning("cache '%s' has unknown version: %"PRIu32, \
+ path, version); \
+ goto fail; \
+ } \
+\
+ map_persist_attach_##map(&name##_map, \
+ name##_buf + 8, \
+ name##_len - 8); \
+ return; \
+\
+fail: \
+ close(name##_fd); \
+ name##_fd = -1; \
+ if (name##_buf) \
+ munmap(name##_buf, name##_len); \
+ name##_buf = NULL; \
+ name##_len = 0; \
+} \
+\
+int name##_cache_get(map_ktype_##map key, map_vtype_##map *value) \
+{ \
+ init_##name##_cache(); \
+ return map_persist_get_##map(&name##_map, key, value); \
+} \
+int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \
+{ \
+ init_##name##_cache(); \
+ return map_persist_set_##map(&name##_map, key, value); \
+}
diff --git a/metadata-cache.h b/metadata-cache.h
new file mode 100644
index 0000000..851a4eb
--- /dev/null
+++ b/metadata-cache.h
@@ -0,0 +1,10 @@
+#ifndef METADATA_CACHE_H
+#define METADATA_CACHE_H
+
+#include "map.h"
+
+#define DECLARE_METADATA_CACHE(name, map) \
+extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \
+extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);
+
+#endif /* METADATA_CACHE_H */
--
1.7.6.34.g86521e
^ permalink raw reply related
* [RFC/PATCH 0/2] patch-id caching
From: Jeff King @ 2011-08-04 22:48 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224354.GA27476@sigill.intra.peff.net>
On Thu, Aug 04, 2011 at 04:43:54PM -0600, Jeff King wrote:
> [1/5]: implement generic key/value map
> [2/5]: fast-export: use object to uint32 map instead of "decorate"
> [3/5]: decorate: use "map" for the underlying implementation
> [4/5]: map: implement persistent maps
> [5/5]: implement metadata cache subsystem
And here's a potential user of the new code:
[1/2]: cherry: read default config
[2/2]: cache patch ids on disk
-Peff
^ permalink raw reply
* [PATCH 1/2] cherry: read default config
From: Jeff King @ 2011-08-04 22:49 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224848.GA27545@sigill.intra.peff.net>
We don't currently read the config at all for git-cherry.
This doesn't seem to cause any issues so far, because what
it does is so simple that none of the configuration matters.
However, the next patch will add a relevant config option.
Signed-off-by: Jeff King <peff@peff.net>
---
builtin/log.c | 2 ++
1 files changed, 2 insertions(+), 0 deletions(-)
diff --git a/builtin/log.c b/builtin/log.c
index 5c2af59..f385fb8 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1438,6 +1438,8 @@ int cmd_cherry(int argc, const char **argv, const char *prefix)
OPT_END()
};
+ git_config(git_default_config, NULL);
+
argc = parse_options(argc, argv, prefix, options, cherry_usage, 0);
switch (argc) {
--
1.7.6.34.g86521e
^ permalink raw reply related
* [PATCH 2/2] cache patch ids on disk
From: Jeff King @ 2011-08-04 22:49 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224848.GA27545@sigill.intra.peff.net>
Some workflows may involve running "git cherry" a lot to
look for identical patches. Git ends up calculating the
patch-id of some commits many times, which can be slow.
This patch provides an option to cache the calculated patch
ids persistently on disk. This trades more disk space (and
more RAM used for disk cache) for less CPU time. Whether
this is a good idea depends on your workflow and how much
disk and RAM you have (the cache uses 40 bytes per stored
commit).
Here's one cherry-heavy workflow (checking which topic
branches have been accepted upstream), and some timings:
have_commits() {
test -z "`git cherry "$@" | grep -v ^-`"
}
for i in $topic_branches; do
if have_commits origin/master $i $i@{u}; then
echo $i: merged to origin/master
elif have_commits origin/next $i $i@{u}; then
echo $i: merged to origin/next
else
echo $i: not merged
done
# without patch
real 0m9.709s
user 0m8.693s
sys 0m0.676s
# with patch, first run
real 0m1.946s
user 0m1.244s
sys 0m0.428s
# with patch, subsequent run
real 0m1.379s
user 0m0.844s
sys 0m0.268s
and the disk used:
$ du -h .git/cache/patch_id/*
8.0K .git/cache/patch_id/0000000000000000000000000000000000000000
Signed-off-by: Jeff King <peff@peff.net>
---
cache.h | 1 +
config.c | 5 +++++
map.c | 16 ++++++++++++++++
map.h | 6 ++++++
metadata-cache.c | 2 ++
metadata-cache.h | 2 ++
patch-ids.c | 22 +++++++++++++++++++++-
7 files changed, 53 insertions(+), 1 deletions(-)
diff --git a/cache.h b/cache.h
index 9e12d55..060f0f9 100644
--- a/cache.h
+++ b/cache.h
@@ -596,6 +596,7 @@ extern int read_replace_refs;
extern int fsync_object_files;
extern int core_preload_index;
extern int core_apply_sparse_checkout;
+extern int core_cache_patch_id;
enum branch_track {
BRANCH_TRACK_UNSPECIFIED = -1,
diff --git a/config.c b/config.c
index e42c59b..09e84c3 100644
--- a/config.c
+++ b/config.c
@@ -659,6 +659,11 @@ static int git_default_core_config(const char *var, const char *value)
return 0;
}
+ if (!strcmp(var, "core.cachepatchid")) {
+ core_cache_patch_id = git_config_bool(var, value);
+ return 0;
+ }
+
/* Add other config variables here and to Documentation/config.txt. */
return 0;
}
diff --git a/map.c b/map.c
index bb0d60a..9d8d5ab 100644
--- a/map.c
+++ b/map.c
@@ -33,6 +33,16 @@ static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
*out = ntohl(*out);
}
+static void sha1_to_disk(struct sha1 v, unsigned char *out)
+{
+ hashcpy(out, v.v);
+}
+
+static void disk_to_sha1(const unsigned char *disk, struct sha1 *out)
+{
+ hashcpy(out->v, disk);
+}
+
static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
unsigned nr,
unsigned ksize, unsigned vsize,
@@ -244,3 +254,9 @@ int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
+
+IMPLEMENT_MAP(object_sha1, obj_equal, hash_obj)
+IMPLEMENT_MAP_PERSIST(object_sha1,
+ 20, obj_to_disk,
+ 20, sha1_to_disk, disk_to_sha1,
+ disk_lookup_sha1)
diff --git a/map.h b/map.h
index ceddc14..18eb939 100644
--- a/map.h
+++ b/map.h
@@ -40,7 +40,13 @@ extern void map_persist_attach_##name(struct map_persist_##name *, \
unsigned int len); \
extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
+struct sha1 {
+ unsigned char v[20];
+};
+
DECLARE_MAP(object_uint32, const struct object *, uint32_t)
DECLARE_MAP(object_void, const struct object *, void *)
+DECLARE_MAP(object_sha1, const struct object *, struct sha1)
+DECLARE_MAP_PERSIST(object_sha1)
#endif /* MAP_H */
diff --git a/metadata-cache.c b/metadata-cache.c
index e217db1..0ce0e90 100644
--- a/metadata-cache.c
+++ b/metadata-cache.c
@@ -124,3 +124,5 @@ int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \
init_##name##_cache(); \
return map_persist_set_##map(&name##_map, key, value); \
}
+
+IMPLEMENT_METADATA_CACHE(patch_id, object_sha1, NULL)
diff --git a/metadata-cache.h b/metadata-cache.h
index 851a4eb..ff2f6d3 100644
--- a/metadata-cache.h
+++ b/metadata-cache.h
@@ -7,4 +7,6 @@
extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \
extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);
+DECLARE_METADATA_CACHE(patch_id, object_sha1)
+
#endif /* METADATA_CACHE_H */
diff --git a/patch-ids.c b/patch-ids.c
index 5717257..d1818eb 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -3,17 +3,37 @@
#include "commit.h"
#include "sha1-lookup.h"
#include "patch-ids.h"
+#include "metadata-cache.h"
+
+int core_cache_patch_id;
static int commit_patch_id(struct commit *commit, struct diff_options *options,
unsigned char *sha1)
{
+ if (core_cache_patch_id) {
+ struct sha1 v;
+ if (patch_id_cache_get(&commit->object, &v)) {
+ hashcpy(sha1, v.v);
+ return 0;
+ }
+ }
+
if (commit->parents)
diff_tree_sha1(commit->parents->item->object.sha1,
commit->object.sha1, "", options);
else
diff_root_tree_sha1(commit->object.sha1, "", options);
diffcore_std(options);
- return diff_flush_patch_id(options, sha1);
+ if (diff_flush_patch_id(options, sha1) < 0)
+ return -1;
+
+ if (core_cache_patch_id) {
+ struct sha1 v;
+ hashcpy(v.v, sha1);
+ patch_id_cache_set(&commit->object, v);
+ }
+
+ return 0;
}
static const unsigned char *patch_id_access(size_t index, void *table)
--
1.7.6.34.g86521e
^ permalink raw reply related
* Re: git-archive's wrong documentation: really write pax rather than tar
From: Junio C Hamano @ 2011-08-04 22:51 UTC (permalink / raw)
To: Jeff King; +Cc: Hin-Tak Leung, git, rene.scharfe
In-Reply-To: <20110804021329.GB32579@sigill.intra.peff.net>
Jeff King <peff@peff.net> writes:
> As a bonus, this also fixes an example in the git-push manpage, in which
> "git push origin :::" was accidentally considered a newly-indented list,
> and not a list item with "git push origin :" in it.
Thanks. That "happens to have colon at the end" one is nasty.
^ permalink raw reply
* Re: [PATCH 2/2] cache patch ids on disk
From: Jeff King @ 2011-08-04 22:52 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <20110804224947.GB28215@sigill.intra.peff.net>
On Thu, Aug 04, 2011 at 04:49:47PM -0600, Jeff King wrote:
> +struct sha1 {
> + unsigned char v[20];
> +};
> +
> [...]
> +DECLARE_MAP(object_sha1, const struct object *, struct sha1)
I'm not altogether happy with this. But the generated code wants to
treat the value type as something that can be instantiated as "vtype
foo", so we need to wrap a struct around an array to make the compiler
happy.
We could do something a little fancier to avoid this, like separating
"this is what it looks like to declare a value" from "this is what a
passed value looks like". And then use "unsigned char v[20]" for the
former and "unsigned char *" for the latter.
-Peff
^ permalink raw reply
* Re: tracking submodules out of main directory.
From: henri GEIST @ 2011-08-05 0:29 UTC (permalink / raw)
To: Jens Lehmann
Cc: Junio C Hamano, Heiko Voigt, Alexei Sholik, git, Sverre Rabbelier
In-Reply-To: <4E3ADAD0.1060800@web.de>
Le jeudi 04 août 2011 à 19:45 +0200, Jens Lehmann a écrit :
> Am 04.08.2011 00:29, schrieb henri GEIST:
> > Le mercredi 03 août 2011 à 23:30 +0200, Jens Lehmann a écrit :
> >> Am 03.08.2011 21:41, schrieb Junio C Hamano:
> >>> Jens Lehmann <Jens.Lehmann@web.de> writes:
> >> But when you fetch a new version of Gimp into your submodule, it would be
> >> really nice if the superproject could be notified that the Gimp developers
> >> updated to 1.2.4 of Glib and inform you that an update of Glib might be
> >> appropriate. That could avoid having you to dig through compiler errors to
> >> find out that the new foobar() function from Glib 1.2.4 is needed (and if
> >> you need to pull in a bugfix in Glib, you might notice that *a lot* later
> >> when you forget to do that).
> >>
> >
> > Exact, I am really happy to read this.
> > And better do not bother to have the suproject.
>
> I don't get this, you can't get rid of the superproject.
Of corse I can.
I have done It the patch I have submit has been done for an do it
successfully.
I am doing it every day.
I have in the same "directory" not repository.
Two repository "gimp" and "libpng".
I cd in the gimp directory.
And do "git add ../libpng" and it is done.
The gimp repository track the "../libpng" repository by its path and
sha1.
I do not need anything else.
>
> > cd to gimp directory, type git status it can tell you every thing and
> > when your satisfied you just have to type make.
> > At this point the superproject have not any use.
>
> "git status" inside the submodule won't tell you anything about the
> dependencies,
Of corse It does if the repository add been add
It will just like any other submodules inside of the repository
Git status is even unable to see the difference.
Essential because there is no difference.
> but a "git status" in the superproject should.
Yes but I have no and want not to have a superproject.
> The submodule shouldn't know where exactly the submodules it depends on lives, that is
> the decision of the superproject, not the submodule.
Why not in my case it is needed has in "gimp.c" I have
#include "../libpng.h"
If the code need to know where is libpng why the repository should not
know it as well ?
>
> >>>> In addition to that, it can (but mustn't) specify any of the following:
> >>>
> >>> I am guessing you meant "does not have to", instead of mustn't, here...
> >>
> >> Sure, thanks for deciphering that.
> >>
> >>>> a) Of this submodule "foo" I need at least that version because I won't
> >>>> compile/work with older versions of that. (this can be tightened to
> >>>> "exactly that version" to give henri the behavior he wants, but that
> >>>> should be policy, not mandatory)
> >>>
> >>> The "loose collection of projects" approach like that has its uses, and it
> >>> is called "repo". Why re-invent it? The behaviour Henri wants to specify
> >>> the exact version is how git submodules work already, so I do not see
> >>> there is anything to be done here.
> >>
> >> Let me make this clear: this is not about changing how submodules are
> >> committed in a superproject. It is not about having a loose collection of
> >> projects, they stay tied together in a defined state by the superproject.
> >>
> >
> > Yes but for me, from when I started this this topic, it was all about
> > having a loose collection of project with dependency references between
> > them. And get rid of the superproject.
> > It is my first and only goal.
>
> But I fail to see how that would improve anything.
>
It improve my life and the life of my team has developers everyday.
All my team agree on this point. In fact they asked me to implement it.
Because we used to have a superproject and it does not scale well.
The "gimp" team and the "gqview" team shares the libpng but at there
point of view they are not related they even not need to know that the
other one exist. Then they will never share the same superproject. It
has no sens for them.
Then in your model you will need a superproject by project.
I think we should put all that you put in the superproject in the
project itself. Then there will be only one project by project.
And if the dependency are not part of the superproject, this remove the
burden of each team to redefine all the dependencies recursively in any
dependency they have. has the original "libpng" team have done it in the
"libpng" project and not in there own superprojec witch the can not
share.
> >> Henri wanted it a bit upside down: any submodule could request a certain
> >> version of another submodule somewhere else in the repo. And he wanted to
> >> use gitlinks from one submodule to another for that, which I - hopefully -
> >> convinced him was no good idea.
> >>
> >
> > You just convince me that submodules are more than I need and to make a
> > lighter independent version of submodules which will never been followed
> > by git commands.
>
> Submodules are what you need, but it's no use to implement dependencies by
> using gitlinks that point outside of their repositories.
>
Submodules is not what I need.
What I need is pointers to external repository tracked by git.
Submodule was to my eyes the logical tool to do it.
And I had made a patch to enable the tracking of external repository
just has they do for internal ones.
You convince me that you think prohibiting me to do so is a feature to
your eyes. Because gitlinks and submodules can do more than this and you
do not want those other things to work outside of the repository.
Then I propose to cook a kind of "my_light_gitlinks" which do only that.
> >>>> b) And if you don't know where to get it, use this url
> >>>
> >>> Again that is the job of .gitmodules in the superproject.
> >>
> >> Yes. But this idea is about how the url could get into the .gitmodules of
> >> the superproject in the first place. That can make it easier for the
> >> superproject's developer to import a submodule into his repo and much more
> >> important: it makes it possible to pull in submodule dependencies
> >> automatically e.g. when running "git submodule add --resolve-dependencies
> >> Gimp".
> >
> > Only if you have a superproject.
> > If not do the same thing from the gimp repository, now it contain all
> > necessary infos to do the job.
>
> No, it doesn't. Apart from the Gimp project telling you what version it
> wants, you need to have a place to record the version that the user really
> used. And that won't work without a superproject.
>
the version of "libpng" that the user really use is stored in his
"libpng" repository !
And tracked by every project depending on it.
> >>>> That is all stuff the submodule knows better than the superproject.
> >>>
> >>> Not necessarily. The version A0 of submodule A may depend on submodule B
> >>> and may also know it must have at least version B0 of that submodule, but
> >>> the superproject would know other constraints, e.g. the superproject
> >>> itself also calls into submodule B and wants a newer version B1 of it.
> >>
> >> Right. That's what I tried to explain to Henri, the superproject ties it all
> >> together. But I also like his idea to add a way to communicate information
> >> from the submodule to the superproject, and give the superproject a choice
> >> if it wants to use it.
> >>
> >
> > yes but the superproject contain no code in your design.
> > Then it will never need anything by itself.
> > It is only a container which you will inform with data already known by
> > the submodules I do not see any value to it.
>
> But being the container that ties it all together is more than enough value.
>
It has absolutely no value to have a git repository as a container.
A simple directory will do it very well.
Henri
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox