[PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

Convert greybus/uart.c from IDR to XArray. The abstract data type XArray
is more memory-efficient, parallelisable, and cache friendly. It takes
advantage of RCU to perform lookups without locking. Furthermore, IDR is
deprecated because XArray has a better (cleaner and more consistent) API.

Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
---

v3->v4: 
	Remove mutex_lock/unlock around xa_load(). These locks seem to
	be unnecessary because there is a 1:1 correspondence between
	a specific minor and its gb_tty and there is no reference
	counting. I think that the RCU locks used inside xa_load()
	are sufficient to protect this API from returning an invalid
	gb_tty in case of concurrent access. Some more considerations 
	on this topic are in the following message to linux-kernel list:
	https://lore.kernel.org/lkml/3554184.2JXonMZcNW@localhost.localdomain/
v2->v3:
        Fix some issues according to a review by Alex Elder <elder@ieee.org>
v1->v2:
        Fix an issue found by the kernel test robot. It is due to
        passing to xa_*lock() the same old mutex that IDR used with
        the previous version of the code.

 drivers/staging/greybus/uart.c | 32 ++++++++++++++------------------
 1 file changed, 14 insertions(+), 18 deletions(-)

diff --git a/drivers/staging/greybus/uart.c b/drivers/staging/greybus/uart.c
index 73f01ed1e5b7..f66983adb51b 100644
--- a/drivers/staging/greybus/uart.c
+++ b/drivers/staging/greybus/uart.c
@@ -22,7 +22,7 @@
 #include <linux/serial.h>
 #include <linux/tty_driver.h>
 #include <linux/tty_flip.h>
-#include <linux/idr.h>
+#include <linux/xarray.h>
 #include <linux/fs.h>
 #include <linux/kdev_t.h>
 #include <linux/kfifo.h>
@@ -32,8 +32,9 @@
 
 #include "gbphy.h"
 
-#define GB_NUM_MINORS	16	/* 16 is more than enough */
-#define GB_NAME		"ttyGB"
+#define GB_NUM_MINORS		16	/* 16 is more than enough */
+#define GB_RANGE_MINORS		XA_LIMIT(0, GB_NUM_MINORS)
+#define GB_NAME			"ttyGB"
 
 #define GB_UART_WRITE_FIFO_SIZE		PAGE_SIZE
 #define GB_UART_WRITE_ROOM_MARGIN	1	/* leave some space in fifo */
@@ -67,8 +68,7 @@ struct gb_tty {
 };
 
 static struct tty_driver *gb_tty_driver;
-static DEFINE_IDR(tty_minors);
-static DEFINE_MUTEX(table_lock);
+static DEFINE_XARRAY(tty_minors);
 
 static int gb_uart_receive_data_handler(struct gb_operation *op)
 {
@@ -341,8 +341,7 @@ static struct gb_tty *get_gb_by_minor(unsigned int minor)
 {
 	struct gb_tty *gb_tty;
 
-	mutex_lock(&table_lock);
-	gb_tty = idr_find(&tty_minors, minor);
+	gb_tty = xa_load(&tty_minors, minor);
 	if (gb_tty) {
 		mutex_lock(&gb_tty->mutex);
 		if (gb_tty->disconnected) {
@@ -353,19 +352,18 @@ static struct gb_tty *get_gb_by_minor(unsigned int minor)
 			mutex_unlock(&gb_tty->mutex);
 		}
 	}
-	mutex_unlock(&table_lock);
 	return gb_tty;
 }
 
 static int alloc_minor(struct gb_tty *gb_tty)
 {
 	int minor;
+	int ret;
 
-	mutex_lock(&table_lock);
-	minor = idr_alloc(&tty_minors, gb_tty, 0, GB_NUM_MINORS, GFP_KERNEL);
-	mutex_unlock(&table_lock);
-	if (minor >= 0)
-		gb_tty->minor = minor;
+	ret = xa_alloc(&tty_minors, &minor, gb_tty, GB_RANGE_MINORS, GFP_KERNEL);
+	if (ret)
+		return ret;
+	gb_tty->minor = minor;
 	return minor;
 }
 
@@ -374,9 +372,7 @@ static void release_minor(struct gb_tty *gb_tty)
 	int minor = gb_tty->minor;
 
 	gb_tty->minor = 0;	/* Maybe should use an invalid value instead */
-	mutex_lock(&table_lock);
-	idr_remove(&tty_minors, minor);
-	mutex_unlock(&table_lock);
+	xa_erase(&tty_minors, minor);
 }
 
 static int gb_tty_install(struct tty_driver *driver, struct tty_struct *tty)
@@ -837,7 +833,7 @@ static int gb_uart_probe(struct gbphy_device *gbphy_dev,
 
 	minor = alloc_minor(gb_tty);
 	if (minor < 0) {
-		if (minor == -ENOSPC) {
+		if (minor == -EBUSY) {
 			dev_err(&gbphy_dev->dev,
 				"no more free minor numbers\n");
 			retval = -ENODEV;
@@ -982,7 +978,7 @@ static void gb_tty_exit(void)
 {
 	tty_unregister_driver(gb_tty_driver);
 	put_tty_driver(gb_tty_driver);
-	idr_destroy(&tty_minors);
+	xa_destroy(&tty_minors);
 }
 
 static const struct gbphy_device_id gb_uart_id_table[] = {
-- 
2.32.0

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Sun, Aug 29, 2021 at 11:22:50AM +0200, Fabio M. De Francesco wrote:
> Convert greybus/uart.c from IDR to XArray. The abstract data type XArray
> is more memory-efficient, parallelisable, and cache friendly. It takes
> advantage of RCU to perform lookups without locking. Furthermore, IDR is
> deprecated because XArray has a better (cleaner and more consistent) API.

Where does it say that IDR is deprecated? Almost all drivers use IDR/IDA
and its interfaces are straight-forward. In most cases we don't care
about a possible slight increase in efficiency either, and so also in
this case. Correctness is what matters and doing these conversions risks
introducing regressions.

And I believe IDR use XArray internally these days anyway.

> Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> ---
> 
> v3->v4: 
> 	Remove mutex_lock/unlock around xa_load(). These locks seem to
> 	be unnecessary because there is a 1:1 correspondence between
> 	a specific minor and its gb_tty and there is no reference
> 	counting. I think that the RCU locks used inside xa_load()
> 	are sufficient to protect this API from returning an invalid
> 	gb_tty in case of concurrent access. Some more considerations 
> 	on this topic are in the following message to linux-kernel list:
> 	https://lore.kernel.org/lkml/3554184.2JXonMZcNW@localhost.localdomain/

This just doesn't make sense (and a valid motivation would need to go in
the commit message if there was one).

> v2->v3:
>         Fix some issues according to a review by Alex Elder <elder@ieee.org>
> v1->v2:
>         Fix an issue found by the kernel test robot. It is due to
>         passing to xa_*lock() the same old mutex that IDR used with
>         the previous version of the code.
> 
>  drivers/staging/greybus/uart.c | 32 ++++++++++++++------------------
>  1 file changed, 14 insertions(+), 18 deletions(-)
> 
> diff --git a/drivers/staging/greybus/uart.c b/drivers/staging/greybus/uart.c
> index 73f01ed1e5b7..f66983adb51b 100644
> --- a/drivers/staging/greybus/uart.c
> +++ b/drivers/staging/greybus/uart.c
> @@ -22,7 +22,7 @@
>  #include <linux/serial.h>
>  #include <linux/tty_driver.h>
>  #include <linux/tty_flip.h>
> -#include <linux/idr.h>
> +#include <linux/xarray.h>
>  #include <linux/fs.h>
>  #include <linux/kdev_t.h>
>  #include <linux/kfifo.h>
> @@ -32,8 +32,9 @@
>  
>  #include "gbphy.h"
>  
> -#define GB_NUM_MINORS	16	/* 16 is more than enough */
> -#define GB_NAME		"ttyGB"
> +#define GB_NUM_MINORS		16	/* 16 is more than enough */
> +#define GB_RANGE_MINORS		XA_LIMIT(0, GB_NUM_MINORS)
> +#define GB_NAME			"ttyGB"
>  
>  #define GB_UART_WRITE_FIFO_SIZE		PAGE_SIZE
>  #define GB_UART_WRITE_ROOM_MARGIN	1	/* leave some space in fifo */
> @@ -67,8 +68,7 @@ struct gb_tty {
>  };
>  
>  static struct tty_driver *gb_tty_driver;
> -static DEFINE_IDR(tty_minors);
> -static DEFINE_MUTEX(table_lock);
> +static DEFINE_XARRAY(tty_minors);
>  
>  static int gb_uart_receive_data_handler(struct gb_operation *op)
>  {
> @@ -341,8 +341,7 @@ static struct gb_tty *get_gb_by_minor(unsigned int minor)
>  {
>  	struct gb_tty *gb_tty;
>  
> -	mutex_lock(&table_lock);
> -	gb_tty = idr_find(&tty_minors, minor);
> +	gb_tty = xa_load(&tty_minors, minor);
>  	if (gb_tty) {
>  		mutex_lock(&gb_tty->mutex);
>  		if (gb_tty->disconnected) {
> @@ -353,19 +352,18 @@ static struct gb_tty *get_gb_by_minor(unsigned int minor)
>  			mutex_unlock(&gb_tty->mutex);
>  		}
>  	}
> -	mutex_unlock(&table_lock);

You can't just drop the locking here since you'd introduce a potential
use-after-free in case gb_tty is freed after the lookup but before the
port reference is taken.

That said, this driver is already broken since it can currently free the
gb_tty while there are references to the port. I'll try to fix it up...

>  	return gb_tty;
>  }

But as you may have gathered, I don't think doing these conversions is a
good idea.

Johan

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

On Monday, August 30, 2021 11:12:28 AM CEST Johan Hovold wrote:
> On Sun, Aug 29, 2021 at 11:22:50AM +0200, Fabio M. De Francesco wrote:
> > Convert greybus/uart.c from IDR to XArray. The abstract data type XArray
> > is more memory-efficient, parallelisable, and cache friendly. It takes
> > advantage of RCU to perform lookups without locking. Furthermore, IDR is
> > deprecated because XArray has a better (cleaner and more consistent) API.
> 
> Where does it say that IDR is deprecated? Almost all drivers use IDR/IDA
> and its interfaces are straight-forward. In most cases we don't care
> about a possible slight increase in efficiency either, and so also in
> this case. Correctness is what matters and doing these conversions risks
> introducing regressions.
> 
> And I believe IDR use XArray internally these days anyway.

Please read the following message by Matthew Wilcox for an authoritative response to your
doubts about efficiency of XArray and IDR deprecation:
https://lore.kernel.org/lkml/20210503182629.GE1847222@casper.infradead.org/

In particular he says that "[] The advantage of the XArray over the IDR is that it has a better 
API (and the IDR interface is deprecated).".

> > Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> > ---
> > 
> > v3->v4: 
> > 	Remove mutex_lock/unlock around xa_load(). These locks seem to
> > 	be unnecessary because there is a 1:1 correspondence between
> > 	a specific minor and its gb_tty and there is no reference
> > 	counting. I think that the RCU locks used inside xa_load()
> > 	are sufficient to protect this API from returning an invalid
> > 	gb_tty in case of concurrent access. Some more considerations 
> > 	on this topic are in the following message to linux-kernel list:
> > 	https://lore.kernel.org/lkml/3554184.2JXonMZcNW@localhost.localdomain/
> 
> This just doesn't make sense (and a valid motivation would need to go in
> the commit message if there was one).

OK, I'll take your words on it. Alex Elder wrote that he guess the mutex_lock/unlock()
around xa_load() are probably not necessary. As I said I don't yet have knowledge of 
this kind of topics, so I was just attempting to find out a reason why. Now I know that 
my v1 was correct in having those Mutexes as the original code with IDR had.
>
> > [...]
> 
> You can't just drop the locking here since you'd introduce a potential
> use-after-free in case gb_tty is freed after the lookup but before the
> port reference is taken.
> 
> That said, this driver is already broken since it can currently free the
> gb_tty while there are references to the port. I'll try to fix it up...
> 
> >  	return gb_tty;
> >  }
> 
> But as you may have gathered, I don't think doing these conversions is a
> good idea.
> 
> Johan
> 

Thanks for your review,

Fabio

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

[ Please wrap your mails at 72 columns or so. ]

On Mon, Aug 30, 2021 at 01:10:54PM +0200, Fabio M. De Francesco wrote:
> On Monday, August 30, 2021 11:12:28 AM CEST Johan Hovold wrote:
> > On Sun, Aug 29, 2021 at 11:22:50AM +0200, Fabio M. De Francesco wrote:
> > > Convert greybus/uart.c from IDR to XArray. The abstract data type XArray
> > > is more memory-efficient, parallelisable, and cache friendly. It takes
> > > advantage of RCU to perform lookups without locking. Furthermore, IDR is
> > > deprecated because XArray has a better (cleaner and more consistent) API.
> > 
> > Where does it say that IDR is deprecated? Almost all drivers use IDR/IDA
> > and its interfaces are straight-forward. In most cases we don't care
> > about a possible slight increase in efficiency either, and so also in
> > this case. Correctness is what matters and doing these conversions risks
> > introducing regressions.
> > 
> > And I believe IDR use XArray internally these days anyway.
> 
> Please read the following message by Matthew Wilcox for an
> authoritative response to your doubts about efficiency of XArray and
> IDR deprecation:

> https://lore.kernel.org/lkml/20210503182629.GE1847222@casper.infradead.org/
> 
> In particular he says that "[] The advantage of the XArray over the
> IDR is that it has a better API (and the IDR interface is
> deprecated).".

Whether the API is better is debatable. As I said, almost no drivers use
the new XArray interface, and perhaps partly because the new interface
isn't as intuitive as has been claimed (e.g. xa_load() instead of
ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
I know.

Your commit message sounds like ad for something, and is mostly
irrelevant for the case at hand.

> > > Signed-off-by: Fabio M. De Francesco <fmdefrancesco@gmail.com>
> > > ---
> > > 
> > > v3->v4: 
> > > 	Remove mutex_lock/unlock around xa_load(). These locks seem to
> > > 	be unnecessary because there is a 1:1 correspondence between
> > > 	a specific minor and its gb_tty and there is no reference
> > > 	counting. I think that the RCU locks used inside xa_load()
> > > 	are sufficient to protect this API from returning an invalid
> > > 	gb_tty in case of concurrent access. Some more considerations 
> > > 	on this topic are in the following message to linux-kernel list:
> > > 	https://lore.kernel.org/lkml/3554184.2JXonMZcNW@localhost.localdomain/
> > 
> > This just doesn't make sense (and a valid motivation would need to go in
> > the commit message if there was one).
> 
> OK, I'll take your words on it. Alex Elder wrote that he guess the
> mutex_lock/unlock() around xa_load() are probably not necessary. As I
> said I don't yet have knowledge of this kind of topics, so I was just
> attempting to find out a reason why. Now I know that my v1 was correct
> in having those Mutexes as the original code with IDR had.

This is partly why doing such conversions is a bad idea in the first
place. You need to understand the code that you're changing.

You don't know the code and risk introducing bugs, we need to spend time
reviewing it, and in the end we gain close to nothing at best.

Johan

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Matthew Wilcox]

On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
> Whether the API is better is debatable. As I said, almost no drivers use
> the new XArray interface, and perhaps partly because the new interface
> isn't as intuitive as has been claimed (e.g. xa_load() instead of
> ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
> I know.

I can't just slap a 'deprecated' attribute on it.  That'll cause a
storm of warnings.  What would you suggest I do to warn people that
this interface is deprecated and I would like to remove it?

Why do you think that idr_find() is more intuitive than xa_load()?
The 'find' verb means that you search for something.  But it doesn't
search for anything; it just returns the pointer at that index.
'find' should return the next non-NULL pointer at-or-above a given
index.

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Mon, Aug 30, 2021 at 01:16:07PM +0100, Matthew Wilcox wrote:
> On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
> > Whether the API is better is debatable. As I said, almost no drivers use
> > the new XArray interface, and perhaps partly because the new interface
> > isn't as intuitive as has been claimed (e.g. xa_load() instead of
> > ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
> > I know.
> 
> I can't just slap a 'deprecated' attribute on it.  That'll cause a
> storm of warnings.  What would you suggest I do to warn people that
> this interface is deprecated and I would like to remove it?

I'd at least expect a suggestion in the IDR documentation to consider
using XArray instead.

> Why do you think that idr_find() is more intuitive than xa_load()?
> The 'find' verb means that you search for something.  But it doesn't
> search for anything; it just returns the pointer at that index.
> 'find' should return the next non-NULL pointer at-or-above a given
> index.

We're looking up a minor number which may or may not exist. "Find" (or
"lookup" or "search") seems to describe this much better than "load"
(even if that may better reflect the implementation of XArray).

And no, I would not expect a find implementation to return the next
entry if the requested entry does not exist (and neither does idr_find()
or radix_tree_lookup()).

Johan

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

On Monday, August 30, 2021 2:33:05 PM CEST Johan Hovold wrote:
> On Mon, Aug 30, 2021 at 01:16:07PM +0100, Matthew Wilcox wrote:
> > On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
> > > Whether the API is better is debatable. As I said, almost no drivers use
> > > the new XArray interface, and perhaps partly because the new interface
> > > isn't as intuitive as has been claimed (e.g. xa_load() instead of
> > > ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
> > > I know.
> > 
> > I can't just slap a 'deprecated' attribute on it.  That'll cause a
> > storm of warnings.  What would you suggest I do to warn people that
> > this interface is deprecated and I would like to remove it?
> 
> I'd at least expect a suggestion in the IDR documentation to consider
> using XArray instead.
> 
> > Why do you think that idr_find() is more intuitive than xa_load()?
> > The 'find' verb means that you search for something.  But it doesn't
> > search for anything; it just returns the pointer at that index.
> > 'find' should return the next non-NULL pointer at-or-above a given
> > index.
> 
> We're looking up a minor number which may or may not exist. "Find" (or
> "lookup" or "search") seems to describe this much better than "load"
> (even if that may better reflect the implementation of XArray).
> 
> And no, I would not expect a find implementation to return the next
> entry if the requested entry does not exist (and neither does idr_find()
> or radix_tree_lookup()).
> 
> Johan
> 
Dear Johan,

