bpf: Add uniqueness invariant to trivial lpm test implementation
authorCraig Gallek <kraig@google.com>
Mon, 18 Sep 2017 19:30:56 +0000 (15:30 -0400)
committerDavid S. Miller <davem@davemloft.net>
Tue, 19 Sep 2017 20:55:15 +0000 (13:55 -0700)
commitbae30468dfc1522464f16051addd7bc7da6da75a
tree55e96d451e143911d36be93038b0cd17f53a5683
parente454cf5958538666635488030046b6a84a22d447
bpf: Add uniqueness invariant to trivial lpm test implementation

The 'trivial' lpm implementation in this test allows equivalent nodes
to be added (that is, nodes consisting of the same prefix and prefix
length).  For lookup operations, this is fine because insertion happens
at the head of the (singly linked) list and the first, best match is
returned.  In order to support deletion, the tlpm data structue must
first enforce uniqueness.  This change modifies the insertion algorithm
to search for equivalent nodes and remove them.  Note: the
BPF_MAP_TYPE_LPM_TRIE already has a uniqueness invariant that is
implemented as node replacement.

Signed-off-by: Craig Gallek <kraig@google.com>
Acked-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: David S. Miller <davem@davemloft.net>
tools/testing/selftests/bpf/test_lpm_map.c