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