1
2
3
4
5
6
7
8
9
10
11
12
13#include "qemu/osdep.h"
14#include "libqos/malloc.h"
15#include "qemu-common.h"
16#include <glib.h>
17
18typedef QTAILQ_HEAD(MemList, MemBlock) MemList;
19
20typedef struct MemBlock {
21 QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
22 uint64_t size;
23 uint64_t addr;
24} MemBlock;
25
26struct QGuestAllocator {
27 QAllocOpts opts;
28 uint64_t start;
29 uint64_t end;
30 uint32_t page_size;
31
32 MemList *used;
33 MemList *free;
34};
35
36#define DEFAULT_PAGE_SIZE 4096
37
38static void mlist_delete(MemList *list, MemBlock *node)
39{
40 g_assert(list && node);
41 QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
42 g_free(node);
43}
44
45static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
46{
47 MemBlock *node;
48 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
49 if (node->addr == addr) {
50 return node;
51 }
52 }
53 return NULL;
54}
55
56static MemBlock *mlist_find_space(MemList *head, uint64_t size)
57{
58 MemBlock *node;
59
60 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
61 if (node->size >= size) {
62 return node;
63 }
64 }
65 return NULL;
66}
67
68static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
69{
70 MemBlock *node;
71 g_assert(head && insr);
72
73 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
74 if (insr->addr < node->addr) {
75 QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
76 return insr;
77 }
78 }
79
80 QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
81 return insr;
82}
83
84static inline uint64_t mlist_boundary(MemBlock *node)
85{
86 return node->size + node->addr;
87}
88
89static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
90{
91 g_assert(head && left && right);
92
93 left->size += right->size;
94 mlist_delete(head, right);
95 return left;
96}
97
98static void mlist_coalesce(MemList *head, MemBlock *node)
99{
100 g_assert(node);
101 MemBlock *left;
102 MemBlock *right;
103 char merge;
104
105 do {
106 merge = 0;
107 left = QTAILQ_PREV(node, MemList, MLIST_ENTNAME);
108 right = QTAILQ_NEXT(node, MLIST_ENTNAME);
109
110
111 if (left && mlist_boundary(left) == node->addr) {
112 node = mlist_join(head, left, node);
113 merge = 1;
114 }
115
116
117 if (right && mlist_boundary(node) == right->addr) {
118 node = mlist_join(head, node, right);
119 merge = 1;
120 }
121
122 } while (merge);
123}
124
125static MemBlock *mlist_new(uint64_t addr, uint64_t size)
126{
127 MemBlock *block;
128
129 if (!size) {
130 return NULL;
131 }
132 block = g_malloc0(sizeof(MemBlock));
133
134 block->addr = addr;
135 block->size = size;
136
137 return block;
138}
139
140static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
141 uint64_t size)
142{
143 uint64_t addr;
144 MemBlock *usednode;
145
146 g_assert(freenode);
147 g_assert_cmpint(freenode->size, >=, size);
148
149 addr = freenode->addr;
150 if (freenode->size == size) {
151
152 QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
153 usednode = freenode;
154 } else {
155
156 freenode->addr += size;
157 freenode->size -= size;
158 usednode = mlist_new(addr, size);
159 }
160
161 mlist_sort_insert(s->used, usednode);
162 return addr;
163}
164
165
166
167static void mlist_check(QGuestAllocator *s)
168{
169 MemBlock *node;
170 uint64_t addr = s->start > 0 ? s->start - 1 : 0;
171 uint64_t next = s->start;
172
173 QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
174 g_assert_cmpint(node->addr, >, addr);
175 g_assert_cmpint(node->addr, >=, next);
176 addr = node->addr;
177 next = node->addr + node->size;
178 }
179
180 addr = s->start > 0 ? s->start - 1 : 0;
181 next = s->start;
182 QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
183 g_assert_cmpint(node->addr, >, addr);
184 g_assert_cmpint(node->addr, >=, next);
185 addr = node->addr;
186 next = node->addr + node->size;
187 }
188}
189
190static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
191{
192 MemBlock *node;
193
194 node = mlist_find_space(s->free, size);
195 if (!node) {
196 fprintf(stderr, "Out of guest memory.\n");
197 g_assert_not_reached();
198 }
199 return mlist_fulfill(s, node, size);
200}
201
202static void mlist_free(QGuestAllocator *s, uint64_t addr)
203{
204 MemBlock *node;
205
206 if (addr == 0) {
207 return;
208 }
209
210 node = mlist_find_key(s->used, addr);
211 if (!node) {
212 fprintf(stderr, "Error: no record found for an allocation at "
213 "0x%016" PRIx64 ".\n",
214 addr);
215 g_assert_not_reached();
216 }
217
218
219 QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
220 mlist_sort_insert(s->free, node);
221 mlist_coalesce(s->free, node);
222}
223
224
225
226
227
228void alloc_uninit(QGuestAllocator *allocator)
229{
230 MemBlock *node;
231 MemBlock *tmp;
232 QAllocOpts mask;
233
234
235 QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
236 if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
237 fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
238 "size 0x%016" PRIx64 ".\n",
239 node->addr, node->size);
240 }
241 if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
242 g_assert_not_reached();
243 }
244 g_free(node);
245 }
246
247
248
249 mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
250 QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
251 if ((allocator->opts & mask) == mask) {
252 if ((node->addr != allocator->start) ||
253 (node->size != allocator->end - allocator->start)) {
254 fprintf(stderr, "Free list is corrupted.\n");
255 g_assert_not_reached();
256 }
257 }
258
259 g_free(node);
260 }
261
262 g_free(allocator->used);
263 g_free(allocator->free);
264 g_free(allocator);
265}
266
267uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
268{
269 uint64_t rsize = size;
270 uint64_t naddr;
271
272 if (!size) {
273 return 0;
274 }
275
276 rsize += (allocator->page_size - 1);
277 rsize &= -allocator->page_size;
278 g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
279 g_assert_cmpint(rsize, >=, size);
280
281 naddr = mlist_alloc(allocator, rsize);
282 if (allocator->opts & ALLOC_PARANOID) {
283 mlist_check(allocator);
284 }
285
286 return naddr;
287}
288
289void guest_free(QGuestAllocator *allocator, uint64_t addr)
290{
291 if (!addr) {
292 return;
293 }
294 mlist_free(allocator, addr);
295 if (allocator->opts & ALLOC_PARANOID) {
296 mlist_check(allocator);
297 }
298}
299
300QGuestAllocator *alloc_init(uint64_t start, uint64_t end)
301{
302 QGuestAllocator *s = g_malloc0(sizeof(*s));
303 MemBlock *node;
304
305 s->start = start;
306 s->end = end;
307
308 s->used = g_malloc(sizeof(MemList));
309 s->free = g_malloc(sizeof(MemList));
310 QTAILQ_INIT(s->used);
311 QTAILQ_INIT(s->free);
312
313 node = mlist_new(s->start, s->end - s->start);
314 QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
315
316 s->page_size = DEFAULT_PAGE_SIZE;
317
318 return s;
319}
320
321QGuestAllocator *alloc_init_flags(QAllocOpts opts,
322 uint64_t start, uint64_t end)
323{
324 QGuestAllocator *s = alloc_init(start, end);
325 s->opts = opts;
326 return s;
327}
328
329void alloc_set_page_size(QGuestAllocator *allocator, size_t page_size)
330{
331
332 g_assert(QTAILQ_EMPTY(allocator->used));
333
334 g_assert(is_power_of_2(page_size));
335 allocator->page_size = page_size;
336}
337
338void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
339{
340 allocator->opts |= opts;
341}
342
343void migrate_allocator(QGuestAllocator *src,
344 QGuestAllocator *dst)
345{
346 MemBlock *node, *tmp;
347 MemList *tmpused, *tmpfree;
348
349
350
351 g_assert_cmphex(src->start, ==, dst->start);
352 g_assert_cmphex(src->end, ==, dst->end);
353
354
355 QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
356 g_free(node);
357 }
358 QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
359 g_free(node);
360 }
361
362 tmpused = dst->used;
363 tmpfree = dst->free;
364
365
366 dst->used = src->used;
367 dst->free = src->free;
368
369
370 src->used = tmpused;
371 src->free = tmpfree;
372 QTAILQ_INIT(src->used);
373 QTAILQ_INIT(src->free);
374 node = mlist_new(src->start, src->end - src->start);
375 QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
376 return;
377}
378