Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/1.2/patches/815138/?format=api
{ "id": 815138, "url": "http://patchwork.ozlabs.org/api/1.2/patches/815138/?format=api", "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=api", "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=api", "name": "Craig Gallek", "email": "kraigatgoog@gmail.com" }, "delegate": { "id": 34, "url": "http://patchwork.ozlabs.org/api/1.2/users/34/?format=api", "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=api", "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": "<netdev-owner@vger.kernel.org>", "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=<UNKNOWN>)", "Received": [ "from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xwx241qrXz9s5L\n\tfor <patchwork-incoming@ozlabs.org>;\n\tTue, 19 Sep 2017 05:31:08 +1000 (AEST)", "(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751408AbdIRTbE (ORCPT <rfc822;patchwork-incoming@ozlabs.org>);\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<rfc822;netdev@vger.kernel.org>); Mon, 18 Sep 2017 15:31:03 -0400", "by mail-qt0-f180.google.com with SMTP id t46so1666452qtj.2\n\tfor <netdev@vger.kernel.org>; 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 <kraigatgoog@gmail.com>", "To": "Daniel Mack <daniel@zonque.org>, Alexei Starovoitov <ast@fb.com>,\n\tDaniel Borkmann <daniel@iogearbox.net>,\n\t\"David S . Miller\" <davem@davemloft.net>", "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": "<netdev.vger.kernel.org>", "X-Mailing-List": "netdev@vger.kernel.org" }, "content": "From: Craig Gallek <kraig@google.com>\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 <kraig@google.com>\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" ] }