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