[PATCH 0/4] Provide event map helper for regulator drivers

[PATCH 0/4] Provide event map helper for regulator drivers

[Matti Vaittinen]

[-- Attachment #1: Type: text/plain, Size: 1463 bytes --]

Misc regulator fixes.

This series provides a trivial event map helper for regulator drivers,
new single_bit_set() (needed by the event map helper) and a fix to
regulator IRQ helper parameters.

Regulators which provide trivial notification IRQs can use generic IRQ
mapper. Trivial in this context means the IRQ only informs one type of
event, for one regulator.

The series also provides a bitop helper which checks if there is only
one bit set in given mask. This was believed to be useful also for
others outside the regulator framework.

Last patch is a fix for IRQ helper removing an unused struct member.

---

Matti Vaittinen (4):
  bitops: Add single_bit_set()
  regulators: Add regulator_err2notif() helper
  regulators: irq_helper: Provide helper for trivial IRQ notifications
  regulator: Drop unnecessary struct member

 drivers/regulator/irq_helpers.c  | 42 +++++++++++++++++++++++++++++++-
 include/linux/bitops.h           | 20 +++++++++++++++
 include/linux/regulator/driver.h | 37 +++++++++++++++++++++++++++-
 3 files changed, 97 insertions(+), 2 deletions(-)

-- 
2.31.1


-- 
Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~~ "I don't think so," said Rene Descartes. Just then he vanished ~~~
Simon says - in Latin please.
~~~ "non cogito me" dixit Rene Descarte, deinde evanescavit ~~~
Thanks to Simon Glass for the translation =] 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH 1/4] bitops: Add single_bit_set()

[Matti Vaittinen]

[-- Attachment #1: Type: text/plain, Size: 1752 bytes --]

There are cases when it is useful to check a bit-mask has only one bit
set. Add a generic helper for it instead of baking own one for each
user.

Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>
---
I am not at all sure what would be the best place for this. Please let
me know if you think some other file would be more appropriate.
---
 include/linux/bitops.h | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 5e62e2383b7f..dd6c7baed3d3 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -66,6 +66,26 @@ extern unsigned long __sw_hweight64(__u64 w);
 	     (start) < (size); \
 	     (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
 
+/**
+ * single_bit_set - check if only one bit is set in value
+ * @bits:		value to check
+ * @bits_to_check:	how many bits we should scan
+ *
+ * Return: true if only one of the checked bits is set, othervice return false.
+ */
+static inline bool single_bit_set(const unsigned long bits, int bits_to_check)
+{
+	int bit;
+
+	bit = find_first_bit(&bits, bits_to_check);
+	if (bit == bits_to_check)
+		return false;
+
+	bit = find_next_bit(&bits, bits_to_check, bit + 1);
+
+	return (bit == bits_to_check);
+}
+
 static inline int get_bitmask_order(unsigned int count)
 {
 	int order;
-- 
2.31.1


-- 
Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~~ "I don't think so," said Rene Descartes. Just then he vanished ~~~
Simon says - in Latin please.
~~~ "non cogito me" dixit Rene Descarte, deinde evanescavit ~~~
Thanks to Simon Glass for the translation =] 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH 2/4] regulators: Add regulator_err2notif() helper

[Matti Vaittinen]

[-- Attachment #1: Type: text/plain, Size: 2370 bytes --]

Help drivers avoid storing both supported notification and supported error
flags by supporting conversion from regulator error to notification.
This may help saving some bytes.

Add helper for finding the regulator notification corresponding to a
regulator error.

Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>
---
 include/linux/regulator/driver.h | 34 ++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

diff --git a/include/linux/regulator/driver.h b/include/linux/regulator/driver.h
index 1cb8071fee34..f0827d34cb65 100644
--- a/include/linux/regulator/driver.h
+++ b/include/linux/regulator/driver.h
@@ -646,6 +646,40 @@ struct regulator_dev {
 	spinlock_t err_lock;
 };
 
+/*
+ * Convert error flags to corresponding notifications.
+ *
+ * Can be used by drivers which use the notification helpers to
+ * find out correct notification flags based on the error flags. Drivers
+ * can avoid storing both supported notification and error flags which
+ * may save few bytes.
+ */
+static inline int regulator_err2notif(int err)
+{
+	switch (err) {
+	case REGULATOR_ERROR_UNDER_VOLTAGE:
+		return REGULATOR_EVENT_UNDER_VOLTAGE;
+	case REGULATOR_ERROR_OVER_CURRENT:
+		return REGULATOR_EVENT_OVER_CURRENT;
+	case REGULATOR_ERROR_REGULATION_OUT:
+		return REGULATOR_EVENT_REGULATION_OUT;
+	case REGULATOR_ERROR_FAIL:
+		return REGULATOR_EVENT_FAIL;
+	case REGULATOR_ERROR_OVER_TEMP:
+		return REGULATOR_EVENT_OVER_TEMP;
+	case REGULATOR_ERROR_UNDER_VOLTAGE_WARN:
+		return REGULATOR_EVENT_UNDER_VOLTAGE_WARN;
+	case REGULATOR_ERROR_OVER_CURRENT_WARN:
+		return REGULATOR_EVENT_OVER_CURRENT_WARN;
+	case REGULATOR_ERROR_OVER_VOLTAGE_WARN:
+		return REGULATOR_EVENT_OVER_VOLTAGE_WARN;
+	case REGULATOR_ERROR_OVER_TEMP_WARN:
+		return REGULATOR_EVENT_OVER_TEMP_WARN;
+	}
+	return 0;
+}
+
+
 struct regulator_dev *
 regulator_register(const struct regulator_desc *regulator_desc,
 		   const struct regulator_config *config);
-- 
2.31.1


-- 
Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~~ "I don't think so," said Rene Descartes. Just then he vanished ~~~
Simon says - in Latin please.
~~~ "non cogito me" dixit Rene Descarte, deinde evanescavit ~~~
Thanks to Simon Glass for the translation =] 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH 3/4] regulators: irq_helper: Provide helper for trivial IRQ notifications

[Matti Vaittinen]

[-- Attachment #1: Type: text/plain, Size: 4376 bytes --]

Provide a generic map_event helper for regulators which have a notification
IRQ with single, well defined purpose. Eg, IRQ always indicates exactly one
event for exactly one regulator device. For such IRQs the mapping is
trivial.

Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>

---
This change was introduced earlier as part of the series:
"Few miscellaneous regulator improvements". Other patches from the
series were merged so this is now a lonely one and also the commit name
was changed to better reflect the new apporach (provide helper instead
of allowing omitting the callback). Changes from the initial idea:

 - Move the single_bit_set() to location where it is usable also for
   others.
 - Export helper for trivial mapping instead of adding the callback on
   behalf of the driver.
---
 drivers/regulator/irq_helpers.c  | 42 +++++++++++++++++++++++++++++++-
 include/linux/regulator/driver.h |  2 ++
 2 files changed, 43 insertions(+), 1 deletion(-)

diff --git a/drivers/regulator/irq_helpers.c b/drivers/regulator/irq_helpers.c
index 522764435575..4ba1f1975f16 100644
--- a/drivers/regulator/irq_helpers.c
+++ b/drivers/regulator/irq_helpers.c
@@ -320,7 +320,9 @@ static void init_rdev_errors(struct regulator_irq *h)
  *			IRQF_ONESHOT when requesting the (threaded) irq.
  * @common_errs:	Errors which can be flagged by this IRQ for all rdevs.
  *			When IRQ is re-enabled these errors will be cleared
- *			from all associated regulators
+ *			from all associated regulators. Use this instead of the
+ *			per_rdev_errs if you use
+ *			regulator_irq_map_event_simple() for event mapping.
  * @per_rdev_errs:	Optional error flag array describing errors specific
  *			for only some of the regulators. These errors will be
  *			or'ed with common errors. If this is given the array
@@ -395,3 +397,41 @@ void regulator_irq_helper_cancel(void **handle)
 	}
 }
 EXPORT_SYMBOL_GPL(regulator_irq_helper_cancel);
+
+/**
+ * regulator_irq_map_event_simple - regulator IRQ notification for trivial IRQs
+ *
+ * @irq:	Number of IRQ that occurred
+ * @rid:	Information about the event IRQ indicates
+ * @dev_mask:	mask indicating the regulator originating the IRQ
+ *
+ * Regulators whose IRQ has single, well defined purpose (always indicate
+ * exactly one event, and are relevant to exactly one regulator device) can
+ * use this function as their map_event callbac for their regulator IRQ
+ * notification helperk. Exactly one rdev and exactly one error (in
+ * "common_errs"-field) can be given at IRQ helper registration for
+ * regulator_irq_map_event_simple() to be viable.
+ */
+int regulator_irq_map_event_simple(int irq, struct regulator_irq_data *rid,
+			    unsigned long *dev_mask)
+{
+	int err = rid->states[0].possible_errs;
+
+	*dev_mask = 1;
+	/*
+	 * This helper should only be used in a situation where the IRQ
+	 * can indicate only one type of problem for one specific rdev.
+	 * Something fishy is going on if we are having multiple rdevs or ERROR
+	 * flags here.
+	 */
+	if (WARN_ON(rid->num_states != 1 ||
+	    !single_bit_set(err, sizeof(err) * 8)))
+		return 0;
+
+	rid->states[0].errors = err;
+	rid->states[0].notifs = regulator_err2notif(err);
+
+	return 0;
+}
+EXPORT_SYMBOL_GPL(regulator_irq_map_event_simple);
+
diff --git a/include/linux/regulator/driver.h b/include/linux/regulator/driver.h
index f0827d34cb65..15cd94bb6769 100644
--- a/include/linux/regulator/driver.h
+++ b/include/linux/regulator/driver.h
@@ -701,6 +701,8 @@ void *regulator_irq_helper(struct device *dev,
 			   int irq_flags, int common_errs, int *per_rdev_errs,
 			   struct regulator_dev **rdev, int rdev_amount);
 void regulator_irq_helper_cancel(void **handle);
+int regulator_irq_map_event_simple(int irq, struct regulator_irq_data *rid,
+				   unsigned long *dev_mask);
 
 void *rdev_get_drvdata(struct regulator_dev *rdev);
 struct device *rdev_get_dev(struct regulator_dev *rdev);
-- 
2.31.1


-- 
Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~~ "I don't think so," said Rene Descartes. Just then he vanished ~~~
Simon says - in Latin please.
~~~ "non cogito me" dixit Rene Descarte, deinde evanescavit ~~~
Thanks to Simon Glass for the translation =] 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH 4/4] regulator: Drop unnecessary struct member

[Matti Vaittinen]

[-- Attachment #1: Type: text/plain, Size: 1159 bytes --]

The irq_flags from the regulator IRQ helper description struct was never
used. The IRQ flags are passed as parameters to helper registration
instead.

Remove the unnecessary struct field.

Fixes: 7111c6d1b31b ("regulator: IRQ based event/error notification helpers")
Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>
---
 include/linux/regulator/driver.h | 1 -
 1 file changed, 1 deletion(-)

diff --git a/include/linux/regulator/driver.h b/include/linux/regulator/driver.h
index 15cd94bb6769..4078c7776453 100644
--- a/include/linux/regulator/driver.h
+++ b/include/linux/regulator/driver.h
@@ -554,7 +554,6 @@ struct regulator_irq_data {
  */
 struct regulator_irq_desc {
 	const char *name;
-	int irq_flags;
 	int fatal_cnt;
 	int reread_ms;
 	int irq_off_ms;
-- 
2.31.1


-- 
Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~~ "I don't think so," said Rene Descartes. Just then he vanished ~~~
Simon says - in Latin please.
~~~ "non cogito me" dixit Rene Descarte, deinde evanescavit ~~~
Thanks to Simon Glass for the translation =] 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> There are cases when it is useful to check a bit-mask has only one bit
> set. Add a generic helper for it instead of baking own one for each
> user.
> 
> Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>
> ---
> I am not at all sure what would be the best place for this. Please let
> me know if you think some other file would be more appropriate.

So, you decided to reinvent hamming weight...
Please, drop this patch and use corresponding hweight() call.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 3/4] regulators: irq_helper: Provide helper for trivial IRQ notifications

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 01:04:12PM +0200, Matti Vaittinen wrote:
> Provide a generic map_event helper for regulators which have a notification
> IRQ with single, well defined purpose. Eg, IRQ always indicates exactly one
> event for exactly one regulator device. For such IRQs the mapping is
> trivial.

...

> +	int err = rid->states[0].possible_errs;

I would rather make it unsigned, but anyway...

> +	    !single_bit_set(err, sizeof(err) * 8)))

hweight32() seems suitable here.


-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Vaittinen, Matti]

On 11/22/21 13:28, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
>> There are cases when it is useful to check a bit-mask has only one bit
>> set. Add a generic helper for it instead of baking own one for each
>> user.
>>
>> Signed-off-by: Matti Vaittinen <matti.vaittinen@fi.rohmeurope.com>
>> ---
>> I am not at all sure what would be the best place for this. Please let
>> me know if you think some other file would be more appropriate.
> 
> So, you decided to reinvent hamming weight...
> Please, drop this patch and use corresponding hweight() call.
> 

Thanks Andy.

There are few differences to hamming weight here. We scan only given 
amount of bits - and we will end scanning immediately when we hit second 
set bit. Oh, and obviously we only return information whether there is 
exactly one bit set. So no, this is not hamming weight().

Yet, I think you are correct. My use-case does not warrant adding this. 
I have no need for scanning only certain amount of bits.

I think I actually tried using hweight() at some point but don't really 
remember why I rolled the single_bit_set. (I remember the hweight() 
usage because I had to do some googling as I had never heard term 
hamming weight before).

I'll see how it works out and if (when) it does I'll respin the series 
w/o this as you suggested. So thanks.

--Matti

-- 
The Linux Kernel guy at ROHM Semiconductors

Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~ this year is the year of a signature writers block ~~

Re: [PATCH 3/4] regulators: irq_helper: Provide helper for trivial IRQ notifications

[Vaittinen, Matti]

On 11/22/21 13:48, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 01:04:12PM +0200, Matti Vaittinen wrote:
>> Provide a generic map_event helper for regulators which have a notification
>> IRQ with single, well defined purpose. Eg, IRQ always indicates exactly one
>> event for exactly one regulator device. For such IRQs the mapping is
>> trivial.
> 
> ...
> 
>> +	int err = rid->states[0].possible_errs;
> 
> I would rather make it unsigned, but anyway...
> 
>> +	    !single_bit_set(err, sizeof(err) * 8)))
> 
> hweight32() seems suitable here.

Thanks Andy,

I\ll see how it works out and respin. I agree this use/case probably 
does not warrant adding the single_bit_set().

Best Regards
	-- Matti Vaittinen


-- 
The Linux Kernel guy at ROHM Semiconductors

Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~ this year is the year of a signature writers block ~~

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> On 11/22/21 13:28, Andy Shevchenko wrote:
> > On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> >> There are cases when it is useful to check a bit-mask has only one bit
> >> set. Add a generic helper for it instead of baking own one for each
> >> user.

> > So, you decided to reinvent hamming weight...
> > Please, drop this patch and use corresponding hweight() call.

> Thanks Andy.
> 
> There are few differences to hamming weight here. We scan only given 
> amount of bits - and we will end scanning immediately when we hit second 
> set bit. Oh, and obviously we only return information whether there is 
> exactly one bit set. So no, this is not hamming weight().

What do you mean by this?

hweight() will return you the number of the non-zero elements in the set.
In application to boolean based arrays it means the number of bits that
are set. Obviously, the condition `hweight() == 1` is what you are looking
for.

Or is there anything that missed in the equation?

> Yet, I think you are correct. My use-case does not warrant adding this. 
> I have no need for scanning only certain amount of bits.

(I guess no need to tell that eliminating bits is using mask in the parameter
 as you do anyway by supplying amount of bits.)

> I think I actually tried using hweight() at some point but don't really 
> remember why I rolled the single_bit_set. (I remember the hweight() 
> usage because I had to do some googling as I had never heard term 
> hamming weight before).

Oh, it should be a very good reason not to use hweight() since on some
architectures it might become just one assembly instruction.

> I'll see how it works out and if (when) it does I'll respin the series 
> w/o this as you suggested. So thanks.

(Side note: all your sentences but last in all of the paragraphs are ending
 with trailing space. For example, "series " and "thanks." for the comparison
 in the previous paragraph. Can you fix this, please?)

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > On 11/22/21 13:28, Andy Shevchenko wrote:

...

