1 /*
2  * Copyright (C) 2010 Dan Carpenter.
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 /*
19  * This is kernel specific stuff for smatch_extra.
20  */
21 
22 #include "scope.h"
23 #include "smatch.h"
24 #include "smatch_extra.h"
25 
26 static sval_t err_ptr_min;
27 static sval_t err_ptr_max;
28 static sval_t null_ptr;
29 
implied_err_cast_return(struct expression * call,void * unused,struct range_list ** rl)30 static int implied_err_cast_return(struct expression *call, void *unused, struct range_list **rl)
31 {
32 	struct expression *arg;
33 
34 	arg = get_argument_from_call_expr(call->args, 0);
35 	if (!get_implied_rl(arg, rl))
36 		*rl = alloc_rl(err_ptr_min, err_ptr_max);
37 
38 	*rl = cast_rl(get_type(call), *rl);
39 	return 1;
40 }
41 
hack_ERR_PTR(struct symbol * sym)42 static void hack_ERR_PTR(struct symbol *sym)
43 {
44 	struct symbol *arg;
45 	struct smatch_state *estate;
46 	struct range_list *after;
47 	sval_t low_error;
48 	sval_t minus_one;
49 	sval_t zero;
50 
51 	low_error.type = &long_ctype;
52 	low_error.value = -4095;
53 
54 	minus_one.type = &long_ctype;
55 	minus_one.value = -1;
56 
57 	zero.type = &long_ctype;
58 	zero.value = 0;
59 
60 	if (!sym || !sym->ident)
61 		return;
62 	if (strcmp(sym->ident->name, "ERR_PTR") != 0)
63 		return;
64 
65 	arg = first_ptr_list((struct ptr_list *)sym->ctype.base_type->arguments);
66 	if (!arg || !arg->ident)
67 		return;
68 
69 	estate = get_state(SMATCH_EXTRA, arg->ident->name, arg);
70 	if (!estate) {
71 		after = alloc_rl(low_error, minus_one);
72 	} else {
73 		after = rl_intersection(estate_rl(estate), alloc_rl(low_error, zero));
74 		if (rl_equiv(estate_rl(estate), after))
75 			return;
76 	}
77 	set_state(SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_rl(after));
78 }
79 
match_param_valid_ptr(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * _param)80 static void match_param_valid_ptr(const char *fn, struct expression *call_expr,
81 			struct expression *assign_expr, void *_param)
82 {
83 	int param = PTR_INT(_param);
84 	struct expression *arg;
85 	struct smatch_state *pre_state;
86 	struct smatch_state *end_state;
87 	struct range_list *rl;
88 
89 	arg = get_argument_from_call_expr(call_expr->args, param);
90 	pre_state = get_state_expr(SMATCH_EXTRA, arg);
91 	if (estate_rl(pre_state)) {
92 		rl = estate_rl(pre_state);
93 		rl = remove_range(rl, null_ptr, null_ptr);
94 		rl = remove_range(rl, err_ptr_min, err_ptr_max);
95 	} else {
96 		rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
97 	}
98 	end_state = alloc_estate_rl(rl);
99 	set_extra_expr_nomod(arg, end_state);
100 }
101 
match_param_err_or_null(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * _param)102 static void match_param_err_or_null(const char *fn, struct expression *call_expr,
103 			struct expression *assign_expr, void *_param)
104 {
105 	int param = PTR_INT(_param);
106 	struct expression *arg;
107 	struct range_list *pre, *rl;
108 	struct smatch_state *pre_state;
109 	struct smatch_state *end_state;
110 
111 	arg = get_argument_from_call_expr(call_expr->args, param);
112 	pre_state = get_state_expr(SMATCH_EXTRA, arg);
113 	if (pre_state)
114 		pre = estate_rl(pre_state);
115 	else
116 		pre = alloc_whole_rl(&ptr_ctype);
117 	call_results_to_rl(call_expr, &ptr_ctype, "0,(-4095)-(-1)", &rl);
118 	rl = rl_intersection(pre, rl);
119 	rl = cast_rl(get_type(arg), rl);
120 	end_state = alloc_estate_rl(rl);
121 	set_extra_expr_nomod(arg, end_state);
122 }
123 
match_not_err(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * unused)124 static void match_not_err(const char *fn, struct expression *call_expr,
125 			struct expression *assign_expr, void *unused)
126 {
127 	struct expression *arg;
128 	struct smatch_state *pre_state;
129 	struct range_list *rl;
130 
131 	arg = get_argument_from_call_expr(call_expr->args, 0);
132 	pre_state = get_state_expr(SMATCH_EXTRA, arg);
133 	if (pre_state)
134 		return;
135 	rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
136 	rl = cast_rl(get_type(arg), rl);
137 	set_extra_expr_nomod(arg, alloc_estate_rl(rl));
138 }
139 
match_err(const char * fn,struct expression * call_expr,struct expression * assign_expr,void * unused)140 static void match_err(const char *fn, struct expression *call_expr,
141 			struct expression *assign_expr, void *unused)
142 {
143 	struct expression *arg;
144 	struct smatch_state *pre_state;
145 	struct range_list *rl;
146 
147 	arg = get_argument_from_call_expr(call_expr->args, 0);
148 	pre_state = get_state_expr(SMATCH_EXTRA, arg);
149 	rl = estate_rl(pre_state);
150 	if (!rl)
151 		rl = alloc_rl(err_ptr_min, err_ptr_max);
152 	rl = rl_intersection(rl, alloc_rl(err_ptr_min, err_ptr_max));
153 	rl = cast_rl(get_type(arg), rl);
154 	if (pre_state && rl) {
155 		/*
156 		 * Ideally this would all be handled by smatch_implied.c
157 		 * but it doesn't work very well for impossible paths.
158 		 *
159 		 */
160 		return;
161 	}
162 	set_extra_expr_nomod(arg, alloc_estate_rl(rl));
163 }
164 
match_container_of_macro(const char * fn,struct expression * expr,void * unused)165 static void match_container_of_macro(const char *fn, struct expression *expr, void *unused)
166 {
167 	set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
168 }
169 
match_container_of(struct expression * expr)170 static void match_container_of(struct expression *expr)
171 {
172 	struct expression *right = expr->right;
173 	char *macro;
174 
175 	/*
176 	 * The problem here is that sometimes the container_of() macro is itself
177 	 * inside a macro and get_macro() only returns the name of the outside
178 	 * macro.
179 	 */
180 
181 	/*
182 	 * This actually an expression statement assignment but smatch_flow
183 	 * pre-mangles it for us so we only get the last chunk:
184 	 * sk = (typeof(sk))((char *)__mptr - offsetof(...))
185 	 */
186 
187 	macro = get_macro_name(right->pos);
188 	if (!macro)
189 		return;
190 	if (right->type != EXPR_CAST)
191 		return;
192 	right = strip_expr(right);
193 	if (right->type != EXPR_BINOP || right->op != '-' ||
194 	    right->left->type != EXPR_CAST)
195 		return;
196 	right = strip_expr(right->left);
197 	if (right->type != EXPR_SYMBOL)
198 		return;
199 	if (!right->symbol->ident ||
200 	    strcmp(right->symbol->ident->name, "__mptr") != 0)
201 		return;
202 	set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
203 }
204 
match_next_bit(struct expression * call,void * unused,struct range_list ** rl)205 static int match_next_bit(struct expression *call, void *unused, struct range_list **rl)
206 {
207 	struct expression *start_arg;
208 	struct expression *size_arg;
209 	struct symbol *type;
210 	sval_t min, max, tmp;
211 
212 	size_arg = get_argument_from_call_expr(call->args, 1);
213 	/* btw. there isn't a start_arg for find_first_bit() */
214 	start_arg = get_argument_from_call_expr(call->args, 2);
215 
216 	type = get_type(call);
217 	min = sval_type_val(type, 0);
218 	max = sval_type_val(type, sizeof(long long) * 8);
219 
220 	if (get_implied_max(size_arg, &tmp) && tmp.uvalue < max.value)
221 		max = tmp;
222 	if (start_arg && get_implied_min(start_arg, &tmp) && !sval_is_negative(tmp))
223 		min = tmp;
224 	if (sval_cmp(min, max) > 0)
225 		max = min;
226 	min = sval_cast(type, min);
227 	max = sval_cast(type, max);
228 	*rl = alloc_rl(min, max);
229 	return 1;
230 }
231 
match_fls(struct expression * call,void * unused,struct range_list ** rl)232 static int match_fls(struct expression *call, void *unused, struct range_list **rl)
233 {
234 	struct expression *arg;
235 	struct range_list *arg_rl;
236 	sval_t zero = {};
237 	sval_t start, end, sval;
238 
239 	start.type = &int_ctype;
240 	start.value = 0;
241 	end.type = &int_ctype;
242 	end.value = 32;
243 
244 	arg = get_argument_from_call_expr(call->args, 0);
245 	if (!get_implied_rl(arg, &arg_rl))
246 		return 0;
247 	if (rl_to_sval(arg_rl, &sval)) {
248 		int i;
249 
250 		for (i = 63; i >= 0; i--) {
251 			if (sval.uvalue & 1ULL << i)
252 				break;
253 		}
254 		sval.value = i + 1;
255 		*rl = alloc_rl(sval, sval);
256 		return 1;
257 	}
258 	zero.type = rl_type(arg_rl);
259 	if (!rl_has_sval(arg_rl, zero))
260 		start.value = 1;
261 	*rl = alloc_rl(start, end);
262 	return 1;
263 }
264 
find_module_init_exit(struct symbol_list * sym_list)265 static void find_module_init_exit(struct symbol_list *sym_list)
266 {
267 	struct symbol *sym;
268 	struct symbol *fn;
269 	struct statement *stmt;
270 	char *name;
271 	int init;
272 	int count;
273 
274 	/*
275 	 * This is more complicated because Sparse ignores the "alias"
276 	 * attribute.  I search backwards because module_init() is normally at
277 	 * the end of the file.
278 	 */
279 	count = 0;
280 	FOR_EACH_PTR_REVERSE(sym_list, sym) {
281 		if (sym->type != SYM_NODE)
282 			continue;
283 		if (!(sym->ctype.modifiers & MOD_STATIC))
284 			continue;
285 		fn = get_base_type(sym);
286 		if (!fn)
287 			continue;
288 		if (fn->type != SYM_FN)
289 			continue;
290 		if (!sym->ident)
291 			continue;
292 		if (!fn->inline_stmt)
293 			continue;
294 		if (strcmp(sym->ident->name, "__inittest") == 0)
295 			init = 1;
296 		else if (strcmp(sym->ident->name, "__exittest") == 0)
297 			init = 0;
298 		else
299 			continue;
300 
301 		count++;
302 
303 		stmt = first_ptr_list((struct ptr_list *)fn->inline_stmt->stmts);
304 		if (!stmt || stmt->type != STMT_RETURN)
305 			continue;
306 		name = expr_to_var(stmt->ret_value);
307 		if (!name)
308 			continue;
309 		if (init)
310 			sql_insert_function_ptr(name, "(struct module)->init");
311 		else
312 			sql_insert_function_ptr(name, "(struct module)->exit");
313 		free_string(name);
314 		if (count >= 2)
315 			return;
316 	} END_FOR_EACH_PTR_REVERSE(sym);
317 }
318 
match_end_file(struct symbol_list * sym_list)319 static void match_end_file(struct symbol_list *sym_list)
320 {
321 	struct symbol *sym;
322 
323 	/* find the last static symbol in the file */
324 	FOR_EACH_PTR_REVERSE(sym_list, sym) {
325 		if (!(sym->ctype.modifiers & MOD_STATIC))
326 			continue;
327 		if (!sym->scope)
328 			continue;
329 		find_module_init_exit(sym->scope->symbols);
330 		return;
331 	} END_FOR_EACH_PTR_REVERSE(sym);
332 }
333 
get_val_expr(struct expression * expr)334 static struct expression *get_val_expr(struct expression *expr)
335 {
336 	struct symbol *sym, *val;
337 
338 	if (expr->type != EXPR_DEREF)
339 		return NULL;
340 	expr = expr->deref;
341 	if (expr->type != EXPR_SYMBOL)
342 		return NULL;
343 	if (strcmp(expr->symbol_name->name, "__u") != 0)
344 		return NULL;
345 	sym = get_base_type(expr->symbol);
346 	val = first_ptr_list((struct ptr_list *)sym->symbol_list);
347 	if (!val || strcmp(val->ident->name, "__val") != 0)
348 		return NULL;
349 	return member_expression(expr, '.', val->ident);
350 }
351 
match__write_once_size(const char * fn,struct expression * call,void * unused)352 static void match__write_once_size(const char *fn, struct expression *call,
353 			       void *unused)
354 {
355 	struct expression *dest, *data, *assign;
356 	struct range_list *rl;
357 
358 	dest = get_argument_from_call_expr(call->args, 0);
359 	if (dest->type != EXPR_PREOP || dest->op != '&')
360 		return;
361 	dest = strip_expr(dest->unop);
362 
363 	data = get_argument_from_call_expr(call->args, 1);
364 	data = get_val_expr(data);
365 	if (!data)
366 		return;
367 	get_absolute_rl(data, &rl);
368 	assign = assign_expression(dest, '=', data);
369 
370 	__in_fake_assign++;
371 	__split_expr(assign);
372 	__in_fake_assign--;
373 }
374 
match__read_once_size(const char * fn,struct expression * call,void * unused)375 static void match__read_once_size(const char *fn, struct expression *call,
376 			       void *unused)
377 {
378 	struct expression *dest, *data, *assign;
379 	struct symbol *type, *val_sym;
380 
381 	/*
382 	 * We want to change:
383 	 *	__read_once_size_nocheck(&(x), __u.__c, sizeof(x));
384 	 * into a fake assignment:
385 	 *	__u.val = x;
386 	 *
387 	 */
388 
389 	data = get_argument_from_call_expr(call->args, 0);
390 	if (data->type != EXPR_PREOP || data->op != '&')
391 		return;
392 	data = strip_parens(data->unop);
393 
394 	dest = get_argument_from_call_expr(call->args, 1);
395 	if (dest->type != EXPR_DEREF || dest->op != '.')
396 		return;
397 	if (!dest->member || strcmp(dest->member->name, "__c") != 0)
398 		return;
399 	dest = dest->deref;
400 	type = get_type(dest);
401 	if (!type)
402 		return;
403 	val_sym = first_ptr_list((struct ptr_list *)type->symbol_list);
404 	dest = member_expression(dest, '.', val_sym->ident);
405 
406 	assign = assign_expression(dest, '=', data);
407 	__in_fake_assign++;
408 	__split_expr(assign);
409 	__in_fake_assign--;
410 }
411 
match_closure_call(const char * name,struct expression * call,void * unused)412 static void match_closure_call(const char *name, struct expression *call,
413 			       void *unused)
414 {
415 	struct expression *cl, *fn, *fake_call;
416 	struct expression_list *args = NULL;
417 
418 	cl = get_argument_from_call_expr(call->args, 0);
419 	fn = get_argument_from_call_expr(call->args, 1);
420 	if (!fn || !cl)
421 		return;
422 
423 	add_ptr_list(&args, cl);
424 	fake_call = call_expression(fn, args);
425 	__split_expr(fake_call);
426 }
427 
is_ignored_kernel_data(const char * name)428 bool is_ignored_kernel_data(const char *name)
429 {
430 	if (option_project != PROJ_KERNEL)
431 		return false;
432 
433 	/*
434 	 * On the file I was looking at lockdep was 25% of the DB.
435 	 */
436 	if (strstr(name, ".dep_map."))
437 		return true;
438 	if (strstr(name, ".lockdep_map."))
439 		return true;
440 	return false;
441 }
442 
check_kernel(int id)443 void check_kernel(int id)
444 {
445 	if (option_project != PROJ_KERNEL)
446 		return;
447 
448 	err_ptr_min.type = &ptr_ctype;
449 	err_ptr_min.value = -4095;
450 	err_ptr_max.type = &ptr_ctype;
451 	err_ptr_max.value = -1l;
452 	null_ptr.type = &ptr_ctype;
453 	null_ptr.value = 0;
454 
455 	err_ptr_min = sval_cast(&ptr_ctype, err_ptr_min);
456 	err_ptr_max = sval_cast(&ptr_ctype, err_ptr_max);
457 
458 	add_implied_return_hook("ERR_PTR", &implied_err_cast_return, NULL);
459 	add_implied_return_hook("ERR_CAST", &implied_err_cast_return, NULL);
460 	add_implied_return_hook("PTR_ERR", &implied_err_cast_return, NULL);
461 	add_hook(hack_ERR_PTR, AFTER_DEF_HOOK);
462 	return_implies_state("IS_ERR_OR_NULL", 0, 0, &match_param_valid_ptr, (void *)0);
463 	return_implies_state("IS_ERR_OR_NULL", 1, 1, &match_param_err_or_null, (void *)0);
464 	return_implies_state("IS_ERR", 0, 0, &match_not_err, NULL);
465 	return_implies_state("IS_ERR", 1, 1, &match_err, NULL);
466 	return_implies_state("tomoyo_memory_ok", 1, 1, &match_param_valid_ptr, (void *)0);
467 
468 	add_macro_assign_hook_extra("container_of", &match_container_of_macro, NULL);
469 	add_hook(match_container_of, ASSIGNMENT_HOOK);
470 
471 	add_implied_return_hook("find_next_bit", &match_next_bit, NULL);
472 	add_implied_return_hook("find_next_zero_bit", &match_next_bit, NULL);
473 	add_implied_return_hook("find_first_bit", &match_next_bit, NULL);
474 	add_implied_return_hook("find_first_zero_bit", &match_next_bit, NULL);
475 
476 	add_implied_return_hook("fls", &match_fls, NULL);
477 	add_implied_return_hook("fls64", &match_fls, NULL);
478 
479 	add_function_hook("__ftrace_bad_type", &__match_nullify_path_hook, NULL);
480 	add_function_hook("__write_once_size", &match__write_once_size, NULL);
481 
482 	add_function_hook("__read_once_size", &match__read_once_size, NULL);
483 	add_function_hook("__read_once_size_nocheck", &match__read_once_size, NULL);
484 
485 	add_function_hook("closure_call", &match_closure_call, NULL);
486 
487 	if (option_info)
488 		add_hook(match_end_file, END_FILE_HOOK);
489 }
490