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