From patchwork Fri Sep 23 20:16:26 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 9348813 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 459D7607D0 for ; Fri, 23 Sep 2016 20:32:21 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 35A602ADD2 for ; Fri, 23 Sep 2016 20:32:21 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 29B6A2ADD7; Fri, 23 Sep 2016 20:32:21 +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, T_TVD_MIME_EPI autolearn=unavailable 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 963E02ADD2 for ; Fri, 23 Sep 2016 20:32:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1034550AbcIWUbb (ORCPT ); Fri, 23 Sep 2016 16:31:31 -0400 Received: from mail-dm3nam03on0096.outbound.protection.outlook.com ([104.47.41.96]:42158 "EHLO NAM03-DM3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1034528AbcIWUb2 (ORCPT ); Fri, 23 Sep 2016 16:31:28 -0400 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=IYr9wjpP9c2fjAnny4Ir0GOJk/hWJsYKMfe/8OYd6jw=; b=Fe6ahSfKGU+0uoa6AgbqWAuib729CYj1irlxnsJ/OMVMi8d+j/9IMN6wXmlXewfztx22EtTxDLqbCCi3xT2cF9+x8HPdnKVrt/gFwsBwBoHhlYdDFgrusi6nklSKUkMvBMojTuoGmNVbXyu8YDnJ5EUU2rrQa7nK8/MxLLB1vbc= Received: from DM2PR21MB0089.namprd21.prod.outlook.com (10.161.141.13) by DM2PR21MB0092.namprd21.prod.outlook.com (10.161.141.140) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.649.2; Fri, 23 Sep 2016 20:16:27 +0000 Received: from DM2PR21MB0089.namprd21.prod.outlook.com ([10.161.141.13]) by DM2PR21MB0089.namprd21.prod.outlook.com ([10.161.141.13]) with mapi id 15.01.0649.010; Fri, 23 Sep 2016 20:16:26 +0000 From: Matthew Wilcox To: Linus Torvalds , Matthew Wilcox CC: "Kirill A. Shutemov" , Andrew Morton , Konstantin Khlebnikov , "Ross Zwisler" , Linux Kernel Mailing List , linux-mm , linux-fsdevel Subject: RE: [PATCH 2/2] radix-tree: Fix optimisation problem Thread-Topic: [PATCH 2/2] radix-tree: Fix optimisation problem Thread-Index: AQHSFPNCYSrccXS7WEK/kXzGlbj9mqCFzvUAgAATN6A= Date: Fri, 23 Sep 2016 20:16:26 +0000 Message-ID: References: <1474570415-14938-1-git-send-email-mawilcox@linuxonhyperv.com> <1474570415-14938-3-git-send-email-mawilcox@linuxonhyperv.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: yes X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=mawilcox@microsoft.com; x-originating-ip: [108.161.120.18] x-ms-office365-filtering-correlation-id: 725f3a02-9148-4027-22f7-08d3e3ee7f2c x-microsoft-exchange-diagnostics: 1; DM2PR21MB0092; 7:JGHTtre5GMpNYJGcSux07aSwi9MjR2MUwdRr3yMBLIrs/gzJaQXD0spnftsSA1c9P0MlVGf3BPFNRbXKMcgih26UsxRQNNfjNpnzrEzRaCb1LoFhvoTP6TLTBDhyJAymqaopjZWd6Jwhsrs5VbJ8Mxx48i3hhlsMcz3Vc9aSY6Yc4vpx6tkZzdR+wLDas/kcf2Due65+Pmi07+OoYOqCCETnKtOQig9Klgq3PCXxamr+ivZfdyYVBGt8Vd9ACISK5B2LhzKoqQ+yhEn33fWmJmEySyWTCnRRvUkpGoj0v6tl36UPLdB8E9TK/uGdSOMNdFLogZDQzoFakpDuulHfaA== x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:DM2PR21MB0092; x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102415321)(61425038)(6040176)(601004)(2401047)(8121501046)(5005006)(3002001)(10201501046)(6055026)(61426038)(61427038); SRVR:DM2PR21MB0092; BCL:0; PCL:0; RULEID:; SRVR:DM2PR21MB0092; x-forefront-prvs: 0074BBE012 x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(7916002)(24454002)(377454003)(199003)(189002)(5890100001)(8676002)(3660700001)(81156014)(81166006)(3280700002)(2900100001)(2906002)(77096005)(122556002)(8990500004)(87936001)(2950100002)(10090500001)(66066001)(10400500002)(10290500002)(8936002)(19580405001)(19580395003)(5005710100001)(33656002)(76176999)(86612001)(101416001)(86362001)(99936001)(54356999)(50986999)(102836003)(189998001)(3846002)(92566002)(4326007)(586003)(106356001)(106116001)(105586002)(7696004)(99286002)(6116002)(9686002)(97736004)(5001770100001)(7736002)(5002640100001)(7846002)(68736007)(74316002)(305945005)(76576001)(5660300001); DIR:OUT; SFP:1102; SCL:1; SRVR:DM2PR21MB0092; H:DM2PR21MB0089.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: 23 Sep 2016 20:16:26.3041 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM2PR21MB0092 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: linus971@gmail.com [mailto:linus971@gmail.com] On Behalf Of Linus Torvalds > On Thu, Sep 22, 2016 at 11:53 AM, Matthew Wilcox > wrote: > > > > Change the test suite to compile with -O2, and > > fix the optimisation problem by passing 'entry' through entry_to_node() > > so gcc knows this isn't a plain pointer. > > Ugh. I really don't like this patch very much. > > Wouldn't it be cleaner to just fix "get_slot_offset()" instead? As it > is, looking at the code, I suspect that it's really hard to convince > people that there isn't some other place this might happen. Because > the "pointer subtraction followed by pointer addition" pattern is all > hidden in these inline functions. > > Or at least add a big comment about why this is the only such case. > > Because without that, the code now looks very bad. That's fair. I looked at all the other callers of get_slot_offset, and all the others are using a real slot pointer. radix_tree_descend() really is the outlier here. I think the real problem is that the types in the tree are wrong; instead of storing void *, we should be storing uintptr_t. But fixing that is a little beyond the scope of -rc8. Here's a slightly better version which asserts that the passed pointer really is a pointer. (attached as well, I have no idea whether this patch will get mangled) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 1b7bf73..368f641 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -91,9 +91,15 @@ static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) } #endif +/* + * The slot pointer must be a real pointer as GCC will optimise + * through inlined functions and may deduce that + * parent->slots + get_slot_offset(parent, slot) == slot + */ static inline unsigned long get_slot_offset(struct radix_tree_node *parent, void **slot) { + BUG_ON(radix_tree_exception(slot)); return slot - parent->slots; } @@ -101,11 +107,12 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent, struct radix_tree_node **nodep, unsigned long index) { unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; - void **entry = rcu_dereference_raw(parent->slots[offset]); + void *entry = rcu_dereference_raw(parent->slots[offset]); #ifdef CONFIG_RADIX_TREE_MULTIORDER if (radix_tree_is_internal_node(entry)) { - unsigned long siboff = get_slot_offset(parent, entry); + unsigned long siboff = get_slot_offset(parent, + (void **)entry_to_node(entry)); if (siboff < RADIX_TREE_MAP_SIZE) { offset = siboff; entry = rcu_dereference_raw(parent->slots[offset]); @@ -113,7 +120,7 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent, } #endif - *nodep = (void *)entry; + *nodep = entry; return offset; } diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 3b53046..9d0919ed 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,5 +1,5 @@ -CFLAGS += -I. -g -Wall -D_LGPL_SOURCE +CFLAGS += -I. -g -O2 -Wall -D_LGPL_SOURCE LDFLAGS += -lpthread -lurcu TARGETS = main OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \