threads / patch / 22739

patchRe: [PATCH] sha1_file: don't malloc the whole compressed result when writing out objects

Subject: Re: [PATCH] sha1_file: don't malloc the whole compressed result when writing out objects

## tl;dr

13 messages between Feb 21, 2010 and Feb 22, 2010. Diffs are folded; open one to read it.

replies: 12people: 3as markdown or json

Nicolas Pitre· Feb 21, 2010, 04:27 UTC · lore

[PATCH] sha1_file: don't malloc the whole compressed result when writing out objects

There is no real advantage to malloc the whole output buffer and deflate the data in a single pass when writing loose objects. That is like only 1% faster while using more memory, especially with large files where memory usage is far more. It is best to deflate and write the data out in small chunks reusing the same memory instead.

For example, using 'git add' on a few large files averaging 40 MB ...

Before: 21.45user 1.10system 0:22.57elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+828040outputs (0major+142640minor)pagefaults 0swaps

After: 21.50user 1.25system 0:22.76elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+828040outputs (0major+104408minor)pagefaults 0swaps

While the runtime stayed relatively the same, the number of minor page faults went down significantly.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
---

I think this is worth doing independently of the paranoid mode being discussed.

Show changes to sha1_file.c +10 −14
diff --git a/sha1_file.c b/sha1_file.c
index 657825e..9196b57 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2281,8 +2281,7 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 			      void *buf, unsigned long len, time_t mtime)
 {
 	int fd, ret;
-	size_t size;
-	unsigned char *compressed;
+	unsigned char compressed[4096];
 	z_stream stream;
 	char *filename;
 	static char tmpfile[PATH_MAX];
@@ -2301,12 +2300,8 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 	/* Set it up */
 	memset(&stream, 0, sizeof(stream));
 	deflateInit(&stream, zlib_compression_level);
-	size = 8 + deflateBound(&stream, len+hdrlen);
-	compressed = xmalloc(size);
-
-	/* Compress it */
 	stream.next_out = compressed;
-	stream.avail_out = size;
+	stream.avail_out = sizeof(compressed);
 
 	/* First header.. */
 	stream.next_in = (unsigned char *)hdr;
@@ -2317,20 +2312,21 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 	/* Then the data itself.. */
 	stream.next_in = buf;
 	stream.avail_in = len;
-	ret = deflate(&stream, Z_FINISH);
+	do {
+		ret = deflate(&stream, Z_FINISH);
+		if (write_buffer(fd, compressed, stream.next_out - compressed) < 0)
+			die("unable to write sha1 file");
+		stream.next_out = compressed;
+		stream.avail_out = sizeof(compressed);
+	} while (ret == Z_OK);
+
 	if (ret != Z_STREAM_END)
 		die("unable to deflate new object %s (%d)", sha1_to_hex(sha1), ret);
-
 	ret = deflateEnd(&stream);
 	if (ret != Z_OK)
 		die("deflateEnd on object %s failed (%d)", sha1_to_hex(sha1), ret);
 
-	size = stream.total_out;
-
-	if (write_buffer(fd, compressed, size) < 0)
-		die("unable to write sha1 file");
 	close_sha1_file(fd);
-	free(compressed);
 
 	if (mtime) {
 		struct utimbuf utb;
Junio C Hamano· Feb 21, 2010, 19:45 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
> I think this is worth doing independently of the paranoid mode being 
> discussed.

While I agree it might be worth doing, I can see that you really hate "paranoia". Now your loop is letting deflate() decide how much it happens to like to consume in a given round, it is much trickier to plug the paranoia in without majorly rewriting the loop this patch introduces.

Nicolas Pitre· Feb 21, 2010, 21:26 UTC · re: Junio C Hamano · lore
On Sun, 21 Feb 2010, Junio C Hamano wrote:
Show 9 quoted lines
> Nicolas Pitre <nico@fluxnic.net> writes:
> 
> > I think this is worth doing independently of the paranoid mode being 
> > discussed.
> 
> While I agree it might be worth doing, I can see that you really hate
> "paranoia".  Now your loop is letting deflate() decide how much it happens
> to like to consume in a given round, it is much trickier to plug the
> paranoia in without majorly rewriting the loop this patch introduces.
I disagree.

Here's my take on the paranoia issue. Now the question is whether or not this should really be optional. I would think no.

FWIW, we already have that double SHA1 protection when dealing with pack files with fixup_pack_header_footer() (see commit abeb40e5aa).

---------- >8
From: Nicolas Pitre <nico@fluxnic.net>
Date: Sun, 21 Feb 2010 15:48:06 -0500
Subject: [PATCH] sha1_file: be paranoid when creating loose objects

We don't want the data being deflated and stored into loose objects to be different from what we expect. While the deflated data is protected by a CRC which is good enough for safe data retrieval operations, we still want to be doubly sure that the source data used at object creation time is still what we expected once that data has been deflated and its CRC32 computed.

The most plausible data corruption may occur if the source file is modified while Git is deflating and writing it out in a loose object. Or Git itself could have a bug causing memory corruption. Or even bad RAM could cause trouble. So it is best to make sure everything is coherent and checksum protected from beginning to end.

To do so we compute the SHA1 of the data being deflated _after_ the deflate operation has consumed that data, and make sure it matches with the expected SHA1. This way we can rely on the CRC32 checked by the inflate operation to provide a good indication that the data is still coherent with its SHA1 hash.

There is some overhead of course. Using 'git add' on a set of large files:
Before:
	real    0m25.210s
	user    0m23.783s
	sys     0m1.408s
After:
	real    0m26.537s
	user    0m25.175s
	sys     0m1.358s
The overhead is around 5% for full data coherency guarantee.
Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
Show changes to sha1_file.c +9 −0
diff --git a/sha1_file.c b/sha1_file.c
index 9196b57..c0214d7 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2283,6 +2283,8 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 	int fd, ret;
 	unsigned char compressed[4096];
 	z_stream stream;
+	git_SHA_CTX c;
+	unsigned char parano_sha1[20];
 	char *filename;
 	static char tmpfile[PATH_MAX];
 
@@ -2302,18 +2304,22 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 	deflateInit(&stream, zlib_compression_level);
 	stream.next_out = compressed;
 	stream.avail_out = sizeof(compressed);
+	git_SHA1_Init(&c);
 
 	/* First header.. */
 	stream.next_in = (unsigned char *)hdr;
 	stream.avail_in = hdrlen;
 	while (deflate(&stream, 0) == Z_OK)
 		/* nothing */;
+	git_SHA1_Update(&c, hdr, hdrlen);
 
 	/* Then the data itself.. */
 	stream.next_in = buf;
 	stream.avail_in = len;
 	do {
+		unsigned char *in0 = stream.next_in;
 		ret = deflate(&stream, Z_FINISH);
+		git_SHA1_Update(&c, in0, stream.next_in - in0);
 		if (write_buffer(fd, compressed, stream.next_out - compressed) < 0)
 			die("unable to write sha1 file");
 		stream.next_out = compressed;
@@ -2325,6 +2331,9 @@ static int write_loose_object(const unsigned char *sha1, char *hdr, int hdrlen,
 	ret = deflateEnd(&stream);
 	if (ret != Z_OK)
 		die("deflateEnd on object %s failed (%d)", sha1_to_hex(sha1), ret);
+	git_SHA1_Final(parano_sha1, &c);
+	if (hashcmp(sha1, parano_sha1) != 0)
+		die("confused by unstable object source data for %s", sha1_to_hex(sha1));
 
 	close_sha1_file(fd);
Junio C Hamano· Feb 21, 2010, 22:22 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
> I disagree.
>
> Here's my take on the paranoia issue.
Ahh, yes, of course.
You are always a better programmer than I am and I keep getting reminded.
Thanks, and I agree it is a sane thing to do this unconditionally.
Junio C Hamano· Feb 21, 2010, 22:30 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
Show 7 quoted lines
>  	/* Then the data itself.. */
>  	stream.next_in = buf;
>  	stream.avail_in = len;
>  	do {
> +		unsigned char *in0 = stream.next_in;
>  		ret = deflate(&stream, Z_FINISH);
> +		git_SHA1_Update(&c, in0, stream.next_in - in0);
Actually, I have to take my earlier comment back.  This is not "paranoia".

I do not see anything that protects the memory area between in0 and stream.next_in from getting modified while deflate() nor SHA1_Update() run from the outside. Unless you copy the data away to somewhere stable at the beginning of each iteration of this loop and run deflate() and SHA1_Update(), you cannot have "paranoia".

My comment about "trickier" is about determining the size of that buffer used as "somewhere stable".

Nicolas Pitre· Feb 22, 2010, 01:35 UTC · re: Junio C Hamano · lore
On Sun, 21 Feb 2010, Junio C Hamano wrote:
Show 15 quoted lines
> Nicolas Pitre <nico@fluxnic.net> writes:
> 
> >  	/* Then the data itself.. */
> >  	stream.next_in = buf;
> >  	stream.avail_in = len;
> >  	do {
> > +		unsigned char *in0 = stream.next_in;
> >  		ret = deflate(&stream, Z_FINISH);
> > +		git_SHA1_Update(&c, in0, stream.next_in - in0);
> 
> Actually, I have to take my earlier comment back.  This is not "paranoia".
> 
> I do not see anything that protects the memory area between in0 and
> stream.next_in from getting modified while deflate() nor SHA1_Update() run
> from the outside.
So what?
> Unless you copy the data away to somewhere stable at
> the beginning of each iteration of this loop and run deflate() and
> SHA1_Update(), you cannot have "paranoia".
No.
The whole point is to detect data incoherencyes.
So current sequence of events is as follows:

T0 write_sha1_file_prepare() is called T1 start initial SHA1 computation on data buffer T2 in the middle of initial SHA1 computation T3 end of initial SHA1 computation -> object name is determined T4 write_loose_object() is called ... enter the write loop T5+n deflate() called on buffer n T6+n git_SHA1_Update(() called on the same buffer n T7+n deflated data written out ... Tend abort if result of T6+n doesn't match object name from T3

So... what can happen:
1) Data is externally modified before T5+n: deflated data and its CRC32 
   will be coherent with the SHA1 computed in T6+n, but incoherent with 
   the SHA1 used for the object name. Wrong data is written to the 
   object even if it will inflate OK. We really want to prevent that 
   from happening. The test in Tend will fail.
2) Data is externally modified between T5+n and T6+n: the deflated data 
   and CRC32 will be coherent with the object name but incoherent with 
   the parano_sha1.  Although written data will be OK, this is way too 
   close from being wrong, and the test in Tend will fail.  If there is 
   more than one round into the loop and the external modifications are 
   large enough then this becomes the same as case 1 above.
3) Data is externally modified in T2: again the test in Tend will fail.

So in all possible cases I can think of, the write will abort. No copy buffer needed, no filesystem mtime required, etc. If the whole data is not stable between T1 and Tend then the object is not added to the repository. Of course it is possible that the data be modified at the beginning of the file while the loop in T[5-7] is passed that point. But still, there is no data inconsistency at that point.

> My comment about "trickier" is about determining the size of that buffer
> used as "somewhere stable".
We don't care about such buffer.
Nicolas
Junio C Hamano· Feb 22, 2010, 05:30 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
> The whole point is to detect data incoherencyes.

Yes. We want to make sure that the SHA-1 we compute is over what we fed deflate().

Show 32 quoted lines
> So current sequence of events is as follows:
>
> T0	write_sha1_file_prepare() is called
> T1	start initial SHA1 computation on data buffer
> T2	in the middle of initial SHA1 computation
> T3	end of initial SHA1 computation -> object name is determined
> T4	write_loose_object() is called
> ...	enter the write loop
> T5+n	deflate() called on buffer n
> T6+n	git_SHA1_Update(() called on the same buffer n
> T7+n	deflated data written out
> ...
> Tend	abort if result of T6+n doesn't match object name from T3
>
> So... what can happen:
>
> 1) Data is externally modified before T5+n: deflated data and its CRC32 
>    will be coherent with the SHA1 computed in T6+n, but incoherent with 
>    the SHA1 used for the object name. Wrong data is written to the 
>    object even if it will inflate OK. We really want to prevent that 
>    from happening. The test in Tend will fail.
>
> 2) Data is externally modified between T5+n and T6+n: the deflated data 
>    and CRC32 will be coherent with the object name but incoherent with 
>    the parano_sha1.  Although written data will be OK, this is way too 
>    close from being wrong, and the test in Tend will fail.  If there is 
>    more than one round into the loop and the external modifications are 
>    large enough then this becomes the same as case 1 above.
>
> 3) Data is externally modified in T2: again the test in Tend will fail.
>
> So in all possible cases I can think of, the write will abort.
There is one pathological case.

Immediately before T5+n (or between T5+n and T6+n), the external process changes the data deflate() is working on, but before T6+n, the external process changes the data back. Two SHA-1's computed may match, but it is not a hash over what was deflated(); you won't be able to abort.

Nicolas Pitre· Feb 22, 2010, 05:50 UTC · re: Junio C Hamano · lore
On Sun, 21 Feb 2010, Junio C Hamano wrote:
Show 46 quoted lines
> Nicolas Pitre <nico@fluxnic.net> writes:
> 
> > The whole point is to detect data incoherencyes.
> 
> Yes.  We want to make sure that the SHA-1 we compute is over what we fed
> deflate().
> 
> > So current sequence of events is as follows:
> >
> > T0	write_sha1_file_prepare() is called
> > T1	start initial SHA1 computation on data buffer
> > T2	in the middle of initial SHA1 computation
> > T3	end of initial SHA1 computation -> object name is determined
> > T4	write_loose_object() is called
> > ...	enter the write loop
> > T5+n	deflate() called on buffer n
> > T6+n	git_SHA1_Update(() called on the same buffer n
> > T7+n	deflated data written out
> > ...
> > Tend	abort if result of T6+n doesn't match object name from T3
> >
> > So... what can happen:
> >
> > 1) Data is externally modified before T5+n: deflated data and its CRC32 
> >    will be coherent with the SHA1 computed in T6+n, but incoherent with 
> >    the SHA1 used for the object name. Wrong data is written to the 
> >    object even if it will inflate OK. We really want to prevent that 
> >    from happening. The test in Tend will fail.
> >
> > 2) Data is externally modified between T5+n and T6+n: the deflated data 
> >    and CRC32 will be coherent with the object name but incoherent with 
> >    the parano_sha1.  Although written data will be OK, this is way too 
> >    close from being wrong, and the test in Tend will fail.  If there is 
> >    more than one round into the loop and the external modifications are 
> >    large enough then this becomes the same as case 1 above.
> >
> > 3) Data is externally modified in T2: again the test in Tend will fail.
> >
> > So in all possible cases I can think of, the write will abort.
> 
> There is one pathological case.
> 
> Immediately before T5+n (or between T5+n and T6+n), the external process
> changes the data deflate() is working on, but before T6+n, the external
> process changes the data back.  Two SHA-1's computed may match, but it is
> not a hash over what was deflated(); you won't be able to abort.

