• Dave Marchevsky's avatar
    selftests/bpf: Add rbtree selftests · 215249f6
    Dave Marchevsky authored
    This patch adds selftests exercising the logic changed/added in the
    previous patches in the series. A variety of successful and unsuccessful
    rbtree usages are validated:
    
    Success:
      * Add some nodes, let map_value bpf_rbtree_root destructor clean them
        up
      * Add some nodes, remove one using the non-owning ref leftover by
        successful rbtree_add() call
      * Add some nodes, remove one using the non-owning ref returned by
        rbtree_first() call
    
    Failure:
      * BTF where bpf_rb_root owns bpf_list_node should fail to load
      * BTF where node of type X is added to tree containing nodes of type Y
        should fail to load
      * No calling rbtree api functions in 'less' callback for rbtree_add
      * No releasing lock in 'less' callback for rbtree_add
      * No removing a node which hasn't been added to any tree
      * No adding a node which has already been added to a tree
      * No escaping of non-owning references past their lock's
        critical section
      * No escaping of non-owning references past other invalidation points
        (rbtree_remove)
    
    These tests mostly focus on rbtree-specific additions, but some of the
    failure cases revalidate scenarios common to both linked_list and rbtree
    which are covered in the former's tests. Better to be a bit redundant in
    case linked_list and rbtree semantics deviate over time.
    Signed-off-by: default avatarDave Marchevsky <davemarchevsky@fb.com>
    Link: https://lore.kernel.org/r/20230214004017.2534011-8-davemarchevsky@fb.comSigned-off-by: default avatarAlexei Starovoitov <ast@kernel.org>
    215249f6
rbtree.c 3.25 KB