smatch_ranges.c

   1 /*
   2  * sparse/smatch_extra_helper.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;
 132
 133         FOR_EACH_PTR(*list, tmp) {
 134                 if (max != whole_range.max && max + 1 == tmp->min) {
 135                         /* join 2 ranges into a big range */
 136                         new = alloc_range(min, tmp->max);
 137                         REPLACE_CURRENT_PTR(tmp, new);
 138                         return;
 139                 }
 140                 if (max < tmp->min) {  /* new range entirely below */
 141                         new = alloc_range(min, max);
 142                         INSERT_CURRENT(new, tmp);
 143                         return;
 144                 }
 145                 if (min < tmp->min) { /* new range partially below */
 146                         if (max < tmp->max)
 147                                 max = tmp->max;
 148                         new = alloc_range(min, max);
 149                         REPLACE_CURRENT_PTR(tmp, new);
 150                         return;
 151                 }
 152                 if (max <= tmp->max) /* new range already included */
 153                         return;
 154                 if (min <= tmp->max) { /* new range partially above */
 155                         min = tmp->min;
 156                         new = alloc_range(min, max);
 157                         REPLACE_CURRENT_PTR(tmp, new);
 158                         return;
 159                 }
 160                 if (min != whole_range.min && min - 1 == tmp->max) {
 161                         /* join 2 ranges into a big range */
 162                         new = alloc_range(tmp->min, max);
 163                         REPLACE_CURRENT_PTR(tmp, new);
 164                         return;
 165                 }
 166         } END_FOR_EACH_PTR(tmp);
 167         new = alloc_range(min, max);
 168         add_ptr_list(list, new);
 169 }
 170
 171 struct range_list *clone_range_list(struct range_list *list)
 172 {
 173         struct data_range *tmp;
 174         struct range_list *ret = NULL;
 175
 176         FOR_EACH_PTR(list, tmp) {
 177                 add_ptr_list(&ret, tmp);
 178         } END_FOR_EACH_PTR(tmp);
 179         return ret;
 180 }
 181
 182 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 183 {
 184         struct data_range *tmp;
 185         struct range_list *ret = NULL;
 186
 187         if (!one || !two)  /*having nothing in a list means everything is in */
 188                 return NULL;
 189
 190         FOR_EACH_PTR(one, tmp) {
 191                 add_range(&ret, tmp->min, tmp->max);
 192         } END_FOR_EACH_PTR(tmp);
 193         FOR_EACH_PTR(two, tmp) {
 194                 add_range(&ret, tmp->min, tmp->max);
 195         } END_FOR_EACH_PTR(tmp);
 196         return ret;
 197 }
 198
 199 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 200 {
 201         struct data_range *tmp;
 202         struct range_list *ret = NULL;
 203
 204         FOR_EACH_PTR(list, tmp) {
 205                 if (tmp->max < min) {
 206                         add_range(&ret, tmp->min, tmp->max);
 207                         continue;
 208                 }
 209                 if (tmp->min > max) {
 210                         add_range(&ret, tmp->min, tmp->max);
 211                         continue;
 212                 }
 213                 if (tmp->min >= min && tmp->max <= max)
 214                         continue;
 215                 if (tmp->min >= min) {
 216                         add_range(&ret, max + 1, tmp->max);
 217                 } else if (tmp->max <= max) {
 218                         add_range(&ret, tmp->min, min - 1);
 219                 } else {
 220                         add_range(&ret, tmp->min, min - 1);
 221                         add_range(&ret, max + 1, tmp->max);
 222                 }
 223         } END_FOR_EACH_PTR(tmp);
 224         return ret;
 225 }
 226
 227 long long get_dinfo_min(struct data_info *dinfo)
 228 {
 229         struct data_range *drange;
 230
 231         if (!dinfo || !dinfo->value_ranges)
 232                 return whole_range.min;
 233         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 234         return drange->min;
 235 }
 236
 237 long long get_dinfo_max(struct data_info *dinfo)
 238 {
 239         struct data_range *drange;
 240
 241         if (!dinfo || !dinfo->value_ranges)
 242                 return whole_range.max;
 243         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 244         return drange->max;
 245 }
 246
 247 /*
 248  * if it can be only one value return that, else return UNDEFINED
 249  */
 250 long long get_single_value_from_range(struct data_info *dinfo)
 251 {
 252         struct data_range *tmp;
 253         int count = 0;
 254         long long ret = UNDEFINED;
 255
 256         if (dinfo->type != DATA_RANGE)
 257                 return UNDEFINED;
 258
 259         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 260                 if (!count++) {
 261                         if (tmp->min != tmp->max)
 262                                 return UNDEFINED;
 263                         ret = tmp->min;
 264                 } else {
 265                         return UNDEFINED;
 266                 }
 267         } END_FOR_EACH_PTR(tmp);
 268         return ret;
 269 }
 270
 271 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 272 {
 273         switch(comparison){
 274         case '<':
 275         case SPECIAL_UNSIGNED_LT:
 276                 if (left->min < right->max)
 277                         return 1;
 278                 return 0;
 279         case SPECIAL_UNSIGNED_LTE:
 280         case SPECIAL_LTE:
 281                 if (left->min <= right->max)
 282                         return 1;
 283                 return 0;
 284         case SPECIAL_EQUAL:
 285                 if (left->max < right->min)
 286                         return 0;
 287                 if (left->min > right->max)
 288                         return 0;
 289                 return 1;
 290         case SPECIAL_UNSIGNED_GTE:
 291         case SPECIAL_GTE:
 292                 if (left->max >= right->min)
 293                         return 1;
 294                 return 0;
 295         case '>':
 296         case SPECIAL_UNSIGNED_GT:
 297                 if (left->max > right->min)
 298                         return 1;
 299                 return 0;
 300         case SPECIAL_NOTEQUAL:
 301                 if (left->min != left->max)
 302                         return 1;
 303                 if (right->min != right->max)
 304                         return 1;
 305                 if (left->min != right->min)
 306                         return 1;
 307                 return 0;
 308         default:
 309                 smatch_msg("unhandled comparison %d\n", comparison);
 310                 return UNDEFINED;
 311         }
 312         return 0;
 313 }
 314
 315 int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 316 {
 317         if (left)
 318                 return true_comparison_range(var, comparison, val);
 319         else
 320                 return true_comparison_range(val, comparison, var);
 321 }
 322
 323 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 324 {
 325         switch(comparison){
 326         case '<':
 327         case SPECIAL_UNSIGNED_LT:
 328                 if (left->max >= right->min)
 329                         return 1;
 330                 return 0;
 331         case SPECIAL_UNSIGNED_LTE:
 332         case SPECIAL_LTE:
 333                 if (left->max > right->min)
 334                         return 1;
 335                 return 0;
 336         case SPECIAL_EQUAL:
 337                 if (left->min != left->max)
 338                         return 1;
 339                 if (right->min != right->max)
 340                         return 1;
 341                 if (left->min != right->min)
 342                         return 1;
 343                 return 0;
 344         case SPECIAL_UNSIGNED_GTE:
 345         case SPECIAL_GTE:
 346                 if (left->min < right->max)
 347                         return 1;
 348                 return 0;
 349         case '>':
 350         case SPECIAL_UNSIGNED_GT:
 351                 if (left->min <= right->max)
 352                         return 1;
 353                 return 0;
 354         case SPECIAL_NOTEQUAL:
 355                 if (left->max < right->min)
 356                         return 0;
 357                 if (left->min > right->max)
 358                         return 0;
 359                 return 1;
 360         default:
 361                 smatch_msg("unhandled comparison %d\n", comparison);
 362                 return UNDEFINED;
 363         }
 364         return 0;
 365 }
 366
 367 int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left)
 368 {
 369         if (left)
 370                 return false_comparison_range(var, comparison, val);
 371         else
 372                 return false_comparison_range(val, comparison, var);
 373 }
 374
 375 int possibly_true(int comparison, struct data_info *dinfo, int num, int left)
 376 {
 377         struct data_range *tmp;
 378         struct data_range drange;
 379
 380         drange.min = num;
 381         drange.max = num;
 382
 383         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 384                 if (true_comparison_range_lr(comparison, tmp, &drange, left))
 385                         return 1;
 386         } END_FOR_EACH_PTR(tmp);
 387         return 0;
 388 }
 389
 390 int possibly_false(int comparison, struct data_info *dinfo, int num, int left)
 391 {
 392         struct data_range *tmp;
 393         struct data_range drange;
 394
 395         drange.min = num;
 396         drange.max = num;
 397
 398         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 399                 if (false_comparison_range_lr(comparison, tmp, &drange, left))
 400                         return 1;
 401         } END_FOR_EACH_PTR(tmp);
 402         return 0;
 403 }
 404
 405 int possibly_true_range_list(int comparison, struct data_info *dinfo, struct range_list *values, int left)
 406 {
 407         struct data_range *tmp, *tmp2;
 408
 409         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 410                 FOR_EACH_PTR(values, tmp2) {
 411                         if (true_comparison_range_lr(comparison, tmp, tmp2, left))
 412                                 return 1;
 413                 } END_FOR_EACH_PTR(tmp2);
 414         } END_FOR_EACH_PTR(tmp);
 415         return 0;
 416 }
 417
 418 int possibly_false_range_list(int comparison, struct data_info *dinfo, struct range_list *values, int left)
 419 {
 420         struct data_range *tmp, *tmp2;
 421
 422         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 423                 FOR_EACH_PTR(values, tmp2) {
 424                         if (false_comparison_range_lr(comparison, tmp, tmp2, left))
 425                                 return 1;
 426                 } END_FOR_EACH_PTR(tmp2);
 427         } END_FOR_EACH_PTR(tmp);
 428         return 0;
 429 }
 430
 431 void tack_on(struct range_list **list, struct data_range *drange)
 432 {
 433         add_ptr_list(list, drange);
 434 }
 435
 436 int in_list_exact(struct range_list *list, struct data_range *drange)
 437 {
 438         struct data_range *tmp;
 439
 440         FOR_EACH_PTR(list, tmp) {
 441                 if (tmp->min == drange->min && tmp->max == drange->max)
 442                         return 1;
 443         } END_FOR_EACH_PTR(tmp);
 444         return 0;
 445
 446 }
 447
 448 void push_range_list(struct range_list_stack **rl_stack, struct range_list *rl)
 449 {
 450         add_ptr_list(rl_stack, rl);
 451 }
 452
 453 struct range_list *pop_range_list(struct range_list_stack **rl_stack)
 454 {
 455         struct range_list *rl;
 456
 457         rl = last_ptr_list((struct ptr_list *)*rl_stack);
 458         delete_ptr_list_last((struct ptr_list **)rl_stack);
 459         return rl;
 460 }
 461
 462 struct range_list *top_range_list(struct range_list_stack *rl_stack)
 463 {
 464         struct range_list *rl;
 465
 466         rl = last_ptr_list((struct ptr_list *)rl_stack);
 467         return rl;
 468 }
 469
 470 void filter_top_range_list(struct range_list_stack **rl_stack, long long num)
 471 {
 472         struct range_list *rl;
 473
 474         rl = pop_range_list(rl_stack);
 475         rl = remove_range(rl, num, num);
 476         push_range_list(rl_stack, rl);
 477 }
 478
 479 static void free_single_dinfo(struct data_info *dinfo)
 480 {
 481         if (dinfo->type == DATA_RANGE)
 482                 __free_ptr_list((struct ptr_list **)&dinfo->value_ranges);
 483 }
 484
 485 static void free_dinfos(struct allocation_blob *blob)
 486 {
 487         unsigned int size = sizeof(struct data_info);
 488         unsigned int offset = 0;
 489
 490         while (offset < blob->offset) {
 491                 free_single_dinfo((struct data_info *)(blob->data + offset));
 492                 offset += size;
 493         }
 494 }
 495
 496 void free_data_info_allocs(void)
 497 {
 498         struct allocator_struct *desc = &data_info_allocator;
 499         struct allocation_blob *blob = desc->blobs;
 500
 501         desc->blobs = NULL;
 502         desc->allocations = 0;
 503         desc->total_bytes = 0;
 504         desc->useful_bytes = 0;
 505         desc->freelist = NULL;
 506         while (blob) {
 507                 struct allocation_blob *next = blob->next;
 508                 free_dinfos(blob);
 509                 blob_free(blob, desc->chunking);
 510                 blob = next;
 511         }
 512         clear_data_range_alloc();
 513 }
 514