{"thread":{"id":"7449","subject":"[RFC] Packing large repositories","startedAt":"2007-03-28T07:05:08Z","lastAt":"2007-04-03T05:39:59Z","messageCount":15,"participants":["Dana How","Linus Torvalds","Shawn O. Pearce","Nicolas Pitre","Geert Bosch","Junio C Hamano","Sam Vilain"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"38234","messageId":"56b7f5510703280005o7998d65pcbcd4636b46d8d23@mail.gmail.com","threadId":"7449","inReplyTo":null,"subject":"[RFC] Packing large repositories","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-03-28T07:05:08Z","receivedAt":"2007-03-28T07:05:08Z","isPatch":false,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"Hi,\n\nI just started experimenting with using git on\na large engineering project which has used p4 so far.\nPart of a checkout is about 55GB;\nafter an initial commit and packing I have a 20GB+ packfile.\nOf course this is unusable, since object_entry's in an .idx\nfile have only 32 bits in their offset fields. I conclude that\nfor such large projects, git-repack/git-pack-objects would need\nnew options to control maximum packfile size.\n\n[ I don't think this affects git-{fetch,receive,send}-pack\nsince apparently only the pack is transferred and it only uses\nthe variable-length size and delta base offset encodings\n(of course the accumulation of the 7 bit chunks in a 32b\n variable would need to be corrected, but at least the data\nformat doesn't change).]\n\nSo I am toying with adding a --limit flag to git-repack/git-pack-objects.\nThis cannot be used with --stdout. If specified, e.g.\n git-repack --limit 2g\nthen each packfile created could be at most 2^31-1 bytes in size.\nIt's possible that multiple packfiles would be created in one shot.\nThus git-pack-objects could write multiple names to stdout\nand git-repack would need to be updated accordingly.\n\nFinally, I wonder if having tree/commit/tag objects mixed into\nsuch large packfiles would be a performance hit.\n(Or maybe this will only appear once I have real history,\n not just a large initial commit. But I can say that I now have 48K\n data blobs and 9K others.)\nTo find out, I may experiment with adding a --type= option\nto git-repack/git-pack-objects. Thus typing\n git-repack --limit 2g --type=tree+commit+tag,blob\nwould cause git-pack-objects to make 2 passes over its internal\nobject list. On the first, it would pack tree, commit, and tag objects.\nOn the second, it would pack blobs. Each pass would write at\nleast one independent packfile (or more with --limit). This would also\nallow different incremental repacking strategies/schedules for different types.\n\nComments?\n\nThanks!\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n"},{"id":"38257","messageId":"Pine.LNX.4.64.0703280943450.6730@woody.linux-foundation.org","threadId":"7449","inReplyTo":"56b7f5510703280005o7998d65pcbcd4636b46d8d23@mail.gmail.com","subject":"Re: [RFC] Packing large repositories","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-28T16:53:07Z","receivedAt":"2007-03-28T16:53:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 28 Mar 2007, Dana How wrote:\n> \n> I just started experimenting with using git on\n> a large engineering project which has used p4 so far.\n> Part of a checkout is about 55GB;\n> after an initial commit and packing I have a 20GB+ packfile.\n\nOh wow. You don't do half measures, do you ;)\n\n> Of course this is unusable, since object_entry's in an .idx\n> file have only 32 bits in their offset fields. I conclude that\n> for such large projects, git-repack/git-pack-objects would need\n> new options to control maximum packfile size.\n\nEither that, or update the index file format. I think that your approach \nof having a size limiter is actually the *better* one, though. \n\n> [ I don't think this affects git-{fetch,receive,send}-pack\n> since apparently only the pack is transferred and it only uses\n> the variable-length size and delta base offset encodings\n> (of course the accumulation of the 7 bit chunks in a 32b\n> variable would need to be corrected, but at least the data\n> format doesn't change).]\n\nWell, it does affect fetching, in that \"git index-pack\" obviously would \nalso need to be taught how to split the resulting indexed packs up into \nmultiple smaller ones from one large incoming one. But that shouldn't be \nfundamentally hard either, apart from the inconvenience of having to \nrewrite the object count in the pack headers..\n\nTo avoid that issue, it may be that it's actually better to split things \nup at pack-generation time *even* for the case of --stdout, exactly so \nthat \"git index-pack\" wouldn't have to split things up (we potentially \nknow a lot more about object sizes up-front at pack-generation time than \nwe know at re-indexing).\n\n> So I am toying with adding a --limit flag to\n> git-repack/git-pack-objects.\n\nSounds very sane.\n\n> This cannot be used with --stdout. If specified, e.g.\n> git-repack --limit 2g\n> then each packfile created could be at most 2^31-1 bytes in size.\n\nSounds good, apart from the caveat above about \"--stdout\" that needs some \nthinking about.\n\n> It's possible that multiple packfiles would be created in one shot.\n> Thus git-pack-objects could write multiple names to stdout\n> and git-repack would need to be updated accordingly.\n\nYes. That seems to be the least of all problems.\n\n> Finally, I wonder if having tree/commit/tag objects mixed into\n> such large packfiles would be a performance hit.\n\nMy initial reaction is that it's best to start off without worrying about \nthat, and just do everything in the order that we do now (ie \"sort by \ntype first, recency second\") and just split when we hit the size limit.\n\nBut if you actually want to experiment with different organizations, I \ndon't think that's wrong. I would just personally start without it.\n\n\t\tLinus\n"},{"id":"38375","messageId":"20070330062324.GU13247@spearce.org","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703280943450.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-30T06:23:25Z","receivedAt":"2007-03-30T06:23:25Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds wrote:\n> On Wed, 28 Mar 2007, Dana How wrote:\n> > Of course this is unusable, since object_entry's in an .idx\n> > file have only 32 bits in their offset fields. I conclude that\n> > for such large projects, git-repack/git-pack-objects would need\n> > new options to control maximum packfile size.\n> \n> Either that, or update the index file format. I think that your approach \n> of having a size limiter is actually the *better* one, though. \n\nNico and I were hoping we could push the index file format change back\nuntil pack v4 was also worthy of merging. So I had also started work\non an index-pack splitter:\n\n URL: git://repo.or.cz/git/fastimport.git\n Branch: sp/splitpack\n \nIts far from complete.\n\n> Well, it does affect fetching, in that \"git index-pack\" obviously would \n> also need to be taught how to split the resulting indexed packs up into \n> multiple smaller ones from one large incoming one. But that shouldn't be \n> fundamentally hard either, apart from the inconvenience of having to \n> rewrite the object count in the pack headers..\n\nWe already do this if its a thin-pack that is being made non-thin.\nSo its annoying, yea, but we already have one toe in that particular\npond...\n \n> To avoid that issue, it may be that it's actually better to split things \n> up at pack-generation time *even* for the case of --stdout\n\nThis is actually a pretty good idea. index-pack knows when the end\nof its current packfile is; if there are 12 more bytes available in\nthe input stream and it looks like another pack header then it can\njust restart itself over again with that next pack. This is actually\na pretty small change in index-pack, certainly a lot less intrusive\nthan what I was trying to do in my sp/splitpack topic above.\n \n-- \nShawn.\n"},{"id":"38387","messageId":"alpine.LFD.0.83.0703300851270.3041@xanadu.home","threadId":"7449","inReplyTo":"20070330062324.GU13247@spearce.org","subject":"Re: [RFC] Packing large repositories","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-30T13:01:22Z","receivedAt":"2007-03-30T13:01:22Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 30 Mar 2007, Shawn O. Pearce wrote:\n\n> Linus Torvalds wrote:\n> > On Wed, 28 Mar 2007, Dana How wrote:\n> > > Of course this is unusable, since object_entry's in an .idx\n> > > file have only 32 bits in their offset fields. I conclude that\n> > > for such large projects, git-repack/git-pack-objects would need\n> > > new options to control maximum packfile size.\n> > \n> > Either that, or update the index file format. I think that your approach \n> > of having a size limiter is actually the *better* one, though. \n> \n> Nico and I were hoping we could push the index file format change back\n> until pack v4 was also worthy of merging. So I had also started work\n> on an index-pack splitter:\n> \n> URL: git://repo.or.cz/git/fastimport.git\n> Branch: sp/splitpack\n> \n> Its far from complete.\n\nWell... actually I really think the best solution might simply be a new \nindex format right now. All the preparatory work has been done already \nanyway.\n\nIMHO that's the solution that would require the least work at this \npoint, with the least possibility of issues/bugs.\n\nPack v4 could just use an index v3 which would be almost the same as \nindex v2.\n\nRemains only to determine what this new index format should look like. \nI think that the SHA1 table and the offset table should be separate. \nFor one it will require less mmap space to binary search through \nthe SHA1 table, and it will make things much easier if pack v4 stores \nthe SHA1 table itself.\n\n\nNicolas\n"},{"id":"38424","messageId":"78639417-ACDB-484F-85BB-EC0AF694949A@adacore.com","threadId":"7449","inReplyTo":"alpine.LFD.0.83.0703300851270.3041@xanadu.home","subject":"Re: [RFC] Packing large repositories","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2007-03-31T11:04:39Z","receivedAt":"2007-03-31T11:04:39Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Mar 30, 2007, at 15:01, Nicolas Pitre wrote:\n\n> Remains only to determine what this new index format should look like.\n> I think that the SHA1 table and the offset table should be separate.\n> For one it will require less mmap space to binary search through\n> the SHA1 table, and it will make things much easier if pack v4 stores\n> the SHA1 table itself.\n\nI've been working on a design for a new index file format, and I'll\ninclude my current draft at the end of this message. It is not finished,\nand I've not written much code yet, but I'd like to prevent duplicated\nwork and give others the opportunity to borrow from the ideas so far.\n\nMy main focus is to minimize the amount of data accessed in a random\nfashion, allow for multiple packs and virtually unlimited scaling.\nThis is achieved through a fan-out table that grows with the number\nof items in the pack, keeping the fan-out table overhead under 2 bits\nper object while encoding a growing prefix of the object ID. This\nfrees up bits for a pack number. The pack number is either used to\nfind the correct pack, or alternatively for the right chunk of a\nvery large pack file.\n\n -Geert\n\n---\nThe primary purpose of the pack index is to quickly\nfind the location of a given SHA1 in any of the pack\nfiles. It is also used for quick lookup of and expansion\nof a unique prefix of a SHA1 object name.\n\nOriginal Pack Index\n\nThe original pack index uses a separate index file\nper pack file, with the same name as the pack file\nbut a .idx extension instead of .pack. After an\ninitial 256 entry fan-out table gives an approximate\nrange of the object, binary lookup is used to find\nthe exact object entry in the table of objects sorted\nby SHA1. Each entry is 24 bytes: the 20 bytes of the\nSHA1 and 4 bytes for the offset.\n\nA problem with that approach is that doesn't scale well\nfor repositories with large numbers of objects and\npack files. In the following I'll assume a repository\nwith 1K packs containing about 1M objects of 1K bytes\neach for a total repository size of 1TB. Such a scenario\ncould occur in a situation where many loosely connected\nprojects are combined in one large repository.\n\nPerformance with Large Repository\n\nNow consider the working set needed to complete a job\ninvolving the lookup of 1K random objects in the\nrepository described above. File access are counted\nin 4K blocks. The index for each pack is about 24M bytes,\nand the total space for all indices is 24G bytes.\n\nEach lookup in a pack file reads the entire fan-out table,\nso the 1K * 4K = 4M of pack fan out tables is read.\nA successful object lookup searches through about half\nof the table entries, so each pack file will be used\napproximately 500 times. Each of the 256 fan-out bins\nhas about 4K objects (totalling 96K bytes)\nand will be accessed twice.\n\nOf the expected 12 binary lookups, the first one will\nbe repeated twice, while the second level has a 50%\nchance of hitting the same location, the third level\n25% and so on. So, on average 11 unique lookups will\nbe done per object access for each pack. Since a total\nof 22 random reads will be done in each 96K bin,\nmost if not all of the file blocks in the pack indices\nneeds to be read. As access is random, there is no\nmeaningful caching possible for the 24G working set\nof indices.\n\nThe result is 500*11=5500 random disk reads accessing\neach object, for a total of 5500K I/Os in the the 24G\nof pack indices.\n\nMultiple Pack Index\n\nThe linear search through packs is very inefficient\nwith large numbers of packs. Having packs much larger\nthan a GB is also problematic, due to this as repacking\nand otherwise modifying packs gets very expensive.\n\nAnother issue is that binary search requires many\nsemi-random accesses spread over the index. Finally,\nmost of the information actually read consists of\nSHA1's that are never needed.\n\nThis proposed pack index format does not focus on reducing\nused disk space, but instead aims to reduce the number\nof blocks that needs to be read to perform lookups.\nThis is done using three techniques:\n 1) scale the number of fan-out bins with the number\n of objects in the index, keeping the expected\n number of objects in each bin constant\n 2) take advantage of 1) by only storing a few bits\n following the common prefix in the main lookup table\n as a discriminant. Store the rest of the SHA1 and\n the pack offest in a separate, parallel, object table.\n 3) Instead of repeating the variable-length common prefix\n and the discriminant, use the space for the prefix\n for a pack identifier and omit the discriminant altogether.\n\nFor a repository with N objects and highest PACK_NR P,\nthe total space used for the index is bounded by\n24 * (N + P) bytes, if N is at least 512 and N >= 512 * P.\n\nLimits:\n - Maximum number of packs: 2^27\n - Maximum number of objects: 2^40\n - Maximum repository size: 2^48 bytes\n\n\n : \n \n \n \n \n \n ;\n\n\n : \n \n ;\n\n # List of packs sorted by ascending PACK_ID\n : ( ) *\n ;\n\n\n # 20-byte binary representation of the 40 hex-digit\n # value PACK_ID_HEX, such that pack-${PACK_ID_HEX}.pack\n # is the name of the pack file\n ;\n\n\n # 32-bit unsigned integer in network order, with the same\n # value as the preceding (or zero for the\n # first entry), increased by the size of the pack file in\n # bytes, divided by 2^32 and rounded up.\n ;\n\n\n # 32-bit zero\n ;\n\n\n # 20-byte SHA1 of \n ;\n\n\n # 1 byte with the smallest value N between 8 and 35,\n # such that 2^(N - 8) greater than or equal to the\n # largest IDX_PACK_NR in the IDX_PACK_LIST, and such that\n # 2^(N+5) is greater than or equal to the total number\n # of objects in all packs.\n ;\n\n\n # Table of 2^${IDX_FANOUT_BITS} entries\n : ( ) *\n ;\n\n\n # 40 bit, network byte order, binary integer of the count of\n # objects in the pack file with the high IDX_FANOUT_BITS bits of\n # the object ID less than or equal to the index of the count,\n # starting from zero.\n ;\n\n\n # One 8-bit key per object indexed by the pack\n : ( ) *\n ;\n\n\n # Bits IDX_FANOUT_BITS through IDX_FANOUT_BITS + 7 of the\n # object ID.\n ;\n\n\n # The total width of each entry is 22 bytes\n : ( ) *\n ;\n\n\n # A IDX_FANOUT_BITS - 8 bit wide integer value, equal to\n # PACK_NR of pack preceding the one containing the object\n # (or zero, if object is in first pack) increased with the\n # pack offset divided by 2^32.\n ;\n\n\n # Bits IDX_FANOUT_BITS + 8 .. 159 of the object ID\n ;\n\n\n # 32-bits offset in network byte order\n ;\n"},{"id":"38443","messageId":"Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org","threadId":"7449","inReplyTo":"78639417-ACDB-484F-85BB-EC0AF694949A@adacore.com","subject":"Re: [RFC] Packing large repositories","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-31T18:36:35Z","receivedAt":"2007-03-31T18:36:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 31 Mar 2007, Geert Bosch wrote:\n> \n> I've been working on a design for a new index file format, and I'll\n> include my current draft at the end of this message. It is not finished,\n> and I've not written much code yet, but I'd like to prevent duplicated\n> work and give others the opportunity to borrow from the ideas so far.\n\nOk, here's one comment...\n\nI think your basic assumption that the current index-pack is bad is \nbroken ;)\n\nThe thing is, I think the index-pack could be improved, but I think we can \nget a bigger improvement from just being more intelligent about searching \nthan from actually needing to re-organize the pack.\n\nHere's a few clues:\n - binary search is certainly not the only way to do lookups on sorted \n contents\n - one of the fundamental rules about cryptographic hashes is that they \n are *evenly*distributed*\n - currently we do not take advantage of our inherent knowledge of the \n distribution when we look things up, and we use a stupid binary lookup \n that is guaranteed to basically always take O(log2(n)) random jumps \n around the data area, with bad locality.\n\nIn other words, the 256-entry fan-out was meant to avoid the first eight \nlevels of binary lookup. But the thing is, we should be able to generally \ndo a *lot* better than any binary lookup by just doing a LINEAR SEARCH, \nwhich is also more cache-friendly, and prefetches much better when it's \nnot in the cache.\n\nThe only thing we want for a linear search is a good starting point. Which \ngets us back to the simple: \"SHA1 hashes are evenly distributed\". In other \nwords, getting a good starting point should be *trivial*.\n\nSo here's a suggestion:\n\n - start finding a range using the 256-entry fan-out, exactly the way we \n did for the binary search. It's cheap. We could probably avoid EVEN \n THIS, and just do one more newton-raphson iteration more. But since we \n have the data, we migth as well use it. After all, it really *is* just \n a first approximation of newton-raphson, and while it uses only 8 bits \n (and we could do better), at least it's an *exact* one.\n\n - use newton-raphson to iterate closer. It should be a much faster way to \n find the rough area for the entry we're searching for than binary \n search. Two or three iterations should get us there, easily.\n\n - do a linear search once you're close enough.\n\nHere's a stupid patch that does that. It's biggest weakness is that it \nonly does a single iteration of newton-raphson. It should probably do at \nleast one more iteration. I bet that you'd get so close that you find it \nreally quickly if you did that. As it is, it doesn't seem to be any slower \nthan the binary search..\n\nAnd the nice thing is that I think that in large packs the \"evenly \ndistributed\" should be *more*true* than in small packs, so this should \nscale up very nicely, and I'm hoping that it would get much better cache \nbehaviour (because we wouldn't bounce around in the index file too much). \nI wouldn't be surprised if we basically hit it on the first try if we did \ntwo or three iterations of newton-raphson.\n\nComments? Does anybody want to take this and run with it?\n\n(No guarantees that this really can ever beat binary search, but somebody \nmight find this interesting. And I think the potential is there, but I \nthink you do need to do at *least* two iterations).\n\n\t\tLinus\n---\n sha1_file.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++-----------\n 1 files changed, 64 insertions(+), 15 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 9c26038..fc4dbc7 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1543,29 +1543,78 @@ int nth_packed_object_sha1(const struct packed_git *p, uint32_t n,\n \treturn 0;\n }\n \n-off_t find_pack_entry_one(const unsigned char *sha1,\n-\t\t\t\t struct packed_git *p)\n+struct index_entry {\n+\tuint32_t nb_offset;\t/* pack-file offset in network byte order */\n+\tunsigned char sha1[20];\t/* SHA1 of the object */\n+};\n+\n+static off_t pack_search_backward(const struct index_entry *index, uint32_t guess, const unsigned char *sha1)\n {\n-\tconst uint32_t *level1_ofs = p->index_data;\n-\tint hi = ntohl(level1_ofs[*sha1]);\n-\tint lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n-\tconst unsigned char *index = p->index_data;\n+\tint count = 1;\n+\twhile (guess) {\n+\t\tint cmp;\n \n-\tindex += 4 * 256;\n+\t\tguess--;\n+\t\tindex--;\n+\t\tcmp = hashcmp(index->sha1, sha1);\n+\t\tif (!cmp)\n+\t\t\treturn ntohl(index->nb_offset);\n+\t\tif (cmp < 0)\n+\t\t\tbreak;\n+\t\tcount++;\n+\t}\n+\treturn 0;\n+}\n \n-\tdo {\n-\t\tint mi = (lo + hi) / 2;\n-\t\tint cmp = hashcmp(index + 24 * mi + 4, sha1);\n+static off_t pack_search_forward(const struct index_entry *index, uint32_t guess, uint32_t max, const unsigned char *sha1)\n+{\n+\tint count = 1;\n+\twhile (++guess < max) {\n+\t\tint cmp;\n+\n+\t\tindex++;\n+\t\tcmp = hashcmp(index->sha1, sha1);\n \t\tif (!cmp)\n-\t\t\treturn ntohl(*((uint32_t *)((char *)index + (24 * mi))));\n+\t\t\treturn ntohl(index->nb_offset);\n \t\tif (cmp > 0)\n-\t\t\thi = mi;\n-\t\telse\n-\t\t\tlo = mi+1;\n-\t} while (lo < hi);\n+\t\t\tbreak;\n+\t\tcount++;\n+\t}\n \treturn 0;\n }\n \n+off_t find_pack_entry_one(const unsigned char *sha1,\n+\t\t\t\t struct packed_git *p)\n+{\n+\tconst struct index_entry *index;\n+\tconst uint32_t *level1_ofs = p->index_data;\n+\tuint32_t min, max, first;\n+\tuint32_t hash_val;\n+\tuint32_t guess;\n+\tint cmp;\n+\n+\tfirst = *sha1;\n+\tmin = first ? ntohl(level1_ofs[first - 1]) : 0;\n+\tmax = ntohl(level1_ofs[first]);\n+\n+\thash_val = (sha1[1] << 24) |\n+\t\t (sha1[2] << 16) |\n+\t\t (sha1[3] << 8) |\n+\t\t (sha1[4]);\n+\tguess = ((uint64_t)(max - min) * hash_val) >> 32;\n+\tguess += min;\n+\n+\tindex = (const struct index_entry *)((char *) p->index_data + 4 * 256);\n+\tindex += guess;\n+\n+\tcmp = hashcmp(index->sha1, sha1);\n+\tif (!cmp)\n+\t\treturn ntohl(index->nb_offset);\n+\tif (cmp > 0)\n+\t\treturn pack_search_backward(index, guess, sha1);\n+\treturn pack_search_forward(index, guess, max, sha1);\n+}\n+\n static int matches_pack_name(struct packed_git *p, const char *ig)\n {\n \tconst char *last_c, *c;\n"},{"id":"38444","messageId":"alpine.LFD.0.98.0703311112340.28181@xanadu.home","threadId":"7449","inReplyTo":"78639417-ACDB-484F-85BB-EC0AF694949A@adacore.com","subject":"Re: [RFC] Packing large repositories","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-31T18:51:23Z","receivedAt":"2007-03-31T18:51:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 31 Mar 2007, Geert Bosch wrote:\n\n> I've been working on a design for a new index file format, and I'll\n> include my current draft at the end of this message. It is not finished,\n> and I've not written much code yet, but I'd like to prevent duplicated\n> work and give others the opportunity to borrow from the ideas so far.\n\nI'm glad you posted this as I intended to work on the index today.\n\n> My main focus is to minimize the amount of data accessed in a random\n> fashion, allow for multiple packs and virtually unlimited scaling.\n> This is achieved through a fan-out table that grows with the number\n> of items in the pack, keeping the fan-out table overhead under 2 bits\n> per object while encoding a growing prefix of the object ID. This\n> frees up bits for a pack number. The pack number is either used to\n> find the correct pack, or alternatively for the right chunk of a\n> very large pack file.\n\nAnd how do you determine that pack number?\n\nThe index should be tied to the pack it is indexing and nothing else \nlike the presence of other packs if possible. When given a 20-byte SHA1 \nyou don't know what packnumber that corresponds to anyway.\n\n> The linear search through packs is very inefficient\n> with large numbers of packs. Having packs much larger\n> than a GB is also problematic, due to this as repacking\n> and otherwise modifying packs gets very expensive.\n\nRepacking is not a frequent operation, and it can be done \nasynchronously. So I don't consider that to be a big issue if it is \nexpensive. It is already extremely expensive compared to other GIT \noperations. So it is better to have fewer and bigger packs to speed up \nruntime object searching than making repack less expensive with more \nsmaller packs.\n\n> Another issue is that binary search requires many\n> semi-random accesses spread over the index. Finally,\n> most of the information actually read consists of\n> SHA1's that are never needed.\n\nOf course the pack v4 design allow for bypassing all this altogether in \nmost cases. But it doesn't eliminate the need for an index in every \ncases. So let's optimize the index first, especially since the pressing \nneed now is to lift the 4G pack size limit. And pack v4 will come after \nthat.\n\nJust to say that the index doesn't need to be the ultimate thing as pack \nv4 will scale much better than any index format could ever do due to its \ndirect object reference design.\n\nHowever, a big detail that would greatly help pack v4 is to have the \nSHA1 table together in one block with no other fields inserted between \nentries. Then the only difference between current packs and pack v4 \nwould be that the SHA1 table will be located in the pack itself instead \nof the index (pack v4 will carry the sorted SHA1 table already so the \nindex won't have to store it).\n\n> This proposed pack index format does not focus on reducing\n> used disk space, but instead aims to reduce the number\n> of blocks that needs to be read to perform lookups.\n> This is done using three techniques:\n> 1) scale the number of fan-out bins with the number\n> of objects in the index, keeping the expected\n> number of objects in each bin constant\n> 2) take advantage of 1) by only storing a few bits\n> following the common prefix in the main lookup table\n> as a discriminant. Store the rest of the SHA1 and\n> the pack offest in a separate, parallel, object table.\n> 3) Instead of repeating the variable-length common prefix\n> and the discriminant, use the space for the prefix\n> for a pack identifier and omit the discriminant altogether.\n\nI think (2) conflicts with my goal of having the SHA1 table independent. \nIt is really important for future compatibility with pack v4 that the \nSHA1 table remains a sorted list of contiguous 20-byte records.\n\nI really like your adaptative fanout idea though. So it could be \npossible to have something based on the largest common SHA1 prefix \nwithin a pack for example. Or maybe it could be made multi level for an \narbitrary portion of the largest common prefix.\n\n\nNicolas\n"},{"id":"38445","messageId":"alpine.LFD.0.98.0703311459000.28181@xanadu.home","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-31T19:02:56Z","receivedAt":"2007-03-31T19:02:56Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 31 Mar 2007, Linus Torvalds wrote:\n\n> The thing is, I think the index-pack could be improved, but I think we can \n> get a bigger improvement from just being more intelligent about searching \n> than from actually needing to re-organize the pack.\n> \n> Here's a few clues:\n> - one of the fundamental rules about cryptographic hashes is that they \n> are *evenly*distributed*\n\nI was thinking about that too.\n\n> So here's a suggestion:\n> \n> - start finding a range using the 256-entry fan-out, exactly the way we \n> did for the binary search. It's cheap. We could probably avoid EVEN \n> THIS, and just do one more newton-raphson iteration more. But since we \n> have the data, we migth as well use it. After all, it really *is* just \n> a first approximation of newton-raphson, and while it uses only 8 bits \n> (and we could do better), at least it's an *exact* one.\n> \n> - use newton-raphson to iterate closer. It should be a much faster way to \n> find the rough area for the entry we're searching for than binary \n> search. Two or three iterations should get us there, easily.\n> \n> - do a linear search once you're close enough.\n\nI like that.\n\n\nNicolas\n"},{"id":"38448","messageId":"7vslbl8780.fsf@assigned-by-dhcp.cox.net","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-31T20:54:07Z","receivedAt":"2007-03-31T20:54:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> In other words, the 256-entry fan-out was meant to avoid the first eight \n> levels of binary lookup. But the thing is, we should be able to generally \n> do a *lot* better than any binary lookup by just doing a LINEAR SEARCH, \n> which is also more cache-friendly, and prefetches much better when it's \n> not in the cache.\n> ...\n> - use newton-raphson to iterate closer. It should be a much faster way to \n> find the rough area for the entry we're searching for than binary \n> search. Two or three iterations should get us there, easily.\n\nThis is another egg of columbus moment that makes me feel it was\nworth to have been in git community ;-).\n\nI like it.\n"},{"id":"38449","messageId":"Pine.LNX.4.64.0703311408560.6730@woody.linux-foundation.org","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-31T21:20:49Z","receivedAt":"2007-03-31T21:20:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 31 Mar 2007, Linus Torvalds wrote:\n> \n> Here's a stupid patch that does that. It's biggest weakness is that it \n> only does a single iteration of newton-raphson. It should probably do at \n> least one more iteration. I bet that you'd get so close that you find it \n> really quickly if you did that. As it is, it doesn't seem to be any slower \n> than the binary search..\n\nOk, here's a slightly updated patch that does a few more iterations..\n\nIt actually seems to outperform the old binary search for me, although \nquite frankly, my only test was the eclipse git thing, and doing a\n\n\ttime git log > /dev/null\n\nwhich isn't exactly scientific or necessarily even very interesting. For \na run of five, I got:\n\nBefore:\n\treal 0m2.940s\n\treal 0m2.277s\n\treal 0m2.220s\n\treal 0m2.377s\n\treal 0m2.223s\n\nAfter:\n\treal 0m2.903s\n\treal 0m2.217s\n\treal 0m2.269s\n\treal 0m2.148s\n\treal 0m2.215s\n\nie it's really pretty much in the noise, but the best-of-five actually \ncomes with this Newton-Raphson + linear search thing rather than with the \nbinary search.\n\nAnyway, it's *so* much in the noise that I doubt that object lookup really \nis a very noticeable cost for this load (and perhaps it never is). But it \nwas interesting to see that at least the theory seems sound.\n\nThe patch has some commented-out statistics code (ie \"hit it in one\" vs \nreporting how many steps forwards/backwards it needed to look.\n\nNot really meant to be applied, but it was interesting to play with \nthis. NOTE! I don't think the math is really strictly correct (ie the \nscaling inside the loop), but it's \"close enough\" to not matter, and this \nreally was meant to be an request-for-discussion.\n\n\t\tLinus\n\n---\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 9c26038..b1643ea 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1543,27 +1543,134 @@ int nth_packed_object_sha1(const struct packed_git *p, uint32_t n,\n \treturn 0;\n }\n \n+struct index_entry {\n+\tuint32_t nb_offset;\t/* pack-file offset in network byte order */\n+\tunsigned char sha1[20];\t/* SHA1 of the object */\n+};\n+\n+static off_t pack_search_backward(const struct index_entry *index, uint32_t guess, const unsigned char *sha1)\n+{\n+\tint count = 1;\n+\twhile (guess) {\n+\t\tint cmp;\n+\n+\t\tguess--;\n+\t\tindex--;\n+\t\tcmp = hashcmp(index->sha1, sha1);\n+\t\tif (!cmp) {\n+//\t\t\terror(\" backward: %d\", count);\n+\t\t\treturn ntohl(index->nb_offset);\n+\t\t}\n+\t\tif (cmp < 0)\n+\t\t\tbreak;\n+\t\tcount++;\n+\t}\n+\treturn 0;\n+}\n+\n+static off_t pack_search_forward(const struct index_entry *index, uint32_t guess, uint32_t max, const unsigned char *sha1)\n+{\n+\tint count = 1;\n+\twhile (++guess < max) {\n+\t\tint cmp;\n+\n+\t\tindex++;\n+\t\tcmp = hashcmp(index->sha1, sha1);\n+\t\tif (!cmp) {\n+//\t\t\terror(\" forward: %d\", count);\n+\t\t\treturn ntohl(index->nb_offset);\n+\t\t}\n+\t\tif (cmp > 0)\n+\t\t\tbreak;\n+\t\tcount++;\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n+ * The \"fraction\" thing is a 32-bit number that is seen as a\n+ * fraction of 1<<32. Ie 0x80000000 means \"half-way\". We use\n+ * this as a way to do simple comparisons of 32-bit partial\n+ * SHA1 fragments, and to estimate how far off we are from\n+ * the value we wish to see.\n+ */\n+static inline uint32_t get_fraction(const unsigned char *p)\n+{\n+\treturn (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];\n+}\n+\n+static inline int update_guess(unsigned int nr, uint32_t fraction)\n+{\n+\treturn (0x80000000 + nr * (uint64_t) fraction) >> 32;\n+}\n+\n off_t find_pack_entry_one(const unsigned char *sha1,\n \t\t\t\t struct packed_git *p)\n {\n+\tint i;\n+\tconst struct index_entry *index;\n \tconst uint32_t *level1_ofs = p->index_data;\n-\tint hi = ntohl(level1_ofs[*sha1]);\n-\tint lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));\n-\tconst unsigned char *index = p->index_data;\n+\tuint32_t min, max, first;\n+\tuint32_t hash_val, guess;\n+\tint cmp;\n \n-\tindex += 4 * 256;\n+\t/*\n+\t * Get the initial range using the first 8 bits of\n+\t * the SHA1 and the 8-bit fan-out in the index\n+\t */\n+\tfirst = *sha1;\n+\tmin = first ? ntohl(level1_ofs[first - 1]) : 0;\n+\tmax = ntohl(level1_ofs[first]);\n+\tif (min == max)\n+\t\treturn 0;\n \n-\tdo {\n-\t\tint mi = (lo + hi) / 2;\n-\t\tint cmp = hashcmp(index + 24 * mi + 4, sha1);\n-\t\tif (!cmp)\n-\t\t\treturn ntohl(*((uint32_t *)((char *)index + (24 * mi))));\n-\t\tif (cmp > 0)\n-\t\t\thi = mi;\n+\t/*\n+\t * Initial guess using the next 32 bits of the SHA1\n+\t * (using \"sha1+1\" because the first byte of the SHA1\n+\t * is now known to be irrelevant and will always match,\n+\t * thanks to the index fan-out)\n+\t */\n+\thash_val = get_fraction(sha1+1);\n+\tguess = min + update_guess(max - min, hash_val);\n+\n+\t/*\n+\t * Look up that entry in the index file...\n+\t */\n+\tindex = (const struct index_entry *)((char *) p->index_data + 4 * 256);\n+\tindex += guess;\n+\n+\t/*\n+\t * ..and update the guess with a correction based on how\n+\t * close the guessed entry's hash value was.\n+\t */\n+\tfor (i = 0; i < 3; i++) {\n+\t\tuint32_t guess_hash_val = get_fraction(index->sha1+1);\n+\t\tint correction;\n+\n+\t\tif (guess_hash_val == hash_val)\n+\t\t\tbreak;\n+\t\tif (guess_hash_val < hash_val)\n+\t\t\tcorrection = update_guess(max - guess, hash_val - guess_hash_val);\n \t\telse\n-\t\t\tlo = mi+1;\n-\t} while (lo < hi);\n-\treturn 0;\n+\t\t\tcorrection = -update_guess(guess - min, guess_hash_val - hash_val);\n+\t\tif (!correction)\n+\t\t\tbreak;\n+\t\tguess += correction;\n+\t\tindex += correction;\n+\t}\n+\n+\t/*\n+\t * ..and we should now be close enough that now we'll just use a\n+\t * linear search from the updated guess.\n+\t */\n+\tcmp = hashcmp(index->sha1, sha1);\n+\tif (!cmp) {\n+//\t\terror(\"hit it in one!\");\n+\t\treturn ntohl(index->nb_offset);\n+\t}\n+\tif (cmp > 0)\n+\t\treturn pack_search_backward(index, guess, sha1);\n+\treturn pack_search_forward(index, guess, max, sha1);\n }\n \n static int matches_pack_name(struct packed_git *p, const char *ig)\n"},{"id":"38453","messageId":"Pine.LNX.4.64.0703311450030.6730@woody.linux-foundation.org","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703311408560.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-31T21:56:09Z","receivedAt":"2007-03-31T21:56:09Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 31 Mar 2007, Linus Torvalds wrote:\n> \n> Ok, here's a slightly updated patch that does a few more iterations..\n\nDon't use this. There's something wrong with it, and unlike the first \npatch, it doesn't even pass all tests.\n\nI think it's because I decided to try to use rounding in the newton thing \n(which got things closer), but I suspect that rounding is broken - I think \nit can round to \"outside\" the valid range. I didn't notice that with the \neclipse performance testing, probably because when you have enough objects \nyou'll never see it, but with smaller packs, being off-by-one means that \nyou can easily fall off the map ;)\n\nSo I'd like to re-iterate the note I had in that email:\n\n> Not really meant to be applied, but it was interesting to play with \n> this. NOTE! I don't think the math is really strictly correct (ie the \n> scaling inside the loop), but it's \"close enough\" to not matter, and this \n> really was meant to be an request-for-discussion.\n\nIOW, it's very much a RFD patch. I suspect it is trivial to fix, but I \nalso suspect that unless somebody else decides that this is interesting, \nI'll just leave the patch behind. None of the loads I tested really seemed \nto be very sensitive to object lookup performance - the binary search \nsimply seems ot be \"good enough\", and usually the costs are in generating \npatches (\"git blame\") or just diffing trees (\"git log \"), and \nthe object lookup doesn't seem to be critical enough to worry about.\n\nIf somebody can point to a load where we spend a noticeable amount of time \non doing index lookups, that would obviously change my opinion, but in the \nmeantime, I think this is better considered a case of \"we _could_ do \nsomething like this if it's ever an issue..\"\n\n\t\tLinus\n"},{"id":"38475","messageId":"46105EC8.90407@vilain.net","threadId":"7449","inReplyTo":"56b7f5510703280005o7998d65pcbcd4636b46d8d23@mail.gmail.com","subject":"Re: [RFC] Packing large repositories","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2007-04-02T01:39:20Z","receivedAt":"2007-04-02T01:39:20Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"Dana How wrote:\n> Hi,\n>\n> I just started experimenting with using git on\n> a large engineering project which has used p4 so far.\n> Part of a checkout is about 55GB;\n> after an initial commit and packing I have a 20GB+ packfile.\n> Of course this is unusable, since object_entry's in an .idx\n\nAnother idea to consider is that if you are storing changes of files\nwhich have a compressed file format, you will almost certainly save a\nhuge amount by storing the uncompressed version in the git repository -\nas then delta compression stands a chance of working.\n\nSam.\n"},{"id":"38477","messageId":"64E16DEF-E572-4384-9E68-42EBBCE678B1@adacore.com","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703311033290.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2007-04-02T06:22:17Z","receivedAt":"2007-04-02T06:22:17Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Mar 31, 2007, at 20:36, Linus Torvalds wrote:\n\n> So here's a suggestion:\n>\n> - start finding a range using the 256-entry fan-out, exactly the \n> way we\n> did for the binary search. It's cheap. We could probably avoid EVEN\n> THIS, and just do one more newton-raphson iteration more. But \n> since we\n> have the data, we migth as well use it. After all, it really \n> *is* just\n> a first approximation of newton-raphson, and while it uses only \n> 8 bits\n> (and we could do better), at least it's an *exact* one.\n>\n> - use newton-raphson to iterate closer. It should be a much faster \n> way to\n> find the rough area for the entry we're searching for than binary\n> search. Two or three iterations should get us there, easily.\n>\n> - do a linear search once you're close enough.\n\nActually, I had implemented this first, using two newton-raphson\niterations and then binary search. With just one iteration is\ntoo little, and one iteration+binary search often is no win.\nTwo iterations followed by binary search cuts the nr of steps in\nhalf for the Linux kernel. Two iterations followed by linear search\nis often worse, because of \"unlucky\" cases that end up doing many\nprobes. Still, during the 5-8 probes in moderately large repositories\n(1M objects), each probe pretty much requires its own cache line:\nvery cache unfriendly.\n\nBy using a fan-out table with an average nr of entries per bin\nof 32 or so, you get a total cache footprint of between 1 and 2 bits\nper entry for the random lookup. So, a complete lookup only hits\nabout 3 cache lines. After a few lookups, almost all of the\nfan-out table will be in cache, while currently, the cache is\nfilled with useless 24 byte SHA1+offset of unrelated objects.\n\n -Geert\n\nPS. I'm travelling now, so can't participate in the discussion\n or send code as much as I'd like and mail may be late or\n out of sequence.\n"},{"id":"38489","messageId":"56b7f5510704021419s4f8635abs8544df2f1065a5d4@mail.gmail.com","threadId":"7449","inReplyTo":"Pine.LNX.4.64.0703280943450.6730@woody.linux-foundation.org","subject":"Re: [RFC] Packing large repositories","fromName":"Dana How","fromEmail":"danahow@gmail.com","sentAt":"2007-04-02T21:19:29Z","receivedAt":"2007-04-02T21:19:29Z","isPatch":false,"sender":{"key":"danahow@gmail.com","avatar":null},"body":"On 3/28/07, Linus Torvalds wrote:\n> > I just started experimenting with using git ...\n> > Part of a checkout is about 55GB;\n> > after an initial commit and packing I have a 20GB+ packfile.\n> > Of course this is unusable, ... . I conclude that\n> > for such large projects, git-repack/git-pack-objects would need\n> > new options to control maximum packfile size.\n>\n> Either that, or update the index file format. I think that your approach\n> of having a size limiter is actually the *better* one, though.\n>\n> > [ I don't think this affects git-{fetch,receive,send}-pack\n> > since apparently only the pack is transferred and it only uses\n> > the variable-length size and delta base offset encodings\n> > (of course the accumulation of the 7 bit chunks in a 32b\n> > variable would need to be corrected, but at least the data\n> > format doesn't change).]\n>\n> Well, it does affect fetching, in that \"git index-pack\" obviously would\n> also need to be taught how to split the resulting indexed packs up into\n> multiple smaller ones from one large incoming one. But that shouldn't be\n> fundamentally hard either, apart from the inconvenience of having to\n> rewrite the object count in the pack headers..\n>\n> To avoid that issue, it may be that it's actually better to split things\n> up at pack-generation time *even* for the case of --stdout, exactly so\n> that \"git index-pack\" wouldn't have to split things up (we potentially\n> know a lot more about object sizes up-front at pack-generation time than\n> we know at re-indexing).\n\nThe attached patch adds a --pack-limit[=N] option\nto git-repack/git-pack-objects. N defaults to 1<<31,\nand the result with --pack-limit is that no packfile\ncan be equal to or larger than N. A --blob-limit=N\noption is also added (see below).\n\nMy original plan was simply to ensure that no\nobject started at a file offset not representable in 31 bits.\nHowever, I became concerned about the arithmetic involved\nwhen mmap'ing a pack, so I decided to make sure *all*\nbytes lived at offsets representable in 31 bits.\n\nConsequently after an object is written out,\nthe new offset is checked. If the limit has been exceeded,\nthe write is rolled back (see sha1mark/sha1undo).\nThis is awkward and inefficient, but yields packs closer\nto the limit and happens too infrequently to be of much impact.\n\nHowever, there are really two modes when packing:\npacking to disk, and packing to stdout.\nSince you can't rollback a write on stdout, the initial\nfile-offset-limit technique is used when --stdout is specified.\n[Note: I did not *test* the --pack-limit && --stdout combination.]\n\nTo fully guarantee that a pack file doesn't exceed a certain size,\nobjects above that size must not be packed into it.\nBut I think this makes sense -- I don't see a lot of advantage\nto packing a 100MB+ object into a pack, except for fetch/send\nwhich is a serial stream without index anyway. Thus\nthis patch automatically excludes any object whose uncompressed\nsize is 1/4 or more of the packfile size limit when --stdout\nis not specified. This behavior can be altered with an explicit\n--blob-limit=N option.\n\nTwo interesting twists presented themselves.\nFirst, the packfile contains the number of objects in\nthe header at the beginning, and this header is included\nin the final SHA1. But I don't know the final count until\nthe limit is reached. Consequently the header must be\nrewritten and the entire file rescanned to make the correct\nchecksum. This already happens in two other places in git.\n\nSecondly, when using --pack-limit with --stdout, the header\ncan't be rewritten. Instead the object count in the header\nis left at 0 to flag that it's wrong. The end of an individual\npack inside a multi-pack stream COULD be detected by checking,\nafter each object, if the next 20 bytes are equal to the SHA1\nof what's come before. I've made no additional effort beyond\nthis minimal solution because it's not clear that splitting\na pack up at the transmitter is better than at the receiver.\nAn alternative method is to add, before the final SHA1, a last\nobject of type OBJ_NONE and length 0 (thus a single zero byte).\nThis would function as an EOF marker. I've indicated where this\nwould go in write_pack_file but didn't put it in since the current\ncode doesn't tolerate a 0 object count in the header anyway (yet?).\n[Note: I have *not* started in on teaching git-index-pack etc.\n how to read such concatenated split packs since (a) I'd like\n to see which way people will prefer and (b) I don't plan on\n using the feature anyway and I'm wondering if I'm alone\n in that reaction.]\n\nSome code has been added but\nvery few function relationships have been changed,\nwith the exception that write_pack_file now calls write_index_file\ndirectly since write_pack_file decides when to split packs\nand thus must call write_index_file before moving on to the next pack.\n\nIn response to my original post, I've seen some emails about\nchanging the pack file/index file format. This is exactly what I\n*didn't* want to do, since (1) it would delay a feature I'd like to\nuse now, (2) the current format is better than people seem to realize,\nand (3) it would create yet another flag in the config file\nto help phase in a new feature over a year or two.\n\nIf, however, there are other pent-up reasons for changing the format\nwhich might make it happen sometime soon, I can see some small tweaks\nthat could be useful.\n\n* [For stdout/serial access:] Tolerate \"0\" for object count in a .pack\nfile; it would mean look for the pack end by either matching a SHA1 or\nlooking for an OBJ_NONE/0 record, all as explained above.\n(The point is to avoid any need to rescan a file to rebuild checksums.)\n\n* [For disk/random access:] Don't change the current .pack/.idx files,\nbut do add a third file type which would be a \"super index\" with a format\nsimilar to .idx. It would map sorted SHA1s to (pack#,offset) pairs,\neither in one table of triples or two parallel tables, one of SHA1s and\nthe other of pairs. It probably would only be used if mentioned in\nobjects/info/packs (and it would be automatically ignored if older than\nobjects/info/packs?). It could be searched by taking advantage of the\nuniform SHA1 distribution recently discussed. There would be at most\none such file in a repository; perhaps the .idx files from which it was\ngenerated could be removed. For safety the \"super index\" could contain\na small table of all the SHA1s for the packs it indexes.\n\nThanks,\n-- \nDana L. How danahow@gmail.com +1 650 804 5991 cell\n\ncat GIT-VERSION-FILE\nGIT_VERSION = 1.5.1.rc2.18.g9c88-dirty\n\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex b5f9648..0a11113 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -14,8 +14,8 @@\n #include \"list-objects.h\"\n \n static const char pack_usage[] = \"\\\n-git-pack-objects [{ -q | --progress | --all-progress }] \\n\\\n-\t[--local] [--incremental] [--window=N] [--depth=N] \\n\\\n+git-pack-objects [{ -q | --progress | --all-progress }] [--pack-limit[=N]]\\n\\\n+\t[--blob-limit=N] [--local] [--incremental] [--window=N] [--depth=N]\\n\\\n \t[--no-reuse-delta] [--delta-base-offset] [--non-empty] \\n\\\n \t[--revs [--unpacked | --all]*] [--reflog] [--stdout | base-name] \\n\\\n \t[delta ? 0 :\n+\t\t\t\t\t!offset_limit ? 1 :\n+\t\t\t\t\tentry->delta->no_write ? 0 :\n+\t\t\t\t\tentry->delta->offset ? 1 : 0;\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 \t\tif (size != entry->size)\n \t\t\tdie(\"object %s size inconsistency (%lu vs %lu)\",\n \t\t\t sha1_to_hex(entry->sha1), size, entry->size);\n-\t\tif (entry->delta) {\n+\t\tif (usable_delta) {\n \t\t\tbuf = delta_against(buf, size, entry);\n \t\t\tsize = entry->delta_size;\n \t\t\tobj_type = (allow_ofs_delta && entry->delta->offset) ?\n@@ -503,62 +511,212 @@ static off_t write_one(struct sha1file *f,\n \t\t\t struct object_entry *e,\n \t\t\t off_t offset)\n {\n-\tif (e->offset || e->preferred_base)\n+\tstruct sha1posn posn;\n+\tuint32_t save_written = 0, save_written_delta = 0;\n+\tuint32_t save_reused = 0, save_reused_delta = 0;\n+\tif (e->offset || e->preferred_base || e->no_write)\n \t\t/* offset starts from header size and cannot be zero\n \t\t * if it is written already.\n \t\t */\n \t\treturn offset;\n \t/* if we are deltified, write out its base object first. */\n-\tif (e->delta)\n+\tif (e->delta) {\n \t\toffset = write_one(f, e->delta, offset);\n+\t\tif (!offset)\n+\t\t\treturn offset;\n+\t}\n+\tif (offset_limit) {\n+\t\tif ( !pack_to_stdout ) {\n+\t\t\t/* save state before write for possible later seekback */\n+\t\t\tsave_written = written, save_written_delta = written_delta;\n+\t\t\tsave_reused = reused, save_reused_delta = reused_delta;\n+\t\t\tsha1mark(f, &posn);\n+\t\t} else if ( (unsigned long)offset >= (unsigned long)offset_limit )\n+\t\t\t/*\n+\t\t\t * This ensures that no object's offset in the pack\n+\t\t\t * exceeds or is equal to the offset_limit. It is\n+\t\t\t * a looser way of limiting packsize w/o seeking and\n+\t\t\t * is used in --stdout mode.\n+\t\t\t */\n+\t\t\treturn 0;\n+\t}\n \te->offset = offset;\n-\treturn offset + write_object(f, e);\n+\toffset += write_object(f, e);\n+\t/*\n+\t * This ensures that the packfile size never exceeds or matches\n+\t * the offset_limit if supplied. The \"20\" is for the final SHA1.\n+\t * This limit isn't used with --stdout since it requires seeking.\n+\t */\n+\tif (offset_limit && !pack_to_stdout &&\n+\t (unsigned long)offset >= (unsigned long)(offset_limit - 20)) {\n+\t\twritten = save_written, written_delta = save_written_delta;\n+\t\treused = save_reused, reused_delta = save_reused_delta;\n+\t\tsha1undo(f, &posn, offset, e->offset);\n+\t\te->offset = 0;\n+\t\treturn 0;\n+\t}\n+\t*written_list++ = e;\n+\treturn offset;\n+}\n+\n+/*\n+ * Move this, the version in fast-import.c,\n+ * and index_pack.c:readjust_pack_header_and_sha1 into sha1_file.c ?\n+ */\n+static void fixup_header_footer(int pack_fd, unsigned char *pack_file_sha1,\n+\t\t\t\tchar *pack_name, uint32_t object_count)\n+{\n+\tstatic const int buf_sz = 128 * 1024;\n+\tSHA_CTX c;\n+\tstruct pack_header hdr;\n+\tchar *buf;\n+\n+\tif (lseek(pack_fd, 0, SEEK_SET) != 0)\n+\t\tdie(\"Failed seeking to start: %s\", strerror(errno));\n+\tif (read_in_full(pack_fd, &hdr, sizeof(hdr)) != sizeof(hdr))\n+\t\tdie(\"Unable to reread header of %s\", pack_name);\n+\tif (lseek(pack_fd, 0, SEEK_SET) != 0)\n+\t\tdie(\"Failed seeking to start: %s\", strerror(errno));\n+\thdr.hdr_entries = htonl(object_count);\n+\twrite_or_die(pack_fd, &hdr, sizeof(hdr));\n+\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, &hdr, sizeof(hdr));\n+\n+\tbuf = xmalloc(buf_sz);\n+\tfor (;;) {\n+\t\tsize_t n = xread(pack_fd, buf, buf_sz);\n+\t\tif (!n)\n+\t\t\tbreak;\n+\t\tif (n < 0)\n+\t\t\tdie(\"Failed to checksum %s\", pack_name);\n+\t\tSHA1_Update(&c, buf, n);\n+\t}\n+\tfree(buf);\n+\n+\tSHA1_Final(pack_file_sha1, &c);\n+\twrite_or_die(pack_fd, pack_file_sha1, 20);\n+\tclose(pack_fd);\n }\n \n+typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n+\n+static entry_sort_t current_sort;\n+\n+/* forward declarations for write_pack_file */\n+/* (probably should move sorting stuff up here) */\n+static int sort_comparator(const void *_a, const void *_b);\n+static int sha1_sort(const struct object_entry *a, const struct object_entry *b);\n+static void write_index_file(void);\n+\n static void write_pack_file(void)\n {\n-\tuint32_t i;\n+\tuint32_t i, j;\n \tstruct sha1file *f;\n \toff_t offset;\n \tstruct pack_header hdr;\n \tunsigned last_percent = 999;\n-\tint do_progress = progress;\n+\tint do_progress = progress >> !base_name;\n+\tchar oldname[PATH_MAX];\n+\tint pack_fd;\n+\tstruct object_entry **list;\n+\tSHA_CTX ctx;\n+\tuint32_t nr_actual = nr_result - nr_skipped;\n \n-\tif (!base_name) {\n-\t\tf = sha1fd(1, \"\");\n-\t\tdo_progress >>= 1;\n-\t}\n-\telse\n-\t\tf = sha1create(\"%s-%s.%s\", base_name,\n-\t\t\t sha1_to_hex(object_list_sha1), \"pack\");\n \tif (do_progress)\n-\t\tfprintf(stderr, \"Writing %u objects.\\n\", nr_result);\n-\n-\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n-\thdr.hdr_version = htonl(PACK_VERSION);\n-\thdr.hdr_entries = htonl(nr_result);\n-\tsha1write(f, &hdr, sizeof(hdr));\n-\toffset = sizeof(hdr);\n-\tif (!nr_result)\n-\t\tgoto done;\n-\tfor (i = 0; i < nr_objects; i++) {\n-\t\toffset = write_one(f, objects + i, offset);\n-\t\tif (do_progress) {\n-\t\t\tunsigned percent = written * 100 / nr_result;\n-\t\t\tif (progress_update || percent != last_percent) {\n-\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n-\t\t\t\t\tpercent, written, nr_result);\n-\t\t\t\tprogress_update = 0;\n-\t\t\t\tlast_percent = percent;\n+\t\tfprintf(stderr, \"Writing %u objects.\\n\", nr_actual);\n+\twritten_list = list = xmalloc(nr_objects * sizeof(struct object_entry *));\n+\n+\tfor (i = 0; i < nr_objects;) {\n+\t\tif (!base_name) {\n+\t\t\tf = sha1fd(pack_fd = 1, \"\");\n+\t\t}\n+\t\telse {\n+\t\t\tint len = snprintf(oldname, sizeof oldname, \"%s-XXXXXX\", base_name);\n+\t\t\tif (len >= PATH_MAX)\n+\t\t\t\tdie(\"excessive pathname length for initial packfile name\");\n+\t\t\tpack_fd = mkstemp(oldname);\n+\t\t\tif (pack_fd < 0)\n+\t\t\t\tdie(\"can't create %s: %s\", oldname, strerror(errno));\n+\t\t\tf = sha1fd(pack_fd, oldname);\n+\t\t}\n+\n+\t\thdr.hdr_signature = htonl(PACK_SIGNATURE);\n+\t\thdr.hdr_version = htonl(PACK_VERSION);\n+\t\thdr.hdr_entries = htonl(!base_name && offset_limit ? 0 : nr_actual);\n+\t\tsha1write(f, &hdr, sizeof(hdr));\n+\t\toffset = sizeof(hdr);\n+\t\tfor (; i < nr_objects; i++) {\n+\t\t\toff_t offset_one = write_one(f, objects + i, offset);\n+\t\t\tif (!offset_one)\n+\t\t\t\tbreak;\n+\t\t\toffset = offset_one;\n+\t\t\tif (do_progress) {\n+\t\t\t\tunsigned percent = written * 100 / nr_actual;\n+\t\t\t\tif (progress_update || percent != last_percent) {\n+\t\t\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n+\t\t\t\t\t\tpercent, written, nr_actual);\n+\t\t\t\t\tprogress_update = 0;\n+\t\t\t\t\tlast_percent = percent;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n+\t\tnr_written = written_list - list;\n+\t\twritten_list = list;\n+\n+\t\t/*\n+\t\t * Write terminator record here if desired:\n+\t\t * type=OBJ_NONE, len=0; this is a zero byte.\n+\t\t */\n+\n+\t\t/*\n+\t\t * Did we write the wrong # entries in the header?\n+\t\t * If so, rewrite it like in fast-import (gackk).\n+\t\t */\n+\t\tif ( !base_name || nr_written == nr_actual ) {\n+\t\t\tsha1close(f, pack_file_sha1, 1);\n+\t\t} else {\n+\t\t\tsha1close(f, pack_file_sha1, -1);\n+\t\t\tfixup_header_footer(pack_fd, pack_file_sha1, oldname, nr_written);\n+\t\t}\n+\n+\t\t/*\n+\t\t * compute object_list_sha1 of sorted sha's we just wrote out;\n+\t\t * we also mark these objects as written\n+\t\t */\n+\t\tcurrent_sort = sha1_sort;\n+\t\tqsort(list, nr_written, sizeof(struct object_entry *), sort_comparator);\n+\t\tSHA1_Init(&ctx);\n+\t\tfor (j = 0; j < nr_written; j++) {\n+\t\t\tstruct object_entry *entry = *list++;\n+\t\t\tentry->no_write = 1;\n+\t\t\tSHA1_Update(&ctx, entry->sha1, 20);\n+\t\t}\n+\t\tSHA1_Final(object_list_sha1, &ctx);\n+\t\tlist = written_list;\n+\t\t/*\n+\t\t * now we can rename the pack correctly and write the index file\n+\t\t */\n+\t\tif (base_name) {\n+\t\t\tchar newname[PATH_MAX];\n+\t\t\tint len = snprintf(newname, sizeof newname, \"%s-%s.%s\",\n+\t\t\t\t\t\tbase_name, sha1_to_hex(object_list_sha1), \"pack\");\n+\t\t\tif (len >= PATH_MAX)\n+\t\t\t\tdie(\"excessive pathname length for final packfile name\");\n+\t\t\tif (rename(oldname, newname) < 0)\n+\t\t\t\tdie(\"could not rename the pack file\");\n+\t\t}\n+\t\tif (!pack_to_stdout) {\n+\t\t\twrite_index_file();\n+\t\t\tputs(sha1_to_hex(object_list_sha1));\n+\t\t}\n \t}\n-\tif (do_progress)\n+\n+\tfree(written_list);\n+\tif (nr_actual && do_progress)\n \t\tfputc('\\n', stderr);\n- done:\n-\tif (written != nr_result)\n-\t\tdie(\"wrote %u objects while expecting %u\", written, nr_result);\n-\tsha1close(f, pack_file_sha1, 1);\n+\tif (written != nr_actual)\n+\t\tdie(\"wrote %u objects while expecting %u\", written, nr_actual);\n }\n \n static void write_index_file(void)\n@@ -566,8 +724,8 @@ static void write_index_file(void)\n \tuint32_t i;\n \tstruct sha1file *f = sha1create(\"%s-%s.%s\", base_name,\n \t\t\t\t\tsha1_to_hex(object_list_sha1), \"idx\");\n-\tstruct object_entry **list = sorted_by_sha;\n-\tstruct object_entry **last = list + nr_result;\n+\tstruct object_entry **list = written_list;\n+\tstruct object_entry **last = list + nr_written;\n \tuint32_t array[256];\n \n \t/*\n@@ -583,7 +741,7 @@ static void write_index_file(void)\n \t\t\t\tbreak;\n \t\t\tnext++;\n \t\t}\n-\t\tarray[i] = htonl(next - sorted_by_sha);\n+\t\tarray[i] = htonl(next - written_list);\n \t\tlist = next;\n \t}\n \tsha1write(f, array, 256 * 4);\n@@ -591,8 +749,8 @@ static void write_index_file(void)\n \t/*\n \t * Write the actual SHA1 entries..\n \t */\n-\tlist = sorted_by_sha;\n-\tfor (i = 0; i < nr_result; i++) {\n+\tlist = written_list;\n+\tfor (i = 0; i < nr_written; i++) {\n \t\tstruct object_entry *entry = *list++;\n \t\tuint32_t offset = htonl(entry->offset);\n \t\tsha1write(f, &offset, 4);\n@@ -1014,7 +1172,7 @@ static void check_object(struct object_entry *entry)\n \t\t\t\tofs = c & 127;\n \t\t\t\twhile (c & 128) {\n \t\t\t\t\tofs += 1;\n-\t\t\t\t\tif (!ofs || ofs & ~(~0UL >> 7))\n+\t\t\t\t\tif (!ofs || ofs & ~(~0UL >> 1))\n \t\t\t\t\t\tdie(\"delta base offset overflow in pack for %s\",\n \t\t\t\t\t\t sha1_to_hex(entry->sha1));\n \t\t\t\t\tc = buf[used_0++];\n@@ -1058,6 +1216,7 @@ static void check_object(struct object_entry *entry)\n \t}\n \n \tentry->type = sha1_object_info(entry->sha1, &entry->size);\n+\tnr_skipped += entry->no_write = blob_limit && (unsigned long)entry->size >= blob_limit;\n \tif (entry->type < 0)\n \t\tdie(\"unable to get type of object %s\",\n \t\t sha1_to_hex(entry->sha1));\n@@ -1103,10 +1262,6 @@ static void get_object_details(void)\n \t}\n }\n \n-typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);\n-\n-static entry_sort_t current_sort;\n-\n static int sort_comparator(const void *_a, const void *_b)\n {\n \tstruct object_entry *a = *(struct object_entry **)_a;\n@@ -1197,6 +1352,12 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (trg_entry->type != src_entry->type)\n \t\treturn -1;\n \n+\t/* Don't try deltas involving excessively large objects when\n+\t * pack size is limited\n+\t */\n+\tif (trg_entry->no_write || src_entry->no_write)\n+\t\treturn -1;\n+\n \t/* We do not compute delta to *create* objects we are not\n \t * going to pack.\n \t */\n@@ -1538,6 +1699,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tconst char **rp_av;\n \tint rp_ac_alloc = 64;\n \tint rp_ac;\n+\tint added = 0;\n \n \trp_av = xcalloc(rp_ac_alloc, sizeof(*rp_av));\n \n@@ -1566,6 +1728,24 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\tincremental = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(\"--pack-limit\", arg)) {\n+\t\t\toffset_limit = 1UL << 31;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!prefixcmp(arg, \"--pack-limit=\")) {\n+\t\t\tchar *end;\n+\t\t\toffset_limit = strtoul(arg+13, &end, 0);\n+\t\t\tif (!arg[13] || *end)\n+\t\t\t\tusage(pack_usage);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!prefixcmp(arg, \"--blob-limit=\")) {\n+\t\t\tchar *end;\n+\t\t\tblob_limit = strtoul(arg+13, &end, 0);\n+\t\t\tif (!arg[13] || *end)\n+\t\t\t\tusage(pack_usage);\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!prefixcmp(arg, \"--window=\")) {\n \t\t\tchar *end;\n \t\t\twindow = strtoul(arg+9, &end, 0);\n@@ -1629,6 +1809,24 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t}\n \t\tusage(pack_usage);\n \t}\n+\tif ( offset_limit && !blob_limit && !pack_to_stdout ) {\n+\t\t/* need to limit blob size when creating bounded packs on disk */\n+\t\tblob_limit = offset_limit >> 2;\n+\t\tadded |= 2;\n+\t}\n+\tif ( offset_limit && !no_reuse_delta ) {\n+\t\t/* didn't audit this case yet */\n+\t\tno_reuse_delta = 1;\n+\t\tadded |= 1;\n+\t}\n+\tif ( added ) {\n+\t\tfprintf(stderr, \"Added to command line:\");\n+\t\tif ( added & 1 )\n+\t\t\tfprintf(stderr, \" --no-reuse-delta\");\n+\t\tif ( added & 2 )\n+\t\t\tfprintf(stderr, \" --blob-limit=%u\", blob_limit);\n+\t\tfprintf(stderr, \"\\n\");\n+\t}\n \n \t/* Traditionally \"pack-objects [options] base extra\" failed;\n \t * we would however want to take refs parameter that would\n@@ -1695,10 +1893,6 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\tprogress_update = 0;\n \t\t}\n \t\twrite_pack_file();\n-\t\tif (!pack_to_stdout) {\n-\t\t\twrite_index_file();\n-\t\t\tputs(sha1_to_hex(object_list_sha1));\n-\t\t}\n \t}\n \tif (progress)\n \t\tfprintf(stderr, \"Total %u (delta %u), reused %u (delta %u)\\n\",\ndiff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c\nindex 3956c56..84a6c5c 100644\n--- a/builtin-unpack-objects.c\n+++ b/builtin-unpack-objects.c\n@@ -209,7 +209,7 @@ static void unpack_delta_entry(enum object_type type, unsigned long delta_size,\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || base_offset & ~(~0UL >> 1))\n \t\t\t\tdie(\"offset value overflow for delta base object\");\n \t\t\tpack = fill(1);\n \t\t\tc = *pack;\ndiff --git a/csum-file.c b/csum-file.c\nindex b7174c6..e2bef75 100644\n--- a/csum-file.c\n+++ b/csum-file.c\n@@ -35,7 +35,10 @@ int sha1close(struct sha1file *f, unsigned char *result, int update)\n \tif (offset) {\n \t\tSHA1_Update(&f->ctx, f->buffer, offset);\n \t\tsha1flush(f, offset);\n+\t\tf->offset = 0;\n \t}\n+\tif (update < 0)\n+\t\treturn 0;\t/* only want to flush (no checksum write, no close) */\n \tSHA1_Final(f->buffer, &f->ctx);\n \tif (result)\n \t\thashcpy(result, f->buffer);\n@@ -69,6 +72,44 @@ int sha1write(struct sha1file *f, void *buf, unsigned int count)\n \treturn 0;\n }\n \n+/*\n+ * Save current position/state in output file\n+ * (needs to be fast -- no system calls!)\n+ */\n+void sha1mark(struct sha1file *f, struct sha1posn *p)\n+{\n+\tp->offset = f->offset;\n+\tp->ctx = f->ctx;\t/* larger than I'd like */\n+}\n+\n+/*\n+ * Restore previous position/state in output file\n+ * (can be slow)\n+ */\n+void sha1undo(struct sha1file *f, struct sha1posn *p, long new, long old)\n+{\n+\tif (new - old == (long)f->offset - (long)p->offset) {\n+\t\tf->ctx = p->ctx;\n+\t\tf->offset = p->offset;\n+\t\treturn;\n+\t}\n+\tif (lseek(f->fd, (off_t)old - (off_t)p->offset, SEEK_SET) == (off_t)-1)\n+\t\tdie(\"sha1 file '%s' undo seekback error (%s)\", f->name, strerror(errno));\n+\tf->ctx = p->ctx;\n+\twhile (p->offset) {\n+\t\tint ret = xread(f->fd, f->buffer, p->offset);\n+\t\tif (!ret)\n+\t\t\tdie(\"sha1 file '%s' undo readback error. No data\", f->name);\n+\t\tif (ret < 0)\n+\t\t\tdie(\"sha1 file '%s' undo readback error (%s)\", f->name, strerror(errno));\n+\t\tSHA1_Update(&f->ctx, f->buffer, ret);\n+\t\tp->offset -= ret;\n+\t}\n+\tif (ftruncate(f->fd, (off_t)old))\n+\t\tdie(\"sha1 file '%s' undo truncate error (%s)\", f->name, strerror(errno));\n+\tf->offset = 0;\n+}\n+\n struct sha1file *sha1create(const char *fmt, ...)\n {\n \tstruct sha1file *f;\ndiff --git a/csum-file.h b/csum-file.h\nindex 3ad1a99..780df17 100644\n--- a/csum-file.h\n+++ b/csum-file.h\n@@ -9,11 +9,17 @@ struct sha1file {\n \tchar name[PATH_MAX];\n \tunsigned char buffer[8192];\n };\n+struct sha1posn {\n+\tunsigned int offset;\n+\tSHA_CTX ctx;\n+};\n \n extern struct sha1file *sha1fd(int fd, const char *name);\n extern struct sha1file *sha1create(const char *fmt, ...) __attribute__((format (printf, 1, 2)));\n extern int sha1close(struct sha1file *, unsigned char *, int);\n extern int sha1write(struct sha1file *, void *, unsigned int);\n extern int sha1write_compressed(struct sha1file *, void *, unsigned int);\n+extern void sha1mark(struct sha1file *, struct sha1posn *);\n+extern void sha1undo(struct sha1file *, struct sha1posn *, long, long);\n \n #endif\ndiff --git a/git-repack.sh b/git-repack.sh\nindex ddfa8b4..0299ff1 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -18,6 +18,9 @@ do\n \t-q)\tquiet=-q ;;\n \t-f)\tno_reuse_delta=--no-reuse-delta ;;\n \t-l)\tlocal=--local ;;\n+\t--pack-limit) extra=\"$extra $1\" ;;\n+\t--pack-limit=*) extra=\"$extra $1\" ;;\n+\t--blob-limit=*) extra=\"$extra $1\" ;;\n \t--window=*) extra=\"$extra $1\" ;;\n \t--depth=*) extra=\"$extra $1\" ;;\n \t*)\tusage ;;\n@@ -62,11 +65,12 @@ case \",$all_into_one,\" in\n esac\n \n args=\"$args $local $quiet $no_reuse_delta$extra\"\n-name=$(git-pack-objects --non-empty --all --reflog $args c);\n \t\tif (prev_posn>0) {\n \t\t\tprev_posn = 0;\n-\t\t\tlseek(obj_req->local, SEEK_SET, 0);\n+\t\t\tlseek(obj_req->local, 0, SEEK_SET);\n \t\t\tftruncate(obj_req->local, 0);\n \t\t}\n \t}\ndiff --git a/http-push.c b/http-push.c\nindex 724720c..e3f7675 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -312,7 +312,7 @@ static void start_fetch_loose(struct transfer_request *request)\n \t\tSHA1_Init(&request->c);\n \t\tif (prev_posn>0) {\n \t\t\tprev_posn = 0;\n-\t\t\tlseek(request->local_fileno, SEEK_SET, 0);\n+\t\t\tlseek(request->local_fileno, 0, SEEK_SET);\n \t\t\tftruncate(request->local_fileno, 0);\n \t\t}\n \t}\ndiff --git a/index-pack.c b/index-pack.c\nindex 6284fe3..d35c4c4 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -249,7 +249,7 @@ static void *unpack_raw_entry(struct object_entry *obj, union delta_base *delta_\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || base_offset & ~(~0UL >> 1))\n \t\t\t\tbad_object(obj->offset, \"offset value overflow for delta base object\");\n \t\t\tp = fill(1);\n \t\t\tc = *p;\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 9c26038..7082d3e 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1149,7 +1149,7 @@ static off_t get_delta_base(struct packed_git *p,\n \t\tbase_offset = c & 127;\n \t\twhile (c & 128) {\n \t\t\tbase_offset += 1;\n-\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\tif (!base_offset || base_offset & ~(~0UL >> 1))\n \t\t\t\tdie(\"offset value overflow for delta base object\");\n \t\t\tc = base_info[used++];\n \t\t\tbase_offset = (base_offset << 7) + (c & 127);\n"},{"id":"38494","messageId":"20070403053959.GH15922@spearce.org","threadId":"7449","inReplyTo":"64E16DEF-E572-4384-9E68-42EBBCE678B1@adacore.com","subject":"Re: [RFC] Packing large repositories","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-03T05:39:59Z","receivedAt":"2007-04-03T05:39:59Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Geert Bosch wrote:\n> Actually, I had implemented this first, using two newton-raphson\n> iterations and then binary search. With just one iteration is\n> too little, and one iteration+binary search often is no win.\n> Two iterations followed by binary search cuts the nr of steps in\n> half for the Linux kernel. Two iterations followed by linear search\n> is often worse, because of \"unlucky\" cases that end up doing many\n> probes. Still, during the 5-8 probes in moderately large repositories\n> (1M objects), each probe pretty much requires its own cache line:\n> very cache unfriendly.\n\nIf Nico and I can ever find the time to get our ideas for pack v4\ncoded into something executable, I think you will find this is less\nof an issue than you think.\n\nWe're hoping to change enough of the commit and tree traversal\ncode that the \"tight\" loops around chasing tree, parent, and blob\npointers can be done using strictly pack offsets and completely\navoid these SHA-1 lookups. Thus the only time we'd fall into the\nabove-mentioned SHA-1 lookup path is on initial entry to a revision\nwalk, or when spanning to another packfile. This would mean most\nworkloads should only hit that code once per command line argument.\n\n-- \nShawn.\n"}]}