From patchwork Mon Dec 3 21:56:17 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jens Axboe X-Patchwork-Id: 10710753 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4CBAA16B1 for ; Mon, 3 Dec 2018 21:56:23 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 37CB329EE5 for ; Mon, 3 Dec 2018 21:56:23 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2B7952B1B9; Mon, 3 Dec 2018 21:56:23 +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=-7.9 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,MAILING_LIST_MULTI,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 A802329EE5 for ; Mon, 3 Dec 2018 21:56:22 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725848AbeLCV4V (ORCPT ); Mon, 3 Dec 2018 16:56:21 -0500 Received: from mail-io1-f41.google.com ([209.85.166.41]:34651 "EHLO mail-io1-f41.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725808AbeLCV4V (ORCPT ); Mon, 3 Dec 2018 16:56:21 -0500 Received: by mail-io1-f41.google.com with SMTP id r9so4440906ioa.1 for ; Mon, 03 Dec 2018 13:56:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel-dk.20150623.gappssmtp.com; s=20150623; h=to:cc:from:subject:message-id:date:user-agent:mime-version :content-language:content-transfer-encoding; bh=b80Vd8FkCwLKcUnA02GWgUE14LNoCb7bPqkj5fjAUCI=; b=lxVhJ7/XZSPzdS000kvFHvj5sK29qgAKMZKJ6U8clVPqZXGHw7BJPnjbyfhJNMM484 FEW9UudkRItrzO8T/kGdSSWF4A4Wt4PGiFntR3a/roDPy0zgsyadv+/9c8qYoRLQryY3 xs0i5icJJMTkNuVfyV3Nqd2s+i2pm80ukt7STYz7Xx5+TU7kkWQfGnLPUOwEAHfthISj BY6Syd+jz8SyyH02JeZs0sn4TrDjlDtZctqtyZl+DPEMuC4aN+KM1X4JjVtAzcsVAbaS GsjahmmUfB+4K58NeVtbAYJHqEA0uoumuNdOT6zm3HJen/vzdd/UnDxfz9qOciPtcFom 3yoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language:content-transfer-encoding; bh=b80Vd8FkCwLKcUnA02GWgUE14LNoCb7bPqkj5fjAUCI=; b=lnTiGdyB4/dFZPxvXx3IBIqHFECxXlVzc9fWQwjm8XtZviIAaidnM6zssBeGkshWgW Gfb4vc9PHHJvyMG4mxis5sNxTpEr3ADWOnLZ7rbzJsUzowBd8N8T7db6cY1iGqWBWsG0 wV+SJAb/gFxUob9Ge41ntUD1GsaHvdWm/wPHxAvg+bIFlcv/ivBi3wZG+sODFk0Kkz2H kCjbUD7GiY7zr8xozh6A/ZguYEENqpcPdW1eCxUa+mtQj3I7YI+IXFcmoVbQwlAyo2mX rBNQh/eHwFWzg1HIdFB2n33j4/OHieMyKpoT+D2J1pzcRVzVKU809YwDR/A5zsejHcfq zogw== X-Gm-Message-State: AA+aEWajYcoWOn4YUFIOJ6hFPNuWQzVBAX3KiI5o6IHEwaDlafoCs9fY rAWsWsAfMinALEdjgIayYdkGZvWk2tw= X-Google-Smtp-Source: AFSGD/WlFskyTKnoXX3hlWJcA8ddAwt0yxsNHnFxchsARhJrkRSB7XSwkLG8UFEZOeoY55FB5zjyPA== X-Received: by 2002:a6b:6604:: with SMTP id a4mr15226257ioc.10.1543874180776; Mon, 03 Dec 2018 13:56:20 -0800 (PST) Received: from ?IPv6:2620:10d:c081:1131::106f? ([2620:10d:c090:180::1:94b1]) by smtp.gmail.com with ESMTPSA id z23sm6350902iob.19.2018.12.03.13.56.18 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 03 Dec 2018 13:56:19 -0800 (PST) To: "linux-block@vger.kernel.org" Cc: Omar Sandoval From: Jens Axboe Subject: sbitmap: check cleared bits when iterating busy bits Message-ID: <8bde3953-56d8-32cb-2c34-582d632f4a3f@kernel.dk> Date: Mon, 3 Dec 2018 14:56:17 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 Content-Language: en-US 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 When we are iterating the set bits in a word, we also need to factor in the cleared bits. Don't call fn() unless the bit is also not set in the cleared word. Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits") Signed-off-by: Jens Axboe diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index 92806a2dbab7..9f374fbcdba6 100644 --- a/include/linux/sbitmap.h +++ b/include/linux/sbitmap.h @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, nr = find_next_bit(&word->word, depth, nr); if (nr >= depth) break; + /* if set in cleared, it's actually free */ + if (test_bit(nr, &word->cleared)) { + nr++; + continue; + } if (!fn(sb, (index << sb->shift) + nr, data)) return;