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 
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 
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 
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 
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 
71 static inline uint64_t mlist_boundary(MemBlock *node)
72 {
73     return node->size + node->addr;
74 }
75 
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 
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 
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 
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. */
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 
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 
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  */
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 
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 
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 
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 
307 void alloc_set_flags(QGuestAllocator *allocator, QAllocOpts opts)
308 {
309     allocator->opts |= opts;
310 }
311 
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