Changeset 7265558 in mainline for uspace/lib/usbhost/src/usb_endpoint_manager.c

Timestamp:

2011-10-28T20:53:41Z (14 years ago)

Author:

Jan Vesely <jano.vesely@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

48ae3ef

Parents:

83c3123

Message:

libusbhost: Drop hash_table and use multiple lists instead.

This has several advantages:
Knowing that all endpoints on one address are in one list makes toggle resets more efficient.
Endpoint search is done only once for inserts and deletes.
Lists are part of the structure and not allocated separately, removing one more failure point from init path.

File:

• uspace/lib/usbhost/src/usb_endpoint_manager.c (modified) (8 diffs)

uspace/lib/usbhost/src/usb_endpoint_manager.c

@@ -34 +34 @@
 #include <usb/host/usb_endpoint_manager.h>
 
-#define BUCKET_COUNT 7
-#define MAX_KEYS (3)
-
-static hash_index_t usb_hash(unsigned long key[])
-{
-        /* USB endpoints use 4 bits, thus ((key[0] << 4) | key[1])
-         * produces unique value for every address.endpoint pair */
-        return ((key[0] << 4) | key[1]) % BUCKET_COUNT;
-}
-/*----------------------------------------------------------------------------*/
-static int ep_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-        assert(item);
-        endpoint_t *ep = hash_table_get_instance(item, endpoint_t, link);
+static inline bool ep_match(const endpoint_t *ep,
+    usb_address_t address, usb_endpoint_t endpoint, usb_direction_t direction)
+{
         assert(ep);
-        bool match = true;
-        switch (keys) {
-        case 3:
-                match = match &&
-                    ((key[2] == ep->direction)
-                    || (ep->direction == USB_DIRECTION_BOTH)
-                    || (key[2] == USB_DIRECTION_BOTH));
-        case 2:
-                match = match && (key[1] == (unsigned long)ep->endpoint);
-        case 1:
-                match = match && (key[0] == (unsigned long)ep->address);
-                break;
-        default:
-                match = false;
-        }
-        return match;
-}
-/*----------------------------------------------------------------------------*/
-static void ep_remove(link_t *item)
-{
-        assert(item);
-        endpoint_t *ep = hash_table_get_instance(item, endpoint_t, link);
-        endpoint_destroy(ep);
-}
-/*----------------------------------------------------------------------------*/
-static void toggle_reset_filtered(link_t *item, void *arg)
-{
-        assert(item);
-        endpoint_t *ep = hash_table_get_instance(item, endpoint_t, link);
-        const usb_target_t *target = arg;
-        endpoint_toggle_reset_filtered(ep, *target);
-}
-/*----------------------------------------------------------------------------*/
-static hash_table_operations_t op = {
-        .hash = usb_hash,
-        .compare = ep_compare,
-        .remove_callback = ep_remove,
-};
+        return
+            ((direction == ep->direction)
+                || (ep->direction == USB_DIRECTION_BOTH)
+                || (direction == USB_DIRECTION_BOTH))
+            && (endpoint == ep->endpoint)
+            && (address == ep->address);
+}
+/*----------------------------------------------------------------------------*/
+static list_t * get_list(usb_endpoint_manager_t *instance, usb_address_t addr)
+{
+        assert(instance);
+        return &instance->endpoint_lists[addr % ENDPOINT_LIST_COUNT];
+}
+/*----------------------------------------------------------------------------*/
+static endpoint_t * find_locked(usb_endpoint_manager_t *instance,
+    usb_address_t address, usb_endpoint_t endpoint, usb_direction_t direction)
+{
+        assert(instance);
+        assert(fibril_mutex_is_locked(&instance->guard));
+        list_foreach(*get_list(instance, address), iterator) {
+                endpoint_t *ep = endpoint_get_instance(iterator);
+                if (ep_match(ep, address, endpoint, direction))
+                        return ep;
+        }
+        return NULL;
+}
 /*----------------------------------------------------------------------------*/
 size_t bandwidth_count_usb11(usb_speed_t speed, usb_transfer_type_t type,
@@ -99 +76 @@
         const unsigned packet_count =
             (size + max_packet_size - 1) / max_packet_size;
-        /* TODO: It may be that ISO and INT transfers use only one data packet
-         * per transaction, but I did not find text in UB spec that confirms
-         * this */
+        /* TODO: It may be that ISO and INT transfers use only one packet per
+         * transaction, but I did not find text in USB spec to confirm this */
         /* NOTE: All data packets will be considered to be max_packet_size */
         switch (speed)
@@ -138 +114 @@
         instance->free_bw = available_bandwidth;
         instance->bw_count = bw_count;
-        const bool ht =
-            hash_table_create(&instance->ep_table, BUCKET_COUNT, MAX_KEYS, &op);
-        return ht ? EOK : ENOMEM;
-}
-/*----------------------------------------------------------------------------*/
-void usb_endpoint_manager_destroy(usb_endpoint_manager_t *instance)
-{
-        hash_table_destroy(&instance->ep_table);
+        for (unsigned i = 0; i < ENDPOINT_LIST_COUNT; ++i) {
+                list_initialize(&instance->endpoint_lists[i]);
+        }
+        return EOK;
 }
 /*----------------------------------------------------------------------------*/
