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