smatch_extra_helper.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
  18 static char *show_num(long long num)
  19 {
  20         static char buff[256];
  21
  22         if (num == whole_range.min) {
  23                 snprintf(buff, 255, "min");
  24         } else if (num == whole_range.max) {
  25                 snprintf(buff, 255, "max");
  26         } else if (num < 0) {
  27                 snprintf(buff, 255, "(%lld)", num);
  28         } else {
  29                 snprintf(buff, 255, "%lld", num);
  30         }
  31         buff[255] = '\0';
  32         return buff;
  33 }
  34
  35 char *show_ranges(struct range_list *list)
  36 {
  37         struct data_range *tmp;
  38         char full[256];
  39         int i = 0;
  40
  41         full[0] = '\0';
  42         full[255] = '\0';
  43         FOR_EACH_PTR(list, tmp) {
  44                 if (i++)
  45                         strncat(full, ",", 254 - strlen(full));
  46                 if (tmp->min == tmp->max) {
  47                         strncat(full, show_num(tmp->min), 254 - strlen(full));
  48                         continue;
  49                 }
  50                 strncat(full, show_num(tmp->min), 254 - strlen(full));
  51                 strncat(full, "-", 254 - strlen(full));
  52                 strncat(full, show_num(tmp->max), 254 - strlen(full));
  53         } END_FOR_EACH_PTR(tmp);
  54         return alloc_sname(full);
  55 }
  56
  57 static struct data_range range_zero = {
  58         .min = 0,
  59         .max = 0,
  60 };
  61
  62 static struct data_range range_one = {
  63         .min = 1,
  64         .max = 1,
  65 };
  66
  67 struct data_range *alloc_range(long long min, long long max)
  68 {
  69         struct data_range *ret;
  70
  71         if (min > max) {
  72                 printf("Error invalid range %lld to %lld\n", min, max);
  73         }
  74         if (min == whole_range.min && max == whole_range.max)
  75                 return &whole_range;
  76         if (min == 0 && max == 0)
  77                 return &range_zero;
  78         if (min == 1 && max == 1)
  79                 return &range_one;
  80         ret = __alloc_data_range(0);
  81         ret->min = min;
  82         ret->max = max;
  83         return ret;
  84 }
  85
  86 struct data_info *alloc_dinfo_range(long long min, long long max)
  87 {
  88         struct data_info *ret;
  89
  90         ret = __alloc_data_info(0);
  91         ret->type = DATA_RANGE;
  92         ret->merged = 0;
  93         ret->value_ranges = NULL;
  94         add_range(&ret->value_ranges, min, max);
  95         return ret;
  96 }
  97
  98 void add_range(struct range_list **list, long long min, long long max)
  99 {
 100         struct data_range *tmp = NULL;
 101         struct data_range *new;
 102
 103         FOR_EACH_PTR(*list, tmp) {
 104                 if (max != whole_range.max && max + 1 == tmp->min) {
 105                         /* join 2 ranges into a big range */
 106                         new = alloc_range(min, tmp->max);
 107                         REPLACE_CURRENT_PTR(tmp, new);
 108                         return;
 109                 }
 110                 if (max < tmp->min) {  /* new range entirely below */
 111                         new = alloc_range(min, max);
 112                         INSERT_CURRENT(new, tmp);
 113                         return;
 114                 }
 115                 if (min < tmp->min) { /* new range partially below */
 116                         if (max < tmp->max)
 117                                 max = tmp->max;
 118                         new = alloc_range(min, max);
 119                         REPLACE_CURRENT_PTR(tmp, new);
 120                         return;
 121                 }
 122                 if (max <= tmp->max) /* new range already included */
 123                         return;
 124                 if (min <= tmp->max) { /* new range partially above */
 125                         min = tmp->min;
 126                         new = alloc_range(min, max);
 127                         REPLACE_CURRENT_PTR(tmp, new);
 128                         return;
 129                 }
 130                 if (min != whole_range.min && min - 1 == tmp->max) {
 131                         /* join 2 ranges into a big range */
 132                         new = alloc_range(tmp->min, max);
 133                         REPLACE_CURRENT_PTR(tmp, new);
 134                         return;
 135                 }
 136         } END_FOR_EACH_PTR(tmp);
 137         new = alloc_range(min, max);
 138         add_ptr_list(list, new);
 139 }
 140
 141 struct range_list *clone_range_list(struct range_list *list)
 142 {
 143         struct data_range *tmp;
 144         struct range_list *ret = NULL;
 145
 146         FOR_EACH_PTR(list, tmp) {
 147                 add_ptr_list(&ret, tmp);
 148         } END_FOR_EACH_PTR(tmp);
 149         return ret;
 150 }
 151
 152 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 153 {
 154         struct data_range *tmp;
 155         struct range_list *ret = NULL;
 156
 157         if (!one || !two)  /*having nothing in a list means everything is in */
 158                 return NULL;
 159
 160         FOR_EACH_PTR(one, tmp) {
 161                 add_range(&ret, tmp->min, tmp->max);
 162         } END_FOR_EACH_PTR(tmp);
 163         FOR_EACH_PTR(two, tmp) {
 164                 add_range(&ret, tmp->min, tmp->max);
 165         } END_FOR_EACH_PTR(tmp);
 166         return ret;
 167 }
 168
 169 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 170 {
 171         struct data_range *tmp;
 172         struct range_list *ret = NULL;
 173
 174         FOR_EACH_PTR(list, tmp) {
 175                 if (tmp->max < min) {
 176                         add_range(&ret, tmp->min, tmp->max);
 177                         continue;
 178                 }
 179                 if (tmp->min > max) {
 180                         add_range(&ret, tmp->min, tmp->max);
 181                         continue;
 182                 }
 183                 if (tmp->min >= min && tmp->max <= max)
 184                         continue;
 185                 if (tmp->min >= min) {
 186                         add_range(&ret, max + 1, tmp->max);
 187                 } else if (tmp->max <= max) {
 188                         add_range(&ret, tmp->min, min - 1);
 189                 } else {
 190                         add_range(&ret, tmp->min, min - 1);
 191                         add_range(&ret, max + 1, tmp->max);
 192                 }
 193         } END_FOR_EACH_PTR(tmp);
 194         return ret;
 195 }
 196
 197 long long get_dinfo_min(struct data_info *dinfo)
 198 {
 199         struct data_range *drange;
 200
 201         if (!dinfo || !dinfo->value_ranges)
 202                 return whole_range.min;
 203         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 204         return drange->min;
 205 }
 206
 207 long long get_dinfo_max(struct data_info *dinfo)
 208 {
 209         struct data_range *drange;
 210
 211         if (!dinfo || !dinfo->value_ranges)
 212                 return whole_range.max;
 213         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
 214         return drange->max;
 215 }
 216
 217 int is_whole_range(struct range_list *ranges)
 218 {
 219         struct data_range *drange;
 220
 221         if (!ranges)
 222                 return 0;
 223
 224         drange = first_ptr_list((struct ptr_list *)ranges);
 225         if (drange->min == whole_range.min && drange->max == whole_range.max)
 226                 return 1;
 227         return 0;
 228 }
 229
 230 /*
 231  * if it can be only one value return that, else return UNDEFINED
 232  */
 233 long long get_single_value_from_range(struct data_info *dinfo)
 234 {
 235         struct data_range *tmp;
 236         int count = 0;
 237         long long ret = UNDEFINED;
 238
 239         if (dinfo->type != DATA_RANGE)
 240                 return UNDEFINED;
 241
 242         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 243                 if (!count++) {
 244                         if (tmp->min != tmp->max)
 245                                 return UNDEFINED;
 246                         ret = tmp->min;
 247                 } else {
 248                         return UNDEFINED;
 249                 }
 250         } END_FOR_EACH_PTR(tmp);
 251         return ret;
 252 }
 253
 254 static int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 255 {
 256         switch(comparison){
 257         case '<':
 258         case SPECIAL_UNSIGNED_LT:
 259                 if (left->min < right->max)
 260                         return 1;
 261                 return 0;
 262         case SPECIAL_UNSIGNED_LTE:
 263         case SPECIAL_LTE:
 264                 if (left->min <= right->max)
 265                         return 1;
 266                 return 0;
 267         case SPECIAL_EQUAL:
 268                 if (left->max < right->min)
 269                         return 0;
 270                 if (left->min > right->max)
 271                         return 0;
 272                 return 1;
 273         case SPECIAL_UNSIGNED_GTE:
 274         case SPECIAL_GTE:
 275                 if (left->max >= right->min)
 276                         return 1;
 277                 return 0;
 278         case '>':
 279         case SPECIAL_UNSIGNED_GT:
 280                 if (left->max > right->min)
 281                         return 1;
 282                 return 0;
 283         case SPECIAL_NOTEQUAL:
 284                 if (left->min != left->max)
 285                         return 1;
 286                 if (right->min != right->max)
 287                         return 1;
 288                 if (left->min != right->min)
 289                         return 1;
 290                 return 0;
 291         default:
 292                 smatch_msg("unhandled comparison %d\n", comparison);
 293                 return UNDEFINED;
 294         }
 295         return 0;
 296 }
 297
 298 static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right)
 299 {
 300         switch(comparison){
 301         case '<':
 302         case SPECIAL_UNSIGNED_LT:
 303                 if (left->max >= right->min)
 304                         return 1;
 305                 return 0;
 306         case SPECIAL_UNSIGNED_LTE:
 307         case SPECIAL_LTE:
 308                 if (left->max > right->min)
 309                         return 1;
 310                 return 0;
 311         case SPECIAL_EQUAL:
 312                 if (left->min != left->max)
 313                         return 1;
 314                 if (right->min != right->max)
 315                         return 1;
 316                 if (left->min != right->min)
 317                         return 1;
 318                 return 0;
 319         case SPECIAL_UNSIGNED_GTE:
 320         case SPECIAL_GTE:
 321                 if (left->min < right->max)
 322                         return 1;
 323                 return 0;
 324         case '>':
 325         case SPECIAL_UNSIGNED_GT:
 326                 if (left->min <= right->max)
 327                         return 1;
 328                 return 0;
 329         case SPECIAL_NOTEQUAL:
 330                 if (left->max < right->min)
 331                         return 0;
 332                 if (left->min > right->max)
 333                         return 0;
 334                 return 1;
 335         default:
 336                 smatch_msg("unhandled comparison %d\n", comparison);
 337                 return UNDEFINED;
 338         }
 339         return 0;
 340 }
 341
 342 int possibly_true(int comparison, struct data_info *dinfo, int num, int left)
 343 {
 344         struct data_range *tmp;
 345         int ret = 0;
 346         struct data_range drange;
 347
 348         drange.min = num;
 349         drange.max = num;
 350
 351         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 352                 if (left)
 353                         ret = true_comparison_range(tmp, comparison, &drange);
 354                 else
 355                         ret = true_comparison_range(&drange,  comparison, tmp);
 356                 if (ret)
 357                         return ret;
 358         } END_FOR_EACH_PTR(tmp);
 359         return ret;
 360 }
 361
 362 int possibly_false(int comparison, struct data_info *dinfo, int num, int left)
 363 {
 364         struct data_range *tmp;
 365         int ret = 0;
 366         struct data_range drange;
 367
 368         drange.min = num;
 369         drange.max = num;
 370
 371         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 372                 if (left)
 373                         ret = false_comparison_range(tmp, comparison, &drange);
 374                 else
 375                         ret = false_comparison_range(&drange,  comparison, tmp);
 376                 if (ret)
 377                         return ret;
 378         } END_FOR_EACH_PTR(tmp);
 379         return ret;
 380 }
 381
 382 static void free_single_dinfo(struct data_info *dinfo)
 383 {
 384         if (dinfo->type == DATA_RANGE)
 385                 __free_ptr_list((struct ptr_list **)&dinfo->value_ranges);
 386 }
 387
 388 static void free_dinfos(struct allocation_blob *blob)
 389 {
 390         unsigned int size = sizeof(struct data_info);
 391         unsigned int offset = 0;
 392
 393         while (offset < blob->offset) {
 394                 free_single_dinfo((struct data_info *)(blob->data + offset));
 395                 offset += size;
 396         }
 397 }
 398
 399 void free_data_info_allocs(void)
 400 {
 401         struct allocator_struct *desc = &data_info_allocator;
 402         struct allocation_blob *blob = desc->blobs;
 403
 404         desc->blobs = NULL;
 405         desc->allocations = 0;
 406         desc->total_bytes = 0;
 407         desc->useful_bytes = 0;
 408         desc->freelist = NULL;
 409         while (blob) {
 410                 struct allocation_blob *next = blob->next;
 411                 free_dinfos(blob);
 412                 blob_free(blob, desc->chunking);
 413                 blob = next;
 414         }
 415         clear_data_range_alloc();
 416 }
 417