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 mappings in the guest system. 16 */ 17 18 #include "memcheck_mmrange_map.h" 19 #include "memcheck_logging.h" 20 21 /* Memory range descriptor stored in the map. */ 22 typedef struct MMRangeMapEntry { 23 /* R-B tree entry. */ 24 RB_ENTRY(MMRangeMapEntry) rb_entry; 25 26 /* Memory range descriptor for this entry. */ 27 MMRangeDesc desc; 28 } MMRangeMapEntry; 29 30 // ============================================================================= 31 // R-B Tree implementation 32 // ============================================================================= 33 34 /* Compare routine for the map. 35 * Param: 36 * d1 - First map entry to compare. 37 * d2 - Second map entry to compare. 38 * Return: 39 * 0 - Descriptors are equal. Note that descriptors are considered to be 40 * equal iff memory blocks they describe intersect in any part. 41 * 1 - d1 is greater than d2 42 * -1 - d1 is less than d2. 43 */ 44 static inline int 45 cmp_rb(MMRangeMapEntry* d1, MMRangeMapEntry* d2) 46 { 47 const target_ulong start1 = d1->desc.map_start; 48 const target_ulong start2 = d2->desc.map_start; 49 50 if (start1 < start2) { 51 return (d1->desc.map_end - 1) < start2 ? -1 : 0; 52 } 53 return (d2->desc.map_end - 1) < start1 ? 1 : 0; 54 } 55 56 /* Expands RB macros here. */ 57 RB_GENERATE(MMRangeMap, MMRangeMapEntry, rb_entry, cmp_rb); 58 59 // ============================================================================= 60 // Static routines 61 // ============================================================================= 62 63 /* Inserts new (or replaces existing) entry into the map. 64 * See comments on mmrangemap_insert routine in the header file for details 65 * about this routine. 66 */ 67 static RBTMapResult 68 mmrangemap_insert_desc(MMRangeMap* map, 69 MMRangeMapEntry* rdesc, 70 MMRangeDesc* replaced) 71 { 72 MMRangeMapEntry* existing = MMRangeMap_RB_INSERT(map, rdesc); 73 if (existing == NULL) { 74 return RBT_MAP_RESULT_ENTRY_INSERTED; 75 } 76 77 // Matching entry exists. Lets see if we need to replace it. 78 if (replaced == NULL) { 79 return RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS; 80 } 81 82 /* Copy existing entry to the provided buffer and replace it 83 * with the new one. */ 84 memcpy(replaced, &existing->desc, sizeof(MMRangeDesc)); 85 MMRangeMap_RB_REMOVE(map, existing); 86 qemu_free(existing); 87 MMRangeMap_RB_INSERT(map, rdesc); 88 return RBT_MAP_RESULT_ENTRY_REPLACED; 89 } 90 91 /* Finds an entry in the map that matches the given address range. 92 * Param: 93 * map - Map where to search for an entry. 94 * start - Starting address of a mapping range. 95 * end - Ending address of a mapping range. 96 * Return: 97 * Address of a map entry that matches the given range, or NULL if no 98 * such entry has been found. 99 */ 100 static inline MMRangeMapEntry* 101 mmrangemap_find_entry(const MMRangeMap* map, 102 target_ulong start, 103 target_ulong end) 104 { 105 MMRangeMapEntry rdesc; 106 rdesc.desc.map_start = start; 107 rdesc.desc.map_end = end; 108 return MMRangeMap_RB_FIND((MMRangeMap*)map, &rdesc); 109 } 110 111 // ============================================================================= 112 // Map API 113 // ============================================================================= 114 115 void 116 mmrangemap_init(MMRangeMap* map) 117 { 118 RB_INIT(map); 119 } 120 121 RBTMapResult 122 mmrangemap_insert(MMRangeMap* map, 123 const MMRangeDesc* desc, 124 MMRangeDesc* replaced) 125 { 126 RBTMapResult ret; 127 128 // Allocate and initialize new map entry. 129 MMRangeMapEntry* rdesc = qemu_malloc(sizeof(MMRangeMapEntry)); 130 if (rdesc == NULL) { 131 ME("memcheck: Unable to allocate new MMRangeMapEntry on insert."); 132 return RBT_MAP_RESULT_ERROR; 133 } 134 memcpy(&rdesc->desc, desc, sizeof(MMRangeDesc)); 135 136 // Insert new entry into the map. 137 ret = mmrangemap_insert_desc(map, rdesc, replaced); 138 if (ret == RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS || 139 ret == RBT_MAP_RESULT_ERROR) { 140 /* Another descriptor already exists for this block, or an error 141 * occurred. We have to free new descriptor, as it wasn't inserted. */ 142 qemu_free(rdesc); 143 } 144 return ret; 145 } 146 147 MMRangeDesc* 148 mmrangemap_find(const MMRangeMap* map, target_ulong start, target_ulong end) 149 { 150 MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end); 151 return rdesc != NULL ? &rdesc->desc : NULL; 152 } 153 154 int 155 mmrangemap_pull(MMRangeMap* map, 156 target_ulong start, 157 target_ulong end, 158 MMRangeDesc* pulled) 159 { 160 MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end); 161 if (rdesc != NULL) { 162 memcpy(pulled, &rdesc->desc, sizeof(MMRangeDesc)); 163 MMRangeMap_RB_REMOVE(map, rdesc); 164 qemu_free(rdesc); 165 return 0; 166 } else { 167 return -1; 168 } 169 } 170 171 int 172 mmrangemap_pull_first(MMRangeMap* map, MMRangeDesc* pulled) 173 { 174 MMRangeMapEntry* first = RB_MIN(MMRangeMap, map); 175 if (first != NULL) { 176 memcpy(pulled, &first->desc, sizeof(MMRangeDesc)); 177 MMRangeMap_RB_REMOVE(map, first); 178 qemu_free(first); 179 return 0; 180 } else { 181 return -1; 182 } 183 } 184 185 int 186 mmrangemap_copy(MMRangeMap* to, const MMRangeMap* from) 187 { 188 MMRangeMapEntry* entry; 189 RB_FOREACH(entry, MMRangeMap, (MMRangeMap*)from) { 190 RBTMapResult ins_res; 191 MMRangeMapEntry* new_entry = 192 (MMRangeMapEntry*)qemu_malloc(sizeof(MMRangeMapEntry)); 193 if (new_entry == NULL) { 194 ME("memcheck: Unable to allocate new MMRangeMapEntry on copy."); 195 return -1; 196 } 197 memcpy(new_entry, entry, sizeof(MMRangeMapEntry)); 198 new_entry->desc.path = qemu_malloc(strlen(entry->desc.path) + 1); 199 if (new_entry->desc.path == NULL) { 200 ME("memcheck: Unable to allocate new path for MMRangeMapEntry on copy."); 201 qemu_free(new_entry); 202 return -1; 203 } 204 strcpy(new_entry->desc.path, entry->desc.path); 205 ins_res = mmrangemap_insert_desc(to, new_entry, NULL); 206 if (ins_res != RBT_MAP_RESULT_ENTRY_INSERTED) { 207 ME("memcheck: Unable to insert new range map entry on copy. Insert returned %u", 208 ins_res); 209 qemu_free(new_entry->desc.path); 210 qemu_free(new_entry); 211 return -1; 212 } 213 } 214 215 return 0; 216 } 217 218 int 219 mmrangemap_empty(MMRangeMap* map) 220 { 221 MMRangeDesc pulled; 222 int removed = 0; 223 224 while (!mmrangemap_pull_first(map, &pulled)) { 225 qemu_free(pulled.path); 226 removed++; 227 } 228 229 return removed; 230 } 231