[PATCH RFC 1/3] lib: add talloc for overlaying a tree onto allocations

[PATCH RFC 1/3] lib: add talloc for overlaying a tree onto allocations

[Ahmad Fatoum]

Talloc is the hierarchical allocator used by Samba, which keeps all
allocated buffers in a tree, where each child may not live longer than
its parent. When a parent is talloc_free'd, all its children are as
well. This can simplify memory management a great deal.

In barebox, this can also be used to implement devm_.

The implementation here is based on MIT-licensed:
https://github.com/esneider/talloc

But the API was adapted to the Samba3 talloc API, as described here:
https://linux.die.net/man/3/talloc
https://talloc.samba.org/talloc/doc/html/index.html

Support for destructors is planned, but not implemented yet.

Also, the TLSF allocator has two spare bits in each block's size:
One bit could be used to mark talloc buffers to prevent use of talloc_
family functions with non-talloc allocated buffers.

Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 include/talloc.h |  42 +++++
 include/xfuncs.h |   6 +
 lib/Makefile     |   1 +
 lib/talloc.c     | 413 +++++++++++++++++++++++++++++++++++++++++++++++
 lib/xfuncs.c     |  20 +++
 5 files changed, 482 insertions(+)
 create mode 100644 include/talloc.h
 create mode 100644 lib/talloc.c

diff --git a/include/talloc.h b/include/talloc.h
new file mode 100644
index 000000000000..e4ee580fc504
--- /dev/null
+++ b/include/talloc.h
@@ -0,0 +1,42 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/**
+ * Talloc is a replacement for the standard memory allocation routines that
+ * provides structure aware allocations.
+ *
+ * @author Dario Sneidermanis
+ */
+
+#ifndef __TALLOC_H__
+#define __TALLOC_H__
+
+#include <linux/types.h>
+
+struct talloc {
+	struct talloc *child;
+	struct talloc *next;
+	union {
+		struct talloc *prev;
+		struct talloc *parent; /* Valid only when is_first(mem) */
+	};
+};
+
+void mem_set_parent(struct talloc *child, struct talloc *parent);
+
+void *talloc_new(const void *parent);
+size_t talloc_usable_size(void *mem);
+void *talloc_size(const void *parent, size_t size);
+void *talloc_zero_size(const void *parent, size_t size);
+void *talloc_realloc_size(const void *parent, void *mem, size_t size);
+void talloc_free(void *mem);
+
+char *talloc_strdup(const void *parent, const char *str);
+const char *talloc_strdup_const(const void *parent, const char *str);
+void talloc_free_const(const void *ptr);
+
+void *talloc_parent(const void *mem);
+void talloc_steal(const void *parent, void *mem);
+void talloc_steal_children(const void *parent, void *mem);
+
+size_t talloc_total_blocks(const void *mem);
+
+#endif /* __TALLOC_H__ */
diff --git a/include/xfuncs.h b/include/xfuncs.h
index 2cc2048bd583..d567f7416f39 100644
--- a/include/xfuncs.h
+++ b/include/xfuncs.h
@@ -26,6 +26,9 @@ wchar_t *xstrdup_wchar(const wchar_t *src);
 wchar_t *xstrdup_char_to_wchar(const char *src);
 char *xstrdup_wchar_to_char(const wchar_t *src);
 
+void *xtalloc_size(const void *parent, size_t size) __xalloc_size(2);
+void *xtalloc_zero_size(const void *parent, size_t size) __xalloc_size(2);
+
 #else
 
 static inline void *xmalloc(size_t size) { BUG(); }
@@ -43,6 +46,9 @@ static inline __printf(2, 3) char *xrasprintf(char *str, const char *fmt, ...) {
 static inline wchar_t *xstrdup_wchar(const wchar_t *src) { BUG(); }
 static inline wchar_t *xstrdup_char_to_wchar(const char *src) { BUG(); }
 static inline char *xstrdup_wchar_to_char(const wchar_t *src) { BUG(); }
+
+static inline void *xtalloc_size(const void *paent, size_t size) { BUG(); }
+static inline void *xtalloc_zero_size(const void *paent, size_t size) { BUG(); }
 #endif
 
 #endif /* __XFUNCS_H */
diff --git a/lib/Makefile b/lib/Makefile
index e9f152b21dad..9ab4cad0359c 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,6 +12,7 @@ obj-$(CONFIG_VERSION_CMP)	+= strverscmp.o
 obj-y			+= strtox.o
 obj-y			+= kstrtox.o
 obj-y			+= vsprintf.o
+obj-y			+= talloc.o
 obj-$(CONFIG_KASAN)	+= kasan/
 obj-pbl-$(CONFIG_STACKPROTECTOR)	+= stackprot.o
 pbl-$(CONFIG_PBL_CONSOLE) += vsprintf.o
diff --git a/lib/talloc.c b/lib/talloc.c
new file mode 100644
index 000000000000..008f8b5cb0a1
--- /dev/null
+++ b/lib/talloc.c
@@ -0,0 +1,413 @@
+// SPDX-License-Identifier: GPL-2.0-only OR MIT
+/*
+ * Talloc is a replacement for the standard memory allocation routines that
+ * provides structure aware allocations.
+ *
+ * @author Dario Sneidermanis
+ *
+ * Each chunk of talloc'ed memory has a header of the following form:
+ *
+ * +---------+---------+---------+--------···
+ * |  first  |  next   |  prev   | memory
+ * |  child  | sibling | sibling | chunk
+ * +---------+---------+---------+--------···
+ *
+ * Thus, a talloc hierarchy tree would look like this:
+ *
+ *   NULL <-- chunk --> NULL
+ *              ^
+ *              |
+ *              +-> chunk <--> chunk <--> chunk --> NULL
+ *                    |          |          ^
+ *                    v          v          |
+ *                   NULL       NULL        +-> chunk <--> chunk --> NULL
+ *                                                |          |
+ *                                                v          v
+ *                                               NULL       NULL
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <linux/bug.h>
+#include <linux/export.h>
+#include <linux/container_of.h>
+#include <asm/sections.h>
+#include "talloc.h"
+
+// TODO difference between set_parent and steal?
+// TODO use a bit from TLSF for extra safety to differentiate talloc
+// TODO allow leaf nodes (that have no children to be destructors!!)
+#define  is_root(hdr) (!(hdr)->prev)
+#define is_first(hdr) ((hdr)->prev->next != (hdr))
+
+static inline void *hdr2mem(struct talloc *hdr)
+{
+	return hdr ? &hdr[1] : NULL;
+}
+
+static inline struct talloc *mem2hdr(const void *mem)
+{
+	return mem ? (void *)mem - sizeof(struct talloc) : NULL;
+}
+
+/**
+ * talloc_ctx_init() - Initialize a raw chunk of memory.
+ *
+ * @hdr: pointer to freshly allocated memory chunk.
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ *
+ * Return: pointer to the allocated memory chunk, or NULL if there was an error.
+ */
+static void *talloc_ctx_init(struct talloc *hdr, const void *parent)
+{
+	void *mem;
+
+	if (!hdr)
+		return NULL;
+
+	memset(hdr, 0, sizeof(*hdr));
+
+	mem = hdr2mem(hdr);
+	talloc_steal(parent, mem);
+	return mem;
+}
+
+/**
+ * talloc_usable_size() - Report the size of the talloation
+ *
+ * @mem: pointer to previously talloc'ed memory chunk.
+ *
+ * Return: size of tallocation
+ */
+size_t talloc_usable_size(void *mem)
+{
+	return malloc_usable_size(mem) - sizeof(struct talloc);
+}
+EXPORT_SYMBOL(talloc_usable_size);
+
+/**
+ * talloc_new() - Allocate a talloc object without user data
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ *
+ * Return: pointer to the allocated object, or NULL if there was an error.
+ */
+void *talloc_new(const void *parent)
+{
+	return talloc_ctx_init(malloc(sizeof(struct talloc)), parent);
+}
+EXPORT_SYMBOL(talloc_new);
+
+/**
+ * talloc_size() - Allocate a (contiguous) memory chunk.
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ * @size: amount of memory requested (in bytes).
+ *
+ * Return: pointer to the allocated memory chunk, or NULL if there was an error.
+ */
+void *talloc_size(const void *parent, size_t size)
+{
+	if (!size)
+		return ZERO_SIZE_PTR;
+
+	return talloc_ctx_init(malloc(size + sizeof(struct talloc)), parent);
+}
+EXPORT_SYMBOL(talloc_size);
+
+/**
+ * talloc_strdup() - Duplicate a string
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ * @str: string to duplicate
+ *
+ * Return: pointer to the duplicated string, or NULL if there was an error.
+ */
+char *talloc_strdup(const void *parent, const char *str)
+{
+	size_t len = strlen(str) + 1;
+	void *usr;
+
+	usr = talloc_size(parent, len);
+	if (!usr)
+		return NULL;
+
+	return memcpy(usr, str, len);
+}
+EXPORT_SYMBOL(talloc_strdup);
+
+/**
+ * talloc_strdup_const() - Duplicate a string if not read-only
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ * @size: amount of memory requested (in bytes).
+ *
+ * Return: pointer to the allocated memory chunk, or NULL if there was an error.
+ */
+const char *talloc_strdup_const(const void *parent, const char *str)
+{
+	if (is_barebox_rodata((ulong)str))
+		return str;
+
+	return talloc_strdup(parent, str);
+}
+EXPORT_SYMBOL(talloc_strdup_const);
+
+/**
+ * tzalloc() - Allocate a zeroed (contiguous) memory chunk.
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ * @size: amount of memory requested (in bytes).
+ *
+ * Return: pointer to the allocated memory chunk, or NULL if there was an error.
+ */
+void *talloc_zero_size(const void *parent, size_t size)
+{
+	if (!size)
+		return ZERO_SIZE_PTR;
+
+	return talloc_ctx_init(calloc(1, size + sizeof(struct talloc)), parent);
+}
+EXPORT_SYMBOL(talloc_zero_size);
+
+/**
+ * trealloc() - Modify the size of a talloc'ed memory chunk.
+ *
+ * @parent: parent to set if mem is NULL.
+ * @mem: pointer to previously talloc'ed memory chunk.
+ * @size: amount of memory requested (in bytes).
+ *
+ * Return: pointer to the allocated memory chunk, or NULL if there was an error.
+ */
+void *talloc_realloc_size(const void *parent, void *mem, size_t size)
+{
+	struct talloc *oldhdr, *hdr;
+	void *newmem;
+
+	if (!size) {
+		talloc_free(mem);
+		return ZERO_SIZE_PTR;
+	}
+	if (ZERO_OR_NULL_PTR(mem))
+		mem = NULL;
+
+	oldhdr = mem2hdr(mem);
+
+	newmem = realloc(oldhdr, size + sizeof(*oldhdr));
+	if (!oldhdr || !newmem)
+		return talloc_ctx_init(newmem, parent);
+
+	if (oldhdr == newmem)
+		return mem;
+
+	/* Buffer start address changed, update all references. */
+	hdr = newmem;
+	mem = hdr2mem(hdr);
+
+	if (hdr->child)
+		hdr->child->parent = hdr;
+
+	if (!is_root(hdr)) {
+		if (hdr->next)
+			hdr->next->prev = hdr;
+
+		if (hdr->prev->next == oldhdr)
+			hdr->prev->next = hdr;
+		if (hdr->parent->child == oldhdr)
+			hdr->parent->child = hdr;
+	}
+
+	return mem;
+}
+EXPORT_SYMBOL(talloc_realloc_size);
+
+/**
+ * __tfree() - Deallocate all the descendants of given parent recursively.
+ *
+ * @hdr: pointer to previously talloc'ed memory chunk.
+ */
+static void __tfree(struct talloc *hdr)
+{
+	if (ZERO_OR_NULL_PTR(hdr))
+		return;
+
+	/* Fail if the tree hierarchy has cycles. */
+
+	ASSERT(hdr->prev);
+	hdr->prev = NULL;
+
+	__tfree(hdr->child);
+	__tfree(hdr->next);
+	free(hdr);
+}
+
+/**
+ * talloc_free() - Deallocate a talloc'ed memory chunk and all the chunks depending on it.
+ *
+ * @mem: pointer to previously talloc'ed memory chunk.
+ */
+void talloc_free(void *mem)
+{
+	struct talloc *hdr = mem2hdr(mem);
+
+	if (ZERO_OR_NULL_PTR(hdr))
+		return;
+
+	talloc_steal(NULL, mem);
+
+	__tfree(hdr->child);
+
+	free(hdr);
+}
+EXPORT_SYMBOL(talloc_free);
+
+/**
+ * talloc_free_const() - call talloc_free, unless read/only memory
+ *
+ * @mem: pointer to previously talloc'ed memory chunk.
+ */
+void talloc_free_const(const void *mem)
+{
+	if (is_barebox_rodata((ulong)mem))
+		return;
+
+	talloc_free((void *)mem);
+}
+EXPORT_SYMBOL(talloc_free_const);
+
+/**
+ * talloc_parent() - Get the parent of a talloc'ed memory chunk
+ *
+ * @mem: pointer to previously talloc'ed memory chunk.
+ *
+ * Return: pointer to the parent memory chunk it depends on (could be NULL).
+ */
+void *talloc_parent(const void *mem)
+{
+	struct talloc *hdr = mem2hdr(mem);
+
+	if (ZERO_OR_NULL_PTR(hdr) || is_root(hdr))
+		return NULL;
+
+	while (!is_first(hdr))
+		hdr = hdr->prev;
+
+	return hdr2mem(hdr->parent);
+}
+EXPORT_SYMBOL(talloc_parent);
+
+void mem_set_parent(struct talloc *hdr, struct talloc *parent_hdr)
+{
+	if (ZERO_OR_NULL_PTR(hdr))
+		return;
+
+	if (!is_root(hdr)) {
+		/* Remove node from old tree. */
+		if (hdr->next)
+			hdr->next->prev = hdr->prev;
+
+		if (!is_first(hdr))
+			hdr->prev->next = hdr->next;
+		else
+			hdr->parent->child = hdr->next;
+	}
+
+	hdr->next = hdr->prev = NULL;
+
+	if (parent_hdr) {
+		/* Insert node into new tree. */
+		if (parent_hdr->child) {
+			hdr->next = parent_hdr->child;
+			parent_hdr->child->prev = hdr;
+		}
+
+		hdr->parent = parent_hdr;
+		parent_hdr->child = hdr;
+	}
+}
+EXPORT_SYMBOL(mem_set_parent);
+
+/**
+ * talloc_steal() - Reparent talloc'ed memory chunk
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk depends, or NULL.
+ * @mem: pointer to previously talloc'ed memory chunk.
+ *
+ * Change the parent of a talloc'ed memory chunk. This will affect the
+ * dependencies of the entire subtree rooted at the given chunk.
+ */
+void talloc_steal(const void *parent, void *mem)
+{
+	struct talloc *hdr = mem2hdr(mem);
+	struct talloc *parent_hdr = mem2hdr(parent);
+
+	mem_set_parent(hdr, parent_hdr);
+}
+EXPORT_SYMBOL(talloc_steal);
+
+/**
+ * talloc_steal_children() - Remove a talloc'ed memory chunk from the dependency tree
+ *
+ * @parent: pointer to previously talloc'ed memory chunk from which this
+ *          chunk's children will depend, or NULL.
+ * @mem: pointer to previously talloc'ed memory chunk.
+ *
+ * Removing a talloc'ed memory chunk from the dependency tree takes care of its
+ * children (they will depend on the specified parent).
+ */
+void talloc_steal_children(const void *parent, void *mem)
+{
+	struct talloc *hdr = mem2hdr(mem);
+	struct talloc *parent_hdr = mem2hdr(parent);
+
+	if (ZERO_OR_NULL_PTR(hdr))
+		return;
+
+	talloc_steal(NULL, mem);
+
+	if (!hdr->child)
+		return;
+
+	if (parent_hdr) {
+		/* Insert mem children in front of the list of parent children. */
+		if (parent_hdr->child) {
+			struct talloc *last = hdr->child;
+
+			while (last->next)
+				last = last->next;
+
+			parent_hdr->child->prev = last;
+			last->next = parent_hdr->child;
+		}
+
+		parent_hdr->child = hdr->child;
+	}
+
+	hdr->child->parent = parent_hdr;
+	hdr->child = NULL;
+}
+EXPORT_SYMBOL(talloc_steal_children);
+
+size_t talloc_total_blocks(const void *mem)
+{
+	struct talloc *hdr = mem2hdr(mem);
+	size_t nblocks = 0;
+
+	if (ZERO_OR_NULL_PTR(hdr))
+		return 0;
+
+	nblocks++;
+
+	for (hdr = hdr->child; hdr; hdr = hdr->next)
+		nblocks++;
+
+	return nblocks;
+}
+EXPORT_SYMBOL(talloc_total_blocks);
diff --git a/lib/xfuncs.c b/lib/xfuncs.c
index 4c694513050e..c34605072411 100644
--- a/lib/xfuncs.c
+++ b/lib/xfuncs.c
@@ -19,6 +19,7 @@
 
 #include <common.h>
 #include <malloc.h>
+#include <talloc.h>
 #include <module.h>
 #include <wchar.h>
 
@@ -44,6 +45,17 @@ void *xmalloc(size_t size)
 }
 EXPORT_SYMBOL(xmalloc);
 
+void *xtalloc_size(const void *parent, size_t size)
+{
+	void *p = NULL;
+
+	if (!(p = talloc_size(parent, size)))
+		enomem_panic(size);
+
+	return p;
+}
+EXPORT_SYMBOL(xtalloc_size);
+
 void *xrealloc(void *ptr, size_t size)
 {
 	void *p = NULL;
@@ -63,6 +75,14 @@ void *xzalloc(size_t size)
 }
 EXPORT_SYMBOL(xzalloc);
 
+void *xtalloc_zero_size(const void *parent, size_t size)
+{
+	void *ptr = xtalloc_size(parent, size);
+	memset(ptr, 0, size);
+	return ptr;
+}
+EXPORT_SYMBOL(xtalloc_zero_size);
+
 char *xstrdup(const char *s)
 {
 	char *p;
-- 
2.47.3

[PATCH RFC 2/3] test: self: add talloc selftest

[Ahmad Fatoum]

This self test exercises the hierarchical properties of talloc.

Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 test/self/Kconfig  |   6 ++
 test/self/Makefile |   1 +
 test/self/talloc.c | 153 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 160 insertions(+)
 create mode 100644 test/self/talloc.c

diff --git a/test/self/Kconfig b/test/self/Kconfig
index fa2911fa649a..23c82b4f2c93 100644
--- a/test/self/Kconfig
+++ b/test/self/Kconfig
@@ -47,6 +47,7 @@ config SELFTEST_ENABLE_ALL
 	select SELFTEST_IDR
 	select SELFTEST_TLV
 	select SELFTEST_DM
+	select SELFTEST_TALLOC
 	help
 	  Selects all self-tests compatible with current configuration
 
@@ -55,6 +56,11 @@ config SELFTEST_MALLOC
 	help
 	  Tests barebox memory allocator
 
+config SELFTEST_TALLOC
+	bool "talloc() selftest"
+	help
+	  Tests barebox talloc allocator
+
 config SELFTEST_PRINTF
 	bool "printf selftest"
 	help
diff --git a/test/self/Makefile b/test/self/Makefile
index 3d74bf9e98ad..3afaada5f54a 100644
--- a/test/self/Makefile
+++ b/test/self/Makefile
@@ -2,6 +2,7 @@
 
 obj-$(CONFIG_SELFTEST) += core.o
 obj-$(CONFIG_SELFTEST_MALLOC) += malloc.o
+obj-$(CONFIG_SELFTEST_TALLOC) += talloc.o
 obj-$(CONFIG_SELFTEST_PRINTF) += printf.o
 CFLAGS_printf.o += -Wno-format-security -Wno-format
 obj-$(CONFIG_SELFTEST_PROGRESS_NOTIFIER) += progress-notifier.o
diff --git a/test/self/talloc.c b/test/self/talloc.c
new file mode 100644
index 000000000000..1322269af498
--- /dev/null
+++ b/test/self/talloc.c
@@ -0,0 +1,153 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#define pr_fmt(fmt) "talloc: " fmt
+
+#include <common.h>
+#include <stdlib.h>
+#include <bselftest.h>
+#include <talloc.h>
+#include <linux/sizes.h>
+#include <linux/bitops.h>
+
+BSELFTEST_GLOBALS();
+
+static bool __selftest_check(bool cond, const char *func, int line)
+{
+	total_tests ++;
+	if (cond)
+		return true;
+
+	pr_err("assertion failure at %s:%d\n", func, line);
+
+	failed_tests++;
+	return false;
+}
+#define selftest_check(cond) __selftest_check((cond), __func__, __LINE__)
+
+#define STRESS_ALLOCS  1024
+#define STRESS_ITERS   5000
+
+static void talloc_basic_tests(void)
+{
+	void *root, *a, *b, *c;
+	void *tmp;
+
+	root = talloc_size(NULL, 0);
+	selftest_check(root == ZERO_SIZE_PTR);
+
+	root = talloc_new(NULL);
+	if (!selftest_check(!ZERO_OR_NULL_PTR(root)))
+		return;
+
+	a = talloc_size(root, 128);
+	selftest_check(a);
+
+	selftest_check(talloc_parent(a) == root);
+
+	b = talloc_zero_size(root, 256);
+	selftest_check(b && memchr_inv(b, 0x00, 256) == NULL);
+
+	c = talloc_strdup(root, "barebox talloc test");
+	selftest_check(c);
+
+	tmp = talloc_realloc_size(talloc_parent(a), a, 512);
+	if (selftest_check(tmp))
+		a = tmp;
+
+	selftest_check(talloc_parent(a) == root);
+
+	selftest_check(talloc_total_blocks(root) == 4);
+
+	/* Free child and verify parent is intact */
+	talloc_free(a);
+	selftest_check(talloc_total_blocks(root) == 3);
+
+	talloc_free(b);
+	selftest_check(talloc_total_blocks(root) == 2);
+
+	talloc_free(c);
+	selftest_check(talloc_total_blocks(root) == 1);
+
+	talloc_free(root);
+}
+
+static void talloc_hierarchy_tests(void)
+{
+	void *root = talloc_new(NULL);
+	void *lvl1, *lvl2, *lvl3;
+
+	lvl1 = talloc_new(root);
+	lvl2 = talloc_new(lvl1);
+	lvl3 = talloc_size(lvl2, 64);
+
+	selftest_check(lvl1 && lvl2 && lvl3);
+
+	selftest_check(talloc_parent(lvl3) == lvl2);
+
+	talloc_free(lvl1); /* should free all children */
+	selftest_check(talloc_total_blocks(root) == 1);
+
+	talloc_free(root);
+}
+
+static void talloc_stress_tests(void)
+{
+	void *root = talloc_new(NULL);
+	void *ptrs[STRESS_ALLOCS];
+
+	memset(ptrs, 0, sizeof(ptrs));
+
+	for (int iter = 0; iter < STRESS_ITERS; iter++) {
+		int idx = prandom_u32_max(STRESS_ALLOCS);
+		if (ptrs[idx]) {
+			talloc_free(ptrs[idx]);
+			ptrs[idx] = NULL;
+		} else {
+			size_t sz = prandom_u32_max(4096) + 1;
+			ptrs[idx] = talloc_size(root, sz);
+			if (selftest_check(ptrs[idx]) &&
+			    prandom_u32_max(8) == 0) {
+				/* Occasionally realloc to a different size */
+				size_t new_sz = prandom_u32_max(8192) + 1;
+				void *tmp = talloc_realloc_size(NULL,
+								ptrs[idx], new_sz);
+				if (selftest_check(tmp))
+					ptrs[idx] = tmp;
+			}
+		}
+	}
+
+	for (int i = 0; i < STRESS_ALLOCS; i++) {
+		if (ptrs[i])
+			talloc_free(ptrs[i]);
+	}
+	talloc_free(root);
+}
+
+static void talloc_corner_cases(void)
+{
+	void *root = talloc_new(NULL);
+	void *large;
+
+	talloc_free(NULL);
+
+	void *realloc_null = talloc_realloc_size(NULL, NULL, 128);
+	selftest_check(realloc_null);
+	talloc_free(realloc_null);
+
+	/* Large alloc test (may fail gracefully if memory-constrained) */
+	large = talloc_size(root, 1024 * 1024 * 10);
+	if (selftest_check(large))
+		talloc_free(large);
+
+	talloc_free(root);
+}
+
+static void test_talloc(void)
+{
+	talloc_basic_tests();
+	talloc_hierarchy_tests();
+	talloc_stress_tests();
+	talloc_corner_cases();
+}
+bselftest(core, test_talloc);
-- 
2.47.3

[PATCH RFC 3/3] hush: fix memory leaks

[Ahmad Fatoum]

The memory leaks in hush have been bothered me for years and every time
I look into it, I give up after a while, because the code is convoluted.

Talloc shines here as we can just allocate a "zero-size" talloc object
as parent for a context and associate all allocations from that context
with it.

Then when that context is free'd all children will be freed as well.

Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 common/hush.c | 41 +++++++++++++++++++++++++----------------
 1 file changed, 25 insertions(+), 16 deletions(-)

diff --git a/common/hush.c b/common/hush.c
index ec3c0cd91320..2e0cc4229d35 100644
--- a/common/hush.c
+++ b/common/hush.c
@@ -97,6 +97,7 @@
 
 #define pr_fmt(fmt) "hush: " fmt
 
+#include <talloc.h>
 #include <malloc.h>         /* malloc, free, realloc*/
 #include <xfuncs.h>
 #include <linux/ctype.h>    /* isalpha, isdigit */
@@ -180,6 +181,7 @@ struct option {
 
 /* This holds pointers to the various results of parsing */
 struct p_context {
+	const void *scope;
 	struct child_prog *child;
 	struct pipe *list_head;
 	struct pipe *pipe;
@@ -308,7 +310,7 @@ static int run_pipe_real(struct p_context *ctx, struct pipe *pi);
 /*   variable assignment: */
 static int is_assignment(const char *s);
 /*   data structure manipulation: */
-static void initialize_context(struct p_context *ctx);
+static void initialize_context(struct p_context *ctx, bool newscope);
 static void release_context(struct p_context *ctx);
 static int done_word(o_string *dest, struct p_context *ctx);
 static int done_command(struct p_context *ctx);
@@ -435,7 +437,7 @@ static char *getprompt(void)
 	if (prompt_command) {
 		unsigned int lr = last_return_code;
 
-		initialize_context(&ctx);
+		initialize_context(&ctx, false);
 		parse_string_outer(&ctx, prompt_command, FLAG_PARSE_SEMICOLON);
 		release_context(&ctx);
 
@@ -837,7 +839,7 @@ static int run_pipe_real(struct p_context *ctx, struct pipe *pi)
 		char * str = NULL;
 		struct p_context ctx1;
 
-		initialize_context(&ctx1);
+		initialize_context(&ctx1, true);
 
 		str = make_string((child->argv + i));
 		rcode = parse_string_outer(&ctx1, str, FLAG_EXIT_FROM_LOOP | FLAG_REPARSING);
@@ -1062,7 +1064,8 @@ static int free_pipe(struct pipe *pi, int indent)
 		}
 	}
 
-	free(pi->progs);   /* children are an array, they get freed all at once */
+	/* children are an array, they get freed all at once */
+	talloc_free(pi->progs);
 	pi->progs = NULL;
 
 	return ret_code;
@@ -1079,7 +1082,7 @@ static int free_pipe_list(struct pipe *head, int indent)
 		final_printf("%s pipe followup code %d\n", indenter(indent), pi->followup);
 		next = pi->next;
 		pi->next = NULL;
-		free(pi);
+		talloc_free(pi);
 	}
 	return rcode;
 }
