From patchwork Mon Mar 21 23:05:20 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Barada X-Patchwork-Id: 87847 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from theia.denx.de (theia.denx.de [85.214.87.163]) by ozlabs.org (Postfix) with ESMTP id E4717B6F73 for ; Tue, 22 Mar 2011 10:15:12 +1100 (EST) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 4F0F0280A8; Tue, 22 Mar 2011 00:15:11 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1sUgQm6Ky9SD; Tue, 22 Mar 2011 00:15:11 +0100 (CET) Received: from theia.denx.de (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id ED64F280A9; Tue, 22 Mar 2011 00:15:08 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 1D93A280A9 for ; Tue, 22 Mar 2011 00:15:07 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at theia.denx.de Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ql2Wd24BGbr6 for ; Tue, 22 Mar 2011 00:15:06 +0100 (CET) X-Greylist: delayed 585 seconds by postgrey-1.27 at theia; Tue, 22 Mar 2011 00:15:01 CET X-policyd-weight: NOT_IN_SBL_XBL_SPAMHAUS=-1.5 NOT_IN_SPAMCOP=-1.5 NOT_IN_BL_NJABL=-1.5 (only DNSBL check requested) Received: from edprlnx06.logicpd.com (unknown [174.46.170.154]) by theia.denx.de (Postfix) with ESMTP id 0DB1C280A8 for ; Tue, 22 Mar 2011 00:15:01 +0100 (CET) Received: from [10.1.249.3] (unknown [10.1.249.3]) by edprlnx06.logicpd.com (Postfix) with ESMTP id ADDA2600095; Mon, 21 Mar 2011 18:05:14 -0500 (CDT) Message-ID: <4D87D9B0.1080102@logicpd.com> Date: Mon, 21 Mar 2011 19:05:20 -0400 From: Peter Barada User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.14) Gecko/20110223 Thunderbird/3.1.8 MIME-Version: 1.0 To: Wolfgang Denk 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> In-Reply-To: <20110321214823.EA538151A99@gemini.denx.de> Cc: U-Boot mailing list Subject: Re: [U-Boot] [Patch v2] Fix hash table deletion to prevent lost entries X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.9 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: u-boot-bounces@lists.denx.de Errors-To: u-boot-bounces@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... From: Peter Barada 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 --- 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