本文将基于第一性原理，深入解析virtio packed virtqueue机制。

Prerequisite

读者需要对split virtqueue有深刻的理解。

Terms

  1. 本文将virtio spec中标准的”Driver Ring Wrap Counter”统称为avail_wrap_counter
  2. 本文将virtio spec中标准的”Device Ring Wrap Counter”统称为used_wrap_counter

Motivation

For software backends

  • Bad cache utilization, several cache misses per request
    • metadata is scattered into several places
    • descriptor chain is not contiguous in memory
    • cache contention in many places

For hardware implementation

  • several PCIe transactions per descriptor

Overview

packed virtqueue将virtio1.0中的desc ring，avail ring，used ring三个ring打包成一个desc ring了。

相对split desc去掉了next字段

在split desc中next字段是记录一个desc chain中的下一个desc idx使用的，通常配合flags这样使用：

1
2
if ((descs[idx].flags & VRING_DESC_F_NEXT) == 1)
        nextdesc = descs[ descs[idx].next];

但是在packed desc ring中一个desc chain一定是相邻的（可以理解为链表变为了数组），所以next字段就用不上了，上面获取nextdesc的方式可以转化为如下方式：

1
2
if ((descs[idx].flags & VRING_DESC_F_NEXT) == 1)
        nextdesc = descs[++idx];

flags字段的变化

为了仅仅使用desc ring就能标记avail ring与used ring信息，packed virtqueue引入了avail_wrap_counter与used_wrap_counter这两个flag。相对split desc，flags字段仍然保留，但是其取值增加了，因为要把三个ring合一，每个desc就需要更多的信息表明身份（是used还是avail）。在原有flags的基础上增加了两个flag：

1
2
#define VRING_DESC_F_AVAIL          (1ULL << 7)
#define VRING_DESC_F_USED (1ULL << 15)

avail desc：当desc flags关于VRING_DESC_F_AVAIL的设置和avail_wrap_counter同步，且VRING_DESC_F_USED的设置和avail_wrap_counter相反时，表示desc为avail desc。例如avail_wrap_counter为1时，flags应该设置VRING_DESC_F_AVAIL|~VRING_DESC_F_USED，当avail_wrap_counter为0时，flags应该设置~VRING_DESC_F_AVAIL|VRING_DESC_F_USED。

used desc：当desc flags关于VRING_DESC_F_USED的设置和used_wrap_counter同步，且VRING_DESC_F_AVAIL的设置也和used_wrap_counter同步时，表示desc为used desc。例如used_wrap_counter为1时，flags应该设置VRING_DESC_F_AVAIL|VRING_DESC_F_USED，当used_wrap_counter为0时，flags应该设置~VRING_DESC_F_AVAIL|~VRING_DESC_F_USED。

综上可以看出，avail desc的两个flag总是相反的（只能设置一个），而used desc的两个flag总是相同的，要么都设置，要么都不设置。

相对split desc增加了id字段

这个id比较特殊，他是buffer id，注意不是desc的下标idx。

核心要点

last_used_idx <= used_idx <= last_avail_idx <= avail_idx

  1. avail_idx/avail_wrap_counter会由driver的局部变量维护
  2. last_avail_idx/对应时刻的avail_wrap_counter会由device的局部变量维护
  3. used_idx/used_wrap_counter会由device的局部变量维护
  4. last_used_idx/对应时刻的used_wrap_counter会由driver的局部变量维护

Placing Available Buffers Into The Descriptor Ring

For each buffer element, b:

  1. Get the next descriptor table entry, d
  2. Get the next free buffer id value
  3. Set d.addr to the physical address of the start of b
  4. Set d.len to the length of b.
  5. Set d.id to the buffer id
  6. Calculate the flags as follows:
    1. If b is device-writable, set the VIRTQ_DESC_F_WRITE bit to 1, otherwise 0
    2. Set the VIRTQ_DESC_F_AVAIL bit to the current value of the Driver Ring Wrap Counter
    3. Set the VIRTQ_DESC_F_USED bit to inverse value
  7. Perform a memory barrier to ensure that the descriptor has been initialized
  8. Set d.flags to the calculated flags value
  9. If d is the last descriptor in the ring, toggle the Driver Ring Wrap Counter
  10. Otherwise, increment d to point at the next descriptor

