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 if (expr->type != EXPR_DEREF) /* hopefully, this doesn't happen */ 123 return -1; 124 125 if (expr->member_offset >= 0) 126 return expr->member_offset; 127 128 member = expr->member; 129 if (!member) 130 return -1; 131 132 type = get_type(expr->deref); 133 if (type_is_ptr(type)) 134 type = get_real_base_type(type); 135 if (!type || type->type != SYM_STRUCT) 136 return -1; 137 138 offset = get_member_offset(type, member->name); 139 if (offset >= 0) 140 expr->member_offset = offset; 141 return offset; 142 } 143 144 static void add_offset_to_pointer(struct range_list **rl, int offset) 145 { 146 sval_t min, max, remove, sval; 147 struct range_list *orig = *rl; 148 149 /* 150 * Ha ha. Treating zero as a special case means I'm correct at least a 151 * tiny fraction of the time. Which is better than nothing. 152 * 153 */ 154 if (offset == 0) 155 return; 156 157 if (is_unknown_ptr(orig)) 158 return; 159 160 /* 161 * This function doesn't necessarily work how you might expect... 162 * 163 * Say you have s64min-(-1),1-s64max and you add 8 then I guess what 164 * we want to say is maybe something like 9-s64max. This shows that the 165 * min it could be is 9 which is potentially useful information. But 166 * if we start with (-12),5000000-57777777 and we add 8 then we'd want 167 * the result to be (-4),5000008-57777777 but (-4),5000000-57777777 is 168 * also probably acceptable. If you start with s64min-s64max then the 169 * result should be 8-s64max. 170 * 171 */ 172 173 /* We do the math on void pointer type, because this isn't "&v + 16" it 174 * is &v->sixteenth_byte. 175 */ 176 orig = cast_rl(&ptr_ctype, orig); 177 min = sval_type_min(&ptr_ctype); 178 min.value = offset; 179 max = sval_type_max(&ptr_ctype); 180 181 if (!orig || is_whole_rl(orig)) { 182 *rl = alloc_rl(min, max); 183 return; 184 } 185 186 /* no wrap around */ 187 max.uvalue = rl_max(orig).uvalue; 188 if (max.uvalue > sval_type_max(&ptr_ctype).uvalue - offset) { 189 remove = sval_type_max(&ptr_ctype); 190 remove.uvalue -= offset; 191 orig = remove_range(orig, remove, max); 192 } 193 194 sval.type = &int_ctype; 195 sval.value = offset; 196 197 *rl = rl_binop(orig, '+', alloc_rl(sval, sval)); 198 } 199 200 static struct range_list *where_allocated_rl(struct symbol *sym) 201 { 202 if (!sym) 203 return NULL; 204 205 return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 206 } 207 208 int get_address_rl(struct expression *expr, struct range_list **rl) 209 { 210 struct expression *unop; 211 212 expr = strip_expr(expr); 213 if (!expr) 214 return 0; 215 216 if (expr->type == EXPR_STRING) { 217 *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 218 return 1; 219 } 220 221 if (expr->type == EXPR_PREOP && expr->op == '&') 222 expr = strip_expr(expr->unop); 223 else { 224 struct symbol *type; 225 226 type = get_type(expr); 227 if (!type || type->type != SYM_ARRAY) 228 return 0; 229 } 230 231 if (expr->type == EXPR_SYMBOL) { 232 *rl = where_allocated_rl(expr->symbol); 233 return 1; 234 } 235 236 if (is_array(expr)) { 237 struct expression *array; 238 struct expression *offset_expr; 239 struct range_list *array_rl, *offset_rl, *bytes_rl, *res; 240 struct symbol *type; 241 sval_t bytes; 242 243 array = get_array_base(expr); 244 offset_expr = get_array_offset(expr); 245 246 type = get_type(array); 247 type = get_real_base_type(type); 248 bytes.type = ssize_t_ctype; 249 bytes.uvalue = type_bytes(type); 250 bytes_rl = alloc_rl(bytes, bytes); 251 252 get_absolute_rl(array, &array_rl); 253 get_absolute_rl(offset_expr, &offset_rl); 254 255 if (type_bytes(type)) { 256 res = rl_binop(offset_rl, '*', bytes_rl); 257 res = rl_binop(res, '+', array_rl); 258 *rl = res; 259 return true; 260 } 261 262 if (implied_not_equal(array, 0) || 263 implied_not_equal(offset_expr, 0)) { 264 *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 265 return 1; 266 } 267 268 return 0; 269 } 270 271 if (expr->type == EXPR_DEREF && expr->member) { 272 struct range_list *unop_rl; 273 int offset; 274 275 offset = get_member_offset_from_deref(expr); 276 unop = strip_expr(expr->unop); 277 if (unop->type == EXPR_PREOP && unop->op == '*') 278 unop = strip_expr(unop->unop); 279 280 if (offset >= 0 && 281 get_implied_rl(unop, &unop_rl) && 282 !is_whole_rl(unop_rl)) { 283 *rl = unop_rl; 284 add_offset_to_pointer(rl, offset); 285 return 1; 286 } 287 288 if (implied_not_equal(unop, 0) || offset > 0) { 289 *rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval); 290 return 1; 291 } 292 293 return 0; 294 } 295 296 if (is_non_null_array(expr)) { 297 *rl = alloc_rl(array_min_sval, array_max_sval); 298 return 1; 299 } 300 301 return 0; 302 } 303