[RFC 0/8] virtio,vhost: Add VIRTIO_F_IN_ORDER support

[Jonah Palmer]

The goal of these patches is to add support to a variety of virtio and
vhost devices for the VIRTIO_F_IN_ORDER transport feature. This feature
indicates that all buffers are used by the device in the same order in
which they were made available by the driver.

These patches attempt to implement a generalized, non-device-specific
solution to support this feature.

The core feature behind this solution is a buffer mechanism in the form
of GLib's GHashTable. The decision behind using a hash table was to
leverage their ability for quick lookup, insertion, and removal
operations. Given that our keys are simply numbers of an ordered
sequence, a hash table seemed like the best choice for a buffer
mechanism.

---------------------

The strategy behind this implementation is as follows:

We know that buffers that are popped from the available ring and enqueued
for further processing will always done in the same order in which they
were made available by the driver. Given this, we can note their order
by assigning the resulting VirtQueueElement a key. This key is a number
in a sequence that represents the order in which they were popped from
the available ring, relative to the other VirtQueueElements.

For example, given 3 "elements" that were popped from the available
ring, we assign a key value to them which represents their order (elem0
is popped first, then elem1, then lastly elem2):

     elem2   --  elem1   --  elem0   ---> Enqueue for processing
    (key: 2)    (key: 1)    (key: 0)

Then these elements are enqueued for further processing by the host.

While most devices will return these completed elements in the same
order in which they were enqueued, some devices may not (e.g.
virtio-blk). To guarantee that these elements are put on the used ring
in the same order in which they were enqueued, we can use a buffering
mechanism that keeps track of the next expected sequence number of an
element.

In other words, if the completed element does not have a key value that
matches the next expected sequence number, then we know this element is
not in-order and we must stash it away in a hash table until an order
can be made. The element's key value is used as the key for placing it
in the hash table.

If the completed element has a key value that matches the next expected
sequence number, then we know this element is in-order and we can push
it on the used ring. Then we increment the next expected sequence number
and check if the hash table contains an element at this key location.

If so, we retrieve this element, push it to the used ring, delete the
key-value pair from the hash table, increment the next expected sequence
number, and check the hash table again for an element at this new key
location. This process is repeated until we're unable to find an element
in the hash table to continue the order.

So, for example, say the 3 elements we enqueued were completed in the
following order: elem1, elem2, elem0. The next expected sequence number
is 0:

    exp-seq-num = 0:

     elem1   --> elem1.key == exp-seq-num ? --> No, stash it
    (key: 1)                                         |
                                                     |
                                                     v
                                               ================
                                               |key: 1 - elem1|
                                               ================
    ---------------------
    exp-seq-num = 0:

     elem2   --> elem2.key == exp-seq-num ? --> No, stash it
    (key: 2)                                         |
                                                     |
                                                     v
                                               ================
                                               |key: 1 - elem1|
                                               |--------------|
                                               |key: 2 - elem2|
                                               ================
    ---------------------
    exp-seq-num = 0:

     elem0   --> elem0.key == exp-seq-num ? --> Yes, push to used ring
    (key: 0)

    exp-seq-num = 1:

    lookup(table, exp-seq-num) != NULL ? --> Yes, push to used ring,
                                             remove elem from table
                                                     |
                                                     v
                                               ================
                                               |key: 2 - elem2|
                                               ================

    exp-seq-num = 2:

    lookup(table, exp-seq-num) != NULL ? --> Yes, push to used ring,
                                             remove elem from table
                                                     |
                                                     v
                                               ================
                                               |   *empty*    |
                                               ================

    exp-seq-num = 3:

    lookup(table, exp-seq-num) != NULL ? --> No, done
    ---------------------

Jonah Palmer (8):
  virtio: Define InOrderVQElement
  virtio: Create/destroy/reset VirtQueue In-Order hash table
  virtio: Define order variables
  virtio: Implement in-order handling for virtio devices
  virtio-net: in-order handling
  vhost-svq: in-order handling
  vhost/vhost-user: Add VIRTIO_F_IN_ORDER to vhost feature bits
  virtio: Add VIRTIO_F_IN_ORDER property definition

 hw/block/vhost-user-blk.c          |   1 +
 hw/net/vhost_net.c                 |   2 +
 hw/net/virtio-net.c                |   6 +-
 hw/scsi/vhost-scsi.c               |   1 +
 hw/scsi/vhost-user-scsi.c          |   1 +
 hw/virtio/vhost-shadow-virtqueue.c |  15 ++++-
 hw/virtio/vhost-user-fs.c          |   1 +
 hw/virtio/vhost-user-vsock.c       |   1 +
 hw/virtio/virtio.c                 | 103 ++++++++++++++++++++++++++++-
 include/hw/virtio/virtio.h         |  20 +++++-
 net/vhost-vdpa.c                   |   1 +
 11 files changed, 145 insertions(+), 7 deletions(-)

-- 
2.39.3