From patchwork Sun Nov 22 15:35:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pavel Begunkov X-Patchwork-Id: 11923909 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8DCAAC5519F for ; Sun, 22 Nov 2020 15:39:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 40F6120727 for ; Sun, 22 Nov 2020 15:39:29 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iVfSAHc1" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727897AbgKVPjI (ORCPT ); Sun, 22 Nov 2020 10:39:08 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33474 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVPjI (ORCPT ); Sun, 22 Nov 2020 10:39:08 -0500 Received: from mail-ed1-x543.google.com (mail-ed1-x543.google.com [IPv6:2a00:1450:4864:20::543]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E01B5C0613CF; Sun, 22 Nov 2020 07:39:07 -0800 (PST) Received: by mail-ed1-x543.google.com with SMTP id l5so14513871edq.11; Sun, 22 Nov 2020 07:39:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=LLyBQQxzTUvx0SP9ZpRqeAeAOBvzcvUPKIXIwPCTeyk=; b=iVfSAHc1H9CV77pfjvfc2M51745vfVMqC1BNMpV7rs02iO6woKtZ4/l+Rc8W+/UvcR mlXP3F8+M78HXArx6mxnxilEU794c5aorXUI2ylqwYsJd7SusnLF28NeLD9hZai22o9k N1duXM6iKDCsPdDLRGpl+nQhZIU2zsoVBbWL1Sn81XnZ59BKF9lz/CVva8rPFL6KL9iy mpKTfeWnCV8QeWHf5BnnK7TeO6C5cD0Yuxm7AbkjQiIkkp3tia97dby5WN8jiJ8w6grU nONmBF7S4Y+80jS6veNK7gqqvwL+IXwtaYxDb5bySLFWi3en9lb1Bqf8m/CnorHYsyhU 0tqQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=LLyBQQxzTUvx0SP9ZpRqeAeAOBvzcvUPKIXIwPCTeyk=; b=B0i6/TbrOCIkvG1eecLQSAR4HyZSopsCeMjJGkdKCjSu1+eAr7D8M1ByqurwHKivLL qbS4UTN1zeLPSSFIEV7A++/rtCAD56C6Q2VUGCMoBry65oJA7ElhS/G3xMbCFHbBYtSA 5gNRMFjmcoseX0JjACQCX3dCFZrxTzQvytatE2P6NZyzEyzSMM7oSPSnt7R+gBatBDbV 10ll9hiiL2WoFTQjzYQxSYPcRfYMc/F8T4YntieBpvqXZk5qH3saHUkGHcnSezrI2zCA nrkm/mSQByrI6BCu9Bmu9JcSwJjsHkc3M636Kp/w4UvBk8KRbCib4HUT0JdO4i7D1vQP 62JA== X-Gm-Message-State: AOAM532oI1DGre6FD3eFUjZ6inhbf1iIWaNeGarU1KQYxZVmi2hCvXlh qSCGSGFLIXJIWX754xkDnLq7xKUig9hWjw== X-Google-Smtp-Source: ABdhPJyebL7zIQqA01s/GGvRTBnKNRzSk2yReIcnpgmnn8zZbYu0c6VwxeDiINHFefts9hjy0S6IQg== X-Received: by 2002:aa7:ca57:: with SMTP id j23mr19873066edt.292.1606059546594; Sun, 22 Nov 2020 07:39:06 -0800 (PST) Received: from localhost.localdomain (host109-152-100-189.range109-152.btcentralplus.com. [109.152.100.189]) by smtp.gmail.com with ESMTPSA id q19sm3693742ejz.90.2020.11.22.07.39.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:39:06 -0800 (PST) From: Pavel Begunkov To: Jens Axboe , linux-block@vger.kernel.org, Omar Sandoval Cc: linux-kernel@vger.kernel.org Subject: [PATCH v2 1/4] sbitmap: optimise sbitmap_deferred_clear() Date: Sun, 22 Nov 2020 15:35:45 +0000 Message-Id: X-Mailer: git-send-email 2.24.0 In-Reply-To: References: MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org Because of spinlocks and atomics sbitmap_deferred_clear() have to reload &sb->map[index] on each access even though the map address won't change. Pass in sbitmap_word instead of {sb, index}, so it's cached in a variable. It also improves code generation of sbitmap_find_bit_in_index(). Signed-off-by: Pavel Begunkov Reviewed-by: John Garry --- lib/sbitmap.c | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 267aa7709416..c1c8a4e69325 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -12,32 +12,32 @@ /* * See if we have deferred clears that we can batch move */ -static inline bool sbitmap_deferred_clear(struct sbitmap *sb, int index) +static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) { unsigned long mask, val; bool ret = false; unsigned long flags; - spin_lock_irqsave(&sb->map[index].swap_lock, flags); + spin_lock_irqsave(&map->swap_lock, flags); - if (!sb->map[index].cleared) + if (!map->cleared) goto out_unlock; /* * First get a stable cleared mask, setting the old mask to 0. */ - mask = xchg(&sb->map[index].cleared, 0); + mask = xchg(&map->cleared, 0); /* * Now clear the masked bits in our free word */ do { - val = sb->map[index].word; - } while (cmpxchg(&sb->map[index].word, val, val & ~mask) != val); + val = map->word; + } while (cmpxchg(&map->word, val, val & ~mask) != val); ret = true; out_unlock: - spin_unlock_irqrestore(&sb->map[index].swap_lock, flags); + spin_unlock_irqrestore(&map->swap_lock, flags); return ret; } @@ -92,7 +92,7 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth) unsigned int i; for (i = 0; i < sb->map_nr; i++) - sbitmap_deferred_clear(sb, i); + sbitmap_deferred_clear(&sb->map[i]); sb->depth = depth; sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); @@ -139,15 +139,15 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, unsigned int alloc_hint, bool round_robin) { + struct sbitmap_word *map = &sb->map[index]; int nr; do { - nr = __sbitmap_get_word(&sb->map[index].word, - sb->map[index].depth, alloc_hint, + nr = __sbitmap_get_word(&map->word, map->depth, alloc_hint, !round_robin); if (nr != -1) break; - if (!sbitmap_deferred_clear(sb, index)) + if (!sbitmap_deferred_clear(map)) break; } while (1); @@ -207,7 +207,7 @@ int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint, break; } - if (sbitmap_deferred_clear(sb, index)) + if (sbitmap_deferred_clear(&sb->map[index])) goto again; /* Jump to next index. */ From patchwork Sun Nov 22 15:35:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pavel Begunkov X-Patchwork-Id: 11923913 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 78A96C6379F for ; Sun, 22 Nov 2020 15:39:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3597E20781 for ; Sun, 22 Nov 2020 15:39:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="LhebEEN3" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727969AbgKVPjK (ORCPT ); Sun, 22 Nov 2020 10:39:10 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33480 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727317AbgKVPjJ (ORCPT ); Sun, 22 Nov 2020 10:39:09 -0500 Received: from mail-ej1-x643.google.com (mail-ej1-x643.google.com [IPv6:2a00:1450:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B226CC0613D3; Sun, 22 Nov 2020 07:39:08 -0800 (PST) Received: by mail-ej1-x643.google.com with SMTP id oq3so19792059ejb.7; Sun, 22 Nov 2020 07:39:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=dLNpQoSRr9iK3S6Fw6tI1eE1E/khRsaWGUWRPRmH1yI=; b=LhebEEN3u1hRCFIyVbHk1ufMBKXxVarWm7ctpvx3YlEWPUQoXm4Kvu7NsS/iy1Z/ug 4MIYE9VN03lgb7DWw3PijIpltHFbxDwjoyv9CDl576zwuCCyTqmjJX6AZWiW+8mMc4g3 GKTQ023PwGMYbixYdcAJ9T+tFw0KxWzBpp86kQhhPVlEFI/KgH7bcUafdseB4UQMMj9Q yDNGyXSh8WfQXFduMQcRX6YYGTWfiPxr511BL1ey+iJWS58+eanyn3H/XEtDgEyJTaRj Esb4HfCFwVaf6vIC9QmnX8N7BjWzAMIOVvEG5M0gzRQpOnR3lbVGP244vslfNgVTQpEr i/gg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=dLNpQoSRr9iK3S6Fw6tI1eE1E/khRsaWGUWRPRmH1yI=; b=HNiTBXDwrbKW3hlmPYh1qg7XOklm8I/jbjNR0UzE8z8aXEIqw9eDZhM1v9Iwoovt+H B2LFmY+XZ8WFlJ9r2nwZj3XnZ+L0fgKdEmSTtjr7/jij2MNnSWpw1mR3pxv7LW+/5tyU hmWKiX8L42qboTH3lv5xl9ST0TzvpjX7+MfHh+XoG3PdwNEuplU/SU9peHUXxffMpgpj e2M3/PXWVhgYO8xMCQHqXs7xCC+Zgrf3TrKUBuUp1W3fCtopOGMzt7jGSsnTNxXSg8fI ulQUpOx5FGtFdnT1i+GpeL/IchpTg3omqvRmHkydmrcFYby63D83qiJWacjIR6N2PYsr 5umQ== X-Gm-Message-State: AOAM531l9zKjumN/oaqIe1xjuAF0wfQhlvlUbjt0hPJfd3ges/3Q/hHG LB3S7ckq+cM6gWzjWEE1B6U= X-Google-Smtp-Source: ABdhPJwcQCyO9nlMXYJcQGNDq6WXtwyRPZHNIePeRwwCEz9RkGB8EgeUqHKzbqi9LybMbyKzTpEQhA== X-Received: by 2002:a17:906:268c:: with SMTP id t12mr40737027ejc.91.1606059547406; Sun, 22 Nov 2020 07:39:07 -0800 (PST) Received: from localhost.localdomain (host109-152-100-189.range109-152.btcentralplus.com. [109.152.100.189]) by smtp.gmail.com with ESMTPSA id q19sm3693742ejz.90.2020.11.22.07.39.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:39:07 -0800 (PST) From: Pavel Begunkov To: Jens Axboe , linux-block@vger.kernel.org, Omar Sandoval Cc: linux-kernel@vger.kernel.org Subject: [PATCH v2 2/4] sbitmap: remove swap_lock Date: Sun, 22 Nov 2020 15:35:46 +0000 Message-Id: <488177c02dccda60c5e8af2e53156c42b7f1acc0.1606058975.git.asml.silence@gmail.com> X-Mailer: git-send-email 2.24.0 In-Reply-To: References: MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org map->swap_lock protects map->cleared from concurrent modification, however sbitmap_deferred_clear() is already atomically drains it, so it's guaranteed to not loose bits on concurrent sbitmap_deferred_clear(). A one threaded tag heavy test on top of nullbk showed ~1.5% t-put increase, and 3% -> 1% cycle reduction of sbitmap_get() according to perf. Signed-off-by: Pavel Begunkov --- include/linux/sbitmap.h | 5 ----- lib/sbitmap.c | 14 +++----------- 2 files changed, 3 insertions(+), 16 deletions(-) diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index e40d019c3d9d..74cc6384715e 100644 --- a/include/linux/sbitmap.h +++ b/include/linux/sbitmap.h @@ -32,11 +32,6 @@ struct sbitmap_word { * @cleared: word holding cleared bits */ unsigned long cleared ____cacheline_aligned_in_smp; - - /** - * @swap_lock: Held while swapping word <-> cleared - */ - spinlock_t swap_lock; } ____cacheline_aligned_in_smp; /** diff --git a/lib/sbitmap.c b/lib/sbitmap.c index c1c8a4e69325..4fd877048ba8 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -15,13 +15,9 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) { unsigned long mask, val; - bool ret = false; - unsigned long flags; - spin_lock_irqsave(&map->swap_lock, flags); - - if (!map->cleared) - goto out_unlock; + if (!READ_ONCE(map->cleared)) + return false; /* * First get a stable cleared mask, setting the old mask to 0. @@ -35,10 +31,7 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) val = map->word; } while (cmpxchg(&map->word, val, val & ~mask) != val); - ret = true; -out_unlock: - spin_unlock_irqrestore(&map->swap_lock, flags); - return ret; + return true; } int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, @@ -80,7 +73,6 @@ int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, for (i = 0; i < sb->map_nr; i++) { sb->map[i].depth = min(depth, bits_per_word); depth -= sb->map[i].depth; - spin_lock_init(&sb->map[i].swap_lock); } return 0; } From patchwork Sun Nov 22 15:35:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pavel Begunkov X-Patchwork-Id: 11923917 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1F768C64E7C for ; Sun, 22 Nov 2020 15:39:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E5897212CC for ; Sun, 22 Nov 2020 15:39:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="VosA01iu" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728020AbgKVPjR (ORCPT ); Sun, 22 Nov 2020 10:39:17 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727935AbgKVPjJ (ORCPT ); Sun, 22 Nov 2020 10:39:09 -0500 Received: from mail-ej1-x644.google.com (mail-ej1-x644.google.com [IPv6:2a00:1450:4864:20::644]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6AC84C0613CF; Sun, 22 Nov 2020 07:39:09 -0800 (PST) Received: by mail-ej1-x644.google.com with SMTP id bo9so14038244ejb.13; Sun, 22 Nov 2020 07:39:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=nQLCp8kee4CMboEl3huLY3cDgMLf3XHMfMZ5RHWYbWE=; b=VosA01iuUvY60bnAzgbI5f6Qy3dP17zZoyNNw+NfIb+i/ggx7GQUDXRwSRhj/5ZjZz TKcSA7sc4J39LFSsUtz0L7zG54THPZlbuAe1i9HSY2rFes+/xT7MyX+8ZQDcdIJG3wA2 Pvg39IHXaewLASwtTPiASI6KA4iaC7kAsjRmNeQtP3t0gQV0zpbypssxLZ8xY8K7Sd81 ijcPJp10HYfzLXjXwMd+/kpYzZaRU64i+u5rkEkx03lSTBXAtFBbisFnnE7qwEP/lCuT IBsg8CUw/zPI6ZAFQ+q/9ap6ynPsJlW85PTcHyojBjMwySy+QfB1NAV1ymuBfYim/Vso FzyA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=nQLCp8kee4CMboEl3huLY3cDgMLf3XHMfMZ5RHWYbWE=; b=SuquFvTXhY0/3gekuF1aWwuqgpyGE51SxaqyS8C4Nc2yp6gyL8WpoPBsmsBV1Djri8 8AD3WcNMhfVa1dNjpRTQakr4QbwqpgSp13evB3AgbhScgub+uGO/yXmRXtjoT+aEOSvk apzxcUXArXx7KlFUbcy8jdqlsa+CobTtzyg3tOhxglq3molnAwQ7mu+aPHyMWrdr1Tpl RamDqgr3LRLbT8gbPf4cConUBSqPG2WVpAd6NrE2eKOhFiB0A0UMzBdaesD1RIsFCLna 47je9dygrmwggpiMGArTyYLD7cdV6SArXqP3h5hs+eEVt90cL/i2rl+/u1H6TbV5pJHG vENQ== X-Gm-Message-State: AOAM5309ysgwJCNGnCzdNm7W7VO7BU3VSDegjXTTBYVg31AFGR094jKX 9BrODYq+3ajWSI6ylMQ1t48= X-Google-Smtp-Source: ABdhPJxAWNxAu1sQTAaKYHc2/PQ2GtrkJyUPEOno6RGB2ExQYrdKdXVW3Zm79WIp71ZzAMsjY5a3ZA== X-Received: by 2002:a17:906:c41:: with SMTP id t1mr40733350ejf.19.1606059548209; Sun, 22 Nov 2020 07:39:08 -0800 (PST) Received: from localhost.localdomain (host109-152-100-189.range109-152.btcentralplus.com. [109.152.100.189]) by smtp.gmail.com with ESMTPSA id q19sm3693742ejz.90.2020.11.22.07.39.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:39:07 -0800 (PST) From: Pavel Begunkov To: Jens Axboe , linux-block@vger.kernel.org, Omar Sandoval Cc: linux-kernel@vger.kernel.org Subject: [PATCH v2 3/4] sbitmap: replace CAS with atomic and Date: Sun, 22 Nov 2020 15:35:47 +0000 Message-Id: <6c9b6664bcd12faa9d1a9969a32774a75d1d316f.1606058975.git.asml.silence@gmail.com> X-Mailer: git-send-email 2.24.0 In-Reply-To: References: MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org sbitmap_deferred_clear() does CAS loop to propagate cleared bits, replace it with equivalent atomic bitwise and. That's slightly faster and makes wait-free instead of lock-free as before. The atomic can be relaxed (i.e. barrier-less) because following sbitmap_get*() deal with synchronisation, see comments in sbitmap_queue_clear(). It's ok to cast to atomic_long_t, that's what bitops/lock.h does. Signed-off-by: Pavel Begunkov --- lib/sbitmap.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 4fd877048ba8..c18b518a16ba 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -14,7 +14,7 @@ */ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) { - unsigned long mask, val; + unsigned long mask; if (!READ_ONCE(map->cleared)) return false; @@ -27,10 +27,8 @@ static inline bool sbitmap_deferred_clear(struct sbitmap_word *map) /* * Now clear the masked bits in our free word */ - do { - val = map->word; - } while (cmpxchg(&map->word, val, val & ~mask) != val); - + atomic_long_andnot(mask, (atomic_long_t *)&map->word); + BUILD_BUG_ON(sizeof(atomic_long_t) != sizeof(map->word)); return true; } From patchwork Sun Nov 22 15:35:48 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pavel Begunkov X-Patchwork-Id: 11923915 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-15.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C50FEC64E75 for ; Sun, 22 Nov 2020 15:39:30 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 90C4920781 for ; Sun, 22 Nov 2020 15:39:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="rPLfAxEf" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727317AbgKVPjN (ORCPT ); Sun, 22 Nov 2020 10:39:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33490 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727924AbgKVPjK (ORCPT ); Sun, 22 Nov 2020 10:39:10 -0500 Received: from mail-ej1-x641.google.com (mail-ej1-x641.google.com [IPv6:2a00:1450:4864:20::641]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3897EC0613D3; Sun, 22 Nov 2020 07:39:10 -0800 (PST) Received: by mail-ej1-x641.google.com with SMTP id lv15so13952045ejb.12; Sun, 22 Nov 2020 07:39:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=fl28dO735aCAhko0B6RL7SyZGlL+dtaEdr7rVCrHNgQ=; b=rPLfAxEfQrMaZWxlGBBQ5d77LNndT6OVQI8MQ2T6907z53C9QoVTKOPOFsmL4yC2JW 36wJA7mxNcfbneKzsAqdpifGDGflHREGS2wnjXY4y+noVa17TU09bkb1/5bjIUHCpeDo BztYKy35vV3e+DDGG38CSWfnkDaogGcnAttQ20IRJKGOkG2qFlVSCw3SYBLqd/Esz3uy HOokYMbQI94IaNxVk/4L7hQhSbepslrv1vpfo9BGZfsoappahdARgR6uA7ccqgNZkWkj l5Joo5IHrLaOWvzNLkCvGpA0xM8IJiq2T8OsTs4fJXzxuRrt7Iq33AKxdF1J+cxwtOnW 8aWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=fl28dO735aCAhko0B6RL7SyZGlL+dtaEdr7rVCrHNgQ=; b=XAxFAr8V2/6aHZlPfqer70Fd7490sYPQch986SCZC39jkCoHUwT+rap82CJ5jN0AZS nKUty2HzWNe/cFBFPnUvLpWm5C2EgQeZOqziOmY4kbCNAAh5nxhlCXRrIKr8JqvE8wkA f43Dp9R+wPPSYwZiRIyM5gbdnzlcldF8hshPEcAjP3KvFZTaK1oo8VG1Ai00IaC/hYSP XnepPxU6AS7z6/Hh6CZqUWFe6Ey/o/jYl0yidLxSsFR1q0m1zgO7fvmxKwMqAirZXNZN zcqhDQDXc0o7G/KcXujbviCQOyd+nUYRaV9cQ0MvwdQE67y4BYMH9YlnlwrV5NwDUnAv D+Dw== X-Gm-Message-State: AOAM533W9hzmvNauTpQa+Bey95SEq1gkMcl3f3t9zyeCyIrQo/sTrRyp n9q/fQvx/W5nnQT1YXfM4oL4CR9mPLbPcg== X-Google-Smtp-Source: ABdhPJzReAQ2abZZjO+qZieauY3jPn1AV5BGddQdRsAaDLI8owcy622mYph2MO6f7bQjG6vikUT4oQ== X-Received: by 2002:a17:906:1c87:: with SMTP id g7mr35785480ejh.37.1606059549013; Sun, 22 Nov 2020 07:39:09 -0800 (PST) Received: from localhost.localdomain (host109-152-100-189.range109-152.btcentralplus.com. [109.152.100.189]) by smtp.gmail.com with ESMTPSA id q19sm3693742ejz.90.2020.11.22.07.39.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 22 Nov 2020 07:39:08 -0800 (PST) From: Pavel Begunkov To: Jens Axboe , linux-block@vger.kernel.org, Omar Sandoval Cc: linux-kernel@vger.kernel.org Subject: [PATCH v2 4/4] sbitmap: simplify wrap check Date: Sun, 22 Nov 2020 15:35:48 +0000 Message-Id: <120b9b0870719675c91764822016597bdfa3ee15.1606058975.git.asml.silence@gmail.com> X-Mailer: git-send-email 2.24.0 In-Reply-To: References: MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org __sbitmap_get_word() doesn't warp if it's starting from the beginning (i.e. initial hint is 0). Instead of stashing the original hint just set @wrap accordingly. Signed-off-by: Pavel Begunkov --- lib/sbitmap.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/lib/sbitmap.c b/lib/sbitmap.c index c18b518a16ba..d693d9213ceb 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -97,9 +97,11 @@ EXPORT_SYMBOL_GPL(sbitmap_resize); static int __sbitmap_get_word(unsigned long *word, unsigned long depth, unsigned int hint, bool wrap) { - unsigned int orig_hint = hint; int nr; + /* don't wrap if starting from 0 */ + wrap = wrap && hint; + while (1) { nr = find_next_zero_bit(word, depth, hint); if (unlikely(nr >= depth)) { @@ -108,8 +110,8 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, * offset to 0 in a failure case, so start from 0 to * exhaust the map. */ - if (orig_hint && hint && wrap) { - hint = orig_hint = 0; + if (hint && wrap) { + hint = 0; continue; } return -1;