smatch_ranges.c

   1 /*
   2  * sparse/smatch_ranges.c
   3  *
   4  * Copyright (C) 2009 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include "parse.h"
  11 #include "smatch.h"
  12 #include "smatch_extra.h"
  13 #include "smatch_slist.h"
  14
  15 ALLOCATOR(data_info, "smatch extra data");
  16 ALLOCATOR(data_range, "data range");
  17 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
  18                          "permanent ranges", perm_data_range);
  19
  20 char *show_rl(struct range_list *list)
  21 {
  22         struct data_range *tmp;
  23         char full[256];
  24         int i = 0;
  25
  26         full[0] = '\0';
  27         full[255] = '\0';
  28         FOR_EACH_PTR(list, tmp) {
  29                 if (i++)
  30                         strncat(full, ",", 254 - strlen(full));
  31                 if (sval_cmp(tmp->min, tmp->max) == 0) {
  32                         strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  33                         continue;
  34                 }
  35                 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
  36                 strncat(full, "-", 254 - strlen(full));
  37                 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
  38         } END_FOR_EACH_PTR(tmp);
  39         return alloc_sname(full);
  40 }
  41
  42 static sval_t parse_val(struct symbol *type, char *c, char **endp)
  43 {
  44         char *start = c;
  45         sval_t ret;
  46
  47         if (!strncmp(start, "max", 3)) {
  48                 ret = sval_type_max(type);
  49                 c += 3;
  50         } else if (!strncmp(start, "u64max", 6)) {
  51                 ret = sval_type_val(type, ULLONG_MAX);
  52                 c += 6;
  53         } else if (!strncmp(start, "s64max", 6)) {
  54                 ret = sval_type_val(type, LLONG_MAX);
  55                 c += 6;
  56         } else if (!strncmp(start, "u32max", 6)) {
  57                 ret = sval_type_val(type, UINT_MAX);
  58                 c += 6;
  59         } else if (!strncmp(start, "s32max", 6)) {
  60                 ret = sval_type_val(type, INT_MAX);
  61                 c += 6;
  62         } else if (!strncmp(start, "u16max", 6)) {
  63                 ret = sval_type_val(type, USHRT_MAX);
  64                 c += 6;
  65         } else if (!strncmp(start, "s16max", 6)) {
  66                 ret = sval_type_val(type, SHRT_MAX);
  67                 c += 6;
  68         } else if (!strncmp(start, "min", 3)) {
  69                 ret = sval_type_min(type);
  70                 c += 3;
  71         } else if (!strncmp(start, "s64min", 6)) {
  72                 ret = sval_type_val(type, LLONG_MIN);
  73                 c += 6;
  74         } else if (!strncmp(start, "s32min", 6)) {
  75                 ret = sval_type_val(type, INT_MIN);
  76                 c += 6;
  77         } else if (!strncmp(start, "s16min", 6)) {
  78                 ret = sval_type_val(type, SHRT_MIN);
  79                 c += 6;
  80         } else {
  81                 ret = sval_type_val(type, strtoll(start, &c, 10));
  82         }
  83         *endp = c;
  84         return ret;
  85 }
  86
  87 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
  88 {
  89         sval_t min, max;
  90         char *c;
  91
  92         if (!type)
  93                 type = &llong_ctype;
  94         *rl = NULL;
  95
  96         if (value && strcmp(value, "empty") == 0)
  97                 return;
  98
  99         c = value;
 100         while (*c) {
 101                 if (*c == '(')
 102                         c++;
 103                 min = parse_val(type, c, &c);
 104                 if (*c == ')')
 105                         c++;
 106                 if (!*c) {
 107                         add_range(rl, min, min);
 108                         break;
 109                 }
 110                 if (*c == ',') {
 111                         add_range(rl, min, min);
 112                         c++;
 113                         continue;
 114                 }
 115                 if (*c != '-') {
 116                         sm_msg("debug XXX: trouble parsing %s ", value);
 117                         break;
 118                 }
 119                 c++;
 120                 if (*c == '(')
 121                         c++;
 122                 max = parse_val(type, c, &c);
 123                 add_range(rl, min, max);
 124                 if (*c == ')')
 125                         c++;
 126                 if (!*c)
 127                         break;
 128                 if (*c != ',') {
 129                         sm_msg("debug YYY: trouble parsing %s %s", value, c);
 130                         break;
 131                 }
 132                 c++;
 133         }
 134
 135         *rl = cast_rl(type, *rl);
 136 }
 137
 138 int is_whole_rl(struct range_list *rl)
 139 {
 140         struct data_range *drange;
 141
 142         if (ptr_list_empty(rl))
 143                 return 1;
 144         drange = first_ptr_list((struct ptr_list *)rl);
 145         if (sval_is_min(drange->min) && sval_is_max(drange->max))
 146                 return 1;
 147         return 0;
 148 }
 149
 150 sval_t rl_min(struct range_list *rl)
 151 {
 152         struct data_range *drange;
 153         sval_t ret;
 154
 155         ret.type = &llong_ctype;
 156         ret.value = LLONG_MIN;
 157         if (ptr_list_empty(rl))
 158                 return ret;
 159         drange = first_ptr_list((struct ptr_list *)rl);
 160         return drange->min;
 161 }
 162
 163 sval_t rl_max(struct range_list *rl)
 164 {
 165         struct data_range *drange;
 166         sval_t ret;
 167
 168         ret.type = &llong_ctype;
 169         ret.value = LLONG_MAX;
 170         if (ptr_list_empty(rl))
 171                 return ret;
 172         drange = last_ptr_list((struct ptr_list *)rl);
 173         return drange->max;
 174 }
 175
 176 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
 177 {
 178         struct data_range *ret;
 179
 180         if (perm)
 181                 ret = __alloc_perm_data_range(0);
 182         else
 183                 ret = __alloc_data_range(0);
 184         ret->min = min;
 185         ret->max = max;
 186         return ret;
 187 }
 188
 189 struct data_range *alloc_range(sval_t min, sval_t max)
 190 {
 191         return alloc_range_helper_sval(min, max, 0);
 192 }
 193
 194 struct data_range *alloc_range_perm(sval_t min, sval_t max)
 195 {
 196         return alloc_range_helper_sval(min, max, 1);
 197 }
 198
 199 struct range_list *alloc_rl(sval_t min, sval_t max)
 200 {
 201         struct range_list *rl = NULL;
 202
 203         if (sval_cmp(min, max) > 0)
 204                 return alloc_whole_rl(min.type);
 205
 206         add_range(&rl, min, max);
 207         return rl;
 208 }
 209
 210 struct range_list *alloc_whole_rl(struct symbol *type)
 211 {
 212         if (!type || type_positive_bits(type) < 0)
 213                 type = &llong_ctype;
 214
 215         return alloc_rl(sval_type_min(type), sval_type_max(type));
 216 }
 217
 218 void add_range(struct range_list **list, sval_t min, sval_t max)
 219 {
 220         struct data_range *tmp = NULL;
 221         struct data_range *new = NULL;
 222         int check_next = 0;
 223
 224         /*
 225          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 226          * with a range like 1-2.  You end up with min-2,3-max instead of
 227          * just min-max.
 228          */
 229         FOR_EACH_PTR(*list, tmp) {
 230                 if (check_next) {
 231                         /* Sometimes we overlap with more than one range
 232                            so we have to delete or modify the next range. */
 233                         if (max.value + 1 == tmp->min.value) {
 234                                 /* join 2 ranges here */
 235                                 new->max = tmp->max;
 236                                 DELETE_CURRENT_PTR(tmp);
 237                                 return;
 238                         }
 239
 240                         /* Doesn't overlap with the next one. */
 241                         if (sval_cmp(max, tmp->min) < 0)
 242                                 return;
 243                         /* Partially overlaps with the next one. */
 244                         if (sval_cmp(max, tmp->max) < 0) {
 245                                 tmp->min.value = max.value + 1;
 246                                 return;
 247                         }
 248                         /* Completely overlaps with the next one. */
 249                         if (sval_cmp(max, tmp->max) >= 0) {
 250                                 DELETE_CURRENT_PTR(tmp);
 251                                 /* there could be more ranges to delete */
 252                                 continue;
 253                         }
 254                 }
 255                 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 256                         /* join 2 ranges into a big range */
 257                         new = alloc_range(min, tmp->max);
 258                         REPLACE_CURRENT_PTR(tmp, new);
 259                         return;
 260                 }
 261                 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
 262                         new = alloc_range(min, max);
 263                         INSERT_CURRENT(new, tmp);
 264                         return;
 265                 }
 266                 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
 267                         if (sval_cmp(max, tmp->max) < 0)
 268                                 max = tmp->max;
 269                         else
 270                                 check_next = 1;
 271                         new = alloc_range(min, max);
 272                         REPLACE_CURRENT_PTR(tmp, new);
 273                         if (!check_next)
 274                                 return;
 275                         continue;
 276                 }
 277                 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
 278                         return;
 279                 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
 280                         min = tmp->min;
 281                         new = alloc_range(min, max);
 282                         REPLACE_CURRENT_PTR(tmp, new);
 283                         check_next = 1;
 284                         continue;
 285                 }
 286                 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
 287                         /* join 2 ranges into a big range */
 288                         new = alloc_range(tmp->min, max);
 289                         REPLACE_CURRENT_PTR(tmp, new);
 290                         check_next = 1;
 291                         continue;
 292                 }
 293                 /* the new range is entirely above the existing ranges */
 294         } END_FOR_EACH_PTR(tmp);
 295         if (check_next)
 296                 return;
 297         new = alloc_range(min, max);
 298         add_ptr_list(list, new);
 299 }
 300
 301 struct range_list *clone_rl(struct range_list *list)
 302 {
 303         struct data_range *tmp;
 304         struct range_list *ret = NULL;
 305
 306         FOR_EACH_PTR(list, tmp) {
 307                 add_ptr_list(&ret, tmp);
 308         } END_FOR_EACH_PTR(tmp);
 309         return ret;
 310 }
 311
 312 struct range_list *clone_rl_permanent(struct range_list *list)
 313 {
 314         struct data_range *tmp;
 315         struct data_range *new;
 316         struct range_list *ret = NULL;
 317
 318         FOR_EACH_PTR(list, tmp) {
 319                 new = alloc_range_perm(tmp->min, tmp->max);
 320                 add_ptr_list(&ret, new);
 321         } END_FOR_EACH_PTR(tmp);
 322         return ret;
 323 }
 324
 325 struct range_list *rl_union(struct range_list *one, struct range_list *two)
 326 {
 327         struct data_range *tmp;
 328         struct range_list *ret = NULL;
 329
 330         FOR_EACH_PTR(one, tmp) {
 331                 add_range(&ret, tmp->min, tmp->max);
 332         } END_FOR_EACH_PTR(tmp);
 333         FOR_EACH_PTR(two, tmp) {
 334                 add_range(&ret, tmp->min, tmp->max);
 335         } END_FOR_EACH_PTR(tmp);
 336         return ret;
 337 }
 338
 339 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
 340 {
 341         struct data_range *tmp;
 342         struct range_list *ret = NULL;
 343
 344         FOR_EACH_PTR(list, tmp) {
 345                 if (sval_cmp(tmp->max, min) < 0) {
 346                         add_range(&ret, tmp->min, tmp->max);
 347                         continue;
 348                 }
 349                 if (sval_cmp(tmp->min, max) > 0) {
 350                         add_range(&ret, tmp->min, tmp->max);
 351                         continue;
 352                 }
 353                 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
 354                         continue;
 355                 if (sval_cmp(tmp->min, min) >= 0) {
 356                         max.value++;
 357                         add_range(&ret, max, tmp->max);
 358                 } else if (sval_cmp(tmp->max, max) <= 0) {
 359                         min.value--;
 360                         add_range(&ret, tmp->min, min);
 361                 } else {
 362                         min.value--;
 363                         max.value++;
 364                         add_range(&ret, tmp->min, min);
 365                         add_range(&ret, max, tmp->max);
 366                 }
 367         } END_FOR_EACH_PTR(tmp);
 368         return ret;
 369 }
 370
 371 int ranges_equiv(struct data_range *one, struct data_range *two)
 372 {
 373         if (!one && !two)
 374                 return 1;
 375         if (!one || !two)
 376                 return 0;
 377         if (sval_cmp(one->min, two->min) != 0)
 378                 return 0;
 379         if (sval_cmp(one->max, two->max) != 0)
 380                 return 0;
 381         return 1;
 382 }
 383
 384 int rl_equiv(struct range_list *one, struct range_list *two)
 385 {
 386         struct data_range *one_range;
 387         struct data_range *two_range;
 388
 389         if (one == two)
 390                 return 1;
 391
 392         PREPARE_PTR_LIST(one, one_range);
 393         PREPARE_PTR_LIST(two, two_range);
 394         for (;;) {
 395                 if (!one_range && !two_range)
 396                         return 1;
 397                 if (!ranges_equiv(one_range, two_range))
 398                         return 0;
 399                 NEXT_PTR_LIST(one_range);
 400                 NEXT_PTR_LIST(two_range);
 401         }
 402         FINISH_PTR_LIST(two_range);
 403         FINISH_PTR_LIST(one_range);
 404
 405         return 1;
 406 }
 407
 408 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 409 {
 410         switch (comparison) {
 411         case '<':
 412         case SPECIAL_UNSIGNED_LT:
 413                 if (sval_cmp(left->min, right->max) < 0)
 414                         return 1;
 415                 return 0;
 416         case SPECIAL_UNSIGNED_LTE:
 417         case SPECIAL_LTE:
 418                 if (sval_cmp(left->min, right->max) <= 0)
 419                         return 1;
 420                 return 0;
 421         case SPECIAL_EQUAL:
 422                 if (sval_cmp(left->max, right->min) < 0)
 423                         return 0;
 424                 if (sval_cmp(left->min, right->max) > 0)
 425                         return 0;
 426                 return 1;
 427         case SPECIAL_UNSIGNED_GTE:
 428         case SPECIAL_GTE:
 429                 if (sval_cmp(left->max, right->min) >= 0)
 430                         return 1;
 431                 return 0;
 432         case '>':
 433         case SPECIAL_UNSIGNED_GT:
 434                 if (sval_cmp(left->max, right->min) > 0)
 435                         return 1;
 436                 return 0;
 437         case SPECIAL_NOTEQUAL:
 438                 if (sval_cmp(left->min, left->max) != 0)
 439                         return 1;
 440                 if (sval_cmp(right->min, right->max) != 0)
 441                         return 1;
 442                 if (sval_cmp(left->min, right->min) != 0)
 443                         return 1;
 444                 return 0;
 445         default:
 446                 sm_msg("unhandled comparison %d\n", comparison);
 447                 return 0;
 448         }
 449         return 0;
 450 }
 451
 452 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 453 {
 454         if (left)
 455                 return true_comparison_range(var, comparison, val);
 456         else
 457                 return true_comparison_range(val, comparison, var);
 458 }
 459
 460 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
 461 {
 462         switch (comparison) {
 463         case '<':
 464         case SPECIAL_UNSIGNED_LT:
 465                 if (sval_cmp(left->max, right->min) >= 0)
 466                         return 1;
 467                 return 0;
 468         case SPECIAL_UNSIGNED_LTE:
 469         case SPECIAL_LTE:
 470                 if (sval_cmp(left->max, right->min) > 0)
 471                         return 1;
 472                 return 0;
 473         case SPECIAL_EQUAL:
 474                 if (sval_cmp(left->min, left->max) != 0)
 475                         return 1;
 476                 if (sval_cmp(right->min, right->max) != 0)
 477                         return 1;
 478                 if (sval_cmp(left->min, right->min) != 0)
 479                         return 1;
 480                 return 0;
 481         case SPECIAL_UNSIGNED_GTE:
 482         case SPECIAL_GTE:
 483                 if (sval_cmp(left->min, right->max) < 0)
 484                         return 1;
 485                 return 0;
 486         case '>':
 487         case SPECIAL_UNSIGNED_GT:
 488                 if (sval_cmp(left->min, right->max) <= 0)
 489                         return 1;
 490                 return 0;
 491         case SPECIAL_NOTEQUAL:
 492                 if (sval_cmp(left->max, right->min) < 0)
 493                         return 0;
 494                 if (sval_cmp(left->min, right->max) > 0)
 495                         return 0;
 496                 return 1;
 497         default:
 498                 sm_msg("unhandled comparison %d\n", comparison);
 499                 return 0;
 500         }
 501         return 0;
 502 }
 503
 504 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
 505 {
 506         if (left)
 507                 return false_comparison_range_sval(var, comparison, val);
 508         else
 509                 return false_comparison_range_sval(val, comparison, var);
 510 }
 511
 512 int possibly_true(struct expression *left, int comparison, struct expression *right)
 513 {
 514         struct range_list *rl_left, *rl_right;
 515         struct data_range *tmp_left, *tmp_right;
 516
 517         if (!get_implied_rl(left, &rl_left))
 518                 return 1;
 519         if (!get_implied_rl(right, &rl_right))
 520                 return 1;
 521
 522         FOR_EACH_PTR(rl_left, tmp_left) {
 523                 FOR_EACH_PTR(rl_right, tmp_right) {
 524                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 525                                 return 1;
 526                 } END_FOR_EACH_PTR(tmp_right);
 527         } END_FOR_EACH_PTR(tmp_left);
 528         return 0;
 529 }
 530
 531 int possibly_false(struct expression *left, int comparison, struct expression *right)
 532 {
 533         struct range_list *rl_left, *rl_right;
 534         struct data_range *tmp_left, *tmp_right;
 535
 536         if (!get_implied_rl(left, &rl_left))
 537                 return 1;
 538         if (!get_implied_rl(right, &rl_right))
 539                 return 1;
 540
 541         FOR_EACH_PTR(rl_left, tmp_left) {
 542                 FOR_EACH_PTR(rl_right, tmp_right) {
 543                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
 544                                 return 1;
 545                 } END_FOR_EACH_PTR(tmp_right);
 546         } END_FOR_EACH_PTR(tmp_left);
 547         return 0;
 548 }
 549
 550 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 551 {
 552         struct data_range *left_tmp, *right_tmp;
 553
 554         if (!left_ranges || !right_ranges)
 555                 return 1;
 556
 557         FOR_EACH_PTR(left_ranges, left_tmp) {
 558                 FOR_EACH_PTR(right_ranges, right_tmp) {
 559                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 560                                 return 1;
 561                 } END_FOR_EACH_PTR(right_tmp);
 562         } END_FOR_EACH_PTR(left_tmp);
 563         return 0;
 564 }
 565
 566 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 567 {
 568         struct data_range *left_tmp, *right_tmp;
 569
 570         if (!left_ranges || !right_ranges)
 571                 return 1;
 572
 573         FOR_EACH_PTR(left_ranges, left_tmp) {
 574                 FOR_EACH_PTR(right_ranges, right_tmp) {
 575                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
 576                                 return 1;
 577                 } END_FOR_EACH_PTR(right_tmp);
 578         } END_FOR_EACH_PTR(left_tmp);
 579         return 0;
 580 }
 581
 582 /* FIXME: the _rl here stands for right left so really it should be _lr */
 583 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 584 {
 585         if (left)
 586                 return possibly_true_rl(a, comparison, b);
 587         else
 588                 return possibly_true_rl(b, comparison, a);
 589 }
 590
 591 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
 592 {
 593         if (left)
 594                 return possibly_false_rl(a, comparison, b);
 595         else
 596                 return possibly_false_rl(b, comparison, a);
 597 }
 598
 599 void tack_on(struct range_list **list, struct data_range *drange)
 600 {
 601         add_ptr_list(list, drange);
 602 }
 603
 604 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
 605 {
 606         add_ptr_list(rl_stack, rl);
 607 }
 608
 609 struct range_list *pop_rl(struct range_list_stack **rl_stack)
 610 {
 611         struct range_list *rl;
 612
 613         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 614         delete_ptr_list_last((struct ptr_list **)rl_stack);
 615         return rl;
 616 }
 617
 618 struct range_list *top_rl(struct range_list_stack *rl_stack)
 619 {
 620         struct range_list *rl;
 621
 622         rl = last_ptr_list((struct ptr_list *)rl_stack);
 623         return rl;
 624 }
 625
 626 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
 627 {
 628         struct range_list *rl;
 629
 630         rl = pop_rl(rl_stack);
 631         rl = remove_range(rl, sval, sval);
 632         push_rl(rl_stack, rl);
 633 }
 634
 635 static int sval_too_big(struct symbol *type, sval_t sval)
 636 {
 637         if (type_bits(type) == 64)
 638                 return 0;
 639         if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
 640                 return 1;
 641         return 0;
 642 }
 643
 644 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
 645 {
 646         /* If we're just adding a number, cast it and add it */
 647         if (sval_cmp(min, max) == 0) {
 648                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 649                 return;
 650         }
 651
 652         /* If the range is within the type range then add it */
 653         if (sval_fits(type, min) && sval_fits(type, max)) {
 654                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 655                 return;
 656         }
 657
 658         /*
 659          * If the range we are adding has more bits than the range type then
 660          * add the whole range type.  Eg:
 661          * 0x8000000000000000 - 0xf000000000000000 -> cast to int
 662          * This isn't totally the right thing to do.  We could be more granular.
 663          */
 664         if (sval_too_big(type, min) || sval_too_big(type, max)) {
 665                 add_range(rl, sval_type_min(type), sval_type_max(type));
 666                 return;
 667         }
 668
 669         /* Cast negative values to high positive values */
 670         if (sval_is_negative(min) && type_unsigned(type)) {
 671                 if (sval_is_positive(max)) {
 672                         if (sval_too_high(type, max)) {
 673                                 add_range(rl, sval_type_min(type), sval_type_max(type));
 674                                 return;
 675                         }
 676                         add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
 677                         max = sval_type_max(type);
 678                 } else {
 679                         max = sval_cast(type, max);
 680                 }
 681                 min = sval_cast(type, min);
 682                 add_range(rl, min, max);
 683         }
 684
 685         /* Cast high positive numbers to negative */
 686         if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
 687                 if (!sval_is_negative(sval_cast(type, min))) {
 688                         add_range(rl, sval_cast(type, min), sval_type_max(type));
 689                         min = sval_type_min(type);
 690                 } else {
 691                         min = sval_cast(type, min);
 692                 }
 693                 max = sval_cast(type, max);
 694                 add_range(rl, min, max);
 695         }
 696
 697         return;
 698 }
 699
 700 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
 701 {
 702         struct data_range *tmp;
 703         struct range_list *ret = NULL;
 704
 705         if (!rl)
 706                 return NULL;
 707
 708         if (!type)
 709                 return clone_rl(rl);
 710
 711         FOR_EACH_PTR(rl, tmp) {
 712                 add_range_t(type, &ret, tmp->min, tmp->max);
 713         } END_FOR_EACH_PTR(tmp);
 714
 715         if (!ret)
 716                 return alloc_whole_rl(type);
 717
 718         return ret;
 719 }
 720
 721 struct range_list *rl_invert(struct range_list *orig)
 722 {
 723         struct range_list *ret = NULL;
 724         struct data_range *tmp;
 725         sval_t gap_min, abs_max, sval;
 726
 727         if (!orig)
 728                 return NULL;
 729
 730         gap_min = sval_type_min(rl_min(orig).type);
 731         abs_max = sval_type_max(rl_max(orig).type);
 732
 733         FOR_EACH_PTR(orig, tmp) {
 734                 if (sval_cmp(tmp->min, gap_min) > 0) {
 735                         sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
 736                         add_range(&ret, gap_min, sval);
 737                 }
 738                 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
 739                 if (sval_cmp(tmp->max, abs_max) == 0)
 740                         gap_min = abs_max;
 741         } END_FOR_EACH_PTR(tmp);
 742
 743         if (sval_cmp(gap_min, abs_max) < 0)
 744                 add_range(&ret, gap_min, abs_max);
 745
 746         return ret;
 747 }
 748
 749 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
 750 {
 751         struct data_range *tmp;
 752
 753         FOR_EACH_PTR(filter, tmp) {
 754                 rl = remove_range(rl, tmp->min, tmp->max);
 755         } END_FOR_EACH_PTR(tmp);
 756
 757         return rl;
 758 }
 759
 760 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
 761 {
 762         if (!two)
 763                 return NULL;
 764         two = rl_invert(two);
 765         return rl_filter(one, two);
 766 }
 767
 768 void free_rl(struct range_list **rlist)
 769 {
 770         __free_ptr_list((struct ptr_list **)rlist);
 771 }
 772
 773 static void free_single_dinfo(struct data_info *dinfo)
 774 {
 775         free_rl(&dinfo->value_ranges);
 776 }
 777
 778 static void free_dinfos(struct allocation_blob *blob)
 779 {
 780         unsigned int size = sizeof(struct data_info);
 781         unsigned int offset = 0;
 782
 783         while (offset < blob->offset) {
 784                 free_single_dinfo((struct data_info *)(blob->data + offset));
 785                 offset += size;
 786         }
 787 }
 788
 789 void free_data_info_allocs(void)
 790 {
 791         struct allocator_struct *desc = &data_info_allocator;
 792         struct allocation_blob *blob = desc->blobs;
 793
 794         desc->blobs = NULL;
 795         desc->allocations = 0;
 796         desc->total_bytes = 0;
 797         desc->useful_bytes = 0;
 798         desc->freelist = NULL;
 799         while (blob) {
 800                 struct allocation_blob *next = blob->next;
 801                 free_dinfos(blob);
 802                 blob_free(blob, desc->chunking);
 803                 blob = next;
 804         }
 805         clear_data_range_alloc();
 806 }
 807