Re: [Xen-devel] [Draft C] Xen on ARM vITS Handling

[Julien Grall <julien.grall@xxxxxxxxxx>]

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.
>>>
>>> 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.

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.

Regards,

-- 
Julien Grall

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel