| /* 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. |
| */ |
| |
| #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; |
| } |