Print this page
new smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_parse_call_math.c
+++ new/usr/src/tools/smatch/src/smatch_parse_call_math.c
1 1 /*
2 2 * Copyright (C) 2012 Oracle.
3 3 *
4 4 * This program is free software; you can redistribute it and/or
5 5 * modify it under the terms of the GNU General Public License
6 6 * as published by the Free Software Foundation; either version 2
7 7 * of the License, or (at your option) any later version.
8 8 *
9 9 * This program is distributed in the hope that it will be useful,
10 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 12 * GNU General Public License for more details.
13 13 *
14 14 * You should have received a copy of the GNU General Public License
15 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 16 */
17 17
18 18 #include "smatch.h"
19 19 #include "smatch_slist.h"
20 20 #include "smatch_extra.h"
21 21
22 22 static int my_id;
23 23
24 24 struct {
25 25 const char *func;
26 26 int param;
27 27 } alloc_functions[] = {
28 28 {"kmalloc", 0},
29 29 {"kzalloc", 0},
30 30 {"__kmalloc", 0},
31 31 {"vmalloc", 0},
32 32 {"__vmalloc", 0},
33 33 {"__vmalloc_node", 0},
34 34 };
35 35
36 36 static struct range_list_stack *rl_stack;
37 37 static struct string_list *op_list;
38 38
39 39 static void push_op(char c)
40 40 {
41 41 char *p;
42 42
43 43 p = malloc(1);
44 44 p[0] = c;
45 45 add_ptr_list(&op_list, p);
46 46 }
47 47
48 48 static char pop_op(void)
49 49 {
50 50 char *p;
51 51 char c;
52 52
53 53 if (!op_list) {
54 54 sm_perror("%s: no op_list", __func__);
55 55 return '\0';
56 56 }
57 57
58 58 p = last_ptr_list((struct ptr_list *)op_list);
59 59
60 60 delete_ptr_list_last((struct ptr_list **)&op_list);
61 61 c = p[0];
62 62 free(p);
63 63
64 64 return c;
65 65 }
66 66
67 67 static int op_precedence(char c)
68 68 {
69 69 switch (c) {
70 70 case '+':
71 71 case '-':
72 72 return 1;
73 73 case '*':
74 74 case '/':
75 75 return 2;
76 76 default:
77 77 return 0;
78 78 }
79 79 }
80 80
81 81 static int top_op_precedence(void)
82 82 {
83 83 char *p;
84 84
85 85 if (!op_list)
86 86 return 0;
87 87
88 88 p = last_ptr_list((struct ptr_list *)op_list);
89 89 return op_precedence(p[0]);
90 90 }
91 91
92 92 static void rl_pop_until(char c)
93 93 {
94 94 char op;
95 95 struct range_list *left, *right;
96 96 struct range_list *res;
97 97
98 98 while (top_op_precedence() && op_precedence(c) <= top_op_precedence()) {
99 99 op = pop_op();
100 100 right = pop_rl(&rl_stack);
101 101 left = pop_rl(&rl_stack);
102 102 res = rl_binop(left, op, right);
103 103 if (!res)
104 104 res = alloc_whole_rl(&llong_ctype);
105 105 push_rl(&rl_stack, res);
106 106 }
107 107 }
108 108
109 109 static void rl_discard_stacks(void)
110 110 {
111 111 while (op_list)
112 112 pop_op();
113 113 while (rl_stack)
114 114 pop_rl(&rl_stack);
115 115 }
116 116
117 117 static int read_rl_from_var(struct expression *call, const char *p, const char **end, struct range_list **rl)
118 118 {
119 119 struct expression *arg;
120 120 struct smatch_state *state;
121 121 long param;
122 122 char *name;
123 123 struct symbol *sym;
124 124 char buf[256];
125 125 int star;
126 126
127 127 p++;
128 128 param = strtol(p, (char **)&p, 10);
129 129
130 130 arg = get_argument_from_call_expr(call->args, param);
131 131 if (!arg)
132 132 return 0;
133 133
134 134 if (*p != '-' && *p != '.') {
135 135 get_absolute_rl(arg, rl);
136 136 *end = p;
137 137 return 1;
138 138 }
139 139
140 140 *end = strchr(p, ' ');
141 141
142 142 if (arg->type == EXPR_PREOP && arg->op == '&') {
143 143 arg = strip_expr(arg->unop);
144 144 star = 0;
145 145 p++;
146 146 } else {
147 147 star = 1;
148 148 p += 2;
149 149 }
150 150
151 151 name = expr_to_var_sym(arg, &sym);
152 152 if (!name)
153 153 return 0;
154 154 snprintf(buf, sizeof(buf), "%s%s", name, star ? "->" : ".");
155 155 free_string(name);
156 156
157 157 if (*end - p + strlen(buf) >= sizeof(buf))
158 158 return 0;
159 159 strncat(buf, p, *end - p);
160 160
161 161 state = get_state(SMATCH_EXTRA, buf, sym);
162 162 if (!state)
163 163 return 0;
164 164 *rl = estate_rl(state);
165 165 return 1;
166 166 }
167 167
168 168 static int read_var_num(struct expression *call, const char *p, const char **end, struct range_list **rl)
169 169 {
170 170 sval_t sval;
171 171
172 172 while (*p == ' ')
173 173 p++;
174 174
175 175 if (*p == '$')
176 176 return read_rl_from_var(call, p, end, rl);
177 177
178 178 sval.type = &llong_ctype;
179 179 sval.value = strtoll(p, (char **)end, 10);
180 180 if (*end == p)
181 181 return 0;
182 182 *rl = alloc_rl(sval, sval);
183 183 return 1;
184 184 }
185 185
186 186 static const char *read_op(const char *p)
187 187 {
188 188 while (*p == ' ')
189 189 p++;
190 190
191 191 switch (*p) {
192 192 case '+':
193 193 case '-':
194 194 case '*':
195 195 case '/':
196 196 return p;
197 197 default:
198 198 return NULL;
199 199 }
200 200 }
201 201
202 202 int parse_call_math_rl(struct expression *call, const char *math, struct range_list **rl)
203 203 {
204 204 struct range_list *tmp;
205 205 const char *c;
206 206
207 207 /* try to implement shunting yard algorithm. */
208 208
209 209 c = math;
210 210 while (1) {
211 211 if (option_debug)
212 212 sm_msg("parsing %s", c);
213 213
214 214 /* read a number and push it onto the number stack */
215 215 if (!read_var_num(call, c, &c, &tmp))
216 216 goto fail;
217 217 push_rl(&rl_stack, tmp);
218 218
219 219 if (option_debug)
220 220 sm_msg("val = %s remaining = %s", show_rl(tmp), c);
221 221
222 222 if (!*c)
223 223 break;
224 224 if (*c == ']' && *(c + 1) == '\0')
225 225 break;
226 226
227 227 c = read_op(c);
228 228 if (!c)
229 229 goto fail;
230 230
231 231 if (option_debug)
232 232 sm_msg("op = %c remaining = %s", *c, c);
233 233
234 234 rl_pop_until(*c);
235 235 push_op(*c);
236 236 c++;
237 237 }
238 238
239 239 rl_pop_until(0);
240 240 *rl = pop_rl(&rl_stack);
241 241 return 1;
242 242 fail:
243 243 rl_discard_stacks();
244 244 return 0;
245 245 }
246 246
247 247 int parse_call_math(struct expression *call, char *math, sval_t *sval)
248 248 {
249 249 struct range_list *rl;
250 250
251 251 if (!parse_call_math_rl(call, math, &rl))
252 252 return 0;
253 253 if (!rl_to_sval(rl, sval))
254 254 return 0;
255 255 return 1;
256 256 }
257 257
258 258 static struct smatch_state *alloc_state_sname(char *sname)
259 259 {
260 260 struct smatch_state *state;
261 261
262 262 state = __alloc_smatch_state(0);
263 263 state->name = sname;
264 264 state->data = INT_PTR(1);
265 265 return state;
266 266 }
267 267
268 268 static int get_arg_number(struct expression *expr)
269 269 {
270 270 struct symbol *sym;
271 271 struct symbol *arg;
272 272 int i;
273 273
274 274 expr = strip_expr(expr);
275 275 if (expr->type != EXPR_SYMBOL)
276 276 return -1;
277 277 sym = expr->symbol;
278 278
279 279 i = 0;
280 280 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
281 281 if (arg == sym)
282 282 return i;
283 283 i++;
284 284 } END_FOR_EACH_PTR(arg);
285 285
286 286 return -1;
287 287 }
288 288
289 289 static int format_name_sym_helper(char *buf, int remaining, char *name, struct symbol *sym)
290 290 {
291 291 int ret = 0;
292 292 int arg;
293 293 char *param_name;
294 294 int name_len;
295 295
296 296 if (!name || !sym || !sym->ident)
297 297 goto free;
298 298 arg = get_param_num_from_sym(sym);
299 299 if (arg < 0)
300 300 goto free;
301 301 if (param_was_set_var_sym(name, sym))
302 302 goto free;
303 303
304 304 param_name = sym->ident->name;
305 305 name_len = strlen(param_name);
306 306
307 307 if (name[name_len] == '\0')
308 308 ret = snprintf(buf, remaining, "$%d", arg);
309 309 else if (name[name_len] == '-')
310 310 ret = snprintf(buf, remaining, "$%d%s", arg, name + name_len);
311 311 else
312 312 goto free;
313 313
314 314 remaining -= ret;
315 315 if (remaining <= 0)
316 316 ret = 0;
317 317
318 318 free:
319 319 free_string(name);
320 320
321 321 return ret;
322 322
323 323 }
324 324
325 325 static int format_variable_helper(char *buf, int remaining, struct expression *expr)
326 326 {
327 327 char *name;
328 328 struct symbol *sym;
329 329
330 330 name = expr_to_var_sym(expr, &sym);
331 331 if (param_was_set_var_sym(name, sym))
332 332 return 0;
333 333 return format_name_sym_helper(buf, remaining, name, sym);
334 334 }
335 335
336 336 static int format_call_to_param_mapping(char *buf, int remaining, struct expression *expr)
337 337 {
338 338 char *name;
339 339 struct symbol *sym;
340 340
341 341 name = map_call_to_param_name_sym(expr, &sym);
342 342 if (param_was_set_var_sym(name, sym))
343 343 return 0;
344 344 return format_name_sym_helper(buf, remaining, name, sym);
345 345 }
346 346
347 347 static int is_mtag_sval(sval_t sval)
348 348 {
349 349 if (!is_ptr_type(sval.type))
350 350 return 0;
351 351 if (sval_cmp(sval, valid_ptr_min_sval) >= 0 &&
352 352 sval_cmp(sval, valid_ptr_max_sval) <= 0)
353 353 return 1;
354 354 return 0;
355 355 }
356 356
357 357 static int format_expr_helper(char *buf, int remaining, struct expression *expr)
358 358 {
359 359 sval_t sval;
360 360 int ret;
361 361 char *cur;
362 362
363 363 if (!expr)
364 364 return 0;
365 365
366 366 cur = buf;
367 367
368 368 if (expr->type == EXPR_BINOP) {
369 369 ret = format_expr_helper(cur, remaining, expr->left);
370 370 if (ret == 0)
371 371 return 0;
372 372 remaining -= ret;
373 373 if (remaining <= 0)
374 374 return 0;
375 375 cur += ret;
376 376
377 377 ret = snprintf(cur, remaining, " %s ", show_special(expr->op));
378 378 remaining -= ret;
379 379 if (remaining <= 0)
380 380 return 0;
381 381 cur += ret;
382 382
383 383 ret = format_expr_helper(cur, remaining, expr->right);
384 384 if (ret == 0)
385 385 return 0;
386 386 remaining -= ret;
387 387 if (remaining <= 0)
388 388 return 0;
389 389 cur += ret;
390 390 return cur - buf;
391 391 }
392 392
393 393 if (!param_was_set(expr) && get_implied_value(expr, &sval) && !is_mtag_sval(sval)) {
394 394 ret = snprintf(cur, remaining, "%s", sval_to_str(sval));
395 395 remaining -= ret;
396 396 if (remaining <= 0)
397 397 return 0;
398 398 return ret;
399 399 }
400 400
401 401 if (expr->type == EXPR_CALL)
402 402 return format_call_to_param_mapping(cur, remaining, expr);
403 403
404 404 return format_variable_helper(cur, remaining, expr);
405 405 }
406 406
407 407 static char *format_expr(struct expression *expr)
408 408 {
409 409 char buf[256] = "";
410 410 int ret;
411 411
412 412 ret = format_expr_helper(buf, sizeof(buf), expr);
413 413 if (ret == 0)
414 414 return NULL;
415 415
416 416 return alloc_sname(buf);
417 417 }
418 418
419 419 char *get_value_in_terms_of_parameter_math(struct expression *expr)
420 420 {
421 421 struct expression *tmp;
422 422 char buf[256] = "";
423 423 sval_t dummy;
424 424 int ret;
425 425
426 426 tmp = get_assigned_expr(expr);
427 427 if (tmp)
428 428 expr = tmp;
429 429 if (param_was_set(expr))
430 430 return NULL;
431 431
432 432 if (get_implied_value(expr, &dummy))
433 433 return NULL;
434 434
435 435 ret = format_expr_helper(buf, sizeof(buf), expr);
436 436 if (ret == 0)
437 437 return NULL;
438 438
439 439 return alloc_sname(buf);
440 440 }
441 441
442 442 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym)
443 443 {
444 444 struct expression *tmp, *expr;
445 445 char buf[256] = "";
446 446 int ret;
447 447 int cnt = 0;
448 448 sval_t sval;
449 449
450 450 expr = get_assigned_expr_name_sym(name, sym);
451 451 if (!expr)
452 452 return NULL;
453 453 while ((tmp = get_assigned_expr(expr))) {
454 454 expr = strip_expr(tmp);
455 455 if (++cnt > 3)
456 456 break;
457 457 }
458 458
459 459 if (get_implied_value(expr, &sval))
460 460 return NULL;
461 461
462 462 ret = format_expr_helper(buf, sizeof(buf), expr);
463 463 if (ret == 0)
464 464 return NULL;
465 465
466 466 return alloc_sname(buf);
467 467
468 468 }
469 469
470 470 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
471 471 {
472 472 int size_arg = PTR_INT(_size_arg);
473 473 struct expression *right;
474 474 struct expression *size_expr;
475 475 char *sname;
476 476
477 477 right = strip_expr(expr->right);
478 478 size_expr = get_argument_from_call_expr(right->args, size_arg);
479 479
480 480 sname = format_expr(size_expr);
481 481 if (!sname)
482 482 return;
483 483 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
484 484 }
485 485
486 486 static char *swap_format(struct expression *call, char *format)
487 487 {
488 488 char buf[256];
489 489 sval_t sval;
490 490 long param;
491 491 struct expression *arg;
492 492 char *p;
493 493 char *out;
494 494 int ret;
495 495
496 496 if (format[0] == '$' && format[2] == '\0') {
497 497 param = strtol(format + 1, NULL, 10);
498 498 arg = get_argument_from_call_expr(call->args, param);
499 499 if (!arg)
500 500 return NULL;
501 501 return format_expr(arg);
502 502 }
503 503
504 504 buf[0] = '\0';
505 505 p = format;
506 506 out = buf;
507 507 while (*p) {
508 508 if (*p == '$') {
509 509 p++;
510 510 param = strtol(p, (char **)&p, 10);
511 511 arg = get_argument_from_call_expr(call->args, param);
512 512 if (!arg)
513 513 return NULL;
514 514 param = get_arg_number(arg);
515 515 if (param >= 0) {
516 516 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param);
517 517 out += ret;
518 518 if (out >= buf + sizeof(buf))
519 519 return NULL;
520 520 } else if (get_implied_value(arg, &sval)) {
521 521 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval));
522 522 out += ret;
523 523 if (out >= buf + sizeof(buf))
524 524 return NULL;
525 525 } else {
526 526 return NULL;
527 527 }
528 528 }
529 529 *out = *p;
530 530 p++;
531 531 out++;
532 532 }
533 533 if (buf[0] == '\0')
534 534 return NULL;
535 535 *out = '\0';
536 536 return alloc_sname(buf);
537 537 }
538 538
539 539 static char *buf_size_recipe;
540 540 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName)
541 541 {
542 542 if (argc != 1)
543 543 return 0;
544 544
545 545 if (!buf_size_recipe)
546 546 buf_size_recipe = alloc_sname(argv[0]);
547 547 else if (strcmp(buf_size_recipe, argv[0]) != 0)
548 548 buf_size_recipe = alloc_sname("invalid");
549 549 return 0;
550 550 }
551 551
552 552 static char *get_allocation_recipe_from_call(struct expression *expr)
553 553 {
554 554 struct symbol *sym;
555 555 static char sql_filter[1024];
556 556 int i;
557 557
558 558 if (is_fake_call(expr))
559 559 return NULL;
560 560 expr = strip_expr(expr);
561 561 if (expr->fn->type != EXPR_SYMBOL)
562 562 return NULL;
563 563 sym = expr->fn->symbol;
564 564 if (!sym)
565 565 return NULL;
566 566
567 567 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) {
568 568 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) {
569 569 char buf[32];
570 570
571 571 snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param);
572 572 buf_size_recipe = alloc_sname(buf);
573 573 return swap_format(expr, buf_size_recipe);
574 574 }
575 575 }
576 576
577 577 if (sym->ctype.modifiers & MOD_STATIC) {
578 578 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';",
579 579 get_filename(), sym->ident->name);
580 580 } else {
|
↓ open down ↓ |
580 lines elided |
↑ open up ↑ |
581 581 snprintf(sql_filter, 1024, "function = '%s' and static = 0;",
582 582 sym->ident->name);
583 583 }
584 584
585 585 buf_size_recipe = NULL;
586 586 run_sql(db_buf_size_callback, NULL,
587 587 "select value from return_states where type=%d and %s",
588 588 BUF_SIZE, sql_filter);
589 589 if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0)
590 590 return NULL;
591 + /* Known sizes should be handled in smatch_buf_size.c */
592 + if (!strchr(buf_size_recipe, '$'))
593 + return NULL;
591 594 return swap_format(expr, buf_size_recipe);
592 595 }
593 596
594 597 static void match_call_assignment(struct expression *expr)
595 598 {
596 599 char *sname;
597 600
598 601 sname = get_allocation_recipe_from_call(expr->right);
599 602 if (!sname)
600 603 return;
601 604 set_state_expr(my_id, expr->left, alloc_state_sname(sname));
602 605 }
603 606
604 -static void match_returns_call(int return_id, char *return_ranges, struct expression *call)
607 +const char *get_allocation_math(struct expression *expr)
605 608 {
606 - char *sname;
607 -
608 - sname = get_allocation_recipe_from_call(call);
609 - if (option_debug)
610 - sm_msg("sname = %s", sname);
611 - if (!sname)
612 - return;
613 -
614 - sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
615 - sname);
616 -}
617 -
618 -static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
619 -{
620 609 struct expression *tmp;
621 610 struct smatch_state *state;
622 - struct symbol *sym;
623 - char *name;
624 611 int cnt = 0;
625 612
626 613 expr = strip_expr(expr);
627 614 while ((tmp = get_assigned_expr(expr))) {
628 615 if (cnt++ > 5) /* assignments to self cause infinite loops */
629 616 break;
630 617 expr = strip_expr(tmp);
631 618 }
632 619 if (!expr)
633 - return;
620 + return NULL;
634 621
635 - if (expr->type == EXPR_CALL) {
636 - match_returns_call(return_id, return_ranges, expr);
637 - return;
638 - }
622 + if (expr->type == EXPR_CALL)
623 + return get_allocation_recipe_from_call(expr);
639 624
640 - name = expr_to_var_sym(expr, &sym);
641 - if (!name || !sym)
642 - goto free;
643 -
644 - state = get_state(my_id, name, sym);
625 + state = get_state_expr(my_id, expr);
645 626 if (!state || !state->data)
646 - goto free;
627 + return NULL;
647 628
648 - sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "",
649 - state->name);
650 -free:
651 - free_string(name);
629 + return state->name;
652 630 }
653 631
654 632 void register_parse_call_math(int id)
655 633 {
656 634 int i;
657 635
658 636 my_id = id;
659 637
660 638 set_dynamic_states(my_id);
661 639
662 640 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++)
663 641 add_function_assign_hook(alloc_functions[i].func, &match_alloc,
664 642 INT_PTR(alloc_functions[i].param));
665 643 add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK);
666 - add_split_return_callback(print_returned_allocations);
667 644 }
668 645
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX