check_atomic_inc_dec.c

   1 /*
   2  * Copyright (C) 2016 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 <ctype.h>
  19
  20 #include "smatch.h"
  21 #include "smatch_extra.h"
  22 #include "smatch_slist.h"
  23
  24 static int my_id;
  25 static int test_id;
  26
  27 STATE(inc);
  28 STATE(start_state);
  29 STATE(dec);
  30
  31 STATE(zero_path);
  32
  33 struct ref_func_info {
  34         const char *name;
  35         int type;
  36         int param;
  37         const char *key;
  38         const sval_t *implies_start, *implies_end;
  39         func_hook *call_back;
  40 };
  41
  42 static void match_atomic_add(const char *fn, struct expression *expr, void *_unused);
  43
  44 static struct ref_func_info func_table[] = {
  45         { "atomic_inc", ATOMIC_INC, 0, "$->counter" },
  46         { "atomic_long_inc", ATOMIC_INC, 0, "$->counter" },
  47         { "atomic64_inc", ATOMIC_INC, 0, "$->counter" },
  48
  49         { "atomic_inc_return", ATOMIC_INC, 0, "$->counter" },
  50         { "atomic_long_inc_return", ATOMIC_INC, 0, "$->counter" },
  51         { "atomic64_return", ATOMIC_INC, 0, "$->counter" },
  52
  53         { "atomic_add_return", ATOMIC_INC, 1, "$->counter", NULL, NULL, match_atomic_add },
  54         { "atomic_long_add_return", ATOMIC_INC, 1, "$->counter", NULL, NULL, match_atomic_add },
  55         { "atomic64_add_return", ATOMIC_INC, 1, "$->counter", NULL, NULL, match_atomic_add },
  56
  57         { "atomic_dec", ATOMIC_DEC, 0, "$->counter" },
  58         { "atomic_long_dec", ATOMIC_DEC, 0, "$->counter" },
  59         { "atomic64_dec", ATOMIC_DEC, 0, "$->counter" },
  60
  61         { "atomic_dec_return", ATOMIC_DEC, 0, "$->counter" },
  62         { "atomic_long_dec_return", ATOMIC_DEC, 0, "$->counter" },
  63         { "atomic64_dec_return", ATOMIC_DEC, 0, "$->counter" },
  64
  65         { "atomic_dec_and_test", ATOMIC_DEC, 0, "$->counter" },
  66         { "atomic_long_dec_and_test", ATOMIC_DEC, 0, "$->counter" },
  67         { "atomic64_dec_and_test", ATOMIC_DEC, 0, "$->counter" },
  68
  69         { "_atomic_dec_and_lock", ATOMIC_DEC, 0, "$->counter" },
  70
  71         { "atomic_sub", ATOMIC_DEC, 1, "$->counter" },
  72         { "atomic_long_sub", ATOMIC_DEC, 1, "$->counter" },
  73         { "atomic64_sub", ATOMIC_DEC, 1, "$->counter" },
  74
  75         { "atomic_sub_return", ATOMIC_DEC, 1, "$->counter" },
  76         { "atomic_long_sub_return", ATOMIC_DEC, 1, "$->counter" },
  77         { "atomic64_sub_return", ATOMIC_DEC, 1, "$->counter" },
  78
  79         { "atomic_sub_and_test", ATOMIC_DEC, 1, "$->counter" },
  80         { "atomic_long_sub_and_test", ATOMIC_DEC, 1, "$->counter" },
  81         { "atomic64_sub_and_test", ATOMIC_DEC, 1, "$->counter" },
  82
  83         { "refcount_inc", ATOMIC_INC, 0, "$->refs.counter" },
  84         { "refcount_dec", ATOMIC_DEC, 0, "$->refs.counter" },
  85         { "refcount_dec_and_test", ATOMIC_DEC, 0, "$->refs.counter" },
  86         { "refcount_add", ATOMIC_INC, 1, "$->refs.counter" },
  87         { "refcount_sub_and_test", ATOMIC_DEC, 1, "$->refs.counter" },
  88
  89         { "pm_runtime_get_sync", ATOMIC_INC, 0, "$->power.usage_count.counter" },
  90         { "of_clk_del_provider", ATOMIC_DEC, 0, "$->kobj.kref.refcount.refs.counter" },
  91
  92         { "refcount_inc_not_zero", ATOMIC_INC, 0, "$->refs.counter", &int_one, &int_one},
  93         { "refcount_add_not_zero", ATOMIC_INC, 1, "$->refs.counter", &int_one, &int_one},
  94
  95         { "atomic_dec_if_positive", ATOMIC_DEC, 0, "$->counter", &int_zero, &int_max},
  96         { "atomic64_dec_if_positive", ATOMIC_DEC, 0, "$->counter", &int_zero, &int_max},
  97
  98         { "of_node_get", ATOMIC_INC, 0, "$->kobj.kref.refcount.refs.counter" },
  99         { "of_node_put", ATOMIC_DEC, 0, "$->kobj.kref.refcount.refs.counter" },
 100         { "of_get_parent", ATOMIC_INC, -1, "$->kobj.kref.refcount.refs.counter" },
 101         { "of_clk_del_provider", ATOMIC_DEC, 0, "$->kobj.kref.refcount.refs.counter" },
 102
 103         { "kfree_skb", ATOMIC_DEC, 0, "$->users.refs.counter" },
 104 };
 105
 106 static struct smatch_state *unmatched_state(struct sm_state *sm)
 107 {
 108         /*
 109          * We default to decremented.  For example, say we have:
 110          *      if (p)
 111          *              atomic_dec(p);
 112          *      <- p is decreemented.
 113          *
 114          */
 115         if ((sm->state == &dec) &&
 116             parent_is_gone_var_sym(sm->name, sm->sym))
 117                 return sm->state;
 118         return &start_state;
 119 }
 120
 121 static struct stree *start_states;
 122 static void set_start_state(const char *name, struct symbol *sym, struct smatch_state *start)
 123 {
 124         struct smatch_state *orig;
 125
 126         orig = get_state_stree(start_states, my_id, name, sym);
 127         if (!orig)
 128                 set_state_stree(&start_states, my_id, name, sym, start);
 129         else if (orig != start)
 130                 set_state_stree(&start_states, my_id, name, sym, &undefined);
 131 }
 132
 133 static struct sm_state *get_best_match(const char *key)
 134 {
 135         struct sm_state *sm;
 136         struct sm_state *match;
 137         int cnt = 0;
 138         int start_pos, state_len, key_len, chunks, i;
 139
 140         if (strncmp(key, "$->", 3) == 0)
 141                 key += 3;
 142
 143         key_len = strlen(key);
 144         chunks = 0;
 145         for (i = key_len - 1; i > 0; i--) {
 146                 if (key[i] == '>' || key[i] == '.')
 147                         chunks++;
 148                 if (chunks == 3) {
 149                         key += (i + 1);
 150                         key_len = strlen(key);
 151                         break;
 152                 }
 153         }
 154
 155         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 156                 state_len = strlen(sm->name);
 157                 if (state_len < key_len)
 158                         continue;
 159                 start_pos = state_len - key_len;
 160                 if ((start_pos == 0 || !isalnum(sm->name[start_pos - 1])) &&
 161                     strcmp(sm->name + start_pos, key) == 0) {
 162                         cnt++;
 163                         match = sm;
 164                 }
 165         } END_FOR_EACH_SM(sm);
 166
 167         if (cnt == 1)
 168                 return match;
 169         return NULL;
 170 }
 171
 172 static void handle_test_functions(struct expression *expr)
 173 {
 174         struct expression *tmp;
 175         struct statement *stmt;
 176         int count = 0;
 177
 178         if (expr->type != EXPR_CALL ||
 179             expr->fn->type != EXPR_SYMBOL ||
 180             !expr->fn->symbol_name)
 181                 return;
 182         if (!strstr(expr->fn->symbol_name->name, "test"))
 183                 return;
 184
 185         while ((tmp = expr_get_parent_expr(expr))) {
 186                 expr = tmp;
 187                 if (count++ > 5)
 188                         break;
 189         }
 190
 191         stmt = expr_get_parent_stmt(expr);
 192         if (!stmt || stmt->type != STMT_IF)
 193                 return;
 194
 195         set_true_false_states(test_id, "dec_path", NULL, &zero_path, NULL);
 196 }
 197
 198 static void db_inc_dec(struct expression *expr, int param, const char *key, int inc_dec)
 199 {
 200         struct sm_state *start_sm;
 201         struct expression *call, *arg;
 202         char *name;
 203         struct symbol *sym;
 204         bool free_at_end = true;
 205
 206         call = expr;
 207         while (call && call->type == EXPR_ASSIGNMENT)
 208                 call = strip_expr(call->right);
 209
 210         if (!call || call->type != EXPR_CALL)
 211                 return;
 212
 213         handle_test_functions(call);
 214
 215         if (param == -1 &&
 216             expr->type == EXPR_ASSIGNMENT &&
 217             expr->op == '=') {
 218                 name = get_variable_from_key(expr->left, key, &sym);
 219                 if (!name || !sym)
 220                         goto free;
 221         } else if (param >= 0) {
 222                 arg = get_argument_from_call_expr(call->args, param);
 223                 if (!arg)
 224                         return;
 225
 226                 name = get_variable_from_key(arg, key, &sym);
 227                 if (!name || !sym)
 228                         goto free;
 229         } else {
 230                 name = alloc_string(key);
 231                 sym = NULL;
 232         }
 233
 234         start_sm = get_sm_state(my_id, name, sym);
 235         if (!start_sm && !sym && inc_dec == ATOMIC_DEC) {
 236                 start_sm = get_best_match(key);
 237                 if (start_sm) {
 238                         free_string(name);
 239                         free_at_end = false;
 240                         name = (char *)start_sm->name;
 241                         sym = start_sm->sym;
 242                 }
 243         }
 244
 245         if (inc_dec == ATOMIC_INC) {
 246                 if (!start_sm)
 247                         set_start_state(name, sym, &dec);
 248 //              set_refcount_inc(name, sym);
 249                 set_state(my_id, name, sym, &inc);
 250         } else {
 251 //              set_refcount_dec(name, sym);
 252                 if (!start_sm)
 253                         set_start_state(name, sym, &inc);
 254
 255                 if (start_sm && start_sm->state == &inc)
 256                         set_state(my_id, name, sym, &start_state);
 257                 else
 258                         set_state(my_id, name, sym, &dec);
 259         }
 260
 261 free:
 262         if (free_at_end)
 263                 free_string(name);
 264 }
 265
 266 static bool is_inc_dec_primitive(struct expression *expr)
 267 {
 268         int i;
 269
 270         while (expr->type == EXPR_ASSIGNMENT)
 271                 expr = strip_expr(expr->right);
 272         if (expr->type != EXPR_CALL)
 273                 return false;
 274
 275         if (expr->fn->type != EXPR_SYMBOL)
 276                 return false;
 277
 278         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
 279                 if (sym_name_is(func_table[i].name, expr->fn))
 280                         return true;
 281         }
 282
 283         return false;
 284 }
 285
 286 static void db_inc(struct expression *expr, int param, char *key, char *value)
 287 {
 288         if (is_inc_dec_primitive(expr))
 289                 return;
 290         db_inc_dec(expr, param, key, ATOMIC_INC);
 291 }
 292
 293 static void db_dec(struct expression *expr, int param, char *key, char *value)
 294 {
 295         if (is_inc_dec_primitive(expr))
 296                 return;
 297         db_inc_dec(expr, param, key, ATOMIC_DEC);
 298 }
 299
 300 static void match_atomic_add(const char *fn, struct expression *expr, void *_unused)
 301 {
 302         struct expression *amount;
 303         sval_t sval;
 304
 305         amount = get_argument_from_call_expr(expr->args, 0);
 306         if (get_implied_value(amount, &sval) && sval_is_negative(sval)) {
 307                 db_inc_dec(expr, 1, "$->counter", ATOMIC_DEC);
 308                 return;
 309         }
 310
 311         db_inc_dec(expr, 1, "$->counter", ATOMIC_INC);
 312 }
 313
 314 static void refcount_function(const char *fn, struct expression *expr, void *data)
 315 {
 316         struct ref_func_info *info = data;
 317
 318         db_inc_dec(expr, info->param, info->key, info->type);
 319 }
 320
 321 static void refcount_implied(const char *fn, struct expression *call_expr,
 322                              struct expression *assign_expr, void *data)
 323 {
 324         struct ref_func_info *info = data;
 325
 326         db_inc_dec(assign_expr ?: call_expr, info->param, info->key, info->type);
 327 }
 328
 329 static bool is_maybe_dec(struct sm_state *sm)
 330 {
 331         if (sm->state == &dec)
 332                 return true;
 333         if (slist_has_state(sm->possible, &dec) &&
 334             !slist_has_state(sm->possible, &inc))
 335                 return true;
 336         return false;
 337 }
 338
 339 static void match_return_info(int return_id, char *return_ranges, struct expression *expr)
 340 {
 341         struct sm_state *sm;
 342         const char *param_name;
 343         int param;
 344
 345         if (is_impossible_path())
 346                 return;
 347
 348         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 349                 if (sm->state != &inc && !is_maybe_dec(sm))
 350                         continue;
 351                 if (sm->state == get_state_stree(start_states, my_id, sm->name, sm->sym))
 352                         continue;
 353                 if (parent_is_null_var_sym(sm->name, sm->sym))
 354                         continue;
 355                 if (sm->state == &inc &&
 356                     parent_is_free_var_sym(sm->name, sm->sym))
 357                         continue;
 358                 param = get_param_key_from_sm(sm, expr, &param_name);
 359                 if (param < -1)
 360                         continue;
 361                 sql_insert_return_states(return_id, return_ranges,
 362                                          (sm->state == &inc) ? ATOMIC_INC : ATOMIC_DEC,
 363                                          param, param_name, "");
 364         } END_FOR_EACH_SM(sm);
 365 }
 366
 367 enum {
 368         EMPTY, NEGATIVE, ZERO, POSITIVE, NUM_BUCKETS
 369 };
 370
 371 static int success_fail_positive(struct range_list *rl)
 372 {
 373         if (!rl)
 374                 return EMPTY;
 375
 376         if (!is_whole_rl(rl) && sval_is_negative(rl_min(rl)))
 377                 return NEGATIVE;
 378
 379         if (rl_min(rl).value == 0)
 380                 return ZERO;
 381
 382         return POSITIVE;
 383 }
 384
 385 static void check_counter(const char *name, struct symbol *sym)
 386 {
 387         struct range_list *inc_lines = NULL;
 388         struct range_list *dec_lines = NULL;
 389         int inc_buckets[NUM_BUCKETS] = {};
 390         int dec_buckets[NUM_BUCKETS] = {};
 391         int start_buckets[NUM_BUCKETS] = {};
 392         struct stree *stree, *orig_stree;
 393         struct smatch_state *state;
 394         struct sm_state *return_sm;
 395         struct sm_state *sm;
 396         sval_t line = sval_type_val(&int_ctype, 0);
 397         int bucket;
 398
 399         /* don't warn about stuff we can't identify */
 400         if (!sym)
 401                 return;
 402
 403         /* static variable are probably just counters */
 404         if (sym->ctype.modifiers & MOD_STATIC &&
 405             !(sym->ctype.modifiers & MOD_TOPLEVEL))
 406                 return;
 407
 408         if (strstr(name, "error") ||
 409             strstr(name, "drop") ||
 410             strstr(name, "xmt_ls_err") ||
 411             strstr(name, "->stats->") ||
 412             strstr(name, "->stats."))
 413                 return;
 414
 415         if (strstr(name, "power.usage_count"))
 416                 return;
 417
 418         FOR_EACH_PTR(get_all_return_strees(), stree) {
 419                 orig_stree = __swap_cur_stree(stree);
 420
 421                 if (is_impossible_path())
 422                         goto swap_stree;
 423
 424                 return_sm = get_sm_state(RETURN_ID, "return_ranges", NULL);
 425                 if (!return_sm)
 426                         goto swap_stree;
 427                 line.value = return_sm->line;
 428
 429                 if (get_state_stree(start_states, my_id, name, sym) == &inc)
 430                         goto swap_stree;
 431
 432                 if (parent_is_gone_var_sym(name, sym))
 433                         goto swap_stree;
 434
 435                 sm = get_sm_state(my_id, name, sym);
 436                 if (sm)
 437                         state = sm->state;
 438                 else
 439                         state = &start_state;
 440
 441                 if (state != &inc &&
 442                     state != &dec &&
 443                     state != &start_state)
 444                         goto swap_stree;
 445
 446                 bucket = success_fail_positive(estate_rl(return_sm->state));
 447
 448                 if (state == &inc) {
 449                         add_range(&inc_lines, line, line);
 450                         inc_buckets[bucket]++;
 451                 }
 452                 if (state == &dec) {
 453                         add_range(&dec_lines, line, line);
 454                         dec_buckets[bucket]++;
 455                 }
 456                 if (state == &start_state)
 457                         start_buckets[bucket]++;
 458 swap_stree:
 459                 __swap_cur_stree(orig_stree);
 460         } END_FOR_EACH_PTR(stree);
 461
 462         if (inc_buckets[NEGATIVE] &&
 463             inc_buckets[ZERO]) {
 464                 // sm_warning("XXX '%s' not decremented on lines: %s.", name, show_rl(inc_lines));
 465         }
 466
 467 }
 468
 469 static void match_check_missed(struct symbol *sym)
 470 {
 471         struct sm_state *sm;
 472
 473         FOR_EACH_MY_SM(my_id, get_all_return_states(), sm) {
 474                 check_counter(sm->name, sm->sym);
 475         } END_FOR_EACH_SM(sm);
 476 }
 477
 478 int on_atomic_dec_path(void)
 479 {
 480         return get_state(test_id, "dec_path", NULL) == &zero_path;
 481 }
 482
 483 int was_inced(const char *name, struct symbol *sym)
 484 {
 485         return get_state(my_id, name, sym) == &inc;
 486 }
 487
 488 static void match_after_func(struct symbol *sym)
 489 {
 490         free_stree(&start_states);
 491 }
 492
 493 void check_atomic_inc_dec(int id)
 494 {
 495         struct ref_func_info *info;
 496         int i;
 497
 498         my_id = id;
 499
 500         if (option_project != PROJ_KERNEL)
 501                 return;
 502
 503         add_unmatched_state_hook(my_id, &unmatched_state);
 504
 505         add_split_return_callback(match_return_info);
 506         select_return_states_hook(ATOMIC_INC, &db_inc);
 507         select_return_states_hook(ATOMIC_DEC, &db_dec);
 508
 509         for (i = 0; i < ARRAY_SIZE(func_table); i++) {
 510                 info = &func_table[i];
 511
 512                 if (info->call_back) {
 513                         add_function_hook(info->name, info->call_back, info);
 514                 } else if (info->implies_start) {
 515                         return_implies_state_sval(info->name,
 516                                         *info->implies_start, *info->implies_end,
 517                                         &refcount_implied, info);
 518                 } else {
 519                         add_function_hook(info->name, &refcount_function, info);
 520                 }
 521         }
 522
 523         add_hook(&match_check_missed, END_FUNC_HOOK);
 524
 525         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 526         add_function_data((unsigned long *)&start_states);
 527 }
 528
 529 void check_atomic_test(int id)
 530 {
 531         if (option_project != PROJ_KERNEL)
 532                 return;
 533
 534         test_id = id;
 535 }