[patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[David Brownell]

From: Anton Vorontsov <avorontsov@ru.mvista.com>

If gpio_chip->base is negative during registration, gpiolib performs
dynamic base allocation. This is useful for devices that aren't always
present, such as GPIOs on hotplugged devices rather than mainboards.
(This behavior was previously specified but not implemented.)

To avoid using any numbers that may have been explicitly assigned but
not yet registered, this dynamic allocation assigns GPIO numbers from
the biggest number on down, instead of from the smallest on up.

Signed-off-by: Anton Vorontsov <avorontsov@ru.mvista.com>
Signed-off-by: David Brownell <dbrownell@users.sourceforge.net>
---
 drivers/gpio/gpiolib.c |   52 ++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 45 insertions(+), 7 deletions(-)

--- g26.orig/drivers/gpio/gpiolib.c	2008-03-13 14:41:52.000000000 -0700
+++ g26/drivers/gpio/gpiolib.c	2008-03-13 14:51:50.000000000 -0700
@@ -80,6 +80,33 @@ static inline struct gpio_chip *gpio_to_
 	return gpio_desc[gpio].chip;
 }
 
+/* dynamic allocation of GPIOs, e.g. on a hotplugged device */
+static int gpiochip_find_base(int ngpio)
+{
+	int i;
+	int spare = 0;
+	int base = -ENOSPC;
+
+	for (i = ARCH_NR_GPIOS - 1; i >= 0 ; i--) {
+		struct gpio_chip *chip = gpio_desc[i].chip;
+
+		if (!chip) {
+			spare++;
+			if (spare == ngpio) {
+				base = i;
+				break;
+			}
+		} else {
+			spare = 0;
+			i -= chip->ngpio - 1;
+		}
+	}
+
+	if (gpio_is_valid(base))
+		pr_debug("%s: found new base at %d\n", __func__, base);
+	return base;
+}
+
 /**
  * gpiochip_add() - register a gpio_chip
  * @chip: the chip to register, with chip->base initialized
@@ -88,38 +115,49 @@ static inline struct gpio_chip *gpio_to_
  * Returns a negative errno if the chip can't be registered, such as
  * because the chip->base is invalid or already associated with a
  * different chip.  Otherwise it returns zero as a success code.
+ *
+ * If chip->base is negative, this requests dynamic assignment of
+ * a range of valid GPIOs.
  */
 int gpiochip_add(struct gpio_chip *chip)
 {
 	unsigned long	flags;
 	int		status = 0;
 	unsigned	id;
+	int		base = chip->base;
 
-	/* NOTE chip->base negative is reserved to mean a request for
-	 * dynamic allocation.  We don't currently support that.
-	 */
-
-	if (chip->base < 0 || !gpio_is_valid(chip->base  + chip->ngpio)) {
+	if ((!gpio_is_valid(base) || !gpio_is_valid(base + chip->ngpio))
+			&& base >= 0) {
 		status = -EINVAL;
 		goto fail;
 	}
 
 	spin_lock_irqsave(&gpio_lock, flags);
 
+	if (base < 0) {
+		base = gpiochip_find_base(chip->ngpio);
+		if (base < 0) {
+			status = base;
+			goto fail_unlock;
+		}
+		chip->base = base;
+	}
+
 	/* these GPIO numbers must not be managed by another gpio_chip */
-	for (id = chip->base; id < chip->base + chip->ngpio; id++) {
+	for (id = base; id < base + chip->ngpio; id++) {
 		if (gpio_desc[id].chip != NULL) {
 			status = -EBUSY;
 			break;
 		}
 	}
 	if (status == 0) {
-		for (id = chip->base; id < chip->base + chip->ngpio; id++) {
+		for (id = base; id < base + chip->ngpio; id++) {
 			gpio_desc[id].chip = chip;
 			gpio_desc[id].flags = 0;
 		}
 	}
 
+fail_unlock:
 	spin_unlock_irqrestore(&gpio_lock, flags);
 fail:
 	/* failures here can mean systems won't boot... */

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[Andrew Morton]

On Thu, 13 Mar 2008 14:49:53 -0800
David Brownell <david-b@pacbell.net> wrote:

> From: Anton Vorontsov <avorontsov@ru.mvista.com>
> 
> If gpio_chip->base is negative during registration, gpiolib performs
> dynamic base allocation. This is useful for devices that aren't always
> present, such as GPIOs on hotplugged devices rather than mainboards.
> (This behavior was previously specified but not implemented.)
> 
> To avoid using any numbers that may have been explicitly assigned but
> not yet registered, this dynamic allocation assigns GPIO numbers from
> the biggest number on down, instead of from the smallest on up.
>
> ..
>
> +/* dynamic allocation of GPIOs, e.g. on a hotplugged device */
> +static int gpiochip_find_base(int ngpio)
> +{
> +	int i;
> +	int spare = 0;
> +	int base = -ENOSPC;
> +
> +	for (i = ARCH_NR_GPIOS - 1; i >= 0 ; i--) {
> +		struct gpio_chip *chip = gpio_desc[i].chip;
> +
> +		if (!chip) {
> +			spare++;
> +			if (spare == ngpio) {
> +				base = i;
> +				break;
> +			}
> +		} else {
> +			spare = 0;
> +			i -= chip->ngpio - 1;
> +		}
> +	}
> +
> +	if (gpio_is_valid(base))
> +		pr_debug("%s: found new base at %d\n", __func__, base);
> +	return base;
> +}

hm.  I suppose that if someone want a huge number of GPIOs then we can
convert this to a bitmap or an IDR tree easily enough.

Shouldn't ARCH_NR_GPIOS be CONFIG_NR_GPIOS?

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[David Brownell]

On Thursday 13 March 2008, Andrew Morton wrote:

> hm.  I suppose that if someone want a huge number of GPIOs then we can
> convert this to a bitmap or an IDR tree easily enough.

Actually, I tried IDRs for a while and they broke platforms
which needed to initialize and use GPIOs early: before kmalloc
would work.  A real PITA that was -- and slow too.


> Shouldn't ARCH_NR_GPIOS be CONFIG_NR_GPIOS?

No more than NR_IRQS is settable via Kconfig.  And for
rather similar reasons.  :)

- Dave

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[Andrew Morton]

On Thu, 13 Mar 2008 15:18:58 -0800
David Brownell <david-b@pacbell.net> wrote:

> On Thursday 13 March 2008, Andrew Morton wrote:
> 
> > hm.  I suppose that if someone want a huge number of GPIOs then we can
> > convert this to a bitmap or an IDR tree easily enough.
> 
> Actually, I tried IDRs for a while and they broke platforms
> which needed to initialize and use GPIOs early: before kmalloc
> would work.  A real PITA that was -- and slow too.

If IDRs were slow, that linear search will be glacial.

> 
> > Shouldn't ARCH_NR_GPIOS be CONFIG_NR_GPIOS?
> 
> No more than NR_IRQS is settable via Kconfig.  And for
> rather similar reasons.  :)

What are those reasons?

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[Anton Vorontsov]

On Thu, Mar 13, 2008 at 04:28:03PM -0700, Andrew Morton wrote:
> On Thu, 13 Mar 2008 15:18:58 -0800
> David Brownell <david-b@pacbell.net> wrote:
> 
> > On Thursday 13 March 2008, Andrew Morton wrote:
> > 
> > > hm.  I suppose that if someone want a huge number of GPIOs then we can
> > > convert this to a bitmap or an IDR tree easily enough.
> > 
> > Actually, I tried IDRs for a while and they broke platforms
> > which needed to initialize and use GPIOs early: before kmalloc
> > would work.  A real PITA that was -- and slow too.
> 
> If IDRs were slow, that linear search will be glacial.

Heh.. FWIW, I didn't notice any slowness of that linear search.

I didn't bother to try anything more complicated than linear search
for mere 256 GPIOs. I doubt that IDRs will pour out into any
measurable win even for something like 1024 GPIOs.

-- 
Anton Vorontsov
email: cbouatmailru@gmail.com
irc://irc.freenode.net/bd2

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[David Brownell]

On Thursday 13 March 2008, Andrew Morton wrote:
> On Thu, 13 Mar 2008 15:18:58 -0800
> David Brownell <david-b@pacbell.net> wrote:
> 
> > On Thursday 13 March 2008, Andrew Morton wrote:
> > 
> > > hm.  I suppose that if someone want a huge number of GPIOs then we can
> > > convert this to a bitmap or an IDR tree easily enough.
> > 
> > Actually, I tried IDRs for a while and they broke platforms
> > which needed to initialize and use GPIOs early: before kmalloc
> > would work.  A real PITA that was -- and slow too.
> 
> If IDRs were slow, that linear search will be glacial.

The slowness of IDRs was needing to use them for the
routine lookups ... versus the current array index,
which costs a fraction of an instruction cycle and
doesn't need separate locks.

Or were you implying they should be used for something
other than mapping GPIO numbers to controllers/state?

- Dave

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[Andrew Morton]

On Thu, 13 Mar 2008 16:53:58 -0800 David Brownell <david-b@pacbell.net> wrote:

> On Thursday 13 March 2008, Andrew Morton wrote:
> > On Thu, 13 Mar 2008 15:18:58 -0800
> > David Brownell <david-b@pacbell.net> wrote:
> > 
> > > On Thursday 13 March 2008, Andrew Morton wrote:
> > > 
> > > > hm.  I suppose that if someone want a huge number of GPIOs then we can
> > > > convert this to a bitmap or an IDR tree easily enough.
> > > 
> > > Actually, I tried IDRs for a while and they broke platforms
> > > which needed to initialize and use GPIOs early: before kmalloc
> > > would work.  A real PITA that was -- and slow too.
> > 
> > If IDRs were slow, that linear search will be glacial.
> 
> The slowness of IDRs was needing to use them for the
> routine lookups ... versus the current array index,
> which costs a fraction of an instruction cycle and
> doesn't need separate locks.
> 
> Or were you implying they should be used for something
> other than mapping GPIO numbers to controllers/state?
> 

For dynamic allocation.  There should be no need for lookups outside
register/unregister.


Where did the CONFIG_NR_GPIOS discussion disappear to?

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[David Brownell]

On Thursday 13 March 2008, Andrew Morton wrote:
> > > > Actually, I tried IDRs for a while and they broke platforms
> > > > which needed to initialize and use GPIOs early: before kmalloc
> > > > would work.  A real PITA that was -- and slow too.
> > > 
> > > If IDRs were slow, that linear search will be glacial.
> > 
> > The slowness of IDRs was needing to use them for the
> > routine lookups ... versus the current array index,
> > which costs a fraction of an instruction cycle and
> > doesn't need separate locks.
> > 
> > Or were you implying they should be used for something
> > other than mapping GPIO numbers to controllers/state?
> 
> For dynamic allocation.  There should be no need for lookups outside
> register/unregister.

So -- a secondary data structure used only for allocation?
With the primary one as it is now? 

If allocation were a hotspot something like that might be
worth considering ... though such duplication is usually
error prone.  But it's not; such allocation is a rarity.


> Where did the CONFIG_NR_GPIOS discussion disappear to?
 
http://marc.info/?l=linux-kernel&m=120545979527097&w=2

I could maybe see a CONFIG_NR_EXTRA_GPIOS.

Re: [patch 2.6.25-rc5 1/2] gpiolib: dynamic gpio number allocation

[David Brownell]

On Thursday 13 March 2008, Andrew Morton wrote:

> > > Shouldn't ARCH_NR_GPIOS be CONFIG_NR_GPIOS?
> > 
> > No more than NR_IRQS is settable via Kconfig.  And for
> > rather similar reasons.  :)
> 
> What are those reasons?

Keeping a lid on the amount of space wasted by unused
table entries is one factor; it's an implementation
tradeoff.  In normal usage the number of IRQs (or GPIOs)
is defined by the board (or system) design, and there's
no real point to allowing more.

That said, NR_IRQS is kind of inflexible.  It's not easy
to provide board-specific overrides for cases like having
a few FPGAs or other external IRQ (or GPIO!) controllers
which chain IRQs and plug into those tables...

Both could use a way to extend a platform-defined minimum
to support a configurable number of external controllers.
Lacking that, both have somewhat ad-hoc solutions to make
sure board variants can be set up with the same kernel.
It basically boils down to making sure there are some extra
entries at end-of-table, and policies to allocate them.

- Dave