Since your are not interested to this changes there's no need to restore the
Mutexes that were in v1. Please drop the patch and sorry for the noise.

Regards,

Fabio

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Alex Elder]

On 8/30/21 7:33 AM, Johan Hovold wrote:
> On Mon, Aug 30, 2021 at 01:16:07PM +0100, Matthew Wilcox wrote:
>> On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
>>> Whether the API is better is debatable. As I said, almost no drivers use
>>> the new XArray interface, and perhaps partly because the new interface
>>> isn't as intuitive as has been claimed (e.g. xa_load() instead of
>>> ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
>>> I know.
>>
>> I can't just slap a 'deprecated' attribute on it.  That'll cause a
>> storm of warnings.  What would you suggest I do to warn people that
>> this interface is deprecated and I would like to remove it?
> 
> I'd at least expect a suggestion in the IDR documentation to consider
> using XArray instead.
> 
>> Why do you think that idr_find() is more intuitive than xa_load()?
>> The 'find' verb means that you search for something.  But it doesn't
>> search for anything; it just returns the pointer at that index.
>> 'find' should return the next non-NULL pointer at-or-above a given
>> index.
> 
> We're looking up a minor number which may or may not exist. "Find" (or
> "lookup" or "search") seems to describe this much better than "load"
> (even if that may better reflect the implementation of XArray).
> 
> And no, I would not expect a find implementation to return the next
> entry if the requested entry does not exist (and neither does idr_find()
> or radix_tree_lookup())

