Skip to content

bpf/analyze: refactor reachability analysis and unused tail call elim#41875

Merged
giorio94 merged 11 commits intocilium:mainfrom
ti-mo:tb/reachability-followups
Sep 25, 2025
Merged

bpf/analyze: refactor reachability analysis and unused tail call elim#41875
giorio94 merged 11 commits intocilium:mainfrom
ti-mo:tb/reachability-followups

Conversation

@ti-mo
Copy link
Copy Markdown
Contributor

@ti-mo ti-mo commented Sep 24, 2025

Some readability and performance improvements that couldn't hold up the merge of the initial work.

In short:

  • added a unified BlockIterator that supports iterating forwards and backwards, as well as cloning for starting temporary backtracking sessions from the current instruction
  • added a Reachable type to hold block reachability information, wrapping a Blocks and insns
  • (not shown in benchmarks) Reachability is now computed only once per CollectionSpec load, as opposed to twice before the PR (once for maps, again for tail calls)
  • Computing reachability now allocates about 80% less memory since Blocks no longer needs to be copied
  • General refactoring for readability
goos: linux
goarch: amd64
pkg: github.com/cilium/cilium/pkg/bpf/analyze
cpu: AMD Ryzen 7 3700X 8-Core Processor
                 │   old.txt   │              new.txt               │
                 │   sec/op    │   sec/op     vs base               │
ComputeBlocks-16   633.7µ ± 2%   622.1µ ± 2%   -1.83% (p=0.015 n=6)
Reachability-16    32.87µ ± 2%   27.67µ ± 1%  -15.84% (p=0.002 n=6)
geomean            144.3µ        131.2µ        -9.10%

                 │   old.txt    │               new.txt               │
                 │     B/op     │     B/op      vs base               │
ComputeBlocks-16   372.6Ki ± 0%   372.5Ki ± 0%   -0.02% (p=0.002 n=6)
Reachability-16     8528.0 ± 0%     352.0 ± 0%  -95.87% (p=0.002 n=6)
geomean            55.71Ki        11.32Ki       -79.69%

                 │   old.txt   │              new.txt               │
                 │  allocs/op  │  allocs/op   vs base               │
ComputeBlocks-16   8.054k ± 0%   8.053k ± 0%   -0.01% (p=0.002 n=6)
Reachability-16     4.000 ± 0%    3.000 ± 0%  -25.00% (p=0.002 n=6)
geomean             179.5         155.4       -13.40%

Fixes: #41628

@ti-mo ti-mo requested review from a team as code owners September 24, 2025 10:18
@ti-mo ti-mo requested review from rgo3 and thorn3r September 24, 2025 10:18
@maintainer-s-little-helper maintainer-s-little-helper bot added the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Sep 24, 2025
@ti-mo ti-mo added the release-note/misc This PR makes changes that have no direct user impact. label Sep 24, 2025
@maintainer-s-little-helper maintainer-s-little-helper bot removed the dont-merge/needs-release-note-label The author needs to describe the release impact of these changes. label Sep 24, 2025
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 24, 2025

/test

@ti-mo ti-mo force-pushed the tb/reachability-followups branch from e40adb1 to b67c431 Compare September 24, 2025 10:23
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 24, 2025

/test

@ti-mo ti-mo force-pushed the tb/reachability-followups branch from b67c431 to 0b675e8 Compare September 24, 2025 10:38
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 24, 2025

/test

@ti-mo ti-mo force-pushed the tb/reachability-followups branch from 0b675e8 to e5beea1 Compare September 24, 2025 11:50
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 24, 2025

/test

@ti-mo ti-mo force-pushed the tb/reachability-followups branch from e5beea1 to b67531a Compare September 24, 2025 12:48
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 24, 2025

/test

@dylandreimerink dylandreimerink mentioned this pull request Sep 24, 2025
Closed
@dylandreimerink dylandreimerink self-requested a review September 24, 2025 13:40
ti-mo added 11 commits September 25, 2025 10:55
@ti-mo
analyze: factor reachability info out into dedicated analyze.Reachable
5d811f9 
This separates concerns and allows turning Blocks into an alias for []*Block.

Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: convert struct Blocks back into a []*Block
e6e9acb 
This was temporarily a struct to add on reachability information, but this has
now been factored out into its own thing.

Also use a fast popcnt() for counting ones in a bitmap.

Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: define Block.predecessor() in preparation for block iterator
572b22f 
A follow-up commit will introduce a Block iterator that can step forwards and
backwards randomly depending on the need. It will use this behaviour.

Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: introduce BlockIterator, use in analyze.LiveInstructions()
61b49e6 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: use BlockIterator.Previous() instead of Block.backward
d794c9a 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: return BlockIterator from LiveInstructions, rename to Iterate()
53042cc 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: store insns in *Reachable and implement visitBlock as method
697f364 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
analyze: export Bitmap for use in pkg/bpf/
4b1e04e 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
bpf: refactor removeUnusedTailcalls using recursion
318c575 
Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
bpf: factor out reachability analysis into computeReachability()
c7e60a8 
This allows reusing reachables across dead map and tail call elimination.

Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo
bpf: refactor removeUnusedTailcalls using reachableSpec
f3aa674 
This commit introduces a reachableSpec object that ties reachability
information to a ProgramSpec, to avoid having to pass an extra reachability
dict around. This is problematic since reachability is indexed by string,
while tails are indexed by id and only include a subset of the CollectionSpec.

Split up removeUnusedTailcalls() into discrete steps with clear in- and
outputs to improve readability.

Signed-off-by: Timo Beckers <timo@isovalent.com>
@ti-mo ti-mo force-pushed the tb/reachability-followups branch from b67531a to f3aa674 Compare September 25, 2025 08:58
@ti-mo
Copy link
Copy Markdown
Contributor Author

ti-mo commented Sep 25, 2025

/test

giorio94
giorio94 approved these changes Sep 25, 2025
View reviewed changes
Copy link
Copy Markdown
Member

@giorio94 giorio94 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

/lgtm for the logfields change.

@giorio94 giorio94 added this pull request to the merge queue Sep 25, 2025
Merged via the queue into cilium:main with commit 89ac07c Sep 25, 2025
71 checks passed
@cilium-release-bot cilium-release-bot bot moved this to Released in cilium v1.19.0 Feb 3, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@dylandreimerink dylandreimerink dylandreimerink approved these changes

@giorio94 giorio94 giorio94 approved these changes

@thorn3r thorn3r Awaiting requested review from thorn3r thorn3r is a code owner automatically assigned from cilium/sig-agent

@rgo3 rgo3 Awaiting requested review from rgo3 rgo3 is a code owner automatically assigned from cilium/loader

Assignees

No one assigned

Labels

release-note/misc This PR makes changes that have no direct user impact.

Projects

No open projects
cilium v1.19.0
Status: Released

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

bpf/analyze: BPF program reachability analysis follow-ups

4 participants

@ti-mo @dylandreimerink @giorio94 @msune