From patchwork Thu Sep 14 14:59:43 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 9953305 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 7CD8C60230 for ; Thu, 14 Sep 2017 14:59:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6415A288BB for ; Thu, 14 Sep 2017 14:59:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 58D7C29138; Thu, 14 Sep 2017 14:59:48 +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.9 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_HI 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 98FAC288BB for ; Thu, 14 Sep 2017 14:59:47 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751590AbdINO7r (ORCPT ); Thu, 14 Sep 2017 10:59:47 -0400 Received: from mail-pg0-f42.google.com ([74.125.83.42]:52416 "EHLO mail-pg0-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751587AbdINO7q (ORCPT ); Thu, 14 Sep 2017 10:59:46 -0400 Received: by mail-pg0-f42.google.com with SMTP id i195so443473pgd.9 for ; Thu, 14 Sep 2017 07:59:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=osandov-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=WXm6rzbK+uZcrU2gnfHmDgSGITbsoVmnSc3g9ZMElAQ=; b=se+cWHYXvaPhf9cuEXLgwQ15LDsCjx2aVXPLezLMDFjlROP4sv3zlszzp52Fwt6kdg DVJb3ZN6g6KRc+lyiRxpzAisBBX56y9A+VMcj+S7b1M7m/rXYFlsXckBYOhpAJvUw3RB tgVyYhOKhNVgQI9OW0ANJeXHf4ubi0MtQoVr3sHbQ48mu8yEFmKu9nnX0em5pDd9/Iha X86ghyAbfVrY8KQpQYxLB/rowvN4nD6ojUF+mDmYfkACWagx+MhecL3RLuTp0ZM9ircO 6bu7obhksyhF8NQ/8snSvkFUTR0llEy3cwy7H4FQOc3g0s6tKu36i/lrAyircXVHlSvK s8LA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=WXm6rzbK+uZcrU2gnfHmDgSGITbsoVmnSc3g9ZMElAQ=; b=JeLqVbL7JkajIcc4J2f3YqAijDnlUrZUV+4XXEmmcpgave80+uy2QtWsHnMQ8lK/re prCuLQ+a5MtlJqUx+DBqh5V1y/cJm+Z6cv/dTfGZoHjev0rgh8RLpn0mafpn/UmUuKrZ heMpv9htEajXaTwDe9WoeXqUOmD7cNAaVmO0jtpHrUCXijnE/QgG4kBheRqqWpQz79CI 7mj9pJ6wOcuw20iR7LKiej07s9V3w0/lqoV81K+GnaWQRxzMKzc+295/+LnArsvmCq9I PjWHhyDdT+CYN/nmj6yUWSLwndHP5Ofzre/dgGp1JbZWpz+C0jNX6+N73CFspGZD/PzI JMAQ== X-Gm-Message-State: AHPjjUgbkSgx+TJSClsrLkqV8LJLuHbWKyty6mjKCdvnHvAEg6uWs9Lz tbZLF4eDFQvbQag3 X-Google-Smtp-Source: ADKCNb642BQNonzX5IGeMxQdPGhNbNVItf7pTlEd7yesrt0lHnmfRvsjAxIgv0Legk1u+cAtzoAa8Q== X-Received: by 10.99.191.6 with SMTP id v6mr22146724pgf.284.1505401185498; Thu, 14 Sep 2017 07:59:45 -0700 (PDT) Received: from vader ([2620:10d:c090:180::1:2bfd]) by smtp.gmail.com with ESMTPSA id c62sm13937355pfl.84.2017.09.14.07.59.43 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Thu, 14 Sep 2017 07:59:44 -0700 (PDT) Date: Thu, 14 Sep 2017 07:59:43 -0700 From: Omar Sandoval To: Ming Lei Cc: Jens Axboe , linux-block@vger.kernel.org, Christoph Hellwig , Bart Van Assche , Laurence Oberman , Paolo Valente , Mel Gorman , Omar Sandoval Subject: Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set() Message-ID: <20170914145943.GA10238@vader> References: <20170902151729.6162-1-ming.lei@redhat.com> <20170902151729.6162-3-ming.lei@redhat.com> <20170908204341.GA13673@vader.DHCP.thefacebook.com> <20170909093812.GE26081@ming.t460p> <20170910172027.GA2579@vader> <20170911040827.GB27079@ming.t460p> <20170913183720.GB30473@vader> <20170914015647.GA2258@ming.t460p> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20170914015647.GA2258@ming.t460p> User-Agent: Mutt/1.9.0 (2017-09-02) 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 On Thu, Sep 14, 2017 at 09:56:56AM +0800, Ming Lei wrote: > On Wed, Sep 13, 2017 at 11:37:20AM -0700, Omar Sandoval wrote: > > On Mon, Sep 11, 2017 at 12:08:29PM +0800, Ming Lei wrote: > > > On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote: > > > > [snip] > > > > > > What I mean is that you keep the same initialization above, but instead of > > > > depth += nr > > > > you do > > > > depth = min_t(unsigned int, word->depth, sb->depth - scanned); > > > > because like I said, the reasoning about why `+= nr` is okay in the > > > > `sb->depth - scanned` case is subtle. > > > > > > > > And maybe even replace the > > > > scanned += depth; > > > > with > > > > scanned += min_t(unsigned int, word->depth - nr, > > > > sb->depth - scanned); > > > > I.e., don't reuse the depth local variable for two different things. I'm > > > > nitpicking here but this code is tricky enough as it is. > > > > > > It wasn't reused in old version, just for saving one local variable, and > > > one extra min_t(). > > > > > > Yeah, I admit it isn't clean enough. > > > > > > > > > > > For completeness, I mean this exactly: > > > > > > > > while (1) { > > > > struct sbitmap_word *word = &sb->map[index]; > > > > unsigned int depth; > > > > > > > > scanned += min_t(unsigned int, word->depth - nr, > > > > sb->depth - scanned); > > > > if (!word->word) > > > > goto next; > > > > > > > > depth = min_t(unsigned int, word->depth, sb->depth - scanned); > > > > > > two min_t and a little code duplication. > > > > They're similar but they represent different things, so I think trying > > to deduplicate this code just makes it more confusing. If performance is > > your concern, I'd be really surprised if there's a noticable difference. > > No only one extra min_t(), also it isn't easy to read the code, since > only in the first scan that 'depth' isn't same with 'depth', that is > why I set the 1st 'scan' outside of the loop, then we can update 'scan' > with 'depth' in every loop. People will be easy to follow the > meaning. > > > > > As a side note, I also realized that this code doesn't handle the > > sb->depth == 0 case. We should change the while (1) to > > while (scanned < sb->depth) and remove the > > if (scanned >= sb->depth) break; > > In the attached patch, I remember that the zero depth case is > addressed by: > > if (start >= sb->depth) > return; > > which is required since 'start' parameter is introduced in > this patch. I think the better way to handle this is if (start >= sb->depth) start = 0; Since the sbitmap may have gotten resized since the last time the user called this and cached their start value. > > > > > > off = index << sb->shift; > > > > while (1) { > > > > nr = find_next_bit(&word->word, depth, nr); > > > > if (nr >= depth) > > > > break; > > > > > > > > if (!fn(sb, off + nr, data)) > > > > return; > > > > > > > > nr++; > > > > } > > > > next: > > > > if (scanned >= sb->depth) > > > > break; > > > > nr = 0; > > > > if (++index >= sb->map_nr) > > > > index = 0; > > > > } > > > > > > The following patch switches to do{}while and handles the > > > 1st scan outside of the loop, then it should be clean > > > enough(no two min_t()), so how about this one? > > > > I find this one subtler and harder to follow. The less it looks like the > > typical loop pattern, the longer someone reading the code has to reason > > about it. > > Looks using 'depth' to update 'scanned' is easier to follow, than > two min_t(), since it will make people easy to understand the relation > between the two, then understand the whole code. Honestly I prefer your original patch with a comment on depth += nr. I'd be happy with the following incremental patch on top of your original v4 patch. diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index 2329b9e1a0e2..8d747048ae4f 100644 --- a/include/linux/sbitmap.h +++ b/include/linux/sbitmap.h @@ -218,7 +218,7 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); /** * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. - * @off: Where to start the iteration + * @off: Where to start the iteration. * @sb: Bitmap to iterate over. * @fn: Callback. Should return true to continue or false to break early. * @data: Pointer to pass to callback. @@ -230,11 +230,16 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, unsigned int off, sb_for_each_fn fn, void *data) { - unsigned int index = SB_NR_TO_INDEX(sb, off); - unsigned int nr = SB_NR_TO_BIT(sb, off); + unsigned int index; + unsigned int nr; unsigned int scanned = 0; - while (1) { + if (off >= sb->depth) + off = 0; + index = SB_NR_TO_INDEX(sb, off); + nr = SB_NR_TO_BIT(sb, off); + + while (scanned < sb->depth) { struct sbitmap_word *word = &sb->map[index]; unsigned int depth = min_t(unsigned int, word->depth - nr, sb->depth - scanned); @@ -243,6 +248,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, if (!word->word) goto next; + /* + * On the first iteration of the outer loop, we need to add the + * bit offset back to the size of the word for find_next_bit(). + * On all other iterations, nr is zero, so this is a noop. + */ depth += nr; off = index << sb->shift; while (1) { @@ -254,9 +264,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, nr++; } - next: - if (scanned >= sb->depth) - break; +next: nr = 0; if (++index >= sb->map_nr) index = 0; @@ -268,9 +276,6 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, * @sb: Bitmap to iterate over. * @fn: Callback. Should return true to continue or false to break early. * @data: Pointer to pass to callback. - * - * This is inline even though it's non-trivial so that the function calls to the - * callback will hopefully get optimized away. */ static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn, void *data)