Based on kernel version 6.8
. Page generated on 2024-03-11 21:26 EST
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | // 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. // cf. __local_list_pop_free() / bpf_percpu_lru_pop_free() local_freelist_check [shape=diamond,fillcolor=1, label="Local freelist\nnode available?"]; 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 LOCAL_FREE_TARGET 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\nLOCAL_FREE_TARGET\nnodes?"] fn___bpf_lru_list_shrink_inactive [shape=rectangle,fillcolor=3, label="Shrink inactive list up to remaining LOCAL_FREE_TARGET (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() } 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 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"] 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 fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem3 [xlabel = "Y"] 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 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] } |