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

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