[U-Boot] [PATCH] lib/hashtable.c: add algorithm for small buffer import
Wolfgang Denk
wd at denx.de
Wed Sep 29 22:01:31 CEST 2010
Dear =?UTF-8?q?Andreas=20Bie=C3=9Fmann?=,
In message <1285788486-43901-1-git-send-email-andreas.devel at 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
More information about the U-Boot
mailing list