Skip to contentSkip to conversation

docs/bpf: Add description of register liveness tracking algorithm

PATCH Superseded Eduard Zingerman 3 participants 5 messages Jan 30, 2023 – Jan 31, 2023

Subsystems (2)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

v2 cover docs/bpf: Add description of register liveness tracking algorithm

An overview of the register tracking liveness algorithm. Previous version posted here: [1].
This update includes fixes 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.

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

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

 Documentation/bpf/verifier.rst | 266 +++++++++++++++++++++++++++++++++
 1 file changed, 266 insertions(+)
Signature · 1 line
2.39.0
author maintainer
#1 lore raw

PATCH v2 1/1 docs/bpf: Add description of register liveness tracking algorithm

This is a followup for [1], adds an overview for the register liveness tracking, covers the following points:
- why register liveness tracking is useful;
- how register parentage chains are constructed;
- how liveness marks are applied using the parentage chains.

[1] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@mail.gmail.com/

---
 Documentation/bpf/verifier.rst | 266 +++++++++++++++++++++++++++++++++
 1 file changed, 266 insertions(+)
Documentation/bpf/verifier.rst +266 -0
index 3afa548ec28c..7269933428e1 100644
@@ -316,6 +316,272 @@ Pruning considers not only the registers but also the stack (and any spilled
 registers it may hold).  They must all be safe for the branch to be pruned.
 This is implemented in states_equal().
 
