In this module we will touch on the concept of device trees, a data structure used by some operating systems (Linux among them) to describe the hardware components of the computer in an OS-agnostic way. This allows device drivers to be more “portable” and, generally speaking, reduces the number of platform-specific details that have to be hardcoded in the kernel itself.

The need for device trees

The Linux kernel has been ported to quite a large number of architectures: IA32, AMD64, ARM, AArch64, RISCV, MIPS, PowerPC, etc. In order to support such a wide range of hardware configurations, in the past it was necessary to hardcode details about the underlying hardware on the drivers or the kernel itself. An example used to be non-discoverable hardware components. Given that the exact “layout” of these components had to be specified in code, the kernel had to be rebuilt for each of them, as opposed to x86 where it is possible to have one compiled kernel which is able to rely on auto configuration protocols such as ACPI to discover hardware.

This was particularly egregious in the case of ARM-based devices, which are in principle quite diverse from one another, but sometimes the differences are minimal. Instead of having to specify these differences in code, it was decided to instead take a more data-driven approach, in which the hardware configuration is provided as an input to the driver or the kernel, allowing these to retrieve the required data at run-time.

Linux chose to rely on the so-called device tree format, which as its name implies, is a data structure that describes the hardware in a hierarchical, tree-like manner. The format itself is independent of the Linux project and is maintained separately.

Device tree format

A device tree is a tree-like structures of nodes and properties. Properties are key-value pairs, and nodes may contain properties or other nodes, called child nodes.

The following is a simple example of a device tree:

/dts-v1/;
/ {
  child-node-1 {
    string-property = "this is a string";
    string-list-property = "this is", "a list", "of strings";
    byte-list-property = [12 34 56];
  };
  child-node-2 {
    empty-property;
    cell-property = <1 2 3 4>;
    inner-child {
      x = <1>;
      y = "foo bar", [12 34], <1024 2048>;
    };
  };
};

It should be noted that although this conforms to the device tree syntax, it doesn’t actually describe something useful. It is only shown for illustration purposes.

The most relevant points being presented with this example are:

  • There are four nodes. The root node is called /, which has two child nodes, called child-node-1 and child-node-2. The latter has a child node of its own, called inner-child.
  • Properties are key-value pairs of the form key = value; where the value can either be empty of contain an arbitrary byte stream. Data types are not encoded into the data structure, but there are a few fundamental representations that are supported as first-class citizens:
    • Empty values are used to convey true or false information, when the presence or absence of the property itself is sufficiently descriptive.
    • Binary data is delimited by square brackets:
      property = [12 34 56 78];
    • “Cells” are 32-bit unsigned integers delimited by angle brackets, stored in big-endian order:
      property = <12 0xDEADBEEF 590>;
    • Zero-terminated strings are represented with double quotes:
      property = "foo bar";
    • Values of different types can be concatenated together using commas:
      property = "foo bar", [12 34 56], <0xDEAD 0xBEEF 1024>;

The Linux source tree includes a device tree compiler that can be used to translate the text representation of a device tree into an equivalent binary representation, which is located in scripts/dtc. It is normally built as part of the process of building the device trees included in the kernel.

Files that contain the text representation of a device tree usually have the .dts extension (which stands for device tree source). This is not required, though, just a convention.

Assuming you saved the previous device tree to a file, its corresponding device tree blob (dtb) can be generated as follows:

$ /path/to/linux/source/tree/scripts/dtc/dtc -I dts -O dtb -o file.dtb file.dts

Since the process of translating from text into binary is lossless, the DTC tool can do the reverse and “decompile” a device tree blob into a device tree source:

$ /path/to/linux/source/tree/scripts/dtc/dtc -I dtb -O dts -o file.dts file.dtb

Properties can also contain “references” to other nodes in the device tree. These are called phandles and are 32-bit values stored in big-endian format. The syntax is as follows:
property = <&node-name>;

Note that there’s nothing “special” about phandles: in principle they are simply a 32-bit value. They can be thought of as a pointer in C, in the sense that their value can be used to reference another object.

Nodes in the device tree are named according to the following convention: <name>[@<unit-address].

  • The first portion specifies the name of the node. It is up to 31 characters in length, each of which can be 0-9, a-z, A-Z, ,, ., _, + or -.
  • The second portion is optional and only included if the node describes a device with an address. In general, the unit address is the primary address used to access the device.

Sibling nodes must be uniquely named but is common for more than one node to use the same generic name so long as the address is different (for example, serial@100f010 and serial@200f010).

Let’s look at a more “real” example:

auart0: serial@8006a000 {
  compatible = "fsl,imx28-auart", "fsl,imx23-auart";
  reg = <0x8006a000 0x200>;
  interrupts = <112>;
  dmas = <&dma_apbx 8>, <&dma_apbx 9>;
  dma-names = "rx", "tx";
  clocks = <&clks 45>;
  status = "disabled";
};
  • The name of the node is serial@8006a000. A label has been attached to it, named auart0. Labels are used to create phandles to nodes.
  • Every node in the tree that represents a device is required to have a compatible property. This is used by the kernel to device which device driver to bind to a device. Conventionally, it follows the pattern <manufacturer>,<model>.This property is a list of strings. Device drivers are bound to the first match.
  • Each addressable device has a reg property, which is a list of tuples in the form <address1 length1 [address2 length2] ... [addressN lengthN]>.Each tuple represents an address range used by the device. Each address value is a list of one or more 32-bit integers (cells). Similarly, the length value can be either a list of cells or empty.Since both the address and length fields are of variable size, the #address-cells and #size-cells properties in the parent node are used to state how many cells are in each field. Assuming that the previous node is a child of the root node, the device tree could look like this:
/dts-v1/;
/ {
  (...)
  #address-cells = <1>;
  #size-cells = <1>;
  (...)
  auart0: serial@8006a000 {
    reg = <0x8006a000 0x200>;
    (...)
  };
};

Device tree inheritance

Device trees are not monolithic: they can be split into several files, as you would a C program, and then “include” one file inside the other. The convention is to have files with extension .dtsi be included files, whereas files with extension .dts are final device tree files. Typically, .dtsi files will contain definitions that are “common” to several boards and can therefore be used as a basis upon which to build a board-specific device tree file.

The following is a fragment of the device tree used by the BeagleBone Black, which is at arch/arm/boot/dts/ti/omap/am335x-boneblack.dts:

/dts-v1/;

#include "am33xx.dtsi"
#include "am335x-bone-common.dtsi"
#include "am335x-boneblack-common.dtsi"

/ {
  model = "TI AM335x BeagleBone Black";
  compatible = "ti,am335x-bone-black", "ti,am335x-bone", "ti,am33xx";
};

Inclusion works by overlaying the tree of the including file over the tree of the included file, according to the order of the #include directives. This allows an including file to override values specified by an included file.

Device trees and bootloaders

Given a device tree blob, it is necessary for the kernel to actually access it in order to extract information from it. There are two approaches here:

  • The kernel can be built with the device tree blob embedded in it. In this case, the kernel will look for the contents of the blob and the end of the kernel image. In order to do so, it is necessary to build the kernel with CONFIG_ARM_APPEND_DTB=y.
    • Be aware that the kernel won’t append the device tree blob for you, it must be explicitly done by yourself:
      $ cat arch/arm/boot/zImage arch/arm/boot/dts/ti/omap/am335x-boneblack.dtb >zImage+dtb
  • Some bootloaders (such as U-Boot and Barebox) handle device tree blobs natively. In the case of U-Boot, the blob is loaded into memory and used with the bootm (or bootz) command:
    => bootz ${kernel_address} - ${dtb_address}

Device trees and device drivers

Using the data provided by device trees in the kernel boils down to matching on the compatible property. There are two use-cases: board identification and device-to-driver identification.

  • Board identification using the device tree’s compatible property of the / node is matched on and can be used to setup the board defaults in the kernel. For example, arch/arm/mach-omap2/board-generic.c:
#ifdef CONFIG_SOC_AM33XX
static const char* const am33xx_boards_compat[] __initconst = {
  "ti,am33xx",
  NULL
};

DT_MACHINE_START(AM33XX_DT, "Generic AM33XX (Flattened Device Tree)")
  .reserve = omap_reserve,
  .map_io = am33xx_map_io,
  .init_early = am33xx_init_early,
  .init_machine = omap_generic_init,
  .init_late = am33xx_init_late,
  .init_time = omap_init_time_of,
  .dt_compat = am33xx_boards_compat,
  .restart = am33xx_restart,
  .reboot_mode = REBOOT_WARM
MACHINE_END
#endif
    • In this case, we are matching the string "ti,am33xx". This is the lowest level of the board setup code and the entry point for the kernel’s bootup routines.
  • With the basic functionality of the board up and running, we also need to setup peripheral drivers or bring up platform drivers. This is done in a similar way as we match on the compatible property, but we use features provided by the kernel to do so. For example, drivers/memory/omap-gpmc.c:
#ifdef CONFIG_OF
static const struct of_device_id gpmc_di_ids[] = {
  { .compatible = "ti,omap2420-gpmc" },
  { .compatible = "ti,omap2430-gpmc" },
  { .compatible = "ti,omap3430-gpmc" },
  { .compatible = "ti,omap4430-gpmc" },
  { .compatible = "ti,am3352-gpmc" },
  { .compatible = "ti,am64-gpmc" },
  { }
};
MODULE_DEVICE_TABLE(of, gpmc_dt_ids);
#endif

static struct platform_driver gpmc_driver = {
  .probe = gpmc_prove,
  .remove = gpmc_remove,
  .driver = {
    .name = "omap-gpmc",
    .of_match_table = of_match_ptr(gpmc_dt_ids),
    .pm = &gpmc_pm_ops
  }
};
  • Handling of device tree data in drivers starts in the function referenced by .probe in the platform_driver data structure, by retrieving the structure of_device_id using of_match_device. Then we can query properties and setup the device accordingly.
  • The most important functions can be found in drivers/of/base.c and are listed below:of_match_device: Indicates if a device matches an of_device_id_list.
const struct of_device_id* of_match_device(
  const struct of_device_id* matches,
  const struct device* dev
);
  • of_device_is_compatible: Checks if a given .compat string matches one of the strings in the device’s compatible property.
int of_device_is_compatible(
  const struct device_node* node,
  const char* compat
);
  • of_property_read_<type>: Retrieves the value of a property.For example, of_property_read_u64.
int of_property_read_u64(
  const struct device_node* np,
  const char* propname,
  u64* out_value
);

Consider the following fragment from the BeagleBone board:

static int gpmc_probe_dt(struct platform_device *pdev)
{
  int ret;
  struct device_node *child;
  const struct of_device_id *of_id =
    of_match_device(gpmc_dt_ids, &pdev->dev);

  if (!of_id) return 0;

  ret = of_property_read_u32(pdev->dev.of_node, "gpmc,num-cs",
                             &gpmc_cs_num);
  [...]
  ret = of_property_read_u32(pdev->dev.of_node, "gpmc,num-waitpins",
                             &gpmc_nr_waitpins);
  [...]
  for_each_child_of_node(pdev->dev.of_node, child) {
    if (!child->name) continue;
    if (of_node_cmp(child->name, "nand") == 0)
      ret = gpmc_probe_nand_child(pdev, child);
    else if (of_node_cmp(child->name, "onenand") == 0)
      ret = gpmc_probe_onenand_child(pdev, child);
    else if (of_node_cmp(child->name, "ethernet") == 0 ||
             of_node_cmp(child->name, "nor") == 0 ||
             of_node_cmp(child->name, "uart") == 0)
      ret = gpmc_probe_generic_child(pdev, child);
    if (WARN(ret < 0, "%s: probing gpmc child %s failed\n",
             __func__, child->full_name))
      of_node_put(child);
  }
  return 0;
}