Skip to contentSkip to conversation

lib: sbi_scratch: re-implement scratch memory allocator

PATCH New Heinrich Schuchardt 3 participants 5 messages Jun 8, 2021 – Jun 25, 2021

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 lib: sbi_scratch: re-implement scratch memory allocator

Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

---
 include/sbi/sbi_scratch.h |  52 +++++++++-
 include/sbi/sbi_types.h   |   2 +
 lib/sbi/sbi_scratch.c     | 203 +++++++++++++++++++++++++++++++-------
 3 files changed, 218 insertions(+), 39 deletions(-)
include/sbi/sbi_scratch.h +48 -4
index 186a40c..f9ea434 100644
@@ -36,10 +36,10 @@
 #define SBI_SCRATCH_TMP0_OFFSET			(9 * __SIZEOF_POINTER__)
 /** Offset of options member in sbi_scratch */
 #define SBI_SCRATCH_OPTIONS_OFFSET		(10 * __SIZEOF_POINTER__)
-/** Offset of extra space in sbi_scratch */
-#define SBI_SCRATCH_EXTRA_SPACE_OFFSET		(11 * __SIZEOF_POINTER__)
 /** Maximum size of sbi_scratch (4KB) */
 #define SBI_SCRATCH_SIZE			(0x1000)
+/** Offset of field mem in the sbi_mem_alloc structure */
+#define SBI_SCRATCH_ALLOC_SIZE (offsetof(struct sbi_scratch_alloc, mem))
 
 /* clang-format on */
 
@@ -47,6 +47,49 @@
 
 #include <sbi/sbi_types.h>
 
