[PATCH v2 0/6] Introduce fdt_overlay_merge() to allow merge of overlay blob

[PATCH v2 0/6] Introduce fdt_overlay_merge() to allow merge of overlay blob

[Gurbir Arora]

Hello Upstream Team,

         This is the second upstream attempt for the fdtoverlay changes and the first attempt can
be found here: https://www.spinics.net/lists/devicetree-compiler/msg01949.html. All of the
issues/comments from the first attempt have been addressed and fixed in this patch.

Changelog:

v1 -> v2: 
- Introduction of new entry point, fdt_overlay_merge(), to handles merging
  overlay blobs (rather than overload that in fdt_overlay_apply()).
- Removed use of printf() in libfdt. snprintf() is still used to help with string
  manipulation.
- Changed the logic to identify fragment nodes.
- Removed use of malloc/calloc and global variables.
- Incorporated a function that copies a node in the overlay tree along with its children and their
properties.

fdt_overlay_apply() API currently allows for an overlay DT blob to be merged
with a base blob. It assumes that all external symbols specified in overlay
blob's __fixups__ section are found in base blob's __symbols__ section and
aborts on the first instance where a symbol could not be found in base blob.

This is mostly fine as the primary use of overlay is on a target for its
bootloader to merge various overlay blobs based on h/w configuration detected?

We are exploring an extended use of fdt_overlay_apply() for offline use, i.e on
the host (build machine) side, which requires merging two overlay DT blobs i.e
the base (overlay) blob will not resolve all the external node references found
in overlay blob.

Currently all the device-tree (DT) code for a given soc is maintained in a
common kernel repository. For example, this common DT code will have code for
audio, video, fingerprint, bluetooth etc. Further this DT code is typically
split into a base (soc-common) code and board specific code, with the soc code
being compiled as soc.dtb and board specific code being compiled as respective
overlay blobs (board1.dtbo, board2.dtbo etc). soc.dtb represents hardware configuration
of a given SOC while boardX.dtbo represents configuration of a board/platform 
designed using that soc.soc.dtb and boardX.dtbo files are flashed separately on 
target (besides improving the overall size of DT blobs flashed on target, Android 
Treble also requires separation of soc and board DT bits). Bootloader will pick 
one of the board overlay blobs and merge it with soc.dtb, before booting kernel 
which is presented a unified DT blob (soc + board overlay).

For ease of code maintenance and better control over release management, we are
exploring allowing some of the tech teams (audio/fingerprint sensor etc) to
maintain their kernel code (including their DT code) outside a common kernel
repository. In our experience, this simplifies number of branches maintained in
core kernel repo. New/experimental features in fingerprint sensor driver for
example that needs to be on a separate branch will not result in unnecessary
branching in core kenrel repo, affecting all other drivers.

In addition to compiling DT code outside core kernel tree, we also want to merge
the blobs back to respective blobs found in kernel build tree (soc.dtb or
boardX.dtbo), as otherwise relying on bootloader to do all the overlay impacts
boot-time.

This brings up the need to merge two overlay blobs (fingerprint-overlay.dtbo +
boardX.dtbo), which currently doesn't seem to be supported and which this patch
series aims to support.

Additional notes: 

If snprintf (in libc) may not available in some environments, then we will need
to write our own snprintf() in libfdt.

Srivatsa Vaddagiri (6):
  libfdt: overlay_merge: Introduce fdt_overlay_merge()
  libfdt: overlay_merge: Rename fragments
  libfdt: overlay_merge: Ignore unresolved symbols
  libfdt: overlay_merge: remove resolved symbols
  libfdt: overlay_merge: Copy over various nodes and their properties
  fdtoverlaymerge: A tool that merges overlays

 Makefile             |   3 +
 Makefile.utils       |   6 +
 fdtoverlaymerge.c    | 223 ++++++++++++++++
 libfdt/fdt_overlay.c | 742 +++++++++++++++++++++++++++++++++++++++++++++++++--
 libfdt/libfdt.h      |  18 ++
 5 files changed, 971 insertions(+), 21 deletions(-)
 create mode 100644 fdtoverlaymerge.c

-- 
2.7.4

[PATCH v2 1/6] libfdt: overlay_merge: Introduce fdt_overlay_merge()

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

fdt_overlay_merge() merges two overlay blobs. This is largely expected to be
used offline on a build machine to combine two or more overlay blobs into one.

This is intended to help maintain device-tree overlay code in
multiple source repositories, but merge their binary forms (overlay blobs)
into one so that bootloader's task of searching for all relevant overlay blobs
is simplified.

This patch introduces fdt_overlay_merge() which is exactly identical to
fdt_overlay_apply(). Subsequent patches will introduce required changes to merge
overlay blobs.

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 libfdt/libfdt.h      | 18 ++++++++++++++++++
 2 files changed, 71 insertions(+)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index b310e49..65d7a29 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -879,3 +879,56 @@ err:
 
 	return ret;
 }
+
+int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
+{
+	uint32_t delta = fdt_get_max_phandle(fdt);
+	int ret;
+
+	FDT_CHECK_HEADER(fdt);
+	FDT_CHECK_HEADER(fdto);
+
+	*fdto_nospace = 0;
+
+	ret = overlay_adjust_local_phandles(fdto, delta);
+	if (ret)
+		goto err;
+
+	ret = overlay_update_local_references(fdto, delta);
+	if (ret)
+		goto err;
+
+	ret = overlay_fixup_phandles(fdt, fdto);
+	if (ret)
+		goto err;
+
+	ret = overlay_merge(fdt, fdto);
+	if (ret)
+		goto err;
+
+	ret = overlay_symbol_update(fdt, fdto);
+	if (ret)
+		goto err;
+
+	/*
+	 * The overlay has been damaged, erase its magic.
+	 */
+	fdt_set_magic(fdto, ~0);
+
+	return 0;
+
+err:
+	/*
+	 * The overlay might have been damaged, erase its magic.
+	 */
+	fdt_set_magic(fdto, ~0);
+
+	/*
+	 * The base device tree might have been damaged, erase its
+	 * magic.
+	 */
+	if (!*fdto_nospace)
+		fdt_set_magic(fdt, ~0);
+
+	return ret;
+}
diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
index 544d3ef..950388e 100644
--- a/libfdt/libfdt.h
+++ b/libfdt/libfdt.h
@@ -2067,6 +2067,24 @@ int fdt_del_node(void *fdt, int nodeoffset);
  */
 int fdt_overlay_apply(void *fdt, void *fdto);
 
+/**
+ * fdt_overlay_merge - Merge two overlays into one
+ * @fdt: pointer to the first device tree overlay blob
+ * @fdto: pointer to the second device tree overlay blob
+ * @fdto_nospace: indicates if FDT_ERR_NOSPACE error code applies to @fdto
+ *
+ * fdt_overlay_merge() will merge second overlay blob into first overlay blob.
+ *
+ * Expect the first device tree to be modified, even if the function
+ * returns an error.
+ *
+ * returns:
+ *	0, on success
+ *	-FDT_ERR_NOSPACE, there's not enough space in first device tree blob
+ *	-FDT_ERR_BADVALUE
+ */
+int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace);
+
 /**********************************************************************/
 /* Debugging / informational functions                                */
 /**********************************************************************/
-- 
2.7.4

[PATCH v2 2/6] libfdt: overlay_merge: Rename fragments

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

When merging two overlay blobs, fragment nodes whose target node can't be found
in base blob would need to be retained as-is (including the fragment names) in
the combined blob. Such unresolved symbols will also need to be listed in
__fixups__ section of combined blob. This could lead to name comflicts in
combined blob (two nodes with same name/path such as /fragment@0).

To avoid such name conflicts in combined blob, rename all fragment@xyz in
overlay blob as fragment@xyz+delta, where delta is the maximum count of fragment
nodes found in base blob

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 329 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 329 insertions(+)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index 65d7a29..d7d6f03 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -8,9 +8,12 @@
 
 #include <fdt.h>
 #include <libfdt.h>
+#include <stdio.h>
 
 #include "libfdt_internal.h"
 
+#define ULONG_MAX	(~0UL)
+
 /**
  * overlay_get_target_phandle - retrieves the target phandle of a fragment
  * @fdto: pointer to the device tree overlay blob
@@ -880,6 +883,325 @@ err:
 	return ret;
 }
 
+/*
+ * Property value could be in this format
+ *	fragment@M ...fragment@N....fragment@O..
+ *
+ * This needs to be converted to
+ *	fragment@M+delta...fragment@N+delta....fragment@O+delta
+ */
+static int rename_fragments_in_property(void *fdto, int offset,
+					int property, int delta)
+{
+	char *start, *sep, *end, *stop, *value;
+	int needed = 0, ret, len, found = 0, available, diff;
+	unsigned long index, new_index;
+	void *p = NULL;
+	const char *label;
+
+	value = (char *)(uintptr_t)fdt_getprop_by_offset(fdto, property,
+				      &label, &len);
+	if (!value)
+		return len;
+
+	start = value;
+	end = value + len;
+
+	/* Find the required additional space */
+	while (start < end) {
+		sep = memchr(start, '@', (end - start));
+		if (!sep) {
+			needed += end - start;
+			break;
+		}
+
+		/* Check if string "fragment" exists */
+		sep -= 8;
+
+		if (sep < start || strncmp(sep, "fragment", 8)) {
+			/* Start scan again after '@' */
+			sep = sep + 9;
+			needed += (sep - start);
+			start = sep;
+			continue;
+		}
+
+		found = 1;
+		sep += 9;
+		needed += (sep - start);
+		index = strtoul(sep, &stop, 10);
+		if (ULONG_MAX - index < delta)
+			return -FDT_ERR_BADVALUE;
+
+		new_index = index + delta;
+		needed += snprintf(NULL, 0, "%lu", new_index);
+		start = stop;
+	}
+
+	if (!found)
+		return 0;
+
+	p = value;
+	if (needed > len) {
+		ret = fdt_setprop_placeholder(fdto, offset, label, needed, &p);
+		if (ret < 0)
+			return ret;
+		len = needed;
+	}
+
+	start = p;
+	end = start + len;
+	ret = 0;
+
+	while (start < end) {
+		sep = memchr(start, '@', (end - start));
+		if (!sep)
+			break;
+
+		/* Check if string "fragment" exists */
+		sep -= 8;
+		if (sep < start || strncmp(sep, "fragment", 8)) {
+			/* Start scan again after '@' */
+			start = sep + 9;
+			continue;
+		}
+
+		sep += 9;
+		index = strtoul(sep, &stop, 10);
+		new_index = index + delta;
+
+		needed = snprintf(NULL, 0, "%lu", new_index);
+		available = stop - sep;
+
+		if (available < needed) {
+			diff = needed - available;
+			memmove(stop + diff, stop, (end - stop));
+		}
+
+		{
+			/* +1 for NULL char */
+			char buf[needed + 1];
+
+			snprintf(buf, needed + 1, "%lu", new_index);
+			memcpy(sep, buf, needed);
+		}
+
+		start = sep + needed;
+	}
+
+	return 0;
+}
+
+/**
+ * rename_fragments_in_node - Rename fragment@xyz instances in a node's
+ * properties
+ *
+ * @fdto    - pointer to a device-tree blob
+ * @nodename - Node in whose properties fragments need to be renamed
+ * @delta   - Increment to be applied to fragment index
+ */
+static int rename_fragments_in_node(void *fdto, const char *nodename,
+				     unsigned long delta)
+{
+	int offset, property;
+	int ret;
+
+	offset = fdt_path_offset(fdto, nodename);
+	if (offset < 0)
+		return offset;
+
+	fdt_for_each_property_offset(property, fdto, offset) {
+		ret = rename_fragments_in_property(fdto, offset,
+						   property, delta);
+		if (ret < 0)
+			return ret;
+	}
+
+	return 0;
+}
+
+/**
+ * rename_nodes - Rename all fragement@xyz nodes
+ *
+ * @fdto - pointer to device-tree blob
+ * @parent_node - node offset of parent whose child fragment nodes need to be
+ *		renamed
+ * @delta - increment to be added to fragment number
+ */
+static int rename_nodes(void *fdto, int parent_node, unsigned long delta)
+{
+	int offset = -1, ret, len, strsize;
+	int child_len, child_offset;
+	const char *name, *child_name, *idx;
+	char *stop = NULL;
+	unsigned long index, new_index;
+
+	offset = fdt_first_subnode(fdto, parent_node);
+	while (offset >= 0) {
+		name = fdt_get_name(fdto, offset, &len);
+		if (!name)
+			return len;
+
+		if (len < 9 || strncmp(name, "fragment@", 9))
+			goto next_node;
+
+		child_offset = fdt_first_subnode(fdto, offset);
+		if (child_offset < 0)
+			return child_offset;
+
+		child_name = fdt_get_name(fdto, child_offset, &child_len);
+		if (!child_name)
+			return child_len;
+
+		/* Extra FDT_TAGSIZE bytes for expanded node name */
+		strsize = FDT_TAGALIGN(len + 1 + FDT_TAGSIZE);
+
+		if (child_len >= 11 && !strncmp(child_name, "__overlay__", 11)){
+			char new_name[strsize];
+
+			idx = name + 9;
+			stop = NULL;
+			index = strtoul(idx, &stop, 10);
+			if (ULONG_MAX - delta < index)
+				return -FDT_ERR_BADVALUE;
+
+			new_index = index + delta;
+			ret = snprintf(new_name, sizeof(new_name),
+				       "fragment@%lu", new_index);
+			if (ret >= sizeof(new_name))
+				return -FDT_ERR_BADVALUE;
+
+			ret = fdt_set_name(fdto, offset, new_name);
+			if (ret < 0)
+				return ret;
+		}
+
+next_node:
+		offset = fdt_next_subnode(fdto, offset);
+	}
+
+	return 0;
+}
+
+/* Return maximum count of overlay fragments */
+static int count_fragments(void *fdt, unsigned long *max_base_fragments)
+{
+	int offset = -1, child_offset, child_len, len, found = 0;
+	const char *name, *child_name, *idx;
+	char *stop;
+	unsigned long index, max = 0;
+
+	offset = fdt_first_subnode(fdt, 0);
+	while (offset >= 0) {
+		name = fdt_get_name(fdt, offset, &len);
+		if (!name)
+			return len;
+
+		if (len < 9 || strncmp(name, "fragment@", 9))
+			goto next_node;
+
+		child_offset = fdt_first_subnode(fdt, offset);
+		if (child_offset < 0)
+			return child_offset;
+
+		child_name = fdt_get_name(fdt, child_offset, &child_len);
+		if (!child_name)
+			return child_len;
+
+		if (child_len < 11 || strncmp(child_name, "__overlay__", 11))
+			goto next_node;
+
+		found = 1;
+		idx = name + 9;
+		index = strtoul(idx, &stop, 10);
+		if (index > max)
+			max = index;
+next_node:
+		offset = fdt_next_subnode(fdt, offset);
+	}
+
+	if (!found)
+		return -FDT_ERR_NOTFOUND;
+
+	*max_base_fragments = max;
+
+	return 0;
+}
+
+/*
+ * Merging two overlay blobs involves copying some of the overlay fragment nodes
+ * (named as fragment@xyz) from second overlay blob into first, which can lead
+ * to naming conflicts (ex: two nodes of same name /fragment@0). To prevent such
+ * naming conflicts, rename all occurences of fragment@xyz in second overlay
+ * blob as fragment@xyz+delta, where delta is the maximum overlay fragments seen
+ * in first overlay blob
+ */
+static int overlay_rename_fragments(void *fdt, void *fdto)
+{
+	int ret, local_offset;
+	unsigned long max_base_fragments = 0;
+
+	ret = count_fragments(fdt, &max_base_fragments);
+	if (ret < 0)
+		return ret;
+
+	max_base_fragments += 1;
+	ret = rename_nodes(fdto, 0, max_base_fragments);
+	if (ret < 0)
+		return ret;
+
+	ret = rename_fragments_in_node(fdto, "/__fixups__", max_base_fragments);
+	if (ret < 0)
+		return ret;
+
+	ret = rename_fragments_in_node(fdto, "/__symbols__",
+						max_base_fragments);
+	if (ret < 0 && ret != -FDT_ERR_NOTFOUND)
+		return ret;
+
+	/*
+	 * renaming fragments in __local_fixups__ node's properties should be
+	 * covered by rename_nodes()
+	 */
+	local_offset = fdt_path_offset(fdto, "/__local_fixups__");
+	if (local_offset >= 0)
+		ret = rename_nodes(fdto, local_offset, max_base_fragments);
+
+	if (ret == -FDT_ERR_NOTFOUND)
+		ret = 0;
+
+	return ret;
+}
+
+/* merge a node's properties from fdto to fdt */
+static int overlay_merge_node_properties(void *fdt,
+					void *fdto, const char *nodename)
+{
+	int fdto_offset, ret;
+
+	fdto_offset = fdt_path_offset(fdto, nodename);
+	if (fdto_offset < 0)
+		return fdto_offset;
+
+	ret = copy_node(fdt, fdto, 0, fdto_offset);
+
+	return ret;
+}
+
+static int overlay_merge_local_fixups(void *fdt, void *fdto)
+{
+	int fdto_local_fixups, ret;
+
+	fdto_local_fixups = fdt_path_offset(fdto, "/__local_fixups__");
+	if (fdto_local_fixups < 0)
+		return fdto_local_fixups;
+
+	ret = copy_node(fdt, fdto, 0, fdto_local_fixups);
+}
+
 int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 {
 	uint32_t delta = fdt_get_max_phandle(fdt);
@@ -890,6 +1212,13 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 
 	*fdto_nospace = 0;
 
+	ret = overlay_rename_fragments(fdt, fdto);
+	if (ret) {
+		if (ret == -FDT_ERR_NOSPACE)
+			*fdto_nospace = 1;
+		goto err;
+	}
+
 	ret = overlay_adjust_local_phandles(fdto, delta);
 	if (ret)
 		goto err;
-- 
2.7.4

[PATCH v2 3/6] libfdt: overlay_merge: Ignore unresolved symbols

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

fdt_overlay_merge(), like fdt_overlay_apply(), has to perform similar operations
on DT blobs, one of which is going through external symbol references specified
in __fixups__ node of overlay DT blob and resolving them in base DT blob (as
performed by overlay_fixup_phandles()).

Unlike overlay case though, in case of merging two overlay blobs, its quite
normal that some of the external references specified in __fixups__ node are not
found in base blob. Modify overlay_fixup_phandles() to understand this
possibility.

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 219 +++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 205 insertions(+), 14 deletions(-)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index d7d6f03..9ea106a 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -408,12 +408,147 @@ static int overlay_fixup_one_phandle(void *fdt, void *fdto,
 						   sizeof(phandle_prop));
 };
 
+#define PATH_MAX	256
+
+static int overlay_add_to_local_fixups(void *fdt, const char *value, int len)
+{
+	const char *path, *fixup_end, *prop;
+	const char *fixup_str = value;
+	uint32_t clen;
+	uint32_t fixup_len;
+	char *sep, *endptr;
+	const char *c;
+	int poffset, nodeoffset, ret, localfixup_off;
+	int pathlen, proplen;
+	char propname[PATH_MAX];
+
+	localfixup_off = fdt_path_offset(fdt, "/__local_fixups__");
+	if (localfixup_off < 0 && localfixup_off == -FDT_ERR_NOTFOUND)
+		localfixup_off = fdt_add_subnode(fdt, 0, "__local_fixups__");
+
+	if (localfixup_off < 0)
+		return localfixup_off;
+
+	while (len > 0) {
+		/* Assumes null-terminated properties! */
+		fixup_end = memchr(value, '\0', len);
+		if (!fixup_end)
+			return -FDT_ERR_BADOVERLAY;
+
+		fixup_len = fixup_end - fixup_str;
+
+		len -= (fixup_len + 1);
+		value += fixup_len + 1;
+
+		c = path = fixup_str;
+		sep = memchr(c, ':', fixup_len);
+		if (!sep || *sep != ':')
+			return -FDT_ERR_BADOVERLAY;
+		pathlen = sep - path;
+		if (pathlen == (fixup_len - 1))
+			return -FDT_ERR_BADOVERLAY;
+
+		fixup_len -= (pathlen + 1);
+		c = path + pathlen + 1;
+
+		sep = memchr(c, ':', fixup_len);
+		if (!sep || *sep != ':')
+			return -FDT_ERR_BADOVERLAY;
+
+		prop = c;
+		proplen = sep - c;
+
+		if (proplen >= PATH_MAX)
+			return -FDT_ERR_BADOVERLAY;
+
+		/*
+		 * Skip fixups that involves the special 'target' property found
+		 * in overlay fragments such as
+		 *	/fragment@0:target:0
+		 *
+		 * The check for one node in path below is to ensure that we
+		 * handle 'target' properties present otherwise in any other
+		 * node, for ex:
+		 *	/fragment@0/__overlay__/xyz:target:0
+		 */
+
+		/* Does path have exactly one node? */
+		c = path;
+		clen = pathlen;
+		if (*c == '/') {
+			c++;
+			clen -= 1;
+		}
+
+		sep = memchr(c, '/', clen);
+		if (!sep && proplen >= 6 && !strncmp(prop, "target", 6))
+			continue;
+
+		memcpy(propname, prop, proplen);
+		propname[proplen] = 0;
+
+		fixup_len -= (proplen + 1);
+		c = prop + proplen + 1;
+		poffset = strtoul(c, &endptr, 10);
+
+		nodeoffset = localfixup_off;
+
+		c = path;
+		clen = pathlen;
+
+		if (*c == '/') {
+			c++;
+			clen -= 1;
+		}
+
+		while (clen > 0) {
+			char nodename[PATH_MAX];
+			int nodelen, childnode;
+
+			sep = memchr(c, '/', clen);
+			if (!sep)
+				nodelen = clen;
+			else
+				nodelen = sep - c;
+
+			if (nodelen + 1 >= PATH_MAX)
+				return -FDT_ERR_BADSTRUCTURE;
+			memcpy(nodename, c, nodelen);
+			nodename[nodelen] = 0;
+
+			childnode = fdt_add_subnode(fdt, nodeoffset, nodename);
+			if (childnode == -FDT_ERR_EXISTS)
+				childnode = fdt_subnode_offset(fdt,
+							      nodeoffset, nodename);
+			nodeoffset = childnode;
+			if (nodeoffset < 0)
+				return nodeoffset;
+
+			c += nodelen;
+			clen -= nodelen;
+
+			if (*c == '/') {
+				c++;
+				clen -= 1;
+			}
+		}
+
+		ret = fdt_setprop_u32(fdt, nodeoffset, propname, poffset);
+		if (ret < 0)
+			return ret;
+	}
+
+	return 0;
+}
+
 /**
  * overlay_fixup_phandle - Set an overlay phandle to the base one
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
  * @symbols_off: Node offset of the symbols node in the base device tree
  * @property: Property offset in the overlay holding the list of fixups
+ * @fixups_off: Offset of __fixups__ node in @fdto
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_fixup_phandle() resolves all the overlay phandles pointed
  * to in a __fixups__ property, and updates them to match the phandles
@@ -428,11 +563,11 @@ static int overlay_fixup_one_phandle(void *fdt, void *fdto,
  *      Negative error code on failure
  */
 static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
-				 int property)
+				int property, int fixups_off, int merge)
 {
 	const char *value;
 	const char *label;
-	int len;
+	int len, ret = 0;
 
 	value = fdt_getprop_by_offset(fdto, property,
 				      &label, &len);
@@ -449,7 +584,7 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
 		uint32_t path_len, name_len;
 		uint32_t fixup_len;
 		char *sep, *endptr;
-		int poffset, ret;
+		int poffset;
 
 		fixup_end = memchr(value, '\0', len);
 		if (!fixup_end)
@@ -489,7 +624,36 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
 			return ret;
 	} while (len > 0);
 
-	return 0;
+	/*
+	 * Properties found in __fixups__ node are typically one of
+	 * these types:
+	 *
+	 * 	abc = "/fragment@2:target:0"		(first type)
+	 *	abc = "/fragment@2/__overlay__:xyz:0"	(second type)
+	 *
+	 * Both types could also be present in some properties as well such as:
+	 *
+	 *	abc = "/fragment@2:target:0", "/fragment@2/__overlay__:xyz:0"
+	 *
+	 * While merging two overlay blobs, a successful overlay phandle fixup
+	 * of second type needs to be recorded in __local_fixups__ node of the
+	 * combined blob, so that the phandle value can be further updated via
+	 * overlay_update_local_references() when the combined overlay blob gets
+	 * overlaid on a different base blob.
+	 *
+	 * Further, since in the case of merging two overlay blobs, we will also
+	 * be merging contents of nodes such as __fixups__ from both overlay
+	 * blobs, delete this property in __fixup__  node, as it no longer
+	 * represents a external phandle reference that needs to be resolved
+	 * during a subsequent overlay of combined blob on a base blob.
+	 */
+	if (merge) {
+		ret = overlay_add_to_local_fixups(fdt, value, len);
+		if (!ret)
+			ret = fdt_delprop(fdto, fixups_off, label);
+	}
+
+	return ret;
 }
 
 /**
@@ -497,6 +661,7 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
  *                          device tree
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_fixup_phandles() resolves all the overlay phandles pointing
  * to nodes in the base device tree.
@@ -509,10 +674,10 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
  *      0 on success
  *      Negative error code on failure
  */
-static int overlay_fixup_phandles(void *fdt, void *fdto)
+static int overlay_fixup_phandles(void *fdt, void *fdto, int merge)
 {
 	int fixups_off, symbols_off;
-	int property;
+	int property, ret = 0, next_property;
 
 	/* We can have overlays without any fixups */
 	fixups_off = fdt_path_offset(fdto, "/__fixups__");
@@ -526,15 +691,41 @@ static int overlay_fixup_phandles(void *fdt, void *fdto)
 	if ((symbols_off < 0 && (symbols_off != -FDT_ERR_NOTFOUND)))
 		return symbols_off;
 
-	fdt_for_each_property_offset(property, fdto, fixups_off) {
-		int ret;
-
-		ret = overlay_fixup_phandle(fdt, fdto, symbols_off, property);
-		if (ret)
+	/* Safeguard against property being deleted in below loop */
+	property = fdt_first_property_offset(fdto, fixups_off);
+	while (property >= 0) {
+		next_property = fdt_next_property_offset(fdto, property);
+		ret = overlay_fixup_phandle(fdt, fdto, symbols_off,
+					   property, fixups_off, merge);
+		if (ret && (!merge || ret != -FDT_ERR_NOTFOUND))
 			return ret;
+
+		if (merge && !ret) {
+			/* Bail if this was the last property */
+			if (next_property < 0)
+				break;
+
+			/*
+			 * Property is deleted in this case. Next property is
+			 * available at the same offset, so loop back with
+			 * 'property' offset unmodified. Also since @fdt would
+			 * have been modified in this case, refresh the offset
+			 * of /__symbols__ node
+			 */
+			symbols_off = fdt_path_offset(fdt, "/__symbols__");
+			if (symbols_off < 0)
+				return symbols_off;
+
+			continue;
+		}
+
+		property = next_property;
 	}
 
-	return 0;
+	if (merge && ret == -FDT_ERR_NOTFOUND)
+		ret = 0;
+
+	return ret;
 }
 
 /**
@@ -849,7 +1040,7 @@ int fdt_overlay_apply(void *fdt, void *fdto)
 	if (ret)
 		goto err;
 
-	ret = overlay_fixup_phandles(fdt, fdto);
+	ret = overlay_fixup_phandles(fdt, fdto, 0);
 	if (ret)
 		goto err;
 
@@ -1227,7 +1418,7 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	if (ret)
 		goto err;
 
-	ret = overlay_fixup_phandles(fdt, fdto);
+	ret = overlay_fixup_phandles(fdt, fdto, 1);
 	if (ret)
 		goto err;
 
-- 
2.7.4

[PATCH v2 4/6] libfdt: overlay_merge: remove resolved symbols

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

Merging two overlay blobs will involve merging contents of nodes such as
__symbols__. Not all properties need to be merged however at the end of merge
process. overlay_symbol_update() may already have updated base blob's
__symbols__ node to reflect new position of some nodes from overlay blob. Remove
such symbols from overlay blob's __symbols__ node, to prevent a subsequent merge
of __symbols__ node of both blobs from creating duplicate entries representing
same node.

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 49 +++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 43 insertions(+), 6 deletions(-)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index 9ea106a..3c2ee88 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -873,6 +873,7 @@ static int get_path_len(const void *fdt, int nodeoffset)
  * overlay_symbol_update - Update the symbols of base tree after a merge
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_symbol_update() updates the symbols of the base tree with the
  * symbols of the applied overlay
@@ -885,9 +886,9 @@ static int get_path_len(const void *fdt, int nodeoffset)
  *      0 on success
  *      Negative error code on failure
  */
-static int overlay_symbol_update(void *fdt, void *fdto)
+static int overlay_symbol_update(void *fdt, void *fdto, int merge)
 {
-	int root_sym, ov_sym, prop, path_len, fragment, target;
+	int root_sym, ov_sym, prop, next_prop, path_len, fragment, target;
 	int len, frag_name_len, ret, rel_path_len;
 	const char *s, *e;
 	const char *path;
@@ -915,7 +916,12 @@ static int overlay_symbol_update(void *fdt, void *fdto)
 		return root_sym;
 
 	/* iterate over each overlay symbol */
-	fdt_for_each_property_offset(prop, fdto, ov_sym) {
+
+	/* Safeguard against property being possibly deleted in this loop */
+	prop = fdt_first_property_offset(fdto, ov_sym);
+	while (prop >= 0) {
+		next_prop = fdt_next_property_offset(fdto, prop);
+
 		path = fdt_getprop_by_offset(fdto, prop, &name, &path_len);
 		if (!path)
 			return path_len;
@@ -973,8 +979,14 @@ static int overlay_symbol_update(void *fdt, void *fdto)
 
 		/* get the target of the fragment */
 		ret = overlay_get_target(fdt, fdto, fragment, &target_path);
-		if (ret < 0)
+		if (ret < 0) {
+			if (ret == -FDT_ERR_BADPHANDLE && merge) {
+				prop = next_prop;
+				continue;
+			}
+
 			return ret;
+		}
 		target = ret;
 
 		/* if we have a target path use */
@@ -1015,6 +1027,31 @@ static int overlay_symbol_update(void *fdt, void *fdto)
 		buf[len] = '/';
 		memcpy(buf + len + 1, rel_path, rel_path_len);
 		buf[len + 1 + rel_path_len] = '\0';
+
+		/*
+		 * In case of merging two overlay blobs, we will be merging
+		 * contents of nodes such as __symbols__ from both overlay
+		 * blobs. Delete this property in __symbols__ node of second
+		 * overlay blob, as it has already been reflected in
+		 * first/combined blob's __symbols__ node.
+		 */
+		if (merge) {
+			ret = fdt_delprop(fdto, ov_sym, name);
+			if (ret < 0)
+				return ret;
+
+			/* Bail if this was the last property */
+			if (next_prop < 0)
+				break;
+
+			/*
+			 * Continue with same 'prop' offset, as the next
+			 * property is now available at the same offset
+			 */
+			continue;
+		}
+
+		prop = next_prop;
 	}
 
 	return 0;
@@ -1048,7 +1085,7 @@ int fdt_overlay_apply(void *fdt, void *fdto)
 	if (ret)
 		goto err;
 
-	ret = overlay_symbol_update(fdt, fdto);
+	ret = overlay_symbol_update(fdt, fdto, 0);
 	if (ret)
 		goto err;
 
@@ -1426,7 +1463,7 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	if (ret)
 		goto err;
 
-	ret = overlay_symbol_update(fdt, fdto);
+	ret = overlay_symbol_update(fdt, fdto, 1);
 	if (ret)
 		goto err;
 
-- 
2.7.4

[PATCH v2 5/6] libfdt: overlay_merge: Copy over various nodes and their properties

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

Many overlay fragment nodes that don't have a target node to be overlaid in base
device-tree will need to be copied over as-is into base-tree. This includes
merging properties found in special nodes such as __fixups__, __symbols__ and
__local_fixups__

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 94 insertions(+), 4 deletions(-)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index 3c2ee88..d3a567f 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -795,9 +795,69 @@ static int overlay_apply_node(void *fdt, int target,
 }
 
 /**
+ * copy_node - copy a node hierarchically
+ * @fdt - pointer to base device tree
+ * @fdto - pointer to overlay device tree
+ * @fdt_child - offset of node in overlay device tree which needs to be copied
+ * @fdt_parent - offset of parent node in base tree under which @fdto_child
+ *		need to be copied
+ *
+ * This function copies a node in overlay tree along with its child-nodes and
+ * their properties, under a given parent node in base tree.
+ */
+static int copy_node(void *fdt, void *fdto, int fdt_parent, int fdto_child)
+{
+	const char *name, *value;
+	int offset, len, ret, prop, child;
+	void *p;
+
+	name = fdt_get_name(fdto, fdto_child, &len);
+	if (!name)
+		return len;
+
+	offset = fdt_subnode_offset(fdt, fdt_parent, name);
+	if (offset < 0) {
+		offset = fdt_add_subnode(fdt, fdt_parent, name);
+		if (offset < 0)
+			return offset;
+	}
+
+	fdt_for_each_subnode(child, fdto, fdto_child) {
+		ret = copy_node(fdt, fdto, offset, child);
+		if (ret < 0)
+			return ret;
+	}
+
+	fdt_for_each_property_offset(prop, fdto, fdto_child) {
+		int fdt_len = 0;
+
+		value = fdt_getprop_by_offset(fdto, prop,
+						  &name, &len);
+
+		if (fdt_getprop(fdt, offset, name, &fdt_len))
+			len += fdt_len;
+
+		ret = fdt_setprop_placeholder(fdt, offset, name,
+								len, &p);
+		if (ret < 0)
+			return ret;
+
+		if (fdt_len > 0) {
+			p = (char *)p + fdt_len;
+			len -= fdt_len;
+		}
+
+		memcpy(p, value, len);
+	}
+
+	return 0;
+}
+
+/**
  * overlay_merge - Merge an overlay into its base device tree
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_merge() merges an overlay into its base device tree.
  *
@@ -809,7 +869,7 @@ static int overlay_apply_node(void *fdt, int target,
  *      0 on success
  *      Negative error code on failure
  */
-static int overlay_merge(void *fdt, void *fdto)
+static int overlay_merge(void *fdt, void *fdto, int merge)
 {
 	int fragment;
 
@@ -830,8 +890,21 @@ static int overlay_merge(void *fdt, void *fdto)
 			return overlay;
 
 		target = overlay_get_target(fdt, fdto, fragment, NULL);
-		if (target < 0)
+		if (target < 0) {
+			/*
+			 * No target found which is acceptable situation in case
+			 * of merging two overlay blobs. Copy this fragment to
+			 * base/combined blob, so that it can be considered for
+			 * overlay during a subsequent overlay operation of
+			 * combined blob on another base blob.
+			 */
+			if (target == -FDT_ERR_BADPHANDLE && merge) {
+				target = copy_node(fdt, fdto, 0, fragment);
+				if (!target)
+					continue;
+			}
 			return target;
+		}
 
 		ret = overlay_apply_node(fdt, target, fdto, overlay);
 		if (ret)
@@ -1081,7 +1154,7 @@ int fdt_overlay_apply(void *fdt, void *fdto)
 	if (ret)
 		goto err;
 
-	ret = overlay_merge(fdt, fdto);
+	ret = overlay_merge(fdt, fdto, 0);
 	if (ret)
 		goto err;
 
@@ -1428,6 +1501,8 @@ static int overlay_merge_local_fixups(void *fdt, void *fdto)
 		return fdto_local_fixups;
 
 	ret = copy_node(fdt, fdto, 0, fdto_local_fixups);
+
+	return ret;
 }
 
 int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
@@ -1459,7 +1534,7 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	if (ret)
 		goto err;
 
-	ret = overlay_merge(fdt, fdto);
+	ret = overlay_merge(fdt, fdto, 1);
 	if (ret)
 		goto err;
 
@@ -1467,6 +1542,21 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	if (ret)
 		goto err;
 
+	/* Can't have an overlay without __fixups__ ? */
+	ret = overlay_merge_node_properties(fdt, fdto, "/__fixups__");
+	if (ret)
+		goto err;
+
+	/* __symbols__ node need not be present */
+	ret = overlay_merge_node_properties(fdt, fdto, "/__symbols__");
+	if (ret && ret != -FDT_ERR_NOTFOUND)
+		goto err;
+
+	/* __local_fixups__ node need not be present */
+	ret = overlay_merge_local_fixups(fdt, fdto);
+	if (ret < 0 && ret != -FDT_ERR_NOTFOUND)
+		goto err;
+
 	/*
 	 * The overlay has been damaged, erase its magic.
 	 */
-- 
2.7.4

[PATCH v2 6/6] fdtoverlaymerge: A tool that merges overlays

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

fdtoverlaymerge is a command-line tool that merges two or more overlay blobs
by making use of fdt_overlay_merge() API

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 Makefile             |   3 +
 Makefile.utils       |   6 ++
 fdtoverlaymerge.c    | 223 +++++++++++++++++++++++++++++++++++++++++++++++++++
 libfdt/fdt_overlay.c |   8 +-
 4 files changed, 236 insertions(+), 4 deletions(-)
 create mode 100644 fdtoverlaymerge.c

diff --git a/Makefile b/Makefile
index cb256e8..5db214f 100644
--- a/Makefile
+++ b/Makefile
@@ -147,6 +147,7 @@ BIN += fdtdump
 BIN += fdtget
 BIN += fdtput
 BIN += fdtoverlay
+BIN += fdtoverlaymerge
 
 SCRIPTS = dtdiff
 
@@ -266,6 +267,8 @@ fdtput:	$(FDTPUT_OBJS) $(LIBFDT_lib)
 
 fdtoverlay: $(FDTOVERLAY_OBJS) $(LIBFDT_lib)
 
+fdtoverlaymerge: $(FDTOVERLAYMERGE_OBJS) $(LIBFDT_archive)
+
 dist:
 	git archive --format=tar --prefix=dtc-$(dtc_version)/ HEAD \
 		> ../dtc-$(dtc_version).tar
diff --git a/Makefile.utils b/Makefile.utils
index 9436b34..e24a8ab 100644
--- a/Makefile.utils
+++ b/Makefile.utils
@@ -29,3 +29,9 @@ FDTOVERLAY_SRCS = \
 	util.c
 
 FDTOVERLAY_OBJS = $(FDTOVERLAY_SRCS:%.c=%.o)
+
+FDTOVERLAYMERGE_SRCS = \
+	fdtoverlaymerge.c \
+	util.c
+
+FDTOVERLAYMERGE_OBJS = $(FDTOVERLAYMERGE_SRCS:%.c=%.o)
diff --git a/fdtoverlaymerge.c b/fdtoverlaymerge.c
new file mode 100644
index 0000000..eaf3e97
--- /dev/null
+++ b/fdtoverlaymerge.c
@@ -0,0 +1,223 @@
+/* Copyright (c) 2018, The Linux Foundation. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 and
+ * only version 2 as published by the Free Software Foundation.
+ *
+ * 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 <ctype.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <inttypes.h>
+
+#include <libfdt.h>
+
+#include "util.h"
+
+/* Usage related data. */
+static const char usage_synopsis[] =
+	"merge a number of overlays\n"
+	"	fdtoverlaymerge <options> [<overlay.dtbo> [<overlay.dtbo>]]\n"
+	"\n"
+	USAGE_TYPE_MSG;
+static const char usage_short_opts[] = "i:o:v" USAGE_COMMON_SHORT_OPTS;
+static struct option const usage_long_opts[] = {
+	{"input",            required_argument, NULL, 'i'},
+	{"output",	     required_argument, NULL, 'o'},
+	{"verbose",	           no_argument, NULL, 'v'},
+	USAGE_COMMON_LONG_OPTS,
+};
+static const char * const usage_opts_help[] = {
+	"Input base overlay DT blob",
+	"Output DT blob",
+	"Verbose messages",
+	USAGE_COMMON_OPTS_HELP
+};
+
+int verbose = 0;
+
+static void grow_blob(char **blob, off_t extra_len)
+{
+	int blob_len;
+
+	if (!extra_len)
+		return;
+
+	blob_len = fdt_totalsize(*blob) + extra_len;
+	*blob = xrealloc(*blob, blob_len);
+	fdt_open_into(*blob, *blob, blob_len);
+}
+
+static int reload_blob(char *filename, char **blob, off_t extra_len)
+{
+	size_t len;
+
+	free(*blob);
+	*blob = utilfdt_read(filename, &len);
+	if (!*blob) {
+		fprintf(stderr, "Failed to reload blob %s\n", filename);
+		return -1;
+	}
+
+	grow_blob(blob, extra_len);
+
+	return 0;
+}
+
+static int do_fdtoverlay_merge(const char *input_filename,
+			 const char *output_filename,
+			 int argc, char *argv[])
+{
+	char *blob = NULL;
+	char **ovblob = NULL;
+	size_t ov_len, blob_len, total_len, extra_blob_len = 0;
+	off_t *extra_ov_len;
+	int i, ret = -1;
+
+	/* allocate blob pointer array */
+	ovblob = xmalloc(sizeof(*ovblob) * argc);
+	memset(ovblob, 0, sizeof(*ovblob) * argc);
+
+	extra_ov_len = xmalloc(sizeof(*extra_ov_len) * argc);
+	memset(extra_ov_len, 0, sizeof(*extra_ov_len) * argc);
+
+reload_all_blobs:
+	/* Free existing buffer first */
+	free(blob);
+	blob = utilfdt_read(input_filename, &blob_len);
+	if (!blob) {
+		fprintf(stderr, "\nFailed to read base blob %s\n",
+				input_filename);
+		goto out_err;
+	}
+	if (fdt_totalsize(blob) > blob_len) {
+		fprintf(stderr,
+		 "\nBase blob is incomplete (%lu / %" PRIu32 " bytes read)\n",
+			(unsigned long)blob_len, fdt_totalsize(blob));
+		goto out_err;
+	}
+	ret = 0;
+
+	/* read and keep track of the overlay blobs */
+	total_len = extra_blob_len;
+	for (i = 0; i < argc; i++) {
+		/* Free existing buffer first */
+		free(ovblob[i]);
+		ovblob[i] = utilfdt_read(argv[i], &ov_len);
+		if (!ovblob[i]) {
+			fprintf(stderr, "\nFailed to read overlay %s\n",
+					argv[i]);
+			goto out_err;
+		}
+		grow_blob(&ovblob[i], extra_ov_len[i]);
+		total_len += ov_len + extra_ov_len[i];
+	}
+
+	/* grow the blob to worst case */
+	grow_blob(&blob, total_len);
+
+	/* apply the overlays in sequence */
+	for (i = 0; i < argc; i++) {
+		do {
+			int fdto_nospace;
+
+			fprintf(stderr, "Merging overlay blob %s\n", argv[i]);
+			ret = fdt_overlay_merge(blob, ovblob[i], &fdto_nospace);
+			if (ret && ret == -FDT_ERR_NOSPACE) {
+				if (fdto_nospace) {
+					extra_ov_len[i] += 512;
+					fprintf(stderr, "Reloading overlay blob %s\n", argv[i]);
+					ret = reload_blob(argv[i], &ovblob[i], extra_ov_len[i]);
+					if (!ret)
+						continue;
+				} else {
+					extra_blob_len += 512;
+					fprintf(stderr, "Reloading all blobs\n");
+					goto reload_all_blobs;
+				}
+			}
+
+			if (!ret)
+				break;
+
+			if (ret) {
+				fprintf(stderr, "\nFailed to merge %s (%d)\n",
+						argv[i], ret);
+				goto out_err;
+			}
+		} while (1);
+	}
+
+	fdt_pack(blob);
+	ret = utilfdt_write(output_filename, blob);
+	if (ret)
+		fprintf(stderr, "\nFailed to write output blob %s\n",
+				output_filename);
+
+out_err:
+	if (ovblob) {
+		for (i = 0; i < argc; i++) {
+			if (ovblob[i])
+				free(ovblob[i]);
+		}
+		free(ovblob);
+	}
+	free(blob);
+
+	return ret;
+}
+
+int main(int argc, char *argv[])
+{
+	int opt, i;
+	char *input_filename = NULL;
+	char *output_filename = NULL;
+
+	while ((opt = util_getopt_long()) != EOF) {
+		switch (opt) {
+		case_USAGE_COMMON_FLAGS
+
+		case 'i':
+			input_filename = optarg;
+			break;
+		case 'o':
+			output_filename = optarg;
+			break;
+		case 'v':
+			verbose = 1;
+			break;
+		}
+	}
+
+	if (!input_filename)
+		usage("missing input file");
+
+	if (!output_filename)
+		usage("missing output file");
+
+	argv += optind;
+	argc -= optind;
+
+	if (argc <= 0)
+		usage("missing overlay file(s)");
+
+	if (verbose) {
+		printf("input  = %s\n", input_filename);
+		printf("output = %s\n", output_filename);
+		for (i = 0; i < argc; i++)
+			printf("overlay[%d] = %s\n", i, argv[i]);
+	}
+
+	if (do_fdtoverlay_merge(input_filename, output_filename, argc, argv))
+		return 1;
+
+	return 0;
+}
diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index d3a567f..bf639c5 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -12,7 +12,7 @@
 
 #include "libfdt_internal.h"
 
-#define ULONG_MAX	(~0UL)
+/* #define ULONG_MAX	(~0UL) */
 
 /**
  * overlay_get_target_phandle - retrieves the target phandle of a fragment
@@ -408,7 +408,7 @@ static int overlay_fixup_one_phandle(void *fdt, void *fdto,
 						   sizeof(phandle_prop));
 };
 
-#define PATH_MAX	256
+/* #define PATH_MAX	256 */
 
 static int overlay_add_to_local_fixups(void *fdt, const char *value, int len)
 {
@@ -1510,8 +1510,8 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	uint32_t delta = fdt_get_max_phandle(fdt);
 	int ret;
 
-	FDT_CHECK_HEADER(fdt);
-	FDT_CHECK_HEADER(fdto);
+	FDT_RO_PROBE(fdt);
+	FDT_RO_PROBE(fdto);
 
 	*fdto_nospace = 0;
 
-- 
2.7.4

Re: [PATCH v2 0/6] Introduce fdt_overlay_merge() to allow merge of overlay blob

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 5313 bytes --]

On Wed, Sep 09, 2020 at 10:17:56AM -0700, Gurbir Arora wrote:
> Hello Upstream Team,
> 
>          This is the second upstream attempt for the fdtoverlay changes and the first attempt can
> be found here: https://www.spinics.net/lists/devicetree-compiler/msg01949.html. All of the
> issues/comments from the first attempt have been addressed and fixed in this patch.

Sorry I've taken so long to look at this.  Before delving into the
code, I think I need to understand your use case a bit better.

There's some confusion here, because there's at least 2 things that
"merging overlays" could mean.

1) Combining 2 overlays into one which will have the same effect as
both applied sequentially.  This is almost trivial, since you can just
list all the fragments of the first, followed by all the fragments of
the second, with only the fixups nodes needing to be actually
"merged".

The question is, does this alone provide any tangible benefit over
just processing a list of overlays in order.

2) "Partially resolving" an overlay.  That is finding cases where we
can determine enough about the targets of 2 fragments that we can
combine the fragments together.  It's entirely possible - both in
theory and in practice with dtc - for a single overlay to have
multiple fragments targetting the same node (or one targetting a
subnode of the first).  Thus, this is something that makes logical
sense on a single overlay.

If you really need both of these operations, I'd suggest separate
entry points for them, so that your "merge" would be (1) followed by
(2) on the result.

> Changelog:
> 
> v1 -> v2: 
> - Introduction of new entry point, fdt_overlay_merge(), to handles merging
>   overlay blobs (rather than overload that in fdt_overlay_apply()).
> - Removed use of printf() in libfdt. snprintf() is still used to help with string
>   manipulation.
> - Changed the logic to identify fragment nodes.
> - Removed use of malloc/calloc and global variables.
> - Incorporated a function that copies a node in the overlay tree along with its children and their
> properties.
> 
> fdt_overlay_apply() API currently allows for an overlay DT blob to be merged
> with a base blob. It assumes that all external symbols specified in overlay
> blob's __fixups__ section are found in base blob's __symbols__ section and
> aborts on the first instance where a symbol could not be found in base blob.
> 
> This is mostly fine as the primary use of overlay is on a target for its
> bootloader to merge various overlay blobs based on h/w configuration detected?
> 
> We are exploring an extended use of fdt_overlay_apply() for offline use, i.e on
> the host (build machine) side, which requires merging two overlay DT blobs i.e
> the base (overlay) blob will not resolve all the external node references found
> in overlay blob.
> 
> Currently all the device-tree (DT) code for a given soc is maintained in a
> common kernel repository. For example, this common DT code will have code for
> audio, video, fingerprint, bluetooth etc. Further this DT code is typically
> split into a base (soc-common) code and board specific code, with the soc code
> being compiled as soc.dtb and board specific code being compiled as respective
> overlay blobs (board1.dtbo, board2.dtbo etc). soc.dtb represents hardware configuration
> of a given SOC while boardX.dtbo represents configuration of a board/platform 
> designed using that soc.soc.dtb and boardX.dtbo files are flashed separately on 
> target (besides improving the overall size of DT blobs flashed on target, Android 
> Treble also requires separation of soc and board DT bits). Bootloader will pick 
> one of the board overlay blobs and merge it with soc.dtb, before booting kernel 
> which is presented a unified DT blob (soc + board overlay).
> 
> For ease of code maintenance and better control over release management, we are
> exploring allowing some of the tech teams (audio/fingerprint sensor etc) to
> maintain their kernel code (including their DT code) outside a common kernel
> repository. In our experience, this simplifies number of branches maintained in
> core kernel repo. New/experimental features in fingerprint sensor driver for
> example that needs to be on a separate branch will not result in unnecessary
> branching in core kenrel repo, affecting all other drivers.
> 
> In addition to compiling DT code outside core kernel tree, we also want to merge
> the blobs back to respective blobs found in kernel build tree (soc.dtb or
> boardX.dtbo), as otherwise relying on bootloader to do all the overlay impacts
> boot-time.
> 
> This brings up the need to merge two overlay blobs (fingerprint-overlay.dtbo +
> boardX.dtbo), which currently doesn't seem to be supported and which this patch
> series aims to support.

Can you connect the dots a bit more as to why your neeed overlay
merging?  If the concern is boot time, then it seems like you want to
merge everything into the base tree before boot time, in which case
you can just apply all the overlays in order.


-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v2 3/6] libfdt: overlay_merge: Ignore unresolved symbols

