{"thread":{"id":"50158","subject":"How DELTA objects values work and are calculated","startedAt":"2019-01-05T02:48:29Z","lastAt":"2019-01-06T02:33:19Z","messageCount":4,"participants":["Farhan Khan","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"366171","messageId":"CAFd4kYBX+HrLxbga=VJgC5WjyeDZEznm2UCL+HF8A1YKVo3Trw@mail.gmail.com","threadId":"50158","inReplyTo":null,"subject":"How DELTA objects values work and are calculated","fromName":"Farhan Khan","fromEmail":"khanzf@gmail.com","sentAt":"2019-01-05T02:48:03Z","receivedAt":"2019-01-05T02:48:29Z","isPatch":false,"sender":{"key":"khanzf@gmail.com","avatar":null},"body":"Hi all,\n\nI'm having trouble understanding how OBJ_REF_DELTA and OBJ_REF_DELTA\n(deltas) work in git. Where does git calculate the sha1 hash values\nwhen doing \"git index-pack\" in builtin/index-pack.c. I think my lack\nof understanding of the code is compounded the fact that I do not\nunderstand what the two object types are.\n\nFrom tracing the code starting from index-pack, all non-delta object\ntype hashes are calculated in index-pack.c:1131 (parse_pack_objects).\nHowever, when the function ends, the delta objects hash values are set\nto all 0's.\n\nMy questions are:\nA) How do Delta objects work?\nB) Where and how are the sha1 values calculated?\n\nI have read Documentation/technical/pack-format.txt, but am still not clear.\n\nThank you!\n--\nFarhan Khan\nPGP Fingerprint: B28D 2726 E2BC A97E 3854 5ABE 9A9F 00BC D525 16EE\n"},{"id":"366189","messageId":"CACsJy8Da7+sNfxvTRz1DRn27TjvBXNAipKB=eumA6q+sVsVjcA@mail.gmail.com","threadId":"50158","inReplyTo":"CAFd4kYBX+HrLxbga=VJgC5WjyeDZEznm2UCL+HF8A1YKVo3Trw@mail.gmail.com","subject":"Re: How DELTA objects values work and are calculated","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-01-05T04:46:07Z","receivedAt":"2019-01-05T04:46:35Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Jan 5, 2019 at 9:49 AM Farhan Khan <khanzf@gmail.com> wrote:\n>\n> Hi all,\n>\n> I'm having trouble understanding how OBJ_REF_DELTA and OBJ_REF_DELTA\n> (deltas) work in git. Where does git calculate the sha1 hash values\n> when doing \"git index-pack\" in builtin/index-pack.c. I think my lack\n> of understanding of the code is compounded the fact that I do not\n> understand what the two object types are.\n>\n> From tracing the code starting from index-pack, all non-delta object\n> type hashes are calculated in index-pack.c:1131 (parse_pack_objects).\n> However, when the function ends, the delta objects hash values are set\n> to all 0's.\n\nDelta objects depend on other objects (and even delta ones). To\ncalculate its sha1 values we may need to recursively calculate sha1\nvalues of its base objects. This is why we do it in a separate phase\nbecause the calculation is more complicated than non-delta objects.\n\n> My questions are:\n> A) How do Delta objects work?\n\nA delta object consists of a reference to the base object (either an\nsha1 value, or the offset to where the object is) and a \"delta\" to be\napplied on (it's basically a binary diff).\n\n> B) Where and how are the sha1 values calculated?\n\nStart at threaded_second_pass() in index-pack.c, we go through all\ndelta objects here and try to calculate their sha1 values. Eventually\nyou'll hit resolve_delta(), where the delta is actually applied to the\nbase object in the patch_delta() call, and the sha1 value calculated\nin the following hash_object_file() call.\n\n>\n> I have read Documentation/technical/pack-format.txt, but am still not clear.\n>\n> Thank you!\n> --\n> Farhan Khan\n> PGP Fingerprint: B28D 2726 E2BC A97E 3854 5ABE 9A9F 00BC D525 16EE\n\n\n\n-- \nDuy\n"},{"id":"366194","messageId":"581076b0-95c5-9af9-dec5-5a9bccfe2634@gmail.com","threadId":"50158","inReplyTo":"CACsJy8Da7+sNfxvTRz1DRn27TjvBXNAipKB=eumA6q+sVsVjcA@mail.gmail.com","subject":"Re: How DELTA objects values work and are calculated","fromName":"Farhan Khan","fromEmail":"khanzf@gmail.com","sentAt":"2019-01-05T22:32:46Z","receivedAt":"2019-01-05T22:32:54Z","isPatch":false,"sender":{"key":"khanzf@gmail.com","avatar":null},"body":"\n\nOn 1/4/19 11:46 PM, Duy Nguyen wrote:\n> On Sat, Jan 5, 2019 at 9:49 AM Farhan Khan <khanzf@gmail.com> wrote:\n>>\n>> Hi all,\n>>\n>> I'm having trouble understanding how OBJ_REF_DELTA and OBJ_REF_DELTA\n>> (deltas) work in git. Where does git calculate the sha1 hash values\n>> when doing \"git index-pack\" in builtin/index-pack.c. I think my lack\n>> of understanding of the code is compounded the fact that I do not\n>> understand what the two object types are.\n>>\n>>  From tracing the code starting from index-pack, all non-delta object\n>> type hashes are calculated in index-pack.c:1131 (parse_pack_objects).\n>> However, when the function ends, the delta objects hash values are set\n>> to all 0's.\n> \n> Delta objects depend on other objects (and even delta ones). To\n> calculate its sha1 values we may need to recursively calculate sha1\n> values of its base objects. This is why we do it in a separate phase\n> because the calculation is more complicated than non-delta objects.\n> \n>> My questions are:\n>> A) How do Delta objects work?\n> \n> A delta object consists of a reference to the base object (either an\n> sha1 value, or the offset to where the object is) and a \"delta\" to be\n> applied on (it's basically a binary diff).\n> \n>> B) Where and how are the sha1 values calculated?\n> \n> Start at threaded_second_pass() in index-pack.c, we go through all\n> delta objects here and try to calculate their sha1 values. Eventually\n> you'll hit resolve_delta(), where the delta is actually applied to the\n> base object in the patch_delta() call, and the sha1 value calculated\n> in the following hash_object_file() call.\n> \n>>\n>> I have read Documentation/technical/pack-format.txt, but am still not clear.\n>>\n>> Thank you!\n>> --\n>> Farhan Khan\n>> PGP Fingerprint: B28D 2726 E2BC A97E 3854 5ABE 9A9F 00BC D525 16EE\n> \n> \n> \n\n\nHi Duy,\n\nThanks for explaining the Delta objects.\n\nWhat does a OBJ_REF_DELTA object itself consist of? Do you have to \nuncompress it to parse its values? How do you get its size?\n\nI read through resolve deltas which leads to threaded_second_pass, where \nyou suggested to start, but I do not understand what is happening at a \nhigh level and get confused while reading the code.\n\n From threaded_second_pass, execution goes into a for-loop that runs \nresolve_base(), which runs runs find_unresolved_deltas(). Is this \nfinding the unresolved deltas of the current object (The current \nOBJ_REF_DELTA we are going through)? This then runs \nfind_unresolved_deltas() and shortly afterwards \nfind_unresolved_deltas_1(). It seems that find_unresolved_deltas_1() is \napplying deltas, but I am not certain.\n\nI do not understand what is happening in any of these functions. There \nare some comments on builtin/index-pack.c:883-904\n\nOverall, I do not understand this entire process, what values to capture \nalong the way, and how they are consumed. Please provide some guidance \non how this process works.\n\nThank you!\nFarhan\n"},{"id":"366200","messageId":"CACsJy8A9=sKjoM+3ZoA0-PnufC4MNvP9MPoM9r6FN3sxAcZvbA@mail.gmail.com","threadId":"50158","inReplyTo":"581076b0-95c5-9af9-dec5-5a9bccfe2634@gmail.com","subject":"Re: How DELTA objects values work and are calculated","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-01-06T02:32:50Z","receivedAt":"2019-01-06T02:33:19Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jan 6, 2019 at 5:32 AM Farhan Khan <khanzf@gmail.com> wrote:\n> Hi Duy,\n>\n> Thanks for explaining the Delta objects.\n>\n> What does a OBJ_REF_DELTA object itself consist of?\n\nfrom pack-format.txt\n\n     (deltified representation)\n     n-byte type and length (3-bit type, (n-1)*7+4-bit length)\n     20-byte base object name if OBJ_REF_DELTA or a negative relative\noffset from the delta object's position in the pack if this\nis an OBJ_OFS_DELTA object\n     compressed delta data\n\n\n> Do you have to uncompress it to parse its values?\n\nThe delta part is compressed, so yes. The \"base object name\" is not.\n\n> How do you get its size?\n\nUncompress until the end the delta until the end. zlib stream has some\nsort of \"end-of-stream\" marker so it knows when to stop.\n\n> I read through resolve deltas which leads to threaded_second_pass, where\n> you suggested to start, but I do not understand what is happening at a\n> high level and get confused while reading the code.\n>\n>  From threaded_second_pass, execution goes into a for-loop that runs\n> resolve_base(), which runs runs find_unresolved_deltas(). Is this\n> finding the unresolved deltas of the current object (The current\n> OBJ_REF_DELTA we are going through)? This then runs\n> find_unresolved_deltas() and shortly afterwards\n> find_unresolved_deltas_1(). It seems that find_unresolved_deltas_1() is\n> applying deltas, but I am not certain.\n\nAh I forgot how \"fun\" these functions were :) The obvious way to\nresolve an delta object is to resolve (recursively) its base object\nfirst, then you apply delta on top and are done. However that implies\nrecursion, and also not really cache friendly. So what\nfind_unresolve_deltas_1() does is backward. It starts at a (already\nresolved, e.g. non-delta) base object, then applies deltas for all\ndelta objects that immediately depend on it, then continue to resolve\ndelta objects depending on these children... The\nfind_*_delta_children() functions find these deltas, then\nfind_unresolve_deltas_1() will call resolve_delta() to do the real\nwork\n\n- the delta type (OBJ_REF_.. or OBJ_OFS_...) is already known at this\npoint. I believe we know from the first pass\n- the delta is uncompressed here, with get_data_from_pack()\n- the base object is obtained via get_base_data(), which is recursive,\nbut since we go backwards from parent to child, base->data should be\nalready valid and get_base_data() becomes no-op\n\n> I do not understand what is happening in any of these functions. There\n> are some comments on builtin/index-pack.c:883-904\n>\n> Overall, I do not understand this entire process, what values to capture\n> along the way, and how they are consumed. Please provide some guidance\n> on how this process works.\n\nAn easier way to understand this is actually run it through a debugger\n(in single thread mode). Create a small repo with a handful of deltas.\nUse \"git verify-pack -v\" to see what object is delta and where... then\nyou have something to double check while you step through the code.\n\n>\n> Thank you!\n> Farhan\n-- \nDuy\n"}]}