For what it's worth, I think of "find" as meaning "look up this one
thing, and return it if it's there (or tell me if it's not)."  That
is irrespective of underlying implementation.

That verb sometimes might mean something else (like create it if it
doesn't exist, or perhaps "get it or the next available" as suggested)
but I wish we had a slightly different naming convention for those
things.

The XArray interface was designed to better match typical usage of
IDR/IDA, as I understand it.  And its name suggests it is modeled
as an array, so "load" seems like a reasonable verb to mean returning
the value associated with an identified entry.  (Even though the
"doesn't exist" part doesn't match normal array semantics.)

So I guess I agree in part with both Johan and Matthew on the
 meaning
of "load" as used in the XArray interface.  Either way, that *is* the
interface at the moment.


I have been offering review feedback on this patch for three reasons:

- First, because I think the intended change does no real harm to the

  Greybus code, and in a small way actually simplifies it.

- Because I wanted to encourage Fabio's efforts to be part of the

  Linux contributor community.

- Because I suspected that Matthew's long-term intention was to

  replace IDR/IDA use with XArray, so this would represent an early

  conversion.



The Greybus code is generally good, but that doesn't mean it can't

evolve.  It gets very little patch traffic, so I don't consider small

changes like this "useless churn."  The Greybus code is held up as
 an
example of Linux kernel code that can be safely modified, and I
 think
it's actively promoted as a possible source of new developer
 tasks
(e.g. for Outreachy).



So aside from the details of the use of XArray, I'd rather we be
more open to changes to the Greybus code.

					-Alex

> 
> Johan
> _______________________________________________
> greybus-dev mailing list
> greybus-dev@lists.linaro.org
> https://lists.linaro.org/mailman/listinfo/greybus-dev
> 

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Matthew Wilcox]

On Mon, Aug 30, 2021 at 02:33:05PM +0200, Johan Hovold wrote:
> On Mon, Aug 30, 2021 at 01:16:07PM +0100, Matthew Wilcox wrote:
> > On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
> > > Whether the API is better is debatable. As I said, almost no drivers use
> > > the new XArray interface, and perhaps partly because the new interface
> > > isn't as intuitive as has been claimed (e.g. xa_load() instead of
> > > ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
> > > I know.
> > 
> > I can't just slap a 'deprecated' attribute on it.  That'll cause a
> > storm of warnings.  What would you suggest I do to warn people that
> > this interface is deprecated and I would like to remove it?
> 
> I'd at least expect a suggestion in the IDR documentation to consider
> using XArray instead.

Fair enough.

+The IDR interface is deprecated; please use the `XArray`_ instead.

Just running that through htmldocs to make sure I've got the syntax
right, and then I'll commit it.

> > Why do you think that idr_find() is more intuitive than xa_load()?
> > The 'find' verb means that you search for something.  But it doesn't
> > search for anything; it just returns the pointer at that index.
> > 'find' should return the next non-NULL pointer at-or-above a given
> > index.
> 
> We're looking up a minor number which may or may not exist. "Find" (or
> "lookup" or "search") seems to describe this much better than "load"
> (even if that may better reflect the implementation of XArray).

It's not the _implementation_ that it fits, it's the _idiom_.
The implementation is a lookup in a trie.  The idiom of the XArray
is that it's a sparse array, and so it's a load.

> And no, I would not expect a find implementation to return the next
> entry if the requested entry does not exist (and neither does idr_find()
> or radix_tree_lookup()).

Oh dear.  You've been corrupted by the bad naming of the IDR functions
;-(

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Mon, Aug 30, 2021 at 08:20:25AM -0500, Alex Elder wrote:

> I have been offering review feedback on this patch for three reasons:
> 
> - First, because I think the intended change does no real harm to the
>   Greybus code, and in a small way actually simplifies it.

You leave out that we've already seen three versions of the patch that
broke things in various ways and that there was still work to be done
with respect to the commit message and verifying the locking. That's all
real costs that someone needs to bear.

> - Because I wanted to encourage Fabio's efforts to be part of the
>   Linux contributor community.

Helping new contributers that for example have run into a bug or need
some assistance adding a new feature that they themselves have use for
is one thing.

I'm not so sure we're helping either newcomers or Linux long term by
inventing work for an already strained community however.

[ This is more of a general comment and of course in no way a critique
  against Fabio or a claim that the XArray conversions are pointless. ]

> - Because I suspected that Matthew's long-term intention was to
>   replace IDR/IDA use with XArray, so this would represent an early
>   conversion.

That could be a valid motivation for the change indeed (since the
efficiency arguments are irrelevant in this case), but I could not find
any indications that there has been an agreement to deprecate the
current interfaces.

Last time around I think there was even push-back to convert IDR/IDA to
use XArray internally instead (but I may misremember).

> The Greybus code is generally good, but that doesn't mean it can't
> evolve.  It gets very little patch traffic, so I don't consider small
> changes like this "useless churn."  The Greybus code is held up as an
> example of Linux kernel code that can be safely modified, and I think
> it's actively promoted as a possible source of new developer tasks
> (e.g. for Outreachy).

Since most people can't really test their changes to Greybus perhaps it
isn't the best example of code that can be safely modified. But yeah,
parts of it are still in staging and, yes, staging has been promoted as
place were some churn is accepted.
 
Johan

Re: [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Mon, Aug 30, 2021 at 02:31:35PM +0100, Matthew Wilcox wrote:
> On Mon, Aug 30, 2021 at 02:33:05PM +0200, Johan Hovold wrote:
> > On Mon, Aug 30, 2021 at 01:16:07PM +0100, Matthew Wilcox wrote:
> > > On Mon, Aug 30, 2021 at 01:52:48PM +0200, Johan Hovold wrote:
> > > > Whether the API is better is debatable. As I said, almost no drivers use
> > > > the new XArray interface, and perhaps partly because the new interface
> > > > isn't as intuitive as has been claimed (e.g. xa_load() instead of
> > > > ida_find()). And IDR/IDA isn't marked/documented as deprecated as far as
> > > > I know.

> > > Why do you think that idr_find() is more intuitive than xa_load()?
> > > The 'find' verb means that you search for something.  But it doesn't
> > > search for anything; it just returns the pointer at that index.
> > > 'find' should return the next non-NULL pointer at-or-above a given
> > > index.
> > 
> > We're looking up a minor number which may or may not exist. "Find" (or
> > "lookup" or "search") seems to describe this much better than "load"
> > (even if that may better reflect the implementation of XArray).
> 
> It's not the _implementation_ that it fits, it's the _idiom_.
> The implementation is a lookup in a trie.  The idiom of the XArray
> is that it's a sparse array, and so it's a load.

Ok, but it still stands out in the conversions since it is in no way
obvious that idr_find() should be replaced by xa_load() from just
looking at the diff. You need to look up the interface for that.

> > And no, I would not expect a find implementation to return the next
> > entry if the requested entry does not exist (and neither does idr_find()
> > or radix_tree_lookup()).
> 
> Oh dear.  You've been corrupted by the bad naming of the IDR functions
> ;-(

Heh. Don't flatter yourself. Just look up any text book on data
structures.

Johan

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Alex Elder]

On 8/31/21 3:07 AM, Johan Hovold wrote:
> On Mon, Aug 30, 2021 at 08:20:25AM -0500, Alex Elder wrote:
> 
>> I have been offering review feedback on this patch for three reasons:
>>
>> - First, because I think the intended change does no real harm to the
>>    Greybus code, and in a small way actually simplifies it.
> 
> You leave out that we've already seen three versions of the patch that
> broke things in various ways and that there was still work to be done
> with respect to the commit message and verifying the locking. That's all
> real costs that someone needs to bear.

This is true.  But it's separate from my reason for doing it,
and unrelated to the suggested change.

>> - Because I wanted to encourage Fabio's efforts to be part of the
>>    Linux contributor community.
> 
> Helping new contributers that for example have run into a bug or need
> some assistance adding a new feature that they themselves have use for
> is one thing.
> 
> I'm not so sure we're helping either newcomers or Linux long term by
> inventing work for an already strained community however.
> 
> [ This is more of a general comment and of course in no way a critique
>    against Fabio or a claim that the XArray conversions are pointless. ]

