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

[Peter Barada]

On 03/21/2011 05:48 PM, Wolfgang Denk wrote:
> Dear Peter Barada,
>
> In message <4D385A7F.2070803 at logicpd.com> you wrote:
>> On 01/19/2011 03:47 PM, Wolfgang Denk wrote:
>>> Dear Peter Barada,
>>>
>>> In message <4D371208.3090801 at 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 at 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 at 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 at 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...

-- 
Peter Barada
peter.barada at logicpd.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: u-boot-hashtable.patch
Type: text/x-patch
Size: 2901 bytes
Desc: not available
Url : http://lists.denx.de/pipermail/u-boot/attachments/20110321/6df2f23f/attachment.bin