Fix the problem of not enough merged dtb size

The dtc has suffix compression for string, ex. "a_string", "string"
and "ing", these strings could share a same string in dtb
string table. libufdt assumes the merged dtb size shouldn't larger
than the summary size of base and overlay dtb, and doesn't
apply the same compression.

The patch add a test case for this case and fix the problem.

Bug: 35255584
Test: tests/run_tests.sh
Change-Id: I6bac1e2823ca90dbdb852452544c41ab040a5ccc

7 files changed, 54 insertions, 2 deletions

diff --git a/fdt_internal.h b/fdt_internal.h
index 1ac9d68..4d7ca47 100644
--- a/fdt_internal.h
+++ b/fdt_internal.h
@@ -100,12 +100,27 @@ static void *_fdt_grab_space(void *fdt, size_t len) {
   return _fdt_offset_ptr_w(fdt, offset);
 }
 
-static int _fdt_add_string(void *fdt, const char *s) {
+static const char *_fdt_find_string(const char *strtab, int tabsize,
+                                    const char *s) {
+  int len = dto_strlen(s) + 1;
+  const char *last = strtab + tabsize - len;
+  const char *p;
+
+  for (p = strtab; p <= last; p++)
+    if (dto_memcmp(p, s, len) == 0) return p;
+  return NULL;
+}
+
+static int _fdt_find_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 = dto_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);
@@ -128,7 +143,7 @@ static int fast_fdt_sw_property(void *fdt, const char *name, const void *val,
   FDT_SW_CHECK_HEADER(fdt);
 
   if (*pnameoff == 0) {
-    *pnameoff = _fdt_add_string(fdt, name);
+    *pnameoff = _fdt_find_add_string(fdt, name);
     if (*pnameoff == 0) return -FDT_ERR_NOSPACE;
   }
 
diff --git a/sysdeps/include/libufdt_sysdeps.h b/sysdeps/include/libufdt_sysdeps.h
index c2682c7..fb5584f 100644
--- a/sysdeps/include/libufdt_sysdeps.h
+++ b/sysdeps/include/libufdt_sysdeps.h
@@ -48,6 +48,8 @@ unsigned long int dto_strtoul(const char *nptr, char **endptr, int base);
 
 size_t dto_strlen(const char *s);
 
+int dto_memcmp(const void *lhs, const void *rhs, size_t n);
+
 void *dto_memcpy(void *dest, const void *src, size_t n);
 
 int dto_strcmp(const char *s1, const char *s2);
diff --git a/sysdeps/libufdt_sysdeps_posix.c b/sysdeps/libufdt_sysdeps_posix.c
index c8a08f6..d7a198f 100644
--- a/sysdeps/libufdt_sysdeps_posix.c
+++ b/sysdeps/libufdt_sysdeps_posix.c
@@ -36,6 +36,10 @@ unsigned long int dto_strtoul(const char *nptr, char **endptr, int base) {
 
 size_t dto_strlen(const char *s) { return strlen(s); }
 
+int dto_memcmp(const void *lhs, const void *rhs, size_t n) {
+  return memcmp(lhs, rhs, n);
+}
+
 void *dto_memcpy(void *dest, const void *src, size_t n) {
   return memcpy(dest, src, n);
 }
diff --git a/sysdeps/libufdt_sysdeps_vendor.c b/sysdeps/libufdt_sysdeps_vendor.c
index e21a2e1..12e7695 100644
--- a/sysdeps/libufdt_sysdeps_vendor.c
+++ b/sysdeps/libufdt_sysdeps_vendor.c
@@ -194,6 +194,10 @@ unsigned long int dto_strtoul(const char *nptr, char **endptr, int base) {
 
 size_t dto_strlen(const char *s) { return strlen(s); }
 
+int dto_memcmp(const void *lhs, const void *rhs, size_t n) {
+  return memcmp(lhs, rhs, n);
+}
+
 void *dto_memcpy(void *dest, const void *src, size_t n) {
   return memcpy(dest, src, n);
 }
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 4513950..ea3e5ba 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -69,6 +69,9 @@ main() {
   run_test_case \
     "empty_overlay" \
     "Run test about overlaying with empty base and overlay dt"
+  run_test_case \
+    "suffix_compress" \
+    "Run test about string suffix compression"
   )
 
   if [ $? -ne 0 ]; then
diff --git a/tests/testdata/suffix_compress-base.dts b/tests/testdata/suffix_compress-base.dts
new file mode 100644
index 0000000..1c51284
--- /dev/null
+++ b/tests/testdata/suffix_compress-base.dts
@@ -0,0 +1,18 @@
+/dts-v1/;
+
+/ {
+  /* these name could be suffix compressed in dtb after compiled */
+  longlonglonglonglonglonglonglonglonglonglonglongname: longlonglonglonglonglonglonglonglonglonglonglongname {};
+  longlonglonglonglonglonglonglonglonglonglongname: longlonglonglonglonglonglonglonglonglonglongname {};
+  longlonglonglonglonglonglonglonglonglongname: longlonglonglonglonglonglonglonglonglongname {};
+  longlonglonglonglonglonglonglonglongname: longlonglonglonglonglonglonglonglongname {};
+  longlonglonglonglonglonglonglongname: longlonglonglonglonglonglonglongname {};
+  longlonglonglonglonglonglongname: longlonglonglonglonglonglongname {};
+  longlonglonglonglonglongname: longlonglonglonglonglongname {};
+  longlonglonglonglongname: longlonglonglonglongname {};
+  longlonglonglongname: longlonglonglongname {};
+  longlonglongname: longlonglongname {};
+  longlongname: longlongname {};
+  longname: longname {};
+};
+
diff --git a/tests/testdata/suffix_compress-overlay.dts b/tests/testdata/suffix_compress-overlay.dts
new file mode 100644
index 0000000..382e376
--- /dev/null
+++ b/tests/testdata/suffix_compress-overlay.dts
@@ -0,0 +1,6 @@
+/dts-v1/;
+/plugin/;
+
+&longname {
+  x {};
+};