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 D8F7421D2E62B for ; Thu, 24 Aug 2017 03:04:58 -0700 (PDT) Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 06C594ACA7; Thu, 24 Aug 2017 10:07:33 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 06C594ACA7 Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=lersek@redhat.com Received: from lacos-laptop-7.usersys.redhat.com (ovpn-116-82.phx2.redhat.com [10.3.116.82]) by smtp.corp.redhat.com (Postfix) with ESMTP id C07CB17AAC; Thu, 24 Aug 2017 10:07:31 +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> <2dc1f802-c566-9bc0-1dce-561f49194fbc@redhat.com> <4500ec50-79f8-40d3-4057-55a4a9edd8e1@amd.com> From: Laszlo Ersek Message-ID: Date: Thu, 24 Aug 2017 12:07:30 +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: <4500ec50-79f8-40d3-4057-55a4a9edd8e1@amd.com> X-Scanned-By: MIMEDefang 2.79 on 10.5.11.13 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.38]); Thu, 24 Aug 2017 10:07:33 +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 10:04:59 -0000 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit 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