And what real life case would trigger this? Given the size of the window for this to happen, what are your chances?

Of course the odds for me to be struck by lightning also exist. And if I work really really hard at it then I might be able to trigger that pathological case above even before the next thunderstorm. But in practice I'm hardly concerned by either of those possibilities.

Nicolas
Junio C Hamano· Feb 22, 2010, 06:17 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
> And what real life case would trigger this?  Given the size of the 
> window for this to happen, what are your chances?
> Of course the odds for me to be struck by lightning also exist.  And if 
> I work really really hard at it then I might be able to trigger that 
> pathological case above even before the next thunderstorm.  But in 
> practice I'm hardly concerned by either of those possibilities.

The real life case for any of this triggers for me is zero, as I won't be mistreating git as a continuous & asynchronous back-up tool.

But then that would make the whole discussion moot. There are people who file "bug reports" with an artificial reproduction recipe built around a loop that runs dd continuously overwriting a file while "git add" is asked to add it.

Junio C Hamano· Feb 22, 2010, 06:31 UTC · re: Junio C Hamano · lore
Junio C Hamano <gitster@pobox.com> writes:
Show 17 quoted lines
> Nicolas Pitre <nico@fluxnic.net> writes:
>
>> And what real life case would trigger this?  Given the size of the 
>> window for this to happen, what are your chances?
>
>> Of course the odds for me to be struck by lightning also exist.  And if 
>> I work really really hard at it then I might be able to trigger that 
>> pathological case above even before the next thunderstorm.  But in 
>> practice I'm hardly concerned by either of those possibilities.
>
> The real life case for any of this triggers for me is zero, as I won't be
> mistreating git as a continuous & asynchronous back-up tool.
>
> But then that would make the whole discussion moot.  There are people who
> file "bug reports" with an artificial reproduction recipe built around a
> loop that runs dd continuously overwriting a file while "git add" is asked
> to add it.

