From patchwork Fri Nov 18 20:23:10 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 9437395 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 945ED60238 for ; Fri, 18 Nov 2016 20:56:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8296F29A22 for ; Fri, 18 Nov 2016 20:56:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 767AC29A24; Fri, 18 Nov 2016 20:56:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E82CA29A22 for ; Fri, 18 Nov 2016 20:56:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753246AbcKRU4q (ORCPT ); Fri, 18 Nov 2016 15:56:46 -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 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=QAhggcmGbxrrK5t3BymIPcq443Ne7BFgO1kVo6w5zGg=; b=cGvBVGSbFP48MkoCbBAqNF2SxWlzJghphrlP8N2bXyXZxmOnPVa03X+GlLdAO9a7e/ZeDTHR2WwKWOB03ikbMwo2rfChY6PS9kKXi4Cfph0jf/YvRypz03lyBaD5BFhaxS5C12W2YkS7Ca4+RLGMQrsHzp039IkRnoAdhk/Osqw= Received: from SN1PR21MB0077.namprd21.prod.outlook.com (10.161.254.150) by SN1PR21MB0080.namprd21.prod.outlook.com (10.161.254.153) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.747.0; Fri, 18 Nov 2016 20:23:10 +0000 Received: from SN1PR21MB0077.namprd21.prod.outlook.com ([10.161.254.150]) by SN1PR21MB0077.namprd21.prod.outlook.com ([10.161.254.150]) with mapi id 15.01.0747.000; Fri, 18 Nov 2016 20:23:10 +0000 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; received-spf: None (protection.outlook.com: microsoft.com does not designate permitted sender hosts) spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM 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-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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(); } }