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 static struct smatch_state *alloc_tag_state(mtag_t tag) 54 { 55 struct smatch_state *state; 56 char buf[64]; 57 58 state = __alloc_smatch_state(0); 59 snprintf(buf, sizeof(buf), "%lld", tag); 60 state->name = alloc_sname(buf); 61 state->data = malloc(sizeof(mtag_t)); 62 *(mtag_t *)state->data = tag; 63 64 return state; 65 } 66 67 static mtag_t str_to_tag(const char *str) 68 { 69 unsigned char c[MD5_DIGEST_LENGTH]; 70 unsigned long long *tag = (unsigned long long *)&c; 71 MD5_CTX mdContext; 72 int len; 73 74 len = strlen(str); 75 MD5_Init(&mdContext); 76 MD5_Update(&mdContext, str, len); 77 MD5_Final(c, &mdContext); 78 79 *tag &= ~MTAG_ALIAS_BIT; 80 *tag &= ~MTAG_OFFSET_MASK; 81 82 return *tag; 83 } 84 85 static void alloc_assign(const char *fn, struct expression *expr, void *unused) 86 { 87 struct expression *left, *right; 88 char *left_name, *right_name; 89 struct symbol *left_sym; 90 char buf[256]; 91 mtag_t tag; 92 93 94 // FIXME: This should only happen when the size is not a paramter of 95 // the caller 96 return; 97 98 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=') 99 return; 100 left = strip_expr(expr->left); 101 right = strip_expr(expr->right); 102 if (right->type != EXPR_CALL || right->fn->type != EXPR_SYMBOL) 103 return; 104 105 left_name = expr_to_str_sym(left, &left_sym); 106 right_name = expr_to_str(right); 107 108 snprintf(buf, sizeof(buf), "%s %s %s %s", get_filename(), get_function(), 109 left_name, right_name); 110 tag = str_to_tag(buf); 111 112 sql_insert_mtag_about(tag, left_name, right_name); 113 114 if (left_name && left_sym) 115 set_state(my_id, left_name, left_sym, alloc_tag_state(tag)); 116 117 free_string(left_name); 118 free_string(right_name); 119 } 120 121 int get_string_mtag(struct expression *expr, mtag_t *tag) 122 { 123 mtag_t xor; 124 125 if (expr->type != EXPR_STRING || !expr->string) 126 return 0; 127 128 /* I was worried about collisions so I added a xor */ 129 xor = str_to_tag("__smatch string"); 130 *tag = str_to_tag(expr->string->data); 131 *tag = *tag ^ xor; 132 133 return 1; 134 } 135 136 int get_toplevel_mtag(struct symbol *sym, mtag_t *tag) 137 { 138 char buf[256]; 139 140 if (!sym) 141 return 0; 142 143 if (!sym->ident || 144 !(sym->ctype.modifiers & MOD_TOPLEVEL)) 145 return 0; 146 147 snprintf(buf, sizeof(buf), "%s %s", 148 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern", 149 sym->ident->name); 150 *tag = str_to_tag(buf); 151 return 1; 152 } 153 154 int get_deref_mtag(struct expression *expr, mtag_t *tag) 155 { 156 mtag_t container_tag, member_tag; 157 int offset; 158 159 /* 160 * I'm not totally sure what I'm doing... 161 * 162 * This is supposed to get something like "global_var->ptr", but I don't 163 * feel like it's complete at all. 164 * 165 */ 166 167 if (!get_mtag(expr->unop, &container_tag)) 168 return 0; 169 170 offset = get_member_offset_from_deref(expr); 171 if (offset < 0) 172 return 0; 173 174 if (!mtag_map_select_tag(container_tag, -offset, &member_tag)) 175 return 0; 176 177 *tag = member_tag; 178 return 1; 179 } 180 181 static void global_variable(struct symbol *sym) 182 { 183 mtag_t tag; 184 185 if (!get_toplevel_mtag(sym, &tag)) 186 return; 187 188 sql_insert_mtag_about(tag, 189 sym->ident->name, 190 (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern"); 191 } 192 193 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math) 194 { 195 struct expression *call; 196 struct range_list *rl; 197 198 if (expr->type != EXPR_ASSIGNMENT) 199 return; 200 call = strip_expr(expr->right); 201 202 if (!parse_call_math_rl(call, math, &rl)) 203 return; 204 // rl = cast_rl(&int_ctype, rl); 205 // set_state_expr(my_size_id, expr->left, alloc_estate_rl(rl)); 206 } 207 208 static void db_returns_memory_tag(struct expression *expr, int param, char *key, char *value) 209 { 210 struct expression *call, *arg; 211 mtag_t tag, alias; 212 char *name; 213 struct symbol *sym; 214 215 call = strip_expr(expr); 216 while (call->type == EXPR_ASSIGNMENT) 217 call = strip_expr(call->right); 218 if (call->type != EXPR_CALL) 219 return; 220 221 tag = strtoul(value, NULL, 10); 222 223 if (!create_mtag_alias(tag, call, &alias)) 224 return; 225 226 arg = get_argument_from_call_expr(call->args, param); 227 if (!arg) 228 return; 229 230 name = get_variable_from_key(arg, key, &sym); 231 if (!name || !sym) 232 goto free; 233 234 set_state(my_id, name, sym, alloc_tag_state(alias)); 235 free: 236 free_string(name); 237 } 238 239 static void match_call_info(struct expression *expr) 240 { 241 struct smatch_state *state; 242 struct expression *arg; 243 int i = -1; 244 245 FOR_EACH_PTR(expr->args, arg) { 246 i++; 247 state = get_state_expr(my_id, arg); 248 if (!state || !state->data) 249 continue; 250 sql_insert_caller_info(expr, MEMORY_TAG, i, "$", state->name); 251 } END_FOR_EACH_PTR(arg); 252 } 253 254 static void save_caller_info(const char *name, struct symbol *sym, char *key, char *value) 255 { 256 struct smatch_state *state; 257 char fullname[256]; 258 mtag_t tag; 259 260 if (strncmp(key, "$", 1) != 0) 261 return; 262 263 tag = atoll(value); 264 snprintf(fullname, 256, "%s%s", name, key + 1); 265 state = alloc_tag_state(tag); 266 set_state(my_id, fullname, sym, state); 267 } 268 269 static int get_array_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 270 { 271 struct expression *array, *offset_expr; 272 struct symbol *type; 273 sval_t sval; 274 275 if (!is_array(expr)) 276 return 0; 277 278 array = get_array_base(expr); 279 if (!array) 280 return 0; 281 type = get_type(array); 282 if (!type || type->type != SYM_ARRAY) 283 return 0; 284 type = get_real_base_type(type); 285 if (!type_bytes(type)) 286 return 0; 287 288 if (!get_mtag(array, tag)) 289 return 0; 290 291 offset_expr = get_array_offset(expr); 292 if (!get_value(offset_expr, &sval)) 293 return 0; 294 *offset = sval.value * type_bytes(type); 295 296 return 1; 297 } 298 299 static int get_implied_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 300 { 301 struct smatch_state *state; 302 struct symbol *type; 303 sval_t sval; 304 305 type = get_type(expr); 306 if (!type_is_ptr(type)) 307 return 0; 308 state = get_extra_state(expr); 309 if (!state || !estate_get_single_value(state, &sval) || sval.value == 0) 310 return 0; 311 312 *tag = sval.uvalue & ~MTAG_OFFSET_MASK; 313 *offset = sval.uvalue & MTAG_OFFSET_MASK; 314 return 1; 315 } 316 317 static int get_mtag_cnt; 318 int get_mtag(struct expression *expr, mtag_t *tag) 319 { 320 struct smatch_state *state; 321 int ret = 0; 322 323 expr = strip_expr(expr); 324 if (!expr) 325 return 0; 326 327 if (get_mtag_cnt > 0) 328 return 0; 329 330 get_mtag_cnt++; 331 332 switch (expr->type) { 333 case EXPR_STRING: 334 if (get_string_mtag(expr, tag)) { 335 ret = 1; 336 goto dec_cnt; 337 } 338 break; 339 case EXPR_SYMBOL: 340 if (get_toplevel_mtag(expr->symbol, tag)) { 341 ret = 1; 342 goto dec_cnt; 343 } 344 break; 345 case EXPR_DEREF: 346 if (get_deref_mtag(expr, tag)) { 347 ret = 1; 348 goto dec_cnt; 349 } 350 break; 351 } 352 353 state = get_state_expr(my_id, expr); 354 if (!state) 355 goto dec_cnt; 356 if (state->data) { 357 *tag = *(mtag_t *)state->data; 358 ret = 1; 359 goto dec_cnt; 360 } 361 362 dec_cnt: 363 get_mtag_cnt--; 364 return ret; 365 } 366 367 int get_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 368 { 369 int val; 370 371 if (!expr) 372 return 0; 373 if (expr->type == EXPR_PREOP && expr->op == '*') 374 return get_mtag_offset(expr->unop, tag, offset); 375 if (get_implied_mtag_offset(expr, tag, offset)) 376 return 1; 377 if (!get_mtag(expr, tag)) 378 return 0; 379 expr = strip_expr(expr); 380 if (expr->type == EXPR_SYMBOL) { 381 *offset = 0; 382 return 1; 383 } 384 val = get_member_offset_from_deref(expr); 385 if (val < 0) 386 return 0; 387 *offset = val; 388 return 1; 389 } 390 391 int create_mtag_alias(mtag_t tag, struct expression *expr, mtag_t *new) 392 { 393 char buf[256]; 394 int lines_from_start; 395 char *str; 396 397 /* 398 * We need the alias to be unique. It's not totally required that it 399 * be the same from one DB build to then next, but it makes debugging 400 * a bit simpler. 401 * 402 */ 403 404 if (!cur_func_sym) 405 return 0; 406 407 lines_from_start = expr->pos.line - cur_func_sym->pos.line; 408 str = expr_to_str(expr); 409 snprintf(buf, sizeof(buf), "%lld %d %s", tag, lines_from_start, str); 410 free_string(str); 411 412 *new = str_to_tag(buf); 413 sql_insert_mtag_alias(tag, *new); 414 415 return 1; 416 } 417 418 int expr_to_mtag_offset(struct expression *expr, mtag_t *tag, int *offset) 419 { 420 *offset = 0; 421 422 expr = strip_expr(expr); 423 if (!expr) 424 return 0; 425 426 if (is_array(expr)) 427 return get_array_mtag_offset(expr, tag, offset); 428 429 if (expr->type == EXPR_DEREF) { 430 *offset = get_member_offset_from_deref(expr); 431 if (*offset < 0) 432 return 0; 433 return get_mtag(expr->deref, tag); 434 } 435 436 if (get_implied_mtag_offset(expr, tag, offset)) 437 return 1; 438 439 return get_mtag(expr, tag); 440 } 441 442 int get_mtag_sval(struct expression *expr, sval_t *sval) 443 { 444 struct symbol *type; 445 mtag_t tag; 446 int offset = 0; 447 448 if (bits_in_pointer != 64) 449 return 0; 450 451 expr = strip_expr(expr); 452 453 type = get_type(expr); 454 if (!type_is_ptr(type)) 455 return 0; 456 /* 457 * There are only three options: 458 * 459 * 1) An array address: 460 * p = array; 461 * 2) An address like so: 462 * p = &my_struct->member; 463 * 3) A pointer: 464 * p = pointer; 465 * 466 */ 467 468 if (expr->type == EXPR_STRING && get_string_mtag(expr, &tag)) 469 goto found; 470 471 if (type->type == SYM_ARRAY && get_toplevel_mtag(expr->symbol, &tag)) 472 goto found; 473 474 if (get_implied_mtag_offset(expr, &tag, &offset)) 475 goto found; 476 477 if (expr->type != EXPR_PREOP || expr->op != '&') 478 return 0; 479 expr = strip_expr(expr->unop); 480 481 if (!expr_to_mtag_offset(expr, &tag, &offset)) 482 return 0; 483 if (offset > MTAG_OFFSET_MASK) 484 offset = MTAG_OFFSET_MASK; 485 486 found: 487 sval->type = type; 488 sval->uvalue = tag | offset; 489 490 return 1; 491 } 492 493 static struct expression *remove_dereference(struct expression *expr) 494 { 495 expr = strip_expr(expr); 496 497 if (expr->type == EXPR_PREOP && expr->op == '*') 498 return strip_expr(expr->unop); 499 return preop_expression(expr, '&'); 500 } 501 502 int get_mtag_addr_sval(struct expression *expr, sval_t *sval) 503 { 504 return get_mtag_sval(remove_dereference(expr), sval); 505 } 506 507 static void print_stored_to_mtag(int return_id, char *return_ranges, struct expression *expr) 508 { 509 struct sm_state *sm; 510 char buf[256]; 511 const char *param_name; 512 int param; 513 514 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 515 if (!sm->state->data) 516 continue; 517 518 param = get_param_num_from_sym(sm->sym); 519 if (param < 0) 520 continue; 521 param_name = get_param_name(sm); 522 if (!param_name) 523 continue; 524 if (strcmp(param_name, "$") == 0) 525 continue; 526 527 snprintf(buf, sizeof(buf), "%lld", *(mtag_t *)sm->state->data); 528 sql_insert_return_states(return_id, return_ranges, MEMORY_TAG, param, param_name, buf); 529 } END_FOR_EACH_SM(sm); 530 } 531 532 void register_mtag(int id) 533 { 534 my_id = id; 535 536 537 /* 538 * The mtag stuff only works on 64 systems because we store the 539 * information in the pointer itself. 540 * bit 63 : set for alias mtags 541 * bit 62-12: mtag hash 542 * bit 11-0 : offset 543 * 544 */ 545 if (bits_in_pointer != 64) 546 return; 547 548 add_hook(&global_variable, BASE_HOOK); 549 550 add_function_assign_hook("kmalloc", &alloc_assign, NULL); 551 add_function_assign_hook("kzalloc", &alloc_assign, NULL); 552 553 select_return_states_hook(BUF_SIZE, &db_returns_buf_size); 554 555 add_hook(&match_call_info, FUNCTION_CALL_HOOK); 556 select_caller_info_hook(save_caller_info, MEMORY_TAG); 557 add_split_return_callback(&print_stored_to_mtag); 558 select_return_states_hook(MEMORY_TAG, db_returns_memory_tag); 559 }