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(orig); 28 STATE(dec); 29 30 static struct smatch_state *unmatched_state(struct sm_state *sm) 31 { 32 if (parent_is_gone_var_sym(sm->name, sm->sym)) 33 return sm->state; 34 return &undefined; 35 } 36 37 static struct stree *start_states; 38 static struct stree_stack *saved_stack; 39 static void set_start_state(const char *name, struct symbol *sym, struct smatch_state *start) 40 { 41 struct smatch_state *orig; 42 43 orig = get_state_stree(start_states, my_id, name, sym); 44 if (!orig) 45 set_state_stree(&start_states, my_id, name, sym, start); 46 else if (orig != start) 47 set_state_stree(&start_states, my_id, name, sym, &undefined); 48 } 49 50 static struct sm_state *get_best_match(const char *key) 51 { 52 struct sm_state *sm; 53 struct sm_state *match; 54 int cnt = 0; 55 int start_pos, state_len, key_len, chunks, i; 56 57 if (strncmp(key, "$->", 3) == 0) 58 key += 3; 59 60 key_len = strlen(key); 61 chunks = 0; 62 for (i = key_len - 1; i > 0; i--) { 63 if (key[i] == '>' || key[i] == '.') 64 chunks++; 65 if (chunks == 2) { 66 key += (i + 1); 67 key_len = strlen(key); 68 break; 69 } 70 } 71 72 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 73 state_len = strlen(sm->name); 74 if (state_len < key_len) 75 continue; 76 start_pos = state_len - key_len; 77 if ((start_pos == 0 || !isalnum(sm->name[start_pos - 1])) && 78 strcmp(sm->name + start_pos, key) == 0) { 79 cnt++; 80 match = sm; 81 } 82 } END_FOR_EACH_SM(sm); 83 84 if (cnt == 1) 85 return match; 86 return NULL; 87 } 88 89 static void db_inc_dec(struct expression *expr, int param, const char *key, const char *value, int inc_dec) 90 { 91 struct sm_state *start_sm; 92 struct expression *arg; 93 char *name; 94 struct symbol *sym; 95 bool free_at_end = true; 96 97 while (expr->type == EXPR_ASSIGNMENT) 98 expr = strip_expr(expr->right); 99 if (expr->type != EXPR_CALL) 100 return; 101 102 arg = get_argument_from_call_expr(expr->args, param); 103 if (!arg) 104 return; 105 106 name = get_variable_from_key(arg, key, &sym); 107 if (!name || !sym) 108 goto free; 109 110 start_sm = get_sm_state(my_id, name, sym); 111 if (!start_sm && inc_dec == ATOMIC_DEC) { 112 start_sm = get_best_match(key); 113 if (start_sm) { 114 free_string(name); 115 free_at_end = false; 116 name = (char *)start_sm->name; 117 sym = start_sm->sym; 118 } 119 } 120 121 if (inc_dec == ATOMIC_INC) { 122 if (!start_sm) 123 set_start_state(name, sym, &dec); 124 // set_refcount_inc(name, sym); 125 set_state(my_id, name, sym, &inc); 126 } else { 127 // set_refcount_dec(name, sym); 128 if (!start_sm) 129 set_start_state(name, sym, &inc); 130 131 if (start_sm && start_sm->state == &inc) 132 set_state(my_id, name, sym, &orig); 133 else 134 set_state(my_id, name, sym, &dec); 135 } 136 137 free: 138 if (free_at_end) 139 free_string(name); 140 } 141 142 static void db_inc(struct expression *expr, int param, char *key, char *value) 143 { 144 db_inc_dec(expr, param, key, value, ATOMIC_INC); 145 } 146 147 static void db_dec(struct expression *expr, int param, char *key, char *value) 148 { 149 db_inc_dec(expr, param, key, value, ATOMIC_DEC); 150 } 151 152 static void match_atomic_inc(const char *fn, struct expression *expr, void *_unused) 153 { 154 db_inc_dec(expr, 0, "$->counter", "", ATOMIC_INC); 155 } 156 157 static void match_atomic_dec(const char *fn, struct expression *expr, void *_unused) 158 { 159 db_inc_dec(expr, 0, "$->counter", "", ATOMIC_DEC); 160 } 161 162 static void match_atomic_add(const char *fn, struct expression *expr, void *_unused) 163 { 164 struct expression *amount; 165 sval_t sval; 166 167 amount = get_argument_from_call_expr(expr->args, 0); 168 if (get_implied_value(amount, &sval) && sval_is_negative(sval)) { 169 db_inc_dec(expr, 1, "$->counter", "", ATOMIC_DEC); 170 return; 171 } 172 173 db_inc_dec(expr, 1, "$->counter", "", ATOMIC_INC); 174 } 175 176 static void match_atomic_sub(const char *fn, struct expression *expr, void *_unused) 177 { 178 db_inc_dec(expr, 1, "$->counter", "", ATOMIC_DEC); 179 } 180 181 static void refcount_inc(const char *fn, struct expression *expr, void *param) 182 { 183 db_inc_dec(expr, PTR_INT(param), "$->ref.counter", "", ATOMIC_INC); 184 } 185 186 static void refcount_dec(const char *fn, struct expression *expr, void *param) 187 { 188 db_inc_dec(expr, PTR_INT(param), "$->ref.counter", "", ATOMIC_DEC); 189 } 190 191 static void match_return_info(int return_id, char *return_ranges, struct expression *expr) 192 { 193 struct sm_state *sm; 194 const char *param_name; 195 int param; 196 197 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 198 if (sm->state != &inc && 199 sm->state != &dec) 200 continue; 201 if (parent_is_gone_var_sym(sm->name, sm->sym)) 202 continue; 203 param = get_param_num_from_sym(sm->sym); 204 if (param < 0) 205 continue; 206 param_name = get_param_name(sm); 207 if (!param_name) 208 continue; 209 sql_insert_return_states(return_id, return_ranges, 210 (sm->state == &inc) ? ATOMIC_INC : ATOMIC_DEC, 211 param, param_name, ""); 212 } END_FOR_EACH_SM(sm); 213 } 214 215 enum { 216 EMPTY, NEGATIVE, ZERO, POSITIVE, NUM_BUCKETS 217 }; 218 219 static int success_fail_positive(struct range_list *rl) 220 { 221 if (!rl) 222 return EMPTY; 223 224 if (sval_is_negative(rl_min(rl))) 225 return NEGATIVE; 226 227 if (rl_min(rl).value == 0) 228 return ZERO; 229 230 return POSITIVE; 231 } 232 233 static void check_counter(const char *name, struct symbol *sym) 234 { 235 struct range_list *inc_lines = NULL; 236 struct range_list *dec_lines = NULL; 237 int inc_buckets[NUM_BUCKETS] = {}; 238 int dec_buckets[NUM_BUCKETS] = {}; 239 struct stree *stree, *orig_stree; 240 struct sm_state *return_sm; 241 struct sm_state *sm; 242 sval_t line = sval_type_val(&int_ctype, 0); 243 int bucket; 244 245 FOR_EACH_PTR(get_all_return_strees(), stree) { 246 orig_stree = __swap_cur_stree(stree); 247 248 return_sm = get_sm_state(RETURN_ID, "return_ranges", NULL); 249 if (!return_sm) 250 goto swap_stree; 251 line.value = return_sm->line; 252 253 if (get_state_stree(start_states, my_id, name, sym) == &inc) 254 goto swap_stree; 255 256 if (parent_is_gone_var_sym(name, sym)) 257 goto swap_stree; 258 259 sm = get_sm_state(my_id, name, sym); 260 if (!sm) 261 goto swap_stree; 262 263 if (sm->state != &inc && 264 sm->state != &dec && 265 sm->state != &orig) 266 goto swap_stree; 267 268 bucket = success_fail_positive(estate_rl(return_sm->state)); 269 270 if (sm->state == &inc) { 271 add_range(&inc_lines, line, line); 272 inc_buckets[bucket] = true; 273 } 274 if (sm->state == &dec || sm->state == &orig) { 275 add_range(&dec_lines, line, line); 276 dec_buckets[bucket] = true; 277 } 278 swap_stree: 279 __swap_cur_stree(orig_stree); 280 } END_FOR_EACH_PTR(stree); 281 282 if (inc_buckets[NEGATIVE] && 283 inc_buckets[ZERO]) { 284 // sm_warning("XXX '%s' not decremented on lines: %s.", name, show_rl(inc_lines)); 285 } 286 287 } 288 289 static void match_check_missed(struct symbol *sym) 290 { 291 struct sm_state *sm; 292 293 FOR_EACH_MY_SM(my_id, get_all_return_states(), sm) { 294 check_counter(sm->name, sm->sym); 295 } END_FOR_EACH_SM(sm); 296 } 297 298 int on_atomic_dec_path(void) 299 { 300 struct sm_state *sm; 301 302 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 303 if (sm->state == &dec) 304 return 1; 305 } END_FOR_EACH_SM(sm); 306 307 return 0; 308 } 309 310 int was_inced(const char *name, struct symbol *sym) 311 { 312 return get_state(my_id, name, sym) == &inc; 313 } 314 315 static void match_save_states(struct expression *expr) 316 { 317 push_stree(&saved_stack, start_states); 318 start_states = NULL; 319 } 320 321 static void match_restore_states(struct expression *expr) 322 { 323 start_states = pop_stree(&saved_stack); 324 } 325 326 static void match_after_func(struct symbol *sym) 327 { 328 free_stree(&start_states); 329 } 330 331 void check_atomic_inc_dec(int id) 332 { 333 my_id = id; 334 335 if (option_project != PROJ_KERNEL) 336 return; 337 338 add_unmatched_state_hook(my_id, &unmatched_state); 339 340 add_split_return_callback(match_return_info); 341 select_return_states_hook(ATOMIC_INC, &db_inc); 342 select_return_states_hook(ATOMIC_DEC, &db_dec); 343 344 add_function_hook("atomic_inc_return", &match_atomic_inc, NULL); 345 add_function_hook("atomic_add_return", &match_atomic_add, NULL); 346 add_function_hook("atomic_sub_return", &match_atomic_sub, NULL); 347 add_function_hook("atomic_sub_and_test", &match_atomic_sub, NULL); 348 add_function_hook("atomic_dec_and_test", &match_atomic_dec, NULL); 349 add_function_hook("_atomic_dec_and_lock", &match_atomic_dec, NULL); 350 add_function_hook("atomic_dec", &match_atomic_dec, NULL); 351 add_function_hook("atomic_long_inc", &match_atomic_inc, NULL); 352 add_function_hook("atomic_long_dec", &match_atomic_dec, NULL); 353 add_function_hook("atomic_inc", &match_atomic_inc, NULL); 354 add_function_hook("atomic_sub", &match_atomic_sub, NULL); 355 356 add_function_hook("refcount_inc", &refcount_inc, INT_PTR(0)); 357 add_function_hook("refcount_dec", &refcount_dec, INT_PTR(0)); 358 add_function_hook("refcount_add", &refcount_inc, INT_PTR(1)); 359 add_function_hook("refcount_add_not_zero", &refcount_inc, INT_PTR(1)); 360 add_function_hook("refcount_inc_not_zero", &refcount_inc, INT_PTR(0)); 361 add_function_hook("refcount_sub_and_test", &refcount_dec, INT_PTR(1)); 362 add_function_hook("refcount_dec_and_test", &refcount_dec, INT_PTR(0)); 363 364 add_hook(&match_check_missed, END_FUNC_HOOK); 365 366 add_hook(&match_after_func, AFTER_FUNC_HOOK); 367 add_hook(&match_save_states, INLINE_FN_START); 368 add_hook(&match_restore_states, INLINE_FN_END); 369 }