+/**
+ * struct sbi_scratch_alloc - memory allocation
+ *
+ * This structure describes a block of allocated or free memory.
+ * The fields @prev and @next are only used for free blocks.
+ */
+struct sbi_scratch_alloc {
+	/**
+	 * @prev_size: size of previous memory block
+	 *
+	 * If the bit 0 is zero the memory is available.
+	 * If the bit 0 is non-zero the memory is allocated.
+	 */
+	unsigned int prev_size;
+	/**
+	 * @size: size of memory block
+	 *
+	 * If the bit 0 is zero the memory is available.
+	 * If the bit 0 is non-zero the memory is allocated.
+	 */
+	unsigned int size;
+
+	union {
+		/**
+		 * @mem: allocated memory
+		 *
+		 * The macro SBI_SCRATCH_ALLOC_SIZE provides the offset of @mem
+		 * in the sbi_mem_alloc structure.
+		 */
+		unsigned char mem[0];
+		struct {
+			/**
+			 * @prev: offset of preceeding block in free block list
+			 */
+			unsigned int prev;
+			/**
+			 * @next: offset of succceeding block in free block list
+			 */
+			unsigned int next;
+		};
+	};
+} __aligned(2 * sizeof(int));
+
 /** Representation of per-HART scratch space */
 struct sbi_scratch {
 	/** Start (or base) address of firmware linked to OpenSBI library */
@@ -71,6 +114,8 @@ struct sbi_scratch {
 	unsigned long tmp0;
 	/** Options for OpenSBI library */
 	unsigned long options;
+	/** Start of scratch memory allocation list */
+	struct sbi_scratch_alloc mem;
 };
 
 /** Possible options for OpenSBI library */
@@ -95,8 +140,7 @@ int sbi_scratch_init(struct sbi_scratch *scratch);
 /**
  * Allocate from extra space in sbi_scratch
  *
- * @return zero on failure and non-zero (>= SBI_SCRATCH_EXTRA_SPACE_OFFSET)
- * on success
+ * @return zero on failure and non-zero on success
  */
 unsigned long sbi_scratch_alloc_offset(unsigned long size);
 
include/sbi/sbi_types.h +2 -0
index 38e3565..2050265 100644
@@ -88,6 +88,8 @@ typedef unsigned long		physical_size_t;
 #define STR(x) XSTR(x)
 #define XSTR(x) #x
 
+#define ALIGN(x, a) ((typeof(x))((unsigned long)(x + (a - 1)) & ~(a - 1)))
+
 #define ROUNDUP(a, b) ((((a)-1) / (b) + 1) * (b))
 #define ROUNDDOWN(a, b) ((a) / (b) * (b))
 
lib/sbi/sbi_scratch.c +168 -35

241 lines not on this page · raw message

--
2.30.2

#1 lore raw

PATCH 1/1 lib: sbi_scratch: re-implement scratch memory allocator

Hi Heinrich,

Quoted 17 lines · Heinrich Schuchardt

Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

---
 include/sbi/sbi_scratch.h |  52 +++++++++-
 include/sbi/sbi_types.h   |   2 +
 lib/sbi/sbi_scratch.c     | 203 +++++++++++++++++++++++++++++++-------
 3 files changed, 218 insertions(+), 39 deletions(-)
include/sbi/sbi_scratch.h +0 -0
index 186a40c..f9ea434 100644

include/sbi/sbi_scratch.h line 42

Quoted 9 lines
include/sbi/sbi_scratch.h +2 -2
@@ -36,10 +36,10 @@
 #define SBI_SCRATCH_TMP0_OFFSET                        (9 * __SIZEOF_POINTER__)
 /** Offset of options member in sbi_scratch */
 #define SBI_SCRATCH_OPTIONS_OFFSET             (10 * __SIZEOF_POINTER__)
-/** Offset of extra space in sbi_scratch */
-#define SBI_SCRATCH_EXTRA_SPACE_OFFSET         (11 * __SIZEOF_POINTER__)
 /** Maximum size of sbi_scratch (4KB) */
 #define SBI_SCRATCH_SIZE                       (0x1000)
+/** Offset of field mem in the sbi_mem_alloc structure */
+#define SBI_SCRATCH_ALLOC_SIZE (offsetof(struct sbi_scratch_alloc, mem))

The SBI_SCRATCH_ALLOC_SIZE is not assembly friendly so should be under "#ifndef __ASSEMBLER__". Better to place it just after "struct sbi_scratch_alloc"
definition.

Quoted 39 lines
include/sbi/sbi_scratch.h +32 -0
 /* clang-format on */
 
@@ -47,6 +47,49 @@
 
 #include <sbi/sbi_types.h>
 
+/**
+ * struct sbi_scratch_alloc - memory allocation
+ *
+ * This structure describes a block of allocated or free memory.
+ * The fields @prev and @next are only used for free blocks.
+ */
+struct sbi_scratch_alloc {
+       /**
+        * @prev_size: size of previous memory block
+        *
+        * If the bit 0 is zero the memory is available.
+        * If the bit 0 is non-zero the memory is allocated.
+        */
+       unsigned int prev_size;
+       /**
+        * @size: size of memory block
+        *
+        * If the bit 0 is zero the memory is available.
+        * If the bit 0 is non-zero the memory is allocated.
+        */
+       unsigned int size;
+
+       union {
+               /**
+                * @mem: allocated memory
+                *
+                * The macro SBI_SCRATCH_ALLOC_SIZE provides the offset of @mem
+                * in the sbi_mem_alloc structure.
+                */
+               unsigned char mem[0];
+               struct {
+                       /**

include/sbi/sbi_scratch.h line 91

Quoted 10 lines
include/sbi/sbi_scratch.h +10 -0
+                        * @prev: offset of preceeding block in free block list
+                        */
+                       unsigned int prev;
+                       /**
+                        * @next: offset of succceeding block in free block list
+                        */
+                       unsigned int next;
+               };
+       };
+} __aligned(2 * sizeof(int));

I would suggest to have
#define SBI_SCRATCH_ALLOC_ALIGN (2 * sizeof(unsigned int)) and use it in above __aligned() and other places in sbi_scratch.c

Quoted 131 lines
include/sbi/sbi_scratch.h +4 -2
+
 /** Representation of per-HART scratch space */
 struct sbi_scratch {
        /** Start (or base) address of firmware linked to OpenSBI library */
@@ -71,6 +114,8 @@ struct sbi_scratch {
        unsigned long tmp0;
        /** Options for OpenSBI library */
        unsigned long options;
+       /** Start of scratch memory allocation list */
+       struct sbi_scratch_alloc mem;
 };
 
 /** Possible options for OpenSBI library */
@@ -95,8 +140,7 @@ int sbi_scratch_init(struct sbi_scratch *scratch);
 /**
  * Allocate from extra space in sbi_scratch
  *
- * @return zero on failure and non-zero (>= SBI_SCRATCH_EXTRA_SPACE_OFFSET)
- * on success
+ * @return zero on failure and non-zero on success
  */
 unsigned long sbi_scratch_alloc_offset(unsigned long size);
 
include/sbi/sbi_types.h +2 -0
index 38e3565..2050265 100644
@@ -88,6 +88,8 @@ typedef unsigned long         physical_size_t;
 #define STR(x) XSTR(x)
 #define XSTR(x) #x
 
+#define ALIGN(x, a) ((typeof(x))((unsigned long)(x + (a - 1)) & ~(a - 1)))
+
 #define ROUNDUP(a, b) ((((a)-1) / (b) + 1) * (b))
 #define ROUNDDOWN(a, b) ((a) / (b) * (b))
 
lib/sbi/sbi_scratch.c +52 -14
index 87b34c6..4c59c62 100644
@@ -18,10 +18,16 @@ u32 last_hartid_having_scratch = SBI_HARTMASK_MAX_BITS - 1;
 struct sbi_scratch *hartid_to_scratch_table[SBI_HARTMASK_MAX_BITS] = { 0 };
 
 static spinlock_t extra_lock = SPIN_LOCK_INITIALIZER;
-static unsigned long extra_offset = SBI_SCRATCH_EXTRA_SPACE_OFFSET;
+static unsigned int first_free;
 
 typedef struct sbi_scratch *(*hartid2scratch)(ulong hartid, ulong hartindex);
 
+/**
+ * sbi_scratch_init() - initialize scratch table and allocator
+ *
+ * @scratch:   pointer to table
+ * Return:     0 on success
+ */
 int sbi_scratch_init(struct sbi_scratch *scratch)
 {
        u32 i;
@@ -37,63 +43,190 @@ int sbi_scratch_init(struct sbi_scratch *scratch)
                        last_hartid_having_scratch = i;
        }
 
+       /* Initialize memory allocation block list */
+       scratch = sbi_hartid_to_scratch(last_hartid_having_scratch);
+
+       scratch->mem.prev_size = (2 * sizeof(unsigned int)) | 1U;
+       scratch->mem.size = SBI_SCRATCH_SIZE -
+                           offsetof(struct sbi_scratch, mem.mem);
+       first_free = offsetof(struct sbi_scratch, mem);
+       scratch->mem.prev = 0;
+       scratch->mem.next = 0;
+
        return 0;
 }
 
+/**
+ * sbi_scratch_alloc_offset() - allocate scratch memory
+ *
+ * @size:      requested size
+ * Return:     offset of allocated block on succcess, 0 on failure
+ */
 unsigned long sbi_scratch_alloc_offset(unsigned long size)
 {
-       u32 i;
-       void *ptr;
-       unsigned long ret = 0;
-       struct sbi_scratch *rscratch;
+       unsigned long ret;
+       unsigned int best_size = ~0U;
+       struct sbi_scratch_alloc *best = NULL;
+       struct sbi_scratch *scratch =
+               sbi_hartid_to_scratch(last_hartid_having_scratch);
+       unsigned int next;
+       struct sbi_scratch_alloc *current;
+       struct sbi_scratch_alloc *pred, *succ;
+       struct sbi_scratch_alloc *end =
+               (void *)((char *)scratch + SBI_SCRATCH_SIZE);
 
        /*
-        * We have a simple brain-dead allocator which never expects
-        * anything to be free-ed hence it keeps incrementing the
-        * next allocation offset until it runs-out of space.
-        *
-        * In future, we will have more sophisticated allocator which
-        * will allow us to re-claim free-ed space.
+        * When allocating zero bytes we still need space
+        * for the prev and next fields.
         */
-
        if (!size)
+               size = 1;
+       size = ALIGN(size, 2 * sizeof(unsigned int));
+
+       spin_lock(&extra_lock);
+
+       /* Find best fitting free block */
+       for (next = first_free; next; next = current->next) {
+               current = (void *)((char *)scratch + next);
+               if (current->size > best_size || current->size < size)
+                       continue;
+               best_size = current->size;
+               best = current;
+       }
+       if (!best) {
+               spin_unlock(&extra_lock);
                return 0;
+       }
 
-       if (size & (__SIZEOF_POINTER__ - 1))
-               size = (size & ~(__SIZEOF_POINTER__ - 1)) + __SIZEOF_POINTER__;
+       /* Update free list */

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 111

Quoted 10 lines
lib/sbi/sbi_scratch.c +10 -0
+       if (best->prev)
+               pred = (void *)((char *)scratch + best->prev);
+       else
+               pred = NULL;
+       if (best->next)
+               succ = (void *)((char *)scratch + best->next);
+       else
+               succ = NULL;
+
+       if (best->size > size + SBI_SCRATCH_ALLOC_SIZE) {

We should split a block only if we have enough residue memory for prev_size, size, prev, and next members of struct sbi_scratch_alloc.

I think this if-condition should be:
"if (best->size >= (size + 2 * SBI_SCRATCH_ALLOC_SIZE))"

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 119

Quoted 8 lines
lib/sbi/sbi_scratch.c +8 -0
+               /* Split block, use the lower part for allocation. */
+               current = (struct sbi_scratch_alloc *)&best->mem[size];
+               next = (char *)current - (char *)scratch;
+               current->size = best->size - size -
+                               SBI_SCRATCH_ALLOC_SIZE;
+               current->prev = best->prev;
+               current->next = best->next;
+               current->prev_size = size | 1U;

Please add a #define for this "1U".

Quoted 14 lines
lib/sbi/sbi_scratch.c +12 -1
+               best->size = size;
+               if (succ)
+                       succ->prev = next;
+       } else {
+               next = best->next;
+               if (succ)
+                       succ->prev = best->prev;
+               current = best;
+       }
 
-       spin_lock(&extra_lock);
+       if (pred)
+               pred->next = next;
+       else

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 138

Quoted 10 lines
lib/sbi/sbi_scratch.c +4 -4
+               first_free = next;
 
-       if (SBI_SCRATCH_SIZE < (extra_offset + size))
-               goto done;
+       /* Update memory block list */
+       succ = (struct sbi_scratch_alloc *)&current->mem[current->size];
 
-       ret = extra_offset;
-       extra_offset += size;
+       best->size |= 1U;

Same as above, need a #define for "1U" here as well.

Quoted 16 lines
lib/sbi/sbi_scratch.c +4 -10
-done:
-       spin_unlock(&extra_lock);
+       if (succ < end)
+               succ->prev_size = current->size;
 
-       if (ret) {
-               for (i = 0; i <= sbi_scratch_last_hartid(); i++) {
-                       rscratch = sbi_hartid_to_scratch(i);
-                       if (!rscratch)
-                               continue;
-                       ptr = sbi_scratch_offset_ptr(rscratch, ret);
-                       sbi_memset(ptr, 0, size);
-               }
+       ret =  best->mem - (unsigned char *)scratch;
+

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 154

Quoted 10 lines
lib/sbi/sbi_scratch.c +10 -0
+       /* Erase allocated scratch memory */
+       for (unsigned int i = 0; i <= last_hartid_having_scratch; i++) {
+               void *ptr;
+               struct sbi_scratch *rscratch;
+
+               rscratch = sbi_hartid_to_scratch(i);
+               if (!rscratch)
+                       continue;
+               ptr = sbi_scratch_offset_ptr(rscratch, ret);
+               sbi_memset(ptr, 0, size);

Any reason why we should zero-out memory with extra_lock held ??

Quoted 28 lines
lib/sbi/sbi_scratch.c +19 -2
        }
 
+       spin_unlock(&extra_lock);
+
        return ret;
 }
 
+/**
+ * sbi_scratch_free_offset() - free scratch memory
+ *
+ * @offset:    offset to memory to be freed
+ */
 void sbi_scratch_free_offset(unsigned long offset)
 {
-       if ((offset < SBI_SCRATCH_EXTRA_SPACE_OFFSET) ||
-           (SBI_SCRATCH_SIZE <= offset))
+       struct sbi_scratch *scratch =
+               sbi_hartid_to_scratch(last_hartid_having_scratch);
+       struct sbi_scratch_alloc *freed = (void *)((unsigned char *)scratch +
+                                     offset - SBI_SCRATCH_ALLOC_SIZE);
+       struct sbi_scratch_alloc *pred, *succ;
+       struct sbi_scratch_alloc *end =
+               (void *)((char *)scratch + SBI_SCRATCH_SIZE);
+
+       spin_lock(&extra_lock);
+
+       if (!offset || !(freed->size & 1U)) {
+               spin_unlock(&extra_lock);

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 186

Quoted 10 lines
lib/sbi/sbi_scratch.c +4 -4
                return;
+       }
 
-       /*
-        * We don't actually free-up because it's a simple
-        * brain-dead allocator.
-        */
+       /* Mark block as free */
+       freed->size &= ~1U;
+

Add single line comment here that we attempt to merge free block into contiguous predecessor block.

Quoted 7 lines
lib/sbi/sbi_scratch.c +7 -0
+       pred = (struct sbi_scratch_alloc *)((char *)freed -
+              (freed->prev_size & ~1U) - SBI_SCRATCH_ALLOC_SIZE);
+       if (pred >= &scratch->mem && !(pred->size & 1U)) {
+               /* Coalesce free blocks */
+               pred->size += freed->size + SBI_SCRATCH_ALLOC_SIZE;
+               freed = pred;
+       } else {

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 203

Quoted 10 lines
lib/sbi/sbi_scratch.c +10 -0
+               /* Insert at start of free list */
+               if (first_free) {
+                       succ = (void *)((char *)scratch + first_free);
+                       succ->prev = offset - SBI_SCRATCH_ALLOC_SIZE;
+               }
+               freed->next = first_free;
+               freed->prev = 0;
+               first_free = offset - SBI_SCRATCH_ALLOC_SIZE;
+       }
+

Add single line comment here that we attempt to merge contiguous successor block into free block.

Quoted 17 lines
lib/sbi/sbi_scratch.c +17 -0
+       succ = (struct sbi_scratch_alloc *)&freed->mem[freed->size & ~1U];
+       if (succ < end) {
+               if (!(succ->size & 1U)) {
+                       struct sbi_scratch_alloc *succ2;
+
+                       /* Coalesce free blocks */
+                       succ2 = (struct sbi_scratch_alloc *)
+                               &succ->mem[succ->size & ~1U];
+                       freed->size += SBI_SCRATCH_ALLOC_SIZE + succ->size;
+                       if (succ2 < end)
+                               succ2->prev_size = freed->size;
+
+                       /* Remove successor from free list */
+                       if (succ->prev) {
+                               pred = (void *)((char *)scratch + succ->prev);
+                               pred->next = succ->next;
+                       } else {

lib/sbi/sbi_scratch.c int sbi_scratch_init(struct sbi_scratch *scratch) · line 230

Quoted 10 lines
lib/sbi/sbi_scratch.c +10 -0
+                               first_free = succ->next;
+                       }
+                       if (succ->next) {
+                               succ2 = (void *)((char *)scratch + succ->next);
+                               succ2->prev = succ->prev;
+                       }
+               } else {
+                       succ->prev_size = freed->size;
+               }
+       }

Add a empty new line here.

Quoted 10 lines
lib/sbi/sbi_scratch.c +1 -1
+       spin_unlock(&extra_lock);
 }
--

2.30.2

--
opensbi mailing list
opensbi at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/opensbi

Apart from above minor comments, this patch looks good to me.

Great work !!!

Regards,
Anup

#2 lore raw

PATCH 1/1 lib: sbi_scratch: re-implement scratch memory allocator

In reply to Heinrich Schuchardt

? 2021-06-08???? 22:30 +0200?Heinrich Schuchardt???

Quoted 5 lines

Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

sbi_scratch_alloc_offset is currently only used to expand the sbi_scratch data structure, and does not need to dynamically release memory. Such modification will increase memory consumption. If you want to add alloc and free, you should add a section for heap in the link script

Regards,
Xiang W

Quoted 383 lines

---

?include/sbi/sbi_scratch.h |? 52 +++++++++-
?include/sbi/sbi_types.h?? |?? 2 +
?lib/sbi/sbi_scratch.c???? | 203 +++++++++++++++++++++++++++++++-----

--
?3 files changed, 218 insertions(+), 39 deletions(-)

include/sbi/sbi_scratch.h +0 -0
index 186a40c..f9ea434 100644
@@ -36,10 +36,10 @@

?#define SBI_SCRATCH_TMP0_OFFSET????????????????????????(9 * __SIZEOF_POINTER__)
?/** Offset of options member in sbi_scratch */ ?#define SBI_SCRATCH_OPTIONS_OFFSET?????????????(10 * __SIZEOF_POINTER__)

include/sbi/sbi_scratch.h +0 -2
-/** Offset of extra space in sbi_scratch */
-#define SBI_SCRATCH_EXTRA_SPACE_OFFSET?????????(11 *

__SIZEOF_POINTER__)
?/** Maximum size of sbi_scratch (4KB) */ ?#define SBI_SCRATCH_SIZE???????????????????????(0x1000)

include/sbi/sbi_scratch.h +2 -0
+/** Offset of field mem in the sbi_mem_alloc structure */
+#define SBI_SCRATCH_ALLOC_SIZE (offsetof(struct sbi_scratch_alloc,

mem))

