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