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