> > I think I actually tried using hweight() at some point but don't really 
> > remember why I rolled the single_bit_set. (I remember the hweight() 
> > usage because I had to do some googling as I had never heard term 
> > hamming weight before).
> 
> Oh, it should be a very good reason not to use hweight() since on some
> architectures it might become just one assembly instruction.

(for the sake of educational purposes to us both)
https://vaibhavsagar.com/blog/2019/09/08/popcount/

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Vaittinen, Matti]

On 11/22/21 14:57, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
>> On 11/22/21 13:28, Andy Shevchenko wrote:
>>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> 
> What do you mean by this?
> 
> hweight() will return you the number of the non-zero elements in the set.

Exactly. The function I added did only check if given set of bits had 
only one bit set.

> In application to boolean based arrays it means the number of bits that
> are set. Obviously, the condition `hweight() == 1` is what you are looking
> for.

Yes. (hweight() == 1) will result exactly same result - which does not 
mean the single_bit_set() was same as hweight(). Say, we have a 32bit 
wide value, which is likely to be '11' (binary). The single_bit_set() 
would return 0 after checking the 2.nd bit. So, this is not equal to 
hamming weight. But as I said, none of this is really needed for my 
use-case and does not warrant adding new function.

>> I think I actually tried using hweight() at some point but don't really
>> remember why I rolled the single_bit_set. (I remember the hweight()
>> usage because I had to do some googling as I had never heard term
>> hamming weight before).
> 
> Oh, it should be a very good reason not to use hweight() since on some
> architectures it might become just one assembly instruction.

I didn't know of this. Thanks for sharing.

> (Side note: all your sentences but last in all of the paragraphs are ending
>   with trailing space. For example, "series " and "thanks." for the comparison
>   in the previous paragraph. Can you fix this, please?)

I changed from evolution to Thunderbird when my old laptop broke. It 
seems Thunderbird is doing this by default, don't know if it can be 
changed :( I'll see if I find a solution.

Best Regards
	--Matti

-- 
The Linux Kernel guy at ROHM Semiconductors

Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~ this year is the year of a signature writers block ~~

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Yury Norov]

On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > On 11/22/21 13:28, Andy Shevchenko wrote:
> > > On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > >> There are cases when it is useful to check a bit-mask has only one bit
> > >> set. Add a generic helper for it instead of baking own one for each
> > >> user.
> 
> > > So, you decided to reinvent hamming weight...
> > > Please, drop this patch and use corresponding hweight() call.
> 
> > Thanks Andy.
> > 
> > There are few differences to hamming weight here. We scan only given 
> > amount of bits - and we will end scanning immediately when we hit second 
> > set bit. Oh, and obviously we only return information whether there is 
> > exactly one bit set. So no, this is not hamming weight().
> 
> What do you mean by this?
> 
> hweight() will return you the number of the non-zero elements in the set.
> In application to boolean based arrays it means the number of bits that
> are set. Obviously, the condition `hweight() == 1` is what you are looking
> for.

Hi Andy,

I think, Matti means earlier return when part of bitmap counts set
bits to a greater nubmer, and we can skip the rest. Right, Matti?

I agree that for Matti's usecase it's useless because 32-bit int is small,
and hweight() would count set bits with a single machine instruction. (And
it should be hweight32(), not bitmap_weight() in this case.)

But in general, it might be useful for long bitmaps.

The more complete way of doing this would be adding a new set of
functions: bitmap_weight_{eq,neq,gt,le}

I'm looking at how bitmap_weight is used in the kernel and see
quite a lot of places where this optimization may take place. For
example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:

        if (bitmap_weight(&flow_cfg->dmacflt_bmap,
                          flow_cfg->dmacflt_max_flows) == 1)
                otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);

may be replaced with:

        if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
                otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);

Most of that places are in drivers however, and the length of bitmaps
there is typically small, so that there's no chance to get any
measurable performance improvement.

There is always a chance that we have opencoded bitmap_weight_eq()
et all. If we add these API, it might help people wright better code.

What do you think?

Thanks,
Yury

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 09:54:14AM -0800, Yury Norov wrote:
> On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > > On 11/22/21 13:28, Andy Shevchenko wrote:
> > > > On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > > >> There are cases when it is useful to check a bit-mask has only one bit
> > > >> set. Add a generic helper for it instead of baking own one for each
> > > >> user.
> > 
> > > > So, you decided to reinvent hamming weight...
> > > > Please, drop this patch and use corresponding hweight() call.
> > 
> > > Thanks Andy.
> > > 
> > > There are few differences to hamming weight here. We scan only given 
> > > amount of bits - and we will end scanning immediately when we hit second 
> > > set bit. Oh, and obviously we only return information whether there is 
> > > exactly one bit set. So no, this is not hamming weight().
> > 
> > What do you mean by this?
> > 
> > hweight() will return you the number of the non-zero elements in the set.
> > In application to boolean based arrays it means the number of bits that
> > are set. Obviously, the condition `hweight() == 1` is what you are looking
> > for.
> 
> Hi Andy,
> 
> I think, Matti means earlier return when part of bitmap counts set
> bits to a greater nubmer, and we can skip the rest. Right, Matti?
> 
> I agree that for Matti's usecase it's useless because 32-bit int is small,
> and hweight() would count set bits with a single machine instruction. (And
> it should be hweight32(), not bitmap_weight() in this case.)
> 
> But in general, it might be useful for long bitmaps.
> 
> The more complete way of doing this would be adding a new set of
> functions: bitmap_weight_{eq,neq,gt,le}
> 
> I'm looking at how bitmap_weight is used in the kernel and see
> quite a lot of places where this optimization may take place. For
> example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:
> 
>         if (bitmap_weight(&flow_cfg->dmacflt_bmap,
>                           flow_cfg->dmacflt_max_flows) == 1)
>                 otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> 
> may be replaced with:
> 
>         if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
>                 otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> 
> Most of that places are in drivers however, and the length of bitmaps
> there is typically small, so that there's no chance to get any
> measurable performance improvement.
> 
> There is always a chance that we have opencoded bitmap_weight_eq()
> et all. If we add these API, it might help people wright better code.
> 
> What do you think?

