hash function for session id now uses a proper hash table

* hash table functions modified from glibc (LGPL)

1 files changed, 169 insertions, 9 deletions

diff --git a/libusb/os/windows_usb.c b/libusb/os/windows_usb.c
index a61176f..5281e31 100644
--- a/libusb/os/windows_usb.c
+++ b/libusb/os/windows_usb.c
@@ -4,6 +4,7 @@
  * With contributions from Michael Plante, Orin Eman et al.
  * Parts of this code adapted from libusb-win32-v1 by Stephan Meyer
  * HID Reports IOCTLs inspired from HIDAPI by Alan Ott, Signal 11 Software
+ * Hash table functions adapted from glibc, by Ulrich Drepper et al.
  * Major code testing contribution by Xiaofan Chen
  *
  * This library is free software; you can redistribute it and/or
@@ -385,16 +386,170 @@ err_exit:
 	return NULL;
 }
 
-/*
- * Hash a string (Nokia suggestion)
- * TODO: add collision detection (also flag 0x00000000 as reserved)
- */
-static inline unsigned long hash(const char* sz)
+/* Hash table functions - modified From glibc 2.3.2:
+   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
+   [Knuth]            The Art of Computer Programming, part 3 (6.4)  */
+typedef struct htab_entry {
+	unsigned long used;
+	char* str;
+} htab_entry;
+htab_entry* htab_table = NULL;
+usbi_mutex_t htab_write_mutex = NULL;
+unsigned long htab_size, htab_filled;
+
+/* For the used double hash method the table size has to be a prime. To
+   correct the user given table size we need a prime test.  This trivial
+   algorithm is adequate because the code is called only during init and
+   the number is likely to be small  */
+static int isprime(unsigned long number)
+{
+	// no even number will be passed
+	unsigned int divider = 3;
+
+	while((divider * divider < number) && (number % divider != 0))
+		divider += 2;
+
+	return (number % divider != 0);
+}
+
+/* Before using the hash table we must allocate memory for it.
+   We allocate one element more as the found prime number says.
+   This is done for more effective indexing as explained in the
+   comment for the hash function.  */
+int htab_create(struct libusb_context *ctx, unsigned long nel)
+{
+	if (htab_table != NULL) {
+		usbi_err(ctx, "hash table already allocated");
+	}
+
+	// Create a mutex
+	usbi_mutex_init(&htab_write_mutex, NULL);
+
+	// Change nel to the first prime number not smaller as nel.
+	nel |= 1;
+	while(!isprime(nel))
+		nel += 2;
+
+	htab_size = nel;
+	usbi_dbg("using %d elements hash table", nel);
+	htab_filled = 0;
+
+	// allocate memory and zero out.
+	htab_table = (htab_entry*)calloc(htab_size + 1, sizeof(htab_entry));
+	if (htab_table == NULL) {
+		usbi_err(ctx, "could not allocate space for hash table");
+		return 0;
+	}
+
+	return 1;
+}
+
+/* After using the hash table it has to be destroyed.  */
+void htab_destroy(void)
+{
+	size_t i;
+	if (htab_table == NULL) {
+		return;
+	}
+
+	for (i=0; i<htab_size; i++) {
+		if (htab_table[i].used) {
+			safe_free(htab_table[i].str);
+		}
+	}
+	usbi_mutex_destroy(&htab_write_mutex);
+	safe_free(htab_table);
+}
+
+/* This is the search function. It uses double hashing with open addressing.
+
+   We use an trick to speed up the lookup. The table is created with one
+   more element available. This enables us to use the index zero special.
+   This index will never be used because we store the first hash index in
+   the field used where zero means not used. Every other value means used.
+   The used field can be used as a first fast comparison for equality of
+   the stored and the parameter value. This helps to prevent unnecessary
+   expensive calls of strcmp.  */
+
+/* NB: the only way we would ever need a mutex here is if 2 colliding
+   hashes were to be stored concurrently from 2 different threads. */
+
+unsigned long htab_hash(char* str)
 {
+	unsigned long hval, hval2;
+	unsigned long idx;
 	unsigned long r = 5381;
 	int c;
+	char* sz = str;
+
+	// Compute main hash value (algorithm suggested by Nokia)
 	while ((c = *sz++))
-		r = ((r << 5) + r) + c; /* r * 33 + c */
+		r = ((r << 5) + r) + c;
+	if (r == 0)
+		++r;
+
+	// compute table hash: simply take the modulus
+	hval = r % htab_size;
+	if (hval == 0)
+		++hval;
+
+	// Try the first index
+	idx = hval;
+
+	if (htab_table[idx].used) {
+		if ( (htab_table[idx].used == hval)
+		  && (safe_strcmp(str, htab_table[idx].str) == 0) ) {
+			// existing hash
+			return r;
+		}
+		usbi_dbg("hash collision ('%s' vs '%s')", str, htab_table[idx].str);
+
+		// Second hash function, as suggested in [Knuth]
+		hval2 = 1 + hval % (htab_size - 2);
+
+		do {
+			// Because size is prime this guarantees to step through all available indexes
+			if (idx <= hval2) {
+				idx = htab_size + idx - hval2;
+			} else {
+				idx -= hval2;
+			}
+
+			// If we visited all entries leave the loop unsuccessfully
+			if (idx == hval) {
+				break;
+			}
+
+			// If entry is found use it.
+			if ( (htab_table[idx].used == hval)
+			  && (safe_strcmp(str, htab_table[idx].str) == 0) ) {
+				return r;
+			}
+		}
+		while (htab_table[idx].used);
+	}
+
+	// Not found => New entry
+
+	// If the table is full return an error
+	if (htab_filled >= htab_size) {
+		usbi_err(NULL, "hash table is full (%d entries)", htab_size);
+		return 0;
+	}
+
+	// Concurrent threads might be storing the same entry at the same time
+	// (eg. "simultaneous" enums from different threads) => use a mutex
+	usbi_mutex_lock(&htab_write_mutex);
+	// Just free any previously allocated string (which should be the same as
+	// new one). The possibility of concurrent threads storing a collision
+	// string (same hash, different string) at the same time is extremely low
+	safe_free(htab_table[idx].str);
+	htab_table[idx].used = hval;
+	htab_table[idx].str = malloc(safe_strlen(str)+1);
+	memcpy(htab_table[idx].str, str, safe_strlen(str)+1);
+	++htab_filled;
+	usbi_mutex_unlock(&htab_write_mutex);
+
 	return r;
 }
 
