1 #include <common.h>
2 #include <debug.h>
3 #include <rangesort.h>
4
5 #define PARALLEL_ARRAY_SIZE (5)
6
7 struct range_list_t {
8 range_t *array;
9 #ifdef DEBUG
10 int is_sorted;
11 #endif
12 int array_length;
13 int num_ranges;
14 };
15
init_range_list(void)16 range_list_t* init_range_list(void) {
17 range_list_t *ranges = (range_list_t *)MALLOC(sizeof(range_list_t));
18
19 ranges->array = (range_t *)MALLOC(PARALLEL_ARRAY_SIZE*sizeof(range_t));
20 ranges->array_length = PARALLEL_ARRAY_SIZE;
21 ranges->num_ranges = 0;
22 #ifdef DEBUG
23 ranges->is_sorted = 0;
24 #endif
25 return ranges;
26 }
27
destroy_range_list(range_list_t * ranges)28 void destroy_range_list(range_list_t *ranges) {
29 int idx;
30 for (idx = 0; idx < ranges->num_ranges; idx++) {
31 if (ranges->array[idx].user_dtor) {
32 ASSERT(ranges->array[idx].user);
33 ranges->array[idx].user_dtor(ranges->array[idx].user);
34 }
35 }
36 FREE(ranges->array);
37 FREE(ranges);
38 }
39
CONTAINS(range_t * container,range_t * contained)40 static inline int CONTAINS(range_t *container, range_t *contained) {
41 return container->start <= contained->start && contained->length &&
42 (container->start + container->length >
43 contained->start + contained->length);
44 }
45
IN_RANGE(range_t * range,GElf_Off point)46 static inline int IN_RANGE(range_t *range, GElf_Off point) {
47 return
48 range->start <= point &&
49 point < (range->start + range->length);
50 }
51
INTERSECT(range_t * left,range_t * right)52 static inline int INTERSECT(range_t *left, range_t *right) {
53 return
54 (IN_RANGE(left, right->start) &&
55 IN_RANGE(right, left->start + left->length)) ||
56 (IN_RANGE(right, left->start) &&
57 IN_RANGE(left, right->start + right->length));
58 }
59
range_cmp_for_search(const void * l,const void * r)60 static int range_cmp_for_search(const void *l, const void *r) {
61 range_t *left = (range_t *)l, *right = (range_t *)r;
62 if (INTERSECT(left, right) ||
63 CONTAINS(left, right) ||
64 CONTAINS(right, left)) {
65 return 0;
66 }
67 return left->start - right->start;
68 }
69
run_checks(const void * l,const void * r)70 static inline void run_checks(const void *l, const void *r) {
71 range_t *left = (range_t *)l, *right = (range_t *)r;
72 if (CONTAINS(left, right)) {
73 if (left->err_fn)
74 left->err_fn(ERROR_CONTAINS, left, right);
75 FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
76 left->start, left->start + left->length,
77 right->start, right->start + right->length);
78 }
79 if (CONTAINS(right, left)) {
80 if (right->err_fn)
81 right->err_fn(ERROR_CONTAINS, left, right);
82 FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
83 right->start, right->start + right->length,
84 left->start, left->start + left->length);
85 }
86 if (INTERSECT(left, right)) {
87 if (left->err_fn)
88 left->err_fn(ERROR_OVERLAPS, left, right);
89 FAILIF(1, "Range sorting error: [%lld, %lld)and [%lld, %lld) intersect!\n",
90 left->start, left->start + left->length,
91 right->start, right->start + right->length);
92 }
93 }
94
range_cmp(const void * l,const void * r)95 static int range_cmp(const void *l, const void *r) {
96 run_checks(l, r);
97 range_t *left = (range_t *)l, *right = (range_t *)r;
98 return left->start - right->start;
99 }
100
add_unique_range_nosort(range_list_t * ranges,GElf_Off start,GElf_Off length,void * user,void (* err_fn)(range_error_t,range_t *,range_t *),void (* user_dtor)(void *))101 void add_unique_range_nosort(
102 range_list_t *ranges,
103 GElf_Off start,
104 GElf_Off length,
105 void *user,
106 void (*err_fn)(range_error_t, range_t *, range_t *),
107 void (*user_dtor)(void * ))
108 {
109 if (ranges->num_ranges == ranges->array_length) {
110 ranges->array_length += PARALLEL_ARRAY_SIZE;
111 ranges->array = REALLOC(ranges->array,
112 ranges->array_length*sizeof(range_t));
113 }
114 ranges->array[ranges->num_ranges].start = start;
115 ranges->array[ranges->num_ranges].length = length;
116 ranges->array[ranges->num_ranges].user = user;
117 ranges->array[ranges->num_ranges].err_fn = err_fn;
118 ranges->array[ranges->num_ranges].user_dtor = user_dtor;
119 ranges->num_ranges++;
120 }
121
sort_ranges(range_list_t * ranges)122 range_list_t *sort_ranges(range_list_t *ranges) {
123 if (ranges->num_ranges > 1)
124 qsort(ranges->array, ranges->num_ranges, sizeof(range_t), range_cmp);
125 ranges->is_sorted = 1;
126 return ranges;
127 }
128
find_range(range_list_t * ranges,GElf_Off value)129 range_t *find_range(range_list_t *ranges, GElf_Off value) {
130 #if 1
131 int i;
132 for (i = 0; i < ranges->num_ranges; i++) {
133 if (ranges->array[i].start <= value &&
134 value < ranges->array[i].start + ranges->array[i].length)
135 return ranges->array + i;
136 }
137 return NULL;
138 #else
139 ASSERT(ranges->is_sorted); /* The range list must be sorted */
140 range_t lookup;
141 lookup.start = value;
142 lookup.length = 0;
143 return
144 (range_t *)bsearch(&lookup,
145 ranges->array, ranges->num_ranges, sizeof(range_t),
146 range_cmp_for_search);
147 #endif
148 }
149
get_num_ranges(const range_list_t * ranges)150 int get_num_ranges(const range_list_t *ranges)
151 {
152 return ranges->num_ranges;
153 }
154
get_sorted_ranges(const range_list_t * ranges,int * num_ranges)155 range_t *get_sorted_ranges(const range_list_t *ranges, int *num_ranges) {
156 ASSERT(ranges->is_sorted); /* The range list must be sorted */
157 if (num_ranges) {
158 *num_ranges = ranges->num_ranges;
159 }
160 return ranges->array;
161 }
162
get_last_address(const range_list_t * ranges)163 GElf_Off get_last_address(const range_list_t *ranges) {
164 ASSERT(ranges->num_ranges);
165 return
166 ranges->array[ranges->num_ranges-1].start +
167 ranges->array[ranges->num_ranges-1].length;
168 }
169
handle_range_error(range_error_t err,range_t * left,range_t * right)170 static void handle_range_error(range_error_t err,
171 range_t *left, range_t *right) {
172 switch (err) {
173 case ERROR_CONTAINS:
174 ERROR("ERROR: section (%lld, %lld bytes) contains "
175 "section (%lld, %lld bytes)\n",
176 left->start, left->length,
177 right->start, right->length);
178 break;
179 case ERROR_OVERLAPS:
180 ERROR("ERROR: Section (%lld, %lld bytes) intersects "
181 "section (%lld, %lld bytes)\n",
182 left->start, left->length,
183 right->start, right->length);
184 break;
185 default:
186 ASSERT(!"Unknown range error code!");
187 }
188
189 FAILIF(1, "Range error.\n");
190 }
191
destroy_contiguous_range_info(void * user)192 static void destroy_contiguous_range_info(void *user) {
193 contiguous_range_info_t *info = (contiguous_range_info_t *)user;
194 FREE(info->ranges);
195 FREE(info);
196 }
197
handle_contiguous_range_error(range_error_t err,range_t * left,range_t * right)198 static void handle_contiguous_range_error(range_error_t err,
199 range_t *left,
200 range_t *right)
201 {
202 contiguous_range_info_t *left_data =
203 (contiguous_range_info_t *)left->user;
204 ASSERT(left_data);
205 contiguous_range_info_t *right_data =
206 (contiguous_range_info_t *)right->user;
207 ASSERT(right_data);
208
209 PRINT("Contiguous-range overlap error. Printing contained ranges:\n");
210 int cnt;
211 PRINT("\tLeft ranges:\n");
212 for (cnt = 0; cnt < left_data->num_ranges; cnt++) {
213 PRINT("\t\t[%lld, %lld)\n",
214 left_data->ranges[cnt].start,
215 left_data->ranges[cnt].start + left_data->ranges[cnt].length);
216 }
217 PRINT("\tRight ranges:\n");
218 for (cnt = 0; cnt < right_data->num_ranges; cnt++) {
219 PRINT("\t\t[%lld, %lld)\n",
220 right_data->ranges[cnt].start,
221 right_data->ranges[cnt].start + right_data->ranges[cnt].length);
222 }
223
224 handle_range_error(err, left, right);
225 }
226
get_contiguous_ranges(const range_list_t * input)227 range_list_t* get_contiguous_ranges(const range_list_t *input)
228 {
229 ASSERT(input);
230 FAILIF(!input->is_sorted,
231 "get_contiguous_ranges(): input range list is not sorted!\n");
232
233 range_list_t* ret = init_range_list();
234 int num_ranges;
235 range_t *ranges = get_sorted_ranges(input, &num_ranges);
236
237 int end_idx = 0;
238 while (end_idx < num_ranges) {
239 int start_idx = end_idx++;
240 int old_end_idx = start_idx;
241 int total_length = ranges[start_idx].length;
242 while (end_idx < num_ranges) {
243 if (ranges[old_end_idx].start + ranges[old_end_idx].length !=
244 ranges[end_idx].start)
245 break;
246 old_end_idx = end_idx++;
247 total_length += ranges[old_end_idx].length;
248 }
249
250 contiguous_range_info_t *user =
251 (contiguous_range_info_t *)MALLOC(sizeof(contiguous_range_info_t));
252 user->num_ranges = end_idx - start_idx;
253 user->ranges = (range_t *)MALLOC(user->num_ranges * sizeof(range_t));
254 int i;
255 for (i = 0; i < end_idx - start_idx; i++)
256 user->ranges[i] = ranges[start_idx + i];
257 add_unique_range_nosort(ret,
258 ranges[start_idx].start,
259 total_length,
260 user,
261 handle_contiguous_range_error,
262 destroy_contiguous_range_info);
263 }
264
265 return ret;
266 }
267
subtract_ranges(const range_list_t * r,const range_list_t * s)268 range_list_t* subtract_ranges(const range_list_t *r, const range_list_t *s)
269 {
270 ASSERT(r); ASSERT(r->is_sorted);
271 ASSERT(s); ASSERT(s->is_sorted);
272
273 range_list_t *result = init_range_list();
274
275 int r_num_ranges, r_idx;
276 range_t *r_ranges = get_sorted_ranges(r, &r_num_ranges);
277 ASSERT(r_ranges);
278
279 int s_num_ranges, s_idx;
280 range_t *s_ranges = get_sorted_ranges(s, &s_num_ranges);
281 ASSERT(s_ranges);
282
283 s_idx = 0;
284 for (r_idx = 0; r_idx < r_num_ranges; r_idx++) {
285 GElf_Off last_start = r_ranges[r_idx].start;
286 for (; s_idx < s_num_ranges; s_idx++) {
287 if (CONTAINS(&r_ranges[r_idx], &s_ranges[s_idx])) {
288 if (last_start ==
289 r_ranges[r_idx].start + r_ranges[r_idx].length) {
290 break;
291 }
292 if (last_start == s_ranges[s_idx].start) {
293 last_start += s_ranges[s_idx].length;
294 continue;
295 }
296 INFO("Adding subtracted range [%lld, %lld)\n",
297 last_start,
298 s_ranges[s_idx].start);
299 add_unique_range_nosort(
300 result,
301 last_start,
302 s_ranges[s_idx].start - last_start,
303 NULL,
304 NULL,
305 NULL);
306 last_start = s_ranges[s_idx].start + s_ranges[s_idx].length;
307 } else {
308 ASSERT(!INTERSECT(&r_ranges[r_idx], &s_ranges[s_idx]));
309 break;
310 }
311 } /* while (s_idx < s_num_ranges) */
312 } /* for (r_idx = 0; r_idx < r_num_ranges; r_idx++) */
313
314 return result;
315 }
316
317
318