Re: [PATCH] hex: use unsigned index for ring buffer

From: Junio C Hamano <gitster@pobox.com>
Date: Oct 24, 2016, 17:27 UTC
Message-ID: <xmqqshrl7j42.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <xmqqwpgx7jn6.fsf@gitster.mtv.corp.google.com>

Junio C Hamano <gitster@pobox.com> writes:

Show 27 quoted lines

>> I think it would be preferable to just fix it inline in each place.
>
> Yeah, probably.
>
> My initial reaction to this was
>
>  char *sha1_to_hex(const unsigned char *sha1)
>  {
> -	static int bufno;
> +	static unsigned int bufno;
>  	static char hexbuffer[4][GIT_SHA1_HEXSZ + 1];
>  	return sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);
>
> "ah, we do not even need bufno as uint; it could be ushort or even
> uchar".  If this were a 256 element ring buffer and the index were
> uchar, we wouldn't even be having this discussion, and "3 &" is a
> way to get a fake type that is a 2-bit unsigned integer that wraps
> around when incremented.
>
> But being explicit, especially when we know that we can rely on the
> fact that the compilers are usually intelligent enough, is a good
> idea, I would think.
>
> Isn't size_t often wider than uint, by the way?  It somehow makes me
> feel dirty to use it when we know we only care about the bottom two
> bit, especially with the explicit "bufno %= ARRAY_SIZE(hexbuffer)",
> but I may be simply superstitious in this case.  I dunno.

If we are doing the wrap-around ourselves, I suspect that the index should stay "int" (not even unsigned), as that is supposed to be the most natural and performant type on the architecture. Would it still result in better code to use size_t instead?

Author: René Scharfe <l.s.r@web.de>
Date:   Sun Oct 23 19:57:30 2016 +0200

    hex: make wraparound of the index into ring-buffer explicit
    
    Overflow is defined for unsigned integers, but not for signed ones.
    
    We could make the ring-buffer index in sha1_to_hex() and
    get_pathname() unsigned to be on the safe side to resolve this, but
    let's make it explicit that we are wrapping around at whatever the
    number of elements the ring-buffer has.  The compiler is smart enough
    to turn modulus into bitmask for these codepaths that use
    ring-buffers of a size that is a power of 2.
---
 cache.h | 3 +++
 hex.c   | 4 ++--
 path.c  | 4 ++--
 3 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/cache.h b/cache.h
index 4cba08ecb1..5429df0f92 100644
--- a/cache.h
+++ b/cache.h
@@ -547,6 +547,9 @@ extern int daemonize(void);
 		} \
 	} while (0)
 
+#define NEXT_RING_ITEM(array, index) \
+	(array)[(index) = ((index) + 1) % ARRAY_SIZE(array)]
+
 /* Initialize and use the cache information */
 struct lock_file;
 extern int read_index(struct index_state *);
diff --git a/hex.c b/hex.c
index ab2610e498..5e711b9e32 100644
--- a/hex.c
+++ b/hex.c
@@ -76,9 +76,9 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)
 
 char *sha1_to_hex(const unsigned char *sha1)
 {
-	static int bufno;
+	static size_t bufno;
 	static char hexbuffer[4][GIT_SHA1_HEXSZ + 1];
-	return sha1_to_hex_r(hexbuffer[3 & ++bufno], sha1);
+	return sha1_to_hex_r(NEXT_RING_ITEM(hexbuffer, bufno), sha1);
 }
 
 char *oid_to_hex(const struct object_id *oid)
diff --git a/path.c b/path.c
index fe3c4d96c6..5b2ab2271f 100644
--- a/path.c
+++ b/path.c
@@ -23,8 +23,8 @@ static struct strbuf *get_pathname(void)
 	static struct strbuf pathname_array[4] = {
 		STRBUF_INIT, STRBUF_INIT, STRBUF_INIT, STRBUF_INIT
 	};
-	static int index;
-	struct strbuf *sb = &pathname_array[3 & ++index];
+	static size_t index;
+	struct strbuf *sb = &NEXT_RING_ITEM(pathname_array, index);
 	strbuf_reset(sb);
 	return sb;
 }