+Some technical details about state pruning implementation could be found below.
+
+Register liveness tracking
+--------------------------
+
+In order to make state pruning effective liveness state is tracked for each
+register and stack slot. The basic idea is to identify which registers or stack
+slots were used by children of the state to reach the program exit. Registers
+that were never used could be removed from the cached state thus making more
+states equivalent to a cached state. This could be illustrated by the following
+program::
+
+  0: call bpf_get_prandom_u32()
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint ---
+  4: r0 = r1
+  5: exit
+
+Suppose that state cache entry is created at instruction #4 (such entries are
+also called "checkpoints" in the text below), verifier reaches this instruction
+in two states:
+
+* r0 = 1, r1 = 0
+* r0 = 0, r1 = 0
+
+However, only the value of register ``r1`` is important to successfully finish
+verification. The goal of liveness tracking algorithm is to spot this fact and
+figure out that both states are actually equivalent.
+
+Data structures
+~~~~~~~~~~~~~~~
+
+Liveness is tracked using the following data structures::
+
+  enum bpf_reg_liveness {
+	REG_LIVE_NONE = 0,
+	REG_LIVE_READ32 = 0x1,
+	REG_LIVE_READ64 = 0x2,
+	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
+	REG_LIVE_WRITTEN = 0x4,
+	REG_LIVE_DONE = 0x8,
+  };
+
+  struct bpf_reg_state {
+ 	...
+	struct bpf_reg_state *parent;
+ 	...
+	enum bpf_reg_liveness live;
+ 	...
+  };
+
+  struct bpf_stack_state {
+	struct bpf_reg_state spilled_ptr;
+	...
+  };
+
+  struct bpf_func_state {
+	struct bpf_reg_state regs[MAX_BPF_REG];
+        ...
+	struct bpf_stack_state *stack;
+  }
+  
+  struct bpf_verifier_state {
+	struct bpf_func_state *frame[MAX_CALL_FRAMES];
+	struct bpf_verifier_state *parent;
+        ...
+  }
+
+* ``REG_LIVE_NONE`` is an initial value assigned to ``->live`` fields upon new
+  verifier state creation;
+
+* ``REG_LIVE_WRITTEN`` means that the value of the register (or stack slot) is
+  defined by some instruction "executed" within verifier state;
+
+* ``REG_LIVE_READ{32,64}`` means that the value of the register (or stack slot)
+  is read by some instruction "executed" within verifier state;
+
+* ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid
+  processing same verifier state multiple times and for some sanity checks;
+
+* ``->live`` field values are formed by combining ``enum bpf_reg_liveness``
+  values using bitwise or.
+
+Register parentage chains
+~~~~~~~~~~~~~~~~~~~~~~~~~
+  
+In order to propagate information between parent and child states register
+parentage chain is established. Each register or stack slot is linked to a
+corresponding register or stack slot in it's parent state via a ``->parent``
+pointer. This link is established upon state creation in function
+``is_state_visited()`` and is never changed.
+
+The rules for correspondence between registers / stack slots are as follows:
+
+* For current stack frame registers and stack slots of the new state are linked
+  to the registers and stack slots of the parent state with the same indices.
+
+* For outer stack frames only caller saved registers (r6-r9) and stack slots are
+  linked to the registers and stack slots of the parent state with the same
+  indices.
+
+This could be illustrated by the following diagram (arrows stand for
+``->parent`` pointers)::
+
+      ...                    ; Frame #0, some instructions
+  --- checkpoint #0 ---
+  1 : r6 = 42                ; Frame #0
+  --- checkpoint #1 ---
+  2 : call foo()             ; Frame #0
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #2 ---
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #3 ---
+      exit                   ; Frame #1, return from foo()
+  3 : r1 = r6                ; Frame #0  <- current state
+  
+             +--------------------------+--------------------------+ 
+             |         Frame #0         |         Frame #1         |
+  Checkpoint +--------------------------+--------------------------+
+  #0         | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+                           
+                ^       ^       ^
+                |       |       |          
+  Checkpoint +--------------------------+                           
+  #1         | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+
+                        ^       ^         nil     nil     nil 
+                        |       |          |       |       |          
+  Checkpoint +--------------------------+--------------------------+
+  #2         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^          ^       ^       ^  
+                        |       |          |       |       |
+  Checkpoint +--------------------------+--------------------------+
+  #3         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^
+                        |       |          
+  Current    +--------------------------+                           
+  state      | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+
+                        \           
+                          r6 read mark is propagated via
+                          these links all the way up to
+                          checkpoint #1.
+
+Liveness marks tracking
+~~~~~~~~~~~~~~~~~~~~~~~
+
+For each processed instruction verifier propagates information about reads up
+the parentage chain and saves information about writes in the current state.
+The information about reads is propagated by function ``mark_reg_read()`` which
+could be summarized as follows::
+
+  mark_reg_read(struct bpf_reg_state *state):
+      parent = state->parent
+      while parent:
+          if parent->live & REG_LIVE_WRITTEN:
+              break
+          if parent->live & REG_LIVE_READ64:
+              break
+          parent->live |= REG_LIVE_READ64
+          state = parent
+          parent = state->parent
+
+Note: details about REG_LIVE_READ32 are omitted.
+
+Also note: the read marks are applied to the **parent** state while write marks
+are applied to the **current** state.
+
+Because stack writes could have different sizes ``REG_LIVE_WRITTEN`` marks are
+applied conservatively: stack slots are marked as written only if write size
+corresponds to the size of the register, e.g. see function ``save_register_state()``.
+
+Consider the following example::
+
+  0: (*u64)(r10 - 8) = 0
+  --- checkpoint #0 ---
+  1: (*u32)(r10 - 8) = 1
+  2: r1 = (*u32)(r10 - 8)
+
+Because write size at instruction (1) is smaller than register size the write
+mark will not be added to fp-8 slot when (1) is verified, thus the fp-8 read at
+instruction (2) would propagate read mark for fp-8 up to checkpoint #0.
+
+Once ``BPF_EXIT`` instruction is reached function ``update_branch_counts()`` is
+called to update the ``->branches`` counter for each verifier state in a chain
+of parent verifier states. When ``->branches`` counter reaches zero the verifier
+state becomes a valid entry in a set of cached verifier states.
+
+Each entry of the verifier states cache is post-processed by a function
+``clean_live_states()``. This function marks all registers and stack slots
+without ``REG_LIVE_READ{32,64}`` marks as ``NOT_INIT`` or ``STACK_INVALID``.
+Registers/stack slots marked in this way are ignored in function ``stacksafe()``
+called from ``states_equal()`` when state cache entry is considered for
+equivalence with a current state.
+
+Now it is possible to explain how the example from the beginning of the section
+works::
+
+  0: call bpf_get_prandom_u32()
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint[0] ---
+  4: r0 = r1
+  5: exit
+
+* At instruction #2 branching point is reached and state ``{ r0 == 0, r1 == 0, pc == 4 }``
+  is pushed to states processing queue (pc stands for program counter).
+  
+* At instruction #4:
+  
+  * ``checkpoint[0]`` states cache entry is created: ``{ r0 == 1, r1 == 0, pc == 4 }``;
+  * ``checkpoint[0].r0`` is marked as written;
+  * ``checkpoint[0].r1`` is marked as read;
+
+* At instruction #5 exit is reached and ``checkpoint[0]`` can now be processed
+  by ``clean_live_states()``, after this processing ``checkpoint[0].r0`` has a
+  read mark and all other registers and stack slots are marked as ``NOT_INIT``
+  or ``STACK_INVALID``
+  
+* The state ``{ r0 == 0, r1 == 0, pc == 4 }`` is popped from the states queue
+  and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states
+  are considered equivalent.
+
+Read marks propagation for cache hits
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Another important point is handling of read marks when a previously verified
+state is found in the states cache. All read marks present on registers and
+stack slots of the cached state must be propagated over the parentage chain of
+the current state. Function ``propagate_liveness()`` handles this case.
+
+For example, consider the following state parentage chain (S is a
+starting state, A-E are derived states, -> arrows show which state is
+derived from which)::
+
+                      r1 read
+               <-------------                    A[r1] == 0
+                    +---+                        C[r1] == 0
+      S ---> A ---> | B | ---> exit              E[r1] == 1
+      |             |   |
+      ` ---> C ---> | D |
+      |             +---+
+      ` ---> E        
+                      ^
+             ^        |___   suppose all these
+             |             states are at insn #Y
+      suppose all these
+    states are at insn #X
+
+* Chain of states ``S -> A -> B -> exit`` is verified first.
+
+* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is
+  propagated up to state ``A``.
+
+* When chain of states ``C -> D`` is verified the state ``D`` turns out to be
+  equivalent to state ``B``.
+
+* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state
+  ``C`` might get mistakenly marked as equivalent to state ``E`` even though
+  values for register ``r1`` differ between ``C`` and ``E``.
+
 Understanding eBPF verifier messages
 ====================================
 
Signature · 1 line
2.39.0
#2 lore raw
Quoted 9 lines · Eduard Zingerman

This is a followup for [1], adds an overview for the register liveness tracking, covers the following points:
- why register liveness tracking is useful;
- how register parentage chains are constructed;
- how liveness marks are applied using the parentage chains.

[1] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@mail.gmail.com/

This is great, thanks a lot for writing this up. Left some comments.

Quoted 9 lines
---
 Documentation/bpf/verifier.rst | 266 +++++++++++++++++++++++++++++++++
 1 file changed, 266 insertions(+)
Documentation/bpf/verifier.rst +0 -0
index 3afa548ec28c..7269933428e1 100644

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 324

Quoted 9 lines
Documentation/bpf/verifier.rst +6 -0
@@ -316,6 +316,272 @@ Pruning considers not only the registers but also the stack (and any spilled
 registers it may hold).  They must all be safe for the branch to be pruned.
 This is implemented in states_equal().
 
+Some technical details about state pruning implementation could be found below.
+
+Register liveness tracking
+--------------------------
+
+In order to make state pruning effective liveness state is tracked for each

