From adbcef37d2d1f838ef24a4ab1f4332cc87b5fdad Mon Sep 17 00:00:00 2001
From: Jason Ekstrand <jason@jlekstrand.net>
Date: Thu, 29 Aug 2019 13:04:25 -0500
Subject: [PATCH] util/vma: Add an option to configure high/low preference

The vma_heap allocator was originally designed to prefer high addresses
in order to find bugs in ANV's high address handling.  However, there
are cases where you might want the allocator to prefer lower addresses
for some reason.  This provides a configure bit for exactly this
purpose.

Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
Reviewed-by: Eric Anholt <eric@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/5019>
---
 src/util/vma.c | 67 ++++++++++++++++++++++++++++++++++++--------------
 src/util/vma.h |  6 +++++
 2 files changed, 54 insertions(+), 19 deletions(-)

diff --git a/src/util/vma.c b/src/util/vma.c
index 714ef01b211..f17ec0c08f1 100644
--- a/src/util/vma.c
+++ b/src/util/vma.c
@@ -38,12 +38,18 @@ struct util_vma_hole {
 #define util_vma_foreach_hole_safe(_hole, _heap) \
    list_for_each_entry_safe(struct util_vma_hole, _hole, &(_heap)->holes, link)
 
+#define util_vma_foreach_hole_safe_rev(_hole, _heap) \
+   list_for_each_entry_safe_rev(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);
+
+   /* Default to using high addresses */
+   heap->alloc_high = true;
 }
 
 void
@@ -141,29 +147,52 @@ util_vma_heap_alloc(struct util_vma_heap *heap,
 
    util_vma_heap_validate(heap);
 
-   util_vma_foreach_hole_safe(hole, heap) {
-      if (size > hole->size)
-         continue;
+   if (heap->alloc_high) {
+      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;
+         /* 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 = (offset / alignment) * alignment;
+         /* Align the offset.  We align down and not up because we are
+          * allocating from the top of the hole and not the bottom.
+          */
+         offset = (offset / alignment) * alignment;
 
-      if (offset < hole->offset)
-         continue;
+         if (offset < hole->offset)
+            continue;
 
-      util_vma_hole_alloc(hole, offset, size);
-      util_vma_heap_validate(heap);
-      return offset;
+         util_vma_hole_alloc(hole, offset, size);
+         util_vma_heap_validate(heap);
+         return offset;
+      }
+   } else {
+      util_vma_foreach_hole_safe_rev(hole, heap) {
+         if (size > hole->size)
+            continue;
+
+         uint64_t offset = hole->offset;
+
+         /* Align the offset */
+         uint64_t misalign = offset % alignment;
+         if (misalign) {
+            uint64_t pad = alignment - misalign;
+            if (pad > hole->size - size)
+               continue;
+
+            offset += pad;
+         }
+
+         util_vma_hole_alloc(hole, offset, size);
+         util_vma_heap_validate(heap);
+         return offset;
+      }
    }
 
    /* Failed to allocate */
diff --git a/src/util/vma.h b/src/util/vma.h
index 91c7ee6e66a..58b4f8bf941 100644
--- a/src/util/vma.h
+++ b/src/util/vma.h
@@ -34,6 +34,12 @@ extern "C" {
 
 struct util_vma_heap {
    struct list_head holes;
+
+   /** If true, util_vma_heap_alloc will prefer high addresses
+    *
+    * Default is true.
+    */
+   bool alloc_high;
 };
 
 void util_vma_heap_init(struct util_vma_heap *heap,
-- 
2.30.2