In various places it is useful to have an array of structures, but allow
it to grow. In some cases we work around it by setting maximum number of
entries, using a Kconfig option. In other places we use a linked list,
which does not provide for random access and can complicate the code.
Introduce a new data structure, which is a variable-sized list of structs
each of the same, pre-set size. It provides O(1) access and is reasonably
efficient at expanding linearly, since it doubles in size when it runs out
of space.
Signed-off-by: Simon Glass <s...@chromium.org>
---
Changes in v4:
- Avoid using realloc() unless specifically enabled by Kconfig
Changes in v3:
- Add prototype for alist_expand_by()
Changes in v2:
- Fix 'typeee' typo
- Make alist_get_ptr() take a const alist *
- Make alist_add() take a struct rather than a pointer
- Declare alist_expand_by() as static
include/alist.h | 214 ++++++++++++++++++++++++++++++++++++++++++++++
lib/Kconfig | 10 +++
lib/Makefile | 1 +
lib/alist.c | 157 ++++++++++++++++++++++++++++++++++
test/lib/Makefile | 1 +
test/lib/alist.c | 197 ++++++++++++++++++++++++++++++++++++++++++
6 files changed, 580 insertions(+)
create mode 100644 include/alist.h
create mode 100644 lib/alist.c
create mode 100644 test/lib/alist.c
diff --git a/include/alist.h b/include/alist.h
new file mode 100644
index 00000000000..6cc3161dcda
--- /dev/null
+++ b/include/alist.h
@@ -0,0 +1,214 @@
+/* SPDX-License-Identifier: GPL-2.0+ */
+/*
+ * Handles a contiguous list of pointers which be allocated and freed
+ *
+ * Copyright 2023 Google LLC
+ * Written by Simon Glass <s...@chromium.org>
+ */
+
+#ifndef __ALIST_H
+#define __ALIST_H
+
+#include <stdbool.h>
+#include <linux/bitops.h>
+#include <linux/types.h>
+
+/**
+ * struct alist - object list that can be allocated and freed
+ *
+ * Holds a list of objects, each of the same size. The object is typically a
+ * C struct. The array is alloced in memory can change in size.
+ *
+ * The list rememebers the size of the list, but has a separate count of how
+ * much space is allocated, This allows it increase in size in steps as more
+ * elements are added, which is more efficient that reallocating the list every
+ * time a single item is added
+ *
+ * Two types of access are provided:
+ *
+ * alist_get...(index)
+ * gets an existing element, if its index is less that size
+ *
+ * alist_ensure(index)
+ * address an existing element, or creates a new one if not present
+ *
+ * @data: object data of size `@obj_size * @alloc`. The list can grow as
+ * needed but never shrinks
+ * @obj_size: Size of each object in bytes
+ * @count: number of objects in array
+ * @alloc: allocated length of array, to which @count can grow
+ * @flags: flags for the alist (ALISTF_...)
+ */
+struct alist {
+ void *data;
+ u16 obj_size;
+ u16 count;
+ u16 alloc;
+ u16 flags;
+};
+
+/**
+ * enum alist_flags - Flags for the alist
+ *
+ * @ALIST_FAIL: true if any allocation has failed. Once this has happened, the
+ * alist is dead and cannot grow further
+ */
+enum alist_flags {
+ ALISTF_FAIL = BIT(0),
+};
+
+/**
+ * alist_has() - Check if an index is within the list range
+ *
+ * Checks if index is within the current alist count
+ *
+ * @lst: alist to check
+ * @index: Index to check
+ * Returns: true if value, else false
+ */
+static inline bool alist_has(struct alist *lst, uint index)
+{
+ return index < lst->count;
+}
+
+/**
+ * alist_err() - Check if the alist is still valid
+ *
+ * @lst: List to check
+ * Return: false if OK, true if any previous allocation failed
+ */
+static inline bool alist_err(struct alist *lst)
+{
+ return lst->flags & ALISTF_FAIL;
+}
+
+/**
+ * alist_get_ptr() - Get the value of a pointer
+ *
+ * @lst: alist to check
+ * @index: Index to read from
+ * Returns: pointer, if present, else NULL
+ */
+const void *alist_get_ptr(const struct alist *lst, uint index);
+
+/**
+ * alist_getd() - Get the value of a pointer directly, with no checking
+ *
+ * This must only be called on indexes for which alist_has() returns true
+ *
+ * @lst: alist to check
+ * @index: Index to read from
+ * Returns: pointer value (may be NULL)
+ */
+static inline const void *alist_getd(struct alist *lst, uint index)
+{
+ return lst->data + index * lst->obj_size;
+}
+
+#define alist_get(_lst, _index, _struct) \
+ ((const _struct *)alist_get_ptr(_lst, _index))
+
+/**
+ * alist_ensure_ptr() - Ensure an object exists at a given index
+ *
+ * This provides read/write access to an array element. If it does not exist,
+ * it is allocated, reading for the caller to store the object into
+ *
+ * Allocates a object at the given index if needed
+ *
+ * @lst: alist to check
+ * @index: Index to address
+ * Returns: pointer where struct can be read/written, or NULL if out of memory
+ */
+void *alist_ensure_ptr(struct alist *lst, uint index);
+
+/**
+ * alist_ensure() - Address a struct, the correct object type
+ *
+ * Use as:
+ * struct my_struct *ptr = alist_ensure(&lst, 4, struct my_struct);
+ */
+#define alist_ensure(_lst, _index, _struct) \
+ ((_struct *)alist_ensure_ptr(_lst, _index))
+
+/**
+ * alist_add_ptr() - Ad a new object to the list
+ *
+ * @lst: alist to add to
+ * @obj: Pointer to object to copy in
+ * Returns: pointer to where the object was copied, or NULL if out of memory
+ */
+void *alist_add_ptr(struct alist *lst, void *obj);
+
+/**
+ * alist_expand_by() - Expand a list by the given amount
+ *
+ * @lst: alist to expand
+ * @inc_by: Amount to expand by
+ * Return: true if OK, false if out of memory
+ */
+bool alist_expand_by(struct alist *lst, uint inc_by);
+
+/**
+ * alist_add() - Used to add an object type with the correct type
+ *
+ * Use as:
+ * struct my_struct obj;
+ * struct my_struct *ptr = alist_add(&lst, &obj, struct my_struct);
+ */
+#define alist_add(_lst, _obj, _struct) \
+ ((_struct *)alist_add_ptr(_lst, (_struct *)&(_obj)))
+
+/**
+ * alist_init() - Set up a new object list
+ *
+ * Sets up a list of objects, initially empty
+ *
+ * @lst: alist to set up
+ * @obj_size: Size of each element in bytes
+ * @alloc_size: Number of items to allowed to start, before reallocation is
+ * needed (0 to start with no space)
+ * Return: true if OK, false if out of memory
+ */
+bool alist_init(struct alist *lst, uint obj_size, uint alloc_size);
+
+#define alist_init_struct(_lst, _struct) \
+ alist_init(_lst, sizeof(_struct), 0)
+
+/**
+ * alist_uninit_move_ptr() - Return the allocated contents and uninit the alist
+ *
+ * This returns the alist data to the caller, so that the caller receives data
+ * that it can be sure will hang around. The caller is responsible for freeing
+ * the data.
+ *
+ * If the alist size is 0, this returns NULL
+ *
+ * The alist is uninited as part of this.
+ *
+ * The alist must be inited before this can be called.
+ *
+ * @alist: alist to uninit
+ * @countp: if non-NULL, returns the number of objects in the returned data
+ * (which is @alist->size)
+ * Return: data contents, allocated with malloc(), or NULL if the data could
not
+ * be allocated, or the data size is 0
+ */
+void *alist_uninit_move_ptr(struct alist *alist, size_t *countp);
+
+/**
+ * alist_uninit_move() - Typed version of alist_uninit_move_ptr()
+ */
+#define alist_uninit_move(_lst, _countp, _struct) \
+ (_struct *)alist_uninit_move_ptr(_lst, _countp)
+
+/**
+ * alist_uninit() - Free any memory used by an alist
+ *
+ * The alist must be inited before this can be called.
+ *
+ * @alist: alist to uninit
+ */
+void alist_uninit(struct alist *alist);
+
+#endif /* __ALIST_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 2059219a120..40b59adbefc 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -8,6 +8,16 @@ config ADDR_MAP
This library only works in the post-relocation phase.
+config ALIST_REALLOC
+ bool "Use realloc() in the alist implementation"
+ help
+ An alist must expand when it runs out of space. It is more efficient
+ to use realloc() for this, but for boards which don't otherwise use
+ this function it can add 1KB of code space, so separate malloc() and
+ free are normally used instead.
+
+ Enable this to use realloc() in alist
+
config SYS_NUM_ADDR_MAP
int "Size of the address-map table"
depends on ADDR_MAP
diff --git a/lib/Makefile b/lib/Makefile
index e389ad014f8..81b503ab526 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -147,6 +147,7 @@ endif
obj-$(CONFIG_$(SPL_)OID_REGISTRY) += oid_registry.o
obj-y += abuf.o
+obj-y += alist.o
obj-y += date.o
obj-y += rtc-lib.o
obj-$(CONFIG_LIB_ELF) += elf.o
diff --git a/lib/alist.c b/lib/alist.c
new file mode 100644
index 00000000000..89339c02dfb
--- /dev/null
+++ b/lib/alist.c
@@ -0,0 +1,157 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Handles a contiguous list of pointers which be allocated and freed
+ *
+ * Copyright 2023 Google LLC
+ * Written by Simon Glass <s...@chromium.org>
+ */
+
+#include <alist.h>
+#include <display_options.h>
+#include <malloc.h>
+#include <stdio.h>
+#include <string.h>
+
+enum {
+ ALIST_INITIAL_SIZE = 4, /* default size of unsized list */
+};
+
+bool alist_init(struct alist *lst, uint obj_size, uint start_size)
+{
+ /* Avoid realloc for the initial size to help malloc_simple */
+ memset(lst, '\0', sizeof(struct alist));
+ if (start_size) {
+ lst->data = calloc(obj_size, start_size);
+ if (!lst->data) {
+ lst->flags = ALISTF_FAIL;
+ return false;
+ }
+ lst->alloc = start_size;
+ }
+ lst->obj_size = obj_size;
+
+ return true;
+}
+
+void alist_uninit(struct alist *lst)
+{
+ free(lst->data);
+
+ /* Clear fields to avoid any confusion */
+ memset(lst, '\0', sizeof(struct alist));
+}
+
+/**
+ * alist_expand_to() - Expand a list to the given size
+ *
+ * @lst: List to modify
+ * @inc_by: Amount to expand to
+ * Return: true if OK, false if out of memory
+ */
+static bool alist_expand_to(struct alist *lst, uint new_alloc)
+{
+ void *new_data;
+
+ if (lst->flags & ALISTF_FAIL)
+ return false;
+
+ if (CONFIG_IS_ENABLED(ALIST_REALLOC))
+ new_data = realloc(lst->data, lst->obj_size * new_alloc);
+ else
+ new_data = malloc(lst->obj_size * new_alloc);
+ if (!new_data) {
+ lst->flags |= ALISTF_FAIL;
+ return false;
+ }
+
+ if (!CONFIG_IS_ENABLED(ALIST_REALLOC)) {
+ memcpy(new_data, lst->data, lst->obj_size * lst->alloc);
+ free(lst->data);
+ }
+
+ memset(new_data + lst->obj_size * lst->alloc, '\0',
+ lst->obj_size * (new_alloc - lst->alloc));
+ lst->alloc = new_alloc;
+ lst->data = new_data;
+
+ return true;
+}
+
+bool alist_expand_by(struct alist *lst, uint inc_by)
+{
+ return alist_expand_to(lst, lst->alloc + inc_by);
+}
+
+/**
+ * alist_expand_min() - Expand to at least the provided size
+ *
+ * Expands to the lowest power of two which can incorporate the new size
+ *
+ * @lst: alist to expand
+ * @min_alloc: Minimum new allocated size; if 0 then ALIST_INITIAL_SIZE is used
+ * Return: true if OK, false if out of memory
+ */
+static bool alist_expand_min(struct alist *lst, uint min_alloc)
+{
+ uint new_alloc;
+
+ for (new_alloc = lst->alloc ?: ALIST_INITIAL_SIZE;
+ new_alloc < min_alloc;)
+ new_alloc *= 2;
+
+ return alist_expand_to(lst, new_alloc);
+}
+
+const void *alist_get_ptr(const struct alist *lst, uint index)
+{
+ if (index >= lst->count)
+ return NULL;
+
+ return lst->data + index * lst->obj_size;
+}
+
+void *alist_ensure_ptr(struct alist *lst, uint index)
+{
+ uint minsize = index + 1;
+ void *ptr;
+
+ if (index >= lst->alloc && !alist_expand_min(lst, minsize))
+ return NULL;
+
+ ptr = lst->data + index * lst->obj_size;
+ if (minsize >= lst->count)
+ lst->count = minsize;
+
+ return ptr;
+}
+
+void *alist_add_ptr(struct alist *lst, void *obj)
+{
+ void *ptr;
+
+ ptr = alist_ensure_ptr(lst, lst->count);
+ if (!ptr)
+ return ptr;
+ memcpy(ptr, obj, lst->obj_size);
+
+ return ptr;
+}
+
+void *alist_uninit_move_ptr(struct alist *alist, size_t *countp)
+{
+ void *ptr;
+
+ if (countp)
+ *countp = alist->count;
+ if (!alist->count) {
+ alist_uninit(alist);
+ return NULL;
+ }
+
+ ptr = alist->data;
+
+ /* Clear everything out so there is no record of the data */
+ alist_init(alist, alist->obj_size, 0);
+
+ return ptr;
+}
diff --git a/test/lib/Makefile b/test/lib/Makefile
index e75a263e6a4..70f14c46b1e 100644
--- a/test/lib/Makefile
+++ b/test/lib/Makefile
@@ -5,6 +5,7 @@
ifeq ($(CONFIG_SPL_BUILD),)
obj-y += cmd_ut_lib.o
obj-y += abuf.o
+obj-y += alist.o
obj-$(CONFIG_EFI_LOADER) += efi_device_path.o
obj-$(CONFIG_EFI_SECURE_BOOT) += efi_image_region.o
obj-y += hexdump.o
diff --git a/test/lib/alist.c b/test/lib/alist.c
new file mode 100644
index 00000000000..f9050a963e0
--- /dev/null
+++ b/test/lib/alist.c
@@ -0,0 +1,197 @@
+// SPDX-License-Identifier: GPL-2.0+
+/*
+ * Copyright 2023 Google LLC
+ * Written by Simon Glass <s...@chromium.org>
+ */
+
+#include <alist.h>
+#include <string.h>
+#include <test/lib.h>
+#include <test/test.h>
+#include <test/ut.h>
+
+struct my_struct {
+ uint val;
+ uint other_val;
+};
+
+enum {
+ obj_size = sizeof(struct my_struct),
+};
+
+/* Test alist_init() */
+static int lib_test_alist_init(struct unit_test_state *uts)
+{
+ struct alist lst;
+ ulong start;
+
+ start = ut_check_free();
+
+ /* with a size of 0, the fields should be inited, with no memory used */
+ memset(&lst, '\xff', sizeof(lst));
+ ut_assert(alist_init_struct(&lst, struct my_struct));
+ ut_asserteq_ptr(NULL, lst.data);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(0, lst.alloc);
+ ut_assertok(ut_check_delta(start));
+ alist_uninit(&lst);
+ ut_asserteq_ptr(NULL, lst.data);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(0, lst.alloc);
+
+ /* use an impossible size */
+ ut_asserteq(false, alist_init(&lst, obj_size,
+ CONFIG_SYS_MALLOC_LEN));
+ ut_assertnull(lst.data);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(0, lst.alloc);
+
+ /* use a small size */
+ ut_assert(alist_init(&lst, obj_size, 4));
+ ut_assertnonnull(lst.data);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(4, lst.alloc);
+
+ /* free it */
+ alist_uninit(&lst);
+ ut_asserteq_ptr(NULL, lst.data);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(0, lst.alloc);
+ ut_assertok(ut_check_delta(start));
+
+ /* Check for memory leaks */
+ ut_assertok(ut_check_delta(start));
+
+ return 0;
+}
+LIB_TEST(lib_test_alist_init, 0);
+
+/* Test alist_get() and alist_getd() */
+static int lib_test_alist_get(struct unit_test_state *uts)
+{
+ struct alist lst;
+ ulong start;
+ void *ptr;
+
+ start = ut_check_free();
+
+ ut_assert(alist_init(&lst, obj_size, 3));
+ ut_asserteq(0, lst.count);
+ ut_asserteq(3, lst.alloc);
+
+ ut_assertnull(alist_get_ptr(&lst, 2));
+ ut_assertnull(alist_get_ptr(&lst, 3));
+
+ ptr = alist_ensure_ptr(&lst, 1);
+ ut_assertnonnull(ptr);
+ ut_asserteq(2, lst.count);
+ ptr = alist_ensure_ptr(&lst, 2);
+ ut_asserteq(3, lst.count);
+ ut_assertnonnull(ptr);
+
+ ptr = alist_ensure_ptr(&lst, 3);
+ ut_assertnonnull(ptr);
+ ut_asserteq(4, lst.count);
+ ut_asserteq(6, lst.alloc);
+
+ ut_assertnull(alist_get_ptr(&lst, 4));
+
+ alist_uninit(&lst);
+
+ /* Check for memory leaks */
+ ut_assertok(ut_check_delta(start));
+
+ return 0;
+}
+LIB_TEST(lib_test_alist_get, 0);
+
+/* Test alist_has() */
+static int lib_test_alist_has(struct unit_test_state *uts)
+{
+ struct alist lst;
+ ulong start;
+ void *ptr;
+
+ start = ut_check_free();
+
+ ut_assert(alist_init(&lst, obj_size, 3));
+
+ ut_assert(!alist_has(&lst, 0));
+ ut_assert(!alist_has(&lst, 1));
+ ut_assert(!alist_has(&lst, 2));
+ ut_assert(!alist_has(&lst, 3));
+
+ /* create a new one to force expansion */
+ ptr = alist_ensure_ptr(&lst, 4);
+ ut_assertnonnull(ptr);
+
+ ut_assert(alist_has(&lst, 0));
+ ut_assert(alist_has(&lst, 1));
+ ut_assert(alist_has(&lst, 2));
+ ut_assert(alist_has(&lst, 3));
+ ut_assert(alist_has(&lst, 4));
+ ut_assert(!alist_has(&lst, 5));
+
+ alist_uninit(&lst);
+
+ /* Check for memory leaks */
+ ut_assertok(ut_check_delta(start));
+
+ return 0;
+}
+LIB_TEST(lib_test_alist_has, 0);
+
+/* Test alist_ensure() */
+static int lib_test_alist_ensure(struct unit_test_state *uts)
+{
+ struct my_struct *ptr3, *ptr4;
+ struct alist lst;
+ ulong start;
+
+ start = ut_check_free();
+
+ ut_assert(alist_init_struct(&lst, struct my_struct));
+ ut_asserteq(obj_size, lst.obj_size);
+ ut_asserteq(0, lst.count);
+ ut_asserteq(0, lst.alloc);
+ ptr3 = alist_ensure_ptr(&lst, 3);
+ ut_asserteq(4, lst.count);
+ ut_asserteq(4, lst.alloc);
+ ut_assertnonnull(ptr3);
+ ptr3->val = 3;
+
+ ptr4 = alist_ensure_ptr(&lst, 4);
+ ut_asserteq(8, lst.alloc);
+ ut_asserteq(5, lst.count);
+ ut_assertnonnull(ptr4);
+ ptr4->val = 4;
+ ut_asserteq(4, alist_get(&lst, 4, struct my_struct)->val);
+
+ ut_asserteq_ptr(ptr4, alist_ensure(&lst, 4, struct my_struct));
+
+ alist_ensure(&lst, 4, struct my_struct)->val = 44;
+ ut_asserteq(44, alist_get(&lst, 4, struct my_struct)->val);
+ ut_asserteq(3, alist_get(&lst, 3, struct my_struct)->val);
+ ut_assertnull(alist_get(&lst, 7, struct my_struct));
+ ut_asserteq(8, lst.alloc);
+ ut_asserteq(5, lst.count);
+
+ /* add some more, checking handling of malloc() failure */
+ malloc_enable_testing(0);
+ ut_assertnonnull(alist_ensure(&lst, 7, struct my_struct));
+ ut_assertnull(alist_ensure(&lst, 8, struct my_struct));
+ malloc_disable_testing();
+
+ lst.flags &= ~ALISTF_FAIL;
+ ut_assertnonnull(alist_ensure(&lst, 8, struct my_struct));
+ ut_asserteq(16, lst.alloc);
+ ut_asserteq(9, lst.count);
+
+ alist_uninit(&lst);
+
+ /* Check for memory leaks */
+ ut_assertok(ut_check_delta(start));
+
+ return 0;
+}
+LIB_TEST(lib_test_alist_ensure, 0);
--
2.34.1