Could you please add a comma after "effective"? Will use shorthand s/xxx/yyy for future suggestions like this.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 326

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+register and stack slot. The basic idea is to identify which registers or stack
+slots were used by children of the state to reach the program exit. Registers

IMO the phrasing "used by children of the state" may be a bit confusing. What do you think about this?

"The basic idea is to track which registers and stack slots are actually used during subseqeuent execution of the program, until program exit is reached."

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 327

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+that were never used could be removed from the cached state thus making more

s/Registers that were never/Registers and stack slots that were never

Quoted 4 lines
Documentation/bpf/verifier.rst +4 -0
+states equivalent to a cached state. This could be illustrated by the following
+program::
+
+  0: call bpf_get_prandom_u32()

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 341

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint ---
+  4: r0 = r1
+  5: exit
+
+Suppose that state cache entry is created at instruction #4 (such entries are
+also called "checkpoints" in the text below), verifier reaches this instruction
+in two states:

Can we split these into two sentences? Wdyt about the following:

"Suppose that a state cache entry is created at instruction #4 (such entries are also called "checkpoints" in the text below). The verifier could reach the instruction with one of two possible register states:"

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 347

Quoted 6 lines
Documentation/bpf/verifier.rst +6 -0
+
+* r0 = 1, r1 = 0
+* r0 = 0, r1 = 0
+
+However, only the value of register ``r1`` is important to successfully finish
+verification. The goal of liveness tracking algorithm is to spot this fact and

s/ of liveness tracking/of the liveness tracking

Quoted 5 lines
Documentation/bpf/verifier.rst +5 -0
+figure out that both states are actually equivalent.
+
+Data structures
+~~~~~~~~~~~~~~~
+

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 362

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+Liveness is tracked using the following data structures::
+
+  enum bpf_reg_liveness {
+	REG_LIVE_NONE = 0,
+	REG_LIVE_READ32 = 0x1,
+	REG_LIVE_READ64 = 0x2,
+	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
+	REG_LIVE_WRITTEN = 0x4,
+	REG_LIVE_DONE = 0x8,
+  };

FYI, you have the option of using the .. kernel-doc:: directive here, as in e.g.:

.. kernel-doc:: include/linux/bpf_verifier.h
:identifiers: bpf_reg_liveness

For enum bpf_reg_liveness and the other types. Doing so would require you updating the kernel-doc header comment in include/linux/bpf_verifier.h to reflect the description in [0], i.e. something like this for enum bpf_reg_liveness:

[0]: https://docs.kernel.org/doc-guide/kernel-doc.html#structure-union-and-enumeration-documentation

/**
* enum bpf_reg_liveness - Liveness marks, used for registers and spilled-regs
* @REG_LIVE_NONE: reg hasn't been read or written this branch
* @REG_LIVE_READ32: reg was read, so we're sensitive to initial value
* @REG_LIVE_READ64: likewise, but full 64-bit content matters
* @REG_LIVE_READ: An OR of both 32 and 64 bit read reg states.
* @REG_LIVE_WRITTEN: reg was written first, screening off later reads
* @REG_LIVE_DONE: liveness won't be updating this register anymore *
* Read marks propagate upwards until they find a write mark; they record that
* "one of this state's descendants read this reg" (and therefore the reg is
* relevant for states_equal() checks).
* Write marks collect downwards and do not propagate; they record that "the
* straight-line code that reached this state (from its parent) wrote this reg"
* (and therefore that reads propagated from this state or its descendants
* should not propagate to its parent).
* A state with a write mark can receive read marks; it just won't propagate
* them to its parent, since the write mark is a property, not of the state,
* but of the link between it and its parent. See mark_reg_read() and
* mark_stack_slot_read() in kernel/bpf/verifier.c.
*/

Not everyone likes how the rendered HTML looks, and I tend to agree that it looks pretty blocky, but it at least keeps all of this documentation in one place and avoids going stale. Also, it has the benefit of automatically creating a link to the ..kernel-doc:: comment anywhere that "enum bpf_reg_liveness" is written in the Documentation subtree.

Quoted 35 lines
Documentation/bpf/verifier.rst +35 -0
+
+  struct bpf_reg_state {
+ 	...
+	struct bpf_reg_state *parent;
+ 	...
+	enum bpf_reg_liveness live;
+ 	...
+  };
+
+  struct bpf_stack_state {
+	struct bpf_reg_state spilled_ptr;
+	...
+  };
+
+  struct bpf_func_state {
+	struct bpf_reg_state regs[MAX_BPF_REG];
+        ...
+	struct bpf_stack_state *stack;
+  }
+  
+  struct bpf_verifier_state {
+	struct bpf_func_state *frame[MAX_CALL_FRAMES];
+	struct bpf_verifier_state *parent;
+        ...
+  }
+
+* ``REG_LIVE_NONE`` is an initial value assigned to ``->live`` fields upon new
+  verifier state creation;
+
+* ``REG_LIVE_WRITTEN`` means that the value of the register (or stack slot) is
+  defined by some instruction "executed" within verifier state;
+
+* ``REG_LIVE_READ{32,64}`` means that the value of the register (or stack slot)
+  is read by some instruction "executed" within verifier state;
+

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 407

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+* ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid
+  processing same verifier state multiple times and for some sanity checks;
+
+* ``->live`` field values are formed by combining ``enum bpf_reg_liveness``
+  values using bitwise or.
+
+Register parentage chains
+~~~~~~~~~~~~~~~~~~~~~~~~~
+  
+In order to propagate information between parent and child states register

Suggestion:

s/parent and child states register parentage chain/
parent and child states, a *register parentage chain*

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 409

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+parentage chain is established. Each register or stack slot is linked to a
+corresponding register or stack slot in it's parent state via a ``->parent``

s/it's/its

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 410

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+pointer. This link is established upon state creation in function

