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