[Gurbir Arora]

From: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>

fdt_overlay_merge(), like fdt_overlay_apply(), has to perform similar operations
on DT blobs, one of which is going through external symbol references specified
in __fixups__ node of overlay DT blob and resolving them in base DT blob (as
performed by overlay_fixup_phandles()).

Unlike overlay case though, in case of merging two overlay blobs, its quite
normal that some of the external references specified in __fixups__ node are not
found in base blob. Modify overlay_fixup_phandles() to understand this
possibility.

Signed-off-by: Srivatsa Vaddagiri <vatsa-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
---
 libfdt/fdt_overlay.c | 219 +++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 205 insertions(+), 14 deletions(-)

diff --git a/libfdt/fdt_overlay.c b/libfdt/fdt_overlay.c
index d7d6f03..9ea106a 100644
--- a/libfdt/fdt_overlay.c
+++ b/libfdt/fdt_overlay.c
@@ -408,12 +408,147 @@ static int overlay_fixup_one_phandle(void *fdt, void *fdto,
 						   sizeof(phandle_prop));
 };
 
+#define PATH_MAX	256
+
+static int overlay_add_to_local_fixups(void *fdt, const char *value, int len)
+{
+	const char *path, *fixup_end, *prop;
+	const char *fixup_str = value;
+	uint32_t clen;
+	uint32_t fixup_len;
+	char *sep, *endptr;
+	const char *c;
+	int poffset, nodeoffset, ret, localfixup_off;
+	int pathlen, proplen;
+	char propname[PATH_MAX];
+
+	localfixup_off = fdt_path_offset(fdt, "/__local_fixups__");
+	if (localfixup_off < 0 && localfixup_off == -FDT_ERR_NOTFOUND)
+		localfixup_off = fdt_add_subnode(fdt, 0, "__local_fixups__");
+
+	if (localfixup_off < 0)
+		return localfixup_off;
+
+	while (len > 0) {
+		/* Assumes null-terminated properties! */
+		fixup_end = memchr(value, '\0', len);
+		if (!fixup_end)
+			return -FDT_ERR_BADOVERLAY;
+
+		fixup_len = fixup_end - fixup_str;
+
+		len -= (fixup_len + 1);
+		value += fixup_len + 1;
+
+		c = path = fixup_str;
+		sep = memchr(c, ':', fixup_len);
+		if (!sep || *sep != ':')
+			return -FDT_ERR_BADOVERLAY;
+		pathlen = sep - path;
+		if (pathlen == (fixup_len - 1))
+			return -FDT_ERR_BADOVERLAY;
+
+		fixup_len -= (pathlen + 1);
+		c = path + pathlen + 1;
+
+		sep = memchr(c, ':', fixup_len);
+		if (!sep || *sep != ':')
+			return -FDT_ERR_BADOVERLAY;
+
+		prop = c;
+		proplen = sep - c;
+
+		if (proplen >= PATH_MAX)
+			return -FDT_ERR_BADOVERLAY;
+
+		/*
+		 * Skip fixups that involves the special 'target' property found
+		 * in overlay fragments such as
+		 *	/fragment@0:target:0
+		 *
+		 * The check for one node in path below is to ensure that we
+		 * handle 'target' properties present otherwise in any other
+		 * node, for ex:
+		 *	/fragment@0/__overlay__/xyz:target:0
+		 */
+
+		/* Does path have exactly one node? */
+		c = path;
+		clen = pathlen;
+		if (*c == '/') {
+			c++;
+			clen -= 1;
+		}
+
+		sep = memchr(c, '/', clen);
+		if (!sep && proplen >= 6 && !strncmp(prop, "target", 6))
+			continue;
+
+		memcpy(propname, prop, proplen);
+		propname[proplen] = 0;
+
+		fixup_len -= (proplen + 1);
+		c = prop + proplen + 1;
+		poffset = strtoul(c, &endptr, 10);
+
+		nodeoffset = localfixup_off;
+
+		c = path;
+		clen = pathlen;
+
+		if (*c == '/') {
+			c++;
+			clen -= 1;
+		}
+
+		while (clen > 0) {
+			char nodename[PATH_MAX];
+			int nodelen, childnode;
+
+			sep = memchr(c, '/', clen);
+			if (!sep)
+				nodelen = clen;
+			else
+				nodelen = sep - c;
+
+			if (nodelen + 1 >= PATH_MAX)
+				return -FDT_ERR_BADSTRUCTURE;
+			memcpy(nodename, c, nodelen);
+			nodename[nodelen] = 0;
+
+			childnode = fdt_add_subnode(fdt, nodeoffset, nodename);
+			if (childnode == -FDT_ERR_EXISTS)
+				childnode = fdt_subnode_offset(fdt,
+							      nodeoffset, nodename);
+			nodeoffset = childnode;
+			if (nodeoffset < 0)
+				return nodeoffset;
+
+			c += nodelen;
+			clen -= nodelen;
+
+			if (*c == '/') {
+				c++;
+				clen -= 1;
+			}
+		}
+
+		ret = fdt_setprop_u32(fdt, nodeoffset, propname, poffset);
+		if (ret < 0)
+			return ret;
+	}
+
+	return 0;
+}
+
 /**
  * overlay_fixup_phandle - Set an overlay phandle to the base one
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
  * @symbols_off: Node offset of the symbols node in the base device tree
  * @property: Property offset in the overlay holding the list of fixups
+ * @fixups_off: Offset of __fixups__ node in @fdto
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_fixup_phandle() resolves all the overlay phandles pointed
  * to in a __fixups__ property, and updates them to match the phandles
@@ -428,11 +563,11 @@ static int overlay_fixup_one_phandle(void *fdt, void *fdto,
  *      Negative error code on failure
  */
 static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
