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