Re: [Draft C] Xen on ARM vITS Handling

[Ian Campbell <ian.campbell@citrix.com>]

On Mon, 2015-06-01 at 13:24 +0100, Julien Grall 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.
> >>>
> >>> 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.

I added "The `ID` is per domain and therefore the datastructure should
be too." before "Possible efficient..."

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

Yes, I suppose we can allocate at PHYSDEVOP_pci_device_add time, but
linking it into the R-B tree will have to happen at assignment time.

This section now ends:

        When `PHYSDEVOP_pci_device_add` is called, memory for its_device
        structure and other needed structure for this device is allocated.
        
        When `XEN_DOMCTL_assign_device` is called the device will be added to
        the per domain RB-tree with all necessary information.

Ian.