Changeset 93939 in vbox for trunk/src/VBox/Devices

Timestamp:

Feb 24, 2022 5:23:37 PM (3 years ago)

Author:

vboxsync

svn:sync-xref-src-repo-rev:

150168

Message:

Devices/USB: Get rid of the address hashing mechanism and replace it with a lookup table approach, bugref:10196

Location:

trunk/src/VBox/Devices/USB

Files:

• DrvVUSBRootHub.cpp (modified) (4 diffs)
• VUSBDevice.cpp (modified) (4 diffs)
• VUSBInternal.h (modified) (5 diffs)

trunk/src/VBox/Devices/USB/DrvVUSBRootHub.cpp

@@ -258 +258 @@
     pDev = pThis->apDevByPort[uPort];
     if (RT_LIKELY(pDev))
-        ASMAtomicIncU32(&pDev->cRefs);
+        vusbDevRetain(pDev);
+
+    RTCritSectLeave(&pThis->CritSectDevices);
+
+    return pDev;
+}
+
+
+/**
+ * Returns the attached VUSB device for the given port or NULL if none is attached.
+ *
+ * @returns Pointer to the VUSB device or NULL if not found.
+ * @param   pThis               The VUSB roothub device instance.
+ * @param   u8Address           The address to get the device for.
+ *
+ * @note The reference count of the VUSB device structure is retained to prevent it from going away.
+ */
+static PVUSBDEV vusbR3RhGetVUsbDevByAddrRetain(PVUSBROOTHUB pThis, uint8_t u8Address)
+{
+    PVUSBDEV pDev = NULL;
+
+    AssertReturn(u8Address < RT_ELEMENTS(pThis->apDevByAddr), NULL);
+
+    RTCritSectEnter(&pThis->CritSectDevices);
+
+    pDev = pThis->apDevByAddr[u8Address];
+    if (RT_LIKELY(pDev))
+        vusbDevRetain(pDev);
 
     RTCritSectLeave(&pThis->CritSectDevices);
@@ -353 +380 @@
 
 /**
- * Finds an device attached to a roothub by it's address.
- *
- * @returns Pointer to the device.
- * @returns NULL if not found.
- * @param   pRh         Pointer to the root hub.
- * @param   Address     The device address.
- */
-static PVUSBDEV vusbRhFindDevByAddress(PVUSBROOTHUB pRh, uint8_t Address)
-{
-    unsigned iHash = vusbHashAddress(Address);
-    PVUSBDEV pDev = NULL;
-
-    RTCritSectEnter(&pRh->CritSectDevices);
-    for (PVUSBDEV pCur = pRh->apAddrHash[iHash]; pCur; pCur = pCur->pNextHash)
-        if (pCur->u8Address == Address)
-        {
-            pDev = pCur;
-            break;
-        }
-
-    if (pDev)
-        vusbDevRetain(pDev);
-    RTCritSectLeave(&pRh->CritSectDevices);
-    return pDev;
-}
-
-
-/**
  * Callback for freeing an URB.
  * @param   pUrb    The URB to free.
@@ -434 +433 @@
     PVUSBDEV pDev;
     if (uPort == VUSB_DEVICE_PORT_INVALID)
-        pDev = vusbRhFindDevByAddress(pRh, DstAddress);
+        pDev = vusbR3RhGetVUsbDevByAddrRetain(pRh, DstAddress);
     else
         pDev = vusbR3RhGetVUsbDevByPortRetain(pRh, uPort);
@@ -1449 +1448 @@
     Assert(pDev->i16Port != -1);
 
-    /*
-     * Check that it's attached and unlink it from the linked list.
-     */
+    /* Check that it's attached and remvoe it. */
     RTCritSectEnter(&pRh->CritSectDevices);
     Assert(pRh->apDevByPort[pDev->i16Port] == pDev);
-    pRh->apDevByPort[pDev->i16Port] = NULL;
+    pRh->apDevByPort[pDev->i16Port]   = NULL;
+
+    if (pDev->u8Address == VUSB_DEFAULT_ADDRESS)
+    {
+        AssertPtr(pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS]);
+
+        if (pDev == pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS])
+            pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS] = pDev->pNextDefAddr;
+        else
+        {
+            /* Search the list for the device and remove it. */
+            PVUSBDEV pDevPrev = pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS];
+
+            while (   pDevPrev
+                   && pDevPrev->pNextDefAddr != pDev)
+                pDevPrev = pDevPrev->pNextDefAddr;
+
+            AssertPtr(pDevPrev);
+            pDevPrev->pNextDefAddr = pDev->pNextDefAddr;
+        }
+
+        pDev->pNextDefAddr = NULL;
+    }
+    else
+    {
+        Assert(pRh->apDevByAddr[pDev->u8Address] == pDev);
+        pRh->apDevByAddr[pDev->u8Address] = NULL;
+    }
     RTCritSectLeave(&pRh->CritSectDevices);
 

trunk/src/VBox/Devices/USB/VUSBDevice.cpp

@@ -994 +994 @@
 
 /**
- * Add a device to the address hash
- */
-static void vusbDevAddressHash(PVUSBDEV pDev)
-{
-    if (pDev->u8Address == VUSB_INVALID_ADDRESS)
-        return;
-    uint8_t u8Hash = vusbHashAddress(pDev->u8Address);
-    pDev->pNextHash = pDev->pHub->pRootHub->apAddrHash[u8Hash];
-    pDev->pHub->pRootHub->apAddrHash[u8Hash] = pDev;
-}
-
-/**
- * Remove a device from the address hash
- */
-static void vusbDevAddressUnHash(PVUSBDEV pDev)
-{
-    if (pDev->u8Address == VUSB_INVALID_ADDRESS)
-        return;
-
-    uint8_t u8Hash = vusbHashAddress(pDev->u8Address);
-    pDev->u8Address = VUSB_INVALID_ADDRESS;
-    pDev->u8NewAddress = VUSB_INVALID_ADDRESS;
-
-    RTCritSectEnter(&pDev->pHub->pRootHub->CritSectDevices);
-    PVUSBDEV pCur = pDev->pHub->pRootHub->apAddrHash[u8Hash];
-    if (pCur == pDev)
-    {
-        /* special case, we're at the head */
-        pDev->pHub->pRootHub->apAddrHash[u8Hash] = pDev->pNextHash;
-        pDev->pNextHash = NULL;
-    }
-    else
-    {
-        /* search the list */
-        PVUSBDEV pPrev;
-        for (pPrev = pCur, pCur = pCur->pNextHash;
-             pCur;
-             pPrev = pCur, pCur = pCur->pNextHash)
-        {
-            if (pCur == pDev)
-            {
-                pPrev->pNextHash = pCur->pNextHash;
-                pDev->pNextHash = NULL;
-                break;
-            }
-        }
-    }
-    RTCritSectLeave(&pDev->pHub->pRootHub->CritSectDevices);
-}
-
-/**
  * Sets the address of a device.
  *
@@ -1077 +1026 @@
         return;
 
+    /** @todo The following logic belongs to the roothub and should actually be in that file. */
     PVUSBROOTHUB pRh = vusbDevGetRh(pDev);
     AssertPtrReturnVoid(pRh);
+
+    RTCritSectEnter(&pRh->CritSectDevices);
+
+    /* Remove the device from the current address. */
     if (pDev->u8Address == VUSB_DEFAULT_ADDRESS)
-        pRh->pDefaultAddress = NULL;
-
-    vusbDevAddressUnHash(pDev);
+    {
+        AssertPtr(pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS]);
+
+        if (pDev == pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS])
+            pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS] = pDev->pNextDefAddr;
+        else
+        {
+            /* Search the list for the device and remove it. */
+            PVUSBDEV pDevPrev = pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS];
+
+            while (   pDevPrev
+                   && pDevPrev->pNextDefAddr != pDev)
+                pDevPrev = pDevPrev->pNextDefAddr;
+
+            AssertPtr(pDevPrev);
+            pDevPrev->pNextDefAddr = pDev->pNextDefAddr;
+        }
+
+        pDev->pNextDefAddr = NULL;
+    }
+    else
+        pRh->apDevByAddr[pDev->u8Address] = NULL;
 
     if (u8Address == VUSB_DEFAULT_ADDRESS)
     {
-        if (pRh->pDefaultAddress != NULL)
+        PVUSBDEV pDevDef = pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS];
+
+        if (pDevDef)
         {
-            vusbDevAddressUnHash(pRh->pDefaultAddress);
-            vusbDevSetStateCmp(pRh->pDefaultAddress, VUSB_DEVICE_STATE_POWERED, VUSB_DEVICE_STATE_DEFAULT);
+            vusbDevSetStateCmp(pDevDef, VUSB_DEVICE_STATE_POWERED, VUSB_DEVICE_STATE_DEFAULT);
             Log(("2 DEFAULT ADDRS\n"));
         }
 
-        pRh->pDefaultAddress = pDev;
+        pDev->pNextDefAddr = pDevDef;
+        pRh->apDevByAddr[VUSB_DEFAULT_ADDRESS] = pDev;
         vusbDevSetState(pDev, VUSB_DEVICE_STATE_DEFAULT);
     }
     else
+    {
+        Assert(!pRh->apDevByAddr[u8Address]);
+        pRh->apDevByAddr[u8Address] = pDev;
         vusbDevSetState(pDev, VUSB_DEVICE_STATE_ADDRESS);
+    }
+
+    RTCritSectLeave(&pRh->CritSectDevices);
 
     pDev->u8Address = u8Address;
-    vusbDevAddressHash(pDev);
 
     Log(("vusb: %p[%s]/%i: Assigned address %u\n",
@@ -1327 +1307 @@
 
     vusbDevCancelAllUrbs(pDev, true);
-    vusbDevAddressUnHash(pDev);
 
     PVUSBROOTHUB pRh = vusbDevGetRh(pDev);
     if (!pRh)
         AssertMsgFailedReturn(("Not attached!\n"), VERR_VUSB_DEVICE_NOT_ATTACHED);
-    if (pRh->pDefaultAddress == pDev)
-        pRh->pDefaultAddress = NULL;
-
+
+    /* The roothub will remove the device from the address to device array. */
     pDev->pHub->pOps->pfnDetach(pDev->pHub, pDev);
     pDev->i16Port = -1;
@@ -1842 +1820 @@
     pDev->IDevice.pfnGetSpeed = vusbIDeviceGetSpeed;
     pDev->pUsbIns = pUsbIns;
-    pDev->pNext = NULL;
-    pDev->pNextHash = NULL;
+    pDev->pNextDefAddr = NULL;
     pDev->pHub = NULL;
     pDev->enmState = VUSB_DEVICE_STATE_DETACHED;

trunk/src/VBox/Devices/USB/VUSBInternal.h

@@ -225 +225 @@
     /** Pointer to the PDM USB device instance. */
     PPDMUSBINS          pUsbIns;
-    /** Next device in the chain maintained by the roothub. */
-    PVUSBDEV            pNext;
-    /** Pointer to the next device with the same address hash. */
-    PVUSBDEV            pNextHash;
+    /** Next device in the chain of devices with the default address. */
+    PVUSBDEV            pNextDefAddr;
     /** Pointer to the hub this device is attached to. */
     PVUSBHUB            pHub;
@@ -380 +378 @@
 typedef struct VUSBROOTHUBLOAD *PVUSBROOTHUBLOAD;
 
-/** The address hash table size. */
-#define VUSB_ADDR_HASHSZ    5
-
 /**
  * The instance data of a root hub driver.
@@ -395 +390 @@
      * @todo remove this? */
     VUSBHUB                     Hub;
-    /** Address hash table. */
-    PVUSBDEV                    apAddrHash[VUSB_ADDR_HASHSZ];
-    /** The default address. */
-    PVUSBDEV                    pDefaultAddress;
-
     /** Pointer to the driver instance. */
     PPDMDRVINS                  pDrvIns;
@@ -411 +401 @@
     /** Array of pointers to USB devices indexed by the port the device is on. */
     PVUSBDEV                    apDevByPort[VUSB_DEVICES_MAX];
+    /** Array of pointers to USB devices indexed by the address assigned. */
+    PVUSBDEV                    apDevByAddr[VUSB_DEVICES_MAX];
     /** Structure after a saved state load to re-attach devices. */
     PVUSBROOTHUBLOAD            pLoad;
@@ -644 +636 @@
 
 
-
-
-/**
- * Addresses are between 0 and 127 inclusive
- */
-DECLINLINE(uint8_t) vusbHashAddress(uint8_t Address)
-{
-    uint8_t u8Hash = Address;
-    u8Hash ^= (Address >> 2);
-    u8Hash ^= (Address >> 3);
-    u8Hash %= VUSB_ADDR_HASHSZ;
-    return u8Hash;
-}
-
-
 /**
  * Gets the roothub of a device.