[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [Draft C] Xen on ARM vITS Handling
On Mon, Jun 1, 2015 at 5:54 PM, Julien Grall <julien.grall@xxxxxxxxxx> wrote: > On 01/06/15 13:11, Ian Campbell wrote: >>>> ### Device ID (`ID`) >>>> >>>> This parameter is used by commands which manage a specific device and >>>> the interrupts associated with that device. Checking if a device is >>>> present and retrieving the data structure must be fast. >>>> >>>> The device identifiers may not be assigned contiguously and the maximum >>>> number is very high (2^32). >>>> >>>> XXX In the context of virtualised device ids this may not be the case, >>>> e.g. we can arrange for (mostly) contiguous device ids and we know the >>>> bound is significantly lower than 2^32 >>>> >>>> Possible efficient data structures would be: >>>> >>>> 1. List: The lookup/deletion is in O(n) and the insertion will depend >>>> if the device should be sorted following their identifier. The >>>> memory overhead is 18 bytes per element. >>>> 2. Red-black tree: All the operations are O(log(n)). The memory >>>> overhead is 24 bytes per element. How about using radix-tree instead of RB-tree? >>>> >>>> A Red-black tree seems the more suitable for having fast deviceID >>>> validation even though the memory overhead is a bit higher compare to >>>> the list. >>> >>> When PHYSDEVOP_pci_device_add is called, memory for its_device structure >>> and other needed structure for this device is allocated added to RB-tree >>> with all necessary information >> >> Sounds like a reasonable time to do it. I added something based on your >> words. > > Hmmm... The RB-tree suggested is per domain not the host and indexed > with the vDevID. > > This is the only way to know quickly if the domain is able to use the > device and retrieving a device. Indeed, the vDevID won't be equal to the > pDevID as the vBDF will be different to the pBDF. Yes, vBDF is converted to pBDF to match DevID > > PHYSDEVOP_pci_device_add is to ask Xen managing the PCI device. At that > time we don't know to which domain the device will be passthrough. PHYSDEVOP_pci_device_add will only add its_device to global radix tree list. When MAPD is received, its_device is removed from global list and added to per domain list. When domain releases the device, its_device is added back to global list. is it ok? _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxx http://lists.xen.org/xen-devel
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |