Description

Simple map-based memory state.

Memory cells (address + value pairs with additional data, MemoryCell) 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 28 of file MemoryCellMap.h.

#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellMap.h>

Inheritance diagram for Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap:

[legend]

Collaboration diagram for Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap:

[legend]

Public Types
using	Super = MemoryCellState
	Base type.

using	Ptr = MemoryCellMapPtr
	Shared-ownership pointer.

typedef uint64_t	CellKey
	Key used to look up memory cells.

typedef Sawyer::Container::Map< CellKey, MemoryCellPtr >	CellMap
	Map of memory cells indexed by cell keys.

Public Types inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState
using	Super = MemoryState
	Base type.

using	Ptr = MemoryCellStatePtr
	Shared-ownership pointer.

Public Types inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryState
typedef MemoryStatePtr	Ptr
	Shared-ownership pointer.

Public Types inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace
using	Ptr = AddressSpacePtr
	Shared-ownership pointer.

using	Purpose = AddressSpacePurpose
	Purpose for the address space.

Public Member Functions
virtual CellKey	generateCellKey (const SValuePtr &address) const =0
	Generate a cell lookup key.

virtual MemoryCellPtr	findCell (const SValuePtr &addr) const
	Look up memory cell for address.

virtual bool	isAllPresent (const SValuePtr &address, size_t nBytes, RiscOperators *addrOps) const
	Predicate to determine whether all bytes are present.

virtual void	hash (Combinatorics::Hasher &, RiscOperators addrOps, RiscOperators valOps) const override
	Hash this address space.

virtual void	clear () override
	Clear memory.

virtual bool	merge (const AddressSpacePtr &other, RiscOperators addrOps, RiscOperators valOps) override
	Merge address spaces for data flow analysis.

virtual SValuePtr	readMemory (const SValuePtr &address, const SValuePtr &dflt, RiscOperators addrOps, RiscOperators valOps) override
	Read a value from memory.

virtual SValuePtr	peekMemory (const SValuePtr &address, const SValuePtr &dflt, RiscOperators addrOps, RiscOperators valOps) override
	Read a value from memory without side effects.

virtual void	writeMemory (const SValuePtr &address, const SValuePtr &value, RiscOperators addrOps, RiscOperators valOps) override
	Write a value to memory.

virtual void	print (std::ostream &, Formatter &) const override
	Print an address space.

virtual std::vector< MemoryCellPtr >	matchingCells (MemoryCell::Predicate &) const override
	Find all matching cells.

virtual std::vector< MemoryCellPtr >	leadingCells (MemoryCell::Predicate &) const override
	Find leading matching cells.

virtual void	eraseMatchingCells (MemoryCell::Predicate &) override
	Remove all matching cells.

virtual void	eraseLeadingCells (MemoryCell::Predicate &) override
	Remove leading matching cells.

virtual void	traverse (MemoryCell::Visitor &) override
	Traverse and modify cells.

virtual AddressSet	getWritersUnion (const SValuePtr &addr, size_t nBits, RiscOperators addrOps, RiscOperators valOps) override
	Writers for an address.

virtual AddressSet	getWritersIntersection (const SValuePtr &addr, size_t nBits, RiscOperators addrOps, RiscOperators valOps) override
	Writers for an address.

Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState
virtual void	updateReadProperties (const CellList &)
	Adjust I/O properties after reading memory.

virtual void	updateWriteProperties (const CellList &, InputOutputPropertySet)
	Adjust I/O properties after writing memory.

void	eraseNonWritten ()
	Erase cells that have no writers.

std::vector< MemoryCellPtr >	allCells () const
	All cells.

virtual MemoryCellPtr	latestWrittenCell () const
	Property: Cell most recently written.

