[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Mike Frysinger]

The non-reentrant versions of the hashtable functions operate on a single
shared hashtable.  So if two different people try using these funcs for
two different purposes, they'll cause problems for the other.

Avoid this by converting all existing hashtable consumers over to the
reentrant versions and then punting the non-reentrant ones.

Signed-off-by: Mike Frysinger <vapier@gentoo.org>
---
 common/cmd_nvedit.c    |   18 +++++++++---------
 common/env_common.c    |    6 ++++--
 common/env_dataflash.c |    2 +-
 common/env_eeprom.c    |    2 +-
 common/env_flash.c     |    4 ++--
 common/env_mmc.c       |    2 +-
 common/env_nand.c      |    4 ++--
 common/env_nvram.c     |    2 +-
 common/env_onenand.c   |    2 +-
 common/env_sf.c        |    4 ++--
 include/environment.h  |    8 ++++++++
 include/search.h       |   18 +-----------------
 lib/hashtable.c        |   40 ++--------------------------------------
 13 files changed, 35 insertions(+), 77 deletions(-)

diff --git a/common/cmd_nvedit.c b/common/cmd_nvedit.c
index dcc93c1..d8d314e 100644
--- a/common/cmd_nvedit.c
+++ b/common/cmd_nvedit.c
@@ -111,7 +111,7 @@ static int env_print(char *name)
 
 		e.key = name;
 		e.data = NULL;
-		ep = hsearch (e, FIND);
+		hsearch_r(e, FIND, &ep, &env_htab);
 		if (ep == NULL)
 			return 0;
 		len = printf ("%s=%s\n", ep->key, ep->data);
@@ -119,7 +119,7 @@ static int env_print(char *name)
 	}
 
 	/* print whole list */
