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 struct data_range whole_range = {
  21         .min = LLONG_MIN,
  22         .max = LLONG_MAX,
  23 };
  24
  25 static char *show_num(long long num)
  26 {
  27         static char buff[256];
  28
  29         if (num == whole_range.min)
  30                 snprintf(buff, 255, "min");
  31         else if (num == whole_range.max)
  32                 snprintf(buff, 255, "max");
  33         else if (num < 0)
  34                 snprintf(buff, 255, "(%lld)", num);
  35         else
  36                 snprintf(buff, 255, "%lld", num);
  37
  38         buff[255] = '\0';
  39         return buff;
  40 }
  41
  42 char *show_ranges(struct range_list *list)
  43 {
  44         struct data_range *tmp;
  45         char full[256];
  46         int i = 0;
  47
  48         full[0] = '\0';
  49         full[255] = '\0';
  50         FOR_EACH_PTR(list, tmp) {
  51                 if (i++)
  52                         strncat(full, ",", 254 - strlen(full));
  53                 if (tmp->min == tmp->max) {
  54                         strncat(full, show_num(tmp->min), 254 - strlen(full));
  55                         continue;
  56                 }
  57                 strncat(full, show_num(tmp->min), 254 - strlen(full));
  58                 strncat(full, "-", 254 - strlen(full));
  59                 strncat(full, show_num(tmp->max), 254 - strlen(full));
  60         } END_FOR_EACH_PTR(tmp);
  61         return alloc_sname(full);
  62 }
  63
  64 void get_value_ranges(char *value, struct range_list **rl)
  65 {
  66         long long val1, val2;
  67         char *start;
  68         char *c;
  69
  70         *rl = NULL;
  71
  72         c = value;
  73         while (*c) {
  74                 if (*c == '(')
  75                         c++;
  76                 start = c;
  77                 if (!strncmp(start, "min", 3)) {
  78                         val1 = LLONG_MIN;
  79                         c += 3;
  80                 } else if (!strncmp(start, "max", 3)) {
  81                         val1 = LLONG_MAX;
  82                         c += 3;
  83                 } else {
  84                         while (*c && *c != ',' && *c != '-')
  85                                 c++;
  86                         val1 = strtoll(start, &c, 10);
  87                 }
  88                 if (*c == ')')
  89                         c++;
  90                 if (!*c) {
  91                         add_range(rl, val1, val1);
  92                         break;
  93                 }
  94                 if (*c == ',') {
  95                         add_range(rl, val1, val1);
  96                         c++;
  97                         start = c;
  98                         continue;
  99                 }
 100                 c++; /* skip the dash in eg. 4-5 */
 101                 if (*c == '(')
 102                         c++;
 103                 start = c;
 104                 if (!strncmp(start, "max", 3)) {
 105                         val2 = LLONG_MAX;
 106                         c += 3;
 107                 } else {
 108
 109                         while (*c && *c != ',' && *c != '-')
 110                                 c++;
 111                         val2 = strtoll(start, &c, 10);
 112                 }
 113                 add_range(rl, val1, val2);
 114                 if (!*c)
 115                         break;
 116                 if (*c == ')')
 117                         c++;
 118                 c++; /* skip the comma in eg: 4-5,7 */
 119         }
 120 }
 121
 122 static struct data_range range_zero = {
 123         .min = 0,
 124         .max = 0,
 125 };
 126
 127 static struct data_range range_one = {
 128         .min = 1,
 129         .max = 1,
 130 };
 131
 132 int is_whole_range_rl(struct range_list *rl)
 133 {
 134         struct data_range *drange;
 135
 136         if (ptr_list_empty(rl))
 137                 return 1;
 138         drange = first_ptr_list((struct ptr_list *)rl);
 139         if (drange->min == whole_range.min && drange->max == whole_range.max)
 140                 return 1;
 141         return 0;
 142 }
 143
 144 int rl_contiguous(struct range_list *rl)
 145 {
 146         if (first_ptr_list((struct ptr_list *)rl) == last_ptr_list((struct ptr_list *)rl))
 147                 return 1;
 148         return 0;
 149 }
 150
 151 long long rl_min(struct range_list *rl)
 152 {
 153         struct data_range *drange;
 154
 155         if (ptr_list_empty(rl))
 156                 return whole_range.min;
 157         drange = first_ptr_list((struct ptr_list *)rl);
 158         return drange->min;
 159 }
 160
 161 long long rl_max(struct range_list *rl)
 162 {
 163         struct data_range *drange;
 164
 165         if (ptr_list_empty(rl))
 166                 return whole_range.max;
 167         drange = last_ptr_list((struct ptr_list *)rl);
 168         return drange->max;
 169 }
 170
 171 static struct data_range *alloc_range_helper(long long min, long long max, int perm)
 172 {
 173         struct data_range *ret;
 174
 175         if (min > max) {
 176                 // sm_msg("debug invalid range %lld to %lld", min, max);
 177                 min = whole_range.min;
 178                 max = whole_range.max;
 179         }
 180         if (min == whole_range.min && max == whole_range.max)
 181                 return &whole_range;
 182         if (min == 0 && max == 0)
 183                 return &range_zero;
 184         if (min == 1 && max == 1)
 185                 return &range_one;
 186
 187         if (perm)
 188                 ret = __alloc_perm_data_range(0);
 189         else
 190                 ret = __alloc_data_range(0);
 191         ret->min = min;
 192         ret->max = max;
 193         return ret;
 194 }
 195
 196 struct data_range *alloc_range(long long min, long long max)
 197 {
 198         return alloc_range_helper(min, max, 0);
 199 }
 200
 201 struct data_range *alloc_range_perm(long long min, long long max)
 202 {
 203         return alloc_range_helper(min, max, 1);
 204 }
 205
 206 struct range_list *alloc_range_list(long long min, long long max)
 207 {
 208         struct range_list *rl = NULL;
 209
 210         add_range(&rl, min, max);
 211         return rl;
 212 }
 213
 214 struct range_list *whole_range_list(void)
 215 {
 216         return alloc_range_list(whole_range.min, whole_range.max);
 217 }
 218
 219 void add_range(struct range_list **list, long long min, long long max)
 220 {
 221         struct data_range *tmp = NULL;
 222         struct data_range *new = NULL;
 223         int check_next = 0;
 224
 225         /*
 226          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 227          * with a range like 1-2.  You end up with min-2,3-max instead of
 228          * just min-max.
 229          */
 230         FOR_EACH_PTR(*list, tmp) {
 231                 if (check_next) {
 232                         /* Sometimes we overlap with more than one range
 233                            so we have to delete or modify the next range. */
 234                         if (max + 1 == tmp->min) {
 235                                 /* join 2 ranges here */
 236                                 new->max = tmp->max;
 237                                 DELETE_CURRENT_PTR(tmp);
 238                                 return;
 239                         }
 240
 241                         /* Doesn't overlap with the next one. */
 242                         if (max < tmp->min)
 243                                 return;
 244                         /* Partially overlaps with the next one. */
 245                         if (max < tmp->max) {
 246                                 tmp->min = max + 1;
 247                                 return;
 248                         }
 249                         /* Completely overlaps with the next one. */
 250                         if (max >= tmp->max) {
 251                                 DELETE_CURRENT_PTR(tmp);
 252                                 /* there could be more ranges to delete */
 253                                 continue;
 254                         }
 255                 }
 256                 if (max != whole_range.max && max + 1 == tmp->min) {
 257                         /* join 2 ranges into a big range */
 258                         new = alloc_range(min, tmp->max);
 259                         REPLACE_CURRENT_PTR(tmp, new);
 260                         return;
 261                 }
 262                 if (max < tmp->min) {  /* new range entirely below */
 263                         new = alloc_range(min, max);
 264                         INSERT_CURRENT(new, tmp);
 265                         return;
 266                 }
 267                 if (min < tmp->min) { /* new range partially below */
 268                         if (max < tmp->max)
 269                                 max = tmp->max;
 270                         else
 271                                 check_next = 1;
 272                         new = alloc_range(min, max);
 273                         REPLACE_CURRENT_PTR(tmp, new);
 274                         if (!check_next)
 275                                 return;
 276                         continue;
 277                 }
 278                 if (max <= tmp->max) /* new range already included */
 279                         return;
 280                 if (min <= tmp->max) { /* new range partially above */
 281                         min = tmp->min;
 282                         new = alloc_range(min, max);
 283                         REPLACE_CURRENT_PTR(tmp, new);
 284                         check_next = 1;
 285                         continue;
 286                 }
 287                 if (min != whole_range.min && min - 1 == tmp->max) {
 288                         /* join 2 ranges into a big range */
 289                         new = alloc_range(tmp->min, max);
 290                         REPLACE_CURRENT_PTR(tmp, new);
 291                         check_next = 1;
 292                         continue;
 293                 }
 294                 /* the new range is entirely above the existing ranges */
 295         } END_FOR_EACH_PTR(tmp);
 296         if (check_next)
 297                 return;
 298         new = alloc_range(min, max);
 299         add_ptr_list(list, new);
 300 }
 301
 302 struct range_list *clone_range_list(struct range_list *list)
 303 {
 304         struct data_range *tmp;
 305         struct range_list *ret = NULL;
 306
 307         FOR_EACH_PTR(list, tmp) {
 308                 add_ptr_list(&ret, tmp);
 309         } END_FOR_EACH_PTR(tmp);
 310         return ret;
 311 }
 312
 313 struct range_list *clone_permanent(struct range_list *list)
 314 {
 315         struct data_range *tmp;
 316         struct data_range *new;
 317         struct range_list *ret = NULL;
 318
 319         FOR_EACH_PTR(list, tmp) {
 320                 new = alloc_range_perm(tmp->min, tmp->max);
 321                 add_ptr_list(&ret, new);
 322         } END_FOR_EACH_PTR(tmp);
 323         return ret;
 324 }
 325
 326 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 327 {
 328         struct data_range *tmp;
 329         struct range_list *ret = NULL;
 330
 331         FOR_EACH_PTR(one, tmp) {
 332                 add_range(&ret, tmp->min, tmp->max);
 333         } END_FOR_EACH_PTR(tmp);
 334         FOR_EACH_PTR(two, tmp) {
 335                 add_range(&ret, tmp->min, tmp->max);
 336         } END_FOR_EACH_PTR(tmp);
 337         return ret;
 338 }
 339
 340 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 341 {
 342         struct data_range *tmp;
 343         struct range_list *ret = NULL;
 344
 345         FOR_EACH_PTR(list, tmp) {
 346                 if (tmp->max < min) {
 347                         add_range(&ret, tmp->min, tmp->max);
 348                         continue;
 349                 }
 350                 if (tmp->min > max) {
 351                         add_range(&ret, tmp->min, tmp->max);
 352                         continue;
 353                 }
 354                 if (tmp->min >= min && tmp->max <= max)
 355                         continue;
 356                 if (tmp->min >= min) {
 357                         add_range(&ret, max + 1, tmp->max);
 358                 } else if (tmp->max <= max) {
 359                         add_range(&ret, tmp->min, min - 1);
 360                 } else {
 361                         add_range(&ret, tmp->min, min - 1);
 362                         add_range(&ret, max + 1, tmp->max);
 363                 }
 364         } END_FOR_EACH_PTR(tmp);
 365         return ret;
 366 }
 367
 368 struct range_list *invert_range_list(struct range_list *orig)
 369 {
 370         struct range_list *ret = NULL;
 371         struct data_range *tmp;
 372         long long gap_min;
 373
 374         if (!orig)
 375                 return NULL;
 376
 377         gap_min = whole_range.min;
 378         FOR_EACH_PTR(orig, tmp) {
 379                 if (tmp->min > gap_min)
 380                         add_range(&ret, gap_min, tmp->min - 1);
 381                 gap_min = tmp->max + 1;
 382                 if (tmp->max == whole_range.max)
 383                         gap_min = whole_range.max;
 384         } END_FOR_EACH_PTR(tmp);
 385
 386         if (gap_min != whole_range.max)
 387                 add_range(&ret, gap_min, whole_range.max);
 388
 389         return ret;
 390 }
 391
 392 /*
 393  * if it can be only one and only value return 1, else return 0
 394  */
 395 int estate_get_single_value(struct smatch_state *state, long long *val)
 396 {
 397         struct data_info *dinfo;
 398         struct data_range *tmp;
 399         int count = 0;
 400
 401         dinfo = get_dinfo(state);
 402         if (!dinfo || dinfo->type != DATA_RANGE)
 403                 return 0;
 404
 405         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 406                 if (!count++) {
 407                         if (tmp->min != tmp->max)
 408                                 return 0;
 409                         *val = tmp->min;
 410                 } else {
 411                         return 0;
 412                 }
 413         } END_FOR_EACH_PTR(tmp);
 414         return count;
 415 }
 416
 417 int range_lists_equiv(struct range_list *one, struct range_list *two)
 418 {
 419         struct data_range *one_range;
 420         struct data_range *two_range;
 421
 422         PREPARE_PTR_LIST(one, one_range);
 423         PREPARE_PTR_LIST(two, two_range);
 424         for (;;) {
 425                 if (!one_range && !two_range)
 426                         return 1;
 427                 if (!one_range || !two_range)
 428                         return 0;
 429                 if (one_range->min != two_range->min)
 430                         return 0;
 431                 if (one_range->max != two_range->max)
 432                         return 0;
 433                 NEXT_PTR_LIST(one_range);
 434                 NEXT_PTR_LIST(two_range);
 435         }
 436         FINISH_PTR_LIST(two_range);
 437         FINISH_PTR_LIST(one_range);
 438
 439         return 1;
 440 }
 441
 442 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 443 {
 444         switch (comparison) {
 445         case '<':
 446         case SPECIAL_UNSIGNED_LT:
 447                 if (left->min < right->max)
 448                         return 1;
 449                 return 0;
 450         case SPECIAL_UNSIGNED_LTE:
 451         case SPECIAL_LTE:
 452                 if (left->min <= right->max)
 453                         return 1;
 454                 return 0;
 455         case SPECIAL_EQUAL:
 456                 if (left->max < right->min)
 457                         return 0;
 458                 if (left->min > right->max)
 459                         return 0;
 460                 return 1;
 461         case SPECIAL_UNSIGNED_GTE:
 462         case SPECIAL_GTE:
 463                 if (left->max >= right->min)
 464                         return 1;
 465                 return 0;
 466         case '>':
 467         case SPECIAL_UNSIGNED_GT:
 468                 if (left->max > right->min)
 469                         return 1;
 470                 return 0;
 471         case SPECIAL_NOTEQUAL:
 472                 if (left->min != left->max)
 473                         return 1;
 474                 if (right->min != right->max)
 475                         return 1;
 476                 if (left->min != right->min)
 477                         return 1;
 478                 return 0;
 479         default:
 480                 sm_msg("unhandled comparison %d\n", comparison);
 481                 return 0;
 482         }
 483         return 0;
 484 }
 485
 486 int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 487 {
 488         if (left)
 489                 return true_comparison_range(var, comparison, val);
 490         else
 491                 return true_comparison_range(val, comparison, var);
 492 }
 493
 494 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 495 {
 496         switch (comparison) {
 497         case '<':
 498         case SPECIAL_UNSIGNED_LT:
 499                 if (left->max >= right->min)
 500                         return 1;
 501                 return 0;
 502         case SPECIAL_UNSIGNED_LTE:
 503         case SPECIAL_LTE:
 504                 if (left->max > right->min)
 505                         return 1;
 506                 return 0;
 507         case SPECIAL_EQUAL:
 508                 if (left->min != left->max)
 509                         return 1;
 510                 if (right->min != right->max)
 511                         return 1;
 512                 if (left->min != right->min)
 513                         return 1;
 514                 return 0;
 515         case SPECIAL_UNSIGNED_GTE:
 516         case SPECIAL_GTE:
 517                 if (left->min < right->max)
 518                         return 1;
 519                 return 0;
 520         case '>':
 521         case SPECIAL_UNSIGNED_GT:
 522                 if (left->min <= right->max)
 523                         return 1;
 524                 return 0;
 525         case SPECIAL_NOTEQUAL:
 526                 if (left->max < right->min)
 527                         return 0;
 528                 if (left->min > right->max)
 529                         return 0;
 530                 return 1;
 531         default:
 532                 sm_msg("unhandled comparison %d\n", comparison);
 533                 return 0;
 534         }
 535         return 0;
 536 }
 537
 538 int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 539 {
 540         if (left)
 541                 return false_comparison_range(var, comparison, val);
 542         else
 543                 return false_comparison_range(val, comparison, var);
 544 }
 545
 546 int possibly_true(struct expression *left, int comparison, struct expression *right)
 547 {
 548         struct range_list *rl_left, *rl_right;
 549         struct data_range *tmp_left, *tmp_right;
 550
 551         if (!get_implied_range_list(left, &rl_left))
 552                 return 1;
 553         if (!get_implied_range_list(right, &rl_right))
 554                 return 1;
 555
 556         FOR_EACH_PTR(rl_left, tmp_left) {
 557                 FOR_EACH_PTR(rl_right, tmp_right) {
 558                         if (true_comparison_range(tmp_left, comparison, tmp_right))
 559                                 return 1;
 560                 } END_FOR_EACH_PTR(tmp_right);
 561         } END_FOR_EACH_PTR(tmp_left);
 562         return 0;
 563 }
 564
 565 int possibly_false(struct expression *left, int comparison, struct expression *right)
 566 {
 567         struct range_list *rl_left, *rl_right;
 568         struct data_range *tmp_left, *tmp_right;
 569
 570         if (!get_implied_range_list(left, &rl_left))
 571                 return 1;
 572         if (!get_implied_range_list(right, &rl_right))
 573                 return 1;
 574
 575         FOR_EACH_PTR(rl_left, tmp_left) {
 576                 FOR_EACH_PTR(rl_right, tmp_right) {
 577                         if (false_comparison_range(tmp_left, comparison, tmp_right))
 578                                 return 1;
 579                 } END_FOR_EACH_PTR(tmp_right);
 580         } END_FOR_EACH_PTR(tmp_left);
 581         return 0;
 582 }
 583
 584 int possibly_true_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 585 {
 586         struct data_range *left_tmp, *right_tmp;
 587
 588         if (!left_ranges || !right_ranges)
 589                 return 1;
 590
 591         FOR_EACH_PTR(left_ranges, left_tmp) {
 592                 FOR_EACH_PTR(right_ranges, right_tmp) {
 593                         if (true_comparison_range(left_tmp, comparison, right_tmp))
 594                                 return 1;
 595                 } END_FOR_EACH_PTR(right_tmp);
 596         } END_FOR_EACH_PTR(left_tmp);
 597         return 0;
 598 }
 599
 600 int possibly_false_range_lists(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
 601 {
 602         struct data_range *left_tmp, *right_tmp;
 603
 604         if (!left_ranges || !right_ranges)
 605                 return 1;
 606
 607         FOR_EACH_PTR(left_ranges, left_tmp) {
 608                 FOR_EACH_PTR(right_ranges, right_tmp) {
 609                         if (false_comparison_range(left_tmp, comparison, right_tmp))
 610                                 return 1;
 611                 } END_FOR_EACH_PTR(right_tmp);
 612         } END_FOR_EACH_PTR(left_tmp);
 613         return 0;
 614 }
 615
 616 int possibly_true_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 617 {
 618         if (left)
 619                 return possibly_true_range_lists(a, comparison, b);
 620         else
 621                 return possibly_true_range_lists(b, comparison, a);
 622 }
 623
 624 int possibly_false_range_lists_rl(int comparison, struct range_list *a, struct range_list *b, int left)
 625 {
 626         if (left)
 627                 return possibly_false_range_lists(a, comparison, b);
 628         else
 629                 return possibly_false_range_lists(b, comparison, a);
 630 }
 631
 632 void tack_on(struct range_list **list, struct data_range *drange)
 633 {
 634         add_ptr_list(list, drange);
 635 }
 636
 637 int in_list_exact(struct range_list *list, struct data_range *drange)
 638 {
 639         struct data_range *tmp;
 640
 641         FOR_EACH_PTR(list, tmp) {
 642                 if (tmp->min == drange->min && tmp->max == drange->max)
 643                         return 1;
 644         } END_FOR_EACH_PTR(tmp);
 645         return 0;
 646 }
 647
 648 void push_range_list(struct range_list_stack **rl_stack, struct range_list *rl)
 649 {
 650         add_ptr_list(rl_stack, rl);
 651 }
 652
 653 struct range_list *pop_range_list(struct range_list_stack **rl_stack)
 654 {
 655         struct range_list *rl;
 656
 657         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 658         delete_ptr_list_last((struct ptr_list **)rl_stack);
 659         return rl;
 660 }
 661
 662 struct range_list *top_range_list(struct range_list_stack *rl_stack)
 663 {
 664         struct range_list *rl;
 665
 666         rl = last_ptr_list((struct ptr_list *)rl_stack);
 667         return rl;
 668 }
 669
 670 void filter_top_range_list(struct range_list_stack **rl_stack, long long num)
 671 {
 672         struct range_list *rl;
 673
 674         rl = pop_range_list(rl_stack);
 675         rl = remove_range(rl, num, num);
 676         push_range_list(rl_stack, rl);
 677 }
 678
 679 void free_range_list(struct range_list **rlist)
 680 {
 681         __free_ptr_list((struct ptr_list **)rlist);
 682 }
 683
 684 static void free_single_dinfo(struct data_info *dinfo)
 685 {
 686         if (dinfo->type == DATA_RANGE)
 687                 free_range_list(&dinfo->value_ranges);
 688 }
 689
 690 static void free_dinfos(struct allocation_blob *blob)
 691 {
 692         unsigned int size = sizeof(struct data_info);
 693         unsigned int offset = 0;
 694
 695         while (offset < blob->offset) {
 696                 free_single_dinfo((struct data_info *)(blob->data + offset));
 697                 offset += size;
 698         }
 699 }
 700
 701 void free_data_info_allocs(void)
 702 {
 703         struct allocator_struct *desc = &data_info_allocator;
 704         struct allocation_blob *blob = desc->blobs;
 705
 706         desc->blobs = NULL;
 707         desc->allocations = 0;
 708         desc->total_bytes = 0;
 709         desc->useful_bytes = 0;
 710         desc->freelist = NULL;
 711         while (blob) {
 712                 struct allocation_blob *next = blob->next;
 713                 free_dinfos(blob);
 714                 blob_free(blob, desc->chunking);
 715                 blob = next;
 716         }
 717         clear_data_range_alloc();
 718 }
 719