Branch: refs/heads/bbiiggppiigg/optimize-getgaprange-fix
Home: https://github.com/dyninst/dyninst
Commit: 3d3f94457124e2f7acc9874c44ae756b22c4d961
https://github.com/dyninst/dyninst/commit/3d3f94457124e2f7acc9874c44ae756b22c4d961
Author: wuxx1279 <bbiiggppiigg@xxxxxxxxx>
Date: 2026-06-20 (Sat, 20 Jun 2026)
Changed paths:
M parseAPI/src/Parser-speculative.C
Log Message:
-----------
parseAPI: make speculative getGapRange O(log F) via funcsByRange
Parser::getGapRange rebuilt a sorted set of *every* function's extents on
every call to locate the gap around curAddr. It is called once per gap
discovered during speculative parsing, so the speculative pass was
~O(gaps x functions). On a large, symbol-rich binary (e.g. a ~400 MB shared
library with hundreds of thousands of functions) this dominated rewrite
time -- the per-gap rebuild ran for hours while the parallel
recursive-descent parse that precedes it finished in seconds.
Query region_data::funcsByRange (an IBSTree_fast<FuncExtent> that already
indexes every function's extents by address) instead:
- gapStart: stab curAddr (find) and advance past any covering extent;
- gapEnd: successor(curAddr) gives the next extent start (mirrors the
old upper_bound logic and the blocksByRange.successor idiom in
region_data::get_next_block).
This is O(log F) per call.
funcsByRange is filled only by finalize_ranges() (draining funcs_to_ranges),
which the parser calls lazily from findFuncs/findBlocks. finalize() fills
funcs_to_ranges but does not flush it, so at the start of the gap loop the
tree can be empty; and each gap-discovered function (parse_at downgrades
_parse_state, re-running finalize()) adds to funcs_to_ranges without
flushing. The old code read sorted_funcs, which parse_at keeps current, so
to preserve that behavior getGapRange now flushes any pending finalized
functions into the tree before querying it. Without the flush every
already-parsed function would be invisible (treated as one giant gap and
re-scanned byte-by-byte), and just-discovered gap functions could spawn
overlapping functions inside themselves.
No functional change to which gaps are scanned; behavior matches the prior
sorted_funcs-based implementation, but the speculative pass on a 256 MB
.text region drops from hours to ~1 second.
Co-Authored-By: Claude Opus 4.8 <noreply@xxxxxxxxxxxxx>
Commit: abd977e372033a4cc18e185a05f1d02b5f62c510
https://github.com/dyninst/dyninst/commit/abd977e372033a4cc18e185a05f1d02b5f62c510
Author: wuxx1279 <bbiiggppiigg@xxxxxxxxx>
Date: 2026-06-20 (Sat, 20 Jun 2026)
Changed paths:
M common/h/IBSTree-fast.h
Log Message:
-----------
common: fix IBSTree_fast::successor assert on coincident-start intervals
IBSTree_fast::successor() called the overlapping-interval tree's scalar
IBSTree::successor(X), which asserts the successor of a point is unique
(out.size() <= 1). That holds for the original caller, blocksByRange (basic
blocks have unique start addresses), but not in general: intervals can share
a start address -- e.g. FuncExtents of identical-code-folded or aliased
functions begin at the same address. When getGapRange() began querying
funcsByRange.successor() during speculative gap parsing, such a coincident
start made the overlapping tree return >1 candidate and aborted the rewrite
(observed on an ICF-heavy shared library; data-dependent, hence latent).
Use the set-returning overlapping_intervals.successor(X, set) and keep the
smallest-low() candidate. That is the true successor and collapses any
coincident-start ties to a single result, so the scalar IBSTree_fast wrapper
still sees at most one. No behavior change for unique-start trees (the set
has <= 1 element); blocksByRange/get_next_block is unaffected.
Co-Authored-By: Claude Opus 4.8 <noreply@xxxxxxxxxxxxx>
Commit: 76f9e1d32f258685e263186cb28e9d96ee9a0f50
https://github.com/dyninst/dyninst/commit/76f9e1d32f258685e263186cb28e9d96ee9a0f50
Author: wuxx1279 <bbiiggppiigg@xxxxxxxxx>
Date: 2026-06-20 (Sat, 20 Jun 2026)
Changed paths:
M parseAPI/src/Parser-speculative.C
Log Message:
-----------
parseAPI: fix getGapRange over-large gap that corrupted the CFG
The O(log F) getGapRange (commit 3d3f944) located the next function extent
with funcsByRange.successor(curAddr). But the speculative gap loop in
parse_gap_heuristic leaves curAddr sitting *on* a function entry almost every
iteration -- it is the FEP that parse_at just discovered, or the next
function's start that bounded the previous gap. IBSTree_fast::successor(X)
returns the extent with the smallest high() greater than X, which for a
covered X is the covering extent itself (start() <= X). The
"next->start() > curAddr" guard then rejected it, so gapEnd fell back to the
region end. That over-large gap let the scanner walk through already-parsed
functions, spuriously parse_at-ing inside them; the resulting overlapping
blocks left an intraproc edge pointing at a block liveness never summarized,
firing the blockLiveInfo.find(block) assertion in LivenessAnalyzer during
relocation (reported on PR #2290, reproduced by test_reloc).
Query the successor at gapStart instead of curAddr: gapStart has already been
advanced past every extent covering curAddr, so successor(gapStart) skips them
and returns the genuinely-following extent. Use its start() directly with no
">curAddr" guard -- a contiguous next function (start() == gapStart) yields
gapEnd == gapStart and getGapRange returns false, exactly like the old
upper_bound logic, while a real gap is bounded at the next function's start.
Verified against a master build (original getGapRange) with a master-linked
testsuite: test_reloc create=PASSED on both, no blockLiveInfo assertion, and
equivalent runtime. The remaining rewriter "Group Teardown" crash reproduces
identically on master and is unrelated to this change.
Co-Authored-By: Claude Opus 4.8 <noreply@xxxxxxxxxxxxx>
Compare: https://github.com/dyninst/dyninst/compare/3d3f94457124%5E...76f9e1d32f25
To unsubscribe from these emails, change your notification settings at https://github.com/dyninst/dyninst/settings/notifications
|