-	len = hexport('\n', &res, 0);
+	len = hexport_r(&env_htab, '\n', &res, 0);
 
 	if (len > 0) {
 		puts(res);
@@ -184,7 +184,7 @@ int _do_env_set (int flag, int argc, char * const argv[])
 	 */
 	e.key = name;
 	e.data = NULL;
-	ep = hsearch (e, FIND);
+	hsearch_r(e, FIND, &ep, &env_htab);
 
 	/* Check for console redirection */
 	if (strcmp(name,"stdin") == 0) {
@@ -267,7 +267,7 @@ int _do_env_set (int flag, int argc, char * const argv[])
 
 	/* Delete only ? */
 	if ((argc < 3) || argv[2] == NULL) {
-		int rc = hdelete(name);
+		int rc = hdelete_r(name, &env_htab);
 		return !rc;
 	}
 
@@ -293,7 +293,7 @@ int _do_env_set (int flag, int argc, char * const argv[])
 
 	e.key  = name;
 	e.data = value;
-	ep = hsearch(e, ENTER);
+	hsearch_r(e, ENTER, &ep, &env_htab);
 	free(value);
 	if (!ep) {
 		printf("## Error inserting \"%s\" variable, errno=%d\n",
@@ -456,7 +456,7 @@ char *getenv (char *name)
 
 		e.key  = name;
 		e.data = NULL;
-		ep = hsearch (e, FIND);
+		hsearch_r(e, FIND, &ep, &env_htab);
 
 		return (ep ? ep->data : NULL);
 	}
@@ -651,7 +651,7 @@ static int do_env_export(cmd_tbl_t *cmdtp, int flag, int argc, char * const argv
 	}
 
 	if (sep) {		/* export as text file */
-		len = hexport(sep, &addr, size);
+		len = hexport_r(&env_htab, sep, &addr, size);
 		if (len < 0) {
 			error("Cannot export environment: errno = %d\n",
 				errno);
@@ -670,7 +670,7 @@ static int do_env_export(cmd_tbl_t *cmdtp, int flag, int argc, char * const argv
 	else			/* export as raw binary data */
 		res = addr;
 
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n",
 			errno);
@@ -790,7 +790,7 @@ static int do_env_import(cmd_tbl_t * cmdtp, int flag, int argc, char * const arg
 		addr = (char *)ep->data;
 	}
 
-	if (himport(addr, size, sep, del ? 0 : H_NOCLEAR) == 0) {
+	if (himport_r(&env_htab, addr, size, sep, del ? 0 : H_NOCLEAR) == 0) {
 		error("Environment import failed: errno = %d\n", errno);
 		return 1;
 	}
diff --git a/common/env_common.c b/common/env_common.c
index a276efc..ae710e5 100644
--- a/common/env_common.c
+++ b/common/env_common.c
@@ -129,6 +129,8 @@ uchar default_environment[] = {
 	"\0"
 };
 
+struct hsearch_data env_htab;
+
 static uchar env_get_char_init (int index)
 {
 	uchar c;
@@ -187,7 +189,7 @@ void set_default_env(const char *s)
 		puts("Using default environment\n\n");
 	}
 
-	if (himport((char *)default_environment,
+	if (himport_r(&env_htab, (char *)default_environment,
 		    sizeof(default_environment), '\0', 0) == 0) {
 		error("Environment import failed: errno = %d\n", errno);
 	}
@@ -213,7 +215,7 @@ int env_import(const char *buf, int check)
 		}
 	}
 
-	if (himport((char *)ep->data, ENV_SIZE, '\0', 0)) {
+	if (himport_r(&env_htab, (char *)ep->data, ENV_SIZE, '\0', 0)) {
 		gd->flags |= GD_FLG_ENV_READY;
 		return 1;
 	}
diff --git a/common/env_dataflash.c b/common/env_dataflash.c
index 270f2b3..1d57079 100644
--- a/common/env_dataflash.c
+++ b/common/env_dataflash.c
@@ -68,7 +68,7 @@ int saveenv(void)
 	char	*res;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_eeprom.c b/common/env_eeprom.c
index 792b44f..0a179ad 100644
--- a/common/env_eeprom.c
+++ b/common/env_eeprom.c
@@ -143,7 +143,7 @@ int saveenv(void)
 	BUG_ON(env_ptr != NULL);
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_flash.c b/common/env_flash.c
index 54c0bfe..456f2e8 100644
--- a/common/env_flash.c
+++ b/common/env_flash.c
@@ -155,7 +155,7 @@ int saveenv(void)
 	}
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		goto done;
@@ -289,7 +289,7 @@ int saveenv(void)
 		goto done;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		goto done;
diff --git a/common/env_mmc.c b/common/env_mmc.c
index 7c9392c..71dcc4c 100644
--- a/common/env_mmc.c
+++ b/common/env_mmc.c
@@ -107,7 +107,7 @@ int saveenv(void)
 		return 1;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_nand.c b/common/env_nand.c
index 4e8307a..6f5fac3 100644
--- a/common/env_nand.c
+++ b/common/env_nand.c
@@ -199,7 +199,7 @@ int saveenv(void)
 		return 1;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
@@ -256,7 +256,7 @@ int saveenv(void)
 		return 1;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_nvram.c b/common/env_nvram.c
index 6e90f2b..544ce47 100644
--- a/common/env_nvram.c
+++ b/common/env_nvram.c
@@ -94,7 +94,7 @@ int saveenv(void)
 	int	rcode = 0;
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_onenand.c b/common/env_onenand.c
index 02cb535..5e04a06 100644
--- a/common/env_onenand.c
+++ b/common/env_onenand.c
@@ -109,7 +109,7 @@ int saveenv(void)
 	};
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
diff --git a/common/env_sf.c b/common/env_sf.c
index 47c6a70..41cc00a 100644
--- a/common/env_sf.c
+++ b/common/env_sf.c
@@ -92,7 +92,7 @@ int saveenv(void)
 	}
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		return 1;
@@ -308,7 +308,7 @@ int saveenv(void)
 	}
 
 	res = (char *)&env_new.data;
-	len = hexport('\0', &res, ENV_SIZE);
+	len = hexport_r(&env_htab, '\0', &res, ENV_SIZE);
 	if (len < 0) {
 		error("Cannot export environment: errno = %d\n", errno);
 		goto done;
diff --git a/include/environment.h b/include/environment.h
index bedbc54..082b3e1 100644
--- a/include/environment.h
+++ b/include/environment.h
@@ -149,6 +149,12 @@ typedef	struct environment_s {
 	unsigned char	data[ENV_SIZE]; /* Environment data		*/
 } env_t;
 
+#ifndef DO_DEPS_ONLY
+
+#include <search.h>
+
+extern struct hsearch_data env_htab;
+
 /* Function that returns a character from the environment */
 unsigned char env_get_char (int);
 
@@ -165,4 +171,6 @@ void set_default_env(const char *s);
 /* Import from binary representation into hash table */
 int env_import(const char *buf, int check);
 
+#endif
+
 #endif	/* _ENVIRONMENT_H_ */
diff --git a/include/search.h b/include/search.h
index fccc757..81ced7f 100644
--- a/include/search.h
+++ b/include/search.h
@@ -32,15 +32,6 @@
 
 #define __set_errno(val) do { errno = val; } while (0)
 
-/*
- * Prototype structure for a linked-list data structure.
- * This is the type used by the `insque' and `remque' functions.
- */
-
-/* For use with hsearch(3).  */
-typedef int (*__compar_fn_t) (__const void *, __const void *);
-typedef __compar_fn_t comparison_fn_t;
-
 /* Action which shall be performed in the call the hsearch.  */
 typedef enum {
 	FIND,
@@ -69,11 +60,9 @@ struct hsearch_data {
 };
 
 /* Create a new hashing table which will at most contain NEL elements.  */
-extern int hcreate(size_t __nel);
 extern int hcreate_r(size_t __nel, struct hsearch_data *__htab);
 
 /* Destroy current internal hashing table.  */
-extern void hdestroy(void);
 extern void hdestroy_r(struct hsearch_data *__htab);
 
 /*
@@ -82,25 +71,20 @@ extern void hdestroy_r(struct hsearch_data *__htab);
  * NULL.  If ACTION is `ENTER' replace existing data (if any) with
  * ITEM.data.
  * */
-extern ENTRY *hsearch(ENTRY __item, ACTION __action);
 extern int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
 		     struct hsearch_data *__htab);
 
 /* Search and delete entry matching ITEM.key in internal hash table. */
-extern int hdelete(const char *__key);
 extern int hdelete_r(const char *__key, struct hsearch_data *__htab);
 
-extern ssize_t hexport(const char __sep, char **__resp, size_t __size);
 extern ssize_t hexport_r(struct hsearch_data *__htab,
 		     const char __sep, char **__resp, size_t __size);
 
-extern int himport(const char *__env, size_t __size, const char __sep,
-		   int __flag);
 extern int himport_r(struct hsearch_data *__htab,
 		     const char *__env, size_t __size, const char __sep,
 		     int __flag);
 
-/* Flags for himport() / himport_r() */
+/* Flags for himport_r() */
 #define	H_NOCLEAR	1	/* do not clear hash table before importing */
 
 #endif /* search.h */
diff --git a/lib/hashtable.c b/lib/hashtable.c
index 7ac3ddd..b47f3b6 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -60,11 +60,6 @@
  */
 
 /*
- * The non-reentrant version use a global space for storing the hash table.
- */
-static struct hsearch_data htab;
-
-/*
  * The reentrant version has no static variables to maintain the state.
  * Instead the interface of all functions is extended to take an argument
  * which describes the current status.
@@ -97,11 +92,6 @@ static int isprime(unsigned int number)
 	return number % div != 0;
 }
 
-int hcreate(size_t nel)
-{
-	return hcreate_r(nel, &htab);
-}
-
 /*
  * Before using the hash table we must allocate memory for it.
  * Test for an existing table are done. We allocate one element
@@ -110,6 +100,7 @@ int hcreate(size_t nel)
  * The contents of the table is zeroed, especially the field used
  * becomes zero.
  */
+
 int hcreate_r(size_t nel, struct hsearch_data *htab)
 {
 	/* Test for correct arguments.  */
@@ -143,15 +134,12 @@ int hcreate_r(size_t nel, struct hsearch_data *htab)
 /*
  * hdestroy()
  */
-void hdestroy(void)
-{
-	hdestroy_r(&htab);
-}
 
 /*
  * After using the hash table it has to be destroyed. The used memory can
  * be freed and the local static variable can be marked as not used.
  */
+
 void hdestroy_r(struct hsearch_data *htab)
 {
 	int i;
@@ -214,15 +202,6 @@ void hdestroy_r(struct hsearch_data *htab)
  *   example for functions like hdelete().
  */
 
-ENTRY *hsearch(ENTRY item, ACTION action)
-{
-	ENTRY *result;
-
-	(void) hsearch_r(item, action, &result, &htab);
-
-	return result;
-}
-
 int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 	      struct hsearch_data *htab)
 {
@@ -369,11 +348,6 @@ int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
  * do that.
  */
 
-int hdelete(const char *key)
-{
-	return hdelete_r(key, &htab);
-}
-
 int hdelete_r(const char *key, struct hsearch_data *htab)
 {
 	ENTRY e, *ep;
@@ -442,11 +416,6 @@ int hdelete_r(const char *key, struct hsearch_data *htab)
  *		bytes in the string will be '\0'-padded.
  */
 
-ssize_t hexport(const char sep, char **resp, size_t size)
-{
-	return hexport_r(&htab, sep, resp, size);
-}
-
 static int cmpkey(const void *p1, const void *p2)
 {
 	ENTRY *e1 = *(ENTRY **) p1;
@@ -605,11 +574,6 @@ ssize_t hexport_r(struct hsearch_data *htab, const char sep,
  * '\0' and '\n' have really been tested.
  */
 
-int himport(const char *env, size_t size, const char sep, int flag)
-{
-	return himport_r(&htab, env, size, sep, flag);
-}
-
 int himport_r(struct hsearch_data *htab,
 	      const char *env, size_t size, const char sep, int flag)
 {
-- 
1.7.3.3

[U-Boot] [RFC PATCH 2/2] env: re-add support for auto-completion

[Mike Frysinger]

Currently, only basic completion is supported (no globs), but this is what
we had previously.  The downside is that the results are not returned in
any sorted order.  The upside is that we get any results at all.

Signed-off-by: Mike Frysinger <vapier@gentoo.org>
---
 common/command.c    |    3 +--
 common/env_common.c |   34 +++++++++++-----------------------
 include/search.h    |    7 +++++++
 lib/hashtable.c     |   20 ++++++++++++++++++++
 4 files changed, 39 insertions(+), 25 deletions(-)

diff --git a/common/command.c b/common/command.c
index 0b1a3fb..aaebaca 100644
--- a/common/command.c
+++ b/common/command.c
@@ -162,7 +162,6 @@ int cmd_usage(cmd_tbl_t *cmdtp)
 
 int var_complete(int argc, char * const argv[], char last_char, int maxv, char *cmdv[])
 {
-#if 0 /* need to reimplement */
 	static char tmp_buf[512];
 	int space;
 
@@ -173,7 +172,7 @@ int var_complete(int argc, char * const argv[], char last_char, int maxv, char *
 
 	if (!space && argc == 2)
 		return env_complete(argv[1], maxv, cmdv, sizeof(tmp_buf), tmp_buf);
-#endif
+
 	return 0;
 }
 
diff --git a/common/env_common.c b/common/env_common.c
index ae710e5..6c694c5 100644
--- a/common/env_common.c
+++ b/common/env_common.c
@@ -246,40 +246,28 @@ void env_relocate (void)
 	}
 }
 
-#if 0 /* need to reimplement - def CONFIG_AUTO_COMPLETE */
+#ifdef CONFIG_AUTO_COMPLETE
 int env_complete(char *var, int maxv, char *cmdv[], int bufsz, char *buf)
 {
-	int i, nxt, len, vallen, found;
-	const char *lval, *rval;
+	ENTRY *match;
+	int found, idx;
 
+	idx = 0;
 	found = 0;
 	cmdv[0] = NULL;
 
-	len = strlen(var);
-	/* now iterate over the variables and select those that match */
-	for (i=0; env_get_char(i) != '\0'; i=nxt+1) {
+	while ((idx = hmatch_r(var, idx, &match, &env_htab))) {
+		int vallen = strlen(match->key) + 1;
 
-		for (nxt=i; env_get_char(nxt) != '\0'; ++nxt)
-			;
-
-		lval = (char *)env_get_addr(i);
-		rval = strchr(lval, '=');
-		if (rval != NULL) {
-			vallen = rval - lval;
-			rval++;
-		} else
-			vallen = strlen(lval);
-
-		if (len > 0 && (vallen < len || memcmp(lval, var, len) != 0))
-			continue;
-
-		if (found >= maxv - 2 || bufsz < vallen + 1) {
+		if (found >= maxv - 2 || bufsz < vallen) {
 			cmdv[found++] = "...";
 			break;
 		}
+
 		cmdv[found++] = buf;
-		memcpy(buf, lval, vallen); buf += vallen; bufsz -= vallen;
-		*buf++ = '\0'; bufsz--;
+		memcpy(buf, match->key, vallen);
+		buf += vallen;
+		bufsz -= vallen;
 	}
 
 	cmdv[found] = NULL;
diff --git a/include/search.h b/include/search.h
index 81ced7f..a7c1293 100644
--- a/include/search.h
+++ b/include/search.h
@@ -74,6 +74,13 @@ extern void hdestroy_r(struct hsearch_data *__htab);
 extern int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
 		     struct hsearch_data *__htab);
 
+/*
+ * Search for an entry matching `MATCH'.  Otherwise, Same semantics
+ * as hsearch_r().
+ */
+extern int hmatch_r(const char *__match, int __last_idx, ENTRY ** __retval,
+		    struct hsearch_data *__htab);
+
 /* Search and delete entry matching ITEM.key in internal hash table. */
 extern int hdelete_r(const char *__key, struct hsearch_data *__htab);
 
diff --git a/lib/hashtable.c b/lib/hashtable.c
index b47f3b6..9f069c0 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -202,6 +202,26 @@ void hdestroy_r(struct hsearch_data *htab)
  *   example for functions like hdelete().
  */
 
+int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
+	     struct hsearch_data *htab)
+{
+	unsigned int idx;
+	size_t key_len = strlen(match);
+
+	for (idx = last_idx + 1; idx < htab->size; ++idx) {
+		if (!htab->table[idx].used)
+			continue;
+		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
+			*retval = &htab->table[idx].entry;
+			return idx;
+		}
+	}
+
+	__set_errno(ESRCH);
+	*retval = NULL;
+	return 0;
+}
+
 int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 	      struct hsearch_data *htab)
 {
-- 
1.7.3.3

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Mike Frysinger]

On Wednesday, December 08, 2010 06:26:04 Mike Frysinger wrote:
> The non-reentrant versions of the hashtable functions operate on a single
> shared hashtable.  So if two different people try using these funcs for
> two different purposes, they'll cause problems for the other.
> 
> Avoid this by converting all existing hashtable consumers over to the
> reentrant versions and then punting the non-reentrant ones.

oh, and this does shrink the final u-boot a little, so that's good
-mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part.
Url : http://lists.denx.de/pipermail/u-boot/attachments/20101208/7acac189/attachment.pgp 

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Joakim Tjernlund]

>
> On Wednesday, December 08, 2010 06:26:04 Mike Frysinger wrote:
> > The non-reentrant versions of the hashtable functions operate on a single
> > shared hashtable.  So if two different people try using these funcs for
> > two different purposes, they'll cause problems for the other.
> >
> > Avoid this by converting all existing hashtable consumers over to the
> > reentrant versions and then punting the non-reentrant ones.
>
> oh, and this does shrink the final u-boot a little, so that's good
> -mike

Nice, over the last years I have noticed that u-boot has grown a lot.
I had to disable a few non essential commands to make it it fit.

Does anyone else share my concern about the rapid growth of u-boot?

 Jocke

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Wolfgang Denk]

Dear Joakim Tjernlund,

In message <OF280890AF.2970DA02-ONC12577F3.004474F0-C12577F3.0044D6E5@transmode.se> you wrote:
>
> > oh, and this does shrink the final u-boot a little, so that's good
> > -mike
> 
> Nice, over the last years I have noticed that u-boot has grown a lot.
> I had to disable a few non essential commands to make it it fit.
> 
> Does anyone else share my concern about the rapid growth of u-boot?

I do, and always did. It's mainly features that drive the code size.
Some recent changes (gc-sections on PPC) help a bit. And users
submitting optimizations like above.

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
In general, they do what you want, unless you want consistency.
                                    - Larry Wall in the perl man page

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Joakim Tjernlund]

Wolfgang Denk <wd@denx.de> wrote on 2010/12/08 15:23:17:
>
> Dear Joakim Tjernlund,
>
> In message <OF280890AF.2970DA02-ONC12577F3.004474F0-C12577F3.0044D6E5@transmode.se> you wrote:
> >
> > > oh, and this does shrink the final u-boot a little, so that's good
> > > -mike
> >
> > Nice, over the last years I have noticed that u-boot has grown a lot.
> > I had to disable a few non essential commands to make it it fit.
> >
> > Does anyone else share my concern about the rapid growth of u-boot?
>
> I do, and always did. It's mainly features that drive the code size.
> Some recent changes (gc-sections on PPC) help a bit. And users
> submitting optimizations like above.

Yes, but I don't see any discussion about it. Just the occasional improvement
that pop by every now and then.

I got my own theory were some of the growth come from: string literals
Especially when using them in tables:
static struct {
		ulong mask;
		char *desc;
	} bits[] = {
		{
		RSR_SWSR, "Software Soft"}, {
		RSR_SWHR, "Software Hard"}, {
		RSR_JSRS, "JTAG Soft"}, {
		RSR_CSHR, "Check Stop"}, {
		RSR_SWRS, "Software Watchdog"}, {
		RSR_BMRS, "Bus Monitor"}, {
		RSR_SRS,  "External/Internal Soft"}, {
		RSR_HRS,  "External/Internal Hard"}
	};
Obviously the strings consume space, but there is an hidden extra cost too:
each string gets an fixup entry(4 bytes) and a GOT entry(4 bytes) too.

  Jocke

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Mike Frysinger]

On Wednesday, December 08, 2010 07:31:54 Joakim Tjernlund wrote:
> > On Wednesday, December 08, 2010 06:26:04 Mike Frysinger wrote:
> > > The non-reentrant versions of the hashtable functions operate on a
> > > single shared hashtable.  So if two different people try using these
> > > funcs for two different purposes, they'll cause problems for the
> > > other.
> > > 
> > > Avoid this by converting all existing hashtable consumers over to the
> > > reentrant versions and then punting the non-reentrant ones.
> > 
> > oh, and this does shrink the final u-boot a little, so that's good
> 
> Nice, over the last years I have noticed that u-boot has grown a lot.
> I had to disable a few non essential commands to make it it fit.
> 
> Does anyone else share my concern about the rapid growth of u-boot?

i try to go through things about once a release to see about culling crap, but 
i focus on things that affect Blackfin, so relocation isnt one
-mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part.
Url : http://lists.denx.de/pipermail/u-boot/attachments/20101208/bee186b7/attachment.pgp 

[U-Boot] [RFC PATCH 1/2] hashtable: drop all non-reentrant versions

[Wolfgang Denk]

Dear Mike Frysinger,

In message <1291807565-4831-1-git-send-email-vapier@gentoo.org> you wrote:
> The non-reentrant versions of the hashtable functions operate on a single
> shared hashtable.  So if two different people try using these funcs for
> two different purposes, they'll cause problems for the other.
> 
> Avoid this by converting all existing hashtable consumers over to the
> reentrant versions and then punting the non-reentrant ones.
> 
> Signed-off-by: Mike Frysinger <vapier@gentoo.org>
> ---
>  common/cmd_nvedit.c    |   18 +++++++++---------
>  common/env_common.c    |    6 ++++--
>  common/env_dataflash.c |    2 +-
>  common/env_eeprom.c    |    2 +-
>  common/env_flash.c     |    4 ++--
>  common/env_mmc.c       |    2 +-
>  common/env_nand.c      |    4 ++--
>  common/env_nvram.c     |    2 +-
>  common/env_onenand.c   |    2 +-
>  common/env_sf.c        |    4 ++--
>  include/environment.h  |    8 ++++++++
>  include/search.h       |   18 +-----------------
>  lib/hashtable.c        |   40 ++--------------------------------------
>  13 files changed, 35 insertions(+), 77 deletions(-)

Apllied to "next", 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
I still miss my ex-wife, but my aim is getting better.

[U-Boot] [RFC PATCH 2/2] env: re-add support for auto-completion

[Wolfgang Denk]

Dear Mike Frysinger,

In message <1291807565-4831-2-git-send-email-vapier@gentoo.org> you wrote:
> Currently, only basic completion is supported (no globs), but this is what
> we had previously.  The downside is that the results are not returned in
> any sorted order.  The upside is that we get any results at all.

Why can we not collect the results and sort them like we do for "env
print" ?

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 hottest places in Hell are reserved for those who, in  times  of
moral crisis, preserved their neutrality."                    - Dante

[U-Boot] [RFC PATCH 2/2] env: re-add support for auto-completion

[Mike Frysinger]

On Friday, December 17, 2010 15:10:14 Wolfgang Denk wrote:
> Mike Frysinger wrote:
> > Currently, only basic completion is supported (no globs), but this is
> > what we had previously.  The downside is that the results are not
> > returned in any sorted order.  The upside is that we get any results at
> > all.
> 
> Why can we not collect the results and sort them like we do for "env
> print" ?

hmm, i dont think the previous code did do any sorting.  it just relied on the 
results of the env code being sorted already.  i also dont think there is any 
support in u-boot today for sorting ?  so i'd basically have to import 
qsort(), and i didnt think the size trade off was worth while.
-mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part.
Url : http://lists.denx.de/pipermail/u-boot/attachments/20101217/6b123fa3/attachment.pgp 

[U-Boot] [RFC PATCH 2/2] env: re-add support for auto-completion

[Wolfgang Denk]

Dear Mike Frysinger,

In message <201012171535.08619.vapier@gentoo.org> you wrote:
>
> > Why can we not collect the results and sort them like we do for "env
> > print" ?
> 
> hmm, i dont think the previous code did do any sorting.  it just relied on the 
> results of the env code being sorted already.  i also dont think there is any 

The old code did not sort the output of pirntenv either - but the now
code does.

> support in u-boot today for sorting ?  so i'd basically have to import 
> qsort(), and i didnt think the size trade off was worth while.

Guess how printenv sorts the entries?

See lib/qsort.c

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
"I can call spirits from the vasty deep."
"Why so can I, or so can any man; but will they come when you do call
for them?"          - Shakespeare, 1 King Henry IV, Act III, Scene I.

[U-Boot] [PATCH v2] env: re-add support for auto-completion

[Mike Frysinger]

Currently, only basic completion is supported (no globs), but this is
what we had previously.

Signed-off-by: Mike Frysinger <vapier@gentoo.org>
---
v2
	- sort the results

 common/command.c    |    3 +--
 common/env_common.c |   40 +++++++++++++++-------------------------
 include/common.h    |    1 +
 include/search.h    |    7 +++++++
 lib/hashtable.c     |   20 ++++++++++++++++++++
 lib/qsort.c         |    6 ++++++
 6 files changed, 50 insertions(+), 27 deletions(-)

diff --git a/common/command.c b/common/command.c
index ef4a081..b3ec510 100644
--- a/common/command.c
+++ b/common/command.c
@@ -162,7 +162,6 @@ int cmd_usage(cmd_tbl_t *cmdtp)
 
 int var_complete(int argc, char * const argv[], char last_char, int maxv, char *cmdv[])
 {
-#if 0 /* need to reimplement */
 	static char tmp_buf[512];
 	int space;
 
@@ -173,7 +172,7 @@ int var_complete(int argc, char * const argv[], char last_char, int maxv, char *
 
 	if (!space && argc == 2)
 		return env_complete(argv[1], maxv, cmdv, sizeof(tmp_buf), tmp_buf);
-#endif
+
 	return 0;
 }
 
diff --git a/common/env_common.c b/common/env_common.c
index ae710e5..c3e6388 100644
--- a/common/env_common.c
+++ b/common/env_common.c
@@ -246,42 +246,32 @@ void env_relocate (void)
 	}
 }
 
-#if 0 /* need to reimplement - def CONFIG_AUTO_COMPLETE */
+#ifdef CONFIG_AUTO_COMPLETE
 int env_complete(char *var, int maxv, char *cmdv[], int bufsz, char *buf)
 {
-	int i, nxt, len, vallen, found;
-	const char *lval, *rval;
+	ENTRY *match;
+	int found, idx;
 
+	idx = 0;
 	found = 0;
 	cmdv[0] = NULL;
 
-	len = strlen(var);
-	/* now iterate over the variables and select those that match */
-	for (i=0; env_get_char(i) != '\0'; i=nxt+1) {
+	while ((idx = hmatch_r(var, idx, &match, &env_htab))) {
+		int vallen = strlen(match->key) + 1;
 
-		for (nxt=i; env_get_char(nxt) != '\0'; ++nxt)
-			;
-
-		lval = (char *)env_get_addr(i);
-		rval = strchr(lval, '=');
-		if (rval != NULL) {
-			vallen = rval - lval;
-			rval++;
-		} else
-			vallen = strlen(lval);
-
-		if (len > 0 && (vallen < len || memcmp(lval, var, len) != 0))
-			continue;
-
-		if (found >= maxv - 2 || bufsz < vallen + 1) {
-			cmdv[found++] = "...";
+		if (found >= maxv - 2 || bufsz < vallen)
 			break;
-		}
+
 		cmdv[found++] = buf;
-		memcpy(buf, lval, vallen); buf += vallen; bufsz -= vallen;
-		*buf++ = '\0'; bufsz--;
+		memcpy(buf, match->key, vallen);
+		buf += vallen;
+		bufsz -= vallen;
 	}
 
+	qsort(cmdv, found, sizeof(cmdv[0]), strcmp_compar);
+
+	if (idx)
+		cmdv[found++] = "...";
 	cmdv[found] = NULL;
 	return found;
 }
diff --git a/include/common.h b/include/common.h
index 0d1c872..d8c912d 100644
--- a/include/common.h
+++ b/include/common.h
@@ -632,6 +632,7 @@ static inline IPaddr_t getenv_IPaddr (char *var)
 /* lib/qsort.c */
 void qsort(void *base, size_t nmemb, size_t size,
 	   int(*compar)(const void *, const void *));
+int strcmp_compar(const void *, const void *);
 
 /* lib/time.c */
 void	udelay        (unsigned long);
diff --git a/include/search.h b/include/search.h
index 81ced7f..a7c1293 100644
--- a/include/search.h
+++ b/include/search.h
@@ -74,6 +74,13 @@ extern void hdestroy_r(struct hsearch_data *__htab);
 extern int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
 		     struct hsearch_data *__htab);
 
+/*
+ * Search for an entry matching `MATCH'.  Otherwise, Same semantics
+ * as hsearch_r().
+ */
+extern int hmatch_r(const char *__match, int __last_idx, ENTRY ** __retval,
+		    struct hsearch_data *__htab);
+
 /* Search and delete entry matching ITEM.key in internal hash table. */
 extern int hdelete_r(const char *__key, struct hsearch_data *__htab);
 
diff --git a/lib/hashtable.c b/lib/hashtable.c
index b47f3b6..9f069c0 100644
--- a/lib/hashtable.c
+++ b/lib/hashtable.c
@@ -202,6 +202,26 @@ void hdestroy_r(struct hsearch_data *htab)
  *   example for functions like hdelete().
  */
 
+int hmatch_r(const char *match, int last_idx, ENTRY ** retval,
+	     struct hsearch_data *htab)
+{
+	unsigned int idx;
+	size_t key_len = strlen(match);
+
+	for (idx = last_idx + 1; idx < htab->size; ++idx) {
+		if (!htab->table[idx].used)
+			continue;
+		if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
+			*retval = &htab->table[idx].entry;
+			return idx;
+		}
+	}
+
+	__set_errno(ESRCH);
+	*retval = NULL;
+	return 0;
+}
+
 int hsearch_r(ENTRY item, ACTION action, ENTRY ** retval,
 	      struct hsearch_data *htab)
 {
diff --git a/lib/qsort.c b/lib/qsort.c
index e771dcf..1cc0d31 100644
--- a/lib/qsort.c
+++ b/lib/qsort.c
@@ -16,6 +16,7 @@
  * bcc and gcc. */
 
 #include <linux/types.h>
+#include <exports.h>
 #if 0
 #include <assert.h>
 #else
@@ -67,3 +68,8 @@ void qsort(void  *base,
 		} while (wgap);
 	}
 }
+
+int strcmp_compar(const void *p1, const void *p2)
+{
+	return strcmp(*(const char **)p1, *(const char **)p2);
+}
-- 
1.7.3.3

[U-Boot] [PATCH v2] env: re-add support for auto-completion

[Wolfgang Denk]

Dear Mike Frysinger,

In message <1292622719-28646-1-git-send-email-vapier@gentoo.org> you wrote:
> Currently, only basic completion is supported (no globs), but this is
> what we had previously.
> 
> Signed-off-by: Mike Frysinger <vapier@gentoo.org>
> ---
> v2
> 	- sort the results
> 
>  common/command.c    |    3 +--
>  common/env_common.c |   40 +++++++++++++++-------------------------
>  include/common.h    |    1 +
>  include/search.h    |    7 +++++++
>  lib/hashtable.c     |   20 ++++++++++++++++++++
>  lib/qsort.c         |    6 ++++++
>  6 files changed, 50 insertions(+), 27 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
I don't care if you *ARE* on a bondage-and-discipline  post-technical
system  pawned off by the nation's largest oughta-be-illegal monopoly
who cannot escape the sins of their forefathers -- namely, using  the
wrong  slash for directories when the C language and its brethren use
it for something else that's very important.
         -- Tom Christiansen in <55oabg$1j1$1@csnews.cs.colorado.edu>