diff mbox

[U-Boot,v2] Fix hash table deletion to prevent lost entries

Message ID 4D87D9B0.1080102@logicpd.com
State Accepted
Headers show

Commit Message

Peter Barada March 21, 2011, 11:05 p.m. UTC 
On 03/21/2011 05:48 PM, Wolfgang Denk wrote:
> Dear Peter Barada,
>
> In message <4D385A7F.2070803@logicpd.com> you wrote:
>> On 01/19/2011 03:47 PM, Wolfgang Denk wrote:
>>> Dear Peter Barada,
>>>
>>> In message <4D371208.3090801@logicpd.com> you wrote:
>>>>>> The hash delete code is in error; instead of just removing the deleted
>>>>>> key, it should instead allocate a new hashtable, hash all the keys into
>>>>>> the new table except for the deleted key and then reclaim the old table
>>>>>> (and deleted key).
>>>>> Can you please come up with a patch?
>> From: Peter Barada <peter.barada@logicpd.com>
>> Date: Thu, 20 Jan 2011 10:38:57 -0500
>> Subject: [PATCH] Fix hashtable to properly handle deletion.
>>
>> Use negative used value to mark deleted entry.  Search keeps probing past
>> deleted entries.  Adding an entry uses first deleted entry when it hits
>> end of probe chain.
>>
>> Signed-off-by: Peter Barada <peter.barada@logicpd.com>
> Checkpatch generates a number of errors:
>
> 	[PATCH] Fix hashtable to properly handle deletion.
> 	total: 8 errors, 16 warnings, 66 lines checked
>
> Can you please fix these, and resubmit?
Updated patch attached (Thunderbird munched tabs)...

> Also, do you happen to have a test case that can be used show the
> problem in the existing code, and to test the patch?
No, I don't have a testcase off hand (IIRC hashtable size is dependent on size of u-boot and amount of RAM), from my original email:

In message <4D34C85E.4030408@logicpd.com> you wrote:

> > 
> > After spending an entire day digging into the hash using GDB/BDI on my 
> > ARM board, I've findally figured out that the hash key of "ramdiskimage" 
> > and "preboot" are the same modulus 347, and this is problematic because 
> > on the initial hash import, preboot is placed into the hash first (at 
> > idx 190 since the table is sorted), and then ramdiskimage collides with 
> > preboot causing the 2nd probe (at idx 191) to occur which works fine.  
> > Unfortunately as part of the housecleaning, preboot is deleted and the 
> > environemnt saved.  The delete of preboot removes entry at idx 190 and 
> > the next lookup of ramdiskimage sees that idx 190 is empty and believes 
> > that the ramdiskimage is not in the table ionstead of rehashing to find 
> > it at idx 191.
Hope this helps...

Comments

Wolfgang Denk March 22, 2011, 9:45 p.m. UTC | #1 
Dear Peter Barada,

In message <4D87D9B0.1080102@logicpd.com> you wrote:
>
> > Can you please fix these, and resubmit?
> Updated patch attached (Thunderbird munched tabs)...

Thanks.

> > Also, do you happen to have a test case that can be used show the
> > problem in the existing code, and to test the patch?
> No, I don't have a testcase off hand (IIRC hashtable size is dependent on size of u-boot and amount of RAM), from my original email:

I was able to verify both the problem and that your fix fixes it.
Tested on "qong".

Added a Tested-by: Wolfgang Denk <wd@denx.de>

> From: Peter Barada <peter.barada@logicpd.com>
> Date: Mon, 21 Mar 2011 19:01:57 -0500
> Subject: [PATCH] Fix hashtable to properly handle deletion.
> 
> Use negative used value to mark deleted entry.  Search keeps probing
> past deleted entries.  Adding an entry uses first deleted entry when
> it hits end of probe chain.
> 
> Initially found that "ramdiskimage" and "preboot" collide modulus 347,
> causing "preboot" to be inserted at idx 190, "ramdiskimage" at idx 191.
> Previous to this fix when "preboot" is deleted, "ramdiskimage" is
> orphaned.
> 
> Signed-off-by: Peter Barada <peter.barada@logicpd.com>
> ---
> diff --git a/lib/hashtable.c b/lib/hashtable.c
> index 9f069c0..fcdb53c 100644
> --- a/lib/hashtable.c
> +++ b/lib/hashtable.c

Applied, thanks.

Best regards,

Wolfgang Denk
diff mbox

Patch

From: Peter Barada <peter.barada@logicpd.com>
Date: Mon, 21 Mar 2011 19:01:57 -0500
Subject: [PATCH] Fix hashtable to properly handle deletion.

Use negative used value to mark deleted entry.  Search keeps probing
past deleted entries.  Adding an entry uses first deleted entry when
it hits end of probe chain.

Initially found that "ramdiskimage" and "preboot" collide modulus 347,
causing "preboot" to be inserted at idx 190, "ramdiskimage" at idx 191.
Previous to this fix when "preboot" is deleted, "ramdiskimage" is
orphaned.

Signed-off-by: Peter Barada <peter.barada@logicpd.com>
---
diff --git a/lib/hashtable.c b/lib/hashtable.c
index 9f069c0..fcdb53c 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -65,7 +65,7 @@ 
  * which describes the current status.
  */
 typedef struct _ENTRY {
-	unsigned int used;
+	int used;
 	ENTRY entry;
 } _ENTRY;
 
@@ -152,7 +152,7 @@  void hdestroy_r(struct hsearch_data *htab)
 
 	/* free used memory */
 	for (i = 1; i <= htab->size; ++i) {
-		if (htab->table[i].used) {
+		if (htab->table[i].used > 0) {
 			ENTRY *ep = &htab->table[i].entry;
 
 			free(ep->key);
@@ -209,7 +209,7 @@  int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
 	size_t key_len = strlen(match);
 
 	for (idx = last_idx + 1; idx < htab->size; ++idx) {
-		if (!htab->table[idx].used)
+		if (htab->table[idx].used > 0)
 			continue;
 		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
 			*retval = &htab->table[idx].entry;
@@ -229,6 +229,7 @@  int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 	unsigned int count;
 	unsigned int len = strlen(item.key);
 	unsigned int idx;
+	unsigned int first_deleted = 0;
 
 	/* Compute an value for the given string. Perhaps use a better method. */
 	hval = len;
@@ -256,6 +257,10 @@  int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 		 */
 		unsigned hval2;
 
+		if (htab->table[idx].used == -1
+		    && !first_deleted)
+			first_deleted = idx;
+
 		if (htab->table[idx].used == hval
 		    && strcmp(item.key, htab->table[idx].entry.key) == 0) {
 			/* Overwrite existing value? */
@@ -335,6 +340,9 @@  int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 		 * Create new entry;
 		 * create copies of item.key and item.data
 		 */
+		if (first_deleted)
+			idx = first_deleted;
+
 		htab->table[idx].used = hval;
 		htab->table[idx].entry.key = strdup(item.key);
 		htab->table[idx].entry.data = strdup(item.data);
@@ -387,7 +395,7 @@  int hdelete_r(const char *key, struct hsearch_data *htab)
 
 	free(ep->key);
 	free(ep->data);
-	htab->table[idx].used = 0;
+	htab->table[idx].used = -1;
 
 	--htab->filled;
 
@@ -467,7 +475,7 @@  ssize_t hexport_r(struct hsearch_data *htab, const char sep,
 	 */
 	for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) {
 
-		if (htab->table[i].used) {
+		if (htab->table[i].used > 0) {
 			ENTRY *ep = &htab->table[i].entry;
 
 			list[n++] = ep;
-- 
1.7.0.4