From patchwork Mon Mar 25 06:22:23 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: 10867963 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 B492813B5 for ; Mon, 25 Mar 2019 06:21:42 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9F5E2291E0 for ; Mon, 25 Mar 2019 06:21:42 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 937B9291EF; Mon, 25 Mar 2019 06:21:42 +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=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,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 F293C291F8 for ; Mon, 25 Mar 2019 06:21:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729606AbfCYGVg (ORCPT ); Mon, 25 Mar 2019 02:21:36 -0400 Received: from mail-pg1-f195.google.com ([209.85.215.195]:46380 "EHLO mail-pg1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729432AbfCYGVg (ORCPT ); Mon, 25 Mar 2019 02:21:36 -0400 Received: by mail-pg1-f195.google.com with SMTP id a22so5720801pgg.13; Sun, 24 Mar 2019 23:21:35 -0700 (PDT) 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=aV6ymFQx+nOtCqgpruu20OLoQlbPHl6p+VcsTxWKcH8=; b=l+3QIjV+3MgIWEYuBy5dV0/rTPiVcvZxtqATTNnNp7aHeyRqSVs9aM4UCcA4jOvKjW NzWylOestU1bIWWrWyLFjHc8q2eZ8j+nQmQ6PH3Y1XealDaKuyQApB3EHr28F8U6XarU Tx/TKLSVJtayTWvIFYyeIuqKDdfdZ7tVC43zCq/wwelQuZjsTs9KohcRCVLUGLSIsSgo Q4lkIvJbtVcZ0UTbc7h26eK1sGJMP+Ho6HYlWiNJVrdHhXvoCt1WWuvM3gbj+lkT/KG+ EETcV4nRiJWT47zKRtrMC5fSBZ8D+cXCMz329ig7L15kqbszQy+e4VhkTHLNSTO/oPr4 P+EA== 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=aV6ymFQx+nOtCqgpruu20OLoQlbPHl6p+VcsTxWKcH8=; b=QgKJUfutbbDlThz5EJyS6tvsp1/MOhEoEHaJt5tmxlsR15Xphd7iaWtEqjQNlNOqsY UiuXHUea8w6l2FWONrLkRHXCaOhu19YBfKSpJEuOOzkPdcLT+V6EPQsUIU+kK6uRscWE DLxJ06iiOsNREYo9IAaZiQuayzs8aAfY9G7Ce9/YfzN5UdPSd4bZllO5qSmiZOR84GOn Uu4lMMsY6pJVvxBgN9kivezEStQnBpjSzcETI3TpXJq1/muJ0Hn+EBaqTedY+bfaE2h9 2gOAH9fXrnogCXqpSBgvdAxoFHlzekSkK7DIaa0dUf/lLZucPqC9/ztKkSwWz03Au/zO ib+g== X-Gm-Message-State: APjAAAUSWFyMJICnurXfzri9d/1YsHh1m+XB9PuAsIMaY6s8ncIUXbrH tPL3rOyrpo6We2tgVwSyXOc= X-Google-Smtp-Source: APXvYqyGFRJcNXz8zrAtlQoSN+BKG5OunI07yjZBglN4A6mnndvUfGJ0CpDCPXWNYLBvZyY0bat1tw== X-Received: by 2002:a17:902:2ac3:: with SMTP id j61mr23358166plb.112.1553494894741; Sun, 24 Mar 2019 23:21:34 -0700 (PDT) Received: from localhost.localdomain ([2001:268:c0a5:e068:c70:4af9:86e2:2]) by smtp.gmail.com with ESMTPSA id k17sm18916699pfk.166.2019.03.24.23.21.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 24 Mar 2019 23:21:34 -0700 (PDT) From: William Breathitt Gray To: linus.walleij@linaro.org, bgolaszewski@baylibre.com Cc: akpm@linux-foundation.org, linux-gpio@vger.kernel.org, linux-arch@vger.kernel.org, linux-kernel@vger.kernel.org, andriy.shevchenko@linux.intel.com, linux@rasmusvillemoes.dk, yamada.masahiro@socionext.com, linux-arm-kernel@lists.infradead.org, linux-pm@vger.kernel.org, geert@linux-m68k.org, preid@electromag.com.au, William Breathitt Gray , Andy Shevchenko , Arnd Bergmann Subject: [PATCH v12 01/11] bitops: Introduce the for_each_set_clump8 macro Date: Mon, 25 Mar 2019 15:22:23 +0900 Message-Id: <9afc30a574ce3e6a86b51dd522146a1d2156dedd.1553494625.git.vilhelm.gray@gmail.com> X-Mailer: git-send-email 2.21.0 In-Reply-To: References: MIME-Version: 1.0 Sender: linux-pm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-pm@vger.kernel.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 Acked-by: 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 602af23b98c7..f19a7bc8f559 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..1b6f8a6f1957 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(low_width - 1, 0) << 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);