hashtable: fix environment variable corruption
PATCH 1/1 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
---
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
lib/hashtable.c +10 -3
@@ -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; }
test/env/Makefile +1 -0
@@ -4,3 +4,4 @@ obj-y += cmd_ut_env.o obj-y += attr.o +obj-y += hashtable.o
test/env/hashtable.c new file +125 -0
125 lines not on this page · raw message
Signature · 1 line
2.11.0
Quoted 11 lines · Roman Kapl
Only first previously deleted entry was recognized, leading
hsearch_rto 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:
Quoted 8 lines
setenv i 0
while true; do
setenv v_$i $i
setenv v_$i
setexpr i $i + 1
doneSigned-off-by Roman Kapl <[email protected]>
Applied to u-boot/master, thanks!
Signature · 8 lines
Tom -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 819 bytes Desc: not available URL: <http://lists.denx.de/pipermail/u-boot/attachments/20190210/9b659d78/attachment.sig>