This makes a single descriptor buffer available. However, in general the driver MAY make use of a batch of descriptors as part of a single request. In that case, it defers updating the descriptor flags for the first descriptor (and the previous memory barrier) until after the rest of the descriptors have been initialized.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* Note: vq->avail_wrap_count is initialized to 1 */ 
/* Note: vq->sgs is an array same size as the ring */ 
 
id = alloc_id(vq); 
 
first = vq->next_avail; 
sgs = 0; 
for (each buffer element b) {
        sgs++; 
 
        vq->desc[vq->next_avail].address = get_addr(b); 
        vq->desc[vq->next_avail].len = get_len(b); 
 
        avail = vq->avail_wrap_count ? VIRTQ_DESC_F_AVAIL : 0; 
        used = !vq->avail_wrap_count ? VIRTQ_DESC_F_USED : 0; 
        f = get_flags(b) | avail | used; 
        if (b is not the last buffer element) { 
                f |= VIRTQ_DESC_F_NEXT; 
        } 

        vq->desc[vq->next_avail].id = id; 
 
        /* Don’t mark the 1st descriptor available until all of them are ready. */ 
        if (vq->next_avail == first) { 
                flags = f; 
        } else { 
                vq->desc[vq->next_avail].flags = f;
                
        }
 
        vq->next_avail++; 
 
        if (vq->next_avail >= vq->size) { 
                vq->next_avail = 0; 
                vq->avail_wrap_count \^= 1; 
        } 
} 
vq->sgs[id] = sgs; 
write_memory_barrier(); 
vq->desc[first].flags = flags; 
 
memory_barrier(); 
 
if (vq->device_event.flags != RING_EVENT_FLAGS_DISABLE) { 
        notify_device(vq); 
}

Don’t mark the 1st descriptor available until all of them are ready
原因: The driver always makes the first descriptor in the list available after the rest of the list has been written out into the ring. This guarantees that the device will never observe a partial scatter/gather list in the ring.

Device writes used descriptor

The device only writes out a single used descriptor for the whole list. It then skips forward according to the number of descriptors in the list. The driver needs to keep track of the size of the list corresponding to each buffer ID, to be able to skip to where the next used descriptor is written by the device.

When the device has finished processing the buffer, it writes a used device descriptor including the Buffer ID into the Descriptor Ring (overwriting a driver descriptor previously made available), and sends a used event notification.

对于一个Descriptor chain，device仅仅往第一个desc中写入used_wrap_counter，而不是往Descriptor chain中的所有desc中写入used_wrap_counter。这样在hardware实现的packed virtqueue中，可以减少设备侧的TLP交互次数。

Example

接下来的案例以一个desc table大小为4的vring为例，展示packed virtqueue的流程与相关rule的原因。Flag中的A表示VIRTQ_DESC_F_AVAIL，U表示VIRTQ_DESC_F_USED，N表示VIRTQ_DESC_F_NEXT。

案例1

step1: 初始化

step2: driver生产Available Buffers

step3: device拉取Available Buffers

step4: device生产used Buffers

对于buffer id 0，device只更新了desc 0的flag(A|U)。

step5: driver消费used Buffers

driver知道buffer id 0的size为3，因此更新last_used_idx为3。VIRTQ_DESC_F_NEXT is reserved in used descriptors, and should be ignored by drivers.

step6: driver生产Available Buffers

step7: device拉取Available Buffers

基于avail_wrap_counter的值，device可以知道desc 1(flag为A|~U|N)为上一轮的avail desc，而非本轮的avail desc。

案例2

step1: 初始化

step2: driver生产Available Buffers

step3: device拉取Available Buffers

step4: device生产used Buffers

device只更新了desc 0的flag(A|U)，更新了desc 0的id为1。In a used descriptor, Element Address is unused. Element Length specifies the length of the buffer that has been initialized (written to) by the device. Element Length is reserved for used descriptors without the VIRTQ_DESC_F_WRITE flag, and is ignored by drivers.

step5: driver消费used Buffers

driver知道buffer id 1的size为2，因此更新last_used_idx为2。

源码解析

1
2
3
4
5
6
7
8
9
10
struct vring_packed_desc {
	/* Buffer Address. */
	__le64 addr;
	/* Buffer Length. */
	__le32 len;
	/* Buffer ID. */
	__le16 id;
	/* The flags depending on descriptor type. */
	__le16 flags;
};

