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