Skip to content
  • Yonghong Song's avatar
    bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map · b471f2f1
    Yonghong Song authored
    
    
    Current LPM_TRIE map type does not implement MAP_GET_NEXT_KEY
    command. This command is handy when users want to enumerate
    keys. Otherwise, a different map which supports key
    enumeration may be required to store the keys. If the
    map data is sparse and all map data are to be deleted without
    closing file descriptor, using MAP_GET_NEXT_KEY to find
    all keys is much faster than enumerating all key space.
    
    This patch implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
    If user provided key pointer is NULL or the key does not have
    an exact match in the trie, the first key will be returned.
    Otherwise, the next key will be returned.
    
    In this implemenation, key enumeration follows a postorder
    traversal of internal trie. More specific keys
    will be returned first than less specific ones, given
    a sequence of MAP_GET_NEXT_KEY syscalls.
    
    Signed-off-by: default avatarYonghong Song <yhs@fb.com>
    Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
    b471f2f1