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