[PATCH v3 0/3] lib: sbi: Heap improvements for SMMTT

[PATCH v3 0/3] lib: sbi: Heap improvements for SMMTT

[Gregor Haas]

This patch series includes two changes to the SBI heap implementation, primarily
to enable future work on the SMMTT implementation. First, it enables allocations
from multiple independent heaps on separate memory regions. Then, it adds a simple
implementation for sbi_memalign for use in allocating aligned memory.

See the individual commit messages in this series for more technical details.

v3:
- Add missing Signed-off-by lines
- Rename struct heap_control -> struct sbi_heap_control
- Make various functions static inline in sbi_heap.h
- Fix previously incorrect sbi_memalign() implementation

Gregor Haas (3):
  lib: sbi: Support multiple heaps
  lib: sbi: Allocate from beginning of heap blocks
  lib: sbi: Implement aligned memory allocators

 include/sbi/sbi_heap.h |  66 +++++++++++--
 lib/sbi/sbi_heap.c     | 204 +++++++++++++++++++++++++++++------------
 2 files changed, 204 insertions(+), 66 deletions(-)

-- 
2.45.2

[PATCH v3 1/3] lib: sbi: Support multiple heaps

[Gregor Haas]

The upcoming SMMTT implementation will require some larger contiguous memory
regions for the memory tracking tables. We plan to specify the memory region
for these tables as a reserved-memory node in the device tree, and then
dynamically allocate individual tables out of this region. These changes to the
SBI heap allocator will allow us to explicitly create and allocate from a
dedicated heap tied to the table memory region.

Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
---
 include/sbi/sbi_heap.h |  57 +++++++++++++++++--
 lib/sbi/sbi_heap.c     | 122 +++++++++++++++++++++++------------------
 2 files changed, 119 insertions(+), 60 deletions(-)

diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
index 16755ec..9a67090 100644
--- a/include/sbi/sbi_heap.h
+++ b/include/sbi/sbi_heap.h
@@ -12,16 +12,32 @@
 
 #include <sbi/sbi_types.h>
 
+/* Opaque declaration of heap control struct */
+struct sbi_heap_control;
+
+/* Global heap control structure */
+extern struct sbi_heap_control global_hpctrl;
+
 /* Alignment of heap base address and size */
 #define HEAP_BASE_ALIGN			1024
 
 struct sbi_scratch;
 
 /** Allocate from heap area */
-void *sbi_malloc(size_t size);
+void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size);
+
+static inline void *sbi_malloc(size_t size)
+{
+	return sbi_malloc_from(&global_hpctrl, size);
+}
 
 /** Zero allocate from heap area */
-void *sbi_zalloc(size_t size);
+void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
+
+static inline void *sbi_zalloc(size_t size)
+{
+	return sbi_zalloc_from(&global_hpctrl, size);
+}
 
 /** Allocate array from heap area */
 static inline void *sbi_calloc(size_t nitems, size_t size)
@@ -29,19 +45,48 @@ static inline void *sbi_calloc(size_t nitems, size_t size)
 	return sbi_zalloc(nitems * size);
 }
 
+static inline void *sbi_calloc_from(struct sbi_heap_control *hpctrl,
+				    size_t nitems, size_t size)
+{
+	return sbi_zalloc_from(hpctrl, nitems * size);
+}
+
 /** Free-up to heap area */
-void sbi_free(void *ptr);
+void sbi_free_from(struct sbi_heap_control *hpctrl, void *ptr);
+
+static inline void sbi_free(void *ptr)
+{
+	return sbi_free_from(&global_hpctrl, ptr);
+}
 
 /** Amount (in bytes) of free space in the heap area */
-unsigned long sbi_heap_free_space(void);
+unsigned long sbi_heap_free_space_from(struct sbi_heap_control *hpctrl);
+
+static inline unsigned long sbi_heap_free_space(void)
+{
+	return sbi_heap_free_space_from(&global_hpctrl);
+}
 
 /** Amount (in bytes) of used space in the heap area */
-unsigned long sbi_heap_used_space(void);
+unsigned long sbi_heap_used_space_from(struct sbi_heap_control *hpctrl);
+
+static inline unsigned long sbi_heap_used_space(void)
+{
+	return sbi_heap_used_space_from(&global_hpctrl);
+}
 
 /** Amount (in bytes) of reserved space in the heap area */
-unsigned long sbi_heap_reserved_space(void);
+unsigned long sbi_heap_reserved_space_from(struct sbi_heap_control *hpctrl);
+
+static inline unsigned long sbi_heap_reserved_space(void)
+{
+	return sbi_heap_reserved_space_from(&global_hpctrl);
+}
 
 /** Initialize heap area */
 int sbi_heap_init(struct sbi_scratch *scratch);
+int sbi_heap_init_new(struct sbi_heap_control *hpctrl, unsigned long base,
+		       unsigned long size);
+int sbi_heap_alloc_new(struct sbi_heap_control **hpctrl);
 
 #endif
diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
index bcd404b..e43d77c 100644
--- a/lib/sbi/sbi_heap.c
+++ b/lib/sbi/sbi_heap.c
@@ -24,7 +24,7 @@ struct heap_node {
 	unsigned long size;
 };
 
-struct heap_control {
+struct sbi_heap_control {
 	spinlock_t lock;
 	unsigned long base;
 	unsigned long size;
@@ -35,9 +35,9 @@ struct heap_control {
 	struct sbi_dlist used_space_list;
 };
 
-static struct heap_control hpctrl;
+struct sbi_heap_control global_hpctrl;
 
-void *sbi_malloc(size_t size)
+void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
 {
 	void *ret = NULL;
 	struct heap_node *n, *np;
@@ -48,10 +48,10 @@ void *sbi_malloc(size_t size)
 	size += HEAP_ALLOC_ALIGN - 1;
 	size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
 
-	spin_lock(&hpctrl.lock);
+	spin_lock(&hpctrl->lock);
 
 	np = NULL;
-	sbi_list_for_each_entry(n, &hpctrl.free_space_list, head) {
+	sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
 		if (size <= n->size) {
 			np = n;
 			break;
@@ -59,47 +59,47 @@ void *sbi_malloc(size_t size)
 	}
 	if (np) {
 		if ((size < np->size) &&
-		    !sbi_list_empty(&hpctrl.free_node_list)) {
-			n = sbi_list_first_entry(&hpctrl.free_node_list,
+		    !sbi_list_empty(&hpctrl->free_node_list)) {
+			n = sbi_list_first_entry(&hpctrl->free_node_list,
 						 struct heap_node, head);
 			sbi_list_del(&n->head);
 			n->addr = np->addr + np->size - size;
 			n->size = size;
 			np->size -= size;
-			sbi_list_add_tail(&n->head, &hpctrl.used_space_list);
+			sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
 			ret = (void *)n->addr;
 		} else if (size == np->size) {
 			sbi_list_del(&np->head);
-			sbi_list_add_tail(&np->head, &hpctrl.used_space_list);
+			sbi_list_add_tail(&np->head, &hpctrl->used_space_list);
 			ret = (void *)np->addr;
 		}
 	}
 
-	spin_unlock(&hpctrl.lock);
+	spin_unlock(&hpctrl->lock);
 
 	return ret;
 }
 
-void *sbi_zalloc(size_t size)
+void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
 {
-	void *ret = sbi_malloc(size);
+	void *ret = sbi_malloc_from(hpctrl, size);
 
 	if (ret)
 		sbi_memset(ret, 0, size);
 	return ret;
 }
 
-void sbi_free(void *ptr)
+void sbi_free_from(struct sbi_heap_control *hpctrl, void *ptr)
 {
 	struct heap_node *n, *np;
 
 	if (!ptr)
 		return;
 
-	spin_lock(&hpctrl.lock);
+	spin_lock(&hpctrl->lock);
 
 	np = NULL;
-	sbi_list_for_each_entry(n, &hpctrl.used_space_list, head) {
+	sbi_list_for_each_entry(n, &hpctrl->used_space_list, head) {
 		if ((n->addr <= (unsigned long)ptr) &&
 		    ((unsigned long)ptr < (n->addr + n->size))) {
 			np = n;
@@ -107,22 +107,22 @@ void sbi_free(void *ptr)
 		}
 	}
 	if (!np) {
-		spin_unlock(&hpctrl.lock);
+		spin_unlock(&hpctrl->lock);
 		return;
 	}
 
 	sbi_list_del(&np->head);
 
-	sbi_list_for_each_entry(n, &hpctrl.free_space_list, head) {
+	sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
 		if ((np->addr + np->size) == n->addr) {
 			n->addr = np->addr;
 			n->size += np->size;
-			sbi_list_add_tail(&np->head, &hpctrl.free_node_list);
+			sbi_list_add_tail(&np->head, &hpctrl->free_node_list);
 			np = NULL;
 			break;
 		} else if (np->addr == (n->addr + n->size)) {
 			n->size += np->size;
-			sbi_list_add_tail(&np->head, &hpctrl.free_node_list);
+			sbi_list_add_tail(&np->head, &hpctrl->free_node_list);
 			np = NULL;
 			break;
 		} else if ((n->addr + n->size) < np->addr) {
@@ -132,73 +132,87 @@ void sbi_free(void *ptr)
 		}
 	}
 	if (np)
-		sbi_list_add_tail(&np->head, &hpctrl.free_space_list);
+		sbi_list_add_tail(&np->head, &hpctrl->free_space_list);
 
-	spin_unlock(&hpctrl.lock);
+	spin_unlock(&hpctrl->lock);
 }
 
-unsigned long sbi_heap_free_space(void)
+unsigned long sbi_heap_free_space_from(struct sbi_heap_control *hpctrl)
 {
 	struct heap_node *n;
 	unsigned long ret = 0;
 
-	spin_lock(&hpctrl.lock);
-	sbi_list_for_each_entry(n, &hpctrl.free_space_list, head)
+	spin_lock(&hpctrl->lock);
+	sbi_list_for_each_entry(n, &hpctrl->free_space_list, head)
 		ret += n->size;
-	spin_unlock(&hpctrl.lock);
+	spin_unlock(&hpctrl->lock);
 
 	return ret;
 }
 
-unsigned long sbi_heap_used_space(void)
+unsigned long sbi_heap_used_space_from(struct sbi_heap_control *hpctrl)
 {
-	return hpctrl.size - hpctrl.hksize - sbi_heap_free_space();
+	return hpctrl->size - hpctrl->hksize - sbi_heap_free_space();
 }
 
-unsigned long sbi_heap_reserved_space(void)
+unsigned long sbi_heap_reserved_space_from(struct sbi_heap_control *hpctrl)
 {
-	return hpctrl.hksize;
+	return hpctrl->hksize;
 }
 
-int sbi_heap_init(struct sbi_scratch *scratch)
+int sbi_heap_init_new(struct sbi_heap_control *hpctrl, unsigned long base,
+		       unsigned long size)
 {
 	unsigned long i;
 	struct heap_node *n;
 
-	/* Sanity checks on heap offset and size */
-	if (!scratch->fw_heap_size ||
-	    (scratch->fw_heap_size & (HEAP_BASE_ALIGN - 1)) ||
-	    (scratch->fw_heap_offset < scratch->fw_rw_offset) ||
-	    (scratch->fw_size < (scratch->fw_heap_offset + scratch->fw_heap_size)) ||
-	    (scratch->fw_heap_offset & (HEAP_BASE_ALIGN - 1)))
-		return SBI_EINVAL;
-
 	/* Initialize heap control */
-	SPIN_LOCK_INIT(hpctrl.lock);
-	hpctrl.base = scratch->fw_start + scratch->fw_heap_offset;
-	hpctrl.size = scratch->fw_heap_size;
-	hpctrl.hkbase = hpctrl.base;
-	hpctrl.hksize = hpctrl.size / HEAP_HOUSEKEEPING_FACTOR;
-	hpctrl.hksize &= ~((unsigned long)HEAP_BASE_ALIGN - 1);
-	SBI_INIT_LIST_HEAD(&hpctrl.free_node_list);
-	SBI_INIT_LIST_HEAD(&hpctrl.free_space_list);
-	SBI_INIT_LIST_HEAD(&hpctrl.used_space_list);
+	SPIN_LOCK_INIT(hpctrl->lock);
+	hpctrl->base = base;
+	hpctrl->size = size;
+	hpctrl->hkbase = hpctrl->base;
+	hpctrl->hksize = hpctrl->size / HEAP_HOUSEKEEPING_FACTOR;
+	hpctrl->hksize &= ~((unsigned long)HEAP_BASE_ALIGN - 1);
+	SBI_INIT_LIST_HEAD(&hpctrl->free_node_list);
+	SBI_INIT_LIST_HEAD(&hpctrl->free_space_list);
+	SBI_INIT_LIST_HEAD(&hpctrl->used_space_list);
 
 	/* Prepare free node list */
-	for (i = 0; i < (hpctrl.hksize / sizeof(*n)); i++) {
-		n = (struct heap_node *)(hpctrl.hkbase + (sizeof(*n) * i));
+	for (i = 0; i < (hpctrl->hksize / sizeof(*n)); i++) {
+		n = (struct heap_node *)(hpctrl->hkbase + (sizeof(*n) * i));
 		SBI_INIT_LIST_HEAD(&n->head);
 		n->addr = n->size = 0;
-		sbi_list_add_tail(&n->head, &hpctrl.free_node_list);
+		sbi_list_add_tail(&n->head, &hpctrl->free_node_list);
 	}
 
 	/* Prepare free space list */
-	n = sbi_list_first_entry(&hpctrl.free_node_list,
+	n = sbi_list_first_entry(&hpctrl->free_node_list,
 				 struct heap_node, head);
 	sbi_list_del(&n->head);
-	n->addr = hpctrl.hkbase + hpctrl.hksize;
-	n->size = hpctrl.size - hpctrl.hksize;
-	sbi_list_add_tail(&n->head, &hpctrl.free_space_list);
+	n->addr = hpctrl->hkbase + hpctrl->hksize;
+	n->size = hpctrl->size - hpctrl->hksize;
+	sbi_list_add_tail(&n->head, &hpctrl->free_space_list);
+
+	return 0;
+}
 
+int sbi_heap_init(struct sbi_scratch *scratch)
+{
+	/* Sanity checks on heap offset and size */
+	if (!scratch->fw_heap_size ||
+	    (scratch->fw_heap_size & (HEAP_BASE_ALIGN - 1)) ||
+	    (scratch->fw_heap_offset < scratch->fw_rw_offset) ||
+	    (scratch->fw_size < (scratch->fw_heap_offset + scratch->fw_heap_size)) ||
+	    (scratch->fw_heap_offset & (HEAP_BASE_ALIGN - 1)))
+		return SBI_EINVAL;
+
+	return sbi_heap_init_new(&global_hpctrl,
+				  scratch->fw_start + scratch->fw_heap_offset,
+				  scratch->fw_heap_size);
+}
+
+int sbi_heap_alloc_new(struct sbi_heap_control **hpctrl)
+{
+	*hpctrl = sbi_calloc(1, sizeof(struct sbi_heap_control));
 	return 0;
 }
-- 
2.45.2

[PATCH v3 2/3] lib: sbi: Allocate from beginning of heap blocks

[Gregor Haas]

In the next commit, we'll add a new sbi_memalign() function. In order to
allocate aligned memory, we'll sometimes need to allocate from the middle of a
heap block, effectively splitting it in two. Allocating from the beginning of a
heap block in the nonaligned case more closely matches this behavior, reducing
the complexity of understanding the heap implementation.

Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
---
 lib/sbi/sbi_heap.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
index e43d77c..cc4893d 100644
--- a/lib/sbi/sbi_heap.c
+++ b/lib/sbi/sbi_heap.c
@@ -63,8 +63,9 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
 			n = sbi_list_first_entry(&hpctrl->free_node_list,
 						 struct heap_node, head);
 			sbi_list_del(&n->head);
-			n->addr = np->addr + np->size - size;
+			n->addr = np->addr;
 			n->size = size;
+			np->addr += size;
 			np->size -= size;
 			sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
 			ret = (void *)n->addr;
-- 
2.45.2

[PATCH v3 3/3] lib: sbi: Implement aligned memory allocators

[Gregor Haas]

This change adds a simple implementation of sbi_memalign(), for future use in
allocating aligned memory for SMMTT tables.

Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
---
 include/sbi/sbi_heap.h |  9 +++++
 lib/sbi/sbi_heap.c     | 81 ++++++++++++++++++++++++++++++++++++++----
 2 files changed, 84 insertions(+), 6 deletions(-)

diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
index 9a67090..2103aef 100644
--- a/include/sbi/sbi_heap.h
+++ b/include/sbi/sbi_heap.h
@@ -31,6 +31,15 @@ static inline void *sbi_malloc(size_t size)
 	return sbi_malloc_from(&global_hpctrl, size);
 }
 
+/** Allocate aligned from heap area */
+void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
+			size_t size);
+
+static inline void *sbi_memalign(size_t alignment, size_t size)
+{
+	return sbi_memalign_from(&global_hpctrl, alignment, size);
+}
+
 /** Zero allocate from heap area */
 void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
 
diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
index cc4893d..ea73b54 100644
--- a/lib/sbi/sbi_heap.c
+++ b/lib/sbi/sbi_heap.c
@@ -37,27 +37,70 @@ struct sbi_heap_control {
 
 struct sbi_heap_control global_hpctrl;
 
-void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
+static void *alloc_with_align(struct sbi_heap_control *hpctrl,
+			      size_t align, size_t size)
 {
 	void *ret = NULL;
-	struct heap_node *n, *np;
+	struct heap_node *n, *np, *rem;
+	uint64_t lowest_aligned;
+	size_t pad;
 
 	if (!size)
 		return NULL;
 
-	size += HEAP_ALLOC_ALIGN - 1;
-	size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
+	size += align - 1;
+	size &= ~((unsigned long)align - 1);
 
 	spin_lock(&hpctrl->lock);
 
 	np = NULL;
 	sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
-		if (size <= n->size) {
+		lowest_aligned = ROUNDUP(n->addr, align);
+		pad = lowest_aligned - n->addr;
+
+		if (size + pad <= n->size) {
 			np = n;
 			break;
 		}
 	}
-	if (np) {
+	if (!np) {
+		goto out;
+	}
+
+	if (pad) {
+		if (sbi_list_empty(&hpctrl->free_node_list)) {
+			goto out;
+		}
+
+		n = sbi_list_first_entry(&hpctrl->free_node_list,
+					 struct heap_node, head);
+		sbi_list_del(&n->head);
+
+		if ((size + pad < np->size) &&
+		    !sbi_list_empty(&hpctrl->free_node_list)) {
+			rem = sbi_list_first_entry(&hpctrl->free_node_list,
+						   struct heap_node, head);
+			sbi_list_del(&rem->head);
+			rem->addr = np->addr + (size + pad);
+			rem->size = np->size - (size + pad);
+			sbi_list_add_tail(&rem->head,
+					  &hpctrl->free_space_list);
+
+			n->addr = lowest_aligned;
+			n->size = size;
+			np->size = pad;
+			sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
+			ret = (void *)n->addr;
+		} else if (size + pad == np->size) {
+			n->addr = lowest_aligned;
+			n->size = size;
+			np->size = pad;
+			ret = (void *)n->addr;
+		} else {
+			// Can't allocate, return n
+			sbi_list_add(&n->head, &hpctrl->free_node_list);
+		}
+	} else {
 		if ((size < np->size) &&
 		    !sbi_list_empty(&hpctrl->free_node_list)) {
 			n = sbi_list_first_entry(&hpctrl->free_node_list,
@@ -76,11 +119,37 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
 		}
 	}
 
+out:
 	spin_unlock(&hpctrl->lock);
 
 	return ret;
 }
 
+void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
+{
+	return alloc_with_align(hpctrl, HEAP_ALLOC_ALIGN, size);
+}
+
+void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
+			size_t size)
+{
+	if(alignment < HEAP_ALLOC_ALIGN) {
+		alignment = HEAP_ALLOC_ALIGN;
+	}
+
+	// Make sure alignment is power of two
+	if((alignment & (alignment - 1)) != 0) {
+		return NULL;
+	}
+
+	// Make sure size is multiple of alignment
+	if(size % alignment != 0) {
+		return NULL;
+	}
+
+	return alloc_with_align(hpctrl, alignment, size);
+}
+
 void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
 {
 	void *ret = sbi_malloc_from(hpctrl, size);
-- 
2.45.2

[PATCH v3 3/3] lib: sbi: Implement aligned memory allocators

[Anup Patel]

On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>
> This change adds a simple implementation of sbi_memalign(), for future use in
> allocating aligned memory for SMMTT tables.
>
> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
> ---
>  include/sbi/sbi_heap.h |  9 +++++
>  lib/sbi/sbi_heap.c     | 81 ++++++++++++++++++++++++++++++++++++++----
>  2 files changed, 84 insertions(+), 6 deletions(-)
>
> diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
> index 9a67090..2103aef 100644
> --- a/include/sbi/sbi_heap.h
> +++ b/include/sbi/sbi_heap.h
> @@ -31,6 +31,15 @@ static inline void *sbi_malloc(size_t size)
>         return sbi_malloc_from(&global_hpctrl, size);
>  }
>
> +/** Allocate aligned from heap area */
> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
> +                       size_t size);
> +
> +static inline void *sbi_memalign(size_t alignment, size_t size)
> +{
> +       return sbi_memalign_from(&global_hpctrl, alignment, size);
> +}

The term "memalign" does not imply it is a memory allocation function.

I suggest the following names instead:
sbi_malloc_aligned_from()
sbi_malloc_aligned()

> +
>  /** Zero allocate from heap area */
>  void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
>
> diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
> index cc4893d..ea73b54 100644
> --- a/lib/sbi/sbi_heap.c
> +++ b/lib/sbi/sbi_heap.c
> @@ -37,27 +37,70 @@ struct sbi_heap_control {
>
>  struct sbi_heap_control global_hpctrl;
>
> -void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
> +static void *alloc_with_align(struct sbi_heap_control *hpctrl,
> +                             size_t align, size_t size)
>  {
>         void *ret = NULL;
> -       struct heap_node *n, *np;
> +       struct heap_node *n, *np, *rem;
> +       uint64_t lowest_aligned;

Since this represents the lowest aligned address, the data type
should be "unsigned long".

> +       size_t pad;
>
>         if (!size)
>                 return NULL;
>
> -       size += HEAP_ALLOC_ALIGN - 1;
> -       size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
> +       size += align - 1;
> +       size &= ~((unsigned long)align - 1);
>
>         spin_lock(&hpctrl->lock);
>
>         np = NULL;
>         sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
> -               if (size <= n->size) {
> +               lowest_aligned = ROUNDUP(n->addr, align);
> +               pad = lowest_aligned - n->addr;
> +
> +               if (size + pad <= n->size) {
>                         np = n;
>                         break;
>                 }
>         }
> -       if (np) {
> +       if (!np) {
> +               goto out;
> +       }

No need for {} here.

> +
> +       if (pad) {
> +               if (sbi_list_empty(&hpctrl->free_node_list)) {
> +                       goto out;
> +               }

No need for {} here.

> +
> +               n = sbi_list_first_entry(&hpctrl->free_node_list,
> +                                        struct heap_node, head);
> +               sbi_list_del(&n->head);
> +
> +               if ((size + pad < np->size) &&
> +                   !sbi_list_empty(&hpctrl->free_node_list)) {
> +                       rem = sbi_list_first_entry(&hpctrl->free_node_list,
> +                                                  struct heap_node, head);
> +                       sbi_list_del(&rem->head);
> +                       rem->addr = np->addr + (size + pad);
> +                       rem->size = np->size - (size + pad);
> +                       sbi_list_add_tail(&rem->head,
> +                                         &hpctrl->free_space_list);
> +
> +                       n->addr = lowest_aligned;
> +                       n->size = size;
> +                       np->size = pad;
> +                       sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
> +                       ret = (void *)n->addr;
> +               } else if (size + pad == np->size) {
> +                       n->addr = lowest_aligned;
> +                       n->size = size;
> +                       np->size = pad;
> +                       ret = (void *)n->addr;
> +               } else {
> +                       // Can't allocate, return n

Use C-style comments.

> +                       sbi_list_add(&n->head, &hpctrl->free_node_list);
> +               }
> +       } else {
>                 if ((size < np->size) &&
>                     !sbi_list_empty(&hpctrl->free_node_list)) {
>                         n = sbi_list_first_entry(&hpctrl->free_node_list,
> @@ -76,11 +119,37 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>                 }
>         }
>
> +out:
>         spin_unlock(&hpctrl->lock);
>
>         return ret;
>  }
>
> +void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
> +{
> +       return alloc_with_align(hpctrl, HEAP_ALLOC_ALIGN, size);
> +}
> +
> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
> +                       size_t size)
> +{
> +       if(alignment < HEAP_ALLOC_ALIGN) {

Need a space between "if" and "(".

> +               alignment = HEAP_ALLOC_ALIGN;
> +       }

No need for {} here.

> +
> +       // Make sure alignment is power of two

Use C-style comments.

> +       if((alignment & (alignment - 1)) != 0) {

Need a space between "if" and "(".

> +               return NULL;
> +       }

No need for {} here.

> +
> +       // Make sure size is multiple of alignment

Use C-style comments.

> +       if(size % alignment != 0) {
> +               return NULL;
> +       }

No need for {} here.

> +
> +       return alloc_with_align(hpctrl, alignment, size);
> +}
> +
>  void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
>  {
>         void *ret = sbi_malloc_from(hpctrl, size);
> --
> 2.45.2
>

Regards,
Anup

[PATCH v3 2/3] lib: sbi: Allocate from beginning of heap blocks

[Anup Patel]

On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>
> In the next commit, we'll add a new sbi_memalign() function. In order to
> allocate aligned memory, we'll sometimes need to allocate from the middle of a
> heap block, effectively splitting it in two. Allocating from the beginning of a
> heap block in the nonaligned case more closely matches this behavior, reducing
> the complexity of understanding the heap implementation.
>
> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>

LGTM.

Reviewed-by: Anup Patel <anup@brainfault.org>

Regards,
Anup


> ---
>  lib/sbi/sbi_heap.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
> index e43d77c..cc4893d 100644
> --- a/lib/sbi/sbi_heap.c
> +++ b/lib/sbi/sbi_heap.c
> @@ -63,8 +63,9 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>                         n = sbi_list_first_entry(&hpctrl->free_node_list,
>                                                  struct heap_node, head);
>                         sbi_list_del(&n->head);
> -                       n->addr = np->addr + np->size - size;
> +                       n->addr = np->addr;
>                         n->size = size;
> +                       np->addr += size;
>                         np->size -= size;
>                         sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
>                         ret = (void *)n->addr;
> --
> 2.45.2
>

[PATCH v3 1/3] lib: sbi: Support multiple heaps

[Anup Patel]

On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>
> The upcoming SMMTT implementation will require some larger contiguous memory
> regions for the memory tracking tables. We plan to specify the memory region
> for these tables as a reserved-memory node in the device tree, and then
> dynamically allocate individual tables out of this region. These changes to the
> SBI heap allocator will allow us to explicitly create and allocate from a
> dedicated heap tied to the table memory region.
>
> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>

LGTM.

Reviewed-by: Anup Patel <anup@brainfault.org>

Regards,
Anup


> ---
>  include/sbi/sbi_heap.h |  57 +++++++++++++++++--
>  lib/sbi/sbi_heap.c     | 122 +++++++++++++++++++++++------------------
>  2 files changed, 119 insertions(+), 60 deletions(-)
>
> diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
> index 16755ec..9a67090 100644
> --- a/include/sbi/sbi_heap.h
> +++ b/include/sbi/sbi_heap.h
> @@ -12,16 +12,32 @@
>
>  #include <sbi/sbi_types.h>
>
> +/* Opaque declaration of heap control struct */
> +struct sbi_heap_control;
> +
> +/* Global heap control structure */
> +extern struct sbi_heap_control global_hpctrl;
> +
>  /* Alignment of heap base address and size */
>  #define HEAP_BASE_ALIGN                        1024
>
>  struct sbi_scratch;
>
>  /** Allocate from heap area */
> -void *sbi_malloc(size_t size);
> +void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size);
> +
> +static inline void *sbi_malloc(size_t size)
> +{
> +       return sbi_malloc_from(&global_hpctrl, size);
> +}
>
>  /** Zero allocate from heap area */
> -void *sbi_zalloc(size_t size);
> +void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
> +
> +static inline void *sbi_zalloc(size_t size)
> +{
> +       return sbi_zalloc_from(&global_hpctrl, size);
> +}
>
>  /** Allocate array from heap area */
>  static inline void *sbi_calloc(size_t nitems, size_t size)
> @@ -29,19 +45,48 @@ static inline void *sbi_calloc(size_t nitems, size_t size)
>         return sbi_zalloc(nitems * size);
>  }
>
> +static inline void *sbi_calloc_from(struct sbi_heap_control *hpctrl,
> +                                   size_t nitems, size_t size)
> +{
> +       return sbi_zalloc_from(hpctrl, nitems * size);
> +}
> +
>  /** Free-up to heap area */
> -void sbi_free(void *ptr);
> +void sbi_free_from(struct sbi_heap_control *hpctrl, void *ptr);
> +
> +static inline void sbi_free(void *ptr)
> +{
> +       return sbi_free_from(&global_hpctrl, ptr);
> +}
>
>  /** Amount (in bytes) of free space in the heap area */
> -unsigned long sbi_heap_free_space(void);
> +unsigned long sbi_heap_free_space_from(struct sbi_heap_control *hpctrl);
> +
> +static inline unsigned long sbi_heap_free_space(void)
> +{
> +       return sbi_heap_free_space_from(&global_hpctrl);
> +}
>
>  /** Amount (in bytes) of used space in the heap area */
> -unsigned long sbi_heap_used_space(void);
> +unsigned long sbi_heap_used_space_from(struct sbi_heap_control *hpctrl);
> +
> +static inline unsigned long sbi_heap_used_space(void)
> +{
> +       return sbi_heap_used_space_from(&global_hpctrl);
> +}
>
>  /** Amount (in bytes) of reserved space in the heap area */
> -unsigned long sbi_heap_reserved_space(void);
> +unsigned long sbi_heap_reserved_space_from(struct sbi_heap_control *hpctrl);
> +
> +static inline unsigned long sbi_heap_reserved_space(void)
> +{
> +       return sbi_heap_reserved_space_from(&global_hpctrl);
> +}
>
>  /** Initialize heap area */
>  int sbi_heap_init(struct sbi_scratch *scratch);
> +int sbi_heap_init_new(struct sbi_heap_control *hpctrl, unsigned long base,
> +                      unsigned long size);
> +int sbi_heap_alloc_new(struct sbi_heap_control **hpctrl);
>
>  #endif
> diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
> index bcd404b..e43d77c 100644
> --- a/lib/sbi/sbi_heap.c
> +++ b/lib/sbi/sbi_heap.c
> @@ -24,7 +24,7 @@ struct heap_node {
>         unsigned long size;
>  };
>
> -struct heap_control {
> +struct sbi_heap_control {
>         spinlock_t lock;
>         unsigned long base;
>         unsigned long size;
> @@ -35,9 +35,9 @@ struct heap_control {
>         struct sbi_dlist used_space_list;
>  };
>
> -static struct heap_control hpctrl;
> +struct sbi_heap_control global_hpctrl;
>
> -void *sbi_malloc(size_t size)
> +void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>  {
>         void *ret = NULL;
>         struct heap_node *n, *np;
> @@ -48,10 +48,10 @@ void *sbi_malloc(size_t size)
>         size += HEAP_ALLOC_ALIGN - 1;
>         size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
>
> -       spin_lock(&hpctrl.lock);
> +       spin_lock(&hpctrl->lock);
>
>         np = NULL;
> -       sbi_list_for_each_entry(n, &hpctrl.free_space_list, head) {
> +       sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
>                 if (size <= n->size) {
>                         np = n;
>                         break;
> @@ -59,47 +59,47 @@ void *sbi_malloc(size_t size)
>         }
>         if (np) {
>                 if ((size < np->size) &&
> -                   !sbi_list_empty(&hpctrl.free_node_list)) {
> -                       n = sbi_list_first_entry(&hpctrl.free_node_list,
> +                   !sbi_list_empty(&hpctrl->free_node_list)) {
> +                       n = sbi_list_first_entry(&hpctrl->free_node_list,
>                                                  struct heap_node, head);
>                         sbi_list_del(&n->head);
>                         n->addr = np->addr + np->size - size;
>                         n->size = size;
>                         np->size -= size;
> -                       sbi_list_add_tail(&n->head, &hpctrl.used_space_list);
> +                       sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
>                         ret = (void *)n->addr;
>                 } else if (size == np->size) {
>                         sbi_list_del(&np->head);
> -                       sbi_list_add_tail(&np->head, &hpctrl.used_space_list);
> +                       sbi_list_add_tail(&np->head, &hpctrl->used_space_list);
>                         ret = (void *)np->addr;
>                 }
>         }
>
> -       spin_unlock(&hpctrl.lock);
> +       spin_unlock(&hpctrl->lock);
>
>         return ret;
>  }
>
> -void *sbi_zalloc(size_t size)
> +void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
>  {
> -       void *ret = sbi_malloc(size);
> +       void *ret = sbi_malloc_from(hpctrl, size);
>
>         if (ret)
>                 sbi_memset(ret, 0, size);
>         return ret;
>  }
>
> -void sbi_free(void *ptr)
> +void sbi_free_from(struct sbi_heap_control *hpctrl, void *ptr)
>  {
>         struct heap_node *n, *np;
>
>         if (!ptr)
>                 return;
>
> -       spin_lock(&hpctrl.lock);
> +       spin_lock(&hpctrl->lock);
>
>         np = NULL;
> -       sbi_list_for_each_entry(n, &hpctrl.used_space_list, head) {
> +       sbi_list_for_each_entry(n, &hpctrl->used_space_list, head) {
>                 if ((n->addr <= (unsigned long)ptr) &&
>                     ((unsigned long)ptr < (n->addr + n->size))) {
>                         np = n;
> @@ -107,22 +107,22 @@ void sbi_free(void *ptr)
>                 }
>         }
>         if (!np) {
> -               spin_unlock(&hpctrl.lock);
> +               spin_unlock(&hpctrl->lock);
>                 return;
>         }
>
>         sbi_list_del(&np->head);
>
> -       sbi_list_for_each_entry(n, &hpctrl.free_space_list, head) {
> +       sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
>                 if ((np->addr + np->size) == n->addr) {
>                         n->addr = np->addr;
>                         n->size += np->size;
> -                       sbi_list_add_tail(&np->head, &hpctrl.free_node_list);
> +                       sbi_list_add_tail(&np->head, &hpctrl->free_node_list);
>                         np = NULL;
>                         break;
>                 } else if (np->addr == (n->addr + n->size)) {
>                         n->size += np->size;
> -                       sbi_list_add_tail(&np->head, &hpctrl.free_node_list);
> +                       sbi_list_add_tail(&np->head, &hpctrl->free_node_list);
>                         np = NULL;
>                         break;
>                 } else if ((n->addr + n->size) < np->addr) {
> @@ -132,73 +132,87 @@ void sbi_free(void *ptr)
>                 }
>         }
>         if (np)
> -               sbi_list_add_tail(&np->head, &hpctrl.free_space_list);
> +               sbi_list_add_tail(&np->head, &hpctrl->free_space_list);
>
> -       spin_unlock(&hpctrl.lock);
> +       spin_unlock(&hpctrl->lock);
>  }
>
> -unsigned long sbi_heap_free_space(void)
> +unsigned long sbi_heap_free_space_from(struct sbi_heap_control *hpctrl)
>  {
>         struct heap_node *n;
>         unsigned long ret = 0;
>
> -       spin_lock(&hpctrl.lock);
> -       sbi_list_for_each_entry(n, &hpctrl.free_space_list, head)
> +       spin_lock(&hpctrl->lock);
> +       sbi_list_for_each_entry(n, &hpctrl->free_space_list, head)
>                 ret += n->size;
> -       spin_unlock(&hpctrl.lock);
> +       spin_unlock(&hpctrl->lock);
>
>         return ret;
>  }
>
> -unsigned long sbi_heap_used_space(void)
> +unsigned long sbi_heap_used_space_from(struct sbi_heap_control *hpctrl)
>  {
> -       return hpctrl.size - hpctrl.hksize - sbi_heap_free_space();
> +       return hpctrl->size - hpctrl->hksize - sbi_heap_free_space();
>  }
>
> -unsigned long sbi_heap_reserved_space(void)
> +unsigned long sbi_heap_reserved_space_from(struct sbi_heap_control *hpctrl)
>  {
> -       return hpctrl.hksize;
> +       return hpctrl->hksize;
>  }
>
> -int sbi_heap_init(struct sbi_scratch *scratch)
> +int sbi_heap_init_new(struct sbi_heap_control *hpctrl, unsigned long base,
> +                      unsigned long size)
>  {
>         unsigned long i;
>         struct heap_node *n;
>
> -       /* Sanity checks on heap offset and size */
> -       if (!scratch->fw_heap_size ||
> -           (scratch->fw_heap_size & (HEAP_BASE_ALIGN - 1)) ||
> -           (scratch->fw_heap_offset < scratch->fw_rw_offset) ||
> -           (scratch->fw_size < (scratch->fw_heap_offset + scratch->fw_heap_size)) ||
> -           (scratch->fw_heap_offset & (HEAP_BASE_ALIGN - 1)))
> -               return SBI_EINVAL;
> -
>         /* Initialize heap control */
> -       SPIN_LOCK_INIT(hpctrl.lock);
> -       hpctrl.base = scratch->fw_start + scratch->fw_heap_offset;
> -       hpctrl.size = scratch->fw_heap_size;
> -       hpctrl.hkbase = hpctrl.base;
> -       hpctrl.hksize = hpctrl.size / HEAP_HOUSEKEEPING_FACTOR;
> -       hpctrl.hksize &= ~((unsigned long)HEAP_BASE_ALIGN - 1);
> -       SBI_INIT_LIST_HEAD(&hpctrl.free_node_list);
> -       SBI_INIT_LIST_HEAD(&hpctrl.free_space_list);
> -       SBI_INIT_LIST_HEAD(&hpctrl.used_space_list);
> +       SPIN_LOCK_INIT(hpctrl->lock);
> +       hpctrl->base = base;
> +       hpctrl->size = size;
> +       hpctrl->hkbase = hpctrl->base;
> +       hpctrl->hksize = hpctrl->size / HEAP_HOUSEKEEPING_FACTOR;
> +       hpctrl->hksize &= ~((unsigned long)HEAP_BASE_ALIGN - 1);
> +       SBI_INIT_LIST_HEAD(&hpctrl->free_node_list);
> +       SBI_INIT_LIST_HEAD(&hpctrl->free_space_list);
> +       SBI_INIT_LIST_HEAD(&hpctrl->used_space_list);
>
>         /* Prepare free node list */
> -       for (i = 0; i < (hpctrl.hksize / sizeof(*n)); i++) {
> -               n = (struct heap_node *)(hpctrl.hkbase + (sizeof(*n) * i));
> +       for (i = 0; i < (hpctrl->hksize / sizeof(*n)); i++) {
> +               n = (struct heap_node *)(hpctrl->hkbase + (sizeof(*n) * i));
>                 SBI_INIT_LIST_HEAD(&n->head);
>                 n->addr = n->size = 0;
> -               sbi_list_add_tail(&n->head, &hpctrl.free_node_list);
> +               sbi_list_add_tail(&n->head, &hpctrl->free_node_list);
>         }
>
>         /* Prepare free space list */
> -       n = sbi_list_first_entry(&hpctrl.free_node_list,
> +       n = sbi_list_first_entry(&hpctrl->free_node_list,
>                                  struct heap_node, head);
>         sbi_list_del(&n->head);
> -       n->addr = hpctrl.hkbase + hpctrl.hksize;
> -       n->size = hpctrl.size - hpctrl.hksize;
> -       sbi_list_add_tail(&n->head, &hpctrl.free_space_list);
> +       n->addr = hpctrl->hkbase + hpctrl->hksize;
> +       n->size = hpctrl->size - hpctrl->hksize;
> +       sbi_list_add_tail(&n->head, &hpctrl->free_space_list);
> +
> +       return 0;
> +}
>
> +int sbi_heap_init(struct sbi_scratch *scratch)
> +{
> +       /* Sanity checks on heap offset and size */
> +       if (!scratch->fw_heap_size ||
> +           (scratch->fw_heap_size & (HEAP_BASE_ALIGN - 1)) ||
> +           (scratch->fw_heap_offset < scratch->fw_rw_offset) ||
> +           (scratch->fw_size < (scratch->fw_heap_offset + scratch->fw_heap_size)) ||
> +           (scratch->fw_heap_offset & (HEAP_BASE_ALIGN - 1)))
> +               return SBI_EINVAL;
> +
> +       return sbi_heap_init_new(&global_hpctrl,
> +                                 scratch->fw_start + scratch->fw_heap_offset,
> +                                 scratch->fw_heap_size);
> +}
> +
> +int sbi_heap_alloc_new(struct sbi_heap_control **hpctrl)
> +{
> +       *hpctrl = sbi_calloc(1, sizeof(struct sbi_heap_control));
>         return 0;
>  }
> --
> 2.45.2
>

[PATCH v3 3/3] lib: sbi: Implement aligned memory allocators

[Gregor Haas]

Hi Anup,

> On Aug 7, 2024, at 10:33?PM, Anup Patel <anup@brainfault.org> wrote:
> 
> On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>> 
>> This change adds a simple implementation of sbi_memalign(), for future use in
>> allocating aligned memory for SMMTT tables.
>> 
>> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
>> ---
>> include/sbi/sbi_heap.h |  9 +++++
>> lib/sbi/sbi_heap.c     | 81 ++++++++++++++++++++++++++++++++++++++----
>> 2 files changed, 84 insertions(+), 6 deletions(-)
>> 
>> diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
>> index 9a67090..2103aef 100644
>> --- a/include/sbi/sbi_heap.h
>> +++ b/include/sbi/sbi_heap.h
>> @@ -31,6 +31,15 @@ static inline void *sbi_malloc(size_t size)
>>        return sbi_malloc_from(&global_hpctrl, size);
>> }
>> 
>> +/** Allocate aligned from heap area */
>> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
>> +                       size_t size);
>> +
>> +static inline void *sbi_memalign(size_t alignment, size_t size)
>> +{
>> +       return sbi_memalign_from(&global_hpctrl, alignment, size);
>> +}
> 
> The term "memalign" does not imply it is a memory allocation function.
> 
> I suggest the following names instead:
> sbi_malloc_aligned_from()
> sbi_malloc_aligned()

I took this function prototype from POSIX?s memalign, which is a standard allocation
function. I can definitely rename this, but thought I would give my justification.

For all other comments below, agreed ? I can integrate these changes. Do you want
me to send a whole new v4 patch series (including the two earlier commits you?ve
reviewed already)? Or send a new version of just this commit?

> 
>> +
>> /** Zero allocate from heap area */
>> void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
>> 
>> diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
>> index cc4893d..ea73b54 100644
>> --- a/lib/sbi/sbi_heap.c
>> +++ b/lib/sbi/sbi_heap.c
>> @@ -37,27 +37,70 @@ struct sbi_heap_control {
>> 
>> struct sbi_heap_control global_hpctrl;
>> 
>> -void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>> +static void *alloc_with_align(struct sbi_heap_control *hpctrl,
>> +                             size_t align, size_t size)
>> {
>>        void *ret = NULL;
>> -       struct heap_node *n, *np;
>> +       struct heap_node *n, *np, *rem;
>> +       uint64_t lowest_aligned;
> 
> Since this represents the lowest aligned address, the data type
> should be "unsigned long".
> 
>> +       size_t pad;
>> 
>>        if (!size)
>>                return NULL;
>> 
>> -       size += HEAP_ALLOC_ALIGN - 1;
>> -       size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
>> +       size += align - 1;
>> +       size &= ~((unsigned long)align - 1);
>> 
>>        spin_lock(&hpctrl->lock);
>> 
>>        np = NULL;
>>        sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
>> -               if (size <= n->size) {
>> +               lowest_aligned = ROUNDUP(n->addr, align);
>> +               pad = lowest_aligned - n->addr;
>> +
>> +               if (size + pad <= n->size) {
>>                        np = n;
>>                        break;
>>                }
>>        }
>> -       if (np) {
>> +       if (!np) {
>> +               goto out;
>> +       }
> 
> No need for {} here.
> 
>> +
>> +       if (pad) {
>> +               if (sbi_list_empty(&hpctrl->free_node_list)) {
>> +                       goto out;
>> +               }
> 
> No need for {} here.
> 
>> +
>> +               n = sbi_list_first_entry(&hpctrl->free_node_list,
>> +                                        struct heap_node, head);
>> +               sbi_list_del(&n->head);
>> +
>> +               if ((size + pad < np->size) &&
>> +                   !sbi_list_empty(&hpctrl->free_node_list)) {
>> +                       rem = sbi_list_first_entry(&hpctrl->free_node_list,
>> +                                                  struct heap_node, head);
>> +                       sbi_list_del(&rem->head);
>> +                       rem->addr = np->addr + (size + pad);
>> +                       rem->size = np->size - (size + pad);
>> +                       sbi_list_add_tail(&rem->head,
>> +                                         &hpctrl->free_space_list);
>> +
>> +                       n->addr = lowest_aligned;
>> +                       n->size = size;
>> +                       np->size = pad;
>> +                       sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
>> +                       ret = (void *)n->addr;
>> +               } else if (size + pad == np->size) {
>> +                       n->addr = lowest_aligned;
>> +                       n->size = size;
>> +                       np->size = pad;
>> +                       ret = (void *)n->addr;
>> +               } else {
>> +                       // Can't allocate, return n
> 
> Use C-style comments.
> 
>> +                       sbi_list_add(&n->head, &hpctrl->free_node_list);
>> +               }
>> +       } else {
>>                if ((size < np->size) &&
>>                    !sbi_list_empty(&hpctrl->free_node_list)) {
>>                        n = sbi_list_first_entry(&hpctrl->free_node_list,
>> @@ -76,11 +119,37 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>>                }
>>        }
>> 
>> +out:
>>        spin_unlock(&hpctrl->lock);
>> 
>>        return ret;
>> }
>> 
>> +void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
>> +{
>> +       return alloc_with_align(hpctrl, HEAP_ALLOC_ALIGN, size);
>> +}
>> +
>> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
>> +                       size_t size)
>> +{
>> +       if(alignment < HEAP_ALLOC_ALIGN) {
> 
> Need a space between "if" and "(".
> 
>> +               alignment = HEAP_ALLOC_ALIGN;
>> +       }
> 
> No need for {} here.
> 
>> +
>> +       // Make sure alignment is power of two
> 
> Use C-style comments.
> 
>> +       if((alignment & (alignment - 1)) != 0) {
> 
> Need a space between "if" and "(".
> 
>> +               return NULL;
>> +       }
> 
> No need for {} here.
> 
>> +
>> +       // Make sure size is multiple of alignment
> 
> Use C-style comments.
> 
>> +       if(size % alignment != 0) {
>> +               return NULL;
>> +       }
> 
> No need for {} here.
> 
>> +
>> +       return alloc_with_align(hpctrl, alignment, size);
>> +}
>> +
>> void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
>> {
>>        void *ret = sbi_malloc_from(hpctrl, size);
>> --
>> 2.45.2
>> 
> 
> Regards,
> Anup

[PATCH v3 3/3] lib: sbi: Implement aligned memory allocators

[Jessica Clarke]

On 8 Aug 2024, at 18:47, Gregor Haas <gregorhaas1997@gmail.com> wrote:
> 
> Hi Anup,
> 
>> On Aug 7, 2024, at 10:33?PM, Anup Patel <anup@brainfault.org> wrote:
>> 
>> On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>>> 
>>> This change adds a simple implementation of sbi_memalign(), for future use in
>>> allocating aligned memory for SMMTT tables.
>>> 
>>> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
>>> ---
>>> include/sbi/sbi_heap.h |  9 +++++
>>> lib/sbi/sbi_heap.c     | 81 ++++++++++++++++++++++++++++++++++++++----
>>> 2 files changed, 84 insertions(+), 6 deletions(-)
>>> 
>>> diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
>>> index 9a67090..2103aef 100644
>>> --- a/include/sbi/sbi_heap.h
>>> +++ b/include/sbi/sbi_heap.h
>>> @@ -31,6 +31,15 @@ static inline void *sbi_malloc(size_t size)
>>>       return sbi_malloc_from(&global_hpctrl, size);
>>> }
>>> 
>>> +/** Allocate aligned from heap area */
>>> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
>>> +                       size_t size);
>>> +
>>> +static inline void *sbi_memalign(size_t alignment, size_t size)
>>> +{
>>> +       return sbi_memalign_from(&global_hpctrl, alignment, size);
>>> +}
>> 
>> The term "memalign" does not imply it is a memory allocation function.
>> 
>> I suggest the following names instead:
>> sbi_malloc_aligned_from()
>> sbi_malloc_aligned()
> 
> I took this function prototype from POSIX?s memalign, which is a standard allocation
> function. I can definitely rename this, but thought I would give my justification.
> 
> For all other comments below, agreed ? I can integrate these changes. Do you want
> me to send a whole new v4 patch series (including the two earlier commits you?ve
> reviewed already)? Or send a new version of just this commit?

I would suggest instead trying to look like ISO C11?s aligned_alloc as
a broader standard function.

Jess

[PATCH v3 3/3] lib: sbi: Implement aligned memory allocators

[Anup Patel]

On Thu, Aug 8, 2024 at 11:17?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
>
> Hi Anup,
>
> > On Aug 7, 2024, at 10:33?PM, Anup Patel <anup@brainfault.org> wrote:
> >
> > On Wed, Aug 7, 2024 at 11:47?PM Gregor Haas <gregorhaas1997@gmail.com> wrote:
> >>
> >> This change adds a simple implementation of sbi_memalign(), for future use in
> >> allocating aligned memory for SMMTT tables.
> >>
> >> Signed-off-by: Gregor Haas <gregorhaas1997@gmail.com>
> >> ---
> >> include/sbi/sbi_heap.h |  9 +++++
> >> lib/sbi/sbi_heap.c     | 81 ++++++++++++++++++++++++++++++++++++++----
> >> 2 files changed, 84 insertions(+), 6 deletions(-)
> >>
> >> diff --git a/include/sbi/sbi_heap.h b/include/sbi/sbi_heap.h
> >> index 9a67090..2103aef 100644
> >> --- a/include/sbi/sbi_heap.h
> >> +++ b/include/sbi/sbi_heap.h
> >> @@ -31,6 +31,15 @@ static inline void *sbi_malloc(size_t size)
> >>        return sbi_malloc_from(&global_hpctrl, size);
> >> }
> >>
> >> +/** Allocate aligned from heap area */
> >> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
> >> +                       size_t size);
> >> +
> >> +static inline void *sbi_memalign(size_t alignment, size_t size)
> >> +{
> >> +       return sbi_memalign_from(&global_hpctrl, alignment, size);
> >> +}
> >
> > The term "memalign" does not imply it is a memory allocation function.
> >
> > I suggest the following names instead:
> > sbi_malloc_aligned_from()
> > sbi_malloc_aligned()
>
> I took this function prototype from POSIX?s memalign, which is a standard allocation
> function. I can definitely rename this, but thought I would give my justification.

sbi_aligned_alloc() (suggested by Jessica) is also fine since it
aligns with C11.

>
> For all other comments below, agreed ? I can integrate these changes. Do you want
> me to send a whole new v4 patch series (including the two earlier commits you?ve
> reviewed already)? Or send a new version of just this commit?

General practice is to send a new version of the entire series. Also, carry
Reviewed-by tags in the commit description after your Signed-off-by in
all the patches which were reviewed so far.

>
> >
> >> +
> >> /** Zero allocate from heap area */
> >> void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size);
> >>
> >> diff --git a/lib/sbi/sbi_heap.c b/lib/sbi/sbi_heap.c
> >> index cc4893d..ea73b54 100644
> >> --- a/lib/sbi/sbi_heap.c
> >> +++ b/lib/sbi/sbi_heap.c
> >> @@ -37,27 +37,70 @@ struct sbi_heap_control {
> >>
> >> struct sbi_heap_control global_hpctrl;
> >>
> >> -void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
> >> +static void *alloc_with_align(struct sbi_heap_control *hpctrl,
> >> +                             size_t align, size_t size)
> >> {
> >>        void *ret = NULL;
> >> -       struct heap_node *n, *np;
> >> +       struct heap_node *n, *np, *rem;
> >> +       uint64_t lowest_aligned;
> >
> > Since this represents the lowest aligned address, the data type
> > should be "unsigned long".
> >
> >> +       size_t pad;
> >>
> >>        if (!size)
> >>                return NULL;
> >>
> >> -       size += HEAP_ALLOC_ALIGN - 1;
> >> -       size &= ~((unsigned long)HEAP_ALLOC_ALIGN - 1);
> >> +       size += align - 1;
> >> +       size &= ~((unsigned long)align - 1);
> >>
> >>        spin_lock(&hpctrl->lock);
> >>
> >>        np = NULL;
> >>        sbi_list_for_each_entry(n, &hpctrl->free_space_list, head) {
> >> -               if (size <= n->size) {
> >> +               lowest_aligned = ROUNDUP(n->addr, align);
> >> +               pad = lowest_aligned - n->addr;
> >> +
> >> +               if (size + pad <= n->size) {
> >>                        np = n;
> >>                        break;
> >>                }
> >>        }
> >> -       if (np) {
> >> +       if (!np) {
> >> +               goto out;
> >> +       }
> >
> > No need for {} here.
> >
> >> +
> >> +       if (pad) {
> >> +               if (sbi_list_empty(&hpctrl->free_node_list)) {
> >> +                       goto out;
> >> +               }
> >
> > No need for {} here.
> >
> >> +
> >> +               n = sbi_list_first_entry(&hpctrl->free_node_list,
> >> +                                        struct heap_node, head);
> >> +               sbi_list_del(&n->head);
> >> +
> >> +               if ((size + pad < np->size) &&
> >> +                   !sbi_list_empty(&hpctrl->free_node_list)) {
> >> +                       rem = sbi_list_first_entry(&hpctrl->free_node_list,
> >> +                                                  struct heap_node, head);
> >> +                       sbi_list_del(&rem->head);
> >> +                       rem->addr = np->addr + (size + pad);
> >> +                       rem->size = np->size - (size + pad);
> >> +                       sbi_list_add_tail(&rem->head,
> >> +                                         &hpctrl->free_space_list);
> >> +
> >> +                       n->addr = lowest_aligned;
> >> +                       n->size = size;
> >> +                       np->size = pad;
> >> +                       sbi_list_add_tail(&n->head, &hpctrl->used_space_list);
> >> +                       ret = (void *)n->addr;
> >> +               } else if (size + pad == np->size) {
> >> +                       n->addr = lowest_aligned;
> >> +                       n->size = size;
> >> +                       np->size = pad;
> >> +                       ret = (void *)n->addr;
> >> +               } else {
> >> +                       // Can't allocate, return n
> >
> > Use C-style comments.
> >
> >> +                       sbi_list_add(&n->head, &hpctrl->free_node_list);
> >> +               }
> >> +       } else {
> >>                if ((size < np->size) &&
> >>                    !sbi_list_empty(&hpctrl->free_node_list)) {
> >>                        n = sbi_list_first_entry(&hpctrl->free_node_list,
> >> @@ -76,11 +119,37 @@ void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
> >>                }
> >>        }
> >>
> >> +out:
> >>        spin_unlock(&hpctrl->lock);
> >>
> >>        return ret;
> >> }
> >>
> >> +void *sbi_malloc_from(struct sbi_heap_control *hpctrl, size_t size)
> >> +{
> >> +       return alloc_with_align(hpctrl, HEAP_ALLOC_ALIGN, size);
> >> +}
> >> +
> >> +void *sbi_memalign_from(struct sbi_heap_control *hpctrl, size_t alignment,
> >> +                       size_t size)
> >> +{
> >> +       if(alignment < HEAP_ALLOC_ALIGN) {
> >
> > Need a space between "if" and "(".
> >
> >> +               alignment = HEAP_ALLOC_ALIGN;
> >> +       }
> >
> > No need for {} here.
> >
> >> +
> >> +       // Make sure alignment is power of two
> >
> > Use C-style comments.
> >
> >> +       if((alignment & (alignment - 1)) != 0) {
> >
> > Need a space between "if" and "(".
> >
> >> +               return NULL;
> >> +       }
> >
> > No need for {} here.
> >
> >> +
> >> +       // Make sure size is multiple of alignment
> >
> > Use C-style comments.
> >
> >> +       if(size % alignment != 0) {
> >> +               return NULL;
> >> +       }
> >
> > No need for {} here.
> >
> >> +
> >> +       return alloc_with_align(hpctrl, alignment, size);
> >> +}
> >> +
> >> void *sbi_zalloc_from(struct sbi_heap_control *hpctrl, size_t size)
> >> {
> >>        void *ret = sbi_malloc_from(hpctrl, size);
> >> --
> >> 2.45.2
> >>
> >
> > Regards,
> > Anup
>
>
>
> --
> opensbi mailing list
> opensbi at lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/opensbi

Regards,
Anup