xref: /illumos-gate/usr/src/tools/smatch/src/check_atomic_inc_dec.c (revision b3263c9871d056ea54cca24eaeedd5a41fd333de)
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 
unmatched_state(struct sm_state * sm)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;
set_start_state(const char * name,struct symbol * sym,struct smatch_state * start)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 
get_best_match(const char * key)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 
db_inc_dec(struct expression * expr,int param,const char * key,int inc_dec)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 
is_inc_dec_primitive(struct expression * expr)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 
db_inc(struct expression * expr,int param,char * key,char * value)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 
db_dec(struct expression * expr,int param,char * key,char * value)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 
match_atomic_inc(const char * fn,struct expression * expr,void * _unused)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 
match_atomic_dec(const char * fn,struct expression * expr,void * _unused)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 
match_atomic_add(const char * fn,struct expression * expr,void * _unused)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 
match_atomic_sub(const char * fn,struct expression * expr,void * _unused)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 
refcount_inc(const char * fn,struct expression * expr,void * param)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 
refcount_dec(const char * fn,struct expression * expr,void * param)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 
pm_runtime_get_sync(const char * fn,struct expression * expr,void * param)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 
match_implies_inc(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * param)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 
match_implies_atomic_dec(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * param)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 
is_maybe_dec(struct sm_state * sm)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 
match_return_info(int return_id,char * return_ranges,struct expression * expr)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 
success_fail_positive(struct range_list * rl)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 
check_counter(const char * name,struct symbol * sym)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 
match_check_missed(struct symbol * sym)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 
on_atomic_dec_path(void)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 
was_inced(const char * name,struct symbol * sym)406 int was_inced(const char *name, struct symbol *sym)
407 {
408 	return get_state(my_id, name, sym) == &inc;
409 }
410 
match_save_states(struct expression * expr)411 static void match_save_states(struct expression *expr)
412 {
413 	push_stree(&saved_stack, start_states);
414 	start_states = NULL;
415 }
416 
match_restore_states(struct expression * expr)417 static void match_restore_states(struct expression *expr)
418 {
419 	start_states = pop_stree(&saved_stack);
420 }
421 
match_after_func(struct symbol * sym)422 static void match_after_func(struct symbol *sym)
423 {
424 	free_stree(&start_states);
425 }
426 
check_atomic_inc_dec(int id)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 }
477