| Message ID | 1359822572-26009-10-git-send-email-acourbot@nvidia.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Sat, Feb 2, 2013 at 5:29 PM, Alexandre Courbot <acourbot@nvidia.com> wrote: > Parse the list of chips to find the descriptor corresponding to a GPIO > number instead of directly picking the entry of the global gpio_desc[] > array, which is due to be removed. > > This turns the complexity of converting a GPIO number into a descriptor > from O(1) to O(n) where n is the number of GPIO chips in the system. > Since n is ought to be small anyway, there should be no noticeable > performance impact. Moreover, GPIO users who care for speed already have > implemented their own gpio_get_value() and gpio_set_value() with a > fast path for the GPIO numbers that matter and this change does not > affect such use cases. > > The descriptor-based GPIO API, due to be introduced soon, will make this > lookup unnecessary. > > Signed-off-by: Alexandre Courbot <acourbot@nvidia.com> OK it's a nice stepping stone. Reviewed-by: Linus Walleij <linus.walleij@linaro.org> Yours, Linus Walleij
On Sun, 3 Feb 2013 01:29:31 +0900, Alexandre Courbot <acourbot@nvidia.com> wrote: > Parse the list of chips to find the descriptor corresponding to a GPIO > number instead of directly picking the entry of the global gpio_desc[] > array, which is due to be removed. > > This turns the complexity of converting a GPIO number into a descriptor > from O(1) to O(n) where n is the number of GPIO chips in the system. > Since n is ought to be small anyway, there should be no noticeable > performance impact. Moreover, GPIO users who care for speed already have > implemented their own gpio_get_value() and gpio_set_value() with a > fast path for the GPIO numbers that matter and this change does not > affect such use cases. > > The descriptor-based GPIO API, due to be introduced soon, will make this > lookup unnecessary. I'm actually going to NAK this one. This is a hot path. Having a O(1) lookup from gpio number to gpio desc is important. I know you want to be rid of the gpio_desc table entirely, but in this case I think it is warranted. However, you can change the gpio_desc table to be a table of pointers to gpio_descs instead of a table of gpio_descs. That would save a lot of memory since unused GPIOs wouldn't have gpio_descs associated with them. It is also the mechanism used by the IRQ subsystem. So, it makes sense for the primary gpio_chip lookup to be the list, but the table needs to stick around as a secondary lookup. g. > > Signed-off-by: Alexandre Courbot <acourbot@nvidia.com> > --- > drivers/gpio/gpiolib.c | 19 +++++++++++++++---- > 1 file changed, 15 insertions(+), 4 deletions(-) > > diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c > index 9599b9a..0247c48 100644 > --- a/drivers/gpio/gpiolib.c > +++ b/drivers/gpio/gpiolib.c > @@ -122,10 +122,21 @@ static int gpio_chip_hwgpio(const struct gpio_desc *desc) > */ > static struct gpio_desc *gpio_to_desc(unsigned gpio) > { > - if (WARN(!gpio_is_valid(gpio), "invalid GPIO %d\n", gpio)) > - return NULL; > - else > - return &gpio_desc[gpio]; > + struct gpio_chip *chip; > + > + list_for_each_entry(chip, &gpio_chips, list) { > + int gpio_min = chip->base; > + int gpio_max = gpio_min + chip->ngpio; > + if (gpio >= gpio_min && gpio < gpio_max) > + return &chip->desc[gpio - gpio_min]; > + else if (gpio < gpio_min) > + /* gpio_chips are ordered by base, so we won't get any > + * hit if we arrive here... */ > + break; > + } > + > + pr_warn("%s: no registered chip to handle GPIO %d\n", __func__, gpio); > + return NULL; > } > > /** > -- > 1.8.1.1 >
On Sat, Feb 9, 2013 at 6:58 PM, Grant Likely <grant.likely@secretlab.ca> wrote: > I'm actually going to NAK this one. This is a hot path. Having a O(1) > lookup from gpio number to gpio desc is important. I know you want to be > rid of the gpio_desc table entirely, but in this case I think it is > warranted. However, you can change the gpio_desc table to be a table of > pointers to gpio_descs instead of a table of gpio_descs. That would save > a lot of memory since unused GPIOs wouldn't have gpio_descs associated > with them. It is also the mechanism used by the IRQ subsystem. That would work - what I don't like is that it still ends being a fixed-size static array that is not necessarily tailored to the platform's needs. But I understand you don't want to punish the users of the integer-based API, even though the penalty should really be neglectable here. Well, maybe I can try to come again with this once everybody uses GPIO descriptors instead of integers. ;) Alex.
On Sat, Feb 9, 2013 at 2:21 PM, Alexandre Courbot <acourbot@nvidia.com> wrote: > On Sat, Feb 9, 2013 at 6:58 PM, Grant Likely <grant.likely@secretlab.ca> wrote: >> I'm actually going to NAK this one. This is a hot path. Having a O(1) >> lookup from gpio number to gpio desc is important. I know you want to be >> rid of the gpio_desc table entirely, but in this case I think it is >> warranted. However, you can change the gpio_desc table to be a table of >> pointers to gpio_descs instead of a table of gpio_descs. That would save >> a lot of memory since unused GPIOs wouldn't have gpio_descs associated >> with them. It is also the mechanism used by the IRQ subsystem. > > That would work - what I don't like is that it still ends being a > fixed-size static array that is not necessarily tailored to the > platform's needs. But I understand you don't want to punish the users > of the integer-based API, even though the penalty should really be > neglectable here. > > Well, maybe I can try to come again with this once everybody uses GPIO > descriptors instead of integers. ;) Yes, when everyone uses descriptor handles the problem goes away. Until then we can just make the table fairly large. If it is pointers to descs instead of the descs themselves then the memory cost really isn't that significant. We could also make the table itself grow dynamically, but I don't think there is evidence suggesting that is needed. Thomas tried to do the same thing with the irq desc table and found the resulting code was far more convoluted than he wanted to support. g.
diff --git a/drivers/gpio/gpiolib.c b/drivers/gpio/gpiolib.c index 9599b9a..0247c48 100644 --- a/drivers/gpio/gpiolib.c +++ b/drivers/gpio/gpiolib.c @@ -122,10 +122,21 @@ static int gpio_chip_hwgpio(const struct gpio_desc *desc) */ static struct gpio_desc *gpio_to_desc(unsigned gpio) { - if (WARN(!gpio_is_valid(gpio), "invalid GPIO %d\n", gpio)) - return NULL; - else - return &gpio_desc[gpio]; + struct gpio_chip *chip; + + list_for_each_entry(chip, &gpio_chips, list) { + int gpio_min = chip->base; + int gpio_max = gpio_min + chip->ngpio; + if (gpio >= gpio_min && gpio < gpio_max) + return &chip->desc[gpio - gpio_min]; + else if (gpio < gpio_min) + /* gpio_chips are ordered by base, so we won't get any + * hit if we arrive here... */ + break; + } + + pr_warn("%s: no registered chip to handle GPIO %d\n", __func__, gpio); + return NULL; } /**
Parse the list of chips to find the descriptor corresponding to a GPIO number instead of directly picking the entry of the global gpio_desc[] array, which is due to be removed. This turns the complexity of converting a GPIO number into a descriptor from O(1) to O(n) where n is the number of GPIO chips in the system. Since n is ought to be small anyway, there should be no noticeable performance impact. Moreover, GPIO users who care for speed already have implemented their own gpio_get_value() and gpio_set_value() with a fast path for the GPIO numbers that matter and this change does not affect such use cases. The descriptor-based GPIO API, due to be introduced soon, will make this lookup unnecessary. Signed-off-by: Alexandre Courbot <acourbot@nvidia.com> --- drivers/gpio/gpiolib.c | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-)