Searching for duplicate names scales O(n^2) with the number of names
added to a fdt, which can cause a noticable slowdown with larger device
trees and very slow CPU cores.
Add fdt_property_nocompress variants that allow the caller to trade
size for speed.
A more comprehensive approach may be a new fdt building API with state
that allows control of these tradeoffs, or in-memory data structures
that can get the best of both worlds. But this simple approach is usable
for now. This adds no real compatibility burden because defining the new
calls to be identical to old is a valid implementation.
Signed-off-by: Nicholas Piggin <npiggin@xxxxxxxxx>
---
libfdt/fdt_sw.c | 54 +++++++++++++++++++++++++++++++++++++++++++------
libfdt/libfdt.h | 15 ++++++++++++++
2 files changed, 63 insertions(+), 6 deletions(-)
diff --git a/libfdt/fdt_sw.c b/libfdt/fdt_sw.c
index 9fa4a94..dbc2e6e 100644
--- a/libfdt/fdt_sw.c
+++ b/libfdt/fdt_sw.c
@@ -262,18 +262,13 @@ int fdt_end_node(void *fdt)
return 0;
}
-static int fdt_find_add_string_(void *fdt, const char *s)
+static int fdt_add_string_(void *fdt, const char *s)
{
char *strtab = (char *)fdt + fdt_totalsize(fdt);
- const char *p;
int strtabsize = fdt_size_dt_strings(fdt);
int len = strlen(s) + 1;
int struct_top, offset;
- p = fdt_find_string_(strtab - strtabsize, strtabsize, s);
- if (p)
- return p - strtab;
-
/* Add it */
offset = -strtabsize - len;
struct_top = fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt);
@@ -285,6 +280,19 @@ static int fdt_find_add_string_(void *fdt, const char *s)
return offset;
}
+static int fdt_find_add_string_(void *fdt, const char *s)
+{
+ char *strtab = (char *)fdt + fdt_totalsize(fdt);
+ int strtabsize = fdt_size_dt_strings(fdt);
+ const char *p;
+
+ p = fdt_find_string_(strtab - strtabsize, strtabsize, s);
+ if (p)
+ return p - strtab;
+
+ return fdt_add_string_(fdt, s);
+}
+
int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp)
{
struct fdt_property *prop;
@@ -307,6 +315,28 @@ int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp)
return 0;
}
+int fdt_property_placeholder_nocompress(void *fdt, const char *name, int len, void **valp)
+{
+ struct fdt_property *prop;
+ int nameoff;
+
+ FDT_SW_PROBE_STRUCT(fdt);
+
+ nameoff = fdt_add_string_(fdt, name);
+ if (nameoff == 0)
+ return -FDT_ERR_NOSPACE;
+
+ prop = fdt_grab_space_(fdt, sizeof(*prop) + FDT_TAGALIGN(len));
+ if (! prop)
+ return -FDT_ERR_NOSPACE;
+
+ prop->tag = cpu_to_fdt32(FDT_PROP);
+ prop->nameoff = cpu_to_fdt32(nameoff);
+ prop->len = cpu_to_fdt32(len);
+ *valp = prop->data;
+ return 0;
+}
+
int fdt_property(void *fdt, const char *name, const void *val, int len)
{
void *ptr;
@@ -319,6 +349,18 @@ int fdt_property(void *fdt, const char *name, const void *val, int len)
return 0;
}
+int fdt_property_nocompress(void *fdt, const char *name, const void *val, int len)
+{
+ void *ptr;
+ int ret;
+
+ ret = fdt_property_placeholder_nocompress(fdt, name, len, &ptr);
+ if (ret)
+ return ret;
+ memcpy(ptr, val, len);
+ return 0;
+}
+
int fdt_finish(void *fdt)
{
char *p = (char *)fdt;
diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
index 1f44177..5c1428c 100644
--- a/libfdt/libfdt.h
+++ b/libfdt/libfdt.h
@@ -1435,11 +1435,17 @@ int fdt_add_reservemap_entry(void *fdt, uint64_t addr, uint64_t size);
int fdt_finish_reservemap(void *fdt);
int fdt_begin_node(void *fdt, const char *name);
int fdt_property(void *fdt, const char *name, const void *val, int len);
+int fdt_property_nocompress(void *fdt, const char *name, const void *val, int len);
static inline int fdt_property_u32(void *fdt, const char *name, uint32_t val)
{
fdt32_t tmp = cpu_to_fdt32(val);
return fdt_property(fdt, name, &tmp, sizeof(tmp));
}
+static inline int fdt_property_u32_nocompress(void *fdt, const char *name, uint32_t val)
+{
+ fdt32_t tmp = cpu_to_fdt32(val);
+ return fdt_property_nocompress(fdt, name, &tmp, sizeof(tmp));
+}
static inline int fdt_property_u64(void *fdt, const char *name, uint64_t val)
{
fdt64_t tmp = cpu_to_fdt64(val);
@@ -1451,6 +1457,10 @@ static inline int fdt_property_cell(void *fdt, const char *name, uint32_t val)
{
return fdt_property_u32(fdt, name, val);
}
+static inline int fdt_property_cell_nocompress(void *fdt, const char *name, uint32_t val)
+{
+ return fdt_property_u32_nocompress(fdt, name, val);
+}
#endif
/**
@@ -1468,6 +1478,11 @@ static inline int fdt_property_cell(void *fdt, const char *name, uint32_t val)
*/
int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp);
+/**
+ * fdt_property_placeholder_nocompress - same as fdt_property_placeholder, trade size for speed
+ */
+int fdt_property_placeholder_nocompress(void *fdt, const char *name, int len, void **valp);
+
#define fdt_property_string(fdt, name, str) \
fdt_property(fdt, name, str, strlen(str)+1)
int fdt_end_node(void *fdt);
--
2.20.1
