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