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...