diff mbox series

[1/1] lib: sbi_scratch: re-implement scratch memory allocator

Message ID 20210608203046.105890-1-xypron.glpk@gmx.de
State New
Headers show
Series [1/1] lib: sbi_scratch: re-implement scratch memory allocator | expand

Commit Message

Heinrich Schuchardt June 8, 2021, 8:30 p.m. UTC
Up to now we could allocated scratch memory but not deallocate it.

Provide a best fit memory allocator.

Signed-off-by: Heinrich Schuchardt <xypron.glpk@gmx.de>
---
 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(-)

--
2.30.2

Comments

Anup Patel June 22, 2021, 12:01 p.m. UTC | #1
Hi Heinrich,

On Wed, Jun 9, 2021 at 2:01 AM Heinrich Schuchardt <xypron.glpk@gmx.de> wrote:
>
> Up to now we could allocated scratch memory but not deallocate it.
>
> Provide a best fit memory allocator.
>
> Signed-off-by: Heinrich Schuchardt <xypron.glpk@gmx.de>
> ---
>  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(-)
>
> diff --git a/include/sbi/sbi_scratch.h b/include/sbi/sbi_scratch.h
> index 186a40c..f9ea434 100644
> --- a/include/sbi/sbi_scratch.h
> +++ b/include/sbi/sbi_scratch.h
> @@ -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.

>
>  /* 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));

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

> +
>  /** 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);
>
> diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h
> index 38e3565..2050265 100644
> --- a/include/sbi/sbi_types.h
> +++ b/include/sbi/sbi_types.h
> @@ -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))
>
> diff --git a/lib/sbi/sbi_scratch.c b/lib/sbi/sbi_scratch.c
> index 87b34c6..4c59c62 100644
> --- a/lib/sbi/sbi_scratch.c
> +++ b/lib/sbi/sbi_scratch.c
> @@ -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 */
> +       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))"

> +               /* 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".

> +               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;

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

>
> -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);

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

>         }
>
> +       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);
>                 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.

> +       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;
> +       }
> +

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

> +       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 {
> +                               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.

> +       spin_unlock(&extra_lock);
>  }
> --
> 2.30.2
>
>
> --
> opensbi mailing list
> opensbi@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
Xiang W June 23, 2021, 4:32 a.m. UTC | #2
在 2021-06-08星期二的 22:30 +0200,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 <xypron.glpk@gmx.de>

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
> ---
>  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(-)
> 
> diff --git a/include/sbi/sbi_scratch.h b/include/sbi/sbi_scratch.h
> index 186a40c..f9ea434 100644
> --- a/include/sbi/sbi_scratch.h
> +++ b/include/sbi/sbi_scratch.h
> @@ -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);
> 
> diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h
> index 38e3565..2050265 100644
> --- a/include/sbi/sbi_types.h
> +++ b/include/sbi/sbi_types.h
> @@ -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))
> 
> diff --git a/lib/sbi/sbi_scratch.c b/lib/sbi/sbi_scratch.c
> index 87b34c6..4c59c62 100644
> --- a/lib/sbi/sbi_scratch.c
> +++ b/lib/sbi/sbi_scratch.c
> @@ -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 */
> +       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);
> +       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);
> +                       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-
> >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
> 
>
Anup Patel June 23, 2021, 4:43 a.m. UTC | #3
On Wed, Jun 23, 2021 at 10:02 AM Xiang W <wxjstz@126.com> wrote:
>
> 在 2021-06-08星期二的 22:30 +0200,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 <xypron.glpk@gmx.de>
>
> 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

>
> Regards,
> Xiang W
> > ---
> >  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(-)
> >
> > diff --git a/include/sbi/sbi_scratch.h b/include/sbi/sbi_scratch.h
> > index 186a40c..f9ea434 100644
> > --- a/include/sbi/sbi_scratch.h
> > +++ b/include/sbi/sbi_scratch.h
> > @@ -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);
> >
> > diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h
> > index 38e3565..2050265 100644
> > --- a/include/sbi/sbi_types.h
> > +++ b/include/sbi/sbi_types.h
> > @@ -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))
> >
> > diff --git a/lib/sbi/sbi_scratch.c b/lib/sbi/sbi_scratch.c
> > index 87b34c6..4c59c62 100644
> > --- a/lib/sbi/sbi_scratch.c
> > +++ b/lib/sbi/sbi_scratch.c
> > @@ -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 */
> > +       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);
> > +       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);
> > +                       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-
> > >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
> >
> >
>
>
>
> --
> opensbi mailing list
> opensbi@lists.infradead.org
> http://lists.infradead.org/mailman/listinfo/opensbi
diff mbox series

Patch

diff --git a/include/sbi/sbi_scratch.h b/include/sbi/sbi_scratch.h
index 186a40c..f9ea434 100644
--- a/include/sbi/sbi_scratch.h
+++ b/include/sbi/sbi_scratch.h
@@ -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);

diff --git a/include/sbi/sbi_types.h b/include/sbi/sbi_types.h
index 38e3565..2050265 100644
--- a/include/sbi/sbi_types.h
+++ b/include/sbi/sbi_types.h
@@ -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))

diff --git a/lib/sbi/sbi_scratch.c b/lib/sbi/sbi_scratch.c
index 87b34c6..4c59c62 100644
--- a/lib/sbi/sbi_scratch.c
+++ b/lib/sbi/sbi_scratch.c
@@ -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 */
+	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);
+	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);
+			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->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);
 }