2 * Copyright © 2018 Intel Corporation
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:
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
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
27 #include "util/u_math.h"
30 struct util_vma_hole
{
31 struct list_head link
;
36 #define util_vma_foreach_hole(_hole, _heap) \
37 list_for_each_entry(struct util_vma_hole, _hole, &(_heap)->holes, link)
39 #define util_vma_foreach_hole_safe(_hole, _heap) \
40 list_for_each_entry_safe(struct util_vma_hole, _hole, &(_heap)->holes, link)
42 #define util_vma_foreach_hole_safe_rev(_hole, _heap) \
43 list_for_each_entry_safe_rev(struct util_vma_hole, _hole, &(_heap)->holes, link)
46 util_vma_heap_init(struct util_vma_heap
*heap
,
47 uint64_t start
, uint64_t size
)
49 list_inithead(&heap
->holes
);
50 util_vma_heap_free(heap
, start
, size
);
52 /* Default to using high addresses */
53 heap
->alloc_high
= true;
57 util_vma_heap_finish(struct util_vma_heap
*heap
)
59 util_vma_foreach_hole_safe(hole
, heap
)
65 util_vma_heap_validate(struct util_vma_heap
*heap
)
67 uint64_t prev_offset
= 0;
68 util_vma_foreach_hole(hole
, heap
) {
69 assert(hole
->offset
> 0);
70 assert(hole
->size
> 0);
72 if (&hole
->link
== heap
->holes
.next
) {
73 /* This must be the top-most hole. Assert that, if it overflows, it
74 * overflows to 0, i.e. 2^64.
76 assert(hole
->size
+ hole
->offset
== 0 ||
77 hole
->size
+ hole
->offset
> hole
->offset
);
79 /* This is not the top-most hole so it must not overflow and, in
80 * fact, must be strictly lower than the top-most hole. If
81 * hole->size + hole->offset == prev_offset, then we failed to join
82 * holes during a util_vma_heap_free.
84 assert(hole
->size
+ hole
->offset
> hole
->offset
&&
85 hole
->size
+ hole
->offset
< prev_offset
);
87 prev_offset
= hole
->offset
;
91 #define util_vma_heap_validate(heap)
95 util_vma_hole_alloc(struct util_vma_hole
*hole
,
96 uint64_t offset
, uint64_t size
)
98 assert(hole
->offset
<= offset
);
99 assert(hole
->size
>= offset
- hole
->offset
+ size
);
101 if (offset
== hole
->offset
&& size
== hole
->size
) {
102 /* Just get rid of the hole. */
103 list_del(&hole
->link
);
108 assert(offset
- hole
->offset
<= hole
->size
- size
);
109 uint64_t waste
= (hole
->size
- size
) - (offset
- hole
->offset
);
111 /* We allocated at the top. Shrink the hole down. */
116 if (offset
== hole
->offset
) {
117 /* We allocated at the bottom. Shrink the hole up. */
118 hole
->offset
+= size
;
123 /* We allocated in the middle. We need to split the old hole into two
124 * holes, one high and one low.
126 struct util_vma_hole
*high_hole
= calloc(1, sizeof(*hole
));
127 high_hole
->offset
= offset
+ size
;
128 high_hole
->size
= waste
;
130 /* Adjust the hole to be the amount of space left at he bottom of the
133 hole
->size
= offset
- hole
->offset
;
135 /* Place the new hole before the old hole so that the list is in order
138 list_addtail(&high_hole
->link
, &hole
->link
);
142 util_vma_heap_alloc(struct util_vma_heap
*heap
,
143 uint64_t size
, uint64_t alignment
)
145 /* The caller is expected to reject zero-size allocations */
147 assert(alignment
> 0);
149 util_vma_heap_validate(heap
);
151 if (heap
->alloc_high
) {
152 util_vma_foreach_hole_safe(hole
, heap
) {
153 if (size
> hole
->size
)
156 /* Compute the offset as the highest address where a chunk of the
157 * given size can be without going over the top of the hole.
159 * This calculation is known to not overflow because we know that
160 * hole->size + hole->offset can only overflow to 0 and size > 0.
162 uint64_t offset
= (hole
->size
- size
) + hole
->offset
;
164 /* Align the offset. We align down and not up because we are
165 * allocating from the top of the hole and not the bottom.
167 offset
= (offset
/ alignment
) * alignment
;
169 if (offset
< hole
->offset
)
172 util_vma_hole_alloc(hole
, offset
, size
);
173 util_vma_heap_validate(heap
);
177 util_vma_foreach_hole_safe_rev(hole
, heap
) {
178 if (size
> hole
->size
)
181 uint64_t offset
= hole
->offset
;
183 /* Align the offset */
184 uint64_t misalign
= offset
% alignment
;
186 uint64_t pad
= alignment
- misalign
;
187 if (pad
> hole
->size
- size
)
193 util_vma_hole_alloc(hole
, offset
, size
);
194 util_vma_heap_validate(heap
);
199 /* Failed to allocate */
204 util_vma_heap_alloc_addr(struct util_vma_heap
*heap
,
205 uint64_t offset
, uint64_t size
)
207 /* An offset of 0 is reserved for allocation failure. It is not a valid
208 * address and cannot be allocated.
212 /* Allocating something with a size of 0 is also not valid. */
215 /* It's possible for offset + size to wrap around if we touch the top of
216 * the 64-bit address space, but we cannot go any higher than 2^64.
218 assert(offset
+ size
== 0 || offset
+ size
> offset
);
220 /* Find the hole if one exists. */
221 util_vma_foreach_hole_safe(hole
, heap
) {
222 if (hole
->offset
> offset
)
225 /* Holes are ordered high-to-low so the first hole we find with
226 * hole->offset <= is our hole. If it's not big enough to contain the
227 * requested range, then the allocation fails.
229 assert(hole
->offset
<= offset
);
230 if (hole
->size
< offset
- hole
->offset
+ size
)
233 util_vma_hole_alloc(hole
, offset
, size
);
237 /* We didn't find a suitable hole */
242 util_vma_heap_free(struct util_vma_heap
*heap
,
243 uint64_t offset
, uint64_t size
)
245 /* An offset of 0 is reserved for allocation failure. It is not a valid
246 * address and cannot be freed.
250 /* Freeing something with a size of 0 is also not valid. */
253 /* It's possible for offset + size to wrap around if we touch the top of
254 * the 64-bit address space, but we cannot go any higher than 2^64.
256 assert(offset
+ size
== 0 || offset
+ size
> offset
);
258 util_vma_heap_validate(heap
);
260 /* Find immediately higher and lower holes if they exist. */
261 struct util_vma_hole
*high_hole
= NULL
, *low_hole
= NULL
;
262 util_vma_foreach_hole(hole
, heap
) {
263 if (hole
->offset
<= offset
) {
271 assert(offset
+ size
<= high_hole
->offset
);
272 bool high_adjacent
= high_hole
&& offset
+ size
== high_hole
->offset
;
275 assert(low_hole
->offset
+ low_hole
->size
> low_hole
->offset
);
276 assert(low_hole
->offset
+ low_hole
->size
<= offset
);
278 bool low_adjacent
= low_hole
&& low_hole
->offset
+ low_hole
->size
== offset
;
280 if (low_adjacent
&& high_adjacent
) {
281 /* Merge the two holes */
282 low_hole
->size
+= size
+ high_hole
->size
;
283 list_del(&high_hole
->link
);
285 } else if (low_adjacent
) {
286 /* Merge into the low hole */
287 low_hole
->size
+= size
;
288 } else if (high_adjacent
) {
289 /* Merge into the high hole */
290 high_hole
->offset
= offset
;
291 high_hole
->size
+= size
;
293 /* Neither hole is adjacent; make a new one */
294 struct util_vma_hole
*hole
= calloc(1, sizeof(*hole
));
296 hole
->offset
= offset
;
299 /* Add it after the high hole so we maintain high-to-low ordering */
301 list_add(&hole
->link
, &high_hole
->link
);
303 list_add(&hole
->link
, &heap
->holes
);
306 util_vma_heap_validate(heap
);
310 util_vma_heap_print(struct util_vma_heap
*heap
, FILE *fp
,
311 const char *tab
, uint64_t total_size
)
313 fprintf(fp
, "%sutil_vma_heap:\n", tab
);
315 uint64_t total_free
= 0;
316 util_vma_foreach_hole(hole
, heap
) {
317 fprintf(fp
, "%s hole: offset = %"PRIu64
" (0x%"PRIx64
", "
318 "size = %"PRIu64
" (0x%"PRIx64
")\n",
319 tab
, hole
->offset
, hole
->offset
, hole
->size
, hole
->size
);
320 total_free
+= hole
->size
;
322 assert(total_free
<= total_size
);
323 fprintf(fp
, "%s%"PRIu64
"B (0x%"PRIx64
") free (%.2f%% full)\n",
324 tab
, total_free
, total_free
,
325 ((double)(total_size
- total_free
) / (double)total_size
) * 100);