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