?/* clang-format on */

include/sbi/sbi_scratch.h +0 -0
@@ -47,6 +47,49 @@
 

?#include <sbi/sbi_types.h>

include/sbi/sbi_scratch.h +27 -0
+/**
+ * struct sbi_scratch_alloc - memory allocation
+ *
+ * This structure describes a block of allocated or free memory.
+ * The fields @prev and @next are only used for free blocks.
+ */
+struct sbi_scratch_alloc {
+???????/**
+??????? * @prev_size: size of previous memory block
+??????? *
+??????? * If the bit 0 is zero the memory is available.
+??????? * If the bit 0 is non-zero the memory is allocated.
+??????? */
+???????unsigned int prev_size;
+???????/**
+??????? * @size: size of memory block
+??????? *
+??????? * If the bit 0 is zero the memory is available.
+??????? * If the bit 0 is non-zero the memory is allocated.
+??????? */
+???????unsigned int size;
+
+???????union {
+???????????????/**
+??????????????? * @mem: allocated memory
+??????????????? *
+??????????????? * The macro SBI_SCRATCH_ALLOC_SIZE provides the

offset of @mem
+??????????????? * in the sbi_mem_alloc structure. +??????????????? */
+???????????????unsigned char mem[0]; +???????????????struct {
+???????????????????????/**
+??????????????????????? * @prev: offset of preceeding block in free block list
+??????????????????????? */ +???????????????????????unsigned int prev; +???????????????????????/**
+??????????????????????? * @next: offset of succceeding block in free block list
+??????????????????????? */ +???????????????????????unsigned int next; +???????????????};
+???????};

include/sbi/sbi_scratch.h +2 -0
+} __aligned(2 * sizeof(int));
+

