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

[Laszlo Ersek <lersek@redhat.com>]

On 08/24/17 02:54, Brijesh Singh wrote:
> On 8/23/17 7:26 PM, Laszlo Ersek wrote:
>> On 08/23/17 14:22, Brijesh Singh wrote:

>>>   OvmfPkg/VirtioBlkDxe: map host address to device address
>>>   OvmfPkg/VirtioScsiDxe: map host address to device address

>> (4) I've looked at these patches briefly. They are possibly fine now,
>> but they've grown way too big. I struggled with the verification of the
>> VirtioRngDxe driver patch, and each of these two is more than twice as big.

> Great thanks, I agree the series is getting bigger. After v1 feedbacks,
> I was almost tempted to say that lets work to enable the base first then
> will do one driver at a time. I was repeating the same mistake in each
> patch and that was causing trouble to you and also I had to rework the
> all drivers.

Unfortunately (for both of us! :) ), this churn is unavoidable in the
first few versions of a large set -- the foundation is not dictated by
some "divine design", it is dictated only by what the higher level
drivers need. And we only find out what the higher level drivers need if
you at least prototype the patches for them, and I at least skim-review
those patches.

It's regrettable that it requires so much wasted work, but I don't know
how to do it better, save for knowing the future. :)

I trust at this point the base has stabilized enough, and if we need
further changes, we can solve that with small incremental patches.

>> (6) This is obviously the most complex driver. I've only snuck a peek. I
>> have one comment at this point: *if* we have to do random lookups, then
>> lists aren't optimal.
>>
>> Please consider using the following library class:
>>
>>   MdePkg/Include/Library/OrderedCollectionLib.h
>>
>> It is already resolved in the OVMF DSC files to the following instance:
>>
>>   MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/
>>
>> Examples for use:
>> - various modules in OvmfPkg,
>> - AppPkg/Applications/OrderedCollectionTest
> 
> 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.)

Cheers
Laszlo