dm: Introduce device sequence numbering

In U-Boot it is pretty common to number devices from 0 and access them
on the command line using this numbering. While it may come to pass that
we will move away from this numbering, the possibility seems remote at
present.

Given that devices within a uclass will have an implied numbering, it
makes sense to build this into driver model as a core feature. The cost
is fairly small in terms of code and data space.

With each uclass having numbered devices we can ask for SPI port 0 or
serial port 1 and receive a single device.

Devices typically request a sequence number using aliases in the device
tree. These are resolved when the device is probed, to deal with conflicts.
Sequence numbers need not be sequential and holes are permitted.

At present there is no support for sequence numbers using static platform
data. It could easily be added to 'struct driver_info' if needed, but it
seems better to add features as we find a use for them, and the use of -1
to mean 'no sequence' makes the default value somewhat painful.

Signed-off-by: Simon Glass <sjg@chromium.org>
diff --git a/doc/driver-model/README.txt b/doc/driver-model/README.txt
index 907ff67..84d21cf 100644
--- a/doc/driver-model/README.txt
+++ b/doc/driver-model/README.txt
@@ -95,12 +95,16 @@
 You should see something like this:
 
     <...U-Boot banner...>
-    Running 14 driver model tests
+    Running 15 driver model tests
     Test: dm_test_autobind
     Test: dm_test_autoprobe
     Test: dm_test_children
     Test: dm_test_fdt
+    Device 'd-test': seq 3 is in use by 'b-test'
     Test: dm_test_fdt_pre_reloc
+    Test: dm_test_fdt_uclass_seq
+    Device 'd-test': seq 3 is in use by 'b-test'
+    Device 'a-test': seq 0 is in use by 'd-test'
     Test: dm_test_gpio
     sandbox_gpio: sb_gpio_get_value: error: offset 4 not reserved
     Test: dm_test_leak
@@ -339,6 +343,80 @@
 end of the enum there, then declare your uclass as above.
 
 
+Device Sequence Numbers
+-----------------------
+
+U-Boot numbers devices from 0 in many situations, such as in the command
+line for I2C and SPI buses, and the device names for serial ports (serial0,
+serial1, ...). Driver model supports this numbering and permits devices
+to be locating by their 'sequence'.
+
+Sequence numbers start from 0 but gaps are permitted. For example, a board
+may have I2C buses 0, 1, 4, 5 but no 2 or 3. The choice of how devices are
+numbered is up to a particular board, and may be set by the SoC in some
+cases. While it might be tempting to automatically renumber the devices
+where there are gaps in the sequence, this can lead to confusion and is
+not the way that U-Boot works.
+
+Each device can request a sequence number. If none is required then the
+device will be automatically allocated the next available sequence number.
+
+To specify the sequence number in the device tree an alias is typically
+used.
+
+aliases {
+	serial2 = "/serial@22230000";
+};
+
+This indicates that in the uclass called "serial", the named node
+("/serial@22230000") will be given sequence number 2. Any command or driver
+which requests serial device 2 will obtain this device.
+
+Some devices represent buses where the devices on the bus are numbered or
+addressed. For example, SPI typically numbers its slaves from 0, and I2C
+uses a 7-bit address. In these cases the 'reg' property of the subnode is
+used, for example:
+
+{
+	aliases {
+		spi2 = "/spi@22300000";
+	};
+
+	spi@22300000 {
+		#address-cells = <1>;
+		#size-cells = <1>;
+		spi-flash@0 {
+			reg = <0>;
+			...
+		}
+		eeprom@1 {
+			reg = <1>;
+		};
+	};
+
+In this case we have a SPI bus with two slaves at 0 and 1. The SPI bus
+itself is numbered 2. So we might access the SPI flash with:
+
+	sf probe 2:0
+
+and the eeprom with
+
+	sspi 2:1 32 ef
+
+These commands simply need to look up the 2nd device in the SPI uclass to
+find the right SPI bus. Then, they look at the children of that bus for the
+right sequence number (0 or 1 in this case).
+
+Typically the alias method is used for top-level nodes and the 'reg' method
+is used only for buses.
+
+Device sequence numbers are resolved when a device is probed. Before then
+the sequence number is only a request which may or may not be honoured,
+depending on what other devices have been probed. However the numbering is
+entirely under the control of the board author so a conflict is generally
+an error.
+
+
 Driver Lifecycle
 ----------------
 
@@ -409,7 +487,11 @@
    This means (for example) that an I2C driver will require that its bus
    be activated.
 
-   e. If the driver provides an ofdata_to_platdata() method, then this is
+   e. The device's sequence number is assigned, either the requested one
+   (assuming no conflicts) or the next available one if there is a conflict
+   or nothing particular is requested.
+
+   f. If the driver provides an ofdata_to_platdata() method, then this is
    called to convert the device tree data into platform data. This should
    do various calls like fdtdec_get_int(gd->fdt_blob, dev->of_offset, ...)
    to access the node and store the resulting information into dev->platdata.
@@ -425,7 +507,7 @@
    data, one day it is possible that U-Boot will cache platformat data for
    devices which are regularly de/activated).
 
