ROSE  0.9.9.109
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList Class Reference

Description

Simple list-based memory state.

MemoryCellList uses a list of MemoryCell objects to represent the memory state. Each memory cell contains at least an address and a value, both of which have a run-time width. The default MemoryCellList configuration restricts memory cell values to be one byte wide and requires the caller to perform any necessary byte extraction or concatenation when higher software layers are reading/writing multi-byte values. Using one-byte values simplifies the aliasing calculations. The super class defines a byteRestricted property that can be set to false to allow the memory to store variable-width cell values.

MemoryCellList also provides a scan() method that returns a list of memory cells that alias a specified address. This method can be used by a higher-level readMemory() operation in preference to the usuall MemoryState::readMemory().

There is no requirement that a State use a MemoryCellList as its memory state; it can use any subclass of MemoryState. Since MemoryCellList is derived from MemoryState it must provide virtual allocating constructors, which makes it possible for users to define their own subclasses and use them in the semantic framework.

This implementation stores memory cells in reverse chronological order: the most recently created cells appear at the beginning of the list. Subclasses, of course, are free to reorder the list however they want.

Definition at line 37 of file MemoryCellList.h.

#include <MemoryCellList.h>

Inheritance diagram for Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList:
Inheritance graph
[legend]
Collaboration diagram for Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList:
Collaboration graph
[legend]

Public Types

typedef std::list< MemoryCellPtrCellList
 List of memory cells. More...
 
typedef Sawyer::Container::Set< rose_addr_t > AddressSet
 Set of concrete virtual addresses. More...
 
- Public Types inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState
typedef MemoryStatePtr Ptr
 Shared-ownership pointer for a MemoryState. More...
 

Public Member Functions

