Hi Jonah, Would you mind helping explain how does VIRTIO_F_IN_ORDER improve the performance?
https://lore.kernel.org/all/20240321155717.1392787-1-jonah.pal...@oracle.com/#t I tried to look for it from prior discussions but could not find why. https://lore.kernel.org/all/byapr18mb2791df7e6c0f61e2d8698e8fa0...@byapr18mb2791.namprd18.prod.outlook.com/ Thank you very much! Dongli Zhang On 3/21/24 08:57, Jonah Palmer wrote: > 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(-) >
