{"thread":{"id":"44360","subject":"[PATCH] hex: use unsigned index for ring buffer","startedAt":"2016-10-23T09:01:57Z","lastAt":"2016-10-26T17:53:55Z","messageCount":14,"participants":["René Scharfe","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"304726","messageId":"ebf769d4-771f-499e-c7fc-f0377d8df18e@web.de","threadId":"44360","inReplyTo":null,"subject":"[PATCH] hex: use unsigned index for ring buffer","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-23T09:00:48Z","receivedAt":"2016-10-23T09:01:57Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Overflow is defined for unsigned integers, but not for signed ones.\nMake the ring buffer index in sha1_to_hex() unsigned to be on the\nsafe side.\n\nSigned-off-by: Rene Scharfe \n---\nHard to trigger, but probably even harder to diagnose once someone\nsomehow manages to do it on some uncommon architecture.\n\n hex.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/hex.c b/hex.c\nindex ab2610e..8c6c189 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -76,7 +76,7 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)\n \n char *sha1_to_hex(const unsigned char *sha1)\n {\n-\tstatic int bufno;\n+\tstatic unsigned int bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n }\n-- \n2.10.1\n\n"},{"id":"304728","messageId":"20161023091146.p2kmqvgwxdf77dnn@sigill.intra.peff.net","threadId":"44360","inReplyTo":"ebf769d4-771f-499e-c7fc-f0377d8df18e@web.de","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-23T09:11:46Z","receivedAt":"2016-10-23T09:11:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 23, 2016 at 11:00:48AM +0200, René Scharfe wrote:\n\n> Overflow is defined for unsigned integers, but not for signed ones.\n> Make the ring buffer index in sha1_to_hex() unsigned to be on the\n> safe side.\n> \n> Signed-off-by: Rene Scharfe \n> ---\n> Hard to trigger, but probably even harder to diagnose once someone\n> somehow manages to do it on some uncommon architecture.\n\nIndeed. If we are worried about overflow, we would also want to assume\nthat it wraps at a multiple of 4, but that is probably a sane\nassumption.\n\n> diff --git a/hex.c b/hex.c\n> index ab2610e..8c6c189 100644\n> --- a/hex.c\n> +++ b/hex.c\n> @@ -76,7 +76,7 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)\n> \n> char *sha1_to_hex(const unsigned char *sha1)\n> {\n> -\tstatic int bufno;\n> +\tstatic unsigned int bufno;\n> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n> \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n> }\n\nI wonder if just truncating bufno would be conceptually simpler (albeit\nlonger):\n\n bufno++;\n bufno &= 3;\n return sha1_to_hex_r(hexbuffer[bufno], sha1);\n\nYou could also write the second line like:\n\n bufno %= ARRAY_SIZE(hexbuffer);\n\nwhich is less magical (right now the set of buffers must be a power of\n2). I expect the compiler could turn that into a bitmask itself.\n\nI'm fine with any of the options. I guess you'd want a similar patch for\nfind_unique_abbrev on top of jk/no-looking-at-dotgit-outside-repo.\n\n-Peff\n"},{"id":"304764","messageId":"fb816dd5-8fb9-c6a6-2ec2-9ea4dddfdb26@web.de","threadId":"44360","inReplyTo":"20161023091146.p2kmqvgwxdf77dnn@sigill.intra.peff.net","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-23T17:57:30Z","receivedAt":"2016-10-23T17:57:56Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 23.10.2016 um 11:11 schrieb Jeff King:\n> On Sun, Oct 23, 2016 at 11:00:48AM +0200, René Scharfe wrote:\n>\n>> Overflow is defined for unsigned integers, but not for signed ones.\n>> Make the ring buffer index in sha1_to_hex() unsigned to be on the\n>> safe side.\n>>\n>> Signed-off-by: Rene Scharfe \n>> ---\n>> Hard to trigger, but probably even harder to diagnose once someone\n>> somehow manages to do it on some uncommon architecture.\n>\n> Indeed. If we are worried about overflow, we would also want to assume\n> that it wraps at a multiple of 4, but that is probably a sane\n> assumption.\n\nHmm, I can't think of a way to violate this assumption except with \nunsigned integers that are only a single bit wide. That would be a \nweird machine. Are there other possibilities?\n\n>> diff --git a/hex.c b/hex.c\n>> index ab2610e..8c6c189 100644\n>> --- a/hex.c\n>> +++ b/hex.c\n>> @@ -76,7 +76,7 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)\n>>\n>> char *sha1_to_hex(const unsigned char *sha1)\n>> {\n>> -\tstatic int bufno;\n>> +\tstatic unsigned int bufno;\n>> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n>> \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n>> }\n>\n> I wonder if just truncating bufno would be conceptually simpler (albeit\n> longer):\n>\n> bufno++;\n> bufno &= 3;\n> return sha1_to_hex_r(hexbuffer[bufno], sha1);\n>\n> You could also write the second line like:\n>\n> bufno %= ARRAY_SIZE(hexbuffer);\n>\n> which is less magical (right now the set of buffers must be a power of\n> 2). I expect the compiler could turn that into a bitmask itself.\n\nExpelling magic is a good idea. And indeed, at least gcc, clang and icc \non x86-64 are smart enough to use an AND instead of dividing \n(https://godbolt.org/g/rFPpzF).\n\nBut gcc also adds a sign extension (cltq/cdqe) if we store the truncated \nvalue, unlike the other two compilers. I don't see why -- the bit mask \noperation enforces a value between 0 and 3 (inclusive) and the upper \nbits of eax are zeroed automatically, so the cltq is effectively a noop.\n\nUsing size_t gets us rid of the extra instruction and is the right type \nanyway. It would suffice on its own, hmm..\n\n> I'm fine with any of the options. I guess you'd want a similar patch for\n> find_unique_abbrev on top of jk/no-looking-at-dotgit-outside-repo.\n\nActually I'd want you to want to amend your series yourself. ;) Maybe I \ncan convince Coccinelle to handle that issue for us.\n\nAnd there's also path.c::get_pathname(). That's enough cases to justify \nadding a macro, I'd say:\n\n---\n cache.h | 3 +++\n hex.c | 4 ++--\n path.c | 4 ++--\n 3 files changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 05ecb88..8bb4918 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -555,6 +555,9 @@ extern int daemonize(void);\n \t\t} \\\n \t} while (0)\n\n+#define NEXT_RING_ITEM(array, index) \\\n+\t(array)[(index) = ((index) + 1) % ARRAY_SIZE(array)]\n+\n /* Initialize and use the cache information */\n struct lock_file;\n extern int read_index(struct index_state *);\ndiff --git a/hex.c b/hex.c\nindex ab2610e..5e711b9 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -76,9 +76,9 @@ char *oid_to_hex_r(char *buffer, const struct \nobject_id *oid)\n\n char *sha1_to_hex(const unsigned char *sha1)\n {\n-\tstatic int bufno;\n+\tstatic size_t bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n-\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n+\treturn sha1_to_hex_r(NEXT_RING_ITEM(hexbuffer, bufno), sha1);\n }\n\n char *oid_to_hex(const struct object_id *oid)\ndiff --git a/path.c b/path.c\nindex a8e7295..60dba6a 100644\n--- a/path.c\n+++ b/path.c\n@@ -24,8 +24,8 @@ static struct strbuf *get_pathname(void)\n \tstatic struct strbuf pathname_array[4] = {\n \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n \t};\n-\tstatic int index;\n-\tstruct strbuf *sb = &pathname_array[3 & ++index];\n+\tstatic size_t index;\n+\tstruct strbuf *sb = &NEXT_RING_ITEM(pathname_array, index);\n \tstrbuf_reset(sb);\n \treturn sb;\n }\n-- \n2.10.1\n\n\n"},{"id":"304772","messageId":"20161024130015.awlmgpfzixiy6wkb@sigill.intra.peff.net","threadId":"44360","inReplyTo":"fb816dd5-8fb9-c6a6-2ec2-9ea4dddfdb26@web.de","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-24T13:00:15Z","receivedAt":"2016-10-24T13:00:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Oct 23, 2016 at 07:57:30PM +0200, René Scharfe wrote:\n\n> > > Hard to trigger, but probably even harder to diagnose once someone\n> > > somehow manages to do it on some uncommon architecture.\n> > \n> > Indeed. If we are worried about overflow, we would also want to assume\n> > that it wraps at a multiple of 4, but that is probably a sane\n> > assumption.\n> \n> Hmm, I can't think of a way to violate this assumption except with unsigned\n> integers that are only a single bit wide. That would be a weird machine.\n> Are there other possibilities?\n\nNo, I don't think so. I don't recall offhand whether the C standard\nallows integers that are not powers of 2. But if it does, and somebody\ndevelops such a platform, I have very little sympathy.\n\nMy comment was mostly \"this is the only other restriction I can think\nof, and it is crazy\".\n\n> > You could also write the second line like:\n> > \n> > bufno %= ARRAY_SIZE(hexbuffer);\n> > \n> > which is less magical (right now the set of buffers must be a power of\n> > 2). I expect the compiler could turn that into a bitmask itself.\n> \n> Expelling magic is a good idea. And indeed, at least gcc, clang and icc on\n> x86-64 are smart enough to use an AND instead of dividing\n> (https://godbolt.org/g/rFPpzF).\n> \n> But gcc also adds a sign extension (cltq/cdqe) if we store the truncated\n> value, unlike the other two compilers. I don't see why -- the bit mask\n> operation enforces a value between 0 and 3 (inclusive) and the upper bits of\n> eax are zeroed automatically, so the cltq is effectively a noop.\n> \n> Using size_t gets us rid of the extra instruction and is the right type\n> anyway. It would suffice on its own, hmm..\n\nYeah, I had assumed you would also switch to some form of unsigned type\neither way.\n\n> > I'm fine with any of the options. I guess you'd want a similar patch for\n> > find_unique_abbrev on top of jk/no-looking-at-dotgit-outside-repo.\n> \n> Actually I'd want you to want to amend your series yourself. ;) Maybe I can\n> convince Coccinelle to handle that issue for us.\n\nI thought that series was in \"next\" already, but I see it isn't yet. I'd\nstill wait until the sha1_to_hex() solution settles, and then copy it.\n\n> And there's also path.c::get_pathname(). That's enough cases to justify\n> adding a macro, I'd say:\n> [...]\n> +#define NEXT_RING_ITEM(array, index) \\\n> +\t(array)[(index) = ((index) + 1) % ARRAY_SIZE(array)]\n> +\n\nI dunno. It hides a lot of magic without saving a lot of lines in the\ncaller, and the callers have to make sure \"array\" is an array and that\n\"index\" is unsigned.\n\nE.g., in this code:\n\n> @@ -24,8 +24,8 @@ static struct strbuf *get_pathname(void)\n> \tstatic struct strbuf pathname_array[4] = {\n> \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n> \t};\n> -\tstatic int index;\n> -\tstruct strbuf *sb = &pathname_array[3 & ++index];\n> +\tstatic size_t index;\n> +\tstruct strbuf *sb = &NEXT_RING_ITEM(pathname_array, index);\n> \tstrbuf_reset(sb);\n> \treturn sb;\n> }\n\nThe truly ugly part is the repeated STRBUF_INIT. :)\n\nI think it would be preferable to just fix it inline in each place.\n\n-Peff\n"},{"id":"304778","messageId":"xmqqwpgx7jn6.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"20161024130015.awlmgpfzixiy6wkb@sigill.intra.peff.net","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-24T17:15:57Z","receivedAt":"2016-10-24T17:16:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> > You could also write the second line like:\n>> > \n>> > bufno %= ARRAY_SIZE(hexbuffer);\n>> > \n>> > which is less magical (right now the set of buffers must be a power of\n>> > 2). I expect the compiler could turn that into a bitmask itself.\n>> ...\n>\n> I think it would be preferable to just fix it inline in each place.\n\nYeah, probably.\n\nMy initial reaction to this was\n\n char *sha1_to_hex(const unsigned char *sha1)\n {\n-\tstatic int bufno;\n+\tstatic unsigned int bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n\n\"ah, we do not even need bufno as uint; it could be ushort or even\nuchar\". If this were a 256 element ring buffer and the index were\nuchar, we wouldn't even be having this discussion, and \"3 &\" is a\nway to get a fake type that is a 2-bit unsigned integer that wraps\naround when incremented.\n\nBut being explicit, especially when we know that we can rely on the\nfact that the compilers are usually intelligent enough, is a good\nidea, I would think.\n\nIsn't size_t often wider than uint, by the way? It somehow makes me\nfeel dirty to use it when we know we only care about the bottom two\nbit, especially with the explicit \"bufno %= ARRAY_SIZE(hexbuffer)\",\nbut I may be simply superstitious in this case. I dunno.\n"},{"id":"304779","messageId":"xmqqshrl7j42.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"xmqqwpgx7jn6.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-24T17:27:25Z","receivedAt":"2016-10-24T17:28:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> I think it would be preferable to just fix it inline in each place.\n>\n> Yeah, probably.\n>\n> My initial reaction to this was\n>\n> char *sha1_to_hex(const unsigned char *sha1)\n> {\n> -\tstatic int bufno;\n> +\tstatic unsigned int bufno;\n> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n> \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n>\n> \"ah, we do not even need bufno as uint; it could be ushort or even\n> uchar\". If this were a 256 element ring buffer and the index were\n> uchar, we wouldn't even be having this discussion, and \"3 &\" is a\n> way to get a fake type that is a 2-bit unsigned integer that wraps\n> around when incremented.\n>\n> But being explicit, especially when we know that we can rely on the\n> fact that the compilers are usually intelligent enough, is a good\n> idea, I would think.\n>\n> Isn't size_t often wider than uint, by the way? It somehow makes me\n> feel dirty to use it when we know we only care about the bottom two\n> bit, especially with the explicit \"bufno %= ARRAY_SIZE(hexbuffer)\",\n> but I may be simply superstitious in this case. I dunno.\n\nIf we are doing the wrap-around ourselves, I suspect that the index\nshould stay \"int\" (not even unsigned), as that is supposed to be the\nmost natural and performant type on the architecture. Would it\nstill result in better code to use size_t instead?\n\n\n\nAuthor: René Scharfe \nDate: Sun Oct 23 19:57:30 2016 +0200\n\n hex: make wraparound of the index into ring-buffer explicit\n \n Overflow is defined for unsigned integers, but not for signed ones.\n \n We could make the ring-buffer index in sha1_to_hex() and\n get_pathname() unsigned to be on the safe side to resolve this, but\n let's make it explicit that we are wrapping around at whatever the\n number of elements the ring-buffer has. The compiler is smart enough\n to turn modulus into bitmask for these codepaths that use\n ring-buffers of a size that is a power of 2.\n---\n cache.h | 3 +++\n hex.c | 4 ++--\n path.c | 4 ++--\n 3 files changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 4cba08ecb1..5429df0f92 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -547,6 +547,9 @@ extern int daemonize(void);\n \t\t} \\\n \t} while (0)\n \n+#define NEXT_RING_ITEM(array, index) \\\n+\t(array)[(index) = ((index) + 1) % ARRAY_SIZE(array)]\n+\n /* Initialize and use the cache information */\n struct lock_file;\n extern int read_index(struct index_state *);\ndiff --git a/hex.c b/hex.c\nindex ab2610e498..5e711b9e32 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -76,9 +76,9 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)\n \n char *sha1_to_hex(const unsigned char *sha1)\n {\n-\tstatic int bufno;\n+\tstatic size_t bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n-\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n+\treturn sha1_to_hex_r(NEXT_RING_ITEM(hexbuffer, bufno), sha1);\n }\n \n char *oid_to_hex(const struct object_id *oid)\ndiff --git a/path.c b/path.c\nindex fe3c4d96c6..5b2ab2271f 100644\n--- a/path.c\n+++ b/path.c\n@@ -23,8 +23,8 @@ static struct strbuf *get_pathname(void)\n \tstatic struct strbuf pathname_array[4] = {\n \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n \t};\n-\tstatic int index;\n-\tstruct strbuf *sb = &pathname_array[3 & ++index];\n+\tstatic size_t index;\n+\tstruct strbuf *sb = &NEXT_RING_ITEM(pathname_array, index);\n \tstrbuf_reset(sb);\n \treturn sb;\n }\n"},{"id":"304811","messageId":"b1f9054e-fadb-c2d3-bf95-00e88e1fb85b@web.de","threadId":"44360","inReplyTo":"xmqqshrl7j42.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-24T22:33:03Z","receivedAt":"2016-10-24T22:33:35Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.10.2016 um 19:27 schrieb Junio C Hamano:\n> Junio C Hamano writes:\n> \n>>> I think it would be preferable to just fix it inline in each place.\n>>\n>> Yeah, probably.\n>>\n>> My initial reaction to this was\n>>\n>> char *sha1_to_hex(const unsigned char *sha1)\n>> {\n>> -\tstatic int bufno;\n>> +\tstatic unsigned int bufno;\n>> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n>> \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n>>\n>> \"ah, we do not even need bufno as uint; it could be ushort or even\n>> uchar\". If this were a 256 element ring buffer and the index were\n>> uchar, we wouldn't even be having this discussion, and \"3 &\" is a\n>> way to get a fake type that is a 2-bit unsigned integer that wraps\n>> around when incremented.\n>>\n>> But being explicit, especially when we know that we can rely on the\n>> fact that the compilers are usually intelligent enough, is a good\n>> idea, I would think.\n>>\n>> Isn't size_t often wider than uint, by the way? It somehow makes me\n>> feel dirty to use it when we know we only care about the bottom two\n>> bit, especially with the explicit \"bufno %= ARRAY_SIZE(hexbuffer)\",\n>> but I may be simply superstitious in this case. I dunno.\n> \n> If we are doing the wrap-around ourselves, I suspect that the index\n> should stay \"int\" (not even unsigned), as that is supposed to be the\n> most natural and performant type on the architecture. Would it\n> still result in better code to use size_t instead?\n\nRight.\n\nGcc emits an extra cltq instruction for x86-64 (Convert Long To Quad,\ni.e. 32-bit to 64-bit) if we wrap explicitly and still use an int in\nsha1_to_hex(). It doesn't if we use an unsigned int or size_t. It\nalso doesn't for get_pathname(). I guess updating the index variable\nonly after use makes the difference there.\n\nBut I think we can ignore that; it's just an extra cycle. I only\neven noticed it when verifying that \"% 4\" is turned into \"& 3\"..\nClang and icc don't add the cltq, by the way.\n\nSo how about this? It gets rid of magic number 3 and works for array\nsize that's not a power of two. And as a nice side effect it can't\ntrigger a signed overflow anymore.\n\nJust adding \"unsigned\" looks more attractive to me for some reason.\nPerhaps I stared enough at the code to get used to the magic values\nthere..\n\nRené\n\n---\n hex.c | 3 ++-\n path.c | 3 ++-\n 2 files changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/hex.c b/hex.c\nindex ab2610e..845b01a 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -78,7 +78,8 @@ char *sha1_to_hex(const unsigned char *sha1)\n {\n \tstatic int bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n-\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n+\tbufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);\n+\treturn sha1_to_hex_r(hexbuffer[bufno], sha1);\n }\n \n char *oid_to_hex(const struct object_id *oid)\ndiff --git a/path.c b/path.c\nindex a8e7295..52d889c 100644\n--- a/path.c\n+++ b/path.c\n@@ -25,7 +25,8 @@ static struct strbuf *get_pathname(void)\n \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n \t};\n \tstatic int index;\n-\tstruct strbuf *sb = &pathname_array[3 & ++index];\n+\tstruct strbuf *sb = &pathname_array[index];\n+\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n \tstrbuf_reset(sb);\n \treturn sb;\n }\n-- \n2.10.1\n"},{"id":"304815","messageId":"xmqq60ohtib5.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"b1f9054e-fadb-c2d3-bf95-00e88e1fb85b@web.de","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-24T23:53:50Z","receivedAt":"2016-10-24T23:53:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Am 24.10.2016 um 19:27 schrieb Junio C Hamano:\n>> Junio C Hamano writes:\n>> \n>>>> I think it would be preferable to just fix it inline in each place.\n>>>\n>>> Yeah, probably.\n>>>\n>>> My initial reaction to this was\n>>>\n>>> char *sha1_to_hex(const unsigned char *sha1)\n>>> {\n>>> -\tstatic int bufno;\n>>> +\tstatic unsigned int bufno;\n>>> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n>>> \treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n>>>\n>>> \"ah, we do not even need bufno as uint; it could be ushort or even\n>>> uchar\". If this were a 256 element ring buffer and the index were\n>>> uchar, we wouldn't even be having this discussion, and \"3 &\" is a\n>>> way to get a fake type that is a 2-bit unsigned integer that wraps\n>>> around when incremented.\n>>>\n>>> But being explicit, especially when we know that we can rely on the\n>>> fact that the compilers are usually intelligent enough, is a good\n>>> idea, I would think.\n>>>\n>>> Isn't size_t often wider than uint, by the way? It somehow makes me\n>>> feel dirty to use it when we know we only care about the bottom two\n>>> bit, especially with the explicit \"bufno %= ARRAY_SIZE(hexbuffer)\",\n>>> but I may be simply superstitious in this case. I dunno.\n>> \n>> If we are doing the wrap-around ourselves, I suspect that the index\n>> should stay \"int\" (not even unsigned), as that is supposed to be the\n>> most natural and performant type on the architecture. Would it\n>> still result in better code to use size_t instead?\n>\n> Right.\n>\n> Gcc emits an extra cltq instruction for x86-64 (Convert Long To Quad,\n> i.e. 32-bit to 64-bit) if we wrap explicitly and still use an int in\n> sha1_to_hex(). It doesn't if we use an unsigned int or size_t. It\n> also doesn't for get_pathname(). I guess updating the index variable\n> only after use makes the difference there.\n>\n> But I think we can ignore that; it's just an extra cycle. I only\n> even noticed it when verifying that \"% 4\" is turned into \"& 3\"..\n> Clang and icc don't add the cltq, by the way.\n>\n> So how about this? It gets rid of magic number 3 and works for array\n> size that's not a power of two. And as a nice side effect it can't\n> trigger a signed overflow anymore.\n\nLooks good to me. Peff?\n\n> Just adding \"unsigned\" looks more attractive to me for some reason.\n> Perhaps I stared enough at the code to get used to the magic values\n> there..\n\nI somehow share that feeling, too.\n"},{"id":"304816","messageId":"20161025003023.6vaqofsixana3zno@sigill.intra.peff.net","threadId":"44360","inReplyTo":"xmqq60ohtib5.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-25T00:30:23Z","receivedAt":"2016-10-25T00:30:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 24, 2016 at 04:53:50PM -0700, Junio C Hamano wrote:\n\n> > So how about this? It gets rid of magic number 3 and works for array\n> > size that's not a power of two. And as a nice side effect it can't\n> > trigger a signed overflow anymore.\n> \n> Looks good to me. Peff?\n\nAny of the variants discussed in this thread is fine by me.\n\n-Peff\n"},{"id":"304860","messageId":"xmqqd1ios2p3.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"20161025003023.6vaqofsixana3zno@sigill.intra.peff.net","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-25T18:28:40Z","receivedAt":"2016-10-25T18:28:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Mon, Oct 24, 2016 at 04:53:50PM -0700, Junio C Hamano wrote:\n>\n>> > So how about this? It gets rid of magic number 3 and works for array\n>> > size that's not a power of two. And as a nice side effect it can't\n>> > trigger a signed overflow anymore.\n>> \n>> Looks good to me. Peff?\n>\n> Any of the variants discussed in this thread is fine by me.\n\nOK, here is what I'll queue then.\nI assumed that René wants to sign it off ;-).\n\n-- >8 --\nFrom: René Scharfe \nDate: Sun, 23 Oct 2016 19:57:30 +0200\nSubject: [PATCH] hex: make wraparound of the index into ring-buffer explicit\n\nOverflow is defined for unsigned integers, but not for signed ones.\n\nWe could make the ring-buffer index in sha1_to_hex() and\nget_pathname() unsigned to be on the safe side to resolve this, but\nlet's make it explicit that we are wrapping around at whatever the\nnumber of elements the ring-buffer has. The compiler is smart enough\nto turn modulus into bitmask for these codepaths that use\nring-buffers of a size that is a power of 2.\n\nSigned-off-by: René Scharfe \nSigned-off-by: Junio C Hamano \n---\n hex.c | 3 ++-\n path.c | 3 ++-\n 2 files changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/hex.c b/hex.c\nindex ab2610e498..845b01a874 100644\n--- a/hex.c\n+++ b/hex.c\n@@ -78,7 +78,8 @@ char *sha1_to_hex(const unsigned char *sha1)\n {\n \tstatic int bufno;\n \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n-\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n+\tbufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);\n+\treturn sha1_to_hex_r(hexbuffer[bufno], sha1);\n }\n \n char *oid_to_hex(const struct object_id *oid)\ndiff --git a/path.c b/path.c\nindex fe3c4d96c6..9bfaeda207 100644\n--- a/path.c\n+++ b/path.c\n@@ -24,7 +24,8 @@ static struct strbuf *get_pathname(void)\n \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n \t};\n \tstatic int index;\n-\tstruct strbuf *sb = &pathname_array[3 & ++index];\n+\tstruct strbuf *sb = &pathname_array[index];\n+\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n \tstrbuf_reset(sb);\n \treturn sb;\n }\n-- \n2.10.1-777-gd068e6bde7\n\n"},{"id":"304862","messageId":"20161025183347.u3cvowf2h6tabtuw@sigill.intra.peff.net","threadId":"44360","inReplyTo":"xmqqd1ios2p3.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-10-25T18:33:48Z","receivedAt":"2016-10-25T18:34:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Oct 25, 2016 at 11:28:40AM -0700, Junio C Hamano wrote:\n\n> OK, here is what I'll queue then.\n> I assumed that René wants to sign it off ;-).\n> \n> -- >8 --\n> From: René Scharfe \n> Date: Sun, 23 Oct 2016 19:57:30 +0200\n> Subject: [PATCH] hex: make wraparound of the index into ring-buffer explicit\n> \n> Overflow is defined for unsigned integers, but not for signed ones.\n> \n> We could make the ring-buffer index in sha1_to_hex() and\n> get_pathname() unsigned to be on the safe side to resolve this, but\n> let's make it explicit that we are wrapping around at whatever the\n> number of elements the ring-buffer has. The compiler is smart enough\n> to turn modulus into bitmask for these codepaths that use\n> ring-buffers of a size that is a power of 2.\n\nLooks good to me.\n\n> diff --git a/path.c b/path.c\n> index fe3c4d96c6..9bfaeda207 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -24,7 +24,8 @@ static struct strbuf *get_pathname(void)\n> \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n> \t};\n> \tstatic int index;\n> -\tstruct strbuf *sb = &pathname_array[3 & ++index];\n> +\tstruct strbuf *sb = &pathname_array[index];\n> +\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n> \tstrbuf_reset(sb);\n> \treturn sb;\n\nThis converts the pre-increment to a post-increment, but I don't think\nit matters.\n\n-Peff\n"},{"id":"304864","messageId":"xmqq4m40s2al.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"20161025183347.u3cvowf2h6tabtuw@sigill.intra.peff.net","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-25T18:37:22Z","receivedAt":"2016-10-25T18:37:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> diff --git a/path.c b/path.c\n>> index fe3c4d96c6..9bfaeda207 100644\n>> --- a/path.c\n>> +++ b/path.c\n>> @@ -24,7 +24,8 @@ static struct strbuf *get_pathname(void)\n>> \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n>> \t};\n>> \tstatic int index;\n>> -\tstruct strbuf *sb = &pathname_array[3 & ++index];\n>> +\tstruct strbuf *sb = &pathname_array[index];\n>> +\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n>> \tstrbuf_reset(sb);\n>> \treturn sb;\n>\n> This converts the pre-increment to a post-increment, but I don't think\n> it matters.\n\nYes, I think that using the ring buffer from the beginning, not from\nthe second element from the beginning, is conceptually cleaner ;-).\n\n"},{"id":"304902","messageId":"3c95a89a-2a9b-2856-42a1-6b994f2e31cd@web.de","threadId":"44360","inReplyTo":"xmqqd1ios2p3.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-10-26T17:08:41Z","receivedAt":"2016-10-26T17:09:08Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 25.10.2016 um 20:28 schrieb Junio C Hamano:\n> Jeff King writes:\n>\n>> On Mon, Oct 24, 2016 at 04:53:50PM -0700, Junio C Hamano wrote:\n>>\n>>>> So how about this? It gets rid of magic number 3 and works for array\n>>>> size that's not a power of two. And as a nice side effect it can't\n>>>> trigger a signed overflow anymore.\n>>>\n>>> Looks good to me. Peff?\n>>\n>> Any of the variants discussed in this thread is fine by me.\n>\n> OK, here is what I'll queue then.\n> I assumed that René wants to sign it off ;-).\n\nActually I didn't sign-off on purpose originally. But OK, let's keep\nthe version below. I just feel strangely sad seeing that concise magic\ngo. Nevermind.\n\nSigned-off-by: Rene Scharfe \n\n> -- >8 --\n> From: René Scharfe \n> Date: Sun, 23 Oct 2016 19:57:30 +0200\n> Subject: [PATCH] hex: make wraparound of the index into ring-buffer explicit\n>\n> Overflow is defined for unsigned integers, but not for signed ones.\n>\n> We could make the ring-buffer index in sha1_to_hex() and\n> get_pathname() unsigned to be on the safe side to resolve this, but\n> let's make it explicit that we are wrapping around at whatever the\n> number of elements the ring-buffer has. The compiler is smart enough\n> to turn modulus into bitmask for these codepaths that use\n> ring-buffers of a size that is a power of 2.\n>\n> Signed-off-by: René Scharfe \n> Signed-off-by: Junio C Hamano \n> ---\n> hex.c | 3 ++-\n> path.c | 3 ++-\n> 2 files changed, 4 insertions(+), 2 deletions(-)\n>\n> diff --git a/hex.c b/hex.c\n> index ab2610e498..845b01a874 100644\n> --- a/hex.c\n> +++ b/hex.c\n> @@ -78,7 +78,8 @@ char *sha1_to_hex(const unsigned char *sha1)\n> {\n> \tstatic int bufno;\n> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n> -\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n> +\tbufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);\n> +\treturn sha1_to_hex_r(hexbuffer[bufno], sha1);\n> }\n>\n> char *oid_to_hex(const struct object_id *oid)\n> diff --git a/path.c b/path.c\n> index fe3c4d96c6..9bfaeda207 100644\n> --- a/path.c\n> +++ b/path.c\n> @@ -24,7 +24,8 @@ static struct strbuf *get_pathname(void)\n> \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n> \t};\n> \tstatic int index;\n> -\tstruct strbuf *sb = &pathname_array[3 & ++index];\n> +\tstruct strbuf *sb = &pathname_array[index];\n> +\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n> \tstrbuf_reset(sb);\n> \treturn sb;\n> }\n>\n"},{"id":"304904","messageId":"xmqqlgxbatec.fsf@gitster.mtv.corp.google.com","threadId":"44360","inReplyTo":"3c95a89a-2a9b-2856-42a1-6b994f2e31cd@web.de","subject":"Re: [PATCH] hex: use unsigned index for ring buffer","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-10-26T17:53:47Z","receivedAt":"2016-10-26T17:53:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Actually I didn't sign-off on purpose originally. But OK, let's keep\n> the version below. I just feel strangely sad seeing that concise magic\n> go. Nevermind.\n\nI actually share the sadness, too, but let's be stupid and obvious\nhere.\n\nThanks.\n\n>\n> Signed-off-by: Rene Scharfe \n>\n>> -- >8 --\n>> From: René Scharfe \n>> Date: Sun, 23 Oct 2016 19:57:30 +0200\n>> Subject: [PATCH] hex: make wraparound of the index into ring-buffer explicit\n>>\n>> Overflow is defined for unsigned integers, but not for signed ones.\n>>\n>> We could make the ring-buffer index in sha1_to_hex() and\n>> get_pathname() unsigned to be on the safe side to resolve this, but\n>> let's make it explicit that we are wrapping around at whatever the\n>> number of elements the ring-buffer has. The compiler is smart enough\n>> to turn modulus into bitmask for these codepaths that use\n>> ring-buffers of a size that is a power of 2.\n>>\n>> Signed-off-by: René Scharfe \n>> Signed-off-by: Junio C Hamano \n>> ---\n>> hex.c | 3 ++-\n>> path.c | 3 ++-\n>> 2 files changed, 4 insertions(+), 2 deletions(-)\n>>\n>> diff --git a/hex.c b/hex.c\n>> index ab2610e498..845b01a874 100644\n>> --- a/hex.c\n>> +++ b/hex.c\n>> @@ -78,7 +78,8 @@ char *sha1_to_hex(const unsigned char *sha1)\n>> {\n>> \tstatic int bufno;\n>> \tstatic char hexbuffer[4][GIT_SHA1_HEXSZ + 1];\n>> -\treturn sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);\n>> +\tbufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);\n>> +\treturn sha1_to_hex_r(hexbuffer[bufno], sha1);\n>> }\n>>\n>> char *oid_to_hex(const struct object_id *oid)\n>> diff --git a/path.c b/path.c\n>> index fe3c4d96c6..9bfaeda207 100644\n>> --- a/path.c\n>> +++ b/path.c\n>> @@ -24,7 +24,8 @@ static struct strbuf *get_pathname(void)\n>> \t\tSTRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT\n>> \t};\n>> \tstatic int index;\n>> -\tstruct strbuf *sb = &pathname_array[3 & ++index];\n>> +\tstruct strbuf *sb = &pathname_array[index];\n>> +\tindex = (index + 1) % ARRAY_SIZE(pathname_array);\n>> \tstrbuf_reset(sb);\n>> \treturn sb;\n>> }\n>>\n"}]}