virtual void	latestWrittenCell (const MemoryCellPtr &)
	Property: Cell most recently written.

Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryState
virtual MemoryStatePtr	create (const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const =0
	Virtual allocating constructor.

SValuePtr	get_addr_protoval () const
	Return the address protoval.

SValuePtr	get_val_protoval () const
	Return the value protoval.

MergerPtr	merger () const
	Property: Merger.

void	merger (const MergerPtr &)
	Property: Merger.

bool	byteRestricted () const
	Indicates whether memory cell values are required to be eight bits wide.

void	byteRestricted (bool)
	Indicates whether memory cell values are required to be eight bits wide.

ByteOrder::Endianness	get_byteOrder () const
	Memory byte order.

void	set_byteOrder (ByteOrder::Endianness)
	Memory byte order.

Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace
virtual Ptr	clone () const =0
	Deep-copy of this address space.

virtual SValuePtr	read (const AddressSpaceAddress &, const SValuePtr &dflt, RiscOperators &addrOps, RiscOperators &valOps)
	Read a value from the address space.

virtual SValuePtr	peek (const AddressSpaceAddress &, const SValuePtr &dflt, RiscOperators &addrOps, RiscOperators &valOps)
	Read without causing side effects.

virtual void	write (const AddressSpaceAddress &, const SValuePtr &value, RiscOperators &addrOps, RiscOperators &valOps)
	Write a value to an address space.

std::string	printableName () const
	Printable name for this address space.

Purpose	purpose () const
	Property: Purpose of this address space.

void	purpose (Purpose)
	Property: Purpose of this address space.

const std::string &	name () const
	Property: Name for this address space.

void	name (const std::string &)
	Property: Name for this address space.

void	print (std::ostream &, const std::string &prefix="") const
	Print an address space.

WithFormatter	with_format (Formatter &)
	Used for printing address spaces with formatting.

WithFormatter	operator+ (Formatter &)
	Used for printing address spaces with formatting.

WithFormatter	operator+ (const std::string &linePrefix)
	Used for printing address spaces with formatting.

Static Public Member Functions
static MemoryCellMapPtr	promote (const AddressSpacePtr &)
	Promote a base address space pointer to a MemoryCellMap pointer.

Static Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState
static MemoryCellStatePtr	promote (const BaseSemantics::AddressSpacePtr &)
	Promote a base address space pointer to a BaseSemantics::MemoryCellState pointer.

Static Public Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryState
static MemoryStatePtr	promote (const AddressSpacePtr &)

Protected Member Functions
	MemoryCellMap (const MemoryCellPtr &protocell)

	MemoryCellMap (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)

	MemoryCellMap (const MemoryCellMap &)

Protected Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState
	MemoryCellState (const MemoryCellPtr &protocell)

	MemoryCellState (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)

	MemoryCellState (const MemoryCellState &other)

Protected Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryState
	MemoryState (const SValuePtr &addrProtoval, const SValuePtr &valProtoval)

	MemoryState (const MemoryStatePtr &other)

Protected Member Functions inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace
	AddressSpace (Purpose, const std::string &name)

	AddressSpace (const AddressSpace &)

AddressSpace &	operator= (const AddressSpace &)=delete

Protected Attributes
CellMap	cells

Protected Attributes inherited from Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState
MemoryCellPtr	protocell

MemoryCellPtr	latestWrittenCell_

Member Typedef Documentation

◆ Super

using Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::Super = MemoryCellState

Base type.

Definition at line 31 of file MemoryCellMap.h.

◆ Ptr

using Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::Ptr = MemoryCellMapPtr

Shared-ownership pointer.

Definition at line 34 of file MemoryCellMap.h.

◆ CellKey

typedef uint64_t Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::CellKey

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 41 of file MemoryCellMap.h.

◆ CellMap

typedef Sawyer::Container::Map<CellKey, MemoryCellPtr> Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::CellMap

Map of memory cells indexed by cell keys.

Definition at line 44 of file MemoryCellMap.h.

Member Function Documentation

◆ promote()

static MemoryCellMapPtr Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::promote ( const AddressSpacePtr & )

static

Promote a base address space pointer to a MemoryCellMap pointer.

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

◆ generateCellKey()

virtual CellKey Rose::BinaryAnalysis::InstructionSemantics::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::InstructionSemantics::SymbolicSemantics::MemoryMapState.

◆ findCell()

virtual MemoryCellPtr Rose::BinaryAnalysis::InstructionSemantics::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.

◆ isAllPresent()

virtual bool Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::isAllPresent	(	const SValuePtr &	address,
		size_t	nBytes,
		RiscOperators *	addrOps
	)		const

virtual

Predicate to determine whether all bytes are present.

Returns true if bytes at the specified address and the following consecutive addresses are all present in this memory state.

◆ hash()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::hash	(	Combinatorics::Hasher &	,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)		const

overridevirtual

Hash this address space.

Hashes this address space by appending its data to the specified hasher. The goal is to identify when two address spaces are the "same" and allow certain kinds of analyses to take shortcuts. The address space purpose and name are not included in the hash. Separate RISC operators are passed for the addresses and values of this address space and are used if the hashing requires any operations on the addresses or values.

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace.

◆ clear()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::clear ( )

overridevirtual

Clear memory.

Removes all memory cells from this memory state.

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

◆ merge()

virtual bool Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::merge	(	const AddressSpacePtr &	other,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)

overridevirtual

Merge address spaces for data flow analysis.

Merges the other address space into this address space, returning true if this space changed.

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace.

◆ readMemory()

virtual SValuePtr Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::readMemory	(	const SValuePtr &	address,
		const SValuePtr &	dflt,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryState.

◆ peekMemory()

virtual SValuePtr Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::peekMemory	(	const SValuePtr &	address,
		const SValuePtr &	dflt,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)

overridevirtual

Read a value from memory without side effects.

This is similar to readMemory except there are no side effects. The memory state is not modified by this function.

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryState.

◆ writeMemory()

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

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryState.

◆ print()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::print	(	std::ostream &	,
		Formatter &
	)		const

overridevirtual

Print an address space.

The output most likely occupies more than one line and each emitted line will be terminated with a line feed.

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::AddressSpace.

◆ matchingCells()

virtual std::vector< MemoryCellPtr > Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::matchingCells ( MemoryCell::Predicate & ) const

overridevirtual

Find all matching cells.

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

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ leadingCells()

virtual std::vector< MemoryCellPtr > Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::leadingCells ( MemoryCell::Predicate & ) const

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ eraseMatchingCells()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::eraseMatchingCells ( MemoryCell::Predicate & )

overridevirtual

Remove all matching cells.

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

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ eraseLeadingCells()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::eraseLeadingCells ( MemoryCell::Predicate & )

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ traverse()

virtual void Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::traverse ( MemoryCell::Visitor & )

overridevirtual

Traverse and modify cells.

Traverse cells and optionally modify them.

Implements Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ getWritersUnion()

virtual AddressSet Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::getWritersUnion	(	const SValuePtr &	addr,
		size_t	nBits,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryCellState.

◆ getWritersIntersection()

virtual AddressSet Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::getWritersIntersection	(	const SValuePtr &	addr,
		size_t	nBits,
		RiscOperators *	addrOps,
		RiscOperators *	valOps
	)

overridevirtual

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::InstructionSemantics::BaseSemantics::MemoryCellState.

Member Data Documentation

◆ cells

CellMap Rose::BinaryAnalysis::InstructionSemantics::BaseSemantics::MemoryCellMap::cells

protected

Definition at line 50 of file MemoryCellMap.h.

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

MemoryCellMap.h

Description

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ Super

◆ Ptr

◆ CellKey

◆ CellMap

Member Function Documentation

◆ promote()

◆ generateCellKey()

◆ findCell()

◆ isAllPresent()

◆ hash()

◆ clear()

◆ merge()

◆ readMemory()

◆ peekMemory()

◆ writeMemory()

◆ print()

◆ matchingCells()

◆ leadingCells()

◆ eraseMatchingCells()

◆ eraseLeadingCells()

◆ traverse()

◆ getWritersUnion()

◆ getWritersIntersection()

Member Data Documentation

◆ cells