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