release-request-4850daec-e2fc-44da-a2dc-4646a78e4550-for-git_oc-dr1-release-3944849 snap-temp-L34500000057864766

Change-Id: I5472ab916041d82652501fc86272f9f4f657e168

8 files changed, 343 insertions, 49 deletions

diff --git a/Android.mk b/Android.mk
index 31012b3..3f56c42 100644
--- a/Android.mk
+++ b/Android.mk
@@ -18,6 +18,7 @@ common_src_files := \
     ufdt_overlay.c \
     ufdt_convert.c \
     ufdt_node.c \
+    ufdt_node_pool.c \
     ufdt_prop_dict.c
 
 ###################################################
diff --git a/include/libufdt.h b/include/libufdt.h
index 03dffef..04c7bc8 100644
--- a/include/libufdt.h
+++ b/include/libufdt.h
@@ -33,12 +33,13 @@
  * @return: a pointer to the newly created ufdt_node or
  *          NULL if dto_malloc failed
  */
-struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr);
+struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr,
+                                      struct ufdt_node_pool *pool);
 
 /*
  * Frees all nodes in the subtree rooted at *node.
  */
-void ufdt_node_destruct(struct ufdt_node *node);
+void ufdt_node_destruct(struct ufdt_node *node, struct ufdt_node_pool *pool);
 
 /*
  * Adds the child as a subnode of the parent.
@@ -152,13 +153,13 @@ uint32_t ufdt_node_get_phandle(const struct ufdt_node *node);
  *
  * @return: an empty ufdt with base fdtp = fdtp
  */
-struct ufdt *ufdt_construct(void *fdtp);
+struct ufdt *ufdt_construct(void *fdtp, struct ufdt_node_pool *pool);
 
 /*
  * Frees the space occupied by the ufdt, including all ufdt_nodes
  * with ufdt_static_phandle_table.
  */
-void ufdt_destruct(struct ufdt *tree);
+void ufdt_destruct(struct ufdt *tree, struct ufdt_node_pool *pool);
 
 /*
  * Add a fdt into this ufdt.
@@ -265,7 +266,8 @@ bool ufdt_node_name_eq(const struct ufdt_node *node, const char *name, int len);
  *
  * @Time: O(# of nodes in tree_b + total length of all names in tree_b) w.h.p.
  */
-int ufdt_node_merge_into(struct ufdt_node *node_a, struct ufdt_node *node_b);
+int ufdt_node_merge_into(struct ufdt_node *node_a, struct ufdt_node *node_b,
+                         struct ufdt_node_pool *pool);
 
 /*
  * END of ufdt methods.
@@ -283,7 +285,8 @@ int ufdt_node_merge_into(struct ufdt_node *node_a, struct ufdt_node *node_b);
  *
  * @Time: O(fdt_size + nlogn) where n = # of nodes in fdt.
  */
-struct ufdt *ufdt_from_fdt(void *fdtp, size_t fdt_size);
+struct ufdt *ufdt_from_fdt(void *fdtp, size_t fdt_size,
+                           struct ufdt_node_pool *pool);
 
 /*
  * Sequentially dumps the whole ufdt to FDT buffer fdtp with buffer size
diff --git a/include/ufdt_node_pool.h b/include/ufdt_node_pool.h
new file mode 100644
index 0000000..cf4e03b
--- /dev/null
+++ b/include/ufdt_node_pool.h
@@ -0,0 +1,36 @@
+#ifndef UFDT_NODE_POOL_H
+#define UFDT_NODE_POOL_H
+
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+struct ufdt_node_pool_block_header;
+
+struct ufdt_node_pool {
+  /* A single linked list contains all blocks.
+     Blocks with one or more unused entries are in front;
+     blocks without unused entry are in rear. */
+  struct ufdt_node_pool_block_header *first_block;
+  struct ufdt_node_pool_block_header **last_block_ptr;
+};
+
+void ufdt_node_pool_construct(struct ufdt_node_pool *pool);
+void ufdt_node_pool_destruct(struct ufdt_node_pool *pool);
+
+void *ufdt_node_pool_alloc(struct ufdt_node_pool *pool);
+void ufdt_node_pool_free(struct ufdt_node_pool *pool, void *node);
+
+#endif
diff --git a/include/ufdt_types.h b/include/ufdt_types.h
index b741f82..867e2c7 100644
--- a/include/ufdt_types.h
+++ b/include/ufdt_types.h
@@ -85,4 +85,6 @@ struct ufdt {
   struct ufdt_static_phandle_table phandle_table;
 };
 
