From patchwork Sat Sep 17 08:28:25 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 9337035 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 5863C60839 for ; Sat, 17 Sep 2016 08:29:35 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4CCE9296FE for ; Sat, 17 Sep 2016 08:29:35 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 41B4B29712; Sat, 17 Sep 2016 08:29:35 +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 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 9EBEB296FE for ; Sat, 17 Sep 2016 08:29:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S935048AbcIQI3d (ORCPT ); Sat, 17 Sep 2016 04:29:33 -0400 Received: from mail-pf0-f175.google.com ([209.85.192.175]:36401 "EHLO mail-pf0-f175.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757538AbcIQI2n (ORCPT ); Sat, 17 Sep 2016 04:28:43 -0400 Received: by mail-pf0-f175.google.com with SMTP id q2so14511871pfj.3 for ; Sat, 17 Sep 2016 01:28:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=osandov-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references :in-reply-to:references; bh=+80W7yJYx/PByIdYZmu9fMPxyP51vP6tcukCG5BwRcA=; b=YYiigyHN+Pb4lZER0gIRHZFlL4jorWkafEeHWCPsyiE5S4hEPYPdw7qzvQpkybwuml fZRiE9wLGOigWpqRAG21a+TwLyAWBCyy/Axip+SJSIs/1PaLclYO5dMFQ8q4ejgP48kj D9pIXh9b0cFXoNhefxeRZXrN598EvcRBpCjd7hWpHSDej/4zNKl7GF0sM2ms3haAOeqW FPWEHe+FOz/Sj3j3iYqP2asFQHB0JfdoqqMQ9rf7Y8kQT0oWxsT8YFUnIA+NsN5TxQC6 5Fxns8y19Qsvf+VUWR7rJzmw2khygDzDiUln4hAU79YZjDiCZmZbWCWqz38yn6+gHmm1 BBeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:in-reply-to:references; bh=+80W7yJYx/PByIdYZmu9fMPxyP51vP6tcukCG5BwRcA=; b=l1YbI2p1DOZqH+xCVrTYE+4hj6SkvBNcZ0ttkUOKgexEv4msIGiFhJ7JsTJPYiW/VA H9tsTAoGTns3if+Q9z5QNghpeVBYjiuta1E6NvgoPRyAAQt+CMFWmVkNPh0+cFciN7S7 oiqUlh63MaqfZlpDIwstnkNdrw0a9jSyO+YTpCCXUNSwvQAcy2lPZd8HcGYz4RZa2xBG 1f/9vqamX7qTlcKjW4aO1l0JoP0YZZ+D9nWW6rq+g5O2TtWE9sC9V0H+h8LTHDErQpf7 I4NZ1+JoW8/WZCZZS5HXe3AGcJhLw5PP+zreEBg9y2aP5kxA5Es+6Dtjb1D9FwthdRXP otyw== X-Gm-Message-State: AE9vXwP9oYEenB1P/w9NIO5QSFr+nafNaXgo0Z5xV81AWBdXcsrZz/x81U1hPIV+QujAFjK0 X-Received: by 10.98.220.93 with SMTP id t90mr29601696pfg.30.1474100921842; Sat, 17 Sep 2016 01:28:41 -0700 (PDT) Received: from vader.thefacebook.com ([2620:10d:c090:180::1:1e34]) by smtp.gmail.com with ESMTPSA id ci9sm17173264pad.34.2016.09.17.01.28.41 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 17 Sep 2016 01:28:41 -0700 (PDT) From: Omar Sandoval To: Jens Axboe , linux-block@vger.kernel.org Cc: linux-kernel@vger.kernel.org, kernel-team@fb.com, Alexei Starovoitov Subject: [PATCH v4 5/6] sbitmap: randomize initial alloc_hint values Date: Sat, 17 Sep 2016 01:28:25 -0700 Message-Id: <1dd4b50b976acc1c250d495822c32f7617b29d07.1474100040.git.osandov@fb.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: References: In-Reply-To: References: Sender: linux-block-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-block@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Omar Sandoval In order to get good cache behavior from a sbitmap, we want each CPU to stick to its own cacheline(s) as much as possible. This might happen naturally as the bitmap gets filled up and the alloc_hint values spread out, but we really want this behavior from the start. blk-mq apparently intended to do this, but the code to do this was never wired up. Get rid of the dead code and make it part of the sbitmap library. Signed-off-by: Omar Sandoval --- block/blk-mq-tag.c | 8 -------- block/blk-mq-tag.h | 1 - lib/sbitmap.c | 6 ++++++ 3 files changed, 6 insertions(+), 9 deletions(-) diff --git a/block/blk-mq-tag.c b/block/blk-mq-tag.c index e1c2bed..cef618f 100644 --- a/block/blk-mq-tag.c +++ b/block/blk-mq-tag.c @@ -7,7 +7,6 @@ */ #include #include -#include #include #include "blk.h" @@ -419,13 +418,6 @@ void blk_mq_free_tags(struct blk_mq_tags *tags) kfree(tags); } -void blk_mq_tag_init_last_tag(struct blk_mq_tags *tags, unsigned int *tag) -{ - unsigned int depth = tags->nr_tags - tags->nr_reserved_tags; - - *tag = prandom_u32() % depth; -} - int blk_mq_tag_update_depth(struct blk_mq_tags *tags, unsigned int tdepth) { tdepth -= tags->nr_reserved_tags; diff --git a/block/blk-mq-tag.h b/block/blk-mq-tag.h index f90b850..09f4cc0 100644 --- a/block/blk-mq-tag.h +++ b/block/blk-mq-tag.h @@ -30,7 +30,6 @@ extern void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx, unsigned int tag); extern bool blk_mq_has_free_tags(struct blk_mq_tags *tags); extern ssize_t blk_mq_tag_sysfs_show(struct blk_mq_tags *tags, char *page); -extern void blk_mq_tag_init_last_tag(struct blk_mq_tags *tags, unsigned int *last_tag); extern int blk_mq_tag_update_depth(struct blk_mq_tags *tags, unsigned int depth); extern void blk_mq_tag_wakeup_all(struct blk_mq_tags *tags, bool); void blk_mq_queue_tag_busy_iter(struct request_queue *q, busy_iter_fn *fn, diff --git a/lib/sbitmap.c b/lib/sbitmap.c index be55f74..928b82a 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -15,6 +15,7 @@ * along with this program. If not, see . */ +#include #include int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, @@ -211,6 +212,11 @@ int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, return -ENOMEM; } + if (depth && !round_robin) { + for_each_possible_cpu(i) + *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth; + } + sbq->wake_batch = sbq_calc_wake_batch(depth); atomic_set(&sbq->wake_index, 0);