1// SPDX-License-Identifier: GPL-2.0-only
  2// Copyright (C) 2022-2023 Isovalent, Inc.
  3digraph {
  4  node [colorscheme=accent4,style=filled] # Apply colorscheme to all nodes
  5  graph [splines=ortho, nodesep=1]
  6
  7  subgraph cluster_key {
  8    label = "Key\n(locks held during operation)";
  9    rankdir = TB;
 10
 11    remote_lock [shape=rectangle,fillcolor=4,label="remote CPU LRU lock"]
 12    hash_lock [shape=rectangle,fillcolor=3,label="hashtab lock"]
 13    lru_lock [shape=rectangle,fillcolor=2,label="LRU lock"]
 14    local_lock [shape=rectangle,fillcolor=1,label="local CPU LRU lock"]
 15    no_lock [shape=rectangle,label="no locks held"]
 16  }
 17
 18  begin [shape=oval,label="begin\nbpf_map_update()"]
 19
 20  // Nodes below with an 'fn_' prefix are roughly labeled by the C function
 21  // names that initiate the corresponding logic in kernel/bpf/bpf_lru_list.c.
 22  // Number suffixes and errno suffixes handle subsections of the corresponding
 23  // logic in the function as of the writing of this dot.
 24
 25  // cf. __local_list_pop_free() / bpf_percpu_lru_pop_free()
 26  local_freelist_check [shape=diamond,fillcolor=1,
 27    label="Local freelist\nnode available?"];
 28  use_local_node [shape=rectangle,
 29    label="Use node owned\nby this CPU"]
 30
 31  // cf. bpf_lru_pop_free()
 32  common_lru_check [shape=diamond,
 33    label="Map created with\ncommon LRU?\n(!BPF_F_NO_COMMON_LRU)"];
 34
 35  fn_bpf_lru_list_pop_free_to_local [shape=rectangle,fillcolor=2,
 36    label="Flush local pending,
 37    Rotate Global list, move
 38    LOCAL_FREE_TARGET
 39    from global -> local"]
 40  // Also corresponds to:
 41  // fn__local_list_flush()
 42  // fn_bpf_lru_list_rotate()
 43  fn___bpf_lru_node_move_to_free[shape=diamond,fillcolor=2,
 44    label="Able to free\nLOCAL_FREE_TARGET\nnodes?"]
 45
 46  fn___bpf_lru_list_shrink_inactive [shape=rectangle,fillcolor=3,
 47    label="Shrink inactive list
 48      up to remaining
 49      LOCAL_FREE_TARGET
 50      (global LRU -> local)"]
 51  fn___bpf_lru_list_shrink [shape=diamond,fillcolor=2,
 52    label="> 0 entries in\nlocal free list?"]
 53  fn___bpf_lru_list_shrink2 [shape=rectangle,fillcolor=2,
 54    label="Steal one node from
 55      inactive, or if empty,
 56      from active global list"]
 57  fn___bpf_lru_list_shrink3 [shape=rectangle,fillcolor=3,
 58    label="Try to remove\nnode from hashtab"]
 59
 60  local_freelist_check2 [shape=diamond,label="Htab removal\nsuccessful?"]
 61  common_lru_check2 [shape=diamond,
 62    label="Map created with\ncommon LRU?\n(!BPF_F_NO_COMMON_LRU)"];
 63
 64  subgraph cluster_remote_lock {
 65    label = "Iterate through CPUs\n(start from current)";
 66    style = dashed;
 67    rankdir=LR;
 68
 69    local_freelist_check5 [shape=diamond,fillcolor=4,
 70      label="Steal a node from\nper-cpu freelist?"]
 71    local_freelist_check6 [shape=rectangle,fillcolor=4,
 72      label="Steal a node from
 73        (1) Unreferenced pending, or
 74        (2) Any pending node"]
 75    local_freelist_check7 [shape=rectangle,fillcolor=3,
 76      label="Try to remove\nnode from hashtab"]
 77    fn_htab_lru_map_update_elem [shape=diamond,
 78      label="Stole node\nfrom remote\nCPU?"]
 79    fn_htab_lru_map_update_elem2 [shape=diamond,label="Iterated\nall CPUs?"]
 80    // Also corresponds to:
 81    // use_local_node()
 82    // fn__local_list_pop_pending()
 83  }
 84
 85  fn_bpf_lru_list_pop_free_to_local2 [shape=rectangle,
 86    label="Use node that was\nnot recently referenced"]
 87  local_freelist_check4 [shape=rectangle,
 88    label="Use node that was\nactively referenced\nin global list"]
 89  fn_htab_lru_map_update_elem_ENOMEM [shape=oval,label="return -ENOMEM"]
 90  fn_htab_lru_map_update_elem3 [shape=rectangle,
 91    label="Use node that was\nactively referenced\nin (another?) CPU's cache"]
 92  fn_htab_lru_map_update_elem4 [shape=rectangle,fillcolor=3,
 93    label="Update hashmap\nwith new element"]
 94  fn_htab_lru_map_update_elem5 [shape=oval,label="return 0"]
 95  fn_htab_lru_map_update_elem_EBUSY [shape=oval,label="return -EBUSY"]
 96  fn_htab_lru_map_update_elem_EEXIST [shape=oval,label="return -EEXIST"]
 97  fn_htab_lru_map_update_elem_ENOENT [shape=oval,label="return -ENOENT"]
 98
 99  begin -> local_freelist_check
100  local_freelist_check -> use_local_node [xlabel="Y"]
101  local_freelist_check -> common_lru_check [xlabel="N"]
102  common_lru_check -> fn_bpf_lru_list_pop_free_to_local [xlabel="Y"]
103  common_lru_check -> fn___bpf_lru_list_shrink_inactive [xlabel="N"]
104  fn_bpf_lru_list_pop_free_to_local -> fn___bpf_lru_node_move_to_free
105  fn___bpf_lru_node_move_to_free ->
106    fn_bpf_lru_list_pop_free_to_local2 [xlabel="Y"]
107  fn___bpf_lru_node_move_to_free ->
108    fn___bpf_lru_list_shrink_inactive [xlabel="N"]
109  fn___bpf_lru_list_shrink_inactive -> fn___bpf_lru_list_shrink
110  fn___bpf_lru_list_shrink -> fn_bpf_lru_list_pop_free_to_local2 [xlabel = "Y"]
111  fn___bpf_lru_list_shrink -> fn___bpf_lru_list_shrink2 [xlabel="N"]
112  fn___bpf_lru_list_shrink2 -> fn___bpf_lru_list_shrink3
113  fn___bpf_lru_list_shrink3 -> local_freelist_check2
114  local_freelist_check2 -> local_freelist_check4 [xlabel = "Y"]
115  local_freelist_check2 -> common_lru_check2 [xlabel = "N"]
116  common_lru_check2 -> local_freelist_check5 [xlabel = "Y"]
117  common_lru_check2 -> fn_htab_lru_map_update_elem_ENOMEM [xlabel = "N"]
118  local_freelist_check5 -> fn_htab_lru_map_update_elem [xlabel = "Y"]
119  local_freelist_check5 -> local_freelist_check6 [xlabel = "N"]
120  local_freelist_check6 -> local_freelist_check7
121  local_freelist_check7 -> fn_htab_lru_map_update_elem
122
123  fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem3 [xlabel = "Y"]
124  fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem2  [xlabel = "N"]
125  fn_htab_lru_map_update_elem2 ->
126    fn_htab_lru_map_update_elem_ENOMEM [xlabel = "Y"]
127  fn_htab_lru_map_update_elem2 -> local_freelist_check5 [xlabel = "N"]
128  fn_htab_lru_map_update_elem3 -> fn_htab_lru_map_update_elem4
129
130  use_local_node -> fn_htab_lru_map_update_elem4
131  fn_bpf_lru_list_pop_free_to_local2 -> fn_htab_lru_map_update_elem4
132  local_freelist_check4 -> fn_htab_lru_map_update_elem4
133
134  fn_htab_lru_map_update_elem4 -> fn_htab_lru_map_update_elem5 [headlabel="Success"]
135  fn_htab_lru_map_update_elem4 ->
136    fn_htab_lru_map_update_elem_EBUSY [xlabel="Hashtab lock failed"]
137  fn_htab_lru_map_update_elem4 ->
138    fn_htab_lru_map_update_elem_EEXIST [xlabel="BPF_EXIST set and\nkey already exists"]
139  fn_htab_lru_map_update_elem4 ->
140    fn_htab_lru_map_update_elem_ENOENT [headlabel="BPF_NOEXIST set\nand no such entry"]
141
142  // Create invisible pad nodes to line up various nodes
143  pad0 [style=invis]
144  pad1 [style=invis]
145  pad2 [style=invis]
146  pad3 [style=invis]
147  pad4 [style=invis]
148
149  // Line up the key with the top of the graph
150  no_lock -> local_lock [style=invis]
151  local_lock -> lru_lock [style=invis]
152  lru_lock -> hash_lock [style=invis]
153  hash_lock -> remote_lock [style=invis]
154  remote_lock -> local_freelist_check5 [style=invis]
155  remote_lock -> fn___bpf_lru_list_shrink [style=invis]
156
157  // Line up return code nodes at the bottom of the graph
158  fn_htab_lru_map_update_elem -> pad0 [style=invis]
159  pad0 -> pad1 [style=invis]
160  pad1 -> pad2 [style=invis]
161  //pad2-> fn_htab_lru_map_update_elem_ENOMEM [style=invis]
162  fn_htab_lru_map_update_elem4 -> pad3 [style=invis]
163  pad3 -> fn_htab_lru_map_update_elem5  [style=invis]
164  pad3 -> fn_htab_lru_map_update_elem_EBUSY  [style=invis]
165  pad3 -> fn_htab_lru_map_update_elem_EEXIST  [style=invis]
166  pad3 -> fn_htab_lru_map_update_elem_ENOENT  [style=invis]
167
168  // Reduce diagram width by forcing some nodes to appear above others
169  local_freelist_check4 -> fn_htab_lru_map_update_elem3 [style=invis]
170  common_lru_check2 -> pad4 [style=invis]
171  pad4 -> local_freelist_check5 [style=invis]
172}