Documentation/bpf/map_lru_hash_update.dot

Source file repositories/reference/linux-study-clean/Documentation/bpf/map_lru_hash_update.dot

File Facts

System
Linux kernel
Corpus path
Documentation/bpf/map_lru_hash_update.dot
Extension
.dot
Size
9802 bytes
Lines
213
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: Documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

// 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.
  //
  // All LRU locks are rqspinlock_t. Every acquire can fail (AA self-deadlock
  // or contention timeout); on failure the corresponding helper returns NULL
  // and the caller propagates -ENOMEM. The "rqspinlock acquire failed"
  // terminal below is reached via the dashed arrows from each acquire site.

  rqspinlock_failed [shape=rectangle,
    label="Any LRU rqspinlock\nacquire fails\n(AA or timeout)"]

  // cf. __local_list_pop_free() / bpf_percpu_lru_pop_free()
  local_freelist_check [shape=diamond,fillcolor=1,
    label="Local freelist\nnode available?\n(lockless free_llist)"];
  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)"];

Annotation

Implementation Notes