Having said all that, I like your approach better. It is not worth paying the price of unnecessary memcpy(3) that would _only_ help catching the insanely artificial test case, but your patch strikes a good balance of small overhead to catch the easier-to-trigger (either by stupidity, malice or mistake) cases.

So I am tempted to discard the "paranoia" patch, and replace with your two patches, with the following caveats in the log message.

--- /var/tmp/2 2010-02-21 22:23:30.000000000 -0800 +++ /var/tmp/1 2010-02-21 22:23:22.000000000 -0800

Show changes to diff +3 −1
@@ -21,7 +21,9 @@
     deflate operation has consumed that data, and make sure it matches
     with the expected SHA1.  This way we can rely on the CRC32 checked by
     the inflate operation to provide a good indication that the data is still
-    coherent with its SHA1 hash.
+    coherent with its SHA1 hash.  One pathological case we ignore is when
+    the data is modified before (or during) deflate call, but changed back
+    before it is hashed.
     
     There is some overhead of course. Using 'git add' on a set of large files:
Nicolas Pitre· Feb 22, 2010, 17:36 UTC · re: Junio C Hamano · lore
On Sun, 21 Feb 2010, Junio C Hamano wrote:
Show 25 quoted lines
> Junio C Hamano <gitster@pobox.com> writes:
> 
> > Nicolas Pitre <nico@fluxnic.net> writes:
> >
> >> And what real life case would trigger this?  Given the size of the 
> >> window for this to happen, what are your chances?
> >
> >> Of course the odds for me to be struck by lightning also exist.  And if 
> >> I work really really hard at it then I might be able to trigger that 
> >> pathological case above even before the next thunderstorm.  But in 
> >> practice I'm hardly concerned by either of those possibilities.
> >
> > The real life case for any of this triggers for me is zero, as I won't be
> > mistreating git as a continuous & asynchronous back-up tool.
> >
> > But then that would make the whole discussion moot.  There are people who
> > file "bug reports" with an artificial reproduction recipe built around a
> > loop that runs dd continuously overwriting a file while "git add" is asked
> > to add it.
> 
> Having said all that, I like your approach better.  It is not worth paying
> the price of unnecessary memcpy(3) that would _only_ help catching the
> insanely artificial test case, but your patch strikes a good balance of
> small overhead to catch the easier-to-trigger (either by stupidity, malice
> or mistake) cases.