@@ -1182,16 +1185,18 @@ static int is_assignment(const char *s)
 }
 
 
-static struct pipe *new_pipe(void)
+static struct pipe *new_pipe(struct p_context *ctx)
 {
-	return xzalloc(sizeof(struct pipe));
+	return xtalloc_zero_size(ctx->scope, sizeof(struct pipe));
 }
 
-static void initialize_context(struct p_context *ctx)
+static void initialize_context(struct p_context *ctx, bool newscope)
 {
+	if (newscope)
+		ctx->scope = talloc_new(NULL);
 	ctx->pipe = NULL;
 	ctx->child = NULL;
-	ctx->list_head = new_pipe();
+	ctx->list_head = new_pipe(ctx);
 	ctx->pipe = ctx->list_head;
 	ctx->w = RES_NONE;
 	ctx->stack = NULL;
@@ -1211,6 +1216,7 @@ static void release_context(struct p_context *ctx)
 		free(opt);
 	}
 #endif
+	talloc_free((void *)ctx->scope);
 }
 
 /* normal return is 0
@@ -1269,7 +1275,7 @@ static int reserved_word(o_string *dest, struct p_context *ctx)
 				return 1;
 			}
 			*new = *ctx;   /* physical copy */
-			initialize_context(ctx);
+			initialize_context(ctx, false);
 			ctx->stack = new;
 		} else if (ctx->w == RES_NONE || !(ctx->old_flag & (1 << r->code))) {
 			syntax_unexpected_token(r->literal);
@@ -1366,7 +1372,10 @@ static int done_command(struct p_context *ctx)
 	} else {
 		hush_debug("%s: initializing\n", __func__);
 	}
