{"thread":{"id":"5148","subject":"Re: GPF in index-pack","startedAt":"2006-08-06T02:44:11Z","lastAt":"2006-08-06T13:46:48Z","messageCount":9,"participants":["Jon Smirl","Shawn Pearce","Sergey Vlasov"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"24864","messageId":"9e4733910608051944v5af7e552wd6909b9773dd516e@mail.gmail.com","threadId":"5148","inReplyTo":"9e4733910608051805j1192d910hf55393f1dbe1e472@mail.gmail.com","subject":"Re: GPF in index-pack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-06T02:44:11Z","receivedAt":"2006-08-06T02:44:11Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Process size is 2.6GB when the seg fault happen. That's a lot of\nmemory to build a pack index over 1M objects.\n\nI'm running a 3:1 process address space split. I wonder why it didn't\ngrow all the way to 3GB. I still have RAM and swap available.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"24865","messageId":"20060806024858.GC20565@spearce.org","threadId":"5148","inReplyTo":"9e4733910608051944v5af7e552wd6909b9773dd516e@mail.gmail.com","subject":"Re: GPF in index-pack","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-06T02:48:58Z","receivedAt":"2006-08-06T02:48:58Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> Process size is 2.6GB when the seg fault happen. That's a lot of\n> memory to build a pack index over 1M objects.\n> \n> I'm running a 3:1 process address space split. I wonder why it didn't\n> grow all the way to 3GB. I still have RAM and swap available.\n\nWas the pack you are trying to index built with that fast-import.c\nI sent last night? Its possible its doing something weird that\npack-index can't handle, such as insert a duplicate object into\nthe same pack...\n\nHow big is the pack file? I'd expect pack-index to be using\nsomething around 24 MB of memory (24 bytes/entry) but maybe its\nhanging onto a lot of data (memory leak?) as it decompresses the\nentries to compute the checksums.\n\n-- \nShawn.\n"},{"id":"24867","messageId":"9e4733910608051958h6144add7td46de70dd8b45a5e@mail.gmail.com","threadId":"5148","inReplyTo":"20060806024858.GC20565@spearce.org","subject":"Re: GPF in index-pack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-06T02:58:21Z","receivedAt":"2006-08-06T02:58:21Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/5/06, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > Process size is 2.6GB when the seg fault happen. That's a lot of\n> > memory to build a pack index over 1M objects.\n> >\n> > I'm running a 3:1 process address space split. I wonder why it didn't\n> > grow all the way to 3GB. I still have RAM and swap available.\n>\n> Was the pack you are trying to index built with that fast-import.c\n> I sent last night? Its possible its doing something weird that\n> pack-index can't handle, such as insert a duplicate object into\n> the same pack...\n\nbuilt with fast-import.\n\n> How big is the pack file? I'd expect pack-index to be using\n> something around 24 MB of memory (24 bytes/entry) but maybe its\n> hanging onto a lot of data (memory leak?) as it decompresses the\n> entries to compute the checksums.\n\nIt is 934MB in size with 985,000 entries.\n\nWhy does resolve_delta in index-pack.c need to be recursive? Is there\na better way to code that routine? If it mmaps the file that uses 1GB\naddress space, why does it need another 1.5GB to build an index?\n\nI had a prior 400MB pack file built with fast-import that I was able\nto index ok.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"24869","messageId":"20060806033222.GD20565@spearce.org","threadId":"5148","inReplyTo":"9e4733910608051958h6144add7td46de70dd8b45a5e@mail.gmail.com","subject":"Re: GPF in index-pack","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-06T03:32:22Z","receivedAt":"2006-08-06T03:32:22Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> On 8/5/06, Shawn Pearce wrote:\n> >Jon Smirl wrote:\n> >> Process size is 2.6GB when the seg fault happen. That's a lot of\n> >> memory to build a pack index over 1M objects.\n> >>\n> >> I'm running a 3:1 process address space split. I wonder why it didn't\n> >> grow all the way to 3GB. I still have RAM and swap available.\n> >\n> >Was the pack you are trying to index built with that fast-import.c\n> >I sent last night? Its possible its doing something weird that\n> >pack-index can't handle, such as insert a duplicate object into\n> >the same pack...\n> \n> built with fast-import.\n> \n> >How big is the pack file? I'd expect pack-index to be using\n> >something around 24 MB of memory (24 bytes/entry) but maybe its\n> >hanging onto a lot of data (memory leak?) as it decompresses the\n> >entries to compute the checksums.\n> \n> It is 934MB in size with 985,000 entries.\n> \n> Why does resolve_delta in index-pack.c need to be recursive? Is there\n> a better way to code that routine? If it mmaps the file that uses 1GB\n> address space, why does it need another 1.5GB to build an index?\n\nProbably the easiest way to code the routine. Delta depth is\nbounded; in the fast-import.c that I sent out last night I hardcoded\nit to 10, which is (I believe) the default for GIT. So long as that\nroutine is recursive only along a single delta chain the recursion\ndepth won't be very high and shouldn't be the problem.\n\n> I had a prior 400MB pack file built with fast-import that I was able\n> to index ok.\n\nDumb luck? Maybe that had no duplicates while this one does?\n\n-- \nShawn.\n"},{"id":"24871","messageId":"9e4733910608052100t463e6fb8gba54e4afde1ab19a@mail.gmail.com","threadId":"5148","inReplyTo":"20060806033222.GD20565@spearce.org","subject":"Re: GPF in index-pack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-06T04:00:11Z","receivedAt":"2006-08-06T04:00:11Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/5/06, Shawn Pearce wrote:\n> Jon Smirl wrote:\n> > On 8/5/06, Shawn Pearce wrote:\n> > >Jon Smirl wrote:\n> > >> Process size is 2.6GB when the seg fault happen. That's a lot of\n> > >> memory to build a pack index over 1M objects.\n> > >>\n> > >> I'm running a 3:1 process address space split. I wonder why it didn't\n> > >> grow all the way to 3GB. I still have RAM and swap available.\n> > >\n> > >Was the pack you are trying to index built with that fast-import.c\n> > >I sent last night? Its possible its doing something weird that\n> > >pack-index can't handle, such as insert a duplicate object into\n> > >the same pack...\n> >\n> > built with fast-import.\n> >\n> > >How big is the pack file? I'd expect pack-index to be using\n> > >something around 24 MB of memory (24 bytes/entry) but maybe its\n> > >hanging onto a lot of data (memory leak?) as it decompresses the\n> > >entries to compute the checksums.\n> >\n> > It is 934MB in size with 985,000 entries.\n> >\n> > Why does resolve_delta in index-pack.c need to be recursive? Is there\n> > a better way to code that routine? If it mmaps the file that uses 1GB\n> > address space, why does it need another 1.5GB to build an index?\n>\n> Probably the easiest way to code the routine. Delta depth is\n> bounded; in the fast-import.c that I sent out last night I hardcoded\n> it to 10, which is (I believe) the default for GIT. So long as that\n> routine is recursive only along a single delta chain the recursion\n> depth won't be very high and shouldn't be the problem.\n\nWhen I put index-pack in gdb at the seg fault, resolve_delta had\nrecursed more than 20,000 times. I stopped looking after that.\n\n> > I had a prior 400MB pack file built with fast-import that I was able\n> > to index ok.\n>\n> Dumb luck? Maybe that had no duplicates while this one does?\n\nIs there a git command to list the sha1's in a pack that doesn't have\nan index? I could sort it, sort it unqiue, and then diff the outputs.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"24872","messageId":"20060806040848.GF20565@spearce.org","threadId":"5148","inReplyTo":"9e4733910608052100t463e6fb8gba54e4afde1ab19a@mail.gmail.com","subject":"Re: GPF in index-pack","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-06T04:08:48Z","receivedAt":"2006-08-06T04:08:48Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jon Smirl wrote:\n> On 8/5/06, Shawn Pearce wrote:\n> >Jon Smirl wrote:\n> >> On 8/5/06, Shawn Pearce wrote:\n> >> >Jon Smirl wrote:\n> >> >> Process size is 2.6GB when the seg fault happen. That's a lot of\n> >> >> memory to build a pack index over 1M objects.\n> >> >>\n> >> >> I'm running a 3:1 process address space split. I wonder why it didn't\n> >> >> grow all the way to 3GB. I still have RAM and swap available.\n> >> >\n> >> >Was the pack you are trying to index built with that fast-import.c\n> >> >I sent last night? Its possible its doing something weird that\n> >> >pack-index can't handle, such as insert a duplicate object into\n> >> >the same pack...\n> >>\n> >> built with fast-import.\n> >>\n> >> >How big is the pack file? I'd expect pack-index to be using\n> >> >something around 24 MB of memory (24 bytes/entry) but maybe its\n> >> >hanging onto a lot of data (memory leak?) as it decompresses the\n> >> >entries to compute the checksums.\n> >>\n> >> It is 934MB in size with 985,000 entries.\n> >>\n> >> Why does resolve_delta in index-pack.c need to be recursive? Is there\n> >> a better way to code that routine? If it mmaps the file that uses 1GB\n> >> address space, why does it need another 1.5GB to build an index?\n> >\n> >Probably the easiest way to code the routine. Delta depth is\n> >bounded; in the fast-import.c that I sent out last night I hardcoded\n> >it to 10, which is (I believe) the default for GIT. So long as that\n> >routine is recursive only along a single delta chain the recursion\n> >depth won't be very high and shouldn't be the problem.\n> \n> When I put index-pack in gdb at the seg fault, resolve_delta had\n> recursed more than 20,000 times. I stopped looking after that.\n\nOuch. I'm not familiar with this code, but looking at right now its\nalso not entirely obviously what its recursing for. Plus dinner\nis trying to be burned on the grill, so my attention is on that\nmore than on GIT. :-)\n \n> >> I had a prior 400MB pack file built with fast-import that I was able\n> >> to index ok.\n> >\n> >Dumb luck? Maybe that had no duplicates while this one does?\n> \n> Is there a git command to list the sha1's in a pack that doesn't have\n> an index? I could sort it, sort it unqiue, and then diff the outputs.\n\nNot that I know of. Packs themselves don't have the SHA1 values and\ngetting them from a pack without an index is a painful exercise as\nyou don't know where the base of an object resides within the pack\nwhen you need it to generate the object's raw content to determine\nits ID.\n\nYea, I'm sure the pack format has some great properties, but storing\nthe base as a 20 byte object ID rather the offset of the base within\nthe pack has its limitations...\n\n-- \nShawn.\n"},{"id":"24874","messageId":"9e4733910608052116u4d58908cj654ea94716b546e6@mail.gmail.com","threadId":"5148","inReplyTo":"20060806040848.GF20565@spearce.org","subject":"Re: GPF in index-pack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-06T04:16:51Z","receivedAt":"2006-08-06T04:16:51Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/6/06, Shawn Pearce wrote:\n> > When I put index-pack in gdb at the seg fault, resolve_delta had\n> > recursed more than 20,000 times. I stopped looking after that.\n>\n> Ouch. I'm not familiar with this code, but looking at right now its\n> also not entirely obviously what its recursing for. Plus dinner\n> is trying to be burned on the grill, so my attention is on that\n> more than on GIT. :-)\n\nIt has recursed 131,000 times before running out of memory. Something\nmust be wrong in the resolve_delta() logic.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"24875","messageId":"9e4733910608052122m7986b04y8eb9c3bbeda5148d@mail.gmail.com","threadId":"5148","inReplyTo":"9e4733910608052116u4d58908cj654ea94716b546e6@mail.gmail.com","subject":"Re: GPF in index-pack","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-06T04:22:55Z","receivedAt":"2006-08-06T04:22:55Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I started another run and added code to record the object_names. I can\nuse the sort utilities then to figure out how many duplicates there\nare. It takes two hours for the run to finish so I won't have results\nuntil tomorrow.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"24888","messageId":"20060806174648.c8cc3b44.vsu@altlinux.ru","threadId":"5148","inReplyTo":"20060806040848.GF20565@spearce.org","subject":"Re: GPF in index-pack","fromName":"Sergey Vlasov","fromEmail":"vsu@altlinux.ru","sentAt":"2006-08-06T13:46:48Z","receivedAt":"2006-08-06T13:46:48Z","isPatch":false,"sender":{"key":"vsu@altlinux.ru","avatar":"https://avatars.githubusercontent.com/u/616082?v=4"},"body":"On Sun, 6 Aug 2006 00:08:48 -0400 Shawn Pearce wrote:\n\n> Jon Smirl wrote:\n> > On 8/5/06, Shawn Pearce wrote:\n> > >Jon Smirl wrote:\n[...]\n> > >> Why does resolve_delta in index-pack.c need to be recursive? Is there\n> > >> a better way to code that routine? If it mmaps the file that uses 1GB\n> > >> address space, why does it need another 1.5GB to build an index?\n> > >\n> > >Probably the easiest way to code the routine. Delta depth is\n> > >bounded; in the fast-import.c that I sent out last night I hardcoded\n> > >it to 10, which is (I believe) the default for GIT. So long as that\n> > >routine is recursive only along a single delta chain the recursion\n> > >depth won't be very high and shouldn't be the problem.\n> > \n> > When I put index-pack in gdb at the seg fault, resolve_delta had\n> > recursed more than 20,000 times. I stopped looking after that.\n> \n> Ouch. I'm not familiar with this code, but looking at right now its\n> also not entirely obviously what its recursing for. Plus dinner\n> is trying to be burned on the grill, so my attention is on that\n> more than on GIT. :-)\n\ngit-pack-objects never creates a pack file with duplicate objects,\ntherefore git-index-pack was never tested on such pack files - no wonder\nthat it breaks.\n\nThe case of patch revert (A -> B -> A again) is probably the problem -\nyour dumb pack generator will probably write this:\n\n\tA\n\tB (delta based on A)\n\tA (delta based on B)\n\ngit-index-pack will first unpack the first copy of A, then notice that A\nis used as a delta base for B and apply the delta, then it will find the\nsecond copy of A and apply that delta, and then it will find B again...\n\nPlease try the patch at the end of this message - it should help to\navoid the infinite recursion in git-index-pack. However, I'm not sure\nthat other git parts won't do something bad when they encounter an index\nwith duplicate sha1 entries (and git-index-pack cannot remove these\nduplicates, because the number of index entries must match the pack\nheader).\n\n> > >> I had a prior 400MB pack file built with fast-import that I was able\n> > >> to index ok.\n> > >\n> > >Dumb luck? Maybe that had no duplicates while this one does?\n> > \n> > Is there a git command to list the sha1's in a pack that doesn't have\n> > an index? I could sort it, sort it unqiue, and then diff the outputs.\n\ngit-index-pack :)\n\n(git-unpack-objects will also have all sha1 values at the end, but the\nside effect of unpacking all objects to separate files is probably not\nwhat you want to get.)\n\n> Not that I know of. Packs themselves don't have the SHA1 values and\n> getting them from a pack without an index is a painful exercise as\n> you don't know where the base of an object resides within the pack\n> when you need it to generate the object's raw content to determine\n> its ID.\n\nYes, this is a problem. git-unpack-objects can unpack all objects in a\nsingle pass, but only because it temporarily saves all deltas which\ncannot be resolved yet, and can read back objects which it has written\nbefore. git-index-pack needs to work without modifying the object\ndatabase, so it works in two passes:\n\n\t/*\n\t * First pass:\n\t * - find locations of all objects;\n\t * - calculate SHA1 of all non-delta objects;\n\t * - remember base SHA1 for all deltas.\n\t */\n\n\t/*\n\t * Second pass:\n\t * - for all non-delta objects, look if it is used as a base for\n\t * deltas;\n\t * - if used as a base, uncompress the object and apply all deltas,\n\t * recursively checking if the resulting object is used as a base\n\t * for some more deltas.\n\t */\n\n-----------------------------------------------------------------------\n\nFrom: Sergey Vlasov \nDate: Sun, 6 Aug 2006 17:28:29 +0400\nSubject: [PATCH] git-index-pack: Avoid infinite recursion if the pack has duplicate objects\n\nAlthough git-pack-objects never creates packs which contain the same\nobject more than once, other tools may be not so careful, so add a check\nto prevents infinite recursion of resolve_delta() for such packs.\n\nSigned-off-by: Sergey Vlasov \n---\n index-pack.c | 7 +++++++\n 1 files changed, 7 insertions(+), 0 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex b39953d..a8e3b1f 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -257,6 +257,13 @@ static void resolve_delta(struct delta_e\n \tunsigned long next_obj_offset;\n \tint j, first, last;\n \n+\t/*\n+\t * Do nothing if this delta was resolved earlier (this can happen if\n+\t * the pack contains duplicate objects for some reason).\n+\t */\n+\tif (obj->real_type != OBJ_DELTA)\n+\t\treturn;\n+\n \tobj->real_type = type;\n \tdelta_data = unpack_raw_entry(obj->offset, &delta_type,\n \t\t\t\t &delta_size, base_sha1,\n-- \n1.4.2.rc3.g23aa\n"}]}