From 94a6384f1b7785d255f66b5d5c237c98f6611760 Mon Sep 17 00:00:00 2001
From: Chad Versace <chadversary@chromium.org>
Date: Thu, 8 Dec 2022 13:49:43 -0800
Subject: [PATCH] util/vma: Track size of free memory in heap

This allows users to detect fragmentation on allocation failure.
If heap allocation fails but the allocation size is not larger than the
total free size, then the allocation failed due to fragmentation.

Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/20289>
---
 src/util/vma.c | 26 +++++++++++++++++++-------
 src/util/vma.h |  3 +++
 2 files changed, 22 insertions(+), 7 deletions(-)

diff --git a/src/util/vma.c b/src/util/vma.c
index dddc3fe..abeaf9f 100644
--- a/src/util/vma.c
+++ b/src/util/vma.c
@@ -47,6 +47,7 @@ util_vma_heap_init(struct util_vma_heap *heap,
                    uint64_t start, uint64_t size)
 {
    list_inithead(&heap->holes);
+   heap->free_size = 0;
    util_vma_heap_free(heap, start, size);
 
    /* Default to using high addresses */
@@ -64,11 +65,14 @@ util_vma_heap_finish(struct util_vma_heap *heap)
 static void
 util_vma_heap_validate(struct util_vma_heap *heap)
 {
+   uint64_t free_size = 0;
    uint64_t prev_offset = 0;
    util_vma_foreach_hole(hole, heap) {
       assert(hole->offset > 0);
       assert(hole->size > 0);
 
+      free_size += hole->size;
+
       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.
@@ -86,13 +90,16 @@ util_vma_heap_validate(struct util_vma_heap *heap)
       }
       prev_offset = hole->offset;
    }
+
+   assert(free_size == heap->free_size);
 }
 #else
 #define util_vma_heap_validate(heap)
 #endif
 
 static void
-util_vma_hole_alloc(struct util_vma_hole *hole,
+util_vma_hole_alloc(struct util_vma_heap *heap,
+                    struct util_vma_hole *hole,
                     uint64_t offset, uint64_t size)
 {
    assert(hole->offset <= offset);
@@ -102,7 +109,7 @@ util_vma_hole_alloc(struct util_vma_hole *hole,
       /* Just get rid of the hole. */
       list_del(&hole->link);
       free(hole);
-      return;
+      goto done;
    }
 
    assert(offset - hole->offset <= hole->size - size);
@@ -110,14 +117,14 @@ util_vma_hole_alloc(struct util_vma_hole *hole,
    if (waste == 0) {
       /* We allocated at the top.  Shrink the hole down. */
       hole->size -= size;
-      return;
+      goto done;
    }
 
    if (offset == hole->offset) {
       /* We allocated at the bottom. Shrink the hole up. */
       hole->offset += size;
       hole->size -= size;
-      return;
+      goto done;
    }
 
    /* We allocated in the middle.  We need to split the old hole into two
@@ -136,6 +143,9 @@ util_vma_hole_alloc(struct util_vma_hole *hole,
     * from high to low.
     */
    list_addtail(&high_hole->link, &hole->link);
+
+ done:
+   heap->free_size -= size;
 }
 
 uint64_t
@@ -169,7 +179,7 @@ util_vma_heap_alloc(struct util_vma_heap *heap,
          if (offset < hole->offset)
             continue;
 
-         util_vma_hole_alloc(hole, offset, size);
+         util_vma_hole_alloc(heap, hole, offset, size);
          util_vma_heap_validate(heap);
          return offset;
       }
@@ -190,7 +200,7 @@ util_vma_heap_alloc(struct util_vma_heap *heap,
             offset += pad;
          }
 
-         util_vma_hole_alloc(hole, offset, size);
+         util_vma_hole_alloc(heap, hole, offset, size);
          util_vma_heap_validate(heap);
          return offset;
       }
@@ -230,7 +240,7 @@ util_vma_heap_alloc_addr(struct util_vma_heap *heap,
       if (hole->size < offset - hole->offset + size)
          return false;
 
-      util_vma_hole_alloc(hole, offset, size);
+      util_vma_hole_alloc(heap, hole, offset, size);
       return true;
    }
 
@@ -303,6 +313,7 @@ util_vma_heap_free(struct util_vma_heap *heap,
          list_add(&hole->link, &heap->holes);
    }
 
+   heap->free_size += size;
    util_vma_heap_validate(heap);
 }
 
@@ -320,6 +331,7 @@ util_vma_heap_print(struct util_vma_heap *heap, FILE *fp,
       total_free += hole->size;
    }
    assert(total_free <= total_size);
+   assert(total_free == heap->free_size);
    fprintf(fp, "%s%"PRIu64"B (0x%"PRIx64") free (%.2f%% full)\n",
            tab, total_free, total_free,
            ((double)(total_size - total_free) / (double)total_size) * 100);
diff --git a/src/util/vma.h b/src/util/vma.h
index 9bc058a..017c4d5 100644
--- a/src/util/vma.h
+++ b/src/util/vma.h
@@ -36,6 +36,9 @@ extern "C" {
 struct util_vma_heap {
    struct list_head holes;
 
+   /** Total size of free memory. */
+   uint64_t free_size;
+
    /** If true, util_vma_heap_alloc will prefer high addresses
     *
     * Default is true.
-- 
2.7.4