git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 11/13] Win32: keep the environment sorted

From
Stepan Kasal <kasal@ucw.cz>
Date
Jul 17, 2014, 15:38 UTC
Message-ID
<1405611486-10176-12-git-send-email-kasal@ucw.cz>
In-Reply-To
<1405611486-10176-1-git-send-email-kasal@ucw.cz>
From: Karsten Blees <blees@dcon.de>

The Windows environment is sorted, keep it that way for O(log n) environment access.

Change compareenv to compare only the keys, so that it can be used to find an entry irrespective of the value.

Change lookupenv to binary seach for an entry. Return one's complement of the insert position if not found (libc's bsearch returns NULL).

Replace MSVCRT's getenv with a minimal do_getenv based on the binary search function.

Change do_putenv to insert new entries at the correct position. Simplify the function by swapping if conditions and using memmove instead of for loops.

Move qsort from make_environment_block to mingw_startup. We still need to sort on startup to make sure that the environment is sorted according to our compareenv function (while Win32 / CreateProcess requires the environment block to be sorted case-insensitively, CreateProcess currently doesn't enforce this, and some applications such as bash just don't care).

Note that environment functions are _not_ thread-safe and are not required to be so by POSIX, the application is responsible for synchronizing access to the environment. MSVCRT's getenv and our new getenv implementation are better than that in that they are thread-safe with respect to other getenv calls as long as the environment is not modified. Git's indiscriminate use of getenv in background threads currently requires this property.

Signed-off-by: Karsten Blees <blees@dcon.de>
Signed-off-by: Stepan Kasal <kasal@ucw.cz>
---
 compat/mingw.c | 104 +++++++++++++++++++++++++++++++++++----------------------
 1 file changed, 65 insertions(+), 39 deletions(-)
diff --git a/compat/mingw.c b/compat/mingw.c
index 757a6b1..9dc6bf6 100644
--- a/compat/mingw.c
+++ b/compat/mingw.c
@@ -905,13 +905,6 @@ static int environ_size = 0;
 /* allocated size of environ array, in bytes */
 static int environ_alloc = 0;
 
-static int compareenv(const void *a, const void *b)
-{
-	char *const *ea = a;
-	char *const *eb = b;
-	return strcasecmp(*ea, *eb);
-}
-
 /*
  * Create environment block suitable for CreateProcess. Merges current
  * process environment and the supplied environment changes.
@@ -933,9 +926,6 @@ static wchar_t *make_environment_block(char **deltaenv)
 	for (i = 0; deltaenv && deltaenv[i]; i++)
 		size = do_putenv(tmpenv, deltaenv[i], size, 0);
 
-	/* environment must be sorted */
-	qsort(tmpenv, size - 1, sizeof(char*), compareenv);
-
 	/* create environment block from temporary environment */
 	for (i = 0; tmpenv[i]; i++) {
 		size = 2 * strlen(tmpenv[i]) + 2; /* +2 for final \0 */
@@ -1193,16 +1183,42 @@ int mingw_kill(pid_t pid, int sig)
 	return -1;
 }
 
