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 int get_member_offset(struct symbol *type, const char *member_name)
  66 {
  67         struct symbol *tmp;
  68         int offset;
  69
  70         if (!type || type->type != SYM_STRUCT)
  71                 return -1;
  72
  73         offset = 0;
  74         FOR_EACH_PTR(type->symbol_list, tmp) {
  75                 offset = ALIGN(offset, tmp->ctype.alignment);
  76                 if (tmp->ident &&
  77                     strcmp(member_name, tmp->ident->name) == 0) {
  78                         return offset;
  79                 }
  80                 offset += type_bytes(tmp);
  81         } END_FOR_EACH_PTR(tmp);
  82         return -1;
  83 }
  84
  85 int get_member_offset_from_deref(struct expression *expr)
  86 {
  87         struct symbol *type;
  88         struct ident *member;
  89         int offset;
  90
  91         if (expr->type != EXPR_DEREF)  /* hopefully, this doesn't happen */
  92                 return -1;
  93
  94         if (expr->member_offset >= 0)
  95                 return expr->member_offset;
  96
  97         member = expr->member;
  98         if (!member)
  99                 return -1;
 100
 101         type = get_type(expr->deref);
 102         if (!type || type->type != SYM_STRUCT)
 103                 return -1;
 104
 105         offset = get_member_offset(type, member->name);
 106         if (offset >= 0)
 107                 expr->member_offset = offset;
 108         return offset;
 109 }
 110
 111 static struct range_list *filter_unknown_negatives(struct range_list *rl)
 112 {
 113         struct data_range *first;
 114         struct range_list *filter = NULL;
 115
 116         first = first_ptr_list((struct ptr_list *)rl);
 117
 118         if (sval_is_min(first->min) &&
 119             sval_is_negative(first->max) &&
 120             first->max.value == -1) {
 121                 add_ptr_list(&filter, first);
 122                 return rl_filter(rl, filter);
 123         }
 124
 125         return rl;
 126 }
 127
 128 static void add_offset_to_pointer(struct range_list **rl, int offset)
 129 {
 130         sval_t min, max, remove, sval;
 131         struct range_list *orig = *rl;
 132
 133         /*
 134          * Ha ha.  Treating zero as a special case means I'm correct at least a
 135          * tiny fraction of the time.  Which is better than nothing.
 136          *
 137          */
 138         if (offset == 0)
 139                 return;
 140
 141         /*
 142          * This function doesn't necessarily work how you might expect...
 143          *
 144          * Say you have s64min-(-1),1-s64max and you add 8 then I guess what
 145          * we want to say is maybe something like 9-s64max.  This shows that the
 146          * min it could be is 9 which is potentially useful information.  But
 147          * if we start with (-12),5000000-57777777 and we add 8 then we'd want
 148          * the result to be (-4),5000008-57777777 but (-4),5000000-57777777 is
 149          * also probably acceptable.  If you start with s64min-s64max then the
 150          * result should be 8-s64max.
 151          *
 152          */
 153
 154         /* We do the math on void pointer type, because this isn't "&v + 16" it
 155          * is &v->sixteenth_byte.
 156          */
 157         orig = cast_rl(&ptr_ctype, orig);
 158         min = sval_type_min(&ptr_ctype);
 159         min.value = offset;
 160         max = sval_type_max(&ptr_ctype);
 161
 162         if (!orig || is_whole_rl(orig)) {
 163                 *rl = alloc_rl(min, max);
 164                 return;
 165         }
 166
 167         orig = filter_unknown_negatives(orig);
 168         /*
 169          * FIXME:  This is not really accurate but we're a bit screwed anyway
 170          * when we start doing pointer math with error pointers so it's probably
 171          * not important.
 172          *
 173          */
 174         if (sval_is_negative(rl_min(orig)))
 175                 return;
 176
 177         /* no wrap around */
 178         max.uvalue = rl_max(orig).uvalue;
 179         if (max.uvalue > sval_type_max(&ptr_ctype).uvalue - offset) {
 180                 remove = sval_type_max(&ptr_ctype);
 181                 remove.uvalue -= offset;
 182                 orig = remove_range(orig, remove, max);
 183         }
 184
 185         sval.type = &int_ctype;
 186         sval.value = offset;
 187
 188         *rl = rl_binop(orig, '+', alloc_rl(sval, sval));
 189 }
 190
 191 static struct range_list *where_allocated_rl(struct symbol *sym)
 192 {
 193         if (!sym)
 194                 return NULL;
 195
 196         if (sym->ctype.modifiers & (MOD_TOPLEVEL | MOD_STATIC)) {
 197                 if (sym->initializer)
 198                         return alloc_rl(data_seg_min, data_seg_max);
 199                 else
 200                         return alloc_rl(bss_seg_min, bss_seg_max);
 201         }
 202         return alloc_rl(stack_seg_min, stack_seg_max);
 203 }
 204
 205 int get_address_rl(struct expression *expr, struct range_list **rl)
 206 {
 207         expr = strip_expr(expr);
 208         if (!expr)
 209                 return 0;
 210
 211         if (expr->type == EXPR_STRING) {
 212                 *rl = alloc_rl(text_seg_min, text_seg_max);
 213                 return 1;
 214         }
 215
 216         if (expr->type == EXPR_PREOP && expr->op == '&') {
 217                 struct expression *unop;
 218
 219                 unop = strip_expr(expr->unop);
 220                 if (unop->type == EXPR_SYMBOL) {
 221                         *rl = where_allocated_rl(unop->symbol);
 222                         return 1;
 223                 }
 224
 225                 if (unop->type == EXPR_DEREF) {
 226                         int offset = get_member_offset_from_deref(unop);
 227
 228                         unop = strip_expr(unop->unop);
 229                         if (unop->type == EXPR_SYMBOL) {
 230                                 *rl = where_allocated_rl(unop->symbol);
 231                         } else if (unop->type == EXPR_PREOP && unop->op == '*') {
 232                                 unop = strip_expr(unop->unop);
 233                                 get_absolute_rl(unop, rl);
 234                         } else {
 235                                 return 0;
 236                         }
 237
 238                         add_offset_to_pointer(rl, offset);
 239                         return 1;
 240                 }
 241
 242                 return 0;
 243         }
 244
 245         if (is_non_null_array(expr)) {
 246                 *rl = alloc_rl(array_min_sval, array_max_sval);
 247                 return 1;
 248         }
 249
 250         return 0;
 251 }