#define util_vma_heap_validate(heap)
#endif
+static void
+util_vma_hole_alloc(struct util_vma_hole *hole,
+ uint64_t offset, uint64_t size)
+{
+ assert(hole->offset <= offset);
+ assert(hole->size >= offset - hole->offset + size);
+
+ if (offset == hole->offset && size == hole->size) {
+ /* Just get rid of the hole. */
+ list_del(&hole->link);
+ free(hole);
+ return;
+ }
+
+ 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;
+ return;
+ }
+
+ if (offset == hole->offset) {
+ /* We allocated at the bottom. Shrink the hole up. */
+ hole->offset += size;
+ hole->size -= size;
+ return;
+ }
+
+ /* 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);
+}
+
uint64_t
util_vma_heap_alloc(struct util_vma_heap *heap,
uint64_t size, uint64_t alignment)
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;
- }
+ util_vma_hole_alloc(hole, offset, size);
+ 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;
- }
+ /* Failed to allocate */
+ return 0;
+}
- 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;
- }
+bool
+util_vma_heap_alloc_addr(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 allocated.
+ */
+ assert(offset > 0);
- /* 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;
+ /* Allocating something with a size of 0 is also not valid. */
+ assert(size > 0);
- /* Adjust the hole to be the amount of space left at he bottom of the
- * original hole.
- */
- hole->size = offset - hole->offset;
+ /* 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);
- /* 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);
+ /* Find the hole if one exists. */
+ util_vma_foreach_hole_safe(hole, heap) {
+ if (hole->offset > offset)
+ continue;
- util_vma_heap_validate(heap);
+ /* Holes are ordered high-to-low so the first hole we find with
+ * hole->offset <= is our hole. If it's not big enough to contain the
+ * requested range, then the allocation fails.
+ */
+ assert(hole->offset <= offset);
+ if (hole->size < offset - hole->offset + size)
+ return false;
- return offset;
+ util_vma_hole_alloc(hole, offset, size);
+ return true;
}
- /* Failed to allocate */
- return 0;
+ /* We didn't find a suitable hole */
+ return false;
}
void