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