Patrick Rudolph has uploaded this change for review.
lib: Add flattened devicetree support
Required for Cavium's BDK and uImage FIT support.
Ported from libpayload.
Change-Id: I6e6cd9f78fb402bd54d684097326d26eb78d552a
Signed-off-by: Patrick Rudolph <patrick.rudolph@9elements.com>
---
A src/include/device_tree.h
A src/include/list.h
M src/lib/Kconfig
M src/lib/Makefile.inc
A src/lib/device_tree.c
A src/lib/list.c
6 files changed, 1,269 insertions(+), 0 deletions(-)
git pull ssh://review.coreboot.org:29418/coreboot refs/changes/23/25523/1
diff --git a/src/include/device_tree.h b/src/include/device_tree.h
new file mode 100644
index 0000000..faa9625
--- /dev/null
+++ b/src/include/device_tree.h
@@ -0,0 +1,197 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but without any warranty; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+
+#ifndef __DEVICE_TREE_H__
+#define __DEVICE_TREE_H__
+
+#include <stdint.h>
+#include <list.h>
+
+/*
+ * Flattened device tree structures/constants.
+ */
+
+typedef struct FdtHeader {
+ uint32_t magic;
+ uint32_t totalsize;
+ uint32_t structure_offset;
+ uint32_t strings_offset;
+ uint32_t reserve_map_offset;
+
+ uint32_t version;
+ uint32_t last_compatible_version;
+
+ uint32_t boot_cpuid_phys;
+
+ uint32_t strings_size;
+ uint32_t structure_size;
+} FdtHeader;
+
+static const uint32_t FdtMagic = 0xd00dfeed;
+
+static const uint32_t TokenBeginNode = 1;
+static const uint32_t TokenEndNode = 2;
+static const uint32_t TokenProperty = 3;
+static const uint32_t TokenEnd = 9;
+
+typedef struct FdtProperty
+{
+ const char *name;
+ void *data;
+ uint32_t size;
+} FdtProperty;
+
+
+
+/*
+ * Unflattened device tree structures.
+ */
+
+typedef struct DeviceTreeProperty
+{
+ FdtProperty prop;
+
+ ListNode list_node;
+} DeviceTreeProperty;
+
+typedef struct DeviceTreeNode
+{
+ const char *name;
+ // List of DeviceTreeProperty-s.
+ ListNode properties;
+ // List of DeviceTreeNodes.
+ ListNode children;
+
+ ListNode list_node;
+} DeviceTreeNode;
+
+typedef struct DeviceTreeReserveMapEntry
+{
+ uint64_t start;
+ uint64_t size;
+
+ ListNode list_node;
+} DeviceTreeReserveMapEntry;
+
+typedef struct DeviceTree
+{
+ void *header;
+ uint32_t header_size;
+
+ ListNode reserve_map;
+
+ DeviceTreeNode *root;
+} DeviceTree;
+
+
+
+/*
+ * Flattened device tree functions. These generally return the number of bytes
+ * which were consumed reading the requested value.
+ */
+
+// Read the property, if any, at offset offset.
+int fdt_next_property(void *blob, uint32_t offset, FdtProperty *prop);
+// Read the name of the node, if any, at offset offset.
+int fdt_node_name(void *blob, uint32_t offset, const char **name);
+
+void fdt_print_node(void *blob, uint32_t offset);
+int fdt_skip_node(void *blob, uint32_t offset);
+
+// Read a flattened device tree into a heirarchical structure which refers to
+// the contents of the flattened tree in place. Modifying the flat tree
+// invalidates the unflattened one.
+DeviceTree *fdt_unflatten(void *blob);
+
+
+
+/*
+ * Unflattened device tree functions.
+ */
+
+// Figure out how big a device tree would be if it were flattened.
+uint32_t dt_flat_size(DeviceTree *tree);
+// Flatten a device tree into the buffer pointed to by dest.
+void dt_flatten(DeviceTree *tree, void *dest);
+void dt_print_node(DeviceTreeNode *node);
+// Read #address-cells and #size-cells properties from a node.
+void dt_read_cell_props(DeviceTreeNode *node, u32 *addrcp, u32 *sizecp);
+// Look up or create a node relative to a parent node, through its path
+// represented as an array of strings.
+DeviceTreeNode *dt_find_node(DeviceTreeNode *parent, const char **path,
+ u32 *addrcp, u32 *sizecp, int create);
+// Look up or create a node relative to a parent node, through its path
+// represented as a string of '/' separated node names.
+DeviceTreeNode *dt_find_node_by_path(DeviceTreeNode *parent, const char *path,
+ u32 *addrcp, u32 *sizecp, int create);
+// Look up a node relative to a parent node, through its compatible string.
+DeviceTreeNode *dt_find_compat(DeviceTreeNode *parent, const char *compatible);
+// Look up the next child of a parent node, through its compatible string. It
+// uses child pointer as the marker to find next.
+DeviceTreeNode *dt_find_next_compat_child(DeviceTreeNode *parent,
+ DeviceTreeNode *child,
+ const char *compat);
+// Look up a node relative to a parent node, through its property value.
+DeviceTreeNode *dt_find_prop_value(DeviceTreeNode *parent, const char *name,
+ void *data, size_t size);
+// Write src into *dest as a 'length'-byte big-endian integer.
+void dt_write_int(u8 *dest, u64 src, size_t length);
+// Add different kinds of properties to a node, or update existing ones.
+void dt_add_bin_prop(DeviceTreeNode *node, const char *name, void *data, size_t size);
+void dt_add_string_prop(DeviceTreeNode *node, const char *name, char *str);
+void dt_add_u32_prop(DeviceTreeNode *node, const char *name, u32 val);
+void dt_add_reg_prop(DeviceTreeNode *node, u64 *addrs, u64 *sizes,
+ int count, u32 addr_cells, u32 size_cells);
+int dt_set_bin_prop_by_path(DeviceTree *tree, const char *path,
+ void *data, size_t size, int create);
+
+void dt_find_bin_prop(DeviceTreeNode *node, const char *name, void **data,
+ size_t *size);
+const char *dt_find_string_prop(DeviceTreeNode *node, const char *name);
+
+/*
+ * Fixups to apply to a kernel's device tree before booting it.
+ */
+
+typedef struct DeviceTreeFixup
+{
+ // The function which does the fixing.
+ int (*fixup)(struct DeviceTreeFixup *fixup, DeviceTree *tree);
+
+ ListNode list_node;
+} DeviceTreeFixup;
+
+extern ListNode device_tree_fixups;
+
+int dt_apply_fixups(DeviceTree *tree);
+
+/*
+ * Structure defining mapping between arbitrary objects and the device tree
+ * path to the property corresponding to the object.
+ */
+typedef struct {
+ int force_create; /* If false - do not create a new node. */
+ const char *dt_path;
+ const char *key;
+} DtPathMap;
+
+/*
+ * Init/retrieve the /reserved-memory/ node.
+ */
+DeviceTreeNode *dt_init_reserved_memory_node(DeviceTree *tree);
+
+#endif /* __DEVICE_TREE_H__ */
diff --git a/src/include/list.h b/src/include/list.h
new file mode 100644
index 0000000..482afee
--- /dev/null
+++ b/src/include/list.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but without any warranty; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+
+#ifndef __LIST_H__
+#define __LIST_H__
+
+#include <stddef.h>
+#include <stdint.h>
+
+//#include "container_of.h"
+
+typedef struct ListNode {
+ struct ListNode *next;
+ struct ListNode *prev;
+} ListNode;
+
+// Remove ListNode node from the doubly linked list it's a part of.
+void list_remove(ListNode *node);
+// Insert ListNode node after ListNode after in a doubly linked list.
+void list_insert_after(ListNode *node, ListNode *after);
+// Insert ListNode node before ListNode before in a doubly linked list.
+void list_insert_before(ListNode *node, ListNode *before);
+
+#define list_for_each(ptr, head, member) \
+ for ((ptr) = container_of((head).next, typeof(*(ptr)), member); \
+ &((ptr)->member); \
+ (ptr) = container_of((ptr)->member.next, \
+ typeof(*(ptr)), member))
+
+#endif /* __LIST_H__ */
diff --git a/src/lib/Kconfig b/src/lib/Kconfig
index bce0291..eb4c16e 100644
--- a/src/lib/Kconfig
+++ b/src/lib/Kconfig
@@ -17,6 +17,12 @@
help
Selected by features that require `libhwbase` in ramstage.
+config FLATTENED_DEVICE_TREE
+ bool
+ help
+ Selected by features that require to parse and manipulate a flattened
+ devicetree in ramstage.
+
if RAMSTAGE_LIBHWBASE
config HWBASE_DYNAMIC_MMIO
diff --git a/src/lib/Makefile.inc b/src/lib/Makefile.inc
index 960b5cb..fbed4ea 100644
--- a/src/lib/Makefile.inc
+++ b/src/lib/Makefile.inc
@@ -135,6 +135,11 @@
ramstage-y += b64_decode.c
ramstage-$(CONFIG_ACPI_NHLT) += nhlt.c
+ramstage-$(CONFIG_FLATTENED_DEVICE_TREE) += list.c
+ramstage-$(CONFIG_FLATTENED_DEVICE_TREE) += device_tree.c
+romstage-$(CONFIG_FLATTENED_DEVICE_TREE) += list.c
+romstage-$(CONFIG_FLATTENED_DEVICE_TREE) += device_tree.c
+
romstage-y += cbmem_common.c
romstage-y += imd_cbmem.c
romstage-y += imd.c
diff --git a/src/lib/device_tree.c b/src/lib/device_tree.c
new file mode 100644
index 0000000..f670036
--- /dev/null
+++ b/src/lib/device_tree.c
@@ -0,0 +1,973 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but without any warranty; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+
+#include <assert.h>
+#include <endian.h>
+#include <stdint.h>
+#include <console/console.h>
+#include <string.h>
+#include <endian.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+#include "device_tree.h"
+
+/*
+ * No support for malloc in romstage.
+ * Implement custom implementation.
+ */
+static void *fdt_alloc(const size_t len)
+{
+#if ENV_ROMSTAGE
+ static char fdtheap[0x2000];
+ static size_t heapptr = 0;
+
+ assert(len + heapptr <= sizeof(fdtheap));
+
+ if (len + heapptr > sizeof(fdtheap))
+ return NULL;
+
+ void *addr = &fdtheap[heapptr];
+ heapptr += len;
+
+ return addr;
+#else
+ return malloc(len);
+#endif
+}
+
+/*
+ * strdup is not available in romstage.
+ * Implement on our own.
+ */
+static char *fdt_strdup(const char *buf)
+{
+ void *tmp = fdt_alloc(strlen(buf) + 1);
+ strcpy(tmp, buf);
+ return tmp;
+}
+
+/*
+ * Functions for picking apart flattened trees.
+ */
+
+static uint32_t size32(uint32_t val)
+{
+ return (val + sizeof(uint32_t) - 1) / sizeof(uint32_t);
+}
+
+int fdt_next_property(void *blob, uint32_t offset, FdtProperty *prop)
+{
+ FdtHeader *header = (FdtHeader *)blob;
+ uint32_t *ptr = (uint32_t *)(((uint8_t *)blob) + offset);
+
+ int index = 0;
+ if (be32toh(ptr[index++]) != TokenProperty)
+ return 0;
+
+ uint32_t size = be32toh(ptr[index++]);
+ uint32_t name_offset = be32toh(ptr[index++]);
+ name_offset += be32toh(header->strings_offset);
+
+ if (prop) {
+ prop->name = (char *)((uint8_t *)blob + name_offset);
+ prop->data = &ptr[index];
+ prop->size = size;
+ }
+
+ index += size32(size);
+
+ return index * 4;
+}
+
+int fdt_node_name(void *blob, uint32_t offset, const char **name)
+{
+ uint8_t *ptr = ((uint8_t *)blob) + offset;
+ if (be32toh(*(uint32_t *)ptr) != TokenBeginNode)
+ return 0;
+
+ ptr += 4;
+ if (name)
+ *name = (char *)ptr;
+ return size32(strlen((char *)ptr) + 1) * sizeof(uint32_t) + 4;
+}
+
+
+
+/*
+ * Functions for printing flattened trees.
+ */
+
+static void print_indent(int depth)
+{
+ while (depth--)
+ printk(BIOS_DEBUG, " ");
+}
+
+static void print_property(FdtProperty *prop, int depth)
+{
+ print_indent(depth);
+ printk(BIOS_DEBUG, "prop \"%s\" (%d bytes).\n", prop->name, prop->size);
+ print_indent(depth + 1);
+ for (int i = 0; i < MIN(25, prop->size); i++) {
+ printk(BIOS_DEBUG, "%02x ", ((uint8_t *)prop->data)[i]);
+ }
+ if (prop->size > 25)
+ printk(BIOS_DEBUG, "...");
+ printk(BIOS_DEBUG, "\n");
+}
+
+static int print_flat_node(void *blob, uint32_t start_offset, int depth)
+{
+ int offset = start_offset;
+ const char *name;
+ int size;
+
+ size = fdt_node_name(blob, offset, &name);
+ if (!size)
+ return 0;
+ offset += size;
+
+ print_indent(depth);
+ printk(BIOS_DEBUG, "name = %s\n", name);
+
+ FdtProperty prop;
+ while ((size = fdt_next_property(blob, offset, &prop))) {
+ print_property(&prop, depth + 1);
+
+ offset += size;
+ }
+
+ while ((size = print_flat_node(blob, offset, depth + 1)))
+ offset += size;
+
+ return offset - start_offset + sizeof(uint32_t);
+}
+
+void fdt_print_node(void *blob, uint32_t offset)
+{
+ print_flat_node(blob, offset, 0);
+}
+
+
+
+/*
+ * A utility function to skip past nodes in flattened trees.
+ */
+
+int fdt_skip_node(void *blob, uint32_t start_offset)
+{
+ int offset = start_offset;
+ int size;
+
+ const char *name;
+ size = fdt_node_name(blob, offset, &name);
+ if (!size)
+ return 0;
+ offset += size;
+
+ while ((size = fdt_next_property(blob, offset, NULL)))
+ offset += size;
+
+ while ((size = fdt_skip_node(blob, offset)))
+ offset += size;
+
+ return offset - start_offset + sizeof(uint32_t);
+}
+
+
+
+/*
+ * Functions to turn a flattened tree into an unflattened one.
+ */
+static DeviceTreeNode *alloc_node(void)
+{
+ DeviceTreeNode *buf = fdt_alloc(sizeof(DeviceTreeNode));
+ if (!buf)
+ return NULL;
+ memset(buf, 0, sizeof(*buf));
+ return buf;
+}
+
+static DeviceTreeProperty *alloc_prop(void)
+{
+ DeviceTreeProperty *buf = fdt_alloc(sizeof(DeviceTreeProperty));
+ if (!buf)
+ return NULL;
+ memset(buf, 0, sizeof(*buf));
+ return buf;
+}
+
+static int fdt_unflatten_node(void *blob, uint32_t start_offset,
+ DeviceTreeNode **new_node)
+{
+ ListNode *last;
+ int offset = start_offset;
+ const char *name;
+ int size;
+
+ size = fdt_node_name(blob, offset, &name);
+ if (!size)
+ return 0;
+ offset += size;
+
+ DeviceTreeNode *node = alloc_node();
+ *new_node = node;
+ node->name = name;
+
+ FdtProperty fprop;
+ last = &node->properties;
+ while ((size = fdt_next_property(blob, offset, &fprop))) {
+ DeviceTreeProperty *prop = alloc_prop();
+ prop->prop = fprop;
+
+ list_insert_after(&prop->list_node, last);
+ last = &prop->list_node;
+
+ offset += size;
+ }
+
+ DeviceTreeNode *child;
+ last = &node->children;
+ while ((size = fdt_unflatten_node(blob, offset, &child))) {
+ list_insert_after(&child->list_node, last);
+ last = &child->list_node;
+
+ offset += size;
+ }
+
+ return offset - start_offset + sizeof(uint32_t);
+}
+
+static int fdt_unflatten_map_entry(void *blob, uint32_t offset,
+ DeviceTreeReserveMapEntry **new_entry)
+{
+ uint64_t *ptr = (uint64_t *)(((uint8_t *)blob) + offset);
+ uint64_t start = be64toh(ptr[0]);
+ uint64_t size = be64toh(ptr[1]);
+
+ if (!size)
+ return 0;
+
+ DeviceTreeReserveMapEntry *entry = fdt_alloc(sizeof(*entry));
+ memset(entry, 0, sizeof(*entry));
+ *new_entry = entry;
+ entry->start = start;
+ entry->size = size;
+
+ return sizeof(uint64_t) * 2;
+}
+
+DeviceTree *fdt_unflatten(void *blob)
+{
+ DeviceTree *tree = fdt_alloc(sizeof(*tree));
+ FdtHeader *header = (FdtHeader *)blob;
+
+ memset(tree, 0, sizeof(*tree));
+ tree->header = header;
+
+ uint32_t struct_offset = be32toh(header->structure_offset);
+ uint32_t strings_offset = be32toh(header->strings_offset);
+ uint32_t reserve_offset = be32toh(header->reserve_map_offset);
+ uint32_t min_offset = 0;
+ min_offset = MIN(struct_offset, strings_offset);
+ min_offset = MIN(min_offset, reserve_offset);
+ // Assume everything up to the first non-header component is part of
+ // the header and needs to be preserved. This will protect us against
+ // new elements being added in the future.
+ tree->header_size = min_offset;
+
+ DeviceTreeReserveMapEntry *entry;
+ uint32_t offset = reserve_offset;
+ int size;
+ ListNode *last = &tree->reserve_map;
+ while ((size = fdt_unflatten_map_entry(blob, offset, &entry))) {
+ list_insert_after(&entry->list_node, last);
+ last = &entry->list_node;
+
+ offset += size;
+ }
+
+ fdt_unflatten_node(blob, struct_offset, &tree->root);
+
+ return tree;
+}
+
+
+
+/*
+ * Functions to find the size of device tree would take if it was flattened.
+ */
+
+static void dt_flat_prop_size(DeviceTreeProperty *prop, uint32_t *struct_size,
+ uint32_t *strings_size)
+{
+ // Starting token.
+ *struct_size += sizeof(uint32_t);
+ // Size.
+ *struct_size += sizeof(uint32_t);
+ // Name offset.
+ *struct_size += sizeof(uint32_t);
+ // Property value.
+ *struct_size += size32(prop->prop.size) * sizeof(uint32_t);
+
+ // Property name.
+ *strings_size += strlen(prop->prop.name) + 1;
+}
+
+static void dt_flat_node_size(DeviceTreeNode *node, uint32_t *struct_size,
+ uint32_t *strings_size)
+{
+ // Starting token.
+ *struct_size += sizeof(uint32_t);
+ // Node name.
+ *struct_size += size32(strlen(node->name) + 1) * sizeof(uint32_t);
+
+ DeviceTreeProperty *prop;
+ list_for_each(prop, node->properties, list_node)
+ dt_flat_prop_size(prop, struct_size, strings_size);
+
+ DeviceTreeNode *child;
+ list_for_each(child, node->children, list_node)
+ dt_flat_node_size(child, struct_size, strings_size);
+
+ // End token.
+ *struct_size += sizeof(uint32_t);
+}
+
+uint32_t dt_flat_size(DeviceTree *tree)
+{
+ uint32_t size = tree->header_size;
+ DeviceTreeReserveMapEntry *entry;
+ list_for_each(entry, tree->reserve_map, list_node)
+ size += sizeof(uint64_t) * 2;
+ size += sizeof(uint64_t) * 2;
+
+ uint32_t struct_size = 0;
+ uint32_t strings_size = 0;
+ dt_flat_node_size(tree->root, &struct_size, &strings_size);
+
+ size += struct_size;
+ // End token.
+ size += sizeof(uint32_t);
+
+ size += strings_size;
+
+ return size;
+}
+
+
+
+/*
+ * Functions to flatten a device tree.
+ */
+
+static void dt_flatten_map_entry(DeviceTreeReserveMapEntry *entry,
+ void **map_start)
+{
+ ((uint64_t *)*map_start)[0] = htobe64(entry->start);
+ ((uint64_t *)*map_start)[1] = htobe64(entry->size);
+ *map_start = ((uint8_t *)*map_start) + sizeof(uint64_t) * 2;
+}
+
+static void dt_flatten_prop(DeviceTreeProperty *prop, void **struct_start,
+ void *strings_base, void **strings_start)
+{
+ uint8_t *dstruct = (uint8_t *)*struct_start;
+ uint8_t *dstrings = (uint8_t *)*strings_start;
+
+ *((uint32_t *)dstruct) = htobe32(TokenProperty);
+ dstruct += sizeof(uint32_t);
+
+ *((uint32_t *)dstruct) = htobe32(prop->prop.size);
+ dstruct += sizeof(uint32_t);
+
+ uint32_t name_offset = (uintptr_t)dstrings - (uintptr_t)strings_base;
+ *((uint32_t *)dstruct) = htobe32(name_offset);
+ dstruct += sizeof(uint32_t);
+
+ strcpy((char *)dstrings, prop->prop.name);
+ dstrings += strlen(prop->prop.name) + 1;
+
+ memcpy(dstruct, prop->prop.data, prop->prop.size);
+ dstruct += size32(prop->prop.size) * 4;
+
+ *struct_start = dstruct;
+ *strings_start = dstrings;
+}
+
+static void dt_flatten_node(DeviceTreeNode *node, void **struct_start,
+ void *strings_base, void **strings_start)
+{
+ uint8_t *dstruct = (uint8_t *)*struct_start;
+ uint8_t *dstrings = (uint8_t *)*strings_start;
+
+ *((uint32_t *)dstruct) = htobe32(TokenBeginNode);
+ dstruct += sizeof(uint32_t);
+
+ strcpy((char *)dstruct, node->name);
+ dstruct += size32(strlen(node->name) + 1) * 4;
+
+ DeviceTreeProperty *prop;
+ list_for_each(prop, node->properties, list_node)
+ dt_flatten_prop(prop, (void **)&dstruct, strings_base,
+ (void **)&dstrings);
+
+ DeviceTreeNode *child;
+ list_for_each(child, node->children, list_node)
+ dt_flatten_node(child, (void **)&dstruct, strings_base,
+ (void **)&dstrings);
+
+ *((uint32_t *)dstruct) = htobe32(TokenEndNode);
+ dstruct += sizeof(uint32_t);
+
+ *struct_start = dstruct;
+ *strings_start = dstrings;
+}
+
+void dt_flatten(DeviceTree *tree, void *start_dest)
+{
+ uint8_t *dest = (uint8_t *)start_dest;
+
+ memcpy(dest, tree->header, tree->header_size);
+ FdtHeader *header = (FdtHeader *)dest;
+ dest += tree->header_size;
+
+ DeviceTreeReserveMapEntry *entry;
+ list_for_each(entry, tree->reserve_map, list_node)
+ dt_flatten_map_entry(entry, (void **)&dest);
+ ((uint64_t *)dest)[0] = ((uint64_t *)dest)[1] = 0;
+ dest += sizeof(uint64_t) * 2;
+
+ uint32_t struct_size = 0;
+ uint32_t strings_size = 0;
+ dt_flat_node_size(tree->root, &struct_size, &strings_size);
+
+ uint8_t *struct_start = dest;
+ header->structure_offset = htobe32(dest - (uint8_t *)start_dest);
+ header->structure_size = htobe32(struct_size);
+ dest += struct_size;
+
+ *((uint32_t *)dest) = htobe32(TokenEnd);
+ dest += sizeof(uint32_t);
+
+ uint8_t *strings_start = dest;
+ header->strings_offset = htobe32(dest - (uint8_t *)start_dest);
+ header->strings_size = htobe32(strings_size);
+ dest += strings_size;
+
+ dt_flatten_node(tree->root, (void **)&struct_start, strings_start,
+ (void **)&strings_start);
+
+ header->totalsize = htobe32(dest - (uint8_t *)start_dest);
+}
+
+
+
+/*
+ * Functions for printing a non-flattened device tree.
+ */
+
+static void print_node(DeviceTreeNode *node, int depth)
+{
+ print_indent(depth);
+ printk(BIOS_DEBUG, "name = %s\n", node->name);
+
+ DeviceTreeProperty *prop;
+ list_for_each(prop, node->properties, list_node)
+ print_property(&prop->prop, depth + 1);
+
+ DeviceTreeNode *child;
+ list_for_each(child, node->children, list_node)
+ print_node(child, depth + 1);
+}
+
+void dt_print_node(DeviceTreeNode *node)
+{
+ print_node(node, 0);
+}
+
+
+
+/*
+ * Functions for reading and manipulating an unflattened device tree.
+ */
+
+/*
+ * Read #address-cells and #size-cells properties from a node.
+ *
+ * @param node The device tree node to read from.
+ * @param addrcp Pointer to store #address-cells in, skipped if NULL.
+ * @param sizecp Pointer to store #size-cells in, skipped if NULL.
+ */
+void dt_read_cell_props(DeviceTreeNode *node, u32 *addrcp, u32 *sizecp)
+{
+ DeviceTreeProperty *prop;
+ list_for_each(prop, node->properties, list_node) {
+ if (addrcp && !strcmp("#address-cells", prop->prop.name))
+ *addrcp = be32toh(*(u32 *)prop->prop.data);
+ if (sizecp && !strcmp("#size-cells", prop->prop.name))
+ *sizecp = be32toh(*(u32 *)prop->prop.data);
+ }
+}
+
+/*
+ * Find a node from a device tree path, relative to a parent node.
+ *
+ * @param parent The node from which to start the relative path lookup.
+ * @param path An array of path component strings that will be looked
+ * up in order to find the node. Must be terminated with
+ * a NULL pointer. Example: {'firmware', 'coreboot', NULL}
+ * @param addrcp Pointer that will be updated with any #address-cells
+ * value found in the path. May be NULL to ignore.
+ * @param sizecp Pointer that will be updated with any #size-cells
+ * value found in the path. May be NULL to ignore.
+ * @param create 1: Create node(s) if not found. 0: Return NULL instead.
+ * @return The found/created node, or NULL.
+ */
+DeviceTreeNode *dt_find_node(DeviceTreeNode *parent, const char **path,
+ u32 *addrcp, u32 *sizecp, int create)
+{
+ DeviceTreeNode *node, *found = NULL;
+
+ // Update #address-cells and #size-cells for this level.
+ dt_read_cell_props(parent, addrcp, sizecp);
+
+ if (!*path)
+ return parent;
+
+ // Find the next node in the path, if it exists.
+ list_for_each(node, parent->children, list_node) {
+ if (!strcmp(node->name, *path)) {
+ found = node;
+ break;
+ }
+ }
+
+ // Otherwise create it or return NULL.
+ if (!found) {
+ if (!create)
+ return NULL;
+
+ found = alloc_node();
+ found->name = fdt_strdup(*path);
+ if (!found->name)
+ return NULL;
+
+ list_insert_after(&found->list_node, &parent->children);
+ }
+
+ return dt_find_node(found, path + 1, addrcp, sizecp, create);
+}
+
+/*
+ * Find a node from a string device tree path, relative to a parent node.
+ *
+ * @param parent The node from which to start the relative path lookup.
+ * @param path A string representing a path in the device tree, with
+ * nodes separated by '/'. Example: "soc/firmware/coreboot"
+ * @param addrcp Pointer that will be updated with any #address-cells
+ * value found in the path. May be NULL to ignore.
+ * @param sizecp Pointer that will be updated with any #size-cells
+ * value found in the path. May be NULL to ignore.
+ * @param create 1: Create node(s) if not found. 0: Return NULL instead.
+ * @return The found/created node, or NULL.
+ *
+ * It is the caller responsibility to provide the correct path string, namely
+ * not starting or ending with a '/', and not having "//" anywhere in it.
+ */
+DeviceTreeNode *dt_find_node_by_path(DeviceTreeNode *parent, const char *path,
+ u32 *addrcp, u32 *sizecp, int create)
+{
+ char *dup_path = fdt_strdup(path);
+ /* Hopefully enough depth for any node. */
+ const char *path_array[15];
+ int i;
+ char *next_slash;
+ DeviceTreeNode *node = NULL;
+
+ if (!dup_path)
+ return NULL;
+
+ next_slash = dup_path;
+ path_array[0] = dup_path;
+ for (i = 1; i < (ARRAY_SIZE(path_array) - 1); i++) {
+
+ next_slash = strchr(next_slash, '/');
+ if (!next_slash)
+ break;
+
+ *next_slash++ = '\0';
+ path_array[i] = next_slash;
+ }
+
+ if (!next_slash) {
+ path_array[i] = NULL;
+ node = dt_find_node(parent, path_array,
+ addrcp, sizecp, create);
+ }
+
+ free(dup_path);
+ return node;
+}
+
+/*
+ * Check if given node is compatible.
+ *
+ * @param node The node which is to be checked for compatible property.
+ * @param compat The compatible string to match.
+ * @return 1 = compatible, 0 = not compatible.
+ */
+static int dt_check_compat_match(DeviceTreeNode *node, const char *compat)
+{
+ DeviceTreeProperty *prop;
+
+ list_for_each(prop, node->properties, list_node) {
+ if (!strcmp("compatible", prop->prop.name)) {
+ size_t bytes = prop->prop.size;
+ const char *str = prop->prop.data;
+ while (bytes > 0) {
+ if (!strncmp(compat, str, bytes))
+ return 1;
+ size_t len = strnlen(str, bytes) + 1;
+ if (bytes <= len)
+ break;
+ str += len;
+ bytes -= len;
+ }
+ break;
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * Find a node from a compatible string, in the subtree of a parent node.
+ *
+ * @param parent The parent node under which to look.
+ * @param compat The compatible string to find.
+ * @return The found node, or NULL.
+ */
+DeviceTreeNode *dt_find_compat(DeviceTreeNode *parent, const char *compat)
+{
+ // Check if the parent node itself is compatible.
+ if (dt_check_compat_match(parent, compat))
+ return parent;
+
+ DeviceTreeNode *child;
+ list_for_each(child, parent->children, list_node) {
+ DeviceTreeNode *found = dt_find_compat(child, compat);
+ if (found)
+ return found;
+ }
+
+ return NULL;
+}
+
+/*
+ * Find the next compatible child of a given parent. All children upto the
+ * child passed in by caller are ignored. If child is NULL, it considers all the
+ * children to find the first child which is compatible.
+ *
+ * @param parent The parent node under which to look.
+ * @param child The child node to start search from (exclusive). If NULL
+ * consider all children.
+ * @param compat The compatible string to find.
+ * @return The found node, or NULL.
+ */
+DeviceTreeNode *dt_find_next_compat_child(DeviceTreeNode *parent,
+ DeviceTreeNode *child,
+ const char *compat)
+{
+ DeviceTreeNode *next;
+ int ignore = 0;
+
+ if (child)
+ ignore = 1;
+
+ list_for_each(next, parent->children, list_node) {
+ if (ignore) {
+ if (child == next)
+ ignore = 0;
+ continue;
+ }
+
+ if (dt_check_compat_match(next, compat))
+ return next;
+ }
+
+ return NULL;
+}
+
+/*
+ * Find a node with matching property value, in the subtree of a parent node.
+ *
+ * @param parent The parent node under which to look.
+ * @param name The property name to look for.
+ * @param data The property value to look for.
+ * @param size The property size.
+ */
+DeviceTreeNode *dt_find_prop_value(DeviceTreeNode *parent, const char *name,
+ void *data, size_t size)
+{
+ DeviceTreeProperty *prop;
+
+ /* Check if parent itself has the required property value. */
+ list_for_each(prop, parent->properties, list_node) {
+ if (!strcmp(name, prop->prop.name)) {
+ size_t bytes = prop->prop.size;
+ void *prop_data = prop->prop.data;
+ if (size != bytes)
+ break;
+ if (!memcmp(data, prop_data, size))
+ return parent;
+ break;
+ }
+ }
+
+ DeviceTreeNode *child;
+ list_for_each(child, parent->children, list_node) {
+ DeviceTreeNode *found = dt_find_prop_value(child, name, data,
+ size);
+ if (found)
+ return found;
+ }
+ return NULL;
+}
+
+/*
+ * Write an arbitrary sized big-endian integer into a pointer.
+ *
+ * @param dest Pointer to the DT property data buffer to write.
+ * @param src The integer to write (in CPU endianess).
+ * @param length the length of the destination integer in bytes.
+ */
+void dt_write_int(u8 *dest, u64 src, size_t length)
+{
+ while (length--) {
+ dest[length] = (u8)src;
+ src >>= 8;
+ }
+}
+
+/*
+ * Add an arbitrary property to a node, or update it if it already exists.
+ *
+ * @param node The device tree node to add to.
+ * @param name The name of the new property.
+ * @param data The raw data blob to be stored in the property.
+ * @param size The size of data in bytes.
+ */
+void dt_add_bin_prop(DeviceTreeNode *node, const char *name, void *data,
+ size_t size)
+{
+ DeviceTreeProperty *prop;
+
+ list_for_each(prop, node->properties, list_node) {
+ if (!strcmp(prop->prop.name, name)) {
+ prop->prop.data = data;
+ prop->prop.size = size;
+ return;
+ }
+ }
+
+ prop = alloc_prop();
+ list_insert_after(&prop->list_node, &node->properties);
+ prop->prop.name = name;
+ prop->prop.data = data;
+ prop->prop.size = size;
+}
+
+/*
+ * Find given string property in a node and return its content.
+ *
+ * @param node The device tree node to search.
+ * @param name The name of the property.
+ * @return The found string, or NULL.
+ */
+const char *dt_find_string_prop(DeviceTreeNode *node, const char *name)
+{
+ void *content;
+ size_t size;
+
+ dt_find_bin_prop(node, name, &content, &size);
+
+ return content;
+}
+
+/*
+ * Find given property in a node.
+ *
+ * @param node The device tree node to search.
+ * @param name The name of the property.
+ * @param data Pointer to return raw data blob in the property.
+ * @param size Pointer to return the size of data in bytes.
+ */
+void dt_find_bin_prop(DeviceTreeNode *node, const char *name, void **data,
+ size_t *size)
+{
+ DeviceTreeProperty *prop;
+
+ *data = NULL;
+ *size = 0;
+
+ list_for_each(prop, node->properties, list_node) {
+ if (!strcmp(prop->prop.name, name)) {
+ *data = prop->prop.data;
+ *size = prop->prop.size;
+ return;
+ }
+ }
+}
+
+/*
+ * Add a string property to a node, or update it if it already exists.
+ *
+ * @param node The device tree node to add to.
+ * @param name The name of the new property.
+ * @param str The zero-terminated string to be stored in the property.
+ */
+void dt_add_string_prop(DeviceTreeNode *node, const char *name, char *str)
+{
+ dt_add_bin_prop(node, name, str, strlen(str) + 1);
+}
+
+/*
+ * Add a 32-bit integer property to a node, or update it if it already exists.
+ *
+ * @param node The device tree node to add to.
+ * @param name The name of the new property.
+ * @param val The integer to be stored in the property.
+ */
+void dt_add_u32_prop(DeviceTreeNode *node, const char *name, u32 val)
+{
+ u32 *val_ptr = fdt_alloc(sizeof(val));
+ *val_ptr = htobe32(val);
+ dt_add_bin_prop(node, name, val_ptr, sizeof(*val_ptr));
+}
+
+/*
+ * Add a 'reg' address list property to a node, or update it if it exists.
+ *
+ * @param node The device tree node to add to.
+ * @param addrs Array of address values to be stored in the property.
+ * @param sizes Array of corresponding size values to 'addrs'.
+ * @param count Number of values in 'addrs' and 'sizes' (must be equal).
+ * @param addr_cells Value of #address-cells property valid for this node.
+ * @param size_cells Value of #size-cells property valid for this node.
+ */
+void dt_add_reg_prop(DeviceTreeNode *node, u64 *addrs, u64 *sizes,
+ int count, u32 addr_cells, u32 size_cells)
+{
+ int i;
+ size_t length = (addr_cells + size_cells) * sizeof(u32) * count;
+ u8 *data = fdt_alloc(length);
+ u8 *cur = data;
+
+ for (i = 0; i < count; i++) {
+ dt_write_int(cur, addrs[i], addr_cells * sizeof(u32));
+ cur += addr_cells * sizeof(u32);
+ dt_write_int(cur, sizes[i], size_cells * sizeof(u32));
+ cur += size_cells * sizeof(u32);
+ }
+
+ dt_add_bin_prop(node, "reg", data, length);
+}
+
+/*
+ * Fixups to apply to a kernel's device tree before booting it.
+ */
+
+ListNode device_tree_fixups;
+
+int dt_apply_fixups(DeviceTree *tree)
+{
+ DeviceTreeFixup *fixup;
+ list_for_each(fixup, device_tree_fixups, list_node) {
+ assert(fixup->fixup);
+ if (fixup->fixup(fixup, tree))
+ return 1;
+ }
+ return 0;
+}
+
+int dt_set_bin_prop_by_path(DeviceTree *tree, const char *path,
+ void *data, size_t data_size, int create)
+{
+ char *path_copy, *prop_name;
+ DeviceTreeNode *dt_node;
+
+ path_copy = fdt_strdup(path);
+
+ if (!path_copy) {
+ printk(BIOS_ERR, "Failed to allocate a copy of path %s\n", path);
+ return 1;
+ }
+
+ prop_name = strrchr(path_copy, '/');
+ if (!prop_name) {
+ printk(BIOS_ERR, "Path %s does not include '/'\n", path);
+ free(path_copy);
+ return 1;
+ }
+
+ *prop_name++ = '\0'; /* Separate path from the property name. */
+
+ dt_node = dt_find_node_by_path(tree->root, path_copy, NULL,
+ NULL, create);
+
+ if (!dt_node) {
+ printk(BIOS_ERR, "Failed to %s %s in the device tree\n",
+ create ? "create" : "find", path_copy);
+ free(path_copy);
+ return 1;
+ }
+
+ dt_add_bin_prop(dt_node, prop_name, data, data_size);
+
+ return 0;
+}
+
+/*
+ * Prepare the /reserved-memory/ node.
+ *
+ * Technically, this can be called more than one time, to init and/or retrieve
+ * the node. But dt_add_u32_prop() may leak a bit of memory if you do.
+ *
+ * @tree: Device tree to add/retrieve from.
+ * @return: The /reserved-memory/ node (or NULL, if error).
+ */
+DeviceTreeNode *dt_init_reserved_memory_node(DeviceTree *tree)
+{
+ DeviceTreeNode *reserved;
+ u32 addr = 0, size = 0;
+
+ reserved = dt_find_node_by_path(tree->root, "reserved-memory", &addr,
+ &size, 1);
+ if (!reserved)
+ return NULL;
+
+ // Binding doc says this should have the same #{address,size}-cells as
+ // the root.
+ dt_add_u32_prop(reserved, "#address-cells", addr);
+ dt_add_u32_prop(reserved, "#size-cells", size);
+ // Binding doc says this should be empty (i.e., 1:1 mapping from root).
+ dt_add_bin_prop(reserved, "ranges", NULL, 0);
+
+ return reserved;
+}
diff --git a/src/lib/list.c b/src/lib/list.c
new file mode 100644
index 0000000..581573e
--- /dev/null
+++ b/src/lib/list.c
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * See file CREDITS for list of people who contributed to this
+ * project.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but without any warranty; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+
+#include <list.h>
+
+void list_remove(ListNode *node)
+{
+ if (node->prev)
+ node->prev->next = node->next;
+ if (node->next)
+ node->next->prev = node->prev;
+}
+
+void list_insert_after(ListNode *node, ListNode *after)
+{
+ node->next = after->next;
+ node->prev = after;
+ after->next = node;
+ if (node->next)
+ node->next->prev = node;
+}
+
+void list_insert_before(ListNode *node, ListNode *before)
+{
+ node->prev = before->prev;
+ node->next = before;
+ before->prev = node;
+ if (node->prev)
+ node->prev->next = node;
+}
To view, visit change 25523. To unsubscribe, or for help writing mail filters, visit settings.