decompiler  1.0.0
Classes | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
ghidra::JumpTable Class Reference

A map from values to control-flow targets within a function. More...

#include <jumptable.hh>

Classes

struct  IndexPair
 An address table index and its corresponding out-edge. More...
 

Public Member Functions

 JumpTable (Architecture *g, Address ad=Address())
 Constructor. More...
 
 JumpTable (const JumpTable *op2)
 Copy constructor. More...
 
 ~JumpTable (void)
 Destructor.
 
bool isRecovered (void) const
 Return true if a model has been recovered.
 
bool isLabelled (void) const
 Return true if case labels are computed.
 
bool isOverride (void) const
 Return true if this table was manually overridden.
 
bool isPossibleMultistage (void) const
 Return true if this could be multi-staged.
 
int4 getStage (void) const
 Return what stage of recovery this jump-table is in.
 
int4 numEntries (void) const
 Return the size of the address table for this jump-table.
 
uintb getSwitchVarConsume (void) const
 Get bits of switch variable consumed by this table.
 
int4 getDefaultBlock (void) const
 Get the out-edge corresponding to the default switch destination.
 
const AddressgetOpAddress (void) const
 Get the address of the BRANCHIND for the switch.
 
PcodeOpgetIndirectOp (void) const
 Get the BRANCHIND PcodeOp.
 
void setIndirectOp (PcodeOp *ind)
 Set the BRANCHIND PcodeOp.
 
void setNormMax (uint4 maddsub, uint4 mleftright, uint4 mext)
 Set the switch variable normalization model restrictions.
 
void setOverride (const vector< Address > &addrtable, const Address &naddr, uintb h, uintb sv)
 Force manual override information on this jump-table. More...
 
int4 numIndicesByBlock (const FlowBlock *bl) const
 Return the number of address table entries that target the given basic-block. More...
 
int4 getIndexByBlock (const FlowBlock *bl, int4 i) const
 Get the index of the i-th address table entry that corresponds to the given basic-block. More...
 
Address getAddressByIndex (int4 i) const
 Get the i-th address table entry.
 
void setLastAsMostCommon (void)
 Set the most common jump-table target to be the last address in the table.
 
void setDefaultBlock (int4 bl)
 Set out-edge of the switch destination considered to be default.
 
void setLoadCollect (bool val)
 Set whether LOAD records should be collected.
 
void addBlockToSwitch (BlockBasic *bl, uintb lab)
 Force a given basic-block to be a switch destination. More...
 
void switchOver (const FlowInfo &flow)
 Convert absolute addresses to block indices. More...
 
uintb getLabelByIndex (int4 index) const
 Given a case index, get its label.
 
void foldInNormalization (Funcdata *fd)
 Hide the normalization code for the switch. More...
 
bool foldInGuards (Funcdata *fd)
 Hide any guard code for this switch.
 
void recoverAddresses (Funcdata *fd)
 Recover the raw jump-table addresses (the address table) More...
 
void recoverMultistage (Funcdata *fd)
 Recover jump-table addresses keeping track of a possible previous stage. More...
 
bool recoverLabels (Funcdata *fd)
 Recover the case labels for this jump-table. More...
 
bool checkForMultistage (Funcdata *fd)
 Check if this jump-table requires an additional recovery stage. More...
 
void clear (void)
 Clear instance specific data for this jump-table. More...
 
void encode (Encoder &encoder) const
 Encode this jump-table as a <jumptable> element. More...
 
void decode (Decoder &decoder)
 Decode this jump-table from a <jumptable> element. More...
 

Private Member Functions

void recoverModel (Funcdata *fd)
 Attempt recovery of the jump-table model. More...
 
void trivialSwitchOver (void)
 Switch this table over to a trivial model. More...
 
void sanityCheck (Funcdata *fd)
 Perform sanity check on recovered address targets. More...
 
int4 block2Position (const FlowBlock *bl) const
 Convert a basic-block to an out-edge index from the switch. More...
 

Static Private Member Functions

static bool isReachable (PcodeOp *op)
 Check if the given PcodeOp still seems reachable in its function. More...
 

Private Attributes

Architectureglb
 Architecture under which this jump-table operates.
 
JumpModeljmodel
 Current model of how the jump table is implemented in code.
 
JumpModelorigmodel
 Initial jump table model, which may be incomplete.
 
vector< Addressaddresstable
 Raw addresses in the jump-table.
 
vector< IndexPairblock2addr
 Map from basic-blocks to address table index.
 
vector< uintb > label
 The case label for each explicit target.
 