-	pi->progs = xrealloc(pi->progs, sizeof(*pi->progs) * (pi->num_progs + 1));
+	pi->progs = talloc_realloc_size(ctx->scope, pi->progs,
+					sizeof(*pi->progs) * (pi->num_progs + 1));
+	if (!pi->progs)
+		panic("enomem");
 
 	prog = pi->progs + pi->num_progs;
 	prog->glob_result.gl_pathv = NULL;
@@ -1392,7 +1401,7 @@ static int done_pipe(struct p_context *ctx, pipe_style type)
 	ctx->pipe->followup = type;
 	ctx->pipe->r_mode = ctx->w;
 
-	new_p = new_pipe();
+	new_p = new_pipe(ctx);
 
 	ctx->pipe->next = new_p;
 	ctx->pipe = new_p;
@@ -1705,7 +1714,7 @@ char *shell_expand(char *str)
 
 	o.quote = 1;
 
-	initialize_context(&ctx);
+	initialize_context(&ctx, false);
 
 	parse_string(&o, &ctx, str);
 
@@ -1732,7 +1741,7 @@ static int parse_stream_outer(struct p_context *ctx, struct in_str *inp, int fla
 
 	do {
 		ctx->type = flag;
-		initialize_context(ctx);
+		initialize_context(ctx, false);
 		update_ifs_map();
 
 		if (!(flag & FLAG_PARSE_SEMICOLON) || (flag & FLAG_REPARSING))
@@ -1921,7 +1930,7 @@ int run_command(const char *cmd)
 	if (!IS_ALLOWED(SCONFIG_SHELL))
 		return -EPERM;
 
-	initialize_context(&ctx);
+	initialize_context(&ctx, true);
 
 	ret = parse_string_outer(&ctx, cmd, FLAG_PARSE_SEMICOLON);
 	release_context(&ctx);
@@ -1949,7 +1958,7 @@ static int source_script(const char *path, int argc, char *argv[])
 	char *script;
 	int ret;
 
-	initialize_context(&ctx);
+	initialize_context(&ctx, true);
 
 	ctx.global_argc = argc;
 	ctx.global_argv = argv;
-- 
2.47.3

Re: [PATCH RFC 1/3] lib: add talloc for overlaying a tree onto allocations

[Sascha Hauer]

On Mon, Oct 27, 2025 at 08:54:32AM +0100, Ahmad Fatoum wrote:
> +#ifndef __TALLOC_H__
> +#define __TALLOC_H__
> +
> +#include <linux/types.h>
> +
> +struct talloc {
> +	struct talloc *child;
> +	struct talloc *next;
> +	union {
> +		struct talloc *prev;
> +		struct talloc *parent; /* Valid only when is_first(mem) */
> +	};
> +};

Currently tlsf allocations are 8 byte aligned. On 32bit architectures
struct talloc will be 12 bytes, so talloc allocations will only have 4
byte alignment.

> +static void *talloc_ctx_init(struct talloc *hdr, const void *parent)
> +{
> +	void *mem;
> +
> +	if (!hdr)
> +		return NULL;
> +
> +	memset(hdr, 0, sizeof(*hdr));
> +
> +	mem = hdr2mem(hdr);
> +	talloc_steal(parent, mem);
> +	return mem;
> +}
> +
> +/**
> + * talloc_usable_size() - Report the size of the talloation

s/talloation/tallocation/

> + *
> + * @mem: pointer to previously talloc'ed memory chunk.
> + *
> + * Return: size of tallocation
> + */
> +size_t talloc_usable_size(void *mem)
> +{
> +	return malloc_usable_size(mem) - sizeof(struct talloc);
> +}
> +EXPORT_SYMBOL(talloc_usable_size);

This function is unused. Do we need it?

> +/**
> + * talloc_free() - Deallocate a talloc'ed memory chunk and all the chunks depending on it.
> + *
> + * @mem: pointer to previously talloc'ed memory chunk.
> + */
> +void talloc_free(void *mem)
> +{
> +	struct talloc *hdr = mem2hdr(mem);
> +
> +	if (ZERO_OR_NULL_PTR(hdr))
> +		return;

For correctness I believe you have to check mem here, not hdr.

(Although the above works as long as sizeof(struct talloc) <= ZERO_SIZE_PTR)

Sascha

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

Re: [PATCH RFC 1/3] lib: add talloc for overlaying a tree onto allocations

[Ahmad Fatoum]

Hi,

On 10/28/25 10:42 AM, Sascha Hauer wrote:
> On Mon, Oct 27, 2025 at 08:54:32AM +0100, Ahmad Fatoum wrote:
>> +#ifndef __TALLOC_H__
>> +#define __TALLOC_H__
>> +
>> +#include <linux/types.h>
>> +
>> +struct talloc {
>> +	struct talloc *child;
>> +	struct talloc *next;
>> +	union {
>> +		struct talloc *prev;
>> +		struct talloc *parent; /* Valid only when is_first(mem) */
>> +	};
>> +};
> 
> Currently tlsf allocations are 8 byte aligned. On 32bit architectures
> struct talloc will be 12 bytes, so talloc allocations will only have 4
> byte alignment.

Good catch. On 32-bit, there is 4 bytes of unused padding inside TLSF
and feels bad sacrificing 4 more bytes here. :/

Will have to give it a thought.

>> +static void *talloc_ctx_init(struct talloc *hdr, const void *parent)
>> +{
>> +	void *mem;
>> +
>> +	if (!hdr)
>> +		return NULL;
>> +
>> +	memset(hdr, 0, sizeof(*hdr));
>> +
>> +	mem = hdr2mem(hdr);
>> +	talloc_steal(parent, mem);
>> +	return mem;
>> +}
>> +
>> +/**
>> + * talloc_usable_size() - Report the size of the talloation
> 
> s/talloation/tallocation/

Will fix for v2.

> 
>> + *
>> + * @mem: pointer to previously talloc'ed memory chunk.
>> + *
>> + * Return: size of tallocation
>> + */
>> +size_t talloc_usable_size(void *mem)
>> +{
>> +	return malloc_usable_size(mem) - sizeof(struct talloc);
>> +}
>> +EXPORT_SYMBOL(talloc_usable_size);
> 
> This function is unused. Do we need it?

To make it easier to retrofit normal malloc code for talloc, it's useful
to have already, I think.

>> +/**
>> + * talloc_free() - Deallocate a talloc'ed memory chunk and all the chunks depending on it.
>> + *
>> + * @mem: pointer to previously talloc'ed memory chunk.
>> + */
>> +void talloc_free(void *mem)
>> +{
>> +	struct talloc *hdr = mem2hdr(mem);
>> +
>> +	if (ZERO_OR_NULL_PTR(hdr))
>> +		return;
> 
> For correctness I believe you have to check mem here, not hdr.
> 
> (Although the above works as long as sizeof(struct talloc) <= ZERO_SIZE_PTR)

Thanks. This used to be container_of_safe of a flexible data member,
which I dropped in the meantime.

Will fix for v2.

Cheers,
Ahmad

> 
> Sascha
> 

-- 
Pengutronix e.K.                  |                             |
Steuerwalder Str. 21              | http://www.pengutronix.de/  |
31137 Hildesheim, Germany         | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686  | Fax:   +49-5121-206917-5555 |