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

[Ian Campbell <ian.campbell@xxxxxxxxxx>]

On Wed, 2015-06-03 at 12:55 +0530, Vijay Kilari wrote:
> 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?

I suspect we might need two list (or tree) entries for each its_device,
one for the pDevice mapping and one for the vDevice mapping. We may even
want a third for vCollection membership, I'm not sure.

Either way I don't think it'll be a big deal, the need or not for each
of those will fall out in the wash from the rest of the design, I think.

Based on the amount of discussion on draftC and the fact that we are
still finding new areas of complexity I'm going to take a step back and
try something simpler and see if I can come up with something which we
can get done for 4.6. I'll try and get a new draft reflecting that out
ASAP.

(I have my edits from the feedback on draftC so far in git, so if it
doesn't work we can always take up this one again...)



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