smatch_ssa.c

   1 /*
   2  * Copyright (C) 2021 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  * The truth is I don't know very much about compilers.  I've heard about
  20  * Single Static Assignment and it seems like a useful feature but it's also
  21  * possible I have misunderstood the whole thing.
  22  *
  23  * Anyway, the point is that say we have code like:
  24  * ret = alloc();
  25  * if (ret < 0)
  26  *      return ret;
  27  * p->foo = ret;
  28  * ret = something else;
  29  *
  30  * So the problem here is "p->foo" and "ret" are equivalent at first but then
  31  * not at the end.  We don't really care if "p->foo" is freed or "ret" is freed,
  32  * we care if the value which was initially stored in "ret" is freed.  This is
  33  * different from equiv because "ret" and "p->foo" are not equiv at the end.
  34  * The SSA module doesn't deal with == only with =.
  35  *
  36  * Using this is a bit different and more complicated than I would like.  If
  37  * there is a new state then call set_ssa_state().  When you're getting the
  38  * state it's probably easiest to always use get_ssa_sm_state() because
  39  * afterwards you will need to call update_ssa_state(my_id, sm->name, sm->sym,
  40  * &state); to change the state.  If you call set_ssa_state() that basically
  41  * works too but it's slower because it adds a layer of indirection.
  42  *
  43  */
  44
  45 #include "smatch.h"
  46 #include "smatch_extra.h"
  47 #include "smatch_slist.h"
  48
  49 static int my_id;
  50
  51 static unsigned long ssa_id = 1;
  52
  53 char *ssa_name(const char *name)
  54 {
  55         char *ret;
  56         char *p;
  57
  58         ret = alloc_sname(name);
  59         p = strchr(ret, ':');
  60         if (p)
  61                 *p = '\0';
  62         return ret;
  63 }
  64
  65 static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
  66 {
  67         /* this should be called early before any checks have run */
  68         set_state(my_id, sm->name, sm->sym, &undefined);
  69 }
  70
  71 static struct smatch_state *alloc_ssa_new(const char *name)
  72 {
  73         struct smatch_state *state;
  74         char buf[64];
  75
  76         state = __alloc_smatch_state(0);
  77         snprintf(buf, sizeof(buf), "%s:%ld", name, ssa_id);
  78         state->name = alloc_sname(buf);
  79
  80         ssa_id++;
  81
  82         return state;
  83 }
  84
  85 static struct smatch_state *alloc_ssa_copy(struct sm_state *sm)
  86 {
  87         struct smatch_state *state;
  88
  89         if (sm->state == &undefined || sm->state == &merged)
  90                 return sm->state;
  91
  92         state = __alloc_smatch_state(0);
  93         state->name = alloc_sname(sm->state->name);
  94         return state;
  95 }
  96
  97 static bool whatever_close_enough(struct expression *left, struct expression *right)
  98 {
  99         struct symbol *left_type, *right_type;
 100
 101         left_type = get_type(left);
 102         right_type = get_type(right);
 103
 104         if (type_bits(right_type) == 64) {
 105                 if (type_bits(left_type) == 64)
 106                         return true;
 107                 return false;
 108         }
 109
 110         if (type_bits(right_type) == 32) {
 111                 if (type_bits(left_type) == 64 || type_bits(left_type) == 32)
 112                         return true;
 113                 return false;
 114         }
 115
 116         return false;
 117 }
 118
 119 static void match_assign(struct expression *expr)
 120 {
 121         struct smatch_state *left_state;
 122         struct sm_state *orig, *clone;
 123         struct symbol *left_sym, *right_sym;
 124         char *left_name = NULL, *right_name = NULL;
 125
 126         if (__in_fake_assign)
 127                 return;
 128
 129         if (expr->op != '=')
 130                 return;
 131
 132         /* The whatever function is more likely to return true #Faster */
 133         if (!whatever_close_enough(expr->left, expr->right) &&
 134             !values_fit_type(expr->left, expr->right))
 135                 return;
 136
 137         left_name = expr_to_var_sym(expr->left, &left_sym);
 138         if (!left_name)
 139                 goto free;
 140
 141         /*
 142          * The ordering of this is really tricky.  The issue here is that we
 143          * have: "dev = of_node_get(node);".  The first thing that happens is
 144          * the modified hook sets "dev" to undefined.  Then the check for
 145          * tracking of_node_get/put() allocates an ssa state for "dev".  So if
 146          * it's set here we can just return.  Otherwise track the SSA state.
 147          */
 148         left_state = get_state(my_id, left_name, left_sym);
 149         if (left_state && left_state != &undefined)
 150                 goto free;
 151
 152         right_name = expr_to_var_sym(expr->right, &right_sym);
 153         if (!right_name)
 154                 goto free;
 155
 156         orig = get_sm_state(my_id, right_name, right_sym);
 157         if (!orig || orig->state == &undefined)
 158                 orig = set_state(my_id, right_name, right_sym, alloc_ssa_new(right_name));
 159
 160         /* This can happen in unreachable code or outside of functions I gess */
 161         if (!orig)
 162                 return;
 163
 164         /*
 165          * Cloning is only really necessary for &merged states but it's better
 166          * to only have one code path where possible.
 167          *
 168          */
 169         clone        = clone_sm(orig);
 170         clone->state = alloc_ssa_copy(orig);
 171         clone->name  = alloc_sname(left_name);
 172         clone->sym   = left_sym;
 173         __set_sm(clone);
 174
 175 free:
 176         free_string(left_name);
 177         free_string(right_name);
 178 }
 179
 180 void set_ssa_state(int owner, const char *name, struct symbol *sym,
 181                struct smatch_state *state)
 182 {
 183         struct sm_state *sm;
 184
 185         if (!name)
 186                 return;
 187
 188         sm = get_sm_state(my_id, name, sym);
 189         if (!sm || sm->state == &undefined)
 190                 sm = set_state(my_id, name, sym, alloc_ssa_new(name));
 191         if (!sm)
 192                 return;
 193         if (sm->state == &merged) {
 194                 sm = clone_sm(sm);
 195                 sm->state = alloc_ssa_new(name);
 196                 add_possible_sm(sm, sm);
 197                 __set_sm(sm);
 198         }
 199         if (!sm)
 200                 return;
 201         set_state(owner, sm->state->name, NULL, state);
 202 }
 203
 204 void update_ssa_state(int owner, const char *name, struct symbol *sym,
 205                       struct smatch_state *state)
 206 {
 207         set_state(owner, name, NULL, state);
 208 }
 209
 210 void set_ssa_state_expr(int owner, struct expression *expr,
 211                 struct smatch_state *state)
 212 {
 213         struct symbol *sym;
 214         char *name;
 215
 216         name = expr_to_var_sym(expr, &sym);
 217         if (!name)
 218                 return;
 219         set_ssa_state(owner, name, sym, state);
 220         free_string(name);
 221 }
 222
 223 struct sm_state *get_ssa_sm_state(int owner, const char *name, struct symbol *sym)
 224 {
 225         struct sm_state *sm, *ret, *tmp;
 226
 227         // TODO: what about if it is merged because one state is &alloc and the
 228         //       other state is NULL/uninitialized
 229
 230         sm = get_sm_state(my_id, name, sym);
 231         if (!sm || sm->state == &undefined)
 232                 return NULL;
 233
 234         ret = get_sm_state(owner, sm->state->name, NULL);
 235         if (ret)
 236                 return ret;
 237
 238         FOR_EACH_PTR(sm->possible, tmp) {
 239                 if (tmp == sm ||
 240                     tmp->state == &merged ||
 241                     tmp->state == &undefined)
 242                         continue;
 243                 ret = get_sm_state(owner, tmp->state->name, NULL);
 244                 if (ret)
 245                         return ret;
 246         } END_FOR_EACH_PTR(tmp);
 247
 248         return NULL;
 249 }
 250
 251 /*
 252  * This function uses the SSA infrastructure instead of smatch_assigned.c
 253  * to set all the other names of a variable.
 254  *
 255  */
 256 void ssa_set_all_states(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
 257 {
 258         struct sm_state *sm, *tmp;
 259
 260         set_state(owner, name, sym, state);
 261
 262         sm = get_sm_state(my_id, name, sym);
 263         if (!sm || sm->state == &undefined || sm->state == &merged)
 264                 return;
 265
 266         FOR_EACH_MY_SM(my_id, __get_cur_stree(), tmp) {
 267                 if (strcmp(tmp->state->name, sm->state->name) != 0)
 268                         continue;
 269                 set_state(owner, tmp->name, tmp->sym, state);
 270         } END_FOR_EACH_SM(tmp);
 271 }
 272
 273 void ssa_set_all_states_expr(int owner, struct expression *expr, struct smatch_state *state)
 274 {
 275         struct symbol *sym;
 276         char *name;
 277
 278         name = expr_to_var_sym(expr, &sym);
 279         if (!name || !sym)
 280                 return;
 281         ssa_set_all_states(owner, name, sym, state);
 282         free_string(name);
 283 }
 284
 285 struct sm_state *get_ssa_sm_state_expr(int owner, struct expression *expr)
 286 {
 287         struct sm_state *ret;
 288         struct symbol *sym;
 289         char *name;
 290
 291         name = expr_to_var_sym(expr, &sym);
 292         if (!name)
 293                 return NULL;
 294         ret = get_ssa_sm_state(owner, name, sym);
 295         free_string(name);
 296         return ret;
 297 }
 298
 299 struct smatch_state *get_ssa_state(int owner, const char *name, struct symbol *sym)
 300 {
 301         struct sm_state *sm;
 302
 303         sm = get_ssa_sm_state(my_id, name, sym);
 304         if (!sm)
 305                 return NULL;
 306         return sm->state;
 307 }
 308
 309 struct smatch_state *get_ssa_state_expr(int owner, struct expression *expr)
 310 {
 311         struct sm_state *sm;
 312
 313         sm = get_ssa_sm_state_expr(my_id, expr);
 314         if (!sm)
 315                 return NULL;
 316         return sm->state;
 317 }
 318
 319 void register_ssa(int id)
 320 {
 321         my_id = id;
 322
 323         set_dynamic_states(my_id);
 324         add_hook(&match_assign, ASSIGNMENT_HOOK_AFTER);
 325         add_modification_hook(my_id, &set_undefined);
 326 }
 327