Vladimir Chtchetkine | 5389aa1 | 2010-02-16 10:38:35 -0800 | [diff] [blame] | 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 | |
Vladimir Chtchetkine | 5389aa1 | 2010-02-16 10:38:35 -0800 | [diff] [blame] | 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 | } |