Skip to contentSkip to conversation

lib/hashtable.c: add algorithm for small buffer import

PATCH New Andreas Bießmann 2 participants 9 messages Sep 29, 2010 – Oct 8, 2010 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib/hashtable.c: add algorithm for small buffer import

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.

---
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(-)
common/env_common.c +1 -1
index a415ef8..bd6eae4 100644
@@ -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;
include/search.h +3 -1
index fccc757..e6cd189 100644
@@ -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 */
lib/hashtable.c +12 -3
index b747f1f..82a4d00 100644
@@ -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;
Signature · 1 line
1.7.3
#1 lore raw

PATCH 1/1 lib/hashtable.c: add algorithm for small buffer import

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

Quoted 7 lines · In message <[email protected]>…

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.

include/search.h extern int himport_r(struct hsearch_data *__htab, · line 107

Quoted 4 lines
include/search.h +3 -1
-
+#define H_ALG_SMALL_BUF	2	/* use another algorithm for small buffers to
+				   calculate hashtable size.
+				 */

Coding style: incorrect multiline comment.

lib/hashtable.c int himport_r(struct hsearch_data *htab, · line 647

Quoted 11 lines
lib/hashtable.c +2 -2
-	 * 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.

Quoted 9 lines
lib/hashtable.c +4 -0
 	 * 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

lib/hashtable.c int himport_r(struct hsearch_data *htab, · line 665

Quoted 10 lines
lib/hashtable.c +6 -1
+	 * 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

Signature · 5 lines
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
#2 lore raw

PATCH 1/1 lib/hashtable.c: add algorithm for small buffer import

(resent to list)

Dear Wolfgang Denk,

Am 29.09.2010 um 22:01 schrieb Wolfgang Denk:

Quoted 3 lines

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

In message <[email protected]> you wrote:

[snip]

Quoted 12 lines
Quoted 12 lines

* 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).

lib/hashtable.c +5 -0
+	 *
+	 * 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.
	 */
Quoted 9 lines

lib/hashtable.c int himport_r(struct hsearch_data *htab, · line 665

Quoted 7 lines
	if (!htab->table) {
lib/hashtable.c +5 -1
-		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.

Quoted 2 lines

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.

Quoted 7 lines

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;
...

Quoted 3 lines

or similar.

What do you think?

How about my suggestion?

Quoted 7 lines

[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

Quoted 10 lines

Best regards,

Wolfgang Denk

Signature · 5 lines
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
#3 lore raw

PATCH 1/1 lib/hashtable.c: add algorithm for small buffer import

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

Quoted 8 lines · In message <[email protected]> you wrote:
Quoted 3 lines

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.

Quoted 8 lines
Quoted 7 lines

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;
Quoted 7 lines

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.

Quoted 4 lines

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
Quoted 2 lines

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

Signature · 5 lines
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.
#4 lore raw

PATCH 1/1 lib/hashtable.c: add algorithm for small buffer import

Dear Wolfgang Denk,

Am 29.09.2010 um 23:02 schrieb Wolfgang Denk:

Quoted 7 lines

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

Quoted 4 lines · In message <[email protected]> you wrote:
Quoted 3 lines

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

Quoted 6 lines
Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 20 lines
Quoted 8 lines
Quoted 7 lines

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;
Quoted 7 lines

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.

Quoted 8 lines
Quoted 4 lines

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.

Quoted 9 lines

Example: "TQM5200.h":

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

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

Quoted 6 lines

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.

Quoted 2 lines

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

#5 lore raw

PATCH v2 1/1 lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

In reply to 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.

---
v2: implement as suggested by Wolfgang

 lib/hashtable.c |   12 ++++++++----
 1 files changed, 8 insertions(+), 4 deletions(-)
lib/hashtable.c +8 -4
index b747f1f..57802cf 100644
@@ -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;
Signature · 1 line
1.7.3.1
#6 lore raw

PATCH v2 1/1 lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

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

Quoted 12 lines · In message <[email protected]>…

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.

Quoted 6 lines

---
v2: implement as suggested by Wolfgang

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

Applied, thanks.

Best regards,

Wolfgang Denk

Signature · 5 lines
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.
#7 lore raw

PATCH v2 1/1 lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

Dear Wolfgang Denk,

Am 06.10.2010 um 22:47 schrieb Wolfgang Denk:

Quoted 4 lines

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

In message <[email protected]> you wrote:

Quoted 8 lines
Quoted 2 lines

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

#8 lore raw

PATCH v2 1/1 lib/hashtable.c: add CONFIG_ENV_MIN_ENTRIES

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

Quoted 11 lines · In message <[email protected]> you wrote:
Quoted 9 lines
Quoted 3 lines

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 <[email protected]>
	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

Signature · 6 lines
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_