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