?/** Representation of per-HART scratch space */ ?struct sbi_scratch {
????????/** Start (or base) address of firmware linked to OpenSBI library */

include/sbi/sbi_scratch.h +0 -0
@@ -71,6 +114,8 @@ struct sbi_scratch {
 ????????unsigned long tmp0;

????????/** Options for OpenSBI library */ ????????unsigned long options;
+???????/** Start of scratch memory allocation list */ +???????struct sbi_scratch_alloc mem;
?};

?/** Possible options for OpenSBI library */

include/sbi/sbi_scratch.h +0 -0
@@ -95,8 +140,7 @@ int sbi_scratch_init(struct sbi_scratch *scratch);

?/**
? * Allocate from extra space in sbi_scratch
? *
- * @return zero on failure and non-zero (>= SBI_SCRATCH_EXTRA_SPACE_OFFSET)
- * on success
+ * @return zero on failure and non-zero on success ? */
?unsigned long sbi_scratch_alloc_offset(unsigned long size);

include/sbi/sbi_types.h +0 -0
index 38e3565..2050265 100644
@@ -88,6 +88,8 @@ typedef unsigned long?????????physical_size_t;
 ?#define STR(x) XSTR(x)

?#define XSTR(x) #x

include/sbi/sbi_types.h +2 -1
+#define ALIGN(x, a) ((typeof(x))((unsigned long)(x + (a - 1)) & ~(a
- 1)))
+

?#define ROUNDUP(a, b) ((((a)-1) / (b) + 1) * (b)) ?#define ROUNDDOWN(a, b) ((a) / (b) * (b))

lib/sbi/sbi_scratch.c +0 -0
index 87b34c6..4c59c62 100644
@@ -18,10 +18,16 @@ u32 last_hartid_having_scratch =
 SBI_HARTMASK_MAX_BITS - 1;

?struct sbi_scratch *hartid_to_scratch_table[SBI_HARTMASK_MAX_BITS] = { 0 };

?static spinlock_t extra_lock = SPIN_LOCK_INITIALIZER;

