{"thread":{"id":"44597","subject":"[PATCH 2/4] shallow.c: avoid theoretical pointer wrap-around","startedAt":"2016-12-02T20:31:38Z","lastAt":"2016-12-07T23:43:32Z","messageCount":20,"participants":["Rasmus Villemoes","Jeff King","Duy Nguyen","Nguyễn Thái Ngọc Duy","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"306810","messageId":"1480710664-26290-2-git-send-email-rv@rasmusvillemoes.dk","threadId":"44597","inReplyTo":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","subject":"[PATCH 2/4] shallow.c: avoid theoretical pointer wrap-around","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2016-12-02T20:31:02Z","receivedAt":"2016-12-02T20:31:38Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"The expression info->free+size is technically undefined behaviour in\nexactly the case we want to test for. Moreover, the compiler is likely\nto translate the expression to\n\n (unsigned long)info->free + size > (unsigned long)info->end\n\nwhere there's at least a theoretical chance that the LHS could wrap\naround 0, giving a false negative.\n\nThis might as well be written using pointer subtraction avoiding these\nissues.\n\nSigned-off-by: Rasmus Villemoes \n---\n shallow.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex e21534a..8b1c35d 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -444,7 +444,7 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tunsigned nr = (info->nr_bits + 31) / 32;\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n-\tif (!info->slab_count || info->free + size > info->end) {\n+\tif (!info->slab_count || size > info->end - info->free) {\n \t\tunsigned alloc_size = size < COMMIT_SLAB_SIZE ?\n \t\t\tCOMMIT_SLAB_SIZE : size;\n \t\tinfo->slab_count++;\n-- \n2.1.4\n\n"},{"id":"306811","messageId":"1480710664-26290-3-git-send-email-rv@rasmusvillemoes.dk","threadId":"44597","inReplyTo":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","subject":"[PATCH 3/4] shallow.c: bit manipulation tweaks","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2016-12-02T20:31:03Z","receivedAt":"2016-12-02T20:31:49Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"First of all, 1 << 31 is technically undefined behaviour, so let's just\nuse an unsigned literal.\n\nIf i is 'signed int' and gcc doesn't know that i is positive, gcc\ngenerates code to compute the C99-mandated values of \"i / 32\" and \"i %\n32\", which is a lot more complicated than simple a simple shifts/mask.\n\nThe only caller of paint_down actually passes an \"unsigned int\" value,\nbut the prototype of paint_down causes (completely well-defined)\nconversion to signed int, and gcc has no way of knowing that the\nconverted value is non-negative. Just make the id parameter unsigned.\n\nIn update_refstatus, the change in generated code is much smaller,\npresumably because gcc is smart enough to see that i starts as 0 and is\nonly incremented, so it is allowed (per the UD of signed overflow) to\nassume that i is always non-negative. But let's just help less smart\ncompilers generate good code anyway.\n\nSigned-off-by: Rasmus Villemoes \n---\n shallow.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 8b1c35d..5aec5a5 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -464,7 +464,7 @@ static uint32_t *paint_alloc(struct paint_info *info)\n * all walked commits.\n */\n static void paint_down(struct paint_info *info, const unsigned char *sha1,\n-\t\t int id)\n+\t\t unsigned int id)\n {\n \tunsigned int i, nr;\n \tstruct commit_list *head = NULL;\n@@ -476,7 +476,7 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1,\n \tif (!c)\n \t\treturn;\n \tmemset(bitmap, 0, bitmap_size);\n-\tbitmap[id / 32] |= (1 << (id % 32));\n+\tbitmap[id / 32] |= (1U << (id % 32));\n \tcommit_list_insert(c, &head);\n \twhile (head) {\n \t\tstruct commit_list *p;\n@@ -650,11 +650,11 @@ static int add_ref(const char *refname, const struct object_id *oid,\n \n static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)\n {\n-\tint i;\n+\tunsigned int i;\n \tif (!ref_status)\n \t\treturn;\n \tfor (i = 0; i < nr; i++)\n-\t\tif (bitmap[i / 32] & (1 << (i % 32)))\n+\t\tif (bitmap[i / 32] & (1U << (i % 32)))\n \t\t\tref_status[i]++;\n }\n \n-- \n2.1.4\n\n"},{"id":"306812","messageId":"1480710664-26290-4-git-send-email-rv@rasmusvillemoes.dk","threadId":"44597","inReplyTo":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","subject":"[PATCH 4/4] shallow.c: remove useless test","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2016-12-02T20:31:04Z","receivedAt":"2016-12-02T20:31:52Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"It seems to be odd to do x=y if x==y. Maybe there's a bug somewhere near\nthis, but as is this is somewhat confusing.\n\nSigned-off-by: Rasmus Villemoes \n---\n shallow.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 5aec5a5..7c28239 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -513,7 +513,7 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1,\n \t\t\t\t\t\t\t p->item);\n \t\t\tif (p->item->object.flags & SEEN)\n \t\t\t\tcontinue;\n-\t\t\tif (*p_refs == NULL || *p_refs == *refs)\n+\t\t\tif (*p_refs == NULL)\n \t\t\t\t*p_refs = *refs;\n \t\t\tcommit_list_insert(p->item, &head);\n \t\t}\n-- \n2.1.4\n\n"},{"id":"306813","messageId":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","threadId":"44597","inReplyTo":null,"subject":"[PATCH 1/4] shallow.c: make paint_alloc slightly more robust","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2016-12-02T20:31:01Z","receivedAt":"2016-12-02T20:31:53Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"I have no idea if this is a real issue, but it's not obvious to me that\npaint_alloc cannot be called with info->nr_bits greater than about\n4M (\\approx 8*COMMIT_SLAB_SIZE). In that case the new slab would be too\nsmall. So just round up the allocation to the maximum of\nCOMMIT_SLAB_SIZE and size.\n\nSigned-off-by: Rasmus Villemoes \n---\n shallow.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 4d0b005..e21534a 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -445,11 +445,13 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n \tif (!info->slab_count || info->free + size > info->end) {\n+\t\tunsigned alloc_size = size < COMMIT_SLAB_SIZE ?\n+\t\t\tCOMMIT_SLAB_SIZE : size;\n \t\tinfo->slab_count++;\n \t\tREALLOC_ARRAY(info->slab, info->slab_count);\n-\t\tinfo->free = xmalloc(COMMIT_SLAB_SIZE);\n+\t\tinfo->free = xmalloc(alloc_size);\n \t\tinfo->slab[info->slab_count - 1] = info->free;\n-\t\tinfo->end = info->free + COMMIT_SLAB_SIZE;\n+\t\tinfo->end = info->free + alloc_size;\n \t}\n \tp = info->free;\n \tinfo->free += size;\n-- \n2.1.4\n\n"},{"id":"306857","messageId":"20161203051454.vp772xtto5ddxe7g@sigill.intra.peff.net","threadId":"44597","inReplyTo":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","subject":"Re: [PATCH 1/4] shallow.c: make paint_alloc slightly more robust","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-03T05:14:54Z","receivedAt":"2016-12-03T05:16:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2016 at 09:31:01PM +0100, Rasmus Villemoes wrote:\n\n> I have no idea if this is a real issue, but it's not obvious to me that\n> paint_alloc cannot be called with info->nr_bits greater than about\n> 4M (\\approx 8*COMMIT_SLAB_SIZE). In that case the new slab would be too\n> small. So just round up the allocation to the maximum of\n> COMMIT_SLAB_SIZE and size.\n\nI had trouble understanding what the problem is from this description,\nbut I think i figured it out from the code.\n\nLet me try to restate it to make sure I understand.\n\nThe paint_alloc() may be asked to allocate a certain number of bits,\nwhich it does across a series of independently allocated slabs. Each\nslab holds a fixed size, but we only allocate a single slab. If the\nnumber we need to allocate is larger than fits in a single slab, then at\nthe end we'll have under-allocated.\n\nYour solution is to make the slab we allocate bigger. But that seems\nodd to me. Usually when we are using COMMIT_SLAB_SIZE, we are allocating\na series of slabs that make up a virtual array, and we know that each\nslab has the same size. So if you need to find the k-th item, and each\nslab has length n, then you'd look at slab (k / n), and then at item (k\n% n) within that slab.\n\nIn other words, I think the solution isn't to make the one slab bigger,\nbut to allocate slabs until we have enough of them to meet the request.\n\nBut I don't really know how this code is used, or why it is using\nCOMMIT_SLAB_SIZE in the first place. That's generally supposed to be an\ninternal detail of the commit-slab.h infrastructure. Why is it being\nused directly, instead of just using the functions that commit-slab\ndefines?\n\n-Peff\n"},{"id":"306858","messageId":"20161203051720.z5elgoaapulqxlw5@sigill.intra.peff.net","threadId":"44597","inReplyTo":"1480710664-26290-2-git-send-email-rv@rasmusvillemoes.dk","subject":"Re: [PATCH 2/4] shallow.c: avoid theoretical pointer wrap-around","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-03T05:17:21Z","receivedAt":"2016-12-03T05:17:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2016 at 09:31:02PM +0100, Rasmus Villemoes wrote:\n\n> The expression info->free+size is technically undefined behaviour in\n> exactly the case we want to test for. Moreover, the compiler is likely\n> to translate the expression to\n> \n> (unsigned long)info->free + size > (unsigned long)info->end\n> \n> where there's at least a theoretical chance that the LHS could wrap\n> around 0, giving a false negative.\n> \n> This might as well be written using pointer subtraction avoiding these\n> issues.\n> [...]\n>\n> -\tif (!info->slab_count || info->free + size > info->end) {\n> +\tif (!info->slab_count || size > info->end - info->free) {\n\nYeah, I agree the correct way to write this is to compare the sizes\ndirectly. That is how overflow checks _must_ be written. This one is\nless likely to overflow, but even computing the value more than one past\nthe end of the array is technically undefined.\n\n-Peff\n"},{"id":"306859","messageId":"20161203052104.jbxhzpweupiaz7wi@sigill.intra.peff.net","threadId":"44597","inReplyTo":"1480710664-26290-3-git-send-email-rv@rasmusvillemoes.dk","subject":"Re: [PATCH 3/4] shallow.c: bit manipulation tweaks","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-03T05:21:04Z","receivedAt":"2016-12-03T05:21:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2016 at 09:31:03PM +0100, Rasmus Villemoes wrote:\n\n> First of all, 1 << 31 is technically undefined behaviour, so let's just\n> use an unsigned literal.\n\nIt took me a second to realize that you weren't talking about the\nunsigned parameter here. You mean using \"1U\". It might be worth saying:\n\n ...use an unsigned literal, \"1U\".\n\nto make it more obvious.\n\n> If i is 'signed int' and gcc doesn't know that i is positive, gcc\n> generates code to compute the C99-mandated values of \"i / 32\" and \"i %\n> 32\", which is a lot more complicated than simple a simple shifts/mask.\n\nRight, that makes sense (though it is a separate issue).\n\n-Peff\n"},{"id":"306860","messageId":"20161203052422.hhaj3idboo6r6dz5@sigill.intra.peff.net","threadId":"44597","inReplyTo":"1480710664-26290-4-git-send-email-rv@rasmusvillemoes.dk","subject":"Re: [PATCH 4/4] shallow.c: remove useless test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-03T05:24:22Z","receivedAt":"2016-12-03T05:25:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 02, 2016 at 09:31:04PM +0100, Rasmus Villemoes wrote:\n\n> It seems to be odd to do x=y if x==y. Maybe there's a bug somewhere near\n> this, but as is this is somewhat confusing.\n\nYeah, this code is definitely wrong, but I'm not sure what it's trying\nto do. This is the first time I've looked at it.\n\n-Peff\n"},{"id":"306923","messageId":"CACsJy8CMd3bnLFuJhkC7u3JO5dLOq6tOwLJXLsJmHgwXi+2FQw@mail.gmail.com","threadId":"44597","inReplyTo":"20161203051454.vp772xtto5ddxe7g@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] shallow.c: make paint_alloc slightly more robust","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-05T10:02:52Z","receivedAt":"2016-12-05T10:04:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 3, 2016 at 12:14 PM, Jeff King wrote:\n> On Fri, Dec 02, 2016 at 09:31:01PM +0100, Rasmus Villemoes wrote:\n>\n>> I have no idea if this is a real issue, but it's not obvious to me that\n>> paint_alloc cannot be called with info->nr_bits greater than about\n>> 4M (\\approx 8*COMMIT_SLAB_SIZE). In that case the new slab would be too\n>> small. So just round up the allocation to the maximum of\n>> COMMIT_SLAB_SIZE and size.\n>\n> I had trouble understanding what the problem is from this description,\n> but I think i figured it out from the code.\n>\n> Let me try to restate it to make sure I understand.\n>\n> The paint_alloc() may be asked to allocate a certain number of bits,\n> which it does across a series of independently allocated slabs. Each\n> slab holds a fixed size, but we only allocate a single slab. If the\n> number we need to allocate is larger than fits in a single slab, then at\n> the end we'll have under-allocated.\n\nEach bit here represents a ref. This code walks the commit graph and\n\"paints\" all commits reachable by the n-th ref with the n-th bit,\nstored in the commit slab. But because the majority of commits will\nhave the same bitmap (e.g. when you exclude tag ABC and nothing else,\nthen all commits from ABC will have the same bitmap \"1\"), it's a waste\nto allocate the same bitmap per commit (and it's also inefficient to\nlet malloc allocate 1 bit). I tried to reduce the memory usage: if the\na commit and its parent has the same bitmap, and the slab pointer of\nthe child commit points to the memory of the parent's, no extra\nallocation is done. This manual memory management is pretty much like\nalloc.c\n\nThe COMMIT_SLAB_SIZE here is really an arbitrary big number so that we\ndon't have to allocate often. It's basically allocating a new memory\npool. When we use all of that pool, we allocate a new one.. Yeah I\nprobably should define a new one instead of reusing COMMIT_SLAB_SIZE.\nTthe chances of under-allocation is super low, but still possible: you\nneed to send more than 4M \"exclude\" (or \"shallow\") requests to\nupload-pack, to create a bitmap of over 512KiB. That's a lot of\ntraffic in git protocol.\n\n> Your solution is to make the slab we allocate bigger. But that seems\n> odd to me. Usually when we are using COMMIT_SLAB_SIZE, we are allocating\n> a series of slabs that make up a virtual array, and we know that each\n> slab has the same size. So if you need to find the k-th item, and each\n> slab has length n, then you'd look at slab (k / n), and then at item (k\n> % n) within that slab.\n>\n> In other words, I think the solution isn't to make the one slab bigger,\n> but to allocate slabs until we have enough of them to meet the request.\n\nIf I still understand my code (it's been a long time since I wrote\nthis thing), then I think we just need to catch the problem and die().\nNormal users should never ask the server to allocate this much.\n-- \nDuy\n"},{"id":"306930","messageId":"CACsJy8DSw_EXojKYXvkkqkbd3fsQJ=hhAb0GCfMYRzK2S3d-3Q@mail.gmail.com","threadId":"44597","inReplyTo":"20161203052422.hhaj3idboo6r6dz5@sigill.intra.peff.net","subject":"Re: [PATCH 4/4] shallow.c: remove useless test","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-05T12:00:14Z","receivedAt":"2016-12-05T12:02:38Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Dec 3, 2016 at 12:24 PM, Jeff King wrote:\n> On Fri, Dec 02, 2016 at 09:31:04PM +0100, Rasmus Villemoes wrote:\n>\n>> It seems to be odd to do x=y if x==y. Maybe there's a bug somewhere near\n>> this, but as is this is somewhat confusing.\n>\n> Yeah, this code is definitely wrong, but I'm not sure what it's trying\n> to do. This is the first time I've looked at it.\n\nI'm sorry I don't know why it's there either :( The first version that\nhas this was v3 [1] which still uses \"util\" pointdf instead of the\ncommit slab but the logic does not differ much.\n\nThis is the place when we \"paint\" the parent commit with the same\nbitmap as the child I mentioned earlier (though I think I mentioned it\nbackward). You see similar code in the same loop just a bit earlier:\nif the commit has not been painted, it gets a new bitmap, otherwise\nnew refs are OR'd to its bitmap. It's the OR part (when the bitmaps\npointed by *p_refs and *refs differ, it's not just about pointer\ncomparison) that's probably missing here.\n\nBut it looks like we can safely delete the \" || *p_refs == *refs\" part\nbecause the commit in question is inserted back to the commit list\n\"head\" and revisited in the next iteration. If its bitmap is different\nfrom the child's, then in the next iteration it should hit the \"if\n(memcmp(tmp, *refs, bitmap_size))\" line above, in the same loop, then\nthe new bit will be added. If it's marked UNINTERESTING though, that\nwon't happen. I'll need more time to stare at this code...\n\n[1] http://public-inbox.org/git/1385351754-9954-9-git-send-email-pclouds@gmail.com/\n-- \nDuy\n"},{"id":"306994","messageId":"20161206125339.16803-2-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 1/6] shallow.c: rename fields in paint_info to better express their purposes","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:34Z","receivedAt":"2016-12-06T12:55:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"paint_alloc() is basically malloc(), tuned for allocating a fixed number\nof bits on every call without worrying about freeing any individual\nallocation since all will be freed at the end. It does it by allocating\na big block of memory every time it runs out of \"free memory\". \"slab\" is\na poor choice of name, at least poorer than \"pool\".\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 18 +++++++++---------\n 1 file changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 4d0b005..8100dfd 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -434,9 +434,9 @@ define_commit_slab(ref_bitmap, uint32_t *);\n struct paint_info {\n \tstruct ref_bitmap ref_bitmap;\n \tunsigned nr_bits;\n-\tchar **slab;\n+\tchar **pools;\n \tchar *free, *end;\n-\tunsigned slab_count;\n+\tunsigned pool_count;\n };\n \n static uint32_t *paint_alloc(struct paint_info *info)\n@@ -444,11 +444,11 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tunsigned nr = (info->nr_bits + 31) / 32;\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n-\tif (!info->slab_count || info->free + size > info->end) {\n-\t\tinfo->slab_count++;\n-\t\tREALLOC_ARRAY(info->slab, info->slab_count);\n+\tif (!info->pool_count || info->free + size > info->end) {\n+\t\tinfo->pool_count++;\n+\t\tREALLOC_ARRAY(info->pools, info->pool_count);\n \t\tinfo->free = xmalloc(COMMIT_SLAB_SIZE);\n-\t\tinfo->slab[info->slab_count - 1] = info->free;\n+\t\tinfo->pools[info->pool_count - 1] = info->free;\n \t\tinfo->end = info->free + COMMIT_SLAB_SIZE;\n \t}\n \tp = info->free;\n@@ -624,9 +624,9 @@ void assign_shallow_commits_to_refs(struct shallow_info *info,\n \t\tpost_assign_shallow(info, &pi.ref_bitmap, ref_status);\n \n \tclear_ref_bitmap(&pi.ref_bitmap);\n-\tfor (i = 0; i < pi.slab_count; i++)\n-\t\tfree(pi.slab[i]);\n-\tfree(pi.slab);\n+\tfor (i = 0; i < pi.pool_count; i++)\n+\t\tfree(pi.pools[i]);\n+\tfree(pi.pools);\n \tfree(shallow);\n }\n \n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306995","messageId":"20161206125339.16803-6-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 5/6] shallow.c: bit manipulation tweaks","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:38Z","receivedAt":"2016-12-06T12:55:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"From: Rasmus Villemoes \n\nFirst of all, 1 << 31 is technically undefined behaviour, so let's just\nuse an unsigned literal.\n\nIf i is 'signed int' and gcc doesn't know that i is positive, gcc\ngenerates code to compute the C99-mandated values of \"i / 32\" and \"i %\n32\", which is a lot more complicated than simple a simple shifts/mask.\n\nThe only caller of paint_down actually passes an \"unsigned int\" value,\nbut the prototype of paint_down causes (completely well-defined)\nconversion to signed int, and gcc has no way of knowing that the\nconverted value is non-negative. Just make the id parameter unsigned.\n\nIn update_refstatus, the change in generated code is much smaller,\npresumably because gcc is smart enough to see that i starts as 0 and is\nonly incremented, so it is allowed (per the UD of signed overflow) to\nassume that i is always non-negative. But let's just help less smart\ncompilers generate good code anyway.\n\nSigned-off-by: Rasmus Villemoes \nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 719f699..beb967e 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -467,7 +467,7 @@ static uint32_t *paint_alloc(struct paint_info *info)\n * all walked commits.\n */\n static void paint_down(struct paint_info *info, const unsigned char *sha1,\n-\t\t int id)\n+\t\t unsigned int id)\n {\n \tunsigned int i, nr;\n \tstruct commit_list *head = NULL;\n@@ -479,7 +479,7 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1,\n \tif (!c)\n \t\treturn;\n \tmemset(bitmap, 0, bitmap_size);\n-\tbitmap[id / 32] |= (1 << (id % 32));\n+\tbitmap[id / 32] |= (1U << (id % 32));\n \tcommit_list_insert(c, &head);\n \twhile (head) {\n \t\tstruct commit_list *p;\n@@ -653,11 +653,11 @@ static int add_ref(const char *refname, const struct object_id *oid,\n \n static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)\n {\n-\tint i;\n+\tunsigned int i;\n \tif (!ref_status)\n \t\treturn;\n \tfor (i = 0; i < nr; i++)\n-\t\tif (bitmap[i / 32] & (1 << (i % 32)))\n+\t\tif (bitmap[i / 32] & (1U << (i % 32)))\n \t\t\tref_status[i]++;\n }\n \n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306996","messageId":"20161206125339.16803-5-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 4/6] shallow.c: avoid theoretical pointer wrap-around","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:37Z","receivedAt":"2016-12-06T12:55:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"From: Rasmus Villemoes \n\nThe expression info->free+size is technically undefined behaviour in\nexactly the case we want to test for. Moreover, the compiler is likely\nto translate the expression to\n\n (unsigned long)info->free + size > (unsigned long)info->end\n\nwhere there's at least a theoretical chance that the LHS could wrap\naround 0, giving a false negative.\n\nThis might as well be written using pointer subtraction avoiding these\nissues.\n\nSigned-off-by: Rasmus Villemoes \nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 75e1702..719f699 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -446,7 +446,7 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tunsigned nr = (info->nr_bits + 31) / 32;\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n-\tif (!info->pool_count || info->free + size > info->end) {\n+\tif (!info->pool_count || size > info->end - info->free) {\n \t\tif (size > POOL_SIZE)\n \t\t\tdie(\"BUG: pool size too small for %d in paint_alloc()\",\n \t\t\t size);\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306997","messageId":"20161206125339.16803-7-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 6/6] shallow.c: remove useless code","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:39Z","receivedAt":"2016-12-06T12:55:11Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Some context before we talk about the removed code.\n\nThis paint_down() is part of step 6 of 58babff (shallow.c: the 8 steps\nto select new commits for .git/shallow - 2013-12-05). When we fetch from\na shallow repository, we need to know if one of the new/updated refs\nneeds new \"shallow commits\" in .git/shallow (because we don't have\nenough history of those refs) and which one.\n\nThe question at step 6 is, what (new) shallow commits are required in\nother to maintain reachability throughout the repository _without_\ncutting our history short? To answer, we mark all commits reachable from\nexisting refs with UNINTERESTING (\"rev-list --not --all\"), mark shallow\ncommits with BOTTOM, then for each new/updated refs, walk through the\ncommit graph until we either hit UNINTERESTING or BOTTOM, marking the\nref on the commit as we walk.\n\nAfter all the walking is done, we check the new shallow commits. If we\nhave not seen any new ref marked on a new shallow commit, we know all\nnew/updated refs are reachable using just our history and .git/shallow.\nThe shallow commit in question is not needed and can be thrown away.\n\nSo, the code.\n\nThe loop here (to walk through commits) is basically\n\n1. get one commit from the queue\n2. ignore if it's SEEN or UNINTERESTING\n3. mark it\n4. go through all the parents and..\n5a. mark it if it's never marked before\n5b. put it back in the queue\n\nWhat we do in this patch is drop step 5a because it is not\nnecessary. The commit being marked at 5a is put back on the queue, and\nwill be marked at step 3 at the next iteration. The only case it will\nnot be marked is when the commit is already marked UNINTERESTING (5a\ndoes not check this), which will be ignored at step 2.\n\nBut we don't care about refs marking on UNINTERESTING. We care about the\nmarking on _shallow commits_ that are not reachable from our current\nhistory (and having UNINTERESTING on it means it's reachable). So it's\nok for an UNINTERESTING not to be ref-marked.\n\nReported-by: Rasmus Villemoes \nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 4 ----\n 1 file changed, 4 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex beb967e..11f7dde 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -512,12 +512,8 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1,\n \t\t\t oid_to_hex(&c->object.oid));\n \n \t\tfor (p = c->parents; p; p = p->next) {\n-\t\t\tuint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,\n-\t\t\t\t\t\t\t p->item);\n \t\t\tif (p->item->object.flags & SEEN)\n \t\t\t\tcontinue;\n-\t\t\tif (*p_refs == NULL || *p_refs == *refs)\n-\t\t\t\t*p_refs = *refs;\n \t\t\tcommit_list_insert(p->item, &head);\n \t\t}\n \t}\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306998","messageId":"20161206125339.16803-4-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 3/6] shallow.c: make paint_alloc slightly more robust","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:36Z","receivedAt":"2016-12-06T12:55:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"paint_alloc() allocates a big block of memory and splits it into\nsmaller, fixed size, chunks of memory whenever it's called. Each chunk\ncontains enough bits to present all \"new refs\" [1] in a fetch from a\nshallow repository.\n\nWe do not check if the new \"big block\" is smaller than the requested\nmemory chunk though. If it happens, we'll happily pass back a memory\nregion smaller than expected. Which will lead to problems eventually.\n\nA normal fetch may add/update a dozen new refs. Let's stay on the\n\"reasonably extreme\" side and say we need 16k refs (or bits from\npaint_alloc's perspective). Each chunk of memory would be 2k, much\nsmaller than the memory pool (512k).\n\nSo, normally, the under-allocation situation should never happen. A bad\nguy, however, could make a fetch that adds more than 4m new/updated refs\nto this code which results in a memory chunk larger than pool size.\nCheck this case and abort.\n\nNoticed-by: Rasmus Villemoes \n\n[1] Details are in commit message of 58babff (shallow.c: the 8 steps to\n select new commits for .git/shallow - 2013-12-05), step 6.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/shallow.c b/shallow.c\nindex 2512ed3..75e1702 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -447,6 +447,9 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tunsigned size = nr * sizeof(uint32_t);\n \tvoid *p;\n \tif (!info->pool_count || info->free + size > info->end) {\n+\t\tif (size > POOL_SIZE)\n+\t\t\tdie(\"BUG: pool size too small for %d in paint_alloc()\",\n+\t\t\t size);\n \t\tinfo->pool_count++;\n \t\tREALLOC_ARRAY(info->pools, info->pool_count);\n \t\tinfo->free = xmalloc(POOL_SIZE);\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"306999","messageId":"20161206125339.16803-3-pclouds@gmail.com","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"[PATCH v2 2/6] shallow.c: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:35Z","receivedAt":"2016-12-06T13:15:55Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"We need to allocate a \"big\" block of memory in paint_alloc(). The exact\nsize does not really matter. But the pool size has no relation with\ncommit-slab. Stop using that macro here.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n shallow.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/shallow.c b/shallow.c\nindex 8100dfd..2512ed3 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -431,6 +431,8 @@ void remove_nonexistent_theirs_shallow(struct shallow_info *info)\n \n define_commit_slab(ref_bitmap, uint32_t *);\n \n+#define POOL_SIZE (512 * 1024)\n+\n struct paint_info {\n \tstruct ref_bitmap ref_bitmap;\n \tunsigned nr_bits;\n@@ -447,9 +449,9 @@ static uint32_t *paint_alloc(struct paint_info *info)\n \tif (!info->pool_count || info->free + size > info->end) {\n \t\tinfo->pool_count++;\n \t\tREALLOC_ARRAY(info->pools, info->pool_count);\n-\t\tinfo->free = xmalloc(COMMIT_SLAB_SIZE);\n+\t\tinfo->free = xmalloc(POOL_SIZE);\n \t\tinfo->pools[info->pool_count - 1] = info->free;\n-\t\tinfo->end = info->free + COMMIT_SLAB_SIZE;\n+\t\tinfo->end = info->free + POOL_SIZE;\n \t}\n \tp = info->free;\n \tinfo->free += size;\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"307002","messageId":"20161206134212.mttcb75dov2jvqu5@sigill.intra.peff.net","threadId":"44597","inReplyTo":"20161206125339.16803-1-pclouds@gmail.com","subject":"Re: [PATCH v2 0/6] shallow.c improvements","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-06T13:42:12Z","receivedAt":"2016-12-06T13:42:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Dec 06, 2016 at 07:53:33PM +0700, Nguyễn Thái Ngọc Duy wrote:\n\n> Nguyễn Thái Ngọc Duy (4):\n> shallow.c: rename fields in paint_info to better express their purposes\n> shallow.c: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools\n> shallow.c: make paint_alloc slightly more robust\n> shallow.c: remove useless code\n> \n> Rasmus Villemoes (2):\n> shallow.c: avoid theoretical pointer wrap-around\n> shallow.c: bit manipulation tweaks\n\nThe first 5 patches look obviously good to me. The naming changes in\npaint_alloc() make things much clearer, and the fixes retained from\nRasmus are all obvious improvements.\n\nThe final one _seems_ reasonable after reading your explanation, but I\nlack enough context to know whether or not there might be a corner case\nthat you're missing. I'm inclined to trust your assessment on it.\n\n-Peff\n"},{"id":"307003","messageId":"20161206125339.16803-1-pclouds@gmail.com","threadId":"44597","inReplyTo":"1480710664-26290-1-git-send-email-rv@rasmusvillemoes.dk","subject":"[PATCH v2 0/6] shallow.c improvements","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T12:53:33Z","receivedAt":"2016-12-06T13:46:36Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"After staring not-so-hard and not-for-so-long at the code. This is\nwhat I come up with. Rasmus I replaced two of your commits with my\nown (and thank you for giving me an opportunity to refresh my memory\nwith this stuff). The first two commits are new and the result of\nJeff's observation on COMMIT_SLAB_SIZE.\n\nYou may find the description here a bit different from my explanation\npreviously (about \"exclude/shallow requests\"). Well.. I was wrong.\nI had the recent --exclude-tag and friends in mind, but this is about\nclone/fetch/push from/to a shallow repository since 2013, no wonder I\ndon't remember much about it :-D\n\nNguyễn Thái Ngọc Duy (4):\n shallow.c: rename fields in paint_info to better express their purposes\n shallow.c: stop abusing COMMIT_SLAB_SIZE for paint_info's memory pools\n shallow.c: make paint_alloc slightly more robust\n shallow.c: remove useless code\n\nRasmus Villemoes (2):\n shallow.c: avoid theoretical pointer wrap-around\n shallow.c: bit manipulation tweaks\n\n shallow.c | 39 ++++++++++++++++++++-------------------\n 1 file changed, 20 insertions(+), 19 deletions(-)\n\n-- \n2.8.2.524.g6ff3d78\n\n"},{"id":"307006","messageId":"CACsJy8A=KeGsXAt6ZR-eOkTurSsnYPkt3yTfkYT9aZ86rV1rYg@mail.gmail.com","threadId":"44597","inReplyTo":"20161206134212.mttcb75dov2jvqu5@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/6] shallow.c improvements","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2016-12-06T13:47:36Z","receivedAt":"2016-12-06T13:55:52Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Dec 6, 2016 at 8:42 PM, Jeff King wrote:\n> The final one _seems_ reasonable after reading your explanation, but I\n> lack enough context to know whether or not there might be a corner case\n> that you're missing. I'm inclined to trust your assessment on it.\n\nYeah I basically just wrote down my thoughts so somebody could maybe\nspot something wrong. I'm going to think about it some more in the\nnext few days.\n-- \nDuy\n"},{"id":"307197","messageId":"xmqqa8c7ux04.fsf@gitster.mtv.corp.google.com","threadId":"44597","inReplyTo":"CACsJy8A=KeGsXAt6ZR-eOkTurSsnYPkt3yTfkYT9aZ86rV1rYg@mail.gmail.com","subject":"Re: [PATCH v2 0/6] shallow.c improvements","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-07T23:42:35Z","receivedAt":"2016-12-07T23:43:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> On Tue, Dec 6, 2016 at 8:42 PM, Jeff King wrote:\n>> The final one _seems_ reasonable after reading your explanation, but I\n>> lack enough context to know whether or not there might be a corner case\n>> that you're missing. I'm inclined to trust your assessment on it.\n>\n> Yeah I basically just wrote down my thoughts so somebody could maybe\n> spot something wrong. I'm going to think about it some more in the\n> next few days.\n\nIn the meantime let me queue them as-is.\n\nThanks.\n"}]}