Print this page
11506 smatch resync
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/smatch_constraints.c
+++ new/usr/src/tools/smatch/src/smatch_constraints.c
1 1 /*
2 2 * Copyright (C) 2017 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 I see constraints as a way of saying "x <= some_limit". The
20 20 * problem is that smatch_capped is not granullar enough.
21 21 *
22 22 * This is mostly for finding out of bounds errors. So there are different
23 23 * types of constraints. Quite often we have "foo->xxx[i] = 42;" and we want
24 24 * to verify that "i" is less than foo->size.
25 25 *
26 26 * My idea was that we could automatically figure out these constraints. And we
27 27 * could load them in the DB so that they are the same every time. As in a
28 28 * constraint could be "< (struct whatever)->size" and give that in ID that
29 29 * would be constant until you completely wiped the DB. So when you do a normal
30 30 * DB rebuild then the first thing it will do is preserve all the constraints.
31 31 * I guess the reason to do it this way is to save space... I sometimes suspect
32 32 * that worrying about saving space is premature optimization.
33 33 *
34 34 * The other thing that I want to do a little bit different here is how I merge
35 35 * constraints. If a constraint is true on both sides, then that's normal. If
36 36 * we merge constraint 23 and 67 then we get constraint 23|67. If we merge 23
37 37 * with &undefined then we get &undefined. We can also have two constraints
38 38 * that are both true so we could have (45&23)|12 which means either both 45 and
39 39 * 23 are true or 12 is true.
40 40 *
41 41 */
42 42
43 43
44 44 #include "smatch.h"
45 45 #include "smatch_extra.h"
46 46 #include "smatch_slist.h"
47 47
48 48 static int my_id;
49 49
50 50 ALLOCATOR(constraint, "constraints");
51 51
52 52 static void add_constraint(struct constraint_list **list, int op, int constraint)
53 53 {
54 54 struct constraint *tmp, *new;
55 55
56 56 FOR_EACH_PTR(*list, tmp) {
57 57 if (tmp->id < constraint)
58 58 continue;
59 59 if (tmp->id == constraint) {
60 60 if (tmp->op == '<')
61 61 return;
62 62 if (op == SPECIAL_LTE)
63 63 return;
64 64
65 65 new = __alloc_constraint(0);
66 66 new->op = op;
67 67 new->id = constraint;
68 68 REPLACE_CURRENT_PTR(tmp, new);
69 69 return;
70 70 }
71 71
72 72 new = __alloc_constraint(0);
73 73 new->op = op;
74 74 new->id = constraint;
75 75 INSERT_CURRENT(new, tmp);
76 76 return;
77 77 } END_FOR_EACH_PTR(tmp);
78 78
79 79 new = __alloc_constraint(0);
80 80 new->op = op;
81 81 new->id = constraint;
82 82 add_ptr_list(list, new);
83 83 }
84 84
85 85 static struct constraint_list *merge_constraint_lists(struct constraint_list *one, struct constraint_list *two)
86 86 {
87 87 struct constraint_list *ret = NULL;
88 88 struct constraint *tmp;
89 89
90 90 // FIXME: not || but &&
91 91 FOR_EACH_PTR(one, tmp) {
92 92 add_constraint(&ret, tmp->op, tmp->id);
93 93 } END_FOR_EACH_PTR(tmp);
94 94
95 95 FOR_EACH_PTR(two, tmp) {
96 96 add_constraint(&ret, tmp->op, tmp->id);
97 97 } END_FOR_EACH_PTR(tmp);
98 98
99 99 return ret;
100 100 }
101 101
102 102 static struct constraint_list *clone_constraint_list(struct constraint_list *list)
103 103 {
104 104 struct constraint_list *ret = NULL;
105 105 struct constraint *tmp;
106 106
107 107 FOR_EACH_PTR(list, tmp) {
108 108 add_constraint(&ret, tmp->op, tmp->id);
109 109 } END_FOR_EACH_PTR(tmp);
110 110
111 111 return ret;
112 112 }
113 113
114 114 static struct smatch_state *alloc_constraint_state(struct constraint_list *list)
115 115 {
116 116 struct smatch_state *state;
117 117 struct constraint *con;
118 118 static char buf[256];
119 119 int cnt = 0;
120 120
121 121 FOR_EACH_PTR(list, con) {
122 122 if (cnt != 0)
123 123 cnt += snprintf(buf + cnt, sizeof(buf) - cnt, ", ");
124 124 cnt += snprintf(buf + cnt, sizeof(buf) - cnt, "%s%d",
125 125 show_special(con->op), con->id);
126 126 } END_FOR_EACH_PTR(con);
127 127
128 128 state = __alloc_smatch_state(0);
129 129 state->name = alloc_string(buf);
130 130 state->data = list;
131 131 return state;
132 132 }
133 133
134 134 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
135 135 {
136 136 struct constraint_list *list;
137 137
138 138 // FIXME: use the dead code below instead
139 139 if (strcmp(s1->name, s2->name) == 0)
140 140 return s1;
141 141 return &merged;
142 142
143 143 list = merge_constraint_lists(s1->data, s2->data);
144 144 return alloc_constraint_state(list);
145 145 }
146 146
147 147 static int negate_gt(int op)
148 148 {
149 149 switch (op) {
150 150 case '>':
151 151 case SPECIAL_UNSIGNED_GT:
152 152 case SPECIAL_GTE:
153 153 case SPECIAL_UNSIGNED_GTE:
154 154 return negate_comparison(op);
155 155 }
156 156 return op;
157 157 }
158 158
159 159 static char *get_func_constraint(struct expression *expr)
160 160 {
161 161 char buf[256];
162 162 char *name;
163 163
164 164 if (is_fake_call(expr))
165 165 return NULL;
166 166 name = expr_to_str(expr->fn);
167 167 if (!name)
168 168 return NULL;
169 169 snprintf(buf, sizeof(buf), "%s()", name);
170 170 free_string(name);
171 171 return alloc_string(buf);
172 172 }
173 173
174 174 static char *get_toplevel_name(struct expression *expr)
175 175 {
176 176 struct symbol *sym;
177 177 char buf[256];
178 178
179 179 expr = strip_expr(expr);
180 180 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->ident)
181 181 return NULL;
182 182
183 183 sym = expr->symbol;
184 184 if (!(sym->ctype.modifiers & MOD_TOPLEVEL))
185 185 return NULL;
186 186
187 187 if (sym->ctype.modifiers & MOD_STATIC)
188 188 snprintf(buf, sizeof(buf), "%s %s", get_base_file(), sym->ident->name);
|
↓ open down ↓ |
188 lines elided |
↑ open up ↑ |
189 189 else
190 190 snprintf(buf, sizeof(buf), "extern %s", sym->ident->name);
191 191
192 192 return alloc_string(buf);
193 193 }
194 194
195 195 char *get_constraint_str(struct expression *expr)
196 196 {
197 197 char *name;
198 198
199 + expr = strip_expr(expr);
199 200 if (!expr)
200 201 return NULL;
201 202 if (expr->type == EXPR_CALL)
202 203 return get_func_constraint(expr);
203 204 if (expr->type == EXPR_BINOP)
204 205 return expr_to_str(expr);
205 206 name = get_toplevel_name(expr);
206 207 if (name)
207 208 return name;
208 209 return get_member_name(expr);
209 210 }
210 211
211 212 static int save_int_callback(void *_p, int argc, char **argv, char **azColName)
212 213 {
213 214 int *p = _p;
214 215
215 216 *p = atoi(argv[0]);
216 217 return 0;
217 218 }
218 219
219 220 static int constraint_str_to_id(const char *str)
220 221 {
221 222 int id = -1;
222 223
223 224 run_sql(save_int_callback, &id,
224 225 "select id from constraints where str = '%q'", str);
225 226
226 227 return id;
227 228 }
228 229
229 230 static int save_constraint_str(void *_str, int argc, char **argv, char **azColName)
230 231 {
231 232 char **str = _str;
232 233
233 234 *str = alloc_string(argv[0]);
234 235 return 0;
235 236 }
236 237
237 238 static char *constraint_id_to_str(int id)
238 239 {
239 240 char *str = NULL;
240 241
241 242 run_sql(save_constraint_str, &str,
242 243 "select str from constraints where id = '%d'", id);
243 244
244 245 return str;
245 246 }
246 247
247 248 static int save_op_callback(void *_p, int argc, char **argv, char **azColName)
248 249 {
249 250 int *p = _p;
250 251
251 252 if (argv[0][0] == '<' && argv[0][1] == '=')
252 253 *p = SPECIAL_LTE;
253 254 else
254 255 *p = '<';
255 256 return 0;
256 257 }
257 258
258 259 static int save_str_callback(void *_p, int argc, char **argv, char **azColName)
259 260 {
260 261 char **p = _p;
261 262
262 263 if (!*p) {
263 264 *p = alloc_string(argv[0]);
264 265 } else {
265 266 char buf[256];
266 267
267 268 snprintf(buf, sizeof(buf), "%s, %s", *p, argv[0]);
268 269 *p = alloc_string(buf);
269 270 }
270 271 return 0;
271 272 }
272 273
273 274 char *get_required_constraint(const char *data_str)
274 275 {
275 276 char *required = NULL;
276 277
277 278 run_sql(save_str_callback, &required,
278 279 "select bound from constraints_required where data = '%q'", data_str);
279 280
280 281 return required;
281 282 }
282 283
283 284 static int get_required_op(char *data_str, char *con_str)
284 285 {
285 286 int op = 0;
286 287
287 288 run_sql(save_op_callback, &op,
288 289 "select op from constraints_required where data = '%q' and bound = '%q'", data_str, con_str);
289 290
290 291 return op;
291 292 }
292 293
293 294 char *unmet_constraint(struct expression *data, struct expression *offset)
294 295 {
295 296 struct smatch_state *state;
296 297 struct constraint_list *list;
297 298 struct constraint *con;
298 299 char *data_str;
299 300 char *required;
300 301 int req_op;
301 302
302 303 data_str = get_constraint_str(data);
303 304 if (!data_str)
304 305 return NULL;
305 306
306 307 required = get_required_constraint(data_str);
307 308 if (!required)
308 309 goto free_data;
309 310
310 311 state = get_state_expr(my_id, offset);
311 312 if (!state)
312 313 goto free_data;
313 314 list = state->data;
314 315
315 316 /* check the list of bounds on our index against the list that work */
316 317 FOR_EACH_PTR(list, con) {
317 318 char *con_str;
318 319
319 320 con_str = constraint_id_to_str(con->id);
320 321 if (!con_str) {
321 322 sm_msg("constraint %d not found", con->id);
322 323 continue;
323 324 }
324 325
325 326 req_op = get_required_op(data_str, con_str);
326 327 free_string(con_str);
327 328 if (!req_op)
328 329 continue;
329 330 if (con->op == '<' || con->op == req_op) {
330 331 free_string(required);
331 332 required = NULL;
332 333 goto free_data;
333 334 }
|
↓ open down ↓ |
125 lines elided |
↑ open up ↑ |
334 335 } END_FOR_EACH_PTR(con);
335 336
336 337 free_data:
337 338 free_string(data_str);
338 339 return required;
339 340 }
340 341
341 342 struct string_list *saved_constraints;
342 343 static void save_new_constraint(const char *con)
343 344 {
344 - if (list_has_string(saved_constraints, con))
345 + if (!insert_string(&saved_constraints, con))
345 346 return;
346 - insert_string(&saved_constraints, con);
347 347 sql_save_constraint(con);
348 348 }
349 349
350 350 static void handle_comparison(struct expression *left, int op, struct expression *right)
351 351 {
352 352 struct constraint_list *constraints;
353 353 struct smatch_state *state;
354 354 char *constraint;
355 355 int constraint_id;
356 356 int orig_op = op;
357 357 sval_t sval;
358 358
359 359 /* known values are handled in smatch extra */
360 360 if (get_value(left, &sval) || get_value(right, &sval))
361 361 return;
362 362
363 - if (local_debug)
364 - sm_msg("COMPARE: %s %s %s", expr_to_str(left), show_special(op), expr_to_str(right));
365 -
366 363 constraint = get_constraint_str(right);
367 364 if (!constraint)
368 365 return;
369 - if (local_debug)
370 - sm_msg("EXPR: %s CONSTRAINT %s", expr_to_str(right), constraint);
371 366 constraint_id = constraint_str_to_id(constraint);
372 - if (local_debug)
373 - sm_msg("CONSTRAINT ID %d", constraint_id);
374 367 if (constraint_id < 0)
375 368 save_new_constraint(constraint);
376 369 free_string(constraint);
377 370 if (constraint_id < 0)
378 371 return;
379 372
380 373 constraints = get_constraints(left);
381 374 constraints = clone_constraint_list(constraints);
382 375 op = negate_gt(orig_op);
383 376 add_constraint(&constraints, remove_unsigned_from_comparison(op), constraint_id);
384 377 state = alloc_constraint_state(constraints);
385 378
386 - if (op == orig_op) {
387 - if (local_debug)
388 - sm_msg("SETTING %s true %s", expr_to_str(left), state->name);
379 + if (op == orig_op)
389 380 set_true_false_states_expr(my_id, left, state, NULL);
390 - } else {
391 - if (local_debug)
392 - sm_msg("SETTING %s false %s", expr_to_str(left), state->name);
393 -
381 + else
394 382 set_true_false_states_expr(my_id, left, NULL, state);
395 - }
396 383 }
397 384
398 385 static void match_condition(struct expression *expr)
399 386 {
400 387 if (expr->type != EXPR_COMPARE)
401 388 return;
402 389
403 390 if (expr->op == SPECIAL_EQUAL ||
404 391 expr->op == SPECIAL_NOTEQUAL)
405 392 return;
406 393
407 394 handle_comparison(expr->left, expr->op, expr->right);
408 395 handle_comparison(expr->right, flip_comparison(expr->op), expr->left);
409 396 }
410 397
411 398 struct constraint_list *get_constraints(struct expression *expr)
412 399 {
413 400 struct smatch_state *state;
414 401
415 402 state = get_state_expr(my_id, expr);
416 403 if (!state)
417 404 return NULL;
418 405 return state->data;
419 406 }
420 407
421 408 static void match_caller_info(struct expression *expr)
422 409 {
423 410 struct expression *tmp;
424 411 struct smatch_state *state;
425 412 int i;
426 413
427 414 i = -1;
428 415 FOR_EACH_PTR(expr->args, tmp) {
429 416 i++;
430 417 state = get_state_expr(my_id, tmp);
431 418 if (!state || state == &merged || state == &undefined)
432 419 continue;
433 420 sql_insert_caller_info(expr, CONSTRAINT, i, "$", state->name);
434 421 } END_FOR_EACH_PTR(tmp);
435 422 }
436 423
437 424 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
438 425 {
439 426 if (sm->state == &merged || sm->state == &undefined)
440 427 return;
441 428 sql_insert_caller_info(call, CONSTRAINT, param, printed_name, sm->state->name);
442 429 }
443 430
444 431 static struct smatch_state *constraint_str_to_state(char *value)
445 432 {
446 433 struct constraint_list *list = NULL;
447 434 char *p = value;
448 435 int op;
449 436 long long id;
450 437
451 438 while (true) {
452 439 op = '<';
453 440 if (*p != '<')
454 441 return &undefined;
455 442 p++;
456 443 if (*p == '=') {
457 444 op = SPECIAL_LTE;
458 445 p++;
459 446 }
460 447 id = strtoll(p, &p, 10);
461 448 add_constraint(&list, op, id);
462 449 if (*p != ',')
463 450 break;
464 451 p++;
465 452 if (*p != ' ')
466 453 return &undefined;
467 454 }
468 455
469 456 return alloc_constraint_state(list);
470 457 }
471 458
472 459 static void set_param_constrained(const char *name, struct symbol *sym, char *key, char *value)
473 460 {
474 461 char fullname[256];
475 462
476 463 if (strcmp(key, "*$") == 0)
477 464 snprintf(fullname, sizeof(fullname), "*%s", name);
478 465 else if (strncmp(key, "$", 1) == 0)
479 466 snprintf(fullname, 256, "%s%s", name, key + 1);
480 467 else
481 468 return;
482 469
483 470 set_state(my_id, name, sym, constraint_str_to_state(value));
484 471 }
485 472
486 473 static void print_return_implies_constrained(int return_id, char *return_ranges, struct expression *expr)
487 474 {
488 475 struct smatch_state *orig;
489 476 struct sm_state *sm;
490 477 const char *param_name;
491 478 int param;
492 479
493 480 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
494 481 if (sm->state == &merged || sm->state == &undefined)
495 482 continue;
496 483
497 484 param = get_param_num_from_sym(sm->sym);
498 485 if (param < 0)
499 486 continue;
500 487
501 488 orig = get_state_stree(get_start_states(), my_id, sm->name, sm->sym);
502 489 if (orig && strcmp(sm->state->name, orig->name) == 0)
503 490 continue;
504 491
505 492 param_name = get_param_name(sm);
506 493 if (!param_name)
507 494 continue;
508 495
509 496 sql_insert_return_states(return_id, return_ranges, CONSTRAINT,
510 497 param, param_name, sm->state->name);
511 498 } END_FOR_EACH_SM(sm);
512 499 }
513 500
514 501 static void db_returns_constrained(struct expression *expr, int param, char *key, char *value)
515 502 {
516 503 char *name;
517 504 struct symbol *sym;
518 505
519 506 name = return_state_to_var_sym(expr, param, key, &sym);
520 507 if (!name || !sym)
521 508 goto free;
|
↓ open down ↓ |
116 lines elided |
↑ open up ↑ |
522 509
523 510 set_state(my_id, name, sym, constraint_str_to_state(value));
524 511 free:
525 512 free_string(name);
526 513 }
527 514
528 515 void register_constraints(int id)
529 516 {
530 517 my_id = id;
531 518
519 + set_dynamic_states(my_id);
532 520 add_merge_hook(my_id, &merge_func);
533 521 add_hook(&match_condition, CONDITION_HOOK);
534 522
535 523 add_hook(&match_caller_info, FUNCTION_CALL_HOOK);
536 524 add_member_info_callback(my_id, struct_member_callback);
537 525 select_caller_info_hook(&set_param_constrained, CONSTRAINT);
538 526
539 527 add_split_return_callback(print_return_implies_constrained);
540 528 select_return_states_hook(CONSTRAINT, &db_returns_constrained);
541 529 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX