1 /*
2  * Copyright (C) 2017 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 "smatch.h"
19 #include "smatch_extra.h"
20 
21 static int my_id;
22 
23 struct allocator {
24 	const char *func;
25 	int param;
26 	int param2;
27 };
28 
29 static struct allocator generic_allocator_table[] = {
30 	{"malloc", 0},
31 	{"memdup", 1},
32 	{"realloc", 1},
33 };
34 
35 static struct allocator kernel_allocator_table[] = {
36 	{"kmalloc", 0},
37 	{"kzalloc", 0},
38 	{"vmalloc", 0},
39 	{"__vmalloc", 0},
40 	{"vzalloc", 0},
41 	{"sock_kmalloc", 1},
42 	{"kmemdup", 1},
43 	{"kmemdup_user", 1},
44 	{"dma_alloc_attrs", 1},
45 	{"pci_alloc_consistent", 1},
46 	{"pci_alloc_coherent", 1},
47 	{"devm_kmalloc", 1},
48 	{"devm_kzalloc", 1},
49 	{"krealloc", 1},
50 };
51 
52 static struct allocator calloc_table[] = {
53 	{"calloc", 0, 1},
54 	{"kcalloc", 0, 1},
55 	{"kmalloc_array", 0, 1},
56 	{"devm_kcalloc", 1, 2},
57 };
58 
bytes_per_element(struct expression * expr)59 static int bytes_per_element(struct expression *expr)
60 {
61 	struct symbol *type;
62 
63 	type = get_type(expr);
64 	if (!type)
65 		return 0;
66 
67 	if (type->type != SYM_PTR && type->type != SYM_ARRAY)
68 		return 0;
69 
70 	type = get_base_type(type);
71 	return type_bytes(type);
72 }
73 
save_constraint_required(struct expression * pointer,int op,struct expression * constraint)74 static void save_constraint_required(struct expression *pointer, int op, struct expression *constraint)
75 {
76 	char *data, *limit;
77 
78 	data = get_constraint_str(pointer);
79 	if (!data)
80 		return;
81 
82 	limit = get_constraint_str(constraint);
83 	if (!limit) {
84 		// FIXME deal with <= also
85 		if (op == '<')
86 			set_state_expr(my_id, constraint, alloc_state_expr(pointer));
87 		goto free_data;
88 	}
89 
90 	sql_save_constraint_required(data, op, limit);
91 
92 	free_string(limit);
93 free_data:
94 	free_string(data);
95 }
96 
handle_zero_size_arrays(struct expression * pointer,struct expression * size)97 static int handle_zero_size_arrays(struct expression *pointer, struct expression *size)
98 {
99 	struct expression *left, *right;
100 	struct symbol *type, *array, *array_type;
101 	sval_t struct_size;
102 	char *limit;
103 	char data[128];
104 
105 	if (size->type != EXPR_BINOP || size->op != '+')
106 		return 0;
107 
108 	type = get_type(pointer);
109 	if (!type || type->type != SYM_PTR)
110 		return 0;
111 	type = get_real_base_type(type);
112 	if (!type || !type->ident || type->type != SYM_STRUCT)
113 		return 0;
114 	if (!last_member_is_resizable(type))
115 		return 0;
116 	array = last_ptr_list((struct ptr_list *)type->symbol_list);
117 	if (!array || !array->ident)
118 		return 0;
119 	array_type = get_real_base_type(array);
120 	if (!array_type || array_type->type != SYM_ARRAY)
121 		return 0;
122 	array_type = get_real_base_type(array_type);
123 
124 	left = strip_expr(size->left);
125 	right = strip_expr(size->right);
126 
127 	if (!get_implied_value(left, &struct_size))
128 		return 0;
129 	if (struct_size.value != type_bytes(type))
130 		return 0;
131 
132 	if (right->type == EXPR_BINOP && right->op == '*') {
133 		struct expression *mult_left, *mult_right;
134 		sval_t sval;
135 
136 		mult_left = strip_expr(right->left);
137 		mult_right = strip_expr(right->right);
138 
139 		if (get_implied_value(mult_left, &sval) &&
140 		    sval.value == type_bytes(array_type))
141 			size = mult_right;
142 		else if (get_implied_value(mult_right, &sval) &&
143 		    sval.value == type_bytes(array_type))
144 			size = mult_left;
145 		else
146 			return 0;
147 	}
148 
149 	snprintf(data, sizeof(data), "(struct %s)->%s", type->ident->name, array->ident->name);
150 	limit = get_constraint_str(size);
151 	if (!limit) {
152 		set_state_expr(my_id, size, alloc_state_expr(
153 			       member_expression(deref_expression(pointer), '*', array->ident)));
154 		return 1;
155 	}
156 
157 	sql_save_constraint_required(data, '<', limit);
158 
159 	free_string(limit);
160 	return 1;
161 }
162 
match_alloc_helper(struct expression * pointer,struct expression * size,int recurse)163 static void match_alloc_helper(struct expression *pointer, struct expression *size, int recurse)
164 {
165 	struct expression *size_orig, *tmp;
166 	sval_t sval;
167 	int cnt = 0;
168 
169 	pointer = strip_expr(pointer);
170 	size = strip_expr(size);
171 	if (!size || !pointer)
172 		return;
173 
174 	size_orig = size;
175 	if (recurse) {
176 		while ((tmp = get_assigned_expr(size))) {
177 			size = strip_expr(tmp);
178 			if (cnt++ > 5)
179 				break;
180 		}
181 		if (size != size_orig) {
182 			match_alloc_helper(pointer, size, 0);
183 			size = size_orig;
184 		}
185 	}
186 
187 	if (handle_zero_size_arrays(pointer, size))
188 		return;
189 
190 	if (size->type == EXPR_BINOP && size->op == '*') {
191 		struct expression *mult_left, *mult_right;
192 
193 		mult_left = strip_expr(size->left);
194 		mult_right = strip_expr(size->right);
195 
196 		if (get_implied_value(mult_left, &sval) &&
197 		    sval.value == bytes_per_element(pointer))
198 			size = mult_right;
199 		else if (get_implied_value(mult_right, &sval) &&
200 		    sval.value == bytes_per_element(pointer))
201 			size = mult_left;
202 		else
203 			return;
204 	}
205 
206 	if (size->type == EXPR_BINOP && size->op == '+' &&
207 	    get_implied_value(size->right, &sval) &&
208 	    sval.value == 1)
209 		save_constraint_required(pointer, SPECIAL_LTE, size->left);
210 	else
211 		save_constraint_required(pointer, '<', size);
212 }
213 
match_alloc(const char * fn,struct expression * expr,void * _size_arg)214 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
215 {
216 	int size_arg = PTR_INT(_size_arg);
217 	struct expression *call, *arg;
218 
219 	call = strip_expr(expr->right);
220 	arg = get_argument_from_call_expr(call->args, size_arg);
221 
222 	match_alloc_helper(expr->left, arg, 1);
223 }
224 
match_calloc(const char * fn,struct expression * expr,void * _start_arg)225 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
226 {
227 	struct expression *pointer, *call, *size;
228 	struct expression *count = NULL;
229 	int start_arg = PTR_INT(_start_arg);
230 	sval_t sval;
231 
232 	pointer = strip_expr(expr->left);
233 	call = strip_expr(expr->right);
234 
235 	size = get_argument_from_call_expr(call->args, start_arg);
236 	if (get_implied_value(size, &sval) &&
237 	    sval.value == bytes_per_element(pointer))
238 		count = get_argument_from_call_expr(call->args, start_arg + 1);
239 	else {
240 		size = get_argument_from_call_expr(call->args, start_arg + 1);
241 		if (get_implied_value(size, &sval) &&
242 		    sval.value == bytes_per_element(pointer))
243 			count = get_argument_from_call_expr(call->args, start_arg);
244 	}
245 
246 	if (!count)
247 		return;
248 
249 	save_constraint_required(pointer, '<', count);
250 }
251 
add_allocation_function(const char * func,void * call_back,int param)252 static void add_allocation_function(const char *func, void *call_back, int param)
253 {
254 	add_function_assign_hook(func, call_back, INT_PTR(param));
255 }
256 
match_assign_size(struct expression * expr)257 static void match_assign_size(struct expression *expr)
258 {
259 	struct smatch_state *state;
260 	char *data, *limit;
261 
262 	state = get_state_expr(my_id, expr->right);
263 	if (!state || !state->data)
264 		return;
265 
266 	data = get_constraint_str(state->data);
267 	if (!data)
268 		return;
269 
270 	limit = get_constraint_str(expr->left);
271 	if (!limit)
272 		goto free_data;
273 
274 	sql_save_constraint_required(data, '<', limit);
275 
276 	free_string(limit);
277 free_data:
278 	free_string(data);
279 }
280 
match_assign_has_buf_comparison(struct expression * expr)281 static void match_assign_has_buf_comparison(struct expression *expr)
282 {
283 	struct expression *size;
284 	int limit_type;
285 
286 	if (expr->op != '=')
287 		return;
288 	if (expr->right->type == EXPR_CALL)
289 		return;
290 	size = get_size_variable(expr->right, &limit_type);
291 	if (!size)
292 		return;
293 	if (limit_type != ELEM_COUNT)
294 		return;
295 	match_alloc_helper(expr->left, size, 1);
296 }
297 
match_assign_data(struct expression * expr)298 static void match_assign_data(struct expression *expr)
299 {
300 	struct expression *right, *arg, *tmp;
301 	int i;
302 	int size_arg;
303 	int size_arg2 = -1;
304 
305 	if (expr->op != '=')
306 		return;
307 
308 	/* Direct calls are handled else where (for now at least) */
309 	tmp = get_assigned_expr(expr->right);
310 	if (!tmp)
311 		return;
312 
313 	right = strip_expr(tmp);
314 	if (right->type != EXPR_CALL)
315 		return;
316 
317 	if (right->fn->type != EXPR_SYMBOL ||
318 	    !right->fn->symbol ||
319 	    !right->fn->symbol->ident)
320 		return;
321 
322 	for (i = 0; i < ARRAY_SIZE(generic_allocator_table); i++) {
323 		if (strcmp(right->fn->symbol->ident->name,
324 			   generic_allocator_table[i].func) == 0) {
325 			size_arg = generic_allocator_table[i].param;
326 			goto found;
327 		}
328 	}
329 
330 	if (option_project != PROJ_KERNEL)
331 		return;
332 
333 	for (i = 0; i < ARRAY_SIZE(kernel_allocator_table); i++) {
334 		if (strcmp(right->fn->symbol->ident->name,
335 			   kernel_allocator_table[i].func) == 0) {
336 			size_arg = kernel_allocator_table[i].param;
337 			goto found;
338 		}
339 	}
340 
341 	for (i = 0; i < ARRAY_SIZE(calloc_table); i++) {
342 		if (strcmp(right->fn->symbol->ident->name,
343 			   calloc_table[i].func) == 0) {
344 			size_arg = calloc_table[i].param;
345 			size_arg2 = calloc_table[i].param2;
346 			goto found;
347 		}
348 	}
349 
350 	return;
351 
352 found:
353 	arg = get_argument_from_call_expr(right->args, size_arg);
354 	match_alloc_helper(expr->left, arg, 1);
355 	if (size_arg2 == -1)
356 		return;
357 	arg = get_argument_from_call_expr(right->args, size_arg2);
358 	match_alloc_helper(expr->left, arg, 1);
359 }
360 
match_assign_ARRAY_SIZE(struct expression * expr)361 static void match_assign_ARRAY_SIZE(struct expression *expr)
362 {
363 	struct expression *array;
364 	char *data, *limit;
365 	const char *macro;
366 
367 	macro = get_macro_name(expr->right->pos);
368 	if (!macro || strcmp(macro, "ARRAY_SIZE") != 0)
369 		return;
370 	array = strip_expr(expr->right);
371 	if (array->type != EXPR_BINOP || array->op != '+')
372 		return;
373 	array = strip_expr(array->left);
374 	if (array->type != EXPR_BINOP || array->op != '/')
375 		return;
376 	array = strip_expr(array->left);
377 	if (array->type != EXPR_SIZEOF)
378 		return;
379 	array = strip_expr(array->cast_expression);
380 	if (array->type != EXPR_PREOP || array->op != '*')
381 		return;
382 	array = strip_expr(array->unop);
383 
384 	data = get_constraint_str(array);
385 	limit = get_constraint_str(expr->left);
386 	if (!data || !limit)
387 		goto free;
388 
389 	sql_save_constraint_required(data, '<', limit);
390 
391 free:
392 	free_string(data);
393 	free_string(limit);
394 }
395 
match_assign_buf_comparison(struct expression * expr)396 static void match_assign_buf_comparison(struct expression *expr)
397 {
398 	struct expression *pointer;
399 
400 	if (expr->op != '=')
401 		return;
402 	pointer = get_array_variable(expr->right);
403 	if (!pointer)
404 		return;
405 
406 	match_alloc_helper(pointer, expr->right, 1);
407 }
408 
constraint_found(void * _found,int argc,char ** argv,char ** azColName)409 static int constraint_found(void *_found, int argc, char **argv, char **azColName)
410 {
411 	int *found = _found;
412 
413 	*found = 1;
414 	return 0;
415 }
416 
has_constraint(struct expression * expr,const char * constraint)417 static int has_constraint(struct expression *expr, const char *constraint)
418 {
419 	int found = 0;
420 
421 	if (get_state_expr(my_id, expr))
422 		return 1;
423 
424 	run_sql(constraint_found, &found,
425 		"select data from constraints_required where bound = '%q' limit 1",
426 		escape_newlines(constraint));
427 
428 	return found;
429 }
430 
match_assign_constraint(struct expression * expr)431 static void match_assign_constraint(struct expression *expr)
432 {
433 	struct symbol *type;
434 	char *left, *right;
435 
436 	if (expr->op != '=')
437 		return;
438 
439 	type = get_type(expr->left);
440 	if (!type || type->type != SYM_BASETYPE)
441 		return;
442 
443 	left = get_constraint_str(expr->left);
444 	if (!left)
445 		return;
446 	right = get_constraint_str(expr->right);
447 	if (!right)
448 		goto free;
449 	if (!has_constraint(expr->right, right))
450 		return;
451 	sql_copy_constraint_required(left, right);
452 free:
453 	free_string(right);
454 	free_string(left);
455 }
456 
register_constraints_required(int id)457 void register_constraints_required(int id)
458 {
459 	my_id = id;
460 
461 	set_dynamic_states(my_id);
462 	add_hook(&match_assign_size, ASSIGNMENT_HOOK);
463 	add_hook(&match_assign_data, ASSIGNMENT_HOOK);
464 	add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK);
465 
466 	add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK);
467 	add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK);
468 	add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK);
469 	add_hook(&match_assign_constraint, ASSIGNMENT_HOOK);
470 
471 	add_allocation_function("malloc", &match_alloc, 0);
472 	add_allocation_function("memdup", &match_alloc, 1);
473 	add_allocation_function("realloc", &match_alloc, 1);
474 	add_allocation_function("realloc", &match_calloc, 0);
475 	if (option_project == PROJ_KERNEL) {
476 		add_allocation_function("kmalloc", &match_alloc, 0);
477 		add_allocation_function("kzalloc", &match_alloc, 0);
478 		add_allocation_function("vmalloc", &match_alloc, 0);
479 		add_allocation_function("__vmalloc", &match_alloc, 0);
480 		add_allocation_function("vzalloc", &match_alloc, 0);
481 		add_allocation_function("sock_kmalloc", &match_alloc, 1);
482 		add_allocation_function("kmemdup", &match_alloc, 1);
483 		add_allocation_function("kmemdup_user", &match_alloc, 1);
484 		add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
485 		add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
486 		add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
487 		add_allocation_function("devm_kmalloc", &match_alloc, 1);
488 		add_allocation_function("devm_kzalloc", &match_alloc, 1);
489 		add_allocation_function("kcalloc", &match_calloc, 0);
490 		add_allocation_function("kmalloc_array", &match_calloc, 0);
491 		add_allocation_function("devm_kcalloc", &match_calloc, 1);
492 		add_allocation_function("krealloc", &match_alloc, 1);
493 	}
494 }
495