]>
git.proxmox.com Git - mirror_qemu.git/blob - tests/qtest/libqos/malloc.c
2 * libqos malloc support
7 * John Snow <jsnow@redhat.com>
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.
13 #include "qemu/osdep.h"
15 #include "qemu/host-utils.h"
17 typedef struct MemBlock
{
18 QTAILQ_ENTRY(MemBlock
) MLIST_ENTNAME
;
23 #define DEFAULT_PAGE_SIZE 4096
25 static void mlist_delete(MemList
*list
, MemBlock
*node
)
27 g_assert(list
&& node
);
28 QTAILQ_REMOVE(list
, node
, MLIST_ENTNAME
);
32 static MemBlock
*mlist_find_key(MemList
*head
, uint64_t addr
)
35 QTAILQ_FOREACH(node
, head
, MLIST_ENTNAME
) {
36 if (node
->addr
== addr
) {
43 static MemBlock
*mlist_find_space(MemList
*head
, uint64_t size
)
47 QTAILQ_FOREACH(node
, head
, MLIST_ENTNAME
) {
48 if (node
->size
>= size
) {
55 static MemBlock
*mlist_sort_insert(MemList
*head
, MemBlock
*insr
)
58 g_assert(head
&& insr
);
60 QTAILQ_FOREACH(node
, head
, MLIST_ENTNAME
) {
61 if (insr
->addr
< node
->addr
) {
62 QTAILQ_INSERT_BEFORE(node
, insr
, MLIST_ENTNAME
);
67 QTAILQ_INSERT_TAIL(head
, insr
, MLIST_ENTNAME
);
71 static inline uint64_t mlist_boundary(MemBlock
*node
)
73 return node
->size
+ node
->addr
;
76 static MemBlock
*mlist_join(MemList
*head
, MemBlock
*left
, MemBlock
*right
)
78 g_assert(head
&& left
&& right
);
80 left
->size
+= right
->size
;
81 mlist_delete(head
, right
);
85 static void mlist_coalesce(MemList
*head
, MemBlock
*node
)
94 left
= QTAILQ_PREV(node
, MLIST_ENTNAME
);
95 right
= QTAILQ_NEXT(node
, MLIST_ENTNAME
);
97 /* clowns to the left of me */
98 if (left
&& mlist_boundary(left
) == node
->addr
) {
99 node
= mlist_join(head
, left
, node
);
103 /* jokers to the right */
104 if (right
&& mlist_boundary(node
) == right
->addr
) {
105 node
= mlist_join(head
, node
, right
);
112 static MemBlock
*mlist_new(uint64_t addr
, uint64_t size
)
119 block
= g_new0(MemBlock
, 1);
127 static uint64_t mlist_fulfill(QGuestAllocator
*s
, MemBlock
*freenode
,
134 g_assert_cmpint(freenode
->size
, >=, size
);
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
);
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
);
148 mlist_sort_insert(s
->used
, usednode
);
152 /* To assert the correctness of the list.
153 * Used only if ALLOC_PARANOID is set. */
154 static void mlist_check(QGuestAllocator
*s
)
157 uint64_t addr
= s
->start
> 0 ? s
->start
- 1 : 0;
158 uint64_t next
= s
->start
;
160 QTAILQ_FOREACH(node
, s
->free
, MLIST_ENTNAME
) {
161 g_assert_cmpint(node
->addr
, >, addr
);
162 g_assert_cmpint(node
->addr
, >=, next
);
164 next
= node
->addr
+ node
->size
;
167 addr
= s
->start
> 0 ? s
->start
- 1 : 0;
169 QTAILQ_FOREACH(node
, s
->used
, MLIST_ENTNAME
) {
170 g_assert_cmpint(node
->addr
, >, addr
);
171 g_assert_cmpint(node
->addr
, >=, next
);
173 next
= node
->addr
+ node
->size
;
177 static uint64_t mlist_alloc(QGuestAllocator
*s
, uint64_t size
)
181 node
= mlist_find_space(s
->free
, size
);
183 fprintf(stderr
, "Out of guest memory.\n");
184 g_assert_not_reached();
186 return mlist_fulfill(s
, node
, size
);
189 static void mlist_free(QGuestAllocator
*s
, uint64_t addr
)
197 node
= mlist_find_key(s
->used
, addr
);
199 fprintf(stderr
, "Error: no record found for an allocation at "
200 "0x%016" PRIx64
".\n",
202 g_assert_not_reached();
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
);
212 * Mostly for valgrind happiness, but it does offer
213 * a chokepoint for debugging guest memory leaks, too.
215 void alloc_destroy(QGuestAllocator
*allocator
)
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
);
228 if (allocator
->opts
& (ALLOC_LEAK_ASSERT
)) {
229 g_assert_not_reached();
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();
249 g_free(allocator
->used
);
250 g_free(allocator
->free
);
253 uint64_t guest_alloc(QGuestAllocator
*allocator
, size_t size
)
255 uint64_t rsize
= size
;
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
);
267 naddr
= mlist_alloc(allocator
, rsize
);
268 if (allocator
->opts
& ALLOC_PARANOID
) {
269 mlist_check(allocator
);
275 void guest_free(QGuestAllocator
*allocator
, uint64_t addr
)
280 mlist_free(allocator
, addr
);
281 if (allocator
->opts
& ALLOC_PARANOID
) {
282 mlist_check(allocator
);
286 void alloc_init(QGuestAllocator
*s
, QAllocOpts opts
,
287 uint64_t start
, uint64_t end
,
296 s
->used
= g_new(MemList
, 1);
297 s
->free
= g_new(MemList
, 1);
298 QTAILQ_INIT(s
->used
);
299 QTAILQ_INIT(s
->free
);
301 node
= mlist_new(s
->start
, s
->end
- s
->start
);
302 QTAILQ_INSERT_HEAD(s
->free
, node
, MLIST_ENTNAME
);
304 s
->page_size
= page_size
;
307 void alloc_set_flags(QGuestAllocator
*allocator
, QAllocOpts opts
)
309 allocator
->opts
|= opts
;
312 void migrate_allocator(QGuestAllocator
*src
,
313 QGuestAllocator
*dst
)
315 MemBlock
*node
, *tmp
;
316 MemList
*tmpused
, *tmpfree
;
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
);
323 /* Destroy (silently, regardless of options) the dest-list: */
324 QTAILQ_FOREACH_SAFE(node
, dst
->used
, MLIST_ENTNAME
, tmp
) {
327 QTAILQ_FOREACH_SAFE(node
, dst
->free
, MLIST_ENTNAME
, tmp
) {
334 /* Inherit the lists of the source allocator: */
335 dst
->used
= src
->used
;
336 dst
->free
= src
->free
;
338 /* Source is now re-initialized, the source memory is 'invalid' now: */
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
);