From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx1.redhat.com (mx1.redhat.com [209.132.183.28]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id AA7592095B9F5 for ; Wed, 23 Aug 2017 18:19:55 -0700 (PDT) Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 86C7D356C9; Thu, 24 Aug 2017 01:22:29 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 86C7D356C9 Authentication-Results: ext-mx06.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx06.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=lersek@redhat.com Received: from lacos-laptop-7.usersys.redhat.com (ovpn-116-43.phx2.redhat.com [10.3.116.43]) by smtp.corp.redhat.com (Postfix) with ESMTP id 1EDA069A59; Thu, 24 Aug 2017 01:22:27 +0000 (UTC) To: Brijesh Singh , edk2-devel@lists.01.org Cc: Jordan Justen , Tom Lendacky , Ard Biesheuvel References: <1503490967-5559-1-git-send-email-brijesh.singh@amd.com> From: Laszlo Ersek Message-ID: <2dc1f802-c566-9bc0-1dce-561f49194fbc@redhat.com> Date: Thu, 24 Aug 2017 03:22:27 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.30]); Thu, 24 Aug 2017 01:22:29 +0000 (UTC) Subject: Re: [PATCH v3 00/21] OvmfPkg/Virtio: introduce IOMMU-like member functions X-BeenThere: edk2-devel@lists.01.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: EDK II Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Aug 2017 01:19:55 -0000 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit 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