-static int lookupenv(char **env, const char *name, size_t nmln)
-{
-	int i;
+/*
+ * Compare environment entries by key (i.e. stopping at '=' or '\0').
+ */
+static int compareenv(const void *v1, const void *v2)
+{
+	const char *e1 = *(const char**)v1;
+	const char *e2 = *(const char**)v2;
+
+	for (;;) {
+		int c1 = *e1++;
+		int c2 = *e2++;
+		c1 = (c1 == '=') ? 0 : tolower(c1);
+		c2 = (c2 == '=') ? 0 : tolower(c2);
+		if (c1 > c2)
+			return 1;
+		if (c1 < c2)
+			return -1;
+		if (c1 == 0)
+			return 0;
+	}
+}
 
-	for (i = 0; env[i]; i++) {
-		if (!strncasecmp(env[i], name, nmln) && '=' == env[i][nmln])
-			/* matches */
-			return i;
+static int bsearchenv(char **env, const char *name, size_t size)
+{
+	unsigned low = 0, high = size;
+	while (low < high) {
+		unsigned mid = low + ((high - low) >> 1);
+		int cmp = compareenv(&env[mid], &name);
+		if (cmp < 0)
+			low = mid + 1;
+		else if (cmp > 0)
+			high = mid;
+		else
+			return mid;
 	}
-	return -1;
+	return ~low; /* not found, return 1's complement of insert position */
 }
 
 /*
@@ -1212,39 +1228,46 @@ static int lookupenv(char **env, const char *name, size_t nmln)
  */
 static int do_putenv(char **env, const char *name, int size, int free_old)
 {
-	char *eq = strchrnul(name, '=');
-	int i = lookupenv(env, name, eq-name);
+	int i = bsearchenv(env, name, size - 1);
 
-	if (i < 0) {
-		if (*eq) {
-			env[size - 1] = (char*) name;
-			env[size] = NULL;
+	/* optionally free removed / replaced entry */
+	if (i >= 0 && free_old)
+		free(env[i]);
+
+	if (strchr(name, '=')) {
+		/* if new value ('key=value') is specified, insert or replace entry */
+		if (i < 0) {
+			i = ~i;
+			memmove(&env[i + 1], &env[i], (size - i) * sizeof(char*));
 			size++;
 		}
-	}
-	else {
-		if (free_old)
-			free(env[i]);
-		if (*eq)
-			env[i] = (char*) name;
-		else {
-			for (; env[i]; i++)
-				env[i] = env[i+1];
-			size--;
-		}
+		env[i] = (char*) name;
+	} else if (i >= 0) {
+		/* otherwise ('key') remove existing entry */
+		size--;
+		memmove(&env[i], &env[i + 1], (size - i) * sizeof(char*));
 	}
 	return size;
 }
 
-#undef getenv
+static char *do_getenv(const char *name)
+{
+	char *value;
+	int pos = bsearchenv(environ, name, environ_size - 1);
+	if (pos < 0)
+		return NULL;
+	value = strchr(environ[pos], '=');
+	return value ? &value[1] : NULL;
+}
+
 char *mingw_getenv(const char *name)
 {
-	char *result = getenv(name);
+	char *result = do_getenv(name);
 	if (!result && !strcmp(name, "TMPDIR")) {
 		/* on Windows it is TMP and TEMP */
-		result = getenv("TMP");
+		result = do_getenv("TMP");
 		if (!result)
-			result = getenv("TEMP");
+			result = do_getenv("TEMP");
 	}
 	return result;
 }
@@ -2087,6 +2110,9 @@ void mingw_startup()
 	environ[i] = NULL;
 	free(buffer);
 
+	/* sort environment for O(log n) getenv / putenv */
+	qsort(environ, i, sizeof(char*), compareenv);
+
 	/* initialize critical section for waitpid pinfo_t list */
 	InitializeCriticalSection(&pinfo_cs);
 

-- 
2.0.0.9635.g0be03cb

-- 
-- 
*** Please reply-to-all at all times ***
*** (do not pretend to know who is subscribed and who is not) ***
*** Please avoid top-posting. ***
The msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.

You received this message because you are subscribed to the Google
Groups "msysGit" group.
To post to this group, send email to msysgit@googlegroups.com
To unsubscribe from this group, send email to
msysgit+unsubscribe@googlegroups.com
For more options, and view previous threads, visit this group at
http://groups.google.com/group/msysgit?hl=en_US?hl=en

--- 
You received this message because you are subscribed to the Google Groups "msysGit" group.
To unsubscribe from this group and stop receiving emails from it, send an email to msysgit+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
Previous: Stepan KasalNext: Stepan Kasal
Message 14 of 23 in “mingw unicode environment”
  1. 00/13 mingw unicode environmentStepan Kasal, Jul 17, 2014
  2. 01/13 Revert "Windows: teach getenv to do a case-sensitive search"Stepan Kasal, Jul 17, 2014
  3. 02/13 Win32: Unicode environment (outgoing)Stepan Kasal, Jul 17, 2014
  4. fixup! Win32: Unicode environment (outgoing)Karsten Blees, Jul 19, 2014
  5. Junio C HamanoJul 21, 2014
  6. 03/13 Win32: Unicode environment (incoming)Stepan Kasal, Jul 17, 2014
  7. 04/13 Win32: fix environment memory leaksStepan Kasal, Jul 17, 2014
  8. 05/13 Win32: unify environment case-sensitivityStepan Kasal, Jul 17, 2014
  9. 06/13 Win32: unify environment function namesStepan Kasal, Jul 17, 2014
  10. 07/13 Win32: factor out environment block creationStepan Kasal, Jul 17, 2014
  11. 08/13 Win32: don't copy the environment twice when spawning child processesStepan Kasal, Jul 17, 2014
  12. 09/13 Win32: reduce environment array reallocationsStepan Kasal, Jul 17, 2014
  13. 10/13 Win32: use low-level memory allocation during initializationStepan Kasal, Jul 17, 2014
  14. 11/13 Win32: keep the environment sortedStepan Kasal, Jul 17, 2014
  15. 12/13 Win32: patch Windows environment on startupStepan Kasal, Jul 17, 2014
  16. 13/13 Enable color output in Windows cmd.exeStepan Kasal, Jul 17, 2014
  17. Junio C HamanoJul 17, 2014
  18. Karsten BleesJul 17, 2014
  19. Junio C HamanoJul 17, 2014
  20. Stepan KasalJul 17, 2014
  21. Junio C HamanoJul 17, 2014
  22. Karsten BleesJul 17, 2014
  23. Stepan KasalJul 18, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.