LinuxLists.cc - [PATCH v4 0/8] Introduce the for_each_set

2018-05-15 16:23:41

Subject: [PATCH v4 0/8] Introduce the for_each_set_clump macro

Changes in v4:
- Fix bitmap_set arguments (last parameter is nbits not endbit)

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_clump macro and utilizes it in
several GPIO drivers. The for_each_set_clump macro facilitates a
for-loop syntax that iterates over entire groups of set bits at a time.

For example, suppose you would like to iterate over a 16-bit integer 4
bits at a time, skipping over 4-bit groups with no set bit, where XXXX
represents the current 4-bit group:

Example: 1011 1110 0000 1111
First loop: 1011 1110 0000 XXXX
Second loop: 1011 XXXX 0000 1111
Third loop: XXXX 1110 0000 1111

Each iteration of the loop returns the next 4-bit group that has at
least one set bit.

The for_each_set_clump macro has six parameters:

* clump: set to current clump index for the iteration
* index: set to current bitmap word index for the iteration
* offset: bits offset of the found clump in the bitmap word
* bits: bitmap to search within
* size: bitmap size in number of clumps
* clump_size: clump size in number of bits

The clump_size argument can be an arbitrary number of bits and is not
required to be a multiple of 2.

This patchset was rebased on top of the following three commits:

* commit aaf96e51de11 ("gpio: pci-idio-16: Fix port memory offset for get_multiple callback")
* commit 304440aa96c6 ("gpio: pcie-idio-24: Fix port memory offset for get_multiple/set_multiple callbacks")
* commit e026646c178d ("gpio: pcie-idio-24: Fix off-by-one error in get_multiple loop")

When I implemented the test_for_each_set_clump function, I used
bitmap_set to set the expected bitmap for the test. This method of
setting bits only segments at a time was rather tedious and error-prone;
is there a better way to accomplish what I did (set a bitmap after a
DECLARE_BITMAP)?

William Breathitt Gray

William Breathitt Gray (8):
bitops: Introduce the for_each_set_clump macro
lib/test_bitmap.c: Add for_each_set_clump test cases
gpio: 104-dio-48e: Utilize for_each_set_clump macro
gpio: 104-idi-48: Utilize for_each_set_clump macro
gpio: gpio-mm: Utilize for_each_set_clump macro
gpio: ws16c48: Utilize for_each_set_clump macro
gpio: pci-idio-16: Utilize for_each_set_clump macro
gpio: pcie-idio-24: Utilize for_each_set_clump macro

drivers/gpio/gpio-104-dio-48e.c | 67 +++++---------------
drivers/gpio/gpio-104-idi-48.c | 32 ++--------
drivers/gpio/gpio-gpio-mm.c | 67 +++++---------------
drivers/gpio/gpio-pci-idio-16.c | 67 ++++++--------------
drivers/gpio/gpio-pcie-idio-24.c | 102 +++++++++++-------------------
drivers/gpio/gpio-ws16c48.c | 66 +++++--------------
include/asm-generic/bitops/find.h | 9 +++
include/linux/bitops.h | 7 ++
lib/find_bit.c | 40 ++++++++++++
lib/test_bitmap.c | 71 +++++++++++++++++++++
10 files changed, 236 insertions(+), 292 deletions(-)

--
2.17.0

2018-05-15 16:23:50

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 2/8] lib/test_bitmap.c: Add for_each_set_clump test cases

The introduction of the for_each_set_clump macro warrants test cases to
verify the implementation. This patch adds test case checks for whether
an out-of-bounds clump index is returned, a zero clump is returned, or
the returned clump value differs from the expected clump value. A 4-bit
clump size is chosen in order to verify non-8-bit iteration.

Cc: Andy Shevchenko <[email protected]>
Signed-off-by: William Breathitt Gray <[email protected]>
---
lib/test_bitmap.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 71 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index de16f7869fb1..fd1b9f0d5eda 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -88,6 +88,39 @@ __check_eq_u32_array(const char *srcfile, unsigned int line,
return true;
}

