1#include <common.h>
2#include <debug.h>
3#include <rangesort.h>
4
5#define PARALLEL_ARRAY_SIZE (5)
6
7struct 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
16range_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
28void 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
40static 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
46static inline int IN_RANGE(range_t *range, GElf_Off point) {
47    return
48    range->start <= point &&
49    point < (range->start + range->length);
50}
51
52static 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
60static 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
79static 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
104static 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
119void 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
140range_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
147range_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
168int get_num_ranges(const range_list_t *ranges)
169{
170    return ranges->num_ranges;
171}
172
173range_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
181GElf_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
188static 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
210static 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
216static 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
245range_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
286range_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