https://elixir.bootlin.com/linux/v6.14/source/drivers/virtio/virtio_ring.c
https://elixir.bootlin.com/qemu/v8.0.0/source/hw/virtio/virtio.c

driver往Descriptor Ring生产Available Buffers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
struct vring_virtqueue_packed {
	/* Actual memory layout for this queue. */
	struct {
		unsigned int num;
		struct vring_packed_desc *desc;
		struct vring_packed_desc_event *driver;
		struct vring_packed_desc_event *device;
	} vring;

	/* Driver ring wrap counter. */
	bool avail_wrap_counter;

	/* Avail used flags. */
	u16 avail_used_flags;

	/* Index of the next avail descriptor. */
	u16 next_avail_idx;
        ...
}

struct vring_desc_state_packed {
	void *data;			/* Data for callback. */

	/* Indirect desc table and extra table, if any. These two will be
	 * allocated together. So we won't stress more to the memory allocator.
	 */
	struct vring_packed_desc *indir_desc;
	u16 num;			/* Descriptor list length. */
	u16 last;			/* The last desc state in a list. */
};

static inline int virtqueue_add_packed(struct virtqueue *_vq,
				       struct scatterlist *sgs[],
				       unsigned int total_sg,
				       unsigned int out_sgs,
				       unsigned int in_sgs,
				       void *data,
				       void *ctx,
				       bool premapped,
				       gfp_t gfp)
{
        ...
	head = vq->packed.next_avail_idx;
	avail_used_flags = vq->packed.avail_used_flags;

	WARN_ON_ONCE(total_sg > vq->packed.vring.num && !vq->indirect);

	desc = vq->packed.vring.desc;
	i = head;
	descs_used = total_sg;

        ...

	id = vq->free_head;
	BUG_ON(id == vq->packed.vring.num);

	curr = id;
	c = 0;
	for (n = 0; n < out_sgs + in_sgs; n++) {
		for (sg = sgs[n]; sg; sg = sg_next(sg)) {
			dma_addr_t addr;

			if (vring_map_one_sg(vq, sg, n < out_sgs ?
					     DMA_TO_DEVICE : DMA_FROM_DEVICE,
					     &addr, &len, premapped))
				goto unmap_release;

			flags = cpu_to_le16(vq->packed.avail_used_flags |
				    (++c == total_sg ? 0 : VRING_DESC_F_NEXT) |
				    (n < out_sgs ? 0 : VRING_DESC_F_WRITE));
			if (i == head)
				head_flags = flags;
			else
				desc[i].flags = flags;

			desc[i].addr = cpu_to_le64(addr);
			desc[i].len = cpu_to_le32(len);
			desc[i].id = cpu_to_le16(id);

			if (unlikely(vq->use_dma_api)) {
				vq->packed.desc_extra[curr].addr = premapped ?
					DMA_MAPPING_ERROR : addr;
				vq->packed.desc_extra[curr].len = len;
				vq->packed.desc_extra[curr].flags =
					le16_to_cpu(flags);
			}
			prev = curr;
			curr = vq->packed.desc_extra[curr].next;

			if ((unlikely(++i >= vq->packed.vring.num))) {
				i = 0;
				vq->packed.avail_used_flags ^=
					1 << VRING_PACKED_DESC_F_AVAIL |
					1 << VRING_PACKED_DESC_F_USED;
			}
		}
	}

	if (i <= head)
		vq->packed.avail_wrap_counter ^= 1;

	/* We're using some buffers from the free list. */
	vq->vq.num_free -= descs_used;

	/* Update free pointer */
	vq->packed.next_avail_idx = i;
	vq->free_head = curr;

	/* Store token. */
	vq->packed.desc_state[id].num = descs_used;
        ...
}

其中，vq->packed.avail_wrap_counter是driver侧维护的avail_wrap_counter，vq->packed.next_avail_idx是driver侧维护的avail_idx，vq->packed.desc_state[id].num是driver侧维护的size of the list corresponding to buffer id。

device从Descriptor Ring消费Available Buffers

1
2
3
4
5
6
7
8
9
10
11
12
static void *virtqueue_packed_pop(VirtQueue *vq, size_t sz)
{
    ...
    vq->last_avail_idx += elem->ndescs;
    vq->inuse += elem->ndescs;

    if (vq->last_avail_idx >= vq->vring.num) {
        vq->last_avail_idx -= vq->vring.num;
        vq->last_avail_wrap_counter ^= 1;
    }
    ...
}

