{"thread":{"id":"29086","subject":"[PATCH] Set hard limit on delta chain depth","startedAt":"2011-12-05T07:04:48Z","lastAt":"2011-12-10T00:02:19Z","messageCount":19,"participants":["Nguyễn Thái Ngọc Duy","Erik Faye-Lund","Nguyen Thai Ngoc Duy","Michael Haggerty","Junio C Hamano","Shawn Pearce","Jeff King","pclouds@gmail.com"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"180303","messageId":"1323068688-31481-1-git-send-email-pclouds@gmail.com","threadId":"29086","inReplyTo":null,"subject":"[PATCH] Set hard limit on delta chain depth","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-05T07:04:48Z","receivedAt":"2011-12-05T07:04:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Too deep delta chains can cause stack overflow in get_base_data(). Set\na hard limit so that index-pack does not run out of stack. Also stop\npeople from producing such a long delta chains using \"pack-object\n--depth=\"\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n I used to make very long delta chains and triggered this in index-pack.\n I did not care reporting because it's my fault anyway. Think again,\n index-pack is called at server side and a malicious client can\n trigger this. This patch does not improve the situation much, but at\n least we won't get sigsegv at server side.\n\n builtin/index-pack.c | 12 ++++++++++--\n builtin/pack-objects.c | 3 +++\n pack.h | 2 ++\n 3 files changed, 15 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0945adb..cfb8cb2 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -504,13 +504,16 @@ static int is_delta_type(enum object_type type)\n \treturn (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);\n }\n \n-static void *get_base_data(struct base_data *c)\n+static void *get_base_data_1(struct base_data *c, int depth)\n {\n+\tif (depth > MAX_DELTA_DEPTH)\n+\t\tdie(\"index-pack: too long delta chain\");\n+\n \tif (!c->data) {\n \t\tstruct object_entry *obj = c->obj;\n \n \t\tif (is_delta_type(obj->type)) {\n-\t\t\tvoid *base = get_base_data(c->base);\n+\t\t\tvoid *base = get_base_data_1(c->base, depth + 1);\n \t\t\tvoid *raw = get_data_from_pack(obj);\n \t\t\tc->data = patch_delta(\n \t\t\t\tbase, c->base->size,\n@@ -530,6 +533,11 @@ static void *get_base_data(struct base_data *c)\n \treturn c->data;\n }\n \n+static void *get_base_data(struct base_data *c)\n+{\n+\treturn get_base_data_1(c, 0);\n+}\n+\n static void resolve_delta(struct object_entry *delta_obj,\n \t\t\t struct base_data *base, struct base_data *result)\n {\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 824ecee..85ee04b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2508,6 +2508,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (keep_unreachable && unpack_unreachable)\n \t\tdie(\"--keep-unreachable and --unpack-unreachable are incompatible.\");\n \n+\tif (depth > MAX_DELTA_DEPTH)\n+\t\tdie(\"--depth exceeds %d\", MAX_DELTA_DEPTH);\n+\n \tif (progress && all_progress_implied)\n \t\tprogress = 2;\n \ndiff --git a/pack.h b/pack.h\nindex 722a54e..b8f60c3 100644\n--- a/pack.h\n+++ b/pack.h\n@@ -3,6 +3,8 @@\n \n #include \"object.h\"\n \n+#define MAX_DELTA_DEPTH 128\n+\n /*\n * Packed object header\n */\n-- \n1.7.8.36.g69ee2\n"},{"id":"180369","messageId":"CABPQNSaE=TWGbBRMnthEuT181=XbOafPfgx88_JQnnQ6TiYyqw@mail.gmail.com","threadId":"29086","inReplyTo":"1323068688-31481-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-12-06T12:17:39Z","receivedAt":"2011-12-06T12:17:39Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"2011/12/5 Nguyễn Thái Ngọc Duy :\n> Too deep delta chains can cause stack overflow in get_base_data(). Set\n> a hard limit so that index-pack does not run out of stack. Also stop\n> people from producing such a long delta chains using \"pack-object\n> --depth=\"\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n>  I used to make very long delta chains and triggered this in index-pack.\n>  I did not care reporting because it's my fault anyway. Think again,\n>  index-pack is called at server side and a malicious client can\n>  trigger this. This patch does not improve the situation much, but at\n>  least we won't get sigsegv at server side.\n>\n\nWouldn't it make more sense to make the limit a config option rather\nthan a hard-coded value of 128 (which seems arbitrary to me)? After\nall, different platforms have different stack-limitations...\n"},{"id":"180370","messageId":"CACsJy8BuUn4htSR6jAJfbueOshE6-YVV5dZGSWTGXbkuA0HO=A@mail.gmail.com","threadId":"29086","inReplyTo":"CABPQNSaE=TWGbBRMnthEuT181=XbOafPfgx88_JQnnQ6TiYyqw@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T12:32:41Z","receivedAt":"2011-12-06T12:32:41Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2011/12/6 Erik Faye-Lund :\n> 2011/12/5 Nguyễn Thái Ngọc Duy :\n>> Too deep delta chains can cause stack overflow in get_base_data(). Set\n>> a hard limit so that index-pack does not run out of stack. Also stop\n>> people from producing such a long delta chains using \"pack-object\n>> --depth=\"\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>>  I used to make very long delta chains and triggered this in index-pack.\n>>  I did not care reporting because it's my fault anyway. Think again,\n>>  index-pack is called at server side and a malicious client can\n>>  trigger this. This patch does not improve the situation much, but at\n>>  least we won't get sigsegv at server side.\n>>\n>\n> Wouldn't it make more sense to make the limit a config option rather\n> than a hard-coded value of 128 (which seems arbitrary to me)? After\n> all, different platforms have different stack-limitations...\n\nThen it'd make more sense to make a compile time config based on\nplatform. We could have a config option that can override the default,\nbut I really don't see the point of making long delta chains.\n-- \nDuy\n"},{"id":"180371","messageId":"CABPQNSbOvVkSFAE32hXoZEZeHqg-+nHc93uGytfCPQMicu0uVg@mail.gmail.com","threadId":"29086","inReplyTo":"CACsJy8BuUn4htSR6jAJfbueOshE6-YVV5dZGSWTGXbkuA0HO=A@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Erik Faye-Lund","fromEmail":"kusmabite@gmail.com","sentAt":"2011-12-06T12:41:38Z","receivedAt":"2011-12-06T12:41:38Z","isPatch":true,"sender":{"key":"kusmabite@gmail.com","avatar":"https://avatars.githubusercontent.com/u/47073?v=4"},"body":"On Tue, Dec 6, 2011 at 1:32 PM, Nguyen Thai Ngoc Duy wrote:\n> 2011/12/6 Erik Faye-Lund :\n>> 2011/12/5 Nguyễn Thái Ngọc Duy :\n>>> Too deep delta chains can cause stack overflow in get_base_data(). Set\n>>> a hard limit so that index-pack does not run out of stack. Also stop\n>>> people from producing such a long delta chains using \"pack-object\n>>> --depth=\"\n>>>\n>>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>>> ---\n>>>  I used to make very long delta chains and triggered this in index-pack.\n>>>  I did not care reporting because it's my fault anyway. Think again,\n>>>  index-pack is called at server side and a malicious client can\n>>>  trigger this. This patch does not improve the situation much, but at\n>>>  least we won't get sigsegv at server side.\n>>>\n>>\n>> Wouldn't it make more sense to make the limit a config option rather\n>> than a hard-coded value of 128 (which seems arbitrary to me)? After\n>> all, different platforms have different stack-limitations...\n>\n> Then it'd make more sense to make a compile time config based on\n> platform.\n\nCan how much stack each recursion use be calculated at compile-time?\nIf so, I agree with you.\n\n> We could have a config option that can override the default,\n> but I really don't see the point of making long delta chains.\n\nAha, I figured you _did_ see a point in this, because 128 seemed\nexcessive to me already. I was thinking more that some platforms can\nhave a much smaller stack than (I would expect to) fit in 128\nrecursions (I've worked relatively recently with platforms with as\nsmall as a static 2k stack per process), so you might not be fixing\nthe issue for such platforms. But that's not really your\nresponsibility either ;)\n"},{"id":"180372","messageId":"CACsJy8BNzMbFcUpKq3vWqmevJeuPxZo+sB7ZxL5BTK_ojYZVjg@mail.gmail.com","threadId":"29086","inReplyTo":"CABPQNSbOvVkSFAE32hXoZEZeHqg-+nHc93uGytfCPQMicu0uVg@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T12:48:28Z","receivedAt":"2011-12-06T12:48:28Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 6, 2011 at 7:41 PM, Erik Faye-Lund wrote:\n>>> Wouldn't it make more sense to make the limit a config option rather\n>>> than a hard-coded value of 128 (which seems arbitrary to me)? After\n>>> all, different platforms have different stack-limitations...\n>>\n>> Then it'd make more sense to make a compile time config based on\n>> platform.\n>\n> Can how much stack each recursion use be calculated at compile-time?\n> If so, I agree with you.\n\nNo, but at least we know default stack size of each platform and can\nmake pretty good limit based on that.\n\n>> We could have a config option that can override the default,\n>> but I really don't see the point of making long delta chains.\n>\n> Aha, I figured you _did_ see a point in this, because 128 seemed\n> excessive to me already. I was thinking more that some platforms can\n> have a much smaller stack than (I would expect to) fit in 128\n> recursions (I've worked relatively recently with platforms with as\n> small as a static 2k stack per process), so you might not be fixing\n> the issue for such platforms. But that's not really your\n> responsibility either ;)\n\nAh, I was thinking of an option that extends the limit, not shortens\nit. Yes it makes sense in this case.\n-- \nDuy\n"},{"id":"180375","messageId":"4EDE2C95.5040804@alum.mit.edu","threadId":"29086","inReplyTo":"CABPQNSaE=TWGbBRMnthEuT181=XbOafPfgx88_JQnnQ6TiYyqw@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-12-06T14:54:13Z","receivedAt":"2011-12-06T14:54:13Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/06/2011 01:17 PM, Erik Faye-Lund wrote:\n> 2011/12/5 Nguyễn Thái Ngọc Duy :\n>> Too deep delta chains can cause stack overflow in get_base_data(). Set\n>> a hard limit so that index-pack does not run out of stack. Also stop\n>> people from producing such a long delta chains using \"pack-object\n>> --depth=\"\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>> I used to make very long delta chains and triggered this in index-pack.\n>> I did not care reporting because it's my fault anyway. Think again,\n>> index-pack is called at server side and a malicious client can\n>> trigger this. This patch does not improve the situation much, but at\n>> least we won't get sigsegv at server side.\n> \n> Wouldn't it make more sense to make the limit a config option rather\n> than a hard-coded value of 128 (which seems arbitrary to me)? After\n> all, different platforms have different stack-limitations...\n\nI'm confused: is the data only ever read by the same host that generated\nit? Because if not, then the \"creator\" had better never be configured\nto use a chain depth that the \"reader\" cannot handle. This in turn\nimply that there should be a common limit that is supported by all git\nclients and is a documented part of the protocol. (Or the code has to\nbe rewritten to use an explicit stack instead of recursion.)\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"180376","messageId":"7vvcpthh97.fsf@alter.siamese.dyndns.org","threadId":"29086","inReplyTo":"1323068688-31481-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-12-06T15:06:12Z","receivedAt":"2011-12-06T15:06:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> Too deep delta chains can cause stack overflow in get_base_data(). Set\n> a hard limit so that index-pack does not run out of stack. Also stop\n> people from producing such a long delta chains using \"pack-object\n> --depth=\"\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> I used to make very long delta chains and triggered this in index-pack.\n> I did not care reporting because it's my fault anyway. Think again,\n> index-pack is called at server side and a malicious client can\n> trigger this. This patch does not improve the situation much, but at\n> least we won't get sigsegv at server side.\n\nWhy should we treat this condition any differently from the case where the\nsender of a pack used beefier machine than you have and stuffed a huge\nobject that the index-pack running on your box cannot hold in core,\ncausing xmalloc() to die on your machine?\n\nI do not think this is the right way to handle the issue. Your other patch\nto flatten the recursion to iteration looked a lot saner approach.\n"},{"id":"180377","messageId":"CACsJy8Btwn0=PGS+PJV-6DqYBmzOp7LTB2=R_kCx4SJHA2YDRw@mail.gmail.com","threadId":"29086","inReplyTo":"4EDE2C95.5040804@alum.mit.edu","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T15:30:30Z","receivedAt":"2011-12-06T15:30:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2011/12/6 Michael Haggerty :\n> On 12/06/2011 01:17 PM, Erik Faye-Lund wrote:\n>> 2011/12/5 Nguyễn Thái Ngọc Duy :\n>>> Too deep delta chains can cause stack overflow in get_base_data(). Set\n>>> a hard limit so that index-pack does not run out of stack. Also stop\n>>> people from producing such a long delta chains using \"pack-object\n>>> --depth=\"\n>>>\n>>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>>> ---\n>>>  I used to make very long delta chains and triggered this in index-pack.\n>>>  I did not care reporting because it's my fault anyway. Think again,\n>>>  index-pack is called at server side and a malicious client can\n>>>  trigger this. This patch does not improve the situation much, but at\n>>>  least we won't get sigsegv at server side.\n>>\n>> Wouldn't it make more sense to make the limit a config option rather\n>> than a hard-coded value of 128 (which seems arbitrary to me)? After\n>> all, different platforms have different stack-limitations...\n>\n> I'm confused: is the data only ever read by the same host that generated\n> it?\n\nindex-pack is called at server side as part of a push. So in theory\nthe sending side can generate very long delta chains and bring down\nthe server side.\n\n>  Because if not, then the \"creator\" had better never be configured\n> to use a chain depth that the \"reader\" cannot handle.\n\nNormal creators (i.e. C Git) use default depth 50 so we should be safe.\n\n>  This in turn\n> imply that there should be a common limit that is supported by all git\n> clients and is a documented part of the protocol.  (Or the code has to\n> be rewritten to use an explicit stack instead of recursion.)\n\nIt's the implementation limitation, not the protocol. If the server\npropagates error messages from index-pack back to client (I'm not\nsure), then users can adjust --depth to be accepted by server. We\ncould negotiate the limit over the protocol but not sure we would want\nto go that route.\n\nThe troubled code could be rewritten to avoid recursion. However long\ndelta chains may degrade performance, I'd rather have support to split\nlong chains (which can be done with --depth at client already) instead\nof just recursion elimination. This patch is simpler, so it would be\neasier to back port it if someone wants to do so.\n-- \nDuy\n"},{"id":"180378","messageId":"CACsJy8AZg3DgZzmPyXhCH9bGBqo9UN7-zLt_feTtpyajf5U1tw@mail.gmail.com","threadId":"29086","inReplyTo":"7vvcpthh97.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-06T15:45:12Z","receivedAt":"2011-12-06T15:45:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2011/12/6 Junio C Hamano :\n> Nguyễn Thái Ngọc Duy   writes:\n>\n>> Too deep delta chains can cause stack overflow in get_base_data(). Set\n>> a hard limit so that index-pack does not run out of stack. Also stop\n>> people from producing such a long delta chains using \"pack-object\n>> --depth=\"\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>>  I used to make very long delta chains and triggered this in index-pack.\n>>  I did not care reporting because it's my fault anyway. Think again,\n>>  index-pack is called at server side and a malicious client can\n>>  trigger this. This patch does not improve the situation much, but at\n>>  least we won't get sigsegv at server side.\n>\n> Why should we treat this condition any differently from the case where the\n> sender of a pack used beefier machine than you have and stuffed a huge\n> object that the index-pack running on your box cannot hold in core,\n> causing xmalloc() to die on your machine?\n\nThat's interesting. First of all xmalloc() is controlled by us while\nindex-pack code might lead to stack overflow exploit (never done it,\nnot sure if it's really pratical to do in this case).\n\nBut can I really use up all memory at server side by sending a huge pack?\n\n> I do not think this is the right way to handle the issue. Your other patch\n> to flatten the recursion to iteration looked a lot saner approach.\n\nIt may take me some time as I'm not really familar with this code.\nAnybody is welcome to step up and flatten the function.\n-- \nDuy\n"},{"id":"180389","messageId":"CAJo=hJuy27Uagmubbv=RqAOMx03e6JBgZxObkjFLg9oG2x_UqA@mail.gmail.com","threadId":"29086","inReplyTo":"CACsJy8Btwn0=PGS+PJV-6DqYBmzOp7LTB2=R_kCx4SJHA2YDRw@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-12-06T18:12:54Z","receivedAt":"2011-12-06T18:12:54Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Tue, Dec 6, 2011 at 07:30, Nguyen Thai Ngoc Duy wrote:\n> index-pack is called at server side as part of a push. So in theory\n> the sending side can generate very long delta chains and bring down\n> the server side.\n\nIt is also called at client side during fetch. So in theory the server\ncan produce very long delta chains and take down a client.\n\n>>  Because if not, then the \"creator\" had better never be configured\n>> to use a chain depth that the \"reader\" cannot handle.\n>\n> Normal creators (i.e. C Git) use default depth 50 so we should be safe.\n\nJGit is also a \"normal creator\", and it sometimes produces chains\ndeeper than 50. Junio identified a 255 deep chain a week or two ago.\nSome people have repacked their repositories very aggressively with\ndeeper chains when they are trying to optimize for space and don't\naccess historical revisions very often. I doubt anyone has packed\ndeeper than 120ish intentionally... but we shouldn't assume that in\nthe code.\n\n>>  This in turn\n>> imply that there should be a common limit that is supported by all git\n>> clients and is a documented part of the protocol.  (Or the code has to\n>> be rewritten to use an explicit stack instead of recursion.)\n>\n> It's the implementation limitation, not the protocol. If the server\n> propagates error messages from index-pack back to client (I'm not\n> sure), then users can adjust --depth to be accepted by server. We\n> could negotiate the limit over the protocol but not sure we would want\n> to go that route.\n\nWhat about clients fetching from a server? The client can't change the\ndepth the server sends it.\n\n> The troubled code could be rewritten to avoid recursion. However long\n> delta chains may degrade performance, I'd rather have support to split\n> long chains (which can be done with --depth at client already) instead\n> of just recursion elimination. This patch is simpler, so it would be\n> easier to back port it if someone wants to do so.\n\nJGit long ago changed its IndexPack routine to use a manually managed\nheap based stack instead of recursion, making it immune from\noverrunning the stack due to a long delta chain. That is probably the\ncleaner route. But you also have to fix sha1_file.c and its recursion\nbased unpacking of a delta chain... again which JGit fixed a long time\nago.\n"},{"id":"180394","messageId":"20111206185636.GC9492@sigill.intra.peff.net","threadId":"29086","inReplyTo":"CAJo=hJuy27Uagmubbv=RqAOMx03e6JBgZxObkjFLg9oG2x_UqA@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-06T18:56:36Z","receivedAt":"2011-12-06T18:56:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 06, 2011 at 10:12:54AM -0800, Shawn O. Pearce wrote:\n\n> > Normal creators (i.e. C Git) use default depth 50 so we should be safe.\n> \n> JGit is also a \"normal creator\", and it sometimes produces chains\n> deeper than 50. Junio identified a 255 deep chain a week or two ago.\n> Some people have repacked their repositories very aggressively with\n> deeper chains when they are trying to optimize for space and don't\n> access historical revisions very often. I doubt anyone has packed\n> deeper than 120ish intentionally... but we shouldn't assume that in\n> the code.\n\n\"git gc --aggressive\" will set the depth to 250.\n\n-Peff\n"},{"id":"180500","messageId":"1323280223-7990-1-git-send-email-pclouds@gmail.com","threadId":"29086","inReplyTo":"7vvcpthh97.fsf@alter.siamese.dyndns.org","subject":"[PATCH] index-pack: eliminate unlimited recursion in get_delta_base()","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-07T17:50:23Z","receivedAt":"2011-12-07T17:50:23Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Revert the order of delta applying so that by the time a delta is\napplied, its base is either non-delta or already inflated.\nget_delta_base() is still recursive, but because base's data is always\nready, the inner get_delta_base() call never has any chance to call\nitself again.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/index-pack.c | 30 +++++++++++++++++++++---------\n 1 files changed, 21 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 0945adb..103e19c 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -508,10 +508,25 @@ static void *get_base_data(struct base_data *c)\n {\n \tif (!c->data) {\n \t\tstruct object_entry *obj = c->obj;\n+\t\tstruct base_data **delta = NULL;\n+\t\tint delta_nr = 0, delta_alloc = 0;\n \n-\t\tif (is_delta_type(obj->type)) {\n-\t\t\tvoid *base = get_base_data(c->base);\n-\t\t\tvoid *raw = get_data_from_pack(obj);\n+\t\tfor (; is_delta_type(c->obj->type); c = c->base) {\n+\t\t\tALLOC_GROW(delta, delta_nr + 1, delta_alloc);\n+\t\t\tdelta[delta_nr++] = c;\n+\t\t}\n+\t\tif (!delta_nr) {\n+\t\t\tc->data = get_data_from_pack(obj);\n+\t\t\tc->size = obj->size;\n+\t\t\tbase_cache_used += c->size;\n+\t\t\tprune_base_data(c);\n+\t\t}\n+\t\tfor (; delta_nr > 0; delta_nr--) {\n+\t\t\tvoid *base, *raw;\n+\t\t\tc = delta[delta_nr - 1];\n+\t\t\tobj = c->obj;\n+\t\t\tbase = get_base_data(c->base);\n+\t\t\traw = get_data_from_pack(obj);\n \t\t\tc->data = patch_delta(\n \t\t\t\tbase, c->base->size,\n \t\t\t\traw, obj->size,\n@@ -519,13 +534,10 @@ static void *get_base_data(struct base_data *c)\n \t\t\tfree(raw);\n \t\t\tif (!c->data)\n \t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n-\t\t} else {\n-\t\t\tc->data = get_data_from_pack(obj);\n-\t\t\tc->size = obj->size;\n+\t\t\tbase_cache_used += c->size;\n+\t\t\tprune_base_data(c);\n \t\t}\n-\n-\t\tbase_cache_used += c->size;\n-\t\tprune_base_data(c);\n+\t\tfree(delta);\n \t}\n \treturn c->data;\n }\n-- \n1.7.8.36.g69ee2\n"},{"id":"180551","messageId":"CAJo=hJvrk3Jzg3dQhQnfbmKAFovLuEtJAP4rakHPFeuZ0T5R7g@mail.gmail.com","threadId":"29086","inReplyTo":"1323280223-7990-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] index-pack: eliminate unlimited recursion in get_delta_base()","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-12-08T03:02:29Z","receivedAt":"2011-12-08T03:02:29Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"2011/12/7 Nguyễn Thái Ngọc Duy :\n> Revert the order of delta applying so that by the time a delta is\n> applied, its base is either non-delta or already inflated.\n> get_delta_base() is still recursive, but because base's data is always\n> ready, the inner get_delta_base() call never has any chance to call\n> itself again.\n...\n> @@ -508,10 +508,25 @@ static void *get_base_data(struct base_data *c)\n>  {\n>        if (!c->data) {\n>                struct object_entry *obj = c->obj;\n> +               struct base_data **delta = NULL;\n> +               int delta_nr = 0, delta_alloc = 0;\n>\n> -               if (is_delta_type(obj->type)) {\n> -                       void *base = get_base_data(c->base);\n> -                       void *raw = get_data_from_pack(obj);\n\nI think you missed the critical recursion. The real work is the\nrecursion within find_unresolved_deltas(). This little helper\nget_base_data() shouldn't be tripping over these cases unless we have\nrun out of delta_base_cache_limit and released objects near the base\nend of the delta chain, in which case this will restore them.\n\nMaybe this is useful on its own, but in my opinion its not an\ninteresting patch to consider without first fixing\nfind_unresolved_deltas's recursion.\n"},{"id":"180570","messageId":"CACsJy8Dr14ek-Fv4a4eAo_QRHyHrg=2X=YaMRy1z8UXRdcescg@mail.gmail.com","threadId":"29086","inReplyTo":"CAJo=hJvrk3Jzg3dQhQnfbmKAFovLuEtJAP4rakHPFeuZ0T5R7g@mail.gmail.com","subject":"Re: [PATCH] index-pack: eliminate unlimited recursion in get_delta_base()","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-08T11:06:27Z","receivedAt":"2011-12-08T11:06:27Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"2011/12/8 Shawn Pearce :\n> I think you missed the critical recursion. The real work is the\n> recursion within find_unresolved_deltas(). This little helper\n> get_base_data() shouldn't be tripping over these cases unless we have\n> run out of delta_base_cache_limit and released objects near the base\n> end of the delta chain, in which case this will restore them.\n>\n> Maybe this is useful on its own, but in my opinion its not an\n> interesting patch to consider without first fixing\n> find_unresolved_deltas's recursion.\n\nThanks. I missed that function. Will try to fix it.\n-- \nDuy\n"},{"id":"180586","messageId":"4ee0be67.05c1e70a.1956.ffff800b@mx.google.com","threadId":"29086","inReplyTo":"CAJo=hJvrk3Jzg3dQhQnfbmKAFovLuEtJAP4rakHPFeuZ0T5R7g@mail.gmail.com","subject":"[PATCH 1/2] index_pack: indent find_unresolved_detals one level","fromName":"","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-08T13:40:37Z","receivedAt":"2011-12-08T13:40:37Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"From: Nguyễn Thái Ngọc Duy \n\nThe next patch puts most of the code in one level deeper. By indenting\nseparately, it'd be easier to see the actual changes.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/index-pack.c | 47 +++++++++++++++++++++++------------------------\n 1 files changed, 23 insertions(+), 24 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 103e19c..9855ada 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -585,37 +585,36 @@ static void find_unresolved_deltas(struct base_data *base,\n \t\tbase_spec.offset = base->obj->idx.offset;\n \t\tfind_delta_children(&base_spec,\n \t\t\t\t &ofs_first, &ofs_last, OBJ_OFS_DELTA);\n-\t}\n \n-\tif (ref_last == -1 && ofs_last == -1) {\n-\t\tfree(base->data);\n-\t\treturn;\n-\t}\n+\t\tif (ref_last == -1 && ofs_last == -1) {\n+\t\t\tfree(base->data);\n+\t\t\treturn;\n+\t\t}\n \n-\tlink_base_data(prev_base, base);\n+\t\tlink_base_data(prev_base, base);\n \n-\tfor (i = ref_first; i <= ref_last; i++) {\n-\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\tstruct base_data result;\n+\t\tfor (i = ref_first; i <= ref_last; i++) {\n+\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\t\tstruct base_data result;\n \n-\t\tassert(child->real_type == OBJ_REF_DELTA);\n-\t\tresolve_delta(child, base, &result);\n-\t\tif (i == ref_last && ofs_last == -1)\n-\t\t\tfree_base_data(base);\n-\t\tfind_unresolved_deltas(&result, base);\n-\t}\n+\t\t\tassert(child->real_type == OBJ_REF_DELTA);\n+\t\t\tresolve_delta(child, base, &result);\n+\t\t\tif (i == ref_last && ofs_last == -1)\n+\t\t\t\tfree_base_data(base);\n+\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t}\n \n-\tfor (i = ofs_first; i <= ofs_last; i++) {\n-\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\tstruct base_data result;\n+\t\tfor (i = ofs_first; i <= ofs_last; i++) {\n+\t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n+\t\t\tstruct base_data result;\n \n-\t\tassert(child->real_type == OBJ_OFS_DELTA);\n-\t\tresolve_delta(child, base, &result);\n-\t\tif (i == ofs_last)\n-\t\t\tfree_base_data(base);\n-\t\tfind_unresolved_deltas(&result, base);\n+\t\t\tassert(child->real_type == OBJ_OFS_DELTA);\n+\t\t\tresolve_delta(child, base, &result);\n+\t\t\tif (i == ofs_last)\n+\t\t\t\tfree_base_data(base);\n+\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t}\n \t}\n-\n \tunlink_base_data(base);\n }\n \n-- \n1.7.8.36.g69ee2\n"},{"id":"180587","messageId":"4ee0be70.44f2320a.3fe8.632b@mx.google.com","threadId":"29086","inReplyTo":"1323351638-4790-1-git-send-email-y","subject":"[PATCH 2/2] index-pack: a naive attempt to flatten find_unresolved_deltas","fromName":"","fromEmail":"pclouds@gmail.com","sentAt":"2011-12-08T13:40:38Z","receivedAt":"2011-12-08T13:40:38Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"From: Nguyễn Thái Ngọc Duy \n\nThis seems to work for me. But I think this approach uses (much?) more\nmemory because it turns a tree of calls into a flat list of calls and\nkeep the list until the end, while the recursive version only has to\nkeep one call chain at a time.\n\nAny ideas how to improve it?\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/index-pack.c | 57 +++++++++++++++++++++++++++++++++++++------------\n 1 files changed, 43 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 9855ada..d4c182f 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -565,18 +565,31 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tnr_resolved_deltas++;\n }\n \n+struct fud_stack {\n+\tstruct base_data base_;\n+\tstruct base_data *base;\n+\tstruct base_data *prev_base;\n+};\n+\n static void find_unresolved_deltas(struct base_data *base,\n \t\t\t\t struct base_data *prev_base)\n {\n+\tstruct fud_stack **stack = NULL;\n+\tint stk, stack_nr = 0, stack_alloc = 0;\n \tint i, ref_first, ref_last, ofs_first, ofs_last;\n \n-\t/*\n-\t * This is a recursive function. Those brackets should help reducing\n-\t * stack usage by limiting the scope of the delta_base union.\n-\t */\n-\t{\n+\tALLOC_GROW(stack, stack_nr + 1, stack_alloc);\n+\tstack[stack_nr] = xmalloc(sizeof(struct fud_stack));\n+\tstack[stack_nr]->base = base;\n+\tstack[stack_nr]->prev_base = prev_base;\n+\tstack_nr++;\n+\n+\tfor (stk = 0; stk < stack_nr; stk++) {\n \t\tunion delta_base base_spec;\n \n+\t\tbase = stack[stk]->base;\n+\t\tprev_base = stack[stk]->prev_base;\n+\n \t\thashcpy(base_spec.sha1, base->obj->idx.sha1);\n \t\tfind_delta_children(&base_spec,\n \t\t\t\t &ref_first, &ref_last, OBJ_REF_DELTA);\n@@ -588,34 +601,50 @@ static void find_unresolved_deltas(struct base_data *base,\n \n \t\tif (ref_last == -1 && ofs_last == -1) {\n \t\t\tfree(base->data);\n-\t\t\treturn;\n+\t\t\tfree(stack[stk]);\n+\t\t\tstack[stk] = NULL;\n+\t\t\tcontinue;\n \t\t}\n \n \t\tlink_base_data(prev_base, base);\n \n+\t\tALLOC_GROW(stack, stack_nr +\n+\t\t\t (ref_last - ref_first + 1) +\n+\t\t\t (ofs_last - ofs_first + 1),\n+\t\t\t stack_alloc);\n+\n \t\tfor (i = ref_first; i <= ref_last; i++) {\n \t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\t\tstruct base_data result;\n \n \t\t\tassert(child->real_type == OBJ_REF_DELTA);\n-\t\t\tresolve_delta(child, base, &result);\n+\t\t\tstack[stack_nr] = xmalloc(sizeof(struct fud_stack));\n+\t\t\tstack[stack_nr]->base = &stack[stack_nr]->base_;\n+\t\t\tresolve_delta(child, base, stack[stack_nr]->base);\n \t\t\tif (i == ref_last && ofs_last == -1)\n \t\t\t\tfree_base_data(base);\n-\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t\tstack[stack_nr]->prev_base = base;\n+\t\t\tstack_nr++;\n \t\t}\n \n \t\tfor (i = ofs_first; i <= ofs_last; i++) {\n \t\t\tstruct object_entry *child = objects + deltas[i].obj_no;\n-\t\t\tstruct base_data result;\n-\n \t\t\tassert(child->real_type == OBJ_OFS_DELTA);\n-\t\t\tresolve_delta(child, base, &result);\n+\t\t\tstack[stack_nr] = xmalloc(sizeof(struct fud_stack));\n+\t\t\tstack[stack_nr]->base = &stack[stack_nr]->base_;\n+\t\t\tresolve_delta(child, base, stack[stack_nr]->base);\n \t\t\tif (i == ofs_last)\n \t\t\t\tfree_base_data(base);\n-\t\t\tfind_unresolved_deltas(&result, base);\n+\t\t\tstack[stack_nr]->prev_base = base;\n+\t\t\tstack_nr++;\n \t\t}\n \t}\n-\tunlink_base_data(base);\n+\n+\tfor (stk = stack_nr - 1; stk >= 0; stk--)\n+\t\tif (stack[stk]) {\n+\t\t\tunlink_base_data(stack[stk]->base);\n+\t\t\tfree(stack[stk]);\n+\t\t}\n+\tfree(stack);\n }\n \n static int compare_delta_entry(const void *a, const void *b)\n-- \n1.7.8.36.g69ee2\n"},{"id":"180593","messageId":"CAJo=hJu35cYkWfBXAoL6OoCLVT4fE-mKjgqyGBN5xRLmiBeRdw@mail.gmail.com","threadId":"29086","inReplyTo":"4ee0be70.44f2320a.3fe8.632b@mx.google.com","subject":"Re: [PATCH 2/2] index-pack: a naive attempt to flatten find_unresolved_deltas","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-12-08T16:42:24Z","receivedAt":"2011-12-08T16:42:24Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"2011/12/8 :\n> From: Nguyễn Thái Ngọc Duy \n>\n> This seems to work for me. But I think this approach uses (much?) more\n> memory because it turns a tree of calls into a flat list of calls and\n> keep the list until the end, while the recursive version only has to\n> keep one call chain at a time.\n>\n> Any ideas how to improve it?\n\nWell, fortunately JGit is under a very liberal BSD license and has a\npretty efficient version of a heap based algorithm for delta\nresolution. You could look at [1] for ideas. I am told the BSD license\nis very compatible with the GPLv2. (Unlike the reverse.)\n\n\n[1] http://egit.eclipse.org/w/?p=jgit.git;a=blob;f=org.eclipse.jgit/src/org/eclipse/jgit/transport/PackParser.java;hb=HEAD#l556\n"},{"id":"180718","messageId":"7vpqfxcu6z.fsf@alter.siamese.dyndns.org","threadId":"29086","inReplyTo":"4ee0be67.05c1e70a.1956.ffff800b@mx.google.com","subject":"Re: [PATCH 1/2] index_pack: indent find_unresolved_detals one level","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-12-09T21:27:00Z","receivedAt":"2011-12-09T21:27:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"pclouds@gmail.com writes:\n\n> From: Nguyễn Thái Ngọc Duy \n>\n> The next patch puts most of the code in one level deeper. By indenting\n> separately, it'd be easier to see the actual changes.\n\nYuck.\n\nIsn't it a sign that \"the next patch\" should perhaps be helped by a small\nhelper function that does whatever the part you are indenting here?\n"},{"id":"180734","messageId":"7vsjktb8fo.fsf@alter.siamese.dyndns.org","threadId":"29086","inReplyTo":"CACsJy8AZg3DgZzmPyXhCH9bGBqo9UN7-zLt_feTtpyajf5U1tw@mail.gmail.com","subject":"Re: [PATCH] Set hard limit on delta chain depth","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-12-10T00:02:19Z","receivedAt":"2011-12-10T00:02:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> That's interesting. First of all xmalloc() is controlled by us while\n> index-pack code might lead to stack overflow exploit (never done it,\n> not sure if it's really pratical to do in this case).\n\nWhat do you exactly mean by \"stack overflow exploit\"?\n\nIf your callee has prepares a stackframe that is not sufficiently big but\ncarelessly tries to store more than it has space for, such a write can\noverflow the stack (without hardware traps) and overwrite return address,\nand instead of coming back to you, the control can be transferred to\nrandom places.\n\nBut I do not think that is what we are talking about here.\n\nYou attempt to write parameters and return address to the area of memory\npointed by your stack pointer, advance the stack pointer to create a stack\nframe and the callee attempts to write to its local variables in the newly\nallocated stack frame. These memory accesses eventually attempt to touch\nmemory beyond the address range the kernel gave you page table entries to\nbe used as your stack space, and hardware traps. If you haven't run out of\nthe stack, a new page is lazily added to the page table and your attempted\naccess will succeed. If you are recursing too deeply, you won't be given a\nnew page and you will be killed by the kernel. That is a rather controlled\ndeath of the process, unlike smashing the contents of the stack to jump to\na randomly chosen place, isn't it?\n\nOf course, some platforms do not have an unwritable gap between the stack\nsegment that grow downwards and the heap that grow upwards, and also your\nstackframe could be larger than such a gap (in this particular callchain I\ndo not think that is the case), so the above discussion does not apply\nuniversally, though.\n"}]}