smatch_capped.c

   1 /*
   2  * Copyright (C) 2011 Oracle.  All rights reserved.
   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 trying to make a list of the variables which
  20  * have capped values.  Sometimes we don't know what the
  21  * cap is, for example if we are comparing variables but
  22  * we don't know the values of the variables.  In that
  23  * case we only know that our variable is capped and we
  24  * sort that information here.
  25  */
  26
  27 #include "smatch.h"
  28 #include "smatch_slist.h"
  29 #include "smatch_extra.h"
  30
  31 static int my_id;
  32
  33 STATE(capped);
  34 STATE(uncapped);
  35
  36 static void set_uncapped(struct sm_state *sm, struct expression *mod_expr)
  37 {
  38         set_state(my_id, sm->name, sm->sym, &uncapped);
  39 }
  40
  41 static struct smatch_state *unmatched_state(struct sm_state *sm)
  42 {
  43         struct smatch_state *state;
  44
  45         state = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
  46         if (state && !estate_is_whole(state))
  47                 return &capped;
  48         return &uncapped;
  49 }
  50
  51 static int is_capped_macro(struct expression *expr)
  52 {
  53         char *name;
  54
  55         name = get_macro_name(expr->pos);
  56         if (!name)
  57                 return 0;
  58
  59         if (strcmp(name, "min") == 0)
  60                 return 1;
  61         if (strcmp(name, "MIN") == 0)
  62                 return 1;
  63         if (strcmp(name, "min_t") == 0)
  64                 return 1;
  65
  66         return 0;
  67 }
  68
  69 int is_capped(struct expression *expr)
  70 {
  71         struct symbol *type;
  72         sval_t dummy;
  73
  74         expr = strip_expr(expr);
  75         while (expr && expr->type == EXPR_POSTOP) {
  76                 expr = strip_expr(expr->unop);
  77         }
  78         if (!expr)
  79                 return 0;
  80
  81         type = get_type(expr);
  82         if (is_ptr_type(type))
  83                 return 0;
  84         if (type == &bool_ctype)
  85                 return 0;
  86         if (type_bits(type) >= 0 && type_bits(type) <= 2)
  87                 return 0;
  88
  89         if (get_hard_max(expr, &dummy))
  90                 return 1;
  91
  92         if (is_capped_macro(expr))
  93                 return 1;
  94
  95         if (expr->type == EXPR_BINOP) {
  96                 struct range_list *left_rl, *right_rl;
  97
  98                 if (expr->op == '&')
  99                         return 1;
 100                 if (expr->op == SPECIAL_RIGHTSHIFT)
 101                         return 1;
 102                 if (expr->op == '%' && is_capped(expr->right))
 103                         return 1;
 104                 if (!is_capped(expr->left))
 105                         return 0;
 106                 if (expr->op == '/')
 107                         return 1;
 108                 if (!is_capped(expr->right))
 109                         return 0;
 110                 if (expr->op == '*') {
 111                         get_absolute_rl(expr->left, &left_rl);
 112                         get_absolute_rl(expr->right, &right_rl);
 113                         if (sval_is_negative(rl_min(left_rl)) ||
 114                             sval_is_negative(rl_min(right_rl)))
 115                                 return 0;
 116                 }
 117                 return 1;
 118         }
 119         if (get_state_expr(my_id, expr) == &capped)
 120                 return 1;
 121         return 0;
 122 }
 123
 124 int is_capped_var_sym(const char *name, struct symbol *sym)
 125 {
 126         if (get_state(my_id, name, sym) == &capped)
 127                 return 1;
 128         return 0;
 129 }
 130
 131 void set_param_capped_data(const char *name, struct symbol *sym, char *key, char *value)
 132 {
 133         char fullname[256];
 134
 135         if (strncmp(key, "$", 1))
 136                 return;
 137         snprintf(fullname, 256, "%s%s", name, key + 1);
 138         set_state(my_id, fullname, sym, &capped);
 139 }
 140
 141 static void match_condition(struct expression *expr)
 142 {
 143         struct expression *left, *right;
 144         struct smatch_state *left_true = NULL;
 145         struct smatch_state *left_false = NULL;
 146         struct smatch_state *right_true = NULL;
 147         struct smatch_state *right_false = NULL;
 148         sval_t sval;
 149
 150
 151         if (expr->type != EXPR_COMPARE)
 152                 return;
 153
 154         left = strip_expr(expr->left);
 155         right = strip_expr(expr->right);
 156
 157         while (left->type == EXPR_ASSIGNMENT)
 158                 left = strip_expr(left->left);
 159
 160         /* If we're dealing with known expressions, that's for smatch_extra.c */
 161         if (get_implied_value(left, &sval) ||
 162             get_implied_value(right, &sval))
 163                 return;
 164
 165         switch (expr->op) {
 166         case '<':
 167         case SPECIAL_LTE:
 168         case SPECIAL_UNSIGNED_LT:
 169         case SPECIAL_UNSIGNED_LTE:
 170                 left_true = &capped;
 171                 right_false = &capped;
 172                 break;
 173         case '>':
 174         case SPECIAL_GTE:
 175         case SPECIAL_UNSIGNED_GT:
 176         case SPECIAL_UNSIGNED_GTE:
 177                 left_false = &capped;
 178                 right_true = &capped;
 179                 break;
 180         case SPECIAL_EQUAL:
 181                 left_true = &capped;
 182                 right_true = &capped;
 183                 break;
 184         case SPECIAL_NOTEQUAL:
 185                 left_false = &capped;
 186                 right_false = &capped;
 187                 break;
 188
 189         default:
 190                 return;
 191         }
 192
 193         set_true_false_states_expr(my_id, left, left_true, left_false);
 194         set_true_false_states_expr(my_id, right, right_true, right_false);
 195 }
 196
 197 static void match_assign(struct expression *expr)
 198 {
 199         struct symbol *type;
 200
 201         type = get_type(expr);
 202         if (is_ptr_type(type))
 203                 return;
 204         if (type == &bool_ctype)
 205                 return;
 206         if (type_bits(type) >= 0 && type_bits(type) <= 2)
 207                 return;
 208
 209         if (is_capped(expr->right)) {
 210                 set_state_expr(my_id, expr->left, &capped);
 211         } else {
 212                 if (get_state_expr(my_id, expr->left))
 213                         set_state_expr(my_id, expr->left, &uncapped);
 214         }
 215 }
 216
 217 static void match_caller_info(struct expression *expr)
 218 {
 219         struct expression *tmp;
 220         sval_t sval;
 221         int i;
 222
 223         i = -1;
 224         FOR_EACH_PTR(expr->args, tmp) {
 225                 i++;
 226                 if (get_implied_value(tmp, &sval))
 227                         continue;
 228                 if (!is_capped(tmp))
 229                         continue;
 230                 sql_insert_caller_info(expr, CAPPED_DATA, i, "$", "1");
 231         } END_FOR_EACH_PTR(tmp);
 232 }
 233
 234 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
 235 {
 236         struct smatch_state *estate;
 237         sval_t sval;
 238
 239         if (sm->state != &capped)
 240                 return;
 241         estate = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
 242         if (estate_get_single_value(estate, &sval))
 243                 return;
 244         sql_insert_caller_info(call, CAPPED_DATA, param, printed_name, "1");
 245 }
 246
 247 static void print_return_implies_capped(int return_id, char *return_ranges, struct expression *expr)
 248 {
 249         struct smatch_state *orig, *estate;
 250         struct sm_state *sm;
 251         struct symbol *ret_sym;
 252         const char *param_name;
 253         char *return_str;
 254         int param;
 255         sval_t sval;
 256         bool return_found = false;
 257
 258         expr = strip_expr(expr);
 259         return_str = expr_to_str(expr);
 260         ret_sym = expr_to_sym(expr);
 261
 262         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 263                 if (sm->state != &capped)
 264                         continue;
 265
 266                 param = get_param_num_from_sym(sm->sym);
 267                 if (param < 0)
 268                         continue;
 269
 270                 estate = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
 271                 if (estate_get_single_value(estate, &sval))
 272                         continue;
 273
 274                 orig = get_state_stree(get_start_states(), my_id, sm->name, sm->sym);
 275                 if (orig == &capped && !param_was_set_var_sym(sm->name, sm->sym))
 276                         continue;
 277
 278                 param_name = get_param_name(sm);
 279                 if (!param_name)
 280                         continue;
 281
 282                 sql_insert_return_states(return_id, return_ranges, CAPPED_DATA,
 283                                          param, param_name, "1");
 284         } END_FOR_EACH_SM(sm);
 285
 286         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
 287                 if (!ret_sym)
 288                         break;
 289                 if (sm->state != &capped)
 290                         continue;
 291                 if (ret_sym != sm->sym)
 292                         continue;
 293
 294                 estate = __get_state(SMATCH_EXTRA, sm->name, sm->sym);
 295                 if (estate_get_single_value(estate, &sval))
 296                         continue;
 297
 298                 param_name = state_name_to_param_name(sm->name, return_str);
 299                 if (!param_name)
 300                         continue;
 301                 if (strcmp(param_name, "$") == 0)
 302                         return_found = true;
 303                 sql_insert_return_states(return_id, return_ranges, CAPPED_DATA,
 304                                          -1, param_name, "1");
 305         } END_FOR_EACH_SM(sm);
 306
 307         if (return_found)
 308                 goto free_string;
 309
 310         if (option_project == PROJ_KERNEL && get_function() &&
 311             strstr(get_function(), "nla_get_"))
 312                 sql_insert_return_states(return_id, return_ranges, CAPPED_DATA,
 313                                          -1, "$", "1");
 314
 315 free_string:
 316         free_string(return_str);
 317 }
 318
 319 static void db_return_states_capped(struct expression *expr, int param, char *key, char *value)
 320 {
 321         char *name;
 322         struct symbol *sym;
 323
 324         name = return_state_to_var_sym(expr, param, key, &sym);
 325         if (!name || !sym)
 326                 goto free;
 327
 328         set_state(my_id, name, sym, &capped);
 329 free:
 330         free_string(name);
 331 }
 332
 333 void register_capped(int id)
 334 {
 335         my_id = id;
 336
 337         add_unmatched_state_hook(my_id, &unmatched_state);
 338         select_caller_info_hook(set_param_capped_data, CAPPED_DATA);
 339         add_hook(&match_condition, CONDITION_HOOK);
 340         add_hook(&match_assign, ASSIGNMENT_HOOK);
 341         add_modification_hook(my_id, &set_uncapped);
 342
 343         add_hook(&match_caller_info, FUNCTION_CALL_HOOK);
 344         add_member_info_callback(my_id, struct_member_callback);
 345
 346         add_split_return_callback(print_return_implies_capped);
 347         select_return_states_hook(CAPPED_DATA, &db_return_states_capped);
 348 }