+struct ufdt_node_pool;
+
 #endif /* UFDT_TYPES_H */
diff --git a/ufdt_convert.c b/ufdt_convert.c
index 2d0750b..9d7c698 100644
--- a/ufdt_convert.c
+++ b/ufdt_convert.c
@@ -16,9 +16,12 @@
 
 #include "libufdt.h"
 
+#include "ufdt_node_pool.h"
 #include "ufdt_prop_dict.h"
 
-struct ufdt *ufdt_construct(void *fdtp) {
+struct ufdt *ufdt_construct(void *fdtp, struct ufdt_node_pool *pool) {
+  (void)(pool); /* unused parameter */
+
   /* Inital size is 2, will be exponentially increased when it needed later.
      (2 -> 4 -> 8 -> ...) */
   const int DEFAULT_MEM_SIZE_FDTPS = 2;
@@ -47,10 +50,10 @@ error:
   return NULL;
 }
 
-void ufdt_destruct(struct ufdt *tree) {
+void ufdt_destruct(struct ufdt *tree, struct ufdt_node_pool *pool) {
   if (tree == NULL) return;
 
-  ufdt_node_destruct(tree->root);
+  ufdt_node_destruct(tree->root, pool);
 
   dto_free(tree->fdtps);
   dto_free(tree->phandle_table.data);
@@ -105,7 +108,8 @@ int ufdt_get_string_off(const struct ufdt *tree, const char *s) {
   return 0;
 }
 
-static struct ufdt_node *ufdt_new_node(void *fdtp, int node_offset) {
+static struct ufdt_node *ufdt_new_node(void *fdtp, int node_offset,
+                                       struct ufdt_node_pool *pool) {
   if (fdtp == NULL) {
     dto_error("Failed to get new_node because tree is NULL\n");
     return NULL;
@@ -113,13 +117,13 @@ static struct ufdt_node *ufdt_new_node(void *fdtp, int node_offset) {
 
   fdt32_t *fdt_tag_ptr =
       (fdt32_t *)fdt_offset_ptr(fdtp, node_offset, sizeof(fdt32_t));
-  struct ufdt_node *res = ufdt_node_construct(fdtp, fdt_tag_ptr);
+  struct ufdt_node *res = ufdt_node_construct(fdtp, fdt_tag_ptr, pool);
   return res;
 }
 
 static struct ufdt_node *fdt_to_ufdt_tree(void *fdtp, int cur_fdt_tag_offset,
-                                          int *next_fdt_tag_offset,
-                                          int cur_tag) {
+                                          int *next_fdt_tag_offset, int cur_tag,
+                                          struct ufdt_node_pool *pool) {
   if (fdtp == NULL) {
     return NULL;
   }
@@ -137,17 +141,17 @@ static struct ufdt_node *fdt_to_ufdt_tree(void *fdtp, int cur_fdt_tag_offset,
       break;
 
     case FDT_PROP:
-      res = ufdt_new_node(fdtp, cur_fdt_tag_offset);
+      res = ufdt_new_node(fdtp, cur_fdt_tag_offset, pool);
       break;
 
     case FDT_BEGIN_NODE:
-      res = ufdt_new_node(fdtp, cur_fdt_tag_offset);
+      res = ufdt_new_node(fdtp, cur_fdt_tag_offset, pool);
 
       do {
         cur_fdt_tag_offset = *next_fdt_tag_offset;
         tag = fdt_next_tag(fdtp, cur_fdt_tag_offset, next_fdt_tag_offset);
         child_node = fdt_to_ufdt_tree(fdtp, cur_fdt_tag_offset,
-                                      next_fdt_tag_offset, tag);
+                                      next_fdt_tag_offset, tag, pool);
         ufdt_node_add_child(res, child_node);
       } while (tag != FDT_END_NODE);
       break;
@@ -279,18 +283,20 @@ struct ufdt_static_phandle_table build_phandle_table(struct ufdt *tree) {
   return res;
 }
 
-struct ufdt *ufdt_from_fdt(void *fdtp, size_t fdt_size) {
+struct ufdt *ufdt_from_fdt(void *fdtp, size_t fdt_size,
+                           struct ufdt_node_pool *pool) {
   (void)(fdt_size); /* unused parameter */
 
   int start_offset = fdt_path_offset(fdtp, "/");
   if (start_offset < 0) {
-    return ufdt_construct(NULL);
+    return ufdt_construct(NULL, pool);
   }
 
-  struct ufdt *res_tree = ufdt_construct(fdtp);
+  struct ufdt *res_tree = ufdt_construct(fdtp, pool);
   int end_offset;
   int start_tag = fdt_next_tag(fdtp, start_offset, &end_offset);
-  res_tree->root = fdt_to_ufdt_tree(fdtp, start_offset, &end_offset, start_tag);
+  res_tree->root =
+      fdt_to_ufdt_tree(fdtp, start_offset, &end_offset, start_tag, pool);
 
   res_tree->phandle_table = build_phandle_table(res_tree);
 
diff --git a/ufdt_node.c b/ufdt_node.c
index 40a05d2..ab9cd06 100644
--- a/ufdt_node.c
+++ b/ufdt_node.c
@@ -16,20 +16,22 @@
 
 #include "libufdt.h"
 
-struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr) {
+#include "ufdt_node_pool.h"
+
+struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr,
+                                      struct ufdt_node_pool *pool) {
+  void *buf = ufdt_node_pool_alloc(pool);
   uint32_t tag = fdt32_to_cpu(*fdt_tag_ptr);
   if (tag == FDT_PROP) {
     const struct fdt_property *prop = (const struct fdt_property *)fdt_tag_ptr;
-    struct ufdt_node_fdt_prop *res =
-        dto_malloc(sizeof(struct ufdt_node_fdt_prop));
+    struct ufdt_node_fdt_prop *res = (struct ufdt_node_fdt_prop *)buf;
     if (res == NULL) return NULL;
     res->parent.fdt_tag_ptr = fdt_tag_ptr;
     res->parent.sibling = NULL;
     res->name = fdt_string(fdtp, fdt32_to_cpu(prop->nameoff));
     return (struct ufdt_node *)res;
   } else {
-    struct ufdt_node_fdt_node *res =
-        dto_malloc(sizeof(struct ufdt_node_fdt_node));
+    struct ufdt_node_fdt_node *res = (struct ufdt_node_fdt_node *)buf;
     if (res == NULL) return NULL;
     res->parent.fdt_tag_ptr = fdt_tag_ptr;
     res->parent.sibling = NULL;
@@ -39,15 +41,16 @@ struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr) {
   }
 }
 
-void ufdt_node_destruct(struct ufdt_node *node) {
+void ufdt_node_destruct(struct ufdt_node *node, struct ufdt_node_pool *pool) {
   if (node == NULL) return;
 
   if (ufdt_node_tag(node) == FDT_BEGIN_NODE) {
-    ufdt_node_destruct(((struct ufdt_node_fdt_node *)node)->child);
+    ufdt_node_destruct(((struct ufdt_node_fdt_node *)node)->child, pool);
   }
 
-  ufdt_node_destruct(node->sibling);
-  dto_free(node);
+  ufdt_node_destruct(node->sibling, pool);
+
+  ufdt_node_pool_free(pool, node);
 }
 
 int ufdt_node_add_child(struct ufdt_node *parent, struct ufdt_node *child) {
@@ -196,7 +199,8 @@ bool ufdt_node_name_eq(const struct ufdt_node *node, const char *name, int len)
  * END of searching-in-ufdt_node methods.
  */
 
-static int merge_children(struct ufdt_node *node_a, struct ufdt_node *node_b) {
+static int merge_children(struct ufdt_node *node_a, struct ufdt_node *node_b,
+                          struct ufdt_node_pool *pool) {
   int err = 0;
   struct ufdt_node *it;
   for (it = ((struct ufdt_node_fdt_node *)node_b)->child; it;) {
@@ -214,7 +218,8 @@ static int merge_children(struct ufdt_node *node_a, struct ufdt_node *node_b) {
     if (target_node == NULL) {
       err = ufdt_node_add_child(node_a, cur_node);
     } else {
-      err = ufdt_node_merge_into(target_node, cur_node);
+      err = ufdt_node_merge_into(target_node, cur_node, pool);
+      ufdt_node_pool_free(pool, cur_node);
     }
     if (err < 0) return -1;
   }
@@ -230,14 +235,15 @@ static int merge_children(struct ufdt_node *node_a, struct ufdt_node *node_b) {
   return 0;
 }
 
-int ufdt_node_merge_into(struct ufdt_node *node_a, struct ufdt_node *node_b) {
+int ufdt_node_merge_into(struct ufdt_node *node_a, struct ufdt_node *node_b,
+                         struct ufdt_node_pool *pool) {
   if (ufdt_node_tag(node_a) == FDT_PROP) {
     node_a->fdt_tag_ptr = node_b->fdt_tag_ptr;
     return 0;
   }
 
   int err = 0;
-  err = merge_children(node_a, node_b);
+  err = merge_children(node_a, node_b, pool);
   if (err < 0) return -1;
 
   return 0;
diff --git a/ufdt_node_pool.c b/ufdt_node_pool.c
new file mode 100644
index 0000000..dabb285
--- /dev/null
+++ b/ufdt_node_pool.c
@@ -0,0 +1,232 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ufdt_node_pool.h"
+
+#include "libufdt_sysdeps.h"
+#include "ufdt_types.h"
+
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
+#define UFDT_NODE_POOL_ENTRIES_PER_BLOCK 1024
+/* UFDT_NODE_POOL_ENTRY_SIZE must be equal to or larger than
+   sizeof(struct ufdt_node_fdt_node) and sizeof(struct ufdt_node_fdt_prop) */
+#define UFDT_NODE_POOL_ENTRY_SIZE \
+  MAX(sizeof(struct ufdt_node_fdt_node), sizeof(struct ufdt_node_fdt_prop))
+/* A block is a header appended UFDT_NODE_POOL_ENTRIES_PER_BLOCK entries */
+#define UFDT_NODE_POOL_BLOCK_SIZE               \
+  (sizeof(struct ufdt_node_pool_block_header) + \
+   UFDT_NODE_POOL_ENTRY_SIZE * UFDT_NODE_POOL_ENTRIES_PER_BLOCK)
+
+/*
+ * The data structure:
+ *
+ *        pool                   block                     block
+ *  +--------------+     +--------------------+     +-----------------+
+ *  | *first_block |---->| block_header:      |     | ...             | ...
+ *  | ...          |     |  *next_block       |---->|                 |---->
+ *  +--------------+     |  *first_free_entry |--\  | ...             |
+ *                       |  ...               |  |
+ *                       +--------------------+  |
+ *                       | entry_header:      |<-/
+ *                       |  *next             |--\
+ *                       +--------------------+  |
+ *                       |  ...               |<-/
+ *                       |                    |--\
+ *                       +--------------------+  |
+ *                       |  ...               |  v
+ */
+
+struct ufdt_node_pool_entry_header {
+  struct ufdt_node_pool_entry_header *next;
+};
+
+struct ufdt_node_pool_block_header {
+  struct ufdt_node_pool_block_header *next_block;
+  struct ufdt_node_pool_entry_header *first_free_entry;
+  int alloc_entry_cnt;
+};
+
+void ufdt_node_pool_construct(struct ufdt_node_pool *pool) {
+  pool->first_block = NULL;
+  pool->last_block_ptr = &pool->first_block;
+}
+
+void ufdt_node_pool_destruct(struct ufdt_node_pool *pool) {
+  int is_leak = 0;
+  struct ufdt_node_pool_block_header *block = pool->first_block;
+  while (block != NULL) {
+    if (block->alloc_entry_cnt != 0) is_leak = 1;
+
+    struct ufdt_node_pool_block_header *next_block = block->next_block;
+    if (!block->first_free_entry) dto_free(block);
+    block = next_block;
+  }
+
+  if (is_leak) {
+    dto_error("Some nodes aren't freed before ufdt_node_pool_destruct().\n");
+  }
+
+  pool->first_block = NULL;
+  pool->last_block_ptr = NULL;
+}
+
+static struct ufdt_node_pool_block_header *_ufdt_node_pool_create_block() {
+  char *block_buf = (char *)dto_malloc(UFDT_NODE_POOL_BLOCK_SIZE);
+  char *block_buf_start = block_buf + sizeof(struct ufdt_node_pool_block_header);
+  char *block_buf_end = block_buf + UFDT_NODE_POOL_BLOCK_SIZE;
+
+  struct ufdt_node_pool_block_header *block =
+      (struct ufdt_node_pool_block_header *)block_buf;
+
+  // Setup all entries to be a one way link list
+  struct ufdt_node_pool_entry_header **next_ptr = &block->first_free_entry;
+  for (char *entry_buf = block_buf_start; entry_buf < block_buf_end;
+       entry_buf += UFDT_NODE_POOL_ENTRY_SIZE) {
+    struct ufdt_node_pool_entry_header *entry =
+        (struct ufdt_node_pool_entry_header *)entry_buf;
+
+    *next_ptr = entry;
+
+    next_ptr = &entry->next;
+  }
+  *next_ptr = NULL;
+
+  block->next_block = NULL;
+  block->alloc_entry_cnt = 0;
+
+  return block;
+}
+
+static void _ufdt_node_pool_destory_block(
+    struct ufdt_node_pool_block_header *block) {
+  dto_free(block);
+}
+
+static void *_ufdt_node_pool_block_alloc(
+    struct ufdt_node_pool_block_header *block) {
+  // take the first free enrtry
+  struct ufdt_node_pool_entry_header *entry = block->first_free_entry;
+
+  block->first_free_entry = entry->next;
+  block->alloc_entry_cnt++;
+
+  return entry;
+}
+
+static void _ufdt_node_pool_block_free(struct ufdt_node_pool_block_header *block,
+                                       void *node) {
+  // put the node to the first free enrtry
+  struct ufdt_node_pool_entry_header *entry = node;
+  entry->next = block->first_free_entry;
+
+  block->first_free_entry = entry;
+  block->alloc_entry_cnt--;
+}
+
+static void _ufdt_node_pool_preppend_block(
+    struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
+  struct ufdt_node_pool_block_header *origin_first_block = pool->first_block;
+  block->next_block = origin_first_block;
+
+  pool->first_block = block;
+  if (origin_first_block == NULL) {
+    pool->last_block_ptr = &block->next_block;
+  }
+}
+
+static void _ufdt_node_pool_append_block(
+    struct ufdt_node_pool *pool, struct ufdt_node_pool_block_header *block) {
+  block->next_block = NULL;
+
+  *pool->last_block_ptr = block;
+  pool->last_block_ptr = &block->next_block;
+}
+
+static void _ufdt_node_pool_remove_block(
+    struct ufdt_node_pool *pool,
+    struct ufdt_node_pool_block_header **block_ptr) {
+  struct ufdt_node_pool_block_header *block = *block_ptr;
+  struct ufdt_node_pool_block_header *next_block = block->next_block;
+
+  *block_ptr = next_block;
+  if (next_block == NULL) {
+    pool->last_block_ptr = block_ptr;
+  }
+
+  block->next_block = NULL;
+}
+
+void *ufdt_node_pool_alloc(struct ufdt_node_pool *pool) {
+  // return dto_malloc(UFDT_NODE_POOL_ENTRY_SIZE);
+  // If there is no free block, create a new one
+  struct ufdt_node_pool_block_header *block = pool->first_block;
+  if (block == NULL || block->first_free_entry == NULL) {
+    block = _ufdt_node_pool_create_block();
+    _ufdt_node_pool_preppend_block(pool, block);
+  }
+
+  void *node = _ufdt_node_pool_block_alloc(block);
+
+  // Move the block to the last if there is no free entry
+  if (block->first_free_entry == NULL && *pool->last_block_ptr != block) {
+    _ufdt_node_pool_remove_block(pool, &pool->first_block);
+    _ufdt_node_pool_append_block(pool, block);
+  }
+
+  return node;
+}
+
+static struct ufdt_node_pool_block_header **_ufdt_node_pool_search_block(
+    struct ufdt_node_pool *pool, void *node) {
+  struct ufdt_node_pool_block_header **block_ptr = &pool->first_block;
+  while (*block_ptr != NULL) {
+    struct ufdt_node_pool_block_header *block = *block_ptr;
+    const char *block_buf_start =
+        (char *)block + sizeof(struct ufdt_node_pool_block_header);
+    const char *block_buf_end = (char *)block + UFDT_NODE_POOL_BLOCK_SIZE;
+
+    if ((char *)node >= block_buf_start && (char *)node < block_buf_end) {
+      break;
+    }
+
+    block_ptr = &block->next_block;
+  }
+  return block_ptr;
+}
+
+void ufdt_node_pool_free(struct ufdt_node_pool *pool, void *node) {
+  struct ufdt_node_pool_block_header **block_ptr =
+      _ufdt_node_pool_search_block(pool, node);
+  if (*block_ptr == NULL) {
+    dto_error("Given node is not in the pool.\n");
+    return;
+  }
+
+  struct ufdt_node_pool_block_header *block = *block_ptr;
+  _ufdt_node_pool_block_free(block, node);
+  _ufdt_node_pool_remove_block(pool, block_ptr);
+
+  /* Delay free block: free the block only if the block is all freed and
+      there has at least one another free block */
+  if (block->alloc_entry_cnt == 0 && pool->first_block != NULL &&
+      pool->first_block->first_free_entry != NULL) {
+    _ufdt_node_pool_destory_block(block);
+    return;
+  }
+
+  _ufdt_node_pool_preppend_block(pool, block);
+}
diff --git a/ufdt_overlay.c b/ufdt_overlay.c
index 7ffb8c1..878df77 100644
--- a/ufdt_overlay.c
+++ b/ufdt_overlay.c
@@ -30,7 +30,7 @@
 #include "ufdt_overlay.h"
 
 #include "libufdt.h"
-
+#include "ufdt_node_pool.h"
 
 /*
  * The original version of fdt_overlay.c is slow in searching for particular
@@ -314,8 +314,9 @@ static int ufdt_overlay_do_fixups(struct ufdt *main_tree,
  * Overlay the overlay_node over target_node.
  */
 static int ufdt_overlay_node(struct ufdt_node *target_node,
-                             struct ufdt_node *overlay_node) {
-  return ufdt_node_merge_into(target_node, overlay_node);
+                             struct ufdt_node *overlay_node,
+                             struct ufdt_node_pool *pool) {
+  return ufdt_node_merge_into(target_node, overlay_node, pool);
 }
 
 /*
@@ -335,7 +336,8 @@ enum overlay_result {
  * Apply one overlay fragment (subtree).
  */
 static enum overlay_result ufdt_apply_fragment(struct ufdt *tree,
-                                               struct ufdt_node *frag_node) {
+                                               struct ufdt_node *frag_node,
+                                               struct ufdt_node_pool *pool) {
   uint32_t target;
   const char *target_path;
   const void *val;
@@ -373,7 +375,7 @@ static enum overlay_result ufdt_apply_fragment(struct ufdt *tree,
     return OVERLAY_RESULT_MISSING_OVERLAY;
   }
 
-  int err = ufdt_overlay_node(target_node, overlay_node);
+  int err = ufdt_overlay_node(target_node, overlay_node, pool);
 
   if (err < 0) {
     dto_error("failed to overlay node %s to target %s\n",
@@ -388,7 +390,8 @@ static enum overlay_result ufdt_apply_fragment(struct ufdt *tree,
  * Applies all fragments to the main_tree.
  */
 static int ufdt_overlay_apply_fragments(struct ufdt *main_tree,
-                                        struct ufdt *overlay_tree) {
+                                        struct ufdt *overlay_tree,
+                                        struct ufdt_node_pool *pool) {
   enum overlay_result err;
   struct ufdt_node **it;
   /*
@@ -396,7 +399,7 @@ static int ufdt_overlay_apply_fragments(struct ufdt *main_tree,
    * In such case, ufdt_apply_fragment would fail with return value = -1.
    */
   for_each_node(it, overlay_tree->root) {
-    err = ufdt_apply_fragment(main_tree, *it);
+    err = ufdt_apply_fragment(main_tree, *it, pool);
     if (err == OVERLAY_RESULT_MERGE_FAIL) {
       return -1;
     }
@@ -559,7 +562,8 @@ static int _ufdt_overlay_fdtps(struct ufdt *main_tree,
 }
 
 static int ufdt_overlay_apply(struct ufdt *main_tree, struct ufdt *overlay_tree,
-                              size_t overlay_length) {
+                              size_t overlay_length,
+                              struct ufdt_node_pool *pool) {
   if (_ufdt_overlay_fdtps(main_tree, overlay_tree) < 0) {
     dto_error("failed to add more fdt into main ufdt tree.\n");
     return -1;
@@ -580,7 +584,7 @@ static int ufdt_overlay_apply(struct ufdt *main_tree, struct ufdt *overlay_tree,
     dto_error("failed to perform fixups in overlay\n");
     return -1;
   }
-  if (ufdt_overlay_apply_fragments(main_tree, overlay_tree) < 0) {
+  if (ufdt_overlay_apply_fragments(main_tree, overlay_tree, pool) < 0) {
     dto_error("failed to apply fragments\n");
     return -1;
   }
@@ -648,9 +652,11 @@ struct fdt_header *ufdt_apply_overlay(struct fdt_header *main_fdt_header,
     return NULL;
   }
 
-  struct ufdt *main_tree = ufdt_from_fdt(main_fdt_header, main_fdt_size);
-  struct ufdt *overlay_tree = ufdt_from_fdt(overlay_fdtp, overlay_size);
-  int err = ufdt_overlay_apply(main_tree, overlay_tree, overlay_size);
+  struct ufdt_node_pool pool;
+  ufdt_node_pool_construct(&pool);
+  struct ufdt *main_tree = ufdt_from_fdt(main_fdt_header, main_fdt_size, &pool);
+  struct ufdt *overlay_tree = ufdt_from_fdt(overlay_fdtp, overlay_size, &pool);
+  int err = ufdt_overlay_apply(main_tree, overlay_tree, overlay_size, &pool);
   if (err < 0) {
     goto fail;
   }
@@ -661,14 +667,16 @@ struct fdt_header *ufdt_apply_overlay(struct fdt_header *main_fdt_header,
     goto fail;
   }
 
-  ufdt_destruct(overlay_tree);
-  ufdt_destruct(main_tree);
+  ufdt_destruct(overlay_tree, &pool);
+  ufdt_destruct(main_tree, &pool);
+  ufdt_node_pool_destruct(&pool);
 
   return out_fdt_header;
 
 fail:
-  ufdt_destruct(overlay_tree);
-  ufdt_destruct(main_tree);
+  ufdt_destruct(overlay_tree, &pool);
+  ufdt_destruct(main_tree, &pool);
+  ufdt_node_pool_destruct(&pool);
   dto_free(out_fdt_header);
 
   return NULL;