[libvirt] [GSoC] Abstracting device address allocation

[Tomasz Flendrich]

Hello everyone,

Let me introduce myself - I'm Tomasz Flendrich and I'm a Google Summer
of Code student from University of Wrocław, Poland.

My goal is to create a generic address allocator (for PCI, virtio,
SCSI, etc.), because current handling of addresses has its flaws:
sometimes addresses aren't properly assigned and checked for duplicates.
Additionally, a generic solution will be very useful when more hypervisors
add the feature of explicitly stating the addresses of devices.

The key goal I'm willing to achieve at this moment is defining
a minimum viable product (one thing to be implemented quickly
which is reasonably complete on its own, and has potential for further
development in the direction which makes sense).


I came up with an initial design. The internal allocator's data
will be kept in struct Allocator. There will be one structure
for one address type and all of the allocators would be in an array.

We will have the possibility of adding an address pool to the allocator.
For example, when we create a root PCI bus, we tell the allocator that
the following PCI addresses are possible: {0..0}:{0..31}.{0..7},
where {a..b} means a range from a to b, inclusive.

This function call could look like this:
allocatorAddPool(
   allocator[PCI_ADDRESS_TYPE],
   &outputAddress,
   AllocatorRange(0, 0),
   AllocatorRange(0, 31),
   AllocatorRange(0, 7));

The outputAddress would be an array owned by the caller
(only filled in by the allocator).


If we were to allocate IP addresses for computers from the range
192.168.1.2 to 192.168.1.240, where the router has to have
the address 192.168.1.254:

First, we reserve the address for the router to let the Allocator know
that it's in use, and that we can track collisions in manually
assigned addresses:

allocatorReserveAddress(
   allocator[IP_ADDRESS_TYPE],
   &outputAddress,
   AllocatorValue(192),
   AllocatorValue(168),
   AllocatorValue(1),
   AllocatorValue(254));

Then, we assign the addresses for the computers:

allocatorReserveAddress(
   allocator[IP_ADDRESS_TYPE],
   &outputAddress,
   AllocatorValue(192),
   AllocatorValue(168),
   AllocatorValue(1),
   AllocatorRange(1, 254));
Please note that AllocatorValue() is now in use.

There could be a different function call to simply assign any address:
allocatorReserveAny(Allocator* allocator, &outputAddress);

Let's say that we want an "sda" disk. We could create a wrapper:
allocatorReserveSCSIAddress(allocator, "sda");
All this wrapper does is representing the string "sda" as an integer
mapping to the letter (eg. 'a' = 0, 'z' = 25):
allocatorReserveAddress(allocator[SCSI_ADDRESS_TYPE], &outputAddress, 0);

If an address is already determined, because it was specified in the XML
or it's some specific device that has to be at some specific address,
we still reserve it to let the Allocator know that it's in use.


How would this work internally?
One of the possible solutions is keeping a set of ranges of addresses.
For example, suppose that we have two PCI busses to use. Our address pool
is stored as one range:
{0..1} {0..31} {0..7}

Now someone reserves address 0:13.2

Our new free addresses pool is now stored as this set of ranges:
{0..0} {0..12} {0..7},
{0..0} {12..12} {0..1},
{0..0} {12..12} {3..7},
{0..0} {13..31} {0..7},
{1..1} {0..31} {0..7}

If we kept every address separately, it would require 2*32*8=512 addresses.

The set data structure from gnulib's gl_oset.h is a candidate for keeping
the ranges in a sorted fashion. Another candidate is simply a sorted list
from gl_list.h.

This structure would be able to handle all types of addresses that are
convertible to a fixed-length list of integers. We don't mind how many
of these integers there are, because we can use variadic arguments.
It won't allow duplicates if we stick to using it in every place where
we have some addresses.
It will also be very generic, with the possibility of writing wrappers on top
of it that might be more convenient for some particular address type.

This way we would keep qemu_* files as they are for now, and just replace
existing allocators (and manual assignment of addresses) to calls to our
new allocator.

My ideas:
- A possibility of reserving a range of addresses might be used
  to reserve a whole PCI slot at once.
- Flags could be added, changing the behavior of particular
  addresses or the whole allocator.

My questions:
- Is this approach good long-term?
- Is address releasing expected to be required at any point?
  (think device hotplug/unplug, etc.)
- What other features are needed?

Please speak up your mind if you have remarks or thoughts about the idea.
I'd really appreciate it.

Tomasz