Skip to content
  • Martin KaFai Lau's avatar
    bpf: LRU List · 3a08c2fd
    Martin KaFai Lau authored
    
    
    Introduce bpf_lru_list which will provide LRU capability to
    the bpf_htab in the later patch.
    
    * General Thoughts:
    1. Target use case.  Read is more often than update.
       (i.e. bpf_lookup_elem() is more often than bpf_update_elem()).
       If bpf_prog does a bpf_lookup_elem() first and then an in-place
       update, it still counts as a read operation to the LRU list concern.
    2. It may be useful to think of it as a LRU cache
    3. Optimize the read case
       3.1 No lock in read case
       3.2 The LRU maintenance is only done during bpf_update_elem()
    4. If there is a percpu LRU list, it will lose the system-wise LRU
       property.  A completely isolated percpu LRU list has the best
       performance but the memory utilization is not ideal considering
       the work load may be imbalance.
    5. Hence, this patch starts the LRU implementation with a global LRU
       list with batched operations before accessing the global LRU list.
       As a LRU cache, #read >> #update/#insert operations, it will work well.
    6. There is a local list (for each cpu) which is named
       'struct bpf_lru_locallist'.  This local list is not used to sort
       the LRU property.  Instead, the local list is to batch enough
       operations before acquiring the lock of the global LRU list.  More
       details on this later.
    7. In the later patch, it allows a percpu LRU list by specifying a
       map-attribute for scalability reason and for use cases that need to
       prepare for the worst (and pathological) case like DoS attack.
       The percpu LRU list is completely isolated from each other and the
       LRU nodes (including free nodes) cannot be moved across the list.  The
       following description is for the global LRU list but mostly applicable
       to the percpu LRU list also.
    
    * Global LRU List:
    1. It has three sub-lists: active-list, inactive-list and free-list.
    2. The two list idea, active and inactive, is borrowed from the
       page cache.
    3. All nodes are pre-allocated and all sit at the free-list (of the
       global LRU list) at the beginning.  The pre-allocation reasoning
       is similar to the existing BPF_MAP_TYPE_HASH.  However,
       opting-out prealloc (BPF_F_NO_PREALLOC) is not supported in
       the LRU map.
    
    * Active/Inactive List (of the global LRU list):
    1. The active list, as its name says it, maintains the active set of
       the nodes.  We can think of it as the working set or more frequently
       accessed nodes.  The access frequency is approximated by a ref-bit.
       The ref-bit is set during the bpf_lookup_elem().
    2. The inactive list, as its name also says it, maintains a less
       active set of nodes.  They are the candidates to be removed
       from the bpf_htab when we are running out of free nodes.
    3. The ordering of these two lists is acting as a rough clock.
       The tail of the inactive list is the older nodes and
       should be released first if the bpf_htab needs free element.
    
    * Rotating the Active/Inactive List (of the global LRU list):
    1. It is the basic operation to maintain the LRU property of
       the global list.
    2. The active list is only rotated when the inactive list is running
       low.  This idea is similar to the current page cache.
       Inactive running low is currently defined as
       "# of inactive < # of active".
    3. The active list rotation always starts from the tail.  It moves
       node without ref-bit set to the head of the inactive list.
       It moves node with ref-bit set back to the head of the active
       list and then clears its ref-bit.
    4. The inactive rotation is pretty simply.
       It walks the inactive list and moves the nodes back to the head of
       active list if its ref-bit is set. The ref-bit is cleared after moving
       to the active list.
       If the node does not have ref-bit set, it just leave it as it is
       because it is already in the inactive list.
    
    * Shrinking the Inactive List (of the global LRU list):
    1. Shrinking is the operation to get free nodes when the bpf_htab is
       full.
    2. It usually only shrinks the inactive list to get free nodes.
    3. During shrinking, it will walk the inactive list from the tail,
       delete the nodes without ref-bit set from bpf_htab.
    4. If no free node found after step (3), it will forcefully get
       one node from the tail of inactive or active list.  Forcefully is
       in the sense that it ignores the ref-bit.
    
    * Local List:
    1. Each CPU has a 'struct bpf_lru_locallist'.  The purpose is to
       batch enough operations before acquiring the lock of the
       global LRU.
    2. A local list has two sub-lists, free-list and pending-list.
    3. During bpf_update_elem(), it will try to get from the free-list
       of (the current CPU local list).
    4. If the local free-list is empty, it will acquire from the
       global LRU list.  The global LRU list can either satisfy it
       by its global free-list or by shrinking the global inactive
       list.  Since we have acquired the global LRU list lock,
       it will try to get at most LOCAL_FREE_TARGET elements
       to the local free list.
    5. When a new element is added to the bpf_htab, it will
       first sit at the pending-list (of the local list) first.
       The pending-list will be flushed to the global LRU list
       when it needs to acquire free nodes from the global list
       next time.
    
    * Lock Consideration:
    The LRU list has a lock (lru_lock).  Each bucket of htab has a
    lock (buck_lock).  If both locks need to be acquired together,
    the lock order is always lru_lock -> buck_lock and this only
    happens in the bpf_lru_list.c logic.
    
    In hashtab.c, both locks are not acquired together (i.e. one
    lock is always released first before acquiring another lock).
    
    Signed-off-by: default avatarMartin KaFai Lau <kafai@fb.com>
    Acked-by: default avatarAlexei Starovoitov <ast@kernel.org>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    3a08c2fd