smatch_address.c

   1 /*
   2  * Copyright (C) 2015 Oracle.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include "smatch.h"
  19 #include "smatch_slist.h"
  20 #include "smatch_extra.h"
  21
  22 static bool is_non_null_array(struct expression *expr)
  23 {
  24         struct symbol *type;
  25         struct symbol *sym;
  26         struct symbol *tmp;
  27         int i;
  28
  29         type = get_type(expr);
  30         if (!type || type->type != SYM_ARRAY)
  31                 return 0;
  32         if (expr->type == EXPR_SYMBOL)
  33                 return 1;
  34         if (implied_not_equal(expr, 0))
  35                 return 1;
  36
  37         /* verify that it's not the first member of the struct */
  38         if (expr->type != EXPR_DEREF || !expr->member)
  39                 return 0;
  40         sym = expr_to_sym(expr);
  41         if (!sym)
  42                 return 0;
  43         type = get_real_base_type(sym);
  44         if (!type || type->type != SYM_PTR)
  45                 return 0;
  46         type = get_real_base_type(type);
  47         if (type->type != SYM_STRUCT)
  48                 return 0;
  49
  50         i = 0;
  51         FOR_EACH_PTR(type->symbol_list, tmp) {
  52                 i++;
  53                 if (!tmp->ident)
  54                         continue;
  55                 if (strcmp(expr->member->name, tmp->ident->name) == 0) {
  56                         if (i == 1)
  57                                 return 0;
  58                         return 1;
  59                 }
  60         } END_FOR_EACH_PTR(tmp);
  61
  62         return 0;
  63 }
  64
  65 static bool matches_anonymous_union(struct symbol *sym, const char *member_name)
  66 {
  67         struct symbol *type, *tmp;
  68
  69         if (sym->ident)
  70                 return false;
  71         type = get_real_base_type(sym);
  72         if (!type || type->type != SYM_UNION)
  73                 return false;
  74
  75         FOR_EACH_PTR(type->symbol_list, tmp) {
  76                 if (tmp->ident &&
  77                     strcmp(member_name, tmp->ident->name) == 0) {
  78                         return true;
  79                 }
  80         } END_FOR_EACH_PTR(tmp);
  81
  82         return false;
  83 }
  84
  85 int get_member_offset(struct symbol *type, const char *member_name)
  86 {
  87         struct symbol *tmp;
  88         int offset;
  89         int bits;
  90
  91         if (!type || type->type != SYM_STRUCT)
  92                 return -1;
  93
  94         bits = 0;
  95         offset = 0;
  96         FOR_EACH_PTR(type->symbol_list, tmp) {
  97                 if (bits_to_bytes(bits + type_bits(tmp)) > tmp->ctype.alignment) {
  98                         offset += bits_to_bytes(bits);
  99                         bits = 0;
 100                 }
 101                 offset = ALIGN(offset, tmp->ctype.alignment);
 102                 if (tmp->ident &&
 103                     strcmp(member_name, tmp->ident->name) == 0) {
 104                         return offset;
 105                 }
 106                 if (matches_anonymous_union(tmp, member_name))
 107                         return offset;
 108                 if (!(type_bits(tmp) % 8) && type_bits(tmp) / 8 == type_bytes(tmp))
 109                         offset += type_bytes(tmp);
 110                 else
 111                         bits += type_bits(tmp);
 112         } END_FOR_EACH_PTR(tmp);
 113         return -1;
 114 }
 115
 116 int get_member_offset_from_deref(struct expression *expr)
 117 {
 118         struct symbol *type;
 119         struct ident *member;
 120         int offset;
 121
 122         /*
 123          * FIXME: This doesn't handle foo.u.bar correctly.
 124          *
 125          */
 126
 127         if (expr->type != EXPR_DEREF) {
 128                 if (expr->type == EXPR_PREOP && expr->op == '&')
 129                         expr = strip_expr(expr->unop);
 130                 else
 131                         return -1;
 132         }
 133
 134         if (expr->member_offset >= 0)
 135                 return expr->member_offset;
 136
 137         member = expr->member;
 138         if (!member)
 139                 return -1;
 140
 141         type = get_type(expr->deref);
 142         if (type_is_ptr(type))
 143                 type = get_real_base_type(type);
 144         if (!type || type->type != SYM_STRUCT)
 145                 return -1;
 146
 147         offset = get_member_offset(type, member->name);
 148         if (offset >= 0)
 149                 expr->member_offset = offset;
 150         return offset;
 151 }
 152
 153 static void add_offset_to_pointer(struct range_list **rl, int offset)
 154 {
 155         sval_t min, max, remove, sval;
 156         struct range_list *orig = *rl;
 157
 158         /*
 159          * Ha ha.  Treating zero as a special case means I'm correct at least a
 160          * tiny fraction of the time.  Which is better than nothing.
 161          *
 162          */
 163         if (offset == 0)
 164                 return;
 165
 166         if (is_unknown_ptr(orig))
 167                 return;
 168
 169         /*
 170          * This function doesn't necessarily work how you might expect...
 171          *
 172          * Say you have s64min-(-1),1-s64max and you add 8 then I guess what
 173          * we want to say is maybe something like 9-s64max.  This shows that the
 174          * min it could be is 9 which is potentially useful information.  But
 175          * if we start with (-12),5000000-57777777 and we add 8 then we'd want
 176          * the result to be (-4),5000008-57777777 but (-4),5000000-57777777 is
 177          * also probably acceptable.  If you start with s64min-s64max then the
 178          * result should be 8-s64max.
 179          *
 180          */
 181
 182         /* We do the math on void pointer type, because this isn't "&v + 16" it
 183          * is &v->sixteenth_byte.
 184          */
 185         orig = cast_rl(&ptr_ctype, orig);
 186         min = sval_type_min(&ptr_ctype);
 187         min.value = offset;
 188         max = sval_type_max(&ptr_ctype);
 189
 190         if (!orig || is_whole_rl(orig)) {
 191                 *rl = alloc_rl(min, max);
 192                 return;
 193         }
 194
 195         /* no wrap around */
 196         max.uvalue = rl_max(orig).uvalue;
 197         if (max.uvalue > sval_type_max(&ptr_ctype).uvalue - offset) {
 198                 remove = sval_type_max(&ptr_ctype);
 199                 remove.uvalue -= offset;
 200                 orig = remove_range(orig, remove, max);
 201         }
 202
 203         sval.type = &int_ctype;
 204         sval.value = offset;
 205
 206         *rl = rl_binop(orig, '+', alloc_rl(sval, sval));
 207 }
 208
 209 static struct range_list *where_allocated_rl(struct symbol *sym)
 210 {
 211         if (!sym)
 212                 return NULL;
 213
 214         /* This should just be the mtag if it's not on the stack */
 215         return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 216 }
 217
 218 static bool handle_fn_address(struct expression *expr, struct range_list **rl)
 219 {
 220         struct symbol *type;
 221
 222         if (expr->type == EXPR_PREOP && expr->op == '&')
 223                 expr = strip_expr(expr->unop);
 224
 225         if (expr->type != EXPR_SYMBOL)
 226                 return false;
 227
 228         type = get_type(expr);
 229         if (!type || type->type != SYM_FN)
 230                 return false;
 231
 232         *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 233         return true;
 234 }
 235
 236 int get_address_rl(struct expression *expr, struct range_list **rl)
 237 {
 238         struct expression *unop;
 239
 240         /*
 241          * Ugh...  This function is bad.  It doesn't work where it's supposed to
 242          * and it does more than it really should.  It shouldn't handle string
 243          * literals I think...
 244          *
 245          * There are several complications.  For arrays and functions the "&foo"
 246          * "foo" are equivalent.  But the problem is that we're also passing in
 247          * foo->array[] and foo->fn.
 248          *
 249          * Then, when we have foo->bar.baz.one.two; that needs to be handled
 250          * correctly but right now, it is not.
 251          *
 252          */
 253
 254         expr = strip_expr(expr);
 255         if (!expr)
 256                 return 0;
 257
 258         /*
 259          * For functions &fn and fn are equivalent.  I don't know if this is
 260          * really the right place to handle it, but let's just get it out of the
 261          * way for now.
 262          *
 263          */
 264         if (handle_fn_address(expr, rl))
 265                 return 1;
 266
 267         /*
 268          * For arrays, &foo->array and foo->array are equivalent.
 269          *
 270          */
 271         if (expr->type == EXPR_PREOP && expr->op == '&') {
 272                 expr = strip_expr(expr->unop);
 273         } else {
 274                 struct symbol *type;
 275
 276                 type = get_type(expr);
 277                 if (!type || type->type != SYM_ARRAY)
 278                         return 0;
 279         }
 280
 281         if (expr->type == EXPR_SYMBOL) {
 282                 *rl = where_allocated_rl(expr->symbol);
 283                 return 1;
 284         }
 285
 286         if (is_array(expr)) {
 287                 struct expression *array;
 288                 struct expression *offset_expr;
 289                 struct range_list *array_rl, *offset_rl, *bytes_rl, *res;
 290                 struct symbol *type;
 291                 sval_t bytes;
 292
 293                 array = get_array_base(expr);
 294                 offset_expr = get_array_offset(expr);
 295
 296                 type = get_type(array);
 297                 type = get_real_base_type(type);
 298                 bytes.type = ssize_t_ctype;
 299                 bytes.uvalue = type_bytes(type);
 300                 bytes_rl = alloc_rl(bytes, bytes);
 301
 302                 get_absolute_rl(array, &array_rl);
 303                 get_absolute_rl(offset_expr, &offset_rl);
 304
 305                 if (type_bytes(type)) {
 306                         res = rl_binop(offset_rl, '*', bytes_rl);
 307                         res = rl_binop(res, '+', array_rl);
 308                         *rl = res;
 309                         return true;
 310                 }
 311
 312                 if (implied_not_equal(array, 0) ||
 313                     implied_not_equal(offset_expr, 0)) {
 314                         *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 315                         return 1;
 316                 }
 317
 318                 return 0;
 319         }
 320
 321         if (expr->type == EXPR_DEREF && expr->member) {
 322                 struct range_list *unop_rl;
 323                 int offset;
 324
 325                 offset = get_member_offset_from_deref(expr);
 326                 unop = strip_expr(expr->unop);
 327                 if (unop->type == EXPR_PREOP && unop->op == '*')
 328                         unop = strip_expr(unop->unop);
 329
 330                 if (offset >= 0 &&
 331                     get_implied_rl(unop, &unop_rl) &&
 332                     !is_whole_rl(unop_rl)) {
 333                         *rl = unop_rl;
 334                         add_offset_to_pointer(rl, offset);
 335                         return 1;
 336                 }
 337
 338                 if (implied_not_equal(unop, 0) || offset > 0) {
 339                         *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 340                         return 1;
 341                 }
 342
 343                 return 0;
 344         }
 345
 346         if (is_non_null_array(expr)) {
 347                 *rl = alloc_rl(array_min_sval, array_max_sval);
 348                 return 1;
 349         }
 350
 351         return 0;
 352 }