* [PATCH] Some documentation...
From: David Greaves @ 2005-04-20 17:08 UTC (permalink / raw)
To: Linus Torvalds, git
[-- Attachment #1: Type: text/plain, Size: 587 bytes --]
Hi
I'm starting to write some docs...
Comments... even "yep, looks OK, carry on" :)
I plan on putting the 'git command' ones into the 'git help ...'
structure once Petr accepts it.
I guess the low level ones go into a README.reference until they
stabilise and become man pages...
In doing this I noticed a couple of points:
* update-cache won't accept ./file or fred/./file
* checkout-cache doesn't seem to preserve mode
Are these bugs or should they be documented?
I've taken the approach of documenting behaviour for now.
Signed-off-by: David Greaves <david@dgreaves.com>
---
[-- Attachment #2: README.reference.patch --]
[-- Type: text/x-patch, Size: 4597 bytes --]
Index: README.reference
===================================================================
--- /dev/null (tree:cf6a46a2199777c3dac32fa4479b97c0752cdf07)
+++ 30de093673d44c7ea8c56a0194fb792e47225ac8/README.reference (mode:100644 sha1:2ec6683b22e5672ea46d27770fcb1a4b4c37aa0e)
@@ -0,0 +1,158 @@
+Terminology: - see README for description
+Each line contains terms used interchangeably
+
+object database, .git directory
+directory cache, index
+id, sha1, sha1-id, sha1 hash
+type, tag, tagname
+blob, blob object
+tree, tree object
+commit, commit object
+parent
+root object
+changeset
+
+################################################################
+cat-file
+ cat-file <-t | tagname> <sha1>
+
+Provide contents or type of objects in the repository. The tagname is
+required if it is not being interrogated.
+
+
+<sha1>
+ The sha1 identifier of the object.
+ (This is the sha1 of the uncompressed content.)
+
+-t
+ show the object type identified by <sha1>
+ One of: blob/tree/commit
+
+<tagname>
+ One of: blob/tree/commit
+
+
+################################################################
+check-files
+ check-files <file>...
+
+Check that a list of files are up-to-date between the filesystem and
+the cache. Used to verify a patch target before doing a patch.
+
+Files that do not exist on the filesystem are considered up-to-date
+(whether or not they are in the cache).
+
+Emits an error message on failure.
+
+exits with a status code indicating success if all files are
+up-to-date.
+
+
+see also: update-cache
+
+
+################################################################
+checkout-cache
+ checkout-cache [-q] [-a] [-f] [--] <file>...
+
+Will copy all files listed from the cache to the working directory
+(not overwriting existing files). Note that the file contents are
+restored - NOT the file permissions.
+
+-q
+ be quiet if files exist or are not in the cache
+
+-f
+ forces overwrite of existing files
+
+-a
+ checks out all files in the cache before processing listed
+ files.
+
+Note that the order of the flags matters:
+
+ checkout-cache -a -f file.c
+
+will first check out all files listed in the cache (but not overwrite
+any old ones), and then force-checkout file.c a second time (ie that
+one _will_ overwrite any old contents with the same filename).
+
+Also, just doing "checkout-cache" does nothing. You probably meant
+"checkout-cache -a". And if you want to force it, you want
+"checkout-cache -f -a".
+
+Intuitiveness is not the goal here. Repeatability is. The reason for
+the "no arguments means no work" thing is that from scripts you are
+supposed to be able to do things like
+
+ find . -name '*.h' -print0 | xargs -0 checkout-cache -f --
+
+which will force all existing *.h files to be replaced with their
+cached copies. If an empty command line implied "all", then this would
+force-refresh everything in the cache, which was not the point.
+
+Oh, and the "--" is just a good idea when you know the rest will be
+filenames. Just so that you wouldn't have a filename of "-a" causing
+problems (not possible in the above example, but get used to it in
+scripting!).
+
+
+################################################################
+commit-id
+ commit-id [tag]
+
+Returns the sha1-id of the commit object associated with given tag.
+
+tag
+ tag of commit object - defaults to the current HEAD.
+
+
+################################################################
+commit-tree
+ commit-tree <sha1> [-p <sha1>]* < changelog
+
+
+################################################################
+diff-tree
+ diff-tree [-r] [-z] <tree sha1> <tree sha1>
+
+
+################################################################
+ls-tree
+ ls-tree [-r] [-z] <key>
+
+
+################################################################
+merge-base
+ merge-base <commit-id> <commit-id>
+
+
+################################################################
+merge-cache
+ merge-cache <merge-program> (-a | <filename>*)
+
+
+################################################################
+read-tree
+ read-tree [-m] <sha1>
+
+
+################################################################
+rev-tree
+ rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]
+
+
+################################################################
+show-diff
+ show-diff [-q] [-s] [-z] [paths...]
+
+
+################################################################
+show-files
+ show-files [-z] [-t] (--[cached|deleted|others|ignored|stage])*
+
+
+################################################################
+unpack-file
+ unpack-file.c <sha1>
+
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 17:06 UTC (permalink / raw)
To: Chris Mason; +Cc: git
In-Reply-To: <200504201237.38374.mason@suse.com>
On Wed, 20 Apr 2005, Chris Mason wrote:
>
> At any rate, the time for a single write-tree is pretty consistent. Before it
> was around .5 seconds, and with this change it goes down to .128s.
Oh, wow.
I bet your SHA1 implementation is done with hand-optimized and scheduled
x86 MMX code or something, while my poor G5 is probably using some slow
generic routine. As a result, it only improved by 33% for me since the
compression was just part of the picture, but with your cheap SHA1 the
compression costs really dominated, and so it's almost four times faster
for you.
Anyway, that's good. It definitely means that I consider tree writing to
be "fast enough". You can commit patches in a third of a second on your
machine.
I'll consider the problem solved for now. Yeah, I realize that it still
takes you half a minute to commit the 100 quilt patches, but I just can't
bring myself to think it's a huge problem in the kind of usage patterns I
think are realistic.
If somebody really wants to replace quilt with git, he'd need to spend
some effort on it. If you just want to work together reasonably well, I
think 3 patches per second is pretty much there.
Linus
^ permalink raw reply
* Re: [GIT PATCH] I2C and W1 bugfixes for 2.6.12-rc2
From: Zlatko Calusic @ 2005-04-20 16:56 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0504191525290.2274@ppc970.osdl.org>
Linus Torvalds <torvalds@osdl.org> writes:
> Real merges have no patches taking place _anywhere_. And they take about
> half a second. Doing an "update" of your tree should _literally_ boil down
> to
>
> #
> # "repo" needs to point to the repo we update from
> #
> rsync -avz --ignore-existing $repo/objects/. .git/objects/.
I see this -avz incantation mentioned everytime when rsync is
involved. But, is the -z part (compression) really necessary knowing
that we're dealing with an already compressed tree? Doesn't it put
additional strain on the rsync server without any benefit in this
case?
Or I might be too ignorant and not understand some internals well, but
then... I would like to know the reason. :)
Regards,
--
Zlatko
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 16:41 UTC (permalink / raw)
To: Chris Mason; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504200931020.6467@ppc970.osdl.org>
On Wed, 20 Apr 2005, Linus Torvalds wrote:
>
> NO! Don't see if this works. For the "sha1 file already exists" file, it
> forgot to return the SHA1 value in "returnsha1", and would thus corrupt
> the trees it wrote.
Proper version with fixes checked in. For me, it brings down the time to
write a kernel tree from 0.34s to 0.24s, so a third of the time was just
compressing objects that we ended up already having.
Two thirds to go ;)
Linus
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Chris Mason @ 2005-04-20 16:37 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 1059 bytes --]
On Wednesday 20 April 2005 11:40, Linus Torvalds wrote:
> On Wed, 20 Apr 2005, Chris Mason wrote:
> > Thanks for looking at this. Your new tree is faster, it gets the commit
> > 100 patches time down from 1m5s to 50s.
>
> It really _shouldn't_ be faster. It still does the compression, and throws
> the end result away.
Well, that's a little odd. I had thought about making sure you did this
change and forgotten. 1 minute benchmarks are a horrible idea since they run
into noise with cache writebacks. I should know better...
At any rate, the time for a single write-tree is pretty consistent. Before it
was around .5 seconds, and with this change it goes down to .128s. My patch
was .024.
The 100 patch time is down to 32s (3 run average). This is close enough that
I don't think my patch is worth it if no other part of git can benefit from
having trees in the index.
>
> To actually go faster, it _should_ need this patch. Untested. See if it
> works..
Thanks. This one missed the filling in the returnsha1. New patch attached.
-chris
[-- Attachment #2: file-check.diff --]
[-- Type: text/x-diff, Size: 1059 bytes --]
diff -u linus.back/sha1_file.c linus/sha1_file.c
--- linus.back/sha1_file.c 2005-04-20 12:31:00.240181016 -0400
+++ linus/sha1_file.c 2005-04-20 12:13:56.339837528 -0400
@@ -173,12 +173,27 @@
z_stream stream;
unsigned char sha1[20];
SHA_CTX c;
+ char *filename;
+ int fd;
/* Sha1.. */
SHA1_Init(&c);
SHA1_Update(&c, buf, len);
SHA1_Final(sha1, &c);
+ filename = sha1_file_name(sha1);
+ fd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);
+ if (fd < 0) {
+ if (errno != EEXIST)
+ return -1;
+
+ /*
+ * We might do collision checking here, but we'd need to
+ * uncompress the old file and check it. Later.
+ */
+ goto out;
+ }
+
/* Set it up */
memset(&stream, 0, sizeof(stream));
deflateInit(&stream, Z_BEST_COMPRESSION);
@@ -195,8 +210,10 @@
deflateEnd(&stream);
size = stream.total_out;
- if (write_sha1_buffer(sha1, compressed, size) < 0)
- return -1;
+ if (write(fd, compressed, size) != size)
+ die("unable to write file");
+ close(fd);
+out:
if (returnsha1)
memcpy(returnsha1, sha1, 20);
return 0;
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: Martin Uecker @ 2005-04-20 16:33 UTC (permalink / raw)
To: Git Mailing List; +Cc: Martin Uecker
In-Reply-To: <20050420155734.GA13575@macavity>
[-- Attachment #1: Type: text/plain, Size: 1002 bytes --]
On Wed, Apr 20, 2005 at 05:57:34PM +0200, Martin Uecker wrote:
> On Wed, Apr 20, 2005 at 11:28:20AM -0400, C. Scott Ananian wrote:
>
> > Yes, I guess this is the detail I was going to abandon. =)
> >
> > I viewed the fact that the top-level hash was dependent on the exact chunk
> > makeup a 'misfeature', because it doesn't allow easy interoperability with
> > existing non-chunked repos.
>
> I thought this as a misfeature too before I realized how
> many advantages this has.
To make it more clear: Ofcourse it is a bug if the
hash depends on unimportant implementation details.
But a hash which is calculated recusively from
subhashes is a lot more usefull than a hash
which can only be calculated from the entire data
at once. And if this hash can be recalculated
cheaply from subhashes even if some data was
inserted somewhere this is an even more usefull
thing.
Martin
--
One night, when little Giana from Milano was fast asleep,
she had a strange dream.
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 16:33 UTC (permalink / raw)
To: Chris Mason; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org>
On Wed, 20 Apr 2005, Linus Torvalds wrote:
>
> To actually go faster, it _should_ need this patch. Untested. See if it
> works..
NO! Don't see if this works. For the "sha1 file already exists" file, it
forgot to return the SHA1 value in "returnsha1", and would thus corrupt
the trees it wrote.
So don't apply, don't test. You won't corrupt your archive (you'll just
write bogus tree objects), but if you commit the bogus trees you're going
to be in a world of hurt and will have to undo everything you did.
It's a good test for "fsck" though. It core-dumps because it tries to add
references to NULL objects.
Linus
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 16:21 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: git
In-Reply-To: <Pine.LNX.4.61.0504201147280.2630@cag.csail.mit.edu>
On Wed, 20 Apr 2005, C. Scott Ananian wrote:
>
> OK, sure. But how 'bout chunking trees? Are you grown happy with the new
> trees-reference-other-trees paradigm, or is there a deep longing in your
> heart for the simplicity of 'trees-reference-blobs-period'?
I'm pretty sure we do better chunking on a subdirectory basis, especially
as it allows us to do various optimizations (avoid diffing common parts).
Yes, you could try to do the same optimizations with chunking, but then
you'd need to make sure that the chunking was always on a full tree entry
boundary etc - ie much harder than blob chunking.
But hey, numbers talk, bullshit walks.
Linus
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: David Willmore @ 2005-04-20 16:10 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Chris Mason, git
In-Reply-To: <Pine.LNX.4.58.0504200833580.6467@ppc970.osdl.org>
On 4/20/05, Linus Torvalds <torvalds@osdl.org> wrote:
> It really _shouldn't_ be faster. It still does the compression, and throws
> the end result away.
Am I misunderstanding or is the proglem that doing:
<file with unknown status> -> compress -> sha1 -> compare with existing hash
is expensive?
What about doing:
<file it's supposed to be equal to> -> uncompress -> compare with
unknown status file
It's more file I/O, but the uncompress is much cheaper than the compress.
On a second issue, what's the format of the main 'index' file? Is it:
<pathspec> <sha1hash>
<pathspec> <sha1hash>
?
If so, that's not going to compress well. A file like:
<pathspec1>
<pathspec2>
<sha1hash1>
<sha1hash2>
Will compress better.
Stop me if I'm way off base--I'm just following the mailing list, I
haven't tried out the code.
Cheers,
David
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: Martin Uecker @ 2005-04-20 15:57 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <Pine.LNX.4.61.0504201121490.2630@cag.csail.mit.edu>
[-- Attachment #1: Type: text/plain, Size: 2419 bytes --]
On Wed, Apr 20, 2005 at 11:28:20AM -0400, C. Scott Ananian wrote:
Hi,
> A merkle-tree (which I think you initially pointed me at) makes the hash
> of the internal nodes be a hash of the chunk's hashes; ie not a straight
> content hash. This is roughly what my current implementation does, but
> I would like to identify each subtree with the hash of the
> *(expanded) contents of that subtree* (ie no explicit reference to
> subtree hashes). This makes it interoperable with non-chunked or
> differently-chunked representations, in that the top-level hash is *just
> the hash of the complete content*, not some hash-of-subtree-hashes. Does
> that make more sense?
Yes, thank you. But I would like to argue against this:
You can make the representations interoperable
if you calculate the hash for the non-chunked
representations exactly as if this file is stored
chunked but simple do not store it in that way.
Of course this is not backward compatible to the
monolithic hash and not compatible with a differently
chunked representation (but you could store subtrees
unchunked if you think your chunks are too small).
> The code I posted doesn't demonstrate this very well, but now that Linus
> has abandoned the 'hash of compressed content' stuff, my next code posting
> should show this more clearly.
I think the hash of the treap piece should be calculated
from the hash of the prefix and suffix tree and the already
calculated hash of the uncompressed data. This makes hashing
nearly as cheap as in Linus version which is important
because checking whether a given file has identically
content as a stored version should be fast.
> >If I don't miss anything essential, you can validate
> >each treap piece at the moment you get it from the
> >network with its SHA1 hash and then proceed with
> >downloading the prefix and suffix tree (in parallel
> >if you have more than one peer a la bittorrent).
>
> Yes, I guess this is the detail I was going to abandon. =)
>
> I viewed the fact that the top-level hash was dependent on the exact chunk
> makeup a 'misfeature', because it doesn't allow easy interoperability with
> existing non-chunked repos.
I thought this as a misfeature too before I realized how
many advantages this has.
Martin
--
One night, when little Giana from Milano was fast asleep,
she had a strange dream.
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: enforcing DB immutability
From: Erik Mouw @ 2005-04-20 15:57 UTC (permalink / raw)
To: linux; +Cc: git, linux-kernel, mingo
In-Reply-To: <20050420084115.2699.qmail@science.horizon.com>
On Wed, Apr 20, 2005 at 08:41:15AM -0000, linux@horizon.com wrote:
> [A discussion on the git list about how to provide a hardlinked file
> that *cannot* me modified by an editor, but must be replaced by
> a new copy.]
Some time ago there was somebody working on copy-on-write links: once
you modify a cow-linked file, the file contents are copied, the file is
unlinked and you can safely work on the new file. It has some horrible
semantics in that the inode number of the opened file changes, I don't
know if applications are or should be aware of that.
Erik
--
+-- Erik Mouw -- www.harddisk-recovery.com -- +31 70 370 12 90 --
| Lab address: Delftechpark 26, 2628 XH, Delft, The Netherlands
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: C. Scott Ananian @ 2005-04-20 15:52 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504200840240.6467@ppc970.osdl.org>
On Wed, 20 Apr 2005, Linus Torvalds wrote:
>> I was considering using a chunked representation for *all* files (not just
>> blobs), which would avoid the original 'trees must reference other trees
>> or they become too large' issue -- and maybe the performance issue you're
>> referring to, as well?
> No. The most common index file operation is reading, and that's the one
> that has to be _fast_. And it is - it's a single "mmap" and some parsing.
OK, sure. But how 'bout chunking trees? Are you grown happy with the new
trees-reference-other-trees paradigm, or is there a deep longing in your
heart for the simplicity of 'trees-reference-blobs-period'? I'm fairly
certain that chunking could get you the space-savings you need without
multi-level trees, if the simplicity of that is still appealing.
Not necessarily for rev.1 of the chunking code, but I'm curious as to
whether it's still of interest at all. I don't know exactly how far
ingrained multilevel trees have become since they were adopted.
--scott
Japan explosion BLUEBIRD Honduras jihad D5 SLBM Diplomat overthrow
JMTIDE CABOUNCE AMTHUG ESODIC Kennedy AVBRANDY CLOWER mail drop PHOENIX
( http://cscott.net/ )
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 15:46 UTC (permalink / raw)
To: C. Scott Ananian; +Cc: Chris Mason, git
In-Reply-To: <Pine.LNX.4.61.0504201128550.2630@cag.csail.mit.edu>
On Wed, 20 Apr 2005, C. Scott Ananian wrote:
>
> Hmm. Are our index files too large, or is there some other factor?
They _are_ pretty large, but they have to be,
For the kernel, the index file is about 1.6MB. That's
- 17,000+ files and filenames
- stat information for all of them
- the sha1 for them all
ie for the kernel it averages to 93.5 bytes per file. Which is actually
pretty dense (just the sha1 and stat information is about half of it, and
those are required).
> I was considering using a chunked representation for *all* files (not just
> blobs), which would avoid the original 'trees must reference other trees
> or they become too large' issue -- and maybe the performance issue you're
> referring to, as well?
No. The most common index file operation is reading, and that's the one
that has to be _fast_. And it is - it's a single "mmap" and some parsing.
In fact, writing it is pretty fast too, exactly because the index file is
totally linear and isn't compressed or anything fancy like that. It's a
_lot_ faster than the "tree objects", exactly because it doesn't need to
be as careful.
The main cost of the index file is probably the fact that I add a sha1
signature of the file into itself to verify that it's ok. The advantage is
that the signature means that the file is ok, and the parsing of it can be
much more relaxed. You win some, you lose some.
Linus
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Linus Torvalds @ 2005-04-20 15:40 UTC (permalink / raw)
To: Chris Mason; +Cc: git
In-Reply-To: <200504201122.35448.mason@suse.com>
On Wed, 20 Apr 2005, Chris Mason wrote:
>
> Thanks for looking at this. Your new tree is faster, it gets the commit 100
> patches time down from 1m5s to 50s.
It really _shouldn't_ be faster. It still does the compression, and throws
the end result away.
To actually go faster, it _should_ need this patch. Untested. See if it
works..
Linus
---
sha1_file.c: 40c00b77d0e52b31dda1696f10026fe6f92bc082
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -173,12 +173,27 @@ int write_sha1_file(char *buf, unsigned
z_stream stream;
unsigned char sha1[20];
SHA_CTX c;
+ char *filename;
+ int fd;
/* Sha1.. */
SHA1_Init(&c);
SHA1_Update(&c, buf, len);
SHA1_Final(sha1, &c);
+ filename = sha1_file_name(sha1);
+ fd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);
+ if (fd < 0) {
+ if (errno != EEXIST)
+ return -1;
+
+ /*
+ * We might do collision checking here, but we'd need to
+ * uncompress the old file and check it. Later.
+ */
+ return 0;
+ }
+
/* Set it up */
memset(&stream, 0, sizeof(stream));
deflateInit(&stream, Z_BEST_COMPRESSION);
@@ -195,8 +210,10 @@ int write_sha1_file(char *buf, unsigned
deflateEnd(&stream);
size = stream.total_out;
- if (write_sha1_buffer(sha1, compressed, size) < 0)
- return -1;
+ if (write(fd, compressed, size) != size)
+ die("unable to write file");
+ close(fd);
+
if (returnsha1)
memcpy(returnsha1, sha1, 20);
return 0;
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: C. Scott Ananian @ 2005-04-20 15:30 UTC (permalink / raw)
To: Chris Mason; +Cc: Linus Torvalds, git
In-Reply-To: <200504201122.35448.mason@suse.com>
On Wed, 20 Apr 2005, Chris Mason wrote:
> With the basic changes I described before, the 100 patch time only goes down
> to 40s. Certainly not fast enough to justify the changes. In this case, the
> bulk of the extra time comes from write-tree writing the index file, so I
> split write-tree.c up into libwrite-tree.c, and created update-cache
> --write-tree.
Hmm. Are our index files too large, or is there some other factor?
I was considering using a chunked representation for *all* files (not just
blobs), which would avoid the original 'trees must reference other trees
or they become too large' issue -- and maybe the performance issue you're
referring to, as well?
--scott
Boston MI6 quiche LPMEDLEY BLUEBIRD PBSUCCESS jihad biowarfare non-violent protest
Yakima NRA EZLN DES hack SARANAC KMPLEBE Echelon PBCABOOSE security
( http://cscott.net/ )
^ permalink raw reply
* Re: [PATCH 1/4] Accept commit in some places when tree is needed.
From: Linus Torvalds @ 2005-04-20 15:32 UTC (permalink / raw)
To: Junio C Hamano; +Cc: git
In-Reply-To: <7vis2ikmj0.fsf@assigned-by-dhcp.cox.net>
On Tue, 19 Apr 2005, Junio C Hamano wrote:
>
> This patch lifts the tree-from-tree-or-commit logic from
> diff-cache.c and moves it to sha1_file.c, which is a common
> library source for the SHA1 storage part.
I don't think that's a good interface. It changes the sha1 passed into it:
that may actually be nice, since you may want to know what it changed to,
but I think you'd want to have that as an (optional) separate
"sha1_result" parameter.
Also, the "type" or "size" things make no sense to have as a parameter
at all.
IOW, it was fine when it was an internal hacky thing in diff-cache, but
once it's promoted to be a real library function it should definitely be
cleaned up to have sane interfaces that make sense in general, and not
just within the original context.
Linus
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: C. Scott Ananian @ 2005-04-20 15:28 UTC (permalink / raw)
To: Martin Uecker; +Cc: Git Mailing List
In-Reply-To: <20050420151902.GA13175@macavity>
On Wed, 20 Apr 2005, Martin Uecker wrote:
>> You can (and my code demonstrates/will demonstrate) still use a whole-file
>> hash to use chunking. With content prefixes, this takes O(N ln M) time
>> (where N is the file size and M is the number of chunks) to compute all
>> hashes; if subtrees can share the same prefix, then you can do this in
>> O(N) time (ie, as fast as possible, modulo a constant factor, which is
>> '2'). You don't *need* internal hashing functions.
>
> I don't understand this paragraph. What is an internal
> hash function? Your code seems to do exactly what I want.
> The hashes are computed recusively as in a hash tree
> with O(N ln N). The only difference between your design
> and a design based on a conventional (binary) hash tree
> seems to be that data is stored in the intermediate nodes
> too.
A merkle-tree (which I think you initially pointed me at) makes the hash
of the internal nodes be a hash of the chunk's hashes; ie not a straight
content hash. This is roughly what my current implementation does, but
I would like to identify each subtree with the hash of the
*(expanded) contents of that subtree* (ie no explicit reference to
subtree hashes). This makes it interoperable with non-chunked or
differently-chunked representations, in that the top-level hash is *just
the hash of the complete content*, not some hash-of-subtree-hashes. Does
that make more sense?
The code I posted doesn't demonstrate this very well, but now that Linus
has abandoned the 'hash of compressed content' stuff, my next code posting
should show this more clearly.
> If I don't miss anything essential, you can validate
> each treap piece at the moment you get it from the
> network with its SHA1 hash and then proceed with
> downloading the prefix and suffix tree (in parallel
> if you have more than one peer a la bittorrent).
Yes, I guess this is the detail I was going to abandon. =)
I viewed the fact that the top-level hash was dependent on the exact chunk
makeup a 'misfeature', because it doesn't allow easy interoperability with
existing non-chunked repos.
--scott
WTO atomic operation Mossad Castro overthrow FSF fissionable HTAUTOMAT
LCPANES MKDELTA Bush non-violent protest OVER THE HORIZON RADAR KUPALM
( http://cscott.net/ )
^ permalink raw reply
* Re: [PATCH] write-tree performance problems
From: Chris Mason @ 2005-04-20 15:22 UTC (permalink / raw)
To: Linus Torvalds; +Cc: git
In-Reply-To: <Pine.LNX.4.58.0504192337120.6467@ppc970.osdl.org>
[-- Attachment #1: Type: text/plain, Size: 1279 bytes --]
On Wednesday 20 April 2005 02:43, Linus Torvalds wrote:
> On Tue, 19 Apr 2005, Chris Mason wrote:
> > I'll finish off the patch once you ok the basics below. My current code
> > works like this:
>
> Chris, before you do anything further, let me re-consider.
>
> Assuming that the real cost of write-tree is the compression (and I think
> it is), I really suspect that this ends up being the death-knell to my
> "use the sha1 of the _compressed_ object" approach.
Thanks for looking at this. Your new tree is faster, it gets the commit 100
patches time down from 1m5s to 50s. I've attached my patch from last night,
which is mostly a rough guess of the changes we would need, I haven't
validated or cleaned things up.
With the basic changes I described before, the 100 patch time only goes down
to 40s. Certainly not fast enough to justify the changes. In this case, the
bulk of the extra time comes from write-tree writing the index file, so I
split write-tree.c up into libwrite-tree.c, and created update-cache
--write-tree.
This gets our time back down to 21s.
The attached patch is not against your latest revs. After updating I would
need to sprinkle a few S_ISDIR checks into diff-cache.c and checkout-cache.c,
but the changes should be small.
-chris
[-- Attachment #2: fast-dirs-3.diff --]
[-- Type: text/x-diff, Size: 15962 bytes --]
Index: Makefile
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/Makefile (mode:100644 sha1:6a04941a337ec50da06cf4cf52aa58f3b1435776)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/Makefile (mode:100644 sha1:2ba6d49196e8a2335cfcd77ec0dbe9cda3e402dd)
@@ -29,7 +29,7 @@
VERSION= VERSION
-LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o
+LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o libwrite-tree.o
LIB_FILE=libgit.a
LIB_H=cache.h object.h
Index: cache.h
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/cache.h (mode:100644 sha1:c182ea0c5c1def37d899f9a05f8884ebe17c9d92)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/cache.h (mode:100644 sha1:0882b713222b71e67c9dab5d58ab6f15c3c49ed6)
@@ -74,7 +74,7 @@
#define ce_stage(ce) ((CE_STAGEMASK & ntohs((ce)->ce_flags)) >> CE_STAGESHIFT)
#define ce_permissions(mode) (((mode) & 0100) ? 0755 : 0644)
-#define create_ce_mode(mode) htonl(S_IFREG | ce_permissions(mode))
+#define create_ce_mode(mode) htonl((mode & (S_IFREG|S_IFDIR)) | ce_permissions(mode))
#define cache_entry_size(len) ((offsetof(struct cache_entry,name) + (len) + 8) & ~7)
Index: libwrite-tree.c
===================================================================
--- /dev/null (tree:dbeacafeb442bcfd39dfdc90c360d47d4215c185)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/libwrite-tree.c (mode:100644 sha1:52202930d02b3721f5a388ae1178c5a4d99ec1b4)
@@ -0,0 +1,174 @@
+/*
+ * GIT - The information manager from hell
+ *
+ * Copyright (C) Linus Torvalds, 2005
+ */
+#include "cache.h"
+
+struct new_ce {
+ struct new_ce *next;
+ struct cache_entry ce;
+};
+
+static struct new_ce *add_list = NULL;
+
+static int check_valid_sha1(unsigned char *sha1)
+{
+ char *filename = sha1_file_name(sha1);
+ int ret;
+
+ /* If we were anal, we'd check that the sha1 of the contents actually matches */
+ ret = access(filename, R_OK);
+ if (ret)
+ perror(filename);
+ return ret;
+}
+
+static int prepend_integer(char *buffer, unsigned val, int i)
+{
+ buffer[--i] = '\0';
+ do {
+ buffer[--i] = '0' + (val % 10);
+ val /= 10;
+ } while (val);
+ return i;
+}
+
+#define ORIG_OFFSET (40) /* Enough space to add the header of "tree <size>\0" */
+
+static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)
+{
+ unsigned char subdir_sha1[20];
+ unsigned long size, offset;
+ char *buffer;
+ int i, nr;
+
+ /* Guess at some random initial size */
+ size = 8192;
+ buffer = malloc(size);
+ offset = ORIG_OFFSET;
+
+ nr = 0;
+ do {
+ struct cache_entry *ce = cachep[nr];
+ const char *pathname = ce->name, *filename, *dirname;
+ int pathlen = ce_namelen(ce), entrylen;
+ unsigned char *sha1;
+ unsigned int mode;
+
+ /* Did we hit the end of the directory? Return how many we wrote */
+ if (baselen >= pathlen || memcmp(base, pathname, baselen))
+ break;
+
+ sha1 = ce->sha1;
+ mode = ntohl(ce->ce_mode);
+
+ /* Do we have _further_ subdirectories? */
+ filename = pathname + baselen;
+ dirname = strchr(filename, '/');
+ if (dirname) {
+ int subdir_written;
+ int len = dirname - pathname;
+ unsigned int size = cache_entry_size(len);
+ struct new_ce *new_ce = malloc(size + sizeof(struct new_ce *));
+ struct cache_entry *c = &new_ce->ce;
+ subdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);
+ nr += subdir_written - 1;
+
+ /* Now we need to write out the directory entry into this tree.. */
+ mode = S_IFDIR;
+ pathlen = dirname - pathname;
+
+ sha1 = subdir_sha1;
+
+ memset(c, 0, size);
+
+ /* create a new cache entry for what we just calculated.
+ * place the new entry on a list for adding later so we
+ * don't change the size of the cache right now.
+ */
+ c->ce_mode = create_ce_mode(mode);
+ c->ce_flags = create_ce_flags(len, 0);
+ memcpy(c->name, pathname, len);
+ c->name[len] = '\0';
+ memcpy(c->sha1, sha1, 20);
+ new_ce->next = add_list;
+ add_list = new_ce;
+ } else if (mode & S_IFDIR) {
+ /* eat all the entries below this directory */
+ while(++nr < maxentries) {
+ struct cache_entry *c = cachep[nr];
+
+ if (strlen(c->name) < pathlen)
+ break;
+ if (memcmp(c->name, pathname, pathlen) ||
+ c->name[pathlen] != '/')
+ break;
+ }
+ /* our loop went too far by 1 */
+ nr--;
+ mode = S_IFDIR;
+ }
+
+ if (check_valid_sha1(sha1) < 0)
+ exit(1);
+
+ entrylen = pathlen - baselen;
+ if (offset + entrylen + 100 > size) {
+ size = alloc_nr(offset + entrylen + 100);
+ buffer = realloc(buffer, size);
+ }
+ offset += sprintf(buffer + offset, "%o %.*s", mode, entrylen, filename);
+ buffer[offset++] = 0;
+ memcpy(buffer + offset, sha1, 20);
+ offset += 20;
+ nr++;
+ } while (nr < maxentries);
+
+ i = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);
+ i -= 5;
+ memcpy(buffer+i, "tree ", 5);
+
+ write_sha1_file(buffer + i, offset - i, returnsha1);
+ free(buffer);
+ return nr;
+}
+
+void write_full_tree(int entries) {
+ unsigned char sha1[20];
+ int i, unmerged;
+
+ if (entries <= 0)
+ die("write-tree: no cache contents to write");
+
+ /* Verify that the tree is merged */
+ unmerged = 0;
+ for (i = 0; i < entries; i++) {
+ struct cache_entry *ce = active_cache[i];
+ if (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {
+ if (++unmerged > 10) {
+ fprintf(stderr, "...\n");
+ break;
+ }
+ fprintf(stderr, "%s: unmerged (%s)\n", ce->name, sha1_to_hex(ce->sha1));
+ }
+ }
+ if (unmerged)
+ die("write-tree: not able to write tree");
+
+ /* Ok, write it out */
+ if (write_tree(active_cache, entries, "", 0, sha1) != entries)
+ die("write-tree: internal error");
+ printf("%s\n", sha1_to_hex(sha1));
+ if (add_list) {
+ struct new_ce *nc = add_list;
+ while(nc) {
+ add_cache_entry(&nc->ce, 1);
+ nc = nc->next;
+ }
+ }
+}
+
+int write_tree_updated_cache(void) {
+ return add_list != NULL;
+}
Index: merge-cache.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/merge-cache.c (mode:100644 sha1:96c86c26d06837bf604a70caf9dd2133884a63bc)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/merge-cache.c (mode:100644 sha1:1b45bfc8cf5b4c610a4b149f3a4295081bc0e00f)
@@ -63,8 +63,16 @@
* If it already exists in the cache as stage0, it's
* already merged and there is nothing to do.
*/
- if (pos < 0)
- merge_entry(-pos-1, path);
+ if (pos < 0) {
+ pos = -pos-1;
+ while(pos > 0) {
+ int mode = htonl(active_cache[pos]->ce_mode);
+ if (S_ISREG(mode))
+ break;
+ pos--;
+ }
+ merge_entry(pos, path);
+ }
}
static void merge_all(void)
@@ -74,7 +82,8 @@
struct cache_entry *ce = active_cache[i];
if (!ce_stage(ce))
continue;
- i += merge_entry(i, ce->name)-1;
+ if (S_ISREG(htonl(ce->ce_mode)))
+ i += merge_entry(i, ce->name)-1;
}
}
Index: read-cache.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/read-cache.c (mode:100644 sha1:17d4d2284e79d3f1070b51200d797115f2d09d6a)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/read-cache.c (mode:100644 sha1:d2fc8e35f5ef602f7baa1a4c83c74dbf373fc3e0)
@@ -96,11 +96,30 @@
return 1;
}
+static void invalidate_trees(char *path) {
+ char *p;
+ int len = strlen(path);
+ int pos;
+ extern void *memrchr(__const void *, int, size_t);
+ while(1) {
+ p = memrchr(path, '/', len);
+ if (!p || p == path)
+ return;
+ len = p-path;
+ pos = cache_name_pos(path, len);
+ if (pos < 0)
+ return;
+ remove_entry_at(pos);
+ }
+}
+
int remove_file_from_cache(char *path)
{
int pos = cache_name_pos(path, strlen(path));
- if (pos >= 0)
+ if (pos >= 0) {
remove_entry_at(pos);
+ invalidate_trees(path);
+ }
return 0;
}
@@ -113,12 +132,16 @@
int add_cache_entry(struct cache_entry *ce, int ok_to_add)
{
int pos;
+ int invalidate = S_ISREG(htonl(ce->ce_mode));
pos = cache_name_pos(ce->name, htons(ce->ce_flags));
/* existing match? Just replace it */
if (pos >= 0) {
active_cache[pos] = ce;
+ if (invalidate) {
+ invalidate_trees(ce->name);
+ }
return 0;
}
pos = -pos-1;
@@ -149,6 +172,9 @@
if (active_nr > pos)
memmove(active_cache + pos + 1, active_cache + pos, (active_nr - pos - 1) * sizeof(ce));
active_cache[pos] = ce;
+ if (invalidate) {
+ invalidate_trees(ce->name);
+ }
return 0;
}
Index: read-tree.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/read-tree.c (mode:100644 sha1:a573a3155e532081a8be0dab60f1ec35ea159ddf)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/read-tree.c (mode:100644 sha1:fa497650937a62caadd043897032cf5f9e07dea2)
@@ -63,7 +63,6 @@
free(buffer);
return -1;
}
- continue;
}
if (read_one_entry(sha1, base, baselen, path, mode) < 0) {
free(buffer);
Index: show-diff.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/show-diff.c (mode:100644 sha1:007dabd2978de4c58f49050d3969ca353278dbb6)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/show-diff.c (mode:100644 sha1:a7b0a0bca00c173f591a0d8ef0dfbcbdd96ef8a9)
@@ -163,6 +163,8 @@
if (1 < argc &&
! matches_pathspec(ce, argv+1, argc-1))
continue;
+ if (S_ISDIR(htonl(ce->ce_mode)))
+ continue;
matched++;
if (ce_stage(ce)) {
Index: update-cache.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/update-cache.c (mode:100644 sha1:11388582a830a6161d1c769aa8616bed6f593b8a)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/update-cache.c (mode:100644 sha1:cab4e8e1fa7aceff287cfb3464710b1dd52f3a5f)
@@ -4,6 +4,7 @@
* Copyright (C) Linus Torvalds, 2005
*/
#include "cache.h"
+#include "write-tree.h"
/*
* Default to not allowing changes to the list of files. The
@@ -12,7 +13,7 @@
* like "update-cache *" and suddenly having all the object
* files be revision controlled.
*/
-static int allow_add = 0, allow_remove = 0;
+static int allow_add = 0, allow_remove = 0, write_tree = 0;
static int index_fd(unsigned char *sha1, int fd, struct stat *st)
{
@@ -182,7 +183,6 @@
if (stat(ce->name, &st) < 0)
return NULL;
-
changed = cache_match_stat(ce, &st);
if (!changed)
return ce;
@@ -191,12 +191,11 @@
* If the mode has changed, there's no point in trying
* to refresh the entry - it's not going to match
*/
- if (changed & MODE_CHANGED)
+ if (changed & MODE_CHANGED) {
return NULL;
-
+ }
if (compare_data(ce, st.st_size))
return NULL;
-
size = ce_size(ce);
updated = malloc(size);
memcpy(updated, ce, size);
@@ -222,7 +221,8 @@
new = refresh_entry(ce);
if (!new) {
- printf("%s: needs update\n", ce->name);
+ if (S_ISREG(ntohl(ce->ce_mode)))
+ printf("%s: needs update\n", ce->name);
continue;
}
/* You can NOT just free active_cache[i] here, since it
@@ -336,6 +336,10 @@
i += 3;
continue;
}
+ if (!strcmp(path, "--write-tree")) {
+ write_tree = 1;
+ continue;
+ }
die("unknown option %s", path);
}
if (!verify_path(path)) {
@@ -345,6 +349,9 @@
if (add_file_to_cache(path))
die("Unable to add %s to database", path);
}
+ if (write_tree) {
+ write_full_tree(active_nr);
+ }
if (write_cache(newfd, active_cache, active_nr) ||
rename(".git/index.lock", ".git/index"))
die("Unable to write new cachefile");
Index: write-tree.c
===================================================================
--- dbeacafeb442bcfd39dfdc90c360d47d4215c185/write-tree.c (mode:100644 sha1:fb046aa6ce6b9fce6a523a1e36ff43adab9bdd93)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/write-tree.c (mode:100644 sha1:c3d62242f0d5fff0c245cd46ac8a5b72d4aef4cd)
@@ -4,127 +4,28 @@
* Copyright (C) Linus Torvalds, 2005
*/
#include "cache.h"
-
-static int check_valid_sha1(unsigned char *sha1)
-{
- char *filename = sha1_file_name(sha1);
- int ret;
-
- /* If we were anal, we'd check that the sha1 of the contents actually matches */
- ret = access(filename, R_OK);
- if (ret)
- perror(filename);
- return ret;
-}
-
-static int prepend_integer(char *buffer, unsigned val, int i)
-{
- buffer[--i] = '\0';
- do {
- buffer[--i] = '0' + (val % 10);
- val /= 10;
- } while (val);
- return i;
-}
-
-#define ORIG_OFFSET (40) /* Enough space to add the header of "tree <size>\0" */
-
-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)
-{
- unsigned char subdir_sha1[20];
- unsigned long size, offset;
- char *buffer;
- int i, nr;
-
- /* Guess at some random initial size */
- size = 8192;
- buffer = malloc(size);
- offset = ORIG_OFFSET;
-
- nr = 0;
- do {
- struct cache_entry *ce = cachep[nr];
- const char *pathname = ce->name, *filename, *dirname;
- int pathlen = ce_namelen(ce), entrylen;
- unsigned char *sha1;
- unsigned int mode;
-
- /* Did we hit the end of the directory? Return how many we wrote */
- if (baselen >= pathlen || memcmp(base, pathname, baselen))
- break;
-
- sha1 = ce->sha1;
- mode = ntohl(ce->ce_mode);
-
- /* Do we have _further_ subdirectories? */
- filename = pathname + baselen;
- dirname = strchr(filename, '/');
- if (dirname) {
- int subdir_written;
-
- subdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);
- nr += subdir_written;
-
- /* Now we need to write out the directory entry into this tree.. */
- mode = S_IFDIR;
- pathlen = dirname - pathname;
-
- /* ..but the directory entry doesn't count towards the total count */
- nr--;
- sha1 = subdir_sha1;
- }
-
- if (check_valid_sha1(sha1) < 0)
- exit(1);
-
- entrylen = pathlen - baselen;
- if (offset + entrylen + 100 > size) {
- size = alloc_nr(offset + entrylen + 100);
- buffer = realloc(buffer, size);
- }
- offset += sprintf(buffer + offset, "%o %.*s", mode, entrylen, filename);
- buffer[offset++] = 0;
- memcpy(buffer + offset, sha1, 20);
- offset += 20;
- nr++;
- } while (nr < maxentries);
-
- i = prepend_integer(buffer, offset - ORIG_OFFSET, ORIG_OFFSET);
- i -= 5;
- memcpy(buffer+i, "tree ", 5);
-
- write_sha1_file(buffer + i, offset - i, returnsha1);
- free(buffer);
- return nr;
-}
+#include "write-tree.h"
int main(int argc, char **argv)
{
- int i, unmerged;
int entries = read_cache();
- unsigned char sha1[20];
+ int newfd;
+ newfd = open(".git/index.lock", O_RDWR | O_CREAT | O_EXCL, 0600);
+ if (newfd < 0)
+ die("unable to create new cachefile");
+
if (entries <= 0)
die("write-tree: no cache contents to write");
- /* Verify that the tree is merged */
- unmerged = 0;
- for (i = 0; i < entries; i++) {
- struct cache_entry *ce = active_cache[i];
- if (ntohs(ce->ce_flags) & ~CE_NAMEMASK) {
- if (++unmerged > 10) {
- fprintf(stderr, "...\n");
- break;
- }
- fprintf(stderr, "%s: unmerged (%s)\n", ce->name, sha1_to_hex(ce->sha1));
- }
+ write_full_tree(entries);
+ if (write_tree_updated_cache()) {
+ if (write_cache(newfd, active_cache, active_nr) ||
+ rename(".git/index.lock", ".git/index"))
+ die("Unable to write new cachefile");
+ } else {
+ close(newfd);
+ unlink(".git/index.lock");
}
- if (unmerged)
- die("write-tree: not able to write tree");
-
- /* Ok, write it out */
- if (write_tree(active_cache, entries, "", 0, sha1) != entries)
- die("write-tree: internal error");
- printf("%s\n", sha1_to_hex(sha1));
return 0;
}
Index: write-tree.h
===================================================================
--- /dev/null (tree:dbeacafeb442bcfd39dfdc90c360d47d4215c185)
+++ 27e71cd40ff1dccfbbd996427833fd7bac714dde/write-tree.h (mode:100644 sha1:0ad5fe36126577e56544e08e0f4dfa766350e841)
@@ -0,0 +1,3 @@
+
+void write_full_tree(int);
+int write_tree_updated_cache(void);
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: Martin Uecker @ 2005-04-20 15:19 UTC (permalink / raw)
To: Git Mailing List
In-Reply-To: <Pine.LNX.4.61.0504201025030.2630@cag.csail.mit.edu>
[-- Attachment #1: Type: text/plain, Size: 2752 bytes --]
On Wed, Apr 20, 2005 at 10:30:15AM -0400, C. Scott Ananian wrote:
Hi,
your code looks pretty cool. thank you!
> On Wed, 20 Apr 2005, Martin Uecker wrote:
>
> >The other thing I don't like is the use of a sha1
> >for a complete file. Switching to some kind of hash
> >tree would allow to introduce chunks later. This has
> >two advantages:
>
> You can (and my code demonstrates/will demonstrate) still use a whole-file
> hash to use chunking. With content prefixes, this takes O(N ln M) time
> (where N is the file size and M is the number of chunks) to compute all
> hashes; if subtrees can share the same prefix, then you can do this in
> O(N) time (ie, as fast as possible, modulo a constant factor, which is
> '2'). You don't *need* internal hashing functions.
I don't understand this paragraph. What is an internal
hash function? Your code seems to do exactly what I want.
The hashes are computed recusively as in a hash tree
with O(N ln N). The only difference between your design
and a design based on a conventional (binary) hash tree
seems to be that data is stored in the intermediate nodes
too.
> >It would allow git to scale to repositories of large
> >binary files. And it would allow to build a very cool
> >content transport algorithm for those repositories.
> >This algorithm could combine all the advantages of
> >bittorrent and rsync (without the cpu load).
>
> Yes, the big benefit of internal hashing is that it lets you check
> validity of a chunk w/o having the entire file available. I'm not sure
> that's terribly useful in this case. [And, if it is, then it can
> obviously be done w/ other means.]
If I don't miss anything essential, you can validate
each treap piece at the moment you get it from the
network with its SHA1 hash and then proceed with
downloading the prefix and suffix tree (in parallel
if you have more than one peer a la bittorrent).
> >And it would allow trivial merging of patches which
> >apply to different chunks of a file in exact the same
> >way as merging changesets which apply to different
> >files in a tree.
>
> I'm not sure anyone should be looking at chunks. To me, at least, they
> are an object-store-implementation detail only. For merging, etc, we
> should be looking at whole files, or (better) the whole repository.
> The chunking algorithm is guaranteed not to respect semantic boundaries
> (for *some* semantics of *some* file).
You might be right. I just wanted to point out this
possibility because it would allow to avoid calling
external merging code for a lot of trivial merges.
bye,
Martin
--
One night, when little Giana from Milano was fast asleep,
she had a strange dream.
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: Linus Torvalds @ 2005-04-20 14:59 UTC (permalink / raw)
To: David Woodhouse; +Cc: H. Peter Anvin, Git Mailing List, Chris Mason
In-Reply-To: <1114006429.5877.42.camel@localhost.localdomain>
On Thu, 21 Apr 2005, David Woodhouse wrote:
>
> The reason for doing this is that without it, we can't ever have a full
> history actually connected to the current trees. There'd always be a
> break at 2.6.12-rc2, at which point you'd have to switch to an entirely
> different git repository.
Quite frankly, I'd _much_ rather have a notion of "external references"
than start depending on external hashes.
IOW, I'd be happier with a new line in the header (after the normal
"author"/"committer" lines) that just pointed to an external tree, aka
external linux-2.6.12-rc2-tree
and then people could literally use this to link whatever they wanted, and
it would not force one particular version of an external tree on you.
Why? Because we can't keep re-generating trees.
However, the second part of that plan is that once you do that, you might
as well make the "external" linkages be external to the repository itself.
IOW, you could just make a file that the git tools can parse that say
external-parent <root-hash> <external-parent-ID>
comment for this parent
external-parent <commit-hash> <external-parent-ID>
comment for this parent
and the nice thing about that is that now that information allows you to
add external parents at any point.
Why do it like this? First off, I think that the "initial import" ends up
being just one special case of the much more _generic_ issue of having
patches come in from other source control systems (ie the above would
actually work with the darcs issues too, and allow people to track the
dependencies between a tree maintained in git and maintained elsewhere).
Secondly, we do need something like this for pruning off history anyway,
so that the tools have a better way of saying "history has been pruned
off" than just hitting a missing commit. That's not a big deal right now,
since I'm not planning on letting people prune their history (or at least
I'm planning on having tools complain loudly), but it _will_ be an issue.
I think history pruning is wonderful, but I do want to have some mechanism
to say "it was pruned" as opposed to "it was lost".
Thirdly, I don't actually want my new tree to depend on a conversion of
the old BK tree.
Two reasons: if it's a really full conversion, there are definitely going
to be issues with BitMover. They do not want people to try to reverse
engineer how they do namespace merges, which is why they have the "don't
look at git and do another SCM at the same time" clause in the first
place. Namespace merges (and probably other things too, for that matter)
tend to be the thing they tend to do better than anybody else. The kernel
probably does not actually have a lot of those so it might be ok by them,
but the keyword is _might_, and I don't want to cloud git by another
flamewar.
The other reason is just the really obvious one: in the last week, I've
already changed the format _twice_ in ways that change the hash. As long
as it's 119MB of data, it's not going to be too nasty to do again. If it's
3+GB of data, I'm going to feel really constrained about the kind of
conversions I can do. It's one thing to have something that takes a few
minutes and that anybody can do. It's another thing entirely to do
something that requires the convertee to dedicate tons of diskspace and
hours of work on it.
Let's face it, I doubt we did our last conversion ever. I still think that
the git data model is the best model _ever_ for an SCM, but it's not all
the minute details I'm proud over, it's the general big things. For
example, let's see how the "blobs are sequences of smaller hashes" thing
works out. I was doubtful, but Scott's first chunking code doesn't make me
hurl chunks, and I've been wrong before.
And the thing is, I'm ok with being wrong. Especially if I can fix things
up later.
So I've got tons of reasons (that you may not agree with, obviously) for
why I don't think it's a good idea to base the kernel on a large
conversion. Some (or all) of those reasons may become moot in another week
or month, but I'd definitely _not_ that interested in doing it now. If it
turns out later that we do want to re-base the kernel, we can do any
conversion we want at a later time - it's not that it's necessarily the
wrong thing to do, but I think it is the wrogn thing to do _now_.
Linus
^ permalink raw reply
* Re: enforcing DB immutability
From: Nick Craig-Wood @ 2005-04-20 14:57 UTC (permalink / raw)
To: Ingo Molnar; +Cc: Linus Torvalds, H. Peter Anvin, git
In-Reply-To: <20050420074948.GA22620@elte.hu>
On Wed, Apr 20, 2005 at 09:49:48AM +0200, Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
>
> > perhaps having a new 'immutable hardlink' feature in the Linux VFS
> > would help? I.e. a hardlink that can only be readonly followed, and
> > can be removed, but cannot be chmod-ed to a writeable hardlink. That i
> > think would be a large enough barrier for editors/build-tools not to
> > play the tricks they already do that makes 'readonly' files virtually
> > meaningless.
>
> immutable hardlinks have the following advantage: a hardlink by design
> hides the information where the link comes from. So even if an editor
> wanted to play stupid games and override the immutability - it doesnt
> know where the DB object is. (sure, it could find it if it wants to, but
> that needs real messing around - editors wont do _that_)
This has already been implemented for the linux vserver project. Take
a look in the patch here :-
http://vserver.13thfloor.at/Experimental/patch-2.6.11.7-vs1.9.5.x5.diff.bz2
(Its not split out, but search for IMMUTABLE and you'll see what I mean)
It implements immutable linkage invert, which basically allows people
to delete hardlinks to immutable files, but not do anything else to
them. It uses another bit out of the attributes to "invert" the
immutability of the linkage of immutable files.
Its used in the vserver project so that individual vservers (which are
basically just fancy chroots) can share libraries, binaries and hence
memory, can't muck each other up, but can upgrade their libs/binaries.
--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: C. Scott Ananian @ 2005-04-20 14:35 UTC (permalink / raw)
To: Linus Torvalds; +Cc: jon, Git Mailing List
In-Reply-To: <Pine.LNX.4.58.0504200725110.6467@ppc970.osdl.org>
On Wed, 20 Apr 2005, Linus Torvalds wrote:
> - _keep_ the same compression format, but notice that we already have an
> object by looking at the uncompressed one.
With a chunked file, you can also skip writing certain *subtrees* of the
file as soon as you notice it's already present on disk. I can code this
up if you are interested.
Of course, the paranoid folks will give up any performance benefit you
obtain if they keep their "yes the SHA1 matches, but is the file *really*
the same" code. But maybe they're willing to be slow -- and they can do
an uncompress rather than a compress in order to do the comparison, which
will give *some* performance improvement.
--scott
LCPANGS Serbian MKSEARCH security KUCLUB LCPANES Saddam Hussein Secretary
Delta Force AMLASH ESMERALDITE TPAJAX plutonium ESGAIN Ft. Meade India
( http://cscott.net/ )
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: C. Scott Ananian @ 2005-04-20 14:30 UTC (permalink / raw)
To: Martin Uecker; +Cc: Git Mailing List
In-Reply-To: <20050420132446.GA10126@macavity>
On Wed, 20 Apr 2005, Martin Uecker wrote:
> The other thing I don't like is the use of a sha1
> for a complete file. Switching to some kind of hash
> tree would allow to introduce chunks later. This has
> two advantages:
You can (and my code demonstrates/will demonstrate) still use a whole-file
hash to use chunking. With content prefixes, this takes O(N ln M) time
(where N is the file size and M is the number of chunks) to compute all
hashes; if subtrees can share the same prefix, then you can do this in
O(N) time (ie, as fast as possible, modulo a constant factor, which is
'2'). You don't *need* internal hashing functions.
> It would allow git to scale to repositories of large
> binary files. And it would allow to build a very cool
> content transport algorithm for those repositories.
> This algorithm could combine all the advantages of
> bittorrent and rsync (without the cpu load).
Yes, the big benefit of internal hashing is that it lets you check
validity of a chunk w/o having the entire file available. I'm not sure
that's terribly useful in this case. [And, if it is, then it can
obviously be done w/ other means.]
> And it would allow trivial merging of patches which
> apply to different chunks of a file in exact the same
> way as merging changesets which apply to different
> files in a tree.
I'm not sure anyone should be looking at chunks. To me, at least, they
are an object-store-implementation detail only. For merging, etc, we
should be looking at whole files, or (better) the whole repository.
The chunking algorithm is guaranteed not to respect semantic boundaries
(for *some* semantics of *some* file).
--scott
explosion JMTRAX DC KUBARK biowarfare LCFLUTTER ESMERALDITE for Dummies
Hager Nader Israel General ZRMETAL Castro cryptographic Indonesia
( http://cscott.net/ )
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: Linus Torvalds @ 2005-04-20 14:29 UTC (permalink / raw)
To: jon; +Cc: Git Mailing List
In-Reply-To: <2cfc4032050420050655265d3a@mail.gmail.com>
On Wed, 20 Apr 2005, Jon Seymour wrote:
>
> Am I correct to understand that with this change, all the objects in the
> database are still being compressed (so no net performance benefit), but by
> doing the SHA1 calculations before compression you are keeping open the
> possibility that at some point in the future you may use a different
> compression technique (including none at all) for some or all of the
> objects?
Correct. There is zero performance benefit to this right now, and the only
reason for doing it is because it will allow other things to happen.
Note that the other things include:
- change the compression format to make it cheaper
- _keep_ the same compression format, but notice that we already have an
object by looking at the uncompressed one.
I'm actually leaning towards just #2 at this time. I like how things
compress, and it sure is simple. The fact that we use the equivalent of
"-9" may be expensive, but the thing is, we don't actually write new files
that often, and it's "just" CPU time (no seeking on disk or anything like
that), which tends to get cheaper over time.
So I suspect that once I optimize the tree writing to notice that "oh, I
already have this tree object", and thus build it up but never compressing
it, "write-tree" performance will go up _hugely_ even without removing the
compressioin. Because most of the time, write-tree actually only needs to
create a couple of small new tree objects.
Linus
^ permalink raw reply
* Re: WARNING! Object DB conversion (was Re: [PATCH] write-tree performance problems)
From: David Woodhouse @ 2005-04-20 14:13 UTC (permalink / raw)
To: Linus Torvalds; +Cc: H. Peter Anvin, Git Mailing List, Chris Mason
In-Reply-To: <Pine.LNX.4.58.0504200144260.6467@ppc970.osdl.org>
On Wed, 2005-04-20 at 02:08 -0700, Linus Torvalds wrote:
> I converted my git archives (kernel and git itself) to do the SHA1
> hash _before_ the compression phase.
I'm happy to see that -- because I'm going to be asking you to make
another change which will also require a simple repository conversion.
We are working on getting the complete history since 2.4.0 into git
form. When it's done and checked (which should be RSN) I'd like you to
edit the first commit object in your tree -- the import of 2.6.12-rc2,
and give it a parent. That parent will be the sha1 hash of the
2.6.12-rc2 commit in the newly-provided history, and of course will
change the sha1 hash of your first commit, and all subsequent commits.
We'll provide a tool to do that, of course.
The history itself will be absent from your tree. Obviously we'll need
to make sure that the tools can cope with an absentee parent, probably
by just treating that case as if no parent exists. That won't be hard,
it'll be useful for people to prune their trees of unwanted older
history in the general case too. That history won't be lost or undone --
it'll just be archived elsewhere.
The reason for doing this is that without it, we can't ever have a full
history actually connected to the current trees. There'd always be a
break at 2.6.12-rc2, at which point you'd have to switch to an entirely
different git repository.
--
dwmw2
^ 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