smatch_mtag.c

   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 mtag_t str_to_tag(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_tag(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_tag("__smatch string");
 160         *tag = str_to_tag(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_tag(buf);
 181         return 1;
 182 }
 183
 184 int get_deref_mtag(struct expression *expr, mtag_t *tag)
 185 {
 186         mtag_t container_tag, member_tag;
 187         int offset;
 188
 189         /*
 190          * I'm not totally sure what I'm doing...
 191          *
 192          * This is supposed to get something like "global_var->ptr", but I don't
 193          * feel like it's complete at all.
 194          *
 195          */
 196
 197         if (!get_mtag(expr->unop, &container_tag))
 198                 return 0;
 199
 200         offset = get_member_offset_from_deref(expr);
 201         if (offset < 0)
 202                 return 0;
 203
 204         if (!mtag_map_select_tag(container_tag, -offset, &member_tag))
 205                 return 0;
 206
 207         *tag = member_tag;
 208         return 1;
 209 }
 210
 211 static void global_variable(struct symbol *sym)
 212 {
 213         mtag_t tag;
 214
 215         if (!get_toplevel_mtag(sym, &tag))
 216                 return;
 217
 218         sql_insert_mtag_about(tag,
 219                               sym->ident->name,
 220                               (sym->ctype.modifiers & MOD_STATIC) ? get_filename() : "extern");
 221 }
 222
 223 static int get_array_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
 224 {
 225         struct expression *array, *offset_expr;
 226         struct symbol *type;
 227         sval_t sval;
 228
 229         if (!is_array(expr))
 230                 return 0;
 231
 232         array = get_array_base(expr);
 233         if (!array)
 234                 return 0;
 235         type = get_type(array);
 236         if (!type || type->type != SYM_ARRAY)
 237                 return 0;
 238         type = get_real_base_type(type);
 239         if (!type_bytes(type))
 240                 return 0;
 241
 242         if (!get_mtag(array, tag))
 243                 return 0;
 244
 245         offset_expr = get_array_offset(expr);
 246         if (!get_value(offset_expr, &sval))
 247                 return 0;
 248         *offset = sval.value * type_bytes(type);
 249
 250         return 1;
 251 }
 252
 253 static int get_implied_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
 254 {
 255         struct smatch_state *state;
 256         struct symbol *type;
 257         sval_t sval;
 258
 259         type = get_type(expr);
 260         if (!type_is_ptr(type))
 261                 return 0;
 262         state = get_extra_state(expr);
 263         if (!state || !estate_get_single_value(state, &sval) || sval.value == 0)
 264                 return 0;
 265
 266         *tag = sval.uvalue & ~MTAG_OFFSET_MASK;
 267         *offset = sval.uvalue & MTAG_OFFSET_MASK;
 268         return 1;
 269 }
 270
 271 static int get_mtag_cnt;
 272 int get_mtag(struct expression *expr, mtag_t *tag)
 273 {
 274         struct smatch_state *state;
 275         int ret = 0;
 276
 277         expr = strip_expr(expr);
 278         if (!expr)
 279                 return 0;
 280
 281         if (get_mtag_cnt > 0)
 282                 return 0;
 283
 284         get_mtag_cnt++;
 285
 286         switch (expr->type) {
 287         case EXPR_STRING:
 288                 if (get_string_mtag(expr, tag)) {
 289                         ret = 1;
 290                         goto dec_cnt;
 291                 }
 292                 break;
 293         case EXPR_SYMBOL:
 294                 if (get_toplevel_mtag(expr->symbol, tag)) {
 295                         ret = 1;
 296                         goto dec_cnt;
 297                 }
 298                 break;
 299         case EXPR_DEREF:
 300                 if (get_deref_mtag(expr, tag)) {
 301                         ret = 1;
 302                         goto dec_cnt;
 303                 }
 304                 break;
 305         }
 306
 307         state = get_state_expr(my_id, expr);
 308         if (!state)
 309                 goto dec_cnt;
 310         if (state->data) {
 311                 *tag = *(mtag_t *)state->data;
 312                 ret = 1;
 313                 goto dec_cnt;
 314         }
 315
 316 dec_cnt:
 317         get_mtag_cnt--;
 318         return ret;
 319 }
 320
 321 int get_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
 322 {
 323         int val;
 324
 325         if (!expr)
 326                 return 0;
 327         if (expr->type == EXPR_PREOP && expr->op == '*')
 328                 return get_mtag_offset(expr->unop, tag, offset);
 329         if (get_implied_mtag_offset(expr, tag, offset))
 330                 return 1;
 331         if (!get_mtag(expr, tag))
 332                 return 0;
 333         expr = strip_expr(expr);
 334         if (expr->type == EXPR_SYMBOL) {
 335                 *offset = 0;
 336                 return 1;
 337         }
 338         val = get_member_offset_from_deref(expr);
 339         if (val < 0)
 340                 return 0;
 341         *offset = val;
 342         return 1;
 343 }
 344
 345 struct range_list *swap_mtag_seed(struct expression *expr, struct range_list *rl)
 346 {
 347         char buf[256];
 348         char *name;
 349         sval_t sval;
 350         mtag_t tag;
 351
 352         if (!rl_to_sval(rl, &sval))
 353                 return rl;
 354         if (sval.type->type != SYM_PTR || sval.uvalue != MTAG_SEED)
 355                 return rl;
 356
 357         name = expr_to_str(expr);
 358         snprintf(buf, sizeof(buf), "%s %s %s", get_filename(), get_function(), name);
 359         free_string(name);
 360         tag = str_to_tag(buf);
 361         sval.value = tag;
 362         return alloc_rl(sval, sval);
 363 }
 364
 365 int create_mtag_alias(mtag_t tag, struct expression *expr, mtag_t *new)
 366 {
 367         char buf[256];
 368         int lines_from_start;
 369         char *str;
 370
 371         /*
 372          * We need the alias to be unique.  It's not totally required that it
 373          * be the same from one DB build to then next, but it makes debugging
 374          * a bit simpler.
 375          *
 376          */
 377
 378         if (!cur_func_sym)
 379                 return 0;
 380
 381         lines_from_start = expr->pos.line - cur_func_sym->pos.line;
 382         str = expr_to_str(expr);
 383         snprintf(buf, sizeof(buf), "%lld %d %s", tag, lines_from_start, str);
 384         free_string(str);
 385
 386         *new = str_to_tag(buf);
 387         sql_insert_mtag_alias(tag, *new);
 388
 389         return 1;
 390 }
 391
 392 int expr_to_mtag_offset(struct expression *expr, mtag_t *tag, int *offset)
 393 {
 394         *offset = 0;
 395
 396         expr = strip_expr(expr);
 397         if (!expr)
 398                 return 0;
 399
 400         if (is_array(expr))
 401                 return get_array_mtag_offset(expr, tag, offset);
 402
 403         if (expr->type == EXPR_DEREF) {
 404                 *offset = get_member_offset_from_deref(expr);
 405                 if (*offset < 0)
 406                         return 0;
 407                 return get_mtag(expr->deref, tag);
 408         }
 409
 410         if (get_implied_mtag_offset(expr, tag, offset))
 411                 return 1;
 412
 413         return get_mtag(expr, tag);
 414 }
 415
 416 int get_mtag_sval(struct expression *expr, sval_t *sval)
 417 {
 418         struct symbol *type;
 419         mtag_t tag;
 420         int offset = 0;
 421
 422         if (bits_in_pointer != 64)
 423                 return 0;
 424
 425         expr = strip_expr(expr);
 426
 427         type = get_type(expr);
 428         if (!type_is_ptr(type))
 429                 return 0;
 430         /*
 431          * There are only three options:
 432          *
 433          * 1) An array address:
 434          *    p = array;
 435          * 2) An address like so:
 436          *    p = &my_struct->member;
 437          * 3) A pointer:
 438          *    p = pointer;
 439          *
 440          */
 441
 442         if (expr->type == EXPR_STRING && get_string_mtag(expr, &tag))
 443                 goto found;
 444
 445         if (expr->type == EXPR_SYMBOL &&
 446             (type->type == SYM_ARRAY || type->type == SYM_FN) &&
 447             get_toplevel_mtag(expr->symbol, &tag))
 448                 goto found;
 449
 450         if (get_implied_mtag_offset(expr, &tag, &offset))
 451                 goto found;
 452
 453         if (expr->type != EXPR_PREOP || expr->op != '&')
 454                 return 0;
 455         expr = strip_expr(expr->unop);
 456
 457         if (!expr_to_mtag_offset(expr, &tag, &offset))
 458                 return 0;
 459         if (offset > MTAG_OFFSET_MASK)
 460                 offset = MTAG_OFFSET_MASK;
 461
 462 found:
 463         sval->type = type;
 464         sval->uvalue = tag | offset;
 465
 466         return 1;
 467 }
 468
 469 static struct expression *remove_dereference(struct expression *expr)
 470 {
 471         expr = strip_expr(expr);
 472
 473         if (!expr)
 474                 return NULL;
 475         if (expr->type == EXPR_PREOP && expr->op == '*')
 476                 return strip_expr(expr->unop);
 477         return preop_expression(expr, '&');
 478 }
 479
 480 int get_mtag_addr_sval(struct expression *expr, sval_t *sval)
 481 {
 482         return get_mtag_sval(remove_dereference(expr), sval);
 483 }
 484
 485 void register_mtag(int id)
 486 {
 487         my_id = id;
 488
 489
 490         /*
 491          * The mtag stuff only works on 64 systems because we store the
 492          * information in the pointer itself.
 493          * bit 63   : set for alias mtags
 494          * bit 62-12: mtag hash
 495          * bit 11-0 : offset
 496          *
 497          */
 498         if (bits_in_pointer != 64)
 499                 return;
 500
 501         add_hook(&global_variable, BASE_HOOK);
 502 }