Before answering this I would like to see how hweight() is currently being used
in the kernel against bitmaps. Like histogram collection

	comparison number	number of usages
	variadic			X
	1				Y
	2				Z
	...				...


-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Vaittinen, Matti]

Morning <please apply local timezone> Yuru, & all,

On 11/22/21 19:54, Yury Norov wrote:
> On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
>> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
>>> On 11/22/21 13:28, Andy Shevchenko wrote:
>>>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
>>>>> There are cases when it is useful to check a bit-mask has only one bit
>>>>> set. Add a generic helper for it instead of baking own one for each
>>>>> user.
>>
>>>> So, you decided to reinvent hamming weight...
>>>> Please, drop this patch and use corresponding hweight() call.
>>
>>> Thanks Andy.
>>>
>>> There are few differences to hamming weight here. We scan only given
>>> amount of bits - and we will end scanning immediately when we hit second
>>> set bit. Oh, and obviously we only return information whether there is
>>> exactly one bit set. So no, this is not hamming weight().
>>
>> What do you mean by this?
>>
>> hweight() will return you the number of the non-zero elements in the set.
>> In application to boolean based arrays it means the number of bits that
>> are set. Obviously, the condition `hweight() == 1` is what you are looking
>> for.
> 
> Hi Andy,
> 
> I think, Matti means earlier return when part of bitmap counts set
> bits to a greater nubmer, and we can skip the rest. Right, Matti?

Yes.

> But in general, it might be useful for long bitmaps.
> 
> The more complete way of doing this would be adding a new set of
> functions: bitmap_weight_{eq,neq,gt,le}
> 
> I'm looking at how bitmap_weight is used in the kernel and see
> quite a lot of places where this optimization may take place. For
> example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:
> 
>          if (bitmap_weight(&flow_cfg->dmacflt_bmap,
>                            flow_cfg->dmacflt_max_flows) == 1)
>                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> 
> may be replaced with:
> 
>          if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
>                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> 
> Most of that places are in drivers however, and the length of bitmaps
> there is typically small, so that there's no chance to get any
> measurable performance improvement.
> 
> There is always a chance that we have opencoded bitmap_weight_eq()
> et all. If we add these API, it might help people wright better code.
> 
> What do you think?

My uneducated opinion (for what it matters :]) is thet the cost of 
adding such functions is negligible so I am all for adding them if there 
are even few users who can benefit from those.

Best Regards
	--Matti Vaittinen

-- 
The Linux Kernel guy at ROHM Semiconductors

Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~ this year is the year of a signature writers block ~~

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Yury Norov]

On Tue, Nov 23, 2021 at 05:26:56AM +0000, Vaittinen, Matti wrote:
> Morning <please apply local timezone> Yuru, & all,
> 
> On 11/22/21 19:54, Yury Norov wrote:
> > On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> >> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> >>> On 11/22/21 13:28, Andy Shevchenko wrote:
> >>>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> >>>>> There are cases when it is useful to check a bit-mask has only one bit
> >>>>> set. Add a generic helper for it instead of baking own one for each
> >>>>> user.
> >>
> >>>> So, you decided to reinvent hamming weight...
> >>>> Please, drop this patch and use corresponding hweight() call.
> >>
> >>> Thanks Andy.
> >>>
> >>> There are few differences to hamming weight here. We scan only given
> >>> amount of bits - and we will end scanning immediately when we hit second
> >>> set bit. Oh, and obviously we only return information whether there is
> >>> exactly one bit set. So no, this is not hamming weight().
> >>
> >> What do you mean by this?
> >>
> >> hweight() will return you the number of the non-zero elements in the set.
> >> In application to boolean based arrays it means the number of bits that
> >> are set. Obviously, the condition `hweight() == 1` is what you are looking
> >> for.
> > 
> > Hi Andy,
> > 
> > I think, Matti means earlier return when part of bitmap counts set
> > bits to a greater nubmer, and we can skip the rest. Right, Matti?
> 
> Yes.
> 
> > But in general, it might be useful for long bitmaps.
> > 
> > The more complete way of doing this would be adding a new set of
> > functions: bitmap_weight_{eq,neq,gt,le}
> > 
> > I'm looking at how bitmap_weight is used in the kernel and see
> > quite a lot of places where this optimization may take place. For
> > example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:
> > 
> >          if (bitmap_weight(&flow_cfg->dmacflt_bmap,
> >                            flow_cfg->dmacflt_max_flows) == 1)
> >                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > 
> > may be replaced with:
> > 
> >          if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
> >                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > 
> > Most of that places are in drivers however, and the length of bitmaps
> > there is typically small, so that there's no chance to get any
> > measurable performance improvement.
> > 
> > There is always a chance that we have opencoded bitmap_weight_eq()
> > et all. If we add these API, it might help people wright better code.
> > 
> > What do you think?
> 
> My uneducated opinion (for what it matters :]) is thet the cost of 
> adding such functions is negligible so I am all for adding them if there 
> are even few users who can benefit from those.

