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 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 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 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 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 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 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 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 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 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 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 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 168 int get_num_ranges(const range_list_t *ranges) 169 { 170 return ranges->num_ranges; 171 } 172 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 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 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 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 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 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 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
