On Tue, May 8, 2018 at 10:58 AM, Jordan Justen <jordan.l.jus...@intel.com>
wrote:

> On 2018-05-07 17:30:43, Scott D Phillips wrote:
> > From: Jason Ekstrand <jason.ekstr...@intel.com>
> >
> > This is simple linear-walk first-fit allocator roughly based on the
> > allocator in the radeon winsys code.  This allocator has two primary
> > functional differences:
> >
> >  1) It cleanly returns 0 on allocation failure
> >
> >  2) It allocates addresses top-down instead of bottom-up.
> >
> > The second one is needed for Intel because high addresses (with bit 47
> > set) need to be canonicalized in order to work properly.  If we allocate
> > bottom-up, then high addresses will be very rare (if they ever happen).
> > We'd rather always have high addresses so that the canonicalization code
> > gets better testing.
> >
> > Reviewed-by: Scott D Phillips <scott.d.phill...@intel.com>
> > Tested-by: Scott D Phillips <scott.d.phill...@intel.com>
> > ---
> >  src/util/Makefile.sources |   4 +-
> >  src/util/meson.build      |   2 +
> >  src/util/vma.c            | 231 ++++++++++++++++++++++++++++++
> ++++++++++++++++
> >  src/util/vma.h            |  53 +++++++++++
> >  4 files changed, 289 insertions(+), 1 deletion(-)
> >  create mode 100644 src/util/vma.c
> >  create mode 100644 src/util/vma.h
> >
> > diff --git a/src/util/Makefile.sources b/src/util/Makefile.sources
> > index 104ecae8ed3..534520ce763 100644
> > --- a/src/util/Makefile.sources
> > +++ b/src/util/Makefile.sources
> > @@ -56,7 +56,9 @@ MESA_UTIL_FILES := \
> >         u_string.h \
> >         u_thread.h \
> >         u_vector.c \
> > -       u_vector.h
> > +       u_vector.h \
> > +       vma.c \
> > +       vma.h
> >
> >  MESA_UTIL_GENERATED_FILES = \
> >         format_srgb.c
> > diff --git a/src/util/meson.build b/src/util/meson.build
> > index eece1cefef6..14660e0fa0c 100644
> > --- a/src/util/meson.build
> > +++ b/src/util/meson.build
> > @@ -81,6 +81,8 @@ files_mesa_util = files(
> >    'u_thread.h',
> >    'u_vector.c',
> >    'u_vector.h',
> > +  'vma.c',
> > +  'vma.h',
> >  )
> >
> >  install_data('drirc', install_dir : get_option('sysconfdir'))
> > diff --git a/src/util/vma.c b/src/util/vma.c
> > new file mode 100644
> > index 00000000000..0d4e097e21f
> > --- /dev/null
> > +++ b/src/util/vma.c
> > @@ -0,0 +1,231 @@
> > +/*
> > + * Copyright © 2018 Intel Corporation
> > + *
> > + * Permission is hereby granted, free of charge, to any person
> obtaining a
> > + * copy of this software and associated documentation files (the
> "Software"),
> > + * to deal in the Software without restriction, including without
> limitation
> > + * the rights to use, copy, modify, merge, publish, distribute,
> sublicense,
> > + * and/or sell copies of the Software, and to permit persons to whom the
> > + * Software is furnished to do so, subject to the following conditions:
> > + *
> > + * The above copyright notice and this permission notice (including the
> next
> > + * paragraph) shall be included in all copies or substantial portions
> of the
> > + * Software.
> > + *
> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> EXPRESS OR
> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT
> SHALL
> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> OTHER
> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
> ARISING
> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> DEALINGS
> > + * IN THE SOFTWARE.
> > + */
> > +
> > +#include <stdlib.h>
> > +
> > +#include "util/u_math.h"
> > +#include "util/vma.h"
> > +
> > +struct util_vma_hole {
> > +   struct list_head link;
> > +   uint64_t offset;
> > +   uint64_t size;
> > +};
> > +
> > +#define util_vma_foreach_hole(_hole, _heap) \
> > +   list_for_each_entry(struct util_vma_hole, _hole, &(_heap)->holes,
> link)
> > +
> > +#define util_vma_foreach_hole_safe(_hole, _heap) \
> > +   list_for_each_entry_safe(struct util_vma_hole, _hole,
> &(_heap)->holes, link)
> > +
> > +void
> > +util_vma_heap_init(struct util_vma_heap *heap,
> > +                   uint64_t start, uint64_t size)
> > +{
> > +   list_inithead(&heap->holes);
> > +   util_vma_heap_free(heap, start, size);
> > +}
> > +
> > +void
> > +util_vma_heap_finish(struct util_vma_heap *heap)
> > +{
> > +   util_vma_foreach_hole_safe(hole, heap)
> > +      free(hole);
> > +}
> > +
> > +static void
> > +util_vma_heap_validate(struct util_vma_heap *heap)
> > +{
> > +   uint64_t prev_offset = 0;
> > +   util_vma_foreach_hole(hole, heap) {
> > +      assert(hole->offset > 0);
> > +      assert(hole->size > 0);
> > +
> > +      if (&hole->link == heap->holes.next) {
> > +         /* This must be the top-most hole.  Assert that, if it
> overflows, it
> > +          * overflows to 0, i.e. 2^64.
> > +          */
> > +         assert(hole->size + hole->offset == 0 ||
> > +                hole->size + hole->offset > hole->offset);
> > +      } else {
> > +         /* This is not the top-most hole so it must not overflow and,
> in
> > +          * fact, must be strictly lower than the top-most hole.  If
> > +          * hole->size + hole->offset == prev_offset, then we failed to
> join
> > +          * holes during a util_vma_heap_free.
> > +          */
> > +         assert(hole->size + hole->offset > hole->offset &&
> > +                hole->size + hole->offset < prev_offset);
> > +      }
> > +      prev_offset = hole->offset;
> > +   }
> > +}
> > +
> > +uint64_t
> > +util_vma_heap_alloc(struct util_vma_heap *heap,
> > +                    uint64_t size, uint64_t alignment)
> > +{
> > +   /* The caller is expected to reject zero-size allocations */
> > +   assert(size > 0);
> > +
> > +   assert(util_is_power_of_two_nonzero(alignment));
> > +
> > +   util_vma_heap_validate(heap);
>
> It looks like the loop in util_vma_heap_validate contains only
> asserts, thus it seems possible that on a release build the compiler
> might eliminate the list walk entirely.
>
> But, we could also make util_vma_heap_validate return a bool, and make
> all calls assert(util_vma_heap_validate(heap)).
>

That's probably a good idea.  If we do that, we'll need to make
util_vma_heap_validate inline so we don't get warnings on release builds.
Another option would be to surround the contents of the function with
"#ifndef NDEBUG"

--Jason


> Reviewed-by: Jordan Justen <jordan.l.jus...@intel.com>
>
> > +
> > +   util_vma_foreach_hole_safe(hole, heap) {
> > +      if (size > hole->size)
> > +         continue;
> > +
> > +      /* Compute the offset as the highest address where a chunk of the
> given
> > +       * size can be without going over the top of the hole.
> > +       *
> > +       * This calculation is known to not overflow because we know that
> > +       * hole->size + hole->offset can only overflow to 0 and size > 0.
> > +       */
> > +      uint64_t offset = (hole->size - size) + hole->offset;
> > +
> > +      /* Align the offset.  We align down and not up because we are
> allocating
> > +       * from the top of the hole and not the bottom.
> > +       */
> > +      offset &= ~(alignment - 1);
> > +
> > +      if (offset < hole->offset)
> > +         continue;
> > +
> > +      if (offset == hole->offset && size == hole->size) {
> > +         /* Just get rid of the hole. */
> > +         list_del(&hole->link);
> > +         free(hole);
> > +         util_vma_heap_validate(heap);
> > +         return offset;
> > +      }
> > +
> > +      assert(offset - hole->offset <= hole->size - size);
> > +      uint64_t waste = (hole->size - size) - (offset - hole->offset);
> > +      if (waste == 0) {
> > +         /* We allocated at the top.  Shrink the hole down. */
> > +         hole->size -= size;
> > +         util_vma_heap_validate(heap);
> > +         return offset;
> > +      }
> > +
> > +      if (offset == hole->offset) {
> > +         /* We allocated at the bottom. Shrink the hole up. */
> > +         hole->offset += size;
> > +         hole->size -= size;
> > +         util_vma_heap_validate(heap);
> > +         return offset;
> > +      }
> > +
> > +      /* We allocated in the middle.  We need to split the old hole
> into two
> > +       * holes, one high and one low.
> > +       */
> > +      struct util_vma_hole *high_hole = calloc(1, sizeof(*hole));
> > +      high_hole->offset = offset + size;
> > +      high_hole->size = waste;
> > +
> > +      /* Adjust the hole to be the amount of space left at he bottom of
> the
> > +       * original hole.
> > +       */
> > +      hole->size = offset - hole->offset;
> > +
> > +      /* Place the new hole before the old hole so that the list is in
> order
> > +       * from high to low.
> > +       */
> > +      list_addtail(&high_hole->link, &hole->link);
> > +
> > +      util_vma_heap_validate(heap);
> > +
> > +      return offset;
> > +   }
> > +
> > +   /* Failed to allocate */
> > +   return 0;
> > +}
> > +
> > +void
> > +util_vma_heap_free(struct util_vma_heap *heap,
> > +                   uint64_t offset, uint64_t size)
> > +{
> > +   /* An offset of 0 is reserved for allocation failure.  It is not a
> valid
> > +    * address and cannot be freed.
> > +    */
> > +   assert(offset > 0);
> > +
> > +   /* Freeing something with a size of 0 is also not valid. */
> > +   assert(size > 0);
> > +
> > +   /* It's possible for offset + size to wrap around if we touch the
> top of
> > +    * the 64-bit address space, but we cannot go any higher than 2^64.
> > +    */
> > +   assert(offset + size == 0 || offset + size > offset);
> > +
> > +   util_vma_heap_validate(heap);
> > +
> > +   /* Find immediately higher and lower holes if they exist. */
> > +   struct util_vma_hole *high_hole = NULL, *low_hole = NULL;
> > +   util_vma_foreach_hole(hole, heap) {
> > +      if (hole->offset <= offset) {
> > +         low_hole = hole;
> > +         break;
> > +      }
> > +      high_hole = hole;
> > +   }
> > +
> > +   if (high_hole)
> > +      assert(offset + size <= high_hole->offset);
> > +   bool high_adjacent = high_hole && offset + size == high_hole->offset;
> > +
> > +   if (low_hole) {
> > +      assert(low_hole->offset + low_hole->size > low_hole->offset);
> > +      assert(low_hole->offset + low_hole->size <= offset);
> > +   }
> > +   bool low_adjacent = low_hole && low_hole->offset + low_hole->size ==
> offset;
> > +
> > +   if (low_adjacent && high_adjacent) {
> > +      /* Merge the two holes */
> > +      low_hole->size += size + high_hole->size;
> > +      list_del(&high_hole->link);
> > +      free(high_hole);
> > +   } else if (low_adjacent) {
> > +      /* Merge into the low hole */
> > +      low_hole->size += size;
> > +   } else if (high_adjacent) {
> > +      /* Merge into the high hole */
> > +      high_hole->offset = offset;
> > +      high_hole->size += size;
> > +   } else {
> > +      /* Neither hole is adjacent; make a new one */
> > +      struct util_vma_hole *hole = calloc(1, sizeof(*hole));
> > +
> > +      hole->offset = offset;
> > +      hole->size = size;
> > +
> > +      /* Add it after the high hole so we maintain high-to-low ordering
> */
> > +      if (high_hole)
> > +         list_add(&hole->link, &high_hole->link);
> > +      else
> > +         list_add(&hole->link, &heap->holes);
> > +   }
> > +
> > +   util_vma_heap_validate(heap);
> > +}
> > diff --git a/src/util/vma.h b/src/util/vma.h
> > new file mode 100644
> > index 00000000000..ed69914e4cb
> > --- /dev/null
> > +++ b/src/util/vma.h
> > @@ -0,0 +1,53 @@
> > +/*
> > + * Copyright © 2018 Intel Corporation
> > + *
> > + * Permission is hereby granted, free of charge, to any person
> obtaining a
> > + * copy of this software and associated documentation files (the
> "Software"),
> > + * to deal in the Software without restriction, including without
> limitation
> > + * the rights to use, copy, modify, merge, publish, distribute,
> sublicense,
> > + * and/or sell copies of the Software, and to permit persons to whom the
> > + * Software is furnished to do so, subject to the following conditions:
> > + *
> > + * The above copyright notice and this permission notice (including the
> next
> > + * paragraph) shall be included in all copies or substantial portions
> of the
> > + * Software.
> > + *
> > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> EXPRESS OR
> > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT
> SHALL
> > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> OTHER
> > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
> ARISING
> > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
> DEALINGS
> > + * IN THE SOFTWARE.
> > + */
> > +
> > +#ifndef _UTIL_VMA_H
> > +#define _UTIL_VMA_H
> > +
> > +#include <stdint.h>
> > +
> > +#include "list.h"
> > +
> > +#ifdef __cplusplus
> > +extern "C" {
> > +#endif
> > +
> > +struct util_vma_heap {
> > +   struct list_head holes;
> > +};
> > +
> > +void util_vma_heap_init(struct util_vma_heap *heap,
> > +                        uint64_t start, uint64_t size);
> > +void util_vma_heap_finish(struct util_vma_heap *heap);
> > +
> > +uint64_t util_vma_heap_alloc(struct util_vma_heap *heap,
> > +                             uint64_t size, uint64_t alignment);
> > +
> > +void util_vma_heap_free(struct util_vma_heap *heap,
> > +                        uint64_t offset, uint64_t size);
> > +
> > +#ifdef __cplusplus
> > +} /* extern C */
> > +#endif
> > +
> > +#endif /* _UTIL_DEBUG_H */
> > --
> > 2.14.3
> >
>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev

Reply via email to