I think I changed my opinion. We have enough examples of opencoded
bitmap_weight_{eq,...} in core code which will definitely benefit
from this optimization. For example, sched_cpu_activate:

         if (cpumask_weight(cpu_smt_mask(cpu)) == 2)
                 static_branch_inc_cpuslocked(&sched_smt_present);

Considering computers with thousands of CPUs, early return would save a
lot. 

I'll take a look on it at this weekend.

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Yury Norov]

On Mon, Nov 22, 2021 at 09:56:46PM +0200, Andy Shevchenko wrote:
> On Mon, Nov 22, 2021 at 09:54:14AM -0800, Yury Norov wrote:
> > On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> > > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > > > On 11/22/21 13:28, Andy Shevchenko wrote:
> > > > > On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > > > >> There are cases when it is useful to check a bit-mask has only one bit
> > > > >> set. Add a generic helper for it instead of baking own one for each
> > > > >> user.
> > > 
> > > > > So, you decided to reinvent hamming weight...
> > > > > Please, drop this patch and use corresponding hweight() call.
> > > 
> > > > Thanks Andy.
> > > > 
> > > > There are few differences to hamming weight here. We scan only given 
> > > > amount of bits - and we will end scanning immediately when we hit second 
> > > > set bit. Oh, and obviously we only return information whether there is 
> > > > exactly one bit set. So no, this is not hamming weight().
> > > 
> > > What do you mean by this?
> > > 
> > > hweight() will return you the number of the non-zero elements in the set.
> > > In application to boolean based arrays it means the number of bits that
> > > are set. Obviously, the condition `hweight() == 1` is what you are looking
> > > for.
> > 
> > Hi Andy,
> > 
> > I think, Matti means earlier return when part of bitmap counts set
> > bits to a greater nubmer, and we can skip the rest. Right, Matti?
> > 
> > I agree that for Matti's usecase it's useless because 32-bit int is small,
> > and hweight() would count set bits with a single machine instruction. (And
> > it should be hweight32(), not bitmap_weight() in this case.)
> > 
> > But in general, it might be useful for long bitmaps.
> > 
> > The more complete way of doing this would be adding a new set of
> > functions: bitmap_weight_{eq,neq,gt,le}
> > 
> > I'm looking at how bitmap_weight is used in the kernel and see
> > quite a lot of places where this optimization may take place. For
> > example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:
> > 
> >         if (bitmap_weight(&flow_cfg->dmacflt_bmap,
> >                           flow_cfg->dmacflt_max_flows) == 1)
> >                 otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > 
> > may be replaced with:
> > 
> >         if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
> >                 otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > 
> > Most of that places are in drivers however, and the length of bitmaps
> > there is typically small, so that there's no chance to get any
> > measurable performance improvement.
> > 
> > There is always a chance that we have opencoded bitmap_weight_eq()
> > et all. If we add these API, it might help people wright better code.
> > 
> > What do you think?
> 
> Before answering this I would like to see how hweight() is currently being used
> in the kernel against bitmaps. Like histogram collection

hweight() is not used against bitmap. We have bitmap_weight() for it.
 
> 	comparison number	number of usages
> 	variadic			X
> 	1				Y
> 	2				Z
> 	...				...

I don't think it would be helpful to build this histogram. For the
proposed optimization it's (almost) not important what number is
compared against bitmap_weight().

The important thing is that some callers in core code can save 
measurable amount of time if we switch them from
        bitmap_weight() == XXX
to
        bitmap_weight_eq(..., XXX)

Consider cpumask_weight and nodes_weight.

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Mon, Nov 22, 2021 at 11:33:46PM -0800, Yury Norov wrote:
> On Tue, Nov 23, 2021 at 05:26:56AM +0000, Vaittinen, Matti wrote:
> > On 11/22/21 19:54, Yury Norov wrote:
> > > On Mon, Nov 22, 2021 at 02:57:27PM +0200, Andy Shevchenko wrote:
> > >> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > >>> On 11/22/21 13:28, Andy Shevchenko wrote:
> > >>>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:

...

> > >>>> So, you decided to reinvent hamming weight...
> > >>>> Please, drop this patch and use corresponding hweight() call.
> > >>
> > >>> Thanks Andy.
> > >>>
> > >>> There are few differences to hamming weight here. We scan only given
> > >>> amount of bits - and we will end scanning immediately when we hit second
> > >>> set bit. Oh, and obviously we only return information whether there is
> > >>> exactly one bit set. So no, this is not hamming weight().
> > >>
> > >> What do you mean by this?
> > >>
> > >> hweight() will return you the number of the non-zero elements in the set.
> > >> In application to boolean based arrays it means the number of bits that
> > >> are set. Obviously, the condition `hweight() == 1` is what you are looking
> > >> for.
> > > 
> > > Hi Andy,
> > > 
> > > I think, Matti means earlier return when part of bitmap counts set
> > > bits to a greater nubmer, and we can skip the rest. Right, Matti?
> > 
> > Yes.
> > 
> > > But in general, it might be useful for long bitmaps.
> > > 
> > > The more complete way of doing this would be adding a new set of
> > > functions: bitmap_weight_{eq,neq,gt,le}
> > > 
> > > I'm looking at how bitmap_weight is used in the kernel and see
> > > quite a lot of places where this optimization may take place. For
> > > example otx2_remove_flow() in drivers/net/ethernet/marvell/octeontx2/nic/otx2_flows.c:
> > > 
> > >          if (bitmap_weight(&flow_cfg->dmacflt_bmap,
> > >                            flow_cfg->dmacflt_max_flows) == 1)
> > >                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > > 
> > > may be replaced with:
> > > 
> > >          if (bitmap_weight_eq(&flow_cfg->dmacflt_bmap, flow_cfg->dmacflt_max_flows, 1)
> > >                  otx2_update_rem_pfmac(pfvf, DMAC_ADDR_DEL);
> > > 
> > > Most of that places are in drivers however, and the length of bitmaps
> > > there is typically small, so that there's no chance to get any
> > > measurable performance improvement.
> > > 
> > > There is always a chance that we have opencoded bitmap_weight_eq()
> > > et all. If we add these API, it might help people wright better code.
> > > 
> > > What do you think?
> > 
> > My uneducated opinion (for what it matters :]) is thet the cost of 
> > adding such functions is negligible so I am all for adding them if there 
> > are even few users who can benefit from those.
> 
> I think I changed my opinion. We have enough examples of opencoded
> bitmap_weight_{eq,...} in core code which will definitely benefit
> from this optimization. For example, sched_cpu_activate:
> 
>          if (cpumask_weight(cpu_smt_mask(cpu)) == 2)
>                  static_branch_inc_cpuslocked(&sched_smt_present);
> 
> Considering computers with thousands of CPUs, early return would save a
> lot. 
> 
> I'll take a look on it at this weekend.