lib/sbi/sbi_scratch.c +1 -1
-static unsigned long extra_offset = SBI_SCRATCH_EXTRA_SPACE_OFFSET;
+static unsigned int first_free;

?typedef struct sbi_scratch *(*hartid2scratch)(ulong hartid, ulong hartindex);

+/**
+ * sbi_scratch_init() - initialize scratch table and allocator
+ *
+ * @scratch:???pointer to table
+ * Return:?????0 on success
+ */
?int sbi_scratch_init(struct sbi_scratch *scratch)
?{
????????u32 i;

lib/sbi/sbi_scratch.c +26 -4
@@ -37,63 +43,190 @@ int sbi_scratch_init(struct sbi_scratch
 *scratch)
 ????????????????????????last_hartid_having_scratch = i;
 ????????}
 
+???????/* Initialize memory allocation block list */
+???????scratch = sbi_hartid_to_scratch(last_hartid_having_scratch);
+
+???????scratch->mem.prev_size = (2 * sizeof(unsigned int)) | 1U;
+???????scratch->mem.size = SBI_SCRATCH_SIZE -
+?????????????????????????? offsetof(struct sbi_scratch, mem.mem);
+???????first_free = offsetof(struct sbi_scratch, mem);
+???????scratch->mem.prev = 0;
+???????scratch->mem.next = 0;
+
 ????????return 0;
 ?}
 
+/**
+ * sbi_scratch_alloc_offset() - allocate scratch memory
+ *
+ * @size:??????requested size
+ * Return:?????offset of allocated block on succcess, 0 on failure
+ */
 ?unsigned long sbi_scratch_alloc_offset(unsigned long size)
 ?{
-???????u32 i;
-???????void *ptr;
-???????unsigned long ret = 0;
-???????struct sbi_scratch *rscratch;
+???????unsigned long ret;
+???????unsigned int best_size = ~0U;
+???????struct sbi_scratch_alloc *best = NULL;
+???????struct sbi_scratch *scratch =
+???????????????sbi_hartid_to_scratch(last_hartid_having_scratch);
+???????unsigned int next;
+???????struct sbi_scratch_alloc *current;
+???????struct sbi_scratch_alloc *pred, *succ;
+???????struct sbi_scratch_alloc *end =
+???????????????(void *)((char *)scratch + SBI_SCRATCH_SIZE);
 

????????/*
-??????? * We have a simple brain-dead allocator which never expects -??????? * anything to be free-ed hence it keeps incrementing the -??????? * next allocation offset until it runs-out of space. -??????? *
-??????? * In future, we will have more sophisticated allocator which -??????? * will allow us to re-claim free-ed space. +??????? * When allocating zero bytes we still need space +??????? * for the prev and next fields.
???????? */
-
????????if (!size)
+???????????????size = 1;
+???????size = ALIGN(size, 2 * sizeof(unsigned int));

lib/sbi/sbi_scratch.c +7 -0
+
+???????spin_lock(&extra_lock);
+
+???????/* Find best fitting free block */
+???????for (next = first_free; next; next = current->next) {
+???????????????current = (void *)((char *)scratch + next);
+???????????????if (current->size > best_size || current->size <

size)
+???????????????????????continue;
+???????????????best_size = current->size;
+???????????????best = current;
+???????}
+???????if (!best) {
+???????????????spin_unlock(&extra_lock);
????????????????return 0;
+???????}

-???????if (size & (__SIZEOF_POINTER__ - 1)) -???????????????size = (size & ~(__SIZEOF_POINTER__ - 1)) + __SIZEOF_POINTER__;
+???????/* Update free list */
+???????if (best->prev)
+???????????????pred = (void *)((char *)scratch + best->prev); +???????else
+???????????????pred = NULL;
+???????if (best->next)
+???????????????succ = (void *)((char *)scratch + best->next); +???????else
+???????????????succ = NULL;
+
+???????if (best->size > size + SBI_SCRATCH_ALLOC_SIZE) { +???????????????/* Split block, use the lower part for allocation. */ +???????????????current = (struct sbi_scratch_alloc *)&best-

Quoted 1 line

mem[size];

+???????????????next = (char *)current - (char *)scratch; +???????????????current->size = best->size - size - +???????????????????????????????SBI_SCRATCH_ALLOC_SIZE; +???????????????current->prev = best->prev; +???????????????current->next = best->next; +???????????????current->prev_size = size | 1U; +???????????????best->size = size; +???????????????if (succ) +???????????????????????succ->prev = next; +???????} else {
+???????????????next = best->next; +???????????????if (succ) +???????????????????????succ->prev = best->prev; +???????????????current = best;
+???????}

-???????spin_lock(&extra_lock);
+???????if (pred)
+???????????????pred->next = next;
+???????else
+???????????????first_free = next;

-???????if (SBI_SCRATCH_SIZE < (extra_offset + size)) -???????????????goto done;
+???????/* Update memory block list */
+???????succ = (struct sbi_scratch_alloc *)&current->mem[current-

Quoted 1 line

size];

-???????ret = extra_offset;
-???????extra_offset += size;
+???????best->size |= 1U;

lib/sbi/sbi_scratch.c +6 -10
-done:
-???????spin_unlock(&extra_lock);
+???????if (succ < end)
+???????????????succ->prev_size = current->size;
 
-???????if (ret) {
-???????????????for (i = 0; i <= sbi_scratch_last_hartid(); i++) {
-???????????????????????rscratch = sbi_hartid_to_scratch(i);
-???????????????????????if (!rscratch)
-???????????????????????????????continue;
-???????????????????????ptr = sbi_scratch_offset_ptr(rscratch, ret);
-???????????????????????sbi_memset(ptr, 0, size);
-???????????????}
+???????ret =? best->mem - (unsigned char *)scratch;
+
+???????/* Erase allocated scratch memory */
+???????for (unsigned int i = 0; i <= last_hartid_having_scratch;

i++) {
+???????????????void *ptr;
+???????????????struct sbi_scratch *rscratch;
+
+???????????????rscratch = sbi_hartid_to_scratch(i); +???????????????if (!rscratch) +???????????????????????continue; +???????????????ptr = sbi_scratch_offset_ptr(rscratch, ret); +???????????????sbi_memset(ptr, 0, size); ????????}

+???????spin_unlock(&extra_lock);
+
????????return ret;
?}

+/**
+ * sbi_scratch_free_offset() - free scratch memory
+ *
+ * @offset:????offset to memory to be freed
+ */
?void sbi_scratch_free_offset(unsigned long offset)
?{
-???????if ((offset < SBI_SCRATCH_EXTRA_SPACE_OFFSET) || -?????????? (SBI_SCRATCH_SIZE <= offset)) +???????struct sbi_scratch *scratch = +???????????????sbi_hartid_to_scratch(last_hartid_having_scratch); +???????struct sbi_scratch_alloc *freed = (void *)((unsigned char *)scratch +
+???????????????????????????????????? offset - SBI_SCRATCH_ALLOC_SIZE);
+???????struct sbi_scratch_alloc *pred, *succ; +???????struct sbi_scratch_alloc *end = +???????????????(void *)((char *)scratch + SBI_SCRATCH_SIZE);

lib/sbi/sbi_scratch.c +5 -0
+
+???????spin_lock(&extra_lock);
+
+???????if (!offset || !(freed->size & 1U)) {
+???????????????spin_unlock(&extra_lock);

????????????????return;
+???????}

-???????/*
-??????? * We don't actually free-up because it's a simple -??????? * brain-dead allocator.
-??????? */
+???????/* Mark block as free */
+???????freed->size &= ~1U;
+
+???????pred = (struct sbi_scratch_alloc *)((char *)freed - +????????????? (freed->prev_size & ~1U) - SBI_SCRATCH_ALLOC_SIZE); +???????if (pred >= &scratch->mem && !(pred->size & 1U)) { +???????????????/* Coalesce free blocks */ +???????????????pred->size += freed->size + SBI_SCRATCH_ALLOC_SIZE; +???????????????freed = pred;
+???????} else {
+???????????????/* Insert at start of free list */ +???????????????if (first_free) { +???????????????????????succ = (void *)((char *)scratch + first_free);
+???????????????????????succ->prev = offset - SBI_SCRATCH_ALLOC_SIZE; +???????????????}
+???????????????freed->next = first_free; +???????????????freed->prev = 0; +???????????????first_free = offset - SBI_SCRATCH_ALLOC_SIZE; +???????}
+
+???????succ = (struct sbi_scratch_alloc *)&freed->mem[freed->size & ~1U];
+???????if (succ < end) {
+???????????????if (!(succ->size & 1U)) { +???????????????????????struct sbi_scratch_alloc *succ2;
+
+???????????????????????/* Coalesce free blocks */ +???????????????????????succ2 = (struct sbi_scratch_alloc *) +???????????????????????????????&succ->mem[succ->size & ~1U]; +???????????????????????freed->size += SBI_SCRATCH_ALLOC_SIZE + succ-

Quoted 1 line

size;

+???????????????????????if (succ2 < end) +???????????????????????????????succ2->prev_size = freed->size; +
+???????????????????????/* Remove successor from free list */ +???????????????????????if (succ->prev) { +???????????????????????????????pred = (void *)((char *)scratch + succ->prev);
+???????????????????????????????pred->next = succ->next; +???????????????????????} else { +???????????????????????????????first_free = succ->next; +???????????????????????}
+???????????????????????if (succ->next) { +???????????????????????????????succ2 = (void *)((char *)scratch + succ->next); +???????????????????????????????succ2->prev = succ->prev; +???????????????????????}
+???????????????} else { +???????????????????????succ->prev_size = freed->size; +???????????????}
+???????}
+???????spin_unlock(&extra_lock);
?}
--
2.30.2

#3 lore raw

PATCH 1/1 lib: sbi_scratch: re-implement scratch memory allocator

Quoted 6 lines · Xiang W

? 2021-06-08???? 22:30 +0200?Heinrich Schuchardt???

Quoted 4 lines

Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

Quoted 7 lines
Quoted 1 line

sbi_scratch_alloc_offset is currently only used to expand the sbi_scratch data structure, and does not need to dynamically release memory. Such modification will increase memory consumption. If you want to add alloc and free, you should add a section for heap in the link script

The sbi_scratch space is per-HART (or per-CPU) space and is very different from a global heap space. The sbi_scratch will usually be a small resource but we still need to manage it hence this patch.

Having a global heap space in OpenSBI is a separate topic and till now we have avoided adding a heap space to keep the runtime memory usage low. Let's see how long we can continue without a global heap space.

Regards,
Anup

Quoted 393 lines

Regards,
Xiang W

Quoted 380 lines
---
 include/sbi/sbi_scratch.h |  52 +++++++++-
 include/sbi/sbi_types.h   |   2 +
 lib/sbi/sbi_scratch.c     | 203 +++++++++++++++++++++++++++++++-----
--
 3 files changed, 218 insertions(+), 39 deletions(-)
include/sbi/sbi_scratch.h +2 -2
index 186a40c..f9ea434 100644
@@ -36,10 +36,10 @@
 #define SBI_SCRATCH_TMP0_OFFSET                        (9 *
 __SIZEOF_POINTER__)
 /** Offset of options member in sbi_scratch */
 #define SBI_SCRATCH_OPTIONS_OFFSET             (10 *
 __SIZEOF_POINTER__)
-/** Offset of extra space in sbi_scratch */
-#define SBI_SCRATCH_EXTRA_SPACE_OFFSET         (11 *
 __SIZEOF_POINTER__)
 /** Maximum size of sbi_scratch (4KB) */
 #define SBI_SCRATCH_SIZE                       (0x1000)
+/** Offset of field mem in the sbi_mem_alloc structure */
+#define SBI_SCRATCH_ALLOC_SIZE (offsetof(struct sbi_scratch_alloc,

mem))

/* clang-format on */

include/sbi/sbi_scratch.h +27 -0
@@ -47,6 +47,49 @@
 
 #include <sbi/sbi_types.h>
 
+/**
+ * struct sbi_scratch_alloc - memory allocation
+ *
+ * This structure describes a block of allocated or free memory.
+ * The fields @prev and @next are only used for free blocks.
+ */
+struct sbi_scratch_alloc {
+       /**
+        * @prev_size: size of previous memory block
+        *
+        * If the bit 0 is zero the memory is available.
+        * If the bit 0 is non-zero the memory is allocated.
+        */
+       unsigned int prev_size;
+       /**
+        * @size: size of memory block
+        *
+        * If the bit 0 is zero the memory is available.
+        * If the bit 0 is non-zero the memory is allocated.
+        */
+       unsigned int size;
+
+       union {
+               /**
+                * @mem: allocated memory
+                *
+                * The macro SBI_SCRATCH_ALLOC_SIZE provides the

offset of @mem

include/sbi/sbi_scratch.h +6 -0
+                * in the sbi_mem_alloc structure.
+                */
+               unsigned char mem[0];
+               struct {
+                       /**
+                        * @prev: offset of preceeding block in free

block list

include/sbi/sbi_scratch.h +4 -0
+                        */
+                       unsigned int prev;
+                       /**
+                        * @next: offset of succceeding block in free

block list

include/sbi/sbi_scratch.h +6 -0
+                        */
+                       unsigned int next;
+               };
+       };
+} __aligned(2 * sizeof(int));
+
 /** Representation of per-HART scratch space */
 struct sbi_scratch {
        /** Start (or base) address of firmware linked to OpenSBI

library */

include/sbi/sbi_scratch.h +3 -2
@@ -71,6 +114,8 @@ struct sbi_scratch {
        unsigned long tmp0;
        /** Options for OpenSBI library */
        unsigned long options;
+       /** Start of scratch memory allocation list */
+       struct sbi_scratch_alloc mem;
 };
 
 /** Possible options for OpenSBI library */
@@ -95,8 +140,7 @@ int sbi_scratch_init(struct sbi_scratch *scratch);
 /**
  * Allocate from extra space in sbi_scratch
  *
- * @return zero on failure and non-zero (>=
 SBI_SCRATCH_EXTRA_SPACE_OFFSET)
- * on success
+ * @return zero on failure and non-zero on success
  */
 unsigned long sbi_scratch_alloc_offset(unsigned long size);
include/sbi/sbi_types.h +2 -1
index 38e3565..2050265 100644
@@ -88,6 +88,8 @@ typedef unsigned long         physical_size_t;
 #define STR(x) XSTR(x)
 #define XSTR(x) #x
 
+#define ALIGN(x, a) ((typeof(x))((unsigned long)(x + (a - 1)) & ~(a
- 1)))
+
 #define ROUNDUP(a, b) ((((a)-1) / (b) + 1) * (b))
 #define ROUNDDOWN(a, b) ((a) / (b) * (b))
