Documentation/bpf/map_lru_hash_update.dot

// SPDX-License-Identifier: GPL-2.0-only
// Copyright (C) 2022-2023 Isovalent, Inc.
digraph {
  node [colorscheme=accent4,style=filled] # Apply colorscheme to all nodes
  graph [splines=ortho, nodesep=1]

  subgraph cluster_key {
    label = "Key\n(locks held during operation)";
    rankdir = TB;

    remote_lock [shape=rectangle,fillcolor=4,label="remote CPU LRU lock"]
    hash_lock [shape=rectangle,fillcolor=3,label="hashtab lock"]
    lru_lock [shape=rectangle,fillcolor=2,label="LRU lock"]
    local_lock [shape=rectangle,fillcolor=1,label="local CPU LRU lock"]
    no_lock [shape=rectangle,label="no locks held"]
  }

  begin [shape=oval,label="begin\nbpf_map_update()"]

  // Nodes below with an 'fn_' prefix are roughly labeled by the C function
  // names that initiate the corresponding logic in kernel/bpf/bpf_lru_list.c.
  // Number suffixes and errno suffixes handle subsections of the corresponding
  // logic in the function as of the writing of this dot.
  //
  // All LRU locks are rqspinlock_t. Every acquire can fail (AA self-deadlock
  // or contention timeout); on failure the corresponding helper returns NULL
  // and the caller propagates -ENOMEM. The "rqspinlock acquire failed"
  // terminal below is reached via the dashed arrows from each acquire site.

  rqspinlock_failed [shape=rectangle,
    label="Any LRU rqspinlock\nacquire fails\n(AA or timeout)"]

  // cf. __local_list_pop_free() / bpf_percpu_lru_pop_free()
  local_freelist_check [shape=diamond,fillcolor=1,
    label="Local freelist\nnode available?\n(lockless free_llist)"];
  use_local_node [shape=rectangle,
    label="Use node owned\nby this CPU"]

  // cf. bpf_lru_pop_free()
  common_lru_check [shape=diamond,
    label="Map created with\ncommon LRU?\n(!BPF_F_NO_COMMON_LRU)"];

  fn_bpf_lru_list_pop_free_to_local [shape=rectangle,fillcolor=2,
    label="Flush local pending,
    Rotate Global list, move
    target_free
    from global -> local"]
  // Also corresponds to:
  // fn__local_list_flush()
  // fn_bpf_lru_list_rotate()
  fn___bpf_lru_node_move_to_free[shape=diamond,fillcolor=2,
    label="Able to free\ntarget_free\nnodes?"]

  fn___bpf_lru_list_shrink_inactive [shape=rectangle,fillcolor=3,
    label="Shrink inactive list
      up to remaining
      target_free
      (global LRU -> local)"]
  fn___bpf_lru_list_shrink [shape=diamond,fillcolor=2,
    label="> 0 entries in\nlocal free list?"]
  fn___bpf_lru_list_shrink2 [shape=rectangle,fillcolor=2,
    label="Steal one node from
      inactive, or if empty,
      from active global list"]
  fn___bpf_lru_list_shrink3 [shape=rectangle,fillcolor=3,
    label="Try to remove\nnode from hashtab"]

  local_freelist_check2 [shape=diamond,label="Htab removal\nsuccessful?"]
  common_lru_check2 [shape=diamond,
    label="Map created with\ncommon LRU?\n(!BPF_F_NO_COMMON_LRU)"];

  subgraph cluster_remote_lock {
    label = "Iterate through CPUs\n(start from current)";
    style = dashed;
    rankdir=LR;

    local_freelist_check5 [shape=diamond,fillcolor=4,
      label="Steal a node from\nper-cpu freelist?"]
    local_freelist_check6 [shape=rectangle,fillcolor=4,
      label="Steal a node from
        (1) Unreferenced pending, or
        (2) Any pending node"]
    local_freelist_check7 [shape=rectangle,fillcolor=3,
      label="Try to remove\nnode from hashtab"]
    fn_htab_lru_map_update_elem [shape=diamond,
      label="Stole node\nfrom remote\nCPU?"]
    fn_htab_lru_map_update_elem2 [shape=diamond,label="Iterated\nall CPUs?"]
    // Also corresponds to:
    // use_local_node()
    // fn__local_list_pop_pending()
  }

  // Post-steal: re-acquire local loc_l->lock to insert the stolen node into
  // the local pending list. If the acquire fails, the stolen node is published
  // to the lockless local free_llist so the next pop on this CPU picks it up
  // instead of orphaning it.
  post_steal_lock [shape=diamond,fillcolor=1,
    label="Acquire local\nloc_l->lock\nto add pending"]
  post_steal_to_free_llist [shape=rectangle,
    label="Publish stolen node to\nlocal free_llist (lockless)"]

  fn_bpf_lru_list_pop_free_to_local2 [shape=rectangle,
    label="Use node that was\nnot recently referenced"]
  local_freelist_check4 [shape=rectangle,
    label="Use node that was\nactively referenced\nin global list"]
  fn_htab_lru_map_update_elem_ENOMEM [shape=oval,label="return -ENOMEM"]
  fn_htab_lru_map_update_elem3 [shape=rectangle,
    label="Use node that was\nactively referenced\nin (another?) CPU's cache"]
  fn_htab_lru_map_update_elem4 [shape=rectangle,fillcolor=3,
    label="Update hashmap\nwith new element"]
  fn_htab_lru_map_update_elem5 [shape=oval,label="return 0"]
  fn_htab_lru_map_update_elem_EBUSY [shape=oval,label="return -EBUSY"]
  fn_htab_lru_map_update_elem_EEXIST [shape=oval,label="return -EEXIST"]
  fn_htab_lru_map_update_elem_ENOENT [shape=oval,label="return -ENOENT"]

  begin -> local_freelist_check
  // The initial per-CPU lock (loc_l->lock for common, l->lock for percpu) is
  // acquired before the local freelist check; rqspinlock failure here exits
  // directly to -ENOMEM (no recovery needed: nothing was removed yet).
  local_freelist_check -> rqspinlock_failed [style=dashed,
    xlabel="acquire fails"]
  local_freelist_check -> use_local_node [xlabel="Y"]
  local_freelist_check -> common_lru_check [xlabel="N"]
  common_lru_check -> fn_bpf_lru_list_pop_free_to_local [xlabel="Y"]
  common_lru_check -> fn___bpf_lru_list_shrink_inactive [xlabel="N"]
  // Global lru_list lock acquire failure in pop_free_to_local: skip refill,
  // fall through to the steal path. Not ENOMEM by itself.
  fn_bpf_lru_list_pop_free_to_local -> common_lru_check2 [style=dashed,
    xlabel="global lru_lock\nacquire fails"]
  fn_bpf_lru_list_pop_free_to_local -> fn___bpf_lru_node_move_to_free
  fn___bpf_lru_node_move_to_free ->
    fn_bpf_lru_list_pop_free_to_local2 [xlabel="Y"]
  fn___bpf_lru_node_move_to_free ->
    fn___bpf_lru_list_shrink_inactive [xlabel="N"]
  fn___bpf_lru_list_shrink_inactive -> fn___bpf_lru_list_shrink
  fn___bpf_lru_list_shrink -> fn_bpf_lru_list_pop_free_to_local2 [xlabel = "Y"]
  fn___bpf_lru_list_shrink -> fn___bpf_lru_list_shrink2 [xlabel="N"]
  fn___bpf_lru_list_shrink2 -> fn___bpf_lru_list_shrink3
  fn___bpf_lru_list_shrink3 -> local_freelist_check2
  local_freelist_check2 -> local_freelist_check4 [xlabel = "Y"]
  local_freelist_check2 -> common_lru_check2 [xlabel = "N"]
  common_lru_check2 -> local_freelist_check5 [xlabel = "Y"]
  common_lru_check2 -> fn_htab_lru_map_update_elem_ENOMEM [xlabel = "N"]
  local_freelist_check5 -> fn_htab_lru_map_update_elem [xlabel = "Y"]
  local_freelist_check5 -> local_freelist_check6 [xlabel = "N"]
  local_freelist_check6 -> local_freelist_check7
  local_freelist_check7 -> fn_htab_lru_map_update_elem

  // Steal-loop victim lock failure is silent: treat as "no node found here"
  // and continue to next CPU; same edge as the existing "N" path.
  local_freelist_check5 -> fn_htab_lru_map_update_elem2 [style=dashed,
    xlabel="victim's lock\nfails: skip"]
  // After a successful steal, re-acquire the local loc_l->lock. On failure
  // the stolen node is published to free_llist (recovered, not orphaned)
  // and the update returns -ENOMEM.
  fn_htab_lru_map_update_elem -> post_steal_lock [xlabel = "Y"]
  post_steal_lock -> fn_htab_lru_map_update_elem3 [xlabel = "OK"]
  post_steal_lock -> post_steal_to_free_llist [style=dashed,
    xlabel="loc_l->lock\nacquire fails"]
  post_steal_to_free_llist -> fn_htab_lru_map_update_elem_ENOMEM
  fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem2  [xlabel = "N"]
  fn_htab_lru_map_update_elem2 ->
    fn_htab_lru_map_update_elem_ENOMEM [xlabel = "Y"]
  fn_htab_lru_map_update_elem2 -> local_freelist_check5 [xlabel = "N"]
  fn_htab_lru_map_update_elem3 -> fn_htab_lru_map_update_elem4

  // Shared rqspinlock-failure terminal collapses to the same -ENOMEM exit.
  rqspinlock_failed -> fn_htab_lru_map_update_elem_ENOMEM

  use_local_node -> fn_htab_lru_map_update_elem4
  fn_bpf_lru_list_pop_free_to_local2 -> fn_htab_lru_map_update_elem4
  local_freelist_check4 -> fn_htab_lru_map_update_elem4

  fn_htab_lru_map_update_elem4 -> fn_htab_lru_map_update_elem5 [headlabel="Success"]
  fn_htab_lru_map_update_elem4 ->
    fn_htab_lru_map_update_elem_EBUSY [xlabel="Hashtab lock failed"]
  fn_htab_lru_map_update_elem4 ->
    fn_htab_lru_map_update_elem_EEXIST [xlabel="BPF_EXIST set and\nkey already exists"]
  fn_htab_lru_map_update_elem4 ->
    fn_htab_lru_map_update_elem_ENOENT [headlabel="BPF_NOEXIST set\nand no such entry"]

  // Create invisible pad nodes to line up various nodes
  pad0 [style=invis]
  pad1 [style=invis]
  pad2 [style=invis]
  pad3 [style=invis]
  pad4 [style=invis]

  // Line up the key with the top of the graph
  no_lock -> local_lock [style=invis]
  local_lock -> lru_lock [style=invis]
  lru_lock -> hash_lock [style=invis]
  hash_lock -> remote_lock [style=invis]
  remote_lock -> local_freelist_check5 [style=invis]
  remote_lock -> fn___bpf_lru_list_shrink [style=invis]

  // Line up return code nodes at the bottom of the graph
  fn_htab_lru_map_update_elem -> pad0 [style=invis]
  pad0 -> pad1 [style=invis]
  pad1 -> pad2 [style=invis]
  //pad2-> fn_htab_lru_map_update_elem_ENOMEM [style=invis]
  fn_htab_lru_map_update_elem4 -> pad3 [style=invis]
  pad3 -> fn_htab_lru_map_update_elem5  [style=invis]
  pad3 -> fn_htab_lru_map_update_elem_EBUSY  [style=invis]
  pad3 -> fn_htab_lru_map_update_elem_EEXIST  [style=invis]
  pad3 -> fn_htab_lru_map_update_elem_ENOENT  [style=invis]

  // Reduce diagram width by forcing some nodes to appear above others
  local_freelist_check4 -> fn_htab_lru_map_update_elem3 [style=invis]
  common_lru_check2 -> pad4 [style=invis]
  pad4 -> local_freelist_check5 [style=invis]
}