From patchwork Sun Sep 25 19:04:33 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Torvalds X-Patchwork-Id: 9349889 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 8D45E607F0 for ; Sun, 25 Sep 2016 19:04:50 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7090828C6E for ; Sun, 25 Sep 2016 19:04:50 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6504928C71; Sun, 25 Sep 2016 19:04:50 +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.3 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,RCVD_IN_SORBS_SPAM,T_DKIM_INVALID,T_TVD_MIME_EPI 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 0050A28C6E for ; Sun, 25 Sep 2016 19:04:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758087AbcIYTEg (ORCPT ); Sun, 25 Sep 2016 15:04:36 -0400 Received: from mail-oi0-f46.google.com ([209.85.218.46]:35635 "EHLO mail-oi0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756866AbcIYTEf (ORCPT ); Sun, 25 Sep 2016 15:04:35 -0400 Received: by mail-oi0-f46.google.com with SMTP id w11so186141635oia.2; Sun, 25 Sep 2016 12:04:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=yBuHynHkUp+9/yX+sMFZXTNfgZbKwwaXmNavrMTcR+E=; b=mZA4Lfp3r79VaX+ffTYnCC9d8fjpIbnMEUXZtr3PvbUNLw7i0eR2RT87jdgthQoD7I /mDN/njx3SQLfZEKCrQcDBXtZtWJC4myNTFmswpXmZgWYirw7JH2rlMzxyQ6JS08WFMx A0U8FA1Itl7B/ImY2x0V8RwrNEboLrBhA+Q9WK+4qz1Y7RtoypbHqHMKgWq03mrdCYYt 78N4r1QIWN+7oboD0hs7+Tu/4/P/MuMdVUtaiZTR2vyxYlM63j9tNOMmO77N8VbyzenY ZqWQbZdefjmSQbmZiwi2bS/VxJAb0FpkywSkDfgcKekqJnC3nQtyTX+/Uu/VBbrL7aqQ iu/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=yBuHynHkUp+9/yX+sMFZXTNfgZbKwwaXmNavrMTcR+E=; b=Q41sDTFCyocm5brSBywgHJEh9eQVYNb0ufmOw9Hvglm35HYAwLaop+34cNQUMQ6Zn3 7Z2RbShvIQl97XxUNVBMGYyEjk9jTqFyKXCJ9FCgcNmFTX/C9dW30hyFDUn5pXXiWC0G tzB74ErKQpdzAZf+xF4R/EHLyo9cMbSBBFYAGlq+jdmRozECoC4s+wOae+eZ+/hoNesX ElMCdHFb6FF1sTD8c7ogqkC3LAPKi4kbPec6w6f2Qk0+dl6NNEG65LeA1TNmdG7uGts8 spFOQLDgBaFI4jq3743++DojMD5AkJkyI2wxx+B8SsGErJ2MHoQkUFTDCx7iNaw1JLmr UrzA== X-Gm-Message-State: AE9vXwN/maYeH5QBhIAm5gdcT+tODJRhPofBbdP3wOTPpEKo4q5nHPAzKLdf65YTlaFzxG5g+CKBOnSUsvtuKg== X-Received: by 10.202.85.14 with SMTP id j14mr21284989oib.37.1474830273841; Sun, 25 Sep 2016 12:04:33 -0700 (PDT) MIME-Version: 1.0 Received: by 10.182.119.104 with HTTP; Sun, 25 Sep 2016 12:04:33 -0700 (PDT) In-Reply-To: References: <1474570415-14938-1-git-send-email-mawilcox@linuxonhyperv.com> <1474570415-14938-3-git-send-email-mawilcox@linuxonhyperv.com> From: Linus Torvalds Date: Sun, 25 Sep 2016 12:04:33 -0700 X-Google-Sender-Auth: a8Ss6Wk_OkLtoZoO16jBUlIsCKY Message-ID: Subject: Re: [PATCH 2/2] radix-tree: Fix optimisation problem To: Cedric Blancher Cc: Ross Zwisler , Matthew Wilcox , Konstantin Khlebnikov , Andrew Morton , "Kirill A. Shutemov" , linux-fsdevel , Linux MM , Linux Kernel Mailing List , Matthew Wilcox 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 On Sun, Sep 25, 2016 at 11:04 AM, Linus Torvalds wrote: > > The more I look at that particular piece of code, the less I like it. It's > buggy shit. It needs to be rewritten entirely too actually check for sibling > entries, not that ad-hoc arithmetic crap. Here's my attempt at cleaning the mess up. I'm not claiming it's perfect, but I think it's better. It gets rid of the ad-hoc arithmetic in radix_tree_descend(), and just makes all that be inside the is_sibling_entry() logic instead. Which got renamed and made to actually return the main sibling. So now there is at least only *one* piece of code that does that range comparison, and I don't think there is any huge need to explain what's going on, because the "magic" is unconditional. Willy? Linus lib/radix-tree.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 1b7bf7314141..210709b07759 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -78,18 +78,20 @@ static inline void *node_to_entry(void *ptr) #ifdef CONFIG_RADIX_TREE_MULTIORDER /* Sibling slots point directly to another slot in the same node */ -static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) +static inline void **get_sibling_entry(struct radix_tree_node *parent, void *node) { - void **ptr = node; - return (parent->slots <= ptr) && - (ptr < parent->slots + RADIX_TREE_MAP_SIZE); + void **ptr = (void **) entry_to_node(node); + if ((parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE)) + return ptr; + return NULL; } #else -static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) +static inline void **get_sibling_entry(struct radix_tree_node *parent, void *node) { - return false; + return NULL; } #endif +#define is_sibling_entry(parent, node) (get_sibling_entry(parent,node) != NULL) static inline unsigned long get_slot_offset(struct radix_tree_node *parent, void **slot) @@ -105,10 +107,10 @@ static unsigned int radix_tree_descend(struct radix_tree_node *parent, #ifdef CONFIG_RADIX_TREE_MULTIORDER if (radix_tree_is_internal_node(entry)) { - unsigned long siboff = get_slot_offset(parent, entry); - if (siboff < RADIX_TREE_MAP_SIZE) { - offset = siboff; - entry = rcu_dereference_raw(parent->slots[offset]); + void **sibentry = get_sibling_entry(parent, entry); + if (sibentry) { + offset = get_slot_offset(parent, sibentry); + entry = rcu_dereference_raw(*sibentry); } } #endif