| Message ID | 20170918193057.37644-3-kraigatgoog@gmail.com |
|---|---|
| State | Accepted, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | Implement delete for BPF LPM trie | expand |
On 9/18/17 12:30 PM, Craig Gallek wrote: > From: Craig Gallek <kraig@google.com> > > 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>
On 09/18/2017 09:30 PM, Craig Gallek wrote: > From: Craig Gallek <kraig@google.com> > > 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: Daniel Borkmann <daniel@iogearbox.net>
diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c index e97565243d59..a5ed7c4f1819 100644 --- a/tools/testing/selftests/bpf/test_lpm_map.c +++ b/tools/testing/selftests/bpf/test_lpm_map.c @@ -31,6 +31,10 @@ struct tlpm_node { uint8_t key[]; }; +static struct tlpm_node *tlpm_match(struct tlpm_node *list, + const uint8_t *key, + size_t n_bits); + static struct tlpm_node *tlpm_add(struct tlpm_node *list, const uint8_t *key, size_t n_bits) @@ -38,9 +42,17 @@ static struct tlpm_node *tlpm_add(struct tlpm_node *list, struct tlpm_node *node; size_t n; + n = (n_bits + 7) / 8; + + /* 'overwrite' an equivalent entry if one already exists */ + node = tlpm_match(list, key, n_bits); + if (node && node->n_bits == n_bits) { + memcpy(node->key, key, n); + return list; + } + /* add new entry with @key/@n_bits to @list and return new head */ - n = (n_bits + 7) / 8; node = malloc(sizeof(*node) + n); assert(node);