From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753444AbdEPNsk (ORCPT ); Tue, 16 May 2017 09:48:40 -0400 Received: from xes-mad.com ([216.165.139.220]:51197 "EHLO mail.xes-mad.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752531AbdEPNsi (ORCPT ); Tue, 16 May 2017 09:48:38 -0400 X-Greylist: delayed 376 seconds by postgrey-1.27 at vger.kernel.org; Tue, 16 May 2017 09:48:38 EDT Date: Tue, 16 May 2017 08:42:21 -0500 (CDT) From: Aaron Sierra To: Robin Murphy Cc: Joerg Roedel , iommu , linux-kernel , Nate Watterson Message-ID: <1044909514.237785.1494942141432.JavaMail.zimbra@xes-inc.com> In-Reply-To: <2f161f6406fd33ea979f6b128f36bb8ac9044d06.1494933782.git.robin.murphy@arm.com> References: <2f161f6406fd33ea979f6b128f36bb8ac9044d06.1494933782.git.robin.murphy@arm.com> Subject: Re: [PATCH] iommu/iova: Sort out rbtree limit_pfn handling MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Originating-IP: [10.52.0.127] X-Mailer: Zimbra 8.7.5_GA_1764 (ZimbraWebClient - FF53 (Linux)/8.7.5_GA_1764) Thread-Topic: iommu/iova: Sort out rbtree limit_pfn handling Thread-Index: oO0wETb8iq5YlE6fh7vsPEiJYo7VoA== Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org ----- Original Message ----- > From: "Robin Murphy" > Sent: Tuesday, May 16, 2017 6:26:48 AM > When walking the rbtree, the fact that iovad->start_pfn and limit_pfn > are both inclusive limits creates an ambiguity once limit_pfn reaches > the bottom of the address space and they overlap. Commit 5016bdb796b3 > ("iommu/iova: Fix underflow bug in __alloc_and_insert_iova_range") fixed > the worst side-effect of this, that of underflow wraparound leading to > bogus allocations, but the remaining fallout is that any attempt to > allocate start_pfn itself erroneously fails. > > The cleanest way to resolve the ambiguity is to simply make limit_pfn an > exclusive limit when inside the guts of the rbtree. Since we're working > with PFNs, representing one past the top of the address space is always > possible without fear of overflow, and elsewhere it just makes life a > little more straightforward. > > Reported-by: Aaron Sierra > Signed-off-by: Robin Murphy > --- > > I've now run this through some more targeted testing, and I'm > confident that it works as intended - Aaron, can you confirm if > this satisfies your tests as well? Robin, Thanks for giving this issue some consideration. I can confirm that your patch passes all of the test cases where I'd previously observed allocation failures. FWIW, my testing consists of defining a fixed limit_pfn (0xfffff) and iterating over domains with start_pfn values of 0, then all powers-of-two up to half of limit_pfn (0x80000). For each domain, I set a fixed allocation unit size, calculate how many allocations I expect to succeed, alloc and save iova structs until allocation fails, then compare expected to actual. I do this for allocation unit sizes of 1, 2, 4, 8, 50% of alloc-able range, and 100% of alloc-able range. -Aaron S.