+static bool __init __check_eq_clump(const char *srcfile, unsigned int line,
+ const size_t clump_index, const size_t size,
+ const unsigned char *const clump_exp,
+ const unsigned long *const bits,
+ const size_t index,
+ const unsigned int offset)
+{
+ unsigned long clump;
+ unsigned long exp;
+
+ if (clump_index >= size) {
+ pr_warn("[%s:%u] clump index out-of-bounds: expected less than %zu, got %zu\n",
+ srcfile, line, size, clump_index);
+ return false;
+ }
+
+ exp = clump_exp[clump_index];
+ if (!exp) {
+ pr_warn("[%s:%u] clump index for zero clump: expected nonzero clump, got clump index %zu with clump value 0",
+ srcfile, line, clump_index);
+ return false;
+ }
+
+ clump = (bits[index] >> offset) & 0xF;
+ if (clump != exp) {
+ pr_warn("[%s:%u] expected 0x%lX, got 0x%lX",
+ srcfile, line, exp, clump);
+ return false;
+ }
+
+ return true;
+}
+
#define __expect_eq(suffix, ...) \
({ \
int result = 0; \
@@ -104,6 +137,7 @@ __check_eq_u32_array(const char *srcfile, unsigned int line,
#define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
#define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
#define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
+#define expect_eq_clump(...) __expect_eq(clump, ##__VA_ARGS__)

static void __init test_zero_clear(void)
{
@@ -352,6 +386,42 @@ static void noinline __init test_mem_optimisations(void)
}
}

+static const unsigned char clump_exp[] __initconst = {
+ 0x1, /* 1 bit set */
+ 0x2, /* non-edge 1 bit set */
+ 0x0, /* zero bits set */
+ 0xE, /* 3 bits set */
+ 0xE, /* Repeated clump */
+ 0xF, /* 4 bits set */
+ 0x3, /* 2 bits set */
+ 0x5, /* non-adjacent 2 bits set */
+};
+
+static void __init test_for_each_set_clump(void)
+{
+ size_t clump;
+ size_t index;
+ unsigned int offset;
+#define CLUMP_BITMAP_NUMBITS 32
+ DECLARE_BITMAP(bits, CLUMP_BITMAP_NUMBITS);
+#define CLUMP_SIZE 4
+ const size_t size = DIV_ROUND_UP(CLUMP_BITMAP_NUMBITS, CLUMP_SIZE);
+
+ /* set bitmap to test case */
+ bitmap_zero(bits, CLUMP_BITMAP_NUMBITS);
+ bitmap_set(bits, 0, 1); /* 0x1 */
+ bitmap_set(bits, 5, 1); /* 0x2 */
+ bitmap_set(bits, 13, 3); /* 0xE */
+ bitmap_set(bits, 17, 3); /* 0xE */
+ bitmap_set(bits, 20, 4); /* 0xF */
+ bitmap_set(bits, 24, 2); /* 0x3 */
+ bitmap_set(bits, 28, 1); /* 0x5 - part 1 */
+ bitmap_set(bits, 30, 1); /* 0x5 - part 2 */
+
+ for_each_set_clump(clump, index, offset, bits, size, CLUMP_SIZE)
+ expect_eq_clump(clump, size, clump_exp, bits, index, offset);
+}
+
static int __init test_bitmap_init(void)
{
test_zero_clear();
@@ -360,6 +430,7 @@ static int __init test_bitmap_init(void)
test_bitmap_arr32();
test_bitmap_parselist();
test_mem_optimisations();
+ test_for_each_set_clump();

if (failed_tests == 0)
pr_info("all %u tests passed\n", total_tests);
--
2.17.0

2018-05-15 16:24:39

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 6/8] gpio: ws16c48: Utilize for_each_set_clump macro

2018-05-15 16:24:40

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 7/8] gpio: pci-idio-16: Utilize for_each_set_clump macro

2018-05-15 16:24:40

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 5/8] gpio: gpio-mm: Utilize for_each_set_clump macro

2018-05-15 16:24:51

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 4/8] gpio: 104-idi-48: Utilize for_each_set_clump macro

2018-05-15 16:24:58

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 1/8] bitops: Introduce the for_each_set_clump macro

This macro iterates for each group of bits (clump) with set bits, within
a bitmap memory region. For each iteration, "clump" is set to the found
clump index, "index" is set to the word index of the bitmap containing
the found clump, and "offset" is set to the bit offset of the found
clump within the respective bitmap word.

Suggested-by: Andy Shevchenko <[email protected]>
Cc: Arnd Bergmann <[email protected]>
Signed-off-by: William Breathitt Gray <[email protected]>
---
include/asm-generic/bitops/find.h | 9 +++++++
include/linux/bitops.h | 7 ++++++
lib/find_bit.c | 40 +++++++++++++++++++++++++++++++
3 files changed, 56 insertions(+)

