Skip to content

Refactor xref management #6438

Description

@Rot127

xrefs are currently stored in RzAnalysis as hash tables.

HtUP *ht_xrefs_from;
HtUP *ht_xrefs_to;

Depending on the number of xrefs and on the way of access this is very slow.

For example:

  • Iterator over all call xrefs requires iteration over all xrefs: O(n)
  • Get all xrefs from/to a certain address range. As above it requires O(n).
    • Assume for example we want to iterate over all basic blocks and for each BB the xrefs. This is then O(|BBs| * |n|). Not ok.

Because the xrefs are such a vital information source it is worth to refactor it I think.
Especially adding new API functions to allow iteration over a specific subset of xrefs.

I think it is the simplest to add indices for different xref types and requests.

Metadata

Metadata

Assignees

No one assigned

    Labels

    New AnalysisA label to mark all PRs associated with the new analysis design and implementation.RzAnalysisperformanceA performance problem/enhancementrefactorRefactoring requests

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions