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 struct smatch_state *alloc_ssa_new(const char *name)
  66 {
  67         struct smatch_state *state;
  68         char buf[64];
  69
  70         state = __alloc_smatch_state(0);
  71         snprintf(buf, sizeof(buf), "%s:%ld", name, ssa_id);
  72         state->name = alloc_sname(buf);
  73
  74         ssa_id++;
  75
  76         return state;
  77 }
  78
  79 static struct smatch_state *alloc_ssa_copy(struct sm_state *sm)
  80 {
  81         struct smatch_state *state;
  82
  83         if (sm->state == &undefined || sm->state == &merged)
  84                 return sm->state;
  85
  86         state = __alloc_smatch_state(0);
  87         state->name = alloc_sname(sm->state->name);
  88         return state;
  89 }
  90
  91 static bool whatever_close_enough(struct expression *left, struct expression *right)
  92 {
  93         struct symbol *left_type, *right_type;
  94
  95         left_type = get_type(left);
  96         right_type = get_type(right);
  97
  98         if (type_bits(right_type) == 64) {
  99                 if (type_bits(left_type) == 64)
 100                         return true;
 101                 return false;
 102         }
 103
 104         if (type_bits(right_type) == 32) {
 105                 if (type_bits(left_type) == 64 || type_bits(left_type) == 32)
 106                         return true;
 107                 return false;
 108         }
 109
 110         return false;
 111 }
 112
 113 static void match_assign(struct expression *expr)
 114 {
 115         struct smatch_state *left_state;
 116         struct sm_state *orig, *clone;
 117         struct symbol *left_sym, *right_sym;
 118         char *left_name = NULL, *right_name = NULL;
 119
 120         if (__in_fake_assign)
 121                 return;
 122
 123         if (expr->op != '=')
 124                 return;
 125
 126         /* The whatever function is more likely to return true #Faster */
 127         if (!whatever_close_enough(expr->left, expr->right) &&
 128             !values_fit_type(expr->left, expr->right))
 129                 return;
 130
 131         left_name = expr_to_var_sym(expr->left, &left_sym);
 132         if (!left_name)
 133                 goto free;
 134
 135         /*
 136          * The ordering of this is really tricky.  The issue here is that we
 137          * have: "dev = of_node_get(node);".  The first thing that happens is
 138          * the modified hook sets "dev" to undefined.  Then the check for
 139          * tracking of_node_get/put() allocates an ssa state for "dev".  So if
 140          * it's set here we can just return.  Otherwise track the SSA state.
 141          */
 142         left_state = get_state(my_id, left_name, left_sym);
 143         if (left_state && left_state != &undefined)
 144                 goto free;
 145
 146         right_name = expr_to_var_sym(expr->right, &right_sym);
 147         if (!right_name)
 148                 goto free;
 149
 150         orig = get_sm_state(my_id, right_name, right_sym);
 151         if (!orig || orig->state == &undefined)
 152                 orig = set_state(my_id, right_name, right_sym, alloc_ssa_new(right_name));
 153
 154         /* This can happen in unreachable code or outside of functions I guess */
 155         if (!orig)
 156                 return;
 157
 158         /*
 159          * Cloning is only really necessary for &merged states but it's better
 160          * to only have one code path where possible.
 161          *
 162          */
 163         clone        = clone_sm(orig);
 164         clone->state = alloc_ssa_copy(orig);
 165         clone->name  = alloc_sname(left_name);
 166         clone->sym   = left_sym;
 167         __set_sm(clone);
 168
 169 free:
 170         free_string(left_name);
 171         free_string(right_name);
 172 }
 173
 174 void set_ssa_state(int owner, const char *name, struct symbol *sym,
 175                struct smatch_state *state)
 176 {
 177         struct sm_state *sm;
 178
 179         if (!name)
 180                 return;
 181
 182         sm = get_sm_state(my_id, name, sym);
 183         if (!sm || sm->state == &undefined)
 184                 sm = set_state(my_id, name, sym, alloc_ssa_new(name));
 185         if (!sm)
 186                 return;
 187         if (sm->state == &merged) {
 188                 sm = clone_sm(sm);
 189                 sm->state = alloc_ssa_new(name);
 190                 add_possible_sm(sm, sm);
 191                 __set_sm(sm);
 192         }
 193         if (!sm)
 194                 return;
 195         set_state(owner, sm->state->name, NULL, state);
 196 }
 197
 198 void update_ssa_state(int owner, const char *name, struct symbol *sym,
 199                       struct smatch_state *state)
 200 {
 201         set_state(owner, name, NULL, state);
 202 }
 203
 204 void update_ssa_sm(int owner, struct sm_state *ssa_sm, struct smatch_state *state)
 205 {
 206         struct sm_state *tmp;
 207
 208         FOR_EACH_PTR(ssa_sm->possible, tmp) {
 209                 if (tmp->state == &merged ||
 210                     tmp->state == &undefined)
 211                         continue;
 212                 set_state(owner, tmp->state->name, NULL, state);
 213         } END_FOR_EACH_PTR(tmp);
 214 }
 215
 216 void set_ssa_state_expr(int owner, struct expression *expr,
 217                 struct smatch_state *state)
 218 {
 219         struct symbol *sym;
 220         char *name;
 221
 222         name = expr_to_var_sym(expr, &sym);
 223         if (!name)
 224                 return;
 225         set_ssa_state(owner, name, sym, state);
 226         free_string(name);
 227 }
 228
 229 struct sm_state *get_ssa_sm_state(int owner, const char *name, struct symbol *sym)
 230 {
 231         struct sm_state *sm, *tmp, *owner_sm;
 232         struct sm_state *ret = NULL;
 233
 234         sm = get_sm_state(my_id, name, sym);
 235         if (!sm || sm->state == &undefined)
 236                 return NULL;
 237
 238         FOR_EACH_PTR(sm->possible, tmp) {
 239                 if (tmp->state == &merged ||
 240                     tmp->state == &undefined)
 241                         continue;
 242                 owner_sm = get_sm_state(owner, tmp->state->name, NULL);
 243                 if (owner_sm) {
 244                         if (!ret)
 245                                 ret = clone_sm(owner_sm);
 246                         else
 247                                 ret = merge_sm_states(ret, owner_sm);
 248                 }
 249         } END_FOR_EACH_PTR(tmp);
 250
 251         if (!ret)
 252                 return NULL;
 253
 254         tmp = ret;
 255         ret = clone_sm(sm);
 256         ret->state = tmp->state;
 257
 258         return ret;
 259 }
 260
 261 struct sm_state *get_ssa_sm_state_expr(int owner, struct expression *expr)
 262 {
 263         struct sm_state *ret;
 264         struct symbol *sym;
 265         char *name;
 266
 267         name = expr_to_var_sym(expr, &sym);
 268         if (!name)
 269                 return NULL;
 270         ret = get_ssa_sm_state(owner, name, sym);
 271         free_string(name);
 272         return ret;
 273 }
 274
 275 struct smatch_state *get_ssa_state(int owner, const char *name, struct symbol *sym)
 276 {
 277         struct sm_state *sm;
 278
 279         sm = get_ssa_sm_state(my_id, name, sym);
 280         if (!sm)
 281                 return NULL;
 282         return sm->state;
 283 }
 284
 285 struct smatch_state *get_ssa_state_expr(int owner, struct expression *expr)
 286 {
 287         struct sm_state *sm;
 288
 289         sm = get_ssa_sm_state_expr(my_id, expr);
 290         if (!sm)
 291                 return NULL;
 292         return sm->state;
 293 }
 294
 295 void register_ssa(int id)
 296 {
 297         my_id = id;
 298
 299         set_dynamic_states(my_id);
 300         add_hook(&match_assign, ASSIGNMENT_HOOK_AFTER);
 301         add_modification_hook(my_id, &set_undefined);
 302 }
 303