virtual MemoryStatePtr create (const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const ROSE_OVERRIDE
 Virtual allocating constructor. More...
 
virtual MemoryStatePtr create (const MemoryCellPtr &protocell) const
 Virtual allocating constructor. More...
 
virtual MemoryStatePtr clone () const ROSE_OVERRIDE
 Virtual allocating copy constructor. More...
 
virtual void clear () ROSE_OVERRIDE
 Clear memory. More...
 
virtual bool merge (const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
 Merge memory states for data flow analysis. More...
 
virtual std::vector< MemoryCellPtrmatchingCells (const MemoryCell::Predicate &) const ROSE_OVERRIDE
 Find all matching cells. More...
 
virtual std::vector< MemoryCellPtrleadingCells (const MemoryCell::Predicate &) const ROSE_OVERRIDE
 Find leading matching cells. More...
 
virtual void eraseMatchingCells (const MemoryCell::Predicate &) ROSE_OVERRIDE
 Remove all matching cells. More...
 
virtual void eraseLeadingCells (const MemoryCell::Predicate &) ROSE_OVERRIDE
 Remove leading matching cells. More...
 
virtual void traverse (MemoryCell::Visitor &) ROSE_OVERRIDE
 Traverse and modify cells. More...
 
virtual SValuePtr readMemory (const SValuePtr &address, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
 Read a value from memory. More...
 
virtual void writeMemory (const SValuePtr &addr, const SValuePtr &value, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
 Write a value to memory. More...
 
virtual void print (std::ostream &, Formatter &) const ROSE_OVERRIDE
 Print a memory state to more than one line of output.
 
template<class Iterator >
CellList scan (Iterator &cursor, const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) const
 Scan cell list to find matching cells. More...
 
virtual CellList scan (const SValuePtr &address, size_t nbits, RiscOperators *addrOps, RiscOperators *valOps, bool &short_circuited) const ROSE_DEPRECATED("use the cursor-based scan instead")
 
virtual MemoryCellPtr get_latest_written_cell () const ROSE_DEPRECATED("use latestWrittenCell instead")
 
virtual MemoryCell::AddressSet getWritersUnion (const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
 Writers for an address. More...
 
virtual MemoryCell::AddressSet getWritersIntersection (const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
 Writers for an address. More...
 
virtual std::set< rose_addr_t > get_latest_writers (const SValuePtr &addr, size_t nbits, RiscOperators *addrOps, RiscOperators *valOps) ROSE_DEPRECATED("use getWritersUnion instead")
 
bool occlusionsErased () const
 Property: erase occluded cells. More...
 
void occlusionsErased (bool b)
 Property: erase occluded cells. More...
 
virtual const CellListget_cells () const
 Returns the list of all memory cells.
 
virtual CellListget_cells ()
 Returns the list of all memory cells.
 
- Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState
void eraseNonWritten ()
 Erase cells that have no writers. More...
 
std::vector< MemoryCellPtrallCells () const
 All cells. More...
 
virtual MemoryCellPtr latestWrittenCell () const
 Property: Cell most recently written.
 
virtual void latestWrittenCell (const MemoryCellPtr &cell)
 Property: Cell most recently written.
 
- Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState
SValuePtr get_addr_protoval () const
 Return the address protoval. More...
 
SValuePtr get_val_protoval () const
 Return the value protoval. More...
 
MergerPtr merger () const
 Property: Merger. More...
 
void merger (const MergerPtr &m)
 Property: Merger. More...
 
bool byteRestricted () const
 Indicates whether memory cell values are required to be eight bits wide. More...
 
void byteRestricted (bool b)
 Indicates whether memory cell values are required to be eight bits wide. More...
 
ByteOrder::Endianness get_byteOrder () const
 Memory byte order.
 
void set_byteOrder (ByteOrder::Endianness bo)
 Memory byte order.
 
void print (std::ostream &stream, const std::string prefix="") const
 Print a memory state to more than one line of output.
 
WithFormatter with_format (Formatter &fmt)
 Used for printing memory states with formatting. More...
 
WithFormatter operator+ (Formatter &fmt)
 Used for printing memory states with formatting. More...
 

Static Public Member Functions

static MemoryCellListPtr instance (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
 Instantiate a new prototypical memory state. More...
 
static MemoryCellListPtr instance (const MemoryCellPtr &protocell)
 Instantiate a new memory state with prototypical memory cell. More...
 
static MemoryCellListPtr instance (const MemoryCellListPtr &other)
 Instantiate a new copy of an existing memory state. More...
 
static MemoryCellListPtr promote (const BaseSemantics::MemoryStatePtr &m)
 Promote a base memory state pointer to a BaseSemantics::MemoryCellList pointer. More...
 
- Static Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState
static MemoryCellStatePtr promote (const BaseSemantics::MemoryStatePtr &m)
 Promote a base memory state pointer to a BaseSemantics::MemoryCellState pointer. More...
 
- Static Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState
static MemoryStatePtr promote (const MemoryStatePtr &x)
 

Protected Member Functions

 MemoryCellList (const MemoryCellPtr &protocell)
 
 MemoryCellList (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
 
 MemoryCellList (const MemoryCellList &other)
 
virtual SValuePtr mergeCellValues (const CellList &cells, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps)
 
virtual AddressSet mergeCellWriters (const CellList &cells)
 
virtual InputOutputPropertySet mergeCellProperties (const CellList &cells)
 
virtual void updateReadProperties (CellList &cells)
 
virtual MemoryCellPtr insertReadCell (const SValuePtr &addr, const SValuePtr &value)
 
virtual MemoryCellPtr insertReadCell (const SValuePtr &addr, const SValuePtr &value, const AddressSet &writers, const InputOutputPropertySet &props)
 
- Protected Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState
 MemoryCellState (const MemoryCellPtr &protocell)
 
 MemoryCellState (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
 
 MemoryCellState (const MemoryCellState &other)
 
- Protected Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState
 MemoryState (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
 
 MemoryState (const MemoryStatePtr &other)
 

Protected Attributes

CellList cells
 
bool occlusionsErased_
 
- Protected Attributes inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState
MemoryCellPtr protocell
 
MemoryCellPtr latestWrittenCell_
 

Member Typedef Documentation

List of memory cells.

Definition at line 39 of file MemoryCellList.h.

Set of concrete virtual addresses.

Definition at line 40 of file MemoryCellList.h.

Member Function Documentation

static MemoryCellListPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::instance ( const SValuePtr addrProtoval,
const SValuePtr valProtoval 
)
inlinestatic

Instantiate a new prototypical memory state.

This constructor uses the default type for the cell type (based on the semantic domain). The prototypical values are usually the same (addresses and stored values are normally the same type).

Definition at line 84 of file MemoryCellList.h.

Referenced by create().

static MemoryCellListPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::instance ( const MemoryCellPtr protocell)
inlinestatic

Instantiate a new memory state with prototypical memory cell.

Definition at line 89 of file MemoryCellList.h.

static MemoryCellListPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::instance ( const MemoryCellListPtr other)
inlinestatic

Instantiate a new copy of an existing memory state.

Definition at line 94 of file MemoryCellList.h.

virtual MemoryStatePtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::create ( const SValuePtr addrProtoval,
const SValuePtr valProtoval 
) const
inlinevirtual

Virtual allocating constructor.

Allocates and constructs a new MemoryState object having the same dynamic type as this object. A prototypical SValue must be supplied and will be used to construct any additional SValue objects needed during the operation of a MemoryState. Two prototypical values are supplied, one for addresses and another for values stored at those addresses, although they will almost always be the same.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState.

Reimplemented in Rose::BinaryAnalysis::InstructionSemantics2::SymbolicSemantics::MemoryListState, and Rose::BinaryAnalysis::InstructionSemantics2::IntervalSemantics::MemoryState.

Definition at line 102 of file MemoryCellList.h.

References instance().

virtual MemoryStatePtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::create ( const MemoryCellPtr protocell) const
inlinevirtual
virtual MemoryStatePtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::clone ( ) const
inlinevirtual
static MemoryCellListPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::promote ( const BaseSemantics::MemoryStatePtr m)
inlinestatic

Promote a base memory state pointer to a BaseSemantics::MemoryCellList pointer.

The memory state m must have a BaseSemantics::MemoryCellList dynamic type.

Definition at line 120 of file MemoryCellList.h.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::clear ( )
virtual

Clear memory.

Removes all memory cells from this memory state.

Reimplemented from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual bool Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::merge ( const MemoryStatePtr other,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Merge memory states for data flow analysis.

Merges the other state into this state, returning true if this state changed.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState.

virtual std::vector<MemoryCellPtr> Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::matchingCells ( const MemoryCell::Predicate ) const
virtual

Find all matching cells.

Returns a vector of cells for which the predicate returns true.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual std::vector<MemoryCellPtr> Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::leadingCells ( const MemoryCell::Predicate ) const
virtual

Find leading matching cells.

Returns the vector of cells obtained by invoking the predicate on each cell and returning those leading cells for which the predicate is true. The first cell for which the predicate is false terminates the traversal and does not appear in the return value.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::eraseMatchingCells ( const MemoryCell::Predicate )
virtual

Remove all matching cells.

Traverses the memory cells and removes those for which the predicate returns true.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::eraseLeadingCells ( const MemoryCell::Predicate )
virtual

Remove leading matching cells.

Traverses the memory cells and removes those for which the predicate returns true. The traversal is terminated the first time the predicate returns false.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::traverse ( MemoryCell::Visitor )
virtual

Traverse and modify cells.

Traverse cells and optionally modify them.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual SValuePtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::readMemory ( const SValuePtr address,
const SValuePtr dflt,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Read a value from memory.

See BaseSemantics::MemoryState() for requirements. This implementation scans the reverse chronological cell list until it finds a cell that must alias the specified addresses and value size. Along the way, it accumulates a list of cells that may alias the specified address. If the accumulated list does not contain exactly one cell, or the scan fell off the end of the list, then dflt becomes the return value, otherwise the return value is the single value on the accumulated list. If the dflt value is returned, then it is also pushed onto the front of the cell list.

The width of the dflt value determines how much data is read. The base implementation assumes that all cells contain 8-bit values.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState.

Reimplemented in Rose::BinaryAnalysis::InstructionSemantics2::SymbolicSemantics::MemoryListState, and Rose::BinaryAnalysis::InstructionSemantics2::IntervalSemantics::MemoryState.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::writeMemory ( const SValuePtr addr,
const SValuePtr value,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Write a value to memory.

See BaseSemantics::MemoryState() for requirements. This implementation creates a new memory cell and pushes it onto the front of the cell list.

The base implementation assumes that all cells contain 8-bit values.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState.

Reimplemented in Rose::BinaryAnalysis::InstructionSemantics2::SymbolicSemantics::MemoryListState, and Rose::BinaryAnalysis::InstructionSemantics2::IntervalSemantics::MemoryState.

bool Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::occlusionsErased ( ) const
inline

Property: erase occluded cells.

If this property is true, then writing a new cell to memory will also erase all older cells that must alias the new cell. Erasing occlusions can adversely affect performance for some semantic domains.

Definition at line 170 of file MemoryCellList.h.

void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::occlusionsErased ( bool  b)
inline

Property: erase occluded cells.

If this property is true, then writing a new cell to memory will also erase all older cells that must alias the new cell. Erasing occlusions can adversely affect performance for some semantic domains.

Definition at line 171 of file MemoryCellList.h.

template<class Iterator >
CellList Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::scan ( Iterator &  cursor,
const SValuePtr addr,
size_t  nBits,
RiscOperators addrOps,
RiscOperators valOps 
) const
inline

Scan cell list to find matching cells.

Scans the cell list from front to back (reverse chronological order) and build a list of cells that may alias the given address and size. The returned list is also in reverse chronological order. The scanning begins at the specified cursor and ends either when an exact alias is found or the end of the list is reached. In either case, the cell that caused the scan to terminate is returned–either the exact alias or the end iterator.

Typical usage is like this:

MemoryCellList::CellList::iterator cursor = memory->get_cells().begin();
MemoryCellList::CellList cells = memory->scan(cursor, address, 8, addrOps, valOps);
if (cursor != memory->get_cells().end())
std::cerr <<"found exact alias: " <<*cursor <<"\n";

Definition at line 190 of file MemoryCellList.h.

References Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::RiscOperators::undefined_().

virtual MemoryCell::AddressSet Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::getWritersUnion ( const SValuePtr addr,
size_t  nBits,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Writers for an address.

Returns the set of all writers that wrote to the specified address or any address that might alias the specified address. Memory states that don't normally compute aliases (e.g., MemoryCellMap) return only the writers for the specified address, not any aliases, and in this case getWritersUnion and getWritersIntersection return the same set.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.

virtual MemoryCell::AddressSet Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellList::getWritersIntersection ( const SValuePtr addr,
size_t  nBits,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Writers for an address.

Returns the set of all writers that wrote to the specified address and any address that might alias the specified address. Memory states that don't normally compute aliases (e.g., MemoryCellMap) return only the writers for the specified address, not any aliases, and in this case getWritersUnion and getWritersIntersection return the same set.

Implements Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState.


The documentation for this class was generated from the following file: