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, const char *value, 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, value, 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, value, 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 void match_return_info(int return_id, char *return_ranges, struct expression *expr)
 263 {
 264         struct sm_state *sm;
 265         const char *param_name;
 266         int param;
 267
 268         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 269                 if (sm->state != &inc &&
 270                     sm->state != &dec)
 271                         continue;
 272                 if (parent_is_gone_var_sym(sm->name, sm->sym))
 273                         continue;
 274                 param = get_param_num_from_sym(sm->sym);
 275                 if (param < 0)
 276                         continue;
 277                 param_name = get_param_name(sm);
 278                 if (!param_name)
 279                         continue;
 280                 sql_insert_return_states(return_id, return_ranges,
 281                                          (sm->state == &inc) ? ATOMIC_INC : ATOMIC_DEC,
 282                                          param, param_name, "");
 283         } END_FOR_EACH_SM(sm);
 284 }
 285
 286 enum {
 287         EMPTY, NEGATIVE, ZERO, POSITIVE, NUM_BUCKETS
 288 };
 289
 290 static int success_fail_positive(struct range_list *rl)
 291 {
 292         if (!rl)
 293                 return EMPTY;
 294
 295         if (sval_is_negative(rl_min(rl)))
 296                 return NEGATIVE;
 297
 298         if (rl_min(rl).value == 0)
 299                 return ZERO;
 300
 301         return POSITIVE;
 302 }
 303
 304 static void check_counter(const char *name, struct symbol *sym)
 305 {
 306         struct range_list *inc_lines = NULL;
 307         struct range_list *dec_lines = NULL;
 308         int inc_buckets[NUM_BUCKETS] = {};
 309         int dec_buckets[NUM_BUCKETS] = {};
 310         struct stree *stree, *orig_stree;
 311         struct smatch_state *state;
 312         struct sm_state *return_sm;
 313         struct sm_state *sm;
 314         sval_t line = sval_type_val(&int_ctype, 0);
 315         int bucket;
 316
 317         FOR_EACH_PTR(get_all_return_strees(), stree) {
 318                 orig_stree = __swap_cur_stree(stree);
 319
 320                 return_sm = get_sm_state(RETURN_ID, "return_ranges", NULL);
 321                 if (!return_sm)
 322                         goto swap_stree;
 323                 line.value = return_sm->line;
 324
 325                 if (get_state_stree(start_states, my_id, name, sym) == &inc)
 326                         goto swap_stree;
 327
 328                 if (parent_is_gone_var_sym(name, sym))
 329                         goto swap_stree;
 330
 331                 sm = get_sm_state(my_id, name, sym);
 332                 if (sm)
 333                         state = sm->state;
 334                 else
 335                         state = &start_state;
 336
 337                 if (state != &inc &&
 338                     state != &dec &&
 339                     state != &start_state)
 340                         goto swap_stree;
 341
 342                 bucket = success_fail_positive(estate_rl(return_sm->state));
 343
 344                 if (state == &inc) {
 345                         add_range(&inc_lines, line, line);
 346                         inc_buckets[bucket] = true;
 347                 }
 348                 if (state == &dec || state == &start_state) {
 349                         add_range(&dec_lines, line, line);
 350                         dec_buckets[bucket] = true;
 351                 }
 352 swap_stree:
 353                 __swap_cur_stree(orig_stree);
 354         } END_FOR_EACH_PTR(stree);
 355
 356         if (inc_buckets[NEGATIVE] &&
 357             inc_buckets[ZERO]) {
 358                 // sm_warning("XXX '%s' not decremented on lines: %s.", name, show_rl(inc_lines));
 359         }
 360
 361 }
 362
 363 static void match_check_missed(struct symbol *sym)
 364 {
 365         struct sm_state *sm;
 366
 367         FOR_EACH_MY_SM(my_id, get_all_return_states(), sm) {
 368                 check_counter(sm->name, sm->sym);
 369         } END_FOR_EACH_SM(sm);
 370 }
 371
 372 int on_atomic_dec_path(void)
 373 {
 374         struct sm_state *sm;
 375
 376         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 377                 if (sm->state == &dec)
 378                         return 1;
 379         } END_FOR_EACH_SM(sm);
 380
 381         return 0;
 382 }
 383
 384 int was_inced(const char *name, struct symbol *sym)
 385 {
 386         return get_state(my_id, name, sym) == &inc;
 387 }
 388
 389 static void match_save_states(struct expression *expr)
 390 {
 391         push_stree(&saved_stack, start_states);
 392         start_states = NULL;
 393 }
 394
 395 static void match_restore_states(struct expression *expr)
 396 {
 397         start_states = pop_stree(&saved_stack);
 398 }
 399
 400 static void match_after_func(struct symbol *sym)
 401 {
 402         free_stree(&start_states);
 403 }
 404
 405 void check_atomic_inc_dec(int id)
 406 {
 407         my_id = id;
 408
 409         if (option_project != PROJ_KERNEL)
 410                 return;
 411
 412         add_unmatched_state_hook(my_id, &unmatched_state);
 413
 414         add_split_return_callback(match_return_info);
 415         select_return_states_hook(ATOMIC_INC, &db_inc);
 416         select_return_states_hook(ATOMIC_DEC, &db_dec);
 417
 418         add_function_hook("atomic_inc_return", &match_atomic_inc, NULL);
 419         add_function_hook("atomic_add_return", &match_atomic_add, NULL);
 420         add_function_hook("atomic_sub_return", &match_atomic_sub, NULL);
 421         add_function_hook("atomic_sub_and_test", &match_atomic_sub, NULL);
 422         add_function_hook("atomic_long_sub_and_test", &match_atomic_sub, NULL);
 423         add_function_hook("atomic64_sub_and_test", &match_atomic_sub, NULL);
 424         add_function_hook("atomic_dec_and_test", &match_atomic_dec, NULL);
 425         add_function_hook("atomic_long_dec_and_test", &match_atomic_dec, NULL);
 426         add_function_hook("atomic64_dec_and_test", &match_atomic_dec, NULL);
 427         add_function_hook("_atomic_dec_and_lock", &match_atomic_dec, NULL);
 428         add_function_hook("atomic_dec", &match_atomic_dec, NULL);
 429         add_function_hook("atomic_dec_return", &match_atomic_dec, NULL);
 430         add_function_hook("atomic_long_inc", &match_atomic_inc, NULL);
 431         add_function_hook("atomic_long_dec", &match_atomic_dec, NULL);
 432         add_function_hook("atomic_inc", &match_atomic_inc, NULL);
 433         add_function_hook("atomic_sub", &match_atomic_sub, NULL);
 434
 435         add_function_hook("refcount_inc", &refcount_inc, INT_PTR(0));
 436         add_function_hook("refcount_dec", &refcount_dec, INT_PTR(0));
 437         add_function_hook("refcount_add", &refcount_inc, INT_PTR(1));
 438
 439         return_implies_state("refcount_add_not_zero", 1, 1, &match_implies_inc, INT_PTR(1));
 440         return_implies_state("refcount_inc_not_zero", 1, 1, &match_implies_inc, INT_PTR(0));
 441
 442         return_implies_state("atomic_dec_if_positive", 0, INT_MAX, &match_implies_atomic_dec, INT_PTR(0));
 443
 444         add_function_hook("refcount_sub_and_test", &refcount_dec, INT_PTR(1));
 445         add_function_hook("refcount_dec_and_test", &refcount_dec, INT_PTR(0));
 446
 447         add_function_hook("pm_runtime_get_sync", &pm_runtime_get_sync, INT_PTR(0));
 448
 449         add_hook(&match_check_missed, END_FUNC_HOOK);
 450
 451         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 452         add_hook(&match_save_states, INLINE_FN_START);
 453         add_hook(&match_restore_states, INLINE_FN_END);
 454 }