smatch_param_set.c

   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  * This is for functions like:
  20  *
  21  * int foo(int *x)
  22  * {
  23  *      if (*x == 42) {
  24  *              *x = 0;
  25  *              return 1;
  26  *      }
  27  *      return 0;
  28  * }
  29  *
  30  * If we return 1 that means the value of *x has been set to 0.  If we return
  31  * 0 then we have left *x alone.
  32  *
  33  */
  34
  35 #include "smatch.h"
  36 #include "smatch_slist.h"
  37 #include "smatch_extra.h"
  38
  39 static int my_id;
  40
  41 static struct smatch_state *unmatched_state(struct sm_state *sm)
  42 {
  43         return alloc_estate_empty();
  44 }
  45
  46 static int parent_is_set(const char *name, struct symbol *sym, struct smatch_state *state)
  47 {
  48         struct expression *faked;
  49         char *left_name;
  50         int ret = 0;
  51         int len;
  52
  53         if (!__in_fake_assign)
  54                 return 0;
  55         if (!is_whole_rl(estate_rl(state)))
  56                 return 0;
  57         if (get_state(my_id, name, sym))
  58                 return 0;
  59
  60         faked = get_faked_expression();
  61         if (!faked)
  62                 return 0;
  63         if ((faked->type == EXPR_PREOP || faked->type == EXPR_POSTOP) &&
  64             (faked->op == SPECIAL_INCREMENT || faked->op == SPECIAL_DECREMENT)) {
  65                 faked = strip_expr(faked->unop);
  66                 if (faked->type == EXPR_SYMBOL)
  67                         return 1;
  68                 return 0;
  69         }
  70         if (faked->type != EXPR_ASSIGNMENT)
  71                 return 0;
  72
  73         left_name = expr_to_var(faked->left);
  74         if (!left_name)
  75                 return 0;
  76
  77         len = strlen(left_name);
  78         if (strncmp(name, left_name, len) == 0 && name[len] == '-')
  79                 ret = 1;
  80         free_string(left_name);
  81
  82         return ret;
  83 }
  84
  85 static bool is_probably_worthless(struct expression *expr)
  86 {
  87         struct expression *faked;
  88
  89         if (!__in_fake_struct_assign)
  90                 return false;
  91
  92         faked = get_faked_expression();
  93         if (!faked || faked->type != EXPR_ASSIGNMENT)
  94                 return false;
  95
  96         if (faked->left->type == EXPR_PREOP &&
  97             faked->left->op == '*')
  98                 return false;
  99
 100         return true;
 101 }
 102
 103 static bool name_is_sym_name(const char *name, struct symbol *sym)
 104 {
 105         if (!name || !sym || !sym->ident)
 106                 return false;
 107
 108         return strcmp(name, sym->ident->name) == 0;
 109 }
 110
 111 static void extra_mod_hook(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 112 {
 113         struct symbol *param_sym;
 114         struct symbol *type;
 115         char *param_name;
 116
 117         if (expr && expr->smatch_flags & Fake)
 118                 return;
 119
 120         if (is_probably_worthless(expr))
 121                 return;
 122
 123         type = get_type(expr);
 124         if (type && (type->type == SYM_STRUCT || type->type == SYM_UNION))
 125                 return;
 126
 127         if (name_is_sym_name(name, sym))
 128                 return;
 129
 130         param_name = get_param_var_sym_var_sym(name, sym, NULL, &param_sym);
 131         if (!param_name || !param_sym)
 132                 goto free;
 133         if (get_param_num_from_sym(param_sym) < 0)
 134                 goto free;
 135         if (parent_is_set(param_name, param_sym, state))
 136                 return;
 137
 138         if (get_state(my_id, param_name, param_sym))
 139                 goto reset;
 140
 141         if (__in_buf_clear)
 142                 return;
 143 reset:
 144         set_state(my_id, param_name, param_sym, state);
 145 free:
 146         free_string(param_name);
 147 }
 148
 149 /*
 150  * This function is is a dirty hack because extra_mod_hook is giving us a NULL
 151  *  sym instead of a vsl.
 152  */
 153 static void match_array_assignment(struct expression *expr)
 154 {
 155         struct expression *array, *offset;
 156         char *name;
 157         struct symbol *sym;
 158         struct range_list *rl;
 159         sval_t sval;
 160         char buf[256];
 161
 162         if (__in_fake_assign)
 163                 return;
 164
 165         if (!is_array(expr->left))
 166                 return;
 167         array = get_array_base(expr->left);
 168         offset = get_array_offset(expr->left);
 169
 170         /* These are handled by extra_mod_hook() */
 171         if (get_value(offset, &sval))
 172                 return;
 173         name = expr_to_var_sym(array, &sym);
 174         if (!name || !sym)
 175                 goto free;
 176         if (map_to_param(name, sym) < 0)
 177                 goto free;
 178         get_absolute_rl(expr->right, &rl);
 179         rl = cast_rl(get_type(expr->left), rl);
 180
 181         snprintf(buf, sizeof(buf), "*%s", name);
 182         set_state(my_id, buf, sym, alloc_estate_rl(rl));
 183 free:
 184         free_string(name);
 185 }
 186
 187 static char *get_two_dots(const char *name)
 188 {
 189         static char buf[80];
 190         int i, cnt = 0;
 191
 192         for (i = 0; i < sizeof(buf); i++) {
 193                 if (name[i] == '.') {
 194                         cnt++;
 195                         if (cnt >= 2) {
 196                                 buf[i] = '\0';
 197                                 return buf;
 198                         }
 199                 }
 200                 buf[i] = name[i];
 201         }
 202         return NULL;
 203 }
 204
 205 /*
 206  * This relies on the fact that these states are stored so that
 207  * foo->bar is before foo->bar->baz.
 208  */
 209 static int parent_set(struct string_list *list, const char *param_name, struct sm_state *sm)
 210 {
 211         char *tmp;
 212         int len;
 213         int ret;
 214
 215         if (strncmp(param_name, "(*$)->", 6) == 0 && sm->sym && sm->sym->ident) {
 216                 char buf[64];
 217
 218                 snprintf(buf, sizeof(buf), "*%s", sm->sym->ident->name);
 219                 if (get_state(my_id, buf, sm->sym))
 220                         return true;
 221         }
 222
 223         FOR_EACH_PTR(list, tmp) {
 224                 len = strlen(tmp);
 225                 ret = strncmp(tmp, sm->name, len);
 226                 if (ret < 0)
 227                         continue;
 228                 if (ret > 0)
 229                         return 0;
 230                 if (sm->name[len] == '-')
 231                         return 1;
 232         } END_FOR_EACH_PTR(tmp);
 233
 234         return 0;
 235 }
 236
 237 static void print_return_value_param_helper(int return_id, char *return_ranges, struct expression *expr, int limit)
 238 {
 239         struct sm_state *sm;
 240         struct smatch_state *extra;
 241         int param;
 242         struct range_list *rl;
 243         const char *param_name;
 244         struct string_list *set_list = NULL;
 245         char *math_str;
 246         char buf[256];
 247         char two_dot[80] = "";
 248         int count = 0;
 249
 250         __promote_sets_to_clears(return_id, return_ranges, expr);
 251
 252         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 253                 bool untracked = false;
 254
 255                 if (!estate_rl(sm->state))
 256                         continue;
 257                 extra = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
 258                 if (extra) {
 259                         rl = rl_intersection(estate_rl(sm->state), estate_rl(extra));
 260                         if (!rl)
 261                                 untracked = true;
 262                 } else {
 263                         rl = estate_rl(sm->state);
 264                 }
 265
 266                 param = get_param_key_from_sm(sm, NULL, &param_name);
 267                 if (param < 0 || !param_name)
 268                         continue;
 269                 if (param_name[0] == '&')
 270                         continue;
 271                 if (strcmp(param_name, "$") == 0 ||
 272                     is_recursive_member(param_name) ||
 273                     is_ignored_kernel_data(param_name)) {
 274                         insert_string(&set_list, (char *)sm->name);
 275                         continue;
 276                 }
 277                 if (untracked) {
 278                         if (parent_was_PARAM_CLEAR(sm->name, sm->sym))
 279                                 continue;
 280
 281                         sql_insert_return_states(return_id, return_ranges,
 282                                                  UNTRACKED_PARAM, param, param_name, "");
 283                         continue;
 284                 }
 285
 286                 if (limit) {
 287                         char *new = get_two_dots(param_name);
 288
 289                         /* no useful information here. */
 290                         if (is_whole_rl(rl) && parent_set(set_list, param_name, sm))
 291                                 continue;
 292
 293                         if (new) {
 294                                 if (strcmp(new, two_dot) == 0)
 295                                         continue;
 296
 297                                 strncpy(two_dot, new, sizeof(two_dot));
 298                                 insert_string(&set_list, (char *)sm->name);
 299                                 sql_insert_return_states(return_id, return_ranges,
 300                                          PARAM_SET, param, new, "s64min-s64max");
 301                                 continue;
 302                         }
 303                 }
 304
 305                 math_str = get_value_in_terms_of_parameter_math_var_sym(sm->name, sm->sym);
 306                 if (math_str && strcmp(show_rl(rl), math_str) != 0) {
 307                         snprintf(buf, sizeof(buf), "%s[%s]", show_rl(rl), math_str);
 308                         insert_string(&set_list, (char *)sm->name);
 309                         sql_insert_return_states(return_id, return_ranges,
 310                                         param_has_filter_data(sm) ? PARAM_ADD : PARAM_SET,
 311                                         param, param_name, buf);
 312                         continue;
 313                 }
 314
 315                 /* no useful information here. */
 316                 if (is_whole_rl(rl) && parent_set(set_list, param_name, sm))
 317                         continue;
 318                 if (is_whole_rl(rl) && parent_was_PARAM_CLEAR(sm->name, sm->sym))
 319                         continue;
 320                 if (rl_is_zero(rl) && parent_was_PARAM_CLEAR_ZERO(sm->name, sm->sym))
 321                         continue;
 322
 323                 insert_string(&set_list, (char *)sm->name);
 324
 325                 sql_insert_return_states(return_id, return_ranges,
 326                                          param_has_filter_data(sm) ? PARAM_ADD : PARAM_SET,
 327                                          param, param_name, show_rl(rl));
 328                 if (limit && ++count > limit)
 329                         break;
 330
 331         } END_FOR_EACH_SM(sm);
 332
 333         free_ptr_list((struct ptr_list **)&set_list);
 334 }
 335
 336 static void print_return_value_param(int return_id, char *return_ranges, struct expression *expr)
 337 {
 338         print_return_value_param_helper(return_id, return_ranges, expr, 0);
 339 }
 340
 341 void print_limited_param_set(int return_id, char *return_ranges, struct expression *expr)
 342 {
 343         print_return_value_param_helper(return_id, return_ranges, expr, 1000);
 344 }
 345
 346 static int possibly_empty(struct sm_state *sm)
 347 {
 348         struct sm_state *tmp;
 349
 350         FOR_EACH_PTR(sm->possible, tmp) {
 351                 if (strcmp(tmp->name, "") == 0)
 352                         return 1;
 353         } END_FOR_EACH_PTR(tmp);
 354         return 0;
 355 }
 356
 357 static bool sym_was_set(struct symbol *sym)
 358 {
 359         char buf[80];
 360
 361         if (!sym || !sym->ident)
 362                 return false;
 363
 364         snprintf(buf, sizeof(buf), "%s orig", sym->ident->name);
 365         if (get_comparison_strings(sym->ident->name, buf) == SPECIAL_EQUAL)
 366                 return false;
 367
 368         return true;
 369 }
 370
 371 int param_was_set_var_sym(const char *name, struct symbol *sym)
 372 {
 373         struct symbol *param_sym;
 374         const char *param_name;
 375         struct sm_state *sm;
 376         char buf[80];
 377         int len, i;
 378
 379         param_name = get_param_var_sym_var_sym(name, sym, NULL, &param_sym);
 380         if (param_name && param_sym) {
 381                 name = param_name;
 382                 sym = param_sym;
 383         }
 384
 385         if (!name)
 386                 return 0;
 387
 388         if (name[0] == '&')
 389                 name++;
 390
 391         if (sym_was_set(sym))
 392                 return true;
 393
 394         len = strlen(name);
 395         if (len >= sizeof(buf))
 396                 len = sizeof(buf) - 1;
 397
 398         for (i = 0; i <= len; i++) {
 399                 if (name[i] != '-' && name[i] != '\0')
 400                         continue;
 401
 402                 memcpy(buf, name, i);
 403                 buf[i] = '\0';
 404
 405                 sm = get_sm_state(my_id, buf, sym);
 406                 if (!sm)
 407                         continue;
 408                 if (possibly_empty(sm))
 409                         continue;
 410                 return 1;
 411         }
 412
 413         if (name[0] == '*')
 414                 return param_was_set_var_sym(name + 1, sym);
 415
 416         return 0;
 417 }
 418
 419 static struct expression *get_unfaked_expr(struct expression *expr)
 420 {
 421         struct expression *tmp;
 422
 423         if (!is_fake_var(expr))
 424                 return expr;
 425         tmp = expr_get_fake_parent_expr(expr);
 426         if (!tmp || tmp->type != EXPR_ASSIGNMENT)
 427                 return expr;
 428         return tmp->right;
 429 }
 430
 431 int param_was_set(struct expression *expr)
 432 {
 433         char *name;
 434         struct symbol *sym;
 435         int ret = 0;
 436
 437         expr = get_unfaked_expr(expr);
 438
 439         name = expr_to_var_sym(expr, &sym);
 440         if (!name || !sym)
 441                 goto free;
 442
 443         ret = param_was_set_var_sym(name, sym);
 444 free:
 445         free_string(name);
 446         return ret;
 447 }
 448
 449 static void match_ignored(struct expression *expr)
 450 {
 451         struct smatch_state *state = alloc_estate_whole(get_type(expr));
 452
 453         set_extra_expr_mod(expr, state);
 454 }
 455
 456 static void register_ignored_params_from_file(void)
 457 {
 458         char name[256];
 459         struct token *token;
 460         const char *func;
 461         int param;
 462
 463         /*
 464          * Eventually I realized that we're ignoring uninitialized variables
 465          * from these functions because in practice they're always set.  I
 466          * thought about tracking them as PARAM_LOST, but that's not really
 467          * accurate, they're just set to unknown.
 468          *
 469          */
 470
 471         snprintf(name, 256, "%s.ignore_uninitialized_param", option_project_str);
 472         name[255] = '\0';
 473         token = get_tokens_file(name);
 474         if (!token)
 475                 return;
 476         if (token_type(token) != TOKEN_STREAMBEGIN)
 477                 return;
 478         token = token->next;
 479         while (token_type(token) != TOKEN_STREAMEND) {
 480                 if (token_type(token) != TOKEN_IDENT)
 481                         return;
 482                 func = show_ident(token->ident);
 483
 484                 token = token->next;
 485                 if (token_type(token) != TOKEN_NUMBER)
 486                         return;
 487                 param = atoi(token->number);
 488
 489                 add_param_key_expr_hook(func, match_ignored, param, "*$", NULL);
 490
 491                 token = token->next;
 492         }
 493         clear_token_alloc();
 494 }
 495
 496 void register_param_set(int id)
 497 {
 498         my_id = id;
 499
 500         set_dynamic_states(my_id);
 501         add_extra_mod_hook(&extra_mod_hook);
 502         add_hook(match_array_assignment, ASSIGNMENT_HOOK);
 503         add_unmatched_state_hook(my_id, &unmatched_state);
 504         add_merge_hook(my_id, &merge_estates);
 505         add_split_return_callback(&print_return_value_param);
 506         register_ignored_params_from_file();
 507 }
 508