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