devicetree: Add local makeshift allocator to avoid straining malloc()
Trick question: What happens when you call a simple malloc()
implementation with linear time complexity several thousand times in a
small loop?
This patch adds an extremely simple constant-time "allocator" for device
tree properties and nodes to cut down fdt_unflatten() time from several
dozen milliseconds to essentially nothing. There's no need for free() or
any of that fancy stuff since we generally only unflatten one kernel
device tree per boot.
The buffer sizes (1000 nodes and 5000 properties) were chosen as roughly
double of what a current Nyan kernel needs, which should hopefully be
reasonably future-proof for a while. The only cost is zeroing another
100-something KB of BSS, which is negligible.
BRANCH=nyan
BUG=None
TEST=Measured a firmware boot time reduction of 37ms on Nyan_Big.
Change-Id: Idc4ac9c81e3a42b400ae614b9b72a57af5155d91
Signed-off-by: Julius Werner <jwerner@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/203034
Reviewed-by: Vadim Bendebury <vbendeb@chromium.org>
Reviewed-by: Stefan Reinauer <reinauer@chromium.org>
Reviewed-by: Tom Warren <twarren@nvidia.com>
Reviewed-by: David Hendricks <dhendrix@chromium.org>
diff --git a/src/base/device_tree.c b/src/base/device_tree.c
index 661248f..14f47ed 100644
--- a/src/base/device_tree.c
+++ b/src/base/device_tree.c
@@ -162,6 +162,29 @@
* Functions to turn a flattened tree into an unflattened one.
*/
+static DeviceTreeNode node_cache[1000];
+static int node_counter = 0;
+static DeviceTreeProperty prop_cache[5000];
+static int prop_counter = 0;
+
+/*
+ * Libpayload's malloc() has linear allocation complexity and goes completely
+ * mental after a few thousand small requests. This little hack will absorb
+ * the worst of it to avoid increasing boot time for no reason.
+ */
+static DeviceTreeNode *alloc_node(void)
+{
+ if (node_counter >= ARRAY_SIZE(node_cache))
+ return xzalloc(sizeof(DeviceTreeNode));
+ return &node_cache[node_counter++];
+}
+static DeviceTreeProperty *alloc_prop(void)
+{
+ if (prop_counter >= ARRAY_SIZE(prop_cache))
+ return xzalloc(sizeof(DeviceTreeProperty));
+ return &prop_cache[prop_counter++];
+}
+
static int fdt_unflatten_node(void *blob, uint32_t start_offset,
DeviceTreeNode **new_node)
{
@@ -175,14 +198,14 @@
return 0;
offset += size;
- DeviceTreeNode *node = xzalloc(sizeof(*node));
+ DeviceTreeNode *node = alloc_node();
*new_node = node;
node->name = name;
FdtProperty fprop;
last = &node->properties;
while ((size = fdt_next_property(blob, offset, &fprop))) {
- DeviceTreeProperty *prop = xzalloc(sizeof(*prop));
+ DeviceTreeProperty *prop = alloc_prop();
prop->prop = fprop;
list_insert_after(&prop->list_node, last);
