1. 21 Jan, 2018 25 commits
  2. 20 Jan, 2018 12 commits
  3. 19 Jan, 2018 3 commits
    • Daniel Borkmann's avatar
      Merge branch 'bpf-lpm-get-next-key' · 05526361
      Daniel Borkmann authored
      Yonghong Song says:
      
      ====================
      This patch set implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
      This command is really useful for key enumeration, and for key deletion
      if what keys in the trie are unknown.
      
      Patch #1 implements the functionality in the kernel and patch #2
      adds a test case in tools/testing/selftests/bpf.
      ====================
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      05526361
    • Yonghong Song's avatar
      tools/bpf: add a testcase for MAP_GET_NEXT_KEY command of LPM_TRIE map · 8c417dc1
      Yonghong Song authored
      A test case is added in tools/testing/selftests/bpf/test_lpm_map.c
      for MAP_GET_NEXT_KEY command. A four node trie, which
      is described in kernel/bpf/lpm_trie.c, is built and the
      MAP_GET_NEXT_KEY results are checked.
      Signed-off-by: default avatarYonghong Song <yhs@fb.com>
      Signed-off-by: default avatarDaniel Borkmann <daniel@iogearbox.net>
      8c417dc1
    • 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