其中，vq->last_avail_idx是device侧维护的last_avail_idx，vq->last_avail_wrap_counter是device侧维护的last_avail_idx时刻对应的avail_wrap_counter。

device往Descriptor Ring生产used Buffers

1
2
3
4
5
6
7
8
9
10
11
static void virtqueue_packed_flush(VirtQueue *vq, unsigned int count)
{
    ...
    vq->inuse -= ndescs;
    vq->used_idx += ndescs;
    if (vq->used_idx >= vq->vring.num) {
        vq->used_idx -= vq->vring.num;
        vq->used_wrap_counter ^= 1;
        ...
    }
}

其中，vq->used_idx是device侧维护的used_idx，vq->used_wrap_counter是device侧维护的used_wrap_counter。

driver从Descriptor Ring消费used Buffers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static void *virtqueue_get_buf_ctx_packed(struct virtqueue *_vq,
					  unsigned int *len,
					  void **ctx)
{
	struct vring_virtqueue *vq = to_vvq(_vq);
	u16 last_used, id, last_used_idx;
	bool used_wrap_counter;
	void *ret;
        ...

	/* Only get used elements after they have been exposed by host. */
	virtio_rmb(vq->weak_barriers);

	last_used_idx = READ_ONCE(vq->last_used_idx);
	used_wrap_counter = packed_used_wrap_counter(last_used_idx);
	last_used = packed_last_used(last_used_idx);
	id = le16_to_cpu(vq->packed.vring.desc[last_used].id);
	*len = le32_to_cpu(vq->packed.vring.desc[last_used].len);

        ...

	/* detach_buf_packed clears data, so grab it now. */
	ret = vq->packed.desc_state[id].data;
	detach_buf_packed(vq, id, ctx);

	last_used += vq->packed.desc_state[id].num;
	if (unlikely(last_used >= vq->packed.vring.num)) {
		last_used -= vq->packed.vring.num;
		used_wrap_counter ^= 1;
	}

	last_used = (last_used | (used_wrap_counter << VRING_PACKED_EVENT_F_WRAP_CTR));
	WRITE_ONCE(vq->last_used_idx, last_used);
	...
}

Packed virtqueues support up to 2^15 entries each.

其中，vq->last_used_idx的第14~第0 bit为driver侧维护的last_used_idx，vq->last_used_idx的第15 bit为driver侧维护的last_used_idx时刻对应的used_wrap_counter。

注释

  1. Packed virtqueues支持2^15 entries;
  2. 每个packed virtqueue 有三部分构成：
    • Descriptor Ring
    • Driver Event Suppression：后端（device）只读，用来控制后端向前端（driver）的通知（used notifications）
    • Device Event Suppression：前端（driver）只读，用来控制前端向后端（device）的通知（avail notifications）
  3. Write Flag，VIRTQ_DESC_F_WRITE
    • 对于avail desc这个flag用来标记其关联的buffer是只读的还是只写的；
    • 对于used desc这个flag用来表示去关联的buffer是否有被后端（device）写入数据；
  4. desc中的len
    • 对于avail desc，len表示desc关联的buffer中被写入的数据长度；
    • 对于uesd desc，当VIRTQ_DESC_F_WRITE被设置时，len表示后端（device）写入数据的长度，当VIRTQ_DESC_F_WRITE没有被设置时，len没有意义；
  5. Descriptor Chain
    VIRTQ_DESC_F_NEXT在used desc中是没有意义的

参考资料:

  1. 从dpdk1811看virtio1.1 的实现—packed ring
  2. Virtual I/O Device (VIRTIO) Version 1.1
  3. What’s new in Virtio 1.1? by Jens Freimann
  4. What’s New in Virtio 1.1 - Jason Wang
  5. Packed virtqueue: How to reduce overhead with virtio
  6. virtio系列-packed virtqueue
  7. add packed ring layout support
  8. [PATCH v10 00/13] packed ring layout spec
  9. Virtio I/O 虚拟化（二）：Packed Virtqueue
  10. 异步模式下的 Vhost Packed Ring 设计介绍
  11. [virtio-dev] [PATCH net-next v3 00/13] virtio: support packed ring