{"thread":{"id":"52760","subject":"[PATCH] pack-format: correct multi-pack-index description","startedAt":"2020-02-07T22:16:49Z","lastAt":"2020-02-10T17:02:16Z","messageCount":8,"participants":["Johannes Berg","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"391356","messageId":"20200207221640.46876-1-johannes@sipsolutions.net","threadId":"52760","inReplyTo":null,"subject":"[PATCH] pack-format: correct multi-pack-index description","fromName":"Johannes Berg","fromEmail":"johannes@sipsolutions.net","sentAt":"2020-02-07T22:16:40Z","receivedAt":"2020-02-07T22:16:49Z","isPatch":true,"sender":{"key":"johannes@sipsolutions.net","avatar":"https://avatars.githubusercontent.com/u/5159728?v=4"},"body":"The description of the multi-pack-index contains a small bug,\nif all offsets are < 2^32 then there will be no LOFF chunk,\nnot only if they're all < 2^31 (since the highest bit is only\nneeded as the \"LOFF-escape\" when that's actually needed.)\n\nCorrect this, and clarify that in that case only offsets up\nto 2^31-1 can be stored in the OOFF chunk.\n\nSigned-off-by: Johannes Berg <johannes@sipsolutions.net>\n---\n Documentation/technical/pack-format.txt | 5 +++--\n 1 file changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\nindex cab5bdd2ff0f..d3a142c65202 100644\n--- a/Documentation/technical/pack-format.txt\n+++ b/Documentation/technical/pack-format.txt\n@@ -315,10 +315,11 @@ CHUNK DATA:\n \t    Stores two 4-byte values for every object.\n \t    1: The pack-int-id for the pack storing this object.\n \t    2: The offset within the pack.\n-\t\tIf all offsets are less than 2^31, then the large offset chunk\n+\t\tIf all offsets are less than 2^32, then the large offset chunk\n \t\twill not exist and offsets are stored as in IDX v1.\n \t\tIf there is at least one offset value larger than 2^32-1, then\n-\t\tthe large offset chunk must exist. If the large offset chunk\n+\t\tthe large offset chunk must exist, and offsets larger than\n+\t\t2^31-1 must be stored in it instead. If the large offset chunk\n \t\texists and the 31st bit is on, then removing that bit reveals\n \t\tthe row in the large offsets containing the 8-byte offset of\n \t\tthis object.\n-- \n2.24.1\n\n"},{"id":"391449","messageId":"8d50143b-adb9-c642-5ca6-d51662c37dda@gmail.com","threadId":"52760","inReplyTo":"20200207221640.46876-1-johannes@sipsolutions.net","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-10T14:18:34Z","receivedAt":"2020-02-10T14:18:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/7/2020 5:16 PM, Johannes Berg wrote:\n> The description of the multi-pack-index contains a small bug,\n> if all offsets are < 2^32 then there will be no LOFF chunk,\n> not only if they're all < 2^31 (since the highest bit is only\n> needed as the \"LOFF-escape\" when that's actually needed.)\n> \n> Correct this, and clarify that in that case only offsets up\n> to 2^31-1 can be stored in the OOFF chunk.\n> \n> Signed-off-by: Johannes Berg <johannes@sipsolutions.net>\n> ---\n>  Documentation/technical/pack-format.txt | 5 +++--\n>  1 file changed, 3 insertions(+), 2 deletions(-)\n> \n> diff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\n> index cab5bdd2ff0f..d3a142c65202 100644\n> --- a/Documentation/technical/pack-format.txt\n> +++ b/Documentation/technical/pack-format.txt\n> @@ -315,10 +315,11 @@ CHUNK DATA:\n>  \t    Stores two 4-byte values for every object.\n>  \t    1: The pack-int-id for the pack storing this object.\n>  \t    2: The offset within the pack.\n> -\t\tIf all offsets are less than 2^31, then the large offset chunk\n> +\t\tIf all offsets are less than 2^32, then the large offset chunk\n>  \t\twill not exist and offsets are stored as in IDX v1.\n>  \t\tIf there is at least one offset value larger than 2^32-1, then\n> -\t\tthe large offset chunk must exist. If the large offset chunk\n> +\t\tthe large offset chunk must exist, and offsets larger than\n> +\t\t2^31-1 must be stored in it instead. If the large offset chunk\n>  \t\texists and the 31st bit is on, then removing that bit reveals\n>  \t\tthe row in the large offsets containing the 8-byte offset of\n>  \t\tthis object.\n\nThank you for finding this doc bug. This is a very subtle point,\nand you have described it very clearly.\n\n-Stolee\n\n"},{"id":"391450","messageId":"526a7a3d8d135c9b97890c1c238ca5baaa138c3c.camel@sipsolutions.net","threadId":"52760","inReplyTo":"8d50143b-adb9-c642-5ca6-d51662c37dda@gmail.com","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Johannes Berg","fromEmail":"johannes@sipsolutions.net","sentAt":"2020-02-10T14:22:53Z","receivedAt":"2020-02-10T14:22:59Z","isPatch":true,"sender":{"key":"johannes@sipsolutions.net","avatar":"https://avatars.githubusercontent.com/u/5159728?v=4"},"body":"On Mon, 2020-02-10 at 09:18 -0500, Derrick Stolee wrote:\n> \n> Thank you for finding this doc bug. This is a very subtle point,\n> and you have described it very clearly.\n\nI was going back and forth on the wording a bit, glad I found something\nthat you think is a good description :)\n\nAre you familiar with the multi-pack-index and how it's used, by any\nchance?\n\nI came here from bup (https://github.com/bup/bup/) and needed a way to\nstore the offset to find objects in \"pure bup\", today it only stores\nobject *presence* and *pack* in its multi-index, but not the offset.\n\nHowever, it seems to do a bit better in terms of not requiring a single\nmulti-index, but instead storing it in midx-*.midx files and multiple\ncan describe the repository state. Why wasn't something like that done\nfor git as well? It's a bit annoying to have to recreate the full midx\nevery time a pack file is added, and searching in two or three midx\nfiles wouldn't really be a big deal?\n\nAnyway, that's just an aside, but during all this investigation I\nstumbled across this small inconsistency - I'm glad the docs exist at\nall! :-)\n\nThanks,\njohannes\n\n"},{"id":"391462","messageId":"28b6fd7f-85ea-9ef1-1977-888cdd737c6d@gmail.com","threadId":"52760","inReplyTo":"526a7a3d8d135c9b97890c1c238ca5baaa138c3c.camel@sipsolutions.net","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-10T14:46:56Z","receivedAt":"2020-02-10T14:47:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/10/2020 9:22 AM, Johannes Berg wrote:\n> On Mon, 2020-02-10 at 09:18 -0500, Derrick Stolee wrote:\n>>\n>> Thank you for finding this doc bug. This is a very subtle point,\n>> and you have described it very clearly.\n> \n> I was going back and forth on the wording a bit, glad I found something\n> that you think is a good description :)\n> \n> Are you familiar with the multi-pack-index and how it's used, by any\n> chance?\n\nYes. I wrote the first version, and we use it a lot in VFS for Git.\n\n> I came here from bup (https://github.com/bup/bup/) and needed a way to\n> store the offset to find objects in \"pure bup\", today it only stores\n> object *presence* and *pack* in its multi-index, but not the offset.\n> \n> However, it seems to do a bit better in terms of not requiring a single\n> multi-index, but instead storing it in midx-*.midx files and multiple\n> can describe the repository state. Why wasn't something like that done\n> for git as well? It's a bit annoying to have to recreate the full midx\n> every time a pack file is added, and searching in two or three midx\n> files wouldn't really be a big deal?\n\nPart of my initial plan was to have this incremental file format.\nThe commit-graph uses a very similar mechanism. The difference may\nbe that you likely allow multiple .midx files found by scanning the\npack directory, but I would expect something like the\n\"commit-graph-chain\" file that provides an ordered list of the\nincremental files. This can be important for deciding when to merge\nlayers or delete old files, and would be critical to the possibility\nof converting reachability bitmaps to rely on a stable object order\nstored in the multi-pack-index instead of pack-order.\n\nThe reason the multi-pack-index has not become incremental is that\nVFS for Git no longer needs to write it very often. We write the\nentire multi-pack-index during a background job that triggers once\nper day. If we needed to write it more frequently, then the incremental\nformat would be more important to us.\n\nThat said: if someone wanted to contribute an incremental format,\nthen I would be happy to review it!\n\n> Anyway, that's just an aside, but during all this investigation I\n> stumbled across this small inconsistency - I'm glad the docs exist at\n> all! :-)\n\nI'm glad they helped.\n\nThanks,\n-Stolee\n\n"},{"id":"391463","messageId":"c077a2100038edf2b0c486c0d364bd00f3921074.camel@sipsolutions.net","threadId":"52760","inReplyTo":"28b6fd7f-85ea-9ef1-1977-888cdd737c6d@gmail.com","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Johannes Berg","fromEmail":"johannes@sipsolutions.net","sentAt":"2020-02-10T14:50:54Z","receivedAt":"2020-02-10T14:51:00Z","isPatch":true,"sender":{"key":"johannes@sipsolutions.net","avatar":"https://avatars.githubusercontent.com/u/5159728?v=4"},"body":"On Mon, 2020-02-10 at 09:46 -0500, Derrick Stolee wrote:\n\n> Part of my initial plan was to have this incremental file format.\n> The commit-graph uses a very similar mechanism. The difference may\n> be that you likely allow multiple .midx files found by scanning the\n> pack directory, \n\nRight, just scan and use any midx that exist, then compare the packs in\nthere against all the packs found, and then remove any packs that\nactually *are* in an midx from the search list. That leaves you with all\ninformation, but optimised by midx where possible.\n\n> but I would expect something like the\n> \"commit-graph-chain\" file that provides an ordered list of the\n> incremental files. This can be important for deciding when to merge\n> layers or delete old files, and would be critical to the possibility\n> of converting reachability bitmaps to rely on a stable object order\n> stored in the multi-pack-index instead of pack-order.\n\nRight, if we delete then we have to also remove any midx covering the\ndeleted pack, that's pretty rare in bup as a backup tool though.\n\n> The reason the multi-pack-index has not become incremental is that\n> VFS for Git no longer needs to write it very often. We write the\n> entire multi-pack-index during a background job that triggers once\n> per day. If we needed to write it more frequently, then the incremental\n> format would be more important to us.\n\nSo, wait, what if a new pack is created? Does it just get used in\naddition to the multi-pack-index, if it's not covered by it, like I\ndescribed above?\n\nIf so, I guess it wouldn't actually really matter here. I was afraid\n(but didn't check yet) that git would always use only the single multi-\npack-index file, and not also search additional packs, so that it always\nhas to be maintained in \"perfect order\" ...\n\n> That said: if someone wanted to contribute an incremental format,\n> then I would be happy to review it!\n\nI might still get motivated to do so :-)\n\njohannes\n\n"},{"id":"391464","messageId":"08dbc3be-34a7-fb8d-e0bd-56a79ab5b65a@gmail.com","threadId":"52760","inReplyTo":"c077a2100038edf2b0c486c0d364bd00f3921074.camel@sipsolutions.net","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-10T15:02:01Z","receivedAt":"2020-02-10T15:02:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/10/2020 9:50 AM, Johannes Berg wrote:\n> On Mon, 2020-02-10 at 09:46 -0500, Derrick Stolee wrote:\n> \n>> Part of my initial plan was to have this incremental file format.\n>> The commit-graph uses a very similar mechanism. The difference may\n>> be that you likely allow multiple .midx files found by scanning the\n>> pack directory, \n> \n> Right, just scan and use any midx that exist, then compare the packs in\n> there against all the packs found, and then remove any packs that\n> actually *are* in an midx from the search list. That leaves you with all\n> information, but optimised by midx where possible.\n> \n>> but I would expect something like the\n>> \"commit-graph-chain\" file that provides an ordered list of the\n>> incremental files. This can be important for deciding when to merge\n>> layers or delete old files, and would be critical to the possibility\n>> of converting reachability bitmaps to rely on a stable object order\n>> stored in the multi-pack-index instead of pack-order.\n> \n> Right, if we delete then we have to also remove any midx covering the\n> deleted pack, that's pretty rare in bup as a backup tool though.\n> \n>> The reason the multi-pack-index has not become incremental is that\n>> VFS for Git no longer needs to write it very often. We write the\n>> entire multi-pack-index during a background job that triggers once\n>> per day. If we needed to write it more frequently, then the incremental\n>> format would be more important to us.\n> \n> So, wait, what if a new pack is created? Does it just get used in\n> addition to the multi-pack-index, if it's not covered by it, like I\n> described above?\n> \n> If so, I guess it wouldn't actually really matter here. I was afraid\n> (but didn't check yet) that git would always use only the single multi-\n> pack-index file, and not also search additional packs, so that it always\n> has to be maintained in \"perfect order\" ...\n\nGit loads the multi-pack-index file, which includes a sorted list of\nthe packs it covers. It then scans the \"pack\" directory for pack-indexes\nand checks if they are covered by the multi-pack-index. If not, then\nGit will add them to the packed_git struct and use them as normal.\nThe hope is that this list of \"uncovered\" packs is small compared to\nthe data covered by the multi-pack-index.\n\nThis allows Git to continue functioning after an action like \"git fetch\"\nthat adds a new pack but may not want to rewrite the multi-pack-index.\n\nOur background maintenance essentially runs these commands:\n\n 1. git multi-pack-index write\n 2. git multi-pack-index expire\n 3. git multi-pack-index repack\n\nStep 1 ensures all packs are pulled into the multi-pack-index. Step 2\ndeletes any pack-files whose objects are contained in newer pack-files.\nStep 3 creates a new pack-file containing all objects from a set of\nsmall pack-files (using the --batch-size=X option). This process helps\nincrementally reduce the size and number of packs. That may be helpful\nfor your backup took, too.\n\nPerhaps after an incremental multi-pack-index is added, then Git could\n(optionally) have a mode that only checks the multi-pack-index to\navoid scanning the packs directory. It would require inserting a\nmulti-pack-index write into the index-pack logic so Git.\n\nI'm not sure if that mode would be helpful, since the pack directory\nscan is typically done once per command and is relatively fast.\n\n>> That said: if someone wanted to contribute an incremental format,\n>> then I would be happy to review it!\n> \n> I might still get motivated to do so :-)\n\nYOU CAN DO IT! (Did that help?)\n\n-Stolee\n"},{"id":"391465","messageId":"a52c8163abfba107a27b359a1588a68efdc581a8.camel@sipsolutions.net","threadId":"52760","inReplyTo":"08dbc3be-34a7-fb8d-e0bd-56a79ab5b65a@gmail.com","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Johannes Berg","fromEmail":"johannes@sipsolutions.net","sentAt":"2020-02-10T15:06:41Z","receivedAt":"2020-02-10T15:06:45Z","isPatch":true,"sender":{"key":"johannes@sipsolutions.net","avatar":"https://avatars.githubusercontent.com/u/5159728?v=4"},"body":"On Mon, 2020-02-10 at 10:02 -0500, Derrick Stolee wrote:\n> Git loads the multi-pack-index file, which includes a sorted list of\n> the packs it covers. It then scans the \"pack\" directory for pack-indexes\n> and checks if they are covered by the multi-pack-index. If not, then\n> Git will add them to the packed_git struct and use them as normal.\n> The hope is that this list of \"uncovered\" packs is small compared to\n> the data covered by the multi-pack-index.\n> \n> This allows Git to continue functioning after an action like \"git fetch\"\n> that adds a new pack but may not want to rewrite the multi-pack-index.\n\nAh, ok.\n\nSo then perhaps I'll just make bup write the multi-pack-index file as\nis. This is fine, there's no real need to have multiple, I just didn't\nwant to have to make sure the file was always consistent.\n\nOr maybe just call git to do it, and only be able to read the resulting\nfile :-)\n\n> Our background maintenance essentially runs these commands:\n> \n>  1. git multi-pack-index write\n>  2. git multi-pack-index expire\n>  3. git multi-pack-index repack\n> \n> Step 1 ensures all packs are pulled into the multi-pack-index. Step 2\n> deletes any pack-files whose objects are contained in newer pack-files.\n> Step 3 creates a new pack-file containing all objects from a set of\n> small pack-files (using the --batch-size=X option). This process helps\n> incrementally reduce the size and number of packs. That may be helpful\n> for your backup took, too.\n\nI'll have to look at this in more detail later, and understand exactly\nwhat the steps do here. Evidently that modifies pack files, which I\nhadn't expected for a type of \"index\" command :-)\n\n> Perhaps after an incremental multi-pack-index is added, then Git could\n> (optionally) have a mode that only checks the multi-pack-index to\n> avoid scanning the packs directory. It would require inserting a\n> multi-pack-index write into the index-pack logic so Git.\n\nI guess you'd still want to read non-covered pack files just in case old\ngit was used or something though.\n\n> I'm not sure if that mode would be helpful, since the pack directory\n> scan is typically done once per command and is relatively fast.\n\nRight.\n\n> > > That said: if someone wanted to contribute an incremental format,\n> > > then I would be happy to review it!\n> > \n> > I might still get motivated to do so :-)\n> \n> YOU CAN DO IT! (Did that help?)\n\n:-)\n\nThanks,\njohannes\n\n"},{"id":"391472","messageId":"xmqqpnem1ilr.fsf@gitster-ct.c.googlers.com","threadId":"52760","inReplyTo":"8d50143b-adb9-c642-5ca6-d51662c37dda@gmail.com","subject":"Re: [PATCH] pack-format: correct multi-pack-index description","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-10T17:02:08Z","receivedAt":"2020-02-10T17:02:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 2/7/2020 5:16 PM, Johannes Berg wrote:\n>> The description of the multi-pack-index contains a small bug,\n>> if all offsets are < 2^32 then there will be no LOFF chunk,\n>> not only if they're all < 2^31 (since the highest bit is only\n>> needed as the \"LOFF-escape\" when that's actually needed.)\n>> \n>> Correct this, and clarify that in that case only offsets up\n>> to 2^31-1 can be stored in the OOFF chunk.\n>> \n>> Signed-off-by: Johannes Berg <johannes@sipsolutions.net>\n>> ---\n>>  Documentation/technical/pack-format.txt | 5 +++--\n>>  1 file changed, 3 insertions(+), 2 deletions(-)\n>> \n>> diff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt\n>> index cab5bdd2ff0f..d3a142c65202 100644\n>> --- a/Documentation/technical/pack-format.txt\n>> +++ b/Documentation/technical/pack-format.txt\n>> @@ -315,10 +315,11 @@ CHUNK DATA:\n>>  \t    Stores two 4-byte values for every object.\n>>  \t    1: The pack-int-id for the pack storing this object.\n>>  \t    2: The offset within the pack.\n>> -\t\tIf all offsets are less than 2^31, then the large offset chunk\n>> +\t\tIf all offsets are less than 2^32, then the large offset chunk\n>>  \t\twill not exist and offsets are stored as in IDX v1.\n>>  \t\tIf there is at least one offset value larger than 2^32-1, then\n>> -\t\tthe large offset chunk must exist. If the large offset chunk\n>> +\t\tthe large offset chunk must exist, and offsets larger than\n>> +\t\t2^31-1 must be stored in it instead. If the large offset chunk\n>>  \t\texists and the 31st bit is on, then removing that bit reveals\n>>  \t\tthe row in the large offsets containing the 8-byte offset of\n>>  \t\tthis object.\n>\n> Thank you for finding this doc bug. This is a very subtle point,\n> and you have described it very clearly.\n\nThanks, both; queued.\n"}]}