1/* Copyright (C) 2007-2010 The Android Open Source Project
2**
3** This software is licensed under the terms of the GNU General Public
4** License version 2, as published by the Free Software Foundation, and
5** may be copied, distributed, and modified under those terms.
6**
7** This program is distributed in the hope that it will be useful,
8** but WITHOUT ANY WARRANTY; without even the implied warranty of
9** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10** GNU General Public License for more details.
11*/
12
13/*
14 * Contains implementation of routines that implement a red-black tree of
15 * memory blocks allocated by the guest system.
16 */
17
18/* This file should compile iff qemu is built with memory checking
19 * configuration turned on. */
20#ifndef CONFIG_MEMCHECK
21#error CONFIG_MEMCHECK is not defined.
22#endif  // CONFIG_MEMCHECK
23
24#include "memcheck_malloc_map.h"
25#include "memcheck_util.h"
26#include "memcheck_logging.h"
27
28/* Global flag, indicating whether or not __ld/__stx_mmu should be instrumented
29 * for checking for access violations. If read / write access violation check.
30 * Defined in memcheck.c
31 */
32extern int memcheck_instrument_mmu;
33
34/* Allocation descriptor stored in the map. */
35typedef struct AllocMapEntry {
36    /* R-B tree entry. */
37    RB_ENTRY(AllocMapEntry) rb_entry;
38
39    /* Allocation descriptor for this entry. */
40    MallocDescEx            desc;
41} AllocMapEntry;
42
43// =============================================================================
44// Inlines
45// =============================================================================
46
47/* Gets address of the beginning of an allocation block for the given entry in
48 * the map.
49 * Param:
50 *  adesc - Entry in the allocation descriptors map.
51 * Return:
52 *  Address of the beginning of an allocation block for the given entry in the
53 *  map.
54 */
55static inline target_ulong
56allocmapentry_alloc_begins(const AllocMapEntry* adesc)
57{
58    return adesc->desc.malloc_desc.ptr;
59}
60
61/* Gets address of the end of an allocation block for the given entry in
62 * the map.
63 * Param:
64 *  adesc - Entry in the allocation descriptors map.
65 * Return:
66 *  Address of the end of an allocation block for the given entry in the map.
67 */
68static inline target_ulong
69allocmapentry_alloc_ends(const AllocMapEntry* adesc)
70{
71    return mallocdesc_get_alloc_end(&adesc->desc.malloc_desc);
72}
73
74// =============================================================================
75// R-B Tree implementation
76// =============================================================================
77
78/* Compare routine for the allocation descriptors map.
79 * Param:
80 *  d1 - First map entry to compare.
81 *  d2 - Second map entry to compare.
82 * Return:
83 *  0 - Descriptors are equal. Note that descriptors are considered to be
84 *      equal iff memory blocks they describe intersect in any part.
85 *  1 - d1 is greater than d2
86 *  -1 - d1 is less than d2.
87 */
88static inline int
89cmp_rb(AllocMapEntry* d1, AllocMapEntry* d2)
90{
91    const target_ulong start1 = allocmapentry_alloc_begins(d1);
92    const target_ulong start2 = allocmapentry_alloc_begins(d2);
93
94    if (start1 < start2) {
95        return (allocmapentry_alloc_ends(d1) - 1) < start2 ? -1 : 0;
96    }
97    return (allocmapentry_alloc_ends(d2) - 1) < start1 ? 1 : 0;
98}
99
100/* Expands RB macros here. */
101RB_GENERATE(AllocMap, AllocMapEntry, rb_entry, cmp_rb);
102
103// =============================================================================
104// Static routines
105// =============================================================================
106
107/* Inserts new (or replaces existing) entry into allocation descriptors map.
108 * See comments on allocmap_insert routine in the header file for details
109 * about this routine.
110 */
111static RBTMapResult
112allocmap_insert_desc(AllocMap* map,
113                     AllocMapEntry* adesc,
114                     MallocDescEx* replaced)
115{
116    AllocMapEntry* existing = AllocMap_RB_INSERT(map, adesc);
117    if (existing == NULL) {
118        return RBT_MAP_RESULT_ENTRY_INSERTED;
119    }
120
121    // Matching entry exists. Lets see if we need to replace it.
122    if (replaced == NULL) {
123        return RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS;
124    }
125
126    /* Copy existing entry to the provided buffer and replace it
127     * with the new one. */
128    memcpy(replaced, &existing->desc, sizeof(MallocDescEx));
129    AllocMap_RB_REMOVE(map, existing);
130    qemu_free(existing);
131    AllocMap_RB_INSERT(map, adesc);
132    return RBT_MAP_RESULT_ENTRY_REPLACED;
133}
134
135/* Finds an entry in the allocation descriptors map that matches the given
136 * address range.
137 * Param:
138 *  map - Allocation descriptors map where to search for an entry.
139 *  address - Virtual address in the guest's user space to find matching
140 *      entry for.
141 * Return:
142 *  Address of an allocation descriptors map entry that matches the given
143 *  address, or NULL if no such entry has been found.
144 */
145static inline AllocMapEntry*
146allocmap_find_entry(const AllocMap* map,
147                    target_ulong address,
148                    uint32_t block_size)
149{
150    AllocMapEntry adesc;
151    adesc.desc.malloc_desc.ptr = address;
152    adesc.desc.malloc_desc.requested_bytes = block_size;
153    adesc.desc.malloc_desc.prefix_size = 0;
154    adesc.desc.malloc_desc.suffix_size = 0;
155    return AllocMap_RB_FIND((AllocMap*)map, &adesc);
156}
157
158// =============================================================================
159// Map API
160// =============================================================================
161
162void
163allocmap_init(AllocMap* map)
164{
165    RB_INIT(map);
166}
167
168RBTMapResult
169allocmap_insert(AllocMap* map, const MallocDescEx* desc, MallocDescEx* replaced)
170{
171    RBTMapResult ret;
172
173    // Allocate and initialize new map entry.
174    AllocMapEntry* adesc = qemu_malloc(sizeof(AllocMapEntry));
175    if (adesc == NULL) {
176        ME("memcheck: Unable to allocate new AllocMapEntry on insert.");
177        return RBT_MAP_RESULT_ERROR;
178    }
179    memcpy(&adesc->desc, desc, sizeof(MallocDescEx));
180
181    // Insert new entry into the map.
182    ret = allocmap_insert_desc(map, adesc, replaced);
183    if (ret == RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS ||
184        ret == RBT_MAP_RESULT_ERROR) {
185        /* Another descriptor already exists for this block, or an error
186         * occurred. We have to tree new descriptor, as it wasn't inserted. */
187        qemu_free(adesc);
188    }
189    return ret;
190}
191
192MallocDescEx*
193allocmap_find(const AllocMap* map, target_ulong address, uint32_t block_size)
194{
195    AllocMapEntry* adesc = allocmap_find_entry(map, address, block_size);
196    return adesc != NULL ? &adesc->desc : NULL;
197}
198
199int
200allocmap_pull(AllocMap* map, target_ulong address, MallocDescEx* pulled)
201{
202    AllocMapEntry* adesc = allocmap_find_entry(map, address, 1);
203    if (adesc != NULL) {
204        memcpy(pulled, &adesc->desc, sizeof(MallocDescEx));
205        AllocMap_RB_REMOVE(map, adesc);
206        qemu_free(adesc);
207        return 0;
208    } else {
209        return -1;
210    }
211}
212
213int
214allocmap_pull_first(AllocMap* map, MallocDescEx* pulled)
215{
216    AllocMapEntry* first = RB_MIN(AllocMap, map);
217    if (first != NULL) {
218        memcpy(pulled, &first->desc, sizeof(MallocDescEx));
219        AllocMap_RB_REMOVE(map, first);
220        qemu_free(first);
221        return 0;
222    } else {
223        return -1;
224    }
225}
226
227int
228allocmap_copy(AllocMap* to,
229              const AllocMap* from,
230              uint32_t set_flags,
231              uint32_t clear_flags)
232{
233    AllocMapEntry* entry;
234    RB_FOREACH(entry, AllocMap, (AllocMap*)from) {
235        RBTMapResult ins_res;
236        AllocMapEntry* new_entry =
237                (AllocMapEntry*)qemu_malloc(sizeof(AllocMapEntry));
238        if (new_entry == NULL) {
239            ME("memcheck: Unable to allocate new AllocMapEntry on copy.");
240            return -1;
241        }
242        memcpy(new_entry, entry, sizeof(AllocMapEntry));
243        new_entry->desc.flags &= ~clear_flags;
244        new_entry->desc.flags |= set_flags;
245        if (entry->desc.call_stack_count) {
246            new_entry->desc.call_stack =
247               qemu_malloc(entry->desc.call_stack_count * sizeof(target_ulong));
248            memcpy(new_entry->desc.call_stack, entry->desc.call_stack,
249                   entry->desc.call_stack_count * sizeof(target_ulong));
250        } else {
251            new_entry->desc.call_stack = NULL;
252        }
253        new_entry->desc.call_stack_count = entry->desc.call_stack_count;
254        ins_res = allocmap_insert_desc(to, new_entry, NULL);
255        if (ins_res == RBT_MAP_RESULT_ENTRY_INSERTED) {
256            if (memcheck_instrument_mmu) {
257                // Invalidate TLB cache for inserted entry.
258                invalidate_tlb_cache(new_entry->desc.malloc_desc.ptr,
259                        mallocdesc_get_alloc_end(&new_entry->desc.malloc_desc));
260            }
261        } else {
262            ME("memcheck: Unable to insert new map entry on copy. Insert returned %u",
263               ins_res);
264            if (new_entry->desc.call_stack != NULL) {
265                qemu_free(new_entry->desc.call_stack);
266            }
267            qemu_free(new_entry);
268            return -1;
269        }
270    }
271
272    return 0;
273}
274
275int
276allocmap_empty(AllocMap* map)
277{
278    MallocDescEx pulled;
279    int removed = 0;
280
281    while (!allocmap_pull_first(map, &pulled)) {
282        removed++;
283        if (pulled.call_stack != NULL) {
284            qemu_free(pulled.call_stack);
285        }
286    }
287
288    return removed;
289}
290