-				 int property)
+				int property, int fixups_off, int merge)
 {
 	const char *value;
 	const char *label;
-	int len;
+	int len, ret = 0;
 
 	value = fdt_getprop_by_offset(fdto, property,
 				      &label, &len);
@@ -449,7 +584,7 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
 		uint32_t path_len, name_len;
 		uint32_t fixup_len;
 		char *sep, *endptr;
-		int poffset, ret;
+		int poffset;
 
 		fixup_end = memchr(value, '\0', len);
 		if (!fixup_end)
@@ -489,7 +624,36 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
 			return ret;
 	} while (len > 0);
 
-	return 0;
+	/*
+	 * Properties found in __fixups__ node are typically one of
+	 * these types:
+	 *
+	 * 	abc = "/fragment@2:target:0"		(first type)
+	 *	abc = "/fragment@2/__overlay__:xyz:0"	(second type)
+	 *
+	 * Both types could also be present in some properties as well such as:
+	 *
+	 *	abc = "/fragment@2:target:0", "/fragment@2/__overlay__:xyz:0"
+	 *
+	 * While merging two overlay blobs, a successful overlay phandle fixup
+	 * of second type needs to be recorded in __local_fixups__ node of the
+	 * combined blob, so that the phandle value can be further updated via
+	 * overlay_update_local_references() when the combined overlay blob gets
+	 * overlaid on a different base blob.
+	 *
+	 * Further, since in the case of merging two overlay blobs, we will also
+	 * be merging contents of nodes such as __fixups__ from both overlay
+	 * blobs, delete this property in __fixup__  node, as it no longer
+	 * represents a external phandle reference that needs to be resolved
+	 * during a subsequent overlay of combined blob on a base blob.
+	 */
+	if (merge) {
+		ret = overlay_add_to_local_fixups(fdt, value, len);
+		if (!ret)
+			ret = fdt_delprop(fdto, fixups_off, label);
+	}
+
+	return ret;
 }
 
 /**
@@ -497,6 +661,7 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
  *                          device tree
  * @fdt: Base Device Tree blob
  * @fdto: Device tree overlay blob
+ * @merge: Both input blobs are overlay blobs that are being merged
  *
  * overlay_fixup_phandles() resolves all the overlay phandles pointing
  * to nodes in the base device tree.
@@ -509,10 +674,10 @@ static int overlay_fixup_phandle(void *fdt, void *fdto, int symbols_off,
  *      0 on success
  *      Negative error code on failure
  */
