{"thread":{"id":"43232","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","startedAt":"2006-11-07T11:02:12Z","lastAt":"2006-11-13T17:36:14Z","messageCount":21,"participants":["Shawn Pearce","Alex Riesen","Christopher Faylor","Jakub Narebski","Johannes Schindelin","Noel Grandin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"296260","messageId":"81b0412b0611070302h50541cd5mf0758afe0d6befda@mail.gmail.com","threadId":"43232","inReplyTo":null,"subject":"win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-07T11:02:12Z","receivedAt":"2006-11-07T11:02:12Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"For me, it fails even on 332Mb pack:\n\n$ git reset --hard 61bb7fcb\nfatal: packfile .git/objects/pack/pack-ad37...pack cannot be mapped.\n\nInstrumenting the code reveals that it fails on 348876870 bytes.\nStrangely enough, a cygwin program which just reads that pack\nmany times without freeing the mem goes up to 1395507480 (1330Mb).\n\nIf I replace the malloc (cygwin) with native VirtualAlloc(MEM_COMMIT)\nit reports that \"Not enough storage is available to process this command\",\nwhich is just ENOMEM, I think.\n\nThis is a 2Gb machine, with almost 1.3Gb free, so I'm a bit confused,\nwhat could here go wrong (besides what already is wrong).\n\n"},{"id":"296834","messageId":"45507965.3010806@peralex.com","threadId":"43232","inReplyTo":"81b0412b0611070302h50541cd5mf0758afe0d6befda@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Noel Grandin","fromEmail":"noel@peralex.com","sentAt":"2006-11-07T12:17:41Z","receivedAt":"2006-11-07T12:17:41Z","isPatch":false,"sender":{"key":"noel@peralex.com","avatar":null},"body":"Looking at\nhttp://msdn2.microsoft.com/en-us/library/ms810627.aspx\nit looks like\n(a) windows provides 2G of address space to play with\n(b) VirtualAlloc is constrained to allocating contiguous ranges of\nmemory within that 2G address space\n\nSo the problem is probably memory fragmentation.\n\nYou might have more joy if you allocated one HUGE chunk immediately on\nstartup to use for the pack,\nand then kept re-using that chunk.\n\n\nAlex Riesen wrote:\n> For me, it fails even on 332Mb pack:\n>\n> $ git reset --hard 61bb7fcb\n> fatal: packfile .git/objects/pack/pack-ad37...pack cannot be mapped.\n>\n> Instrumenting the code reveals that it fails on 348876870 bytes.\n> Strangely enough, a cygwin program which just reads that pack\n> many times without freeing the mem goes up to 1395507480 (1330Mb).\n>\n> If I replace the malloc (cygwin) with native VirtualAlloc(MEM_COMMIT)\n> it reports that \"Not enough storage is available to process this\n> command\",\n> which is just ENOMEM, I think.\n>\n> This is a 2Gb machine, with almost 1.3Gb free, so I'm a bit confused,\n> what could here go wrong (besides what already is wrong).\n>\n> Any ideas?\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n>\n\n\nNOTICE: This email, and the contents thereof, \nare subject to the standard Peralex email disclaimer, which may \nbe found at: http://www.peralex.com/disclaimer.html\n\nIf you cannot access the disclaimer through the URL attached \n and you wish to receive a copy thereof please send \n an email to email@peralex.com\n"},{"id":"295674","messageId":"81b0412b0611070555u1833cc8ci1d37d45782562df8@mail.gmail.com","threadId":"43232","inReplyTo":"45507965.3010806@peralex.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-07T13:55:01Z","receivedAt":"2006-11-07T13:55:01Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"> So the problem is probably memory fragmentation.\n\nprobably.\n\n> You might have more joy if you allocated one HUGE chunk immediately on\n> startup to use for the pack, and then kept re-using that chunk.\n\nWell, it is not _one_ chunk. The windows/cygwin abomin...combination\nmay take an issue with this: it seem to copy complete address space\nat fork, which even for such a small packs I have here takes system\ndown lightly (yes, I tried it).\n\n"},{"id":"295738","messageId":"eiq9vm$l7c$1@sea.gmane.org","threadId":"43232","inReplyTo":"81b0412b0611070555u1833cc8ci1d37d45782562df8@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-11-07T15:50:59Z","receivedAt":"2006-11-07T15:50:59Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Alex Riesen wrote:\n\n>> So the problem is probably memory fragmentation.\n> \n> probably.\n> \n>> You might have more joy if you allocated one HUGE chunk immediately on\n>> startup to use for the pack, and then kept re-using that chunk.\n> \n> Well, it is not _one_ chunk. The windows/cygwin abomin...combination\n> may take an issue with this: it seem to copy complete address space\n> at fork, which even for such a small packs I have here takes system\n> down lightly (yes, I tried it).\n\nPerhaps planned mmapping only parts of packs would help there.\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n\n"},{"id":"295844","messageId":"81b0412b0611070928l7be83e08kbfc9657937fe7c92@mail.gmail.com","threadId":"43232","inReplyTo":"eiq9vm$l7c$1@sea.gmane.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-07T17:28:00Z","receivedAt":"2006-11-07T17:28:00Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"> Perhaps planned mmapping only parts of packs would help there.\n\n"},{"id":"295062","messageId":"20061107174859.GB26591@spearce.org","threadId":"43232","inReplyTo":"81b0412b0611070928l7be83e08kbfc9657937fe7c92@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-07T17:48:59Z","receivedAt":"2006-11-07T17:48:59Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Alex Riesen wrote:\n> >Perhaps planned mmapping only parts of packs would help there.\n> \n> BTW, can I find this code somewhere to try it out?\n\nThe patches are on the mailing list archives somewhere around\nSept. 5th timeframe from me; as I recall we dropped them as they\ndidn't apply on top of Junio's 64 bit index changes (which were\nreverted out of next anyway).\n\nI was going to push my branch to a public mirror but it turns\nout I deleted that branch. :-(\n\n-- \n"},{"id":"296738","messageId":"81b0412b0611071013j51254a40s749fb6cba65e6873@mail.gmail.com","threadId":"43232","inReplyTo":"20061107174859.GB26591@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-07T18:13:31Z","receivedAt":"2006-11-07T18:13:31Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"> The patches are on the mailing list archives somewhere around\n> Sept. 5th timeframe from me; as I recall we dropped them as they\n> didn't apply on top of Junio's 64 bit index changes (which were\n> reverted out of next anyway).\n\nI seem to be unable to find them. Does anyone still has the\npatches/branch please? Junio, you did sound interested?\n"},{"id":"297256","messageId":"20061107181808.GC26591@spearce.org","threadId":"43232","inReplyTo":"81b0412b0611071013j51254a40s749fb6cba65e6873@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-07T18:18:08Z","receivedAt":"2006-11-07T18:18:08Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Alex Riesen wrote:\n> >The patches are on the mailing list archives somewhere around\n> >Sept. 5th timeframe from me; as I recall we dropped them as they\n> >didn't apply on top of Junio's 64 bit index changes (which were\n> >reverted out of next anyway).\n> \n> I seem to be unable to find them. Does anyone still has the\n> patches/branch please? Junio, you did sound interested?\n> (God, I wish I have paid attention then...)\n\nJunio definately wants to implement at least something similar\nto what I did; I just happened to do it at the wrong time. :-)\n\nI keep saying I'll get back around to rewriting the patch (as the\naffected regions of git have been heavily modified recently by Nico\nand thus it doesn't apply) but I keep not finding the time.\n\nMaybe that's because I was working on git-gui...\n\n-- \n"},{"id":"298650","messageId":"20061107182636.GD26591@spearce.org","threadId":"43232","inReplyTo":"20061107181808.GC26591@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-07T18:26:36Z","receivedAt":"2006-11-07T18:26:36Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Shawn Pearce wrote:\n> Alex Riesen wrote:\n> > >The patches are on the mailing list archives somewhere around\n> > >Sept. 5th timeframe from me; as I recall we dropped them as they\n> > >didn't apply on top of Junio's 64 bit index changes (which were\n> > >reverted out of next anyway).\n> > \n> > I seem to be unable to find them. Does anyone still has the\n> > patches/branch please? Junio, you did sound interested?\n> > (God, I wish I have paid attention then...)\n\nYou can't find them because I never sent them. *sigh*\n\nToo f'ing bad this .patch I created with format-patch doesn't say\nwhat commits it was based on, 'cause I can't find anything it will\napply too. Or better, too f'ing bad I deleted that branch. *sigh*\n\n-- \n"},{"id":"294091","messageId":"20061107185648.GE26591@spearce.org","threadId":"43232","inReplyTo":"20061107182636.GD26591@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-07T18:56:48Z","receivedAt":"2006-11-07T18:56:48Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Shawn Pearce wrote:\n> Shawn Pearce wrote:\n> > Alex Riesen wrote:\n> > > >The patches are on the mailing list archives somewhere around\n> > > >Sept. 5th timeframe from me; as I recall we dropped them as they\n> > > >didn't apply on top of Junio's 64 bit index changes (which were\n> > > >reverted out of next anyway).\n> > > \n> > > I seem to be unable to find them. Does anyone still has the\n> > > patches/branch please? Junio, you did sound interested?\n> > > (God, I wish I have paid attention then...)\n> \n> You can't find them because I never sent them. *sigh*\n> \n> Too f'ing bad this .patch I created with format-patch doesn't say\n> what commits it was based on, 'cause I can't find anything it will\n> apply too. Or better, too f'ing bad I deleted that branch. *sigh*\n\nThis thread has now proven without any shadow of a doubt that I can\nbe an idiot sometimes.\n\nIn this case my patch didn't apply because it was 3rd in a series;\nI had two of those patches but lacked the third (a simple cleanup\npatch). Redoing that simple cleanup let everything apply.\n\n\nI've pushed the changes out to repo.or.cz:\n\n\thttp://repo.or.cz/w/git/fastimport.git\n\nin the window-mapping branch. Note that this is based on a slightly\nolder version of Git (v1.4.2). There are two \"tuneables\" on line 376\nof sha1_file.c, this is the maximum amount of memory (in bytes) to\ndenote to packs and the maximum chunk size of each pack (in bytes).\nI planned on making these configuration options but didn't get to\nthat yet.\n\n-- \n"},{"id":"297198","messageId":"20061107192759.GA4484@steel.home","threadId":"43232","inReplyTo":"20061107182636.GD26591@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-11-07T19:27:59Z","receivedAt":"2006-11-07T19:27:59Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Shawn Pearce, Tue, Nov 07, 2006 19:26:36 +0100:\n> Too f'ing bad this .patch I created with format-patch doesn't say\n> what commits it was based on, 'cause I can't find anything it will\n> apply too. Or better, too f'ing bad I deleted that branch. *sigh*\n\nMaybe you just send the patch anyway? It could give someone an idea\nwhere to start, or what not to do...\n"},{"id":"298022","messageId":"20061107231130.GA5141@steel.home","threadId":"43232","inReplyTo":"20061107185648.GE26591@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-11-07T23:11:30Z","receivedAt":"2006-11-07T23:11:30Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Shawn Pearce, Tue, Nov 07, 2006 19:56:48 +0100:\n> I've pushed the changes out to repo.or.cz:\n> \n> \thttp://repo.or.cz/w/git/fastimport.git\n> \n> in the window-mapping branch. Note that this is based on a slightly\n> older version of Git (v1.4.2). There are two \"tuneables\" on line 376\n> of sha1_file.c, this is the maximum amount of memory (in bytes) to\n> denote to packs and the maximum chunk size of each pack (in bytes).\n\nThanks.\nI couldn't help noticing that the interface to the packs data is\na bit complex:\n\n unsigned char *use_pack(struct packed_git *p,\n\t\t\t struct pack_window **window,\n\t\t\t unsigned long offset,\n\t\t\t unsigned int *left);\n void unuse_pack(struct pack_window **w);\n\nCan I suggest something like below?\n\n unsigned char *use_pack(struct packed_git *p,\n\t\t\t off_t offset, size_t size, size_t *mapped);\n void unuse_pack(struct packed_git *p, off_t offset, size_t size);\n or\n void unuse_pack(struct packed_git *p, unsigned char *data);\n\n (where size/maxsize is the amount of bytes at the offset in the\n pack file the caller was asking for. use_pack would fail if offset\n or size do not pass sanity checks (offset past end of file, size\n is 0). The mapped argument would get the length of the data\n actually mapped, and can be less than requested, subject to end of\n data). The window sliding code seem to have all information it\n needs with this set of arguments.\n\nOr am I missing something very obvious, and something like this\nis just not feasible for some reasons?\n\nI'm asking because I tried to slowly rebase the window-mapping up and\nmerge the newer branches into it (to get it working with more recent\ncode). At some point I came over conflicts and one of them got me\nthinking about the interface. That's the part:\n\n<<<<<<< HEAD/sha1_file.c\n\tc = *use_pack(p, w, offset++, NULL);\n\t*type = (c >> 4) & 7;\n\tsize = c & 15;\n\tshift = 4;\n\twhile (c & 0x80) {\n\t\tc = *use_pack(p, w, offset++, NULL);\n\t\tsize += (c & 0x7f) << shift;\n\t\tshift += 7;\n\t}\n\t*sizep = size;\n\treturn offset;\n=======\n\tused = unpack_object_header_gently((unsigned char *)p->pack_base +\n\t\t\t\t\t offset,\n\t\t\t\t\t p->pack_size - offset, type, sizep);\n\tif (!used)\n\t\tdie(\"object offset outside of pack file\");\n\n\treturn offset + used;\n>>>>>>> f685d07de045423a69045e42e72d2efc22a541ca/sha1_file.c\n\nI was almost about to move your code into unpack_object_header_gently,\nbut ... The header isn't that big, is it? It is variable in the pack,\nbut the implementation of the parser is at the moment restricted by\nthe type we use for object size (unsigned long for the particular\nplatform). For example:\n\n\t/* Object size is in the first 4 bits, and in the low 7 bits\n\t * of the subsequent bytes which have high bit set */\n\t#define MAX_LOCAL_HDRSIZE ((sizeof(long) * 8 - 4) / 7 + 1)\n\tunsigned long size;\n\tunsigned char *header = use_pack(p, offset, MAX_LOCAL_HDRSIZE, &size);\n\tif (!header)\n\t die(\"object header offset out of range\");\n\t/* unpack_object_header_gently takes care about truncated\n\t * headers, by returning 0 if it encounters one */\n\tused = unpack_object_header_gently(header, size, type, sizep);\n\nWouldn't have to change unpack_object_header_gently at all.\n\n(BTW, current unpack_object_header_gently does not use it's len\nargument to check if there actually is enough data to hold at least\nminimal header. Is the size of mapped data checked for correctness\nsomewhere before?)\n"},{"id":"294332","messageId":"20061108051914.GB28498@spearce.org","threadId":"43232","inReplyTo":"20061107231130.GA5141@steel.home","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-08T05:19:14Z","receivedAt":"2006-11-08T05:19:14Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Alex Riesen wrote:\n> I couldn't help noticing that the interface to the packs data is\n> a bit complex:\n> \n> unsigned char *use_pack(struct packed_git *p,\n> \t\t\t struct pack_window **window,\n> \t\t\t unsigned long offset,\n> \t\t\t unsigned int *left);\n> void unuse_pack(struct pack_window **w);\n> \n> Or am I missing something very obvious, and something like this\n> is just not feasible for some reasons?\n\nThe use counter. Every time someone asks for a pointer into the\npack they need to lock that window into memory to prevent us from\ngarbage collecting it by unmapping it to make room for another\nwindow that the application needs.\n \n> I was almost about to move your code into unpack_object_header_gently,\n> but ... The header isn't that big, is it? It is variable in the pack,\n> but the implementation of the parser is at the moment restricted by\n> the type we use for object size (unsigned long for the particular\n> platform). For example:\n\nAll true. However what happens when the header spans two windows?\nLets say I have the first 4 MiB mapped and the next 4 MiB mapped in\na different window; these are not necessarily at the same locations\nwithin memory. Now if an object header is split over these two\nthen some bytes are at the end of the first window and the rest\nare at the start of the next window.\n\nI can't just say \"make sure we have at least X bytes available\nbefore starting to decode the header, as to do that in this case\nwe'd have to unmap BOTH windows and remap a new one which keeps\nthat very small header fully contiguous in memory. That's thrashing\nthe VM page tables for really no benefit.\n \n> (BTW, current unpack_object_header_gently does not use it's len\n> argument to check if there actually is enough data to hold at least\n> minimal header. Is the size of mapped data checked for correctness\n> somewhere before?)\n\nYes. Somewhere. I think we make sure there's at least 20 bytes\nin the pack remaining before we start to decode a header. We must\nhave at least 20 as that's the trailing SHA1 checksum of the entire\npack. :-)\n\n-- \n"},{"id":"297599","messageId":"81b0412b0611080537k1087be66x1a4a9686b43d7b46@mail.gmail.com","threadId":"43232","inReplyTo":"20061108051914.GB28498@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-08T13:37:55Z","receivedAt":"2006-11-08T13:37:55Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"> > I couldn't help noticing that the interface to the packs data is\n> > a bit complex:\n> >\n> > unsigned char *use_pack(struct packed_git *p,\n> > struct pack_window **window,\n> > unsigned long offset,\n> > unsigned int *left);\n> > void unuse_pack(struct pack_window **w);\n> >\n> > Or am I missing something very obvious, and something like this\n> > is just not feasible for some reasons?\n>\n> The use counter. Every time someone asks for a pointer into the\n> pack they need to lock that window into memory to prevent us from\n> garbage collecting it by unmapping it to make room for another\n> window that the application needs.\n\nI think the counters can be kept in struct packed_git somewhere. Given mmap\ngranularity, and the fact that not all of the pack is used in normal case\n(and the granularity help us in the worst case) the memory used up by the\npage counters shouldn't be too much.\n\n> > I was almost about to move your code into unpack_object_header_gently,\n> > but ... The header isn't that big, is it? It is variable in the pack,\n> > but the implementation of the parser is at the moment restricted by\n> > the type we use for object size (unsigned long for the particular\n> > platform). For example:\n>\n> All true. However what happens when the header spans two windows?\n> Lets say I have the first 4 MiB mapped and the next 4 MiB mapped in\n> a different window; these are not necessarily at the same locations\n> within memory. Now if an object header is split over these two\n> then some bytes are at the end of the first window and the rest\n> are at the start of the next window.\n\nAssuming these are adjacent windows, we can just increment counters on the\nall touched pages (at least the two together) and return the pointer into\nthe lowest page. Otherwise - time for garbage collection (why produce the\ngarbage at all, btw?) and remap.\n\n> I can't just say \"make sure we have at least X bytes available\n> before starting to decode the header, as to do that in this case\n> we'd have to unmap BOTH windows and remap a new one which keeps\n> that very small header fully contiguous in memory. That's thrashing\n> the VM page tables for really no benefit.\n\nYou can't mmap less than a page, can you? So it's actually never a small\nportion, but at least 4k on x86.\n\n> > (BTW, current unpack_object_header_gently does not use it's len\n> > argument to check if there actually is enough data to hold at least\n> > minimal header. Is the size of mapped data checked for correctness\n> > somewhere before?)\n>\n> Yes. Somewhere. I think we make sure there's at least 20 bytes\n> in the pack remaining before we start to decode a header. We must\n> have at least 20 as that's the trailing SHA1 checksum of the entire\n> pack. :-)\n\n"},{"id":"297423","messageId":"20061108171131.GA13487@spearce.org","threadId":"43232","inReplyTo":"81b0412b0611080537k1087be66x1a4a9686b43d7b46@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-08T17:11:31Z","receivedAt":"2006-11-08T17:11:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Alex Riesen wrote:\n> >The use counter. Every time someone asks for a pointer into the\n> >pack they need to lock that window into memory to prevent us from\n> >garbage collecting it by unmapping it to make room for another\n> >window that the application needs.\n> \n> I think the counters can be kept in struct packed_git somewhere. Given mmap\n> granularity, and the fact that not all of the pack is used in normal case\n> (and the granularity help us in the worst case) the memory used up by the\n> page counters shouldn't be too much.\n\nWe already have a counter in struct packed_git (pack_use_cnt),\nbut this counter and struct permits only one mmap per pack.\nWe actually want at least two, but really four sliding windows\nper pack. Here's why:\n\nThe commits are at the front of the pack, trees are somewhere just\nbehind them, and the blobs are behind that. The objects are also\nloosely ordered by time, so the further back in the commit graph\nyou go the associated data is closer to the end of the pack file.\n\nIf a pack file is larger than our mmap unit (32 MiB in my\nimplementation) then we will mmap it in at least two different\nnon-contiguous windows. In the case of the Linux kernel pack\n(>128 MiB now) that's at least 4 windows to mmap the entire file.\n\nIf we are a commit parsing application (merge-base, blame, log,\nrev-list, etc...) we need to walk back along the commit DAG to\nidentify objects of interest. So we need the front of the pack\nmmap'd. But if we have a path filter than we also need to mmap the\nmiddle of the pack to get access to the trees; and if we need blob\ndata than we need to mmap near the back too to get those.\n\nSo really an application wants 2-3 sliding windows of a pack file;\none focused on the front covering the unparsed commits; one slightly\nbehind that focused on the trees; and one further back focused on\nthe blobs. Oh and you may actually need a 4th to do delta base\ndecompression. If you work with less than 4 sliding windows then\nyou are going to be thrashing the page tables somewhat as you toss\nout one window to load another, then toss that window out just to\ngo back and reaccess the one you previously tossed.\n\nIf the sliding window size is large enough that nearly all commits\nand trees fit into it then this is mostly a non-issue. Heck the\ngit.git pack is hovering around 10 MiB these days; that's less than\none window. But when the pack is larger than a couple of windows\nthis really starts to matter... and that's specifically the type\nof repository this feature is designed for.\n\n> >All true. However what happens when the header spans two windows?\n> >Lets say I have the first 4 MiB mapped and the next 4 MiB mapped in\n> >a different window; these are not necessarily at the same locations\n> >within memory. Now if an object header is split over these two\n> >then some bytes are at the end of the first window and the rest\n> >are at the start of the next window.\n> \n> Assuming these are adjacent windows, we can just increment counters on the\n> all touched pages (at least the two together) and return the pointer into\n> the lowest page. Otherwise - time for garbage collection (why produce the\n> garbage at all, btw?) and remap.\n\nThey are adjacent in the pack file but not necessarily in virtual memory!\n\nI'm just asking the OS to return me a mapping for a chunk of a file;\nI'm not also trying to make them contiguous in virtual memory.\n\nMaking adjacent pack file chunks contiguous in virtual memory is even\nmore code and probably going to cause problems at runtime. How do\nwe know what area of virtual memory is mostly unused on any given\nplatform? Any application that I have seen that tries to manage\nits own virtual memory layout is usually full of platform specific\nhacks to make it work everywhere. Lets not go there with Git.\n\nThe garbage creation is to account for the 2-4 windows required\nby most applications. Most of the time each window is unused;\nwe really only have two windows in use during delta decompression,\nat all other times we really only have 1 window in use. The commit\nparsing applications don't keep the commit window in use when they\ngo access a tree or a blob.\n\nConsequently we want the garbage there. Actually I shouldn't have\nused garbage: the correct term would be LRU managed cache. :-)\nWhen we need a new window and we would exceed our maximum limit\n(128 MiB in my implementation) we unmap the least recently used\nwindow which is not currently in use.\n\n> >I can't just say \"make sure we have at least X bytes available\n> >before starting to decode the header, as to do that in this case\n> >we'd have to unmap BOTH windows and remap a new one which keeps\n> >that very small header fully contiguous in memory. That's thrashing\n> >the VM page tables for really no benefit.\n> \n> You can't mmap less than a page, can you? So it's actually never a small\n> portion, but at least 4k on x86.\n\nNo. But we always mmap even more than that per window; e.g. 32\nMiB. Since the header is way smaller than 4k we're talking about\nunmapping two 32 MiB windows and remapping one of them just one\npage earlier to get the whole object header in a contiguous region.\nI'm not a kernel hacker (nor do I pretended to be) but from what I\nknow of the x86 page table structure that's not exactly the fastest\noperation we can ask the system to perform. :)\n\nI could be wrong. It may not matter. But I think its crazy to\nunmap otherwise valid mappings just because 2 bytes are on the\nwrong side of an arbitrary boundary.\n\n-- \n"},{"id":"295424","messageId":"20061108192214.GA21892@trixie.casa.cgf.cx","threadId":"43232","inReplyTo":"81b0412b0611070555u1833cc8ci1d37d45782562df8@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Christopher Faylor","fromEmail":"cgf-use-the-mailinglist-please@sourceware.org","sentAt":"2006-11-08T19:22:14Z","receivedAt":"2006-11-08T19:22:14Z","isPatch":false,"sender":{"key":"cgf-use-the-mailinglist-please@sourceware.org","avatar":null},"body":"On Tue, Nov 07, 2006 at 02:55:01PM +0100, Alex Riesen wrote:\n>>So the problem is probably memory fragmentation.\n>\n>probably.\n>\n>>You might have more joy if you allocated one HUGE chunk immediately on\n>>startup to use for the pack, and then kept re-using that chunk.\n>\n>Well, it is not _one_ chunk. The windows/cygwin abomin...combination\n\nI would like to ask you, once again, to exercise some adult self-control\nwhen you feel compelled to answer questions about Cygwin. If you need\nto vent your frustration in some direction, I'd suggest getting a dog.\nThey can look very contrite when you yell at them even if they didn't\nactually do anything wrong.\n\n>may take an issue with this: it seem to copy complete address space\n>at fork, which even for such a small packs I have here takes system\n>down lightly (yes, I tried it).\n\nYes, Cygwin copies the heap on fork since Windows doesn't implement fork.\n\nFWIW, Cygwin's malloc is based on Doug Lea's malloc. It reverts to\nusing mmap when allocating memory above a certain threshhold.\n\ncgf\n--\nChristopher Faylor\t\t\tspammer? ->\taaaspam@sourceware.org\nCygwin Co-Project Leader\t\t\t\taaaspam@duffek.com\n"},{"id":"298045","messageId":"20061108213314.GA4437@steel.home","threadId":"43232","inReplyTo":"20061108171131.GA13487@spearce.org","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"fork0@t-online.de","sentAt":"2006-11-08T21:33:14Z","receivedAt":"2006-11-08T21:33:14Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Shawn Pearce, Wed, Nov 08, 2006 18:11:31 +0100:\n> > >All true. However what happens when the header spans two windows?\n> > >Lets say I have the first 4 MiB mapped and the next 4 MiB mapped in\n> > >a different window; these are not necessarily at the same locations\n> > >within memory. Now if an object header is split over these two\n> > >then some bytes are at the end of the first window and the rest\n> > >are at the start of the next window.\n> > \n> > Assuming these are adjacent windows, we can just increment counters on the\n> > all touched pages (at least the two together) and return the pointer into\n> > the lowest page. Otherwise - time for garbage collection (why produce the\n> > garbage at all, btw?) and remap.\n> \n> They are adjacent in the pack file but not necessarily in virtual memory!\n\nOh, right! Don't know why I thought the mapped regions would be\nconnected.\n\n> The garbage creation is to account for the 2-4 windows required\n> by most applications. Most of the time each window is unused;\n> we really only have two windows in use during delta decompression,\n> at all other times we really only have 1 window in use. The commit\n> parsing applications don't keep the commit window in use when they\n> go access a tree or a blob.\n\nSo they actually can call unuse_pack to unmap the window,\nbut it's kept for caching reasons?\n\n> Consequently we want the garbage there. Actually I shouldn't have\n> used garbage: the correct term would be LRU managed cache. :-)\n> When we need a new window and we would exceed our maximum limit\n> (128 MiB in my implementation) we unmap the least recently used\n> window which is not currently in use.\n\nYep, noticed that :) Just wondered why.\n\n> I could be wrong. It may not matter. But I think its crazy to\n> unmap otherwise valid mappings just because 2 bytes are on the\n> wrong side of an arbitrary boundary.\n\nYou're right, would be unfortunate to remap too often.\n\nuse_pack always maps at least 20 bytes, if I understand in_window and\nits use correctly. Actually, now I'm staring at it longer, I think the\ninterface I suggested does almost the same, just allows to configure\n(well, hint at) the amount of bytes to be mapped in.\n\nI still can't let go of the idea to get as much data as possible with\njust one call to sliding window code. Calling use_pack for every byte\njust does not seem right.\n"},{"id":"298541","messageId":"20061108222837.GA14446@spearce.org","threadId":"43232","inReplyTo":"20061108213314.GA4437@steel.home","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-11-08T22:28:37Z","receivedAt":"2006-11-08T22:28:37Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Alex Riesen wrote:\n> Shawn Pearce, Wed, Nov 08, 2006 18:11:31 +0100:\n> > The garbage creation is to account for the 2-4 windows required\n> > by most applications. Most of the time each window is unused;\n> > we really only have two windows in use during delta decompression,\n> > at all other times we really only have 1 window in use. The commit\n> > parsing applications don't keep the commit window in use when they\n> > go access a tree or a blob.\n> \n> So they actually can call unuse_pack to unmap the window,\n> but it's kept for caching reasons?\n\nActually very few parts of the code even know about the windows.\nReally the only parts that know it are the ones that directly\naccess the pack file, which is mostly restricted to sha1_file.c.\n\nSo since all access is through the more public interfaces what\nyou find is that the application code never keeps the window.\nWe are always doing use_pack/unuse_pack on every object access.\nSo the window is almost never in use. So if we didn't hang onto\nit in an LRU we would be in a world of hurt performance wise.\n\n> > I could be wrong. It may not matter. But I think its crazy to\n> > unmap otherwise valid mappings just because 2 bytes are on the\n> > wrong side of an arbitrary boundary.\n> \n> You're right, would be unfortunate to remap too often.\n> \n> use_pack always maps at least 20 bytes, if I understand in_window and\n> its use correctly. Actually, now I'm staring at it longer, I think the\n> interface I suggested does almost the same, just allows to configure\n> (well, hint at) the amount of bytes to be mapped in.\n\nTrue; but if you look nobody wants more than 20 bytes. They either\nwant <20 for the object header or 20 for the base object id in\na delta. Otherwise they are shoving the data into zlib which\ndoesn't care. No need to configure it, just shove it in.\n \n> I still can't let go of the idea to get as much data as possible with\n> just one call to sliding window code. Calling use_pack for every byte\n> just does not seem right.\n\nTrue. But the only other idea I have is to copy the data into a\nbuffer for the caller. Which we use only for the header section,\nbeing that its small... we already copy the delta base (20 bytes)\nonto the stack during decompression. Might as well copy the header\nto decompress it. Then you can batch up the range checks to at\nworst no more than 2 range checks per header.\n\n-- \n"},{"id":"296067","messageId":"Pine.LNX.4.63.0611131333000.13772@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"43232","inReplyTo":"81b0412b0611070302h50541cd5mf0758afe0d6befda@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-11-13T12:45:16Z","receivedAt":"2006-11-13T12:45:16Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 7 Nov 2006, Alex Riesen wrote:\n\n> For me, it fails even on 332Mb pack:\n> \n> $ git reset --hard 61bb7fcb\n> fatal: packfile .git/objects/pack/pack-ad37...pack cannot be mapped.\n> \n> Instrumenting the code reveals that it fails on 348876870 bytes.\n> Strangely enough, a cygwin program which just reads that pack\n> many times without freeing the mem goes up to 1395507480 (1330Mb).\n> \n> If I replace the malloc (cygwin) with native VirtualAlloc(MEM_COMMIT)\n> it reports that \"Not enough storage is available to process this command\",\n> which is just ENOMEM, I think.\n\nThis looks to me as if you have NO_MMAP=1 set in your Makefile (which I \nalso do automatically when compiling on cygwin).\n\nThe old problem: Windows does not have fork.\n\n And before somebody starts cygwin bashing: don't. It is not \ncygwin's problem, it is Windows'. The cygwin people worked long and hard \non something truly useful, and it helps me _every_ time I have to work on \na Windows platform (which _is_ utter crap). Some problems of Windows are \nso unhideable though, that even cygwin cannot work around them. \n\n\nCygwin provides a mmap(), which works remarkably well even with the \nemulated fork(), but one thing is not possible: since mmap()ed files \nhave to be _reopened_ after a fork(), and git uses the \nopen-temp-file-then-delete-it-but-continue-to-use-it paradigm quite often, \nwe work around it by setting NO_MMAP=1. Again, this is _not_ Cygwin's \nfault!\n\nAnd I think that a mmap() of 332MB would not fail.\n\nLong time ago (to be precise, July 18th), Linus suggested (in Message-Id: \n) to find out which mmap() \ncalls are _not_ used before a fork(), and not emulate them by malloc().\n\nI never came around to do that, but maybe others do?\n\nCiao,\nDscho\n"},{"id":"296647","messageId":"81b0412b0611130934u67f4da98rd39412b07f2169c0@mail.gmail.com","threadId":"43232","inReplyTo":"Pine.LNX.4.63.0611131333000.13772@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-13T17:34:39Z","receivedAt":"2006-11-13T17:34:39Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"> This looks to me as if you have NO_MMAP=1 set in your Makefile (which I\n> also do automatically when compiling on cygwin).\n\nKind of. I use mmap (from cygwin) in specially selected places.\nI remember posting the patches once.\n\n> The old problem: Windows does not have fork.\n\nAs if it have anything non-fubar at all...\n\n> And before somebody starts cygwin bashing: don't. It is not\n> cygwin's problem, it is Windows'.\n\nI didn't bash cygwin. I just pity the whole effort (and myself, atm).\n\n> And I think that a mmap() of 332MB would not fail.\n\nIt does not in isolated environment. It just fails in my particular context.\nAnd before anyone suggests: yes, CreateFileMapping, and VirtualAlloc were\ntried. They do return errors suggesting the same reason (ENOMEM).\n\n> Long time ago (to be precise, July 18th), Linus suggested (in Message-Id:\n> ) to find out which mmap()\n> calls are _not_ used before a fork(), and not emulate them by malloc().\n>\n> I never came around to do that, but maybe others do?\n\nI'm trying to find some time to make Shawn's sliding window work.\nIt looks promising (patches, not the time).\n\n\nOn 11/13/06, Johannes Schindelin wrote:\n> Hi,\n>\n> On Tue, 7 Nov 2006, Alex Riesen wrote:\n>\n> > For me, it fails even on 332Mb pack:\n> >\n> > $ git reset --hard 61bb7fcb\n> > fatal: packfile .git/objects/pack/pack-ad37...pack cannot be mapped.\n> >\n> > Instrumenting the code reveals that it fails on 348876870 bytes.\n> > Strangely enough, a cygwin program which just reads that pack\n> > many times without freeing the mem goes up to 1395507480 (1330Mb).\n> >\n> > If I replace the malloc (cygwin) with native VirtualAlloc(MEM_COMMIT)\n> > it reports that \"Not enough storage is available to process this command\",\n> > which is just ENOMEM, I think.\n>\n> This looks to me as if you have NO_MMAP=1 set in your Makefile (which I\n> also do automatically when compiling on cygwin).\n>\n> The old problem: Windows does not have fork.\n>\n> And before somebody starts cygwin bashing: don't. It is not\n> cygwin's problem, it is Windows'. The cygwin people worked long and hard\n> on something truly useful, and it helps me _every_ time I have to work on\n> a Windows platform (which _is_ utter crap). Some problems of Windows are\n> so unhideable though, that even cygwin cannot work around them.\n> \n>\n> Cygwin provides a mmap(), which works remarkably well even with the\n> emulated fork(), but one thing is not possible: since mmap()ed files\n> have to be _reopened_ after a fork(), and git uses the\n> open-temp-file-then-delete-it-but-continue-to-use-it paradigm quite often,\n> we work around it by setting NO_MMAP=1. Again, this is _not_ Cygwin's\n> fault!\n>\n> And I think that a mmap() of 332MB would not fail.\n>\n> Long time ago (to be precise, July 18th), Linus suggested (in Message-Id:\n> ) to find out which mmap()\n> calls are _not_ used before a fork(), and not emulate them by malloc().\n>\n> I never came around to do that, but maybe others do?\n>\n> Ciao,\n> Dscho\n>\n"},{"id":"294307","messageId":"81b0412b0611130936i6d5fe595y4ee3c7bf9c372eab@mail.gmail.com","threadId":"43232","inReplyTo":"81b0412b0611130934u67f4da98rd39412b07f2169c0@mail.gmail.com","subject":"Re: win2k/cygwin cannot handle even moderately sized packs","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2006-11-13T17:36:14Z","receivedAt":"2006-11-13T17:36:14Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"oh, damn. Sorry for the appended copy. It's behind a broken corporate\n"}]}