threads / patch / 47846

patch, 6 partsminor test-hashmap fixes

Subject: [PATCH 0/6] minor test-hashmap fixes

## tl;dr

11 messages between Feb 14, 2018 and Feb 14, 2018. Diffs are folded; open one to read it.

replies: 10people: 4as markdown or json

Jeff King· Feb 14, 2018, 18:03 UTC · lore
This series started with me fixing the sizeof() mismatch discussed in
  https://public-inbox.org/git/20180214164628.GA907@sigill.intra.peff.net/

but I found a number of minor irritations. Most of them are cosmetic in practice, but I think it's important for test-helper code like this to model best practices, since people are likely to use it as a reference.

  [1/6]: test-hashmap: use ALLOC_ARRAY rather than bare malloc
  [2/6]: test-hashmap: check allocation computation for overflow
  [3/6]: test-hashmap: use xsnprintf rather than snprintf
  [4/6]: test-hashmap: use strbuf_getline rather than fgets
  [5/6]: test-hashmap: simplify alloc_test_entry
  [6/6]: test-hashmap: use "unsigned int" for hash storage
 t/helper/test-hashmap.c | 53 +++++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 26 deletions(-)
-Peff
Jeff King· Feb 14, 2018, 18:05 UTC · re: Jeff King · lore

[PATCH 1/6] test-hashmap: use ALLOC_ARRAY rather than bare malloc

These two array allocations have several minor flaws:
  - they use bare malloc, rather than our error-checking
    xmalloc
  - they do a bare multiplication to determine the total
    size (which in theory can overflow, though in this case
    the sizes are all constants)
  - they use sizeof(type), but the type in the second one
    doesn't match the actual array (though it's "int" versus
    "unsigned int", which are guaranteed by C99 to have the
    same size)

None of these are likely to be problems in practice, and this is just a test helper. But since people often look at test helpers as reference code, we should do our best to model the recommended techniques.

Switching to ALLOC_ARRAY fixes all three.
Signed-off-by: Jeff King <peff@peff.net>
---
The sizeof() thing came from Code AI's original email. I'm happy to
include a Reported-by there, but I wasn't sure of the correct entity to
credit. :)
 t/helper/test-hashmap.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
Show changes to t/helper/test-hashmap.c +2 −2
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 1145d51671..b36886bf35 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -85,8 +85,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 	unsigned int *hashes;
 	unsigned int i, j;
 
-	entries = malloc(TEST_SIZE * sizeof(struct test_entry *));
-	hashes = malloc(TEST_SIZE * sizeof(int));
+	ALLOC_ARRAY(entries, TEST_SIZE);
+	ALLOC_ARRAY(hashes, TEST_SIZE);
 	for (i = 0; i < TEST_SIZE; i++) {
 		snprintf(buf, sizeof(buf), "%i", i);
 		entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0);

-- 
2.16.1.464.gc4bae515b7
Code AI· Feb 14, 2018, 18:47 UTC · re: Jeff King · lore

Re: [PATCH 1/6] test-hashmap: use ALLOC_ARRAY rather than bare malloc

Jeff,

Thanks for the feedback! Most of our users find CodeAI's fixes useful, even if they are not exactly correct. However, we are constantly working on improving the quality of CodeAI's fixes. The more people who use it, the more we can improve it. We would love for you to try the system directly by visiting mycode.ai. Its free for open source users, and you can easily login using your GitHub account. Also, you may attribute the allocator sizeof() issue to C0deAi. That's the Github account used by the tool to submit pull requests.

