Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753324AbcKRU4s (ORCPT ); Fri, 18 Nov 2016 15:56:48 -0500 Received: from mail-bl2nam02on0100.outbound.protection.outlook.com ([104.47.38.100]:19712 "EHLO NAM02-BL2-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1752136AbcKRU4p (ORCPT ); Fri, 18 Nov 2016 15:56:45 -0500 From: Matthew Wilcox To: Konstantin Khlebnikov CC: Matthew Wilcox , Linux Kernel Mailing List , Andrew Morton , Ross Zwisler , linux-fsdevel , "linux-mm@kvack.org" , "Kirill A . Shutemov" , Huang Ying Subject: RE: [PATCH 20/29] radix tree: Improve multiorder iterators Thread-Topic: [PATCH 20/29] radix tree: Improve multiorder iterators Thread-Index: AQHSQFgot1kf63WjGkKZ6X7PkzZ2UaDeomuAgAAhNlCAAEXLgIAABMJg Date: Fri, 18 Nov 2016 20:23:10 +0000 Message-ID: References: <1479341856-30320-1-git-send-email-mawilcox@linuxonhyperv.com> <1479341856-30320-59-git-send-email-mawilcox@linuxonhyperv.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=mawilcox@microsoft.com; x-originating-ip: [184.175.4.94] x-ms-office365-filtering-correlation-id: 2abf3c44-ddc5-4439-0428-08d40ff0b72d x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001);SRVR:SN1PR21MB0080; x-microsoft-exchange-diagnostics: 1;SN1PR21MB0080;7:8Y2S23uu4BbKEr1sraenFKKmX7SkazyaIFKtIlXEI6dBIzHKumFlK0BWuHJK+PsEZW+HvO9sGonL348qJzeEfDyw/mQ6OgPWcOrH+FHKm0udPSn9rCZBdfqoWLEyvWB0aTGbLL6QU5fS/oXJcjWsFSnNO55ldoFNJKkVV1BpNx6g6vKu/CWhcJO3AO4LksVr0pRsuFOlcy3/KGE4YbcsYg2RbgQyZbrVlH2cC34bmFEUu5QEsb8oWtCmfAZiajJzNKgSalI3tWED3oHCQFPjWX5CeyYOaDb1+24CAL/8HVdJ+bWtGV0JkePgbuoX7Fnf+fRSsUdGXzcueUPK3ZtF4z6RaEvdbQCrT1Hj9fG7TKiea0aHlnxhFlIz2THrz39vfc2fBEUVNlBRkTldKjuANTNVKiVfdwmjYNECFPqOuE3tlXWKe3YJI8Ezuqte4y7VL68diQsR7RtmM93iuxGbyuLSisi0uYeEaSJGHWliovI= x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(61425038)(6040281)(6060326)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6055026)(61426038)(61427038)(6041223)(6061324);SRVR:SN1PR21MB0080;BCL:0;PCL:0;RULEID:;SRVR:SN1PR21MB0080; x-forefront-prvs: 01304918F3 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(7916002)(199003)(189002)(24454002)(377454003)(3846002)(189998001)(7736002)(102836003)(97736004)(7846002)(6116002)(74316002)(76176999)(105586002)(106116001)(6506003)(50986999)(77096005)(305945005)(92566002)(229853002)(8676002)(5005710100001)(1411001)(2900100001)(10290500002)(38730400001)(66066001)(99286002)(10090500001)(106356001)(8990500004)(86362001)(8936002)(68736007)(101416001)(93886004)(54356999)(9686002)(87936001)(122556002)(33656002)(81166006)(76576001)(81156014)(4326007)(7696004)(110136003)(5660300001)(3660700001)(3280700002)(2950100002)(86612001)(6916009)(2906002);DIR:OUT;SFP:1102;SCL:1;SRVR:SN1PR21MB0080;H:SN1PR21MB0077.namprd21.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 X-OriginatorOrg: microsoft.com X-MS-Exchange-CrossTenant-originalarrivaltime: 18 Nov 2016 20:23:10.4099 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN1PR21MB0080 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by mail.home.local id uAIKuwTP021607 Content-Length: 3516 Lines: 86 From: Konstantin Khlebnikov [mailto:koct9i@gmail.com] > On Fri, Nov 18, 2016 at 7:31 PM, Matthew Wilcox > wrote: > > I think what you're suggesting is that we introduce a new API: > > > > slot = radix_tree_iter_save(&iter, order); > > > > where the caller tells us the order of the entry it just consumed. Or maybe > you're suggesting > > > > slot = radix_tree_iter_advance(&iter, newindex) > > Yes, someting like that. > > > > > which would allow us to skip to any index. Although ... isn't that just > radix_tree_iter_init()? > > Iterator could keep pointer to current node and reuse it for next > iteration if possible. The point of this API is that it's never possible, because we're about to drop the lock and allow other users to modify the tree. Actually, it is different from radix_tree_iter_init() because it has to set ->tags to 0 and ->index == ->next_index in order to get through a call to radix_tree_next_slot(). > > It does push a bit of complexity onto the callers. We have 7 callers of > > radix_tree_iter_next() in my current tree (after applying this patch set, so > > range_tag_if_tagged and locate_item have been pushed into their callers): > > btrfs, kugepaged, page-writeback and shmem. btrfs knows its objects occupy > > one slot. khugepaged knows that its page is order 0 at the time it calls > > radix_tree_iter_next(). Page-writeback has a struct page and can simply use > > compound_order(). It's shmem where things get sticky, although it's all > > solvable with some temporary variables. > > Users who work only with single slot enties don't get any complications, > all other already manage these multiorder entries somehow. If you read the patch below, you'll see that most callers don't need to be concerned with the size of the entry they're looking at. I'll trim away the trivial ones so it's easier to see my point. It's not a huge amount of code in each caller, but is this a burden we really want to push onto the callers when we could handle it behind the interface? diff --git a/mm/shmem.c b/mm/shmem.c index 8f9c9aa..90dd18d9 100644 --- a/mm/shmem.c +++ b/mm/shmem.c @@ -658,7 +658,10 @@ unsigned long shmem_partial_swap_usage(struct address_space *mapping, swapped++; if (need_resched()) { - slot = radix_tree_iter_next(slot, &iter); + unsigned int order = 0; + if (!radix_tree_exceptional_entry(page)) + order = compound_order(page); + slot = radix_tree_iter_save(&iter, order); cond_resched_rcu(); } } @@ -2450,6 +2453,7 @@ static void shmem_tag_pins(struct address_space *mapping) slot = radix_tree_iter_retry(&iter); continue; } + page = NULL; } else if (page_count(page) - page_mapcount(page) > 1) { spin_lock_irq(&mapping->tree_lock); radix_tree_tag_set(&mapping->page_tree, iter.index, @@ -2458,7 +2462,8 @@ static void shmem_tag_pins(struct address_space *mapping) } if (need_resched()) { - slot = radix_tree_iter_next(slot, &iter); + unsigned int order = page ? compound_order(page) : 0; + slot = radix_tree_iter_save(&iter, order); cond_resched_rcu(); } } @@ -2528,7 +2533,10 @@ static int shmem_wait_for_pins(struct address_space *mapping) spin_unlock_irq(&mapping->tree_lock); continue_resched: if (need_resched()) { - slot = radix_tree_iter_next(slot, &iter); + unsigned int order = 0; + if (page) + order = compound_order(page); + slot = radix_tree_iter_save(&iter, order); cond_resched_rcu(); } }