lib/sbi/sbi_scratch.c +7 -1
index 87b34c6..4c59c62 100644
@@ -18,10 +18,16 @@ u32 last_hartid_having_scratch =
 SBI_HARTMASK_MAX_BITS - 1;
 struct sbi_scratch *hartid_to_scratch_table[SBI_HARTMASK_MAX_BITS] =
 { 0 };
 
 static spinlock_t extra_lock = SPIN_LOCK_INITIALIZER;
-static unsigned long extra_offset = SBI_SCRATCH_EXTRA_SPACE_OFFSET;
+static unsigned int first_free;
 
 typedef struct sbi_scratch *(*hartid2scratch)(ulong hartid, ulong
 hartindex);
 
+/**
+ * sbi_scratch_init() - initialize scratch table and allocator
+ *
+ * @scratch:   pointer to table
+ * Return:     0 on success
+ */

int sbi_scratch_init(struct sbi_scratch *scratch)

 {
        u32 i;
lib/sbi/sbi_scratch.c +104 -30
@@ -37,63 +43,190 @@ int sbi_scratch_init(struct sbi_scratch
 *scratch)
                        last_hartid_having_scratch = i;
        }
 
+       /* Initialize memory allocation block list */
+       scratch = sbi_hartid_to_scratch(last_hartid_having_scratch);
+
+       scratch->mem.prev_size = (2 * sizeof(unsigned int)) | 1U;
+       scratch->mem.size = SBI_SCRATCH_SIZE -
+                           offsetof(struct sbi_scratch, mem.mem);
+       first_free = offsetof(struct sbi_scratch, mem);
+       scratch->mem.prev = 0;
+       scratch->mem.next = 0;
+
        return 0;
 }
 