vector< LoadTableloadpoints
 Any recovered in-memory data for the jump-table.
 
Address opaddress
 Absolute address of the BRANCHIND jump.
 
PcodeOpindirect
 CPUI_BRANCHIND linked to this jump-table.
 
uintb switchVarConsume
 Bits of the switch variable being consumed.
 
int4 defaultBlock
 The out-edge corresponding to the default switch destination (-1 = undefined)
 
int4 lastBlock
 Block out-edge corresponding to last entry in the address table.
 
uint4 maxaddsub
 Maximum ADDs or SUBs to normalize.
 
uint4 maxleftright
 Maximum shifts to normalize.
 
uint4 maxext
 Maximum extensions to normalize.
 
int4 recoverystage
 0=no stages recovered, 1=additional stage needed, 2=complete
 
bool collectloads
 Set to true if information about in-memory model data is/should be collected.
 

Detailed Description

A map from values to control-flow targets within a function.

A JumpTable is attached to a specific CPUI_BRANCHIND and encapsulates all the information necessary to model the indirect jump as a switch statement. It knows how to map from specific switch variable values to the destination case block and how to label the value.

Constructor & Destructor Documentation

◆ JumpTable() [1/2]

ghidra::JumpTable::JumpTable ( Architecture g,
Address  ad = Address() 
)

Constructor.

Parameters
gis the Architecture the table exists within
adis the Address of the BRANCHIND this models

References collectloads, defaultBlock, glb, indirect, jmodel, lastBlock, maxaddsub, maxext, maxleftright, origmodel, recoverystage, and switchVarConsume.

◆ JumpTable() [2/2]

ghidra::JumpTable::JumpTable ( const JumpTable op2)

Copy constructor.

This is a partial clone of another jump-table. Objects that are specific to the particular Funcdata instance must be recalculated.

Parameters
op2is the jump-table to clone

References addresstable, ghidra::JumpModel::clone(), collectloads, defaultBlock, glb, indirect, jmodel, lastBlock, loadpoints, maxaddsub, maxext, maxleftright, opaddress, origmodel, recoverystage, and switchVarConsume.

Member Function Documentation

◆ addBlockToSwitch()

void ghidra::JumpTable::addBlockToSwitch ( BlockBasic bl,
uintb  lab 
)

Force a given basic-block to be a switch destination.

This is used to add address targets from guard branches if they are not already in the address table. A specific case label for the block can also be provided. The new target is appended directly to the end of the table.

Parameters
blis the given basic-block
labis the case label for the block

References addresstable, block2addr, ghidra::PcodeOp::getParent(), ghidra::BlockBasic::getStart(), indirect, label, lastBlock, and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::JumpBasic::foldInOneGuard().

◆ block2Position()

int4 ghidra::JumpTable::block2Position ( const FlowBlock bl) const
private

Convert a basic-block to an out-edge index from the switch.

Given a specific basic-block, figure out which edge out of the switch block hits it. This position is different from the index into the address table, the out edges are deduped and may include additional guard destinations. If no edge hits it, throw an exception.

Parameters
blis the specific basic-block
Returns
the position of the basic-block

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::FlowBlock::getParent(), and ghidra::FlowBlock::sizeIn().

Referenced by getIndexByBlock(), and numIndicesByBlock().

◆ checkForMultistage()

bool ghidra::JumpTable::checkForMultistage ( Funcdata fd)

Check if this jump-table requires an additional recovery stage.

Look for the override directive that indicates we need an additional recovery stage for this jump-table.

Parameters
fdis the function containing the switch
Returns
true if an additional recovery stage is required.

References addresstable, ghidra::PcodeOp::getAddr(), ghidra::Funcdata::getOverride(), indirect, ghidra::Override::queryMultistageJumptable(), and recoverystage.

Referenced by ghidra::FlowInfo::checkMultistageJumptables().

◆ clear()

void ghidra::JumpTable::clear ( void  )

Clear instance specific data for this jump-table.

Clear out any data that is specific to a Funcdata instance. Right now this is only getting called, when the jumptable is an override in order to clear out derived data.

References addresstable, block2addr, ghidra::JumpModel::clear(), defaultBlock, indirect, ghidra::JumpModel::isOverride(), jmodel, label, lastBlock, loadpoints, origmodel, recoverystage, and switchVarConsume.

Referenced by ghidra::Funcdata::clearJumpTables().

◆ decode()

void ghidra::JumpTable::decode ( Decoder decoder)

Decode this jump-table from a <jumptable> element.

Parse addresses, case labels, and any override information from a <jumptable> element. Other parts of the model and jump-table will still need to be recovered.