suggestion: I think you can remove the word 'function'.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 416

Quoted 6 lines
Documentation/bpf/verifier.rst +6 -0
+``is_state_visited()`` and is never changed.
+
+The rules for correspondence between registers / stack slots are as follows:
+
+* For current stack frame registers and stack slots of the new state are linked
+  to the registers and stack slots of the parent state with the same indices.

s/For current stack frame registers/For the current stack frame, registers

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 420

Quoted 4 lines
Documentation/bpf/verifier.rst +4 -0
+
+* For outer stack frames only caller saved registers (r6-r9) and stack slots are
+  linked to the registers and stack slots of the parent state with the same
+  indices.

s/For the outer stack frames only/For the outer stack frames, only

Quoted 35 lines
Documentation/bpf/verifier.rst +35 -0
+
+This could be illustrated by the following diagram (arrows stand for
+``->parent`` pointers)::
+
+      ...                    ; Frame #0, some instructions
+  --- checkpoint #0 ---
+  1 : r6 = 42                ; Frame #0
+  --- checkpoint #1 ---
+  2 : call foo()             ; Frame #0
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #2 ---
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #3 ---
+      exit                   ; Frame #1, return from foo()
+  3 : r1 = r6                ; Frame #0  <- current state
+  
+             +--------------------------+--------------------------+ 
+             |         Frame #0         |         Frame #1         |
+  Checkpoint +--------------------------+--------------------------+
+  #0         | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+                           
+                ^       ^       ^
+                |       |       |          
+  Checkpoint +--------------------------+                           
+  #1         | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+
+                        ^       ^         nil     nil     nil 
+                        |       |          |       |       |          
+  Checkpoint +--------------------------+--------------------------+
+  #2         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^          ^       ^       ^  
+                        |       |          |       |       |
+  Checkpoint +--------------------------+--------------------------+
+  #3         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 465

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+             +--------------------------+--------------------------+
+                        ^       ^
+                        |       |          
+  Current    +--------------------------+                           
+  state      | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+
+                        \           
+                          r6 read mark is propagated via
+                          these links all the way up to
+                          checkpoint #1.

IMO this illustration is kind of confusing as shown, relative to the descriptions of current / outer above. 'Frame #1' is potentially in a different function / subprog, correct? So it seems kind of confusing to see it propagating registers from checkpoint 3 -> checkpoint 2, etc. And it's propagating r0-r5. Similarly, it looks like 'Current state' isn't propagating r0-r5. I'm sure I'm misunderstanding something.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 470

Quoted 5 lines
Documentation/bpf/verifier.rst +5 -0
+
+Liveness marks tracking
+~~~~~~~~~~~~~~~~~~~~~~~
+
+For each processed instruction verifier propagates information about reads up

s/processed instruction verifier/processed instruction, the verifier

Quoted 22 lines
Documentation/bpf/verifier.rst +22 -0
+the parentage chain and saves information about writes in the current state.
+The information about reads is propagated by function ``mark_reg_read()`` which
+could be summarized as follows::
+
+  mark_reg_read(struct bpf_reg_state *state):
+      parent = state->parent
+      while parent:
+          if parent->live & REG_LIVE_WRITTEN:
+              break
+          if parent->live & REG_LIVE_READ64:
+              break
+          parent->live |= REG_LIVE_READ64
+          state = parent
+          parent = state->parent
+
+Note: details about REG_LIVE_READ32 are omitted.
+
+Also note: the read marks are applied to the **parent** state while write marks
+are applied to the **current** state.
+
+Because stack writes could have different sizes ``REG_LIVE_WRITTEN`` marks are
+applied conservatively: stack slots are marked as written only if write size

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 502

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+corresponds to the size of the register, e.g. see function ``save_register_state()``.
+
+Consider the following example::
+
+  0: (*u64)(r10 - 8) = 0
+  --- checkpoint #0 ---
+  1: (*u32)(r10 - 8) = 1
+  2: r1 = (*u32)(r10 - 8)
+
+Because write size at instruction (1) is smaller than register size the write

s/write size/the write size

also

s/than register size the/than register size, the

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 504

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+mark will not be added to fp-8 slot when (1) is verified, thus the fp-8 read at
+instruction (2) would propagate read mark for fp-8 up to checkpoint #0.

s/is verified, thus/is verifier. Thus

also

s/would propagate read mark/would propagate the read mark

In general, this sentence explains mechanically why the write won't propagate (the write size is smaller than the register size), but I think it would be useful to explain why sizeof(write) < sizeof(reg) implies that it won't be propagated.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 506

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+
+Once ``BPF_EXIT`` instruction is reached function ``update_branch_counts()`` is

s/Once ``BPF_EXIT``/Once the ``BPF_EXIT``

also

s/is reached function/is reached,

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 508

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+called to update the ``->branches`` counter for each verifier state in a chain
+of parent verifier states. When ``->branches`` counter reaches zero the verifier

s/When ``->branches`` counter reaches zero/
When the ``branches`` counter reaches zero,

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 515

Quoted 7 lines
Documentation/bpf/verifier.rst +7 -0
+state becomes a valid entry in a set of cached verifier states.
+
+Each entry of the verifier states cache is post-processed by a function
+``clean_live_states()``. This function marks all registers and stack slots
+without ``REG_LIVE_READ{32,64}`` marks as ``NOT_INIT`` or ``STACK_INVALID``.
+Registers/stack slots marked in this way are ignored in function ``stacksafe()``
+called from ``states_equal()`` when state cache entry is considered for

s/when state cache entry/when a state cache entry

Quoted 14 lines
Documentation/bpf/verifier.rst +14 -0
+equivalence with a current state.
+
+Now it is possible to explain how the example from the beginning of the section
+works::
+
+  0: call bpf_get_prandom_u32()
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint[0] ---
+  4: r0 = r1
+  5: exit
+
+* At instruction #2 branching point is reached and state ``{ r0 == 0, r1 == 0, pc == 4 }``

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 539

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+  is pushed to states processing queue (pc stands for program counter).
+  
+* At instruction #4:
+  
+  * ``checkpoint[0]`` states cache entry is created: ``{ r0 == 1, r1 == 0, pc == 4 }``;
+  * ``checkpoint[0].r0`` is marked as written;
+  * ``checkpoint[0].r1`` is marked as read;
+
+* At instruction #5 exit is reached and ``checkpoint[0]`` can now be processed
+  by ``clean_live_states()``, after this processing ``checkpoint[0].r0`` has a

s/by ``clean_live_states()``, after/by ``clean_live_states()``. After

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 550

Quoted 11 lines
Documentation/bpf/verifier.rst +11 -0
+  read mark and all other registers and stack slots are marked as ``NOT_INIT``
+  or ``STACK_INVALID``
+  
+* The state ``{ r0 == 0, r1 == 0, pc == 4 }`` is popped from the states queue
+  and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states
+  are considered equivalent.
+
+Read marks propagation for cache hits
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Another important point is handling of read marks when a previously verified

s/is handling of/is the handling of

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 553

Quoted 3 lines
Documentation/bpf/verifier.rst +3 -0
+state is found in the states cache. All read marks present on registers and
+stack slots of the cached state must be propagated over the parentage chain of
+the current state. Function ``propagate_liveness()`` handles this case.

Suggestion: Consider expanding the sentence to include why it's necessary to propagate like this. You explain below after the diagram, but it might be helpful to clarify here so the reader has some context when reading over the diagram.

Quoted 37 lines
Documentation/bpf/verifier.rst +31 -0
+
+For example, consider the following state parentage chain (S is a
+starting state, A-E are derived states, -> arrows show which state is
+derived from which)::
+
+                      r1 read
+               <-------------                    A[r1] == 0
+                    +---+                        C[r1] == 0
+      S ---> A ---> | B | ---> exit              E[r1] == 1
+      |             |   |
+      ` ---> C ---> | D |
+      |             +---+
+      ` ---> E        
+                      ^
+             ^        |___   suppose all these
+             |             states are at insn #Y
+      suppose all these
+    states are at insn #X
+
+* Chain of states ``S -> A -> B -> exit`` is verified first.
+
+* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is
+  propagated up to state ``A``.
+
+* When chain of states ``C -> D`` is verified the state ``D`` turns out to be
+  equivalent to state ``B``.
+
+* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state
+  ``C`` might get mistakenly marked as equivalent to state ``E`` even though
+  values for register ``r1`` differ between ``C`` and ``E``.
+
 Understanding eBPF verifier messages
 ====================================
 
Signature · 1 line
2.39.0
author maintainer
#3 lore raw
Quoted 25 lines · David Vernet
Quoted 9 lines · Eduard Zingerman

This is a followup for [1], adds an overview for the register liveness tracking, covers the following points:
- why register liveness tracking is useful;
- how register parentage chains are constructed;
- how liveness marks are applied using the parentage chains.

[1] https://lore.kernel.org/bpf/CAADnVQKs2i1iuZ5SUGuJtxWVfGYR9kDgYKhq3rNV+kBLQCu7rA@mail.gmail.com/

This is great, thanks a lot for writing this up. Left some comments.

Quoted 12 lines
---
 Documentation/bpf/verifier.rst | 266 +++++++++++++++++++++++++++++++++
 1 file changed, 266 insertions(+)
Documentation/bpf/verifier.rst +0 -0
index 3afa548ec28c..7269933428e1 100644
@@ -316,6 +316,272 @@ Pruning considers not only the registers but also the stack (and any spilled
 registers it may hold).  They must all be safe for the branch to be pruned.
 This is implemented in states_equal().
 
Quoted 1 line

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 319

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+Some technical details about state pruning implementation could be found below.

Hi David,

Thank you for commenting. I'll update the doc according to your s/xxx/yyy/ suggestions, sorry for the amount of missing comas, etc. Regarding some bigger points please see below.

Quoted 104 lines

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 324

Quoted 5 lines
Documentation/bpf/verifier.rst +5 -0
+
+Register liveness tracking
+--------------------------
+
+In order to make state pruning effective liveness state is tracked for each

Could you please add a comma after "effective"? Will use shorthand s/xxx/yyy for future suggestions like this.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 326

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+register and stack slot. The basic idea is to identify which registers or stack
+slots were used by children of the state to reach the program exit. Registers

IMO the phrasing "used by children of the state" may be a bit confusing. What do you think about this?

"The basic idea is to track which registers and stack slots are actually used during subseqeuent execution of the program, until program exit is reached."

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 327

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+that were never used could be removed from the cached state thus making more

s/Registers that were never/Registers and stack slots that were never

Quoted 4 lines
Documentation/bpf/verifier.rst +4 -0
+states equivalent to a cached state. This could be illustrated by the following
+program::
+
+  0: call bpf_get_prandom_u32()

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 341

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint ---
+  4: r0 = r1
+  5: exit
+
+Suppose that state cache entry is created at instruction #4 (such entries are
+also called "checkpoints" in the text below), verifier reaches this instruction
+in two states:

Can we split these into two sentences? Wdyt about the following:

"Suppose that a state cache entry is created at instruction #4 (such entries are also called "checkpoints" in the text below). The verifier could reach the instruction with one of two possible register states:"

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 347

Quoted 6 lines
Documentation/bpf/verifier.rst +6 -0
+
+* r0 = 1, r1 = 0
+* r0 = 0, r1 = 0
+
+However, only the value of register ``r1`` is important to successfully finish
+verification. The goal of liveness tracking algorithm is to spot this fact and

s/ of liveness tracking/of the liveness tracking

Quoted 5 lines
Documentation/bpf/verifier.rst +5 -0
+figure out that both states are actually equivalent.
+
+Data structures
+~~~~~~~~~~~~~~~
+

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 362

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+Liveness is tracked using the following data structures::
+
+  enum bpf_reg_liveness {
+	REG_LIVE_NONE = 0,
+	REG_LIVE_READ32 = 0x1,
+	REG_LIVE_READ64 = 0x2,
+	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
+	REG_LIVE_WRITTEN = 0x4,
+	REG_LIVE_DONE = 0x8,
+  };

FYI, you have the option of using the .. kernel-doc:: directive here, as in e.g.:

.. kernel-doc:: include/linux/bpf_verifier.h
:identifiers: bpf_reg_liveness

For enum bpf_reg_liveness and the other types. Doing so would require you updating the kernel-doc header comment in include/linux/bpf_verifier.h to reflect the description in [0], i.e. something like this for enum bpf_reg_liveness:

[0]: https://docs.kernel.org/doc-guide/kernel-doc.html#structure-union-and-enumeration-documentation

/**
* enum bpf_reg_liveness - Liveness marks, used for registers and spilled-regs
* @REG_LIVE_NONE: reg hasn't been read or written this branch
* @REG_LIVE_READ32: reg was read, so we're sensitive to initial value
* @REG_LIVE_READ64: likewise, but full 64-bit content matters
* @REG_LIVE_READ: An OR of both 32 and 64 bit read reg states.
* @REG_LIVE_WRITTEN: reg was written first, screening off later reads
* @REG_LIVE_DONE: liveness won't be updating this register anymore *
* Read marks propagate upwards until they find a write mark; they record that
* "one of this state's descendants read this reg" (and therefore the reg is
* relevant for states_equal() checks).
* Write marks collect downwards and do not propagate; they record that "the
* straight-line code that reached this state (from its parent) wrote this reg"
* (and therefore that reads propagated from this state or its descendants
* should not propagate to its parent).
* A state with a write mark can receive read marks; it just won't propagate
* them to its parent, since the write mark is a property, not of the state,
* but of the link between it and its parent. See mark_reg_read() and
* mark_stack_slot_read() in kernel/bpf/verifier.c.
*/

Quoted 5 lines

Not everyone likes how the rendered HTML looks, and I tend to agree that it looks pretty blocky, but it at least keeps all of this documentation in one place and avoids going stale. Also, it has the benefit of automatically creating a link to the ..kernel-doc:: comment anywhere that "enum bpf_reg_liveness" is written in the Documentation subtree.

Thank you for pointing to this capability. I'd like to stick to the current variant because I don't need full definitions of struct bpf_reg_state and others. The only complete definition I want to describe is enum bpf_reg_liveness, for all others just want to show the dependencies. I just tried mixing .. kernel-doc:: for the enum, and code block for the structs but it looks awkward in the final HTML.

Quoted 122 lines
Quoted 36 lines
Documentation/bpf/verifier.rst +35 -0
+
+  struct bpf_reg_state {
+ 	...
+	struct bpf_reg_state *parent;
+ 	...
+	enum bpf_reg_liveness live;
+ 	...
+  };
+
+  struct bpf_stack_state {
+	struct bpf_reg_state spilled_ptr;
+	...
+  };
+
+  struct bpf_func_state {
+	struct bpf_reg_state regs[MAX_BPF_REG];
+        ...
+	struct bpf_stack_state *stack;
+  }
+  
+  struct bpf_verifier_state {
+	struct bpf_func_state *frame[MAX_CALL_FRAMES];
+	struct bpf_verifier_state *parent;
+        ...
+  }
+
+* ``REG_LIVE_NONE`` is an initial value assigned to ``->live`` fields upon new
+  verifier state creation;
+
+* ``REG_LIVE_WRITTEN`` means that the value of the register (or stack slot) is
+  defined by some instruction "executed" within verifier state;
+
+* ``REG_LIVE_READ{32,64}`` means that the value of the register (or stack slot)
+  is read by some instruction "executed" within verifier state;
+

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 407

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+* ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid
+  processing same verifier state multiple times and for some sanity checks;
+
+* ``->live`` field values are formed by combining ``enum bpf_reg_liveness``
+  values using bitwise or.
+
+Register parentage chains
+~~~~~~~~~~~~~~~~~~~~~~~~~
+  
+In order to propagate information between parent and child states register

Suggestion:

s/parent and child states register parentage chain/
parent and child states, a *register parentage chain*

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 409

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+parentage chain is established. Each register or stack slot is linked to a
+corresponding register or stack slot in it's parent state via a ``->parent``

s/it's/its

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 410

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+pointer. This link is established upon state creation in function

suggestion: I think you can remove the word 'function'.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 416

Quoted 6 lines
Documentation/bpf/verifier.rst +6 -0
+``is_state_visited()`` and is never changed.
+
+The rules for correspondence between registers / stack slots are as follows:
+
+* For current stack frame registers and stack slots of the new state are linked
+  to the registers and stack slots of the parent state with the same indices.

s/For current stack frame registers/For the current stack frame, registers

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 420

Quoted 4 lines
Documentation/bpf/verifier.rst +4 -0
+
+* For outer stack frames only caller saved registers (r6-r9) and stack slots are
+  linked to the registers and stack slots of the parent state with the same
+  indices.

s/For the outer stack frames only/For the outer stack frames, only

Quoted 44 lines
Documentation/bpf/verifier.rst +44 -0
+
+This could be illustrated by the following diagram (arrows stand for
+``->parent`` pointers)::
+
+      ...                    ; Frame #0, some instructions
+  --- checkpoint #0 ---
+  1 : r6 = 42                ; Frame #0
+  --- checkpoint #1 ---
+  2 : call foo()             ; Frame #0
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #2 ---
+      ...                    ; Frame #1, instructions from foo()
+  --- checkpoint #3 ---
+      exit                   ; Frame #1, return from foo()
+  3 : r1 = r6                ; Frame #0  <- current state
+  
+             +--------------------------+--------------------------+ 
+             |         Frame #0         |         Frame #1         |
+  Checkpoint +--------------------------+--------------------------+
+  #0         | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+                           
+                ^       ^       ^
+                |       |       |          
+  Checkpoint +--------------------------+                           
+  #1         | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+
+                        ^       ^         nil     nil     nil 
+                        |       |          |       |       |          
+  Checkpoint +--------------------------+--------------------------+
+  #2         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^          ^       ^       ^  
+                        |       |          |       |       |
+  Checkpoint +--------------------------+--------------------------+
+  #3         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^
+                        |       |          
+  Current    +--------------------------+                           
+  state      | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+
+                        \           
+                          r6 read mark is propagated via
+                          these links all the way up to
Quoted 9 lines

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 465

Quoted 1 line
Documentation/bpf/verifier.rst +1 -0
+                          checkpoint #1.

IMO this illustration is kind of confusing as shown, relative to the descriptions of current / outer above. 'Frame #1' is potentially in a different function / subprog, correct? So it seems kind of confusing to see it propagating registers from checkpoint 3 -> checkpoint 2, etc. And it's propagating r0-r5. Similarly, it looks like 'Current state' isn't propagating r0-r5. I'm sure I'm misunderstanding something.

Good point. I reviewed the logic in __check_func_call() and it turns out I missed the actions performed by:
- init_func_state() which cuts all parent links for the newly created callee state.
- set_callee_state() which copies r1-r5 from caller byte-to-byte (thus including parent link).
I'll update the description and diagram to reflect this.

Quoted 127 lines

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 470

Quoted 5 lines
Documentation/bpf/verifier.rst +5 -0
+
+Liveness marks tracking
+~~~~~~~~~~~~~~~~~~~~~~~
+
+For each processed instruction verifier propagates information about reads up

s/processed instruction verifier/processed instruction, the verifier

Quoted 22 lines
Documentation/bpf/verifier.rst +22 -0
+the parentage chain and saves information about writes in the current state.
+The information about reads is propagated by function ``mark_reg_read()`` which
+could be summarized as follows::
+
+  mark_reg_read(struct bpf_reg_state *state):
+      parent = state->parent
+      while parent:
+          if parent->live & REG_LIVE_WRITTEN:
+              break
+          if parent->live & REG_LIVE_READ64:
+              break
+          parent->live |= REG_LIVE_READ64
+          state = parent
+          parent = state->parent
+
+Note: details about REG_LIVE_READ32 are omitted.
+
+Also note: the read marks are applied to the **parent** state while write marks
+are applied to the **current** state.
+
+Because stack writes could have different sizes ``REG_LIVE_WRITTEN`` marks are
+applied conservatively: stack slots are marked as written only if write size

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 502

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+corresponds to the size of the register, e.g. see function ``save_register_state()``.
+
+Consider the following example::
+
+  0: (*u64)(r10 - 8) = 0
+  --- checkpoint #0 ---
+  1: (*u32)(r10 - 8) = 1
+  2: r1 = (*u32)(r10 - 8)
+
+Because write size at instruction (1) is smaller than register size the write

s/write size/the write size

also

s/than register size the/than register size, the

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 504

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+mark will not be added to fp-8 slot when (1) is verified, thus the fp-8 read at
+instruction (2) would propagate read mark for fp-8 up to checkpoint #0.

s/is verified, thus/is verifier. Thus

also

s/would propagate read mark/would propagate the read mark

In general, this sentence explains mechanically why the write won't propagate (the write size is smaller than the register size), but I think it would be useful to explain why sizeof(write) < sizeof(reg) implies that it won't be propagated.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 506

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+
+Once ``BPF_EXIT`` instruction is reached function ``update_branch_counts()`` is

s/Once ``BPF_EXIT``/Once the ``BPF_EXIT``

also

s/is reached function/is reached,

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 508

Quoted 2 lines
Documentation/bpf/verifier.rst +2 -0
+called to update the ``->branches`` counter for each verifier state in a chain
+of parent verifier states. When ``->branches`` counter reaches zero the verifier

s/When ``->branches`` counter reaches zero/
When the ``branches`` counter reaches zero,

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 515

Quoted 7 lines
Documentation/bpf/verifier.rst +7 -0
+state becomes a valid entry in a set of cached verifier states.
+
+Each entry of the verifier states cache is post-processed by a function
+``clean_live_states()``. This function marks all registers and stack slots
+without ``REG_LIVE_READ{32,64}`` marks as ``NOT_INIT`` or ``STACK_INVALID``.
+Registers/stack slots marked in this way are ignored in function ``stacksafe()``
+called from ``states_equal()`` when state cache entry is considered for

s/when state cache entry/when a state cache entry

Quoted 14 lines
Documentation/bpf/verifier.rst +14 -0
+equivalence with a current state.
+
+Now it is possible to explain how the example from the beginning of the section
+works::
+
+  0: call bpf_get_prandom_u32()
+  1: r1 = 0
+  2: if r0 == 0 goto +1
+  3: r0 = 1
+  --- checkpoint[0] ---
+  4: r0 = r1
+  5: exit
+
+* At instruction #2 branching point is reached and state ``{ r0 == 0, r1 == 0, pc == 4 }``

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 539

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+  is pushed to states processing queue (pc stands for program counter).
+  
+* At instruction #4:
+  
+  * ``checkpoint[0]`` states cache entry is created: ``{ r0 == 1, r1 == 0, pc == 4 }``;
+  * ``checkpoint[0].r0`` is marked as written;
+  * ``checkpoint[0].r1`` is marked as read;
+
+* At instruction #5 exit is reached and ``checkpoint[0]`` can now be processed
+  by ``clean_live_states()``, after this processing ``checkpoint[0].r0`` has a

s/by ``clean_live_states()``, after/by ``clean_live_states()``. After

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 550

Quoted 11 lines
Documentation/bpf/verifier.rst +11 -0
+  read mark and all other registers and stack slots are marked as ``NOT_INIT``
+  or ``STACK_INVALID``
+  
+* The state ``{ r0 == 0, r1 == 0, pc == 4 }`` is popped from the states queue
+  and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states
+  are considered equivalent.
+
+Read marks propagation for cache hits
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Another important point is handling of read marks when a previously verified

s/is handling of/is the handling of

Quoted 8 lines

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 553

Quoted 3 lines
Documentation/bpf/verifier.rst +3 -0
+state is found in the states cache. All read marks present on registers and
+stack slots of the cached state must be propagated over the parentage chain of
+the current state. Function ``propagate_liveness()`` handles this case.

Suggestion: Consider expanding the sentence to include why it's necessary to propagate like this. You explain below after the diagram, but it might be helpful to clarify here so the reader has some context when reading over the diagram.

Well, I figured that the diagram below is the simplest way to describe why this logic is necessary. I'll try to come up with some condensed description as you suggest.

Quoted 38 lines
Quoted 38 lines
Documentation/bpf/verifier.rst +31 -0
+
+For example, consider the following state parentage chain (S is a
+starting state, A-E are derived states, -> arrows show which state is
+derived from which)::
+
+                      r1 read
+               <-------------                    A[r1] == 0
+                    +---+                        C[r1] == 0
+      S ---> A ---> | B | ---> exit              E[r1] == 1
+      |             |   |
+      ` ---> C ---> | D |
+      |             +---+
+      ` ---> E        
+                      ^
+             ^        |___   suppose all these
+             |             states are at insn #Y
+      suppose all these
+    states are at insn #X
+
+* Chain of states ``S -> A -> B -> exit`` is verified first.
+
+* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is
+  propagated up to state ``A``.
+
+* When chain of states ``C -> D`` is verified the state ``D`` turns out to be
+  equivalent to state ``B``.
+
+* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state
+  ``C`` might get mistakenly marked as equivalent to state ``E`` even though
+  values for register ``r1`` differ between ``C`` and ``E``.
+
 Understanding eBPF verifier messages
 ====================================
 
Signature · 1 line
2.39.0
#4 lore raw
In reply to Eduard Zingerman
Quoted 6 lines · Eduard Zingerman
Documentation/bpf/verifier.rst +6 -0
+  
+             +--------------------------+--------------------------+ 
+             |         Frame #0         |         Frame #1         |
+  Checkpoint +--------------------------+--------------------------+
+  #0         | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+                           

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 451

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+                ^       ^       ^
+                |       |       |          
+  Checkpoint +--------------------------+                           
+  #1         | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+
+                        ^       ^         nil     nil     nil 
+                        |       |          |       |       |          
+  Checkpoint +--------------------------+--------------------------+
+  #2         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+

Looks like you already realized that frame1 r1-r5 needs to be connected to frame0 r1-r5. Otherwise when subprog (frame1) reads r1 the read mark won't be propagated into checkpoint#1 r1 frame0 and r1 in frame0 will be trimmed incorrectly.

Quoted 15 lines
Documentation/bpf/verifier.rst +15 -0
+                        ^       ^          ^       ^       ^  
+                        |       |          |       |       |
+  Checkpoint +--------------------------+--------------------------+
+  #3         | r0-r5 | r6-r9 | fp-8 ... | r0-r5 | r6-r9 | fp-8 ... |
+             +--------------------------+--------------------------+
+                        ^       ^
+                        |       |          
+  Current    +--------------------------+                           
+  state      | r0-r5 | r6-r9 | fp-8 ... |                           
+             +--------------------------+
+                        \           
+                          r6 read mark is propagated via
+                          these links all the way up to
+                          checkpoint #1.
+

...

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+Read marks propagation for cache hits
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Another important point is handling of read marks when a previously verified
+state is found in the states cache. All read marks present on registers and
+stack slots of the cached state must be propagated over the parentage chain of
+the current state. Function ``propagate_liveness()`` handles this case.
+
+For example, consider the following state parentage chain (S is a
+starting state, A-E are derived states, -> arrows show which state is

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 566

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+derived from which)::
+
+                      r1 read
+               <-------------                    A[r1] == 0
+                    +---+                        C[r1] == 0
+      S ---> A ---> | B | ---> exit              E[r1] == 1
+      |             |   |
+      ` ---> C ---> | D |
+      |             +---+
+      ` ---> E        

The box around B and D is confusing.
The description doesn't explain what the box is for. If the box is removed the description stays as-is, no?

Quoted 7 lines
Documentation/bpf/verifier.rst +7 -0
+                      ^
+             ^        |___   suppose all these
+             |             states are at insn #Y
+      suppose all these
+    states are at insn #X
+
+* Chain of states ``S -> A -> B -> exit`` is verified first.

Documentation/bpf/verifier.rst Pruning considers not only the registers but also the stack (and any spilled · line 583

Quoted 10 lines
Documentation/bpf/verifier.rst +10 -0
+
+* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is
+  propagated up to state ``A``.
+
+* When chain of states ``C -> D`` is verified the state ``D`` turns out to be
+  equivalent to state ``B``.
+
+* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state
+  ``C`` might get mistakenly marked as equivalent to state ``E`` even though
+  values for register ``r1`` differ between ``C`` and ``E``.

Overall it's awesome.
Please cc Edward Cree <[email protected]> in the respin.