)]}'
{
  "commit": "96a30e469ca1d2b8cc7811b40911f8614b558241",
  "tree": "b47affc76e77e06914d0d1895e7d8149e054daf7",
  "parents": [
    "4ff04abf9d5bc33d33c7a799887517619188b068"
  ],
  "author": {
    "name": "Andrii Nakryiko",
    "email": "andrii@kernel.org",
    "time": "Thu Nov 14 16:13:03 2024 -0800"
  },
  "committer": {
    "name": "Alexei Starovoitov",
    "email": "ast@kernel.org",
    "time": "Fri Nov 15 10:20:47 2024 -0800"
  },
  "message": "bpf: use common instruction history across all states\n\nInstead of allocating and copying instruction history each time we\nenqueue child verifier state, switch to a model where we use one common\ndynamically sized array of instruction history entries across all states.\n\nThe key observation for proving this is correct is that instruction\nhistory is only relevant while state is active, which means it either is\na current state (and thus we are actively modifying instruction history\nand no other state can interfere with us) or we are checkpointed state\nwith some children still active (either enqueued or being current).\n\nIn the latter case our portion of instruction history is finalized and\nwon\u0027t change or grow, so as long as we keep it immutable until the state\nis finalized, we are good.\n\nNow, when state is finalized and is put into state hash for potentially\nfuture pruning lookups, instruction history is not used anymore. This is\nbecause instruction history is only used by precision marking logic, and\nwe never modify precision markings for finalized states.\n\nSo, instead of each state having its own small instruction history, we\nkeep a global dynamically-sized instruction history, where each state in\ncurrent DFS path from root to active state remembers its portion of\ninstruction history. Current state can append to this history, but\ncannot modify any of its parent histories.\n\nAsync callback state enqueueing, while logically detached from parent\nstate, still is part of verification backtracking tree, so has to follow\nthe same schema as normal state checkpoints.\n\nBecause the insn_hist array can be grown through realloc, states don\u0027t\nkeep pointers, they instead maintain two indices, [start, end), into\nglobal instruction history array. End is exclusive index, so\n`start \u003d\u003d end` means there is no relevant instruction history.\n\nThis eliminates a lot of allocations and minimizes overall memory usage.\n\nFor instance, running a worst-case test from [0] (but without the\nheuristics-based fix [1]), it took 12.5 minutes until we get -ENOMEM.\nWith the changes in this patch the whole test succeeds in 10 minutes\n(very slow, so heuristics from [1] is important, of course).\n\nTo further validate correctness, veristat-based comparison was performed for\nMeta production BPF objects and BPF selftests objects. In both cases there\nwere no differences *at all* in terms of verdict or instruction and state\ncounts, providing a good confidence in the change.\n\nHaving this low-memory-overhead solution of keeping dynamic\nper-instruction history cheaply opens up some new possibilities, like\nkeeping extra information for literally every single validated\ninstruction. This will be used for simplifying precision backpropagation\nlogic in follow up patches.\n\n  [0] https://lore.kernel.org/bpf/20241029172641.1042523-2-eddyz87@gmail.com/\n  [1] https://lore.kernel.org/bpf/20241029172641.1042523-1-eddyz87@gmail.com/\n\nAcked-by: Eduard Zingerman \u003ceddyz87@gmail.com\u003e\nSigned-off-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nLink: https://lore.kernel.org/r/20241115001303.277272-1-andrii@kernel.org\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "6b7c916291761dd9e422d765046efc6e93cb5ebe",
      "old_mode": 33188,
      "old_path": "include/linux/bpf_verifier.h",
      "new_id": "f4290c179bee0ad206a6be1dc4e18c89fb3209c7",
      "new_mode": 33188,
      "new_path": "include/linux/bpf_verifier.h"
    },
    {
      "type": "modify",
      "old_id": "09f7fa635f6778d97ca1a729e5cc170b2d2367be",
      "old_mode": 33188,
      "old_path": "kernel/bpf/verifier.c",
      "new_id": "1c4ebb326785d412bd5fc729b31fc2df348bec7a",
      "new_mode": 33188,
      "new_path": "kernel/bpf/verifier.c"
    }
  ]
}