Be sure you get better assembly in these cases. As I have told already,
hweight() is a single assembly instruction, I'm not sure open coded variant
may be better even for long bitmaps. That said, assembly comparison and
some performance tests would be nice to have.

As an API per se it might make sense to have such, but you know that we don't
add it without users.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Geert Uytterhoeven]

Hi Andy,

On Tue, Nov 23, 2021 at 10:04 AM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
> Be sure you get better assembly in these cases. As I have told already,
> hweight() is a single assembly instruction, I'm not sure open coded variant

... on a select set of architectures.

Do we need CONFIG_HAVE_FAST_HWEIGHT?

> may be better even for long bitmaps. That said, assembly comparison and
> some performance tests would be nice to have.

> As an API per se it might make sense to have such, but you know that we don't
> add it without users.

Indeed. And code for unused APIs increase kernel size, too
(without LTO).

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

RE: [PATCH 1/4] bitops: Add single_bit_set()

[David Laight]

From: Vaittinen, Matti
> Sent: 22 November 2021 13:19
> 
> On 11/22/21 14:57, Andy Shevchenko wrote:
> > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> >> On 11/22/21 13:28, Andy Shevchenko wrote:
> >>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> >
> > What do you mean by this?
> >
> > hweight() will return you the number of the non-zero elements in the set.
> 
> Exactly. The function I added did only check if given set of bits had
> only one bit set.

Checking for exactly one bit can use the (x & (x - 1)) check on
non-zero values - which may even be better on some cpus with a
popcnt instruction.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Andy Shevchenko]

On Tue, Nov 23, 2021 at 10:42:45AM +0000, David Laight wrote:
> From: Vaittinen, Matti
> > Sent: 22 November 2021 13:19
> > 
> > On 11/22/21 14:57, Andy Shevchenko wrote:
> > > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > >> On 11/22/21 13:28, Andy Shevchenko wrote:
> > >>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > >
> > > What do you mean by this?
> > >
> > > hweight() will return you the number of the non-zero elements in the set.
> > 
> > Exactly. The function I added did only check if given set of bits had
> > only one bit set.
> 
> Checking for exactly one bit can use the (x & (x - 1)) check on
> non-zero values - which may even be better on some cpus with a
> popcnt instruction.

In the discussed case the value pretty much can be 0, meaning you have
to add an additional test which I believe diminishes all efforts for
the is_power_of_2() call.

-- 
With Best Regards,
Andy Shevchenko

RE: [PATCH 1/4] bitops: Add single_bit_set()

[David Laight]

From: Andy Shevchenko
> Sent: 23 November 2021 10:48
> 
> On Tue, Nov 23, 2021 at 10:42:45AM +0000, David Laight wrote:
> > From: Vaittinen, Matti
> > > Sent: 22 November 2021 13:19
> > >
> > > On 11/22/21 14:57, Andy Shevchenko wrote:
> > > > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > > >> On 11/22/21 13:28, Andy Shevchenko wrote:
> > > >>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > > >
> > > > What do you mean by this?
> > > >
> > > > hweight() will return you the number of the non-zero elements in the set.
> > >
> > > Exactly. The function I added did only check if given set of bits had
> > > only one bit set.
> >
> > Checking for exactly one bit can use the (x & (x - 1)) check on
> > non-zero values - which may even be better on some cpus with a
> > popcnt instruction.
> 
> In the discussed case the value pretty much can be 0, meaning you have
> to add an additional test which I believe diminishes all efforts for
> the is_power_of_2() call.

I wouldn't have thought so.
Code would be:
	if (!scan_for_non_zero())
		return 0;
	if (!is_power_of_2())
		return 0;
	return scan_for_non_zero() ? 0 : 1;

Hand-crafting asm you'd actually check for (x - 1) generating
carry in the initial scan.

The latency of popcnt it worse than arithmetic on a lot of x86 cpu.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Re: [PATCH 1/4] bitops: Add single_bit_set()

[Vaittinen, Matti]

On 11/23/21 12:42, David Laight wrote:
> From: Vaittinen, Matti
>> Sent: 22 November 2021 13:19
>>
>> On 11/22/21 14:57, Andy Shevchenko wrote:
>>> On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
>>>> On 11/22/21 13:28, Andy Shevchenko wrote:
>>>>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
>>>
>>> What do you mean by this?
>>>
>>> hweight() will return you the number of the non-zero elements in the set.
>>
>> Exactly. The function I added did only check if given set of bits had
>> only one bit set.
> 
> Checking for exactly one bit can use the (x & (x - 1)) check on
> non-zero values