Parameters
decoderis the stream decoder

References addresstable, ghidra::Decoder::closeElement(), ghidra::Address::decode(), ghidra::JumpModel::decode(), ghidra::Decoder::getNextAttributeId(), jmodel, label, loadpoints, opaddress, ghidra::Decoder::openElement(), ghidra::Decoder::peekElement(), and ghidra::Decoder::readUnsignedInteger().

Referenced by ghidra::Funcdata::decodeJumpTable().

◆ encode()

void ghidra::JumpTable::encode ( Encoder encoder) const

Encode this jump-table as a <jumptable> element.

The recovered addresses and case labels are encode to the stream. If override information is present, this is also incorporated into the element.

Parameters
encoderis the stream encoder

References addresstable, ghidra::Encoder::closeElement(), ghidra::Address::encode(), ghidra::JumpModel::encode(), ghidra::AddrSpace::encodeAttributes(), ghidra::JumpModel::isOverride(), isRecovered(), jmodel, label, loadpoints, opaddress, ghidra::Encoder::openElement(), and ghidra::Encoder::writeUnsignedInteger().

◆ foldInNormalization()

void ghidra::JumpTable::foldInNormalization ( Funcdata fd)

Hide the normalization code for the switch.

Eliminate any code involved in actually computing the destination address so it looks like the CPUI_BRANCHIND operation does it all internally.

Parameters
fdis the function containing this switch

