-
Notifications
You must be signed in to change notification settings - Fork 3.4k
bpf/analyze: reachability analysis for pruning unused maps #40416
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
Commit 458d50d does not match "(?m)^Signed-off-by:". Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin |
/test |
Commit 458d50d does not match "(?m)^Signed-off-by:". Please follow instructions provided in https://docs.cilium.io/en/stable/contributing/development/contributing_guide/#developer-s-certificate-of-origin |
/test |
/test |
/test |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Very nice work @tb and @dylandreimerink. Excellent comments in the code to guide readers who are less familiar or new to the code 🙇.
Special thanks to Dylan for that offline code walk, that helped a lot!
Overall looks good to me, just two questions to clarify my understanding of the tests and underlying logic.
1655d9e
to
18be707
Compare
At present, we use `ifdef`s to manually determine when a map definition should be emitted into the object file. When the object file gets loaded by the agent, every map therein is created and populated before programs can be loaded into the kernel. Given the quest for clang-freedom, we want to pre-compile all programs and only create and populate maps for features that are enabled at runtime based on global variables for feature flags. This commit introduces this capability. It performs static analysis on the BPF program, splits it into basic blocks and finds global data accesses used in branching instructions. Then, it can predict whether a branch is always or never taken. By occluding unreachable parts of the program, it predicts which maps will remain in use after the verifier performed its own dead code elimination as part of the verification process. Before loading, unused maps are removed from the CollectionSpec, and all of their references are poisoned with simple immediate load instructions. This means all maps can now be unconditionally defined, normal branches (if statements!) can be used, and developers no longer have to worry about when and which maps are or are not loaded under which conditions. Users don't have to pay for features they don't use. Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com> Signed-off-by: Timo Beckers <timo@isovalent.com> Co-authored-by: Timo Beckers <timo@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
Signed-off-by: Dylan Reimerink <dylan.reimerink@isovalent.com>
18be707
to
0cd3846
Compare
/test |
@cilium/sig-datapath still looking for a review on this 🥺 |
My take on #39462.
At present, we use
ifdef
s to manually determine when a map definitionshould be emitted into the object file. When the object file gets loaded by
the agent, every map therein is created and populated before programs can
be loaded into the kernel.
Given the quest for clang-freedom, we want to to pre-compile all programs
and only create and populate maps for features that are enabled at runtime
based on global variables for feature flags.
This commit introduces this capability. It performs static analysis on the BPF
program, splits it into basic blocks and finds global data accesses used in
branching instructions. Then, it can predict whether a branch is always or
never taken.
By occluding unreachable parts of the program, it predicts which maps will
remain in use after the verifier performed its own dead code elimination as
part of the verification process. Before loading, unused maps are removed from
the CollectionSpec, and all of their references are poisoned with simple
immediate load instructions.
This means all maps can now be unconditionally defined, normal branches (if
statements!) can be used, and developers no longer have to worry about when
and which maps are or are not loaded under which conditions. Users don't
have to pay for features they don't use.