{"id":815138,"url":"http://patchwork.ozlabs.org/api/1.2/patches/815138/?format=json","web_url":"http://patchwork.ozlabs.org/project/netdev/patch/20170918193057.37644-4-kraigatgoog@gmail.com/","project":{"id":7,"url":"http://patchwork.ozlabs.org/api/1.2/projects/7/?format=json","name":"Linux network development","link_name":"netdev","list_id":"netdev.vger.kernel.org","list_email":"netdev@vger.kernel.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"<20170918193057.37644-4-kraigatgoog@gmail.com>","list_archive_url":null,"date":"2017-09-18T19:30:57","name":"[net-next,3/3] bpf: Test deletion in BPF_MAP_TYPE_LPM_TRIE","commit_ref":null,"pull_url":null,"state":"accepted","archived":true,"hash":"f8384ff8d9d9c1a5adc61dd81d08d2b485fa012c","submitter":{"id":67365,"url":"http://patchwork.ozlabs.org/api/1.2/people/67365/?format=json","name":"Craig Gallek","email":"kraigatgoog@gmail.com"},"delegate":{"id":34,"url":"http://patchwork.ozlabs.org/api/1.2/users/34/?format=json","username":"davem","first_name":"David","last_name":"Miller","email":"davem@davemloft.net"},"mbox":"http://patchwork.ozlabs.org/project/netdev/patch/20170918193057.37644-4-kraigatgoog@gmail.com/mbox/","series":[{"id":3720,"url":"http://patchwork.ozlabs.org/api/1.2/series/3720/?format=json","web_url":"http://patchwork.ozlabs.org/project/netdev/list/?series=3720","date":"2017-09-18T19:30:54","name":"Implement delete for BPF LPM trie","version":1,"mbox":"http://patchwork.ozlabs.org/series/3720/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/815138/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/815138/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":"patchwork-incoming@ozlabs.org","Delivered-To":"patchwork-incoming@ozlabs.org","Authentication-Results":"ozlabs.org;\n\tspf=none (mailfrom) smtp.mailfrom=vger.kernel.org\n\t(client-ip=209.132.180.67; helo=vger.kernel.org;\n\tenvelope-from=netdev-owner@vger.kernel.org;\n\treceiver=)","Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xwx241qrXz9s5L\n\tfor ;\n\tTue, 19 Sep 2017 05:31:08 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751408AbdIRTbE (ORCPT );\n\tMon, 18 Sep 2017 15:31:04 -0400","from mail-qt0-f180.google.com ([209.85.216.180]:45523 \"EHLO\n\tmail-qt0-f180.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751024AbdIRTbD (ORCPT\n\t); Mon, 18 Sep 2017 15:31:03 -0400","by mail-qt0-f180.google.com with SMTP id t46so1666452qtj.2\n\tfor ; Mon, 18 Sep 2017 12:31:02 -0700 (PDT)","from monkey.nyc.corp.google.com ([100.101.213.79])\n\tby smtp.gmail.com with ESMTPSA id\n\te67sm5483579qkb.67.2017.09.18.12.31.01\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128);\n\tMon, 18 Sep 2017 12:31:01 -0700 (PDT)"],"X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to\n\t:references;\n\tbh=a0/XPXJPdahaRgnmyHb/qT+Q6K6PgsGcHFjilab66gM=;\n\tb=Su0/TlxijY3NfpmONi2rZLP4GTrnbzQrrsBds8jJlZTrhtGZ60l/oRHiDOjNc+0Y9D\n\tDVVRT/v4avrF0OJGHUjv5sE9IXksy8TtI2IZelahXrL8i8VeUwf6Ub2SLIvvHATTO6R9\n\t4enujSMI3WwJ40wUUJgXeXfWRCA59DkpldB2T2tMIQbiWXIKyzWqNXTUTQK6fNj1HOtW\n\tz4wZXGDj9NfltqAe4QMi1lB8x6FI6FG8eD+i5X3rr7bE0KDmCotoKjp1ODv8J8wVrpkl\n\ttRHAjokmpNQF4ixjTZ0Ae5qUtjuyj2nVqnn/09IQl9Bu+DEGrIN8oh2LNE9CmRkMiQhV\n\tU/Dg==","X-Gm-Message-State":"AHPjjUhmsNioIXzL8Gvjnrf1/1xgG8uZtOhNxEgXGu60kI89FI4ggf5I\n\t54noKcb0UVmkz7Tf","X-Google-Smtp-Source":"AOwi7QAse1kGB+z5paO9GAAGzffrt7ZjzLrouimCZjoLx/pOx8Y8ZtECaSpZVqaTsChphjYR8qyvoA==","X-Received":"by 10.200.37.157 with SMTP id e29mr33940881qte.271.1505763062175;\n\tMon, 18 Sep 2017 12:31:02 -0700 (PDT)","From":"Craig Gallek ","To":"Daniel Mack , Alexei Starovoitov ,\n\tDaniel Borkmann ,\n\t\"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"},"content":"From: Craig Gallek \n\nExtend the 'random' operation tests to include a delete operation\n(delete half of the nodes from both lpm implementions and ensure\nthat lookups are still equivalent).\n\nAlso, add a simple IPv4 test which verifies lookup behavior as nodes\nare deleted from the tree.\n\nSigned-off-by: Craig Gallek \n---\n tools/testing/selftests/bpf/test_lpm_map.c | 187 ++++++++++++++++++++++++++++-\n 1 file changed, 183 insertions(+), 4 deletions(-)","diff":"diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c\nindex a5ed7c4f1819..6fedb9fec36b 100644\n--- a/tools/testing/selftests/bpf/test_lpm_map.c\n+++ b/tools/testing/selftests/bpf/test_lpm_map.c\n@@ -104,6 +104,34 @@ static struct tlpm_node *tlpm_match(struct tlpm_node *list,\n \treturn best;\n }\n \n+static struct tlpm_node *tlpm_delete(struct tlpm_node *list,\n+\t\t\t\t const uint8_t *key,\n+\t\t\t\t size_t n_bits)\n+{\n+\tstruct tlpm_node *best = tlpm_match(list, key, n_bits);\n+\tstruct tlpm_node *node;\n+\n+\tif (!best || best->n_bits != n_bits)\n+\t\treturn list;\n+\n+\tif (best == list) {\n+\t\tnode = best->next;\n+\t\tfree(best);\n+\t\treturn node;\n+\t}\n+\n+\tfor (node = list; node; node = node->next) {\n+\t\tif (node->next == best) {\n+\t\t\tnode->next = best->next;\n+\t\t\tfree(best);\n+\t\t\treturn list;\n+\t\t}\n+\t}\n+\t/* should never get here */\n+\tassert(0);\n+\treturn list;\n+}\n+\n static void test_lpm_basic(void)\n {\n \tstruct tlpm_node *list = NULL, *t1, *t2;\n@@ -126,6 +154,13 @@ static void test_lpm_basic(void)\n \tassert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 15));\n \tassert(!tlpm_match(list, (uint8_t[]){ 0x7f, 0xff }, 16));\n \n+\tlist = tlpm_delete(list, (uint8_t[]){ 0xff, 0xff }, 16);\n+\tassert(t1 == tlpm_match(list, (uint8_t[]){ 0xff }, 8));\n+\tassert(t1 == tlpm_match(list, (uint8_t[]){ 0xff, 0xff }, 16));\n+\n+\tlist = tlpm_delete(list, (uint8_t[]){ 0xff }, 8);\n+\tassert(!tlpm_match(list, (uint8_t[]){ 0xff }, 8));\n+\n \ttlpm_clear(list);\n }\n \n@@ -170,7 +205,7 @@ static void test_lpm_order(void)\n \n static void test_lpm_map(int keysize)\n {\n-\tsize_t i, j, n_matches, n_nodes, n_lookups;\n+\tsize_t i, j, n_matches, n_matches_after_delete, n_nodes, n_lookups;\n \tstruct tlpm_node *t, *list = NULL;\n \tstruct bpf_lpm_trie_key *key;\n \tuint8_t *data, *value;\n@@ -182,6 +217,7 @@ static void test_lpm_map(int keysize)\n \t */\n \n \tn_matches = 0;\n+\tn_matches_after_delete = 0;\n \tn_nodes = 1 << 8;\n \tn_lookups = 1 << 16;\n \n@@ -235,15 +271,54 @@ static void test_lpm_map(int keysize)\n \t\t}\n \t}\n \n+\t/* Remove the first half of the elements in the tlpm and the\n+\t * corresponding nodes from the bpf-lpm. Then run the same\n+\t * large number of random lookups in both and make sure they match.\n+\t * Note: we need to count the number of nodes actually inserted\n+\t * since there may have been duplicates.\n+\t */\n+\tfor (i = 0, t = list; t; i++, t = t->next)\n+\t\t;\n+\tfor (j = 0; j < i / 2; ++j) {\n+\t\tkey->prefixlen = list->n_bits;\n+\t\tmemcpy(key->data, list->key, keysize);\n+\t\tr = bpf_map_delete_elem(map, key);\n+\t\tassert(!r);\n+\t\tlist = tlpm_delete(list, list->key, list->n_bits);\n+\t\tassert(list);\n+\t}\n+\tfor (i = 0; i < n_lookups; ++i) {\n+\t\tfor (j = 0; j < keysize; ++j)\n+\t\t\tdata[j] = rand() & 0xff;\n+\n+\t\tt = tlpm_match(list, data, 8 * keysize);\n+\n+\t\tkey->prefixlen = 8 * keysize;\n+\t\tmemcpy(key->data, data, keysize);\n+\t\tr = bpf_map_lookup_elem(map, key, value);\n+\t\tassert(!r || errno == ENOENT);\n+\t\tassert(!t == !!r);\n+\n+\t\tif (t) {\n+\t\t\t++n_matches_after_delete;\n+\t\t\tassert(t->n_bits == value[keysize]);\n+\t\t\tfor (j = 0; j < t->n_bits; ++j)\n+\t\t\t\tassert((t->key[j / 8] & (1 << (7 - j % 8))) ==\n+\t\t\t\t (value[j / 8] & (1 << (7 - j % 8))));\n+\t\t}\n+\t}\n+\n \tclose(map);\n \ttlpm_clear(list);\n \n \t/* With 255 random nodes in the map, we are pretty likely to match\n \t * something on every lookup. For statistics, use this:\n \t *\n-\t * printf(\" nodes: %zu\\n\"\n-\t * \"lookups: %zu\\n\"\n-\t * \"matches: %zu\\n\", n_nodes, n_lookups, n_matches);\n+\t * printf(\" nodes: %zu\\n\"\n+\t * \" lookups: %zu\\n\"\n+\t * \" matches: %zu\\n\"\n+\t * \"matches(delete): %zu\\n\",\n+\t * n_nodes, n_lookups, n_matches, n_matches_after_delete);\n \t */\n }\n \n@@ -343,6 +418,108 @@ static void test_lpm_ipaddr(void)\n \tclose(map_fd_ipv6);\n }\n \n+static void test_lpm_delete(void)\n+{\n+\tstruct bpf_lpm_trie_key *key;\n+\tsize_t key_size;\n+\tint map_fd;\n+\t__u64 value;\n+\n+\tkey_size = sizeof(*key) + sizeof(__u32);\n+\tkey = alloca(key_size);\n+\n+\tmap_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE,\n+\t\t\t\tkey_size, sizeof(value),\n+\t\t\t\t100, BPF_F_NO_PREALLOC);\n+\tassert(map_fd >= 0);\n+\n+\t/* Add nodes:\n+\t * 192.168.0.0/16 (1)\n+\t * 192.168.0.0/24 (2)\n+\t * 192.168.128.0/24 (3)\n+\t * 192.168.1.0/24 (4)\n+\t *\n+\t * (1)\n+\t * / \\\n+ * (IM) (3)\n+\t * / \\\n+ * (2) (4)\n+\t */\n+\tvalue = 1;\n+\tkey->prefixlen = 16;\n+\tinet_pton(AF_INET, \"192.168.0.0\", key->data);\n+\tassert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);\n+\n+\tvalue = 2;\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.0.0\", key->data);\n+\tassert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);\n+\n+\tvalue = 3;\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.128.0\", key->data);\n+\tassert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);\n+\n+\tvalue = 4;\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.1.0\", key->data);\n+\tassert(bpf_map_update_elem(map_fd, key, &value, 0) == 0);\n+\n+\t/* remove non-existent node */\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"10.0.0.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&\n+\t\terrno == ENOENT);\n+\n+\t/* assert initial lookup */\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"192.168.0.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == 0);\n+\tassert(value == 2);\n+\n+\t/* remove leaf node */\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.0.0\", key->data);\n+\tassert(bpf_map_delete_elem(map_fd, key) == 0);\n+\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"192.168.0.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == 0);\n+\tassert(value == 1);\n+\n+\t/* remove leaf (and intermediary) node */\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.1.0\", key->data);\n+\tassert(bpf_map_delete_elem(map_fd, key) == 0);\n+\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"192.168.1.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == 0);\n+\tassert(value == 1);\n+\n+\t/* remove root node */\n+\tkey->prefixlen = 16;\n+\tinet_pton(AF_INET, \"192.168.0.0\", key->data);\n+\tassert(bpf_map_delete_elem(map_fd, key) == 0);\n+\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"192.168.128.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == 0);\n+\tassert(value == 3);\n+\n+\t/* remove last node */\n+\tkey->prefixlen = 24;\n+\tinet_pton(AF_INET, \"192.168.128.0\", key->data);\n+\tassert(bpf_map_delete_elem(map_fd, key) == 0);\n+\n+\tkey->prefixlen = 32;\n+\tinet_pton(AF_INET, \"192.168.128.1\", key->data);\n+\tassert(bpf_map_lookup_elem(map_fd, key, &value) == -1 &&\n+\t\terrno == ENOENT);\n+\n+\tclose(map_fd);\n+}\n+\n int main(void)\n {\n \tstruct rlimit limit = { RLIM_INFINITY, RLIM_INFINITY };\n@@ -365,6 +542,8 @@ int main(void)\n \n \ttest_lpm_ipaddr();\n \n+\ttest_lpm_delete();\n+\n \tprintf(\"test_lpm: OK\\n\");\n \treturn 0;\n }\n","prefixes":["net-next","3/3"]}