From patchwork Sun Mar 3 07:48:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: William Breathitt Gray X-Patchwork-Id: 10836983 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 04D111575 for ; Sun, 3 Mar 2019 07:48:01 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E165D2A52D for ; Sun, 3 Mar 2019 07:48:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D055E2A52F; Sun, 3 Mar 2019 07:48:00 +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=-5.2 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,DKIM_VALID,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 406CC2A52D for ; Sun, 3 Mar 2019 07:48:00 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-Id:Date:Subject:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=oq/2+P7lEOa9ZL7OvXd1p1OPe3Ukr7b4yRP6j5yHvsc=; b=MzESkx9azEh3qn jvzh2ZRHmtHfYWz+eSLnACNXR05JiVFmcgAipM7HzGvQy7AqKH4EePTk7NGl6owCO4fzUuzKNlO87 6gIDeWOkPfon5VY4yDk/pn5vEMmzAnSPiOlHvAzI88bnDj/cnN4/ZNCOSh3cQsFSCCYNLn8jXnMgM XJddPi/l8eCzvlsI4sRB3ATXzZrDdLIS9Xj8sGM/S9QrUW4F14P0gID2/HHlHR3nrcBRzS4H3efin bHBoR8e58+/e7n3DV1vV4Mx3V0qPNJ1gES7Sg62W5578tdVaQRBk6VnhNWYqOs1sCwKQyxaAnU+/6 k0lDQw7uhLiChqLC6sXQ==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.90_1 #2 (Red Hat Linux)) id 1h0Lqi-0008C4-7i; Sun, 03 Mar 2019 07:47:52 +0000 Received: from mail-pf1-x443.google.com ([2607:f8b0:4864:20::443]) by bombadil.infradead.org with esmtps (Exim 4.90_1 #2 (Red Hat Linux)) id 1h0Lqf-0008Bh-EX for linux-arm-kernel@lists.infradead.org; Sun, 03 Mar 2019 07:47:51 +0000 Received: by mail-pf1-x443.google.com with SMTP id i19so974800pfd.0 for ; Sat, 02 Mar 2019 23:47:49 -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=5ShWnQ4n5foUkzD6q0EUYaaxbLy/TY+i7Ft3bXpmfRg=; b=K3s/GXb+qCLU0tBYbjBhACOHRqxVXy2BWt5nyY+EvGvmDBAC7MK9VBL/i9RznuxDjb 1RWbpzO1U2Yn7QVl+uUxTwp2Lh3HJZCuy1YsIQ+SnBUBW+OSxZ47/stUiOUO1X24WApq kUpZmhyburujHHRvLdYqnB6KXa6+PJH1SF93j9FUT8Zts5rQf2RcQ46nZscCTFjljzEu M3CoCh/u7zsq9wqWYQF4W0llTsv/YS10EYOrCfCDlpCE91P51dqtXii2ghQHWOckIPe1 FyuyzDMT0DXMpv8gtxsVodAw8oPkNg/2X1sQxVj1ODG1pV0zkIyKX392ccLS28bpeedJ Xp8A== 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=5ShWnQ4n5foUkzD6q0EUYaaxbLy/TY+i7Ft3bXpmfRg=; b=oRwGtPqVDZODmBPu5igI0TC73iBCffj+9qp2Hv8hsw/M7mDYjHfZppCC8y/DooTh0o Z2vtTPJ25GPF38vPBHqn122WwmrAT2yypfqjOjM8YtszJ6asxCGtkESVa141Op3/a0ck 0ePqrzUrfYSi8xRu0odwEKlH7IRDSGHvQsaxy1/6lcRJ7ZMhmmt7RROnjfrSU4aqccqJ khZ9ufcooBcwi4y3L3R1RALjNsJxziPAIk9hsvslippI8RNAL6g8pF1lT0ZyMFzQPLPC X/FwpFszn8BhpBNF7oP1fXXHGP7EqZX1IweoOp3Tp29o8UrDahaMFnTwUq8xgZF1E0OT nXrA== X-Gm-Message-State: APjAAAX/UFoi/bH/yxN9jHvTBbKRQFCwpln7+DnB/rb10FDNrClF2FDh DP63nGW6nBhXFTSQQ6wBZtg= X-Google-Smtp-Source: APXvYqwSy53757lsDFOC+awhk1BMnvhr27fsGj+61YyFheroHA9PEVmgQnFH9Af4uXRvS4HNYIogqQ== X-Received: by 2002:a63:8042:: with SMTP id j63mr12561873pgd.36.1551599269023; Sat, 02 Mar 2019 23:47:49 -0800 (PST) Received: from localhost.localdomain ([2001:268:c0a5:3b5c:c70:4af9:86e2:2]) by smtp.gmail.com with ESMTPSA id s1sm3443392pgv.30.2019.03.02.23.47.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 02 Mar 2019 23:47:48 -0800 (PST) From: William Breathitt Gray To: linus.walleij@linaro.org Subject: [PATCH v9 1/9] bitops: Introduce the for_each_set_clump8 macro Date: Sun, 3 Mar 2019 16:48:36 +0900 Message-Id: <12b3a364ac7fc32194fa6f55911dd800aca92a56.1551598603.git.vilhelm.gray@gmail.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: References: MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20190302_234749_483190_E75E2443 X-CRM114-Status: GOOD ( 15.60 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-arch@vger.kernel.org, Arnd Bergmann , yamada.masahiro@socionext.com, linux@rasmusvillemoes.dk, linux-kernel@vger.kernel.org, William Breathitt Gray , linux-gpio@vger.kernel.org, Andy Shevchenko , bgolaszewski@baylibre.com, akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com, linux-arm-kernel@lists.infradead.org Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Virus-Scanned: ClamAV using ClamSMTP This macro iterates for each 8-bit group of bits (clump) with set bits, within a bitmap memory region. For each iteration, "start" is set to the bit offset of the found clump, while the respective clump value is stored to the location pointed by "clump". Additionally, the bitmap_get_value8 and bitmap_set_value8 functions are introduced to respectively get and set an 8-bit value in a bitmap memory region. Suggested-by: Andy Shevchenko Suggested-by: Rasmus Villemoes Cc: Arnd Bergmann Cc: Andrew Morton Reviewed-by: Andy Shevchenko Reviewed-by: Linus Walleij Signed-off-by: William Breathitt Gray --- include/asm-generic/bitops/find.h | 14 ++++++ include/linux/bitops.h | 5 ++ lib/find_bit.c | 81 +++++++++++++++++++++++++++++++ 3 files changed, 100 insertions(+) diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h index 8a1ee10014de..9a76adff59c6 100644 --- a/include/asm-generic/bitops/find.h +++ b/include/asm-generic/bitops/find.h @@ -80,4 +80,18 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr, #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +unsigned long bitmap_get_value8(const unsigned long *const bitmap, + const unsigned int size, + const unsigned int start); + +void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size, + const unsigned long value, const unsigned int start); + +unsigned int find_next_clump8(unsigned long *const clump, + const unsigned long *const addr, + unsigned int offset, const unsigned int size); + +#define find_first_clump8(clump, bits, size) \ + find_next_clump8((clump), (bits), 0, (size)) + #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 705f7c442691..61c10f20079e 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -40,6 +40,11 @@ extern unsigned long __sw_hweight64(__u64 w); (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) +#define for_each_set_clump8(start, clump, bits, size) \ + for ((start) = find_first_clump8(&(clump), (bits), (size)); \ + (start) < (size); \ + (start) = find_next_clump8(&(clump), (bits), (start) + 8, (size))) + static inline int get_bitmask_order(unsigned int count) { int order; diff --git a/lib/find_bit.c b/lib/find_bit.c index ee3df93ba69a..c2af1f013ea2 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -218,3 +218,84 @@ EXPORT_SYMBOL(find_next_bit_le); #endif #endif /* __BIG_ENDIAN */ + +/** + * bitmap_get_value8 - get an 8-bit value within a memory region + * @bitmap: address to the bitmap memory region + * @size: bitmap size in number of bits + * @start: bit offset of the 8-bit value + * + * Returns the 8-bit value located at the @start bit offset within the @bitmap + * memory region. + */ +unsigned long bitmap_get_value8(const unsigned long *const bitmap, + const unsigned int size, + const unsigned int start) +{ + const size_t index = BIT_WORD(start); + const unsigned int offset = start % BITS_PER_LONG; + const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ? + BITS_PER_LONG - offset : 8; + const unsigned long low = bitmap[index] >> offset; + const unsigned long high = (low_width < 8 && start + 8 <= size) ? + bitmap[index + 1] << low_width : 0; + + return (low | high) & 0xFF; +} +EXPORT_SYMBOL(bitmap_get_value8); + +/** + * bitmap_set_value8 - set an 8-bit value within a memory region + * @bitmap: address to the bitmap memory region + * @size: bitmap size in number of bits + * @value: the 8-bit value; values wider than 8 bits may clobber bitmap + * @start: bit offset of the 8-bit value + */ +void bitmap_set_value8(unsigned long *const bitmap, const unsigned int size, + const unsigned long value, const unsigned int start) +{ + const size_t index = BIT_WORD(start); + const unsigned int offset = start % BITS_PER_LONG; + const unsigned int low_width = (offset + 8 > BITS_PER_LONG) ? + BITS_PER_LONG - offset : 8; + const unsigned long low_mask = GENMASK(offset + low_width - 1, offset); + const unsigned int high_width = 8 - low_width; + const unsigned long high_mask = GENMASK(high_width - 1, 0); + + /* set lower portion */ + bitmap[index] &= ~low_mask; + bitmap[index] |= value << offset; + + /* set higher portion if space available in bitmap */ + if (high_width && start + 8 <= size) { + bitmap[index + 1] &= ~high_mask; + bitmap[index + 1] |= value >> low_width; + } +} +EXPORT_SYMBOL(bitmap_set_value8); + +/** + * find_next_clump8 - find next 8-bit clump with set bits in a memory region + * @clump: location to store copy of found clump + * @addr: address to base the search on + * @offset: bit offset at which to start searching + * @size: bitmap size in number of bits + * + * Returns the bit offset for the next set clump; the found clump value is + * copied to the location pointed by @clump. If no bits are set, returns @size. + */ +unsigned int find_next_clump8(unsigned long *const clump, + const unsigned long *const addr, + unsigned int offset, const unsigned int size) +{ + for (; offset < size; offset += 8) { + *clump = bitmap_get_value8(addr, size, offset); + if (!*clump) + continue; + + return offset; + } + + return size; +} +EXPORT_SYMBOL(find_next_clump8);