-Ben
On Wed, Feb 14, 2018 at 1:05 PM, Jeff King <peff@peff.net> wrote:
Show 48 quoted lines
> These two array allocations have several minor flaws:
>
>   - they use bare malloc, rather than our error-checking
>     xmalloc
>
>   - they do a bare multiplication to determine the total
>     size (which in theory can overflow, though in this case
>     the sizes are all constants)
>
>   - they use sizeof(type), but the type in the second one
>     doesn't match the actual array (though it's "int" versus
>     "unsigned int", which are guaranteed by C99 to have the
>     same size)
>
> None of these are likely to be problems in practice, and
> this is just a test helper. But since people often look at
> test helpers as reference code, we should do our best to
> model the recommended techniques.
>
> Switching to ALLOC_ARRAY fixes all three.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> The sizeof() thing came from Code AI's original email. I'm happy to
> include a Reported-by there, but I wasn't sure of the correct entity to
> credit. :)
>
>  t/helper/test-hashmap.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
> index 1145d51671..b36886bf35 100644
> --- a/t/helper/test-hashmap.c
> +++ b/t/helper/test-hashmap.c
> @@ -85,8 +85,8 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
>         unsigned int *hashes;
>         unsigned int i, j;
>
> -       entries = malloc(TEST_SIZE * sizeof(struct test_entry *));
> -       hashes = malloc(TEST_SIZE * sizeof(int));
> +       ALLOC_ARRAY(entries, TEST_SIZE);
> +       ALLOC_ARRAY(hashes, TEST_SIZE);
>         for (i = 0; i < TEST_SIZE; i++) {
>                 snprintf(buf, sizeof(buf), "%i", i);
>                 entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0);
> --
> 2.16.1.464.gc4bae515b7
>
-- 
Sincerely,

CodeAI Tech Support Team
Jeff King· Feb 14, 2018, 18:06 UTC · re: Jeff King · lore

[PATCH 2/6] test-hashmap: check allocation computation for overflow

When we allocate the test_entry flex-struct, we have to add up all of the elements that go into the flex array. If these were to overflow a size_t, this would allocate a too-small buffer, which we would then overflow in our memcpy steps.

Since this is just a test-helper, it probably doesn't matter in practice, but we should model the correct technique by using the st_add() macros.

Unfortunately, we cannot use the FLEX_ALLOC() macros here, because we are stuffing two different buffers into a single flex array.

While we're here, let's also swap out "malloc" for our error-checking "xmalloc", and use the preferred "sizeof(*var)" instead of "sizeof(type)".

Signed-off-by: Jeff King <peff@peff.net>
---
 t/helper/test-hashmap.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
