From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935598AbcHaO5Y (ORCPT ); Wed, 31 Aug 2016 10:57:24 -0400 Received: from mail-dm3nam03on0131.outbound.protection.outlook.com ([104.47.41.131]:31389 "EHLO NAM03-DM3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S934021AbcHaO5U (ORCPT ); Wed, 31 Aug 2016 10:57:20 -0400 From: Matthew Wilcox To: Dan Williams , Ross Zwisler CC: Konstantin Khlebnikov , "linux-kernel@vger.kernel.org" Subject: RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Thread-Topic: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Thread-Index: AQHSAI4pNn/ps2i9FEaiEt5NHHGFKKBf8b9wgAAt5wCAAB85MIAAAsaAgAAJfDCAAcZtgIAAAiCAgAAE5QCAARX1UA== Date: Wed, 31 Aug 2016 14:57:17 +0000 Message-ID: References: <147230727479.9957.1087787722571077339.stgit@zurg> <20160827180927.GA22919@linux.intel.com> <20160830220353.GB20121@linux.intel.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: [75.119.248.4] x-ms-office365-filtering-correlation-id: 00660b46-1e8d-48ab-5bd0-08d3d1af1a41 x-microsoft-exchange-diagnostics: 1;DM2PR21MB0089;6:5sbiLbOY6NL7wGxF4fzR+3NIX1QWnpukKrfdkm9BpgWG4km6u3h79Vs751n2bCCnkZrGbdkLH71+Cvguj76dqtdx42IelqFcuzWWg3qwkhFBnsTInQYUwflXE3t0EZCAORlovOm3sYc1mWXsO7z7WK7INcUo3hQ4t1Cn7AsIorS/ZV5H+X5y9K2zMDaCrhaRiPHGDuMFrt/wdhM0V4hgZEDQOZWGAJ/XkT8TxRWt12r+0+Ylr/wx188RGXUwBaLpc3O2QLBYbhuMCbcgYdXRWwcNVExZb1aPxGNYL2fDwwlvkBie5NgHgzGSrOojAecMYMdA6CBNvZX8DJ2r3bfBzg==;5:b7aCL7Z7k0qpg628Z5KNo0xSEdn1J3WbyjGpaxIJY5c6tpRGOSAuOryF55TsRxqureLL6jnr+5r2QQdEwRKOMoU0qEZfSO7bPikJw5vyXyBr1N74qaEEmBp5qo5+lbPIZ0HWdakFWpisp6Fv5qhAig==;24:r8pEXJSn2JWjAIuBy1WT8KKwKBWwaDc8TT3XrbId6VeliLsI6X+7vOFK43v8kuk1vkmXTzI541kwDFyVugURfOyJZ58wPuIFQxpO+z2lrfM=;7:Jrm1vC47USqBXF1w78m5O4QGl5WICkC3hBqcmTAqViAGOuAQLTTI16cRkblmM5K04x/Xfl+Yd7EG77kiaCwjvy4vTNT8AZm9OpUHP651GLxuFxUi2Qp8kD7hQJs3e4Cf+Iq2dJM2zpuq6E+C8hktFYzmymO/9SvKwvAMsNqL2QYv5KTO1zlI/p1d3b9usEYwu//fLiImKsSZeSFTzMZfduedUjUUod2dbzYCAAW8bT9nR8AICRnlnN5wd3ljy7EH x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:DM2PR21MB0089; x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(9452136761055)(228905959029699); x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(61425038)(6040176)(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046)(6055026)(61426038)(61427038);SRVR:DM2PR21MB0089;BCL:0;PCL:0;RULEID:;SRVR:DM2PR21MB0089; x-forefront-prvs: 00514A2FE6 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(7916002)(24454002)(199003)(377454003)(13464003)(189002)(11100500001)(10090500001)(2906002)(87936001)(77096005)(3660700001)(8676002)(10290500002)(8990500004)(5001770100001)(5005710100001)(81166006)(81156014)(97736004)(10400500002)(92566002)(68736007)(50986999)(86362001)(586003)(189998001)(5002640100001)(8936002)(6116002)(86612001)(33656002)(102836003)(4326007)(3846002)(101416001)(76176999)(54356999)(9686002)(7736002)(7696003)(305945005)(7846002)(122556002)(76576001)(93886004)(2900100001)(3280700002)(2950100001)(74316002)(106116001)(99286002)(105586002)(19580395003)(66066001)(19580405001)(106356001)(5660300001)(217873001);DIR:OUT;SFP:1102;SCL:1;SRVR:DM2PR21MB0089;H:DM2PR21MB0089.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: 31 Aug 2016 14:57:17.8153 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM2PR21MB0089 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 u7VEvaQ4005465 I'm not at all against the idea of having a tree which supports ranges, except that we already have one; the interval tree. Did you investigate using the interval tree for your use case? -----Original Message----- From: Dan Williams [mailto:dan.j.williams@intel.com] Sent: Tuesday, August 30, 2016 6:21 PM To: Ross Zwisler Cc: Matthew Wilcox ; Konstantin Khlebnikov ; linux-kernel@vger.kernel.org Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler wrote: > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote: >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox wrote: >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually. No mapping lock, just like the page cache. >> > >> > Even if we can work around it, why do we want to? What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range? There are no in-kernel users right now; is there a performance reason to change? We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it. >> >> I'd use a fill range api for the radix backing get_dev_pagemap() and >> potentially another use in device-dax. It centralizes the common >> routine of breaking down a range into its constituent power-of-2 >> ranges. > > Does your usage not work with the current sibling & canonical entry model? It does, but I find myself writing code to walk a range and determine the order of each entry as I insert them. I can see other users needing the same sort of insert helper and the aspect I like of Konstantin's proposed change is that the functionality is part of the core implementation rather than left to be duplicated in each user.