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

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

[Andreas Bießmann]

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.

Signed-off-by: Andreas Bie?mann <andreas.devel@googlemail.com>
---
In my case i had to import 5 key/value pairs from default_environment which
was about 30 byte buffer. These key/values fit in my hash table but the
ethernet driver would like to setenv() another key/value which returned with
error.

 common/env_common.c |    2 +-
 include/search.h    |    4 +++-
 lib/hashtable.c     |   15 ++++++++++++---
 3 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/common/env_common.c b/common/env_common.c
index a415ef8..bd6eae4 100644
--- a/common/env_common.c
+++ b/common/env_common.c
@@ -188,7 +188,7 @@ void set_default_env(const char *s)
 	}
 
 	if (himport((char *)default_environment,
-		    sizeof(default_environment), '\0', 0) == 0) {
+		    sizeof(default_environment), '\0', H_ALG_SMALL_BUF) == 0) {
 		error("Environment import failed: errno = %d\n", errno);
 	}
 	gd->flags |= GD_FLG_ENV_READY;
diff --git a/include/search.h b/include/search.h
index fccc757..e6cd189 100644
--- a/include/search.h
+++ b/include/search.h
@@ -102,5 +102,7 @@ extern int himport_r(struct hsearch_data *__htab,
 
 /* Flags for himport() / himport_r() */
 #define	H_NOCLEAR	1	/* do not clear hash table before importing */
-
+#define H_ALG_SMALL_BUF	2	/* use another algorithm for small buffers to
+				   calculate hashtable size.
+				 */
 #endif /* search.h */
diff --git a/lib/hashtable.c b/lib/hashtable.c
index b747f1f..82a4d00 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -636,7 +636,7 @@ int himport_r(struct hsearch_data *htab,
 	}
 
 	/*
-	 * 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
 	 * 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;
 
 		if (nent > CONFIG_ENV_MAX_ENTRIES)
 			nent = CONFIG_ENV_MAX_ENTRIES;
-- 
1.7.3

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

[Wolfgang Denk]

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

[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@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

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

[Wolfgang Denk]

Dear =?iso-8859-1?Q?Andreas_Bie=DFmann?=,

In message <8AE7E072-8389-49CA-B6C7-6C15C1877625@googlemail.com> you wrote:
> 
> > 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.

Well, you were talking about your defualt environment settings only.
How big is the envrionment in your persistent storage (flash)? I bet
it's at least several KB, resulting in thousands of 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;
> 
> 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;

I cannot really proof it, but I am pretty much convinced that we
should start with a non-zero constant and rather use a less steep
increase.

> 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

This is not true. Sector sizes affect only the CONFIG_ENV_SECT_SIZE
settings, while the environment size is determined by CONFIG_ENV_SIZE
which usually is MUCH smaller.

Example: "TQM5200.h":

	#define CONFIG_ENV_SIZE         0x4000  /* 16 k - keep small for fast booting */
	...
	#define CONFIG_ENV_SECT_SIZE    0x40000

> it would meet the needs when we have one (configurable) size for hash
> table without the calculation.

I disagree. Have a look at the "env import" and "env export" commands
and think about what you can do with these - essentially they lift the
fix connection to a pre-configured environment storage. Even if you
have just 2 or 4 KiB environment settings in flash, you can now just
load a file (over network, from USB stick or SDCard etc.) which may
contain tons of commands and macro definitions.

Even if you don't have such usage in mind, I do not want to make this
impossible by a too limited design.

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
Too many people are ready to carry the stool when the piano needs  to
be moved.

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

[Andreas Bießmann]

Dear Wolfgang Denk,

Am 29.09.2010 um 23:02 schrieb Wolfgang Denk:

> Dear =?iso-8859-1?Q?Andreas_Bie=DFmann?=,
> 
> In message <8AE7E072-8389-49CA-B6C7-6C15C1877625@googlemail.com> you wrote:
>> 
>>> 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.
> 
> Well, you were talking about your defualt environment settings only.

Yes I do. This was the only place I used the newly defined flag for different hash table size calculation. The main problem here is the extremely small buffer of default_environment which will calculate a way to small hash table.

> How big is the envrionment in your persistent storage (flash)? I bet
> it's at least several KB, resulting in thousands of entries in the
> hash table.

Yes, I understood this. The main aim of my patch was to introduce a switch between two fixed factors. Think about y = x * k with two hard coded k1 and k2 to switch between.

I'd like to make a cut here. My first suggestion has limitations and will bring more patches like this in future. Lets make it more flexible. Also the current implementation has limitations which should be changed.

>>> 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;
> 
> I cannot really proof it, but I am pretty much convinced that we
> should start with a non-zero constant and rather use a less steep
> increase.
> 
>> 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
> 
> This is not true. Sector sizes affect only the CONFIG_ENV_SECT_SIZE
> settings, while the environment size is determined by CONFIG_ENV_SIZE
> which usually is MUCH smaller.

Well this is new information for me. Most boards I worked with only defined CONFIG_ENV_SIZE which was naturally the size of one sector in NOR flash.

> Example: "TQM5200.h":
> 
> 	#define CONFIG_ENV_SIZE         0x4000  /* 16 k - keep small for fast booting */
> 	...
> 	#define CONFIG_ENV_SECT_SIZE    0x40000
> 
>> it would meet the needs when we have one (configurable) size for hash
>> table without the calculation.
> 
> I disagree. Have a look at the "env import" and "env export" commands
> and think about what you can do with these - essentially they lift the
> fix connection to a pre-configured environment storage. Even if you
> have just 2 or 4 KiB environment settings in flash, you can now just
> load a file (over network, from USB stick or SDCard etc.) which may
> contain tons of commands and macro definitions.

Ok this is a quite cool feature I had really not in mind. 

> Even if you don't have such usage in mind, I do not want to make this
> impossible by a too limited design.

Therefore it is necessary to have a connection between buffer size to import/parse and resulting hash table for environment. Another requirement is a reasonable fixed part. This is needed for rare cases where a small buffer is imported (aka default_environment) which will be expanded later on by setenv().

In my opinion these factors should be definable by user at compile time (but with realistic default values if not defined by user). Therefore the behavior of the hash table size algorithm can be optimized for different use cases. I think about a user defining a lot of keys with small sized values and another user defining only some keys with very large sized values. It is really difficult to find factors for the calculation which meet all users needs.

regards

Andreas Bie?mann

[U-Boot] [PATCH v2] lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

[Andreas Bießmann]

This patch adds a new config parameter for adjusting the calculation of
hash table size when importing a buffer.

When importing a extremely small buffer (e.g. the default_environment)
the old calculation generated a hash table which could hold at most the
buffer content but no more entires.

The new calculation add a fixed number of entries to the result to fit
better for small import buffers. This amount may be configured by the
user in board file to adjust the behaviour.

Signed-off-by: Andreas Bie?mann <andreas.devel@googlemail.com>
---
v2: implement as suggested by Wolfgang

 lib/hashtable.c |   12 ++++++++----
 1 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/lib/hashtable.c b/lib/hashtable.c
index b747f1f..57802cf 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -45,6 +45,9 @@
 # include <linux/string.h>
 #endif
 
+#ifndef	CONFIG_ENV_MIN_ENTRIES	/* minimum number of entries */
+#define	CONFIG_ENV_MIN_ENTRIES 64
+#endif
 #ifndef	CONFIG_ENV_MAX_ENTRIES	/* maximum number of entries */
 #define	CONFIG_ENV_MAX_ENTRIES 512
 #endif
@@ -647,13 +650,14 @@ int himport_r(struct hsearch_data *htab,
 	 * (CONFIG_ENV_SIZE).  This heuristics will result in
 	 * 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).
+	 * envrionment size), so we clip it to a reasonable value.
+	 * On the other hand we need to add some more entries for free
+	 * space when importing very small buffers. Both boundaries can
+	 * be overwritten in the board config file if needed.
 	 */
 
 	if (!htab->table) {
-		int nent = size / 8;
+		int nent = CONFIG_ENV_MIN_ENTRIES + size / 8;
 
 		if (nent > CONFIG_ENV_MAX_ENTRIES)
 			nent = CONFIG_ENV_MAX_ENTRIES;
-- 
1.7.3.1

[U-Boot] [PATCH v2] lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

[Wolfgang Denk]

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

In message <1285966262-73388-1-git-send-email-andreas.devel@googlemail.com> you wrote:
> 
> This patch adds a new config parameter for adjusting the calculation of
> hash table size when importing a buffer.
> 
> When importing a extremely small buffer (e.g. the default_environment)
> the old calculation generated a hash table which could hold at most the
> buffer content but no more entires.
> 
> The new calculation add a fixed number of entries to the result to fit
> better for small import buffers. This amount may be configured by the
> user in board file to adjust the behaviour.
> 
> Signed-off-by: Andreas Bie?mann <andreas.devel@googlemail.com>
> ---
> v2: implement as suggested by Wolfgang
> 
>  lib/hashtable.c |   12 ++++++++----
>  1 files changed, 8 insertions(+), 4 deletions(-)

Applied, thanks.

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
The human race is faced with a cruel choice: work  or  daytime  tele-
vision.

[U-Boot] [PATCH v2] lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

[Andreas Bießmann]

Dear Wolfgang Denk,

Am 06.10.2010 um 22:47 schrieb Wolfgang Denk:

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

>> lib/hashtable.c |   12 ++++++++----
>> 1 files changed, 8 insertions(+), 4 deletions(-)
> 
> Applied, thanks.
> 
> Best regards,
> 
> Wolfgang Denk

couldn't find this patch mainline. Where did it go?

regards

Andreas Bie?mann

[U-Boot] [PATCH v2] lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

[Wolfgang Denk]

Dear =?iso-8859-1?Q?Andreas_Bie=DFmann?=,

In message <F2DA4AEA-D25A-4355-9727-715E47AE8AFB@googlemail.com> you wrote:
> 
> >> lib/hashtable.c |   12 ++++++++----
> >> 1 files changed, 8 insertions(+), 4 deletions(-)
> > 
> > Applied, thanks.
> > 
> > Best regards,
> > 
> > Wolfgang Denk
>
> couldn't find this patch mainline. Where did it go?

	commit fc5fc76bdad14425e3743e1494c9e444570df1be
	Author: Andreas Bie?mann <andreas.devel@googlemail.com>
	Date:   Fri Oct 1 22:51:02 2010 +0200

	    lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

See
http://git.denx.de/?p=u-boot.git;a=commit;h=fc5fc76bdad14425e3743e1494c9e444570df1be

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
Quotation, n. The act of repeating erroneously the words of  another.
The  words  erroneously  repeated.
                            - Ambrose Bierce _The Devil's Dictionary_