Yes, yours is a general comment.  But I would characterize
this as Fabio "scratching an itch" rather than "inventing
new work."  The strained community needs more helpers, and
they don't suddenly appear fully-formed; they need to be
cultivated.  There's a balance to strike between "I see
you need a little guidance here" and "go away and come
back when you know how to do it right."

In any case, I don't disagree with your general point, but
we seem to view this particular instance differently.

>> - Because I suspected that Matthew's long-term intention was to
>>    replace IDR/IDA use with XArray, so this would represent an early
>>    conversion.
> 
> That could be a valid motivation for the change indeed (since the
> efficiency arguments are irrelevant in this case), but I could not find
> any indications that there has been an agreement to deprecate the
> current interfaces.
> 
> Last time around I think there was even push-back to convert IDR/IDA to
> use XArray internally instead (but I may misremember).
> 
>> The Greybus code is generally good, but that doesn't mean it can't
>> evolve.  It gets very little patch traffic, so I don't consider small
>> changes like this "useless churn."  The Greybus code is held up as an
>> example of Linux kernel code that can be safely modified, and I think
>> it's actively promoted as a possible source of new developer tasks
>> (e.g. for Outreachy).
> 
> Since most people can't really test their changes to Greybus perhaps it
> isn't the best example of code that can be safely modified. But yeah,
> parts of it are still in staging and, yes, staging has been promoted as
> place were some churn is accepted.

Testing Greybus code is a problem.  *That* would be something useful
for people to help fix.

					-Alex

>   
> Johan
> 

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

On Tuesday, August 31, 2021 10:07:38 AM CEST Johan Hovold wrote:
> On Mon, Aug 30, 2021 at 08:20:25AM -0500, Alex Elder wrote:
> 
> > I have been offering review feedback on this patch for three reasons:
> > 
> > - First, because I think the intended change does no real harm to the
> >   Greybus code, and in a small way actually simplifies it.
> 
> You leave out that we've already seen three versions of the patch that
> broke things in various ways and that there was still work to be done
> with respect to the commit message and verifying the locking. That's all
> real costs that someone needs to bear.
> 
> > - Because I wanted to encourage Fabio's efforts to be part of the
> >   Linux contributor community.

I really appreciated it, thank you so much Alex.

> Helping new contributers that for example have run into a bug or need
> some assistance adding a new feature that they themselves have use for
> is one thing.
> 
> I'm not so sure we're helping either newcomers or Linux long term by
> inventing work for an already strained community however.
> 
> [ This is more of a general comment and of course in no way a critique
>   against Fabio or a claim that the XArray conversions are pointless. ]
> 
> > - Because I suspected that Matthew's long-term intention was to
> >   replace IDR/IDA use with XArray, so this would represent an early
> >   conversion.

I am pretty sure that Mathew desires that people convert as much as possible 
code from IDR to XArray. You had his confirmation in this thread along with 
the link to the old message I have provided. However you and Alex are the 
maintainers, not Matthew. I must respect your POV.

> That could be a valid motivation for the change indeed (since the
> efficiency arguments are irrelevant in this case), but I could not find
> any indications that there has been an agreement to deprecate the
> current interfaces.
> 
> Last time around I think there was even push-back to convert IDR/IDA to
> use XArray internally instead (but I may misremember).
> 
> > The Greybus code is generally good, but that doesn't mean it can't
> > evolve.  It gets very little patch traffic, so I don't consider small
> > changes like this "useless churn."  The Greybus code is held up as an
> > example of Linux kernel code that can be safely modified, and I think
> > it's actively promoted as a possible source of new developer tasks
> > (e.g. for Outreachy).
> 
> Since most people can't really test their changes to Greybus perhaps it
> isn't the best example of code that can be safely modified. But yeah,
> parts of it are still in staging and, yes, staging has been promoted as
> place were some churn is accepted.
>  
> Johan

I cannot test my changes to Greybus, but I think that trivial changes are 
just required to build. To stay on the safe side I had left those 
mutex_lock() around xa_load(). I wasn't sure about it, but since the original 
code had the Mutexes I thought it wouldn't hurt to leave them there.

As it was conceived it was a "trivial" patch that didn't" need any tests, 
IMO. Greg has said, more than once, that "trivial" patches are "more than
welcome" in drivers/staging, so I took his words applicable to staging/
greybus too. 

Until the locks were there, my patch was indeed a "trivial" patch. I know the 
XArray API enough to do this task because I've already worked on unisys/
visorhba and you may bet I had not the hardware to test that patch. 
Furthermore, it was much more complex work than what I've done in staging/
greybus. After some time, due to the lack of responses from Unisys 
maintainers he took the responsibility to apply my patch. He knew that it was 
not tested, so he wrote "let's see what it breaks :)". 

I'm very sorry to bother you. I don't really know in the deep how Greybus 
works and I don't know how to write drivers because at the moment I prefer  
to spend my (very limited) time to learn core subsystems (process management 
and the schedulers above all). But while learning, I also want to give back 
something to the kernel and its Community. I think that little works on 
staging are the best way to accomplish this goal.

I was wrong in assuming that trivial patches to Greybus are welcome as they 
are for other drivers.

Best regards,

Fabio

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Tue, Aug 31, 2021 at 05:42:20AM -0500, Alex Elder wrote:
> On 8/31/21 3:07 AM, Johan Hovold wrote:
> > On Mon, Aug 30, 2021 at 08:20:25AM -0500, Alex Elder wrote:
> > 
> >> I have been offering review feedback on this patch for three reasons:
> >>
> >> - First, because I think the intended change does no real harm to the
> >>    Greybus code, and in a small way actually simplifies it.
> > 
> > You leave out that we've already seen three versions of the patch that
> > broke things in various ways and that there was still work to be done
> > with respect to the commit message and verifying the locking. That's all
> > real costs that someone needs to bear.
> 
> This is true.  But it's separate from my reason for doing it,
> and unrelated to the suggested change.

