From 9dfdbd9f0c69c6c8005bc41ac602c27023492ee8 Mon Sep 17 00:00:00 2001 From: Roman Kapl Date: Wed, 30 Jan 2019 11:39:54 +0100 Subject: hashtable: fix environment variable corruption Only first previously deleted entry was recognized, leading hsearch_r to think that there was no previously deleted entry. It then conluded that a free entry was found, even if there were no free entries and it overwrote a random entry. This patch makes sure all deleted or free entries are always found and also introduces constants for the 0 and -1 numbers. Unit tests to excersise a simple hash table usage and catch the corruption were added. To trash your environment, simply run this loop: setenv i 0 while true; do setenv v_$i $i setenv v_$i setexpr i $i + 1 done Signed-off-by: Roman Kapl --- test/env/Makefile | 1 + test/env/hashtable.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 126 insertions(+) create mode 100644 test/env/hashtable.c (limited to 'test') diff --git a/test/env/Makefile b/test/env/Makefile index d71a11b..5c8eae3 100644 --- a/test/env/Makefile +++ b/test/env/Makefile @@ -4,3 +4,4 @@ obj-y += cmd_ut_env.o obj-y += attr.o +obj-y += hashtable.o diff --git a/test/env/hashtable.c b/test/env/hashtable.c new file mode 100644 index 0000000..8c87e65 --- /dev/null +++ b/test/env/hashtable.c @@ -0,0 +1,125 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * (C) Copyright 2019 + * Roman Kapl, SYSGO, rka@sysgo.com + */ + +#include +#include +#include +#include +#include +#include + +#define SIZE 32 +#define ITERATIONS 10000 + +static int htab_fill(struct unit_test_state *uts, + struct hsearch_data *htab, size_t size) +{ + size_t i; + ENTRY item; + ENTRY *ritem; + char key[20]; + + for (i = 0; i < size; i++) { + sprintf(key, "%d", (int)i); + item.callback = NULL; + item.data = key; + item.flags = 0; + item.key = key; + ut_asserteq(1, hsearch_r(item, ENTER, &ritem, htab, 0)); + } + + return 0; +} + +static int htab_check_fill(struct unit_test_state *uts, + struct hsearch_data *htab, size_t size) +{ + size_t i; + ENTRY item; + ENTRY *ritem; + char key[20]; + + for (i = 0; i < size; i++) { + sprintf(key, "%d", (int)i); + item.callback = NULL; + item.flags = 0; + item.data = key; + item.key = key; + hsearch_r(item, FIND, &ritem, htab, 0); + ut_assert(ritem); + ut_asserteq_str(key, ritem->key); + ut_asserteq_str(key, ritem->data); + } + + return 0; +} + +static int htab_create_delete(struct unit_test_state *uts, + struct hsearch_data *htab, size_t iterations) +{ + size_t i; + ENTRY item; + ENTRY *ritem; + char key[20]; + + for (i = 0; i < iterations; i++) { + sprintf(key, "cd-%d", (int)i); + item.callback = NULL; + item.flags = 0; + item.data = key; + item.key = key; + hsearch_r(item, ENTER, &ritem, htab, 0); + ritem = NULL; + + hsearch_r(item, FIND, &ritem, htab, 0); + ut_assert(ritem); + ut_asserteq_str(key, ritem->key); + ut_asserteq_str(key, ritem->data); + + ut_asserteq(1, hdelete_r(key, htab, 0)); + } + + return 0; +} + +/* Completely fill up the hash table */ +static int env_test_htab_fill(struct unit_test_state *uts) +{ + struct hsearch_data htab; + + memset(&htab, 0, sizeof(htab)); + ut_asserteq(1, hcreate_r(SIZE, &htab)); + + ut_assertok(htab_fill(uts, &htab, SIZE)); + ut_assertok(htab_check_fill(uts, &htab, SIZE)); + ut_asserteq(SIZE, htab.filled); + + hdestroy_r(&htab); + return 0; +} + +ENV_TEST(env_test_htab_fill, 0); + +/* Fill the hashtable up halfway an repeateadly delete/create elements + * and check for corruption + */ +static int env_test_htab_deletes(struct unit_test_state *uts) +{ + struct hsearch_data htab; + + memset(&htab, 0, sizeof(htab)); + ut_asserteq(1, hcreate_r(SIZE, &htab)); + + ut_assertok(htab_fill(uts, &htab, SIZE / 2)); + ut_assertok(htab_create_delete(uts, &htab, ITERATIONS)); + ut_assertok(htab_check_fill(uts, &htab, SIZE / 2)); + ut_asserteq(SIZE / 2, htab.filled); + + hdestroy_r(&htab); + return 0; +} + +ENV_TEST(env_test_htab_deletes, 0); -- cgit v1.1