src/util/vma.c

   1 /*
   2  * Copyright © 2018 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #include <stdlib.h>
  25
  26 #include "util/u_math.h"
  27 #include "util/vma.h"
  28
  29 struct util_vma_hole {
  30    struct list_head link;
  31    uint64_t offset;
  32    uint64_t size;
  33 };
  34
  35 #define util_vma_foreach_hole(_hole, _heap) \
  36    list_for_each_entry(struct util_vma_hole, _hole, &(_heap)->holes, link)
  37
  38 #define util_vma_foreach_hole_safe(_hole, _heap) \
  39    list_for_each_entry_safe(struct util_vma_hole, _hole, &(_heap)->holes, link)
  40
  41 #define util_vma_foreach_hole_safe_rev(_hole, _heap) \
  42    list_for_each_entry_safe_rev(struct util_vma_hole, _hole, &(_heap)->holes, link)
  43
  44 void
  45 util_vma_heap_init(struct util_vma_heap *heap,
  46                    uint64_t start, uint64_t size)
  47 {
  48    list_inithead(&heap->holes);
  49    util_vma_heap_free(heap, start, size);
  50
  51    /* Default to using high addresses */
  52    heap->alloc_high = true;
  53 }
  54
  55 void
  56 util_vma_heap_finish(struct util_vma_heap *heap)
  57 {
  58    util_vma_foreach_hole_safe(hole, heap)
  59       free(hole);
  60 }
  61
  62 #ifndef NDEBUG
  63 static void
  64 util_vma_heap_validate(struct util_vma_heap *heap)
  65 {
  66    uint64_t prev_offset = 0;
  67    util_vma_foreach_hole(hole, heap) {
  68       assert(hole->offset > 0);
  69       assert(hole->size > 0);
  70
  71       if (&hole->link == heap->holes.next) {
  72          /* This must be the top-most hole.  Assert that, if it overflows, it
  73           * overflows to 0, i.e. 2^64.
  74           */
  75          assert(hole->size + hole->offset == 0 ||
  76                 hole->size + hole->offset > hole->offset);
  77       } else {
  78          /* This is not the top-most hole so it must not overflow and, in
  79           * fact, must be strictly lower than the top-most hole.  If
  80           * hole->size + hole->offset == prev_offset, then we failed to join
  81           * holes during a util_vma_heap_free.
  82           */
  83          assert(hole->size + hole->offset > hole->offset &&
  84                 hole->size + hole->offset < prev_offset);
  85       }
  86       prev_offset = hole->offset;
  87    }
  88 }
  89 #else
  90 #define util_vma_heap_validate(heap)
  91 #endif
  92
  93 static void
  94 util_vma_hole_alloc(struct util_vma_hole *hole,
  95                     uint64_t offset, uint64_t size)
  96 {
  97    assert(hole->offset <= offset);
  98    assert(hole->size >= offset - hole->offset + size);
  99
 100    if (offset == hole->offset && size == hole->size) {
 101       /* Just get rid of the hole. */
 102       list_del(&hole->link);
 103       free(hole);
 104       return;
 105    }
 106
 107    assert(offset - hole->offset <= hole->size - size);
 108    uint64_t waste = (hole->size - size) - (offset - hole->offset);
 109    if (waste == 0) {
 110       /* We allocated at the top.  Shrink the hole down. */
 111       hole->size -= size;
 112       return;
 113    }
 114
 115    if (offset == hole->offset) {
 116       /* We allocated at the bottom. Shrink the hole up. */
 117       hole->offset += size;
 118       hole->size -= size;
 119       return;
 120    }
 121
 122    /* We allocated in the middle.  We need to split the old hole into two
 123     * holes, one high and one low.
 124     */
 125    struct util_vma_hole *high_hole = calloc(1, sizeof(*hole));
 126    high_hole->offset = offset + size;
 127    high_hole->size = waste;
 128
 129    /* Adjust the hole to be the amount of space left at he bottom of the
 130     * original hole.
 131     */
 132    hole->size = offset - hole->offset;
 133
 134    /* Place the new hole before the old hole so that the list is in order
 135     * from high to low.
 136     */
 137    list_addtail(&high_hole->link, &hole->link);
 138 }
 139
 140 uint64_t
 141 util_vma_heap_alloc(struct util_vma_heap *heap,
 142                     uint64_t size, uint64_t alignment)
 143 {
 144    /* The caller is expected to reject zero-size allocations */
 145    assert(size > 0);
 146    assert(alignment > 0);
 147
 148    util_vma_heap_validate(heap);
 149
 150    if (heap->alloc_high) {
 151       util_vma_foreach_hole_safe(hole, heap) {
 152          if (size > hole->size)
 153             continue;
 154
 155          /* Compute the offset as the highest address where a chunk of the
 156           * given size can be without going over the top of the hole.
 157           *
 158           * This calculation is known to not overflow because we know that
 159           * hole->size + hole->offset can only overflow to 0 and size > 0.
 160           */
 161          uint64_t offset = (hole->size - size) + hole->offset;
 162
 163          /* Align the offset.  We align down and not up because we are
 164           * allocating from the top of the hole and not the bottom.
 165           */
 166          offset = (offset / alignment) * alignment;
 167
 168          if (offset < hole->offset)
 169             continue;
 170
 171          util_vma_hole_alloc(hole, offset, size);
 172          util_vma_heap_validate(heap);
 173          return offset;
 174       }
 175    } else {
 176       util_vma_foreach_hole_safe_rev(hole, heap) {
 177          if (size > hole->size)
 178             continue;
 179
 180          uint64_t offset = hole->offset;
 181
 182          /* Align the offset */
 183          uint64_t misalign = offset % alignment;
 184          if (misalign) {
 185             uint64_t pad = alignment - misalign;
 186             if (pad > hole->size - size)
 187                continue;
 188
 189             offset += pad;
 190          }
 191
 192          util_vma_hole_alloc(hole, offset, size);
 193          util_vma_heap_validate(heap);
 194          return offset;
 195       }
 196    }
 197
 198    /* Failed to allocate */
 199    return 0;
 200 }
 201
 202 bool
 203 util_vma_heap_alloc_addr(struct util_vma_heap *heap,
 204                          uint64_t offset, uint64_t size)
 205 {
 206    /* An offset of 0 is reserved for allocation failure.  It is not a valid
 207     * address and cannot be allocated.
 208     */
 209    assert(offset > 0);
 210
 211    /* Allocating something with a size of 0 is also not valid. */
 212    assert(size > 0);
 213
 214    /* It's possible for offset + size to wrap around if we touch the top of
 215     * the 64-bit address space, but we cannot go any higher than 2^64.
 216     */
 217    assert(offset + size == 0 || offset + size > offset);
 218
 219    /* Find the hole if one exists. */
 220    util_vma_foreach_hole_safe(hole, heap) {
 221       if (hole->offset > offset)
 222          continue;
 223
 224       /* Holes are ordered high-to-low so the first hole we find with
 225        * hole->offset <= is our hole.  If it's not big enough to contain the
 226        * requested range, then the allocation fails.
 227        */
 228       assert(hole->offset <= offset);
 229       if (hole->size < offset - hole->offset + size)
 230          return false;
 231
 232       util_vma_hole_alloc(hole, offset, size);
 233       return true;
 234    }
 235
 236    /* We didn't find a suitable hole */
 237    return false;
 238 }
 239
 240 void
 241 util_vma_heap_free(struct util_vma_heap *heap,
 242                    uint64_t offset, uint64_t size)
 243 {
 244    /* An offset of 0 is reserved for allocation failure.  It is not a valid
 245     * address and cannot be freed.
 246     */
 247    assert(offset > 0);
 248
 249    /* Freeing something with a size of 0 is also not valid. */
 250    assert(size > 0);
 251
 252    /* It's possible for offset + size to wrap around if we touch the top of
 253     * the 64-bit address space, but we cannot go any higher than 2^64.
 254     */
 255    assert(offset + size == 0 || offset + size > offset);
 256
 257    util_vma_heap_validate(heap);
 258
 259    /* Find immediately higher and lower holes if they exist. */
 260    struct util_vma_hole *high_hole = NULL, *low_hole = NULL;
 261    util_vma_foreach_hole(hole, heap) {
 262       if (hole->offset <= offset) {
 263          low_hole = hole;
 264          break;
 265       }
 266       high_hole = hole;
 267    }
 268
 269    if (high_hole)
 270       assert(offset + size <= high_hole->offset);
 271    bool high_adjacent = high_hole && offset + size == high_hole->offset;
 272
 273    if (low_hole) {
 274       assert(low_hole->offset + low_hole->size > low_hole->offset);
 275       assert(low_hole->offset + low_hole->size <= offset);
 276    }
 277    bool low_adjacent = low_hole && low_hole->offset + low_hole->size == offset;
 278
 279    if (low_adjacent && high_adjacent) {
 280       /* Merge the two holes */
 281       low_hole->size += size + high_hole->size;
 282       list_del(&high_hole->link);
 283       free(high_hole);
 284    } else if (low_adjacent) {
 285       /* Merge into the low hole */
 286       low_hole->size += size;
 287    } else if (high_adjacent) {
 288       /* Merge into the high hole */
 289       high_hole->offset = offset;
 290       high_hole->size += size;
 291    } else {
 292       /* Neither hole is adjacent; make a new one */
 293       struct util_vma_hole *hole = calloc(1, sizeof(*hole));
 294
 295       hole->offset = offset;
 296       hole->size = size;
 297
 298       /* Add it after the high hole so we maintain high-to-low ordering */
 299       if (high_hole)
 300          list_add(&hole->link, &high_hole->link);
 301       else
 302          list_add(&hole->link, &heap->holes);
 303    }
 304
 305    util_vma_heap_validate(heap);
 306 }