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