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

[Wolfgang Denk <wd@denx.de>]

Dear =?UTF-8?q?Andreas=20Bie=C3=9Fmann?=,

In message <1285788486-43901-1-git-send-email-andreas.devel@googlemail.com> you wrote:
> This patch adds a new flag to influence the hashtable internal algorithm
> for creation size when importing a buffer.
> 
> When importing a extremely small buffer (e.g. the default_environment)
> the current algorithm cuts down the size of hash table to extremely
> small size. In some cases this may render the device unusable until one
> saves the environment to non volatile memory and restarts the device.

I understand your problem, but I don't agree with the approach.

> -
> +#define H_ALG_SMALL_BUF	2	/* use another algorithm for small buffers to
> +				   calculate hashtable size.
> +				 */

Coding style: incorrect multiline comment.

> -	 * Create new hash table (if needed).  The computation of the hash
> +	 * Create new hash table (if needed). The computation of the hash
>  	 * table size is based on heuristics: in a sample of some 70+
>  	 * existing systems we found an average size of 39+ bytes per entry
>  	 * in the environment (for the whole key=value pair). Assuming a
> @@ -644,16 +644,25 @@ int himport_r(struct hsearch_data *htab,
>  	 * safety margin for any existing environment definitions and still
>  	 * allow for more than enough dynamic additions. Note that the
>  	 * "size" argument is supposed to give the maximum enviroment size
> -	 * (CONFIG_ENV_SIZE).  This heuristics will result in
> +	 * (CONFIG_ENV_SIZE). This heuristics will result in

Please don't mess with the white space, especially when you make it
worse instead of better.

>  	 * 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?

With your configuration, importing a 64 kB environment buffer would
result in 32 k entries in the hash table. 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;

or similar.

What do you think?


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

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