[U-Boot] [PATCH] lib/hashtable.c: add algorithm for small buffer import

[Andreas Bießmann]

(resent to list)

Dear Wolfgang Denk,

Am 29.09.2010 um 22:01 schrieb Wolfgang Denk:

> Dear =?UTF-8?q?Andreas=20Bie=C3=9Fmann?=,
> 
> In message <1285788486-43901-1-git-send-email-andreas.devel at googlemail.com> you wrote:

[snip]

>> 	 * unreasonably large numbers (and thus memory footprint) for
>> 	 * big flash environments (>8,000 entries for 64 KB
>> 	 * envrionment size), so we clip it to a reasonable value
>> 	 * (which can be overwritten in the board config file if
>> 	 * needed).
>> +	 *
>> +	 * But in some cases it is necessary to have another algorithm to
>> +	 * get the size of hash table. Especially for extremely small buffers
>> +	 * there is the flag H_ALG_SMALL_BUF which takes another factor to
>> +	 * calculate the hash table size.
>> 	 */
>> 
>> 	if (!htab->table) {
>> -		int nent = size / 8;
>> +		int nent;
>> +		if (flag & H_ALG_SMALL_BUF)
>> +			nent = size / 2;
>> +		else
>> +			nent = size / 8;
> 
> Did you read the comment above?

Yes, I did.

> With your configuration, importing a 64 kB environment buffer would
> result in 32 k entries in the hash table.

Well therefore we have another 'algorithm' implemented to cope with this. The flag H_ALG_SMALL_BUF should be set especially when importing a small buffer. Anyhow the maximum limit some lines below will never be exceeded.

> This obviously makes no
> sense.
> 
> I think we should rather make sure that a certain minimum of entries
> will always be available, for exmaple something like this:
> 
> 		int nent = 64 + size / 8;

This sounds also good but why do not calculate as before and after that check some (maybe definable) borders?

How about:
int nent = size / 8;
if (nent < CONFIG_ENV_MIN_ENTRIES)
 nent = CONFIG_ENV_MIN_ENTRIES;
...

> or similar.
> 
> What do you think?

How about my suggestion?

> [Actually I think the current setting (size / 8) is _way_ too
> conservative in most cases. eventually we'd really be better off with
> something like "64 + size / 32" or so. I'm interested in feedback -
> the statistics I have about environment settings (number of entries
> versus total size) is unfortunately a bit limited, and since most of
> the boards come from the same hands they follow a common style, which
> eventually is not what other users do.]

Well in most cases the environment needs a static size. The actual size of environment has (in my view) no/small connection to space for environment in NV memory. In most cases the space reserved for environment is way to big cause of sector boundaries. Therefore I think it would meet the needs when we have one (configurable) size for hash table without the calculation.

regards

Andreas Bießmann

> Best regards,
> 
> Wolfgang Denk
> 
> -- 
> DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
> HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
> Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
> As far as we know, our computer has never had an undetected error.
> 		                                           -- Weisert