Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1759777AbcLRCn3 (ORCPT ); Sat, 17 Dec 2016 21:43:29 -0500 Received: from mail-co1nam03on0125.outbound.protection.outlook.com ([104.47.40.125]:63848 "EHLO NAM03-CO1-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1755023AbcLRCn0 (ORCPT ); Sat, 17 Dec 2016 21:43:26 -0500 X-Greylist: delayed 111390 seconds by postgrey-1.27 at vger.kernel.org; Sat, 17 Dec 2016 21:43:25 EST From: Matthew Wilcox To: Rasmus Villemoes CC: Tejun Heo , "linux-kernel@vger.kernel.org" , Lai Jiangshan , "Jens Axboe" , Greg Kroah-Hartman , "linux-block@vger.kernel.org" , "dri-devel@lists.freedesktop.org" , "Andrew Morton" Subject: RE: [RFC 00/10] implement alternative and much simpler id allocator Thread-Topic: [RFC 00/10] implement alternative and much simpler id allocator Thread-Index: AQHSUme+SjIWPmjllE++nkCQM7WotKEKtg/QgABcHJ+AAAiNEIAACqdQgAHl61A= Date: Sun, 18 Dec 2016 02:42:07 +0000 Message-ID: References: <1481160187-9652-1-git-send-email-linux@rasmusvillemoes.dk> <20161209140140.5e0a68e2e1cf9861335bdf3b@linux-foundation.org> <87inqj8vjo.fsf@rasmusvillemoes.dk> 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: [76.10.168.227] x-ms-office365-filtering-correlation-id: 05713418-cf79-4eda-449c-08d426ef75af x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001);SRVR:BY2PR21MB0035; x-microsoft-exchange-diagnostics: 1;BY2PR21MB0035;7:PxK2wIZ/LtrPW2GZWlkFEf40M4qn6ebxLnfmoEzuMNRUwZSVDdgw/tIOeWBYBvw4GOZmzlYZyl9fCi2jgangvHJy2GAabU0rQcE4DRuwA7w9nyx6Im0uQazqWawfNkU1HiDAOSeLhPkHBYynLzsPrqpkaqeyxpZSt026TXJ0ei/LKXJxo1IxThEaSVIBpCQ3Um2IJbnnPDfM5ax3DM64rBlIKgJfAy8h4M/lVR3VdbczP/qMiA6HhwnnrAyLPSTiaGN2fe+CZn4klI7/8RPo5Ddmh+q2goFahoe9pEwA0iqDH5KBOA7rqnpU+om83p2HANrrDELLz13Kw/J33MNDR/e38G7YbLpt0+EX+9/ozqfwPcKUgaxxW28wXeyd+yK/xsD1q85wKvlPJp2mvfNxzxgycsO6Y/YDgqruv4B6dM9Aefstc8y9STD84c26dYpHjag+RNqtw1yxS281C11Fho5z74gvrwYRFV3gVDWjPik= x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(61425038)(6040375)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6055026)(61426038)(61427038)(6041248)(20161123555025)(20161123560025)(20161123558021)(20161123564025)(20161123562025)(6072148);SRVR:BY2PR21MB0035;BCL:0;PCL:0;RULEID:;SRVR:BY2PR21MB0035; x-forefront-prvs: 01604FB62B x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(7916002)(39850400002)(39450400003)(39840400002)(39860400002)(39410400002)(199003)(189002)(99286002)(3280700002)(3660700001)(122556002)(105586002)(106116001)(106356001)(10290500002)(8990500004)(76576001)(2900100001)(1720100001)(8676002)(81156014)(81166006)(97736004)(7696004)(9686002)(110136003)(8936002)(4001150100001)(66066001)(6916009)(3846002)(102836003)(6116002)(189998001)(33656002)(2906002)(4326007)(68736007)(5660300001)(54356999)(229853002)(76176999)(50986999)(7736002)(305945005)(74316002)(101416001)(86362001)(10090500001)(6436002)(25786008)(38730400001)(6506006)(39060400001)(86612001)(77096006)(93886004)(92566002)(5005710100001);DIR:OUT;SFP:1102;SCL:1;SRVR:BY2PR21MB0035;H:BY2PR21MB0036.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 Dec 2016 02:42:07.8541 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY2PR21MB0035 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 uBI2hcTT002346 Content-Length: 1115 Lines: 18 From: Matthew Wilcox > From: Matthew Wilcox > > Heh, I was thinking about that too. The radix tree supports "exceptional > > entries" which have the bottom bit set. On a 64-bit machine, we could use > 62 > > of the bits in the radix tree root to store the ID bitmap. I'm a little wary of > the > > potential complexity, but we should try it out. > > Test patch here: http://git.infradead.org/users/willy/linux- > dax.git/shortlog/refs/heads/idr-2016-12-16 > It passes the test suite ... which I actually had to adjust because it now succeeds > in cases where it hadn't (allocating ID 0 without preallocating), and it will now > fail in cases where it hadn't previously (assuming a single preallocation would > be enough). There shouldn't be any examples of that in the kernel proper; it > was simply me being lazy when I wrote the test suite. Found a bug, committed a fix (and another test case). It now no longer returns -EAGAIN in situations where it wouldn't have, so I've reverted that bit of the test suite change. Still succeeds when it wouldn't have before, but I feel no pressure to change that ;-)