diff options
-rw-r--r-- | libusb/core.c | 184 | ||||
-rw-r--r-- | libusb/libusbi.h | 30 | ||||
-rw-r--r-- | libusb/os/linux_usbfs.c | 4 | ||||
-rw-r--r-- | libusb/os/windows_usb.c | 189 | ||||
-rw-r--r-- | libusb/os/windows_usb.h | 1 |
5 files changed, 204 insertions, 204 deletions
diff --git a/libusb/core.c b/libusb/core.c index 12c0c9c..cb0038d 100644 --- a/libusb/core.c +++ b/libusb/core.c @@ -1530,6 +1530,184 @@ void API_EXPORTED libusb_set_debug(libusb_context *ctx, int level) ctx->debug = level; } +/* 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) */ +#define DEFAULT_HTAB_SIZE 1021 + +/* 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. */ +static int usbi_htab_create(struct libusb_context *ctx, unsigned long nel) +{ + if (ctx == NULL) { + usbi_err(ctx, "null context"); + return 0; + } + + if (ctx->htab_table != NULL) { + usbi_err(ctx, "hash table already allocated"); + return 0; + } + + // Create a mutex + usbi_mutex_init(&ctx->htab_write_mutex, NULL); + + // Change nel to the first prime number not smaller as nel. + nel |= 1; + while(!isprime(nel)) + nel += 2; + + ctx->htab_size = nel; + usbi_dbg("using %d entries hash table", nel); + ctx->htab_filled = 0; + + // allocate memory and zero out. + ctx->htab_table = (struct htab_entry*)calloc(ctx->htab_size + 1, sizeof(struct htab_entry)); + if (ctx->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. */ +static void usbi_htab_destroy(struct libusb_context *ctx) +{ + size_t i; + if ((ctx == NULL) || (ctx->htab_table == NULL)) { + return; + } + + for (i=0; i<ctx->htab_size; i++) { + if (ctx->htab_table[i].used) { + free(ctx->htab_table[i].str); + } + } + usbi_mutex_destroy(&ctx->htab_write_mutex); + free(ctx->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. */ +unsigned long usbi_htab_hash(struct libusb_context *ctx, const char* str) +{ + unsigned long hval, hval2; + unsigned long idx; + unsigned long r = 5381; + int c; + char* sz = (char*) str; + + if (ctx == NULL) { + usbi_err(ctx, "no context"); + return 0; + } + if ((str == NULL) || (str[0] == 0)) { + usbi_err(ctx, "empty string"); + return 0; + } + + // Compute main hash value (djb2 algorithm) + while ((c = *sz++)) + r = ((r << 5) + r) + c; + if (r == 0) + ++r; + + // compute table hash: simply take the modulus + hval = r % ctx->htab_size; + if (hval == 0) + ++hval; + + // Try the first index + idx = hval; + + if (ctx->htab_table[idx].used) { + if ( (ctx->htab_table[idx].used == hval) + && (strcmp(str, ctx->htab_table[idx].str) == 0) ) { + // existing hash + return idx; + } + usbi_dbg("hash collision ('%s' vs '%s')", str, ctx->htab_table[idx].str); + + // Second hash function, as suggested in [Knuth] + hval2 = 1 + hval % (ctx->htab_size - 2); + + do { + // Because size is prime this guarantees to step through all available indexes + if (idx <= hval2) { + idx = ctx->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 ( (ctx->htab_table[idx].used == hval) + && (strcmp(str, ctx->htab_table[idx].str) == 0) ) { + return idx; + } + } + while (ctx->htab_table[idx].used); + } + + // Not found => New entry + + // If the table is full return an error + if (ctx->htab_filled >= ctx->htab_size) { + usbi_err(ctx, "hash table is full (%d entries)", ctx->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(&ctx->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 + if (ctx->htab_table[idx].str != NULL) { + free(ctx->htab_table[idx].str); + } + ctx->htab_table[idx].used = hval; + ctx->htab_table[idx].str = malloc(strlen(str)+1); + if (ctx->htab_table[idx].str == NULL) { + usbi_err(ctx, "could not duplicate string for hash table"); + usbi_mutex_unlock(&ctx->htab_write_mutex); + return 0; + } + memcpy(ctx->htab_table[idx].str, str, strlen(str)+1); + ++ctx->htab_filled; + usbi_mutex_unlock(&ctx->htab_write_mutex); + + return idx; +} + /** \ingroup lib * Initialize libusb. This function must be called before calling any other * libusb function. @@ -1609,6 +1787,10 @@ int API_EXPORTED libusb_init(libusb_context **context) usbi_default_context = ctx; default_context_refcnt++; } + + // TODO: check return + usbi_htab_create(ctx, DEFAULT_HTAB_SIZE); + usbi_mutex_static_unlock(&default_context_lock); return 0; @@ -1649,6 +1831,8 @@ void API_EXPORTED libusb_exit(struct libusb_context *ctx) usbi_mutex_static_unlock(&default_context_lock); } + usbi_htab_destroy(ctx); + /* a little sanity check. doesn't bother with open_devs locking because * unless there is an application bug, nobody will be accessing this. */ if (!list_empty(&ctx->open_devs)) diff --git a/libusb/libusbi.h b/libusb/libusbi.h index 2963a9a..f829fa4 100644 --- a/libusb/libusbi.h +++ b/libusb/libusbi.h @@ -179,26 +179,6 @@ static inline void usbi_dbg(const char *format, ...) #endif /* !defined(_MSC_VER) || _MSC_VER > 1200 */ -/* - * djb2 - * - * This algorithm (k=33) was first reported by Dan Bernstein many years - * ago in comp.lang.c. - */ -// TODO: maintain a hash table and detect collisions -static inline unsigned long usbi_hash(const char* sz) -{ - unsigned long r = 5381; - int c; - while ((c = *sz++)) { - r = ((r << 5) + r) + c; /* r * 33 + c */ - } - if (r == 0) { - usbi_warn(NULL, "'%s''s hash is 0!", sz); - } - return r; -} - #define USBI_GET_CONTEXT(ctx) if (!(ctx)) (ctx) = usbi_default_context #define DEVICE_CTX(dev) ((dev)->ctx) #define HANDLE_CTX(handle) (DEVICE_CTX((handle)->dev)) @@ -275,6 +255,15 @@ struct libusb_context { int timerfd; #endif + /* the following are used to maintain a hash table for session IDs */ + usbi_mutex_t htab_write_mutex; + unsigned long htab_size; + unsigned long htab_filled; + struct htab_entry { + unsigned long used; + char* str; + }* htab_table; + libusb_hotplug_cb_fn hotplug_connected_listener; libusb_hotplug_cb_fn hotplug_disconnected_listener; void* hotplug_listener_user_data; @@ -391,6 +380,7 @@ struct libusb_device *usbi_get_device_by_session_id(struct libusb_context *ctx, struct libusb_device *usbi_get_device_by_session_id_ref(struct libusb_context *ctx, unsigned long session_id); int usbi_sanitize_device(struct libusb_device *dev); +unsigned long usbi_htab_hash(struct libusb_context *ctx, const char* str); void usbi_handle_disconnect(struct libusb_device_handle *handle); int usbi_handle_transfer_completion(struct usbi_transfer *itransfer, diff --git a/libusb/os/linux_usbfs.c b/libusb/os/linux_usbfs.c index eed8a9c..f006fff 100644 --- a/libusb/os/linux_usbfs.c +++ b/libusb/os/linux_usbfs.c @@ -839,7 +839,7 @@ static int get_device(struct libusb_context* ctx, unsigned long session_id; int r = 0; - session_id = usbi_hash(sysfs_dir); + session_id = usbi_htab_hash(ctx, sysfs_dir); usbi_dbg("busnum %d devaddr %d session_id %ld", busnum, devaddr, session_id); @@ -2227,7 +2227,7 @@ static void handle_hotplug_event(struct libusb_context *ctx) } } else if (strncmp(udev_action, "remove", 6) == 0) { - dev = usbi_get_device_by_session_id_ref(ctx, usbi_hash(sys_name)); + dev = usbi_get_device_by_session_id_ref(ctx, usbi_htab_hash(ctx, sys_name)); if (dev) { pthread_mutex_lock(&dev->status_online_lock); dev->status_online = 0; diff --git a/libusb/os/windows_usb.c b/libusb/os/windows_usb.c index 547d9c1..6019bbb 100644 --- a/libusb/os/windows_usb.c +++ b/libusb/os/windows_usb.c @@ -391,177 +391,10 @@ err_exit: return NULL; } -/* 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 entries 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. */ -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; - 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 idx; - } - 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 idx; - } - } - 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); - if (htab_table[idx].str == NULL) { - usbi_err(NULL, "could not duplicate string for hash table"); - usbi_mutex_unlock(&htab_write_mutex); - return 0; - } - memcpy(htab_table[idx].str, str, safe_strlen(str)+1); - ++htab_filled; - usbi_mutex_unlock(&htab_write_mutex); - - return idx; -} - /* * Returns the Device ID path of a device's parent */ -static unsigned long get_parent_session_id(DWORD devinst) +static unsigned long get_parent_session_id(struct libusb_context *ctx, DWORD devinst) { DWORD parent_devinst; unsigned long session_id = 0; @@ -578,7 +411,7 @@ static unsigned long get_parent_session_id(DWORD devinst) if (sanitized_path == NULL) { return 0; } - session_id = htab_hash(sanitized_path); + session_id = usbi_htab_hash(ctx, sanitized_path); safe_free(sanitized_path); return session_id; } @@ -586,7 +419,7 @@ static unsigned long get_parent_session_id(DWORD devinst) /* * Returns the Device ID path of a device's grandparent */ -static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp) +static unsigned long get_grandparent_session_id(struct libusb_context *ctx, DWORD devinst, bool* non_usb_gp) { DWORD parent_devinst, grandparent_devinst; unsigned long session_id = 0; @@ -614,7 +447,7 @@ static unsigned long get_grandparent_session_id(DWORD devinst, bool* non_usb_gp) if (sanitized_path == NULL) { return 0; } - session_id = htab_hash(sanitized_path); + session_id = usbi_htab_hash(ctx, sanitized_path); safe_free(sanitized_path); return session_id; } @@ -813,7 +646,7 @@ LRESULT CALLBACK messaging_callback(HWND hWnd, UINT message, WPARAM wParam, LPAR // If it's an insertion, update the list libusb_get_device_list(ctx, &devs); } - dev = usbi_get_device_by_session_id(ctx, usbi_hash(hotplug_path)); + dev = usbi_get_device_by_session_id(ctx, usbi_htab_hash(ctx, hotplug_path)); if (dev == NULL) { usbi_warn(ctx, "%s: '%s' (not active)", (online)?"INSERTION":"REMOVAL", hotplug_path); @@ -1003,9 +836,6 @@ static int windows_init(struct libusb_context *ctx) goto init_exit; } - // Create a hash table to store session ids Second parameter is better if prime - htab_create(ctx, HTAB_SIZE); - r = LIBUSB_SUCCESS; } @@ -1035,7 +865,6 @@ init_exit: // Holds semaphore here. CloseHandle(timer_mutex); timer_mutex = NULL; } - htab_destroy(); } if (r != LIBUSB_SUCCESS) @@ -1557,7 +1386,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered case DEV_PASS: break; default: - session_id = get_parent_session_id(dev_info_data.DevInst); + session_id = get_parent_session_id(ctx, dev_info_data.DevInst); if (session_id == 0) { usbi_err(ctx, "program assertion failed: orphan device '%s'", dev_id_path); LOOP_BREAK(LIBUSB_ERROR_NO_DEVICE); @@ -1565,7 +1394,7 @@ static int windows_get_device_list(struct libusb_context *ctx, struct discovered parent_dev = usbi_get_device_by_session_id(ctx, session_id); // Composite HID devices have double indirection => Check grandparent if (pass == HID_PASS) { - session_id = get_grandparent_session_id(dev_info_data.DevInst, &non_usb_hid_parent); + session_id = get_grandparent_session_id(ctx, dev_info_data.DevInst, &non_usb_hid_parent); if (session_id == 0) { if (non_usb_hid_parent) { usbi_dbg("skipping non USB HID interface '%s'", dev_id_path); @@ -1598,7 +1427,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 = usbi_hash(dev_id_path); + session_id = usbi_htab_hash(ctx, dev_id_path); dev = usbi_get_device_by_session_id(ctx, session_id); if (dev != NULL) { // No need to re-process hubs @@ -1783,8 +1612,6 @@ static void windows_exit(struct libusb_context *ctx) TerminateThread(hotplug_thread, 1); } } - - htab_destroy(); } ReleaseSemaphore(semaphore, 1, NULL); // increase count back to 1 diff --git a/libusb/os/windows_usb.h b/libusb/os/windows_usb.h index 2138361..a1319ca 100644 --- a/libusb/os/windows_usb.h +++ b/libusb/os/windows_usb.h @@ -89,7 +89,6 @@ inline void upperize(char* str) { #define TIMER_REQUEST_RETRY_MS 100 #define ERR_BUFFER_SIZE 256 #define LIST_SEPARATOR ';' -#define HTAB_SIZE 1021 // Handle code for HID interface that have been claimed ("dibs") #define INTERFACE_CLAIMED ((HANDLE)(intptr_t)0xD1B5) |