{"thread":{"id":"5432","subject":"Re: Mozilla .git tree","startedAt":"2006-08-30T01:51:22Z","lastAt":"2006-09-05T08:12:35Z","messageCount":52,"participants":["Shawn Pearce","Jon Smirl","Nicolas Pitre","Junio C Hamano","A Large Angry SCM","Linus Torvalds","Johannes Schindelin","Sam Ravnborg"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26102","messageId":"20060830015122.GE22935@spearce.org","threadId":"5432","inReplyTo":"9e4733910608291807q9b896e4sdbfaa9e49de58c2b@mail.gmail.com","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-30T01:51:22Z","receivedAt":"2006-08-30T01:51:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> I suspect the bulk of the file will be the base blobs. A zlib\n> dictionary would help more with the trees and the 120K copies of the\n> GPL in the files.\n\nHere's what I got by taking the output of verify-pack -v run\nagainst the 430 MiB Mozilla pack and running that through a simple\nPerl script:\n\n COUNT BASE commit: 197613\n COUNT BASE tree: 154496\n COUNT BASE blob: 49860\n COUNT BASE tag: 1203\n COUNT DELTA commit: 3308\n COUNT DELTA tree: 976712\n COUNT DELTA blob: 579780\n COUNT DELTA tag: 353\n\nThose are just raw numbers of objects of each type broken out by\nbase and delta. We gotta alotta objects. :-)\n\nWe probably also have around 49,860 copies of the identical license\ntext (one per base object). I'm just assuming the xdelta algorithm\nwould recognize the identical run in the dependent object and\ncopy it from the base rather than use a literal insert command.\nThus I'm assuming the 579,780 deltas don't contain the license text.\n\n UNCOMP BASE commit: 55 MiB\n UNCOMP BASE tree: 30 MiB\n UNCOMP BASE blob: 597 MiB\n UNCOMP BASE tag: 0 MiB\n UNCOMP DELTA commit: 0 MiB\n UNCOMP DELTA tree: 44 MiB\n UNCOMP DELTA blob: 190 MiB\n UNCOMP DELTA tag: 0 MiB\n\nThese are the sizes of the objects and deltas prior to using zlib\nto deflate them (aka the decompression buffer size, stored in the\nobject header).\n\n ZIPPED BASE commit: 38 MiB\n ZIPPED BASE tree: 26 MiB\n ZIPPED BASE blob: 164 MiB\n ZIPPED BASE tag: 0 MiB\n ZIPPED DELTA commit : 0 MiB\n ZIPPED DELTA tree: 73 MiB\n ZIPPED DELTA blob: 126 MiB\n ZIPPED DELTA tag: 0 MiB\n\nThese are the sizes of the objects within the pack, determined by\ncomputing the difference in adjacent objects' offsets.\n\n\n55 MiB of commits compressed into 38 MiB (saved 30%).\nWe can probably do better.\n\n30 MiB of tree bases compressed into 26 MiB (saved 13.3%).\nWith 154,496 tree bases I think we can do better _somehow_. It may\njust mean using more deltas so we have less bases. We don't have\n154k unique directories. It may just mean using a tree specific\npack dictionary is enough.\n\n44 MiB of tree deltas compressed into 73 MiB (saved -65.9%).\nOuch! We wasted 29 MiB by trying to compress tree deltas.\nWay to go zlib!\n\nBlob bases were 597 MiB uncompressed, 164 MiB compressed (saved 72%).\nBlob deltas were 190 MiB uncompressed, 126 MiB compressed (saved 33%).\nWe might be able to do better here, but we're already fairing pretty\nwell.\n\n\nTo compare a .tar.gz of the ,v files from CVS is around 550 MiB.\nWe're already smaller than that in a pack file. But ,v is not the\nmost compact representation. I hoped we could do even better than\n430 MiB.\n\n\nI ran the same script against my Git pack. There I'm seeing the\nsame explosion of tree deltas: uncompressed they are 1380174 bytes,\ncompressed they are 1620439 bytes (-17.4% saved).\n\nWe may well have a general problem here with always compressing\ntree deltas. It appears to be a minor dent in the space required\nfor a pack but its certainly a non-trivial amount on the larger\nMozilla pack. The wasted space is 2% of the Git pack and its 6.7%\nof the Mozilla pack.\n\n-- \nShawn.\n"},{"id":"26103","messageId":"20060830022534.GF22935@spearce.org","threadId":"5432","inReplyTo":"20060830015122.GE22935@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-30T02:25:34Z","receivedAt":"2006-08-30T02:25:34Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Shawn Pearce wrote:\n> We may well have a general problem here with always compressing\n> tree deltas. It appears to be a minor dent in the space required\n> for a pack but its certainly a non-trivial amount on the larger\n> Mozilla pack. The wasted space is 2% of the Git pack and its 6.7%\n> of the Mozilla pack.\n\nWhoops.\n\nmugwump (Sam Vilain) just pointed out on #git that I didn't account\nfor the 20 byte base when comparing the offset differences (claimed\ncompressed size) and the uncompressed size. Nor did I account for\nthe variable sized headers.\n\nI stated that 29 MiB of the Mozilla pack was wasted by 976712\ntree deltas. Of that 29 MiB we know that 18.6 MiB must be the\n20 byte base-SHA1 header. That leaves 10.4 MiB unaccounted for.\nBut we also have the variable length header; lets say the average\nuncompressed length of a tree delta is 44 MiB/976712 so 47 bytes.\nThat average length can be encoded in two header bytes, so that's\nanother 1.8 MiB. Which leaves us with 8.6 MiB of wasted space.\n\nWhich is clearly not the 29 MiB I previously stated. But we're\nstill wasting a small amount of space over not compressing them.\n\n-- \nShawn.\n"},{"id":"26104","messageId":"9e4733910608291958l45c0257dla6e5ebd4176f7164@mail.gmail.com","threadId":"5432","inReplyTo":"20060830015122.GE22935@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-30T02:58:58Z","receivedAt":"2006-08-30T02:58:58Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"sha1s are effectively 20 byte pointer addresses into the pack. With 2M\nobjects you can easily get away with 4 byte address and a mapping\ntable. Another idea would be to replace the 20 byte sha1 in tree\nobjects with 32b file offsets - requiring that anything the tree\nrefers to has to already be in the pack before the tree entry can be\nwritten.\n\n\nOn 8/29/06, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > I suspect the bulk of the file will be the base blobs. A zlib\n> > dictionary would help more with the trees and the 120K copies of the\n> > GPL in the files.\n>\n> Here's what I got by taking the output of verify-pack -v run\n> against the 430 MiB Mozilla pack and running that through a simple\n> Perl script:\n>\n> COUNT BASE commit: 197613\n> COUNT BASE tree: 154496\n> COUNT BASE blob: 49860\n> COUNT BASE tag: 1203\n> COUNT DELTA commit: 3308\n> COUNT DELTA tree: 976712\n> COUNT DELTA blob: 579780\n> COUNT DELTA tag: 353\n>\n> Those are just raw numbers of objects of each type broken out by\n> base and delta. We gotta alotta objects. :-)\n>\n> We probably also have around 49,860 copies of the identical license\n> text (one per base object). I'm just assuming the xdelta algorithm\n\nThe Mozilla license has changed at least five times. That makes 250K\ncopies of licenses.\n\n> would recognize the identical run in the dependent object and\n> copy it from the base rather than use a literal insert command.\n> Thus I'm assuming the 579,780 deltas don't contain the license text.\n>\n> UNCOMP BASE commit: 55 MiB\n> UNCOMP BASE tree: 30 MiB\n> UNCOMP BASE blob: 597 MiB\n> UNCOMP BASE tag: 0 MiB\n> UNCOMP DELTA commit: 0 MiB\n> UNCOMP DELTA tree: 44 MiB\n> UNCOMP DELTA blob: 190 MiB\n> UNCOMP DELTA tag: 0 MiB\n>\n> These are the sizes of the objects and deltas prior to using zlib\n> to deflate them (aka the decompression buffer size, stored in the\n> object header).\n>\n> ZIPPED BASE commit: 38 MiB\n> ZIPPED BASE tree: 26 MiB\n> ZIPPED BASE blob: 164 MiB\n> ZIPPED BASE tag: 0 MiB\n> ZIPPED DELTA commit : 0 MiB\n> ZIPPED DELTA tree: 73 MiB\n> ZIPPED DELTA blob: 126 MiB\n> ZIPPED DELTA tag: 0 MiB\n>\n> These are the sizes of the objects within the pack, determined by\n> computing the difference in adjacent objects' offsets.\n>\n>\n> 55 MiB of commits compressed into 38 MiB (saved 30%).\n> We can probably do better.\n>\n> 30 MiB of tree bases compressed into 26 MiB (saved 13.3%).\n> With 154,496 tree bases I think we can do better _somehow_. It may\n> just mean using more deltas so we have less bases. We don't have\n> 154k unique directories. It may just mean using a tree specific\n> pack dictionary is enough.\n\nI suspect a tree specific zlib dictionary will be a good win. But\nthose trees contain a lot of uncompressible data, the sha1. Those\nsha1s are in binary not hex, right?\n\n>\n> 44 MiB of tree deltas compressed into 73 MiB (saved -65.9%).\n> Ouch! We wasted 29 MiB by trying to compress tree deltas.\n> Way to go zlib!\n\nThe git tools can be modified to set the compression level to 0 before\ncompressing tree deltas. There is no need to change the decoding code.\nEven with compression level 0 they still get slightly larger because\nzlib tacks on a header.\n\n>\n> Blob bases were 597 MiB uncompressed, 164 MiB compressed (saved 72%).\n> Blob deltas were 190 MiB uncompressed, 126 MiB compressed (saved 33%).\n> We might be able to do better here, but we're already fairing pretty\n> well.\n>\n>\n> To compare a .tar.gz of the ,v files from CVS is around 550 MiB.\n> We're already smaller than that in a pack file. But ,v is not the\n> most compact representation. I hoped we could do even better than\n> 430 MiB.\n>\n>\n> I ran the same script against my Git pack. There I'm seeing the\n> same explosion of tree deltas: uncompressed they are 1380174 bytes,\n> compressed they are 1620439 bytes (-17.4% saved).\n>\n> We may well have a general problem here with always compressing\n> tree deltas. It appears to be a minor dent in the space required\n> for a pack but its certainly a non-trivial amount on the larger\n> Mozilla pack. The wasted space is 2% of the Git pack and its 6.7%\n> of the Mozilla pack.\n\nI'm still interested in getting an idea of how much a Clucene type\ndictionary compression would help. It is hard to see how you can get\nsmaller than that method. Note that you don't want to include the\nindexing portion of Clucene in the comparison. Just the part where\neverything gets tokenized into a big dictionary, arithmetic encoded\nbased on usage frequency, and then the strings in the orginal\ndocuments are replaced with the codes. You want to do the diffs before\nreplacing everything with codes. Encoding this way is a two pass\nprocess so it is easiest to work from an existing pack.\n\nThe indexing phase then constructs a bit vector for each word\nrepresenting all of the documents in the archive and whether they\ncontain the word or not. The vectors are then compressed using\nsomething similar to zlib. To query you and/or/not the word vectors\ntogether to identify candidate documents. There are algorithms for\ncombining the compressed vectors without decompressing them.\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26105","messageId":"20060830031029.GA23967@spearce.org","threadId":"5432","inReplyTo":"9e4733910608291958l45c0257dla6e5ebd4176f7164@mail.gmail.com","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-30T03:10:29Z","receivedAt":"2006-08-30T03:10:29Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> sha1s are effectively 20 byte pointer addresses into the pack. With 2M\n> objects you can easily get away with 4 byte address and a mapping\n> table. Another idea would be to replace the 20 byte sha1 in tree\n> objects with 32b file offsets - requiring that anything the tree\n> refers to has to already be in the pack before the tree entry can be\n> written.\n\nI've thought of that, but when you transfer a \"thin\" pack over the\nwire the base object may not even be in the pack. Thus you can't\nuse an offset to reference it. Otherwise there's probably little\nreason why the base couldn't be referenced by its 4 byte offset\nrather than its full 20 byte object ID. Added up over all deltas\nin the mozilla pack it saves a whopping 23 MiB.\n\n> The Mozilla license has changed at least five times. That makes 250K\n> copies of licenses.\n\nCute.\n \n> I suspect a tree specific zlib dictionary will be a good win. But\n> those trees contain a lot of uncompressible data, the sha1. Those\n> sha1s are in binary not hex, right?\n\nYup, binary.\n \n> The git tools can be modified to set the compression level to 0 before\n> compressing tree deltas. There is no need to change the decoding code.\n> Even with compression level 0 they still get slightly larger because\n> zlib tacks on a header.\n\nSee my followup email to myself; I think we're talking a zlib\noverhead of 9.2 bytes on average per tree delta. That's with a\ncompression level of -1 (default, which is 6).\n \n> I'm still interested in getting an idea of how much a Clucene type\n> dictionary compression would help. It is hard to see how you can get\n> smaller than that method. Note that you don't want to include the\n> indexing portion of Clucene in the comparison. Just the part where\n> everything gets tokenized into a big dictionary, arithmetic encoded\n> based on usage frequency, and then the strings in the orginal\n> documents are replaced with the codes. You want to do the diffs before\n> replacing everything with codes. Encoding this way is a two pass\n> process so it is easiest to work from an existing pack.\n\n>From what I was able to gather I don't think Clucene stores the\ndocuments themselves as the tokenized compressed data. Or if it\ndoes you lose everything between the tokens. There's a number of\nthings we want to preserve in the original \"document\" like whitespace\nthat would be likely stripped when constructing tokens.\n\nBut it shouldn't be that difficult to produce a rough estimate of\nwhat that storage size would be.\n \n-- \nShawn.\n"},{"id":"26106","messageId":"9e4733910608292027v46eb5db4y3e2c4cbeed8d5f92@mail.gmail.com","threadId":"5432","inReplyTo":"20060830031029.GA23967@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-30T03:27:08Z","receivedAt":"2006-08-30T03:27:08Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/29/06, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > sha1s are effectively 20 byte pointer addresses into the pack. With 2M\n> > objects you can easily get away with 4 byte address and a mapping\n> > table. Another idea would be to replace the 20 byte sha1 in tree\n> > objects with 32b file offsets - requiring that anything the tree\n> > refers to has to already be in the pack before the tree entry can be\n> > written.\n>\n> I've thought of that, but when you transfer a \"thin\" pack over the\n> wire the base object may not even be in the pack. Thus you can't\n> use an offset to reference it. Otherwise there's probably little\n> reason why the base couldn't be referenced by its 4 byte offset\n> rather than its full 20 byte object ID. Added up over all deltas\n> in the mozilla pack it saves a whopping 23 MiB.\n\nEvery time an object goes on the wire these 'pack internal'\noptimizations need to be undone. If you are sending the whole pack\neverything can be sent as is.\n\nThese intense compression schemes are meant for archival level data.\nEverybody should end up with a copy of the entire archive and that\nwill be the end of those objects moving on the wire.\n\n> From what I was able to gather I don't think Clucene stores the\n> documents themselves as the tokenized compressed data. Or if it\n> does you lose everything between the tokens. There's a number of\n> things we want to preserve in the original \"document\" like whitespace\n> that would be likely stripped when constructing tokens.\n\nI can't remember if the Clucene code includes the ability to compress\nusing the dictionary. I had thought that the code was in there but\nmaybe not. Things that aren't in the dictionary use an escape code and\nare copied intact. I have the Lucene book on my desk, I'll flip\nthrough it and see what it says.\n\nMight be worthwhile to poke around on the net and see if you can come\nup with an existing dictionary based compressor. There has got to be\none out there, this is a 30 year old concept.\n\n> But it shouldn't be that difficult to produce a rough estimate of\n> what that storage size would be.\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"26108","messageId":"Pine.LNX.4.64.0608300124550.9796@xanadu.home","threadId":"5432","inReplyTo":"20060830031029.GA23967@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-30T05:53:48Z","receivedAt":"2006-08-30T05:53:48Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 29 Aug 2006, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > The git tools can be modified to set the compression level to 0 before\n> > compressing tree deltas. There is no need to change the decoding code.\n> > Even with compression level 0 they still get slightly larger because\n> > zlib tacks on a header.\n> \n> See my followup email to myself; I think we're talking a zlib\n> overhead of 9.2 bytes on average per tree delta. That's with a\n> compression level of -1 (default, which is 6).\n\nIn fact, the bulk of a tree delta is most likely to contain the \nliteral sha1 of one or more directory entries that changed, and this is \nhardly compressible. There is nothing to gain by forcing zlib level to \n0 for tree deltas since it never makes the deflated stream smaller from \nthe tests I've performed in the past. It seems that zlib is smart \nenough not to attempt any compression when there is no gain. That \nleaves the zlib header as the only overhead.\n\nAnd the zlib header contains a CRC which we're about to use for \nvalidating the data when doing delta data reuse in order to prevent pack \ncorruption propagation like the one recently posted on the list. \nWithout that a pack corruption (from a bad disk sector for example) is \nlikely to go unnoticed when doing a repack. The data could be validated \nby expanding deltas and verifying the sha1 on the end result but this is \na really expensive operation if performed on all deltas which is best \nleft to git-fsck-objects --full. So I think the small overhead relative \nto total pack size might be worth it for better data integrity.\n\nUsing an offset instead of a sha1 to reference a delta base object is \ncertainly a good idea though. But I'd use the same variable encoding as \nthe object size to avoid the 32-bit limit issue. When generating a thin \npack the real sha1 of the delta object could be substituted for the \noffset quite easily if the base object is not sent a part of the same \npack.\n\n\nNicolas\n"},{"id":"26110","messageId":"7vzmdmh2lu.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0608300124550.9796@xanadu.home","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-30T11:42:05Z","receivedAt":"2006-08-30T11:42:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> And the zlib header contains a CRC which we're about to use for \n> validating the data when doing delta data reuse in order to prevent pack \n> corruption propagation like the one recently posted on the list. \n\nAh, never thought of using the CRC directly. I was thinking\nabout inflating into void and see if it succeeds, which as you\nsay is perhaps quite expensive.\n\nThis brings me back to my pet-peeve, though. I do not think\nzlib stream seeks back and leaves some clue at the beginning to\ntell me the deflated length, so it is quite hard to find where\neach deflated stream ends in a packfile cheaply. Loose objects\n(with new or legacy style header) are easy (st.st_size is\navailable), but I do not think of a way short of building a\nreverse index of pack .idx file, which means I am already\ntalking about not so cheap way X-<.\n\nIt might be a reason to define a new .idx format. We could lift\n32-bit offset limitation while we are at it. Each entry could\nhave 20-byte hash, 64-bit offset into the corresponding .pack,\nand 32-bit deflated length (heh, why not make it 64-bit while we\nare at it). Luckily, .idx _is_ a local matter so we can even\nhave a flag day and tell people to run the updated index-pack on\nexisting packfiles to regenerate .idx.\n\n> Using an offset instead of a sha1 to reference a delta base object is \n> certainly a good idea though. But I'd use the same variable encoding as \n> the object size to avoid the 32-bit limit issue. When generating a thin \n> pack the real sha1 of the delta object could be substituted for the \n> offset quite easily if the base object is not sent a part of the same \n> pack.\n\nThat sounds quite a reasonable suggestion. I love this kind of\nmoment when I find us very fortunate to have bright people on\nthe list ;-).\n"},{"id":"26180","messageId":"7vr6yw58xp.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"7vzmdmh2lu.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-01T07:42:58Z","receivedAt":"2006-09-01T07:42:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Nicolas Pitre writes:\n>\n>> And the zlib header contains a CRC which we're about to use for \n>> validating the data when doing delta data reuse in order to prevent pack \n>> corruption propagation like the one recently posted on the list. \n>\n> Ah, never thought of using the CRC directly. I was thinking\n> about inflating into void and see if it succeeds, which as you\n> say is perhaps quite expensive.\n>\n> This brings me back to my pet-peeve, though. I do not think\n> zlib stream seeks back and leaves some clue at the beginning to\n> tell me the deflated length, so it is quite hard to find where\n> each deflated stream ends in a packfile cheaply. Loose objects\n> (with new or legacy style header) are easy (st.st_size is\n> available), but I do not think of a way short of building a\n> reverse index of pack .idx file, which means I am already\n> talking about not so cheap way X-<.\n>\n> It might be a reason to define a new .idx format. We could lift\n> 32-bit offset limitation while we are at it. Each entry could\n> have 20-byte hash, 64-bit offset into the corresponding .pack,\n> and 32-bit deflated length (heh, why not make it 64-bit while we\n> are at it). Luckily, .idx _is_ a local matter so we can even\n> have a flag day and tell people to run the updated index-pack on\n> existing packfiles to regenerate .idx.\n\nSo I whipped up this as the zeroth step to propose a migration\nplan:\n\n Step 0. Prepare conversion and debugging tool.\n\n Step 1. Prepare sha1_file (consumer) side to understand the\n \t idx file in the new format. I haven't decided if\n \t making the runtime to understand both formats is\n \t feasible; I believe it is with what we currently do,\n \t but finding out where the end of each pack entry\n \t cheaply was one of the side effects I wanted to get\n \t from this conversion whose primary purpose is to bust\n \t the 4GB ceiling\n\n Step 2. Update pack-objects and index-pack to emit the new\n\t format.\n\n Step 3. Work on integrating partial mmap() support with Shawn.\n This is more or less orthogonal to 4GB ceiling (people\n would hit mmap() limit even with a 1.5GB pack), but I\n suspect it would be necessary to be able to tell where\n the end of each pack entry is cheaply to implement\n this.\n\nThis patch is step 0.\n\n-- >8 --\nSubject: [PATCH] convert-idx: prepare large pack idx support.\n\nThis adds git-convert-idx which converts between the traditional\n32-bit offset pack .idx file and the new 64-bit offset pack .idx\nfile, and updates git-show-index to understand both formats.\n\nDon't get too excited, not just yet. The programs pack-objects\nand index-pack need to be updated to produce 64-bit pack .idx\nfiles, and the core sha1_file routines also needs to be told\nabout the new format.\n\nSigned-off-by: Junio C Hamano \n---\n Makefile | 1 \n builtin-convert-idx.c | 351 +++++++++++++++++++++++++++++++++++++++++++++++++\n builtin.h | 1 \n git.c | 1 \n show-index.c | 36 ++++-\n 5 files changed, 384 insertions(+), 6 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 05bd77f..fccf747 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -260,6 +260,7 @@ BUILTIN_OBJS = \\\n \tbuiltin-check-ref-format.o \\\n \tbuiltin-commit-tree.o \\\n \tbuiltin-count-objects.o \\\n+\tbuiltin-convert-idx.o \\\n \tbuiltin-diff.o \\\n \tbuiltin-diff-files.o \\\n \tbuiltin-diff-index.o \\\ndiff --git a/builtin-convert-idx.c b/builtin-convert-idx.c\nnew file mode 100644\nindex 0000000..af111d2\n--- /dev/null\n+++ b/builtin-convert-idx.c\n@@ -0,0 +1,351 @@\n+#include \"cache.h\"\n+\n+/*****************************************************************\n+\n+The differences between the original and new style pack-*.idx files\n+are as follows:\n+\n+ - A new style .idx file can record 64-bit offsets into corresponding\n+ .pack file (an original .idx has 32-bit offsets hence limiting the\n+ .pack file to 4GB).\n+\n+ - A new style .idx file allows finding out the end of one entry in\n+ the .pack (you need to find the object with next offset in an\n+ original .idx file).\n+\n+Other than these major differences, the overall structure is quite\n+similar.\n+\n+A new style .idx file begins with a signature, \"\\377tOc\", and a\n+version number as a 4-byte network byte order integer. The version\n+of this implementation is 2.\n+\n+The location of the signature used to hold the number of objects in\n+the pack whose object name start with byte 0x00 as a 4-byte integer in\n+the network byte order. The original .idx format allowed only 32-bit\n+offset into the pack, and data for 0xFF744F63 objects would certainly\n+exceed 4GB (because an object needs at least 1-byte for type and its\n+deflated length, and deflated data will be 1 or more bytes), so the\n+older git would not mistake the new style .idx file as something\n+valid.\n+\n+Following the signature and the version number is a header, which\n+consists of 256 4-byte network byte order integers. N-th entry of\n+this table records the number of objects in the corresponding pack,\n+the first byte of whose object name are smaller than N. This means a\n+.pack file is still limited to maximum 4 billion objects.\n+\n+The header is followed by the main toc table, which is a list of\n+N-byte entries, one entry per object in the pack, sorted by the object\n+name. Each entry is:\n+\n+ . 8-byte network byte order integer, recording where the object is\n+ stored in the packfile as the offset from the beginning.\n+\n+ . 4-byte network byte order integer, recording the location of the\n+ next object in the main toc table.\n+\n+ . 20-byte object name.\n+\n+The file is concluded with a trailer:\n+\n+ . A copy of the 20-byte SHA-1 checksum at the end of the\n+ corresponding packfile.\n+\n+ . 20-byte SHA-1 checksum of all of the above.\n+\n+******************************************************************/\n+\n+#define PACK_IDX_SIGNATURE\t0xFF744F63 /* \"\\377tOc\" */\n+#define PACK_IDX_VERSION\t2\n+\n+static unsigned get4(const void *buf, unsigned long offset)\n+{\n+\tconst unsigned char *p = ((const unsigned char *)buf) + offset;\n+\n+\treturn (p[3] | (p[2]<<8) | (p[1]<<16) | (p[0]<<24));\n+}\n+\n+static unsigned long long get8(const void *buf, unsigned long offset)\n+{\n+\tunsigned long long n, m;\n+\tn = get4(buf, offset);\n+\tm = get4(buf, offset + 4);\n+\treturn (n << 32) | m;\n+}\n+\n+static void put4(void *buf, unsigned long offset, unsigned data)\n+{\n+\tunsigned char *p = ((unsigned char *)buf) + offset;\n+\n+\tp[3] = data; data >>= 8;\n+\tp[2] = data; data >>= 8;\n+\tp[1] = data; data >>= 8;\n+\tp[0] = data;\n+}\n+\n+static void put8(void *buf, unsigned long offset, unsigned long long data)\n+{\n+\tput4(buf, offset, data >> 32);\n+\tput4(buf, offset + 4, data);\n+}\n+\n+static int write_out(const char *path, void *data, unsigned long sz)\n+{\n+\tchar newpath[PATH_MAX];\n+\tint fd;\n+\n+\tif (PATH_MAX < strlen(path) + 10)\n+\t\treturn error(\"%s: pathname too long\", path);\n+\tsprintf(newpath, \"%s_XXXXXX\", path);\n+\tfd = mkstemp(newpath);\n+\tif (fd < 0)\n+\t\treturn error(\"%s: unable to create temporary file: %s\",\n+\t\t\t newpath, strerror(errno));\n+\twrite_or_die(fd, data, sz);\n+\treturn rename(newpath, path);\n+}\n+\n+static int downgrade_idx(const char *path, const unsigned char *data, unsigned long sz)\n+{\n+\tunsigned i, num = 0;\n+\tunsigned osz;\n+\tunsigned char *odata, *otable;\n+\tconst unsigned char *table;\n+\tunsigned char hash[20];\n+\tSHA_CTX ctx;\n+\n+\tif (get4(data, 0) != PACK_IDX_SIGNATURE)\n+\t\treturn error(\"%s is not a new style index\", path);\n+\tif (get4(data, 4) != 2)\n+\t\treturn error(\"%s: version %u of new style index not supported\",\n+\t\t\t path, get4(data, 4));\n+\n+\t/* Validate the fan-out and find out the number of objects */\n+\tfor (i = 0; i < 256; i++) {\n+\t\tunsigned n = get4(data + 8, i * 4);\n+\t\tif (n < num)\n+\t\t\treturn error(\"%s: corrupt old index file\", path);\n+\t\tnum = n;\n+\t}\n+\n+\t/* Make sure the sz is correct */\n+\tif (sz != 8 + 4 * 256 + 32 * num + 40)\n+\t\treturn error(\"%s: new index file with incorrect size\", path);\n+\n+\t/* Make sure the hash matches */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, data, sz - 20);\n+\tSHA1_Final(hash, &ctx);\n+\tif (memcmp(hash, data + sz - 20, 20))\n+\t\treturn error(\"%s: new index file with incorrect hash\", path);\n+\n+\tosz = 4 * 256 + 24 * num + 40;\n+\todata = xcalloc(1, osz);\n+\n+\t/* Convert the fan-out */\n+\tfor (i = 0; i < 256; i++)\n+\t\tput4(odata, i * 4, get4(data + 8, i * 4));\n+\n+\t/* Make them point at the main table */\n+\ttable = data + 4 * 256 + 8;\n+\totable = odata + 4 * 256;\n+\n+\t/* Convert entries, while validating that they are sorted */\n+\tfor (i = 0; i < num; i++) {\n+\t\tunsigned long long ofs = get8(table, 32 * i);\n+\t\tunsigned const char *hash1, *hash2;\n+\n+\t\tif (ofs & (0xFFFFFFFFLL << 32))\n+\t\t\treturn error(\"%s: the packfile is too big to be \"\n+\t\t\t\t \"indexed with an old index\", path);\n+\t\tput4(otable + 24 * i, 0, ofs);\n+\t\tmemcpy(otable + 24 * i + 4, table + 32 * i + 12, 20);\n+\t\tif (!i)\n+\t\t\tcontinue;\n+\t\thash1 = table + 32 * (i-1) + 12;\n+\t\thash2 = hash1 + 32;\n+\t\tif (0 <= memcmp(hash1, hash2, 20))\n+\t\t\treturn error(\"%s: new index file with unsorted table\",\n+\t\t\t\t path);\n+\t\tif (*hash1 != *hash2) {\n+\t\t\t/* fan-out of hash1[0] should point here */\n+\t\t\tif (get4(data + 8, *hash1 * 4) != i)\n+\t\t\t\treturn error(\"%s: old index file with \"\n+\t\t\t\t\t \"invalid fan-out\", path);\n+\t\t}\n+\t}\n+\n+\t/* Copy the pack SHA-1 checksum */\n+\tmemcpy(odata + osz - 40, data + sz - 40, 20);\n+\n+\t/* Compute the overall SHA-1 checksum */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, odata, osz - 20);\n+\tSHA1_Final(odata + osz - 20, &ctx);\n+\n+\t/* Write it out */\n+\treturn write_out(path, odata, osz);\n+}\n+\n+static int map_compare(const void *a_, const void *b_)\n+{\n+\t/* These point at new style table entry whose first element is\n+\t * 8-byte network byte order offset. Compare them\n+\t */\n+\tconst char *a = *((const char **)a_);\n+\tconst char *b = *((const char **)b_);\n+\tunsigned long long aofs, bofs;\n+\n+\taofs = get8(a, 0);\n+\tbofs = get8(b, 0);\n+\tif (aofs < bofs)\n+\t\treturn -1;\n+\tif (aofs == bofs)\n+\t\treturn 0;\n+\treturn 1;\n+}\n+\n+static int upgrade_idx(const char *path, const unsigned char *data, unsigned long sz)\n+{\n+\tconst unsigned char *table;\n+\tunsigned char *ndata, *ntable, **map;\n+\tunsigned i, num = 0;\n+\tunsigned nsz;\n+\tunsigned prev_ix;\n+\tunsigned char hash[20];\n+\tSHA_CTX ctx;\n+\n+\tif (get4(data, 0) == PACK_IDX_SIGNATURE)\n+\t\treturn error(\"%s is a new style index\", path);\n+\n+\t/* Validate the fan-out and find out the number of objects */\n+\tfor (i = 0; i < 256; i++) {\n+\t\tunsigned n = get4(data, i * 4);\n+\t\tif (n < num)\n+\t\t\treturn error(\"%s: corrupt old index file\", path);\n+\t\tnum = n;\n+\t}\n+\n+\t/* Make sure the sz is correct */\n+\tif (sz != 4 * 256 + 24 * num + 40)\n+\t\treturn error(\"%s: old index file with incorrect size\", path);\n+\n+\t/* Make sure the hash matches */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, data, sz - 20);\n+\tSHA1_Final(hash, &ctx);\n+\tif (memcmp(hash, data + sz - 20, 20))\n+\t\treturn error(\"%s: old index file with incorrect hash\", path);\n+\n+\tnsz = 8 + 4 * 256 + 32 * num + 40;\n+\tndata = xcalloc(1, nsz);\n+\tmap = xcalloc(sizeof(*map), num);\n+\n+\tput4(ndata, 0, PACK_IDX_SIGNATURE);\n+\tput4(ndata, 4, PACK_IDX_VERSION);\n+\n+\t/* Convert the fan-out */\n+\tfor (i = 0; i < 256; i++)\n+\t\tput4(ndata, 8 + i * 4, get4(data, i * 4));\n+\n+\t/* Make them point at the main table */\n+\ttable = data + 4 * 256;\n+\tntable = ndata + 8 + 4 * 256;\n+\n+\t/* Convert entries, while validating that they are sorted */\n+\tfor (i = 0; i < num; i++) {\n+\t\tunsigned ofs = get4(table, 24 * i);\n+\t\tunsigned const char *hash1, *hash2;\n+\t\tmap[i] = ntable + 32 * i;\n+\t\tput8(ntable + 32 * i, 0, ofs);\n+\t\tmemcpy(ntable + 32 * i + 12, table + 24 * i + 4, 20);\n+\t\tif (!i)\n+\t\t\tcontinue;\n+\t\thash1 = table + 24 * (i-1) + 4;\n+\t\thash2 = hash1 + 24;\n+\t\tif (0 <= memcmp(hash1, hash2, 20))\n+\t\t\treturn error(\"%s: old index file with unsorted table\",\n+\t\t\t\t path);\n+\t\tif (*hash1 != *hash2) {\n+\t\t\t/* fan-out of hash1[0] should point here */\n+\t\t\tif (get4(data, *hash1 * 4) != i)\n+\t\t\t\treturn error(\"%s: old index file with \"\n+\t\t\t\t\t \"invalid fan-out\", path);\n+\t\t}\n+\t}\n+\n+\t/* Using the reverse map, fill in the next object number */\n+\tqsort(map, num, sizeof(*map), map_compare);\n+\tprev_ix = (map[0] - ntable) / 32;\n+\tfor (i = 1; i < num; i++) {\n+\t\t/* map is an array of main table entry index,\n+\t\t * sorted by the offset of the pack data.\n+\t\t */\n+\t\tunsigned next_ix = (map[i] - ntable) / 32;\n+\t\tput4(ntable + 32 * prev_ix, 8, next_ix);\n+\t\tprev_ix = next_ix;\n+\t}\n+\tput4(map[num-1], 8, num); /* Mark the last entry with num */\n+\n+\t/* Copy the pack SHA-1 checksum */\n+\tmemcpy(ndata + nsz - 40, data + sz - 40, 20);\n+\n+\t/* Compute the overall SHA-1 checksum */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, ndata, nsz - 20);\n+\tSHA1_Final(ndata + nsz - 20, &ctx);\n+\n+\t/* Write it out */\n+\treturn write_out(path, ndata, nsz);\n+}\n+\n+static int convert_one(const char *path, int downgrade)\n+{\n+\tint fd, err;\n+\tstruct stat st;\n+\tvoid *map;\n+\n+\tfd = open(path, O_RDONLY);\n+\tif (fd < 0)\n+\t\treturn error(\"%s: cannot open: %s\", path, strerror(errno));\n+\tif (fstat(fd, &st)) {\n+\t\terr = errno;\n+\t\tclose(fd);\n+\t\treturn error(\"%s: cannot stat: %s\", path, strerror(err));\n+\t}\n+\tmap = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\terr = downgrade\n+\t\t? downgrade_idx(path, map, st.st_size)\n+\t\t: upgrade_idx(path, map, st.st_size);\n+\tmunmap(map, st.st_size);\n+\treturn err;\n+}\n+\n+static const char convert_idx_usage[] =\n+\"git-convert-idx [-d] \";\n+\n+int cmd_convert_idx(int ac, const char **av, const char *prefix)\n+{\n+\tint i, downgrade = 0, status = 0;\n+\n+\tfor (i = 1; i < ac; i++) {\n+\t\tconst char *arg = av[i];\n+\t\tif (arg[0] != '-')\n+\t\t\tbreak;\n+\t\tif (!strcmp(arg, \"--\")) {\n+\t\t\ti++;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (!strcmp(arg, \"-d\") || !strcmp(arg, \"--downgrade\")) {\n+\t\t\tdowngrade = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tusage(convert_idx_usage);\n+\t}\n+\n+\tfor ( ; i < ac; i++)\n+\t\tstatus |= convert_one(av[i], downgrade);\n+\treturn status;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex 25431d7..e282cb8 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -19,6 +19,7 @@ extern int cmd_cat_file(int argc, const \n extern int cmd_checkout_index(int argc, const char **argv, const char *prefix);\n extern int cmd_check_ref_format(int argc, const char **argv, const char *prefix);\n extern int cmd_commit_tree(int argc, const char **argv, const char *prefix);\n+extern int cmd_convert_idx(int ac, const char **av, const char *prefix);\n extern int cmd_count_objects(int argc, const char **argv, const char *prefix);\n extern int cmd_diff_files(int argc, const char **argv, const char *prefix);\n extern int cmd_diff_index(int argc, const char **argv, const char *prefix);\ndiff --git a/git.c b/git.c\nindex 05871ad..22dbad8 100644\n--- a/git.c\n+++ b/git.c\n@@ -230,6 +230,7 @@ static void handle_internal_command(int \n \t\t{ \"checkout-index\", cmd_checkout_index, RUN_SETUP },\n \t\t{ \"check-ref-format\", cmd_check_ref_format },\n \t\t{ \"commit-tree\", cmd_commit_tree, RUN_SETUP },\n+\t\t{ \"convert-idx\", cmd_convert_idx },\n \t\t{ \"count-objects\", cmd_count_objects },\n \t\t{ \"diff\", cmd_diff, RUN_SETUP },\n \t\t{ \"diff-files\", cmd_diff_files, RUN_SETUP },\ndiff --git a/show-index.c b/show-index.c\nindex c21d660..a00b691 100644\n--- a/show-index.c\n+++ b/show-index.c\n@@ -1,14 +1,28 @@\n #include \"cache.h\"\n \n+#define PACK_IDX_SIGNATURE\t0xFF744F63 /* \"\\377tOc\" */\n+#define PACK_IDX_VERSION\t2\n+\n int main(int argc, char **argv)\n {\n \tint i;\n \tunsigned nr;\n-\tunsigned int entry[6];\n+\tunsigned int entry[8];\n \tstatic unsigned int top_index[256];\n+\tint new_style = 0;\n \n \tif (fread(top_index, sizeof(top_index), 1, stdin) != 1)\n-\t\tdie(\"unable to read idex\");\n+\t\tdie(\"unable to read index\");\n+\n+\tif (ntohl(top_index[0]) == PACK_IDX_SIGNATURE) {\n+\t\tfprintf(stderr, \"new style idx version %u\\n\",\n+\t\t\tntohl(top_index[1]));\n+\t\tmemmove(top_index, top_index + 2, 4 * 254);\n+\t\tif (fread(top_index + 254, sizeof(unsigned), 2, stdin) != 2)\n+\t\t\tdie(\"unable to read index\");\n+\t\tnew_style = 1;\n+\t}\n+\n \tnr = 0;\n \tfor (i = 0; i < 256; i++) {\n \t\tunsigned n = ntohl(top_index[i]);\n@@ -16,13 +30,23 @@ int main(int argc, char **argv)\n \t\t\tdie(\"corrupt index file\");\n \t\tnr = n;\n \t}\n+\n \tfor (i = 0; i < nr; i++) {\n-\t\tunsigned offset;\n+\t\tunsigned long long offset;\n \n-\t\tif (fread(entry, 24, 1, stdin) != 1)\n+\t\tif (fread(entry,\n+\t\t\t new_style ? 32 : 24,\n+\t\t\t 1, stdin) != 1)\n \t\t\tdie(\"unable to read entry %u/%u\", i, nr);\n-\t\toffset = ntohl(entry[0]);\n-\t\tprintf(\"%u %s\\n\", offset, sha1_to_hex((void *)(entry+1)));\n+\t\tif (new_style) {\n+\t\t\toffset = ntohl(entry[0]);\n+\t\t\toffset = (offset << 32) | ntohl(entry[1]);\n+\t\t}\n+\t\telse {\n+\t\t\toffset = ntohl(entry[0]);\n+\t\t}\n+\t\tprintf(\"%llu %s\\n\", offset,\n+\t\t sha1_to_hex((void *)(entry + 1 + new_style * 2)));\n \t}\n \treturn 0;\n }\n-- \n1.4.2.gc9dce\n"},{"id":"26187","messageId":"44F871BA.3070303@gmail.com","threadId":"5432","inReplyTo":"7vzmdmh2lu.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2006-09-01T17:45:30Z","receivedAt":"2006-09-01T17:45:30Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"Junio C Hamano wrote:\n> Nicolas Pitre writes:\n> \n>> And the zlib header contains a CRC which we're about to use for \n>> validating the data when doing delta data reuse in order to prevent pack \n>> corruption propagation like the one recently posted on the list. \n> \n> Ah, never thought of using the CRC directly. I was thinking\n> about inflating into void and see if it succeeds, which as you\n> say is perhaps quite expensive.\n\nUnfortunately, the zlib CRC is of the _uncompressed_ data [1], so\ninflating the stream is still necessary to check for corruption.\n\n[1] RFC 1950, \"ZLIB Compressed Data Format Specification\", May 1996.\nPages 4-6.\n"},{"id":"26188","messageId":"Pine.LNX.4.64.0609011129270.27779@g5.osdl.org","threadId":"5432","inReplyTo":"44F871BA.3070303@gmail.com","subject":"Re: Mozilla .git tree","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-01T18:35:23Z","receivedAt":"2006-09-01T18:35:23Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 1 Sep 2006, A Large Angry SCM wrote:\n> \n> Unfortunately, the zlib CRC is of the _uncompressed_ data [1], so\n> inflating the stream is still necessary to check for corruption.\n\nI don't think that is unfortunate.\n\nWe really should inflate the stream anyway, since not only inflating it, \nbut also applying any deltas to the base object is really the only way to \nverify its correctness for a delta thing. Otherwise, the SHA1 of the base \ncould be totally corrupt.\n\nAnd once you inflate it and apply all deltas, you obviously also get the \nfull SHA1 check, so you're _really_ safe.\n\nSo let's do the really safe thing first, and see if it actually results in \nany problems.\n\nNOTE NOTE NOTE! We might well choose to do this checking _only_ when we \nwrite the index file (ie we have \"!pack_to_stdout\" set). Why? Because if \nwe pack to stdout, and don't generate an index file, then by _definition_ \nthe other end has to do the index generation, which means that the other \nend will be doing all the SHA1 re-calculation and sanity checking (and \nthus inflation and CRC checking).\n\nSo this means that if we only do this for the \"!pack_to_stdout\" case, we \nwon't be adding any overhead to the git network protocol server, only to \n\"git repack\". Which is exactly what we want to do.\n\n\t\t\tLinus\n"},{"id":"26193","messageId":"7vfyfb5pjk.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609011129270.27779@g5.osdl.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-01T19:56:31Z","receivedAt":"2006-09-01T19:56:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Fri, 1 Sep 2006, A Large Angry SCM wrote:\n>> \n>> Unfortunately, the zlib CRC is of the _uncompressed_ data [1], so\n>> inflating the stream is still necessary to check for corruption.\n>\n> I don't think that is unfortunate.\n>\n> We really should inflate the stream anyway, since not only inflating it, \n> but also applying any deltas to the base object is really the only way to \n> verify its correctness for a delta thing. Otherwise, the SHA1 of the base \n> could be totally corrupt.\n>\n> And once you inflate it and apply all deltas, you obviously also get the \n> full SHA1 check, so you're _really_ safe.\n>\n> So let's do the really safe thing first, and see if it actually results in \n> any problems.\n\nI think this makes sense.\n"},{"id":"26196","messageId":"7vveo741tc.fsf_-_@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609011129270.27779@g5.osdl.org","subject":"[PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-01T23:14:23Z","receivedAt":"2006-09-01T23:14:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When reusing data from an existing pack and from a new style\nloose objects, we used to just copy it staight into the\nresulting pack. Instead make sure they are not corrupt, but\ndo so only when we are not streaming to stdout, in which case\nthe receiving end will do the validation either by unpacking\nthe stream or by constructing the .idx file.\n\nSigned-off-by: Junio C Hamano \n---\n\n Linus Torvalds writes:\n\n > On Fri, 1 Sep 2006, A Large Angry SCM wrote:\n >> \n >> Unfortunately, the zlib CRC is of the _uncompressed_ data [1], so\n >> inflating the stream is still necessary to check for corruption.\n >\n > I don't think that is unfortunate.\n >\n > We really should inflate the stream anyway, since not only inflating it, \n > but also applying any deltas to the base object is really the only way to \n > verify its correctness for a delta thing. Otherwise, the SHA1 of the base \n > could be totally corrupt.\n >\n > And once you inflate it and apply all deltas, you obviously also get the \n > full SHA1 check, so you're _really_ safe.\n >\n > So let's do the really safe thing first, and see if it actually results in \n > any problems.\n\n So here is an attempt to do this.\n\n builtin-pack-objects.c | 64 +++++++++++++++++++++++++++++++++++++++++++++---\n 1 files changed, 60 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 46f524d..10ba866 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -65,6 +65,7 @@ static unsigned char pack_file_sha1[20];\n static int progress = 1;\n static volatile sig_atomic_t progress_update;\n static int window = 10;\n+static int pack_to_stdout;\n \n /*\n * The object names in objects array are hashed with this hashtable,\n@@ -242,6 +243,55 @@ static int encode_header(enum object_typ\n \treturn n;\n }\n \n+static int revalidate_one(struct object_entry *entry,\n+\t\t\t void *data, char *type, unsigned long size)\n+{\n+\tunsigned char hdr[50];\n+\tint hdrlen;\n+\tunsigned char sha1[20];\n+\n+\tif (!data)\n+\t\treturn -1;\n+\tif (size != entry->size)\n+\t\treturn -1;\n+\twrite_sha1_file_prepare(data, size, type, sha1, hdr, &hdrlen);\n+\tfree(data);\n+\tif (hashcmp(sha1, entry->sha1))\n+\t\treturn -1;\n+\treturn 0;\n+}\n+\n+/*\n+ * we are going to reuse the existing pack entry data. make\n+ * sure it is not corrupt.\n+ */\n+static int revalidate_pack_entry(struct object_entry *entry)\n+{\n+\tvoid *data;\n+\tchar type[20];\n+\tunsigned long size;\n+\tstruct pack_entry e;\n+\n+\te.p = entry->in_pack;\n+\te.offset = entry->in_pack_offset;\n+\n+\t/* the caller has already called use_packed_git() for us */\n+\tdata = unpack_entry_gently(&e, type, &size);\n+\treturn revalidate_one(entry, data, type, size);\n+}\n+\n+static int revalidate_loose_object(struct object_entry *entry,\n+\t\t\t\t unsigned char *map,\n+\t\t\t\t unsigned long mapsize)\n+{\n+\t/* we already know this is a loose object with new type header. */\n+\tvoid *data;\n+\tchar type[20];\n+\tunsigned long size;\n+\tdata = unpack_sha1_file(map, mapsize, type, &size);\n+\treturn revalidate_one(entry, data, type, size);\n+}\n+\n static unsigned long write_object(struct sha1file *f,\n \t\t\t\t struct object_entry *entry)\n {\n@@ -276,6 +326,9 @@ static unsigned long write_object(struct\n \t\tmap = map_sha1_file(entry->sha1, &mapsize);\n \t\tif (map && !legacy_loose_object(map)) {\n \t\t\t/* We can copy straight into the pack file */\n+\t\t\tif (revalidate_loose_object(entry, map, mapsize))\n+\t\t\t\tdie(\"corrupt loose object %s\",\n+\t\t\t\t sha1_to_hex(entry->sha1));\n \t\t\tsha1write(f, map, mapsize);\n \t\t\tmunmap(map, mapsize);\n \t\t\twritten++;\n@@ -286,7 +339,7 @@ static unsigned long write_object(struct\n \t\t\tmunmap(map, mapsize);\n \t}\n \n-\tif (! to_reuse) {\n+\tif (!to_reuse) {\n \t\tbuf = read_sha1_file(entry->sha1, type, &size);\n \t\tif (!buf)\n \t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -319,6 +372,9 @@ static unsigned long write_object(struct\n \n \t\tdatalen = find_packed_object_size(p, entry->in_pack_offset);\n \t\tbuf = (char *) p->pack_base + entry->in_pack_offset;\n+\n+\t\tif (revalidate_pack_entry(entry))\n+\t\t\tdie(\"corrupt delta in pack %s\", sha1_to_hex(entry->sha1));\n \t\tsha1write(f, buf, datalen);\n \t\tunuse_packed_git(p);\n \t\thdrlen = 0; /* not really */\n@@ -1163,7 +1219,7 @@ static void prepare_pack(int window, int\n \t\tfind_deltas(sorted_by_type, window+1, depth);\n }\n \n-static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)\n+static int reuse_cached_pack(unsigned char *sha1)\n {\n \tstatic const char cache[] = \"pack-cache/pack-%s.%s\";\n \tchar *cached_pack, *cached_idx;\n@@ -1247,7 +1303,7 @@ int cmd_pack_objects(int argc, const cha\n {\n \tSHA_CTX ctx;\n \tchar line[40 + 1 + PATH_MAX + 2];\n-\tint depth = 10, pack_to_stdout = 0;\n+\tint depth = 10;\n \tstruct object_entry **list;\n \tint num_preferred_base = 0;\n \tint i;\n@@ -1367,7 +1423,7 @@ int cmd_pack_objects(int argc, const cha\n \tif (progress && (nr_objects != nr_result))\n \t\tfprintf(stderr, \"Result has %d objects.\\n\", nr_result);\n \n-\tif (reuse_cached_pack(object_list_sha1, pack_to_stdout))\n+\tif (reuse_cached_pack(object_list_sha1))\n \t\t;\n \telse {\n \t\tif (nr_result)\n-- \n1.4.2.ga2654\n\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26197","messageId":"Pine.LNX.4.64.0609011721390.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vveo741tc.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-02T00:23:15Z","receivedAt":"2006-09-02T00:23:15Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 1 Sep 2006, Junio C Hamano wrote:\n>\n> \t[...] Instead make sure they are not corrupt, but\n> do so only when we are not streaming to stdout, [...]\n\nHmm. I see you making pack_to_stdout available to those functions, but I \ndon't actually see you using it - looks like you revalidate regardless.\n\nWhich is safe, of course, but it doesn't match your description ;)\n\n\t\tLinus\n\n-- \nVGER BF report: H 0.0110285\n"},{"id":"26201","messageId":"20060902011950.GB24234@spearce.org","threadId":"5432","inReplyTo":"7vr6yw58xp.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T01:19:50Z","receivedAt":"2006-09-02T01:19:50Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Step 3. Work on integrating partial mmap() support with Shawn.\n> This is more or less orthogonal to 4GB ceiling (people\n> would hit mmap() limit even with a 1.5GB pack), but I\n> suspect it would be necessary to be able to tell where\n> the end of each pack entry is cheaply to implement\n> this.\n\nI was just getting ready to move my partial mmap support over from\nfast-import.\n\nAlthough I did the implementation a little differently in fast-import\nthan what I think I'll do in core Git. In fast-import store a\nhashtable in memory of all objects in the pack but I chose not to\nstore the ending offset (or compressed length) and instead just\nguess about where the object ends. I did that to save 4 bytes of\nmemory per object. :-)\n\nIts necessary to know where the object ends to ensure that your\ncurrent mapping (or any remapping you are about to do) covers the\nentire object before you start deflating. Otherwise you might\nhave to remap the pack in the middle of the inflate operation.\n(Of course you might need to do this anyway if the compressed object\nis larger than your default mapping unit.)\n\nWhat I did in fast-import was give inflate whatever was left in\nthe current mapping; then if I got a Z_OK or Z_BUF_ERROR back from\ninflate I move the mapping to the next 128 MiB chunk and reset my\nz_stream's next_in/avail_in accordingly, then recall inflate.\n\nNo I didn't performance test it to see how frequently I'm mapping\na pack multiple times to get one object. But I'm going to stick my\nneck out and say that most objects probably don't have a compressed\nlength exceeding 128 MiB so we're talking one remap that we would\nhave had to do anyway if the object spanned over the end of the\ncurrent mapping. If the object's starting offset was completely\noutside of the current mapping then I rounded the offset down to\nthe page size (from getpagesize) and remapped; therefore we also\nprobably only do one remap on objects needing it.\n\n\nBut having the length or ending offset in the index will help with\ncopying the object during a repack as well as prevent us from needing\nto guess during accesses. So good news indeed that you are adding\nit to the index.\n\n-- \nShawn.\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26199","messageId":"Pine.LNX.4.63.0609020338430.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609011721390.27779@g5.osdl.org","subject":"VGER BF report?","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-09-02T01:39:30Z","receivedAt":"2006-09-02T01:39:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"> VGER BF report: H 0.0110285\n\nWhat is this?\n\n\n-- \nVGER BF report: H 0.00947004\n"},{"id":"26200","messageId":"7vr6yv3uh4.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609011721390.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T01:52:55Z","receivedAt":"2006-09-02T01:52:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Fri, 1 Sep 2006, Junio C Hamano wrote:\n>>\n>> \t[...] Instead make sure they are not corrupt, but\n>> do so only when we are not streaming to stdout, [...]\n>\n> Hmm. I see you making pack_to_stdout available to those functions, but I \n> don't actually see you using it - looks like you revalidate regardless.\n>\n> Which is safe, of course, but it doesn't match your description ;)\n\nOops, that was a thinko. My previous crappoid had\n\n\tif (pack_to_stdout)\n \treturn 0;\n\nat the beginning of revalidate function.\n\n\n-- \nVGER BF report: U 0.499951\n"},{"id":"26202","messageId":"20060902020426.GF24234@spearce.org","threadId":"5432","inReplyTo":"7vr6yw58xp.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T02:04:27Z","receivedAt":"2006-09-02T02:04:27Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n[snip]\n> +A new style .idx file begins with a signature, \"\\377tOc\", and a\n> +version number as a 4-byte network byte order integer. The version\n> +of this implementation is 2.\n\nIck. I understand why you did this (and thanks for such a good\nexplanation of it by the way) but what a horrible signature number\nand way to wedge in a version number.\n\n>From now on I propose that if we write a file - especially a binary\nfile - to disk that we always include a 4 byte version number into\nthe header of the file. Then we can avoid trying to wedge this into\nthe file after the fact when some worthwhile improvement requires\nchanging the format.\n\nI think we probably should have done this when the binary headers\nwere introduced into loose objects. Would 4 bytes of file format\nversion number with an (initial version number which wasn't 0x78\nin byte 0 and failed the % 31 test) really have hurt that much in\na loose object?\n\n[snip]\n> + . 4-byte network byte order integer, recording the location of the\n> + next object in the main toc table.\n\nWhy not just the 4 byte object entry length? To load an object we\nhave to go find the next object in the idx file so we can compute\nthe offset difference. On very large packs (e.g. the Mozilla pack)\nthe index is 46 MiB. The jump across the index could be the entire\nthing from back to front just to compute the size of an object when\nthe fan-out table and the binary search process really only poked\nthe tail end of the index when searching for the entry. So we're\ndemand paging in the front of the index just to compute a length\n\nSure the scheme you outlined allows a 64 bit difference but\nuncompressed objects already can't be larger than 2**32-1 and we\ncould just as easily move that limit down to say 2**32-16 to leave\nroom for the object header and zlib header.\n\n-- \nShawn.\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26203","messageId":"7vd5ae3ox2.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609011721390.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T03:52:57Z","receivedAt":"2006-09-02T03:52:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Fri, 1 Sep 2006, Junio C Hamano wrote:\n>>\n>> \t[...] Instead make sure they are not corrupt, but\n>> do so only when we are not streaming to stdout, [...]\n>\n> Hmm. I see you making pack_to_stdout available to those functions, but I \n> don't actually see you using it - looks like you revalidate regardless.\n>\n> Which is safe, of course, but it doesn't match your description ;)\n\nBut \"git repack -a -d\", which you now consider almost being\nfree, in the recent kernel repository counts 300k objects, and\nreuses 298k objects or so. That means we expand and recompress\nthat many objects, totalling 120MB.\n\nIt might be worthwhile to disable revalidate reused objects\nindividually and instead scan and checksum the entire .pack file\nwhen the number of objects being reused exceeds certain\nthreshold, relative to the number of objects in existing pack,\nperhaps.\n\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26204","messageId":"7v8xl23oia.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902011950.GB24234@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T04:01:49Z","receivedAt":"2006-09-02T04:01:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> What I did in fast-import was give inflate whatever was left in\n> the current mapping; then if I got a Z_OK or Z_BUF_ERROR back from\n> inflate I move the mapping to the next 128 MiB chunk and reset my\n> z_stream's next_in/avail_in accordingly, then recall inflate.\n\nMakes sense.\n\n> But having the length or ending offset in the index will help with\n> copying the object during a repack as well as prevent us from needing\n> to guess during accesses.\n\nActually pack-objects already builds the reverse index without\nthe help from the updated .idx file format, so while having it\npre-built in .idx may help, it is not necessary for it. With\nyour \"feed until the end of the current window and if we need\nmore map in the next window\" logic, we do not even need to know\nthe length of each entry at runtime either.\n\nSo I am inclined to chuck the previous patch that records the\nnext object number in each entry. We could keep the 64-bit\noffset, which would make an entry to be 28-byte instead of\n32-byte.\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26213","messageId":"20060902043931.GA25146@spearce.org","threadId":"5432","inReplyTo":"7v8xl23oia.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T04:39:31Z","receivedAt":"2006-09-02T04:39:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> So I am inclined to chuck the previous patch that records the\n> next object number in each entry. We could keep the 64-bit\n> offset, which would make an entry to be 28-byte instead of\n> 32-byte.\n\nI can agree with that. :-)\n\nRepacking is infrequent compared to searching for an object.\nAsking the repack code to determine object lengths (especially if it\nis going to deflate the entry anyway to verify it) isn't that much of\na performance hit. As you pointed out its already happening today.\n\nUsing a 28 byte index entry instead of a 32 byte index entry means\nthe Mozilla historical pack index will only be 52.4 MiB rather than\nthe slightly larger 59.9 MiB. 1.9x10^6 objects will do that to you.\n\n-- \nShawn.\n"},{"id":"26208","messageId":"20060902045246.GB25146@spearce.org","threadId":"5432","inReplyTo":"7vd5ae3ox2.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T04:52:46Z","receivedAt":"2006-09-02T04:52:46Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> It might be worthwhile to disable revalidate reused objects\n> individually and instead scan and checksum the entire .pack file\n> when the number of objects being reused exceeds certain\n> threshold, relative to the number of objects in existing pack,\n> perhaps.\n\nCorrect me if I'm wrong but didn't this revalidate check happen\nbecause the SHA1 of the pack was correct but there was a bad bit\nin the zlib stream?\n\nIf we are trying to detect such an error before removing the possibly\nvalid pack how are we supposed to do that if we are bypassing the\ncode on larger packs?\n\n\nI think the better thing to do here is to not repack objects which\nare already contained in very large packs. Just leave them be.\n\nIf the pack you are about to copy an object out of is over 25 MiB,\nyou aren't outputting to stdout and the object isn't needed\nas a delta base in the new pack then don't copy it. Introduce a\nnew flag to git-pack-objects such as \"--max-source-pack-size=100\"\nwhich can be used to change this 25 MiB threshold; setting it to\n0 would act as \"-a\" does today.\n\nThis way users can repack with 'git repack -a -d' as though it were\nfree and much less frequently (such as once a year) combine their\nmedium sized packs together based on a larger maximum threshold\nwhile still ignoring their really large historical packs.\n\nNote that you are never bypassing the deflate validation; before\ncopying an object you *always* validate it is correct, even if the\nsource pack SHA1 is correct. But this time consuming validation\nshould not be a big issue as users shouldn't repack very large\npacks very frequently with this strategy. E.g. some kernel devs\nmight repack once a year with --max-source-pack-size=512 (512 MiB)\nbut during normal use accept the 25 MiB default and the slightly\nlarger number of small packs that result.\n\n-- \nShawn.\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26205","messageId":"20060902055833.GA26009@uranus.ravnborg.org","threadId":"5432","inReplyTo":"Pine.LNX.4.63.0609020338430.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: VGER BF report?","fromName":"Sam Ravnborg","fromEmail":"sam@ravnborg.org","sentAt":"2006-09-02T05:58:33Z","receivedAt":"2006-09-02T05:58:33Z","isPatch":false,"sender":{"key":"sam@ravnborg.org","avatar":"https://gravatar.com/avatar/168a912606ed0742d840bb365e3cc21db390c36531a58341dc7a069cc1f15f62?d=mp&s=160"},"body":"On Sat, Sep 02, 2006 at 03:39:30AM +0200, Johannes Schindelin wrote:\n> > VGER BF report: H 0.0110285\n> \n> What is this?\nvger.kernel.org is experimentibg with bogofilter.\nSeems to be a ham score.\n\nMatti announced the use of bogofilter on linux-kernel yesterday.\n\n\tSam\n\n-- \nVGER BF report: U 0.497275\n"},{"id":"26209","messageId":"7vwt8m1u6b.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902045246.GB25146@spearce.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T09:42:20Z","receivedAt":"2006-09-02T09:42:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>> It might be worthwhile to disable revalidate reused objects\n>> individually and instead scan and checksum the entire .pack file\n>> when the number of objects being reused exceeds certain\n>> threshold, relative to the number of objects in existing pack,\n>> perhaps.\n>\n> Correct me if I'm wrong but didn't this revalidate check happen\n> because the SHA1 of the pack was correct but there was a bad bit\n> in the zlib stream?\n\nThere are two more or less independent problems and you are\ncorrect to point out that summing the entire .pack does not\ncatch one class of problem while it does catch the other.\n\nThe Linus's theory goes like this:\n\n (1) A bit in an existing pack was damaged somehow. It might have\n happened on the mothership machine when it was first created,\n or after it was read and copied to the notebook via rsync.\n\n (2) A 'repack -a -d' was done in a repository that had that\n damanged pack, it decided to reuse a deflated object from the\n existing, damaged pack, and copied that deflated\n representation into a newly created pack without validating.\n\n (3) The 'repack -a -d', when finishing the newly created pack,\n computed a checksum over the whole new pack and wrote the\n SHA-1 checksum in it.\n\nNow, sha1_file() has check_packed_git_idx() that makes sure .idx\nfile is not corrupted; it runs the checksum over the whole .idx\ndata when it first maps in and makes sure the sum matches what\nis recorded at the end. So if the corruption in (1) happened to\nthe .idx file, 'repack -a -d' in (2) would have noticed and\nrefused to use the corresponding .pack.\n\nThe problem is that there is however no corresponding \"checksum\nover the whole file before use\" for .pack file during a normal\noperation of use_packed_git(). Otherwise we would have caught\nthe corruption in the existing pack and prevented step (2) from\npropagating the error.\n\nThe idea proposed by Linus and implemented in the patch in this\nthread is to mitigate this by revalidating the individual pieces\nwe copy in (2). If we copy out most of what is in the existing\npack, however, it may be cheaper to do the \"whole file checksum\nbefore use\" instead.\n\nOn the other hand, the \"alpha particle at the right moment\"\ntheory goes like this:\n\n (1) write_object() gave the buffer to sha1write_compressed();\n\n (2) sha1write_compressed() asked zlib to deflate the data and\n received the result in buffer pointed by void *out;\n\n (3) bit flipped in that buffer, after zlib finished writing\n into it with the CRC;\n\n (4) sha1write() wrote out the now-corrupt buffer, while\n computing the correct checksum for the end result (which is\n now corrupt).\n\nThis breakage will not be caught unless we revalidate everything\nwe copy out to the new pack.\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26210","messageId":"7vodty1swz.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902045246.GB25146@spearce.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T10:09:32Z","receivedAt":"2006-09-02T10:09:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> I think the better thing to do here is to not repack objects which\n> are already contained in very large packs. Just leave them be.\n\nI've been thinking about updating rev-list so that repack\ncan be used to organize packs into zero or more \"archive packs\"\nand one \"active pack\".\n\nrepack without -a essentially boils down to:\n\n\trev-list --objects --all --unpacked |\n pack-objects $new_pack\n\nwhich picks up all live loose objects and create a new pack.\n\nIf rev-list had an extention that lets you say\n\n\trev-list --objects --all --unpacked=$active_pack |\n\tpack-objects $new_pack\n\ninstead, to mean \"all live loose objects but pretend as if\nobjects that are in this pack are also unpacked\", then the\nnewly created pack would be perfect for updating $active_pack\nby replacing it.\n\nPerhaps something like this.\n\n-- >8 --\n\ndiff --git a/builtin-count-objects.c b/builtin-count-objects.c\nindex 1d3729a..73c5982 100644\n--- a/builtin-count-objects.c\n+++ b/builtin-count-objects.c\n@@ -62,7 +62,7 @@ static void count_objects(DIR *d, char *\n \t\thex[40] = 0;\n \t\tif (get_sha1_hex(hex, sha1))\n \t\t\tdie(\"internal error\");\n-\t\tif (has_sha1_pack(sha1))\n+\t\tif (has_sha1_pack(sha1, NULL))\n \t\t\t(*packed_loose)++;\n \t}\n }\ndiff --git a/builtin-prune-packed.c b/builtin-prune-packed.c\nindex d3dd94d..960db49 100644\n--- a/builtin-prune-packed.c\n+++ b/builtin-prune-packed.c\n@@ -19,7 +19,7 @@ static void prune_dir(int i, DIR *dir, c\n \t\tmemcpy(hex+2, de->d_name, 38);\n \t\tif (get_sha1_hex(hex, sha1))\n \t\t\tcontinue;\n-\t\tif (!has_sha1_pack(sha1))\n+\t\tif (!has_sha1_pack(sha1, NULL))\n \t\t\tcontinue;\n \t\tmemcpy(pathname + len, de->d_name, 38);\n \t\tif (dryrun)\ndiff --git a/cache.h b/cache.h\nindex 7257c4c..b50a823 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -259,7 +259,7 @@ extern int write_sha1_from_fd(const unsi\n extern int write_sha1_to_fd(int fd, const unsigned char *sha1);\n extern int move_temp_to_file(const char *tmpfile, const char *filename);\n \n-extern int has_sha1_pack(const unsigned char *sha1);\n+extern int has_sha1_pack(const unsigned char *sha1, const char *ignore);\n extern int has_sha1_file(const unsigned char *sha1);\n extern void *map_sha1_file(const unsigned char *sha1, unsigned long *);\n extern int legacy_loose_object(unsigned char *);\ndiff --git a/revision.c b/revision.c\nindex b588f74..fad3b24 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -416,7 +416,8 @@ static void limit_list(struct rev_info *\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (revs->unpacked && has_sha1_pack(obj->sha1))\n+\t\tif (revs->unpacked &&\n+\t\t has_sha1_pack(obj->sha1, revs->ignore_packed))\n \t\t\tobj->flags |= UNINTERESTING;\n \t\tadd_parents_to_list(revs, commit, &list);\n \t\tif (obj->flags & UNINTERESTING) {\n@@ -737,6 +738,12 @@ int setup_revisions(int argc, const char\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"--unpacked\")) {\n \t\t\t\trevs->unpacked = 1;\n+\t\t\t\trevs->ignore_packed = NULL;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (!strncmp(arg, \"--unpacked=\", 11)) {\n+\t\t\t\trevs->unpacked = 1;\n+\t\t\t\trevs->ignore_packed = arg + 11;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tif (!strcmp(arg, \"-r\")) {\n@@ -1046,7 +1053,8 @@ struct commit *get_revision(struct rev_i\n \t\t */\n \t\tif (!revs->limited) {\n \t\t\tif ((revs->unpacked &&\n-\t\t\t has_sha1_pack(commit->object.sha1)) ||\n+\t\t\t has_sha1_pack(commit->object.sha1,\n+\t\t\t\t\t revs->ignore_packed)) ||\n \t\t\t (revs->max_age != -1 &&\n \t\t\t (commit->date < revs->max_age)))\n \t\t\t\tcontinue;\ndiff --git a/revision.h b/revision.h\nindex d289781..843aeea 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -57,6 +57,9 @@ struct rev_info {\n \tunsigned int\tshown_one:1,\n \t\t\tabbrev_commit:1,\n \t\t\trelative_date:1;\n+\n+\tconst char *ignore_packed;\n+\n \tunsigned int\tabbrev;\n \tenum cmit_fmt\tcommit_format;\n \tstruct log_info *loginfo;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 76f66e6..7031f65 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1189,12 +1189,15 @@ int find_pack_entry_one(const unsigned c\n \treturn 0;\n }\n \n-static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)\n+static int find_pack_entry(const unsigned char *sha1,\n+\t\t\t struct pack_entry *e, const char *ignore_packed)\n {\n \tstruct packed_git *p;\n \tprepare_packed_git();\n \n \tfor (p = packed_git; p; p = p->next) {\n+\t\tif (ignore_packed && !strcmp(p->pack_name, ignore_packed))\n+\t\t\tcontinue;\n \t\tif (find_pack_entry_one(sha1, e, p))\n \t\t\treturn 1;\n \t}\n@@ -1227,10 +1230,10 @@ int sha1_object_info(const unsigned char\n \tif (!map) {\n \t\tstruct pack_entry e;\n \n-\t\tif (find_pack_entry(sha1, &e))\n+\t\tif (find_pack_entry(sha1, &e, NULL))\n \t\t\treturn packed_object_info(&e, type, sizep);\n \t\treprepare_packed_git();\n-\t\tif (find_pack_entry(sha1, &e))\n+\t\tif (find_pack_entry(sha1, &e, NULL))\n \t\t\treturn packed_object_info(&e, type, sizep);\n \t\treturn error(\"unable to find %s\", sha1_to_hex(sha1));\n \t}\n@@ -1253,7 +1256,7 @@ static void *read_packed_sha1(const unsi\n {\n \tstruct pack_entry e;\n \n-\tif (!find_pack_entry(sha1, &e)) {\n+\tif (!find_pack_entry(sha1, &e, NULL)) {\n \t\terror(\"cannot read sha1_file for %s\", sha1_to_hex(sha1));\n \t\treturn NULL;\n \t}\n@@ -1266,7 +1269,7 @@ void * read_sha1_file(const unsigned cha\n \tvoid *map, *buf;\n \tstruct pack_entry e;\n \n-\tif (find_pack_entry(sha1, &e))\n+\tif (find_pack_entry(sha1, &e, NULL))\n \t\treturn read_packed_sha1(sha1, type, size);\n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n@@ -1275,7 +1278,7 @@ void * read_sha1_file(const unsigned cha\n \t\treturn buf;\n \t}\n \treprepare_packed_git();\n-\tif (find_pack_entry(sha1, &e))\n+\tif (find_pack_entry(sha1, &e, NULL))\n \t\treturn read_packed_sha1(sha1, type, size);\n \treturn NULL;\n }\n@@ -1707,10 +1710,10 @@ int has_pack_file(const unsigned char *s\n \treturn 1;\n }\n \n-int has_sha1_pack(const unsigned char *sha1)\n+int has_sha1_pack(const unsigned char *sha1, const char *ignore_packed)\n {\n \tstruct pack_entry e;\n-\treturn find_pack_entry(sha1, &e);\n+\treturn find_pack_entry(sha1, &e, ignore_packed);\n }\n \n int has_sha1_file(const unsigned char *sha1)\n@@ -1718,7 +1721,7 @@ int has_sha1_file(const unsigned char *s\n \tstruct stat st;\n \tstruct pack_entry e;\n \n-\tif (find_pack_entry(sha1, &e))\n+\tif (find_pack_entry(sha1, &e, NULL))\n \t\treturn 1;\n \treturn find_sha1_file(sha1, &st) ? 1 : 0;\n }\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26214","messageId":"7v3bba1qg5.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902020426.GF24234@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T11:02:50Z","receivedAt":"2006-09-02T11:02:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n> [snip]\n>> +A new style .idx file begins with a signature, \"\\377tOc\", and a\n>> +version number as a 4-byte network byte order integer. The version\n>> +of this implementation is 2.\n>\n> Ick. I understand why you did this (and thanks for such a good\n> explanation of it by the way) but what a horrible signature number\n> and way to wedge in a version number.\n\nI do not think it is particularly horrible. \n\nI initially was planning to introduce a new file extention .toc\n(table of contents), not just because that would let us start\nafresh with file format that has version number from the\nbeginning, but also because we use the word \"index\" to mean\n\"cache\" these days, and it would be a good idea to use a\ndifferent word to mean different things. The latter 3 bytes\nreflects that.\n\n> I think we probably should have done this when the binary headers\n> were introduced into loose objects.\n\nNo. That was purely .pack format and did not affect .idx\nformat. Honestly .idx is purely a local matter and not as\nimportant to keep stable as the .pack format.\n\n> Sure the scheme you outlined allows a 64 bit difference but\n> uncompressed objects already can't be larger than 2**32-1...\n\nWhere do we have that limitation?\n\nIn any case, the next round I am planning to get rid of this\n\"where the tail is\" business. I do not think it buys us much\nand inflates the 46MB index you need to deal with even more.\n\nI think your \"allow zlib to eat the remainder of the current\nwindow and slide window when it exhausts the current window\"\nlogic is a very good on and makes it unnecessary to know the\ntail of each object.\n\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26215","messageId":"7vveo6zfx0.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902043931.GA25146@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T11:06:19Z","receivedAt":"2006-09-02T11:06:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Using a 28 byte index entry instead of a 32 byte index entry means\n> the Mozilla historical pack index will only be 52.4 MiB rather than\n> the slightly larger 59.9 MiB.\n\nYup, that was one consideration. One small worry is we will be\nplacing u64 at 4-byte alignment by using 28-byte entries but I\nthink that is Ok.\n\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26220","messageId":"9e4733910609020720w3633aa0cq5016fb1e223fc4cb@mail.gmail.com","threadId":"5432","inReplyTo":"7vveo6zfx0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-09-02T14:20:49Z","receivedAt":"2006-09-02T14:20:49Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/2/06, Junio C Hamano wrote:\n> Shawn Pearce writes:\n>\n> > Using a 28 byte index entry instead of a 32 byte index entry means\n> > the Mozilla historical pack index will only be 52.4 MiB rather than\n> > the slightly larger 59.9 MiB.\n>\n> Yup, that was one consideration. One small worry is we will be\n> placing u64 at 4-byte alignment by using 28-byte entries but I\n> think that is Ok.\n\nIf you're going to redo the pack formats another big win for the\nMozilla pack is to convert pack internal sha1 references into file\noffsets.within the pack. Doing that will take around 30MB off from the\nMozilla pack size. sha1's are not compressible so this is a direct\nsavings.\n\nThis might reduce memory usage too. The index is only needed to get\nthe initial object from the pack. Since index use is lighter it could\njust be open/closed when needed.\n\nYou could also introduce a zlib dictionary object into the format and\njust leave it empty for now.\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26230","messageId":"20060902173922.GA27826@spearce.org","threadId":"5432","inReplyTo":"9e4733910609020720w3633aa0cq5016fb1e223fc4cb@mail.gmail.com","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T17:39:22Z","receivedAt":"2006-09-02T17:39:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> If you're going to redo the pack formats another big win for the\n> Mozilla pack is to convert pack internal sha1 references into file\n> offsets.within the pack. Doing that will take around 30MB off from the\n> Mozilla pack size. sha1's are not compressible so this is a direct\n> savings.\n\nRight now Junio's working on the index to break the 4 GiB barrier.\nI think Junio and Nico have already agreed to change the base SHA1\nto be an offset instead; though this is an issue for the current\nway the base gets written out behind the delta as you need to know\nexactly how many bytes the delta is going to be so you can correctly\ncompute the offset.\n \n> This might reduce memory usage too. The index is only needed to get\n> the initial object from the pack. Since index use is lighter it could\n> just be open/closed when needed.\n\nTrue; however when you are walking a series of commits (to produce\noutput for `git log` for example) every time you parse a commit you\nneed to go back to the .idx to relookup the ancestor commit(s).\nSo you don't want to open/close the .idx file on every object;\ninstead put the .idx file into the LRU like the .pack files are\n(or into their own LRU chain) and maintain some threshold on how\nmany bytes worth of .idx is kept live.\n \n> You could also introduce a zlib dictionary object into the format and\n> just leave it empty for now.\n\nNo. I'm not sure I'm ready to propose that as a solution for\ndecreasing pack size. Now that my exams are over I've started\nworking on a true dictionary based compression implementation.\nI want to try to get Git itself repacked under it, then try the\nMozilla pack after I get my new amd64 based system built.\n\nIf that's as big of space saver as we're hoping it would be then\nthe pack format would be radically different and need to change;\nif it doesn't gain us anything (or is worse!) then we can go back\nto the drawing board and consider other pack format changes such as\na zlib dictionary. But right now its measly 4% gain isn't very much.\n\n-- \nShawn.\n\n-- \nVGER BF report: U 0.653439\n"},{"id":"26231","messageId":"Pine.LNX.4.64.0609021041170.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vwt8m1u6b.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-02T17:43:52Z","receivedAt":"2006-09-02T17:43:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 2 Sep 2006, Junio C Hamano wrote:\n> \n> The Linus's theory goes like this:\n> \n> (1) A bit in an existing pack was damaged somehow. It might have\n> happened on the mothership machine when it was first created,\n> or after it was read and copied to the notebook via rsync.\n\nNOTE! With the new loose object format, this will be true even of \nindividually packed files (if you set \"core.legacyheaders\" to false). So \nchecking the SHA1 of the pack-files is insufficient - at least for those \nloose objects.\n\nSo revalidating the individual objects will catch that case too, while \nrevalidating the SHA1 of the old pack-files won't.\n\n\t\tLinus\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26252","messageId":"20060902174432.GB27826@spearce.org","threadId":"5432","inReplyTo":"7vveo6zfx0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T17:44:32Z","receivedAt":"2006-09-02T17:44:32Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > Using a 28 byte index entry instead of a 32 byte index entry means\n> > the Mozilla historical pack index will only be 52.4 MiB rather than\n> > the slightly larger 59.9 MiB.\n> \n> Yup, that was one consideration. One small worry is we will be\n> placing u64 at 4-byte alignment by using 28-byte entries but I\n> think that is Ok.\n\nOn some systems (SPARC?) that's definately an issue. Other systems\n(x86) obviously don't have that problem.\n\nIf you code the decode function as treating that 64 bit value as\ntwo 32 bit values in network byte order and combine them together\nafter ntohl() then this shouldn't be a problem. Though big-endian\nsystems which can take a u64 on a 4-byte alignment just fine would\npay a small performance penalty that they don't need to pay.\n\n-- \nShawn.\n\n-- \nVGER BF report: S 0.998672\n"},{"id":"26232","messageId":"20060902175125.GC27826@spearce.org","threadId":"5432","inReplyTo":"7v3bba1qg5.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T17:51:25Z","receivedAt":"2006-09-02T17:51:25Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> > I think we probably should have done this when the binary headers\n> > were introduced into loose objects.\n> \n> No. That was purely .pack format and did not affect .idx\n> format. Honestly .idx is purely a local matter and not as\n> important to keep stable as the .pack format.\n\nI think you missed the point of my comment. I apologize for it\nnot being clear the first time.\n\nThe loose objects have format #1 (legacy text format compressed as\none big zlib stream) and now format #2 (pack object header followed\nby data-only zlib stream).\n\nIn looking at this dictionary packing code that I'm working on right\nnow I may be introducing format #3 (dictionary based compression\nrather than zlib compression).\n\nWe have no easy way to mark the version number of the loose objects.\nI'm sure we can shoehorn in something though.\n \n> > Sure the scheme you outlined allows a 64 bit difference but\n> > uncompressed objects already can't be larger than 2**32-1...\n> \n> Where do we have that limitation?\n\nsha1_file.c uses \"unsigned long\" a lot to deal with size of an\nobject, deflated. iirc unsigned long is only 32 bits even in many\n64 bit architectures. Or am I wrong?\n\n> I think your \"allow zlib to eat the remainder of the current\n> window and slide window when it exhausts the current window\"\n> logic is a very good on and makes it unnecessary to know the\n> tail of each object.\n\nI'll send patches to sha1_file.c probably later tonight. My last\nround of offset changes was the start of that, this next round\nshould finish it. Its mostly a copy-n-paste from fast-import.c\nso it should go quickly.\n\n-- \nShawn.\n\n-- \nVGER BF report: U 0.960524\n"},{"id":"26250","messageId":"20060902175408.GD27826@spearce.org","threadId":"5432","inReplyTo":"7vodty1swz.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-02T17:54:08Z","receivedAt":"2006-09-02T17:54:08Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > I think the better thing to do here is to not repack objects which\n> > are already contained in very large packs. Just leave them be.\n> \n> I've been thinking about updating rev-list so that repack\n> can be used to organize packs into zero or more \"archive packs\"\n> and one \"active pack\".\n> \n> repack without -a essentially boils down to:\n> \n> \trev-list --objects --all --unpacked |\n> pack-objects $new_pack\n> \n> which picks up all live loose objects and create a new pack.\n> \n> If rev-list had an extention that lets you say\n> \n> \trev-list --objects --all --unpacked=$active_pack |\n> \tpack-objects $new_pack\n\nHmm. Seems very reasonable actually. :-)\n\nHow do we pick the \"active pack\" in git-repack.sh?\n\nHow about \"--include-pack=$active_pack\" instead of\n\"--unpacked=$active_pack\"? The latter just reads really funny to me.\n\n-- \nShawn.\n\n-- \nVGER BF report: S 0.9993\n"},{"id":"26234","messageId":"Pine.LNX.4.64.0609021138500.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vd5ae3ox2.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-02T18:43:07Z","receivedAt":"2006-09-02T18:43:07Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 1 Sep 2006, Junio C Hamano wrote:\n> \n> But \"git repack -a -d\", which you now consider almost being\n> free, in the recent kernel repository counts 300k objects, and\n> reuses 298k objects or so. That means we expand and recompress\n> that many objects, totalling 120MB.\n\nSure. Do we have data for how expensive that is (ie did you apply the \npatch and time it)?\n\nI'd rather be really safe by default, and then if somebody knows to trust \ntheir archive, maybe add a \"--fast\" flag (or even a \"core.reliablepack\" \nconfig option) to disable it for people who have backups and think their \nmachines are infallible - or have slow CPU's..\n\nFor me, performance has always been one of the primary goals, but being \nable to trust the end result has been even _more_ primary. A lot of the \ndesign has centered around not doing things that are unsafe (eg the whole \n\"never ever re-write an object\" thing was obviously a big part of the \ndesign, and a lot of it is about being able to do things quickly _without_ \nhaving to do slow things like fsync).\n\n\t\t\tLinus\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26235","messageId":"Pine.LNX.4.64.0609021151280.27779@g5.osdl.org","threadId":"5432","inReplyTo":"20060902173922.GA27826@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-02T18:56:58Z","receivedAt":"2006-09-02T18:56:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 2 Sep 2006, Shawn Pearce wrote:\n\n> Jon Smirl wrote:\n> > If you're going to redo the pack formats another big win for the\n> > Mozilla pack is to convert pack internal sha1 references into file\n> > offsets.within the pack. Doing that will take around 30MB off from the\n> > Mozilla pack size. sha1's are not compressible so this is a direct\n> > savings.\n> \n> Right now Junio's working on the index to break the 4 GiB barrier.\n> I think Junio and Nico have already agreed to change the base SHA1\n> to be an offset instead; though this is an issue for the current\n> way the base gets written out behind the delta as you need to know\n> exactly how many bytes the delta is going to be so you can correctly\n> compute the offset.\n\nI think moving the delta to after the base object is fine, and solves that \nproblem.\n\nHowever, the \"--thin\" pack problem is potentially worse, since the object \nyou delta against doesn't even _exist_, and as such you'd then end up \nhaving two totally different formats (or perhaps we'd add a new object \ntype for use in thin packs: a \"dummy object\" that says \"my type is \n and my SHA1 is , you'd better have me already\".\n\nI'm not actually personally convinced that we need to solve the 4GB \npack-file problem right now. Does anybody have that problem yet? The \n\"partial mapping\" issue is a much bigger one, I suspect, even if the tree \ndelta stuff seems to have fixed it largely (yes?) for the mozilla \nfast-import pack-file.\n\nSo in many ways, I'd think that the 4GB problem is one where we are \nperfectly happy to _know_ that a solution exists, rather than have to \nactually solve it today. \n\nOf course, if we change the pack/index-file format for other reasons, then \nwe should obviously fix the 4G issue at the same time, but were there \nactually any real other reasons at this point?\n\n\t\t\tLinus\n\n-- \nVGER BF report: U 0.500001\n"},{"id":"26239","messageId":"7virk6yopp.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609021151280.27779@g5.osdl.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T20:53:54Z","receivedAt":"2006-09-02T20:53:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sat, 2 Sep 2006, Shawn Pearce wrote:\n>\n>> I think Junio and Nico have already agreed to change the base SHA1\n>> to be an offset instead;\n\nI am not in favor of that, at least not yet, especially I\nhaven't thought about the implications of that on streaming\nunpacker. I do not have much objections about changing\nbase-delta order, though.\n\n> Of course, if we change the pack/index-file format for other reasons, then \n> we should obviously fix the 4G issue at the same time, but were there \n> actually any real other reasons at this point?\n\nNot really, from my point of view. Probably 70% of motivation\nof the new \\377tOc index format originally came from wanting to\nhave \"where is the end of this object\" which turned out to be\nunneeded; and by making repack easier to use I think we do not\nhave to solve 4G issue either.\n\nThere is only one case that might need a single pack that can be\nindexed with 4G offset: initial clone or repack of a huge\nrepository.\n\n\n-- \nVGER BF report: U 0.788936\n"},{"id":"26240","messageId":"7vejuuyon7.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902175125.GC27826@spearce.org","subject":"Re: Mozilla .git tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T20:55:24Z","receivedAt":"2006-09-02T20:55:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n>> > Sure the scheme you outlined allows a 64 bit difference but\n>> > uncompressed objects already can't be larger than 2**32-1...\n>> \n>> Where do we have that limitation?\n>\n> sha1_file.c uses \"unsigned long\" a lot to deal with size of an\n> object, deflated. iirc unsigned long is only 32 bits even in many\n> 64 bit architectures. Or am I wrong?\n\nOf course 4G .idx (\\377tOc) patch would update them to u64.\nWhat is the problem?\n\n\n-- \nVGER BF report: U 0.905241\n"},{"id":"26241","messageId":"7vac5iyol5.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609021138500.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-02T20:56:38Z","receivedAt":"2006-09-02T20:56:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> For me, performance has always been one of the primary goals, but being \n> able to trust the end result has been even _more_ primary.\n\nAgreed, violently ;-).\n\n\n-- \nVGER BF report: U 0.735423\n"},{"id":"26244","messageId":"Pine.LNX.4.64.0609021720500.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vodty1swz.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-03T00:27:48Z","receivedAt":"2006-09-03T00:27:48Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 2 Sep 2006, Junio C Hamano wrote:\n> \n> repack without -a essentially boils down to:\n> \n> \trev-list --objects --all --unpacked |\n> pack-objects $new_pack\n> \n> which picks up all live loose objects and create a new pack.\n> \n> If rev-list had an extention that lets you say\n> \n> \trev-list --objects --all --unpacked=$active_pack |\n> \tpack-objects $new_pack\n\nI have to say, that adding another pack-objects-specific flag to rev-list \ndoesn't necessarily strike me as very nice.\n\nIt might be much better to just teach \"git pack-objects\" to walk the \nobject list by hand. The whole \"git-rev-list | git-pack-objects\" approach \nmade more sense back when git-rev-list was the _only_ think listing \nobjects, but now that we've librarized the whole object listing thing, \nmaybe it's time to avoid the pipeline and just do it inside the packer \nlogic.\n\nOf course, having git-pack-objects be able to take input from stdin is \nstill useful, but I'd rather start moving the obviously packing-specific \nflags out of git-rev-list, and into git-pack-objects instead.\n\n[ That would also potentially make packing more efficient - right now the \n \"phase 1\" of packing is literally to just figure out the type and the \n size of the object, in order to sort the object list.\n\n So when you do a big repack, first \"git-rev-list\" ends up doing all this \n work, and then \"git-pack-object\" ends up _redoing_ some of it. \n\n Especially for tree objects (which are one of the most common kinds), we \n already opened the object once when we traversed it, so opening it again \n just to look at its size is kind of sad.. ]\n\nWe also used to have a bug with repacking, where a git-rev-list that died \nwith a failure would silently cause a \"good\" repack to happen because it \nhad fed git-pack-objects an incomplete list of objects. Junio fixed that \nwith a hack, but if we did all the object listing inside git-pack-objects, \nwe'd not need that kind of things at all..\n\nHmm? Comments?\n\n\t\tLinus\n\n-- \nVGER BF report: U 0.500053\n"},{"id":"26248","messageId":"7vslj9yelw.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609021720500.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-03T00:32:11Z","receivedAt":"2006-09-03T00:32:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> I have to say, that adding another pack-objects-specific flag to rev-list \n> doesn't necessarily strike me as very nice.\n>\n> It might be much better to just teach \"git pack-objects\" to walk the \n> object list by hand. The whole \"git-rev-list | git-pack-objects\" approach \n> made more sense back when git-rev-list was the _only_ think listing \n> objects, but now that we've librarized the whole object listing thing, \n> maybe it's time to avoid the pipeline and just do it inside the packer \n> logic.\n>...\n> Hmm? Comments?\n\nYes it all makes perfect sense, though I am a bit too tired to\nassess how much work it would involve right now.\n\n\n-- \nVGER BF report: S 0.993177\n"},{"id":"26251","messageId":"20060903035409.GA29756@spearce.org","threadId":"5432","inReplyTo":"7vejuuyon7.fsf@assigned-by-dhcp.cox.net","subject":"Re: Mozilla .git tree","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-03T03:54:09Z","receivedAt":"2006-09-03T03:54:09Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> >> > Sure the scheme you outlined allows a 64 bit difference but\n> >> > uncompressed objects already can't be larger than 2**32-1...\n> >> \n> >> Where do we have that limitation?\n> >\n> > sha1_file.c uses \"unsigned long\" a lot to deal with size of an\n> > object, deflated. iirc unsigned long is only 32 bits even in many\n> > 64 bit architectures. Or am I wrong?\n> \n> Of course 4G .idx (\\377tOc) patch would update them to u64.\n> What is the problem?\n\nNone then. I must have missed that.\n\nBesides this issue is moot as you are removing it from the .idx.\n\nSorry for the noise. :-)\n\n-- \nShawn.\n\n-- \nVGER BF report: S 0.999999\n"},{"id":"26259","messageId":"7vhczovf6m.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060902175408.GD27826@spearce.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-03T21:00:17Z","receivedAt":"2006-09-03T21:00:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>\n>> If rev-list had an extention that lets you say\n>> \n>> \trev-list --objects --all --unpacked=$active_pack |\n>> \tpack-objects $new_pack\n>\n> Hmm. Seems very reasonable actually. :-)\n>\n> How do we pick the \"active pack\" in git-repack.sh?\n\nI was hoping that will be a Porcelain policy issue I do not have\nto decide ;-).\n\nYou could introduce repack.active in .git/config that points at\nthe latest active, make git-repack to notice and update when it\nupdates it.\n\nWe could also just use .git/objects/pack/pack-active.{pack,idx}\nfiles. This needs some surgery to get rid of packed_git.sha1[],\nsha1_pack_name() and friends and have them only require .pack\nand .idx are linked by their basename only as was discussed in a\nseparate thread to make it dumb-transport friendly.\n\n\n-- \nVGER BF report: U 0.658122\n"},{"id":"26269","messageId":"7vslj8tydc.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609021138500.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-03T21:48:47Z","receivedAt":"2006-09-03T21:48:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Fri, 1 Sep 2006, Junio C Hamano wrote:\n>> \n>> But \"git repack -a -d\", which you now consider almost being\n>> free, in the recent kernel repository counts 300k objects, and\n>> reuses 298k objects or so. That means we expand and recompress\n>> that many objects, totalling 120MB.\n>\n> Sure. Do we have data for how expensive that is (ie did you apply the \n> patch and time it)?\n\nQuite bad. For the kernel archive of today (I usually am nearly\nfully packed):\n\n$ /usr/bin/time ~/git-master/bin/git-pack-objects p1 8 --\n[PATCH] pack-objects: fix thinko in revalidate code\n\nWhen revalidating an entry from an existing pack entry->size and\nentry->type are not necessarily the size of the final object\nwhen the entry is deltified, but for base objects they must\nmatch.\n\nSigned-off-by: Junio C Hamano \n---\n builtin-pack-objects.c | 13 +++++++------\n 1 files changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 11cc3c8..5e42387 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -247,12 +247,13 @@ static int revalidate_one(struct object_\n \t\t\t void *data, char *type, unsigned long size)\n {\n \tint err;\n-\tif (!data)\n-\t\treturn -1;\n-\tif (size != entry->size)\n-\t\treturn -1;\n-\terr = check_sha1_signature(entry->sha1, data, size,\n-\t\t\t\t type_names[entry->type]);\n+\tif ((!data) ||\n+\t ((entry->type != OBJ_DELTA) &&\n+\t ( (size != entry->size) ||\n+\t strcmp(type_names[entry->type], type))))\n+\t\terr = -1;\n+\telse\n+\t\terr = check_sha1_signature(entry->sha1, data, size, type);\n \tfree(data);\n \treturn err;\n }\n-- \n1.4.2.g99d7d\n\n\n\n-- \nVGER BF report: U 0.528006\n"},{"id":"26270","messageId":"Pine.LNX.4.64.0609031456520.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vslj8tydc.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-03T22:00:16Z","receivedAt":"2006-09-03T22:00:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 3 Sep 2006, Junio C Hamano wrote:\n> \n> Quite bad. For the kernel archive of today (I usually am nearly\n> fully packed):\n\nOk. Is it less painful if it just checks the zlib CRC (and that the SHA1 \n_exists_ for a delta - although I guess we check that indirectly by just \naccepting the delta in the first place)? That combination should still be \na fairly strong check, of course.\n\nThen we could have something like\n\n\t[repack]\n\t\tcheck=[none|weak|default|strong]\n\nwhere the \"none\" check would be to just copy the data as-is, the \"weak\" \n(aka \"default\") would check just the CRC, and the strong one would unpack \nthe whole object and check the SHA1..\n\n\t\tLinus\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26272","messageId":"Pine.LNX.4.64.0609031510330.27779@g5.osdl.org","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609031456520.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-03T22:16:47Z","receivedAt":"2006-09-03T22:16:47Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 3 Sep 2006, Linus Torvalds wrote:\n> \n> Ok. Is it less painful if it just checks the zlib CRC (and that the SHA1 \n> _exists_ for a delta - although I guess we check that indirectly by just \n> accepting the delta in the first place)? That combination should still be \n> a fairly strong check, of course.\n\nThinking some more about it, doing the stupid \"apply full delta chain and \ncheck the final SHA1\" is horribly inefficient, because if you have a repo \nthat packs well, you'd expect to have a lot of things with a 10-deep delta \nchain.\n\nAnd doing it the silly way means that you'll do each object independently, \nie for a 10-deep chain you'd unpack the base object ten times, and apply \nthe first delta 9 times, the second one 8 times etc etc. And each time \nyou'd deflate everything, since we don't keep a cache of actual object \ncontents.\n\nSo I'd expect that with full SHA1 checking, you'd end up doing ~45 \ndeflates for the ten-object chain, instead of doing just 10.\n\nSo it should hopefully be _much_ cheaper to just check the zlib CRC, not \nbecause the \"apply delta\" and \"calculate sha1\" are necessarily all that \nexpensive, but because the unoptimized chain-unpacking is doing so much \nunnecessary work.\n\n\t\t\tLinus\n\n-- \nVGER BF report: U 0.5\n"},{"id":"26273","messageId":"7vodtwtw9v.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609031456520.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-03T22:34:04Z","receivedAt":"2006-09-03T22:34:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 3 Sep 2006, Junio C Hamano wrote:\n>> \n>> Quite bad. For the kernel archive of today (I usually am nearly\n>> fully packed):\n>\n> Ok. Is it less painful if it just checks the zlib CRC...\n\nI haven't checked myself but somebody said that zlib CRC is of\npreimage so we would need to incur inflate cost anyway if that\nis the case. But I think it may be a reasonable comproise to\nassume that an existing delta that inflates properly would apply\nto its base object, and if we can assume that we do not have to\ncheck the inflated xdelta data. Oops, not really, there is no\ncheck other than the pack overall SHA-1 checksum that protects\nthe 20-byte base object name recorded in the pack.\n\n> ... and that the SHA1 \n> _exists_ for a delta - although I guess we check that indirectly by just \n> accepting the delta in the first place)? That combination should still be \n> a fairly strong check, of course.\n\nAnother thing the current check is _not_ doing is for this\npathological case:\n\n - .idx table says the pack entry is N bytes\n\n - unpack_entry_gently() used in the revalidate code uses the\n usual codepath that says \"here is the start of the pack\n entry; inflate using as much data as you need\"; .idx is\n somehow wrong and it needed N+M bytes where 0 < M.\n\n - we copy out N bytes because we belive .idx.\n\n\n-- \nVGER BF report: U 0.626721\n"},{"id":"26281","messageId":"7vhczos2ak.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"7vodtwtw9v.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-04T04:06:59Z","receivedAt":"2006-09-04T04:06:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>\n>> Ok. Is it less painful if it just checks the zlib CRC...\n>\n> I haven't checked myself but somebody said that zlib CRC is of\n> preimage so we would need to incur inflate cost anyway if that\n> is the case. But I think it may be a reasonable comproise to\n> assume that an existing delta that inflates properly would apply\n> to its base object, and if we can assume that we do not have to\n> check the inflated xdelta data.\n> ...\n> Another thing the current check is _not_ doing is for this\n> pathological case:\n>\n> - .idx table says the pack entry is N bytes\n>\n> - unpack_entry_gently() used in the revalidate code uses the\n> usual codepath that says \"here is the start of the pack\n> entry; inflate using as much data as you need\"; .idx is\n> somehow wrong and it needed N+M bytes where 0 < M.\n>\n> - we copy out N bytes because we belive .idx.\n\nSo here is a patch against \"master\" which contains none of the\nearlier patches in this thread.\n\nWhen copying from an existing pack and when copying from a loose\nobject with new style header, the code makes sure that the piece\nwe are going to copy out inflates well and inflate() consumes\nthe data in full while doing so.\n\nThe check to see if the xdelta really apply is quite expensive\nas you described, because you would need to have the image of\nthe base object which can be represented as a delta against\nsomething else.\n\nThe same repack takes this much with this code.\n\nTotal 301361, written 301361 (delta 238935), reused 300995 (delta 238663)\n6.66user 0.67system 0:07.40elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+62728minor)pagefaults 0swaps\n\n---\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 46f524d..149fa28 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -65,6 +65,7 @@ static unsigned char pack_file_sha1[20];\n static int progress = 1;\n static volatile sig_atomic_t progress_update;\n static int window = 10;\n+static int pack_to_stdout;\n \n /*\n * The object names in objects array are hashed with this hashtable,\n@@ -242,6 +243,82 @@ static int encode_header(enum object_typ\n \treturn n;\n }\n \n+static int check_inflate(unsigned char *data, unsigned long len, unsigned long expect)\n+{\n+\tz_stream stream;\n+\tunsigned char fakebuf[4096];\n+\tint st;\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\tstream.next_in = data;\n+\tstream.avail_in = len;\n+\tstream.next_out = fakebuf;\n+\tstream.avail_out = sizeof(fakebuf);\n+\tinflateInit(&stream);\n+\n+\twhile (1) {\n+\t\tst = inflate(&stream, Z_FINISH);\n+\t\tif (st == Z_STREAM_END || st == Z_OK) {\n+\t\t\tst = (stream.total_out == expect &&\n+\t\t\t stream.total_in == len) ? 0 : -1;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (st != Z_BUF_ERROR) {\n+\t\t\tst = -1;\n+\t\t\tbreak;\n+\t\t}\n+\t\tstream.next_out = fakebuf;\n+\t\tstream.avail_out = sizeof(fakebuf);\n+\t}\n+\tinflateEnd(&stream);\n+\treturn st;\n+}\n+\n+/*\n+ * we are going to reuse the existing pack entry data. make\n+ * sure it is not corrupt.\n+ */\n+static int revalidate_pack_entry(struct object_entry *entry, unsigned char *data, unsigned long len)\n+{\n+\tenum object_type type;\n+\tunsigned long size, used;\n+\n+\tif (pack_to_stdout)\n+\t\treturn 0;\n+\n+\t/* the caller has already called use_packed_git() for us,\n+\t * so it is safe to access the pack data from mmapped location.\n+\t * make sure the entry inflates correctly.\n+\t */\n+\tused = unpack_object_header_gently(data, len, &type, &size);\n+\tif (!used)\n+\t\treturn -1;\n+\tif (type == OBJ_DELTA)\n+\t\tused += 20; /* skip base object name */\n+\tdata += used;\n+\tlen -= used;\n+\treturn check_inflate(data, len, entry->size);\n+}\n+\n+static int revalidate_loose_object(struct object_entry *entry,\n+\t\t\t\t unsigned char *map,\n+\t\t\t\t unsigned long mapsize)\n+{\n+\t/* we already know this is a loose object with new type header. */\n+\tenum object_type type;\n+\tunsigned long size, used;\n+\n+\tif (pack_to_stdout)\n+\t\treturn 0;\n+\n+\tused = unpack_object_header_gently(map, mapsize, &type, &size);\n+\tif (!used)\n+\t\treturn -1;\n+\tmap += used;\n+\tmapsize -= used;\n+\treturn check_inflate(map, mapsize, size);\n+}\n+\n static unsigned long write_object(struct sha1file *f,\n \t\t\t\t struct object_entry *entry)\n {\n@@ -276,6 +353,9 @@ static unsigned long write_object(struct\n \t\tmap = map_sha1_file(entry->sha1, &mapsize);\n \t\tif (map && !legacy_loose_object(map)) {\n \t\t\t/* We can copy straight into the pack file */\n+\t\t\tif (revalidate_loose_object(entry, map, mapsize))\n+\t\t\t\tdie(\"corrupt loose object %s\",\n+\t\t\t\t sha1_to_hex(entry->sha1));\n \t\t\tsha1write(f, map, mapsize);\n \t\t\tmunmap(map, mapsize);\n \t\t\twritten++;\n@@ -286,7 +366,7 @@ static unsigned long write_object(struct\n \t\t\tmunmap(map, mapsize);\n \t}\n \n-\tif (! to_reuse) {\n+\tif (!to_reuse) {\n \t\tbuf = read_sha1_file(entry->sha1, type, &size);\n \t\tif (!buf)\n \t\t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -319,6 +399,9 @@ static unsigned long write_object(struct\n \n \t\tdatalen = find_packed_object_size(p, entry->in_pack_offset);\n \t\tbuf = (char *) p->pack_base + entry->in_pack_offset;\n+\n+\t\tif (revalidate_pack_entry(entry, buf, datalen))\n+\t\t\tdie(\"corrupt delta in pack %s\", sha1_to_hex(entry->sha1));\n \t\tsha1write(f, buf, datalen);\n \t\tunuse_packed_git(p);\n \t\thdrlen = 0; /* not really */\n@@ -1163,7 +1246,7 @@ static void prepare_pack(int window, int\n \t\tfind_deltas(sorted_by_type, window+1, depth);\n }\n \n-static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout)\n+static int reuse_cached_pack(unsigned char *sha1)\n {\n \tstatic const char cache[] = \"pack-cache/pack-%s.%s\";\n \tchar *cached_pack, *cached_idx;\n@@ -1247,7 +1330,7 @@ int cmd_pack_objects(int argc, const cha\n {\n \tSHA_CTX ctx;\n \tchar line[40 + 1 + PATH_MAX + 2];\n-\tint depth = 10, pack_to_stdout = 0;\n+\tint depth = 10;\n \tstruct object_entry **list;\n \tint num_preferred_base = 0;\n \tint i;\n@@ -1367,7 +1450,7 @@ int cmd_pack_objects(int argc, const cha\n \tif (progress && (nr_objects != nr_result))\n \t\tfprintf(stderr, \"Result has %d objects.\\n\", nr_result);\n \n-\tif (reuse_cached_pack(object_list_sha1, pack_to_stdout))\n+\tif (reuse_cached_pack(object_list_sha1))\n \t\t;\n \telse {\n \t\tif (nr_result)\n\n\n-- \nVGER BF report: U 0.976258\n"},{"id":"26289","messageId":"20060904041052.GA29369@spearce.org","threadId":"5432","inReplyTo":"7vhczovf6m.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-04T04:10:52Z","receivedAt":"2006-09-04T04:10:52Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> > Junio C Hamano wrote:\n> >\n> >> If rev-list had an extention that lets you say\n> >> \n> >> \trev-list --objects --all --unpacked=$active_pack |\n> >> \tpack-objects $new_pack\n> >\n> > Hmm. Seems very reasonable actually. :-)\n> >\n> > How do we pick the \"active pack\" in git-repack.sh?\n> \n> I was hoping that will be a Porcelain policy issue I do not have\n> to decide ;-).\n\nBut would need to update git-repack.sh. :-)\n \n> You could introduce repack.active in .git/config that points at\n> the latest active, make git-repack to notice and update when it\n> updates it.\n\nNo. I don't think its a good idea for git-repack to be updating\nyour configuration file during a repack. If something goes badly\nthere you could lose settings you would rather not lose.\n\nBetter that it update a symref like thing instead. For example\ncreate a \".git/objects/pack/active\" file holding the name\n(\"pack-n{40}.pack\") of the current active pack. If this file is\nmissing choose the pack that is smallest as the active pack.\n\n-- \nShawn.\n\n-- \nVGER BF report: S 0.999999\n"},{"id":"26290","messageId":"7v3bb8qixi.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060904041052.GA29369@spearce.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-04T05:50:33Z","receivedAt":"2006-09-04T05:50:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>...\n>> You could introduce repack.active in .git/config that points at\n>> the latest active, make git-repack to notice and update when it\n>> updates it.\n>...\n> Better that it update a symref like thing instead. For example\n> create a \".git/objects/pack/active\" file holding the name\n> (\"pack-n{40}.pack\") of the current active pack. If this file is\n> missing choose the pack that is smallest as the active pack.\n\nActually I like the one you did not quote even better the more I\nthink about it.\n\n>> We could also just use .git/objects/pack/pack-active.{pack,idx}\n>> files. This needs some surgery to get rid of packed_git.sha1[],\n>> sha1_pack_name() and friends and have them only require .pack\n>> and .idx are linked by their basename only as was discussed in a\n>> separate thread to make it dumb-transport friendly.\n\nThe argument given as the reason (rather, excuse) the dumb\ntransport routines wanted to rely on the packed_git.sha1[] and\nsha1_pack_name() was because we would need to avoid packname\ncollisions _anyway_ so relying on the convention to have\n\"pack-[0-9a-f]{40}.(pack|idx)\" is OK or even desirable.\n\nWe need to avoid packname collisions, and it is acceptable to\nassume that SHA-1 is practically collision free like the rest of\nthe system does. However, if the dumb transport wants to avoid\npackname collision, it should not rely on the way how the other\nside names its packs. It first downloads the .idx files, so it\ncan compute the _right_ packname using the sorted object names\nrecorded there [*1*], and store the downloaded pack/idx under\nthe right name, without relying on the way how the other side\nnames their packs (it still needs to rely on the names in that\ntheir name end with .pack and .idx, and .pack and .idx\ncorresponds with each other by their basenames. But the point\nis it should not depend on more than that, especially that the\nbasename is of the form \"pack-[0-9a-f]{40}\" nor the hex part is\nthe correct packname).\n\nNow if we fix dumb transport downloaders, then we could even\nmake a convention that the packs named pack-[0-9a-f]{40}.pack\nare archive packs. And git-repack can even have a convention\nthat .git/objects/pack/pack-active.(pack|idx) is the active\npack.\n\n[Footnote]\n\n*1* a refresher course of the packname generation; it is SHA-1\nover the object names (20-byte binary representation) in the\npack, sorted in byte order. See builtin-pack-objects.c for\ndetails.\n\n\n-- \nVGER BF report: S 0.99883\n"},{"id":"26288","messageId":"20060904064443.GB30032@spearce.org","threadId":"5432","inReplyTo":"7v3bb8qixi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-09-04T06:44:43Z","receivedAt":"2006-09-04T06:44:43Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Now if we fix dumb transport downloaders, then we could even\n> make a convention that the packs named pack-[0-9a-f]{40}.pack\n> are archive packs. And git-repack can even have a convention\n> that .git/objects/pack/pack-active.(pack|idx) is the active\n> pack.\n\nSeems reasonable.\n\nI take it you are proposing that a dumb transport always downloads\npack-active.pack as pack-n{40}.pack where the dumb protocol\ndownloader computed the correct pack name from its contents. Thus\nany remote pack downloaded over a dumb transport is automatically\ntreated as a historical pack by the receiving repository.\n\nThis will cause someone tracking a remote repository over a dumb\ntransport to need to repack only a subset of their historical packs\nfrequently into their own active.pack while leaving other historical\npacks untouched.\n\n\nBut the more that I think about this neither solution (an active\npack symref or pack-active.pack) really solves this. Being limited\nto just one active pack seems to be a problem with at least the\ndumb transports.\n\nI think that's why I preferred the size threshold idea. The active\npacks are cheap to repack because they are small. The larger\npacks aren't cheap to repack because they are large - and probably\nhistorical. What we are trying to get is fast repacks for the\nactive objects while still getting full validation anytime we do a\nrepack and (possibly) destroy the source. A size threshold does it.\n\nWhen Jon Smirl and I started kicking around the idea of a historical\npack for Mozilla I was thinking of just storing a list of pack base\nnames in \".git/objects/pack/historical\". Packs listed there should\ngenerally be exempt from repacking. During an initial clone we'd\nneed to deliver the contents of that file to the new repository,\nas if the source considers a pack historical its likely the new\nrepository would want to as well.\n\nBut now as I write this email I'm thinking that it may be just as\neasy to change the base name of the pack to \"hist-n{40}\" when we\nwant to consider it historical.\n\n[snipped and re-ordered]\n> It first downloads the .idx files, so it can compute the\n> _right_ packname using the sorted object names recorded there\n\nWhy trust the .idx? I've seen you post that the .idx is purely\na local matter. The \"smart\" Git protocol only receives the .pack\nfrom the remote and computes the .idx locally or unpacks it to loose\nobjects locally; why should a dumb transport trust the remote .idx?\n\nOh, I know, when the .idx is >50 MiB, the .pack is >450 MiB, has\n2 million objects and delta chains ~5000 long.\n\nAre we thinking that .idx files may need to have a slightly wider\ndistribution than \"local\"?\n\n-- \nShawn.\n\n-- \nVGER BF report: S 1\n"},{"id":"26287","messageId":"7v8xl0ozbx.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"20060904064443.GB30032@spearce.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-04T07:39:14Z","receivedAt":"2006-09-04T07:39:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n> Junio C Hamano wrote:\n>> Now if we fix dumb transport downloaders, then we could even\n>> make a convention that the packs named pack-[0-9a-f]{40}.pack\n>> are archive packs. And git-repack can even have a convention\n>> that .git/objects/pack/pack-active.(pack|idx) is the active\n>> pack.\n>\n> Seems reasonable.\n>\n> I take it you are proposing that a dumb transport always downloads\n> pack-active.pack as pack-n{40}.pack where the dumb protocol\n> downloader computed the correct pack name from its contents. Thus\n> any remote pack downloaded over a dumb transport is automatically\n> treated as a historical pack by the receiving repository.\n\nIt is a lot lot lot stronger than that. If the dumb transport\n(or git in general) uses [0-9a-f]{40} part as the assuarance\nmechanism to avoid packname collisions, it should be prepared to\nrecompute the correct name for not just pack-acrive but _all_\nremote packs and store them under the right name.\n\nAlso, if repack uses the convention to treat pack-active.* as\nthe active pack, it might make sense for dumb transport to use\nthat as a clue and explode what the other side calls pack-active.*\nupon reception. For the purpose of repacking decision for the\nperson at the other end, they are subject for frequent repacking,\nso maybe we should treat it as such.\n\n> [snipped and re-ordered]\n>> It first downloads the .idx files, so it can compute the\n>> _right_ packname using the sorted object names recorded there\n>\n> Why trust the .idx? I've seen you post that the .idx is purely\n> a local matter. The \"smart\" Git protocol only receives the .pack\n> from the remote and computes the .idx locally or unpacks it to loose\n> objects locally; why should a dumb transport trust the remote .idx?\n\nRemote .idx is paired with remote .pack and must be able to\naccess into .pack otherwise the remote person could not use the\npack locally ;-). Note that we are not talking about malicious\nrepository.\n\nThe issue here is not about _trusting_, but adjusting its name\nto its contents to match your local convention, which is what\nthe recent pack-objects spits out to its standard output. Older\nversions of pack-objects named the resulting pack with pretty\nmuch randomly (it used to use SHA-1 checksum of object names in\ninput order, not in index order which is sorted, so the same\npack _could_ have different names), and its output files should\nbe considered valid packs if they are still around.\n\n\n-- \nVGER BF report: S 0.999988\n"},{"id":"26303","messageId":"Pine.LNX.4.64.0609040805400.27779@g5.osdl.org","threadId":"5432","inReplyTo":"7vhczos2ak.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-04T15:19:07Z","receivedAt":"2006-09-04T15:19:07Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 3 Sep 2006, Junio C Hamano wrote:\n> \n> So here is a patch against \"master\" which contains none of the\n> earlier patches in this thread.\n\nOk, this looks good. It only adds two extra seconds for me (after fixing \nthe patch: \"unpack_object_header_gently()\" was static to sha1_file.c so \nyour patch wouldn't actually compile on its own), and it should be a lot \nless prone to problems.\n\n\t\tLinus\n"},{"id":"26350","messageId":"7vr6yqivf0.fsf@assigned-by-dhcp.cox.net","threadId":"5432","inReplyTo":"Pine.LNX.4.64.0609021720500.27779@g5.osdl.org","subject":"Re: [PATCH] pack-objects: re-validate data we copy from elsewhere.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-05T08:12:35Z","receivedAt":"2006-09-05T08:12:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sat, 2 Sep 2006, Junio C Hamano wrote:\n>> \n>> repack without -a essentially boils down to:\n>> \n>> \trev-list --objects --all --unpacked |\n>> pack-objects $new_pack\n>> \n>> which picks up all live loose objects and create a new pack.\n>> \n>> If rev-list had an extention that lets you say\n>> \n>> \trev-list --objects --all --unpacked=$active_pack |\n>> \tpack-objects $new_pack\n>\n> I have to say, that adding another pack-objects-specific flag to rev-list \n> doesn't necessarily strike me as very nice.\n>\n> It might be much better to just teach \"git pack-objects\" to walk the \n> object list by hand. The whole \"git-rev-list | git-pack-objects\" approach \n> made more sense back when git-rev-list was the _only_ think listing \n> objects, but now that we've librarized the whole object listing thing, \n> maybe it's time to avoid the pipeline and just do it inside the packer \n> logic.\n>\n> Of course, having git-pack-objects be able to take input from stdin is \n> still useful, but I'd rather start moving the obviously packing-specific \n> flags out of git-rev-list, and into git-pack-objects instead.\n>\n> [ That would also potentially make packing more efficient - right now the \n> \"phase 1\" of packing is literally to just figure out the type and the \n> size of the object, in order to sort the object list.\n>\n> So when you do a big repack, first \"git-rev-list\" ends up doing all this \n> work, and then \"git-pack-object\" ends up _redoing_ some of it. \n>\n> Especially for tree objects (which are one of the most common kinds), we \n> already opened the object once when we traversed it, so opening it again \n> just to look at its size is kind of sad.. ]\n\nWell, I tried (see two patches from tonight, and the result is\nsitting in \"pu\"), but it turns out that the information\npack-objects wants to get in check_object() is somewhat\ndifferent from what \"struct object\" family is willing to give\nback easily during the traversal done by get_revision()\ninterface.\n\nSince \"struct object\" traditionally has not had provision of\nrecording size (created_object() interface just takes sha1\nwithout size, for example), and it was slimmed down to contain\nabsolute minimum information, I am reluctant to add fields to\nrecord the size there. Also having in-pack size available would\nbe rather nice but the functions involved in the call chain\n(including process_tree and process_blob) did not even care\nwhere the objects are stored, so it would involve rather nasty\nsurgery. So I stopped short of that. I am not quite sure how\nuseful tonight's patches are in practice. It gets rid of the\npipe, but moves the revision walker memory pressure from rev-list\nto pack-objects itself, so...\n"}]}