From mboxrd@z Thu Jan 1 00:00:00 1970 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=-3.8 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS autolearn=no 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 2C7A3C43603 for ; Thu, 5 Dec 2019 00:51:01 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id CCB58224F8 for ; Thu, 5 Dec 2019 00:51:00 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="cpJkqXdo" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org CCB58224F8 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=linux-foundation.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 26EA36B0D71; Wed, 4 Dec 2019 19:51:00 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 15A726B0D95; Wed, 4 Dec 2019 19:51:00 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 07B7E6B0D97; Wed, 4 Dec 2019 19:51:00 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0051.hostedemail.com [216.40.44.51]) by kanga.kvack.org (Postfix) with ESMTP id E2C126B0D71 for ; Wed, 4 Dec 2019 19:50:59 -0500 (EST) Received: from smtpin15.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay02.hostedemail.com (Postfix) with SMTP id B2A6752CE for ; Thu, 5 Dec 2019 00:50:59 +0000 (UTC) X-FDA: 76229258238.15.boot44_8a37a7a7c74d X-HE-Tag: boot44_8a37a7a7c74d X-Filterd-Recvd-Size: 10775 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by imf38.hostedemail.com (Postfix) with ESMTP for ; Thu, 5 Dec 2019 00:50:59 +0000 (UTC) Received: from localhost.localdomain (c-73-231-172-41.hsd1.ca.comcast.net [73.231.172.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id ECA6724249; Thu, 5 Dec 2019 00:50:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1575507058; bh=Mu9WVAL0GqMi49KhKEWxWptMH0d8pT/Z8TfY4PzIniE=; h=Date:From:To:Subject:In-Reply-To:From; b=cpJkqXdoqpdPIFRVaEO3lAWoU1jkIjDqRNkQyL+/zG8MltQT2KTn5aE6NqHMoKiIr SIZJL/meD9R2HiCLadjVI4B67j9WC6iZkWuXkiAe90KY/6t6FfFKzOb4TqZ7suEqtC LtL4ag/pBKdg4yrQX5gXXdtm9rsVX083Qz/cr3Xo= Date: Wed, 04 Dec 2019 16:50:57 -0800 From: Andrew Morton To: akpm@linux-foundation.org, andriy.shevchenko@linux.intel.com, andy.shevchenko@gmail.com, arnd@arndb.de, bgolaszewski@baylibre.com, geert+renesas@glider.be, geert@linux-m68k.org, gustavo@embeddedor.com, linus.walleij@linaro.org, linux-mm@kvack.org, linux@rasmusvillemoes.dk, lukas@wunner.de, m.duckeck@kunbus.de, mm-commits@vger.kernel.org, morten.tiljeset@prevas.dk, preid@electromag.com.au, sean.nyekjaer@prevas.dk, torvalds@linux-foundation.org, vilhelm.gray@gmail.com, yamada.masahiro@socionext.com Subject: [patch 24/86] bitops: introduce the for_each_set_clump8 macro Message-ID: <20191205005057.gUdhyBVHB%akpm@linux-foundation.org> In-Reply-To: <20191204164858.fe4ed8886e34ad9f3b34ea00@linux-foundation.org> User-Agent: s-nail v14.8.16 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: From: William Breathitt Gray Subject: bitops: introduce the for_each_set_clump8 macro Pach series "Introduce the for_each_set_clump8 macro", v18. While adding GPIO get_multiple/set_multiple callback support for various drivers, I noticed a pattern of looping manifesting that would be useful standardized as a macro. This patchset introduces the for_each_set_clump8 macro and utilizes it in several GPIO drivers. The for_each_set_clump macro8 facilitates a for-loop syntax that iterates over a memory region entire groups of set bits at a time. For example, suppose you would like to iterate over a 32-bit integer 8 bits at a time, skipping over 8-bit groups with no set bit, where XXXXXXXX represents the current 8-bit group: Example: 10111110 00000000 11111111 00110011 First loop: 10111110 00000000 11111111 XXXXXXXX Second loop: 10111110 00000000 XXXXXXXX 00110011 Third loop: XXXXXXXX 00000000 11111111 00110011 Each iteration of the loop returns the next 8-bit group that has at least one set bit. The for_each_set_clump8 macro has four parameters: * start: set to the bit offset of the current clump * clump: set to the current clump value * bits: bitmap to search within * size: bitmap size in number of bits In this version of the patchset, the for_each_set_clump macro has been reimplemented and simplified based on the suggestions provided by Rasmus Villemoes and Andy Shevchenko in the version 4 submission. In particular, the function of the for_each_set_clump macro has been restricted to handle only 8-bit clumps; the drivers that use the for_each_set_clump macro only handle 8-bit ports so a generic for_each_set_clump implementation is not necessary. Thus, a solution for large clumps (i.e. those larger than the width of a bitmap word) can be postponed until a driver appears that actually requires such a generic for_each_set_clump implementation. For what it's worth, a semi-generic for_each_set_clump (i.e. for clumps smaller than the width of a bitmap word) can be implemented by simply replacing the hardcoded '8' and '0xFF' instances with respective variables. I have not yet had a need for such an implementation, and since it falls short of a true generic for_each_set_clump function, I have decided to forgo such an implementation for now. In addition, the bitmap_get_value8 and bitmap_set_value8 functions are introduced to get and set 8-bit values respectively. Their use is based on the behavior suggested in the patchset version 4 review. This patch (of 14): 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. [gustavo@embeddedor.com: fix potential sign-extension overflow] Link: http://lkml.kernel.org/r/20191015184657.GA26541@embeddedor [akpm@linux-foundation.org: s/ULL/UL/, per Joe] [vilhelm.gray@gmail.com: add for_each_set_clump8 documentation] Link: http://lkml.kernel.org/r/20191016161825.301082-1-vilhelm.gray@gmail.com Link: http://lkml.kernel.org/r/893c3b4f03266c9496137cc98ac2b1bd27f92c73.1570641097.git.vilhelm.gray@gmail.com Signed-off-by: William Breathitt Gray Signed-off-by: Gustavo A. R. Silva Suggested-by: Andy Shevchenko Suggested-by: Rasmus Villemoes Suggested-by: Lukas Wunner Tested-by: Andy Shevchenko Cc: Arnd Bergmann Cc: Linus Walleij Cc: Bartosz Golaszewski Cc: Masahiro Yamada Cc: Geert Uytterhoeven Cc: Phil Reid Cc: Geert Uytterhoeven Cc: Mathias Duckeck Cc: Morten Hein Tiljeset Cc: Sean Nyekjaer Signed-off-by: Andrew Morton --- include/asm-generic/bitops/find.h | 17 +++++++++++++ include/linux/bitmap.h | 35 ++++++++++++++++++++++++++++ include/linux/bitops.h | 12 +++++++++ lib/find_bit.c | 14 +++++++++++ 4 files changed, 78 insertions(+) --- a/include/asm-generic/bitops/find.h~bitops-introduce-the-for_each_set_clump8-macro +++ a/include/asm-generic/bitops/find.h @@ -80,4 +80,21 @@ extern unsigned long find_first_zero_bit #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +/** + * 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 + * @size: bitmap size in number of bits + * @offset: bit offset at which to start searching + * + * 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. + */ +extern unsigned long find_next_clump8(unsigned long *clump, + const unsigned long *addr, + unsigned long size, unsigned long offset); + +#define find_first_clump8(clump, bits, size) \ + find_next_clump8((clump), (bits), (size), 0) + #endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ --- a/include/linux/bitmap.h~bitops-introduce-the-for_each_set_clump8-macro +++ a/include/linux/bitmap.h @@ -66,6 +66,8 @@ * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region * bitmap_from_arr32(dst, buf, nbits) Copy nbits from u32[] buf to dst * bitmap_to_arr32(buf, src, nbits) Copy nbits from buf to u32[] dst + * bitmap_get_value8(map, start) Get 8bit value from map at start + * bitmap_set_value8(map, value, start) Set 8bit value to map at start * * Note, bitmap_zero() and bitmap_fill() operate over the region of * unsigned longs, that is, bits behind bitmap till the unsigned long @@ -489,6 +491,39 @@ static inline void bitmap_from_u64(unsig dst[1] = mask >> 32; } +/** + * bitmap_get_value8 - get an 8-bit value within a memory region + * @map: address to the bitmap memory region + * @start: bit offset of the 8-bit value; must be a multiple of 8 + * + * Returns the 8-bit value located at the @start bit offset within the @src + * memory region. + */ +static inline unsigned long bitmap_get_value8(const unsigned long *map, + unsigned long start) +{ + const size_t index = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + + return (map[index] >> offset) & 0xFF; +} + +/** + * bitmap_set_value8 - set an 8-bit value within a memory region + * @map: address to the bitmap memory region + * @value: the 8-bit value; values wider than 8 bits may clobber bitmap + * @start: bit offset of the 8-bit value; must be a multiple of 8 + */ +static inline void bitmap_set_value8(unsigned long *map, unsigned long value, + unsigned long start) +{ + const size_t index = BIT_WORD(start); + const unsigned long offset = start % BITS_PER_LONG; + + map[index] &= ~(0xFFUL << offset); + map[index] |= value << offset; +} + #endif /* __ASSEMBLY__ */ #endif /* __LINUX_BITMAP_H */ --- a/include/linux/bitops.h~bitops-introduce-the-for_each_set_clump8-macro +++ a/include/linux/bitops.h @@ -47,6 +47,18 @@ extern unsigned long __sw_hweight64(__u6 (bit) < (size); \ (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) +/** + * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits + * @start: bit offset to start search and to store the current iteration offset + * @clump: location to store copy of current 8-bit clump + * @bits: bitmap address to base the search on + * @size: bitmap size in number of bits + */ +#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), (size), (start) + 8)) + static inline int get_bitmask_order(unsigned int count) { int order; --- a/lib/find_bit.c~bitops-introduce-the-for_each_set_clump8-macro +++ a/lib/find_bit.c @@ -214,3 +214,17 @@ EXPORT_SYMBOL(find_next_bit_le); #endif #endif /* __BIG_ENDIAN */ + +unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, + unsigned long size, unsigned long offset) +{ + offset = find_next_bit(addr, size, offset); + if (offset == size) + return size; + + offset = round_down(offset, 8); + *clump = bitmap_get_value8(addr, offset); + + return offset; +} +EXPORT_SYMBOL(find_next_clump8); _