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