1 /*
2 * Copyright (C) 2012 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 /*
19 * Basically the point of sval is that it can hold both ULLONG_MAX and
20 * LLONG_MIN. If it is an unsigned type then we use sval.uvalue or if it is
21 * signed we use sval.value.
22 *
23 * I considered just using one bit to store whether the value was signed vs
24 * unsigned but I think it might help to have the type information so we know
25 * how to do type promotion.
26 *
27 */
28
29 #include "smatch.h"
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
32
33 __ALLOCATOR(sval_t, "svals", sval);
34
35 sval_t *sval_alloc(sval_t sval)
36 {
37 sval_t *ret;
38
39 ret = __alloc_sval(0);
40 *ret = sval;
41 return ret;
42 }
43
44 sval_t *sval_alloc_permanent(sval_t sval)
45 {
46 sval_t *ret;
47
48 ret = malloc(sizeof(*ret));
49 *ret = sval;
50 return ret;
51 }
52
53 sval_t sval_blank(struct expression *expr)
54 {
55 sval_t ret;
56
57 ret.type = get_type(expr);
58 if (!ret.type)
59 ret.type = &int_ctype;
60 ret.value = 123456789;
61
62 return ret;
63 }
64
65 sval_t sval_type_val(struct symbol *type, long long val)
66 {
67 sval_t ret;
68
69 if (!type)
70 type = &llong_ctype;
71
72 ret.type = type;
73 ret.value = val;
74 return ret;
75 }
76
77 sval_t sval_from_val(struct expression *expr, long long val)
78 {
79 sval_t ret;
80
81 ret = sval_blank(expr);
82 ret.value = val;
83 ret = sval_cast(get_type(expr), ret);
84
85 return ret;
86 }
87
88 int sval_is_ptr(sval_t sval)
89 {
90 if (!sval.type)
91 return 0;
92 return (sval.type->type == SYM_PTR || sval.type->type == SYM_ARRAY);
93 }
94
95 int sval_unsigned(sval_t sval)
96 {
97 if (is_ptr_type(sval.type))
98 return true;
99 return type_unsigned(sval.type);
100 }
101
102 int sval_signed(sval_t sval)
103 {
104 return !type_unsigned(sval.type);
105 }
106
107 int sval_bits(sval_t sval)
108 {
109 return type_bits(sval.type);
110 }
111
112 int sval_bits_used(sval_t sval)
113 {
114 int i;
115
116 for (i = 64; i >= 1; i--) {
117 if (sval.uvalue & (1ULL << (i - 1)))
118 return i;
119 }
120 return 0;
121 }
122
123 int sval_is_negative(sval_t sval)
124 {
125 if (type_unsigned(sval.type))
126 return 0;
127 if (sval.value < 0)
128 return 1;
129 return 0;
130 }
131
132 int sval_is_positive(sval_t sval)
133 {
134 return !sval_is_negative(sval);
135 }
136
137 int sval_is_min(sval_t sval)
138 {
139 sval_t min = sval_type_min(sval.type);
140
141 if (sval_unsigned(sval)) {
142 if (sval.uvalue == 0)
143 return 1;
144 return 0;
145 }
146 /* return true for less than min as well */
147 return (sval.value <= min.value);
148 }
149
150 int sval_is_max(sval_t sval)
151 {
152 sval_t max = sval_type_max(sval.type);
153
154 if (sval_unsigned(sval))
155 return (sval.uvalue >= max.value);
156 return (sval.value >= max.value);
157 }
158
159 int sval_is_a_min(sval_t sval)
160 {
161 if (sval_is_min(sval))
162 return 1;
163 if (sval_signed(sval) && sval.value == SHRT_MIN)
164 return 1;
165 if (sval_signed(sval) && sval.value == INT_MIN)
166 return 1;
167 if (sval_signed(sval) && sval.value == LLONG_MIN)
168 return 1;
169 return 0;
170 }
171
172 int sval_is_a_max(sval_t sval)
173 {
174 if (sval_is_max(sval))
175 return 1;
176 if (sval.uvalue == SHRT_MAX)
177 return 1;
178 if (sval.uvalue == INT_MAX)
179 return 1;
180 if (sval.uvalue == LLONG_MAX)
181 return 1;
182 if (sval.uvalue == USHRT_MAX)
183 return 1;
184 if (sval.uvalue == UINT_MAX)
185 return 1;
186 if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX)
187 return 1;
188 if (sval.value > valid_ptr_max - 1000 &&
189 sval.value < valid_ptr_max + 1000)
190 return 1;
191 return 0;
192 }
193
194 int sval_is_negative_min(sval_t sval)
195 {
196 if (!sval_is_negative(sval))
197 return 0;
198 return sval_is_min(sval);
199 }
200
201 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
202 {
203 sval_t one_cast, two_cast;
204
205 one_cast = sval_cast(type, one);
206 two_cast = sval_cast(type, two);
207 return sval_cmp(one_cast, two_cast);
208 }
209
210 int sval_cmp_val(sval_t one, long long val)
211 {
212 sval_t sval;
213
214 sval = sval_type_val(&llong_ctype, val);
215 return sval_cmp(one, sval);
216 }
217
218 sval_t sval_min(sval_t one, sval_t two)
219 {
220 if (sval_cmp(one, two) > 0)
221 return two;
222 return one;
223 }
224
225 sval_t sval_max(sval_t one, sval_t two)
226 {
227 if (sval_cmp(one, two) < 0)
228 return two;
229 return one;
230 }
231
232 int sval_too_low(struct symbol *type, sval_t sval)
233 {
234 if (sval_is_negative(sval) && type_unsigned(type))
235 return 1;
236 if (type_signed(type) && sval_unsigned(sval))
237 return 0;
238 if (type_signed(sval.type) &&
239 sval.value < sval_type_min(type).value)
240 return 1;
241 if (sval_cmp(sval, sval_type_min(type)) < 0)
242 return 1;
243 return 0;
244 }
245
246 int sval_too_high(struct symbol *type, sval_t sval)
247 {
248 if (sval_is_negative(sval))
249 return 0;
250 if (sval.uvalue > sval_type_max(type).uvalue)
251 return 1;
252 return 0;
253 }
254
255 int sval_fits(struct symbol *type, sval_t sval)
256 {
257 if (sval_too_low(type, sval))
258 return 0;
259 if (sval_too_high(type, sval))
260 return 0;
261 return 1;
262 }
263
264 sval_t sval_cast(struct symbol *type, sval_t sval)
265 {
266 sval_t ret;
267
268 if (!type)
269 type = &int_ctype;
270
271 ret.type = type;
272 switch (sval_bits(ret)) {
273 case 1:
274 ret.value = !!sval.value;
275 break;
276 case 8:
277 if (sval_unsigned(ret))
278 ret.value = (long long)(unsigned char)sval.value;
279 else
280 ret.value = (long long)(char)sval.value;
281 break;
282 case 16:
283 if (sval_unsigned(ret))
284 ret.value = (long long)(unsigned short)sval.value;
285 else
286 ret.value = (long long)(short)sval.value;
287 break;
288 case 32:
289 if (sval_unsigned(ret))
290 ret.value = (long long)(unsigned int)sval.value;
291 else
292 ret.value = (long long)(int)sval.value;
293 break;
294 default:
295 ret.value = sval.value;
296 }
297 return ret;
298
299 }
300
301 sval_t sval_preop(sval_t sval, int op)
302 {
303 switch (op) {
304 case '!':
305 sval.value = !sval.value;
306 break;
307 case '~':
308 sval.value = ~sval.value;
309 sval = sval_cast(sval.type, sval);
310 break;
311 case '-':
312 sval.value = -sval.value;
313 sval = sval_cast(sval.type, sval);
314 break;
315 }
316 return sval;
317 }
318
319 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
320 {
321 sval_t ret;
322
323 ret.type = type;
324 switch (op) {
325 case '*':
326 ret.uvalue = left.uvalue * right.uvalue;
327 break;
328 case '/':
329 if (right.uvalue == 0) {
330 sm_debug("%s: divide by zero", __func__);
331 ret.uvalue = 123456789;
332 } else {
333 ret.uvalue = left.uvalue / right.uvalue;
334 }
335 break;
336 case '+':
337 ret.uvalue = left.uvalue + right.uvalue;
338 break;
339 case '-':
340 ret.uvalue = left.uvalue - right.uvalue;
341 break;
342 case '%':
343 if (right.uvalue == 0) {
344 sm_perror(" %s: MOD by zero", __func__);
345 ret.uvalue = 123456789;
346 } else {
347 ret.uvalue = left.uvalue % right.uvalue;
348 }
349 break;
350 case '|':
351 ret.uvalue = left.uvalue | right.uvalue;
352 break;
353 case '&':
354 ret.uvalue = left.uvalue & right.uvalue;
355 break;
356 case SPECIAL_RIGHTSHIFT:
357 ret.uvalue = left.uvalue >> right.uvalue;
358 break;
359 case SPECIAL_LEFTSHIFT:
360 ret.uvalue = left.uvalue << right.uvalue;
361 break;
362 case '^':
363 ret.uvalue = left.uvalue ^ right.uvalue;
364 break;
365 default:
366 sm_perror(" %s: unhandled binop %s", __func__,
367 show_special(op));
368 ret.uvalue = 1234567;
369 }
370 return ret;
371 }
372
373
374 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
375 {
376 sval_t ret;
377
378 ret.type = type;
379 switch (op) {
380 case '*':
381 ret.value = left.value * right.value;
382 break;
383 case '/':
384 if (right.value == 0) {
385 sm_debug("%s: divide by zero", __func__);
386 ret.value = 123456789;
387 } else if (left.value == LLONG_MIN && right.value == -1) {
388 sm_debug("%s: invalid divide LLONG_MIN/-1", __func__);
389 ret.value = 12345678;
390 } else {
391 ret.value = left.value / right.value;
392 }
393 break;
394 case '+':
395 ret.value = left.value + right.value;
396 break;
397 case '-':
398 ret.value = left.value - right.value;
399 break;
400 case '%':
401 if (right.value == 0) {
402 sm_perror(" %s: MOD by zero", __func__);
403 ret.value = 123456789;
404 } else {
405 ret.value = left.value % right.value;
406 }
407 break;
408 case '|':
409 ret.value = left.value | right.value;
410 break;
411 case '&':
412 ret.value = left.value & right.value;
413 break;
414 case SPECIAL_RIGHTSHIFT:
415 ret.value = left.value >> right.value;
416 break;
417 case SPECIAL_LEFTSHIFT:
418 ret.value = left.value << right.value;
419 break;
420 case '^':
421 ret.value = left.value ^ right.value;
422 break;
423 default:
424 sm_perror(" %s: unhandled binop %s", __func__,
425 show_special(op));
426 ret.value = 1234567;
427 }
428 return ret;
429 }
430
431 static sval_t ptr_binop(struct symbol *type, sval_t left, int op, sval_t right)
432 {
433 sval_t ret;
434 int align;
435
436 if (op != '+' && op != '-')
437 return sval_binop_unsigned(type, left, op, right);
438
439 ret.type = type;
440 if (type->type == SYM_PTR)
441 type = get_real_base_type(type);
442 align = type->ctype.alignment;
443 if (align <= 0)
444 align = 1;
445
446 if (op == '+') {
447 if (type_is_ptr(left.type))
448 ret.value = left.value + right.value * align;
449 else
450 ret.value = left.value * align + right.value;
451 } else {
452 if (!type_is_ptr(left.type)) {
453 left.value = -left.value;
454 ret = ptr_binop(type, left, '+', right);
455 } else if (!type_is_ptr(right.type)) {
456 right.value = -right.value;
457 ret = ptr_binop(type, left, '+', right);
458 } else {
459 ret.value = (left.value - right.value) / align;
460 }
461 }
462
463 if (op == '-')
464 ret.type = ssize_t_ctype;
465 return ret;
466 }
467
468 sval_t sval_binop(sval_t left, int op, sval_t right)
469 {
470 struct symbol *type;
471 sval_t ret;
472
473 type = get_promoted_type(left.type, right.type);
474
475 if (type_is_ptr(type))
476 ret = ptr_binop(type, left, op, right);
477 else if (type_unsigned(type))
478 ret = sval_binop_unsigned(type, left, op, right);
479 else
480 ret = sval_binop_signed(type, left, op, right);
481 return sval_cast(type, ret);
482 }
483
484 int sval_unop_overflows(sval_t sval, int op)
485 {
486 if (op != '-')
487 return 0;
488 if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN)
489 return 1;
490 if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN)
491 return 1;
492 if (sval_is_negative(sval))
493 return 0;
494 if (sval_signed(sval))
495 return 0;
496 if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX)
497 return 1;
498 if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX)
499 return 1;
500 return 0;
501 }
502
503 int sval_binop_overflows(sval_t left, int op, sval_t right)
504 {
505 struct symbol *type;
506 sval_t max, min;
507
508 type = left.type;
509 if (type_positive_bits(right.type) > type_positive_bits(left.type))
510 type = right.type;
511 if (type_positive_bits(type) < 31)
512 type = &int_ctype;
513
514 max = sval_type_max(type);
515 min = sval_type_min(type);
516
517 switch (op) {
518 case '+':
519 if (sval_is_negative(left) && sval_is_negative(right)) {
520 if (left.value < min.value + right.value)
521 return 1;
522 return 0;
523 }
524 if (sval_is_negative(left) || sval_is_negative(right))
525 return 0;
526 if (left.uvalue > max.uvalue - right.uvalue)
527 return 1;
528 return 0;
529 case '*':
530 if (type_signed(type)) {
531 if (left.value == 0 || right.value == 0)
532 return 0;
533 if (left.value > max.value / right.value)
534 return 1;
535 if (left.value == -1 || right.value == -1)
536 return 0;
537 return left.value != left.value * right.value / right.value;
538
539 }
540 return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue;
541 case '-':
542 if (type_unsigned(type)) {
543 if (sval_cmp(left, right) < 0)
544 return 1;
545 return 0;
546 }
547 if (sval_is_negative(left) && sval_is_negative(right))
548 return 0;
549
550 if (sval_is_negative(left)) {
551 if (left.value < min.value + right.value)
552 return 1;
553 return 0;
554 }
555 if (sval_is_negative(right)) {
556 if (right.value == min.value)
557 return 1;
558 right = sval_preop(right, '-');
559 if (sval_binop_overflows(left, '+', right))
560 return 1;
561 return 0;
562 }
563 return 0;
564 case SPECIAL_LEFTSHIFT:
565 if (sval_cmp(left, sval_binop(max, invert_op(op), right)) > 0)
566 return 1;
567 return 0;
568 }
569 return 0;
570 }
571
572 int sval_binop_overflows_no_sign(sval_t left, int op, sval_t right)
573 {
574
575 struct symbol *type;
576
577 type = left.type;
578 if (type_positive_bits(right.type) > type_positive_bits(left.type))
579 type = right.type;
580 if (type_positive_bits(type) <= 31)
581 type = &uint_ctype;
582 else
583 type = &ullong_ctype;
584
585 left = sval_cast(type, left);
586 right = sval_cast(type, right);
587 return sval_binop_overflows(left, op, right);
588 }
589
590 int find_first_zero_bit(unsigned long long uvalue)
591 {
592 int i;
593
594 for (i = 0; i < 64; i++) {
595 if (!(uvalue & (1ULL << i)))
596 return i;
597 }
598 return i;
599 }
600
601 int sm_fls64(unsigned long long uvalue)
602 {
603 int high_bit = 0;
604
605 while (uvalue) {
606 uvalue >>= 1;
607 high_bit++;
608 }
609
610 return high_bit;
611 }
612
613 unsigned long long fls_mask(unsigned long long uvalue)
614 {
615 int high_bit = 0;
616
617 high_bit = sm_fls64(uvalue);
618 if (high_bit == 0)
619 return 0;
620
621 return ((unsigned long long)-1) >> (64 - high_bit);
622 }
623
624 unsigned long long sval_fls_mask(sval_t sval)
625 {
626 return fls_mask(sval.uvalue);
627 }
628
629 const char *sval_to_str(sval_t sval)
630 {
631 char buf[30];
632
633 if (sval_is_ptr(sval) && sval.value == valid_ptr_max)
634 return "ptr_max";
635 if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
636 return "u64max";
637 if (sval_unsigned(sval) && sval.value == UINT_MAX)
638 return "u32max";
639 if (sval.value == USHRT_MAX)
640 return "u16max";
641
642 if (sval_signed(sval) && sval.value == LLONG_MAX)
643 return "s64max";
644 if (sval.value == INT_MAX)
645 return "s32max";
646 if (sval.value == SHRT_MAX)
647 return "s16max";
648
649 if (sval_signed(sval) && sval.value == SHRT_MIN)
650 return "s16min";
651 if (sval_signed(sval) && sval.value == INT_MIN)
652 return "s32min";
653 if (sval_signed(sval) && sval.value == LLONG_MIN)
654 return "s64min";
655
656 if (sval_unsigned(sval))
657 snprintf(buf, sizeof(buf), "%llu", sval.value);
658 else if (sval.value < 0)
659 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
660 else
661 snprintf(buf, sizeof(buf), "%lld", sval.value);
662
663 return alloc_sname(buf);
664 }
665
666 const char *sval_to_str_or_err_ptr(sval_t sval)
667 {
668 char buf[12];
669
670 if (option_project != PROJ_KERNEL ||
671 !is_ptr_type(sval.type))
672 return sval_to_str(sval);
673
674 if (sval.uvalue >= -4905ULL) {
675 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
676 return alloc_sname(buf);
677 }
678
679 return sval_to_str(sval);
680 }
681
682 const char *sval_to_numstr(sval_t sval)
683 {
684 char buf[30];
685
686 if (sval_unsigned(sval))
687 snprintf(buf, sizeof(buf), "%llu", sval.value);
688 else if (sval.value < 0)
689 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
690 else
691 snprintf(buf, sizeof(buf), "%lld", sval.value);
692
693 return alloc_sname(buf);
694 }
695
696 sval_t ll_to_sval(long long val)
697 {
698 sval_t ret;
699
700 ret.type = &llong_ctype;
701 ret.value = val;
702 return ret;
703 }
704
705 static void free_svals(struct symbol *sym)
706 {
707 if (__inline_fn)
708 return;
709 clear_sval_alloc();
710 }
711
712 void register_sval(int my_id)
713 {
714 add_hook(&free_svals, AFTER_FUNC_HOOK);
715 }