I think it also catches the bad RAM case which is probably more common too.

Show 13 quoted lines
> So I am tempted to discard the "paranoia" patch, and replace with your two
> patches, with the following caveats in the log message.
> 
> --- /var/tmp/2	2010-02-21 22:23:30.000000000 -0800
> +++ /var/tmp/1	2010-02-21 22:23:22.000000000 -0800
> @@ -21,7 +21,9 @@
>      deflate operation has consumed that data, and make sure it matches
>      with the expected SHA1.  This way we can rely on the CRC32 checked by
>      the inflate operation to provide a good indication that the data is still
> -    coherent with its SHA1 hash.
> +    coherent with its SHA1 hash.  One pathological case we ignore is when
> +    the data is modified before (or during) deflate call, but changed back
> +    before it is hashed.
ACK.
Nicolas
Junio C Hamano· Feb 22, 2010, 19:55 UTC · re: Nicolas Pitre · lore
Nicolas Pitre <nico@fluxnic.net> writes:
Show 8 quoted lines
>> Having said all that, I like your approach better.  It is not worth paying
>> the price of unnecessary memcpy(3) that would _only_ help catching the
>> insanely artificial test case, but your patch strikes a good balance of
>> small overhead to catch the easier-to-trigger (either by stupidity, malice
>> or mistake) cases.
>
> I think it also catches the bad RAM case which is probably more common 
> too.

That is true; a broken RAM that returns unstable values will yield different values between the time the first hash runs and the time the deflate loop runs will trigger the safety.

Dmitry Potapov· Feb 22, 2010, 06:27 UTC · re: Nicolas Pitre · lore
On Mon, Feb 22, 2010 at 12:50:18AM -0500, Nicolas Pitre wrote:
> 
> And what real life case would trigger this?  Given the size of the 
> window for this to happen, what are your chances?

If some process changes just one byte (or one word) back and forth then the possibility of this is 25%. Whether such a process can exist, I don't know... I could not imagine that anyone would want to change the file when we add it to the repository. In any case, it is wrong to call it a _paranoic_ mode if there is even a small (but practically feasable) chance of this to happen.

Dmitry

← back to recent threads