/* Classes for modeling the state of memory.
- Copyright (C) 2020 Free Software Foundation, Inc.
+ Copyright (C) 2020-2022 Free Software Foundation, Inc.
Contributed by David Malcolm <dmalcolm@redhat.com>.
This file is part of GCC.
namespace ana {
-class concrete_binding;
+/* A class for keeping track of aspects of a program_state that we don't
+ know about, to avoid false positives about leaks.
+
+ Consider:
+
+ p->field = malloc (1024);
+ q->field = NULL;
+
+ where we don't know whether or not p and q point to the same memory,
+ and:
+
+ p->field = malloc (1024);
+ unknown_fn (p);
+
+ In both cases, the svalue for the address of the allocated buffer
+ goes from being bound to p->field to not having anything explicitly bound
+ to it.
+
+ Given that we conservatively discard bindings due to possible aliasing or
+ calls to unknown function, the store loses references to svalues,
+ but these svalues could still be live. We don't want to warn about
+ them leaking - they're effectively in a "maybe live" state.
-/* An enum for discriminating between "direct" vs "default" levels of
- mapping. */
+ This "maybe live" information is somewhat transient.
-enum binding_kind
+ We don't want to store this "maybe live" information in the program_state,
+ region_model, or store, since we don't want to bloat these objects (and
+ potentially bloat the exploded_graph with more nodes).
+ However, we can't store it in the region_model_context, as these context
+ objects sometimes don't last long enough to be around when comparing the
+ old vs the new state.
+
+ This class is a way to track a set of such svalues, so that we can
+ temporarily capture that they are in a "maybe live" state whilst
+ comparing old and new states. */
+
+class uncertainty_t
{
- /* Special-case value for hash support.
- This is the initial entry, so that hash traits can have
- empty_zero_p = true. */
- BK_empty = 0,
+public:
+ typedef hash_set<const svalue *>::iterator iterator;
- /* Special-case value for hash support. */
- BK_deleted,
+ void on_maybe_bound_sval (const svalue *sval)
+ {
+ m_maybe_bound_svals.add (sval);
+ }
+ void on_mutable_sval_at_unknown_call (const svalue *sval)
+ {
+ m_mutable_at_unknown_call_svals.add (sval);
+ }
- /* The normal kind of mapping. */
- BK_direct,
+ bool unknown_sm_state_p (const svalue *sval)
+ {
+ return (m_maybe_bound_svals.contains (sval)
+ || m_mutable_at_unknown_call_svals.contains (sval));
+ }
+
+ void dump_to_pp (pretty_printer *pp, bool simple) const;
+ void dump (bool simple) const;
- /* A lower-priority kind of mapping, for use when inheriting
- default values from a parent region. */
- BK_default
+ iterator begin_maybe_bound_svals () const
+ {
+ return m_maybe_bound_svals.begin ();
+ }
+ iterator end_maybe_bound_svals () const
+ {
+ return m_maybe_bound_svals.end ();
+ }
+
+private:
+
+ /* svalues that might or might not still be bound. */
+ hash_set<const svalue *> m_maybe_bound_svals;
+
+ /* svalues that have mutable sm-state at unknown calls. */
+ hash_set<const svalue *> m_mutable_at_unknown_call_svals;
};
-extern const char *binding_kind_to_string (enum binding_kind kind);
+class byte_range;
+class concrete_binding;
+class symbolic_binding;
/* Abstract base class for describing ranges of bits within a binding_map
that can have svalues bound to them. */
virtual bool concrete_p () const = 0;
bool symbolic_p () const { return !concrete_p (); }
- static const binding_key *make (store_manager *mgr, const region *r,
- enum binding_kind kind);
+ static const binding_key *make (store_manager *mgr, const region *r);
- virtual void dump_to_pp (pretty_printer *pp, bool simple) const;
+ virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
void dump (bool simple) const;
label_text get_desc (bool simple=true) const;
virtual const concrete_binding *dyn_cast_concrete_binding () const
{ return NULL; }
+ virtual const symbolic_binding *dyn_cast_symbolic_binding () const
+ { return NULL; }
+};
- enum binding_kind get_kind () const { return m_kind; }
+/* A concrete range of bits. */
- void mark_deleted () { m_kind = BK_deleted; }
- void mark_empty () { m_kind = BK_empty; }
- bool is_deleted () const { return m_kind == BK_deleted; }
- bool is_empty () const { return m_kind == BK_empty; }
+struct bit_range
+{
+ bit_range (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
+ : m_start_bit_offset (start_bit_offset),
+ m_size_in_bits (size_in_bits)
+ {}
-protected:
- binding_key (enum binding_kind kind) : m_kind (kind) {}
+ void dump_to_pp (pretty_printer *pp) const;
+ void dump () const;
- hashval_t impl_hash () const
+ bit_offset_t get_start_bit_offset () const
{
- return m_kind;
+ return m_start_bit_offset;
}
- bool impl_eq (const binding_key &other) const
+ bit_offset_t get_next_bit_offset () const
{
- return m_kind == other.m_kind;
+ return m_start_bit_offset + m_size_in_bits;
+ }
+ bit_offset_t get_last_bit_offset () const
+ {
+ return get_next_bit_offset () - 1;
}
-private:
- enum binding_kind m_kind;
+ bool contains_p (bit_offset_t offset) const
+ {
+ return (offset >= get_start_bit_offset ()
+ && offset < get_next_bit_offset ());
+ }
+
+ bool contains_p (const bit_range &other, bit_range *out) const;
+
+ bool operator== (const bit_range &other) const
+ {
+ return (m_start_bit_offset == other.m_start_bit_offset
+ && m_size_in_bits == other.m_size_in_bits);
+ }
+
+ bool intersects_p (const bit_range &other) const
+ {
+ return (get_start_bit_offset () < other.get_next_bit_offset ()
+ && other.get_start_bit_offset () < get_next_bit_offset ());
+ }
+ bool intersects_p (const bit_range &other,
+ bit_range *out_this,
+ bit_range *out_other) const;
+
+ static int cmp (const bit_range &br1, const bit_range &br2);
+
+ bit_range operator- (bit_offset_t offset) const;
+
+ static bool from_mask (unsigned HOST_WIDE_INT mask, bit_range *out);
+
+ bool as_byte_range (byte_range *out) const;
+
+ bit_offset_t m_start_bit_offset;
+ bit_size_t m_size_in_bits;
+};
+
+/* A concrete range of bytes. */
+
+struct byte_range
+{
+ byte_range (byte_offset_t start_byte_offset, byte_size_t size_in_bytes)
+ : m_start_byte_offset (start_byte_offset),
+ m_size_in_bytes (size_in_bytes)
+ {}
+
+ void dump_to_pp (pretty_printer *pp) const;
+ void dump () const;
+
+ bool contains_p (byte_offset_t offset) const
+ {
+ return (offset >= get_start_byte_offset ()
+ && offset < get_next_byte_offset ());
+ }
+ bool contains_p (const byte_range &other, byte_range *out) const;
+
+ bool operator== (const byte_range &other) const
+ {
+ return (m_start_byte_offset == other.m_start_byte_offset
+ && m_size_in_bytes == other.m_size_in_bytes);
+ }
+
+ byte_offset_t get_start_byte_offset () const
+ {
+ return m_start_byte_offset;
+ }
+ byte_offset_t get_next_byte_offset () const
+ {
+ return m_start_byte_offset + m_size_in_bytes;
+ }
+ byte_offset_t get_last_byte_offset () const
+ {
+ return m_start_byte_offset + m_size_in_bytes - 1;
+ }
+
+ bit_range as_bit_range () const
+ {
+ return bit_range (m_start_byte_offset * BITS_PER_UNIT,
+ m_size_in_bytes * BITS_PER_UNIT);
+ }
+
+ static int cmp (const byte_range &br1, const byte_range &br2);
+
+ byte_offset_t m_start_byte_offset;
+ byte_size_t m_size_in_bytes;
};
/* Concrete subclass of binding_key, for describing a concrete range of
/* This class is its own key for the purposes of consolidation. */
typedef concrete_binding key_t;
- concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits,
- enum binding_kind kind)
- : binding_key (kind),
- m_start_bit_offset (start_bit_offset),
- m_size_in_bits (size_in_bits)
+ concrete_binding (bit_offset_t start_bit_offset, bit_size_t size_in_bits)
+ : m_bit_range (start_bit_offset, size_in_bits)
{}
bool concrete_p () const FINAL OVERRIDE { return true; }
hashval_t hash () const
{
inchash::hash hstate;
- hstate.add_wide_int (m_start_bit_offset);
- hstate.add_wide_int (m_size_in_bits);
- return hstate.end () ^ binding_key::impl_hash ();
+ hstate.add_wide_int (m_bit_range.m_start_bit_offset);
+ hstate.add_wide_int (m_bit_range.m_size_in_bits);
+ return hstate.end ();
}
bool operator== (const concrete_binding &other) const
{
- if (!binding_key::impl_eq (other))
- return false;
- return (m_start_bit_offset == other.m_start_bit_offset
- && m_size_in_bits == other.m_size_in_bits);
+ return m_bit_range == other.m_bit_range;
}
void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
const concrete_binding *dyn_cast_concrete_binding () const FINAL OVERRIDE
{ return this; }
- bit_offset_t get_start_bit_offset () const { return m_start_bit_offset; }
- bit_size_t get_size_in_bits () const { return m_size_in_bits; }
+ const bit_range &get_bit_range () const { return m_bit_range; }
+
+ bit_offset_t get_start_bit_offset () const
+ {
+ return m_bit_range.m_start_bit_offset;
+ }
+ bit_size_t get_size_in_bits () const
+ {
+ return m_bit_range.m_size_in_bits;
+ }
/* Return the next bit offset after the end of this binding. */
bit_offset_t get_next_bit_offset () const
{
- return m_start_bit_offset + m_size_in_bits;
+ return m_bit_range.get_next_bit_offset ();
}
bool overlaps_p (const concrete_binding &other) const;
static int cmp_ptr_ptr (const void *, const void *);
+ void mark_deleted () { m_bit_range.m_start_bit_offset = -1; }
+ void mark_empty () { m_bit_range.m_start_bit_offset = -2; }
+ bool is_deleted () const { return m_bit_range.m_start_bit_offset == -1; }
+ bool is_empty () const { return m_bit_range.m_start_bit_offset == -2; }
+
private:
- bit_offset_t m_start_bit_offset;
- bit_size_t m_size_in_bits;
+ bit_range m_bit_range;
};
} // namespace ana
template <> struct default_hash_traits<ana::concrete_binding>
: public member_function_hash_traits<ana::concrete_binding>
{
- static const bool empty_zero_p = true;
+ static const bool empty_zero_p = false;
};
namespace ana {
/* This class is its own key for the purposes of consolidation. */
typedef symbolic_binding key_t;
- symbolic_binding (const region *region, enum binding_kind kind)
- : binding_key (kind),
- m_region (region)
- {}
+ symbolic_binding (const region *region) : m_region (region) {}
bool concrete_p () const FINAL OVERRIDE { return false; }
hashval_t hash () const
{
- return (binding_key::impl_hash () ^ (long)m_region);
+ return (intptr_t)m_region;
}
bool operator== (const symbolic_binding &other) const
{
- if (!binding_key::impl_eq (other))
- return false;
- return (m_region == other.m_region);
+ return m_region == other.m_region;
}
void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE;
+ const symbolic_binding *dyn_cast_symbolic_binding () const FINAL OVERRIDE
+ { return this; }
+
const region *get_region () const { return m_region; }
static int cmp_ptr_ptr (const void *, const void *);
+ void mark_deleted () { m_region = reinterpret_cast<const region *> (1); }
+ void mark_empty () { m_region = NULL; }
+ bool is_deleted () const
+ { return m_region == reinterpret_cast<const region *> (1); }
+ bool is_empty () const { return m_region == NULL; }
+
private:
const region *m_region;
};
static int cmp (const binding_map &map1, const binding_map &map2);
+ void remove_overlapping_bindings (store_manager *mgr,
+ const binding_key *drop_key,
+ uncertainty_t *uncertainty);
+
private:
+ void get_overlapping_bindings (const binding_key *key,
+ auto_vec<const binding_key *> *out);
bool apply_ctor_val_to_range (const region *parent_reg,
region_model_manager *mgr,
tree min_index, tree max_index,
void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
void dump (bool simple) const;
+ void validate () const;
+
json::object *to_json () const;
- void bind (store_manager *mgr, const region *, const svalue *,
- binding_kind kind);
+ void bind (store_manager *mgr, const region *, const svalue *);
void clobber_region (store_manager *mgr, const region *reg);
void purge_region (store_manager *mgr, const region *reg);
+ void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
void zero_fill_region (store_manager *mgr, const region *reg);
- void mark_region_as_unknown (store_manager *mgr, const region *reg);
+ void mark_region_as_unknown (store_manager *mgr, const region *reg,
+ uncertainty_t *uncertainty);
+ void purge_state_involving (const svalue *sval,
+ region_model_manager *sval_mgr);
- const svalue *get_binding (store_manager *mgr, const region *reg,
- binding_kind kind) const;
+ const svalue *get_binding (store_manager *mgr, const region *reg) const;
const svalue *get_binding_recursive (store_manager *mgr,
- const region *reg,
- enum binding_kind kind) const;
+ const region *reg) const;
const svalue *get_any_binding (store_manager *mgr,
const region *reg) const;
const svalue *maybe_get_compound_binding (store_manager *mgr,
const region *reg) const;
- void remove_overlapping_bindings (store_manager *mgr, const region *reg);
+ void remove_overlapping_bindings (store_manager *mgr, const region *reg,
+ uncertainty_t *uncertainty);
template <typename T>
void for_each_value (void (*cb) (const svalue *sval, T user_data),
- T user_data)
+ T user_data) const
{
for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
cb ((*iter).second, user_data);
static bool can_merge_p (const binding_cluster *cluster_a,
const binding_cluster *cluster_b,
binding_cluster *out_cluster,
+ store *out_store,
store_manager *mgr,
model_merger *merger);
void make_unknown_relative_to (const binding_cluster *other_cluster,
+ store *out_store,
store_manager *mgr);
void mark_as_escaped ();
void on_unknown_fncall (const gcall *call, store_manager *mgr);
+ void on_asm (const gasm *stmt, store_manager *mgr);
bool escaped_p () const { return m_escaped; }
bool touched_p () const { return m_touched; }
const svalue *maybe_get_simple_value (store_manager *mgr) const;
template <typename BindingVisitor>
- void for_each_binding (BindingVisitor &v)
+ void for_each_binding (BindingVisitor &v) const
{
for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter)
{
private:
const svalue *get_any_value (const binding_key *key) const;
- void get_overlapping_bindings (store_manager *mgr, const region *reg,
- auto_vec<const binding_key *> *out);
void bind_compound_sval (store_manager *mgr,
const region *reg,
const compound_svalue *compound_sval);
void dump (bool simple) const;
void summarize_to_pp (pretty_printer *pp, bool simple) const;
+ void validate () const;
+
json::object *to_json () const;
- const svalue *get_direct_binding (store_manager *mgr, const region *reg);
- const svalue *get_default_binding (store_manager *mgr, const region *reg);
const svalue *get_any_binding (store_manager *mgr, const region *reg) const;
bool called_unknown_fn_p () const { return m_called_unknown_fn; }
void set_value (store_manager *mgr, const region *lhs_reg,
- const svalue *rhs_sval, enum binding_kind kind);
+ const svalue *rhs_sval,
+ uncertainty_t *uncertainty);
void clobber_region (store_manager *mgr, const region *reg);
void purge_region (store_manager *mgr, const region *reg);
+ void fill_region (store_manager *mgr, const region *reg, const svalue *sval);
void zero_fill_region (store_manager *mgr, const region *reg);
- void mark_region_as_unknown (store_manager *mgr, const region *reg);
+ void mark_region_as_unknown (store_manager *mgr, const region *reg,
+ uncertainty_t *uncertainty);
+ void purge_state_involving (const svalue *sval,
+ region_model_manager *sval_mgr);
const binding_cluster *get_cluster (const region *base_reg) const;
binding_cluster *get_cluster (const region *base_reg);
/* binding consolidation. */
const concrete_binding *
get_concrete_binding (bit_offset_t start_bit_offset,
- bit_offset_t size_in_bits,
- enum binding_kind kind);
+ bit_offset_t size_in_bits);
+ const concrete_binding *
+ get_concrete_binding (const bit_range &bits)
+ {
+ return get_concrete_binding (bits.get_start_bit_offset (),
+ bits.m_size_in_bits);
+ }
const symbolic_binding *
- get_symbolic_binding (const region *region,
- enum binding_kind kind);
+ get_symbolic_binding (const region *region);
region_model_manager *get_svalue_manager () const
{
projects / thirdparty / gcc.git / blobdiff