smatch_constraints.c

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