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
68 /* elfcopy.c checks that the start of a section begins at or
69 after end of the previous section in the sorted list. So we need
70 to be careful about empty sections. */
71 if (left->start != right->start)
72 return left->start - right->start;
73 else {
74 ASSERT(left->length == 0 || right->length == 0);
75 return left->length - right->length;
76 }
77 }
78
run_checks(const void * l,const void * r)79 static inline void run_checks(const void *l, const void *r) {
80 range_t *left = (range_t *)l, *right = (range_t *)r;
81 if (CONTAINS(left, right)) {
82 if (left->err_fn)
83 left->err_fn(ERROR_CONTAINS, left, right);
84 FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
85 left->start, left->start + left->length,
86 right->start, right->start + right->length);
87 }
88 if (CONTAINS(right, left)) {
89 if (right->err_fn)
90 right->err_fn(ERROR_CONTAINS, left, right);
91 FAILIF(1, "Range sorting error: [%lld, %lld) contains [%lld, %lld)!\n",
92 right->start, right->start + right->length,
93 left->start, left->start + left->length);
94 }
95 if (INTERSECT(left, right)) {
96 if (left->err_fn)
97 left->err_fn(ERROR_OVERLAPS, left, right);
98 FAILIF(1, "Range sorting error: [%lld, %lld)and [%lld, %lld) intersect!\n",
99 left->start, left->start + left->length,
100 right->start, right->start + right->length);
101 }
102 }
103
range_cmp(const void * l,const void * r)104 static int range_cmp(const void *l, const void *r) {
105 run_checks(l, r);
106 range_t *left = (range_t *)l, *right = (range_t *)r;
107
108 /* elfcopy.c checks that the start of a section begins at or
109 after end of the previous section in the sorted list. So we need
110 to be careful about empty sections. */
111 if (left->start != right->start)
112 return left->start - right->start;
113 else {
114 ASSERT(left->length == 0 || right->length == 0);
115 return left->length - right->length;
116 }
117 }
118
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 *))119 void add_unique_range_nosort(
120 range_list_t *ranges,
121 GElf_Off start,
122 GElf_Off length,
123 void *user,
124 void (*err_fn)(range_error_t, range_t *, range_t *),
125 void (*user_dtor)(void * ))
126 {
127 if (ranges->num_ranges == ranges->array_length) {
128 ranges->array_length += PARALLEL_ARRAY_SIZE;
129 ranges->array = REALLOC(ranges->array,
130 ranges->array_length*sizeof(range_t));
131 }
132 ranges->array[ranges->num_ranges].start = start;
133 ranges->array[ranges->num_ranges].length = length;
134 ranges->array[ranges->num_ranges].user = user;
135 ranges->array[ranges->num_ranges].err_fn = err_fn;
136 ranges->array[ranges->num_ranges].user_dtor = user_dtor;
137 ranges->num_ranges++;
138 }
139
sort_ranges(range_list_t * ranges)140 range_list_t *sort_ranges(range_list_t *ranges) {
141 if (ranges->num_ranges > 1)
142 qsort(ranges->array, ranges->num_ranges, sizeof(range_t), range_cmp);
143 ranges->is_sorted = 1;
144 return ranges;
145 }
146
find_range(range_list_t * ranges,GElf_Off value)147 range_t *find_range(range_list_t *ranges, GElf_Off value) {
148 #if 1
149 int i;
150 for (i = 0; i < ranges->num_ranges; i++) {
151 if (ranges->array[i].start <= value &&
152 value < ranges->array[i].start + ranges->array[i].length)
153 return ranges->array + i;
154 }
155 return NULL;
156 #else
157 ASSERT(ranges->is_sorted); /* The range list must be sorted */
158 range_t lookup;
159 lookup.start = value;
160 lookup.length = 0;
161 return
162 (range_t *)bsearch(&lookup,
163 ranges->array, ranges->num_ranges, sizeof(range_t),
164 range_cmp_for_search);
165 #endif
166 }
167
get_num_ranges(const range_list_t * ranges)168 int get_num_ranges(const range_list_t *ranges)
169 {
170 return ranges->num_ranges;
171 }
172
get_sorted_ranges(const range_list_t * ranges,int * num_ranges)173 range_t *get_sorted_ranges(const range_list_t *ranges, int *num_ranges) {
174 ASSERT(ranges->is_sorted); /* The range list must be sorted */
175 if (num_ranges) {
176 *num_ranges = ranges->num_ranges;
177 }
178 return ranges->array;
179 }
180
get_last_address(const range_list_t * ranges)181 GElf_Off get_last_address(const range_list_t *ranges) {
182 ASSERT(ranges->num_ranges);
183 return
184 ranges->array[ranges->num_ranges-1].start +
185 ranges->array[ranges->num_ranges-1].length;
186 }
187
handle_range_error(range_error_t err,range_t * left,range_t * right)188 static void handle_range_error(range_error_t err,
189 range_t *left, range_t *right) {
190 switch (err) {
191 case ERROR_CONTAINS:
192 ERROR("ERROR: section (%lld, %lld bytes) contains "
193 "section (%lld, %lld bytes)\n",
194 left->start, left->length,
195 right->start, right->length);
196 break;
197 case ERROR_OVERLAPS:
198 ERROR("ERROR: Section (%lld, %lld bytes) intersects "
199 "section (%lld, %lld bytes)\n",
200 left->start, left->length,
201 right->start, right->length);
202 break;
203 default:
204 ASSERT(!"Unknown range error code!");
205 }
206
207 FAILIF(1, "Range error.\n");
208 }
209
destroy_contiguous_range_info(void * user)210 static void destroy_contiguous_range_info(void *user) {
211 contiguous_range_info_t *info = (contiguous_range_info_t *)user;
212 FREE(info->ranges);
213 FREE(info);
214 }
215
handle_contiguous_range_error(range_error_t err,range_t * left,range_t * right)216 static void handle_contiguous_range_error(range_error_t err,
217 range_t *left,
218 range_t *right)
219 {
220 contiguous_range_info_t *left_data =
221 (contiguous_range_info_t *)left->user;
222 ASSERT(left_data);
223 contiguous_range_info_t *right_data =
224 (contiguous_range_info_t *)right->user;
225 ASSERT(right_data);
226
227 PRINT("Contiguous-range overlap error. Printing contained ranges:\n");
228 int cnt;
229 PRINT("\tLeft ranges:\n");
230 for (cnt = 0; cnt < left_data->num_ranges; cnt++) {
231 PRINT("\t\t[%lld, %lld)\n",
232 left_data->ranges[cnt].start,
233 left_data->ranges[cnt].start + left_data->ranges[cnt].length);
234 }
235 PRINT("\tRight ranges:\n");
236 for (cnt = 0; cnt < right_data->num_ranges; cnt++) {
237 PRINT("\t\t[%lld, %lld)\n",
238 right_data->ranges[cnt].start,
239 right_data->ranges[cnt].start + right_data->ranges[cnt].length);
240 }
241
242 handle_range_error(err, left, right);
243 }
244
get_contiguous_ranges(const range_list_t * input)245 range_list_t* get_contiguous_ranges(const range_list_t *input)
246 {
247 ASSERT(input);
248 FAILIF(!input->is_sorted,
249 "get_contiguous_ranges(): input range list is not sorted!\n");
250
251 range_list_t* ret = init_range_list();
252 int num_ranges;
253 range_t *ranges = get_sorted_ranges(input, &num_ranges);
254
255 int end_idx = 0;
256 while (end_idx < num_ranges) {
257 int start_idx = end_idx++;
258 int old_end_idx = start_idx;
259 int total_length = ranges[start_idx].length;
260 while (end_idx < num_ranges) {
261 if (ranges[old_end_idx].start + ranges[old_end_idx].length !=
262 ranges[end_idx].start)
263 break;
264 old_end_idx = end_idx++;
265 total_length += ranges[old_end_idx].length;
266 }
267
268 contiguous_range_info_t *user =
269 (contiguous_range_info_t *)MALLOC(sizeof(contiguous_range_info_t));
270 user->num_ranges = end_idx - start_idx;
271 user->ranges = (range_t *)MALLOC(user->num_ranges * sizeof(range_t));
272 int i;
273 for (i = 0; i < end_idx - start_idx; i++)
274 user->ranges[i] = ranges[start_idx + i];
275 add_unique_range_nosort(ret,
276 ranges[start_idx].start,
277 total_length,
278 user,
279 handle_contiguous_range_error,
280 destroy_contiguous_range_info);
281 }
282
283 return ret;
284 }
285
subtract_ranges(const range_list_t * r,const range_list_t * s)286 range_list_t* subtract_ranges(const range_list_t *r, const range_list_t *s)
287 {
288 ASSERT(r); ASSERT(r->is_sorted);
289 ASSERT(s); ASSERT(s->is_sorted);
290
291 range_list_t *result = init_range_list();
292
293 int r_num_ranges, r_idx;
294 range_t *r_ranges = get_sorted_ranges(r, &r_num_ranges);
295 ASSERT(r_ranges);
296
297 int s_num_ranges, s_idx;
298 range_t *s_ranges = get_sorted_ranges(s, &s_num_ranges);
299 ASSERT(s_ranges);
300
301 s_idx = 0;
302 for (r_idx = 0; r_idx < r_num_ranges; r_idx++) {
303 GElf_Off last_start = r_ranges[r_idx].start;
304 for (; s_idx < s_num_ranges; s_idx++) {
305 if (CONTAINS(&r_ranges[r_idx], &s_ranges[s_idx])) {
306 if (last_start ==
307 r_ranges[r_idx].start + r_ranges[r_idx].length) {
308 break;
309 }
310 if (last_start == s_ranges[s_idx].start) {
311 last_start += s_ranges[s_idx].length;
312 continue;
313 }
314 INFO("Adding subtracted range [%lld, %lld)\n",
315 last_start,
316 s_ranges[s_idx].start);
317 add_unique_range_nosort(
318 result,
319 last_start,
320 s_ranges[s_idx].start - last_start,
321 NULL,
322 NULL,
323 NULL);
324 last_start = s_ranges[s_idx].start + s_ranges[s_idx].length;
325 } else {
326 ASSERT(!INTERSECT(&r_ranges[r_idx], &s_ranges[s_idx]));
327 break;
328 }
329 } /* while (s_idx < s_num_ranges) */
330 } /* for (r_idx = 0; r_idx < r_num_ranges; r_idx++) */
331
332 return result;
333 }
334
335
336