ROSE 0.11.145.134
|
Discovers instructions, basic blocks, and functions.
The partitioner is reponsible for discovering the locations of valid instructions and organizing them to form a consistent set of basic blocks that form a global control flow graph. The basic blocks are further organized into subsets called functions.
Definition at line 675 of file ParallelPartitioner.h.
#include <Rose/BinaryAnalysis/Partitioner2/ParallelPartitioner.h>
Classes | |
struct | CreateLinkedCfgVertices |
Information returned by createLinkedCfgVertices. More... | |
struct | LockInCache |
Object returned by lockInCache. More... | |
Public Member Functions | |
Partitioner (const MemoryMap::Ptr &memory, const Disassembler::BasePtr &decoder, const Settings &settings=Settings()) | |
Constructor new partitioner. | |
Progress::Ptr | progress () const |
Progress reports for ratio of memory disassembled. | |
void | statusReports () |
Generate status reports every so often. | |
MemoryMap::Ptr | memoryMap () const |
Returns the memory map used for disassembling. | |
size_t | nDecodedAddresses () const |
Amount of memory with known instructions. | |
AddressIntervalSet | unusedExecutableVas (AddressInterval where) const |
All unused executable addresses within region. | |
InstructionPtr | decodeInstruction (rose_addr_t) |
Decode an instruction at the specified address. | |
InsnInfo::Ptr | existingInstruction (rose_addr_t) |
Return information about a vertex of the global CFG. | |
InstructionPtr | existingInstructionAst (rose_addr_t) |
Returns the AST for an instruction. | |
InstructionCache & | instructionCache () const |
The instruction cache. | |
LockInCache | lockInCache (const InsnInfo::List &) |
Lock instructions in the cache. | |
CreateLinkedCfgVertices | createLinkedCfgVertices (rose_addr_t sourceVa, rose_addr_t targetVa, const CfgEdge &) |
Add an edge and maybe vertices to the global CFG. | |
void | scheduleDecodeInstruction (rose_addr_t insnVa) |
Add a work item to decode an instruction. | |
void | scheduleNextUnusedRegion (const AddressInterval &where) |
Add a work item to decode lowest unused addresses. | |
InsnInfo::List | basicBlockEndingAt (rose_addr_t, size_t maxInsns=UNLIMITED) const |
Find a basic block's worth of instructions. | |
InsnInfo::List | basicBlockContaining (rose_addr_t) const |
Find basic block containing specified instruction. | |
Borrowed< CachedItem< Semantics::RiscOperatorsPtr, uint64_t > > | basicBlockSemantics (const InsnInfo::List &) |
Calculate the semantics for a basic block. | |
AddressSet | computedConcreteSuccessors (rose_addr_t insnVa, Accuracy accuracy) |
Return the computed concrete successors for an instruction. | |
bool | isFunctionCall (rose_addr_t insnVa, Accuracy accuracy) |
Determine whether the instruction is a function call. | |
void | run (size_t maxWorkers) |
Run in parallel. | |
bool | isRunning () const |
Whether the partitioner is running. | |
void | printInsnCfg (std::ostream &) const |
Output the CFG as a DOT graph. | |
void | dumpInsnCfg (std::ostream &, const Rose::BinaryAnalysis::Partitioner2::Partitioner &) const |
Output the CFG as text for debugging. | |
std::vector< InsnInfo::List > | allBasicBlocks () const |
List of all basic blocks. | |
std::map< rose_addr_t, rose_addr_t > | calculateInsnToBbMap () const |
Create a map from instructions to basic blocks. | |
std::map< rose_addr_t, AddressSet > | assignFunctions () |
Assign instructions to functions. | |
void | transferResults (const Rose::BinaryAnalysis::Partitioner2::PartitionerPtr &out) |
Build results from CFG. | |
rose_addr_t | remap () |
Figure out how to remap memory. | |
const Settings & | settings () const |
Behavior settings. | |
Settings & | settings () |
Behavior settings. | |
InsnInfo::Ptr | makeInstruction (rose_addr_t) |
Create and return information about a vertex of the CFG. | |
InsnInfo::Ptr | makeInstruction (rose_addr_t, const InstructionPtr &) |
Create and return information about a vertex of the CFG. | |
std::vector< SymbolicExpression::Ptr > | computeSuccessors (const InsnInfo::List &, Accuracy accuracy) |
Return the computed symbolic successors for an instruction. | |
std::vector< SymbolicExpression::Ptr > | computeSuccessors (rose_addr_t insnVa, Accuracy accuracy) |
Return the computed symbolic successors for an instruction. | |
const InsnCfg & | insnCfg () const |
Control flow graph. | |
InsnCfg & | insnCfg () |
Control flow graph. | |
Public Member Functions inherited from Sawyer::Attribute::Storage< SyncTag > | |
Storage () | |
Default constructor. | |
Storage (const Storage &other) | |
Copy constructor. | |
Storage & | operator= (const Storage &other) |
Assignment operator. | |
bool | attributeExists (Id id) const |
Check attribute existence. | |
void | eraseAttribute (Id id) |
Erase an attribute. | |
void | clearAttributes () |
Erase all attributes. | |
template<typename T > | |
void | setAttribute (Id id, const T &value) |
Store an attribute. | |
template<typename T > | |
bool | setAttributeMaybe (Id id, const T &value) |
Store an attribute if not already present. | |
template<typename T > | |
T | getAttribute (Id id) const |
Get an attribute that is known to exist. | |
template<typename T > | |
T | attributeOrElse (Id id, const T &dflt) const |
Return an attribute or a specified value. | |
template<typename T > | |
T | attributeOrDefault (Id id) const |
Return an attribute or a default-constructed value. | |
template<typename T > | |
Sawyer::Optional< T > | optionalAttribute (Id id) const |
Return the attribute as an optional value. | |
size_t | nAttributes () const |
Number of attributes stored. | |
std::vector< Id > | attributeIds () const |
Returns ID numbers for all IDs stored in this container. | |
Public Member Functions inherited from Sawyer::SharedObject | |
SharedObject () | |
Default constructor. | |
SharedObject (const SharedObject &) | |
Copy constructor. | |
virtual | ~SharedObject () |
Virtual destructor. | |
SharedObject & | operator= (const SharedObject &) |
Assignment. | |
Static Public Member Functions | |
static Accuracy | choose (Accuracy a, Accuracy b) |
Accuracy setting. | |
static bool | addressOrder (const InsnInfo::List &a, const InsnInfo::List &b) |
Predicate to order blocks by starting address. | |
Additional Inherited Members | |
Public Types inherited from Sawyer::Attribute::Storage< SyncTag > | |
typedef SynchronizationTraits< SyncTag > | Sync |
Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::Partitioner | ( | const MemoryMap::Ptr & | memory, |
const Disassembler::BasePtr & | decoder, | ||
const Settings & | settings = Settings() |
||
) |
Constructor new partitioner.
The memory mapping and the memory contents should not change after the partitioner is initialized, nor should the decoder or its behavior change after initialization. This is due to the requirement that any instruction AST can be deleted and when it's recreated later it must be the same as the original.
|
inline |
Behavior settings.
These settings control the bavior of the partitioner.
Thread safety: This function is not thread safe. All settings should be done prior to running the partitioner and should not change while the partitioner is running.
Definition at line 707 of file ParallelPartitioner.h.
|
inline |
Behavior settings.
These settings control the bavior of the partitioner.
Thread safety: This function is not thread safe. All settings should be done prior to running the partitioner and should not change while the partitioner is running.
Definition at line 708 of file ParallelPartitioner.h.
|
static |
Accuracy setting.
Returns a
if not Accuracy::DEFAULT
, else returns b
if not Accuracy::DEFAULT
, else returns Accuracy::LOW
.
Progress::Ptr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::progress | ( | ) | const |
Progress reports for ratio of memory disassembled.
Returns the number of bytes of memory that have been disassembled as a fraction of the number of executable bytes.
Thread safety: This function is thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::statusReports | ( | ) |
Generate status reports every so often.
This function loops until all work is finished, printing a status report to standard error every so often. Obviously some other thread needs to be making progress or else this function will never return.
Thread safety: This function is thread safe.
MemoryMap::Ptr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::memoryMap | ( | ) | const |
Returns the memory map used for disassembling.
Thread safety: This function is thread safe.
size_t Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::nDecodedAddresses | ( | ) | const |
Amount of memory with known instructions.
Returns the number of byte addresses of the memory where instructions have been decoded. If an instruction occupies multiple addresses then all those addresse are counted. If multiple instructions occupy a single address then the address is counted only once.
Thread safety: This function is thread safe.
AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::unusedExecutableVas | ( | AddressInterval | where | ) | const |
All unused executable addresses within region.
Returns the list of all unused executable addresses within the specified address range.
Thread safety: This function is thread safe.
InstructionPtr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::decodeInstruction | ( | rose_addr_t | ) |
Decode an instruction at the specified address.
Returns a smart pointer to the instruction which is either already decoded or will be decoded when the pointer is dereferenced. The address need not be a vertex in the global control flow graph. If the memory at the specified address is not mapped or is not mapped with execute permission then a null pointer is returned. If the memory address is valid but the opcode at that address is meaningless or incomplete (i.e., missing or not fully executable) then an "unknown" instruction is returned.
Thread safety: This function is thread safe.
InsnInfo::Ptr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::makeInstruction | ( | rose_addr_t | ) |
Create and return information about a vertex of the CFG.
Returns the instruction information for the specified vertex of the control flow graph, creating it if necessary. If only an address is specified, then any created instruction info object will contain only an address and will be in a non-decoded state where its wasDecoded function returns false (at least until something causes it to be decoded).
If an instruction AST is specified (via InstructionPtr argument) then all the previously described steps happen plus the specified AST is assigned to the instruction info, but only if it doesn't already have one. The instruction may be null if the memory location is invalid (not mapped or not executable). If the location is valid but the opcode is invalid then a non-null "unknown" instruction should be specified. If the instruction is non-null then it's address must equal the specified address (which is required because of the possibility of null instructions).
Thread safety: This function is thread safe. However, by time the caller can use the return value some other thread might have removed it from the CFG. In any case, the return value is always valid.
InsnInfo::Ptr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::makeInstruction | ( | rose_addr_t | , |
const InstructionPtr & | |||
) |
Create and return information about a vertex of the CFG.
Returns the instruction information for the specified vertex of the control flow graph, creating it if necessary. If only an address is specified, then any created instruction info object will contain only an address and will be in a non-decoded state where its wasDecoded function returns false (at least until something causes it to be decoded).
If an instruction AST is specified (via InstructionPtr argument) then all the previously described steps happen plus the specified AST is assigned to the instruction info, but only if it doesn't already have one. The instruction may be null if the memory location is invalid (not mapped or not executable). If the location is valid but the opcode is invalid then a non-null "unknown" instruction should be specified. If the instruction is non-null then it's address must equal the specified address (which is required because of the possibility of null instructions).
Thread safety: This function is thread safe. However, by time the caller can use the return value some other thread might have removed it from the CFG. In any case, the return value is always valid.
InsnInfo::Ptr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::existingInstruction | ( | rose_addr_t | ) |
Return information about a vertex of the global CFG.
If the global control flow graph contains the specified address then its information is returned as a pointer, otherwise a null pointer is returned.
Thread safety: This function is thread safe.
InstructionPtr Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::existingInstructionAst | ( | rose_addr_t | ) |
Returns the AST for an instruction.
This is similar to existingInstruction except it obtains the AST of the instructio rather than information about the instruction. Although the instrucition information includes the AST, this function is easier to call because it does all the necessary null checks.
Thread safety: This function is thread safe.
InstructionCache & Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::instructionCache | ( | ) | const |
The instruction cache.
The instruction cache holds the ASTs for instructions that have been decoded and used recently.
Thread safety: This function is thread safe.
LockInCache Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::lockInCache | ( | const InsnInfo::List & | ) |
Lock instructions in the cache.
This function should be used when you need to call an old ROSE function that uses multiple raw AST pointers. The call to that old function must ensure that none the ASTs for the specified instructions are evicted from the cache by other threads for the duration of the call. The return value consists of two vectors named "locks", which are the locking pointers, and "insns", which are the raw pointers to the instruction ASTs. Since the raw pointers can be obtained by invoking get
on the LockedInstruction objects, the vector of raw pointers is primarily for convenience when calling old-style functions that take vectors of instructions. This function should be used as follows:
Thread safety: This function is thread safe.
CreateLinkedCfgVertices Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::createLinkedCfgVertices | ( | rose_addr_t | sourceVa, |
rose_addr_t | targetVa, | ||
const CfgEdge & | |||
) |
Add an edge and maybe vertices to the global CFG.
Ensures that the two instruction addresses exist in the global CFG and creates an edge between them if there is no such edge yet. Returns information about whether the vertices and edges where created. If an edge is created then it is set to the specified value, otherwise the specified value is merged into the existing edge.
Thread safety: This function is thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::scheduleDecodeInstruction | ( | rose_addr_t | insnVa | ) |
Add a work item to decode an instruction.
When run, this work item will attempt to decode an instruction at the specified CFG node, which must exist, and then create additional CFG nodes and work items for that instruction's basic block sucessors.
Thread safety: This function is thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::scheduleNextUnusedRegion | ( | const AddressInterval & | where | ) |
Add a work item to decode lowest unused addresses.
When run, this work item will find all the unused executable addresses within the specified region, group them into contiguous regions, arrange to start discovering instructions at each region, and schedule more unused address checks for later.
InsnInfo::List Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::basicBlockEndingAt | ( | rose_addr_t | , |
size_t | maxInsns = UNLIMITED |
||
) | const |
Find a basic block's worth of instructions.
Given an instruction address, recursively follow parent pointers to construct a list of instructions that form a basic block. The returned list will end at the specified instruction even if the CFG contains successors that would also be part of the same basic block. At most maxInsns
instructions are returned.
Thread safety: This function is thread safe.
InsnInfo::List Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::basicBlockContaining | ( | rose_addr_t | ) | const |
Find basic block containing specified instruction.
Given at least one instruction of a basic block, find all the other instructions and return them as a list.
Thread safety: This function is thread safe. If possible, use basicBlockEndingAt instead, which is slightly faster and supports limiting the block size.
Borrowed< CachedItem< Semantics::RiscOperatorsPtr, uint64_t > > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::basicBlockSemantics | ( | const InsnInfo::List & | ) |
Calculate the semantics for a basic block.
The instructions of the specified basic block are calculated and the final state is cached and returned (as part of a RiscOperators object). If the semantics are already known then a pointer is returned without recalculating them. Since the state is cached, you should not modify the state–make a copy instead.
If semantics have failed, then a non-null RISC operators object is returned, but it has a null current state.
Since semantic states are modified in place and are not thread safe, the returned operators must be borrowed from the cache and returned when we're done. This means that if two threads try to borrow at the same time, one of them will end up creating a new semantic state from scratch.
Thread safety: This function is thread safe, but the returned value should not be modified.
std::vector< SymbolicExpression::Ptr > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::computeSuccessors | ( | const InsnInfo::List & | , |
Accuracy | accuracy | ||
) |
Return the computed symbolic successors for an instruction.
The semantics for the specified instructions, or the basic block ending at the specified address, are computed and returned. The returned values are obtained one of two ways, depending on the successorAccuracy
settings. If the setting is LOW
then we just look at the final instruction of the basic block. If HIGH
, then we look at the symbolic value of the instruction pointer from the basic block semantics, but we process this to return values that are more usable. For instance, if the IP is an ITE symbolic expression whose operands are both integer constants, then both constants are returned. Similar if the IP is a set of values. Any non-constant values are simply returned as a free variable (the returned vector will have at most one variable).
Thread safety: This function is thread safe.
std::vector< SymbolicExpression::Ptr > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::computeSuccessors | ( | rose_addr_t | insnVa, |
Accuracy | accuracy | ||
) |
Return the computed symbolic successors for an instruction.
The semantics for the specified instructions, or the basic block ending at the specified address, are computed and returned. The returned values are obtained one of two ways, depending on the successorAccuracy
settings. If the setting is LOW
then we just look at the final instruction of the basic block. If HIGH
, then we look at the symbolic value of the instruction pointer from the basic block semantics, but we process this to return values that are more usable. For instance, if the IP is an ITE symbolic expression whose operands are both integer constants, then both constants are returned. Similar if the IP is a set of values. Any non-constant values are simply returned as a free variable (the returned vector will have at most one variable).
Thread safety: This function is thread safe.
AddressSet Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::computedConcreteSuccessors | ( | rose_addr_t | insnVa, |
Accuracy | accuracy | ||
) |
Return the computed concrete successors for an instruction.
If instruction semantics are available, then the successors for the instruction at the specified addresss are calculated by accumulating a basic block of instructions and then processing those instructions semantically. A vector of the concrete successor addresses is returned and cached in the CFG.
If the Settings::successorAccuracy determines whether the calculation looks at just the specified instruction or an entire basic block.
Thread safety: This function is thread safe.
bool Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::isFunctionCall | ( | rose_addr_t | insnVa, |
Accuracy | accuracy | ||
) |
Determine whether the instruction is a function call.
Determines whether the specified address is a function call. The Settings::functionCallDetectionAccuracy determines whether this looks at just the specified instruction or an entire basic block. The result is cached in the control flow graph.
Thread safety: This function is thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::run | ( | size_t | maxWorkers | ) |
Run in parallel.
Runs all pending work in parallel and returns when that work, and all work recursively created, has completed. The work is run in at most maxWorkers
threads at a time.
Thread safety: This function is not thread safe. It should be called from only one thread at a time.
bool Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::isRunning | ( | ) | const |
Whether the partitioner is running.
Returns true while run is called.
Thread safety: This function is thread safe.
const InsnCfg & Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::insnCfg | ( | ) | const |
Control flow graph.
Returns a reference to the control flow graph. This function can only be called when the partitioner is not running (i.e., while isRunning returns false), and the return value is valid only as long as the partitioner remains in that state. Accessing or modifying the control flow graph while the partitioner is running has undefined behavior.
Thread safety: This function is not thread safe.
InsnCfg & Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::insnCfg | ( | ) |
Control flow graph.
Returns a reference to the control flow graph. This function can only be called when the partitioner is not running (i.e., while isRunning returns false), and the return value is valid only as long as the partitioner remains in that state. Accessing or modifying the control flow graph while the partitioner is running has undefined behavior.
Thread safety: This function is not thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::printInsnCfg | ( | std::ostream & | ) | const |
Output the CFG as a DOT graph.
Thread safety: This function is thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::dumpInsnCfg | ( | std::ostream & | , |
const Rose::BinaryAnalysis::Partitioner2::Partitioner & | |||
) | const |
Output the CFG as text for debugging.
The serial partitioner is used only for unparsing the instructions.
Thread safety: This function is thread safe.
std::vector< InsnInfo::List > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::allBasicBlocks | ( | ) | const |
List of all basic blocks.
This returns a list of all the basic blocks in the global control flow graph. The list is calculated on demand and is not particularly fast (on the order of the number of instructions in teh control flow graph). The blocks are returned in no particular order.
Thread safety: This function is not thread safe.
std::map< rose_addr_t, rose_addr_t > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::calculateInsnToBbMap | ( | ) | const |
Create a map from instructions to basic blocks.
Traverses the entire CFG and creates a mapping from each instruction address to that instruction's basic block address.
Thread safety: This function is not thread safe.
|
static |
Predicate to order blocks by starting address.
Compares two instruction lists and returns true if the first list starts at an earlier address than the second list. An empty list compares less than all non-empty lists.
std::map< rose_addr_t, AddressSet > Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::assignFunctions | ( | ) |
Assign instructions to functions.
This starts with instructions that are marked as function entry points and traverses certain edges of the control flow graph to assign reachable instructions to the same function. It's possible for an instruction to be owned by any number of functions – including none at all – although most instructions will normally be owned by one function.
Thread safety: This function is not thread safe.
void Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::transferResults | ( | const Rose::BinaryAnalysis::Partitioner2::PartitionerPtr & | out | ) |
Build results from CFG.
Clears and repopulates the specified partitioner object with information from this partitioner's global control flow graph.
Thread safety: This function is not thread safe.
rose_addr_t Rose::BinaryAnalysis::Partitioner2::Experimental::ParallelPartitioner::Partitioner::remap | ( | ) |
Figure out how to remap memory.
Based on how function calls line up with function entry points, try to figure out if there's a way we could rearrange memory to get better matching. Returns zero or a shift amount.