Show changes to t/helper/test-hashmap.c +1 −2
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index b36886bf35..2100877c2b 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -32,8 +32,7 @@ static int test_entry_cmp(const void *cmp_data,
 static struct test_entry *alloc_test_entry(int hash, char *key, int klen,
 		char *value, int vlen)
 {
-	struct test_entry *entry = malloc(sizeof(struct test_entry) + klen
-			+ vlen + 2);
+	struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
 	hashmap_entry_init(entry, hash);
 	memcpy(entry->key, key, klen + 1);
 	memcpy(entry->key + klen + 1, value, vlen + 1);

-- 
2.16.1.464.gc4bae515b7
Jeff King· Feb 14, 2018, 18:06 UTC · re: Jeff King · lore

[PATCH 3/6] test-hashmap: use xsnprintf rather than snprintf

In general, using a bare snprintf can truncate the resulting buffer, leading to confusing results. In this case we know that our buffer is sized large enough to accommodate our loop, so there's no bug. However, we should use xsnprintf() to document (and check) that assumption, and to model good practice to people reading the code.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/helper/test-hashmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Show changes to t/helper/test-hashmap.c +1 −1
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 2100877c2b..28b913fbd6 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -87,7 +87,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 	ALLOC_ARRAY(entries, TEST_SIZE);
 	ALLOC_ARRAY(hashes, TEST_SIZE);
 	for (i = 0; i < TEST_SIZE; i++) {
-		snprintf(buf, sizeof(buf), "%i", i);
+		xsnprintf(buf, sizeof(buf), "%i", i);
 		entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0);
 		hashes[i] = hash(method, i, entries[i]->key);
 	}

-- 
2.16.1.464.gc4bae515b7
Jeff King· Feb 14, 2018, 18:07 UTC · re: Jeff King · lore

[PATCH 4/6] test-hashmap: use strbuf_getline rather than fgets

Using fgets() with a fixed-size buffer can lead to lines being accidentally split across two calls if they are larger than the buffer size.

As this is just a test helper, this is unlikely to be a problem in practice. But since people may look at test helpers as reference code, it's a good idea for them to model the preferred behavior.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/helper/test-hashmap.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
Show changes to t/helper/test-hashmap.c +5 −3
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 28b913fbd6..15fc4e372f 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -1,5 +1,6 @@
 #include "git-compat-util.h"
 #include "hashmap.h"
+#include "strbuf.h"
 
 struct test_entry
 {
@@ -143,7 +144,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
  */
 int cmd_main(int argc, const char **argv)
 {
-	char line[1024];
+	struct strbuf line = STRBUF_INIT;
 	struct hashmap map;
 	int icase;
 
@@ -152,13 +153,13 @@ int cmd_main(int argc, const char **argv)
 	hashmap_init(&map, test_entry_cmp, &icase, 0);
 
 	/* process commands from stdin */
-	while (fgets(line, sizeof(line), stdin)) {
+	while (strbuf_getline(&line, stdin) != EOF) {
 		char *cmd, *p1 = NULL, *p2 = NULL;
 		int l1 = 0, l2 = 0, hash = 0;
 		struct test_entry *entry;
 
 		/* break line into command and up to two parameters */
-		cmd = strtok(line, DELIM);
+		cmd = strtok(line.buf, DELIM);
 		/* ignore empty lines */
 		if (!cmd || *cmd == '#')
 			continue;
@@ -262,6 +263,7 @@ int cmd_main(int argc, const char **argv)
 		}
 	}
 
+	strbuf_release(&line);
 	hashmap_free(&map, 1);
 	return 0;
 }

-- 
2.16.1.464.gc4bae515b7
Jeff King· Feb 14, 2018, 18:08 UTC · re: Jeff King · lore

[PATCH 5/6] test-hashmap: simplify alloc_test_entry

This function takes two ptr/len pairs, which implies that they can be arbitrary buffers. But internally, it assumes that each "ptr" is NUL-terminated at "len" (because we memcpy an extra byte to pick up the NUL terminator).

In practice this works because each caller only ever passes strlen(ptr) as the length. But let's drop the "len" parameters to make our expectations clear.

Note that we can get rid of the "l1" and "l2" variables from cmd_main() as a further cleanup, since they are now mostly used to check whether the p1 and p2 arguments are present (technically the length parameters conflated NULL with the empty string, which we no longer do, but I think that is actually an improvement).

Signed-off-by: Jeff King <peff@peff.net>
---
 t/helper/test-hashmap.c | 35 +++++++++++++++++------------------
 1 file changed, 17 insertions(+), 18 deletions(-)
Show changes to t/helper/test-hashmap.c +17 −18
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 15fc4e372f..56efff36e8 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -30,9 +30,10 @@ static int test_entry_cmp(const void *cmp_data,
 		return strcmp(e1->key, key ? key : e2->key);
 }
 
-static struct test_entry *alloc_test_entry(int hash, char *key, int klen,
-		char *value, int vlen)
+static struct test_entry *alloc_test_entry(int hash, char *key, char *value)
 {
+	size_t klen = strlen(key);
+	size_t vlen = strlen(value);
 	struct test_entry *entry = xmalloc(st_add4(sizeof(*entry), klen, vlen, 2));
 	hashmap_entry_init(entry, hash);
 	memcpy(entry->key, key, klen + 1);
@@ -89,7 +90,7 @@ static void perf_hashmap(unsigned int method, unsigned int rounds)
 	ALLOC_ARRAY(hashes, TEST_SIZE);
 	for (i = 0; i < TEST_SIZE; i++) {
 		xsnprintf(buf, sizeof(buf), "%i", i);
-		entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0);
+		entries[i] = alloc_test_entry(0, buf, "");
 		hashes[i] = hash(method, i, entries[i]->key);
 	}
 
@@ -155,7 +156,7 @@ int cmd_main(int argc, const char **argv)
 	/* process commands from stdin */
 	while (strbuf_getline(&line, stdin) != EOF) {
 		char *cmd, *p1 = NULL, *p2 = NULL;
-		int l1 = 0, l2 = 0, hash = 0;
+		int hash = 0;
 		struct test_entry *entry;
 
 		/* break line into command and up to two parameters */
@@ -166,31 +167,29 @@ int cmd_main(int argc, const char **argv)
 
 		p1 = strtok(NULL, DELIM);
 		if (p1) {
-			l1 = strlen(p1);
 			hash = icase ? strihash(p1) : strhash(p1);
 			p2 = strtok(NULL, DELIM);
-			if (p2)
-				l2 = strlen(p2);
 		}
 
-		if (!strcmp("hash", cmd) && l1) {
+		if (!strcmp("hash", cmd) && p1) {
 
 			/* print results of different hash functions */
-			printf("%u %u %u %u\n", strhash(p1), memhash(p1, l1),
-					strihash(p1), memihash(p1, l1));
+			printf("%u %u %u %u\n",
+			       strhash(p1), memhash(p1, strlen(p1)),
+			       strihash(p1), memihash(p1, strlen(p1)));
 
-		} else if (!strcmp("add", cmd) && l1 && l2) {
+		} else if (!strcmp("add", cmd) && p1 && p2) {
 
 			/* create entry with key = p1, value = p2 */
-			entry = alloc_test_entry(hash, p1, l1, p2, l2);
+			entry = alloc_test_entry(hash, p1, p2);
 
 			/* add to hashmap */
 			hashmap_add(&map, entry);
 
-		} else if (!strcmp("put", cmd) && l1 && l2) {
+		} else if (!strcmp("put", cmd) && p1 && p2) {
 
 			/* create entry with key = p1, value = p2 */
-			entry = alloc_test_entry(hash, p1, l1, p2, l2);
+			entry = alloc_test_entry(hash, p1, p2);
 
 			/* add / replace entry */
 			entry = hashmap_put(&map, entry);
@@ -199,7 +198,7 @@ int cmd_main(int argc, const char **argv)
 			puts(entry ? get_value(entry) : "NULL");
 			free(entry);
 
-		} else if (!strcmp("get", cmd) && l1) {
+		} else if (!strcmp("get", cmd) && p1) {
 
 			/* lookup entry in hashmap */
 			entry = hashmap_get_from_hash(&map, hash, p1);
@@ -212,7 +211,7 @@ int cmd_main(int argc, const char **argv)
 				entry = hashmap_get_next(&map, entry);
 			}
 
-		} else if (!strcmp("remove", cmd) && l1) {
+		} else if (!strcmp("remove", cmd) && p1) {
 
 			/* setup static key */
 			struct hashmap_entry key;
@@ -238,7 +237,7 @@ int cmd_main(int argc, const char **argv)
 			printf("%u %u\n", map.tablesize,
 			       hashmap_get_size(&map));
 
-		} else if (!strcmp("intern", cmd) && l1) {
+		} else if (!strcmp("intern", cmd) && p1) {
 
 			/* test that strintern works */
 			const char *i1 = strintern(p1);
@@ -252,7 +251,7 @@ int cmd_main(int argc, const char **argv)
 			else
 				printf("%s\n", i1);
 
-		} else if (!strcmp("perfhashmap", cmd) && l1 && l2) {
+		} else if (!strcmp("perfhashmap", cmd) && p1 && p2) {
 
 			perf_hashmap(atoi(p1), atoi(p2));
 

-- 
2.16.1.464.gc4bae515b7
Junio C Hamano· Feb 14, 2018, 19:01 UTC · re: Jeff King · lore

Re: [PATCH 5/6] test-hashmap: simplify alloc_test_entry

Jeff King <peff@peff.net> writes:
> This function takes two ptr/len pairs, which implies that
> they can be arbitrary buffers. But internally, it assumes
> that each "ptr" is NUL-terminated at "len" (because we
> memcpy an extra byte to pick up the NUL terminator).

Makes quite a lot of sense. In addition, get_value() assumes that the key cannot have NUL in it, so the use of counted string in alloc_test_entry() serves no purpose other than to confuse the readers ;-)

> Note that we can get rid of the "l1" and "l2" variables from
> cmd_main() as a further cleanup, since they are now mostly

Made me wonder if this "we can" is "we could if we wanted to in the future although we do not go that far in this patch", but it turns out that this is also done, and I think it is a good clean-up.

Jeff King· Feb 14, 2018, 18:08 UTC · re: Jeff King · lore

[PATCH 6/6] test-hashmap: use "unsigned int" for hash storage

The hashmap API always use an unsigned value for storing and comparing hashes. Whereas this test code uses "int". This works out in practice since one can typically round-trip between "int" and "unsigned int". But since this is essentially reference code for the hashmap API, we should model using the correct types.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/helper/test-hashmap.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
Show changes to t/helper/test-hashmap.c +3 −2
diff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c
index 56efff36e8..9ae9281c07 100644
--- a/t/helper/test-hashmap.c
+++ b/t/helper/test-hashmap.c
@@ -30,7 +30,8 @@ static int test_entry_cmp(const void *cmp_data,
 		return strcmp(e1->key, key ? key : e2->key);
 }
 
-static struct test_entry *alloc_test_entry(int hash, char *key, char *value)
+static struct test_entry *alloc_test_entry(unsigned int hash,
+					   char *key, char *value)
 {
 	size_t klen = strlen(key);
 	size_t vlen = strlen(value);
@@ -156,7 +157,7 @@ int cmd_main(int argc, const char **argv)
 	/* process commands from stdin */
 	while (strbuf_getline(&line, stdin) != EOF) {
 		char *cmd, *p1 = NULL, *p2 = NULL;
-		int hash = 0;
+		unsigned int hash = 0;
 		struct test_entry *entry;
 
 		/* break line into command and up to two parameters */

-- 
2.16.1.464.gc4bae515b7
Stefan Beller· Feb 14, 2018, 18:41 UTC · re: Jeff King · lore

Re: [PATCH 0/6] minor test-hashmap fixes

On Wed, Feb 14, 2018 at 10:03 AM, Jeff King <peff@peff.net> wrote:
Show 15 quoted lines
> This series started with me fixing the sizeof() mismatch discussed in
>
>   https://public-inbox.org/git/20180214164628.GA907@sigill.intra.peff.net/
>
> but I found a number of minor irritations. Most of them are cosmetic in
> practice, but I think it's important for test-helper code like this to
> model best practices, since people are likely to use it as a reference.
>
>   [1/6]: test-hashmap: use ALLOC_ARRAY rather than bare malloc
>   [2/6]: test-hashmap: check allocation computation for overflow
>   [3/6]: test-hashmap: use xsnprintf rather than snprintf
>   [4/6]: test-hashmap: use strbuf_getline rather than fgets
>   [5/6]: test-hashmap: simplify alloc_test_entry
>   [6/6]: test-hashmap: use "unsigned int" for hash storage
>
The whole series is
Reviewed-by: Stefan Beller <sbeller@google.com>

Thanks for improving the example code. I have lost track of the hashmap improvements lately, but with such a good test helper, we could reduce the amount of commented code in hashmap.h and just link to the test helper? (as an extra step after this series, I thought we already had that)

Thanks, Stefan

Jeff King· Feb 14, 2018, 18:48 UTC · re: Stefan Beller · lore

Re: [PATCH 0/6] minor test-hashmap fixes

On Wed, Feb 14, 2018 at 10:41:35AM -0800, Stefan Beller wrote:
> I have lost track of the hashmap improvements lately, but with
> such a good test helper, we could reduce the amount of
> commented code in hashmap.h and just link to the test helper?
> (as an extra step after this series, I thought we already had that)

Yeah, the example code in hashmap.h looks to be more or less the same thing as what's here (it maps a long to a value, which simplifies the FLEX_ARRAY bits, but I think it serves equally well as a reference).

I'd also be fine with drastically simplifying the example in hashmap.h, and letting test-hashmap serve as a more fleshed-out example (we don't need to see the main and scanf bits there).

-Peff

← back to recent threads