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 --- lib/hashtable.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'lib/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 #include #include @@ -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; } -- cgit