diff options
Diffstat (limited to 'memcheck/memcheck_mmrange_map.c')
| -rw-r--r-- | memcheck/memcheck_mmrange_map.c | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/memcheck/memcheck_mmrange_map.c b/memcheck/memcheck_mmrange_map.c new file mode 100644 index 0000000..f2609df --- /dev/null +++ b/memcheck/memcheck_mmrange_map.c @@ -0,0 +1,236 @@ +/* Copyright (C) 2007-2010 The Android Open Source Project +** +** This software is licensed under the terms of the GNU General Public +** License version 2, as published by the Free Software Foundation, and +** may be copied, distributed, and modified under those terms. +** +** This program is distributed in the hope that it will be useful, +** but WITHOUT ANY WARRANTY; without even the implied warranty of +** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +** GNU General Public License for more details. +*/ + +/* + * Contains implementation of routines that implement a red-black tree of + * memory mappings in the guest system. + */ + +/* This file should compile iff qemu is built with memory checking + * configuration turned on. */ +#ifndef CONFIG_MEMCHECK +#error CONFIG_MEMCHECK is not defined. +#endif // CONFIG_MEMCHECK + +#include "memcheck_mmrange_map.h" +#include "memcheck_logging.h" + +/* Memory range descriptor stored in the map. */ +typedef struct MMRangeMapEntry { + /* R-B tree entry. */ + RB_ENTRY(MMRangeMapEntry) rb_entry; + + /* Memory range descriptor for this entry. */ + MMRangeDesc desc; +} MMRangeMapEntry; + +// ============================================================================= +// R-B Tree implementation +// ============================================================================= + +/* Compare routine for the map. + * Param: + * d1 - First map entry to compare. + * d2 - Second map entry to compare. + * Return: + * 0 - Descriptors are equal. Note that descriptors are considered to be + * equal iff memory blocks they describe intersect in any part. + * 1 - d1 is greater than d2 + * -1 - d1 is less than d2. + */ +static inline int +cmp_rb(MMRangeMapEntry* d1, MMRangeMapEntry* d2) +{ + const target_ulong start1 = d1->desc.map_start; + const target_ulong start2 = d2->desc.map_start; + + if (start1 < start2) { + return (d1->desc.map_end - 1) < start2 ? -1 : 0; + } + return (d2->desc.map_end - 1) < start1 ? 1 : 0; +} + +/* Expands RB macros here. */ +RB_GENERATE(MMRangeMap, MMRangeMapEntry, rb_entry, cmp_rb); + +// ============================================================================= +// Static routines +// ============================================================================= + +/* Inserts new (or replaces existing) entry into the map. + * See comments on mmrangemap_insert routine in the header file for details + * about this routine. + */ +static RBTMapResult +mmrangemap_insert_desc(MMRangeMap* map, + MMRangeMapEntry* rdesc, + MMRangeDesc* replaced) +{ + MMRangeMapEntry* existing = MMRangeMap_RB_INSERT(map, rdesc); + if (existing == NULL) { + return RBT_MAP_RESULT_ENTRY_INSERTED; + } + + // Matching entry exists. Lets see if we need to replace it. + if (replaced == NULL) { + return RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS; + } + + /* Copy existing entry to the provided buffer and replace it + * with the new one. */ + memcpy(replaced, &existing->desc, sizeof(MMRangeDesc)); + MMRangeMap_RB_REMOVE(map, existing); + qemu_free(existing); + MMRangeMap_RB_INSERT(map, rdesc); + return RBT_MAP_RESULT_ENTRY_REPLACED; +} + +/* Finds an entry in the map that matches the given address range. + * Param: + * map - Map where to search for an entry. + * start - Starting address of a mapping range. + * end - Ending address of a mapping range. + * Return: + * Address of a map entry that matches the given range, or NULL if no + * such entry has been found. + */ +static inline MMRangeMapEntry* +mmrangemap_find_entry(const MMRangeMap* map, + target_ulong start, + target_ulong end) +{ + MMRangeMapEntry rdesc; + rdesc.desc.map_start = start; + rdesc.desc.map_end = end; + return MMRangeMap_RB_FIND((MMRangeMap*)map, &rdesc); +} + +// ============================================================================= +// Map API +// ============================================================================= + +void +mmrangemap_init(MMRangeMap* map) +{ + RB_INIT(map); +} + +RBTMapResult +mmrangemap_insert(MMRangeMap* map, + const MMRangeDesc* desc, + MMRangeDesc* replaced) +{ + RBTMapResult ret; + + // Allocate and initialize new map entry. + MMRangeMapEntry* rdesc = qemu_malloc(sizeof(MMRangeMapEntry)); + if (rdesc == NULL) { + ME("memcheck: Unable to allocate new MMRangeMapEntry on insert."); + return RBT_MAP_RESULT_ERROR; + } + memcpy(&rdesc->desc, desc, sizeof(MMRangeDesc)); + + // Insert new entry into the map. + ret = mmrangemap_insert_desc(map, rdesc, replaced); + if (ret == RBT_MAP_RESULT_ENTRY_ALREADY_EXISTS || + ret == RBT_MAP_RESULT_ERROR) { + /* Another descriptor already exists for this block, or an error + * occurred. We have to free new descriptor, as it wasn't inserted. */ + qemu_free(rdesc); + } + return ret; +} + +MMRangeDesc* +mmrangemap_find(const MMRangeMap* map, target_ulong start, target_ulong end) +{ + MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end); + return rdesc != NULL ? &rdesc->desc : NULL; +} + +int +mmrangemap_pull(MMRangeMap* map, + target_ulong start, + target_ulong end, + MMRangeDesc* pulled) +{ + MMRangeMapEntry* rdesc = mmrangemap_find_entry(map, start, end); + if (rdesc != NULL) { + memcpy(pulled, &rdesc->desc, sizeof(MMRangeDesc)); + MMRangeMap_RB_REMOVE(map, rdesc); + qemu_free(rdesc); + return 0; + } else { + return -1; + } +} + +int +mmrangemap_pull_first(MMRangeMap* map, MMRangeDesc* pulled) +{ + MMRangeMapEntry* first = RB_MIN(MMRangeMap, map); + if (first != NULL) { + memcpy(pulled, &first->desc, sizeof(MMRangeDesc)); + MMRangeMap_RB_REMOVE(map, first); + qemu_free(first); + return 0; + } else { + return -1; + } +} + +int +mmrangemap_copy(MMRangeMap* to, const MMRangeMap* from) +{ + MMRangeMapEntry* entry; + RB_FOREACH(entry, MMRangeMap, (MMRangeMap*)from) { + RBTMapResult ins_res; + MMRangeMapEntry* new_entry = + (MMRangeMapEntry*)qemu_malloc(sizeof(MMRangeMapEntry)); + if (new_entry == NULL) { + ME("memcheck: Unable to allocate new MMRangeMapEntry on copy."); + return -1; + } + memcpy(new_entry, entry, sizeof(MMRangeMapEntry)); + new_entry->desc.path = qemu_malloc(strlen(entry->desc.path) + 1); + if (new_entry->desc.path == NULL) { + ME("memcheck: Unable to allocate new path for MMRangeMapEntry on copy."); + qemu_free(new_entry); + return -1; + } + strcpy(new_entry->desc.path, entry->desc.path); + ins_res = mmrangemap_insert_desc(to, new_entry, NULL); + if (ins_res != RBT_MAP_RESULT_ENTRY_INSERTED) { + ME("memcheck: Unable to insert new range map entry on copy. Insert returned %u", + ins_res); + qemu_free(new_entry->desc.path); + qemu_free(new_entry); + return -1; + } + } + + return 0; +} + +int +mmrangemap_empty(MMRangeMap* map) +{ + MMRangeDesc pulled; + int removed = 0; + + while (!mmrangemap_pull_first(map, &pulled)) { + qemu_free(pulled.path); + removed++; + } + + return removed; +} |