• Kumar Kartikeya Dwivedi's avatar
    bpf: Introduce single ownership BPF linked list API · 8cab76ec
    Kumar Kartikeya Dwivedi authored
    Add a linked list API for use in BPF programs, where it expects
    protection from the bpf_spin_lock in the same allocation as the
    bpf_list_head. For now, only one bpf_spin_lock can be present hence that
    is assumed to be the one protecting the bpf_list_head.
    
    The following functions are added to kick things off:
    
    // Add node to beginning of list
    void bpf_list_push_front(struct bpf_list_head *head, struct bpf_list_node *node);
    
    // Add node to end of list
    void bpf_list_push_back(struct bpf_list_head *head, struct bpf_list_node *node);
    
    // Remove node at beginning of list and return it
    struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head);
    
    // Remove node at end of list and return it
    struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head);
    
    The lock protecting the bpf_list_head needs to be taken for all
    operations. The verifier ensures that the lock that needs to be taken is
    always held, and only the correct lock is taken for these operations.
    These checks are made statically by relying on the reg->id preserved for
    registers pointing into regions having both bpf_spin_lock and the
    objects protected by it. The comment over check_reg_allocation_locked in
    this change describes the logic in detail.
    
    Note that bpf_list_push_front and bpf_list_push_back are meant to
    consume the object containing the node in the 1st argument, however that
    specific mechanism is intended to not release the ref_obj_id directly
    until the bpf_spin_unlock is called. In this commit, nothing is done,
    but the next commit will be introducing logic to handle this case, so it
    has been left as is for now.
    
    bpf_list_pop_front and bpf_list_pop_back delete the first or last item
    of the list respectively, and return pointer to the element at the
    list_node offset. The user can then use container_of style macro to get
    the actual entry type. The verifier however statically knows the actual
    type, so the safety properties are still preserved.
    
    With these additions, programs can now manage their own linked lists and
    store their objects in them.
    Signed-off-by: default avatarKumar Kartikeya Dwivedi <memxor@gmail.com>
    Link: https://lore.kernel.org/r/20221118015614.2013203-17-memxor@gmail.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    8cab76ec
bpf_experimental.h 2.07 KB