Thanks! This was educating. I admit I had to launch a calculator with 
bit editor to see where this went to. I doubt I had ever noticed such 
possibility if I didn't send the original patch. I guess this is the 
true power of the collaboration ;)

Best Regards
--Matti

-- 
The Linux Kernel guy at ROHM Semiconductors

Matti Vaittinen, Linux device drivers
ROHM Semiconductors, Finland SWDC
Kiviharjunlenkki 1E
90220 OULU
FINLAND

~~ this year is the year of a signature writers block ~~

Re: [PATCH 1/4] bitops: Add single_bit_set()

['Andy Shevchenko']

On Tue, Nov 23, 2021 at 10:58:44AM +0000, David Laight wrote:
> From: Andy Shevchenko
> > On Tue, Nov 23, 2021 at 10:42:45AM +0000, David Laight wrote:
> > > From: Vaittinen, Matti
> > > > Sent: 22 November 2021 13:19
> > > > On 11/22/21 14:57, Andy Shevchenko wrote:
> > > > > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > > > >> On 11/22/21 13:28, Andy Shevchenko wrote:
> > > > >>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > > > >
> > > > > What do you mean by this?
> > > > >
> > > > > hweight() will return you the number of the non-zero elements in the set.
> > > >
> > > > Exactly. The function I added did only check if given set of bits had
> > > > only one bit set.
> > >
> > > Checking for exactly one bit can use the (x & (x - 1)) check on
> > > non-zero values - which may even be better on some cpus with a
> > > popcnt instruction.
> > 
> > In the discussed case the value pretty much can be 0, meaning you have
> > to add an additional test which I believe diminishes all efforts for
> > the is_power_of_2() call.
> 
> I wouldn't have thought so.
> Code would be:
> 	if (!scan_for_non_zero())
> 		return 0;
> 	if (!is_power_of_2())
> 		return 0;
> 	return scan_for_non_zero() ? 0 : 1;
> 
> Hand-crafting asm you'd actually check for (x - 1) generating
> carry in the initial scan.

Have you done any benchmarks? Can we see them?

> The latency of popcnt it worse than arithmetic on a lot of x86 cpu.

Ditto.


-- 
With Best Regards,
Andy Shevchenko

RE: [PATCH 1/4] bitops: Add single_bit_set()

[David Laight]

From: 'Andy Shevchenko'
> Sent: 23 November 2021 13:43
> 
> On Tue, Nov 23, 2021 at 10:58:44AM +0000, David Laight wrote:
> > From: Andy Shevchenko
> > > On Tue, Nov 23, 2021 at 10:42:45AM +0000, David Laight wrote:
> > > > From: Vaittinen, Matti
> > > > > Sent: 22 November 2021 13:19
> > > > > On 11/22/21 14:57, Andy Shevchenko wrote:
> > > > > > On Mon, Nov 22, 2021 at 12:42:21PM +0000, Vaittinen, Matti wrote:
> > > > > >> On 11/22/21 13:28, Andy Shevchenko wrote:
> > > > > >>> On Mon, Nov 22, 2021 at 01:03:25PM +0200, Matti Vaittinen wrote:
> > > > > >
> > > > > > What do you mean by this?
> > > > > >
> > > > > > hweight() will return you the number of the non-zero elements in the set.
> > > > >
> > > > > Exactly. The function I added did only check if given set of bits had
> > > > > only one bit set.
> > > >
> > > > Checking for exactly one bit can use the (x & (x - 1)) check on
> > > > non-zero values - which may even be better on some cpus with a
> > > > popcnt instruction.
> > >
> > > In the discussed case the value pretty much can be 0, meaning you have
> > > to add an additional test which I believe diminishes all efforts for
> > > the is_power_of_2() call.
> >
> > I wouldn't have thought so.
> > Code would be:
> > 	if (!scan_for_non_zero())
> > 		return 0;
> > 	if (!is_power_of_2())
> > 		return 0;
> > 	return scan_for_non_zero() ? 0 : 1;
> >
> > Hand-crafting asm you'd actually check for (x - 1) generating
> > carry in the initial scan.
> 
> Have you done any benchmarks? Can we see them?
> 
> > The latency of popcnt it worse than arithmetic on a lot of x86 cpu.

Well, on AMD piledriver and bulldozer (etc) 64bit popcnt has a latency of 4.
On bobcat the latency is 12.
Excavator and Ryzen are better.
Intel are ok except for the Atoms (silvermont/goldmont).
That isn't going to help.

But run on a cpu without a popcnt instruction and the performance will
really be horrid.
At best the gain for using popcnt is marginal.

If you want to try a benchmark then code up (and debug):
	%rsi = buf + length // pointer to end of bitmap
	%rcx = -length	// in bytes
1:	jrcxz	8f		// jumps if all zeros
	mov	(%rsi, %rcx),%rax
	mov	%rax, %rdx,
	sub	$1, %rax
	lea	8(%rcx), %rcx
	jc	1b		// jump if zero word
	and	%rdx, %rax
	jnz	8f		// jump if >1 bit set
2:	jrcxz	9f
	cmp	(%rsi, %rcx), %rax
	lea	8(%rcx), %rcx
	jz	2b
8:	xor	%eax,%eax
	ret
9:	int	%eax
	ret

I think that is (about) right).
The initial loop may be 3 clocks per iteration on a recent Intel cpu.

But I suspect the only real gains are on cpu without popcnt.
It isn't as though you'll be doing this as often as (say)
the IP checksum function - which I have benchmarked.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)