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_heap_alloc(struct util_vma_heap
*heap
,
89 uint64_t size
, uint64_t alignment
)
91 /* The caller is expected to reject zero-size allocations */
93 assert(alignment
> 0);
95 util_vma_heap_validate(heap
);
97 util_vma_foreach_hole_safe(hole
, heap
) {
98 if (size
> hole
->size
)
101 /* Compute the offset as the highest address where a chunk of the given
102 * size can be without going over the top of the hole.
104 * This calculation is known to not overflow because we know that
105 * hole->size + hole->offset can only overflow to 0 and size > 0.
107 uint64_t offset
= (hole
->size
- size
) + hole
->offset
;
109 /* Align the offset. We align down and not up because we are allocating
110 * from the top of the hole and not the bottom.
112 offset
= (offset
/ alignment
) * alignment
;
114 if (offset
< hole
->offset
)
117 if (offset
== hole
->offset
&& size
== hole
->size
) {
118 /* Just get rid of the hole. */
119 list_del(&hole
->link
);
121 util_vma_heap_validate(heap
);
125 assert(offset
- hole
->offset
<= hole
->size
- size
);
126 uint64_t waste
= (hole
->size
- size
) - (offset
- hole
->offset
);
128 /* We allocated at the top. Shrink the hole down. */
130 util_vma_heap_validate(heap
);
134 if (offset
== hole
->offset
) {
135 /* We allocated at the bottom. Shrink the hole up. */
136 hole
->offset
+= size
;
138 util_vma_heap_validate(heap
);
142 /* We allocated in the middle. We need to split the old hole into two
143 * holes, one high and one low.
145 struct util_vma_hole
*high_hole
= calloc(1, sizeof(*hole
));
146 high_hole
->offset
= offset
+ size
;
147 high_hole
->size
= waste
;
149 /* Adjust the hole to be the amount of space left at he bottom of the
152 hole
->size
= offset
- hole
->offset
;
154 /* Place the new hole before the old hole so that the list is in order
157 list_addtail(&high_hole
->link
, &hole
->link
);
159 util_vma_heap_validate(heap
);
164 /* Failed to allocate */
169 util_vma_heap_free(struct util_vma_heap
*heap
,
170 uint64_t offset
, uint64_t size
)
172 /* An offset of 0 is reserved for allocation failure. It is not a valid
173 * address and cannot be freed.
177 /* Freeing something with a size of 0 is also not valid. */
180 /* It's possible for offset + size to wrap around if we touch the top of
181 * the 64-bit address space, but we cannot go any higher than 2^64.
183 assert(offset
+ size
== 0 || offset
+ size
> offset
);
185 util_vma_heap_validate(heap
);
187 /* Find immediately higher and lower holes if they exist. */
188 struct util_vma_hole
*high_hole
= NULL
, *low_hole
= NULL
;
189 util_vma_foreach_hole(hole
, heap
) {
190 if (hole
->offset
<= offset
) {
198 assert(offset
+ size
<= high_hole
->offset
);
199 bool high_adjacent
= high_hole
&& offset
+ size
== high_hole
->offset
;
202 assert(low_hole
->offset
+ low_hole
->size
> low_hole
->offset
);
203 assert(low_hole
->offset
+ low_hole
->size
<= offset
);
205 bool low_adjacent
= low_hole
&& low_hole
->offset
+ low_hole
->size
== offset
;
207 if (low_adjacent
&& high_adjacent
) {
208 /* Merge the two holes */
209 low_hole
->size
+= size
+ high_hole
->size
;
210 list_del(&high_hole
->link
);
212 } else if (low_adjacent
) {
213 /* Merge into the low hole */
214 low_hole
->size
+= size
;
215 } else if (high_adjacent
) {
216 /* Merge into the high hole */
217 high_hole
->offset
= offset
;
218 high_hole
->size
+= size
;
220 /* Neither hole is adjacent; make a new one */
221 struct util_vma_hole
*hole
= calloc(1, sizeof(*hole
));
223 hole
->offset
= offset
;
226 /* Add it after the high hole so we maintain high-to-low ordering */
228 list_add(&hole
->link
, &high_hole
->link
);
230 list_add(&hole
->link
, &heap
->holes
);
233 util_vma_heap_validate(heap
);