lib: sbi_scratch: re-implement scratch memory allocator
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
@@ -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
@@ -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
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.
Signed-off-by Heinrich Schuchardt <[email protected]>--- 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
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@@ -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@@ -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 *)¤t->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
-4return ; + } -/* -* 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
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.
Signed-off-by Heinrich Schuchardt <[email protected]>
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@@ -36,10 +36,10 @@?#define SBI_SCRATCH_TMP0_OFFSET????????????????????????(9 *
__SIZEOF_POINTER__)
?/** Offset of options member insbi_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 ofsbi_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 theoffset of @mem
+??????????????? * in thesbi_mem_allocstructure. +??????????????? */
+???????????????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 */ +???????structsbi_scratch_allocmem;
?};?/** 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 insbi_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 longsbi_scratch_alloc_offset(unsigned long size);include/sbi/sbi_types.h +0
-0@@ -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)) ?#defineROUNDDOWN(a, b)((a) / (b) * (b))lib/sbi/sbi_scratch.c +0
-0@@ -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_textra_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
+ */
?intsbi_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 = (structsbi_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 = (structsbi_scratch_alloc*)¤t->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;
+???????????????structsbi_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
+ */
?voidsbi_scratch_free_offset(unsigned long offset)
?{
-???????if ((offset <SBI_SCRATCH_EXTRA_SPACE_OFFSET) || -?????????? (SBI_SCRATCH_SIZE<= offset)) +???????structsbi_scratch*scratch = +???????????????sbi_hartid_to_scratch(last_hartid_having_scratch); +???????structsbi_scratch_alloc*freed = (void *)((unsigned char *)scratch +
+???????????????????????????????????? offset -SBI_SCRATCH_ALLOC_SIZE);
+???????structsbi_scratch_alloc*pred, *succ; +???????structsbi_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 = (structsbi_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 = (structsbi_scratch_alloc*)&freed->mem[freed->size & ~1U];
+???????if (succ < end) {
+???????????????if (!(succ->size & 1U)) { +???????????????????????structsbi_scratch_alloc*succ2;
+
+???????????????????????/* Coalesce free blocks */ +???????????????????????succ2 = (structsbi_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
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
Signed-off-by Heinrich Schuchardt <[email protected]>
sbi_scratch_alloc_offsetis currently only used to expand thesbi_scratchdata 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 WQuoted 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@@ -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@@ -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@@ -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 *)¤t->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
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
Signed-off-by Heinrich Schuchardt <[email protected]>
sbi_scratch_alloc_offsetis currently only used to expand thesbi_scratchdata 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 scriptThe
sbi_scratchspace is per-HART (or per-CPU) space and is very different from a global heap space. Thesbi_scratchwill 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