I was perhaps reading the "no harm" bit too literally, but I'd say it
very much applies to the suggested change (which was the example I
used).

> >> - Because I wanted to encourage Fabio's efforts to be part of the
> >>    Linux contributor community.
> > 
> > Helping new contributers that for example have run into a bug or need
> > some assistance adding a new feature that they themselves have use for
> > is one thing.
> > 
> > I'm not so sure we're helping either newcomers or Linux long term by
> > inventing work for an already strained community however.
> > 
> > [ This is more of a general comment and of course in no way a critique
> >    against Fabio or a claim that the XArray conversions are pointless. ]
> 
> Yes, yours is a general comment.  But I would characterize
> this as Fabio "scratching an itch" rather than "inventing
> new work."

Just to clarify again, my comment was in no way directed at Fabio or
not necessarily even at the XArray conversions if it indeed means that
IDR/IDA can be removed.

> The strained community needs more helpers, and
> they don't suddenly appear fully-formed; they need to be
> cultivated.  There's a balance to strike between "I see
> you need a little guidance here" and "go away and come
> back when you know how to do it right."

And here's where I think the invented work bit really comes in. I have
no problem helping someone fix a real problem or add a feature they
need, but spending hours on reviewing changes that in the end no one
needs I find a bit frustrating. My guess is that the former is also more
likely to generate long-term contributors than teaching people C on
made-up tasks or asking them to silence checkpatch.pl indentation
warnings.

> In any case, I don't disagree with your general point, but
> we seem to view this particular instance differently.

Perhaps I shouldn't have brought up the general issue in this case. If
there was a general consensus that IDR was going away and some
precedence outside of staging that could be used as a model, then this
change would be fine.

Johan

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Johan Hovold]

On Tue, Aug 31, 2021 at 01:50:05PM +0200, Fabio M. De Francesco wrote:
> On Tuesday, August 31, 2021 10:07:38 AM CEST Johan Hovold wrote:

> > Since most people can't really test their changes to Greybus perhaps it
> > isn't the best example of code that can be safely modified. But yeah,
> > parts of it are still in staging and, yes, staging has been promoted as
> > place were some churn is accepted.

> I cannot test my changes to Greybus, but I think that trivial changes are 
> just required to build. To stay on the safe side I had left those 
> mutex_lock() around xa_load(). I wasn't sure about it, but since the original 
> code had the Mutexes I thought it wouldn't hurt to leave them there.

But if you weren't sure that your patch was correct, you can't also
claim that it was trivial. Patches dealing with locking and concurrency
usually are not.

I too had go look up the XArray interface and review the Greybus uart
code (which is broken and that doesn't make it easier for any of us).

So no, this wasn't trivial, it carries a cost and should therefore in
the end also have some gain. And what that was wasn't clear from the
commit message (since any small efficiency gain is irrelevant in this
case).

Sorry you got stuck in the middle. Perhaps you can see it as a
first-hand experience of some of the trade offs involved when doing
kernel development.

And remember that a good commit message describing the motivation for
the change (avoiding boiler-plate marketing terms) is a good start if
you want to get your patches accepted.

Johan

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Alex Elder]

On 8/31/21 6:50 AM, Fabio M. De Francesco wrote:
> I was wrong in assuming that trivial patches to Greybus are welcome as they 
> are for other drivers.

This is not a correct statement.

But as Johan pointed out, even for a trivial patch if you
must understand the consequences of what the change does.
If testing is not possible, you must work extra hard to
ensure your patch is correct.

In the first (or an early) version of your patch I pointed
out a bug.  Later, I suggested
 the lock might not be necessary
and asked you to either confirm
 it was or explain why it was
not, but you didn't do that.


I agree that the change appeared trivial, and even sensible,
but even trivial patches must result in correct code.  And
all patches should have good and complete explanations.

					-Alex

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

On Wednesday, September 1, 2021 2:09:16 PM CEST Alex Elder wrote:
> On 8/31/21 6:50 AM, Fabio M. De Francesco wrote:
> > I was wrong in assuming that trivial patches to Greybus are welcome as 
they 
> > are for other drivers.
> 
> This is not a correct statement.

Yes, I agree: it's not a correct statement. Please let me explain what I was 
trying to convey with that consideration...

The Mutexes were there around idr_find() and I decided to leave the code as 
it was. Who am I to say that they are not necessary? I must stay on the safe 
side. First because I don't know how the drivers work (can that critical 
section really be entered by different threads that could possibly share the 
gb_tty that is retrieved by xa_load()? Even if xa_load() always give you back 
the right gb_tty, how do I know if in the while other threads change its 
fields or destroy the object? I guess I should stay on the safe side and 
leave the Mutexes there, exactly were they were.

These are the reason why v1 was indeed a trivial patch. But v2 *was not* 
because you wrote that you were pretty sure they were unneeded and you asked 
me to leave them or remove them and in either case I had to provide a reason 
why. 

I guess that in v1 I should not provide a reason why they are still there, as 
well as I don't have to provide any reason on why the greybus code (line by 
line) is as it is: it is out of the scope of my patch. Am I wrong?

Your note about the possibility that the mutexes could be removed pushed me 
beyond what I need to know to accomplish the intended task. 

Anyway I tried to reason about it. I perfectly know what is required to 
protect critical sections of code, but I don't know how drivers work; I mean 
I don't know whether or not different threads that run concurrently could 
really interfere in that specific section. This is because I simply reason in 
terms of general rules of protection of critical section but I really don't 
know how Greybus works or (more in general) how drivers work.