References ghidra::calc_mask(), ghidra::PcodeOp::code(), ghidra::CPUI_INT_SEXT, ghidra::JumpModel::foldInNormalization(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getNZMask(), ghidra::Varnode::getSize(), indirect, ghidra::Varnode::isWritten(), jmodel, ghidra::minimalmask(), and switchVarConsume.

Referenced by ghidra::ActionSwitchNorm::apply().

◆ getIndexByBlock()

int4 ghidra::JumpTable::getIndexByBlock ( const FlowBlock bl,
int4  i 
) const

Get the index of the i-th address table entry that corresponds to the given basic-block.

An exception is thrown if no address table entry targets the block.

Parameters
blis the given basic-block
irequests a specific position within the duplicate entries
Returns
the address table index

References block2addr, block2Position(), ghidra::JumpTable::IndexPair::blockPosition, and ghidra::JumpTable::IndexPair::compareByPosition().

Referenced by ghidra::BlockSwitch::getLabel().

◆ isReachable()

bool ghidra::JumpTable::isReachable ( PcodeOp op)
staticprivate

Check if the given PcodeOp still seems reachable in its function.

We are not doing a complete check, we are looking for a guard that has collapsed to "if (false)"

Parameters
opis the given PcodeOp to check
Returns
true is the PcodeOp is reachable

References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIn(), ghidra::Varnode::getOffset(), ghidra::FlowBlock::getOut(), ghidra::PcodeOp::getParent(), ghidra::PcodeOp::isBooleanFlip(), ghidra::Varnode::isConstant(), ghidra::BlockBasic::lastOp(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ numIndicesByBlock()

int4 ghidra::JumpTable::numIndicesByBlock ( const FlowBlock bl) const

Return the number of address table entries that target the given basic-block.

Parameters
blis the given basic-block
Returns
the count of entries

References block2addr, block2Position(), and ghidra::JumpTable::IndexPair::compareByPosition().

Referenced by ghidra::BlockSwitch::getNumLabels().

◆ recoverAddresses()

void ghidra::JumpTable::recoverAddresses ( Funcdata fd)

Recover the raw jump-table addresses (the address table)

The addresses that the raw BRANCHIND op might branch to itself are recovered, not including other targets of the final model, like guard addresses. The normalized switch variable and the guards are identified in the process however.

Generally this method is run during flow analysis when we only have partial information about the function (and possibly the switch itself). The Funcdata instance is a partial clone of the function and is different from the final instance that will hold the fully recovered jump-table. The final instance inherits the addresses recovered here, but recoverModel() will need to be run on it separately.

A sanity check is also run, which might truncate the original set of addresses.

Parameters
fdis the function containing the switch

References addresstable, ghidra::JumpModel::buildAddresses(), collectloads, ghidra::JumpModel::getTableSize(), indirect, jmodel, loadpoints, opaddress, recoverModel(), and sanityCheck().

Referenced by recoverMultistage(), and ghidra::Funcdata::stageJumpTable().

◆ recoverLabels()

bool ghidra::JumpTable::recoverLabels ( Funcdata fd)

Recover the case labels for this jump-table.

This is run assuming the address table has already been recovered, via recoverAddresses() in another Funcdata instance. So recoverModel() needs to be rerun on the instance passed in here.

The unnormalized switch variable is recovered, and for each possible address table entry, the variable value that produces it is calculated and stored as the formal case label for the associated code block.

Parameters
fdis the (final instance of the) function containing the switch
Returns
true if it looks like a multi-stage restart is needed.

References addresstable, ghidra::JumpModel::buildAddresses(), ghidra::JumpModel::buildLabels(), ghidra::JumpModel::findUnnormalized(), ghidra::JumpModel::getTableSize(), glb, indirect, ghidra::JumpModel::isOverride(), isRecovered(), jmodel, label, ghidra::Architecture::max_jumptable_size, maxaddsub, maxext, maxleftright, opaddress, origmodel, ghidra::JumpModel::recoverModel(), recoverModel(), trivialSwitchOver(), and ghidra::Funcdata::warning().

Referenced by ghidra::ActionSwitchNorm::apply().

◆ recoverModel()

void ghidra::JumpTable::recoverModel ( Funcdata fd)
private

Attempt recovery of the jump-table model.

Try to recover each model in turn, until we find one that matches the specific BRANCHIND.

Parameters
fdis the function containing the switch

References ghidra::PcodeOp::code(), ghidra::CPUI_CALLOTHER, ghidra::Varnode::getDef(), ghidra::JumpBasic::getPathMeld(), ghidra::Varnode::isWritten(), ghidra::JumpBasic::JumpBasic(), and ghidra::Funcdata::size.

Referenced by recoverAddresses(), and recoverLabels().

◆ recoverMultistage()

void ghidra::JumpTable::recoverMultistage ( Funcdata fd)

Recover jump-table addresses keeping track of a possible previous stage.

Do a normal recoverAddresses, but save off the old JumpModel, and if we fail recovery, put back the old model.

Parameters
fdis the function containing the switch

References addresstable, ghidra::PcodeOp::getAddr(), indirect, jmodel, loadpoints, origmodel, recoverAddresses(), recoverystage, and ghidra::Funcdata::warning().

Referenced by ghidra::Funcdata::stageJumpTable().

◆ sanityCheck()

void ghidra::JumpTable::sanityCheck ( Funcdata fd)
private

Perform sanity check on recovered address targets.

Check that the BRANCHIND is still reachable, if not throw JumptableNotReachableError. Check pathological cases when there is only one address in the table, if we find this, throw the JumptableThunkError. Let the model run its sanity check. Print a warning if the sanity check truncates the original address table.

Parameters
fdis the function containing the switch

References ghidra::Address::getOffset(), and ghidra::Funcdata::warning().

Referenced by recoverAddresses().

◆ setOverride()

void ghidra::JumpTable::setOverride ( const vector< Address > &  addrtable,
const Address naddr,
uintb  h,
uintb  sv 
)

Force manual override information on this jump-table.

The model is switched over to JumpBasicOverride, which is initialized with an externally provided list of addresses. The addresses are forced as the output addresses the BRANCHIND for this jump-table. If a non-zero hash and an address is provided, this identifies a specific Varnode to use as the normalized switch variable. A potential starting value for normalized switch variable range is provided.

Parameters
addrtableis the manually provided list of addresses to put in the address table
naddris the address where the normalized switch variable is defined
his a hash identifying the normalized switch variable (or 0)
svis the starting value for the range of possible normalized switch variable values (usually 0)

References jmodel.

Referenced by ghidra::IfcJumpOverride::execute().

◆ switchOver()

void ghidra::JumpTable::switchOver ( const FlowInfo flow)

Convert absolute addresses to block indices.

Convert addresses in this table to actual targeted basic-blocks.

This constructs a map from each out-edge from the basic-block containing the BRANCHIND to addresses in the table targetting that out-block. The most common address table entry is also calculated here.

Parameters
flowis used to resolve address targets

References addresstable, block2addr, defaultBlock, ghidra::FlowBlock::getOut(), ghidra::PcodeOp::getParent(), indirect, lastBlock, ghidra::FlowBlock::sizeOut(), and ghidra::FlowInfo::target().

◆ trivialSwitchOver()

void ghidra::JumpTable::trivialSwitchOver ( void  )
private

Switch this table over to a trivial model.

Make exactly one case for each output edge of the switch block.

References addresstable, block2addr, defaultBlock, ghidra::PcodeOp::getParent(), indirect, lastBlock, and ghidra::FlowBlock::sizeOut().

Referenced by recoverLabels().


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