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[] = {
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
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
[ 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
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.
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
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
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
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
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
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
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
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
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
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
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.
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
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 ;-(
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
-
Alex Elder -
Fabio M. De Francesco -
Johan Hovold -
Matthew Wilcox