BPF LRU 해시 맵 갱신 상태 전이

로컬·공통·원격 CPU LRU에서 갱신 노드를 확보하는 경로

이 Graphviz DOT 원문은 `bpf_map_update()`가 BPF LRU 해시 맵에 새 원소를 넣을 때 사용할 노드를 확보하고 해시 테이블을 갱신하는 흐름을 나타냅니다. 먼저 현재 CPU의 로컬 freelist를 확인하고, 노드가 없으면 공통 LRU 여부와 전역 목록 회수 결과에 따라 inactive·active 목록 또는 다른 CPU의 캐시까지 탐색합니다.

`fn_` 접두사가 붙은 노드는 `kernel/bpf/bpf_lru_list.c`에서 해당 논리를 시작하는 C 함수 이름을 대략 반영합니다. 숫자 접미사와 `ENOMEM`, `EBUSY`, `EEXIST`, `ENOENT` 접미사는 DOT 작성 당시 한 함수 안의 서로 다른 하위 구간과 반환 지점을 구분하기 위한 그래프 식별자입니다.

색은 노드 작업 중 보유하는 잠금을 뜻합니다. `accent4` 색상 1은 local CPU LRU lock, 2는 LRU lock, 3은 hashtab lock, 4는 remote CPU LRU lock이며 채움색을 따로 지정하지 않은 기능 노드는 잠금을 보유하지 않는 경로로 읽습니다. 점선 CPU 클러스터는 현재 CPU부터 모든 CPU를 순회하는 반복 영역입니다.

아래 코드는 Linux v6.18.37 원문 1-172줄 전체입니다. 표시 안정성을 위해 탭만 여덟 칸으로 정규화했으며 노드 ID, C 함수명, label, Y/N·errno 분기, 색상, 클러스터, 비가시 pad와 간선, 줄 순서는 변경하지 않았습니다.

// 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
    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()
  }

  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]
}