@@ -418,7 +573,7 @@ static unsigned long get_parent_session_id(DWORD devinst)
 	if (sanitized_path == NULL) {
 		return 0;
 	}
-	session_id = hash(sanitized_path);
+	session_id = htab_hash(sanitized_path);
 	safe_free(sanitized_path);
 	return session_id;
 }
@@ -454,7 +609,7 @@ static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp)
 	if (sanitized_path == NULL) {
 		return 0;
 	}
-	session_id = hash(sanitized_path);
+	session_id = htab_hash(sanitized_path);
 	safe_free(sanitized_path);
 	return session_id;
 }
@@ -703,6 +858,9 @@ static int windows_init(struct libusb_context *ctx)
 		}
 		SetThreadAffinityMask(timer_thread, 0);
 
+		// Create a hash table to store session ids (769 is prime)
+		htab_create(ctx, 769);
+
 		r = LIBUSB_SUCCESS;
 	}
 
@@ -732,6 +890,7 @@ init_exit: // Holds semaphore here.
 			CloseHandle(timer_mutex);
 			timer_mutex = NULL;
 		}
+		htab_destroy();
 	}
 
 	if (r != LIBUSB_SUCCESS)
@@ -1294,7 +1453,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered
 			// Create new or match existing device, using the (hashed) device_id as session id
 			if (pass <= DEV_PASS) {	// For subsequent passes, we'll lookup the parent
 				// These are the passes that create "new" devices
-				session_id = hash(dev_id_path);
+				session_id = htab_hash(dev_id_path);
 				dev = usbi_get_device_by_session_id(ctx, session_id);
 				if (dev != NULL) {
 					// No need to re-process hubs
@@ -1470,6 +1629,7 @@ static void windows_exit(void)
 			CloseHandle(timer_mutex);
 			timer_mutex = NULL;
 		}
+		htab_destroy();
 	}
 
 	ReleaseSemaphore(semaphore, 1, NULL);	// increase count back to 1