+/**
+ * sbi_scratch_alloc_offset() - allocate scratch memory
+ *
+ * @size:      requested size
+ * Return:     offset of allocated block on succcess, 0 on failure
+ */
 unsigned long sbi_scratch_alloc_offset(unsigned long size)
 {
-       u32 i;
-       void *ptr;
-       unsigned long ret = 0;
-       struct sbi_scratch *rscratch;
+       unsigned long ret;
+       unsigned int best_size = ~0U;
+       struct sbi_scratch_alloc *best = NULL;
+       struct sbi_scratch *scratch =
+               sbi_hartid_to_scratch(last_hartid_having_scratch);
+       unsigned int next;
+       struct sbi_scratch_alloc *current;
+       struct sbi_scratch_alloc *pred, *succ;
+       struct sbi_scratch_alloc *end =
+               (void *)((char *)scratch + SBI_SCRATCH_SIZE);
 
        /*
-        * We have a simple brain-dead allocator which never expects
-        * anything to be free-ed hence it keeps incrementing the
-        * next allocation offset until it runs-out of space.
-        *
-        * In future, we will have more sophisticated allocator which
-        * will allow us to re-claim free-ed space.
+        * When allocating zero bytes we still need space
+        * for the prev and next fields.
         */
-
        if (!size)
+               size = 1;
+       size = ALIGN(size, 2 * sizeof(unsigned int));
+
+       spin_lock(&extra_lock);
+
+       /* Find best fitting free block */
+       for (next = first_free; next; next = current->next) {
+               current = (void *)((char *)scratch + next);
+               if (current->size > best_size || current->size <
 size)
+                       continue;
+               best_size = current->size;
+               best = current;
+       }
+       if (!best) {
+               spin_unlock(&extra_lock);
                return 0;
+       }
 
-       if (size & (__SIZEOF_POINTER__ - 1))
-               size = (size & ~(__SIZEOF_POINTER__ - 1)) +
 __SIZEOF_POINTER__;
+       /* Update free list */
+       if (best->prev)
+               pred = (void *)((char *)scratch + best->prev);
+       else
+               pred = NULL;
+       if (best->next)
+               succ = (void *)((char *)scratch + best->next);
+       else
+               succ = NULL;
+
+       if (best->size > size + SBI_SCRATCH_ALLOC_SIZE) {
+               /* Split block, use the lower part for allocation. */
+               current = (struct sbi_scratch_alloc *)&best-
 >mem[size];
+               next = (char *)current - (char *)scratch;
+               current->size = best->size - size -
+                               SBI_SCRATCH_ALLOC_SIZE;
+               current->prev = best->prev;
+               current->next = best->next;
+               current->prev_size = size | 1U;
+               best->size = size;
+               if (succ)
+                       succ->prev = next;
+       } else {
+               next = best->next;
+               if (succ)
+                       succ->prev = best->prev;
+               current = best;
+       }
 
-       spin_lock(&extra_lock);
+       if (pred)
+               pred->next = next;
+       else
+               first_free = next;
 
-       if (SBI_SCRATCH_SIZE < (extra_offset + size))
-               goto done;
+       /* Update memory block list */
+       succ = (struct sbi_scratch_alloc *)&current->mem[current-
 >size];
 
-       ret = extra_offset;
-       extra_offset += size;
+       best->size |= 1U;
 
-done:
-       spin_unlock(&extra_lock);
+       if (succ < end)
+               succ->prev_size = current->size;
 
-       if (ret) {
-               for (i = 0; i <= sbi_scratch_last_hartid(); i++) {
-                       rscratch = sbi_hartid_to_scratch(i);
-                       if (!rscratch)
-                               continue;
-                       ptr = sbi_scratch_offset_ptr(rscratch, ret);
-                       sbi_memset(ptr, 0, size);
-               }
+       ret =  best->mem - (unsigned char *)scratch;
+
+       /* Erase allocated scratch memory */
+       for (unsigned int i = 0; i <= last_hartid_having_scratch;
 i++) {
+               void *ptr;
+               struct sbi_scratch *rscratch;
+
+               rscratch = sbi_hartid_to_scratch(i);
+               if (!rscratch)
+                       continue;
+               ptr = sbi_scratch_offset_ptr(rscratch, ret);
+               sbi_memset(ptr, 0, size);
        }
 
+       spin_unlock(&extra_lock);
+
        return ret;
 }
 
+/**
+ * sbi_scratch_free_offset() - free scratch memory
+ *
+ * @offset:    offset to memory to be freed
+ */
 void sbi_scratch_free_offset(unsigned long offset)
 {
-       if ((offset < SBI_SCRATCH_EXTRA_SPACE_OFFSET) ||
-           (SBI_SCRATCH_SIZE <= offset))
+       struct sbi_scratch *scratch =
+               sbi_hartid_to_scratch(last_hartid_having_scratch);
+       struct sbi_scratch_alloc *freed = (void *)((unsigned char
 *)scratch +
+                                     offset -

SBI_SCRATCH_ALLOC_SIZE);

lib/sbi/sbi_scratch.c +22 -4
+       struct sbi_scratch_alloc *pred, *succ;
+       struct sbi_scratch_alloc *end =
+               (void *)((char *)scratch + SBI_SCRATCH_SIZE);
+
+       spin_lock(&extra_lock);
+
+       if (!offset || !(freed->size & 1U)) {
+               spin_unlock(&extra_lock);
                return;
+       }
 
-       /*
-        * We don't actually free-up because it's a simple
-        * brain-dead allocator.
-        */
+       /* Mark block as free */
+       freed->size &= ~1U;
+
+       pred = (struct sbi_scratch_alloc *)((char *)freed -
+              (freed->prev_size & ~1U) - SBI_SCRATCH_ALLOC_SIZE);
+       if (pred >= &scratch->mem && !(pred->size & 1U)) {
+               /* Coalesce free blocks */
+               pred->size += freed->size + SBI_SCRATCH_ALLOC_SIZE;
+               freed = pred;
+       } else {
+               /* Insert at start of free list */
+               if (first_free) {
+                       succ = (void *)((char *)scratch +

first_free);

lib/sbi/sbi_scratch.c +8 -0
+                       succ->prev = offset - SBI_SCRATCH_ALLOC_SIZE;
+               }
+               freed->next = first_free;
+               freed->prev = 0;
+               first_free = offset - SBI_SCRATCH_ALLOC_SIZE;
+       }
+
+       succ = (struct sbi_scratch_alloc *)&freed->mem[freed->size &

~1U];

lib/sbi/sbi_scratch.c +8 -0
+       if (succ < end) {
+               if (!(succ->size & 1U)) {
+                       struct sbi_scratch_alloc *succ2;
+
+                       /* Coalesce free blocks */
+                       succ2 = (struct sbi_scratch_alloc *)
+                               &succ->mem[succ->size & ~1U];
+                       freed->size += SBI_SCRATCH_ALLOC_SIZE + succ-
Quoted 1 line

size;

lib/sbi/sbi_scratch.c +6 -0
+                       if (succ2 < end)
+                               succ2->prev_size = freed->size;
+
+                       /* Remove successor from free list */
+                       if (succ->prev) {
+                               pred = (void *)((char *)scratch +

succ->prev);

lib/sbi/sbi_scratch.c +6 -0
+                               pred->next = succ->next;
+                       } else {
+                               first_free = succ->next;
+                       }
+                       if (succ->next) {
+                               succ2 = (void *)((char *)scratch +

succ->next);

lib/sbi/sbi_scratch.c +7 -1
+                               succ2->prev = succ->prev;
+                       }
+               } else {
+                       succ->prev_size = freed->size;
+               }
+       }
+       spin_unlock(&extra_lock);
 }
--
Quoted 3 lines

2.30.2

--
opensbi mailing list
opensbi at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/opensbi

#4 lore raw

PATCH 1/1 lib: sbi_scratch: re-implement scratch memory allocator

Quoted 19 lines · Anup Patel
Quoted 6 lines · Xiang W

? 2021-06-08???? 22:30 +0200?Heinrich Schuchardt???

Quoted 4 lines

Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

Quoted 7 lines
Quoted 1 line

sbi_scratch_alloc_offset is currently only used to expand the sbi_scratch data structure, and does not need to dynamically release memory. Such modification will increase memory consumption. If you want to add alloc and free, you should add a section for heap in the link script

The sbi_scratch space is per-HART (or per-CPU) space and is very different from a global heap space. The sbi_scratch will usually be a small resource but we still need to manage it hence this patch.

Quoted 7 lines

Having a global heap space in OpenSBI is a separate topic and till now we have avoided adding a heap space to keep the runtime memory usage low. Let's see how long we can continue without a global heap space.

Regards,
Anup

The most problematic thing about sbi_scratch_free_offset() is synchronization of the harts. It is necessary that all harts stop using a memory area before it is released by sbi_scratch_free_offset().

Currently sbi_tlb_init() is the only caller of sbi_scratch_free_offset(). sbi_scratch_free_offset() is only used to free memory that was allocated in the same call to sbi_tlb_init(). So here synchronization is not problematic.

Best regards

Heinrich