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 #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