From patchwork Mon Sep 18 19:30:55 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Craig Gallek X-Patchwork-Id: 815137 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3xwx201Wq2z9s7G for ; Tue, 19 Sep 2017 05:31:04 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751284AbdIRTbC (ORCPT ); Mon, 18 Sep 2017 15:31:02 -0400 Received: from mail-qt0-f181.google.com ([209.85.216.181]:50936 "EHLO mail-qt0-f181.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750938AbdIRTbA (ORCPT ); Mon, 18 Sep 2017 15:31:00 -0400 Received: by mail-qt0-f181.google.com with SMTP id f15so1660886qtf.7 for ; Mon, 18 Sep 2017 12:31:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=JNxJujDEl1wO1dLl9VBW+4YMqZEJiTcr5sSEKDsp4P0=; b=qlFu9YyJWp8VSxJOO52wgBOXij2MBFN7EzofKkokk3hUBaJaaaqm0DFMQjrkBMQQHg gVp3SI55VE9c0S220nf8Kw6urHvpNTS3shk5B41bVwqeAH4wNdK8K5yCDXMGxS9qtjPN uJapgJ0d+gQE4xpWoG9rFw/VlVqkiWfKYyfP2/u+G0fttvjE1e3kq2FGSbChwhaJFAA6 XxkerkzZZ8xPvnAiKptQFLPO1HlcdAFS34d58ZAlgFssLQTyB4EdAMAmB0q5xhgxT4Vf 9/AKBADA2MWs0ZcVjsX2C0VvCn93KBXyQM7KFqqd3nKDXSKCuYYDrS15Wt5CPKA6Zere GKrA== X-Gm-Message-State: AHPjjUgCBEfVdDgQJrGRhG5KojTu6Kw52pPv+txpS+XOEmRBOpr92FoM wusmbVApwhidOff+ X-Google-Smtp-Source: AOwi7QAPXqh/NlOGdnmr7MHZnJAXRp2869klz6hmcfSez3wtETCGVMjz69D4/NpzIdPQr1WwuT/CGA== X-Received: by 10.200.52.117 with SMTP id v50mr54299593qtb.333.1505763059701; Mon, 18 Sep 2017 12:30:59 -0700 (PDT) Received: from monkey.nyc.corp.google.com ([100.101.213.79]) by smtp.gmail.com with ESMTPSA id e67sm5483579qkb.67.2017.09.18.12.30.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 18 Sep 2017 12:30:58 -0700 (PDT) From: Craig Gallek To: Daniel Mack , Alexei Starovoitov , Daniel Borkmann , "David S . Miller" Cc: netdev@vger.kernel.org Subject: [PATCH net-next 1/3] bpf: Implement map_delete_elem for BPF_MAP_TYPE_LPM_TRIE Date: Mon, 18 Sep 2017 15:30:55 -0400 Message-Id: <20170918193057.37644-2-kraigatgoog@gmail.com> X-Mailer: git-send-email 2.14.1.690.gbb1197296e-goog In-Reply-To: <20170918193057.37644-1-kraigatgoog@gmail.com> References: <20170918193057.37644-1-kraigatgoog@gmail.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Craig Gallek This is a simple non-recursive delete operation. It prunes paths of empty nodes in the tree, but it does not try to further compress the tree as nodes are removed. Signed-off-by: Craig Gallek Acked-by: Daniel Borkmann --- kernel/bpf/lpm_trie.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 77 insertions(+), 3 deletions(-) diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c index 1b767844a76f..9d58a576b2ae 100644 --- a/kernel/bpf/lpm_trie.c +++ b/kernel/bpf/lpm_trie.c @@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map, return ret; } -static int trie_delete_elem(struct bpf_map *map, void *key) +/* Called from syscall or from eBPF program */ +static int trie_delete_elem(struct bpf_map *map, void *_key) { - /* TODO */ - return -ENOSYS; + struct lpm_trie *trie = container_of(map, struct lpm_trie, map); + struct bpf_lpm_trie_key *key = _key; + struct lpm_trie_node __rcu **trim; + struct lpm_trie_node *node; + unsigned long irq_flags; + unsigned int next_bit; + size_t matchlen = 0; + int ret = 0; + + if (key->prefixlen > trie->max_prefixlen) + return -EINVAL; + + raw_spin_lock_irqsave(&trie->lock, irq_flags); + + /* Walk the tree looking for an exact key/length match and keeping + * track of where we could begin trimming the tree. The trim-point + * is the sub-tree along the walk consisting of only single-child + * intermediate nodes and ending at a leaf node that we want to + * remove. + */ + trim = &trie->root; + node = rcu_dereference_protected( + trie->root, lockdep_is_held(&trie->lock)); + while (node) { + matchlen = longest_prefix_match(trie, node, key); + + if (node->prefixlen != matchlen || + node->prefixlen == key->prefixlen) + break; + + next_bit = extract_bit(key->data, node->prefixlen); + /* If we hit a node that has more than one child or is a valid + * prefix itself, do not remove it. Reset the root of the trim + * path to its descendant on our path. + */ + if (!(node->flags & LPM_TREE_NODE_FLAG_IM) || + (node->child[0] && node->child[1])) + trim = &node->child[next_bit]; + node = rcu_dereference_protected( + node->child[next_bit], lockdep_is_held(&trie->lock)); + } + + if (!node || node->prefixlen != key->prefixlen || + (node->flags & LPM_TREE_NODE_FLAG_IM)) { + ret = -ENOENT; + goto out; + } + + trie->n_entries--; + + /* If the node we are removing is not a leaf node, simply mark it + * as intermediate and we are done. + */ + if (rcu_access_pointer(node->child[0]) || + rcu_access_pointer(node->child[1])) { + node->flags |= LPM_TREE_NODE_FLAG_IM; + goto out; + } + + /* trim should now point to the slot holding the start of a path from + * zero or more intermediate nodes to our leaf node for deletion. + */ + while ((node = rcu_dereference_protected( + *trim, lockdep_is_held(&trie->lock)))) { + RCU_INIT_POINTER(*trim, NULL); + trim = rcu_access_pointer(node->child[0]) ? + &node->child[0] : + &node->child[1]; + kfree_rcu(node, rcu); + } + +out: + raw_spin_unlock_irqrestore(&trie->lock, irq_flags); + + return ret; } #define LPM_DATA_SIZE_MAX 256 From patchwork Mon Sep 18 19:30:56 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Craig Gallek X-Patchwork-Id: 815139 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3xwx2D2bH1z9s7p for ; Tue, 19 Sep 2017 05:31:16 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751611AbdIRTbO (ORCPT ); Mon, 18 Sep 2017 15:31:14 -0400 Received: from mail-qt0-f178.google.com ([209.85.216.178]:45520 "EHLO mail-qt0-f178.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751057AbdIRTbB (ORCPT ); Mon, 18 Sep 2017 15:31:01 -0400 Received: by mail-qt0-f178.google.com with SMTP id t46so1666376qtj.2 for ; Mon, 18 Sep 2017 12:31:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=twLbRwJvi1BHrf+mNf9S6riOhUOYfWslpI2WmXJaQio=; b=hUYPs/hhGka132iJkSWzL87risNN+fkAb2rPCDYSzobfN8EQI6WcSqtMurV95nO+ae b7Pp0QpePCMBDv737ZGqvp2FbWafqjA8wwcEvTo5wROihA9rBg7xCbECQ/8/A914Qtep DX0vBwRV8vGLX8lRZz3Il2BI/QxVmX2Za4L5GFdp+FBIgj6bP+gozmXBYgmM99/0FCQJ Fujn+GKvlB/WnBEqMg+H8aiyO5GPig+SMXK1nu9i7T2hOPVVtKjTmCuu2TXMqCbHiUde q2AdfTIXl6ZXO22yr4TSjzw20l3MDbWL7lUVq5yhwJkqjIGtSWb5PM6a/nm3Ar91YwP5 fang== X-Gm-Message-State: AHPjjUgFFz0fyg0eC+JNXtUTPsc4dzHk6byvxVIfRj5mGyXsFBKbdvbO 8s5wGxm++Mg/VaQj X-Google-Smtp-Source: AOwi7QD60Y3YzNTcDCU38XsgpdrbDgfTBt4nF1xVJVtKNh8e+Cey8xVDTGqPfjsXlfxWDFXXtbGEwQ== X-Received: by 10.200.1.206 with SMTP id b14mr27762758qtg.66.1505763060995; Mon, 18 Sep 2017 12:31:00 -0700 (PDT) Received: from monkey.nyc.corp.google.com ([100.101.213.79]) by smtp.gmail.com with ESMTPSA id e67sm5483579qkb.67.2017.09.18.12.30.59 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 18 Sep 2017 12:30:59 -0700 (PDT) From: Craig Gallek To: Daniel Mack , Alexei Starovoitov , Daniel Borkmann , "David S . Miller" Cc: netdev@vger.kernel.org Subject: [PATCH net-next 2/3] bpf: Add uniqueness invariant to trivial lpm test implementation Date: Mon, 18 Sep 2017 15:30:56 -0400 Message-Id: <20170918193057.37644-3-kraigatgoog@gmail.com> X-Mailer: git-send-email 2.14.1.690.gbb1197296e-goog In-Reply-To: <20170918193057.37644-1-kraigatgoog@gmail.com> References: <20170918193057.37644-1-kraigatgoog@gmail.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Craig Gallek 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 Acked-by: Alexei Starovoitov Acked-by: Daniel Borkmann --- tools/testing/selftests/bpf/test_lpm_map.c | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) 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); From patchwork Mon Sep 18 19:30:57 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Craig Gallek X-Patchwork-Id: 815138 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=netdev-owner@vger.kernel.org; receiver=) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3xwx241qrXz9s5L for ; Tue, 19 Sep 2017 05:31:08 +1000 (AEST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751408AbdIRTbE (ORCPT ); Mon, 18 Sep 2017 15:31:04 -0400 Received: from mail-qt0-f180.google.com ([209.85.216.180]:45523 "EHLO mail-qt0-f180.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751024AbdIRTbD (ORCPT ); Mon, 18 Sep 2017 15:31:03 -0400 Received: by mail-qt0-f180.google.com with SMTP id t46so1666452qtj.2 for ; Mon, 18 Sep 2017 12:31:02 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=a0/XPXJPdahaRgnmyHb/qT+Q6K6PgsGcHFjilab66gM=; b=Su0/TlxijY3NfpmONi2rZLP4GTrnbzQrrsBds8jJlZTrhtGZ60l/oRHiDOjNc+0Y9D DVVRT/v4avrF0OJGHUjv5sE9IXksy8TtI2IZelahXrL8i8VeUwf6Ub2SLIvvHATTO6R9 4enujSMI3WwJ40wUUJgXeXfWRCA59DkpldB2T2tMIQbiWXIKyzWqNXTUTQK6fNj1HOtW z4wZXGDj9NfltqAe4QMi1lB8x6FI6FG8eD+i5X3rr7bE0KDmCotoKjp1ODv8J8wVrpkl tRHAjokmpNQF4ixjTZ0Ae5qUtjuyj2nVqnn/09IQl9Bu+DEGrIN8oh2LNE9CmRkMiQhV U/Dg== X-Gm-Message-State: AHPjjUhmsNioIXzL8Gvjnrf1/1xgG8uZtOhNxEgXGu60kI89FI4ggf5I 54noKcb0UVmkz7Tf X-Google-Smtp-Source: AOwi7QAse1kGB+z5paO9GAAGzffrt7ZjzLrouimCZjoLx/pOx8Y8ZtECaSpZVqaTsChphjYR8qyvoA== X-Received: by 10.200.37.157 with SMTP id e29mr33940881qte.271.1505763062175; Mon, 18 Sep 2017 12:31:02 -0700 (PDT) Received: from monkey.nyc.corp.google.com ([100.101.213.79]) by smtp.gmail.com with ESMTPSA id e67sm5483579qkb.67.2017.09.18.12.31.01 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 18 Sep 2017 12:31:01 -0700 (PDT) From: Craig Gallek To: Daniel Mack , Alexei Starovoitov , Daniel Borkmann , "David S . Miller" Cc: netdev@vger.kernel.org Subject: [PATCH net-next 3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE Date: Mon, 18 Sep 2017 15:30:57 -0400 Message-Id: <20170918193057.37644-4-kraigatgoog@gmail.com> X-Mailer: git-send-email 2.14.1.690.gbb1197296e-goog In-Reply-To: <20170918193057.37644-1-kraigatgoog@gmail.com> References: <20170918193057.37644-1-kraigatgoog@gmail.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org From: Craig Gallek Extend the 'random' operation tests to include a delete operation (delete half of the nodes from both lpm implementions and ensure that lookups are still equivalent). Also, add a simple IPv4 test which verifies lookup behavior as nodes are deleted from the tree. Signed-off-by: Craig Gallek Acked-by: Alexei Starovoitov Acked-by: Daniel Borkmann --- tools/testing/selftests/bpf/test_lpm_map.c | 187 ++++++++++++++++++++++++++++- 1 file changed, 183 insertions(+), 4 deletions(-) diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c index a5ed7c4f1819..6fedb9fec36b 100644 --- a/tools/testing/selftests/bpf/test_lpm_map.c +++ b/tools/testing/selftests/bpf/test_lpm_map.c @@ -104,6 +104,34 @@ static struct tlpm_node *tlpm_match(struct tlpm_node *list, return best; } +static struct tlpm_node *tlpm_delete(struct tlpm_node *list, + const uint8_t *key, + size_t n_bits) +{ + struct tlpm_node *best = tlpm_match(list, key, n_bits); + struct tlpm_node *node; + + if (!best || best->n_bits != n_bits) + return list; + + if (best == list) { + node = best->next; + free(best); + return node; + } + + for (node = list; node; node = node->next) { + if (node->next == best) { + node->next = best->next; + free(best); + return list; + } + } + /* should never get here */ + assert(0); + return list; +} + static void test_lpm_basic(void) { struct tlpm_node *list = NULL, *t1, *t2; @@ -126,6 +154,13 @@ static void test_lpm_basic(void) assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15)); assert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16)); + list = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16); + assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8)); + assert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16)); + + list = tlpm_delete(list, (uint8_t[]){ 0xff }, 8); + assert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8)); + tlpm_clear(list); } @@ -170,7 +205,7 @@ static void test_lpm_order(void) static void test_lpm_map(int keysize) { - size_t i, j, n_matches, n_nodes, n_lookups; + size_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups; struct tlpm_node *t, *list = NULL; struct bpf_lpm_trie_key *key; uint8_t *data, *value; @@ -182,6 +217,7 @@ static void test_lpm_map(int keysize) */ n_matches = 0; + n_matches_after_delete = 0; n_nodes = 1 << 8; n_lookups = 1 << 16; @@ -235,15 +271,54 @@ static void test_lpm_map(int keysize) } } + /* Remove the first half of the elements in the tlpm and the + * corresponding nodes from the bpf-lpm. Then run the same + * large number of random lookups in both and make sure they match. + * Note: we need to count the number of nodes actually inserted + * since there may have been duplicates. + */ + for (i = 0, t = list; t; i++, t = t->next) + ; + for (j = 0; j < i / 2; ++j) { + key->prefixlen = list->n_bits; + memcpy(key->data, list->key, keysize); + r = bpf_map_delete_elem(map, key); + assert(!r); + list = tlpm_delete(list, list->key, list->n_bits); + assert(list); + } + for (i = 0; i < n_lookups; ++i) { + for (j = 0; j < keysize; ++j) + data[j] = rand() & 0xff; + + t = tlpm_match(list, data, 8 * keysize); + + key->prefixlen = 8 * keysize; + memcpy(key->data, data, keysize); + r = bpf_map_lookup_elem(map, key, value); + assert(!r || errno == ENOENT); + assert(!t == !!r); + + if (t) { + ++n_matches_after_delete; + assert(t->n_bits == value[keysize]); + for (j = 0; j < t->n_bits; ++j) + assert((t->key[j / 8] & (1 << (7 - j % 8))) == + (value[j / 8] & (1 << (7 - j % 8)))); + } + } + close(map); tlpm_clear(list); /* With 255 random nodes in the map, we are pretty likely to match * something on every lookup. For statistics, use this: * - * printf(" nodes: %zu\n" - * "lookups: %zu\n" - * "matches: %zu\n", n_nodes, n_lookups, n_matches); + * printf(" nodes: %zu\n" + * " lookups: %zu\n" + * " matches: %zu\n" + * "matches(delete): %zu\n", + * n_nodes, n_lookups, n_matches, n_matches_after_delete); */ } @@ -343,6 +418,108 @@ static void test_lpm_ipaddr(void) close(map_fd_ipv6); } +static void test_lpm_delete(void) +{ + struct bpf_lpm_trie_key *key; + size_t key_size; + int map_fd; + __u64 value; + + key_size = sizeof(*key) + sizeof(__u32); + key = alloca(key_size); + + map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, + key_size, sizeof(value), + 100, BPF_F_NO_PREALLOC); + assert(map_fd >= 0); + + /* Add nodes: + * 192.168.0.0/16 (1) + * 192.168.0.0/24 (2) + * 192.168.128.0/24 (3) + * 192.168.1.0/24 (4) + * + * (1) + * / \ + * (IM) (3) + * / \ + * (2) (4) + */ + value = 1; + key->prefixlen = 16; + inet_pton(AF_INET, "192.168.0.0", key->data); + assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); + + value = 2; + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.0.0", key->data); + assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); + + value = 3; + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.128.0", key->data); + assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); + + value = 4; + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.1.0", key->data); + assert(bpf_map_update_elem(map_fd, key, &value, 0) == 0); + + /* remove non-existent node */ + key->prefixlen = 32; + inet_pton(AF_INET, "10.0.0.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 && + errno == ENOENT); + + /* assert initial lookup */ + key->prefixlen = 32; + inet_pton(AF_INET, "192.168.0.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); + assert(value == 2); + + /* remove leaf node */ + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.0.0", key->data); + assert(bpf_map_delete_elem(map_fd, key) == 0); + + key->prefixlen = 32; + inet_pton(AF_INET, "192.168.0.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); + assert(value == 1); + + /* remove leaf (and intermediary) node */ + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.1.0", key->data); + assert(bpf_map_delete_elem(map_fd, key) == 0); + + key->prefixlen = 32; + inet_pton(AF_INET, "192.168.1.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); + assert(value == 1); + + /* remove root node */ + key->prefixlen = 16; + inet_pton(AF_INET, "192.168.0.0", key->data); + assert(bpf_map_delete_elem(map_fd, key) == 0); + + key->prefixlen = 32; + inet_pton(AF_INET, "192.168.128.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == 0); + assert(value == 3); + + /* remove last node */ + key->prefixlen = 24; + inet_pton(AF_INET, "192.168.128.0", key->data); + assert(bpf_map_delete_elem(map_fd, key) == 0); + + key->prefixlen = 32; + inet_pton(AF_INET, "192.168.128.1", key->data); + assert(bpf_map_lookup_elem(map_fd, key, &value) == -1 && + errno == ENOENT); + + close(map_fd); +} + int main(void) { struct rlimit limit = { RLIM_INFINITY, RLIM_INFINITY }; @@ -365,6 +542,8 @@ int main(void) test_lpm_ipaddr(); + test_lpm_delete(); + printf("test_lpm: OK\n"); return 0; }