1 /* 2 * Copyright (C) 2017 Oracle. All rights reserved. 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 /* 19 * One problem that I have is that it's really hard to track how pointers are 20 * passed around. For example, it would be nice to know that the probe() and 21 * remove() functions get the same pci_dev pointer. It would be good to know 22 * what pointers we're passing to the open() and close() functions. But that 23 * information gets lost in a call tree full of function pointer calls. 24 * 25 * I think the first step is to start naming specific pointers. So when a 26 * pointer is allocated, then it gets a tag. So calls to kmalloc() generate a 27 * tag. But we might not use that, because there might be a better name like 28 * framebuffer_alloc(). The framebuffer_alloc() is interesting because there is 29 * one per driver and it's passed around to all the file operations. 30 * 31 * Perhaps we could make a list of functions like framebuffer_alloc() which take 32 * a size and say that those are the interesting alloc functions. 33 * 34 * Another place where we would maybe name the pointer is when they are passed 35 * to the probe(). Because that's an important pointer, since there is one 36 * per driver (sort of). 37 * 38 * My vision is that you could take a pointer and trace it back to a global. So 39 * I'm going to track that pointer_tag - 28 bytes takes you to another pointer 40 * tag. You could follow that one back and so on. Also when we pass a pointer 41 * to a function that would be recorded as sort of a link or path or something. 42 * 43 */ 44 45 #include "smatch.h" 46 #include "smatch_slist.h" 47 #include "smatch_extra.h" 48 49 #include <openssl/md5.h> 50 51 static int my_id; 52 53 mtag_t str_to_mtag(const char *str) 54 { 55 unsigned char c[MD5_DIGEST_LENGTH]; 56 unsigned long long *tag = (unsigned long long *)&c; 57 MD5_CTX mdContext; 58 int len; 59 60 len = strlen(str); 61 MD5_Init(&mdContext); 62 MD5_Update(&mdContext, str, len); 63 MD5_Final(c, &mdContext); 64 65 *tag &= ~MTAG_ALIAS_BIT; 66 *tag &= ~MTAG_OFFSET_MASK; 67 68 return *tag; 69 } 70 71 const struct { 72 const char *name; 73 int size_arg; 74 } allocator_info[] = { 75 { "kmalloc", 0 }, 76 { "kzalloc", 0 }, 77 { "devm_kmalloc", 1}, 78 { "devm_kzalloc", 1}, 79 }; 80 81 static bool is_mtag_call(struct expression *expr) 82 { 83 struct expression *arg; 84 int i; 85 sval_t sval; 86 87 if (expr->type != EXPR_CALL || 88 expr->fn->type != EXPR_SYMBOL || 89 !expr->fn->symbol) 90 return false; 91 92 for (i = 0; i < ARRAY_SIZE(allocator_info); i++) { 93 if (strcmp(expr->fn->symbol->ident->name, allocator_info[i].name) == 0) 94 break; 95 } 96 if (i == ARRAY_SIZE(allocator_info)) 97 return false; 98 99 arg = get_argument_from_call_expr(expr->args, allocator_info[i].size_arg); 100 if (!get_implied_value(arg, &sval)) 101 return false; 102 103 return true; 104 } 105 106 struct smatch_state *swap_mtag_return(struct expression *expr, struct smatch_state *state) 107 { 108 struct expression *left, *right; 109 char *left_name, *right_name; 110 struct symbol *left_sym; 111 struct range_list *rl; 112 char buf[256]; 113 mtag_t tag; 114 sval_t tag_sval; 115 116 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=') 117 return state; 118 119 if (!estate_rl(state) || strcmp(state->name, "0,4096-ptr_max") != 0) 120 return state; 121 122 left = strip_expr(expr->left); 123 right = strip_expr(expr->right); 124 125 if (!is_mtag_call(right)) 126 return state; 127 128 left_name = expr_to_str_sym(left, &left_sym); 129 if (!left_name || !left_sym) 130 return state; 131 right_name = expr_to_str(right); 132 133 snprintf(buf, sizeof(buf), "%s %s %s %s", get_filename(), get_function(), 134 left_name, right_name); 135 tag = str_to_mtag(buf); 136 tag_sval.type = estate_type(state); 137 tag_sval.uvalue = tag; 138 139 rl = rl_filter(estate_rl(state), valid_ptr_rl); 140 rl = clone_rl(rl); 141 add_range(&rl, tag_sval, tag_sval); 142 143 sql_insert_mtag_about(tag, left_name, buf); 144 145 free_string(left_name); 146 free_string(right_name); 147 148 return alloc_estate_rl(rl); 149 } 150 151 int get_string_mtag(struct expression *expr, mtag_t *tag) 152 { 153 mtag_t xor; 154 155 if (expr->type != EXPR_STRING || !expr->string) 156 return 0; 157 158 /* I was worried about collisions so I added a xor */ 159 xor = str_to_mtag("__smatch string"); 160 *tag = str_to_mtag(expr->string->data); 161 *tag = *tag ^ xor; 162 163 return 1; 164 } 165 166 int get_toplevel_mtag(struct symbol *sym, mtag_t *tag) 167 { 168 char buf[256]; 169 170 if (!sym) 171 return 0; 172 173 if (!sym->ident || 174 !(sym->ctype.modifiers & MOD_TOPLEVEL)) 175 return 0; 176 177 snprintf(buf, sizeof(buf), "%s %s", 178 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern", 179 sym->ident->name); 180 *tag = str_to_mtag(buf); 181 return 1; 182 } 183 184 bool get_symbol_mtag(struct symbol *sym, mtag_t *tag) 185 { 186 char buf[256]; 187 188 if (!sym || !sym->ident) 189 return false; 190 191 if (get_toplevel_mtag(sym, tag)) 192 return true; 193 194 if (get_param_num_from_sym(sym) >= 0) 195 return false; 196 197 snprintf(buf, sizeof(buf), "%s %s %s", 198 get_filename(), get_function(), sym->ident->name); 199 *tag = str_to_mtag(buf); 200 return true; 201 } 202 203 static void global_variable(struct symbol *sym) 204 { 205 mtag_t tag; 206 207 if (!get_toplevel_mtag(sym, &tag)) 208 return; 209 210 sql_insert_mtag_about(tag, 211 sym->ident->name, 212 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern"); 213 } 214 215 static int get_array_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 216 { 217 struct expression *array, *offset_expr; 218 struct symbol *type; 219 sval_t sval; 220 int start_offset; 221 222 if (!is_array(expr)) 223 return 0; 224 225 array = get_array_base(expr); 226 if (!array) 227 return 0; 228 type = get_type(array); 229 if (!type || type->type != SYM_ARRAY) 230 return 0; 231 type = get_real_base_type(type); 232 if (!type_bytes(type)) 233 return 0; 234 235 if (!expr_to_mtag_offset(array, tag, &start_offset)) 236 return 0; 237 238 offset_expr = get_array_offset(expr); 239 if (!get_value(offset_expr, &sval)) 240 return 0; 241 *offset = start_offset + sval.value * type_bytes(type); 242 243 return 1; 244 } 245 246 struct range_list *swap_mtag_seed(struct expression *expr, struct range_list *rl) 247 { 248 char buf[256]; 249 char *name; 250 sval_t sval; 251 mtag_t tag; 252 253 if (!rl_to_sval(rl, &sval)) 254 return rl; 255 if (sval.type->type != SYM_PTR || sval.uvalue != MTAG_SEED) 256 return rl; 257 258 name = expr_to_str(expr); 259 snprintf(buf, sizeof(buf), "%s %s %s", get_filename(), get_function(), name); 260 free_string(name); 261 tag = str_to_mtag(buf); 262 sval.value = tag; 263 return alloc_rl(sval, sval); 264 } 265 266 int create_mtag_alias(mtag_t tag, struct expression *expr, mtag_t *new) 267 { 268 char buf[256]; 269 int lines_from_start; 270 char *str; 271 272 /* 273 * We need the alias to be unique. It's not totally required that it 274 * be the same from one DB build to then next, but it makes debugging 275 * a bit simpler. 276 * 277 */ 278 279 if (!cur_func_sym) 280 return 0; 281 282 lines_from_start = expr->pos.line - cur_func_sym->pos.line; 283 str = expr_to_str(expr); 284 snprintf(buf, sizeof(buf), "%lld %d %s", tag, lines_from_start, str); 285 free_string(str); 286 287 *new = str_to_mtag(buf); 288 sql_insert_mtag_alias(tag, *new); 289 290 return 1; 291 } 292 293 static int get_implied_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 294 { 295 struct smatch_state *state; 296 struct symbol *type; 297 sval_t sval; 298 299 type = get_type(expr); 300 if (!type_is_ptr(type)) 301 return 0; 302 state = get_extra_state(expr); 303 if (!state || !estate_get_single_value(state, &sval) || sval.value == 0) 304 return 0; 305 306 *tag = sval.uvalue & ~MTAG_OFFSET_MASK; 307 *offset = sval.uvalue & MTAG_OFFSET_MASK; 308 return 1; 309 } 310 311 /* 312 * The point of this function is to give you the mtag and the offset so 313 * you can look up the data in the DB. It takes an expression. 314 * 315 * So say you give it "foo->bar". Then it would give you the offset of "bar" 316 * and the implied value of "foo". Or if you lookup "*foo" then the offset is 317 * zero and we look up the implied value of "foo. But if the expression is 318 * foo, then if "foo" is a global variable, then we get the mtag and the offset 319 * is zero. If "foo" is a local variable, then there is nothing to look up in 320 * the mtag_data table because that's handled by smatch_extra.c to this returns 321 * false. 322 * 323 */ 324 int expr_to_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 325 { 326 *tag = 0; 327 *offset = 0; 328 329 if (bits_in_pointer != 64) 330 return 0; 331 332 expr = strip_expr(expr); 333 if (!expr) 334 return 0; 335 336 if (is_array(expr)) 337 return get_array_mtag_offset(expr, tag, offset); 338 339 if (expr->type == EXPR_PREOP && expr->op == '*') { 340 expr = strip_expr(expr->unop); 341 return get_implied_mtag_offset(expr, tag, offset); 342 } else if (expr->type == EXPR_DEREF) { 343 int tmp, tmp_offset = 0; 344 345 while (expr->type == EXPR_DEREF) { 346 tmp = get_member_offset_from_deref(expr); 347 if (tmp < 0) 348 return 0; 349 tmp_offset += tmp; 350 expr = strip_expr(expr->deref); 351 } 352 *offset = tmp_offset; 353 if (expr->type == EXPR_PREOP && expr->op == '*') { 354 expr = strip_expr(expr->unop); 355 356 if (get_implied_mtag_offset(expr, tag, &tmp_offset)) { 357 // FIXME: look it up recursively? 358 if (tmp_offset) 359 return 0; 360 return 1; 361 } 362 return 0; 363 } else if (expr->type == EXPR_SYMBOL) { 364 return get_symbol_mtag(expr->symbol, tag); 365 } 366 return 0; 367 } else if (expr->type == EXPR_SYMBOL) { 368 return get_symbol_mtag(expr->symbol, tag); 369 } 370 return 0; 371 } 372 373 /* 374 * This function takes an address and returns an sval. Let's take some 375 * example things you might pass to it: 376 * foo->bar: 377 * If we were only called from smatch_math, we wouldn't need to bother with 378 * this because it's already been looked up in smatch_extra.c but this is 379 * also called from other places so we have to check smatch_extra.c. 380 * &foo 381 * If "foo" is global return the mtag for "foo". 382 * &foo.bar 383 * If "foo" is global return the mtag for "foo" + the offset of ".bar". 384 * It also handles string literals. 385 * 386 */ 387 int get_mtag_sval(struct expression *expr, sval_t *sval) 388 { 389 struct symbol *type; 390 mtag_t tag; 391 int offset = 0; 392 393 if (bits_in_pointer != 64) 394 return 0; 395 396 expr = strip_expr(expr); 397 398 type = get_type(expr); 399 if (!type_is_ptr(type)) 400 return 0; 401 /* 402 * There are several options: 403 * 404 * If the expr is a string literal, that's an address/mtag. 405 * SYM_ARRAY and SYM_FN are mtags. There are "&foo" type addresses. 406 * And there are saved pointers "p = &foo;" 407 * 408 */ 409 410 if (expr->type == EXPR_STRING && get_string_mtag(expr, &tag)) 411 goto found; 412 413 if (expr->type == EXPR_SYMBOL && 414 (type->type == SYM_ARRAY || type->type == SYM_FN) && 415 get_toplevel_mtag(expr->symbol, &tag)) 416 goto found; 417 418 if (expr->type == EXPR_PREOP && expr->op == '&') { 419 expr = strip_expr(expr->unop); 420 if (expr_to_mtag_offset(expr, &tag, &offset)) 421 goto found; 422 return 0; 423 } 424 425 if (get_implied_mtag_offset(expr, &tag, &offset)) 426 goto found; 427 428 return 0; 429 found: 430 if (offset >= MTAG_OFFSET_MASK) 431 return 0; 432 433 sval->type = type; 434 sval->uvalue = tag | offset; 435 436 return 1; 437 } 438 439 void register_mtag(int id) 440 { 441 my_id = id; 442 443 444 /* 445 * The mtag stuff only works on 64 systems because we store the 446 * information in the pointer itself. 447 * bit 63 : set for alias mtags 448 * bit 62-12: mtag hash 449 * bit 11-0 : offset 450 * 451 */ 452 453 add_hook(&global_variable, BASE_HOOK); 454 } 455