An overview of the register tracking liveness algorithm.
Previous versions posted here: [1], [2].
- Changes from RFC to v1 (suggested by Andrii Nakryiko):
- wording corrected to use term "stack slot" instead of "stack spill";
- parentage chain diagram updated to show nil links for frame #1;
- added example for non-BPF_DW writes behavior;
- explanation in "Read marks propagation for cache hits" is reworked.
- Changes from v1 to v2:
- lot's of grammatical / wording fixes as suggested by David Vernet;
- "Register parentage chains" section is fixed to reflect what
happens to r1-r5 when function call is processed (as suggested by David and Alexei);
- Example in "Liveness marks tracking" section updated to explain
why partial writes should not lead to REG_LIVE_WRITTEN marks
(suggested by David);
- "Read marks propagation for cache hits" section updates:
- Explanation updated to hint why read marks should be propagated
before jumping to example (suggested by David);
- Removed box around B/D in the diagram updated (suggested by Alexei).
[1] https://lore.kernel.org/bpf/20230124220343.2942203-1-eddyz87@xxxxxxxxx/
[2] https://lore.kernel.org/bpf/20230130182400.630997-1-eddyz87@xxxxxxxxx/
Eduard Zingerman (1):
docs/bpf: Add description of register liveness tracking algorithm
Documentation/bpf/verifier.rst | 280 +++++++++++++++++++++++++++++++++
1 file changed, 280 insertions(+)
--
2.39.0
