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 }