Re: [PATCH v3 00/21] OvmfPkg/Virtio: introduce IOMMU-like member functions

[Laszlo Ersek <lersek@redhat.com>]

On 08/24/17 04:06, Brijesh Singh wrote:
> 
> 
> On 8/23/17 8:22 PM, Laszlo Ersek wrote:Okay, I will look into it -
> thanks for the tip. I wanted to actually use
>>> the Simple array (because we know the maximum number of buffer we can
>>> queue) but was  not sure about your preferences hence I went to with
>>> list. If you are okay then I can use array's too.
>> My concern isn't about memory consumption (if our queue is full (64
>> elements, IIRC), we just reject the transmit request and let the caller
>> deal with the error).
>>
>> Instead, I'd like to avoid an O(n) lookup time (where n is the number of
>> pending requests), for whatever lookup is necessary now (I haven't
>> checked the specifics yet). BaseOrderedCollectionRedBlackTreeLib would
>> give you O(log n) lookup time.
>>
>> Without having looked at the details, I think an array would have O(n)
>> lookup time as well (linear search, right?).
>>
>> (Let's not try to do O(1) with a hash function -- that's quite out of
>> scope for now, and with a hash table, one has to think about collisions
>> too, etc. When I contributed BaseOrderedCollectionRedBlackTreeLib, I
>> wanted it to become *the* go-to associative data structure for edk2 --
>> at least in such DXE and UEFI driver contexts where frequent pool
>> allocations and releases are not a problem. Plus, RB trees double as
>> fast priority queues, can be used for one-off sorting, have worst-case
>> (not just on-average) O(log n) time guarantees... I think they're
>> versatile.)
> 
> To my understanding the network packet enqueued in the transmit ring
> will be completed in same order,

The current code does not make this assumption -- please see the very
last paragraph in "OvmfPkg/VirtioNetDxe/TechNotes.txt" --, and it would
be good to keep it that way.

> hence I was thinking about the queue
> data structure and was not concern about the search time. I was mostly
> concerned about the memory consumption but if my understanding is wrong
> then I agree that we need to pick right data structure. Since the
> RedBlack tree is already implemented hence I have no issue using it. thanks

OK, thanks!
Laszlo