* Re: "git-send-pack"
From: Linus Torvalds @ 2005-06-30 21:08 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Daniel Barkalow, git
In-Reply-To: <7vll4r1sxz.fsf@assigned-by-dhcp.cox.net>
On Thu, 30 Jun 2005, Junio C Hamano wrote:
>
> Now is there anything for us poor mortals who would want to have
> a "pull" support? Logging in via ssh and run send-pack on the
> other end is workable but not so pretty ;-).
I'm thinking about it. You can't actually do send-pack from the other end,
since send-pack needs to know what the base is, and the base you have may
not even exist in the remote.
So a "git-pull-pack" will follow the objects on the other side until it
hits one we have, and _then_ it can send a nice pack. It's not hard per
se, and some of the problems are actually simpler than git-send-pack, but
it needs more communication (and in order to be efficient you want to not
ping-pong a "do-you-have-it" query every time around).
I also want to make sure that the biggest burden is on the pull side, not
the push side. I have a plan, though.
Linus
^ permalink raw reply
* Re: "git-send-pack"
From: Daniel Barkalow @ 2005-06-30 21:05 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, git
In-Reply-To: <7vll4r1sxz.fsf@assigned-by-dhcp.cox.net>
On Thu, 30 Jun 2005, Junio C Hamano wrote:
> >>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:
>
> LT> In fact, the most recent push was gone with a
>
> LT> git-send-pack master.kernel.org:/pub/scm/linux/kernel/git/torvalds/git.git
>
> Congrats for a job well done.
>
> Now is there anything for us poor mortals who would want to have
> a "pull" support? Logging in via ssh and run send-pack on the
> other end is workable but not so pretty ;-).
I suspect that I'll be able to merge send-pack/receive-pack with
ssh-push/ssh-pull this evening, and then it'll have the feature of not
caring too much which side your command line is on.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: "git-send-pack"
From: Dan Holmsand @ 2005-06-30 21:10 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Linus Torvalds, Daniel Barkalow, git
In-Reply-To: <7vll4r1sxz.fsf@assigned-by-dhcp.cox.net>
Junio C Hamano wrote:
>>>>>>"LT" == Linus Torvalds <torvalds@osdl.org> writes:
>
>
> LT> In fact, the most recent push was gone with a
>
> LT> git-send-pack master.kernel.org:/pub/scm/linux/kernel/git/torvalds/git.git
>
> Congrats for a job well done.
Agree totally. And the whole pack thing is really cool. Git is sooo much
faster when running from pack-files only on my poor laptop.
> Now is there anything for us poor mortals who would want to have
> a "pull" support? Logging in via ssh and run send-pack on the
> other end is workable but not so pretty ;-).
Agreed again :-)
Even cooler would be pack-pulls via http. That would be a bit hard on
the servers with the current git-pack-objects, but it ought to be
possible to create something similar that doesn't re-delta anything, but
instead just spits out what's in an existing pack-file, and (perhaps)
deltifies objects from the file system.
If people then re-pack their repositories occasionally, this should be
plenty fast, the number of files for rsync to deal with could be kept
down, as could download times for mortal users.
/dan
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-06-30 21:26 UTC (permalink / raw)
To: H. Peter Anvin
Cc: Linus Torvalds, Daniel Barkalow, Git Mailing List, Junio C Hamano,
ftpadmin
In-Reply-To: <42C462CD.9010909@zytor.com>
H. Peter Anvin wrote:
> Linus Torvalds wrote:
>
>>
>>> For the purposes of rsync, storing the objects in a single
>>> append-only file would be a very efficient method, since the rsync
>>> algorithm will quickly discover an invariant head and only transmit
>>> the tail.
>>
>>
>> Actually, it won't be "quick" - it will have to read the whole file
>> and do it's hash window thing.
>>
>
> It does that, but it only have to do that when the actual file has
> changed. That's acceptable, at least for the repository sizes we're
> likely to deal with within the medium term.
>
I guess I should clarify a bit here. I'm concerned with two aspects:
the "keeping mirrors in sync" problem, where asking people to use a tool
other than rsync is a really tough sell, and the developer usage
scenario, in which case something git-aware is obviously the better thing.
-hpa
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-06-30 21:23 UTC (permalink / raw)
To: Linus Torvalds
Cc: Daniel Barkalow, Git Mailing List, Junio C Hamano, ftpadmin
In-Reply-To: <Pine.LNX.4.58.0506301344070.14331@ppc970.osdl.org>
Linus Torvalds wrote:
>
>>For the purposes of rsync, storing the objects in a single append-only
>>file would be a very efficient method, since the rsync algorithm will
>>quickly discover an invariant head and only transmit the tail.
>
> Actually, it won't be "quick" - it will have to read the whole file and do
> it's hash window thing.
>
It does that, but it only have to do that when the actual file has
changed. That's acceptable, at least for the repository sizes we're
likely to deal with within the medium term.
-hpa
^ permalink raw reply
* Re: "git-send-pack"
From: Linus Torvalds @ 2005-06-30 21:29 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.21.0506301651250.30848-100000@iabervon.org>
On Thu, 30 Jun 2005, Daniel Barkalow wrote:
>
> I suspect that I'll be able to merge send-pack/receive-pack with
> ssh-push/ssh-pull this evening, and then it'll have the feature of not
> caring too much which side your command line is on.
The simple thing to do is to just get one commit at a time, see if you
have it already, parse if it not, and go on to the parents.
That would fit the current git-pull thing, and may be good enough, but it
has the downside that it can need a _lot_ of back-and-forth fecthing of
commit objects from the other side until you find the one you want. That's
going to be _very_ slow over a high-latency connection.
So what I'd suggest is:
- puller starts by just asking "what's your SHA1 for the ref I want"
The puller wants to know this, because a common case may be that it
already has it, in which case it doesn't need to do anything. But more
importantly, the puller will need to know this anyway if it gets an
object-pack, so that the puller can update it's FETCH_HEAD.
- if puller doesn't have it, then the _puller_ does:
"git-rev-list my-current-refs"
to generate an in-date-order list of commits it has, and it starts
feeding the result in chunks of 100 entries or something to the other
end.
- now, the server sees this stream of SHA1's that the client wants, and
it can very cheaply just test "do I have this SHA1". Now, if the client
hasn't made any changes at all, then the first one will be a hit, and
we already have sufficient knowledge to tell what the difference
between the client and the server is.
But more importantly, even if the client _has_ made changes, the client
likely has more available CPU than the server has, _and_ the client
likely has a shorter list of changes than the server has, so it's
really the client that should do this. We should burden the server as
lightly as possible for this to scale.
- At some point the server sees the first SHA1 it recognizes, and at that
point the server will have to start working. It will just send back an
"ok, got it" message (telling the client to not bother continuing to
send it any more commit ID's), and then does
git-rev-list --objects ref-client-wants ^first-common-sha1 |
git-pack-objects --stdout
- the client just unpacks the objects, and if successful, it puts the new
top ref it got into FETCH_HEAD. It's now done.
And I do _not_ think that it makes a lot of sense to try to be symmetric.
For one thing, while a "git-send-pack" should update all the refs
in-place, a "git-pull-pack" should _not_ update the ref, it should just
set FETCH_HEAD instead and the puller can decide what he wants to do with
that ref (possibly merge it, but possibly just make it be a new local
branch "remote-branch").
So I think sending and receiving are fundamentally non-symmetric.
Linus
^ permalink raw reply
* Re: "git-send-pack"
From: Linus Torvalds @ 2005-06-30 21:42 UTC (permalink / raw)
To: H. Peter Anvin
Cc: Daniel Barkalow, Git Mailing List, Junio C Hamano, ftpadmin
In-Reply-To: <42C462CD.9010909@zytor.com>
On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
> It does that, but it only have to do that when the actual file has
> changed. That's acceptable, at least for the repository sizes we're
> likely to deal with within the medium term.
Well, realize that "incremental packs" deltify a lot worse than a "big
pack", since pack-files don't do deltas to objects outside the pack-file.
So we'd get _some_ compression, but not as much as possible. The current
kernel compresses down to a single 63 MB pack-file (that's with the 2.6.11
tree too, not just the HEAD history), but without deltas it weights in at
about 177 MB.
So a "sum of incremental packs" should be somewhere in between those two
values, even today. For a single kernel archive.
So repository sizes aren't exactly trivial. I don't know how expensive
that rsync hash thing is, but one thing you lose is the ability to
hardlink objects, so if you have a few kernel repositories at some point
it doesn't fit in the cache any more, and then the rsync will have to read
that much pack object stuff from disk in addition to doing the hash. Ugh.
Linus
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-06-30 21:55 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Barkalow, Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506301412470.14331@ppc970.osdl.org>
It seems to me that git always defines a DAG of objects, such that if
you have a list of terminals (defined as objects not referenced by other
objects), you can, given access to the same objects, figure out all
intervening objects.
The tricky bit becomes finding the DAG both sides have in common with as
little traffic as possible.
For producing minimum network traffic, I think something like this would
work:
a) The sender sends a list of its terminals to the receiver.
b) The receiver sends a list of nodes it needs, plus a list of all its
own meta-terminals, obtained by pruning its own DAG according to the
terminals list of the sender.
c) This may have to be performed iteratively? I need to sit down and
work out the exact algorithm for all cases, including branch trees and
multi-rooted DAGs.
d) Once the sender knows the subset of its own DAG available to the
receiver, it can transmit either all objects that it has the sender does
not, or all objects on the path to one or more specific objects (e.g. HEAD.)
-hpa
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-06-30 22:00 UTC (permalink / raw)
To: Linus Torvalds
Cc: Daniel Barkalow, Git Mailing List, Junio C Hamano, ftpadmin
In-Reply-To: <Pine.LNX.4.58.0506301432500.14331@ppc970.osdl.org>
Linus Torvalds wrote:
>
> On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
>>It does that, but it only have to do that when the actual file has
>>changed. That's acceptable, at least for the repository sizes we're
>>likely to deal with within the medium term.
>
>
> Well, realize that "incremental packs" deltify a lot worse than a "big
> pack", since pack-files don't do deltas to objects outside the pack-file.
>
> So we'd get _some_ compression, but not as much as possible. The current
> kernel compresses down to a single 63 MB pack-file (that's with the 2.6.11
> tree too, not just the HEAD history), but without deltas it weights in at
> about 177 MB.
>
> So a "sum of incremental packs" should be somewhere in between those two
> values, even today. For a single kernel archive.
>
> So repository sizes aren't exactly trivial. I don't know how expensive
> that rsync hash thing is, but one thing you lose is the ability to
> hardlink objects, so if you have a few kernel repositories at some point
> it doesn't fit in the cache any more, and then the rsync will have to read
> that much pack object stuff from disk in addition to doing the hash. Ugh.
>
The bulk of the cost in doing the hashing comes from having to read the
file.
Well, if you grow a single pack file with appending, then you can have
delta references to earlier objects within the same pack file.
At least at this point, we'd handle a few very large files a lot better
than an enormous swarm of smaller ones.
In the end, it might be that the right thing to do for git on kernel.org
is to have a single, unified object store which isn't accessible by
anything other than git-specific protocols. There would have to be some
way of dealing with, for example, conflicting tags that apply to
different repositories, though.
-hpa
^ permalink raw reply
* Re: "git-send-pack"
From: Linus Torvalds @ 2005-06-30 22:26 UTC (permalink / raw)
To: H. Peter Anvin; +Cc: Daniel Barkalow, Junio C Hamano, git
In-Reply-To: <42C46A3C.1070104@zytor.com>
On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
> For producing minimum network traffic, I think something like this would
> work:
In the "minimum traffic", the thing to look at is number of packets, and
penalize further for anything that requires a synchronous reply.
That's why I'd suggest just letting the client stream out the list of
objects it has - it may appear wasteful to stream out even a thousand
SHA1's, but hey, that's just 20kB worth of data, and especially if there
is no synchronous stuff, that's just 15 ethernet packets.
For the server side, looking up a thousand SHA's is pretty easy (it's
_really_ cheap if the server ends up using a few big packed objects: you
don't even have to look at the pack data itself, it can look at just the
index and say "yup, I've got it")
So I'd go for simple brute force over anything that needs to discuss
things and have a back-and-forth between server/client. And making the
client do the heavy lifting is the right thing to do (the server will have
to create the pack, which can be expensive, but you can tune the delta
window for how much CPU the server has)
Linus
^ permalink raw reply
* Re: "git-send-pack"
From: Daniel Barkalow @ 2005-06-30 22:25 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506301412470.14331@ppc970.osdl.org>
On Thu, 30 Jun 2005, Linus Torvalds wrote:
> On Thu, 30 Jun 2005, Daniel Barkalow wrote:
> >
> > I suspect that I'll be able to merge send-pack/receive-pack with
> > ssh-push/ssh-pull this evening, and then it'll have the feature of not
> > caring too much which side your command line is on.
>
> The simple thing to do is to just get one commit at a time, see if you
> have it already, parse if it not, and go on to the parents.
>
> That would fit the current git-pull thing, and may be good enough, but it
> has the downside that it can need a _lot_ of back-and-forth fecthing of
> commit objects from the other side until you find the one you want. That's
> going to be _very_ slow over a high-latency connection.
>
> So what I'd suggest is:
>
> 1- puller starts by just asking "what's your SHA1 for the ref I want"
>
> The puller wants to know this, because a common case may be that it
> already has it, in which case it doesn't need to do anything. But more
> importantly, the puller will need to know this anyway if it gets an
> object-pack, so that the puller can update it's FETCH_HEAD.
Already have this, for the non-pack case.
> - At some point the server sees the first SHA1 it recognizes, and at that
> point the server will have to start working. It will just send back an
> "ok, got it" message (telling the client to not bother continuing to
> send it any more commit ID's), and then does
>
> git-rev-list --objects ref-client-wants ^first-common-sha1 |
> git-pack-objects --stdout
Right.
> - the client just unpacks the objects, and if successful, it puts the new
> top ref it got into FETCH_HEAD. It's now done.
Or wherever it's been told to, yes.
> And I do _not_ think that it makes a lot of sense to try to be symmetric.
> For one thing, while a "git-send-pack" should update all the refs
> in-place, a "git-pull-pack" should _not_ update the ref, it should just
> set FETCH_HEAD instead and the puller can decide what he wants to do with
> that ref (possibly merge it, but possibly just make it be a new local
> branch "remote-branch").
My expectation is that the puller will have a ref "remote-branch", and
will therefore: (1) want to update it, and (2) know the last commit pulled
from it. In this situation, we can skip figuring out the start (the two
points I didn't quote), because we saved it from before.
At least, this is how I've always done it; I've got a "linus" branch that
follows the public repo, and I commit changes to a different branch. I
suppose one could skip hanging onto this info, but it seems like an
obviously useful thing to keep, if for no other reason than that I want to
diff against it. This is essentially promoting FETCH_HEAD to a refs/heads/
thing, and having separate ones when you pull from separate sources.
I suppose things are different if you do a lot of one-shot pulls, rather
than tracking branches that you pull from; I'll need to think about this
case (assuming that's actually what you do).
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-06-30 23:40 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Barkalow, Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506301514240.14331@ppc970.osdl.org>
Linus Torvalds wrote:
>
> On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
>>For producing minimum network traffic, I think something like this would
>>work:
>
> In the "minimum traffic", the thing to look at is number of packets, and
> penalize further for anything that requires a synchronous reply.
>
> That's why I'd suggest just letting the client stream out the list of
> objects it has - it may appear wasteful to stream out even a thousand
> SHA1's, but hey, that's just 20kB worth of data, and especially if there
> is no synchronous stuff, that's just 15 ethernet packets.
>
In your linux-2.6 tree, there are currently 54,204 objects, and that is
after less than one full 2.6.x kernel release cycle. That's a megabyte
of SHA1s.
In /pub/scm on kernel.org, there are currently 1,815,573 objects or hard
links to objects, which would take a 36.3 MB list to produce.
Although this is better than what rsync does, which is it encodes this
list into ASCII with pathnames and all and it ends up being closer to
200 MB, it isn't fundamentally different.
-hpa
^ permalink raw reply
* Re: "git-send-pack"
From: Linus Torvalds @ 2005-06-30 23:56 UTC (permalink / raw)
To: Daniel Barkalow; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.21.0506301731220.30848-100000@iabervon.org>
On Thu, 30 Jun 2005, Daniel Barkalow wrote:
>
> My expectation is that the puller will have a ref "remote-branch", and
> will therefore: (1) want to update it, and (2) know the last commit pulled
> from it. In this situation, we can skip figuring out the start (the two
> points I didn't quote), because we saved it from before.
This is _never_ how I do things, so I think that's a bad expectation. I
have other peoples trees "just show up", since they are actually based on
mine..
Linus
^ permalink raw reply
* Re: "git-send-pack"
From: Linus Torvalds @ 2005-07-01 0:02 UTC (permalink / raw)
To: H. Peter Anvin; +Cc: Daniel Barkalow, Junio C Hamano, git
In-Reply-To: <42C482ED.1010306@zytor.com>
On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
> In your linux-2.6 tree, there are currently 54,204 objects, and that is
> after less than one full 2.6.x kernel release cycle. That's a megabyte
> of SHA1s.
But that's _all_ objects. There are "only" 4040 commit objects (which are
always the starting point for a search).
So streaming out the commit objects a few hundred at a time is actually
a very simple strategy.
Also, note that the server is usually _more_ ahead than the client is, and
the server is the one that potentially has lots of commits that the
client doesn't have. Not the other way around. So if the client makes a
list of it's top commits, it almost certainly won't have to make a very
long list until the server can tell it "ok, stop, I've seen it".
Yeah, maybe we want to limit the "burst" to 70 sha1's, since that will fit
in a regular-sized ethernet packet, but whatever - you'd burst out your
commits "latest first", so you'd never even get to the current 4040 unless
you've literally done the kind of work we've done in the git tree for the
last 3 months _and_you've_not_pulled_from_that_server_in_the_whole_time_.
Linus
^ permalink raw reply
* [PATCH] Avoid unnecessarily inflating and interpreting delta
From: Junio C Hamano @ 2005-07-01 0:13 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This teaches packed_delta_info() that it only needs to look at
the type of the base object to figure out both type and size of
a deltified object. This saves quite a many calls to inflate()
when dealing with a deep delta chain.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
cat-file.c | 3 ++
sha1_file.c | 77 +++++++++++++++++++++++++++++++----------------------------
2 files changed, 43 insertions(+), 37 deletions(-)
f0792cd64bd42cde6706dc2c039e7b6901547169
diff --git a/cat-file.c b/cat-file.c
--- a/cat-file.c
+++ b/cat-file.c
@@ -16,7 +16,8 @@ int main(int argc, char **argv)
usage("git-cat-file [-t | -s | tagname] <sha1>");
if (!strcmp("-t", argv[1]) || !strcmp("-s", argv[1])) {
- if (!sha1_object_info(sha1, type, &size)) {
+ if (!sha1_object_info(sha1, type,
+ argv[1][1] == 's' ? &size : NULL)) {
switch (argv[1][1]) {
case 't':
printf("%s\n", type);
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -624,41 +624,49 @@ static int packed_delta_info(unsigned ch
char *type,
unsigned long *sizep)
{
- const unsigned char *data;
- unsigned char delta_head[64];
- unsigned long result_size, base_size, verify_base_size;
- z_stream stream;
- int st;
-
if (left < 20)
die("truncated pack file");
- if (sha1_object_info(base_sha1, type, &base_size))
- die("cannot get info for delta-pack base");
- memset(&stream, 0, sizeof(stream));
+ /* We choose to only get the type of the base object and
+ * ignore potentially corrupt pack file that expects the delta
+ * based on a base with a wrong size. This saves tons of
+ * inflate() calls.
+ */
- data = stream.next_in = base_sha1 + 20;
- stream.avail_in = left - 20;
- stream.next_out = delta_head;
- stream.avail_out = sizeof(delta_head);
+ if (sha1_object_info(base_sha1, type, NULL))
+ die("cannot get info for delta-pack base");
- inflateInit(&stream);
- st = inflate(&stream, Z_FINISH);
- inflateEnd(&stream);
- if ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head))
- die("delta data unpack-initial failed");
+ if (sizep) {
+ const unsigned char *data;
+ unsigned char delta_head[64];
+ unsigned long result_size;
+ z_stream stream;
+ int st;
+
+ memset(&stream, 0, sizeof(stream));
+
+ data = stream.next_in = base_sha1 + 20;
+ stream.avail_in = left - 20;
+ stream.next_out = delta_head;
+ stream.avail_out = sizeof(delta_head);
+
+ inflateInit(&stream);
+ st = inflate(&stream, Z_FINISH);
+ inflateEnd(&stream);
+ if ((st != Z_STREAM_END) &&
+ stream.total_out != sizeof(delta_head))
+ die("delta data unpack-initial failed");
- /* Examine the initial part of the delta to figure out
- * the result size. Verify the base size while we are at it.
- */
- data = delta_head;
- verify_base_size = get_delta_hdr_size(&data);
- if (verify_base_size != base_size)
- die("delta base size mismatch");
+ /* Examine the initial part of the delta to figure out
+ * the result size.
+ */
+ data = delta_head;
+ get_delta_hdr_size(&data); /* ignore base size */
- /* Read the result size */
- result_size = get_delta_hdr_size(&data);
- *sizep = result_size;
+ /* Read the result size */
+ result_size = get_delta_hdr_size(&data);
+ *sizep = result_size;
+ }
return 0;
}
@@ -726,7 +734,8 @@ static int packed_object_info(struct pac
default:
die("corrupted pack file");
}
- *sizep = size;
+ if (sizep)
+ *sizep = size;
unuse_packed_git(p);
return 0;
}
@@ -915,12 +924,7 @@ int sha1_object_info(const unsigned char
if (!find_pack_entry(sha1, &e))
return error("unable to find %s", sha1_to_hex(sha1));
- if (!packed_object_info(&e, type, sizep))
- return 0;
- /* sheesh */
- map = unpack_entry(&e, type, sizep);
- free(map);
- return (map == NULL) ? 0 : -1;
+ return packed_object_info(&e, type, sizep);
}
if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)
status = error("unable to unpack %s header",
@@ -929,7 +933,8 @@ int sha1_object_info(const unsigned char
status = error("unable to parse %s header", sha1_to_hex(sha1));
else {
status = 0;
- *sizep = size;
+ if (sizep)
+ *sizep = size;
}
inflateEnd(&stream);
munmap(map, mapsize);
------------
^ permalink raw reply
* [PATCH 1/2] verify-pack updates.
From: Junio C Hamano @ 2005-07-01 0:15 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
Nico pointed out that having verify_pack.c and verify-pack.c was
confusing. Rename verify_pack.c to pack-check.c as suggested,
and enhances the verification done quite a bit.
- Built-in sha1_file unpacking knows that a base object of a
deltified object _must_ be in the same pack, and takes
advantage of that fact.
- Earlier verify-pack command only checked the SHA1 sum for the
entire pack file and did not look into its contents. It now
checks everything idx file claims to have unpacks correctly.
- It now has a hook to give more detailed information for
objects contained in the pack under -v flag.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
*** I used "git format-patch -M20" to generate diff to show this
*** commit as a rename/copy patch. Let's see if git-apply can
*** still grok it ;-).
Makefile | 2 +-
cache.h | 9 ++++++++
fsck-cache.c | 2 +-
pack-check.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++--------
pack.h | 2 +-
sha1_file.c | 66 +++++++++++++++++++++++++++++++++++++------------------
verify-pack.c | 51 ++++++++++++++++++++++++++++++++++---------
7 files changed, 156 insertions(+), 44 deletions(-)
rename verify_pack.c => pack-check.c (25%)
cf43fb6e9fec205d4786a284e1656b3612c28a77
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -46,7 +46,7 @@ install: $(PROG) $(SCRIPTS)
LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \
tag.o date.o index.o diff-delta.o patch-delta.o entry.o \
- epoch.o refs.o csum-file.o verify_pack.o pkt-line.o
+ epoch.o refs.o csum-file.o pack-check.o pkt-line.o
LIB_FILE=libgit.a
LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h csum-file.h \
pack.h pkt-line.h
diff --git a/cache.h b/cache.h
--- a/cache.h
+++ b/cache.h
@@ -251,11 +251,20 @@ extern struct packed_git {
unsigned int pack_use_cnt;
char pack_name[0]; /* something like ".git/objects/pack/xxxxx.pack" */
} *packed_git;
+
+struct pack_entry {
+ unsigned int offset;
+ unsigned char sha1[20];
+ struct packed_git *p;
+};
+
extern void prepare_packed_git(void);
extern int use_packed_git(struct packed_git *);
extern void unuse_packed_git(struct packed_git *);
extern struct packed_git *add_packed_git(char *, int);
extern int num_packed_objects(const struct packed_git *p);
extern int nth_packed_object_sha1(const struct packed_git *, int, unsigned char*);
+extern int find_pack_entry_one(const unsigned char *, struct pack_entry *, struct packed_git *);
+extern void *unpack_entry_gently(struct pack_entry *, char *, unsigned long *);
#endif /* CACHE_H */
diff --git a/fsck-cache.c b/fsck-cache.c
--- a/fsck-cache.c
+++ b/fsck-cache.c
@@ -440,7 +440,7 @@ int main(int argc, char **argv)
prepare_packed_git();
for (p = packed_git; p; p = p->next)
/* verify gives error messages itself */
- verify_pack(p);
+ verify_pack(p, 0);
for (p = packed_git; p; p = p->next) {
int num = num_packed_objects(p);
diff --git a/verify_pack.c b/pack-check.c
similarity index 25%
rename from verify_pack.c
rename to pack-check.c
--- a/verify_pack.c
+++ b/pack-check.c
@@ -10,8 +10,9 @@ static int verify_packfile(struct packed
unsigned long pack_size = p->pack_size;
void *pack_base;
struct pack_header *hdr;
- int nr_objects;
+ int nr_objects, err, i;
+ /* Header consistency check */
hdr = p->pack_base;
if (hdr->hdr_signature != htonl(PACK_SIGNATURE))
return error("Packfile signature mismatch", p->pack_name);
@@ -34,11 +35,47 @@ static int verify_packfile(struct packed
if (memcmp(sha1, pack_base + pack_size - 20, 20))
return error("Packfile %s SHA1 mismatch with itself",
p->pack_name);
- return 0;
+
+ /* Make sure everything reachable from idx is valid. Since we
+ * have verified that nr_objects matches between idx and pack,
+ * we do not do scan-streaming check on the pack file.
+ */
+ for (i = err = 0; i < nr_objects; i++) {
+ unsigned char sha1[20];
+ struct pack_entry e;
+ void *data;
+ char type[20];
+ unsigned long size;
+
+ if (nth_packed_object_sha1(p, i, sha1))
+ die("internal error pack-check nth-packed-object");
+ if (!find_pack_entry_one(sha1, &e, p))
+ die("internal error pack-check find-pack-entry-one");
+ data = unpack_entry_gently(&e, type, &size);
+ if (!data) {
+ err = error("cannot unpack %s from %s",
+ sha1_to_hex(sha1), p->pack_name);
+ continue;
+ }
+ if (check_sha1_signature(sha1, data, size, type)) {
+ err = error("cannot packed %s from %s corrupt",
+ sha1_to_hex(sha1), p->pack_name);
+ free(data);
+ continue;
+ }
+ free(data);
+ }
+
+ return err;
}
-int verify_pack(struct packed_git *p)
+static void show_pack_info(struct packed_git *p)
+{
+ /* Next round */
+}
+
+int verify_pack(struct packed_git *p, int verbose)
{
unsigned long index_size = p->index_size;
void *index_base = p->index_base;
@@ -46,17 +83,30 @@ int verify_pack(struct packed_git *p)
unsigned char sha1[20];
int ret;
+ ret = 0;
/* Verify SHA1 sum of the index file */
SHA1_Init(&ctx);
SHA1_Update(&ctx, index_base, index_size - 20);
SHA1_Final(sha1, &ctx);
if (memcmp(sha1, index_base + index_size - 20, 20))
- return error("Packfile index for %s SHA1 mismatch",
- p->pack_name);
+ ret = error("Packfile index for %s SHA1 mismatch",
+ p->pack_name);
+
+ if (!ret) {
+ /* Verify pack file */
+ use_packed_git(p);
+ ret = verify_packfile(p);
+ unuse_packed_git(p);
+ }
+
+ if (verbose) {
+ if (ret)
+ printf("%s: bad\n", p->pack_name);
+ else {
+ show_pack_info(p);
+ printf("%s: ok\n", p->pack_name);
+ }
+ }
- /* Verify pack file */
- use_packed_git(p);
- ret = verify_packfile(p);
- unuse_packed_git(p);
return ret;
}
diff --git a/pack.h b/pack.h
--- a/pack.h
+++ b/pack.h
@@ -27,6 +27,6 @@ struct pack_header {
unsigned int hdr_entries;
};
-extern int verify_pack(struct packed_git *);
+extern int verify_pack(struct packed_git *, int);
#endif
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -272,12 +272,6 @@ static int pack_used_ctr;
static unsigned long pack_mapped;
struct packed_git *packed_git;
-struct pack_entry {
- unsigned int offset;
- unsigned char sha1[20];
- struct packed_git *p;
-};
-
static int check_packed_git_idx(const char *path, unsigned long *idx_size_,
void **idx_map_)
{
@@ -618,22 +612,34 @@ void * unpack_sha1_file(void *map, unsig
return unpack_sha1_rest(&stream, hdr, *size);
}
+/* forward declaration for a mutually recursive function */
+static int packed_object_info(struct pack_entry *entry,
+ char *type, unsigned long *sizep);
+
static int packed_delta_info(unsigned char *base_sha1,
unsigned long delta_size,
unsigned long left,
char *type,
- unsigned long *sizep)
+ unsigned long *sizep,
+ struct packed_git *p)
{
+ struct pack_entry base_ent;
+
if (left < 20)
die("truncated pack file");
+ /* The base entry _must_ be in the same pack */
+ if (!find_pack_entry_one(base_sha1, &base_ent, p))
+ die("failed to find delta-pack base object %s",
+ sha1_to_hex(base_sha1));
+
/* We choose to only get the type of the base object and
* ignore potentially corrupt pack file that expects the delta
* based on a base with a wrong size. This saves tons of
* inflate() calls.
*/
- if (sha1_object_info(base_sha1, type, NULL))
+ if (packed_object_info(&base_ent, type, NULL))
die("cannot get info for delta-pack base");
if (sizep) {
@@ -716,7 +722,7 @@ static int packed_object_info(struct pac
switch (kind) {
case OBJ_DELTA:
- retval = packed_delta_info(pack, size, left, type, sizep);
+ retval = packed_delta_info(pack, size, left, type, sizep, p);
unuse_packed_git(p);
return retval;
case OBJ_COMMIT:
@@ -747,8 +753,10 @@ static void *unpack_delta_entry(unsigned
unsigned long delta_size,
unsigned long left,
char *type,
- unsigned long *sizep)
+ unsigned long *sizep,
+ struct packed_git *p)
{
+ struct pack_entry base_ent;
void *data, *delta_data, *result, *base;
unsigned long data_size, result_size, base_size;
z_stream stream;
@@ -773,8 +781,11 @@ static void *unpack_delta_entry(unsigned
if ((st != Z_STREAM_END) || stream.total_out != delta_size)
die("delta data unpack failed");
- /* This may recursively unpack the base, which is what we want */
- base = read_sha1_file(base_sha1, type, &base_size);
+ /* The base entry _must_ be in the same pack */
+ if (!find_pack_entry_one(base_sha1, &base_ent, p))
+ die("failed to find delta-pack base object %s",
+ sha1_to_hex(base_sha1));
+ base = unpack_entry_gently(&base_ent, type, &base_size);
if (!base)
die("failed to read delta-pack base object %s",
sha1_to_hex(base_sha1));
@@ -820,21 +831,33 @@ static void *unpack_entry(struct pack_en
char *type, unsigned long *sizep)
{
struct packed_git *p = entry->p;
- unsigned long offset, size, left;
- unsigned char *pack;
- enum object_type kind;
void *retval;
if (use_packed_git(p))
die("cannot map packed file");
+ retval = unpack_entry_gently(entry, type, sizep);
+ unuse_packed_git(p);
+ if (!retval)
+ die("corrupted pack file");
+ return retval;
+}
+
+/* The caller is responsible for use_packed_git()/unuse_packed_git() pair */
+void *unpack_entry_gently(struct pack_entry *entry,
+ char *type, unsigned long *sizep)
+{
+ struct packed_git *p = entry->p;
+ unsigned long offset, size, left;
+ unsigned char *pack;
+ enum object_type kind;
+ void *retval;
offset = unpack_object_header(p, entry->offset, &kind, &size);
pack = p->pack_base + offset;
left = p->pack_size - offset;
switch (kind) {
case OBJ_DELTA:
- retval = unpack_delta_entry(pack, size, left, type, sizep);
- unuse_packed_git(p);
+ retval = unpack_delta_entry(pack, size, left, type, sizep, p);
return retval;
case OBJ_COMMIT:
strcpy(type, "commit");
@@ -849,11 +872,10 @@ static void *unpack_entry(struct pack_en
strcpy(type, "tag");
break;
default:
- die("corrupted pack file");
+ return NULL;
}
*sizep = size;
retval = unpack_non_delta_entry(pack, size, left);
- unuse_packed_git(p);
return retval;
}
@@ -873,8 +895,8 @@ int nth_packed_object_sha1(const struct
return 0;
}
-static int find_pack_entry_1(const unsigned char *sha1,
- struct pack_entry *e, struct packed_git *p)
+int find_pack_entry_one(const unsigned char *sha1,
+ struct pack_entry *e, struct packed_git *p)
{
int *level1_ofs = p->index_base;
int hi = ntohl(level1_ofs[*sha1]);
@@ -904,7 +926,7 @@ static int find_pack_entry(const unsigne
prepare_packed_git();
for (p = packed_git; p; p = p->next) {
- if (find_pack_entry_1(sha1, e, p))
+ if (find_pack_entry_one(sha1, e, p))
return 1;
}
return 0;
diff --git a/verify-pack.c b/verify-pack.c
--- a/verify-pack.c
+++ b/verify-pack.c
@@ -1,25 +1,56 @@
#include "cache.h"
#include "pack.h"
-static int verify_one_pack(char *arg)
+static int verify_one_pack(char *arg, int verbose)
{
- struct packed_git *g = add_packed_git(arg, strlen(arg));
- if (!g)
- return -1;
- return verify_pack(g);
+ int len = strlen(arg);
+ struct packed_git *g;
+
+ while (1) {
+ /* Should name foo.idx, but foo.pack may be named;
+ * convert it to foo.idx
+ */
+ if (!strcmp(arg + len - 5, ".pack")) {
+ strcpy(arg + len - 5, ".idx");
+ len--;
+ }
+ /* Should name foo.idx now */
+ if ((g = add_packed_git(arg, len)))
+ break;
+ /* No? did you name just foo? */
+ strcpy(arg + len, ".idx");
+ len += 4;
+ if ((g = add_packed_git(arg, len)))
+ break;
+ return error("packfile %s not found.", arg);
+ }
+ return verify_pack(g, verbose);
}
+static const char *verify_pack_usage = "git-verify-pack [-v] <pack>...";
+
int main(int ac, char **av)
{
int errs = 0;
+ int verbose = 0;
+ int no_more_options = 0;
while (1 < ac) {
char path[PATH_MAX];
- strcpy(path, av[1]);
- if (verify_one_pack(path))
- errs++;
- else
- printf("%s: OK\n", av[1]);
+
+ if (!no_more_options && av[1][0] == '-') {
+ if (!strcmp("-v", av[1]))
+ verbose = 1;
+ else if (!strcmp("--", av[1]))
+ no_more_options = 1;
+ else
+ usage(verify_pack_usage);
+ }
+ else {
+ strcpy(path, av[1]);
+ if (verify_one_pack(path, verbose))
+ errs++;
+ }
ac--; av++;
}
return !!errs;
------------
^ permalink raw reply
* [PATCH 2/2] Show more details of packfile with verify-pack -v.
From: Junio C Hamano @ 2005-07-01 0:17 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This implements show_pack_info() function used in verify-pack
command when -v flag is used to obtain something like
unpack-objects used to give when it was first written.
It shows the following for each non-deltified object found in
the pack:
SHA1 type size offset
For deltified objects, it shows this instead:
SHA1 type size offset depth base_sha1
In order to get the output in the order that appear in the pack
file for debugging purposes, you can do this:
$ git-verify-pack -v packfile | sort -n -k 4,4
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
cache.h | 1 +
pack-check.c | 33 ++++++++++++++++++++++++++++++++-
sha1_file.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 84 insertions(+), 1 deletions(-)
c45c7e2f7d1718a156cef21630940e6be0e75d18
diff --git a/cache.h b/cache.h
--- a/cache.h
+++ b/cache.h
@@ -266,5 +266,6 @@ extern int num_packed_objects(const stru
extern int nth_packed_object_sha1(const struct packed_git *, int, unsigned char*);
extern int find_pack_entry_one(const unsigned char *, struct pack_entry *, struct packed_git *);
extern void *unpack_entry_gently(struct pack_entry *, char *, unsigned long *);
+extern void packed_object_info_detail(struct pack_entry *, char *, unsigned long *, unsigned long *, int *, unsigned char *);
#endif /* CACHE_H */
diff --git a/pack-check.c b/pack-check.c
--- a/pack-check.c
+++ b/pack-check.c
@@ -72,7 +72,36 @@ static int verify_packfile(struct packed
static void show_pack_info(struct packed_git *p)
{
- /* Next round */
+ struct pack_header *hdr;
+ int nr_objects, i;
+
+ hdr = p->pack_base;
+ nr_objects = ntohl(hdr->hdr_entries);
+
+ for (i = 0; i < nr_objects; i++) {
+ unsigned char sha1[20], base_sha1[20];
+ struct pack_entry e;
+ char type[20];
+ unsigned long size;
+ unsigned long store_size;
+ int delta_chain_length;
+
+ if (nth_packed_object_sha1(p, i, sha1))
+ die("internal error pack-check nth-packed-object");
+ if (!find_pack_entry_one(sha1, &e, p))
+ die("internal error pack-check find-pack-entry-one");
+
+ packed_object_info_detail(&e, type, &size, &store_size,
+ &delta_chain_length,
+ base_sha1);
+ printf("%s ", sha1_to_hex(sha1));
+ if (!delta_chain_length)
+ printf("%-6s %lu %u\n", type, size, e.offset);
+ else
+ printf("%-6s %lu %u %d %s\n", type, size, e.offset,
+ delta_chain_length, sha1_to_hex(base_sha1));
+ }
+
}
int verify_pack(struct packed_git *p, int verbose)
@@ -103,7 +132,9 @@ int verify_pack(struct packed_git *p, in
if (ret)
printf("%s: bad\n", p->pack_name);
else {
+ use_packed_git(p);
show_pack_info(p);
+ unuse_packed_git(p);
printf("%s: ok\n", p->pack_name);
}
}
diff --git a/sha1_file.c b/sha1_file.c
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -704,6 +704,57 @@ static unsigned long unpack_object_heade
return offset;
}
+void packed_object_info_detail(struct pack_entry *e,
+ char *type,
+ unsigned long *size,
+ unsigned long *store_size,
+ int *delta_chain_length,
+ unsigned char *base_sha1)
+{
+ struct packed_git *p = e->p;
+ unsigned long offset, left;
+ unsigned char *pack;
+ enum object_type kind;
+
+ offset = unpack_object_header(p, e->offset, &kind, size);
+ pack = p->pack_base + offset;
+ left = p->pack_size - offset;
+ if (kind != OBJ_DELTA)
+ *delta_chain_length = 0;
+ else {
+ int chain_length = 0;
+ memcpy(base_sha1, pack, 20);
+ do {
+ struct pack_entry base_ent;
+ unsigned long junk;
+
+ find_pack_entry_one(pack, &base_ent, p);
+ offset = unpack_object_header(p, base_ent.offset,
+ &kind, &junk);
+ pack = p->pack_base + offset;
+ chain_length++;
+ } while (kind == OBJ_DELTA);
+ *delta_chain_length = chain_length;
+ }
+ switch (kind) {
+ case OBJ_COMMIT:
+ strcpy(type, "commit");
+ break;
+ case OBJ_TREE:
+ strcpy(type, "tree");
+ break;
+ case OBJ_BLOB:
+ strcpy(type, "blob");
+ break;
+ case OBJ_TAG:
+ strcpy(type, "tag");
+ break;
+ default:
+ die("corrupted pack file");
+ }
+ *store_size = 0; /* notyet */
+}
+
static int packed_object_info(struct pack_entry *entry,
char *type, unsigned long *sizep)
{
------------
^ permalink raw reply
* Re: "git-send-pack"
From: H. Peter Anvin @ 2005-07-01 1:24 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Daniel Barkalow, Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506301656570.14331@ppc970.osdl.org>
Linus Torvalds wrote:
>
> On Thu, 30 Jun 2005, H. Peter Anvin wrote:
>
>>In your linux-2.6 tree, there are currently 54,204 objects, and that is
>>after less than one full 2.6.x kernel release cycle. That's a megabyte
>>of SHA1s.
>
>
> But that's _all_ objects. There are "only" 4040 commit objects (which are
> always the starting point for a search).
>
Well, there are objects that reference commit objects (e.g. tag
objects), not the other way around, but your point is well taken.
> So streaming out the commit objects a few hundred at a time is actually
> a very simple strategy.
>
> Also, note that the server is usually _more_ ahead than the client is, and
> the server is the one that potentially has lots of commits that the
> client doesn't have. Not the other way around. So if the client makes a
> list of it's top commits, it almost certainly won't have to make a very
> long list until the server can tell it "ok, stop, I've seen it".
Well, what I proposed was pretty much that except to have the client
(receiver) start first.
I prefer calling it sender and receiver, because in the case of upload
and download you have different sides being the "server".
> Yeah, maybe we want to limit the "burst" to 70 sha1's, since that will fit
> in a regular-sized ethernet packet, but whatever - you'd burst out your
> commits "latest first", so you'd never even get to the current 4040 unless
> you've literally done the kind of work we've done in the git tree for the
> last 3 months _and_you've_not_pulled_from_that_server_in_the_whole_time_.
Well, in the common case (sender has a superset of receiver), what I
proposed would converge on the first iteration. I'm not even convinced
that the algorithm *ever* needs to iterate.
-hpa
^ permalink raw reply
* Re: verify_pack.c vs verify-pack.c
From: Jon Seymour @ 2005-07-01 2:01 UTC (permalink / raw)
To: Nicolas Pitre; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.63.0506301631480.1667@localhost.localdomain>
I think this is odd too..
Why not rename the one containing the main as:
verify-pack-main.c
jon.
^ permalink raw reply
* Re: "git-send-pack"
From: Daniel Barkalow @ 2005-07-01 5:01 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Junio C Hamano, git
In-Reply-To: <Pine.LNX.4.58.0506301655310.14331@ppc970.osdl.org>
On Thu, 30 Jun 2005, Linus Torvalds wrote:
> On Thu, 30 Jun 2005, Daniel Barkalow wrote:
> >
> > My expectation is that the puller will have a ref "remote-branch", and
> > will therefore: (1) want to update it, and (2) know the last commit pulled
> > from it. In this situation, we can skip figuring out the start (the two
> > points I didn't quote), because we saved it from before.
>
> This is _never_ how I do things, so I think that's a bad expectation. I
> have other peoples trees "just show up", since they are actually based on
> mine..
Okay, so my next task will be to support this case.
What I'm doing now is:
- if the source is using an old version, fall back on individual objects
- send one (or more) ids to exclude
- find out if the server recognized any of the ids
- if not, fall back on transferring individual objects (or we could try
another batch)
- request a pack for the given hash, excluding whatever we've said to
exclude
I've implemented this for the case of updating a head, and got it to
transfer a pack of 11 objects. It took 31s (including connecting) to
transfer the entire history of git (3973 objects) over a DSL-DSL link with
a 39ms ping time. I sent the same thing with the old method previously,
and it took ages (wasn't timing it, though).
It should be possible to notice that we're not updating a ref, send all
the refs you have instead, see if the source recognized any, try again
with the next 70 commits, check, and repeat. Does this match what you were
suggesting?
I can send you the messy version tomorrow if you want to hack on it or
test it, and I'll have a clean patch series over the weekend.
-Daniel
*This .sig left intentionally blank*
^ permalink raw reply
* [PATCH] pack-objects: emit base before delta.
From: Junio C Hamano @ 2005-07-01 5:58 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
This micro-optimizes the order of objects in a pack. By
emitting base objects before deltified ones, unpack-objects do
not keep items on delta_list.
I think it is prudent to keep the add_delta_to_list() logic in
unpack-objects, so this commit only changes the packing side.
Signed-off-by: Junio C Hamano <junkio@cox.net>
---
pack-objects.c | 8 +++++---
1 files changed, 5 insertions(+), 3 deletions(-)
9be15981d7038f1d9d0b105f45760987584e60a6
diff --git a/pack-objects.c b/pack-objects.c
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -114,11 +114,13 @@ static unsigned long write_one(struct sh
* if it is written already.
*/
return offset;
- e->offset = offset;
- offset += write_object(f, e);
- /* if we are delitified, write out its base object. */
+
+ /* if we are delitified, write out its base objects first */
if (e->delta)
offset = write_one(f, e->delta, offset);
+
+ e->offset = offset;
+ offset += write_object(f, e);
return offset;
}
------------
^ permalink raw reply
* Re: [PATCH] pack-objects: emit base before delta.
From: Junio C Hamano @ 2005-07-01 6:18 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <7vbr5nxe38.fsf@assigned-by-dhcp.cox.net>
>>>>> "JCH" == Junio C Hamano <junkio@cox.net> writes:
JCH> This micro-optimizes the order of objects in a pack. By
JCH> emitting base objects before deltified ones, unpack-objects do
JCH> not keep items on delta_list.
Oops; "does not have to keep items" is what I meant.
^ permalink raw reply
* [PATCH] Add a topological sort procedure to commit.c [rev 3]
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch introduces an in-place topological sort procedure to commit.c.
Given a list of commits, sort_in_topological_order() will perform an in-place
topological sort of that list.
The invariant that applies to the resulting list is:
a reachable from b => ord(b) < ord(a)
This invariant is weaker than the --merge-order invariant, but is cheaper
to calculate (assuming the list has been identified) and will serve any
purpose where only a minimal topological order guarantee is required.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Note: this patch currently has no observable consequences since nothing
in this patch calls it. A future patch will use this algorithm to provide
an O(n) bisection algorithm as a suggested replacement for the
existing O(n^2) bisection algorithm.
This patch is a complete replacement for earlier revisions of this patch.
[rev 2]
* incorporates Junio's questions/comments as commentary,
* adds object.util save/restore functionality so that no
assumption is made about the pre-existing state of object.util
upon entry to the procedure.
[rev 3]
* removed object.util save/restore
* added more documentation to header about pre-conditions
---
commit.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
commit.h | 13 ++++++++
2 files changed, 120 insertions(+), 0 deletions(-)
5213443ab584624c3ebcec9a6d2624615c934e5b
diff --git a/commit.c b/commit.c
--- a/commit.c
+++ b/commit.c
@@ -3,6 +3,22 @@
#include "commit.h"
#include "cache.h"
+struct sort_node
+{
+ /*
+ * the number of children of the associated commit
+ * that also occur in the list being sorted.
+ */
+ unsigned int indegree;
+
+ /*
+ * reference to original list item that we will re-use
+ * on output.
+ */
+ struct commit_list * list_item;
+
+};
+
const char *commit_type = "commit";
enum cmit_fmt get_commit_format(const char *arg)
@@ -346,3 +362,94 @@ int count_parents(struct commit * commit
return count;
}
+/*
+ * Performs an in-place topological sort on the list supplied.
+ */
+void sort_in_topological_order(struct commit_list ** list)
+{
+ struct commit_list * next = *list;
+ struct commit_list * work = NULL;
+ struct commit_list ** pptr = list;
+ struct sort_node * nodes;
+ struct sort_node * next_nodes;
+ int count = 0;
+
+ /* determine the size of the list */
+ while (next) {
+ next = next->next;
+ count++;
+ }
+ /* allocate an array to help sort the list */
+ nodes = xcalloc(count, sizeof(*nodes));
+ /* link the list to the array */
+ next_nodes = nodes;
+ next=*list;
+ while (next) {
+ next_nodes->list_item = next;
+ next->item->object.util = next_nodes;
+ next_nodes++;
+ next = next->next;
+ }
+ /* update the indegree */
+ next=*list;
+ while (next) {
+ struct commit_list * parents = next->item->parents;
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn)
+ pn->indegree++;
+ parents=parents->next;
+ }
+ next=next->next;
+ }
+ /*
+ * find the tips
+ *
+ * tips are nodes not reachable from any other node in the list
+ *
+ * the tips serve as a starting set for the work queue.
+ */
+ next=*list;
+ while (next) {
+ struct sort_node * node = (struct sort_node *)next->item->object.util;
+
+ if (node->indegree == 0) {
+ commit_list_insert(next->item, &work);
+ }
+ next=next->next;
+ }
+ /* process the list in topological order */
+ while (work) {
+ struct commit * work_item = pop_commit(&work);
+ struct sort_node * work_node = (struct sort_node *)work_item->object.util;
+ struct commit_list * parents = work_item->parents;
+
+ while (parents) {
+ struct commit * parent=parents->item;
+ struct sort_node * pn = (struct sort_node *)parent->object.util;
+
+ if (pn) {
+ /*
+ * parents are only enqueued for emission
+ * when all their children have been emitted thereby
+ * guaranteeing topological order.
+ */
+ pn->indegree--;
+ if (!pn->indegree)
+ commit_list_insert(parent, &work);
+ }
+ parents=parents->next;
+ }
+ /*
+ * work_item is a commit all of whose children
+ * have already been emitted. we can emit it now.
+ */
+ *pptr = work_node->list_item;
+ pptr = &(*pptr)->next;
+ *pptr = NULL;
+ work_item->object.util = NULL;
+ }
+ free(nodes);
+}
diff --git a/commit.h b/commit.h
--- a/commit.h
+++ b/commit.h
@@ -55,4 +55,17 @@ struct commit *pop_most_recent_commit(st
struct commit *pop_commit(struct commit_list **stack);
int count_parents(struct commit * commit);
+
+/*
+ * Performs an in-place topological sort of list supplied.
+ *
+ * Pre-conditions:
+ * all commits in input list and all parents of those
+ * commits must have object.util == NULL
+ *
+ * Post-conditions:
+ * invariant of resulting list is:
+ * a reachable from b => ord(b) < ord(a)
+ */
+void sort_in_topological_order(struct commit_list ** list);
#endif /* COMMIT_H */
------------
^ permalink raw reply
* [PATCH] Removes DEBUG code from rev-list.c and -DDEBUG from Makefile
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch removes DEBUG code and -DDEBUG flag from Makefile.
Signed-off-by: Jon Seymour <jon.seymour@gmail.com>
---
Makefile | 2 +-
rev-list.c | 30 ------------------------------
2 files changed, 1 insertions(+), 31 deletions(-)
be52c026e003b9774acc3d0f53ae5ed67d878b03
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@
# break unless your underlying filesystem supports those sub-second times
# (my ext3 doesn't).
COPTS=-O2
-CFLAGS=-DDEBUG -g $(COPTS) -Wall
+CFLAGS=-g $(COPTS) -Wall
prefix=$(HOME)
bin=$(prefix)/bin
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -44,10 +44,6 @@ static int merge_order = 0;
static int show_breaks = 0;
static int stop_traversal = 0;
static int bisect_by_cut_option = 0;
-#ifdef DEBUG
-static int debug = 0;
-static unsigned int complexity = 0;
-#endif
static void show_commit(struct commit *commit)
{
@@ -283,9 +279,6 @@ static int count_distance(struct commit_
static void clear_distance(struct commit_list *list)
{
-#ifdef DEBUG
- complexity++;
-#endif
while (list) {
struct commit *commit = list->item;
commit->object.flags &= ~COUNTED;
@@ -422,14 +415,6 @@ static inline struct bisect_by_cut_node
return (struct bisect_by_cut_node *)commit->object.util;
}
-#ifdef DEBUG
-static void print_bisect_by_cut_node(struct commit * commit, const char * prefix)
-{
- struct bisect_by_cut_node * node = get_bisect_by_cut_node(commit);
- fprintf(stderr, "%s%s %u %d\n", prefix, sha1_to_hex(commit->object.sha1), node->flags, node->count);
-}
-#endif
-
/*
* Find the best bisection point by cutting a topological order in two then
* identifying a set of boundary nodes with a reachability known to be
@@ -558,11 +543,6 @@ struct commit * bisect_by_cut(struct com
best = work_item;
fittest = fitness;
}
-#ifdef DEBUG
- if (debug) {
- print_bisect_by_cut_node(work_item, "work ");
- }
-#endif
if (goal_test < goal) {
while (children) {
struct bisect_by_cut_node * cn
@@ -666,12 +646,6 @@ int main(int argc, char **argv)
show_breaks = 1;
continue;
}
-#ifdef DEBUG
- if (!strcmp(arg, "--debug")) {
- debug = 1;
- continue;
- }
-#endif
flags = 0;
if (*arg == '^') {
flags = UNINTERESTING;
@@ -700,9 +674,5 @@ int main(int argc, char **argv)
die("merge order sort failed\n");
}
}
-#ifdef DEBUG
- if (debug)
- fprintf(stderr, "complexity=%d\n", complexity);
-#endif
return 0;
}
------------
^ permalink raw reply
* [PATCH] Make O(n) algorithm the default implementation of --bisect
From: Jon Seymour @ 2005-07-01 6:31 UTC (permalink / raw)
To: git; +Cc: torvalds, jon.seymour
This patch makes the O(n) the default implementation of the git-rev-list
--bisect switch.
The original O(n^2) algorithm is still available as --bisect-orig.
It is left around to provide a quick and simple way to verify the
accuracy of the O(n) algorithm.
A subsequent patch is supplied to remove support for --bisect-orig
completely.
Signed-off: Jon Seymour <jon.seymour@gmail.com>
---
Linus: you may choose to defer application of this patch if you are
not confident that the O(n) algorithm is good.
---
rev-list.c | 5 +++--
1 files changed, 3 insertions(+), 2 deletions(-)
342b91442a303b222f1601ef34ef37fffe5a9d57
diff --git a/rev-list.c b/rev-list.c
--- a/rev-list.c
+++ b/rev-list.c
@@ -16,6 +16,7 @@ static const char rev_list_usage[] =
" --min-age=epoch\n"
" --header\n"
" --pretty\n"
+ " --bisect\n"
" --merge-order [ --show-breaks ]";
static int bisect_list = 0;
@@ -365,11 +366,11 @@ int main(int argc, char **argv)
show_parents = 1;
continue;
}
- if (!strcmp(arg, "--bisect-by-cut")) {
+ if (!strcmp(arg, "--bisect")) {
bisect_by_cut_option = 1;
continue;
}
- if (!strcmp(arg, "--bisect")) {
+ if (!strcmp(arg, "--bisect-orig")) {
bisect_list = 1;
continue;
}
------------
^ 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