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 */
32 extern int memcheck_instrument_mmu;
33
34 /* Allocation descriptor stored in the map. */
35 typedef 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 */
55 static inline target_ulong
allocmapentry_alloc_begins(const AllocMapEntry * adesc)56 allocmapentry_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 */
68 static inline target_ulong
allocmapentry_alloc_ends(const AllocMapEntry * adesc)69 allocmapentry_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 */
88 static inline int
cmp_rb(AllocMapEntry * d1,AllocMapEntry * d2)89 cmp_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. */
101 RB_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 */
111 static RBTMapResult
allocmap_insert_desc(AllocMap * map,AllocMapEntry * adesc,MallocDescEx * replaced)112 allocmap_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 */
145 static inline AllocMapEntry*
allocmap_find_entry(const AllocMap * map,target_ulong address,uint32_t block_size)146 allocmap_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
162 void
allocmap_init(AllocMap * map)163 allocmap_init(AllocMap* map)
164 {
165 RB_INIT(map);
166 }
167
168 RBTMapResult
allocmap_insert(AllocMap * map,const MallocDescEx * desc,MallocDescEx * replaced)169 allocmap_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
192 MallocDescEx*
allocmap_find(const AllocMap * map,target_ulong address,uint32_t block_size)193 allocmap_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
199 int
allocmap_pull(AllocMap * map,target_ulong address,MallocDescEx * pulled)200 allocmap_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
213 int
allocmap_pull_first(AllocMap * map,MallocDescEx * pulled)214 allocmap_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
227 int
allocmap_copy(AllocMap * to,const AllocMap * from,uint32_t set_flags,uint32_t clear_flags)228 allocmap_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
275 int
allocmap_empty(AllocMap * map)276 allocmap_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