From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752217AbdI0Quq (ORCPT ); Wed, 27 Sep 2017 12:50:46 -0400 Received: from mail-he1eur01on0054.outbound.protection.outlook.com ([104.47.0.54]:5120 "EHLO EUR01-HE1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1750786AbdI0Quo (ORCPT ); Wed, 27 Sep 2017 12:50:44 -0400 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Robin.Murphy@arm.com; Date: Wed, 27 Sep 2017 17:50:31 +0100 From: Robin Murphy To: Joerg Roedel Cc: iommu@lists.linux-foundation.org, linux-kernel@vger.kernel.org, nd@arm.com Subject: Re: [PATCH 3/3] iommu/iova: Try harder to allocate from rcache magazine Message-ID: <20170927175031.7fef6fdd@m750.lan> In-Reply-To: <20170927140051.GO8398@8bytes.org> References: <8127fabc219811d8169189e9d7177d42bc74bcbf.1505827369.git.robin.murphy@arm.com> <20170927140051.GO8398@8bytes.org> X-Mailer: Claws Mail 3.15.1-dirty (GTK+ 2.24.31; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Originating-IP: [91.125.195.39] X-ClientProxiedBy: HE1PR0701CA0062.eurprd07.prod.outlook.com (2603:10a6:3:9e::30) To VI1PR0802MB2463.eurprd08.prod.outlook.com (2603:10a6:800:bb::18) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 7d51ac7b-8288-4eca-02a0-08d505c7e351 X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001)(2017030254152)(48565401081)(2017052603199)(201703131423075)(201703031133081)(201702281549075);SRVR:VI1PR0802MB2463; X-Microsoft-Exchange-Diagnostics: 1;VI1PR0802MB2463;3:g260Fmt692Duv97Yd7NvfNyQQat4kas93oyy0FxIIaukTbnflRuaP3RKK8kAA3sh9briZM5J04+1wfY5ZOM6LP8eumwv4BAqLV+mi+0FfDyMZtra3Vpk17R8Mm1rqio/0WHtFHcJFjF2jLYrfyhSV8F2QVXqrTZ8YkznFAKWT7tY0ndOlX5ziXqzJbE/IivHBdv4qgjoelhWwB08zU8HKutzM23IzFs3COONhjlzr4PGVtH5xBJx65U+da7smkwM;25:Z6zxo0jFa6CbWyqdNVdCq39WrvTYY76FB6idizBaxq4XEsZUyiN11NP7jX/8tN5L04lwEIuMcz+prODIm2acy+l31k095BTgbyVvF7U7uXjqH+o6DzbWZtS0vs0OO80qd9zrgAahZ1cImrb9iBOCI5+2sFBsb4r3lqLsjj/jdpaNDHSWqka/mU4f0VBTMEoFj0+LdQwHX6AfgbAAjVL+okHGHJcw3WASPHAgAudVe6ABdN8G8NHtN6KHAzYt17Ppy1tpt7MZaOIOvNPjUNUdzB/2ysTQ+m/aQ456K8ajxqexNlkfkEkpaNLL6OT/KEHKRSeB1W3IlwvnqJOV3zEMbA==;31:P7puav8SaIEz0g3VHajE1EOk+Xsc4O8yVZCqMriHzXPNGb79aPKleu1nCl6tKGWvMptatYjwb2+BX01I9cKZrjDWM/2bvLYj4YJMQAU8SUOWBGgwnFEftjGiMH52XLvVgdU6Bdz3w2wpBkPSZvRNkQe9QZTxSVXV/m7egjwlRV4rJ9ngcbA5JrT3pH5Zze26fJUpGuLCjfFYhQsxrNrXoFJwwGlb3iRMvTSN/YCiHsE= X-MS-TrafficTypeDiagnostic: VI1PR0802MB2463: NoDisclaimer: True X-Microsoft-Exchange-Diagnostics: 1;VI1PR0802MB2463;20:Jl1rA9w8egKBoqqUVNDRVEUEL4yQ3IpDWClOiWzXAFS5Fejrw8Vp6lN7qhiYsWpFm3frrafoN+DCT1+nNyVl4rmKjZsiCI1Ts57p2ch0IQmNSccgTyf2iDq2fOXvvTAGXxfLziMWApngZeaby0a0CKfj+rzV+D59QK9q55ZhBdk=;4:HpXf6A9C18chztvy2y6QFeSe2gnXAwFSmngml2cdlek+UZi2Dxo2jS76PmKtrZhl2yJhRtz/wLHhSUxWKBrc/OU09kcaQVJrmOtiswe1DpAAjJyEtl6MNP+eNl+BxrxYwwoUAwgcpFnlUQYLSfRq+eM8L/eSe7p/dZTUmkcJWWkgvIDVJ2A4wzhV/b/2u8spvv549y2iN1l74TmYMNz+rMVtkE4Mn2x4LOh0d/CPNWW0Ftp0YHfd0ngItsWNxf6ipoyzjWBUrX2cfPbGuOT5JvBzvJmvzELkTmV2xshzBaa1LrN27amCZ8wvIi9KApTMufI4Ul8xmiGBdyW2m/Hjwg== X-Exchange-Antispam-Report-Test: UriScan:(180628864354917)(131327999870524); X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(2401047)(5005006)(8121501046)(93006095)(93001095)(3002001)(10201501046)(100000703101)(100105400095)(6055026)(6041248)(20161123555025)(20161123560025)(20161123564025)(20161123558100)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123562025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:VI1PR0802MB2463;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:VI1PR0802MB2463; X-Forefront-PRVS: 04433051BF X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10009020)(979002)(6009001)(376002)(39860400002)(346002)(57704003)(199003)(24454002)(189002)(8676002)(81156014)(81166006)(1076002)(23726003)(8936002)(3846002)(305945005)(50466002)(16526017)(7736002)(316002)(2906002)(50226002)(68736007)(53936002)(2950100002)(5660300001)(6246003)(72206003)(6116002)(47776003)(189998001)(9686003)(55016002)(86362001)(50986999)(25786009)(36756003)(69596002)(21086003)(478600001)(66066001)(6916009)(101416001)(230700001)(6506006)(6666003)(229853002)(4326008)(33646002)(105586002)(106356001)(76176999)(97736004)(34023003)(148693002)(39210200001)(969003)(989001)(999001)(1009001)(1019001);DIR:OUT;SFP:1101;SCL:1;SRVR:VI1PR0802MB2463;H:m750.lan;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1;VI1PR0802MB2463;23:08nzSgNhgFancN6mRiozyU7zR2xxGMHD0UI9fiz?= =?us-ascii?Q?toJES9P5Gxx/hHDHuX27ydGcdKvnG3mfWSGic9yNEz9NBsrDttIZQHO6HNa9?= =?us-ascii?Q?LwSCRPg2emUG2SjNWnXPYYJsPtfE0Pji6zV6l/IcrN/mBS5w8eF/c9k3ui8n?= =?us-ascii?Q?hK6iA90riT+5geuxi63a8NRu4QTOkzX612V/cL55CL3TxAOws6pyTQ5UO6e+?= =?us-ascii?Q?zP3nwGQM/SZMbmi3iZQt6Cs3h1etVhQ3y0ES3hdet52RnwxeRyVoV7539mfw?= =?us-ascii?Q?4z1tik6jXSpWOD6M54cvn1jySVrfPRUkj9XoEcpgPPefHHMUyADOuUPjHUyr?= =?us-ascii?Q?KvGbam/TZWCnsYYbu10LrH7vD/I2agK5QIbgELJjnKPjzzART+CTFqIjExbi?= =?us-ascii?Q?t2qCFgH0eiGsmpR0cdQ3i5JIdFukZpah6wmF1E1C3A4timllEr4vfehbUdSH?= =?us-ascii?Q?MkblMRhiaG3M/ObJbdQxQ7qAFzYLNcC80W5H3fUuoHbr02oZf7Mf7k/eGHIT?= =?us-ascii?Q?+MPnsMgKiIFuHWDMgvwiAheAjX+EHmgRPf0qnSgRXf2CoqmZtY9EaVsgACBI?= =?us-ascii?Q?n0ohf80Q71mYwyR5tNx+TX80tXlDPzgNi6fd/DcI8zQTreSjy8WmgaNEY5Bq?= =?us-ascii?Q?7bV0DQklEgaUhBsU9uhyZTpQzz4qot+4lzxz48+9639EBvJQus9liplT6DzQ?= =?us-ascii?Q?d2W5p2xwMKdjEoE+PG8BFmtt1lySio/9nG0PkgXAqeCzvb7JIHUywPt0ZxhS?= =?us-ascii?Q?NPu5EGxkEA/WE/aAoQasZfWk8NucuP68Hd+omNBRBMXcs1AmdXNx11ClCR+g?= =?us-ascii?Q?RA8nxFvMrYJmiCxGo9nKwJvGeaY3UQ4vwmS3/eya7P4GPT1TNeozcmQ2Z3GG?= =?us-ascii?Q?kRzlXlc7V6dlQayun2V2H40+SxacTqjFHOb6g/8V0D4oqpWKvY8v3Glfgf+x?= =?us-ascii?Q?eX+xuZ/sAe6C3mDWJYPQBqHwBdtS/hM69fSADiOCy6yM76Vt41dN56fC1Voa?= =?us-ascii?Q?DknVNPhLYKfqhjR8fPLsmRj08Vmy00OAILprM5XI0UYy7CNiNCyISBJkHSrc?= =?us-ascii?Q?QGbbPzGOp1o44/9MDi7Dohdh1zU18IxdHEg7ggaKtESetD65j57WEwDP74cM?= =?us-ascii?Q?my3mhzD/WPe2VCcM97hHG2hT4Tao+DZ1/aGMqBV9Tx4G7ppJ0lfijUlTQtM8?= =?us-ascii?Q?yY4+srxfe4HkqXR1+RRK2AjAkw5pNUIVMV8lj8oD4BV9LKRQXwAlOMcLRucs?= =?us-ascii?Q?9sJRBd1CFJ5eQqVSE5mrODDCA2O99e5/CQakKZVZRxJlwvQXJKcAWHEzqWmj?= =?us-ascii?Q?3WKyFgcU85B1yK9juiCj0u7gzeJFtg8Y6egkhsimFyfE4asBL/wBcYW69App?= =?us-ascii?Q?z8jh2/uvbRbsQ6HU/Nq2C9ATW22/4bv/J16tYqtUDCoPx3Z/x?= X-Microsoft-Exchange-Diagnostics: 1;VI1PR0802MB2463;6:nSe5vxb56LSNj5gyScpavhzrio7pLzM+o3is/Nx+sUbjFd18mm4uMUJv7rZyx680y2SaJlQdKGpGOYR9JIaXUq48qNuEUSpvjA2+Fu8v0u+jKa3qvaNKYefW+8lIPLdfPSjwX9o6EZM0lBYztPHQ5pjGAvd1bGMDppmjLTH6V8Dp12CvLn1tfuRKM/5Nl8Ad2pIj9AMWTD+7ezMJFrqxlnwJj4anMifo6jQtDJdkhc6qCq8dA1s+iQ8qtao9WDwMyqXCtDFoEEWSEV91rlFipT1AENs0PQ/T4zQVovskmAJ/ZNpzI7mk/NRXAnV/y3gdQsdAZiGwNJsYYsOmSIuPQQ==;5:Gbmx7zlknsb+7d3sZyHww1U0/U8zPGyU3hVilcOS/58OAGmMudfhBXgOoCCtlfxkn8XpiL9eqFfAeqtiEEcVmFlMbwW5xwcbBA406LfwYqkUeTD2qyMgjr/M67KqgGScwbBV45J2F2izBDDMKxpxFg==;24:udGDjGSzOWanJOwWAK74z/0hEQr8PfWrbWPE9/m7nBILgqgTURU59fkOQngrWwehA/ItsV8KSC7zpZLdwRzHHXrb1op7GKzRnRM8PThYG4o=;7:JgWO4OSp/W3Xzvwbk4T+i6SP0Kdk0c41GPPxmKisrHmI4fJ5xpvicZFUNJ/JbXqSh0WOhz2TertNEwRLe0D1Q6XwTif96DBJxu/UuG2D0erATviNyuVK/aMflu0GdzKfKXlXyHRQRRVkCfYNysgs1WY7PAyGdUf8QgYQMu+K1Ce2FJaqu3HUfFbZCNpgAiXEM8oDNz4nlZ5iw4eg912h+Fo0FXMHv4wQ5XmkGx5RlZg= SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 27 Sep 2017 16:50:40.7379 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2463 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Wed, 27 Sep 2017 16:00:51 +0200 Joerg Roedel wrote: > On Tue, Sep 19, 2017 at 02:48:41PM +0100, Robin Murphy wrote: > > When devices with different DMA masks are using the same domain, or > > for PCI devices where we usually try a speculative 32-bit > > allocation first, there is a fair possibility that the top PFN of > > the rcache stack at any given time may be unsuitable for the lower > > limit, prompting a fallback to allocating anew from the rbtree. > > Consequently, we may end up artifically increasing pressure on the > > 32-bit IOVA space as unused IOVAs accumulate lower down in the > > rcache stacks, while callers with 32-bit masks also impose > > unnecessary rbtree overhead. > > > > In such cases, let's try a bit harder to satisfy the allocation > > locally first - scanning the whole stack should still be relatively > > inexpensive, and even rotating an entry up from the very bottom > > probably has less overall impact than going to the rbtree. > > > > Signed-off-by: Robin Murphy > > --- > > drivers/iommu/iova.c | 19 ++++++++++++++++--- > > 1 file changed, 16 insertions(+), 3 deletions(-) > > > > diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c > > index 8f8b436afd81..a7af8273fa98 100644 > > --- a/drivers/iommu/iova.c > > +++ b/drivers/iommu/iova.c > > @@ -826,12 +826,25 @@ static bool iova_magazine_empty(struct > > iova_magazine *mag) static unsigned long iova_magazine_pop(struct > > iova_magazine *mag, unsigned long limit_pfn) > > { > > + int i; > > + unsigned long pfn; > > + > > BUG_ON(iova_magazine_empty(mag)); > > > > - if (mag->pfns[mag->size - 1] > limit_pfn) > > - return 0; > > + /* > > + * If we can pull a suitable pfn from anywhere in the > > stack, that's > > + * still probably preferable to falling back to the rbtree. > > + */ > > + for (i = mag->size - 1; mag->pfns[i] > limit_pfn; i--) > > + if (i == 0) > > + return 0; > > > > - return mag->pfns[--mag->size]; > > + pfn = mag->pfns[i]; > > + mag->size--; > > + for (; i < mag->size; i++) > > + mag->pfns[i] = mag->pfns[i + 1]; > > Do we need to preserve the order of the elements on the stack or would > it also suffice to just copy the top-element to the position we are > removing? Ooh, good point - the order is more or less meaningless, and if it *did* matter then that would imply we couldn't do this anyway. Getting rid of the second loop makes it even more compelling. Robin.