diff --git a/include/asm-generic/bitops/find.h b/include/asm-generic/bitops/find.h
index 8a1ee10014de..3d3b2fc34908 100644
--- a/include/asm-generic/bitops/find.h
+++ b/include/asm-generic/bitops/find.h
@@ -2,6 +2,8 @@
#ifndef _ASM_GENERIC_BITOPS_FIND_H_
#define _ASM_GENERIC_BITOPS_FIND_H_

+#include <linux/types.h>
+
#ifndef find_next_bit
/**
* find_next_bit - find the next set bit in a memory region
@@ -80,4 +82,11 @@ extern unsigned long find_first_zero_bit(const unsigned long *addr,

#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */

+size_t find_next_clump(size_t *const index, unsigned int *const offset,
+ const unsigned long *const bits, const size_t size,
+ const size_t clump_index, const unsigned int clump_size);
+
+#define find_first_clump(index, offset, bits, size, clump_size) \
+ find_next_clump((index), (offset), (bits), (size), 0, (clump_size))
+
#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 4cac4e1a72ff..cfaff6a14406 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -59,6 +59,13 @@ extern unsigned long __sw_hweight64(__u64 w);
(bit) < (size); \
(bit) = find_next_zero_bit((addr), (size), (bit) + 1))

+#define for_each_set_clump(clump, index, offset, bits, size, clump_size) \
+ for ((clump) = find_first_clump(&(index), &(offset), (bits), (size), \
+ (clump_size)); \
+ (clump) < (size); \
+ (clump) = find_next_clump(&(index), &(offset), (bits), (size), \
+ (clump) + 1, (clump_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..1d547fe9304f 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -218,3 +218,43 @@ EXPORT_SYMBOL(find_next_bit_le);
#endif

#endif /* __BIG_ENDIAN */
+
+/**
+ * find_next_clump - find next clump with set bits in a memory region
+ * @index: location to store bitmap word index of found clump
+ * @offset: bits offset of the found clump within the respective bitmap word
+ * @bits: address to base the search on
+ * @size: bitmap size in number of clumps
+ * @clump_index: clump index at which to start searching
+ * @clump_size: clump size in bits
+ *
+ * Returns the clump index for the next clump with set bits; the respective
+ * bitmap word index is stored at the location pointed by @index, and the bits
+ * offset of the found clump within the respective bitmap word is stored at the
+ * location pointed by @offset. If no bits are set, returns @size.
+ */
+size_t find_next_clump(size_t *const index, unsigned int *const offset,
+ const unsigned long *const bits, const size_t size,
+ const size_t clump_index, const unsigned int clump_size)
+{
+ size_t i;
+ unsigned int bits_offset;
+ unsigned long word_mask;
+ const unsigned long clump_mask = GENMASK(clump_size - 1, 0);
+
+ for (i = clump_index; i < size; i++) {
+ bits_offset = i * clump_size;
+
+ *index = BIT_WORD(bits_offset);
+ *offset = bits_offset % BITS_PER_LONG;
+
+ word_mask = bits[*index] & (clump_mask << *offset);
+ if (!word_mask)
+ continue;
+
+ return i;
+ }
+
+ return size;
+}
+EXPORT_SYMBOL(find_next_clump);
--
2.17.0

2018-05-15 16:25:02

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 3/8] gpio: 104-dio-48e: Utilize for_each_set_clump macro

Replace verbose implementation in get_multiple/set_multiple callbacks
with for_each_set_clump macro to simplify code and improve clarity.

Signed-off-by: William Breathitt Gray <[email protected]>
---
drivers/gpio/gpio-104-dio-48e.c | 67 ++++++++-------------------------
1 file changed, 16 insertions(+), 51 deletions(-)

diff --git a/drivers/gpio/gpio-104-dio-48e.c b/drivers/gpio/gpio-104-dio-48e.c
index 9c4e07fcb74b..77eeaa36094c 100644
--- a/drivers/gpio/gpio-104-dio-48e.c
+++ b/drivers/gpio/gpio-104-dio-48e.c
@@ -183,46 +183,23 @@ static int dio48e_gpio_get(struct gpio_chip *chip, unsigned offset)
return !!(port_state & mask);
}

+static const size_t ports[] = { 0, 1, 2, 4, 5, 6 };
+
static int dio48e_gpio_get_multiple(struct gpio_chip *chip, unsigned long *mask,
unsigned long *bits)
{
struct dio48e_gpio *const dio48egpio = gpiochip_get_data(chip);
size_t i;
- static const size_t ports[] = { 0, 1, 2, 4, 5, 6 };
- const unsigned int gpio_reg_size = 8;
- unsigned int bits_offset;
- size_t word_index;
- unsigned int word_offset;
- unsigned long word_mask;
- const unsigned long port_mask = GENMASK(gpio_reg_size - 1, 0);
+ size_t word;
+ unsigned int offset;
unsigned long port_state;

/* clear bits array to a clean slate */
bitmap_zero(bits, chip->ngpio);

- /* get bits are evaluated a gpio port register at a time */
- for (i = 0; i < ARRAY_SIZE(ports); i++) {
- /* gpio offset in bits array */
- bits_offset = i * gpio_reg_size;
-
- /* word index for bits array */
- word_index = BIT_WORD(bits_offset);
-
- /* gpio offset within current word of bits array */
- word_offset = bits_offset % BITS_PER_LONG;
-
- /* mask of get bits for current gpio within current word */
- word_mask = mask[word_index] & (port_mask << word_offset);
- if (!word_mask) {
- /* no get bits in this port so skip to next one */
- continue;
- }
-
- /* read bits from current gpio port */
+ for_each_set_clump(i, word, offset, mask, ARRAY_SIZE(ports), 8) {
port_state = inb(dio48egpio->base + ports[i]);
-
- /* store acquired bits at respective bits array offset */
- bits[word_index] |= port_state << word_offset;
+ bits[word] |= port_state << offset;
}

return 0;
@@ -252,37 +229,25 @@ static void dio48e_gpio_set_multiple(struct gpio_chip *chip,
unsigned long *mask, unsigned long *bits)
{
struct dio48e_gpio *const dio48egpio = gpiochip_get_data(chip);
- unsigned int i;
- const unsigned int gpio_reg_size = 8;
- unsigned int port;
- unsigned int out_port;
+ size_t i;
+ size_t word;
+ unsigned int offset;
+ unsigned int iomask;
unsigned int bitmask;
unsigned long flags;

- /* set bits are evaluated a gpio register size at a time */
- for (i = 0; i < chip->ngpio; i += gpio_reg_size) {
- /* no more set bits in this mask word; skip to the next word */
- if (!mask[BIT_WORD(i)]) {
- i = (BIT_WORD(i) + 1) * BITS_PER_LONG - gpio_reg_size;
- continue;
- }
-
- port = i / gpio_reg_size;
- out_port = (port > 2) ? port + 1 : port;
- bitmask = mask[BIT_WORD(i)] & bits[BIT_WORD(i)];
+ for_each_set_clump(i, word, offset, mask, ARRAY_SIZE(ports), 8) {
+ iomask = mask[word] >> offset;
+ bitmask = iomask & (bits[word] >> offset);

raw_spin_lock_irqsave(&dio48egpio->lock, flags);

/* update output state data and set device gpio register */
- dio48egpio->out_state[port] &= ~mask[BIT_WORD(i)];
- dio48egpio->out_state[port] |= bitmask;
- outb(dio48egpio->out_state[port], dio48egpio->base + out_port);
+ dio48egpio->out_state[i] &= ~iomask;
+ dio48egpio->out_state[i] |= bitmask;
+ outb(dio48egpio->out_state[i], dio48egpio->base + ports[i]);

raw_spin_unlock_irqrestore(&dio48egpio->lock, flags);
-
- /* prepare for next gpio register set */
- mask[BIT_WORD(i)] >>= gpio_reg_size;
- bits[BIT_WORD(i)] >>= gpio_reg_size;
}
}

--
2.17.0

2018-05-15 16:26:05

by William Breathitt Gray

[permalink] [raw]

Subject: [PATCH v4 8/8] gpio: pcie-idio-24: Utilize for_each_set_clump macro

Replace verbose implementation in get_multiple/set_multiple callbacks
with for_each_set_clump macro to simplify code and improve clarity.

Signed-off-by: William Breathitt Gray <[email protected]>
---
drivers/gpio/gpio-pcie-idio-24.c | 102 +++++++++++--------------------
1 file changed, 36 insertions(+), 66 deletions(-)

diff --git a/drivers/gpio/gpio-pcie-idio-24.c b/drivers/gpio/gpio-pcie-idio-24.c
index f953541e7890..b4d300338a05 100644
--- a/drivers/gpio/gpio-pcie-idio-24.c
+++ b/drivers/gpio/gpio-pcie-idio-24.c
@@ -199,41 +199,21 @@ static int idio_24_gpio_get_multiple(struct gpio_chip *chip,
{
struct idio_24_gpio *const idio24gpio = gpiochip_get_data(chip);
size_t i;
- const unsigned int gpio_reg_size = 8;
- unsigned int bits_offset;
- size_t word_index;
- unsigned int word_offset;
- unsigned long word_mask;
- const unsigned long port_mask = GENMASK(gpio_reg_size - 1, 0);
- unsigned long port_state;
+ size_t word;
+ unsigned int offset;
void __iomem *ports[] = {
&idio24gpio->reg->out0_7, &idio24gpio->reg->out8_15,
&idio24gpio->reg->out16_23, &idio24gpio->reg->in0_7,
&idio24gpio->reg->in8_15, &idio24gpio->reg->in16_23,
};
+ const size_t num_ports = ARRAY_SIZE(ports) + 1;
+ unsigned long port_state;
const unsigned long out_mode_mask = BIT(1);

/* clear bits array to a clean slate */
bitmap_zero(bits, chip->ngpio);

- /* get bits are evaluated a gpio port register at a time */
- for (i = 0; i < ARRAY_SIZE(ports) + 1; i++) {
- /* gpio offset in bits array */
- bits_offset = i * gpio_reg_size;
-
- /* word index for bits array */
- word_index = BIT_WORD(bits_offset);
-
- /* gpio offset within current word of bits array */
- word_offset = bits_offset % BITS_PER_LONG;
-
- /* mask of get bits for current gpio within current word */
- word_mask = mask[word_index] & (port_mask << word_offset);
- if (!word_mask) {
- /* no get bits in this port so skip to next one */
- continue;
- }
-
+ for_each_set_clump(i, word, offset, mask, num_ports, 8) {
/* read bits from current gpio port (port 6 is TTL GPIO) */
if (i < 6)
port_state = ioread8(ports[i]);
@@ -243,7 +223,7 @@ static int idio_24_gpio_get_multiple(struct gpio_chip *chip,
port_state = ioread8(&idio24gpio->reg->ttl_in0_7);

/* store acquired bits at respective bits array offset */
- bits[word_index] |= port_state << word_offset;
+ bits[word] |= port_state << offset;
}

return 0;
@@ -295,58 +275,48 @@ static void idio_24_gpio_set_multiple(struct gpio_chip *chip,
{
struct idio_24_gpio *const idio24gpio = gpiochip_get_data(chip);
size_t i;
- unsigned long bits_offset;
- unsigned long gpio_mask;
- const unsigned int gpio_reg_size = 8;
- const unsigned long port_mask = GENMASK(gpio_reg_size, 0);
- unsigned long flags;
- unsigned int out_state;
+ size_t word;
+ unsigned int offset;
void __iomem *ports[] = {
&idio24gpio->reg->out0_7, &idio24gpio->reg->out8_15,
&idio24gpio->reg->out16_23
};
+ const size_t num_ports = ARRAY_SIZE(ports) + 1;
+ unsigned int iomask;
+ unsigned int bitmask;
+ unsigned long flags;
const unsigned long out_mode_mask = BIT(1);
- const unsigned int ttl_offset = 48;
- const size_t ttl_i = BIT_WORD(ttl_offset);
- const unsigned int word_offset = ttl_offset % BITS_PER_LONG;
- const unsigned long ttl_mask = (mask[ttl_i] >> word_offset) & port_mask;
- const unsigned long ttl_bits = (bits[ttl_i] >> word_offset) & ttl_mask;
-
- /* set bits are processed a gpio port register at a time */
- for (i = 0; i < ARRAY_SIZE(ports); i++) {
- /* gpio offset in bits array */
- bits_offset = i * gpio_reg_size;
-
- /* check if any set bits for current port */
- gpio_mask = (*mask >> bits_offset) & port_mask;
- if (!gpio_mask) {
- /* no set bits for this port so move on to next port */
+ unsigned int out_state;
+
+ for_each_set_clump(i, word, offset, mask, num_ports, 8) {
+ iomask = mask[word] >> offset;
+ bitmask = iomask & (bits[word] >> offset);
+
+ raw_spin_lock_irqsave(&idio24gpio->lock, flags);
+
+ /* read bits from current gpio port (port 6 is TTL GPIO) */
+ if (i < 6) {
+ out_state = ioread8(ports[i]) & ~iomask;
+ } else if (ioread8(&idio24gpio->reg->ctl) & out_mode_mask) {
+ out_state = ioread8(&idio24gpio->reg->ttl_out0_7);
+ } else {
+ /* skip TTL GPIO if set for input */
+ raw_spin_unlock_irqrestore(&idio24gpio->lock, flags);
continue;
}

- raw_spin_lock_irqsave(&idio24gpio->lock, flags);
+ /* set requested bit states */
+ out_state &= ~iomask;
+ out_state |= bitmask;

- /* process output lines */
- out_state = ioread8(ports[i]) & ~gpio_mask;
- out_state |= (*bits >> bits_offset) & gpio_mask;
- iowrite8(out_state, ports[i]);
+ /* write bits for current gpio port (port 6 is TTL GPIO) */
+ if (i < 6)
+ iowrite8(out_state, ports[i]);
+ else
+ iowrite8(out_state, &idio24gpio->reg->ttl_out0_7);

raw_spin_unlock_irqrestore(&idio24gpio->lock, flags);
}
-
- /* check if setting TTL lines and if they are in output mode */
- if (!ttl_mask || !(ioread8(&idio24gpio->reg->ctl) & out_mode_mask))
- return;
-
- /* handle TTL output */
- raw_spin_lock_irqsave(&idio24gpio->lock, flags);
-
- /* process output lines */
- out_state = ioread8(&idio24gpio->reg->ttl_out0_7) & ~ttl_mask;
- out_state |= ttl_bits;
- iowrite8(out_state, &idio24gpio->reg->ttl_out0_7);
-
- raw_spin_unlock_irqrestore(&idio24gpio->lock, flags);
}

static void idio_24_irq_ack(struct irq_data *data)
--
2.17.0

2018-05-16 14:04:38

by Linus Walleij

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
<[email protected]> wrote:

> For example, suppose you would like to iterate over a 16-bit integer 4
> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
> represents the current 4-bit group:
>
> Example: 1011 1110 0000 1111
> First loop: 1011 1110 0000 XXXX
> Second loop: 1011 XXXX 0000 1111
> Third loop: XXXX 1110 0000 1111
>
> Each iteration of the loop returns the next 4-bit group that has at
> least one set bit.
>
> The for_each_set_clump macro has six parameters:
>
> * clump: set to current clump index for the iteration
> * index: set to current bitmap word index for the iteration
> * offset: bits offset of the found clump in the bitmap word
> * bits: bitmap to search within
> * size: bitmap size in number of clumps
> * clump_size: clump size in number of bits
>
> The clump_size argument can be an arbitrary number of bits and is not
> required to be a multiple of 2.

I must say I'm impressed. Very nice arithmetics going on there.

If I can get some ACK for the bitops patch I'd be happy to merge
it all through the GPIO tree. The users are pretty clear cut.

BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
to see what he has to say about the subject, but I don't have
that book as it turns out.

Yours,
Linus Walleij

2018-05-16 20:09:14

by Andy Shevchenko

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Wed, May 16, 2018 at 5:03 PM, Linus Walleij <[email protected]> wrote:
> On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
> <[email protected]> wrote:
>
>> For example, suppose you would like to iterate over a 16-bit integer 4
>> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
>> represents the current 4-bit group:
>>
>> Example: 1011 1110 0000 1111
>> First loop: 1011 1110 0000 XXXX
>> Second loop: 1011 XXXX 0000 1111
>> Third loop: XXXX 1110 0000 1111
>>
>> Each iteration of the loop returns the next 4-bit group that has at
>> least one set bit.
>>
>> The for_each_set_clump macro has six parameters:
>>
>> * clump: set to current clump index for the iteration
>> * index: set to current bitmap word index for the iteration
>> * offset: bits offset of the found clump in the bitmap word
>> * bits: bitmap to search within
>> * size: bitmap size in number of clumps
>> * clump_size: clump size in number of bits
>>
>> The clump_size argument can be an arbitrary number of bits and is not
>> required to be a multiple of 2.
>
> I must say I'm impressed. Very nice arithmetics going on there.
>
> If I can get some ACK for the bitops patch I'd be happy to merge
> it all through the GPIO tree. The users are pretty clear cut.

Give me also some time to go through proposed API, I think it might
have needed more alignment with existing find_* and for_* helpers.

> BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
> Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
> to see what he has to say about the subject, but I don't have
> that book as it turns out.

I can also add the Standford collection of bit algos here:

https://graphics.stanford.edu/~seander/bithacks.html

--
With Best Regards,
Andy Shevchenko

2018-06-16 19:18:10

by William Breathitt Gray

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Wed, May 16, 2018 at 11:08:28PM +0300, Andy Shevchenko wrote:
>On Wed, May 16, 2018 at 5:03 PM, Linus Walleij <[email protected]> wrote:
>> On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
>> <[email protected]> wrote:
>>
>>> For example, suppose you would like to iterate over a 16-bit integer 4
>>> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
>>> represents the current 4-bit group:
>>>
>>> Example: 1011 1110 0000 1111
>>> First loop: 1011 1110 0000 XXXX
>>> Second loop: 1011 XXXX 0000 1111
>>> Third loop: XXXX 1110 0000 1111
>>>
>>> Each iteration of the loop returns the next 4-bit group that has at
>>> least one set bit.
>>>
>>> The for_each_set_clump macro has six parameters:
>>>
>>> * clump: set to current clump index for the iteration
>>> * index: set to current bitmap word index for the iteration
>>> * offset: bits offset of the found clump in the bitmap word
>>> * bits: bitmap to search within
>>> * size: bitmap size in number of clumps
>>> * clump_size: clump size in number of bits
>>>
>>> The clump_size argument can be an arbitrary number of bits and is not
>>> required to be a multiple of 2.
>>
>> I must say I'm impressed. Very nice arithmetics going on there.
>>
>> If I can get some ACK for the bitops patch I'd be happy to merge
>> it all through the GPIO tree. The users are pretty clear cut.
>
>Give me also some time to go through proposed API, I think it might
>have needed more alignment with existing find_* and for_* helpers.

Hi Andy,

Are there any additional changes you would like me to make before this
patchset is merged through the GPIO tree?

William Breathitt Gray

>
>> BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
>> Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
>> to see what he has to say about the subject, but I don't have
>> that book as it turns out.
>
>I can also add the Standford collection of bit algos here:
>
>https://graphics.stanford.edu/~seander/bithacks.html
>
>--
>With Best Regards,
>Andy Shevchenko

2018-09-05 15:06:25

by William Breathitt Gray

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Wed, May 16, 2018 at 04:03:51PM +0200, Linus Walleij wrote:
>On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
><[email protected]> wrote:
>
>> For example, suppose you would like to iterate over a 16-bit integer 4
>> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
>> represents the current 4-bit group:
>>
>> Example: 1011 1110 0000 1111
>> First loop: 1011 1110 0000 XXXX
>> Second loop: 1011 XXXX 0000 1111
>> Third loop: XXXX 1110 0000 1111
>>
>> Each iteration of the loop returns the next 4-bit group that has at
>> least one set bit.
>>
>> The for_each_set_clump macro has six parameters:
>>
>> * clump: set to current clump index for the iteration
>> * index: set to current bitmap word index for the iteration
>> * offset: bits offset of the found clump in the bitmap word
>> * bits: bitmap to search within
>> * size: bitmap size in number of clumps
>> * clump_size: clump size in number of bits
>>
>> The clump_size argument can be an arbitrary number of bits and is not
>> required to be a multiple of 2.
>
>I must say I'm impressed. Very nice arithmetics going on there.
>
>If I can get some ACK for the bitops patch I'd be happy to merge
>it all through the GPIO tree. The users are pretty clear cut.
>
>BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
>Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
>to see what he has to say about the subject, but I don't have
>that book as it turns out.
>
>Yours,
>Linus Walleij

Hi Linus,

I'd like to get this patchset merged, but I'm aware that we haven't yet
received additional ACKs in the past couple months. Are there any
changes you would like made, or should I resubmit this patchset with
additional CCs in the hopes of some ACKs for the bitops patch?

Sincerely,

William Breathitt Gray

2018-09-10 07:56:26

by Linus Walleij

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Wed, Sep 5, 2018 at 5:04 PM William Breathitt Gray
<[email protected]> wrote:
> On Wed, May 16, 2018 at 04:03:51PM +0200, Linus Walleij wrote:
> >On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
> ><[email protected]> wrote:
> >
> >> For example, suppose you would like to iterate over a 16-bit integer 4
> >> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
> >> represents the current 4-bit group:
> >>
> >> Example: 1011 1110 0000 1111
> >> First loop: 1011 1110 0000 XXXX
> >> Second loop: 1011 XXXX 0000 1111
> >> Third loop: XXXX 1110 0000 1111
> >>
> >> Each iteration of the loop returns the next 4-bit group that has at
> >> least one set bit.
> >>
> >> The for_each_set_clump macro has six parameters:
> >>
> >> * clump: set to current clump index for the iteration
> >> * index: set to current bitmap word index for the iteration
> >> * offset: bits offset of the found clump in the bitmap word
> >> * bits: bitmap to search within
> >> * size: bitmap size in number of clumps
> >> * clump_size: clump size in number of bits
> >>
> >> The clump_size argument can be an arbitrary number of bits and is not
> >> required to be a multiple of 2.
> >
> >I must say I'm impressed. Very nice arithmetics going on there.
> >
> >If I can get some ACK for the bitops patch I'd be happy to merge
> >it all through the GPIO tree. The users are pretty clear cut.
> >
> >BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
> >Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
> >to see what he has to say about the subject, but I don't have
> >that book as it turns out.
> >
> >Yours,
> >Linus Walleij
>
> Hi Linus,
>
> I'd like to get this patchset merged, but I'm aware that we haven't yet
> received additional ACKs in the past couple months. Are there any
> changes you would like made, or should I resubmit this patchset with
> additional CCs in the hopes of some ACKs for the bitops patch?

It seems Andy wanted some time and he had ~4 months now
so either he forgot it or has way too much to do.

I would say send this patch to Andrew Morton (the bitops patches)
so he can decide on it. He has the right bird's eye view on this
kind of things.

Yours,
Linus Walleij

2018-09-10 14:51:36

by Andy Shevchenko

[permalink] [raw]

Subject: Re: [PATCH v4 0/8] Introduce the for_each_set_clump macro

On Mon, Sep 10, 2018 at 09:54:47AM +0200, Linus Walleij wrote:
> On Wed, Sep 5, 2018 at 5:04 PM William Breathitt Gray
> <[email protected]> wrote:
> > On Wed, May 16, 2018 at 04:03:51PM +0200, Linus Walleij wrote:
> > >On Tue, May 15, 2018 at 6:22 PM, William Breathitt Gray
> > ><[email protected]> wrote:
> > >
> > >> For example, suppose you would like to iterate over a 16-bit integer 4
> > >> bits at a time, skipping over 4-bit groups with no set bit, where XXXX
> > >> represents the current 4-bit group:
> > >>
> > >> Example: 1011 1110 0000 1111
> > >> First loop: 1011 1110 0000 XXXX
> > >> Second loop: 1011 XXXX 0000 1111
> > >> Third loop: XXXX 1110 0000 1111
> > >>
> > >> Each iteration of the loop returns the next 4-bit group that has at
> > >> least one set bit.
> > >>
> > >> The for_each_set_clump macro has six parameters:
> > >>
> > >> * clump: set to current clump index for the iteration
> > >> * index: set to current bitmap word index for the iteration
> > >> * offset: bits offset of the found clump in the bitmap word
> > >> * bits: bitmap to search within
> > >> * size: bitmap size in number of clumps
> > >> * clump_size: clump size in number of bits
> > >>
> > >> The clump_size argument can be an arbitrary number of bits and is not
> > >> required to be a multiple of 2.
> > >
> > >I must say I'm impressed. Very nice arithmetics going on there.
> > >
> > >If I can get some ACK for the bitops patch I'd be happy to merge
> > >it all through the GPIO tree. The users are pretty clear cut.
> > >
> > >BTW: if I could, I would pull out Donald Knuth's "The Art of Computer
> > >Programming vol 4A" chapter 7.1.3 "Bitwise Tricks and Techniques"
> > >to see what he has to say about the subject, but I don't have
> > >that book as it turns out.
> > >
> > >Yours,
> > >Linus Walleij
> >
> > Hi Linus,
> >
> > I'd like to get this patchset merged, but I'm aware that we haven't yet
> > received additional ACKs in the past couple months. Are there any
> > changes you would like made, or should I resubmit this patchset with
> > additional CCs in the hopes of some ACKs for the bitops patch?
>
> It seems Andy wanted some time and he had ~4 months now
> so either he forgot it or has way too much to do.

Sorry, indeed, it got piled under huge backlog I have.

>
> I would say send this patch to Andrew Morton (the bitops patches)
> so he can decide on it. He has the right bird's eye view on this
> kind of things.

Agreed, and please add Rasmus as well.

--
With Best Regards,
Andy Shevchenko