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
cmp_rb(MMRangeMapEntry * d1,MMRangeMapEntry * d2)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
mmrangemap_insert_desc(MMRangeMap * map,MMRangeMapEntry * rdesc,MMRangeDesc * replaced)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*
mmrangemap_find_entry(const MMRangeMap * map,target_ulong start,target_ulong end)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
mmrangemap_init(MMRangeMap * map)116 mmrangemap_init(MMRangeMap* map)
117 {
118 RB_INIT(map);
119 }
120
121 RBTMapResult
mmrangemap_insert(MMRangeMap * map,const MMRangeDesc * desc,MMRangeDesc * replaced)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*
mmrangemap_find(const MMRangeMap * map,target_ulong start,target_ulong end)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
mmrangemap_pull(MMRangeMap * map,target_ulong start,target_ulong end,MMRangeDesc * pulled)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
mmrangemap_pull_first(MMRangeMap * map,MMRangeDesc * pulled)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
mmrangemap_copy(MMRangeMap * to,const MMRangeMap * from)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
mmrangemap_empty(MMRangeMap * map)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