{"thread":{"id":"34890","subject":"pack v4 trees with a canonical base","startedAt":"2013-09-09T19:25:35Z","lastAt":"2013-09-10T21:03:31Z","messageCount":6,"participants":["Nicolas Pitre","Duy Nguyen","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"227248","messageId":"alpine.LFD.2.03.1309091517380.20709@syhkavp.arg","threadId":"34890","inReplyTo":null,"subject":"pack v4 trees with a canonical base","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-09T19:25:35Z","receivedAt":"2013-09-09T19:25:35Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"While reviewing the pack v4 thin support Ive realized that some base \ntree objects appended to a thin pack won't be in pack v4 format. Hence \nthe patch below to deal with that possibility.\n\nAn eventual optimization to index-pack when completing a pack would be \nto attempt the encoding of appended tree objects into the packv4 format \nusing the existing dictionary table in the pack, and fall back to the \ncanonical format if that table doesn't have all the necessary elements.\n\n packv4-parse.c: allow tree entry copying from a canonical tree object\n \n It is possible for a base tree object to be in the canonical\n representation. This may happen if the encoder detected an irregularity\n preventing a loss free encoding to the pack v4 format, or if a thin pack\n was completed with such tree objects.\n \n Signed-off-by: Nicolas Pitre \n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex c62c4ae..36942bb 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -10,6 +10,7 @@\n \n #include \"cache.h\"\n #include \"packv4-parse.h\"\n+#include \"tree-walk.h\"\n #include \"varint.h\"\n \n const unsigned char *get_sha1ref(struct packed_git *p,\n@@ -321,6 +322,45 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,\n \treturn dst;\n }\n \n+static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,\n+\t\t\t\t unsigned int start, unsigned int count,\n+\t\t\t\t unsigned char **dstp, unsigned long *sizep)\n+{\n+\tvoid *data;\n+\tconst void *from, *end;\n+\tenum object_type type;\n+\tunsigned long size;\n+\tstruct tree_desc desc;\n+\n+\tdata = unpack_entry(p, offset, &type, &size);\n+\tif (!data)\n+\t\treturn -1;\n+\tif (type != OBJ_TREE) {\n+\t\tfree(data);\n+\t\treturn -1;\n+\t}\n+\n+\tinit_tree_desc(&desc, data, size);\n+\n+\twhile (start--)\n+\t\tupdate_tree_entry(&desc);\n+\n+\tfrom = desc.buffer;\n+\twhile (count--)\n+\t\tupdate_tree_entry(&desc);\n+\tend = desc.buffer;\n+\n+\tif (end - from > *sizep) {\n+\t\tfree(data);\n+\t\treturn -1;\n+\t}\n+\tmemcpy(*dstp, from, end - from);\n+\t*dstp += end - from;\n+\t*sizep -= end - from;\n+\tfree(data);\n+\treturn 0;\n+}\n+\n static int tree_entry_prefix(unsigned char *buf, unsigned long size,\n \t\t\t const unsigned char *path, unsigned mode)\n {\n@@ -364,7 +404,12 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\twhile (*scp & 128)\n \t\t\tif (++scp - src >= avail - 20)\n \t\t\t\treturn -1;\n-\t\t/* let's still make sure this is actually a tree */\n+\t\t/* is this a canonical tree object? */\n+\t\tif ((*scp & 0xf) == OBJ_TREE)\n+\t\t\treturn copy_canonical_tree_entries(p, offset,\n+\t\t\t\t\t\t\t start, count,\n+\t\t\t\t\t\t\t dstp, sizep);\n+\t\t/* let's still make sure this is actually a pv4 tree */\n \t\tif ((*scp++ & 0xf) != OBJ_PV4_TREE)\n \t\t\treturn -1;\n \t}\n"},{"id":"227290","messageId":"CACsJy8C+SFBRD1czeeK5VBDYT4xA6K+61HgLRnjB+CYJ-2g+uA@mail.gmail.com","threadId":"34890","inReplyTo":"alpine.LFD.2.03.1309091517380.20709@syhkavp.arg","subject":"Re: pack v4 trees with a canonical base","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-10T00:52:15Z","receivedAt":"2013-09-10T00:52:15Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Sep 10, 2013 at 2:25 AM, Nicolas Pitre wrote:\n> An eventual optimization to index-pack when completing a pack would be\n> to attempt the encoding of appended tree objects into the packv4 format\n> using the existing dictionary table in the pack, and fall back to the\n> canonical format if that table doesn't have all the necessary elements.\n\nYeah, it's on the improvement todo list. The way pack-objects creates\ndictionaries right now, the tree dict should contain all elements the\nbase trees need so fall back is only necessary when trees are have\nextra zeros in mode field.\n-- \nDuy\n"},{"id":"227362","messageId":"xmqqbo40xwnv.fsf@gitster.dls.corp.google.com","threadId":"34890","inReplyTo":"CACsJy8C+SFBRD1czeeK5VBDYT4xA6K+61HgLRnjB+CYJ-2g+uA@mail.gmail.com","subject":"Re: pack v4 trees with a canonical base","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-10T20:13:24Z","receivedAt":"2013-09-10T20:13:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> On Tue, Sep 10, 2013 at 2:25 AM, Nicolas Pitre wrote:\n>> An eventual optimization to index-pack when completing a pack would be\n>> to attempt the encoding of appended tree objects into the packv4 format\n>> using the existing dictionary table in the pack, and fall back to the\n>> canonical format if that table doesn't have all the necessary elements.\n>\n> Yeah, it's on the improvement todo list. The way pack-objects creates\n> dictionaries right now, the tree dict should contain all elements the\n> base trees need so fall back is only necessary when trees are have\n> extra zeros in mode field.\n\nCareful.\n\nThere may be trees in the wild that record 100775 or 100777 in the\nmode field for executable blobs, which also need to be special\ncased.\n"},{"id":"227363","messageId":"alpine.LFD.2.03.1309101615080.20709@syhkavp.arg","threadId":"34890","inReplyTo":"xmqqbo40xwnv.fsf@gitster.dls.corp.google.com","subject":"Re: pack v4 trees with a canonical base","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-10T20:17:27Z","receivedAt":"2013-09-10T20:17:27Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 10 Sep 2013, Junio C Hamano wrote:\n\n> Duy Nguyen writes:\n> \n> > On Tue, Sep 10, 2013 at 2:25 AM, Nicolas Pitre wrote:\n> >> An eventual optimization to index-pack when completing a pack would be\n> >> to attempt the encoding of appended tree objects into the packv4 format\n> >> using the existing dictionary table in the pack, and fall back to the\n> >> canonical format if that table doesn't have all the necessary elements.\n> >\n> > Yeah, it's on the improvement todo list. The way pack-objects creates\n> > dictionaries right now, the tree dict should contain all elements the\n> > base trees need so fall back is only necessary when trees are have\n> > extra zeros in mode field.\n> \n> Careful.\n> \n> There may be trees in the wild that record 100775 or 100777 in the\n> mode field for executable blobs, which also need to be special\n> cased.\n\nAll the file mode bits are always preserved. So this is not really a \nspecial case as far as the pack v4 encoding is concerned.\n\n\nNicolas\n"},{"id":"227365","messageId":"xmqq38pcxv5z.fsf@gitster.dls.corp.google.com","threadId":"34890","inReplyTo":"alpine.LFD.2.03.1309101615080.20709@syhkavp.arg","subject":"Re: pack v4 trees with a canonical base","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-10T20:45:44Z","receivedAt":"2013-09-10T20:45:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\nvery much appreciated to> On Tue, 10 Sep 2013, Junio C Hamano wrote:\n>\n>> Duy Nguyen writes:\n>> \n>> > On Tue, Sep 10, 2013 at 2:25 AM, Nicolas Pitre wrote:\n>> >> An eventual optimization to index-pack when completing a pack would be\n>> >> to attempt the encoding of appended tree objects into the packv4 format\n>> >> using the existing dictionary table in the pack, and fall back to the\n>> >> canonical format if that table doesn't have all the necessary elements.\n>> >\n>> > Yeah, it's on the improvement todo list. The way pack-objects creates\n>> > dictionaries right now, the tree dict should contain all elements the\n>> > base trees need so fall back is only necessary when trees are have\n>> > extra zeros in mode field.\n>> \n>> Careful.\n>> \n>> There may be trees in the wild that record 100775 or 100777 in the\n>> mode field for executable blobs, which also need to be special\n>> cased.\n>\n> All the file mode bits are always preserved. So this is not really a \n> special case as far as the pack v4 encoding is concerned.\n\nAhh. OK. It can theoretically be argued that you could further\nsqueeze 13 bits out per tree entry because you would need only 5\npossible values (100644, 100755 120000, 40000, and 160000, all\noctal) for the modes, but we will never know what other modes we\nwould want to use in the future, so not being over-tight and using\n16-bit for this purpose is probably a good trade-off (squeezing 8\nbits out per tree entry would make the shape of ident table entry\nand tree path entry different and may hurt reusing the code to parse\nthese tables).\n"},{"id":"227367","messageId":"alpine.LFD.2.03.1309101652240.20709@syhkavp.arg","threadId":"34890","inReplyTo":"xmqq38pcxv5z.fsf@gitster.dls.corp.google.com","subject":"Re: pack v4 trees with a canonical base","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-09-10T21:03:31Z","receivedAt":"2013-09-10T21:03:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 10 Sep 2013, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > On Tue, 10 Sep 2013, Junio C Hamano wrote:\n> >\n> >> There may be trees in the wild that record 100775 or 100777 in the\n> >> mode field for executable blobs, which also need to be special\n> >> cased.\n> >\n> > All the file mode bits are always preserved. So this is not really a \n> > special case as far as the pack v4 encoding is concerned.\n> \n> Ahh. OK. It can theoretically be argued that you could further\n> squeeze 13 bits out per tree entry because you would need only 5\n> possible values (100644, 100755 120000, 40000, and 160000, all\n> octal) for the modes, but we will never know what other modes we\n> would want to use in the future, so not being over-tight and using\n> 16-bit for this purpose is probably a good trade-off\n\nAbsolutely. I tried not to lose any of the currently available \nextension possibilities in the canonical object format.\n\n> (squeezing 8 bits out per tree entry would make the shape of ident \n> table entry and tree path entry different and may hurt reusing the \n> code to parse these tables).\n\nOne could argue that 16 bits is much more than sufficient to encode a \ntime zone offset too. but again this didn't seem worth painting \nourselves in a corner if ever some creative time zones are used.\n\nThose table are also compressed. So any repetition of the same mode bit \npattern or sparseness in the tz bits is likely to be compressed well.\n\n\nNicolas\n"}]}