Changeset 7265558 in mainline

Timestamp:

2011-10-28T20:53:41Z (12 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.

Location:

uspace

Files:

• drv/bus/usb/ohci/hc.c (modified) (1 diff)
• drv/bus/usb/uhci/hc.c (modified) (1 diff)
• lib/usbhost/include/usb/host/endpoint.h (modified) (1 diff)
• lib/usbhost/include/usb/host/hcd.h (modified) (2 diffs)
• lib/usbhost/include/usb/host/usb_endpoint_manager.h (modified) (1 diff)
• lib/usbhost/src/endpoint.c (modified) (1 diff)
• lib/usbhost/src/usb_endpoint_manager.c (modified) (8 diffs)

uspace/drv/bus/usb/ohci/hc.c

@@ -192 +192 @@
         list_initialize(&instance->pending_batches);
 
-        ret = hcd_init(&instance->generic, BANDWIDTH_AVAILABLE_USB11,
+        hcd_init(&instance->generic, BANDWIDTH_AVAILABLE_USB11,
             bandwidth_count_usb11);
-        CHECK_RET_RETURN(ret, "Failed to initialize generic driver: %s.\n",
-            str_error(ret));
         instance->generic.private_data = instance;
         instance->generic.schedule = hc_schedule;

uspace/drv/bus/usb/uhci/hc.c

@@ -192 +192 @@
             "Device registers at %p (%zuB) accessible.\n", io, reg_size);
 
-        ret = hcd_init(&instance->generic, BANDWIDTH_AVAILABLE_USB11,
+        ret = hc_init_mem_structures(instance);
+        CHECK_RET_RETURN(ret,
+            "Failed to initialize UHCI memory structures: %s.\n",
+            str_error(ret));
+
+#undef CHECK_RET_RETURN
+
+        hcd_init(&instance->generic, BANDWIDTH_AVAILABLE_USB11,
             bandwidth_count_usb11);
-        CHECK_RET_RETURN(ret, "Failed to initialize HCD generic driver: %s.\n",
-            str_error(ret));
 
         instance->generic.private_data = instance;
         instance->generic.schedule = hc_schedule;
         instance->generic.ep_add_hook = NULL;
-
-#undef CHECK_RET_DEST_FUN_RETURN
-
-        ret = hc_init_mem_structures(instance);
-        if (ret != EOK) {
-                usb_log_error(
-                    "Failed to initialize UHCI memory structures: %s.\n",
-                    str_error(ret));
-                hcd_destroy(&instance->generic);
-                return ret;
-        }
 
         hc_init_hw(instance);

uspace/lib/usbhost/include/usb/host/endpoint.h

@@ -77 +77 @@
 int endpoint_toggle_get(endpoint_t *instance);
 void endpoint_toggle_set(endpoint_t *instance, int toggle);
-void endpoint_toggle_reset_filtered(endpoint_t *instance, usb_target_t target);
+
+static inline endpoint_t * endpoint_get_instance(link_t *item)
+{
+        return list_get_instance(item, endpoint_t, link);
+}
 #endif
 /**

uspace/lib/usbhost/include/usb/host/hcd.h

@@ -37 +37 @@
 
 #include <assert.h>
+#include <usbhc_iface.h>
 #include <usb/host/usb_device_manager.h>
 #include <usb/host/usb_endpoint_manager.h>
 #include <usb/host/usb_transfer_batch.h>
-#include <usbhc_iface.h>
 
 typedef struct hcd hcd_t;
@@ -53 +53 @@
 };
 /*----------------------------------------------------------------------------*/
-static inline int hcd_init(hcd_t *hcd, size_t bandwidth,
+static inline void hcd_init(hcd_t *hcd, size_t bandwidth,
     size_t (*bw_count)(usb_speed_t, usb_transfer_type_t, size_t, size_t))
 {
         assert(hcd);
         usb_device_manager_init(&hcd->dev_manager);
-        return usb_endpoint_manager_init(&hcd->ep_manager, bandwidth, bw_count);
-}
-/*----------------------------------------------------------------------------*/
-static inline void hcd_destroy(hcd_t *hcd)
-{
-        usb_endpoint_manager_destroy(&hcd->ep_manager);
+        usb_endpoint_manager_init(&hcd->ep_manager, bandwidth, bw_count);
 }
 /*----------------------------------------------------------------------------*/

uspace/lib/usbhost/include/usb/host/usb_endpoint_manager.h

@@ -40 +40 @@
 #define LIBUSBHOST_HOST_USB_ENDPOINT_MANAGER_H
 
-#include <stdlib.h>
-#include <adt/hash_table.h>
+#include <adt/list.h>
 #include <fibril_synch.h>
 #include <usb/usb.h>
+
 #include <usb/host/endpoint.h>
 
 #define BANDWIDTH_TOTAL_USB11 12000000
 #define BANDWIDTH_AVAILABLE_USB11 ((BANDWIDTH_TOTAL_USB11 / 10) * 9)
+#define ENDPOINT_LIST_COUNT 8
 
 typedef struct usb_endpoint_manager {
-        hash_table_t ep_table;
+        list_t endpoint_lists[ENDPOINT_LIST_COUNT];
         fibril_mutex_t guard;
         size_t free_bw;

uspace/lib/usbhost/src/endpoint.c

@@ -133 +133 @@
         instance->toggle = toggle;
 }
-/*----------------------------------------------------------------------------*/
-void endpoint_toggle_reset_filtered(endpoint_t *instance, usb_target_t target)
-{
-        assert(instance);
-        if (instance->address == target.address &&
-            (instance->endpoint == target.endpoint || target.endpoint == 0))
-                endpoint_toggle_set(instance, 0);
-}
 /**
  * @}

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);
                 }