I still think that if I stayed within the bounds of my original purpose I 
didn't have to reason about this topic and that the v1 patch was trivial.
v2 was not!

I'm sorry because I'm still not sure if I was able to conveyed what I thought 
and still think.

> But as Johan pointed out, even for a trivial patch if you
> must understand the consequences of what the change does.
> If testing is not possible, you must work extra hard to
> ensure your patch is correct.

Again, I don't see any possible harm with the mutexes in place :)
 
> In the first (or an early) version of your patch I pointed
> out a bug.  Later, I suggested
>  the lock might not be necessary
> and asked you to either confirm
>  it was or explain why it was
> not, but you didn't do that.

This was beyond my knowledge and perhaps unnecessary (sorry if I insist on 
that :)).

> I agree that the change appeared trivial, and even sensible,
> but even trivial patches must result in correct code.  And
> all patches should have good and complete explanations.
>
>	- Alex

Is v2 correct with the mutexes restored where they were? I guess it is.

Thanks for you kind review and the time you spent for me. I appreciated it, 
seriously.

Fabio	

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Matthew Wilcox]

On Wed, Sep 01, 2021 at 03:56:20PM +0200, Fabio M. De Francesco wrote:
> Anyway I tried to reason about it. I perfectly know what is required to 
> protect critical sections of code, but I don't know how drivers work; I mean 
> I don't know whether or not different threads that run concurrently could 
> really interfere in that specific section. This is because I simply reason in 
> terms of general rules of protection of critical section but I really don't 
> know how Greybus works or (more in general) how drivers work.

From a quick look, it is indeed possible to get rid of the mutex.
If this were a high-performance path which needed to have many threads
simultaneously looking up the gb_tty, or it were core kernel code, I
would say that you should use kfree_rcu() to free gb_tty and then
you could replace the mutex_lock() on lookup with a rcu_read_lock().

Since this is low-performance and driver code, I think you're better off
simply doing this:

	xa_lock((&tty_minors);
	gb_tty = xa_load(&tty_minors, minor);
	... establish a refcount ...
	xa_unlock(&tty_minors);

EXCEPT ...

establishing a refcount currently involves taking a mutex.  So you can't
do that.  First, you have to convert the gb_tty mutex to a spinlock
(which looks fine to me), and then you can do this.  But this is where
you need to work with the driver authors to make sure it's OK.

Re: [greybus-dev] [PATCH v4] staging: greybus: Convert uart.c from IDR to XArray

[Fabio M. De Francesco]

On Wednesday, September 1, 2021 4:29:26 PM CEST Matthew Wilcox wrote:
> On Wed, Sep 01, 2021 at 03:56:20PM +0200, Fabio M. De Francesco wrote:
> > Anyway I tried to reason about it. I perfectly know what is required to 
> > protect critical sections of code, but I don't know how drivers work; I 
mean 
> > I don't know whether or not different threads that run concurrently could 
> > really interfere in that specific section. This is because I simply 
reason in 
> > terms of general rules of protection of critical section but I really 
don't 
> > know how Greybus works or (more in general) how drivers work.
> 
> From a quick look, it is indeed possible to get rid of the mutex.
> If this were a high-performance path which needed to have many threads
> simultaneously looking up the gb_tty, or it were core kernel code, I
> would say that you should use kfree_rcu() to free gb_tty and then
> you could replace the mutex_lock() on lookup with a rcu_read_lock().
> 
> Since this is low-performance and driver code, I think you're better off
> simply doing this:
> 
> 	xa_lock((&tty_minors);
> 	gb_tty = xa_load(&tty_minors, minor);
> 	... establish a refcount ...
> 	xa_unlock(&tty_minors);
> 
> EXCEPT ...
> 
> establishing a refcount currently involves taking a mutex.  So you can't
> do that.  First, you have to convert the gb_tty mutex to a spinlock
> (which looks fine to me), and then you can do this.  But this is where
> you need to work with the driver authors to make sure it's OK.

Dear Matthew,

I think that I understand your suggestion and, as far as my experience with 
concurrency in userspace may have any relevance here, I often use reference 
counting with objects that are shared by multiple threads.

Unfortunately, this is not the point. The *real* issue is that I am not able 
to provide good reasons for doing IDR to XArray conversions in Greybus code. 
I tried to provide some sort of motivation by using your own words that I 
still remember from a message you sent a couple of months ago: 

More or less you wrote:

"The abstract data type XArray is more memory-efficient, parallelisable, and 
cache friendly. It takes advantage of RCU to perform lookups without locking. 
Furthermore, IDR is deprecated because XArray has a better (cleaner and more 
consistent) API.".

I can reason on the "cleaner and more consistent API" and for what I 
understand from the grand design of the implementation of XArray I may also 
attempt to discuss some of the other parts of the above-mentioned statement.

Anyway I must respect the point of view of Johan H.: "And remember that a 
good commit message describing the motivation for the change (avoiding 
boiler-plate marketing terms) is a good start if you want to get your patches 
accepted.". That's absolutely fair and, I say that seriously, I must follow  
this rule. Since I'm not able to do that I understand that I have to desist.

If it depended on me I'd like to convert as many possible drivers from IDR to 
XArray, but it seems that many maintainers don't care (even if the work was 
perfect in every detail since v1). I guess they have their reason to think 
that the trade-off isn't even worth the time to review. I'm yet not sure that 
IDA to XArray is worth as much as IDR to XArray is. But for the latter I 
would bet it is.

Please, nobody should misunderstand me. I know that I'm going well beyond 
what my experience may permit to say about this matter. I'm just expressing 
my opinion with no intentions to push anybody in any direction. Please 
forgive me if this is what it may seem to the readers that are following this 
thread.

Thanks,

Fabio