Skip to content

docs/bpf: Add description of register liveness tracking algorithm

Eduard Zingerman bpf 4 versions – Applied

Status from this message: This patch was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest1 patch 1 replyApplied 1/1
  2. v31 patch 5 repliesSuperseded
  3. v21 patch 3 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v1 RFC1 patch3 repliesSuperseded

Patches in v4 All 1 applied

#Subject and filesSizeRepliesApplied
1/1docs/bpf: Add description of register liveness tracking algorithmDocumentation/bpf/verifier.rst+295 -01 replyApplied

Reviews trailers per patch

The patch has a Reviewed-by or Acked-by.

PatchEdward Cree
1/1R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH bpf-next v4 0/1] docs/bpf: Add description of register liveness tracking algorithm

An overview of the register tracking liveness algorithm. Previous versions posted here: [1], [2], [3].
- Changes from RFC to v2 (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 v2 to v3:
- 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).
- Changes from v3 to v4 (suggested by Edward Cree):
- register parentage chain diagram updated to explain why r6 mark is

    not propagated;
  - read mark propagation algorithm pseudo-code fixed to correctly
    show "if state->live & REG_LIVE_WRITTEN" stop condition;

- general wording improvements in section "Liveness marks tracking".

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/
[3] https://lore.kernel.org/bpf/[email protected]/

Eduard Zingerman (1):
docs/bpf: Add description of register liveness tracking algorithm

 Documentation/bpf/verifier.rst | 295 +++++++++++++++++++++++++++++++++
 1 file changed, 295 insertions(+)
Signature · 1 line
2.39.0