1 /*
2 * libqos malloc support
3 *
4 * Copyright (c) 2014
5 *
6 * Author:
7 * John Snow <jsnow@redhat.com>
8 *
9 * This work is licensed under the terms of the GNU GPL, version 2 or later.
10 * See the COPYING file in the top-level directory.
11 */
12
13 #include "qemu/osdep.h"
14 #include "libqos-malloc.h"
15 #include "qemu/host-utils.h"
16
17 typedef struct MemBlock {
18 QTAILQ_ENTRY(MemBlock) MLIST_ENTNAME;
19 uint64_t size;
20 uint64_t addr;
21 } MemBlock;
22
23 #define DEFAULT_PAGE_SIZE 4096
24
mlist_delete(MemList * list,MemBlock * node)25 static void mlist_delete(MemList *list, MemBlock *node)
26 {
27 g_assert(list && node);
28 QTAILQ_REMOVE(list, node, MLIST_ENTNAME);
29 g_free(node);
30 }
31
mlist_find_key(MemList * head,uint64_t addr)32 static MemBlock *mlist_find_key(MemList *head, uint64_t addr)
33 {
34 MemBlock *node;
35 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
36 if (node->addr == addr) {
37 return node;
38 }
39 }
40 return NULL;
41 }
42
mlist_find_space(MemList * head,uint64_t size)43 static MemBlock *mlist_find_space(MemList *head, uint64_t size)
44 {
45 MemBlock *node;
46
47 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
48 if (node->size >= size) {
49 return node;
50 }
51 }
52 return NULL;
53 }
54
mlist_sort_insert(MemList * head,MemBlock * insr)55 static MemBlock *mlist_sort_insert(MemList *head, MemBlock *insr)
56 {
57 MemBlock *node;
58 g_assert(head && insr);
59
60 QTAILQ_FOREACH(node, head, MLIST_ENTNAME) {
61 if (insr->addr < node->addr) {
62 QTAILQ_INSERT_BEFORE(node, insr, MLIST_ENTNAME);
63 return insr;
64 }
65 }
66
67 QTAILQ_INSERT_TAIL(head, insr, MLIST_ENTNAME);
68 return insr;
69 }
70
mlist_boundary(MemBlock * node)71 static inline uint64_t mlist_boundary(MemBlock *node)
72 {
73 return node->size + node->addr;
74 }
75
mlist_join(MemList * head,MemBlock * left,MemBlock * right)76 static MemBlock *mlist_join(MemList *head, MemBlock *left, MemBlock *right)
77 {
78 g_assert(head && left && right);
79
80 left->size += right->size;
81 mlist_delete(head, right);
82 return left;
83 }
84
mlist_coalesce(MemList * head,MemBlock * node)85 static void mlist_coalesce(MemList *head, MemBlock *node)
86 {
87 g_assert(node);
88 MemBlock *left;
89 MemBlock *right;
90 char merge;
91
92 do {
93 merge = 0;
94 left = QTAILQ_PREV(node, MLIST_ENTNAME);
95 right = QTAILQ_NEXT(node, MLIST_ENTNAME);
96
97 /* clowns to the left of me */
98 if (left && mlist_boundary(left) == node->addr) {
99 node = mlist_join(head, left, node);
100 merge = 1;
101 }
102
103 /* jokers to the right */
104 if (right && mlist_boundary(node) == right->addr) {
105 node = mlist_join(head, node, right);
106 merge = 1;
107 }
108
109 } while (merge);
110 }
111
mlist_new(uint64_t addr,uint64_t size)112 static MemBlock *mlist_new(uint64_t addr, uint64_t size)
113 {
114 MemBlock *block;
115
116 if (!size) {
117 return NULL;
118 }
119 block = g_new0(MemBlock, 1);
120
121 block->addr = addr;
122 block->size = size;
123
124 return block;
125 }
126
mlist_fulfill(QGuestAllocator * s,MemBlock * freenode,uint64_t size)127 static uint64_t mlist_fulfill(QGuestAllocator *s, MemBlock *freenode,
128 uint64_t size)
129 {
130 uint64_t addr;
131 MemBlock *usednode;
132
133 g_assert(freenode);
134 g_assert_cmpint(freenode->size, >=, size);
135
136 addr = freenode->addr;
137 if (freenode->size == size) {
138 /* re-use this freenode as our used node */
139 QTAILQ_REMOVE(s->free, freenode, MLIST_ENTNAME);
140 usednode = freenode;
141 } else {
142 /* adjust the free node and create a new used node */
143 freenode->addr += size;
144 freenode->size -= size;
145 usednode = mlist_new(addr, size);
146 }
147
148 mlist_sort_insert(s->used, usednode);
149 return addr;
150 }
151
152 /* To assert the correctness of the list.
153 * Used only if ALLOC_PARANOID is set. */
mlist_check(QGuestAllocator * s)154 static void mlist_check(QGuestAllocator *s)
155 {
156 MemBlock *node;
157 uint64_t addr = s->start > 0 ? s->start - 1 : 0;
158 uint64_t next = s->start;
159
160 QTAILQ_FOREACH(node, s->free, MLIST_ENTNAME) {
161 g_assert_cmpint(node->addr, >, addr);
162 g_assert_cmpint(node->addr, >=, next);
163 addr = node->addr;
164 next = node->addr + node->size;
165 }
166
167 addr = s->start > 0 ? s->start - 1 : 0;
168 next = s->start;
169 QTAILQ_FOREACH(node, s->used, MLIST_ENTNAME) {
170 g_assert_cmpint(node->addr, >, addr);
171 g_assert_cmpint(node->addr, >=, next);
172 addr = node->addr;
173 next = node->addr + node->size;
174 }
175 }
176
mlist_alloc(QGuestAllocator * s,uint64_t size)177 static uint64_t mlist_alloc(QGuestAllocator *s, uint64_t size)
178 {
179 MemBlock *node;
180
181 node = mlist_find_space(s->free, size);
182 if (!node) {
183 fprintf(stderr, "Out of guest memory.\n");
184 g_assert_not_reached();
185 }
186 return mlist_fulfill(s, node, size);
187 }
188
mlist_free(QGuestAllocator * s,uint64_t addr)189 static void mlist_free(QGuestAllocator *s, uint64_t addr)
190 {
191 MemBlock *node;
192
193 if (addr == 0) {
194 return;
195 }
196
197 node = mlist_find_key(s->used, addr);
198 if (!node) {
199 fprintf(stderr, "Error: no record found for an allocation at "
200 "0x%016" PRIx64 ".\n",
201 addr);
202 g_assert_not_reached();
203 }
204
205 /* Rip it out of the used list and re-insert back into the free list. */
206 QTAILQ_REMOVE(s->used, node, MLIST_ENTNAME);
207 mlist_sort_insert(s->free, node);
208 mlist_coalesce(s->free, node);
209 }
210
211 /*
212 * Mostly for valgrind happiness, but it does offer
213 * a chokepoint for debugging guest memory leaks, too.
214 */
alloc_destroy(QGuestAllocator * allocator)215 void alloc_destroy(QGuestAllocator *allocator)
216 {
217 MemBlock *node;
218 MemBlock *tmp;
219 QAllocOpts mask;
220
221 /* Check for guest leaks, and destroy the list. */
222 QTAILQ_FOREACH_SAFE(node, allocator->used, MLIST_ENTNAME, tmp) {
223 if (allocator->opts & (ALLOC_LEAK_WARN | ALLOC_LEAK_ASSERT)) {
224 fprintf(stderr, "guest malloc leak @ 0x%016" PRIx64 "; "
225 "size 0x%016" PRIx64 ".\n",
226 node->addr, node->size);
227 }
228 if (allocator->opts & (ALLOC_LEAK_ASSERT)) {
229 g_assert_not_reached();
230 }
231 g_free(node);
232 }
233
234 /* If we have previously asserted that there are no leaks, then there
235 * should be only one node here with a specific address and size. */
236 mask = ALLOC_LEAK_ASSERT | ALLOC_PARANOID;
237 QTAILQ_FOREACH_SAFE(node, allocator->free, MLIST_ENTNAME, tmp) {
238 if ((allocator->opts & mask) == mask) {
239 if ((node->addr != allocator->start) ||
240 (node->size != allocator->end - allocator->start)) {
241 fprintf(stderr, "Free list is corrupted.\n");
242 g_assert_not_reached();
243 }
244 }
245
246 g_free(node);
247 }
248
249 g_free(allocator->used);
250 g_free(allocator->free);
251 }
252
guest_alloc(QGuestAllocator * allocator,size_t size)253 uint64_t guest_alloc(QGuestAllocator *allocator, size_t size)
254 {
255 uint64_t rsize = size;
256 uint64_t naddr;
257
258 if (!size) {
259 return 0;
260 }
261
262 rsize += (allocator->page_size - 1);
263 rsize &= -allocator->page_size;
264 g_assert_cmpint((allocator->start + rsize), <=, allocator->end);
265 g_assert_cmpint(rsize, >=, size);
266
267 naddr = mlist_alloc(allocator, rsize);
268 if (allocator->opts & ALLOC_PARANOID) {
269 mlist_check(allocator);
270 }
271
272 return naddr;
273 }
274
guest_free(QGuestAllocator * allocator,uint64_t addr)275 void guest_free(QGuestAllocator *allocator, uint64_t addr)
276 {
277 if (!addr) {
278 return;
279 }
280 mlist_free(allocator, addr);
281 if (allocator->opts & ALLOC_PARANOID) {
282 mlist_check(allocator);
283 }
284 }
285
alloc_init(QGuestAllocator * s,QAllocOpts opts,uint64_t start,uint64_t end,size_t page_size)286 void alloc_init(QGuestAllocator *s, QAllocOpts opts,
287 uint64_t start, uint64_t end,
288 size_t page_size)
289 {
290 MemBlock *node;
291
292 s->opts = opts;
293 s->start = start;
294 s->end = end;
295
296 s->used = g_new(MemList, 1);
297 s->free = g_new(MemList, 1);
298 QTAILQ_INIT(s->used);
299 QTAILQ_INIT(s->free);
300
301 node = mlist_new(s->start, s->end - s->start);
302 QTAILQ_INSERT_HEAD(s->free, node, MLIST_ENTNAME);
303
304 s->page_size = page_size;
305 }
306
alloc_set_flags(QGuestAllocator * allocator,QAllocOpts opts)307 void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
308 {
309 allocator->opts |= opts;
310 }
311
migrate_allocator(QGuestAllocator * src,QGuestAllocator * dst)312 void migrate_allocator(QGuestAllocator *src,
313 QGuestAllocator *dst)
314 {
315 MemBlock *node, *tmp;
316 MemList *tmpused, *tmpfree;
317
318 /* The general memory layout should be equivalent,
319 * though opts can differ. */
320 g_assert_cmphex(src->start, ==, dst->start);
321 g_assert_cmphex(src->end, ==, dst->end);
322
323 /* Destroy (silently, regardless of options) the dest-list: */
324 QTAILQ_FOREACH_SAFE(node, dst->used, MLIST_ENTNAME, tmp) {
325 g_free(node);
326 }
327 QTAILQ_FOREACH_SAFE(node, dst->free, MLIST_ENTNAME, tmp) {
328 g_free(node);
329 }
330
331 tmpused = dst->used;
332 tmpfree = dst->free;
333
334 /* Inherit the lists of the source allocator: */
335 dst->used = src->used;
336 dst->free = src->free;
337
338 /* Source is now re-initialized, the source memory is 'invalid' now: */
339 src->used = tmpused;
340 src->free = tmpfree;
341 QTAILQ_INIT(src->used);
342 QTAILQ_INIT(src->free);
343 node = mlist_new(src->start, src->end - src->start);
344 QTAILQ_INSERT_HEAD(src->free, node, MLIST_ENTNAME);
345 return;
346 }
347