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::MemoryCellMap Class Referenceabstract

Description

Simple map-based memory state.

Memory cells (address + value pairs with additional data, ) are stored in a map-like container so that a cell can be accessed in logarithmic time given its address. The keys for the map are generated from the cell virtual addresses, either by using the address directly or by hashing it. The function that generates these keys, generateCellKey, is pure virtual.

Definition at line 27 of file MemoryCellMap.h.

#include <MemoryCellMap.h>

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

Public Types

typedef uint64_t CellKey
 Key used to look up memory cells. More...
 
typedef Sawyer::Container::Map< CellKey, MemoryCellPtrCellMap
 Map of memory cells indexed by cell keys. More...
 
typedef MemoryCellMap Ptr
 Shared-ownership pointer for a memory cell map object. More...
 
- Public Types inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryState
typedef MemoryStatePtr Ptr
 Shared-ownership pointer for a MemoryState. More...
 

Public Member Functions

virtual CellKey generateCellKey (const SValuePtr &address) const =0
 Generate a cell lookup key. More...
 
virtual MemoryCellPtr findCell (const SValuePtr &addr) const
 Look up memory cell for address. 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 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 &address, 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.
 
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 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...
 
- 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
virtual MemoryStatePtr create (const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const =0
 Virtual allocating constructor. More...
 
virtual MemoryStatePtr clone () const =0
 Virtual allocating copy constructor. More...
 
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 MemoryCellMapPtr promote (const MemoryStatePtr &x)
 Promote a base memory state pointer to a MemoryCellMap 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

 MemoryCellMap (const MemoryCellPtr &protocell)
 
 MemoryCellMap (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
 
 MemoryCellMap (const MemoryCellMap &other)
 
- 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

CellMap cells
 
- Protected Attributes inherited from Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellState
MemoryCellPtr protocell
 
MemoryCellPtr latestWrittenCell_
 

Member Typedef Documentation

Key used to look up memory cells.

The key is generated from the cell's virtual address either by using the address directly or by hashing it. For instance, a concrete domain might use the address directly while a symbolic domain will probably hash the symbolic address expression.

Definition at line 34 of file MemoryCellMap.h.

Map of memory cells indexed by cell keys.

Definition at line 37 of file MemoryCellMap.h.

Shared-ownership pointer for a memory cell map object.

Definition at line 73 of file MemoryCellMap.h.

Member Function Documentation

static MemoryCellMapPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::promote ( const MemoryStatePtr x)
inlinestatic

Promote a base memory state pointer to a MemoryCellMap pointer.

The memory state, x, must have a MemoryCellMap dynamic type.

Definition at line 78 of file MemoryCellMap.h.

virtual CellKey Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::generateCellKey ( const SValuePtr address) const
pure virtual

Generate a cell lookup key.

Generates a key from a virtual address. The key is used to look up the cell in a map-based container.

Implemented in Rose::BinaryAnalysis::InstructionSemantics2::SymbolicSemantics::MemoryMapState.

virtual MemoryCellPtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::findCell ( const SValuePtr addr) const
virtual

Look up memory cell for address.

Returns the memory cell for the specified address, or a null pointer if the cell does not exist. The address is used to look up the cell in logirithmic time. This is just a convenience wrapper around matchingCells that returns either the (single) cell found by that function or a null pointer.

virtual void Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::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::MemoryCellMap::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 SValuePtr Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::readMemory ( const SValuePtr address,
const SValuePtr dflt,
RiscOperators addrOps,
RiscOperators valOps 
)
virtual

Read a value from memory.

Consults the memory represented by this MemoryState object and returns a semantic value. Depending on the semantic domain, the value can be a value that is already stored in the memory state, a supplied default value, a new value constructed from some combination of existing values and/or the default value, or anything else. For instance, in a symbolic domain the address could alias multiple existing memory locations and the implementation may choose to return a McCarthy expression. Additional data (such as SMT solvers) may be passed via the RiscOperators argument.

The size of the value being read does not necessarily need to be equal to the size of values stored in the memory state, though it typically is(1). For instance, an implementation may allow reading a 32-bit little endian value from a memory state that stores only bytes. A RiscOperators object is provided for use in these situations.

In order to support cases where an address does not match any existing location, the dflt value can be used to initialize a new memory location. The manner in which the default is used depends on the implementation. In any case, the width of the dflt value determines how much to read.

Footnote 1: A MemoryState::readMemory() call is the last in a sequence of delegations starting with RiscOperators::readMemory(). The designers of the MemoryState, State, and RiscOperators subclasses will need to coordinate to decide which layer should handle concatenating values from individual memory locations.

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

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

Write a value to memory.

Consults the memory represented by this MemoryState object and possibly inserts the specified value. The details of how a value is inserted into a memory state depends entirely on the implementation in a subclass and will probably be different for each semantic domain.

A MemoryState::writeMemory() call is the last in a sequence of delegations starting with RiscOperators::writeMemory(). The designers of the MemoryState, State, and RiscOperators will need to coordinate to decide which layer (if any) should handle splitting a multi-byte value into multiple memory locations.

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

virtual std::vector<MemoryCellPtr> Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::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::MemoryCellMap::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::MemoryCellMap::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::MemoryCellMap::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::MemoryCellMap::traverse ( MemoryCell::Visitor )
virtual

Traverse and modify cells.

Traverse cells and optionally modify them.

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

virtual MemoryCell::AddressSet Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics::MemoryCellMap::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::MemoryCellMap::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: