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

From: René Scharfe <l.s.r@web.de>
Date: Oct 23, 2016, 17:57 UTC
Message-ID: <fb816dd5-8fb9-c6a6-2ec2-9ea4dddfdb26@web.de>
In-Reply-To: <20161023091146.p2kmqvgwxdf77dnn@sigill.intra.peff.net>

Am 23.10.2016 um 11:11 schrieb Jeff King:

Show 14 quoted lines

> On Sun, Oct 23, 2016 at 11:00:48AM +0200, René Scharfe wrote:
>
>> Overflow is defined for unsigned integers, but not for signed ones.
>> Make the ring buffer index in sha1_to_hex() unsigned to be on the
>> safe side.
>>
>> Signed-off-by: Rene Scharfe <l.s.r@web.de>
>> ---
>> Hard to trigger, but probably even harder to diagnose once someone
>> somehow manages to do it on some uncommon architecture.
>
> Indeed. If we are worried about overflow, we would also want to assume
> that it wraps at a multiple of 4, but that is probably a sane
> assumption.

Hmm, I can't think of a way to violate this assumption except with unsigned integers that are only a single bit wide. That would be a weird machine. Are there other possibilities?

Show 27 quoted lines

>> diff --git a/hex.c b/hex.c
>> index ab2610e..8c6c189 100644
>> --- a/hex.c
>> +++ b/hex.c
>> @@ -76,7 +76,7 @@ char *oid_to_hex_r(char *buffer, const struct object_id *oid)
>>
>>  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);
>>  }
>
> I wonder if just truncating bufno would be conceptually simpler (albeit
> longer):
>
>   bufno++;
>   bufno &= 3;
>   return sha1_to_hex_r(hexbuffer[bufno], sha1);
>
> You could also write the second line like:
>
>   bufno %= ARRAY_SIZE(hexbuffer);
>
> which is less magical (right now the set of buffers must be a power of
> 2). I expect the compiler could turn that into a bitmask itself.

Expelling magic is a good idea. And indeed, at least gcc, clang and icc on x86-64 are smart enough to use an AND instead of dividing (https://godbolt.org/g/rFPpzF).

But gcc also adds a sign extension (cltq/cdqe) if we store the truncated value, unlike the other two compilers. I don't see why -- the bit mask operation enforces a value between 0 and 3 (inclusive) and the upper bits of eax are zeroed automatically, so the cltq is effectively a noop.

Using size_t gets us rid of the extra instruction and is the right type anyway. It would suffice on its own, hmm..

> I'm fine with any of the options. I guess you'd want a similar patch for
> find_unique_abbrev on top of jk/no-looking-at-dotgit-outside-repo.

Actually I'd want you to want to amend your series yourself. ;) Maybe I can convince Coccinelle to handle that issue for us.

And there's also path.c::get_pathname(). That's enough cases to justify adding a macro, I'd say:

---
  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 05ecb88..8bb4918 100644
--- a/cache.h
+++ b/cache.h
@@ -555,6 +555,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 ab2610e..5e711b9 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 a8e7295..60dba6a 100644
--- a/path.c
+++ b/path.c
@@ -24,8 +24,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;
  }

-- 
2.10.1