Print this page
12257 resync smatch to 0.6.1-rc1-il-4
Split |
Close |
Expand all |
Collapse all |
--- old/usr/src/tools/smatch/src/smatch_math.c
+++ new/usr/src/tools/smatch/src/smatch_math.c
1 1 /*
2 2 * Copyright (C) 2010 Dan Carpenter.
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 "symbol.h"
19 19 #include "smatch.h"
20 20 #include "smatch_slist.h"
21 21 #include "smatch_extra.h"
22 22
23 23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24 24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25 25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26 26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27 27
28 28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29 29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30 30
31 31 static sval_t zero = {.type = &int_ctype, {.value = 0} };
32 32 static sval_t one = {.type = &int_ctype, {.value = 1} };
33 33
34 34 static int fast_math_only;
35 35
36 36 struct range_list *rl_zero(void)
37 37 {
38 38 static struct range_list *zero_perm;
39 39
40 40 if (!zero_perm)
41 41 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
42 42 return zero_perm;
43 43 }
44 44
45 45 struct range_list *rl_one(void)
46 46 {
47 47 static struct range_list *one_perm;
48 48
49 49 if (!one_perm)
50 50 one_perm = clone_rl_permanent(alloc_rl(one, one));
51 51
52 52 return one_perm;
53 53 }
54 54
55 55 enum {
56 56 RL_EXACT,
57 57 RL_HARD,
58 58 RL_FUZZY,
59 59 RL_IMPLIED,
60 60 RL_ABSOLUTE,
61 61 RL_REAL_ABSOLUTE,
62 62 };
63 63
64 64 static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
65 65 {
66 66 struct expression *expr;
67 67
68 68 if (!stmt)
69 69 return false;
70 70
71 71 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
72 72 if (stmt->type == STMT_LABEL) {
73 73 if (stmt->label_statement &&
74 74 stmt->label_statement->type == STMT_EXPRESSION)
75 75 expr = stmt->label_statement->expression;
76 76 else
77 77 return false;
78 78 } else if (stmt->type == STMT_EXPRESSION) {
79 79 expr = stmt->expression;
80 80 } else {
81 81 return false;
82 82 }
83 83 return get_rl_sval(expr, implied, recurse_cnt, res, res_sval);
84 84 }
85 85
86 86 static bool handle_expression_statement_rl(struct expression *expr, int implied,
87 87 int *recurse_cnt, struct range_list **res, sval_t *res_sval)
88 88 {
89 89 return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval);
90 90 }
91 91
92 92 static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
93 93 {
94 94 struct range_list *rl;
95 95 static int recursed;
96 96 sval_t sval;
97 97
98 98 if (recursed > 10)
99 99 return false;
100 100 if (implied == RL_EXACT)
101 101 return false;
102 102
103 103 if (custom_handle_variable) {
104 104 rl = custom_handle_variable(expr);
105 105 if (rl) {
106 106 *res = rl;
107 107 return true;
108 108 }
109 109 }
110 110
111 111 recursed++;
112 112 if (get_mtag_sval(expr, &sval)) {
113 113 recursed--;
114 114 *res_sval = sval;
115 115 return true;
116 116 }
117 117
118 118 if (get_address_rl(expr, res)) {
119 119 recursed--;
120 120 return true;
121 121 }
122 122 recursed--;
123 123 return 0;
124 124 }
125 125
126 126 static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
127 127 {
128 128 return handle_address(expr, implied, recurse_cnt, res, res_sval);
129 129 }
130 130
131 131 static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
132 132 {
133 133 if (known_condition_true(expr->unop)) {
134 134 *res_sval = zero;
135 135 return true;
136 136 }
137 137 if (known_condition_false(expr->unop)) {
138 138 *res_sval = one;
139 139 return true;
140 140 }
141 141
142 142 if (implied == RL_EXACT)
143 143 return false;
144 144
145 145 if (implied_condition_true(expr->unop)) {
146 146 *res_sval = zero;
147 147 return true;
148 148 }
149 149 if (implied_condition_false(expr->unop)) {
150 150 *res_sval = one;
151 151 return true;
152 152 }
153 153
154 154 *res = alloc_rl(zero, one);
155 155 return true;
156 156 }
157 157
158 158 static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
159 159 {
160 160 struct range_list *rl;
161 161 sval_t sval = {};
162 162
163 163 if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
164 164 return false;
165 165 if (!sval.type && !rl_to_sval(rl, &sval))
166 166 return false;
167 167 sval = sval_preop(sval, '~');
168 168 sval_cast(get_type(expr->unop), sval);
169 169 *res_sval = sval;
170 170 return true;
171 171 }
172 172
173 173 static bool untrusted_type_min(struct expression *expr)
174 174 {
175 175 struct range_list *rl;
176 176
177 177 rl = var_user_rl(expr);
178 178 return rl && sval_is_min(rl_min(rl));
179 179 }
180 180
181 181 static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
182 182 {
183 183 struct range_list *rl;
184 184 struct range_list *ret = NULL;
185 185 struct symbol *type;
186 186 sval_t neg_one = { 0 };
187 187 sval_t zero = { 0 };
188 188 sval_t sval = {};
189 189
190 190 neg_one.value = -1;
191 191 zero.value = 0;
192 192
193 193 if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
194 194 return false;
195 195 if (sval.type) {
196 196 *res_sval = sval_preop(sval, '-');
197 197 return true;
198 198 }
199 199 /*
200 200 * One complication is that -INT_MIN is still INT_MIN because of integer
201 201 * overflows... But how many times do we set a time out to INT_MIN?
202 202 * So normally when we call abs() then it does return a positive value.
203 203 *
204 204 */
205 205 type = rl_type(rl);
206 206 neg_one.type = zero.type = type;
207 207
208 208 if (sval_is_negative(rl_min(rl))) {
209 209 struct range_list *neg;
210 210 struct data_range *drange;
211 211 sval_t new_min, new_max;
212 212
213 213 neg = alloc_rl(sval_type_min(type), neg_one);
214 214 neg = rl_intersection(rl, neg);
215 215
216 216 if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg)))
217 217 neg = remove_range(neg, sval_type_min(type), sval_type_min(type));
218 218
219 219 FOR_EACH_PTR(neg, drange) {
220 220 new_min = drange->max;
221 221 new_min.value = -new_min.value;
222 222 new_max = drange->min;
223 223 new_max.value = -new_max.value;
224 224 add_range(&ret, new_min, new_max);
225 225 } END_FOR_EACH_PTR(drange);
226 226
227 227 if (untrusted_type_min(expr))
228 228 add_range(&ret, sval_type_min(type), sval_type_min(type));
229 229 }
230 230
231 231 if (!sval_is_negative(rl_max(rl))) {
232 232 struct range_list *pos;
233 233 struct data_range *drange;
234 234 sval_t new_min, new_max;
235 235
236 236 pos = alloc_rl(zero, sval_type_max(type));
237 237 pos = rl_intersection(rl, pos);
238 238
239 239 FOR_EACH_PTR(pos, drange) {
240 240 new_min = drange->max;
241 241 new_min.value = -new_min.value;
242 242 new_max = drange->min;
243 243 new_max.value = -new_max.value;
244 244 add_range(&ret, new_min, new_max);
245 245 } END_FOR_EACH_PTR(drange);
246 246 }
247 247
248 248 *res = ret;
249 249 return true;
250 250 }
251 251
252 252 static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
253 253 {
254 254 switch (expr->op) {
255 255 case '&':
256 256 return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval);
257 257 case '!':
258 258 return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval);
259 259 case '~':
260 260 return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval);
261 261 case '-':
262 262 return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval);
263 263 case '*':
264 264 return handle_variable(expr, implied, recurse_cnt, res, res_sval);
265 265 case '(':
266 266 return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval);
267 267 default:
268 268 return false;
269 269 }
270 270 }
271 271
272 272 static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
273 273 {
274 274 struct range_list *left_rl = NULL;
275 275 struct range_list *right_rl = NULL;
276 276 struct symbol *type;
277 277
278 278 type = get_type(expr);
279 279
280 280 get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
281 281 left_rl = cast_rl(type, left_rl);
282 282 get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
283 283 right_rl = cast_rl(type, right_rl);
284 284
285 285 if (!left_rl || !right_rl)
286 286 return false;
287 287
288 288 if (implied != RL_REAL_ABSOLUTE) {
289 289 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
290 290 return false;
291 291 }
292 292
293 293 *res = rl_binop(left_rl, '/', right_rl);
294 294 return true;
295 295 }
296 296
297 297 static int handle_offset_subtraction(struct expression *expr)
298 298 {
299 299 struct expression *left, *right;
300 300 struct symbol *left_sym, *right_sym;
301 301 struct symbol *type;
302 302 int left_offset, right_offset;
303 303
304 304 type = get_type(expr);
305 305 if (!type || type->type != SYM_PTR)
306 306 return -1;
307 307 type = get_real_base_type(type);
308 308 if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
309 309 return -1;
310 310
311 311 left = strip_expr(expr->left);
312 312 right = strip_expr(expr->right);
313 313
314 314 if (left->type != EXPR_PREOP || left->op != '&')
315 315 return -1;
316 316 left = strip_expr(left->unop);
317 317
318 318 left_sym = expr_to_sym(left);
319 319 right_sym = expr_to_sym(right);
320 320 if (!left_sym || left_sym != right_sym)
321 321 return -1;
322 322
323 323 left_offset = get_member_offset_from_deref(left);
324 324 if (right->type == EXPR_SYMBOL)
325 325 right_offset = 0;
326 326 else {
327 327 if (right->type != EXPR_PREOP || right->op != '&')
328 328 return -1;
329 329 right = strip_expr(right->unop);
330 330 right_offset = get_member_offset_from_deref(right);
331 331 }
332 332 if (left_offset < 0 || right_offset < 0)
333 333 return -1;
334 334
335 335 return left_offset - right_offset;
336 336 }
337 337
338 338 static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
339 339 {
340 340 struct symbol *type;
341 341 struct range_list *left_orig, *right_orig;
342 342 struct range_list *left_rl, *right_rl;
343 343 sval_t min, max, tmp;
344 344 int comparison;
345 345 int offset;
346 346
347 347 type = get_type(expr);
348 348
349 349 offset = handle_offset_subtraction(expr);
350 350 if (offset >= 0) {
351 351 tmp.type = type;
352 352 tmp.value = offset;
353 353
354 354 *res = alloc_rl(tmp, tmp);
355 355 return true;
356 356 }
357 357
358 358 comparison = get_comparison(expr->left, expr->right);
359 359
360 360 left_orig = NULL;
361 361 get_rl_internal(expr->left, implied, recurse_cnt, &left_orig);
362 362 left_rl = cast_rl(type, left_orig);
363 363 right_orig = NULL;
364 364 get_rl_internal(expr->right, implied, recurse_cnt, &right_orig);
365 365 right_rl = cast_rl(type, right_orig);
366 366
367 367 if ((!left_rl || !right_rl) &&
368 368 (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
369 369 return false;
370 370
371 371 if (!left_rl)
372 372 left_rl = alloc_whole_rl(type);
373 373 if (!right_rl)
374 374 right_rl = alloc_whole_rl(type);
375 375
376 376 /* negative values complicate everything fix this later */
377 377 if (sval_is_negative(rl_min(right_rl)))
378 378 return false;
379 379 max = rl_max(left_rl);
380 380 min = sval_type_min(type);
381 381
382 382 switch (comparison) {
383 383 case '>':
384 384 case SPECIAL_UNSIGNED_GT:
385 385 min = sval_type_val(type, 1);
386 386 max = rl_max(left_rl);
387 387 break;
388 388 case SPECIAL_GTE:
389 389 case SPECIAL_UNSIGNED_GTE:
390 390 min = sval_type_val(type, 0);
391 391 max = rl_max(left_rl);
392 392 break;
393 393 case SPECIAL_EQUAL:
394 394 min = sval_type_val(type, 0);
395 395 max = sval_type_val(type, 0);
396 396 break;
397 397 case '<':
398 398 case SPECIAL_UNSIGNED_LT:
399 399 max = sval_type_val(type, -1);
400 400 break;
401 401 case SPECIAL_LTE:
402 402 case SPECIAL_UNSIGNED_LTE:
403 403 max = sval_type_val(type, 0);
404 404 break;
405 405 default:
406 406 if (!left_orig || !right_orig)
407 407 return false;
408 408 *res = rl_binop(left_rl, '-', right_rl);
409 409 return true;
410 410 }
411 411
412 412 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
413 413 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
414 414 if (sval_cmp(tmp, min) > 0)
415 415 min = tmp;
416 416 }
417 417
418 418 if (!sval_is_max(rl_max(left_rl))) {
419 419 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
420 420 if (sval_cmp(tmp, max) < 0)
421 421 max = tmp;
422 422 }
423 423
424 424 if (sval_is_min(min) && sval_is_max(max))
425 425 return false;
426 426
427 427 *res = cast_rl(type, alloc_rl(min, max));
428 428 return true;
429 429 }
430 430
431 431 static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
432 432 {
433 433 struct range_list *rl;
434 434 sval_t left, right, sval;
435 435
436 436 if (implied == RL_EXACT) {
437 437 if (!get_implied_value(expr->right, &right))
438 438 return false;
439 439 if (!get_implied_value(expr->left, &left))
440 440 return false;
441 441 sval = sval_binop(left, '%', right);
442 442 *res = alloc_rl(sval, sval);
443 443 return true;
444 444 }
445 445 /* if we can't figure out the right side it's probably hopeless */
446 446 if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
447 447 return false;
448 448
449 449 right = sval_cast(get_type(expr), right);
450 450 right.value--;
451 451
452 452 if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl &&
453 453 rl_max(rl).uvalue < right.uvalue)
454 454 right.uvalue = rl_max(rl).uvalue;
455 455
456 456 *res = alloc_rl(sval_cast(right.type, zero), right);
457 457 return true;
458 458 }
459 459
460 460 static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
461 461 {
462 462 struct symbol *type;
463 463 struct range_list *left_rl, *right_rl;
464 464 int new_recurse;
465 465
466 466 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
467 467 return false;
468 468
469 469 type = get_type(expr);
470 470
471 471 if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl))
472 472 left_rl = alloc_whole_rl(type);
473 473 left_rl = cast_rl(type, left_rl);
474 474
475 475 new_recurse = *recurse_cnt;
476 476 if (*recurse_cnt >= 200)
477 477 new_recurse = 100; /* Let's try super hard to get the mask */
478 478 if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl))
479 479 right_rl = alloc_whole_rl(type);
480 480 right_rl = cast_rl(type, right_rl);
481 481 *recurse_cnt = new_recurse;
482 482
483 483 *res = rl_binop(left_rl, '&', right_rl);
484 484 return true;
485 485 }
486 486
487 487 static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
488 488 {
489 489 struct symbol *type;
490 490 struct range_list *left_rl, *right_rl;
491 491
492 492 if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
493 493 return false;
494 494
495 495 type = get_type(expr);
496 496
497 497 get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
498 498 get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
499 499 left_rl = cast_rl(type, left_rl);
500 500 right_rl = cast_rl(type, right_rl);
501 501 if (!left_rl || !right_rl)
502 502 return false;
503 503
504 504 *res = rl_binop(left_rl, expr->op, right_rl);
505 505 return true;
506 506 }
507 507
508 508 static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
509 509 {
510 510 struct range_list *left_rl, *right_rl;
511 511 sval_t min, max;
512 512
513 513 if (implied == RL_EXACT || implied == RL_HARD)
514 514 return false;
515 515
516 516 if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
517 517 max = rl_max(left_rl);
518 518 min = rl_min(left_rl);
519 519 } else {
520 520 if (implied == RL_FUZZY)
521 521 return false;
522 522 max = sval_type_max(get_type(expr->left));
523 523 min = sval_type_val(get_type(expr->left), 0);
524 524 }
525 525
526 526 if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) &&
527 527 !sval_is_negative(rl_min(right_rl))) {
528 528 min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl));
529 529 max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl));
530 530 } else if (!sval_is_negative(min)) {
531 531 min.value = 0;
532 532 max = sval_type_max(max.type);
533 533 } else {
534 534 return false;
535 535 }
536 536
537 537 *res = alloc_rl(min, max);
538 538 return true;
539 539 }
540 540
541 541 static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
542 542 {
543 543 struct range_list *left_rl, *rl;
544 544 sval_t right;
545 545
546 546 if (implied == RL_EXACT || implied == RL_HARD)
547 547 return false;
548 548 /* this is hopeless without the right side */
549 549 if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
550 550 return false;
551 551 if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
552 552 if (implied == RL_FUZZY)
553 553 return false;
554 554 left_rl = alloc_whole_rl(get_type(expr->left));
555 555 }
556 556
557 557 rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right));
558 558 if (!rl)
559 559 return false;
560 560 *res = rl;
561 561 return true;
562 562 }
563 563
564 564 static bool handle_known_binop(struct expression *expr, sval_t *res)
565 565 {
566 566 sval_t left, right;
567 567
568 568 if (!get_value(expr->left, &left))
569 569 return false;
570 570 if (!get_value(expr->right, &right))
571 571 return false;
572 572 *res = sval_binop(left, expr->op, right);
573 573 return true;
574 574 }
575 575
576 576 static int has_actual_ranges(struct range_list *rl)
577 577 {
578 578 struct data_range *tmp;
579 579
580 580 FOR_EACH_PTR(rl, tmp) {
581 581 if (sval_cmp(tmp->min, tmp->max) != 0)
582 582 return 1;
583 583 } END_FOR_EACH_PTR(tmp);
584 584 return 0;
585 585 }
586 586
587 587 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
588 588 {
589 589 struct range_list *res_rl;
590 590 struct data_range *left_drange, *right_drange;
591 591 sval_t res;
592 592
593 593 if (!left_rl || !right_rl)
594 594 return NULL;
595 595 if (has_actual_ranges(left_rl))
596 596 return NULL;
597 597 if (has_actual_ranges(right_rl))
598 598 return NULL;
599 599
600 600 if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
601 601 return NULL;
602 602
603 603 res_rl = NULL;
604 604
605 605 FOR_EACH_PTR(left_rl, left_drange) {
606 606 FOR_EACH_PTR(right_rl, right_drange) {
607 607 if ((op == '%' || op == '/') &&
608 608 right_drange->min.value == 0)
609 609 return NULL;
610 610 res = sval_binop(left_drange->min, op, right_drange->min);
611 611 add_range(&res_rl, res, res);
612 612 } END_FOR_EACH_PTR(right_drange);
613 613 } END_FOR_EACH_PTR(left_drange);
614 614
615 615 return res_rl;
616 616 }
617 617
618 618 static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
619 619 {
620 620 struct symbol *type;
621 621 struct range_list *left_rl = NULL;
622 622 struct range_list *right_rl = NULL;
623 623 struct range_list *rl;
624 624 sval_t min, max;
625 625
626 626 type = get_promoted_type(get_type(expr->left), get_type(expr->right));
627 627 get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
628 628 left_rl = cast_rl(type, left_rl);
629 629 get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
630 630 right_rl = cast_rl(type, right_rl);
631 631 if (!left_rl && !right_rl)
632 632 return false;
633 633
634 634 rl = handle_implied_binop(left_rl, expr->op, right_rl);
635 635 if (rl) {
636 636 *res = rl;
637 637 return true;
638 638 }
639 639
640 640 switch (expr->op) {
641 641 case '%':
642 642 return handle_mod_rl(expr, implied, recurse_cnt, res);
643 643 case '&':
644 644 return handle_bitwise_AND(expr, implied, recurse_cnt, res);
645 645 case '|':
646 646 case '^':
647 647 return use_rl_binop(expr, implied, recurse_cnt, res);
648 648 case SPECIAL_RIGHTSHIFT:
649 649 return handle_right_shift(expr, implied, recurse_cnt, res);
650 650 case SPECIAL_LEFTSHIFT:
651 651 return handle_left_shift(expr, implied, recurse_cnt, res);
652 652 case '-':
653 653 return handle_subtract_rl(expr, implied, recurse_cnt, res);
654 654 case '/':
655 655 return handle_divide_rl(expr, implied, recurse_cnt, res);
656 656 }
657 657
658 658 if (!left_rl || !right_rl)
659 659 return false;
660 660
661 661 if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
662 662 return false;
663 663 if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
664 664 return false;
665 665
666 666 min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
667 667 max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
668 668
669 669 *res = alloc_rl(min, max);
670 670 return true;
671 671
672 672 }
673 673
674 674 static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
675 675 {
676 676 struct smatch_state *state;
677 677 struct range_list *rl;
678 678 sval_t val;
679 679
680 680 if (handle_known_binop(expr, &val)) {
681 681 *res_sval = val;
682 682 return true;
683 683 }
684 684 if (implied == RL_EXACT)
685 685 return false;
686 686
687 687 if (custom_handle_variable) {
688 688 rl = custom_handle_variable(expr);
689 689 if (rl) {
690 690 *res = rl;
691 691 return true;
692 692 }
693 693 }
694 694
695 695 state = get_extra_state(expr);
696 696 if (state && !is_whole_rl(estate_rl(state))) {
697 697 if (implied != RL_HARD || estate_has_hard_max(state)) {
698 698 *res = clone_rl(estate_rl(state));
699 699 return true;
700 700 }
701 701 }
702 702
703 703 return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval);
704 704 }
705 705
706 706 static int do_comparison(struct expression *expr)
707 707 {
708 708 struct range_list *left_ranges = NULL;
709 709 struct range_list *right_ranges = NULL;
710 710 int poss_true, poss_false;
711 711 struct symbol *type;
712 712
713 713 type = get_type(expr);
714 714 get_absolute_rl(expr->left, &left_ranges);
715 715 get_absolute_rl(expr->right, &right_ranges);
716 716
717 717 left_ranges = cast_rl(type, left_ranges);
718 718 right_ranges = cast_rl(type, right_ranges);
719 719
720 720 poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
721 721 poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
722 722
723 723 if (!poss_true && !poss_false)
724 724 return 0x0;
725 725 if (poss_true && !poss_false)
726 726 return 0x1;
727 727 if (!poss_true && poss_false)
728 728 return 0x2;
729 729 return 0x3;
730 730 }
731 731
732 732 static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
733 733 {
734 734 sval_t left, right;
735 735 int cmp;
736 736
737 737 if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
738 738 struct symbol *left, *right;
739 739
740 740 if (expr->right->type != EXPR_TYPE)
741 741 return false;
742 742
743 743 left = get_real_base_type(expr->left->symbol);
744 744 right = get_real_base_type(expr->right->symbol);
745 745 if (type_bits(left) == type_bits(right) &&
746 746 type_positive_bits(left) == type_positive_bits(right))
747 747 *res_sval = one;
748 748 else
749 749 *res_sval = zero;
750 750 return true;
751 751 }
752 752
753 753 if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
754 754 struct data_range tmp_left, tmp_right;
755 755
756 756 tmp_left.min = left;
757 757 tmp_left.max = left;
758 758 tmp_right.min = right;
759 759 tmp_right.max = right;
760 760 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
761 761 *res_sval = one;
762 762 else
763 763 *res_sval = zero;
764 764 return true;
765 765 }
766 766
767 767 if (implied == RL_EXACT)
768 768 return false;
769 769
770 770 cmp = do_comparison(expr);
771 771 if (cmp == 1) {
772 772 *res_sval = one;
773 773 return true;
774 774 }
775 775 if (cmp == 2) {
776 776 *res_sval = zero;
777 777 return true;
778 778 }
779 779
780 780 *res = alloc_rl(zero, one);
781 781 return true;
782 782 }
783 783
784 784 static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
785 785 {
786 786 sval_t left, right;
787 787 int left_known = 0;
788 788 int right_known = 0;
789 789
790 790 if (implied == RL_EXACT) {
791 791 if (get_value(expr->left, &left))
792 792 left_known = 1;
793 793 if (get_value(expr->right, &right))
794 794 right_known = 1;
795 795 } else {
796 796 if (get_implied_value_internal(expr->left, recurse_cnt, &left))
797 797 left_known = 1;
798 798 if (get_implied_value_internal(expr->right, recurse_cnt, &right))
799 799 right_known = 1;
800 800 }
801 801
802 802 switch (expr->op) {
803 803 case SPECIAL_LOGICAL_OR:
804 804 if (left_known && left.value)
805 805 goto one;
806 806 if (right_known && right.value)
807 807 goto one;
808 808 if (left_known && right_known)
809 809 goto zero;
810 810 break;
811 811 case SPECIAL_LOGICAL_AND:
812 812 if (left_known && right_known) {
813 813 if (left.value && right.value)
814 814 goto one;
815 815 goto zero;
816 816 }
817 817 break;
818 818 default:
819 819 return false;
820 820 }
821 821
822 822 if (implied == RL_EXACT)
823 823 return false;
824 824
825 825 *res = alloc_rl(zero, one);
826 826 return true;
827 827
828 828 zero:
829 829 *res_sval = zero;
830 830 return true;
831 831 one:
832 832 *res_sval = one;
833 833 return true;
834 834 }
835 835
836 836 static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
837 837 {
838 838 struct expression *cond_true;
839 839 struct range_list *true_rl, *false_rl;
840 840 struct symbol *type;
841 841 int final_pass_orig = final_pass;
842 842
843 843 cond_true = expr->cond_true;
844 844 if (!cond_true)
845 845 cond_true = expr->conditional;
846 846
847 847 if (known_condition_true(expr->conditional))
848 848 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
849 849 if (known_condition_false(expr->conditional))
850 850 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
851 851
852 852 if (implied == RL_EXACT)
853 853 return false;
854 854
855 855 if (implied_condition_true(expr->conditional))
856 856 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
857 857 if (implied_condition_false(expr->conditional))
858 858 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
859 859
860 860 /* this becomes a problem with deeply nested conditional statements */
861 861 if (fast_math_only || low_on_memory())
862 862 return false;
863 863
864 864 type = get_type(expr);
865 865
866 866 __push_fake_cur_stree();
867 867 final_pass = 0;
868 868 __split_whole_condition(expr->conditional);
869 869 true_rl = NULL;
870 870 get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
871 871 __push_true_states();
872 872 __use_false_states();
873 873 false_rl = NULL;
874 874 get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
875 875 __merge_true_states();
876 876 __free_fake_cur_stree();
877 877 final_pass = final_pass_orig;
878 878
879 879 if (!true_rl || !false_rl)
880 880 return false;
881 881 true_rl = cast_rl(type, true_rl);
882 882 false_rl = cast_rl(type, false_rl);
883 883
884 884 *res = rl_union(true_rl, false_rl);
885 885 return true;
886 886 }
887 887
888 888 static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max)
889 889 {
890 890 struct smatch_state *state;
891 891 sval_t sval;
892 892
893 893 if (get_hard_max(expr, &sval)) {
894 894 *max = sval;
895 895 return true;
896 896 }
897 897
898 898 state = get_extra_state(expr);
899 899 if (!state || !estate_has_fuzzy_max(state))
900 900 return false;
901 901 *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
902 902 return true;
903 903 }
904 904
905 905 static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min)
906 906 {
907 907 struct smatch_state *state;
908 908 sval_t sval;
909 909
910 910 state = get_extra_state(expr);
911 911 if (!state || !estate_rl(state))
912 912 return false;
913 913
914 914 sval = estate_min(state);
915 915 if (sval_is_negative(sval) && sval_is_min(sval))
916 916 return false;
917 917
918 918 if (sval_is_max(sval))
919 919 return false;
920 920
921 921 *min = sval_cast(get_type(expr), sval);
922 922 return true;
923 923 }
924 924
925 925 int get_const_value(struct expression *expr, sval_t *sval)
926 926 {
927 927 struct symbol *sym;
928 928 sval_t right;
929 929
930 930 if (expr->type != EXPR_SYMBOL || !expr->symbol)
931 931 return 0;
932 932 sym = expr->symbol;
933 933 if (!(sym->ctype.modifiers & MOD_CONST))
934 934 return 0;
935 935 if (get_value(sym->initializer, &right)) {
936 936 *sval = sval_cast(get_type(expr), right);
937 937 return 1;
938 938 }
939 939 return 0;
940 940 }
941 941
942 942 struct range_list *var_to_absolute_rl(struct expression *expr)
943 943 {
944 944 struct smatch_state *state;
945 945 struct range_list *rl;
946 946
947 947 state = get_extra_state(expr);
948 948 if (!state || is_whole_rl(estate_rl(state))) {
949 949 state = get_real_absolute_state(expr);
950 950 if (state && state->data && !estate_is_whole(state))
951 951 return clone_rl(estate_rl(state));
952 952 if (get_mtag_rl(expr, &rl))
953 953 return rl;
954 954 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
955 955 return rl;
956 956 return alloc_whole_rl(get_type(expr));
957 957 }
958 958 /* err on the side of saying things are possible */
959 959 if (!estate_rl(state))
960 960 return alloc_whole_rl(get_type(expr));
961 961 return clone_rl(estate_rl(state));
962 962 }
963 963
964 964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
965 965 {
966 966 struct smatch_state *state;
967 967 struct range_list *rl;
968 968 sval_t sval, min, max;
969 969 struct symbol *type;
970 970
971 971 if (get_const_value(expr, &sval)) {
972 972 *res_sval = sval;
973 973 return true;
974 974 }
975 975
976 976 if (implied == RL_EXACT)
977 977 return false;
978 978
979 979 if (custom_handle_variable) {
980 980 rl = custom_handle_variable(expr);
981 981 if (rl) {
982 982 if (!rl_to_sval(rl, res_sval))
983 983 *res = rl;
984 984 } else {
985 985 *res = var_to_absolute_rl(expr);
986 986 }
987 987 return true;
988 988 }
989 989
990 990 if (get_mtag_sval(expr, &sval)) {
991 991 *res_sval = sval;
992 992 return true;
993 993 }
994 994
995 995 type = get_type(expr);
996 996 if (type &&
997 997 (type->type == SYM_ARRAY ||
998 998 type->type == SYM_FN))
999 999 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000 1000
1001 1001 /* FIXME: call rl_to_sval() on the results */
1002 1002
1003 1003 switch (implied) {
1004 1004 case RL_HARD:
1005 1005 case RL_IMPLIED:
1006 1006 case RL_ABSOLUTE:
1007 1007 state = get_extra_state(expr);
1008 1008 if (!state) {
1009 1009 if (implied == RL_HARD)
1010 1010 return false;
1011 1011 if (get_mtag_rl(expr, res))
1012 1012 return true;
1013 1013 if (get_db_type_rl(expr, res))
1014 1014 return true;
1015 1015 if (is_array(expr) && get_array_rl(expr, res))
1016 1016 return true;
1017 1017 return false;
1018 1018 }
1019 1019 if (implied == RL_HARD && !estate_has_hard_max(state))
1020 1020 return false;
1021 1021 *res = clone_rl(estate_rl(state));
1022 1022 return true;
1023 1023 case RL_REAL_ABSOLUTE: {
1024 1024 struct smatch_state *abs_state;
1025 1025
1026 1026 state = get_extra_state(expr);
1027 1027 abs_state = get_real_absolute_state(expr);
1028 1028
1029 1029 if (estate_rl(state) && estate_rl(abs_state)) {
1030 1030 *res = clone_rl(rl_intersection(estate_rl(state),
1031 1031 estate_rl(abs_state)));
1032 1032 return true;
1033 1033 } else if (estate_rl(state)) {
1034 1034 *res = clone_rl(estate_rl(state));
1035 1035 return true;
1036 1036 } else if (estate_is_empty(state)) {
1037 1037 /*
1038 1038 * FIXME: we don't handle empty extra states correctly.
1039 1039 *
1040 1040 * The real abs rl is supposed to be filtered by the
1041 1041 * extra state if there is one. We don't bother keeping
1042 1042 * the abs state in sync all the time because we know it
1043 1043 * will be filtered later.
1044 1044 *
1045 1045 * It's not totally obvious to me how they should be
1046 1046 * handled. Perhaps we should take the whole rl and
1047 1047 * filter by the imaginary states. Perhaps we should
1048 1048 * just go with the empty state.
1049 1049 *
1050 1050 * Anyway what we currently do is return NULL here and
1051 1051 * that gets translated into the whole range in
1052 1052 * get_real_absolute_rl().
1053 1053 *
1054 1054 */
1055 1055 return false;
1056 1056 } else if (estate_rl(abs_state)) {
1057 1057 *res = clone_rl(estate_rl(abs_state));
1058 1058 return true;
1059 1059 }
1060 1060
1061 1061 if (get_mtag_rl(expr, res))
1062 1062 return true;
1063 1063 if (get_db_type_rl(expr, res))
1064 1064 return true;
1065 1065 if (is_array(expr) && get_array_rl(expr, res))
1066 1066 return true;
1067 1067 return false;
1068 1068 }
1069 1069 case RL_FUZZY:
1070 1070 if (!get_fuzzy_min_helper(expr, &min))
1071 1071 min = sval_type_min(get_type(expr));
1072 1072 if (!get_fuzzy_max_helper(expr, &max))
1073 1073 return false;
1074 1074 /* fuzzy ranges are often inverted */
1075 1075 if (sval_cmp(min, max) > 0) {
1076 1076 sval = min;
1077 1077 min = max;
1078 1078 max = sval;
1079 1079 }
1080 1080 *res = alloc_rl(min, max);
1081 1081 return true;
1082 1082 }
1083 1083 return false;
1084 1084 }
1085 1085
1086 1086 static sval_t handle_sizeof(struct expression *expr)
1087 1087 {
1088 1088 struct symbol *sym;
1089 1089 sval_t ret;
1090 1090
1091 1091 ret = sval_blank(expr);
1092 1092 sym = expr->cast_type;
1093 1093 if (!sym) {
1094 1094 sym = evaluate_expression(expr->cast_expression);
1095 1095 if (!sym) {
1096 1096 __silence_warnings_for_stmt = true;
1097 1097 sym = &int_ctype;
1098 1098 }
1099 1099 #if 0
1100 1100 /*
1101 1101 * Expressions of restricted types will possibly get
1102 1102 * promoted - check that here. I'm not sure how this works,
1103 1103 * the problem is that sizeof(le16) shouldn't be promoted and
1104 1104 * the original code did that... Let's if zero this out and
1105 1105 * see what breaks.
1106 1106 */
1107 1107
1108 1108 if (is_restricted_type(sym)) {
1109 1109 if (type_bits(sym) < bits_in_int)
1110 1110 sym = &int_ctype;
1111 1111 }
1112 1112 #endif
1113 1113 if (is_fouled_type(sym))
1114 1114 sym = &int_ctype;
1115 1115 }
1116 1116 examine_symbol_type(sym);
1117 1117
1118 1118 ret.type = size_t_ctype;
1119 1119 if (type_bits(sym) <= 0) /* sizeof(void) */ {
1120 1120 if (get_real_base_type(sym) == &void_ctype)
1121 1121 ret.value = 1;
1122 1122 else
1123 1123 ret.value = 0;
1124 1124 } else
1125 1125 ret.value = type_bytes(sym);
1126 1126
1127 1127 return ret;
1128 1128 }
1129 1129
1130 1130 static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1131 1131 {
1132 1132 struct expression *arg, *tmp;
1133 1133 sval_t tag;
1134 1134 sval_t ret = { .type = &ulong_ctype };
1135 1135 struct range_list *rl;
1136 1136
1137 1137 arg = get_argument_from_call_expr(expr->args, 0);
1138 1138 if (!arg)
1139 1139 return false;
1140 1140 if (arg->type == EXPR_STRING) {
1141 1141 ret.value = arg->string->length - 1;
1142 1142 *res_sval = ret;
1143 1143 return true;
1144 1144 }
1145 1145 if (implied == RL_EXACT)
1146 1146 return false;
1147 1147 if (get_implied_value(arg, &tag) &&
1148 1148 (tmp = fake_string_from_mtag(tag.uvalue))) {
1149 1149 ret.value = tmp->string->length - 1;
1150 1150 *res_sval = ret;
1151 1151 return true;
1152 1152 }
1153 1153
1154 1154 if (implied == RL_HARD || implied == RL_FUZZY)
1155 1155 return false;
1156 1156
1157 1157 if (get_implied_return(expr, &rl)) {
1158 1158 *res = rl;
1159 1159 return true;
1160 1160 }
1161 1161
1162 1162 return false;
1163 1163 }
1164 1164
1165 1165 static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
1166 1166 {
1167 1167 struct expression *arg;
1168 1168 struct range_list *rl;
1169 1169
1170 1170 arg = get_argument_from_call_expr(expr->args, 0);
1171 1171 if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl))
1172 1172 *res_sval = one;
1173 1173 else
1174 1174 *res_sval = zero;
1175 1175 return true;
1176 1176 }
1177 1177
1178 1178 static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1179 1179 {
1180 1180 struct expression *const_expr, *expr1, *expr2;
1181 1181 sval_t sval;
1182 1182
1183 1183 const_expr = get_argument_from_call_expr(expr->args, 0);
1184 1184 expr1 = get_argument_from_call_expr(expr->args, 1);
1185 1185 expr2 = get_argument_from_call_expr(expr->args, 2);
1186 1186
1187 1187 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1188 1188 return false;
1189 1189 if (sval.value)
1190 1190 return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval);
1191 1191 else
1192 1192 return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval);
1193 1193 }
1194 1194
1195 1195 static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1196 1196 {
1197 1197 struct range_list *rl;
1198 1198
1199 1199 if (sym_name_is("__builtin_constant_p", expr->fn))
1200 1200 return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval);
1201 1201
1202 1202 if (sym_name_is("__builtin_choose_expr", expr->fn))
1203 1203 return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval);
1204 1204
1205 1205 if (sym_name_is("__builtin_expect", expr->fn) ||
1206 1206 sym_name_is("__builtin_bswap16", expr->fn) ||
1207 1207 sym_name_is("__builtin_bswap32", expr->fn) ||
1208 1208 sym_name_is("__builtin_bswap64", expr->fn)) {
1209 1209 struct expression *arg;
1210 1210
1211 1211 arg = get_argument_from_call_expr(expr->args, 0);
1212 1212 return get_rl_sval(arg, implied, recurse_cnt, res, res_sval);
1213 1213 }
1214 1214
1215 1215 if (sym_name_is("strlen", expr->fn))
1216 1216 return handle_strlen(expr, implied, recurse_cnt, res, res_sval);
1217 1217
1218 1218 if (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY)
1219 1219 return false;
1220 1220
1221 1221 if (custom_handle_variable) {
1222 1222 rl = custom_handle_variable(expr);
1223 1223 if (rl) {
1224 1224 *res = rl;
1225 1225 return true;
1226 1226 }
1227 1227 }
1228 1228
1229 1229 /* Ugh... get_implied_return() sets *rl to NULL on failure */
1230 1230 if (get_implied_return(expr, &rl)) {
1231 1231 *res = rl;
1232 1232 return true;
1233 1233 }
1234 1234 rl = db_return_vals(expr);
1235 1235 if (rl) {
1236 1236 *res = rl;
1237 1237 return true;
1238 1238 }
1239 1239 return false;
1240 1240 }
1241 1241
1242 1242 static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1243 1243 {
1244 1244 struct range_list *rl;
1245 1245 struct symbol *type;
1246 1246 sval_t sval = {};
1247 1247
1248 1248 type = get_type(expr);
1249 1249 if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) {
1250 1250 if (sval.type)
1251 1251 *res_sval = sval_cast(type, sval);
1252 1252 else
1253 1253 *res = cast_rl(type, rl);
1254 1254 return true;
1255 1255 }
1256 1256 if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) {
1257 1257 *res = alloc_whole_rl(type);
1258 1258 return true;
1259 1259 }
1260 1260 if (implied == RL_IMPLIED && type &&
1261 1261 type_bits(type) > 0 && type_bits(type) < 32) {
1262 1262 *res = alloc_whole_rl(type);
1263 1263 return true;
1264 1264 }
1265 1265 return false;
1266 1266 }
1267 1267
1268 1268 static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1269 1269 {
1270 1270 struct expression *index;
1271 1271 struct symbol *type = expr->in;
1272 1272 struct range_list *rl;
1273 1273 struct symbol *field;
1274 1274 int offset = 0;
1275 1275 sval_t sval = { .type = ssize_t_ctype };
1276 1276 sval_t tmp_sval = {};
1277 1277
1278 1278 /*
1279 1279 * FIXME: I don't really know what I'm doing here. I wish that I
1280 1280 * could just get rid of the __builtin_offset() function and use:
1281 1281 * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead...
1282 1282 * Anyway, I have done the minimum ammount of work to get that
1283 1283 * expression to work.
1284 1284 *
1285 1285 */
1286 1286
1287 1287 if (expr->op != '.' || !expr->down ||
1288 1288 expr->down->type != EXPR_OFFSETOF ||
1289 1289 expr->down->op != '[' ||
1290 1290 !expr->down->index)
1291 1291 return false;
1292 1292
1293 1293 index = expr->down->index;
1294 1294
1295 1295 examine_symbol_type(type);
1296 1296 type = get_real_base_type(type);
1297 1297 if (!type)
1298 1298 return false;
1299 1299 field = find_identifier(expr->ident, type->symbol_list, &offset);
1300 1300 if (!field)
1301 1301 return false;
1302 1302
1303 1303 type = get_real_base_type(field);
1304 1304 if (!type || type->type != SYM_ARRAY)
1305 1305 return false;
1306 1306 type = get_real_base_type(type);
1307 1307
1308 1308 if (get_implied_value_internal(index, recurse_cnt, &sval)) {
1309 1309 res_sval->type = ssize_t_ctype;
1310 1310 res_sval->value = offset + sval.value * type_bytes(type);
1311 1311 return true;
1312 1312 }
1313 1313
1314 1314 if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval))
1315 1315 return false;
1316 1316
1317 1317 /*
1318 1318 * I'm not sure why get_rl_sval() would return an sval when
1319 1319 * get_implied_value_internal() failed but it does when I
1320 1320 * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c
1321 1321 *
1322 1322 */
1323 1323 if (tmp_sval.type) {
1324 1324 res_sval->type = ssize_t_ctype;
1325 1325 res_sval->value = offset + sval.value * type_bytes(type);
1326 1326 return true;
1327 1327 }
1328 1328
1329 1329 sval.value = type_bytes(type);
1330 1330 rl = rl_binop(rl, '*', alloc_rl(sval, sval));
1331 1331 sval.value = offset;
1332 1332 *res = rl_binop(rl, '+', alloc_rl(sval, sval));
1333 1333 return true;
1334 1334 }
1335 1335
1336 1336 static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1337 1337 {
1338 1338 struct symbol *type = get_real_base_type(expr->in);
1339 1339 struct symbol *field;
1340 1340 int offset = 0;
1341 1341
1342 1342 if (expr->op != '.' || !type || !expr->ident)
1343 1343 return false;
1344 1344
1345 1345 field = find_identifier(expr->ident, type->symbol_list, &offset);
1346 1346 if (!field)
1347 1347 return false;
1348 1348
1349 1349 res_sval->type = size_t_ctype;
1350 1350 res_sval->value = offset;
1351 1351
1352 1352 return true;
1353 1353 }
1354 1354
1355 1355 static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1356 1356 {
1357 1357 if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval))
1358 1358 return true;
1359 1359
1360 1360 if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval))
1361 1361 return true;
1362 1362
1363 1363 evaluate_expression(expr);
1364 1364 if (expr->type == EXPR_VALUE) {
1365 1365 *res_sval = sval_from_val(expr, expr->value);
1366 1366 return true;
1367 1367 }
1368 1368 return false;
1369 1369 }
1370 1370
1371 1371 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res)
1372 1372 {
1373 1373 struct range_list *rl = (void *)-1UL;
1374 1374 struct symbol *type;
1375 1375 sval_t sval = {};
1376 1376
1377 1377 type = get_type(expr);
1378 1378 expr = strip_parens(expr);
1379 1379 if (!expr)
1380 1380 return false;
1381 1381
1382 1382 if (++(*recurse_cnt) >= 200)
1383 1383 return false;
1384 1384
1385 1385 switch(expr->type) {
1386 1386 case EXPR_CAST:
1387 1387 case EXPR_FORCE_CAST:
1388 1388 case EXPR_IMPLIED_CAST:
1389 1389 handle_cast(expr, implied, recurse_cnt, &rl, &sval);
1390 1390 goto out_cast;
1391 1391 }
1392 1392
1393 1393 expr = strip_expr(expr);
1394 1394 if (!expr)
1395 1395 return false;
1396 1396
1397 1397 switch (expr->type) {
1398 1398 case EXPR_VALUE:
1399 1399 sval = sval_from_val(expr, expr->value);
1400 1400 break;
1401 1401 case EXPR_FVALUE:
1402 1402 sval = sval_from_fval(expr, expr->fvalue);
1403 1403 break;
1404 1404 case EXPR_PREOP:
1405 1405 handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval);
1406 1406 break;
1407 1407 case EXPR_POSTOP:
1408 1408 get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval);
1409 1409 break;
1410 1410 case EXPR_BINOP:
1411 1411 handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval);
1412 1412 break;
1413 1413 case EXPR_COMPARE:
1414 1414 handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval);
1415 1415 break;
1416 1416 case EXPR_LOGICAL:
1417 1417 handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval);
1418 1418 break;
1419 1419 case EXPR_PTRSIZEOF:
1420 1420 case EXPR_SIZEOF:
1421 1421 sval = handle_sizeof(expr);
1422 1422 break;
1423 1423 case EXPR_SELECT:
1424 1424 case EXPR_CONDITIONAL:
1425 1425 handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval);
1426 1426 break;
1427 1427 case EXPR_CALL:
1428 1428 handle_call_rl(expr, implied, recurse_cnt, &rl, &sval);
1429 1429 break;
1430 1430 case EXPR_STRING:
1431 1431 if (get_mtag_sval(expr, &sval))
1432 1432 break;
1433 1433 if (implied == RL_EXACT)
1434 1434 break;
1435 1435 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1436 1436 break;
1437 1437 case EXPR_OFFSETOF:
1438 1438 handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval);
1439 1439 break;
1440 1440 case EXPR_ALIGNOF:
1441 1441 evaluate_expression(expr);
1442 1442 if (expr->type == EXPR_VALUE)
1443 1443 sval = sval_from_val(expr, expr->value);
1444 1444 break;
1445 1445 default:
1446 1446 handle_variable(expr, implied, recurse_cnt, &rl, &sval);
1447 1447 }
1448 1448
1449 1449 out_cast:
1450 1450 if (rl == (void *)-1UL)
1451 1451 rl = NULL;
1452 1452
1453 1453 if (sval.type || (rl && rl_to_sval(rl, &sval))) {
1454 1454 *sval_res = sval;
1455 1455 return true;
1456 1456 }
1457 1457 if (implied == RL_EXACT)
1458 1458 return false;
1459 1459
1460 1460 if (rl) {
1461 1461 *res = rl;
1462 1462 return true;
1463 1463 }
1464 1464 if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) {
1465 1465 *res = alloc_whole_rl(type);
1466 1466 return true;
1467 1467 }
1468 1468 return false;
1469 1469 }
1470 1470
1471 1471 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
1472 1472 {
1473 1473 struct range_list *rl = NULL;
1474 1474 sval_t sval = {};
1475 1475
1476 1476 if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval))
1477 1477 return false;
1478 1478
1479 1479 if (sval.type)
1480 1480 *res = alloc_rl(sval, sval);
1481 1481 else
1482 1482 *res = rl;
1483 1483 return true;
1484 1484 }
1485 1485
1486 1486 static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res)
1487 1487 {
1488 1488 struct range_list *rl = NULL;
1489 1489 sval_t sval = {};
1490 1490 int recurse_cnt = 0;
1491 1491
1492 1492 if (get_value(expr, &sval)) {
1493 1493 *res = alloc_rl(sval, sval);
1494 1494 return true;
1495 1495 }
1496 1496
1497 1497 if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval))
1498 1498 return false;
1499 1499
1500 1500 if (sval.type)
1501 1501 *res = alloc_rl(sval, sval);
1502 1502 else
1503 1503 *res = rl;
1504 1504 return true;
1505 1505 }
1506 1506
1507 1507 struct {
1508 1508 struct expression *expr;
1509 1509 sval_t sval;
1510 1510 } cached_results[24];
1511 1511 static int cache_idx;
1512 1512
1513 1513 void clear_math_cache(void)
1514 1514 {
1515 1515 memset(cached_results, 0, sizeof(cached_results));
1516 1516 }
1517 1517
1518 1518 void set_fast_math_only(void)
1519 1519 {
1520 1520 fast_math_only++;
1521 1521 }
1522 1522
1523 1523 void clear_fast_math_only(void)
1524 1524 {
1525 1525 fast_math_only--;
1526 1526 }
1527 1527
1528 1528 /*
1529 1529 * Don't cache EXPR_VALUE because values are fast already.
1530 1530 *
1531 1531 */
1532 1532 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1533 1533 {
1534 1534 struct expression *tmp;
1535 1535 int recurse_cnt = 0;
1536 1536
1537 1537 tmp = strip_expr(expr);
1538 1538 if (!tmp || tmp->type != EXPR_VALUE)
1539 1539 return false;
1540 1540
1541 1541 return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1542 1542 }
1543 1543
1544 1544 /* returns 1 if it can get a value literal or else returns 0 */
1545 1545 int get_value(struct expression *expr, sval_t *res_sval)
1546 1546 {
1547 1547 struct range_list *(*orig_custom_fn)(struct expression *expr);
1548 1548 int recurse_cnt = 0;
1549 1549 sval_t sval = {};
1550 1550 int i;
1551 1551
1552 1552 if (get_value_literal(expr, res_sval))
1553 1553 return 1;
1554 1554
1555 1555 /*
1556 1556 * This only handles RL_EXACT because other expr statements can be
1557 1557 * different at different points. Like the list iterator, for example.
1558 1558 */
1559 1559 for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1560 1560 if (expr == cached_results[i].expr) {
1561 1561 if (cached_results[i].sval.type) {
1562 1562 *res_sval = cached_results[i].sval;
1563 1563 return true;
1564 1564 }
1565 1565 return false;
1566 1566 }
1567 1567 }
1568 1568
1569 1569 orig_custom_fn = custom_handle_variable;
1570 1570 custom_handle_variable = NULL;
1571 1571 get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval);
1572 1572
1573 1573 custom_handle_variable = orig_custom_fn;
1574 1574
1575 1575 cached_results[cache_idx].expr = expr;
1576 1576 cached_results[cache_idx].sval = sval;
1577 1577 cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1578 1578
1579 1579 if (!sval.type)
1580 1580 return 0;
1581 1581
1582 1582 *res_sval = sval;
1583 1583 return 1;
1584 1584 }
1585 1585
1586 1586 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval)
1587 1587 {
1588 1588 struct range_list *rl;
1589 1589
1590 1590 res_sval->type = NULL;
1591 1591
1592 1592 if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval))
1593 1593 return false;
1594 1594 if (!res_sval->type && !rl_to_sval(rl, res_sval))
1595 1595 return false;
1596 1596 return true;
1597 1597 }
1598 1598
↓ open down ↓ |
1598 lines elided |
↑ open up ↑ |
1599 1599 int get_implied_value(struct expression *expr, sval_t *sval)
1600 1600 {
1601 1601 struct range_list *rl;
1602 1602
1603 1603 if (!get_rl_helper(expr, RL_IMPLIED, &rl) ||
1604 1604 !rl_to_sval(rl, sval))
1605 1605 return 0;
1606 1606 return 1;
1607 1607 }
1608 1608
1609 +int get_implied_value_fast(struct expression *expr, sval_t *sval)
1610 +{
1611 + struct range_list *rl;
1612 + static int recurse;
1613 + int ret = 0;
1614 +
1615 + if (recurse)
1616 + return 0;
1617 +
1618 + recurse = 1;
1619 + set_fast_math_only();
1620 + if (get_rl_helper(expr, RL_IMPLIED, &rl) &&
1621 + rl_to_sval(rl, sval))
1622 + ret = 1;
1623 + clear_fast_math_only();
1624 + recurse = 0;
1625 +
1626 + return ret;
1627 +}
1628 +
1609 1629 int get_implied_min(struct expression *expr, sval_t *sval)
1610 1630 {
1611 1631 struct range_list *rl;
1612 1632
1613 1633 if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1614 1634 return 0;
1615 1635 *sval = rl_min(rl);
1616 1636 return 1;
1617 1637 }
1618 1638
1619 1639 int get_implied_max(struct expression *expr, sval_t *sval)
1620 1640 {
1621 1641 struct range_list *rl;
1622 1642
1623 1643 if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1624 1644 return 0;
1625 1645 *sval = rl_max(rl);
1626 1646 return 1;
1627 1647 }
1628 1648
1629 1649 int get_implied_rl(struct expression *expr, struct range_list **rl)
1630 1650 {
1631 1651 if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl)
1632 1652 return 0;
1633 1653 return 1;
1634 1654 }
1635 1655
1636 1656 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1637 1657 {
1638 1658 *rl = NULL;
1639 1659 get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl);
1640 1660 if (!*rl)
1641 1661 *rl = alloc_whole_rl(get_type(expr));
1642 1662 return 1;
1643 1663 }
1644 1664
1645 1665 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1646 1666 {
1647 1667 *rl = NULL;
1648 1668 get_rl_helper(expr, RL_ABSOLUTE, rl);
1649 1669 if (!*rl)
1650 1670 *rl = alloc_whole_rl(get_type(expr));
1651 1671 return 1;
1652 1672 }
1653 1673
1654 1674 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1655 1675 {
1656 1676 *rl = NULL;
1657 1677 get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1658 1678 if (!*rl)
1659 1679 *rl = alloc_whole_rl(get_type(expr));
1660 1680 return 1;
1661 1681 }
1662 1682
1663 1683 int custom_get_absolute_rl(struct expression *expr,
1664 1684 struct range_list *(*fn)(struct expression *expr),
1665 1685 struct range_list **rl)
1666 1686 {
1667 1687 int ret;
1668 1688
1669 1689 *rl = NULL;
1670 1690 custom_handle_variable = fn;
1671 1691 ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1672 1692 custom_handle_variable = NULL;
1673 1693 return ret;
1674 1694 }
1675 1695
1676 1696 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1677 1697 {
1678 1698 struct smatch_state *state;
1679 1699
1680 1700 state = get_state(SMATCH_EXTRA, var, sym);
1681 1701 *rl = estate_rl(state);
1682 1702 if (*rl)
1683 1703 return 1;
1684 1704 return 0;
1685 1705 }
1686 1706
1687 1707 int get_hard_max(struct expression *expr, sval_t *sval)
1688 1708 {
1689 1709 struct range_list *rl;
1690 1710
1691 1711 if (!get_rl_helper(expr, RL_HARD, &rl) || !rl)
1692 1712 return 0;
1693 1713 *sval = rl_max(rl);
1694 1714 return 1;
1695 1715 }
1696 1716
1697 1717 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1698 1718 {
1699 1719 struct range_list *rl;
1700 1720 sval_t tmp;
1701 1721
1702 1722 if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1703 1723 return 0;
1704 1724 tmp = rl_min(rl);
1705 1725 if (sval_is_negative(tmp) && sval_is_min(tmp))
1706 1726 return 0;
1707 1727 *sval = tmp;
1708 1728 return 1;
1709 1729 }
1710 1730
1711 1731 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1712 1732 {
1713 1733 struct range_list *rl;
1714 1734 sval_t max;
1715 1735
1716 1736 if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1717 1737 return 0;
1718 1738 max = rl_max(rl);
1719 1739 if (max.uvalue > INT_MAX - 10000)
1720 1740 return 0;
1721 1741 *sval = max;
1722 1742 return 1;
1723 1743 }
1724 1744
1725 1745 int get_absolute_min(struct expression *expr, sval_t *sval)
1726 1746 {
1727 1747 struct range_list *rl;
1728 1748 struct symbol *type;
1729 1749
1730 1750 type = get_type(expr);
1731 1751 if (!type)
1732 1752 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail.
1733 1753 rl = NULL;
1734 1754 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1735 1755 if (rl)
1736 1756 *sval = rl_min(rl);
1737 1757 else
1738 1758 *sval = sval_type_min(type);
1739 1759
1740 1760 if (sval_cmp(*sval, sval_type_min(type)) < 0)
1741 1761 *sval = sval_type_min(type);
1742 1762 return 1;
1743 1763 }
1744 1764
1745 1765 int get_absolute_max(struct expression *expr, sval_t *sval)
1746 1766 {
1747 1767 struct range_list *rl;
1748 1768 struct symbol *type;
1749 1769
1750 1770 type = get_type(expr);
1751 1771 if (!type)
1752 1772 type = &llong_ctype;
1753 1773 rl = NULL;
1754 1774 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1755 1775 if (rl)
1756 1776 *sval = rl_max(rl);
1757 1777 else
1758 1778 *sval = sval_type_max(type);
1759 1779
1760 1780 if (sval_cmp(sval_type_max(type), *sval) < 0)
1761 1781 *sval = sval_type_max(type);
1762 1782 return 1;
1763 1783 }
1764 1784
1765 1785 int known_condition_true(struct expression *expr)
1766 1786 {
1767 1787 sval_t tmp;
1768 1788
1769 1789 if (!expr)
1770 1790 return 0;
1771 1791
1772 1792 if (__inline_fn && get_param_num(expr) >= 0) {
1773 1793 if (get_implied_value(expr, &tmp) && tmp.value)
1774 1794 return 1;
1775 1795 return 0;
1776 1796 }
1777 1797
1778 1798 if (get_value(expr, &tmp) && tmp.value)
1779 1799 return 1;
1780 1800
1781 1801 return 0;
1782 1802 }
1783 1803
1784 1804 int known_condition_false(struct expression *expr)
1785 1805 {
1786 1806 sval_t tmp;
1787 1807
1788 1808 if (!expr)
1789 1809 return 0;
1790 1810
1791 1811 if (__inline_fn && get_param_num(expr) >= 0) {
1792 1812 if (get_implied_value(expr, &tmp) && tmp.value == 0)
1793 1813 return 1;
1794 1814 return 0;
1795 1815 }
1796 1816
1797 1817 if (expr_is_zero(expr))
1798 1818 return 1;
1799 1819
1800 1820 return 0;
1801 1821 }
1802 1822
1803 1823 int implied_condition_true(struct expression *expr)
1804 1824 {
1805 1825 sval_t tmp;
1806 1826
1807 1827 if (!expr)
1808 1828 return 0;
1809 1829
1810 1830 if (known_condition_true(expr))
1811 1831 return 1;
1812 1832 if (get_implied_value(expr, &tmp) && tmp.value)
1813 1833 return 1;
1814 1834
1815 1835 if (expr->type == EXPR_POSTOP)
1816 1836 return implied_condition_true(expr->unop);
1817 1837
1818 1838 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1819 1839 return implied_not_equal(expr->unop, 1);
1820 1840 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1821 1841 return implied_not_equal(expr->unop, -1);
1822 1842
1823 1843 expr = strip_expr(expr);
1824 1844 switch (expr->type) {
1825 1845 case EXPR_COMPARE:
1826 1846 if (do_comparison(expr) == 1)
1827 1847 return 1;
1828 1848 break;
1829 1849 case EXPR_PREOP:
1830 1850 if (expr->op == '!') {
1831 1851 if (implied_condition_false(expr->unop))
1832 1852 return 1;
1833 1853 break;
1834 1854 }
1835 1855 break;
1836 1856 default:
1837 1857 if (implied_not_equal(expr, 0) == 1)
1838 1858 return 1;
1839 1859 break;
1840 1860 }
1841 1861 return 0;
1842 1862 }
1843 1863
1844 1864 int implied_condition_false(struct expression *expr)
1845 1865 {
1846 1866 struct expression *tmp;
1847 1867 sval_t sval;
1848 1868
1849 1869 if (!expr)
1850 1870 return 0;
1851 1871
1852 1872 if (known_condition_false(expr))
1853 1873 return 1;
1854 1874
1855 1875 switch (expr->type) {
1856 1876 case EXPR_COMPARE:
1857 1877 if (do_comparison(expr) == 2)
1858 1878 return 1;
1859 1879 case EXPR_PREOP:
1860 1880 if (expr->op == '!') {
1861 1881 if (implied_condition_true(expr->unop))
1862 1882 return 1;
1863 1883 break;
1864 1884 }
1865 1885 tmp = strip_expr(expr);
1866 1886 if (tmp != expr)
1867 1887 return implied_condition_false(tmp);
1868 1888 break;
1869 1889 default:
1870 1890 if (get_implied_value(expr, &sval) && sval.value == 0)
1871 1891 return 1;
1872 1892 break;
1873 1893 }
1874 1894 return 0;
1875 1895 }
1876 1896
1877 1897
↓ open down ↓ |
259 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX