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
26 #include "util/u_math.h"
29 struct util_vma_hole
{
30 struct list_head link
;
35 #define util_vma_foreach_hole(_hole, _heap) \
36 list_for_each_entry(struct util_vma_hole, _hole, &(_heap)->holes, link)
38 #define util_vma_foreach_hole_safe(_hole, _heap) \
39 list_for_each_entry_safe(struct util_vma_hole, _hole, &(_heap)->holes, link)
42 util_vma_heap_init(struct util_vma_heap
*heap
,
43 uint64_t start
, uint64_t size
)
45 list_inithead(&heap
->holes
);
46 util_vma_heap_free(heap
, start
, size
);
50 util_vma_heap_finish(struct util_vma_heap
*heap
)
52 util_vma_foreach_hole_safe(hole
, heap
)
58 util_vma_heap_validate(struct util_vma_heap
*heap
)
60 uint64_t prev_offset
= 0;
61 util_vma_foreach_hole(hole
, heap
) {
62 assert(hole
->offset
> 0);
63 assert(hole
->size
> 0);
65 if (&hole
->link
== heap
->holes
.next
) {
66 /* This must be the top-most hole. Assert that, if it overflows, it
67 * overflows to 0, i.e. 2^64.
69 assert(hole
->size
+ hole
->offset
== 0 ||
70 hole
->size
+ hole
->offset
> hole
->offset
);
72 /* This is not the top-most hole so it must not overflow and, in
73 * fact, must be strictly lower than the top-most hole. If
74 * hole->size + hole->offset == prev_offset, then we failed to join
75 * holes during a util_vma_heap_free.
77 assert(hole
->size
+ hole
->offset
> hole
->offset
&&
78 hole
->size
+ hole
->offset
< prev_offset
);
80 prev_offset
= hole
->offset
;
84 #define util_vma_heap_validate(heap)
88 util_vma_hole_alloc(struct util_vma_hole
*hole
,
89 uint64_t offset
, uint64_t size
)
91 assert(hole
->offset
<= offset
);
92 assert(hole
->size
>= offset
- hole
->offset
+ size
);
94 if (offset
== hole
->offset
&& size
== hole
->size
) {
95 /* Just get rid of the hole. */
96 list_del(&hole
->link
);
101 assert(offset
- hole
->offset
<= hole
->size
- size
);
102 uint64_t waste
= (hole
->size
- size
) - (offset
- hole
->offset
);
104 /* We allocated at the top. Shrink the hole down. */
109 if (offset
== hole
->offset
) {
110 /* We allocated at the bottom. Shrink the hole up. */
111 hole
->offset
+= size
;
116 /* We allocated in the middle. We need to split the old hole into two
117 * holes, one high and one low.
119 struct util_vma_hole
*high_hole
= calloc(1, sizeof(*hole
));
120 high_hole
->offset
= offset
+ size
;
121 high_hole
->size
= waste
;
123 /* Adjust the hole to be the amount of space left at he bottom of the
126 hole
->size
= offset
- hole
->offset
;
128 /* Place the new hole before the old hole so that the list is in order
131 list_addtail(&high_hole
->link
, &hole
->link
);
135 util_vma_heap_alloc(struct util_vma_heap
*heap
,
136 uint64_t size
, uint64_t alignment
)
138 /* The caller is expected to reject zero-size allocations */
140 assert(alignment
> 0);
142 util_vma_heap_validate(heap
);
144 util_vma_foreach_hole_safe(hole
, heap
) {
145 if (size
> hole
->size
)
148 /* Compute the offset as the highest address where a chunk of the given
149 * size can be without going over the top of the hole.
151 * This calculation is known to not overflow because we know that
152 * hole->size + hole->offset can only overflow to 0 and size > 0.
154 uint64_t offset
= (hole
->size
- size
) + hole
->offset
;
156 /* Align the offset. We align down and not up because we are allocating
157 * from the top of the hole and not the bottom.
159 offset
= (offset
/ alignment
) * alignment
;
161 if (offset
< hole
->offset
)
164 util_vma_hole_alloc(hole
, offset
, size
);
165 util_vma_heap_validate(heap
);
169 /* Failed to allocate */
174 util_vma_heap_alloc_addr(struct util_vma_heap
*heap
,
175 uint64_t offset
, uint64_t size
)
177 /* An offset of 0 is reserved for allocation failure. It is not a valid
178 * address and cannot be allocated.
182 /* Allocating something with a size of 0 is also not valid. */
185 /* It's possible for offset + size to wrap around if we touch the top of
186 * the 64-bit address space, but we cannot go any higher than 2^64.
188 assert(offset
+ size
== 0 || offset
+ size
> offset
);
190 /* Find the hole if one exists. */
191 util_vma_foreach_hole_safe(hole
, heap
) {
192 if (hole
->offset
> offset
)
195 /* Holes are ordered high-to-low so the first hole we find with
196 * hole->offset <= is our hole. If it's not big enough to contain the
197 * requested range, then the allocation fails.
199 assert(hole
->offset
<= offset
);
200 if (hole
->size
< offset
- hole
->offset
+ size
)
203 util_vma_hole_alloc(hole
, offset
, size
);
207 /* We didn't find a suitable hole */
212 util_vma_heap_free(struct util_vma_heap
*heap
,
213 uint64_t offset
, uint64_t size
)
215 /* An offset of 0 is reserved for allocation failure. It is not a valid
216 * address and cannot be freed.
220 /* Freeing something with a size of 0 is also not valid. */
223 /* It's possible for offset + size to wrap around if we touch the top of
224 * the 64-bit address space, but we cannot go any higher than 2^64.
226 assert(offset
+ size
== 0 || offset
+ size
> offset
);
228 util_vma_heap_validate(heap
);
230 /* Find immediately higher and lower holes if they exist. */
231 struct util_vma_hole
*high_hole
= NULL
, *low_hole
= NULL
;
232 util_vma_foreach_hole(hole
, heap
) {
233 if (hole
->offset
<= offset
) {
241 assert(offset
+ size
<= high_hole
->offset
);
242 bool high_adjacent
= high_hole
&& offset
+ size
== high_hole
->offset
;
245 assert(low_hole
->offset
+ low_hole
->size
> low_hole
->offset
);
246 assert(low_hole
->offset
+ low_hole
->size
<= offset
);
248 bool low_adjacent
= low_hole
&& low_hole
->offset
+ low_hole
->size
== offset
;
250 if (low_adjacent
&& high_adjacent
) {
251 /* Merge the two holes */
252 low_hole
->size
+= size
+ high_hole
->size
;
253 list_del(&high_hole
->link
);
255 } else if (low_adjacent
) {
256 /* Merge into the low hole */
257 low_hole
->size
+= size
;
258 } else if (high_adjacent
) {
259 /* Merge into the high hole */
260 high_hole
->offset
= offset
;
261 high_hole
->size
+= size
;
263 /* Neither hole is adjacent; make a new one */
264 struct util_vma_hole
*hole
= calloc(1, sizeof(*hole
));
266 hole
->offset
= offset
;
269 /* Add it after the high hole so we maintain high-to-low ordering */
271 list_add(&hole
->link
, &high_hole
->link
);
273 list_add(&hole
->link
, &heap
->holes
);
276 util_vma_heap_validate(heap
);