]> git.baikalelectronics.ru Git - kernel.git/commit
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)
commit93e5248d3ebbfd0a56b53dabd67c165ff91410a4
tree0ba426508fa8d1365460989daf658681eaf47f8e
parentce7f496c9281f36a5bfdfcc0668ba311129f7937
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