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 declarations of structures and routines that implement a red-black 15 * tree (a map) of memory blocks allocated by the guest system. The map is 16 * organized in such a way, that each entry in the map describes a virtual 17 * address range that belongs to a memory block allocated in the guest's space. 18 * The range includes block's suffix and prefix, as well as block returned to 19 * malloc's caller. Map considers two blocks to be equal if their address ranges 20 * intersect in any part. Allocation descriptor maps are instantiated one per 21 * each process running on the guest system. 22 */ 23 24 #ifndef QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H 25 #define QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H 26 27 #include "sys-tree.h" 28 #include "memcheck_common.h" 29 30 #ifdef __cplusplus 31 extern "C" { 32 #endif 33 34 /* Allocation descriptors map. */ 35 typedef struct AllocMap { 36 /* Head of the map. */ 37 struct AllocMapEntry* rbh_root; 38 } AllocMap; 39 40 // ============================================================================= 41 // Map API 42 // ============================================================================= 43 44 /* Initializes allocation descriptors map. 45 * Param: 46 * map - Allocation descriptors map to initialize. 47 */ 48 void allocmap_init(AllocMap* map); 49 50 /* Inserts new (or replaces existing) entry in the allocation descriptors map. 51 * Insertion, or replacement is controlled by the value, passed to this routine 52 * with 'replaced' parameter. If this parameter is NULL, insertion will fail if 53 * a matching entry already exists in the map. If 'replaced' parameter is not 54 * NULL, and a matching entry exists in the map, content of the existing entry 55 * will be copied to the descriptor, addressed by 'replace' parameter, existing 56 * entry will be removed from the map, and new entry will be inserted. 57 * Param: 58 * map - Allocation descriptors map where to insert new, or replace existing 59 * entry. 60 * desc - Allocation descriptor to insert to the map. 61 * replaced - If not NULL, upon return from this routine contains descriptor 62 * that has been replaced in the map with the new entry. Note that if this 63 * routine returns with value other than RBT_MAP_RESULT_ENTRY_REPLACED, 64 * content of the 'replaced' buffer is not defined, as no replacement has 65 * actually occurred. 66 * Return 67 * See RBTMapResult for the return codes. 68 */ 69 RBTMapResult allocmap_insert(AllocMap* map, 70 const MallocDescEx* desc, 71 MallocDescEx* replaced); 72 73 /* Finds an entry in the allocation descriptors map that matches the given 74 * address. 75 * Param: 76 * map - Allocation descriptors map where to search for an entry. 77 * address - Virtual address in the guest's user space to find matching 78 * entry for. Entry matches the address, if address is contained within 79 * allocated memory range (including guarding areas), as defined by the 80 * memory allocation descriptor for that entry. 81 * block_size - Size of the block, beginning with 'address'. 82 * Return: 83 * Pointer to the allocation descriptor found in a map entry, or NULL if no 84 * matching entry has been found in the map. 85 */ 86 MallocDescEx* allocmap_find(const AllocMap* map, 87 target_ulong address, 88 uint32_t block_size); 89 90 /* Pulls (finds and removes) an entry from the allocation descriptors map that 91 * matches the given address. 92 * Param: 93 * map - Allocation descriptors map where to search for an entry. 94 * address - Virtual address in the guest's user space to find matching 95 * entry for. Entry matches the address, if address is contained within 96 * allocated memory range (including guarding areas), as defined by the 97 * memory allocation descriptor for that entry. 98 * pulled - Upon successful return contains allocation descriptor data pulled 99 * from the map. 100 * Return: 101 * Zero if an allocation descriptor that matches the given address has 102 * been pulled, or 1 if no matching entry has been found in the map. 103 */ 104 int allocmap_pull(AllocMap* map, target_ulong address, MallocDescEx* pulled); 105 106 /* Pulls (removes) an entry from the head of the allocation descriptors map. 107 * Param: 108 * map - Allocation descriptors map where to pull an entry from. 109 * pulled - Upon successful return contains allocation descriptor data pulled 110 * from the head of the map. 111 * Return: 112 * Zero if an allocation descriptor has been pulled from the head of the map, 113 * or 1 if map is empty. 114 */ 115 int allocmap_pull_first(AllocMap* map, MallocDescEx* pulled); 116 117 /* Copies content of one memory allocation descriptors map to another. 118 * Param: 119 * to - Map where to copy entries to. 120 * from - Map where to copy entries from. 121 * set_flags - Flags that should be set in the copied entry's 'flags' field. 122 * celar_flags - Flags that should be cleared in the copied entry's 'flags' 123 * field. 124 * Return: 125 * Zero on success, or -1 on error. 126 */ 127 int allocmap_copy(AllocMap* to, 128 const AllocMap* from, 129 uint32_t set_flags, 130 uint32_t clear_flags); 131 132 /* Empties the map. 133 * Param: 134 * map - Map to empty. 135 * Return: 136 * Number of entries removed from the map. 137 */ 138 int allocmap_empty(AllocMap* map); 139 140 #ifdef __cplusplus 141 }; /* end of extern "C" */ 142 #endif 143 144 #endif // QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H 145