0%

一种硬件队列的驱动设计

首先描述这个硬件的队列模型:

他有N个发送队列(sq),N个完成队列(cq), 这N个sq和cq一一对应组成N个队列对(qp)。这
N个qp对应一个事件队列(eq)。

用户可以依次在sq里填入请求,然后发通知(doorbell)给硬件,要求硬件执行这个请求。
可以执行请求的部件我们把他独立开来(core)。core执行完请求后会依次在cq里填入请求
完成(描述符)。为了异步的通知给用户,当cq里有请求完成描述符的时候,并且没有屏蔽
cq写eq的通道的时候,cq会依次在eq里填入一个事件完成描述符(eqe)。对于eq,在eq里有事件
完成描述符,并且没有屏蔽中断的时候,向CPU报一个中断。

软件可以操作doorbell更新sq尾指针,更新cq头指针,更新eq头指针。其他硬件指针硬件
自己会更新(比如,core在取走一个sq请求的时候更新sq头指针,cq、eq在被写入的时候,
硬件更新cq tail和eq tail)。

cq在满足条件向eq填一个eqe的同时自动屏蔽cq写eq的通道。软件可以再下发一个特定的
doorbell打开这个通道。

eq满足条件上报中断的同时自动屏蔽中断上报。软件下发doorbell更新eq head时,除了
更新硬件eq head,还同时打开了中断屏蔽。

整体的硬件框图类似是这样的:

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
              cq/sq/eq doorbell
| | | ^ irq
+---------+-------+--------------------+-------+----------------------+
| | | | | |
| | v | | |
| +---+-+-+---+---+---- | | |
| |sqe|s|e|sqe|sqe| | | |
| +---+-+-+---+---+---- | | |
| +---+-v-+---+---+-\-- | | |
| |cqe|cqe|cqe|cqe| \ \ | | |
| +---+---+---+---+---\ \ | | |
| ^ ^ ^ \ \ | | |
| | | \ \ \ | | |
| head tail \ \ \ | | |
| \ \ v v | |
| \ \ +---+---+---+---+----- |
| N个 \ \ |eqe|eqe|eqe|eqe|... |
| \ X +---+---+---+---+----- |
| \ / \ ^ ^ |
| +---+---+---+---+---- \/ \ | | |
| |sqe|sqe|sqe|sqe| /\ \ head tail |
| +---+---+---+---+---- / \ \ |
| +---+---+---+---+---- / \ \ |
| |cqe|cqe|cqe|cqe| / \ \ |
| +---+---+---+---+---- \ \ |
| \ v |
| \+--------+ |
| | | |
| | core | |
| | | |
| +--------+ |
| cq/sq depth = M eq depth = K |
+---------------------------------------------------------------------+

对于sq,软件需要维护软件sq_head, sq_tail。保证发到sq的请求不会导致sq溢出。
对于cq,其input来自core, output来自中断处理程序中更新cq head。
对于eq,其input来自cq,output来自中断处理程序中更新eq head。

软件设计的重点在于,在保证cq,eq不发生溢出的情况下,做到高性能。我们先找到保证
cq、eq不发生溢出的条件。然后,提高中断的汇聚程度提高性能(同时不破坏之前的约束
条件)。

cq不溢出的条件是(考虑中断很久才到,这时候sq, cq已被填满, 注意因为上面我们已经
限制sq不溢出,所以这里即使没有中断更新cq head,cq也不会溢出)。中断中我们通过
eqe中的索引找到对应的cq进行处理,必须先跟新cq head,才能更新软件的sq head。否则,
如果先更新sq head,下发的新sq请求可能通过core产生cqe使得cq溢出。
(注意这里没有考虑cqe汇聚处理)

eq不溢出的条件是,考虑所有cq并发向eq写eqe,中断到来在写满eq时刻之后的情况,得出
eq深度至少要等于并发cq数N。假设eq已被写满,现在在中断处理函数中遍历各个cq处理,
并且处理完后打开cq写eq通道,并且N个cq上都有排队cqe(意味着会写N个新eqe给eq)。如果
eq的队列深度不增加(依然是N),那么保证eq不溢出的条件是,irq中断中处理一个eq head
(相当于在eq里留出一个空位),才能在处理一个cq的时候放开放cq写eq的通路(放开通路就
意味着可能有cq向eq写入一个eqe)。当然也可以处理n个eqe,放开<=n个cq到eq的通路。

上面已经明确不溢出的条件,那么,下来就是看优化了。按照上面对eq的处理,需要在中断
中对每个eqe做eq head的更新,注意上面的硬件描述里提到,每次更新eq head都会打开
中断屏蔽,这样每个eq都会上报一个中断,性能会差。我们考虑把多个完成的eqe做一下汇聚,
然后更新eq head。注意, 在实际实现时,我们的处理大概是这样的:

1
2
3
4
5
while (轮询已完成n个eqe) {  /* 这里最大汇聚为n */
处理eqe对应的cqe;
打开cq到eq的通道;
}
更新eq head到原来eq_head + n的位置;

可以看到实际处理的时候为了把处理cq和打开cq到eq的通道放在一起,会在eq head处理
之前打开cq到eq的通道,这样和上面的eq不溢出的条件是冲突的。这样做eq会溢出。
注意到上面的分析是假设eq深度等于并发cq个数N。要使得eq不溢出,我们这里还可以增加
eq的深度来解决,可以看到我们需要至少把eq的深度加到N+n。

下面分析cqe汇聚处理的问题。一个eqe至少都对应着一个cqe,在cq写eq后,对应cq写eq的
通道被屏蔽,后续core处理完的请求将在cq上排队。在中断处理程序中,通过eq找到对应的
cq,然后处理cqe,如果只处理一个cqe后就打开cq到eq的通道,就会上报eq,eq可能会上报
中断(这个要看eq上的汇聚处理)。所以在处理cq的时候,我们可汇聚k个cq一起处理,然后
再打开cq到eq的通道。这个是一个和上面独立的逻辑。