1 /*
2 * Copyright (c) 2021, 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 shall be included
12 * in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22 //!
23 //! \file mos_vma.c
24 //! \brief interface for virtual memory address allocation
25 //!
26
27 #include "mos_vma.h"
28
29 void
mos_vma_heap_init(mos_vma_heap * heap,uint64_t start,uint64_t size)30 mos_vma_heap_init(mos_vma_heap *heap, uint64_t start, uint64_t size)
31 {
32 assert(heap);
33 list_inithead(&heap->holes);
34 mos_vma_heap_free(heap, start, size);
35
36 /* Default to using high addresses */
37 heap->alloc_high = true;
38 }
39
40 void
mos_vma_heap_finish(mos_vma_heap * heap)41 mos_vma_heap_finish(mos_vma_heap *heap)
42 {
43 assert(heap);
44 list_for_each_entry_safe(mos_vma_hole, hole, &heap->holes, link)
45 {
46 free(hole);
47 }
48 }
49
50 #ifdef _DEBUG
51 static void
mos_vma_heap_validate(mos_vma_heap * heap)52 mos_vma_heap_validate(mos_vma_heap *heap)
53 {
54 assert(heap);
55 uint64_t prev_offset = 0;
56
57 list_for_each_entry(mos_vma_hole, hole, &heap->holes, link)
58 {
59 assert(hole->offset > 0);
60 assert(hole->size > 0);
61
62 if (&hole->link == heap->holes.next)
63 {
64 /* This must be the top-most hole. Assert that, if it overflows, it
65 * overflows to 0, i.e. 2^64.
66 */
67 assert(hole->size + hole->offset == 0 ||
68 hole->size + hole->offset > hole->offset);
69 }
70 else
71 {
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 mos_vma_heap_free.
76 */
77 assert(hole->size + hole->offset > hole->offset &&
78 hole->size + hole->offset < prev_offset);
79 }
80 prev_offset = hole->offset;
81 }
82 }
83 #else
84 #define mos_vma_heap_validate(heap)
85 #endif
86
87 static void
mos_vma_hole_alloc(mos_vma_hole * hole,uint64_t offset,uint64_t size)88 mos_vma_hole_alloc(mos_vma_hole *hole, uint64_t offset, uint64_t size)
89 {
90 assert(hole);
91 assert(hole->offset <= offset);
92 assert(hole->size >= offset - hole->offset + size);
93
94 if (offset == hole->offset && size == hole->size) {
95 /* Just get rid of the hole. */
96 list_del(&hole->link);
97 free(hole);
98 return;
99 }
100
101 uint64_t waste = (hole->size - size) - (offset - hole->offset);
102 if (waste == 0) {
103 /* We allocated at the top. Shrink the hole down. */
104 hole->size -= size;
105 return;
106 }
107
108 if (offset == hole->offset) {
109 /* We allocated at the bottom. Shrink the hole up. */
110 hole->offset += size;
111 hole->size -= size;
112 return;
113 }
114
115 /* We allocated in the middle. We need to split the old hole into two
116 * holes, one high and one low.
117 */
118 mos_vma_hole *high_hole = (mos_vma_hole*)calloc(1, sizeof(*hole));
119 if(high_hole == nullptr)
120 {
121 assert(high_hole);
122
123 return;
124 }
125
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
mos_vma_heap_alloc(mos_vma_heap * heap,uint64_t size,uint64_t alignment)141 mos_vma_heap_alloc(mos_vma_heap *heap, uint64_t size, uint64_t alignment)
142 {
143 assert(heap);
144 /* The caller is expected to reject zero-size allocations */
145 assert(size > 0);
146 assert(alignment > 0);
147
148 mos_vma_heap_validate(heap);
149
150 if (heap->alloc_high) {
151 list_for_each_entry_safe(mos_vma_hole, hole, &heap->holes, link)
152 {
153 if (size > hole->size)
154 continue;
155
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.
158 *
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.
161 */
162 uint64_t offset = (hole->size - size) + hole->offset;
163
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.
166 */
167 offset = (offset / alignment) * alignment;
168
169 if (offset < hole->offset)
170 continue;
171
172 mos_vma_hole_alloc(hole, offset, size);
173 mos_vma_heap_validate(heap);
174 return offset;
175 }
176 } else {
177 list_for_each_entry_safe_rev(mos_vma_hole, hole, &heap->holes, link) {
178 if (size > hole->size)
179 continue;
180
181 uint64_t offset = hole->offset;
182
183 /* Align the offset */
184 uint64_t misalign = offset % alignment;
185 if (misalign) {
186 uint64_t pad = alignment - misalign;
187 if (pad > hole->size - size)
188 continue;
189
190 offset += pad;
191 }
192
193 mos_vma_hole_alloc(hole, offset, size);
194 mos_vma_heap_validate(heap);
195 return offset;
196 }
197 }
198
199 /* Failed to allocate */
200 return 0;
201 }
202
203 bool
mos_vma_heap_alloc_addr(mos_vma_heap * heap,uint64_t offset,uint64_t size)204 mos_vma_heap_alloc_addr(mos_vma_heap *heap, uint64_t offset, uint64_t size)
205 {
206 assert(heap);
207 /* An offset of 0 is reserved for allocation failure. It is not a valid
208 * address and cannot be allocated.
209 */
210 assert(offset > 0);
211
212 /* Allocating something with a size of 0 is also not valid. */
213 assert(size > 0);
214
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.
217 */
218 assert(offset + size == 0 || offset + size > offset);
219
220 /* Find the hole if one exists. */
221 list_for_each_entry_safe(mos_vma_hole, hole, &heap->holes, link)
222 {
223 if (hole->offset > offset)
224 continue;
225
226 /* Holes are ordered high-to-low so the first hole we find with
227 * hole->offset <= is our hole. If it's not big enough to contain the
228 * requested range, then the allocation fails.
229 */
230 assert(hole->offset <= offset);
231 if (hole->size < offset - hole->offset + size)
232 return false;
233
234 mos_vma_hole_alloc(hole, offset, size);
235 return true;
236 }
237
238 /* We didn't find a suitable hole */
239 return false;
240 }
241
242 void
mos_vma_heap_free(mos_vma_heap * heap,uint64_t offset,uint64_t size)243 mos_vma_heap_free(mos_vma_heap *heap, uint64_t offset, uint64_t size)
244 {
245 assert(heap);
246 /* An offset of 0 is reserved for allocation failure. It is not a valid
247 * address and cannot be freed.
248 */
249 assert(offset > 0);
250
251 /* Freeing something with a size of 0 is also not valid. */
252 assert(size > 0);
253
254 /* It's possible for offset + size to wrap around if we touch the top of
255 * the 64-bit address space, but we cannot go any higher than 2^64.
256 */
257 assert(offset + size == 0 || offset + size > offset);
258
259 mos_vma_heap_validate(heap);
260
261 /* Find immediately higher and lower holes if they exist. */
262 mos_vma_hole *high_hole = NULL, *low_hole = NULL;
263 list_for_each_entry(mos_vma_hole, hole, &heap->holes, link)
264 {
265 if (hole->offset <= offset) {
266 low_hole = hole;
267 break;
268 }
269 high_hole = hole;
270 }
271
272 if (high_hole)
273 {
274 assert(offset + size <= high_hole->offset);
275 }
276
277 bool high_adjacent = high_hole && offset + size == high_hole->offset;
278
279 if (low_hole) {
280 assert(low_hole->offset + low_hole->size > low_hole->offset);
281 assert(low_hole->offset + low_hole->size <= offset);
282 }
283 bool low_adjacent = low_hole && low_hole->offset + low_hole->size == offset;
284
285 if (low_adjacent && high_adjacent) {
286 /* Merge the two holes */
287 low_hole->size += size + high_hole->size;
288 list_del(&high_hole->link);
289 free(high_hole);
290 } else if (low_adjacent) {
291 /* Merge into the low hole */
292 low_hole->size += size;
293 } else if (high_adjacent) {
294 /* Merge into the high hole */
295 high_hole->offset = offset;
296 high_hole->size += size;
297 } else {
298 /* Neither hole is adjacent; make a new one */
299 mos_vma_hole *hole = (mos_vma_hole*)calloc(1, sizeof(*hole));
300 assert(hole);
301 if(hole)
302 {
303 hole->offset = offset;
304 hole->size = size;
305
306 /* Add it after the high hole so we maintain high-to-low ordering */
307 if (high_hole)
308 list_add(&hole->link, &high_hole->link);
309 else
310 list_add(&hole->link, &heap->holes);
311 }
312 }
313
314 mos_vma_heap_validate(heap);
315 }
316