From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from NAM01-BY2-obe.outbound.protection.outlook.com (mail-by2nam01on0088.outbound.protection.outlook.com [104.47.34.88]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ml01.01.org (Postfix) with ESMTPS id BC18E21E47D57 for ; Wed, 23 Aug 2017 19:04:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amdcloud.onmicrosoft.com; s=selector1-amd-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=zMvjxNyDI0aMhtPsdZBOKhP7lhe4YFe0oFHTZZcOcLA=; b=FkYFZDBCJ7ISEUrcPTgWCwjr+BUdm9q3uG/iOlVb/J6ZDTWkWCTJZsM+aEEYNBuwr5AgU25lYmcZYPQ01/FyRRsXl4w2PHLNfSXGnE3/IRIojA10A2bXZ+Wig/hu58ZWWeYFEcGkBVtQIkqsAu+ugYdNXAUBoOXSVWFO2ZwO4Q0= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=brijesh.singh@amd.com; Received: from Brijeshs-MacBook-Pro.local (70.112.153.56) by BY2PR12MB0146.namprd12.prod.outlook.com (10.162.82.19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1362.18; Thu, 24 Aug 2017 02:07:06 +0000 Cc: brijesh.singh@amd.com, Jordan Justen , Tom Lendacky , Ard Biesheuvel To: Laszlo Ersek , edk2-devel@lists.01.org References: <1503490967-5559-1-git-send-email-brijesh.singh@amd.com> <2dc1f802-c566-9bc0-1dce-561f49194fbc@redhat.com> From: Brijesh Singh Message-ID: <4500ec50-79f8-40d3-4057-55a4a9edd8e1@amd.com> Date: Wed, 23 Aug 2017 21:06:55 -0500 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:52.0) Gecko/20100101 Thunderbird/52.2.1 MIME-Version: 1.0 In-Reply-To: <2dc1f802-c566-9bc0-1dce-561f49194fbc@redhat.com> X-Originating-IP: [70.112.153.56] X-ClientProxiedBy: DM5PR20CA0001.namprd20.prod.outlook.com (10.173.136.139) To BY2PR12MB0146.namprd12.prod.outlook.com (10.162.82.19) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 1dce4480-eb3a-489c-cc51-08d4ea94d250 X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0; RULEID:(300000500095)(300135000095)(300000501095)(300135300095)(22001)(300000502095)(300135100095)(2017030254152)(48565401081)(300000503095)(300135400095)(201703131423075)(201703031133081)(201702281549075)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095); SRVR:BY2PR12MB0146; X-Microsoft-Exchange-Diagnostics: 1; BY2PR12MB0146; 3:ZI62+mUGkcpZYD1Mw9NaPb7ostWRTHZWalzq6iRAq0znyoIH8YaFhuOjHdyTUds83Z7CgzvP7AwyXgS6lE+JRfbnMV3LkGzVLQ2GXqdpipZ1EGAcqJqZ29CSfHbQ+Pm+QUwOTXibH8+1CHmdPFcE+LTfKBSL4vEuh8+sMCzAwlukx0RIX5z+NroL5HQBDQTuErknH935S93/dSj5WmjuELlPY3WosK6XpFht1qqo1suz8DaS4qNbRdLQNwIP1ENp; 25:JqbW1zVfGGUbbLlc6JgSWZjhAfUx494ykrKWU5JIlXc/UvYZzbPwlgbzXitKvemmY7cpsYyOYUYVfcN2ZViL72oFfunSAfbAeHuGd1iElFdm0Pih50N5pYxtZVuYFtSovtyXUETefgu02A+yyTFuKJ4ix3/DBmsWaUcOlueofEJLKElLqwrHcepDSgTHYv6Hs1kZou9QmXxZ/uFs4zhIBDhJvBmpdX9SIr91iWSNUAPy0M1qCdaJylVMZMqwiQjhrhgKjgPHn9kKshiCuv5ERpzrGGHHYbeEyKdeXsdiz5Gfsmsk7p5mXwWG6+0E7D1MGDhXDgGRZFCNzC45M74PfQ==; 31:iB1FutsnzaHybx+XkUYHx9LgvPNuGPhA14HCvVxCXAZfUBh7wgKOeiqtPIciuVn0vPcVH2Fov1ep3FsBOlBUN1abpc38iN9tLN0oZyZ8qNbJcfAYnn1urOhvLO6W6RW7EdiTevO42+xaZLnto7w1RcZFYlEzI7eBgfFJXB4SAlI56KKwilX9WbwirtJD9T8KXvHW5cJ/yDbgVHoK/kr7sH1iKDYntoTfoZm0do2SNOQ= X-MS-TrafficTypeDiagnostic: BY2PR12MB0146: X-Microsoft-Exchange-Diagnostics: 1; BY2PR12MB0146; 20:4xdyTCwKxLgQLCwW1+tKp8lBPAHQd+TnhWOFvqHLJN2Rivz7jbV3/Jz9pULAwqoKvdMm4mnf8y43ASild3ScjyRvmiTwJU4L71Q5CQB4tfTpbNR4wb1aF37NZDAv0ZhWRmbtDGOSdW6uR4tZYoNIaRS49bsg4R6qiXWFJ3hl5fzcCViMvTXxybpbuZoDDPBxd9RavnqImJk1qscb0HzaHk7yLSdtKH0cMVeJ0b4GlzhLOqzn9uBIoJ17XzxiyEtqpVwRPs4M73MWkG0NddgDgU22haPfGpixT62YGuUup7SUPbGNGjqnjftUzv6v+0Ng/f+BST0SSMLFXmq0e+euz7/Uhu3GgKu3kSAuxpOM2eLxhJmK6mFwP4TkBfCYQQNs++EuaD6UcYy/z43kzhL3jgIn+90asVPQZtaAX6MX36rcfm+cTbx+99wsSCO0aNHVRBmBhSdilL04pTtoxVlfKIsneKsmHxxo5pT6VKYsNK8QJGbx9XxvHpyawkJJZ11V; 4:PH0KunaP4X4EaymFzZFuc0UchcfxM45o7zsnWOJacYTijHM3nEZXTciorUuRXbzrpLm0hX2uh7eAymPqpacH4G5HxeQIzujG9a5eLulspmURJiZLe+RxwBPqGxN52piwcrKWMd5wqrPZWEYyRkwu8IXRJETf/RLKafAolc9eLZ/tv56+eYPlySuJ3V1upYO1+a7fbdxhTqxhxOyE52ZCoUmOxbOJKuwnvMtefg8r/0gRzpjqa6gYsFjp2iGyq0zYsfaY3L2DpLSYv2ei3bvb4ztHzbbTR1TwoHi6Nlf+fmc= X-Exchange-Antispam-Report-Test: UriScan:(131327999870524); X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046)(100000703101)(100105400095)(93006095)(93001095)(6055026)(6041248)(20161123564025)(20161123560025)(20161123558100)(20161123562025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123555025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:BY2PR12MB0146; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:BY2PR12MB0146; X-Forefront-PRVS: 04097B7F7F X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(4630300001)(7370300001)(6009001)(39860400002)(199003)(377454003)(189002)(24454002)(51914003)(6246003)(97736004)(65826007)(230700001)(8676002)(6512007)(93886005)(54906002)(64126003)(66066001)(65956001)(65806001)(7350300001)(25786009)(189998001)(68736007)(23676002)(2950100002)(36756003)(53936002)(4001350100001)(7736002)(478600001)(47776003)(5660300001)(81156014)(110136004)(83506001)(305945005)(81166006)(31686004)(2906002)(31696002)(101416001)(54356999)(3846002)(229853002)(76176999)(50986999)(105586002)(6666003)(6486002)(86362001)(33646002)(42186005)(6506006)(50466002)(6116002)(106356001)(4326008); DIR:OUT; SFP:1101; SCL:1; SRVR:BY2PR12MB0146; H:Brijeshs-MacBook-Pro.local; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en; Received-SPF: None (protection.outlook.com: amd.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCWTJQUjEyTUIwMTQ2OzIzOmhSaG85SkYyaW9FazQ5OGo0OWRxNUt5dkQ4?= =?utf-8?B?R01YYTdnUk9tckkvYnRUbVZjTTlSNnBnRVRyMWNNRHA1ZElRKzhrYzRPbTh4?= =?utf-8?B?YVZiSEtkQWxLcVdFVnB1MXlVSW9hOXNrM090ZlBka1pWRTBDNTFyNDZYYzNv?= =?utf-8?B?TWRLVnRyQjJBOThMR25BS3BYUUNNVVdrOFZWUGF5S0FrMHVFL2JxckdETmpw?= =?utf-8?B?a1NLRWVaRmZxYjdqYUJJaXg2d2JIQ3lRTU9IY1dveGQwNXluSCtsVHdVOVd2?= =?utf-8?B?T3ZCdG9SdWIrYVZLSkhMUWJyeFlNMitYQlp6QldvaXNrdTF6blZsQXNteWs4?= =?utf-8?B?Q2JRcUpDZmF4eldoRG1WTG16YURYdnF0SmtYY0o4U1ovZ3B5c1lNaHNxUnVs?= =?utf-8?B?OUR3clZWR2VjbEJmMkR3NXZ3TGlrOGpSU1RqWjhreVpMang1d1Jscm1XVE1F?= =?utf-8?B?eXVBN1h1UHh2amxxblQvUzZGcFg0a1ozalpRMWF1T3pMdW5YZnNCNURrZ09C?= =?utf-8?B?T2pvUWpHTWY3WjlGMTFzN3RIckVDQlNlWGJEeWkvcW5hK1FySTJiVVJHV1Vu?= =?utf-8?B?Q3JDbm5MRTZnTTAxUzdrZkxXNzk1ZEFKSXppaUxyVThSVmc3TGVaazMvWkQr?= =?utf-8?B?WmkvbHJYWEl3aGpiNWJ1bWgxekZtRGlaaU9WWFVMQVF1OTNicWRHem93ek1L?= =?utf-8?B?OTVMUCtyem11VDJSVERVeElURkQ2Sm9QN200cWVtdEZ3ajFoSDFSZDJYeXN3?= =?utf-8?B?T3pTUWNUMW11Q1lTemZJSm1CWnhjN1ovNEx5ZFBqZFBsbmF5cGp6UERwektQ?= =?utf-8?B?dHliaGVob3FVR3hkWXJhc3dQdTM4TTh3dXpSVGZIYkEwSXA3bVRWL25lMllC?= =?utf-8?B?TVgxSGJyWXl0QTBrN2VrbXZ4a01BQmFEa1Nwa2lINkMvWXdJdmR4cEh0RFJL?= =?utf-8?B?WGNGQUlpNndrYWZJUEUzTlo2QmJHWi9YTnF3K2VyVkdwN29sNmR5VjBCOFhx?= =?utf-8?B?WWNtZmkydFdITTRZZ0YvdzkraVFUTStQSExlZkc1Nk9ubkJuQlRiUmJGZXFN?= =?utf-8?B?Vit4WGJrQzRWT09qODZ1djUvVXVmaHp3K0ZSNFpld0VuN25HS1BrY3FZbUZl?= =?utf-8?B?dXNkMWNCWHV3V0VXbTJQNU9GSmRFZytOQlNEOGdJdmtMdXF5RWttVFd2WGdx?= =?utf-8?B?MS93SEpGM0dzRWhEWk1tZlFya1FESmwrb1JjVEU2RjQxd2MvbVpMUk5qVmtX?= =?utf-8?B?SlpSdURPc3YzZURSNm9leFdtTW9Fc3BmUEl0VlVYTC9TNTVndWFKbm9pL1Zo?= =?utf-8?B?aW95anAvK0MrZFpwbFlrTXlFTE42QWFDNUdGTlRpRkQ0QXZiZ2FvckxnbHR2?= =?utf-8?B?cEVwcFZaaHNYVGI4WkdEblNpTi94VklVbU5CQkhiYjVXWHdaZ1ZMNmc2ajF1?= =?utf-8?B?eU13cVFGYkY4UWx2NXl3aU4xVWRVWVVFODZmYVdRdGdTcFlvQ1VpeTVwR1hQ?= =?utf-8?B?bU9PT2x1VncyQklaZEY3ak5vMHU3elRBS0xoR0I3cjVFcWdMZGlhUW9CQldZ?= =?utf-8?B?YndDd2IvRU14cExuRjh3Sy8wcGx3NnlScEVGNmVmemYybXpSd05nOUNWd1dw?= =?utf-8?B?SUhUdFZzSS9VclQ5ZHE4blMyZk9WWUJqRS9SQlVBbkRxeGIrNklqYmZBMHQ4?= =?utf-8?B?bUYrMHdKeGM5YTRRRFQydy9ETm1jb255UWRvTm9UYzdDWTZkeTNRVXFkck5w?= =?utf-8?B?OEVqQXR1YUhCSlFkTXMxdlptdHhrb1RtL1J0bStCQnZVV2U2d3JGZk9Ca05i?= =?utf-8?B?alkvN0FTUUZNOGUrNHEveFZWd1oxbjllSG96TFZMTXl6ak13YWVqckpwNXJn?= =?utf-8?B?MitTNTVpSUNBWFpHOFJOY3R1ODJ0bW15Y204UTNCbGdWOHNxZmlUVjlqYWVy?= =?utf-8?B?MVVUZTNyelJnPT0=?= X-Microsoft-Exchange-Diagnostics: 1; BY2PR12MB0146; 6:cNViCdZjCVDnHL/vNrSpHu6Oiqy+KtPV8jZG0PcjByofJyD/vj8JL/SGmFdwQ+i3blNALHmX+GXXUC7WHpJeQ2NX54RPplKtEYJyVy6KYiCASzHQGIG1schc4/RORelC58x3eF7n90mS6EpxuUN7wNjyoyMLc8SymdXEVr6+se4EtSp8SeUFDYnzvu3uLmrPrYbPC+BoO3Y2yd/3G7meGwCPC2+W/QHVZH4p+oSqAFC8ZeB7ZWDXDiYubbNKr/Mvv/Mpipc7B0EXmpHawnxf8dwzIM1EHJl2GZIAByGFfvtyIz/HYXMK+QfTaQVMB+EBnLSqH8CO7rv4xkSMGzF2KQ==; 5:7OcORmK7Ko9LSjtQexhZvZSXorToDNDRV7P1EHQO46jkNx4CJL/Ctz8CfS28LF5YPgswQemwMu5co0/iIykraOgLFBg4X1Z86X0k3Sh4QzmZP8VFwAqGAKU+OCO8VyS7RRmsm6gLPFQUJMLzYJZKcQ==; 24:gISdDQQq6lCv/LwjcqGxQBNppSU92WVGhwiDIcR+kei+hXAqgFejCPq1X2M6oPmKlXAuwx1ueOxezLOVZ8OmYLtkZsiWcalQjGT71TK1/lY=; 7:TrX9mZJGbDXpEwCbLJx7YUmVllSER1eiQefTuhslULQbI8tsUDwBStmDKJ15VyDKtT2GXBhETac3W1I5X1k63bWjub0YALBDfsvzWpxxhON6Lz9Fh1kA6yR3igi+1D6Qv723vdDafTh6DdV+ZMXqCOSMN1tIIskboDO/sqZIZ1zsozsijhwJIMSJj1uCprn4uckLUKprkhEeNdiDS1QwgTXxaqmItKtAPFTSGZNs/es= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-Microsoft-Exchange-Diagnostics: 1; BY2PR12MB0146; 20:XXS+4jI8kqgewRszaNyApox+cjR0EOcCE1z/k/sQdF8yqtMUXN8GFZJYl0QUrp6XbxMZ+u6lWJ5PuzL1XJMutWjK40kMX2jiWelKGKPlbq10x0TwQpC7GwRyu8gzBcggw0mlvfvnHAgbHgL8+1T06W9WsUGmKoMvUMpiTXTemU85CnoNS6rkWr89Hl4GQKxiV6Ckjlts/3HoDfSRXmY8FaW6Xz8d+so6CB/EP4aPcUHNqb1u02+7mD0q0S2Nyw+G X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 24 Aug 2017 02:07:06.3621 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY2PR12MB0146 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 02:04:35 -0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Content-Language: en-US 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, 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 -Brijesh