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