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 rka@sysgo.com ---
Note: The hash-table will still degenerate into a linear search in the case above, maybe re-hashing should be done with an appropriate trigger.
lib/hashtable.c | 13 ++++-- test/env/Makefile | 1 + test/env/hashtable.c | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 136 insertions(+), 3 deletions(-) create mode 100644 test/env/hashtable.c
diff --git a/lib/hashtable.c b/lib/hashtable.c index 50ff40a397..0d288d12d9 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -40,6 +40,9 @@ #define CONFIG_ENV_MAX_ENTRIES 512 #endif
+#define USED_FREE 0 +#define USED_DELETED -1 + #include <env_callback.h> #include <env_flags.h> #include <search.h> @@ -303,7 +306,7 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, */ unsigned hval2;
- if (htab->table[idx].used == -1 + if (htab->table[idx].used == USED_DELETED && !first_deleted) first_deleted = idx;
@@ -335,13 +338,17 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval, if (idx == hval) break;
+ if (htab->table[idx].used == USED_DELETED + && !first_deleted) + first_deleted = idx; + /* If entry is found use it. */ ret = _compare_and_overwrite_entry(item, action, retval, htab, flag, hval, idx); if (ret != -1) return ret; } - while (htab->table[idx].used); + while (htab->table[idx].used != USED_FREE); }
/* An empty bucket has been found. */ @@ -433,7 +440,7 @@ static void _hdelete(const char *key, struct hsearch_data *htab, ENTRY *ep, free(ep->data); ep->callback = NULL; ep->flags = 0; - htab->table[idx].used = -1; + htab->table[idx].used = USED_DELETED;
--htab->filled; } diff --git a/test/env/Makefile b/test/env/Makefile index d71a11b6e2..5c8eae31b0 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 0000000000..8c87e65457 --- /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 <common.h> +#include <command.h> +#include <search.h> +#include <stdio.h> +#include <test/env.h> +#include <test/ut.h> + +#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);