bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map
authorYonghong Song <yhs@fb.com>
Thu, 18 Jan 2018 23:08:50 +0000 (15:08 -0800)
committerDaniel Borkmann <daniel@iogearbox.net>
Fri, 19 Jan 2018 22:26:41 +0000 (23:26 +0100)
commitb471f2f1de8b816f1e799b80aa92588f3566e4bd
tree0ba426508fa8d1365460989daf658681eaf47f8e
parentb7bcc0bbb8acb640258bb451f1f9391737da48b1
bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map

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: Yonghong Song <yhs@fb.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
kernel/bpf/lpm_trie.c