From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Barada Date: Mon, 21 Mar 2011 19:05:20 -0400 Subject: [U-Boot] [Patch v2] Fix hash table deletion to prevent lost entries In-Reply-To: <20110321214823.EA538151A99@gemini.denx.de> References: <4D34C85E.4030408@logicpd.com> <20110119083223.DEA112FC@gemini.denx.de> <4D371208.3090801@logicpd.com> <20110119204755.B8D0DD301BF@gemini.denx.de> <4D385A7F.2070803@logicpd.com> <20110321214823.EA538151A99@gemini.denx.de> Message-ID: <4D87D9B0.1080102@logicpd.com> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: u-boot@lists.denx.de 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 >> 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 > 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... -- 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