1 /* Classes for representing the state of interest at a given path of analysis. 2 Copyright (C) 2019-2022 Free Software Foundation, Inc. 3 Contributed by David Malcolm <dmalcolm@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #ifndef GCC_ANALYZER_PROGRAM_STATE_H 22 #define GCC_ANALYZER_PROGRAM_STATE_H 23 24 namespace ana { 25 26 /* Data shared by all program_state instances. */ 27 28 class extrinsic_state 29 { 30 public: 31 extrinsic_state (auto_delete_vec <state_machine> &checkers, 32 engine *eng, 33 logger *logger = NULL) m_checkers(checkers)34 : m_checkers (checkers), m_logger (logger), m_engine (eng) 35 { 36 } 37 get_sm(int idx)38 const state_machine &get_sm (int idx) const 39 { 40 return *m_checkers[idx]; 41 } 42 get_name(int idx)43 const char *get_name (int idx) const 44 { 45 return m_checkers[idx]->get_name (); 46 } 47 get_num_checkers()48 unsigned get_num_checkers () const { return m_checkers.length (); } 49 get_logger()50 logger *get_logger () const { return m_logger; } 51 52 void dump_to_pp (pretty_printer *pp) const; 53 void dump_to_file (FILE *outf) const; 54 void dump () const; 55 56 json::object *to_json () const; 57 get_engine()58 engine *get_engine () const { return m_engine; } 59 region_model_manager *get_model_manager () const; 60 61 bool get_sm_idx_by_name (const char *name, unsigned *out) const; 62 63 private: 64 /* The state machines. */ 65 auto_delete_vec <state_machine> &m_checkers; 66 67 logger *m_logger; 68 engine *m_engine; 69 }; 70 71 /* Map from svalue * to state machine state, also capturing the origin of 72 each state. */ 73 74 class sm_state_map 75 { 76 public: 77 /* An entry in the hash_map. */ 78 struct entry_t 79 { 80 /* Default ctor needed by hash_map::empty. */ entry_tentry_t81 entry_t () 82 : m_state (0), m_origin (NULL) 83 { 84 } 85 entry_tentry_t86 entry_t (state_machine::state_t state, 87 const svalue *origin) 88 : m_state (state), m_origin (origin) 89 {} 90 91 bool operator== (const entry_t &other) const 92 { 93 return (m_state == other.m_state 94 && m_origin == other.m_origin); 95 } 96 bool operator!= (const entry_t &other) const 97 { 98 return !(*this == other); 99 } 100 101 static int cmp (const entry_t &entry_a, const entry_t &entry_b); 102 103 state_machine::state_t m_state; 104 const svalue *m_origin; 105 }; 106 typedef hash_map <const svalue *, entry_t> map_t; 107 typedef map_t::iterator iterator_t; 108 109 sm_state_map (const state_machine &sm); 110 111 sm_state_map *clone () const; 112 113 void print (const region_model *model, 114 bool simple, bool multiline, 115 pretty_printer *pp) const; 116 void dump (bool simple) const; 117 118 json::object *to_json () const; 119 120 bool is_empty_p () const; 121 122 hashval_t hash () const; 123 124 bool operator== (const sm_state_map &other) const; 125 bool operator!= (const sm_state_map &other) const 126 { 127 return !(*this == other); 128 } 129 130 state_machine::state_t get_state (const svalue *sval, 131 const extrinsic_state &ext_state) const; 132 const svalue *get_origin (const svalue *sval, 133 const extrinsic_state &ext_state) const; 134 135 void set_state (region_model *model, 136 const svalue *sval, 137 state_machine::state_t state, 138 const svalue *origin, 139 const extrinsic_state &ext_state); 140 bool set_state (const equiv_class &ec, 141 state_machine::state_t state, 142 const svalue *origin, 143 const extrinsic_state &ext_state); 144 bool impl_set_state (const svalue *sval, 145 state_machine::state_t state, 146 const svalue *origin, 147 const extrinsic_state &ext_state); 148 149 void set_global_state (state_machine::state_t state); 150 state_machine::state_t get_global_state () const; 151 152 void on_svalue_leak (const svalue *sval, 153 impl_region_model_context *ctxt); 154 void on_liveness_change (const svalue_set &live_svalues, 155 const region_model *model, 156 impl_region_model_context *ctxt); 157 158 void on_unknown_change (const svalue *sval, 159 bool is_mutable, 160 const extrinsic_state &ext_state); 161 162 void purge_state_involving (const svalue *sval, 163 const extrinsic_state &ext_state); 164 begin()165 iterator_t begin () const { return m_map.begin (); } end()166 iterator_t end () const { return m_map.end (); } elements()167 size_t elements () const { return m_map.elements (); } 168 169 static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b); 170 171 static const svalue * 172 canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state); 173 174 private: 175 const state_machine &m_sm; 176 map_t m_map; 177 state_machine::state_t m_global_state; 178 }; 179 180 /* A class for representing the state of interest at a given path of 181 analysis. 182 183 Currently this is a combination of: 184 (a) a region_model, giving: 185 (a.1) a hierarchy of memory regions 186 (a.2) values for the regions 187 (a.3) inequalities between values 188 (b) sm_state_maps per state machine, giving a sparse mapping of 189 values to states. */ 190 191 class program_state 192 { 193 public: 194 program_state (const extrinsic_state &ext_state); 195 program_state (const program_state &other); 196 program_state& operator= (const program_state &other); 197 program_state (program_state &&other); 198 ~program_state (); 199 200 hashval_t hash () const; 201 bool operator== (const program_state &other) const; 202 bool operator!= (const program_state &other) const 203 { 204 return !(*this == other); 205 } 206 207 void print (const extrinsic_state &ext_state, 208 pretty_printer *pp) const; 209 210 void dump_to_pp (const extrinsic_state &ext_state, bool simple, 211 bool multiline, pretty_printer *pp) const; 212 void dump_to_file (const extrinsic_state &ext_state, bool simple, 213 bool multiline, FILE *outf) const; 214 void dump (const extrinsic_state &ext_state, bool simple) const; 215 216 json::object *to_json (const extrinsic_state &ext_state) const; 217 218 void push_frame (const extrinsic_state &ext_state, function *fun); 219 function * get_current_function () const; 220 221 void push_call (exploded_graph &eg, 222 exploded_node *enode, 223 const gcall *call_stmt, 224 uncertainty_t *uncertainty); 225 226 void returning_call (exploded_graph &eg, 227 exploded_node *enode, 228 const gcall *call_stmt, 229 uncertainty_t *uncertainty); 230 231 232 bool on_edge (exploded_graph &eg, 233 exploded_node *enode, 234 const superedge *succ, 235 uncertainty_t *uncertainty); 236 237 program_state prune_for_point (exploded_graph &eg, 238 const program_point &point, 239 exploded_node *enode_for_diag, 240 uncertainty_t *uncertainty) const; 241 242 tree get_representative_tree (const svalue *sval) const; 243 can_purge_p(const extrinsic_state & ext_state,const svalue * sval)244 bool can_purge_p (const extrinsic_state &ext_state, 245 const svalue *sval) const 246 { 247 /* Don't purge vars that have non-purgeable sm state, to avoid 248 generating false "leak" complaints. */ 249 int i; 250 sm_state_map *smap; 251 FOR_EACH_VEC_ELT (m_checker_states, i, smap) 252 { 253 const state_machine &sm = ext_state.get_sm (i); 254 if (!sm.can_purge_p (smap->get_state (sval, ext_state))) 255 return false; 256 } 257 return true; 258 } 259 260 bool can_purge_base_region_p (const extrinsic_state &ext_state, 261 const region *base_reg) const; 262 263 bool can_merge_with_p (const program_state &other, 264 const extrinsic_state &ext_state, 265 const program_point &point, 266 program_state *out) const; 267 268 void validate (const extrinsic_state &ext_state) const; 269 270 static void detect_leaks (const program_state &src_state, 271 const program_state &dest_state, 272 const svalue *extra_sval, 273 const extrinsic_state &ext_state, 274 region_model_context *ctxt); 275 276 void impl_call_analyzer_dump_state (const gcall *call, 277 const extrinsic_state &ext_state, 278 region_model_context *ctxt); 279 280 /* TODO: lose the pointer here (const-correctness issues?). */ 281 region_model *m_region_model; 282 auto_delete_vec<sm_state_map> m_checker_states; 283 284 /* If false, then don't attempt to explore further states along this path. 285 For use in "handling" lvalues for tree codes we haven't yet 286 implemented. */ 287 bool m_valid; 288 }; 289 290 /* An abstract base class for use with for_each_state_change. */ 291 292 class state_change_visitor 293 { 294 public: ~state_change_visitor()295 virtual ~state_change_visitor () {} 296 297 /* Return true for early exit, false to keep iterating. */ 298 virtual bool on_global_state_change (const state_machine &sm, 299 state_machine::state_t src_sm_val, 300 state_machine::state_t dst_sm_val) = 0; 301 302 /* Return true for early exit, false to keep iterating. */ 303 virtual bool on_state_change (const state_machine &sm, 304 state_machine::state_t src_sm_val, 305 state_machine::state_t dst_sm_val, 306 const svalue *dst_sval, 307 const svalue *dst_origin_sval) = 0; 308 }; 309 310 extern bool for_each_state_change (const program_state &src_state, 311 const program_state &dst_state, 312 const extrinsic_state &ext_state, 313 state_change_visitor *visitor); 314 315 } // namespace ana 316 317 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */ 318