-static int overlay_fixup_phandles(void *fdt, void *fdto)
+static int overlay_fixup_phandles(void *fdt, void *fdto, int merge)
 {
 	int fixups_off, symbols_off;
-	int property;
+	int property, ret = 0, next_property;
 
 	/* We can have overlays without any fixups */
 	fixups_off = fdt_path_offset(fdto, "/__fixups__");
@@ -526,15 +691,41 @@ static int overlay_fixup_phandles(void *fdt, void *fdto)
 	if ((symbols_off < 0 && (symbols_off != -FDT_ERR_NOTFOUND)))
 		return symbols_off;
 
-	fdt_for_each_property_offset(property, fdto, fixups_off) {
-		int ret;
-
-		ret = overlay_fixup_phandle(fdt, fdto, symbols_off, property);
-		if (ret)
+	/* Safeguard against property being deleted in below loop */
+	property = fdt_first_property_offset(fdto, fixups_off);
+	while (property >= 0) {
+		next_property = fdt_next_property_offset(fdto, property);
+		ret = overlay_fixup_phandle(fdt, fdto, symbols_off,
+					   property, fixups_off, merge);
+		if (ret && (!merge || ret != -FDT_ERR_NOTFOUND))
 			return ret;
+
+		if (merge && !ret) {
+			/* Bail if this was the last property */
+			if (next_property < 0)
+				break;
+
+			/*
+			 * Property is deleted in this case. Next property is
+			 * available at the same offset, so loop back with
+			 * 'property' offset unmodified. Also since @fdt would
+			 * have been modified in this case, refresh the offset
+			 * of /__symbols__ node
+			 */
+			symbols_off = fdt_path_offset(fdt, "/__symbols__");
+			if (symbols_off < 0)
+				return symbols_off;
+
+			continue;
+		}
+
+		property = next_property;
 	}
 
-	return 0;
+	if (merge && ret == -FDT_ERR_NOTFOUND)
+		ret = 0;
+
+	return ret;
 }
 
 /**
@@ -849,7 +1040,7 @@ int fdt_overlay_apply(void *fdt, void *fdto)
 	if (ret)
 		goto err;
 
-	ret = overlay_fixup_phandles(fdt, fdto);
+	ret = overlay_fixup_phandles(fdt, fdto, 0);
 	if (ret)
 		goto err;
 
@@ -1227,7 +1418,7 @@ int fdt_overlay_merge(void *fdt, void *fdto, int *fdto_nospace)
 	if (ret)
 		goto err;
 
-	ret = overlay_fixup_phandles(fdt, fdto);
+	ret = overlay_fixup_phandles(fdt, fdto, 1);
 	if (ret)
 		goto err;
 
-- 
2.7.4