-   f. The device's probe() method is called. This should do anything that
+   g. The device's probe() method is called. This should do anything that
    is required by the device to get it going. This could include checking
    that the hardware is actually present, setting up clocks for the
    hardware and setting up hardware registers to initial values. The code
@@ -440,9 +522,9 @@
    allocate the priv space here yourself. The same applies also to
    platdata_auto_alloc_size. Remember to free them in the remove() method.
 
-   g. The device is marked 'activated'
+   h. The device is marked 'activated'
 
-   h. The uclass's post_probe() method is called, if one exists. This may
+   i. The uclass's post_probe() method is called, if one exists. This may
    cause the uclass to do some housekeeping to record the device as
    activated and 'known' by the uclass.
 
@@ -488,7 +570,14 @@
       or preferably ofdata_to_platdata()) and the deallocation in remove()
       are the responsibility of the driver author.
 
-   e. The device is marked inactive. Note that it is still bound, so the
+   e. The device sequence number is set to -1, meaning that it no longer
+   has an allocated sequence. If the device is later reactivated and that
+   sequence number is still free, it may well receive the name sequence
+   number again. But from this point, the sequence number previously used
+   by this device will no longer exist (think of SPI bus 2 being removed
+   and bus 2 is no longer available for use).
+
+   f. The device is marked inactive. Note that it is still bound, so the
    device structure itself is not freed at this point. Should the device be
    activated again, then the cycle starts again at step 2 above.
 
diff --git a/drivers/core/device.c b/drivers/core/device.c
index 86b9ff8..848ce3b 100644
--- a/drivers/core/device.c
+++ b/drivers/core/device.c
@@ -10,6 +10,7 @@
  */
 
 #include <common.h>
+#include <fdtdec.h>
 #include <malloc.h>
 #include <dm/device.h>
 #include <dm/device-internal.h>
@@ -21,6 +22,8 @@
 #include <linux/err.h>
 #include <linux/list.h>
 
+DECLARE_GLOBAL_DATA_PTR;
+
 /**
  * device_chld_unbind() - Unbind all device's children from the device
  *
@@ -95,6 +98,21 @@
 	dev->parent = parent;
 	dev->driver = drv;
 	dev->uclass = uc;
+
+	/*
+	 * For some devices, such as a SPI or I2C bus, the 'reg' property
+	 * is a reasonable indicator of the sequence number. But if there is
+	 * an alias, we use that in preference. In any case, this is just
+	 * a 'requested' sequence, and will be resolved (and ->seq updated)
+	 * when the device is probed.
+	 */
+	dev->req_seq = fdtdec_get_int(gd->fdt_blob, of_offset, "reg", -1);
+	dev->seq = -1;
+	if (uc->uc_drv->name && of_offset != -1) {
+		fdtdec_get_alias_seq(gd->fdt_blob, uc->uc_drv->name, of_offset,
+				     &dev->req_seq);
+	}
+
 	if (!dev->platdata && drv->platdata_auto_alloc_size)
 		dev->flags |= DM_FLAG_ALLOC_PDATA;
 
@@ -207,6 +225,7 @@
 	struct driver *drv;
 	int size = 0;
 	int ret;
+	int seq;
 
 	if (!dev)
 		return -EINVAL;
@@ -249,6 +268,13 @@
 			goto fail;
 	}
 
+	seq = uclass_resolve_seq(dev);
+	if (seq < 0) {
+		ret = seq;
+		goto fail;
+	}
+	dev->seq = seq;
+
 	if (drv->ofdata_to_platdata && dev->of_offset >= 0) {
 		ret = drv->ofdata_to_platdata(dev);
 		if (ret)
@@ -276,6 +302,7 @@
 			__func__, dev->name);
 	}
 fail:
+	dev->seq = -1;
 	device_free(dev);
 
 	return ret;
@@ -311,6 +338,7 @@
 
 	device_free(dev);
 
+	dev->seq = -1;
 	dev->flags &= ~DM_FLAG_ACTIVATED;
 
 	return 0;
diff --git a/drivers/core/uclass.c b/drivers/core/uclass.c
index db91526..c28cf67 100644
--- a/drivers/core/uclass.c
+++ b/drivers/core/uclass.c
@@ -158,6 +158,35 @@
 	return -ENODEV;
 }
 
+int uclass_find_device_by_seq(enum uclass_id id, int seq_or_req_seq,
+			      bool find_req_seq, struct udevice **devp)
+{
+	struct uclass *uc;
+	struct udevice *dev;
+	int ret;
+
+	*devp = NULL;
+	debug("%s: %d %d\n", __func__, find_req_seq, seq_or_req_seq);
+	if (seq_or_req_seq == -1)
+		return -ENODEV;
+	ret = uclass_get(id, &uc);
+	if (ret)
+		return ret;
+
+	list_for_each_entry(dev, &uc->dev_head, uclass_node) {
+		debug("   - %d %d\n", dev->req_seq, dev->seq);
+		if ((find_req_seq ? dev->req_seq : dev->seq) ==
+				seq_or_req_seq) {
+			*devp = dev;
+			debug("   - found\n");
+			return 0;
+		}
+	}
+	debug("   - not found\n");
+
+	return -ENODEV;
+}
+
 /**
  * uclass_get_device_tail() - handle the end of a get_device call
  *
@@ -193,6 +222,23 @@
 	return uclass_get_device_tail(dev, ret, devp);
 }
 
+int uclass_get_device_by_seq(enum uclass_id id, int seq, struct udevice **devp)
+{
+	struct udevice *dev;
+	int ret;
+
+	*devp = NULL;
+	ret = uclass_find_device_by_seq(id, seq, false, &dev);
+	if (ret == -ENODEV) {
+		/*
+		 * We didn't find it in probed devices. See if there is one
+		 * that will request this seq if probed.
+		 */
+		ret = uclass_find_device_by_seq(id, seq, true, &dev);
+	}
+	return uclass_get_device_tail(dev, ret, devp);
+}
+
 int uclass_first_device(enum uclass_id id, struct udevice **devp)
 {
 	struct uclass *uc;
@@ -270,6 +316,37 @@
 	return 0;
 }
 
+int uclass_resolve_seq(struct udevice *dev)
+{
+	struct udevice *dup;
+	int seq;
+	int ret;
+
+	assert(dev->seq == -1);
+	ret = uclass_find_device_by_seq(dev->uclass->uc_drv->id, dev->req_seq,
+					false, &dup);
+	if (!ret) {
+		dm_warn("Device '%s': seq %d is in use by '%s'\n",
+			dev->name, dev->req_seq, dup->name);
+	} else if (ret == -ENODEV) {
+		/* Our requested sequence number is available */
+		if (dev->req_seq != -1)
+			return dev->req_seq;
+	} else {
+		return ret;
+	}
+
+	for (seq = 0; seq < DM_MAX_SEQ; seq++) {
+		ret = uclass_find_device_by_seq(dev->uclass->uc_drv->id, seq,
+						false, &dup);
+		if (ret == -ENODEV)
+			break;
+		if (ret)
+			return ret;
+	}
+	return seq;
+}
+
 int uclass_post_probe_device(struct udevice *dev)
 {
 	struct uclass_driver *uc_drv = dev->uclass->uc_drv;
@@ -297,6 +374,7 @@
 		free(dev->uclass_priv);
 		dev->uclass_priv = NULL;
 	}
+	dev->seq = -1;
 
 	return 0;
 }
diff --git a/include/dm/device.h b/include/dm/device.h
index 4679979..6005e7e 100644
--- a/include/dm/device.h
+++ b/include/dm/device.h
@@ -55,6 +55,8 @@
  * @child_head: List of children of this device
  * @sibling_node: Next device in list of all devices
  * @flags: Flags for this device DM_FLAG_...