@@ -164 +136 @@
         }
 
-        unsigned long key[MAX_KEYS] =
-            {ep->address, ep->endpoint, ep->direction};
-
-        const link_t *item =
-            hash_table_find(&instance->ep_table, key);
-        if (item != NULL) {
+        /* Check for existence */
+        const endpoint_t *endpoint =
+            find_locked(instance, ep->address, ep->endpoint, ep->direction);
+        if (endpoint != NULL) {
                 fibril_mutex_unlock(&instance->guard);
                 return EEXISTS;
         }
-
-        hash_table_insert(&instance->ep_table, key, &ep->link);
+        list_t *list = get_list(instance, ep->address);
+        list_append(&ep->link, list);
+
         instance->free_bw -= ep->bandwidth;
         fibril_mutex_unlock(&instance->guard);
@@ -184 +155 @@
 {
         assert(instance);
-        unsigned long key[MAX_KEYS] = {address, endpoint, direction};
 
         fibril_mutex_lock(&instance->guard);
-        link_t *item = hash_table_find(&instance->ep_table, key);
-        if (item == NULL) {
-                fibril_mutex_unlock(&instance->guard);
-                return EINVAL;
-        }
-
-        endpoint_t *ep = hash_table_get_instance(item, endpoint_t, link);
-        if (ep->active) {
-                fibril_mutex_unlock(&instance->guard);
-                return EBUSY;
-        }
-
-        instance->free_bw += ep->bandwidth;
-        hash_table_remove(&instance->ep_table, key, MAX_KEYS);
+        endpoint_t *ep = find_locked(instance, address, endpoint, direction);
+        if (ep != NULL) {
+                list_remove(&ep->link);
+                instance->free_bw += ep->bandwidth;
+        }
 
         fibril_mutex_unlock(&instance->guard);
-        return EOK;
+        endpoint_destroy(ep);
+        return (ep != NULL) ? EOK : EINVAL;
 }
 /*----------------------------------------------------------------------------*/
@@ -210 +172 @@
 {
         assert(instance);
-        unsigned long key[MAX_KEYS] = {address, endpoint, direction};
 
         fibril_mutex_lock(&instance->guard);
-        const link_t *item = hash_table_find(&instance->ep_table, key);
-        if (item == NULL) {
-                fibril_mutex_unlock(&instance->guard);
-                return NULL;
-        }
-        endpoint_t *ep = hash_table_get_instance(item, endpoint_t, link);
-
+        endpoint_t *ep = find_locked(instance, address, endpoint, direction);
         fibril_mutex_unlock(&instance->guard);
+
         return ep;
 }
@@ -247 +203 @@
                 /* Recipient is endpoint, value is zero (ENDPOINT_STALL) */
                 if (((data[0] & 0xf) == 1) && ((data[2] | data[3]) == 0)) {
+                        fibril_mutex_lock(&instance->guard);
                         /* endpoint number is < 16, thus first byte is enough */
-                        usb_target_t reset_target =
-                            { .address = target.address, data[4] };
-                        fibril_mutex_lock(&instance->guard);
-                        hash_table_apply(&instance->ep_table,
-                            toggle_reset_filtered, &reset_target);
+                        list_foreach(*get_list(instance, target.address), it) {
+                                endpoint_t *ep = endpoint_get_instance(it);
+                                if ((ep->address == target.address)
+                                    && (ep->endpoint = data[4])) {
+                                        endpoint_toggle_set(ep,0);
+                                }
+                        }
                         fibril_mutex_unlock(&instance->guard);
                 }
@@ -259 +218 @@
         case 0x9: /* Set Configuration */
         case 0x11: /* Set Interface */
-                /* Recipient must be device */
+                /* Recipient must be device, this resets all endpoints,
+                 * In fact there should be no endpoints but EP 0 registered
+                 * as different interfaces use different endpoints. */
                 if ((data[0] & 0xf) == 0) {
-                        usb_target_t reset_target =
-                            { .address = target.address, 0 };
                         fibril_mutex_lock(&instance->guard);
-                        hash_table_apply(&instance->ep_table,
-                            toggle_reset_filtered, &reset_target);
+                        list_foreach(*get_list(instance, target.address), it) {
+                                endpoint_t *ep = endpoint_get_instance(it);
+                                if (ep->address == target.address) {
+                                        endpoint_toggle_set(ep,0);
+                                }
+                        }
                         fibril_mutex_unlock(&instance->guard);
                 }