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         FOR_EACH_PTR(list, tmp) {
  43                 if (i++)
  44                         strncat(full, ",", 254);
  45                 if (tmp->min == tmp->max) {
  46                         strncat(full, show_num(tmp->min), 254);
  47                         continue;
  48                 }
  49                 strncat(full, show_num(tmp->min), 254);
  50                 strncat(full, "-", 254);
  51                 strncat(full, show_num(tmp->max), 254);
  52         } END_FOR_EACH_PTR(tmp);
  53         full[255] = '\0';
  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 (tmp->min < min) {
  90                         continue;
  91                 } else {
  92                         if (tmp->max >= max)
  93                                 return;
  94                         if (tmp->max >= min) {
  95                                 new = alloc_range(tmp->min, max);
  96                                 REPLACE_CURRENT_PTR(tmp, new);
  97                                 return;
  98                         }
  99                         new = alloc_range(min, max);
 100                         INSERT_CURRENT(new, tmp);
 101                         return;
 102                 }
 103         } END_FOR_EACH_PTR(tmp);
 104         new = alloc_range(min, max);
 105         add_ptr_list(list, new);
 106 }
 107
 108 struct range_list *clone_range_list(struct range_list *list)
 109 {
 110         struct data_range *tmp;
 111         struct range_list *ret = NULL;
 112
 113         FOR_EACH_PTR(list, tmp) {
 114                 add_ptr_list(&ret, tmp);
 115         } END_FOR_EACH_PTR(tmp);
 116         return ret;
 117 }
 118
 119 struct range_list *range_list_union(struct range_list *one, struct range_list *two)
 120 {
 121         struct data_range *tmp;
 122         struct range_list *ret = NULL;
 123
 124         if (!one || !two)  /*having nothing in a list means everything is in */
 125                 return NULL;
 126
 127         FOR_EACH_PTR(one, tmp) {
 128                 add_range(&ret, tmp->min, tmp->max);
 129         } END_FOR_EACH_PTR(tmp);
 130         FOR_EACH_PTR(two, tmp) {
 131                 add_range(&ret, tmp->min, tmp->max);
 132         } END_FOR_EACH_PTR(tmp);
 133         return ret;
 134 }
 135
 136 struct range_list *remove_range(struct range_list *list, long long min, long long max)
 137 {
 138         struct data_range *tmp;
 139         struct range_list *ret = NULL;
 140
 141         FOR_EACH_PTR(list, tmp) {
 142                 if (tmp->max < min) {
 143                         add_range(&ret, tmp->min, tmp->max);
 144                         continue;
 145                 }
 146                 if (tmp->min > max) {
 147                         add_range(&ret, tmp->min, tmp->max);
 148                         continue;
 149                 }
 150                 if (tmp->min >= min && tmp->max <= max)
 151                         continue;
 152                 if (tmp->min >= min) {
 153                         add_range(&ret, max + 1, tmp->max);
 154                 } else if (tmp->max <= max) {
 155                         add_range(&ret, tmp->min, min - 1);
 156                 } else {
 157                         add_range(&ret, tmp->min, min - 1);
 158                         add_range(&ret, max + 1, tmp->max);
 159                 }
 160         } END_FOR_EACH_PTR(tmp);
 161         return ret;
 162 }
 163
 164 /*
 165  * if it can be only one value return that, else return UNDEFINED
 166  */
 167 long long get_single_value_from_range(struct data_info *dinfo)
 168 {
 169         struct data_range *tmp;
 170         int count = 0;
 171         long long ret = UNDEFINED;
 172
 173         if (dinfo->type != DATA_RANGE)
 174                 return UNDEFINED;
 175
 176         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 177                 if (!count++) {
 178                         if (tmp->min != tmp->max)
 179                                 return UNDEFINED;
 180                         ret = tmp->min;
 181                 } else {
 182                         return UNDEFINED;
 183                 }
 184         } END_FOR_EACH_PTR(tmp);
 185         return ret;
 186 }
 187
 188 int possibly_true(int comparison, struct data_info *dinfo, int num, int left)
 189 {
 190         struct data_range *tmp;
 191         int ret = 0;
 192         struct data_range drange;
 193
 194         drange.min = num;
 195         drange.max = num;
 196
 197         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 198                 if (left)
 199                         ret = true_comparison_range(tmp, comparison, &drange);
 200                 else
 201                         ret = true_comparison_range(&drange,  comparison, tmp);
 202                 if (ret)
 203                         return ret;
 204         } END_FOR_EACH_PTR(tmp);
 205         return ret;
 206 }
 207
 208 int possibly_false(int comparison, struct data_info *dinfo, int num, int left)
 209 {
 210         struct data_range *tmp;
 211         int ret = 0;
 212         struct data_range drange;
 213
 214         drange.min = num;
 215         drange.max = num;
 216
 217         FOR_EACH_PTR(dinfo->value_ranges, tmp) {
 218                 if (left)
 219                         ret = false_comparison_range(tmp, comparison, &drange);
 220                 else
 221                         ret = false_comparison_range(&drange,  comparison, tmp);
 222                 if (ret)
 223                         return ret;
 224         } END_FOR_EACH_PTR(tmp);
 225         return ret;
 226 }
 227
 228 static void free_single_dinfo(struct data_info *dinfo)
 229 {
 230         if (dinfo->type == DATA_RANGE)
 231                 __free_ptr_list((struct ptr_list **)&dinfo->value_ranges);
 232 }
 233
 234 static void free_dinfos(struct allocation_blob *blob)
 235 {
 236         unsigned int size = sizeof(struct data_info);
 237         unsigned int offset = 0;
 238
 239         while (offset < blob->offset) {
 240                 free_single_dinfo((struct data_info *)(blob->data + offset));
 241                 offset += size;
 242         }
 243 }
 244
 245 void free_data_info_allocs(void)
 246 {
 247         struct allocator_struct *desc = &data_info_allocator;
 248         struct allocation_blob *blob = desc->blobs;
 249
 250         desc->blobs = NULL;
 251         desc->allocations = 0;
 252         desc->total_bytes = 0;
 253         desc->useful_bytes = 0;
 254         desc->freelist = NULL;
 255         while (blob) {
 256                 struct allocation_blob *next = blob->next;
 257                 free_dinfos(blob);
 258                 blob_free(blob, desc->chunking);
 259                 blob = next;
 260         }
 261         clear_data_range_alloc();
 262 }
 263