9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 "permanent ranges", perm_data_range);
27 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
28
29 static bool is_err_ptr(sval_t sval)
30 {
31 if (option_project != PROJ_KERNEL)
32 return false;
33 if (!type_is_ptr(sval.type))
34 return false;
35 if (sval.uvalue < -4095ULL)
36 return false;
37 return true;
38 }
39
40 static char *get_err_pointer_str(struct data_range *drange)
41 {
42 static char buf[20];
43
44 /*
45 * The kernel has error pointers where you do essentially:
46 *
47 * return (void *)(unsigned long)-12;
48 *
49 * But what I want here is to print -12 instead of the unsigned version
232 *comparison = SPECIAL_GTE;
233 c++;
234 } else {
235 *comparison = '>';
236 }
237 } else if (*c == '!') {
238 c++;
239 c++;
240 *comparison = SPECIAL_NOTEQUAL;
241 } else if (*c == '$') {
242 *comparison = SPECIAL_EQUAL;
243 } else {
244 return 0;
245 }
246
247 if (*c != '$')
248 return 0;
249 c++;
250
251 param = strtoll(c, (char **)&c, 10);
252 if (*c == ',' || *c == ']')
253 c++; /* skip the ']' character */
254 if (endp)
255 *endp = (char *)c;
256
257 if (!call)
258 return 0;
259 *arg = get_argument_from_call_expr(call->args, param);
260 if (!*arg)
261 return 0;
262 if (*c == '-' && *(c + 1) == '>') {
263 char buf[256];
264 int n;
265
266 n = snprintf(buf, sizeof(buf), "$%s", c);
267 if (n >= sizeof(buf))
268 return 0;
269 if (buf[n - 1] == ']')
270 buf[n - 1] = '\0';
271 *arg = gen_expression_from_key(*arg, buf);
325 static sval_t add_one(sval_t sval)
326 {
327 sval.value++;
328 return sval;
329 }
330
331 static sval_t sub_one(sval_t sval)
332 {
333 sval.value--;
334 return sval;
335 }
336
337 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
338 {
339 struct range_list *left_orig = *rl;
340 struct range_list *right_orig = right;
341 struct range_list *ret_rl = *rl;
342 struct symbol *cast_type;
343 sval_t min, max;
344
345 cast_type = rl_type(left_orig);
346 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
347 cast_type = rl_type(right_orig);
348 if (sval_type_max(cast_type).uvalue < INT_MAX)
349 cast_type = &int_ctype;
350
351 min = sval_type_min(cast_type);
352 max = sval_type_max(cast_type);
353 left_orig = cast_rl(cast_type, left_orig);
354 right_orig = cast_rl(cast_type, right_orig);
355
356 switch (comparison) {
357 case '<':
358 case SPECIAL_UNSIGNED_LT:
359 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
360 break;
361 case SPECIAL_LTE:
362 case SPECIAL_UNSIGNED_LTE:
363 if (!sval_is_max(rl_max(right_orig)))
364 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
377 break;
378 case SPECIAL_NOTEQUAL:
379 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
380 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
381 break;
382 default:
383 sm_perror("unhandled comparison %s", show_special(comparison));
384 return;
385 }
386
387 *rl = cast_rl(rl_type(*rl), ret_rl);
388 }
389
390 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
391 {
392 struct symbol *type;
393 struct expression *arg;
394 struct range_list *casted_start, *right_orig;
395 int comparison;
396
397 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
398 return start_rl;
399
400 if (!get_implied_rl(arg, &right_orig))
401 return start_rl;
402
403 type = &int_ctype;
404 if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
405 type = rl_type(start_rl);
406 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
407 type = rl_type(right_orig);
408
409 casted_start = cast_rl(type, start_rl);
410 right_orig = cast_rl(type, right_orig);
411
412 filter_by_comparison(&casted_start, comparison, right_orig);
413 return cast_rl(rl_type(start_rl), casted_start);
414 }
415
416 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
474 *endp = c;
475 return ret;
476 }
477
478 static const char *jump_to_call_math(const char *value)
479 {
480 const char *c = value;
481
482 while (*c && *c != '[')
483 c++;
484
485 if (!*c)
486 return NULL;
487 c++;
488 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
489 return NULL;
490
491 return c;
492 }
493
494 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
495 {
496 struct range_list *rl_tmp = NULL;
497 sval_t prev_min, min, max;
498 const char *c;
499
500 prev_min = sval_type_min(type);
501 min = sval_type_min(type);
502 max = sval_type_max(type);
503 c = str;
504 while (*c != '\0' && *c != '[') {
505 if (*c == '+') {
506 if (sval_cmp(min, sval_type_min(type)) != 0)
507 min = max;
508 max = sval_type_max(type);
509 add_range_t(type, &rl_tmp, min, max);
510 break;
511 }
512 if (*c == '(')
513 c++;
575
576 if (strcmp(value, "empty") == 0)
577 return;
578
579 if (strncmp(value, "[==$", 4) == 0) {
580 struct expression *arg;
581 int comparison;
582
583 if (!str_to_comparison_arg(value, call, &comparison, &arg))
584 return;
585 if (!get_implied_rl(arg, &rl))
586 return;
587 goto cast;
588 }
589
590 str_to_rl_helper(call, type, value, &c, &rl);
591 if (*c == '\0')
592 goto cast;
593
594 call_math = jump_to_call_math(value);
595 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
596 rl = rl_intersection(rl, math_rl);
597 goto cast;
598 }
599
600 /*
601 * For now if we already tried to handle the call math and couldn't
602 * figure it out then bail.
603 */
604 if (jump_to_call_math(c) == c + 1)
605 goto cast;
606
607 rl = filter_by_comparison_call(c, call, &c, rl);
608
609 cast:
610 rl = cast_rl(type, rl);
611 dinfo->value_ranges = rl;
612 }
613
614 static int rl_is_sane(struct range_list *rl)
634 struct data_info dinfo = {};
635
636 str_to_dinfo(NULL, type, value, &dinfo);
637 if (!rl_is_sane(dinfo.value_ranges))
638 dinfo.value_ranges = alloc_whole_rl(type);
639 *rl = dinfo.value_ranges;
640 }
641
642 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
643 {
644 struct data_info dinfo = {};
645
646 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
647 *rl = dinfo.value_ranges;
648 }
649
650 int is_whole_rl(struct range_list *rl)
651 {
652 struct data_range *drange;
653
654 if (ptr_list_empty(rl))
655 return 0;
656 drange = first_ptr_list((struct ptr_list *)rl);
657 if (sval_is_min(drange->min) && sval_is_max(drange->max))
658 return 1;
659 return 0;
660 }
661
662 int is_unknown_ptr(struct range_list *rl)
663 {
664 struct data_range *drange;
665 int cnt = 0;
666
667 if (is_whole_rl(rl))
668 return 1;
669
670 FOR_EACH_PTR(rl, drange) {
671 if (++cnt >= 3)
672 return 0;
673 if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
674 sval_cmp(drange->max, valid_ptr_max_sval) == 0)
675 return 1;
676 } END_FOR_EACH_PTR(drange);
677
678 return 0;
679 }
680
681 int is_whole_rl_non_zero(struct range_list *rl)
682 {
683 struct data_range *drange;
684
685 if (ptr_list_empty(rl))
686 return 0;
687 drange = first_ptr_list((struct ptr_list *)rl);
688 if (sval_unsigned(drange->min) &&
689 drange->min.value == 1 &&
690 sval_is_max(drange->max))
691 return 1;
692 if (!sval_is_min(drange->min) || drange->max.value != -1)
693 return 0;
694 drange = last_ptr_list((struct ptr_list *)rl);
695 if (drange->min.value != 1 || !sval_is_max(drange->max))
696 return 0;
697 return 1;
698 }
699
700 sval_t rl_min(struct range_list *rl)
701 {
702 struct data_range *drange;
703 sval_t ret;
704
705 ret.type = &llong_ctype;
706 ret.value = LLONG_MIN;
707 if (ptr_list_empty(rl))
708 return ret;
709 drange = first_ptr_list((struct ptr_list *)rl);
710 return drange->min;
711 }
712
713 sval_t rl_max(struct range_list *rl)
714 {
715 struct data_range *drange;
716 sval_t ret;
717
718 ret.type = &llong_ctype;
719 ret.value = LLONG_MAX;
720 if (ptr_list_empty(rl))
721 return ret;
722 drange = last_ptr_list((struct ptr_list *)rl);
723 return drange->max;
724 }
725
726 int rl_to_sval(struct range_list *rl, sval_t *sval)
727 {
728 sval_t min, max;
729
730 if (!rl)
731 return 0;
732
733 min = rl_min(rl);
734 max = rl_max(rl);
735 if (sval_cmp(min, max) != 0)
736 return 0;
737 *sval = min;
738 return 1;
739 }
740
1173 sm_perror("unhandled comparison %d", comparison);
1174 return 0;
1175 }
1176 return 0;
1177 }
1178
1179 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1180 {
1181 if (left)
1182 return false_comparison_range_sval(var, comparison, val);
1183 else
1184 return false_comparison_range_sval(val, comparison, var);
1185 }
1186
1187 int possibly_true(struct expression *left, int comparison, struct expression *right)
1188 {
1189 struct range_list *rl_left, *rl_right;
1190 struct data_range *tmp_left, *tmp_right;
1191 struct symbol *type;
1192
1193 if (!get_implied_rl(left, &rl_left))
1194 return 1;
1195 if (!get_implied_rl(right, &rl_right))
1196 return 1;
1197
1198 type = rl_type(rl_left);
1199 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1200 type = rl_type(rl_right);
1201 if (type_positive_bits(type) < 31)
1202 type = &int_ctype;
1203
1204 rl_left = cast_rl(type, rl_left);
1205 rl_right = cast_rl(type, rl_right);
1206
1207 FOR_EACH_PTR(rl_left, tmp_left) {
1208 FOR_EACH_PTR(rl_right, tmp_right) {
1209 if (true_comparison_range(tmp_left, comparison, tmp_right))
1210 return 1;
1211 } END_FOR_EACH_PTR(tmp_right);
1212 } END_FOR_EACH_PTR(tmp_left);
1230 if (type_positive_bits(type) < 31)
1231 type = &int_ctype;
1232
1233 rl_left = cast_rl(type, rl_left);
1234 rl_right = cast_rl(type, rl_right);
1235
1236 FOR_EACH_PTR(rl_left, tmp_left) {
1237 FOR_EACH_PTR(rl_right, tmp_right) {
1238 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1239 return 1;
1240 } END_FOR_EACH_PTR(tmp_right);
1241 } END_FOR_EACH_PTR(tmp_left);
1242 return 0;
1243 }
1244
1245 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1246 {
1247 struct data_range *left_tmp, *right_tmp;
1248 struct symbol *type;
1249
1250 if (!left_ranges || !right_ranges)
1251 return 1;
1252
1253 type = rl_type(left_ranges);
1254 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1255 type = rl_type(right_ranges);
1256 if (type_positive_bits(type) < 31)
1257 type = &int_ctype;
1258
1259 left_ranges = cast_rl(type, left_ranges);
1260 right_ranges = cast_rl(type, right_ranges);
1261
1262 FOR_EACH_PTR(left_ranges, left_tmp) {
1263 FOR_EACH_PTR(right_ranges, right_tmp) {
1264 if (true_comparison_range(left_tmp, comparison, right_tmp))
1265 return 1;
1266 } END_FOR_EACH_PTR(right_tmp);
1267 } END_FOR_EACH_PTR(left_tmp);
1268 return 0;
1269 }
1270
1271 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1272 {
1273 struct data_range *left_tmp, *right_tmp;
1274 struct symbol *type;
1275
1276 if (!left_ranges || !right_ranges)
1277 return 1;
1278
1279 type = rl_type(left_ranges);
1280 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1281 type = rl_type(right_ranges);
1282 if (type_positive_bits(type) < 31)
1283 type = &int_ctype;
1284
1285 left_ranges = cast_rl(type, left_ranges);
1286 right_ranges = cast_rl(type, right_ranges);
1287
1288 FOR_EACH_PTR(left_ranges, left_tmp) {
1289 FOR_EACH_PTR(right_ranges, right_tmp) {
1290 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1291 return 1;
1292 } END_FOR_EACH_PTR(right_tmp);
1293 } END_FOR_EACH_PTR(left_tmp);
1294 return 0;
1295 }
1296
1830 zero.uvalue = 0;
1831 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1832
1833 return cast_rl(rl_type(left), alloc_rl(zero, max));
1834 }
1835
1836 static sval_t sval_lowest_set_bit(sval_t sval)
1837 {
1838 sval_t ret = { .type = sval.type };
1839 int i;
1840
1841 for (i = 0; i < 64; i++) {
1842 if (sval.uvalue & 1ULL << i) {
1843 ret.uvalue = (1ULL << i);
1844 return ret;
1845 }
1846 }
1847 return ret;
1848 }
1849
1850 static struct range_list *handle_AND_rl_sval(struct range_list *rl, sval_t sval)
1851 {
1852 struct range_list *known_rl;
1853 sval_t zero = { 0 };
1854 sval_t min;
1855
1856 zero.type = sval.type;
1857 zero.value = 0;
1858
1859 if (sm_fls64(rl_max(rl).uvalue) < find_first_zero_bit(sval.uvalue) &&
1860 sm_fls64(rl_min(rl).uvalue) < find_first_zero_bit(sval.uvalue))
1861 return rl;
1862
1863 min = sval_lowest_set_bit(sval);
1864
1865 if (min.value != 0) {
1866 sval_t max, mod;
1867
1868 max = rl_max(rl);
1869 mod = sval_binop(max, '%', min);
1870 if (mod.value) {
1871 max = sval_binop(max, '-', mod);
1872 max.value++;
1873 if (max.value > 0 && sval_cmp(max, rl_max(rl)) < 0)
1874 rl = remove_range(rl, max, rl_max(rl));
1875 }
1876 }
1877
1878 known_rl = alloc_rl(min, sval);
1879
1880 rl = rl_intersection(rl, known_rl);
1881 zero = rl_min(rl);
1882 zero.value = 0;
1883 add_range(&rl, zero, zero);
1884
1885 return rl;
1886 }
1887
1888 static struct range_list *fudge_AND_rl(struct range_list *rl)
1889 {
1890 struct range_list *ret;
1891 sval_t min;
1892
1893 min = sval_lowest_set_bit(rl_min(rl));
1894 ret = clone_rl(rl);
1895 add_range(&ret, min, rl_min(rl));
1896
1897 return ret;
1898 }
1899
1900 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1901 {
1902 sval_t sval, zero;
1903 struct range_list *rl;
1904
1905 if (rl_to_sval(left, &sval))
1906 return handle_AND_rl_sval(right, sval);
1907 if (rl_to_sval(right, &sval))
1908 return handle_AND_rl_sval(left, sval);
1909
1910 left = fudge_AND_rl(left);
1911 right = fudge_AND_rl(right);
1912
1913 rl = rl_intersection(left, right);
1914 zero = rl_min(rl);
1915 zero.value = 0;
1916 add_range(&rl, zero, zero);
1917
1918 return rl;
1919 }
1920
1921 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
1922 {
1923 struct range_list *left;
1924 struct data_range *tmp;
1925 struct range_list *ret = NULL;
1926 sval_t zero = { .type = rl_type(left_orig), };
1927 sval_t shift, min, max;
1928 bool add_zero = false;
1929
1930 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1931 return NULL;
1932 if (shift.value == 0)
1933 return left_orig;
2131 case SPECIAL_UNSIGNED_GT:
2132 left_true = remove_range(left_orig, min, rl_min(right_orig));
2133 if (!sval_is_max(rl_max(right_orig)))
2134 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2135
2136 right_true = remove_range(right_orig, rl_max(left_orig), max);
2137 if (!sval_is_min(rl_min(left_orig)))
2138 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2139 break;
2140 case SPECIAL_NOTEQUAL:
2141 left_false = rl_intersection(left_orig, right_orig);
2142 right_false = clone_rl(left_false);
2143
2144 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2145 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2146 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2147 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2148 break;
2149 default:
2150 sm_perror(" unhandled comparison %d", op);
2151 return;
2152 }
2153
2154 if (left_true_rl) {
2155 *left_true_rl = left_true;
2156 *left_false_rl = left_false;
2157 }
2158 if (right_true_rl) {
2159 *right_true_rl = right_true;
2160 *right_false_rl = right_false;
2161 }
2162 }
|
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 */
17
18 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 "permanent ranges", perm_data_range);
27 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
28
29 bool is_err_ptr(sval_t sval)
30 {
31 if (option_project != PROJ_KERNEL)
32 return false;
33 if (!type_is_ptr(sval.type))
34 return false;
35 if (sval.uvalue < -4095ULL)
36 return false;
37 return true;
38 }
39
40 static char *get_err_pointer_str(struct data_range *drange)
41 {
42 static char buf[20];
43
44 /*
45 * The kernel has error pointers where you do essentially:
46 *
47 * return (void *)(unsigned long)-12;
48 *
49 * But what I want here is to print -12 instead of the unsigned version
232 *comparison = SPECIAL_GTE;
233 c++;
234 } else {
235 *comparison = '>';
236 }
237 } else if (*c == '!') {
238 c++;
239 c++;
240 *comparison = SPECIAL_NOTEQUAL;
241 } else if (*c == '$') {
242 *comparison = SPECIAL_EQUAL;
243 } else {
244 return 0;
245 }
246
247 if (*c != '$')
248 return 0;
249 c++;
250
251 param = strtoll(c, (char **)&c, 10);
252 /*
253 * FIXME: handle parameter math. [==$1 + 100]
254 *
255 */
256 if (*c == ' ')
257 return 0;
258
259 if (*c == ',' || *c == ']')
260 c++; /* skip the ']' character */
261 if (endp)
262 *endp = (char *)c;
263
264 if (!call)
265 return 0;
266 *arg = get_argument_from_call_expr(call->args, param);
267 if (!*arg)
268 return 0;
269 if (*c == '-' && *(c + 1) == '>') {
270 char buf[256];
271 int n;
272
273 n = snprintf(buf, sizeof(buf), "$%s", c);
274 if (n >= sizeof(buf))
275 return 0;
276 if (buf[n - 1] == ']')
277 buf[n - 1] = '\0';
278 *arg = gen_expression_from_key(*arg, buf);
332 static sval_t add_one(sval_t sval)
333 {
334 sval.value++;
335 return sval;
336 }
337
338 static sval_t sub_one(sval_t sval)
339 {
340 sval.value--;
341 return sval;
342 }
343
344 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
345 {
346 struct range_list *left_orig = *rl;
347 struct range_list *right_orig = right;
348 struct range_list *ret_rl = *rl;
349 struct symbol *cast_type;
350 sval_t min, max;
351
352 if (comparison == UNKNOWN_COMPARISON)
353 return;
354
355 cast_type = rl_type(left_orig);
356 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
357 cast_type = rl_type(right_orig);
358 if (sval_type_max(cast_type).uvalue < INT_MAX)
359 cast_type = &int_ctype;
360
361 min = sval_type_min(cast_type);
362 max = sval_type_max(cast_type);
363 left_orig = cast_rl(cast_type, left_orig);
364 right_orig = cast_rl(cast_type, right_orig);
365
366 switch (comparison) {
367 case '<':
368 case SPECIAL_UNSIGNED_LT:
369 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
370 break;
371 case SPECIAL_LTE:
372 case SPECIAL_UNSIGNED_LTE:
373 if (!sval_is_max(rl_max(right_orig)))
374 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
387 break;
388 case SPECIAL_NOTEQUAL:
389 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
390 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
391 break;
392 default:
393 sm_perror("unhandled comparison %s", show_special(comparison));
394 return;
395 }
396
397 *rl = cast_rl(rl_type(*rl), ret_rl);
398 }
399
400 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
401 {
402 struct symbol *type;
403 struct expression *arg;
404 struct range_list *casted_start, *right_orig;
405 int comparison;
406
407 /* For when we have a function that takes a function pointer. */
408 if (!call || call->type != EXPR_CALL)
409 return start_rl;
410
411 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
412 return start_rl;
413
414 if (!get_implied_rl(arg, &right_orig))
415 return start_rl;
416
417 type = &int_ctype;
418 if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
419 type = rl_type(start_rl);
420 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
421 type = rl_type(right_orig);
422
423 casted_start = cast_rl(type, start_rl);
424 right_orig = cast_rl(type, right_orig);
425
426 filter_by_comparison(&casted_start, comparison, right_orig);
427 return cast_rl(rl_type(start_rl), casted_start);
428 }
429
430 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
488 *endp = c;
489 return ret;
490 }
491
492 static const char *jump_to_call_math(const char *value)
493 {
494 const char *c = value;
495
496 while (*c && *c != '[')
497 c++;
498
499 if (!*c)
500 return NULL;
501 c++;
502 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
503 return NULL;
504
505 return c;
506 }
507
508 static struct range_list *get_param_return_rl(struct expression *call, const char *call_math)
509 {
510 struct expression *arg;
511 int param;
512
513 call_math += 3;
514 param = atoi(call_math);
515
516 arg = get_argument_from_call_expr(call->args, param);
517 if (!arg)
518 return NULL;
519
520 return db_return_vals_no_args(arg);
521 }
522
523 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
524 {
525 struct range_list *rl_tmp = NULL;
526 sval_t prev_min, min, max;
527 const char *c;
528
529 prev_min = sval_type_min(type);
530 min = sval_type_min(type);
531 max = sval_type_max(type);
532 c = str;
533 while (*c != '\0' && *c != '[') {
534 if (*c == '+') {
535 if (sval_cmp(min, sval_type_min(type)) != 0)
536 min = max;
537 max = sval_type_max(type);
538 add_range_t(type, &rl_tmp, min, max);
539 break;
540 }
541 if (*c == '(')
542 c++;
604
605 if (strcmp(value, "empty") == 0)
606 return;
607
608 if (strncmp(value, "[==$", 4) == 0) {
609 struct expression *arg;
610 int comparison;
611
612 if (!str_to_comparison_arg(value, call, &comparison, &arg))
613 return;
614 if (!get_implied_rl(arg, &rl))
615 return;
616 goto cast;
617 }
618
619 str_to_rl_helper(call, type, value, &c, &rl);
620 if (*c == '\0')
621 goto cast;
622
623 call_math = jump_to_call_math(value);
624 if (call_math && call_math[0] == 'r') {
625 math_rl = get_param_return_rl(call, call_math);
626 if (math_rl)
627 rl = rl_intersection(rl, math_rl);
628 goto cast;
629 }
630 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
631 rl = rl_intersection(rl, math_rl);
632 goto cast;
633 }
634
635 /*
636 * For now if we already tried to handle the call math and couldn't
637 * figure it out then bail.
638 */
639 if (jump_to_call_math(c) == c + 1)
640 goto cast;
641
642 rl = filter_by_comparison_call(c, call, &c, rl);
643
644 cast:
645 rl = cast_rl(type, rl);
646 dinfo->value_ranges = rl;
647 }
648
649 static int rl_is_sane(struct range_list *rl)
669 struct data_info dinfo = {};
670
671 str_to_dinfo(NULL, type, value, &dinfo);
672 if (!rl_is_sane(dinfo.value_ranges))
673 dinfo.value_ranges = alloc_whole_rl(type);
674 *rl = dinfo.value_ranges;
675 }
676
677 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
678 {
679 struct data_info dinfo = {};
680
681 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
682 *rl = dinfo.value_ranges;
683 }
684
685 int is_whole_rl(struct range_list *rl)
686 {
687 struct data_range *drange;
688
689 if (ptr_list_empty((struct ptr_list *)rl))
690 return 0;
691 drange = first_ptr_list((struct ptr_list *)rl);
692 if (sval_is_min(drange->min) && sval_is_max(drange->max))
693 return 1;
694 return 0;
695 }
696
697 int is_unknown_ptr(struct range_list *rl)
698 {
699 struct data_range *drange;
700 int cnt = 0;
701
702 if (is_whole_rl(rl))
703 return 1;
704
705 FOR_EACH_PTR(rl, drange) {
706 if (++cnt >= 3)
707 return 0;
708 if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
709 sval_cmp(drange->max, valid_ptr_max_sval) == 0)
710 return 1;
711 } END_FOR_EACH_PTR(drange);
712
713 return 0;
714 }
715
716 int is_whole_rl_non_zero(struct range_list *rl)
717 {
718 struct data_range *drange;
719
720 if (ptr_list_empty((struct ptr_list *)rl))
721 return 0;
722 drange = first_ptr_list((struct ptr_list *)rl);
723 if (sval_unsigned(drange->min) &&
724 drange->min.value == 1 &&
725 sval_is_max(drange->max))
726 return 1;
727 if (!sval_is_min(drange->min) || drange->max.value != -1)
728 return 0;
729 drange = last_ptr_list((struct ptr_list *)rl);
730 if (drange->min.value != 1 || !sval_is_max(drange->max))
731 return 0;
732 return 1;
733 }
734
735 sval_t rl_min(struct range_list *rl)
736 {
737 struct data_range *drange;
738 sval_t ret;
739
740 ret.type = &llong_ctype;
741 ret.value = LLONG_MIN;
742 if (ptr_list_empty((struct ptr_list *)rl))
743 return ret;
744 drange = first_ptr_list((struct ptr_list *)rl);
745 return drange->min;
746 }
747
748 sval_t rl_max(struct range_list *rl)
749 {
750 struct data_range *drange;
751 sval_t ret;
752
753 ret.type = &llong_ctype;
754 ret.value = LLONG_MAX;
755 if (ptr_list_empty((struct ptr_list *)rl))
756 return ret;
757 drange = last_ptr_list((struct ptr_list *)rl);
758 return drange->max;
759 }
760
761 int rl_to_sval(struct range_list *rl, sval_t *sval)
762 {
763 sval_t min, max;
764
765 if (!rl)
766 return 0;
767
768 min = rl_min(rl);
769 max = rl_max(rl);
770 if (sval_cmp(min, max) != 0)
771 return 0;
772 *sval = min;
773 return 1;
774 }
775
1208 sm_perror("unhandled comparison %d", comparison);
1209 return 0;
1210 }
1211 return 0;
1212 }
1213
1214 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1215 {
1216 if (left)
1217 return false_comparison_range_sval(var, comparison, val);
1218 else
1219 return false_comparison_range_sval(val, comparison, var);
1220 }
1221
1222 int possibly_true(struct expression *left, int comparison, struct expression *right)
1223 {
1224 struct range_list *rl_left, *rl_right;
1225 struct data_range *tmp_left, *tmp_right;
1226 struct symbol *type;
1227
1228 if (comparison == UNKNOWN_COMPARISON)
1229 return 1;
1230 if (!get_implied_rl(left, &rl_left))
1231 return 1;
1232 if (!get_implied_rl(right, &rl_right))
1233 return 1;
1234
1235 type = rl_type(rl_left);
1236 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1237 type = rl_type(rl_right);
1238 if (type_positive_bits(type) < 31)
1239 type = &int_ctype;
1240
1241 rl_left = cast_rl(type, rl_left);
1242 rl_right = cast_rl(type, rl_right);
1243
1244 FOR_EACH_PTR(rl_left, tmp_left) {
1245 FOR_EACH_PTR(rl_right, tmp_right) {
1246 if (true_comparison_range(tmp_left, comparison, tmp_right))
1247 return 1;
1248 } END_FOR_EACH_PTR(tmp_right);
1249 } END_FOR_EACH_PTR(tmp_left);
1267 if (type_positive_bits(type) < 31)
1268 type = &int_ctype;
1269
1270 rl_left = cast_rl(type, rl_left);
1271 rl_right = cast_rl(type, rl_right);
1272
1273 FOR_EACH_PTR(rl_left, tmp_left) {
1274 FOR_EACH_PTR(rl_right, tmp_right) {
1275 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1276 return 1;
1277 } END_FOR_EACH_PTR(tmp_right);
1278 } END_FOR_EACH_PTR(tmp_left);
1279 return 0;
1280 }
1281
1282 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1283 {
1284 struct data_range *left_tmp, *right_tmp;
1285 struct symbol *type;
1286
1287 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1288 return 1;
1289
1290 type = rl_type(left_ranges);
1291 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1292 type = rl_type(right_ranges);
1293 if (type_positive_bits(type) < 31)
1294 type = &int_ctype;
1295
1296 left_ranges = cast_rl(type, left_ranges);
1297 right_ranges = cast_rl(type, right_ranges);
1298
1299 FOR_EACH_PTR(left_ranges, left_tmp) {
1300 FOR_EACH_PTR(right_ranges, right_tmp) {
1301 if (true_comparison_range(left_tmp, comparison, right_tmp))
1302 return 1;
1303 } END_FOR_EACH_PTR(right_tmp);
1304 } END_FOR_EACH_PTR(left_tmp);
1305 return 0;
1306 }
1307
1308 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1309 {
1310 struct data_range *left_tmp, *right_tmp;
1311 struct symbol *type;
1312
1313 if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1314 return 1;
1315
1316 type = rl_type(left_ranges);
1317 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1318 type = rl_type(right_ranges);
1319 if (type_positive_bits(type) < 31)
1320 type = &int_ctype;
1321
1322 left_ranges = cast_rl(type, left_ranges);
1323 right_ranges = cast_rl(type, right_ranges);
1324
1325 FOR_EACH_PTR(left_ranges, left_tmp) {
1326 FOR_EACH_PTR(right_ranges, right_tmp) {
1327 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1328 return 1;
1329 } END_FOR_EACH_PTR(right_tmp);
1330 } END_FOR_EACH_PTR(left_tmp);
1331 return 0;
1332 }
1333
1867 zero.uvalue = 0;
1868 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1869
1870 return cast_rl(rl_type(left), alloc_rl(zero, max));
1871 }
1872
1873 static sval_t sval_lowest_set_bit(sval_t sval)
1874 {
1875 sval_t ret = { .type = sval.type };
1876 int i;
1877
1878 for (i = 0; i < 64; i++) {
1879 if (sval.uvalue & 1ULL << i) {
1880 ret.uvalue = (1ULL << i);
1881 return ret;
1882 }
1883 }
1884 return ret;
1885 }
1886
1887 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1888 {
1889 struct bit_info *one, *two;
1890 struct range_list *rl;
1891 sval_t min, max, zero;
1892 unsigned long long bits;
1893
1894 one = rl_to_binfo(left);
1895 two = rl_to_binfo(right);
1896 bits = one->possible & two->possible;
1897
1898 max = rl_max(left);
1899 max.uvalue = bits;
1900 min = sval_lowest_set_bit(max);
1901
1902 rl = alloc_rl(min, max);
1903
1904 zero = rl_min(rl);
1905 zero.value = 0;
1906 add_range(&rl, zero, zero);
1907
1908 return rl;
1909 }
1910
1911 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
1912 {
1913 struct range_list *left;
1914 struct data_range *tmp;
1915 struct range_list *ret = NULL;
1916 sval_t zero = { .type = rl_type(left_orig), };
1917 sval_t shift, min, max;
1918 bool add_zero = false;
1919
1920 if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1921 return NULL;
1922 if (shift.value == 0)
1923 return left_orig;
2121 case SPECIAL_UNSIGNED_GT:
2122 left_true = remove_range(left_orig, min, rl_min(right_orig));
2123 if (!sval_is_max(rl_max(right_orig)))
2124 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2125
2126 right_true = remove_range(right_orig, rl_max(left_orig), max);
2127 if (!sval_is_min(rl_min(left_orig)))
2128 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2129 break;
2130 case SPECIAL_NOTEQUAL:
2131 left_false = rl_intersection(left_orig, right_orig);
2132 right_false = clone_rl(left_false);
2133
2134 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2135 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2136 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2137 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2138 break;
2139 default:
2140 sm_perror(" unhandled comparison %d", op);
2141 }
2142
2143 if (left_true_rl) {
2144 *left_true_rl = left_true;
2145 *left_false_rl = left_false;
2146 }
2147 if (right_true_rl) {
2148 *right_true_rl = right_true;
2149 *right_false_rl = right_false;
2150 }
2151 }
|