+ * @req_seq: Requested sequence number for this device (-1 = any)
+ * @seq: Allocated sequence number for this device (-1 = none)
  */
 struct udevice {
 	struct driver *driver;
@@ -69,8 +71,13 @@
 	struct list_head child_head;
 	struct list_head sibling_node;
 	uint32_t flags;
+	int req_seq;
+	int seq;
 };
 
+/* Maximum sequence number supported */
+#define DM_MAX_SEQ	999
+
 /* Returns the operations for a device */
 #define device_get_ops(dev)	(dev->driver->ops)
 
@@ -161,4 +168,26 @@
  */
 void *dev_get_priv(struct udevice *dev);
 
+/**
+ * device_find_child_by_seq() - Find a child device based on a sequence
+ *
+ * This searches for a device with the given seq or req_seq.
+ *
+ * For seq, if an active device has this sequence it will be returned.
+ * If there is no such device then this will return -ENODEV.
+ *
+ * For req_seq, if a device (whether activated or not) has this req_seq
+ * value, that device will be returned. This is a strong indication that
+ * the device will receive that sequence when activated.
+ *
+ * @parent: Parent device
+ * @seq_or_req_seq: Sequence number to find (0=first)
+ * @find_req_seq: true to find req_seq, false to find seq
+ * @devp: Returns pointer to device (there is only one per for each seq).
+ * Set to NULL if none is found
+ * @return 0 if OK, -ve on error
+ */
+int device_find_child_by_seq(struct udevice *parent, int seq_or_req_seq,
+			     bool find_req_seq, struct udevice **devp);
+
 #endif
diff --git a/include/dm/uclass-internal.h b/include/dm/uclass-internal.h
index 1434db3..f718f37 100644
--- a/include/dm/uclass-internal.h
+++ b/include/dm/uclass-internal.h
@@ -82,4 +82,27 @@
  */
 int uclass_destroy(struct uclass *uc);
 
+/**
+ * uclass_find_device_by_seq() - Find uclass device based on ID and sequence
+ *
+ * This searches for a device with the given seq or req_seq.
+ *
+ * For seq, if an active device has this sequence it will be returned.
+ * If there is no such device then this will return -ENODEV.
+ *
+ * For req_seq, if a device (whether activated or not) has this req_seq
+ * value, that device will be returned. This is a strong indication that
+ * the device will receive that sequence when activated.
+ *
+ * The device is NOT probed, it is merely returned.
+ *
+ * @id: ID to look up
+ * @seq_or_req_seq: Sequence number to find (0=first)
+ * @find_req_seq: true to find req_seq, false to find seq
+ * @devp: Returns pointer to device (there is only one per for each seq)
+ * @return 0 if OK, -ve on error
+ */
+int uclass_find_device_by_seq(enum uclass_id id, int seq_or_req_seq,
+			      bool find_req_seq, struct udevice **devp);
+
 #endif
diff --git a/include/dm/uclass.h b/include/dm/uclass.h
index afd9923..48ae242 100644
--- a/include/dm/uclass.h
+++ b/include/dm/uclass.h
@@ -106,6 +106,22 @@
 int uclass_get_device(enum uclass_id id, int index, struct udevice **devp);
 
 /**
+ * uclass_get_device_by_seq() - Get a uclass device based on an ID and sequence
+ *
+ * If an active device has this sequence it will be returned. If there is no
+ * such device then this will check for a device that is requesting this
+ * sequence.
+ *
+ * The device is probed to activate it ready for use.
+ *
+ * @id: ID to look up
+ * @seq: Sequence number to find (0=first)
+ * @devp: Returns pointer to device (there is only one for each seq)
+ * @return 0 if OK, -ve on error
+ */
+int uclass_get_device_by_seq(enum uclass_id id, int seq, struct udevice **devp);
+
+/**
  * uclass_first_device() - Get the first device in a uclass
  *
  * @id: Uclass ID to look up
@@ -124,6 +140,21 @@
 int uclass_next_device(struct udevice **devp);
 
 /**
+ * uclass_resolve_seq() - Resolve a device's sequence number
+ *
+ * On entry dev->seq is -1, and dev->req_seq may be -1 (to allocate a
+ * sequence number automatically, or >= 0 to select a particular number.
+ * If the requested sequence number is in use, then this device will
+ * be allocated another one.
+ *
+ * Note that the device's seq value is not changed by this function.
+ *
+ * @dev: Device for which to allocate sequence number
+ * @return sequence number allocated, or -ve on error
+ */
+int uclass_resolve_seq(struct udevice *dev);
+
+/**
  * uclass_foreach_dev() - Helper function to iteration through devices
  *
  * This creates a for() loop which works through the available devices in
diff --git a/test/dm/test-fdt.c b/test/dm/test-fdt.c
index d284f7f..d8e94d8 100644
--- a/test/dm/test-fdt.c
+++ b/test/dm/test-fdt.c
@@ -94,7 +94,7 @@
 /* Test that FDT-based binding works correctly */
 static int dm_test_fdt(struct dm_test_state *dms)
 {
-	const int num_drivers = 3;
+	const int num_drivers = 4;
 	struct udevice *dev;
 	struct uclass *uc;
 	int ret;
@@ -163,3 +163,55 @@
 	return 0;
 }
 DM_TEST(dm_test_fdt_pre_reloc, 0);
+
+/* Test that sequence numbers are allocated properly */
+static int dm_test_fdt_uclass_seq(struct dm_test_state *dms)
+{
+	struct udevice *dev;
+
+	/* A few basic santiy tests */
+	ut_assertok(uclass_find_device_by_seq(UCLASS_TEST_FDT, 3, true, &dev));
+	ut_asserteq_str("b-test", dev->name);
+
+	ut_assertok(uclass_find_device_by_seq(UCLASS_TEST_FDT, 0, true, &dev));
+	ut_asserteq_str("a-test", dev->name);
+
+	ut_asserteq(-ENODEV, uclass_find_device_by_seq(UCLASS_TEST_FDT, 5,
+						       true, &dev));
+	ut_asserteq_ptr(NULL, dev);
+
+	/* Test aliases */
+	ut_assertok(uclass_get_device_by_seq(UCLASS_TEST_FDT, 6, &dev));
+	ut_asserteq_str("e-test", dev->name);
+
+	ut_asserteq(-ENODEV, uclass_find_device_by_seq(UCLASS_TEST_FDT, 7,
+						       true, &dev));
+
+	/* Note that c-test is not probed since it is not a top-level node */
+	ut_assertok(uclass_get_device_by_seq(UCLASS_TEST_FDT, 3, &dev));
+	ut_asserteq_str("b-test", dev->name);
+
+	/*
+	 * d-test wants sequence number 3 also, but it can't have it because
+	 * b-test gets it first.
+	 */
+	ut_assertok(uclass_get_device(UCLASS_TEST_FDT, 2, &dev));
+	ut_asserteq_str("d-test", dev->name);
+
+	/* d-test actually gets 0 */
+	ut_assertok(uclass_get_device_by_seq(UCLASS_TEST_FDT, 0, &dev));
+	ut_asserteq_str("d-test", dev->name);
+
+	/* initially no one wants seq 1 */
+	ut_asserteq(-ENODEV, uclass_get_device_by_seq(UCLASS_TEST_FDT, 1,
+						      &dev));
+	ut_assertok(uclass_get_device(UCLASS_TEST_FDT, 0, &dev));
+	ut_assertok(uclass_get_device(UCLASS_TEST_FDT, 1, &dev));
+
+	/* But now that it is probed, we can find it */
+	ut_assertok(uclass_get_device_by_seq(UCLASS_TEST_FDT, 1, &dev));
+	ut_asserteq_str("a-test", dev->name);
+
+	return 0;
+}
+DM_TEST(dm_test_fdt_uclass_seq, DM_TESTF_SCAN_PDATA | DM_TESTF_SCAN_FDT);
diff --git a/test/dm/test.dts b/test/dm/test.dts
index cd18a31..60503f1 100644
--- a/test/dm/test.dts
+++ b/test/dm/test.dts
@@ -8,6 +8,7 @@
 
 	aliases {
 		console = &uart0;
+		testfdt6 = "/e-test";
 	};
 
 	uart0: serial {
@@ -42,6 +43,7 @@
 	some-bus {
 		#address-cells = <1>;
 		#size-cells = <0>;
+		reg = <3>;
 		ping-expect = <4>;
 		ping-add = <4>;
 		c-test {
@@ -52,7 +54,14 @@
 	};
 
 	d-test {
-		reg = <6>;
+		reg = <3>;
+		ping-expect = <6>;
+		ping-add = <6>;
+		compatible = "google,another-fdt-test";
+	};
+
+	e-test {
+		reg = <3>;
 		ping-expect = <6>;
 		ping-add = <6>;
 		compatible = "google,another-fdt-test";