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