[{"id":1770565,"web_url":"http://patchwork.ozlabs.org/comment/1770565/","msgid":"<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>","list_archive_url":null,"date":"2017-09-18T22:53:23","subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","submitter":{"id":68234,"url":"http://patchwork.ozlabs.org/api/people/68234/","name":"Alexei Starovoitov","email":"ast@fb.com"},"content":"On 9/18/17 12:30 PM, Craig Gallek wrote:\n> From: Craig Gallek \n>\n> This is a simple non-recursive delete operation. It prunes paths\n> of empty nodes in the tree, but it does not try to further compress\n> the tree as nodes are removed.\n>\n> Signed-off-by: Craig Gallek \n> ---\n> kernel/bpf/lpm_trie.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++--\n> 1 file changed, 77 insertions(+), 3 deletions(-)\n>\n> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c\n> index 1b767844a76f..9d58a576b2ae 100644\n> --- a/kernel/bpf/lpm_trie.c\n> +++ b/kernel/bpf/lpm_trie.c\n> @@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map,\n> \treturn ret;\n> }\n>\n> -static int trie_delete_elem(struct bpf_map *map, void *key)\n> +/* Called from syscall or from eBPF program */\n> +static int trie_delete_elem(struct bpf_map *map, void *_key)\n> {\n> -\t/* TODO */\n> -\treturn -ENOSYS;\n> +\tstruct lpm_trie *trie = container_of(map, struct lpm_trie, map);\n> +\tstruct bpf_lpm_trie_key *key = _key;\n> +\tstruct lpm_trie_node __rcu **trim;\n> +\tstruct lpm_trie_node *node;\n> +\tunsigned long irq_flags;\n> +\tunsigned int next_bit;\n> +\tsize_t matchlen = 0;\n> +\tint ret = 0;\n> +\n> +\tif (key->prefixlen > trie->max_prefixlen)\n> +\t\treturn -EINVAL;\n> +\n> +\traw_spin_lock_irqsave(&trie->lock, irq_flags);\n> +\n> +\t/* Walk the tree looking for an exact key/length match and keeping\n> +\t * track of where we could begin trimming the tree. The trim-point\n> +\t * is the sub-tree along the walk consisting of only single-child\n> +\t * intermediate nodes and ending at a leaf node that we want to\n> +\t * remove.\n> +\t */\n> +\ttrim = &trie->root;\n> +\tnode = rcu_dereference_protected(\n> +\t\ttrie->root, lockdep_is_held(&trie->lock));\n> +\twhile (node) {\n> +\t\tmatchlen = longest_prefix_match(trie, node, key);\n> +\n> +\t\tif (node->prefixlen != matchlen ||\n> +\t\t node->prefixlen == key->prefixlen)\n> +\t\t\tbreak;\n\ncurious why there is no need to do\n'node->prefixlen == trie->max_prefixlen' in the above\nlike update/lookup do?\n\n> +\n> +\t\tnext_bit = extract_bit(key->data, node->prefixlen);\n> +\t\t/* If we hit a node that has more than one child or is a valid\n> +\t\t * prefix itself, do not remove it. Reset the root of the trim\n> +\t\t * path to its descendant on our path.\n> +\t\t */\n> +\t\tif (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||\n> +\t\t (node->child[0] && node->child[1]))\n> +\t\t\ttrim = &node->child[next_bit];\n> +\t\tnode = rcu_dereference_protected(\n> +\t\t\tnode->child[next_bit], lockdep_is_held(&trie->lock));\n> +\t}\n> +\n> +\tif (!node || node->prefixlen != key->prefixlen ||\n> +\t (node->flags & LPM_TREE_NODE_FLAG_IM)) {\n> +\t\tret = -ENOENT;\n> +\t\tgoto out;\n> +\t}\n> +\n> +\ttrie->n_entries--;\n> +\n> +\t/* If the node we are removing is not a leaf node, simply mark it\n> +\t * as intermediate and we are done.\n> +\t */\n> +\tif (rcu_access_pointer(node->child[0]) ||\n> +\t rcu_access_pointer(node->child[1])) {\n> +\t\tnode->flags |= LPM_TREE_NODE_FLAG_IM;\n> +\t\tgoto out;\n> +\t}\n> +\n> +\t/* trim should now point to the slot holding the start of a path from\n> +\t * zero or more intermediate nodes to our leaf node for deletion.\n> +\t */\n> +\twhile ((node = rcu_dereference_protected(\n> +\t\t\t*trim, lockdep_is_held(&trie->lock)))) {\n> +\t\tRCU_INIT_POINTER(*trim, NULL);\n> +\t\ttrim = rcu_access_pointer(node->child[0]) ?\n> +\t\t\t&node->child[0] :\n> +\t\t\t&node->child[1];\n> +\t\tkfree_rcu(node, rcu);\n\ncan it be that some of the nodes this loop walks have\nboth child[0] and [1] ?","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=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=fb.com header.i=@fb.com header.b=\"cYWy8T7n\";\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=fb.onmicrosoft.com header.i=@fb.onmicrosoft.com\n\theader.b=\"ceOlbhYU\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xx1X36Yy8z9s7M\n\tfor ;\n\tTue, 19 Sep 2017 08:53:55 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751301AbdIRWxw (ORCPT );\n\tMon, 18 Sep 2017 18:53:52 -0400","from mx0b-00082601.pphosted.com ([67.231.153.30]:34603 \"EHLO\n\tmx0a-00082601.pphosted.com\" rhost-flags-OK-OK-OK-FAIL)\n\tby vger.kernel.org with ESMTP id S1750815AbdIRWxu (ORCPT\n\t); Mon, 18 Sep 2017 18:53:50 -0400","from pps.filterd (m0089730.ppops.net [127.0.0.1])\n\tby m0089730.ppops.net (8.16.0.21/8.16.0.21) with SMTP id\n\tv8IMmVor021926; Mon, 18 Sep 2017 15:53:37 -0700","from maileast.thefacebook.com ([199.201.65.23])\n\tby m0089730.ppops.net with ESMTP id 2d2p0qgb0b-1\n\t(version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT);\n\tMon, 18 Sep 2017 15:53:37 -0700","from NAM02-SN1-obe.outbound.protection.outlook.com (192.168.183.28)\n\tby o365-in.thefacebook.com (192.168.177.24) with Microsoft SMTP\n\tServer (TLS) id 14.3.319.2; Mon, 18 Sep 2017 18:53:30 -0400","from [IPv6:2620:10d:c081:1131::119f] (2620:10d:c090:180::1:8838) by\n\tSN2PR15MB0974.namprd15.prod.outlook.com (2603:10b6:804:20::24) with\n\tMicrosoft SMTP Server (version=TLS1_2,\n\tcipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.56.11;\n\tMon, 18 Sep 2017 22:53:27 +0000"],"DKIM-Signature":["v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com;\n\th=subject : to : references\n\t: cc : from : message-id : date : mime-version : in-reply-to :\n\tcontent-type : content-transfer-encoding; s=facebook;\n\tbh=zvbbHyWRVoB08viv8hXeZ4uIK0NQTd6O4rERIVbNU7s=;\n\tb=cYWy8T7nXhaikFBSvFNZnrdztkLYjTVLah3P7Dd/TIc4k+GdsH8TMXCl2nf0cseuZq/t\n\tQj7WUM0v6SEFJSr7ViRd12iUAUPKU16DEVcrmslPfoHcwSFpoMK/YHgB5aE26sqjRsal\n\tn/+joqAvp3Hn8PU9RiLZkq2guUFTVHykfxk= ","v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.onmicrosoft.com; \n\ts=selector1-fb-com;\n\th=From:Date:Subject:Message-ID:Content-Type:MIME-Version; \n\tbh=zvbbHyWRVoB08viv8hXeZ4uIK0NQTd6O4rERIVbNU7s=;\n\tb=ceOlbhYUQM0qoVw5CDnwAyg3Hql92ZcoIbFYO4+n7hsMWpS7ZHtbzfHyeWvS5i4KRGTgzFD9VCCnjGuw9AuiePbEqdDxMOJ57AwWlsBJWqfCHz1adIQrymRzZ42erpULA3bGrULUGAUU361k7ykvxvEWUAwp/IL3+Ys2KJi3JgA="],"Subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","To":"Craig Gallek , Daniel Mack ,\n\tDaniel Borkmann ,\n\t\"David S . Miller\" ","References":"<20170918193057.37644-1-kraigatgoog@gmail.com>\n\t<20170918193057.37644-2-kraigatgoog@gmail.com>","CC":"","From":"Alexei Starovoitov ","Message-ID":"<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>","Date":"Mon, 18 Sep 2017 15:53:23 -0700","User-Agent":"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0)\n\tGecko/20100101 Thunderbird/45.8.0","MIME-Version":"1.0","In-Reply-To":"<20170918193057.37644-2-kraigatgoog@gmail.com>","Content-Type":"text/plain; charset=\"windows-1252\"; format=flowed","Content-Transfer-Encoding":"7bit","X-Originating-IP":"[2620:10d:c090:180::1:8838]","X-ClientProxiedBy":"MWHPR14CA0029.namprd14.prod.outlook.com\n\t(2603:10b6:300:12b::15) To SN2PR15MB0974.namprd15.prod.outlook.com\n\t(2603:10b6:804:20::24)","X-MS-PublicTrafficType":"Email","X-MS-Office365-Filtering-Correlation-Id":"c9cfd79c-caa2-4973-0711-08d4fee813ae","X-Microsoft-Antispam":"UriScan:; BCL:0; PCL:0;\n\tRULEID:(300000500095)(300135000095)(300000501095)(300135300095)(22001)(300000502095)(300135100095)(2017030254152)(300000503095)(300135400095)(2017052603199)(201703131423075)(201703031133081)(201702281549075)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095);\n\tSRVR:SN2PR15MB0974; ","X-Microsoft-Exchange-Diagnostics":["1; SN2PR15MB0974;\n\t3:TI4jDfWXEpKPdUq6MwKnTqwTobz2dL7b/o4ij4EL0lplQcmqLsBJ22bTzCvHwbjqjlJpha/8iLftwfp0/ytNnNtWM9lWKs48Bt9zPbQXFlbvFwRfR34TMcM9mvRW6N6TTocMoOjD9icrcP72D3METrX7KVsDm8yLwMNuq7DQFZ1U629U+YisamQHNfIqhmvevu95rUiOj+JGbvhhREK0Hik9h45yej0gHInL5IpPcfgx1iUOznpTjIVTgSzL1TF6;\n\t25:aogbYNErFNxkx4Mks9f7wSi1CYIjSETyWVE6ys1PRXjdr/oMHjAi4qDUaQLVXS7lTwmgK341MGcy9UCfcF4cL20BNUlexJTY8RMWkVRqIkZFSncs3HwMfdsNOo6aOl7pMb52H8G06KPpUbuMnEPzL7dhuQQQUxl7EZEeA9VYHcLZPU1tasFSr3OUSo2+cN4N/loViNfNz2ysx3P/b8BQaod1Cv9agNp+NLgSTuMZ7CXT6+K5zqB26DobAqgNZfXikAewsace3MMF9KAdHqeurosCj+g1gjRb2YC0/0mrIomDMW8M1BYFTQRQoxj//duP6F/VNkCseIf2t2mj0Yva9w==;\n\t31:mZlnjVLBGGXuvOu+jot3Ok58jhR1yuPKZDIwm7LjwjMlyNWtDu/kky55OSrAaSdYtdRn+0k5p91dKczz/tvQLBflum05yQspALzPgFUasNqEPHXmV7K1C5ePaouchgKfrT/DbJDFzeXcDLwwsxdciy2n6GkRnzgxp6yYpugSdTi9Hq7trwiGWAov4I0ecf69LjkZBg02M30BsWuPvTty4puqrAjfW8TtE5PFzs8hGAw=","1; SN2PR15MB0974;\n\t20:ySwfi18Rff8YC/oZ77oeMnyUWw0CiHJj3pSfpt4GFq96CwwAHxYOrfuBHGWyQnWrka7ndvpCEeqn0C4ROOqWlLwnROWEm/B7H6fuq2pm7QrejWFyR+JDuUsw0ToiUoYJlLi7X3i3P/kO0vedgUYpeumXCdmA5c478j4c7OcTS3xwxnN95ujS6QnP380qokur5gIHqwUj5EalzhdojsLoHMte8qZimNUkNdAYJ4zghlhvRI3abxJCCaqJdeQ7fCcGEn15DBlq4m/6kvDm8E0SdhypdqJ1vmitcW97DS7cQrOYAMmS5nnxyGXVZgswqBselAhJvT5/Vf3hvimjw3GH9U6VXrGtdu0TChNtkmzlrtojc6MdHZGqiNN5hakkIA9KZcgZK0cgznuHuY/guWr4/YfGmvVGdgjBJhZcxuYNCKp8SDFPh7u1E145JhgWkeFDmSpUhHrksuAQNZ/oVaPwB3c0Mo1wEC/qcAYkKiaxBbSjZHQoDGB5R4X61gQAEm3P;\n\t4:gncV1VmPkDjFiRks7yth1qG4rMr8cSv5hLsfhP2aJyM1oTqq4m/B54+kPwIuDGptwn7OVqyT6DMs2JBzTvggkbj0y29SPGNcYQPO+EIaKwcu9aVOdmRQgo3HIls9hA9kNExXy0XCxbbf0W7g5wYGjYr9jnxJu8Eqx9q8/RJXudSWEbsfn9iZrC+qRvVw1ykWwZDFllUvY0gpFRnSNKYZfYvAtx6VeDo/daHmPtNzQPZsTSyJErmAjyzlmlkKghtEfcaFNwkQVz+zbbrscb2iGN+pf+7oWeIQ6UY4fjTM3pqayjXh2yvVg2Bs2zP9NNa+jgVwo/Vc2viTt/kvR2ojzQ==","=?windows-1252?q?1=3BSN2PR15MB0974=3B23?=\n\t=?windows-1252?q?=3APdhE/Mkkuo1Pgw/h50HzIwb0OXx8tyeDRHaCCvWY01Lzma?=\n\t=?windows-1252?q?rgqGkWb6zZ3lQwg2/3H7uSOL5l84kBV+xjifk4WYXdCQ5vZDi?=\n\t=?windows-1252?q?/TwhsZsRtVsiCaO9MQlWPeFo2PlGSzJjwOtsrGkjoRrDWgnRv?=\n\t=?windows-1252?q?aO+S5tRXWiaeeWrnc5Rr116deBhpOxy8kTuXxwMHPRBNCw09v?=\n\t=?windows-1252?q?8luY3C+/dsGn+SDHlqZ1P9LdRdnRsdxkz2RgBVzAkycUekzdy?=\n\t=?windows-1252?q?FDh5YF1Wug+b65WSv/8fNkrpUfTOoIuCQYjZVRcI0fZV0OmQU?=\n\t=?windows-1252?q?6a42L/K4UF4WmSMSaCym8x1SxW8deLSk5ceh2SHDNZwhy0Vsq?=\n\t=?windows-1252?q?gTV4vx483CxH3p3rIyApCcYOG+aD+sYxPBFqD/txT17RNPMEU?=\n\t=?windows-1252?q?LMwKGwRZZRiZXrh497q2HxYqFdzhh7KfD8oyQjnH9Dkzzflx2?=\n\t=?windows-1252?q?8IZnl/Lo57GtQ9Acp+lAqZgjzSy5YhJnXhFi+MuvhMbzIbvKK?=\n\t=?windows-1252?q?eWaxDdyYRp9vLHIWl0nugOw+GSiHE3eZtTpzn5ZYoQGoBCnlq?=\n\t=?windows-1252?q?SaCkG7w9DQhwApei7T9w1UI7Fx8SeyNt6Gey/Q+9DJOHdBER/?=\n\t=?windows-1252?q?dwb3x65mHig5anlBsfm3BP/JQP5upPAu3wdNIAuz4ND8/lFS7?=\n\t=?windows-1252?q?NlqDaUbnViTv/E9BDNsWzOvxgpkpPD6dlXLn9DcTxJB9p8TPb?=\n\t=?windows-1252?q?wRvWxNYXhafQymYabreZbABJOsuIehuC61t/Q3cktWafatL+P?=\n\t=?windows-1252?q?W0tDFiqhFoF4922ed85jBzZVEVYcD4218lGZcoqZf0JBlAhfW?=\n\t=?windows-1252?q?WPNRrsRRwOkuRPsRqyArwtzSMyTF9992CN9sncSuA5CG4RGKg?=\n\t=?windows-1252?q?Wi0voWqpWeaQMvvdBGjBYOjiRuvgEvIPvlXdR8q4mnNIe7iUS?=\n\t=?windows-1252?q?+uALLiMFBPZG5OR7JRuQILmvjkHIIg7vtL+l097vGdwLLHVhW?=\n\t=?windows-1252?q?LDoMAXBFoJ72mkYwad13Mlgclui8xaOU3kRh/WZUp15lza5sM?=\n\t=?windows-1252?q?woQQIxqXy27A0KkLr3yEnHO0ilY+aqWTt+7yCgMWlhlpqtOV5?=\n\t=?windows-1252?q?xjVMAqgSlUZ0nYM8f4ttXOvrlgn8ZvFHq+zGqZQaW8eQge0bw?=\n\t=?windows-1252?q?y+Bq1G1osx3bY1plM0huu7n6XCzIKGRm3llCZJoWWmFYezaDU?=\n\t=?windows-1252?q?Wsg7Y1z+N+/pR+1/T/MTD2vO5qv0ZCoZ1Sh2Uc5g2NEzBW8VR?=\n\t=?windows-1252?q?gBXcnlU1GlS84rvaTnst+8w3oNTjy5f1eQMInT4A4pzysHHzY?=\n\t=?windows-1252?q?9b01BW1Tz6LdN2SaSQanHWTr5hePrWKDYszi6JVVJN3vfMixv?=\n\t=?windows-1252?q?XBMq6bWXuRyuimVYmqlfKCEfY9My4BUmA2YxAKUbfoqx9MMrw?=\n\t=?windows-1252?q?DkY=3D?=","1; SN2PR15MB0974;\n\t6:D9HSHk4q+4VBQrTGMS+k0CoVEg5rhRxL4oTep9ENq6oaQtY/5QN4qSHnEjKBcOGXkjRcXKrANI1QJhbc1kxfDSh8oc85cwfBVodpNE1Uibxgchyc5PH6YFlDOmLtT+G4p87an1gNSuLFIUzZLiu0+MkyEMmWLtOHloEbkmoQuPClFYRK/VLKuJLj+21LB35yKYC+HGvMo33eth/8CJ6smg2i/oAWkYgBjSLgfHsGz9jc11xQex/fxV5pibyEb/nsKr7oBpkErzNgODXimWsFADIBh1Y1T/0iJbp5hSAiv7C2A3lDA++8fEch7oTVgL23Mo1K0L/PgvxbSvP1xXSkAw==;\n\t5:IRw6LFbousUzlawvBUX5CkP3dAAmyQAjAIM7kybwplVrqD0NFu/CxHICf9HSYvw7tIAhPth7ZQTul590k8sif+fbKV8xhlw2z4LPuovSiTKv4TnsZ4XgjUkA2JW0YCLWP4yWokPFnYdQjYelnmruQw==;\n\t24:h9juq9uM10c5Nva0fRSDrntZbVse1pydktfvjiAnJ+sBIXgMcbhz+ZhgRZJd3DuaKyynvaWdxeSw4xFQ0yy9F8ZlPmPgnhyhbbMyAjx0zk8=;\n\t7:syJwSkbYXvYE1xOKNqyFP+XmYgumYoHSNZBE7f2ITE8ERInyJ51xW7DLaPKUnvySXfg3vgrSA6wjWpUICKOoIU9BZrgP+14buk/Yvji7F7UQ5hJ43KBsg1F+nvR9lsLT3OCr4/mNqIRauDs7YzJ/GDw8k9xlBbBDK37NYgFyzUXmkWOtdwZWZQqyknJ8woaz0sj2c7tpJJidBGlqdJU/W9NW8nnhom/K73QmpcCshV8=","1; SN2PR15MB0974;\n\t20:ONG0rrG8ef+wP8b8Sj+NP9JBsyO4HtZUMwmYYgZhH7L9CL7g4zMNgMHcq9IxOwCvHw//BjnytGxyBr1MX4hUD97Vr7MBO4ZE7FyDRrnHkav+5JmTZUk6lwnsUjCdj90fEpa5QXfEEdQmtFEA1iArydFozDiXQ5RtIvY+SSIVhZY="],"X-MS-TrafficTypeDiagnostic":"SN2PR15MB0974:","X-Exchange-Antispam-Report-Test":"UriScan:(211936372134217)(153496737603132); ","X-Microsoft-Antispam-PRVS":"","X-Exchange-Antispam-Report-CFA-Test":"BCL:0; PCL:0;\n\tRULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(2401047)(5005006)(8121501046)(93006095)(93001095)(100000703101)(100105400095)(3002001)(10201501046)(920507026)(6041248)(20161123562025)(20161123558100)(20161123560025)(20161123564025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123555025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);\n\tSRVR:SN2PR15MB0974; BCL:0; PCL:0;\n\tRULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);\n\tSRVR:SN2PR15MB0974; ","X-Forefront-PRVS":"04347F8039","X-Forefront-Antispam-Report":"SFV:NSPM;\n\tSFS:(10019020)(6009001)(346002)(376002)(377454003)(199003)(24454002)(189002)(50986999)(54356999)(316002)(76176999)(39060400002)(229853002)(1706002)(33646002)(31696002)(230700001)(8936002)(25786009)(97736004)(6486002)(58126008)(6666003)(4326008)(83506001)(110136005)(53546010)(2906002)(53936002)(6246003)(101416001)(23746002)(36756003)(8676002)(68736007)(2950100002)(305945005)(6116002)(64126003)(34040400001)(189998001)(65826007)(65806001)(7736002)(5660300001)(105586002)(81156014)(65956001)(86362001)(47776003)(106356001)(31686004)(478600001)(50466002)(81166006)(42262002);\n\tDIR:OUT; SFP:1102; SCL:1; SRVR:SN2PR15MB0974;\n\tH:[IPv6:2620:10d:c081:1131::119f]; FPR:; SPF:None;\n\tPTR:InfoNoRecords; A:1; MX:1; LANG:en; ","Received-SPF":"None (protection.outlook.com: fb.com does not designate\n\tpermitted sender hosts)","SpamDiagnosticOutput":"1:99","SpamDiagnosticMetadata":"NSPM","X-MS-Exchange-CrossTenant-OriginalArrivalTime":"18 Sep 2017 22:53:27.5403\n\t(UTC)","X-MS-Exchange-CrossTenant-FromEntityHeader":"Hosted","X-MS-Exchange-CrossTenant-Id":"8ae927fe-1255-47a7-a2af-5f3a069daaa2","X-MS-Exchange-Transport-CrossTenantHeadersStamped":"SN2PR15MB0974","X-OriginatorOrg":"fb.com","X-Proofpoint-Spam-Reason":"safe","X-FB-Internal":"Safe","X-Proofpoint-Virus-Version":"vendor=fsecure engine=2.50.10432:, ,\n\tdefinitions=2017-09-18_10:, , signatures=0","Sender":"netdev-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"netdev@vger.kernel.org"}},{"id":1771133,"web_url":"http://patchwork.ozlabs.org/comment/1771133/","msgid":"","list_archive_url":null,"date":"2017-09-19T15:08:03","subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","submitter":{"id":67365,"url":"http://patchwork.ozlabs.org/api/people/67365/","name":"Craig Gallek","email":"kraigatgoog@gmail.com"},"content":"On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov wrote:\nThanks for the review! Please correct me if I'm wrong...\n\n> On 9/18/17 12:30 PM, Craig Gallek wrote:\n>>\n>> From: Craig Gallek \n>>\n>> This is a simple non-recursive delete operation. It prunes paths\n>> of empty nodes in the tree, but it does not try to further compress\n>> the tree as nodes are removed.\n>>\n>> Signed-off-by: Craig Gallek \n>> ---\n>> kernel/bpf/lpm_trie.c | 80\n>> +++++++++++++++++++++++++++++++++++++++++++++++++--\n>> 1 file changed, 77 insertions(+), 3 deletions(-)\n>>\n>> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c\n>> index 1b767844a76f..9d58a576b2ae 100644\n>> --- a/kernel/bpf/lpm_trie.c\n>> +++ b/kernel/bpf/lpm_trie.c\n>> @@ -389,10 +389,84 @@ static int trie_update_elem(struct bpf_map *map,\n>> return ret;\n>> }\n>>\n>> -static int trie_delete_elem(struct bpf_map *map, void *key)\n>> +/* Called from syscall or from eBPF program */\n>> +static int trie_delete_elem(struct bpf_map *map, void *_key)\n>> {\n>> - /* TODO */\n>> - return -ENOSYS;\n>> + struct lpm_trie *trie = container_of(map, struct lpm_trie, map);\n>> + struct bpf_lpm_trie_key *key = _key;\n>> + struct lpm_trie_node __rcu **trim;\n>> + struct lpm_trie_node *node;\n>> + unsigned long irq_flags;\n>> + unsigned int next_bit;\n>> + size_t matchlen = 0;\n>> + int ret = 0;\n>> +\n>> + if (key->prefixlen > trie->max_prefixlen)\n>> + return -EINVAL;\n>> +\n>> + raw_spin_lock_irqsave(&trie->lock, irq_flags);\n>> +\n>> + /* Walk the tree looking for an exact key/length match and keeping\n>> + * track of where we could begin trimming the tree. The\n>> trim-point\n>> + * is the sub-tree along the walk consisting of only single-child\n>> + * intermediate nodes and ending at a leaf node that we want to\n>> + * remove.\n>> + */\n>> + trim = &trie->root;\n>> + node = rcu_dereference_protected(\n>> + trie->root, lockdep_is_held(&trie->lock));\n>> + while (node) {\n>> + matchlen = longest_prefix_match(trie, node, key);\n>> +\n>> + if (node->prefixlen != matchlen ||\n>> + node->prefixlen == key->prefixlen)\n>> + break;\n>\n>\n> curious why there is no need to do\n> 'node->prefixlen == trie->max_prefixlen' in the above\n> like update/lookup do?\nI don't believe the node->prefixlen == trie->max_prefixlen check in\ntrie_update_elem is necessary. In order to get to this third clause,\nit implies that the first two clauses evaluated false. Which happens\nwhen we find an exact prefix match for the current node, but the\nto-be-inserted key prefix is different. If the node we are comparing\nagainst had a prefix of max_prefixlen, it would not be possible to\nhave both a full prefix match but different prefix lengths. This\nassumes that there are no nodes in the tree with > max_prefixlen\nprefixes, but that is handled earlier in the update function.\n\nThere's a similar (I believe) unnecessary max_prefixlen check in\ntrie_lookup_elem. The function should behave the same way without\nthat check, but at least in this case it's used as an early-out and\nsaves a few lines of execution.\n\n>\n>> +\n>> + next_bit = extract_bit(key->data, node->prefixlen);\n>> + /* If we hit a node that has more than one child or is a\n>> valid\n>> + * prefix itself, do not remove it. Reset the root of the\n>> trim\n>> + * path to its descendant on our path.\n>> + */\n>> + if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||\n>> + (node->child[0] && node->child[1]))\n>> + trim = &node->child[next_bit];\n>> + node = rcu_dereference_protected(\n>> + node->child[next_bit],\n>> lockdep_is_held(&trie->lock));\n>> + }\n>> +\n>> + if (!node || node->prefixlen != key->prefixlen ||\n>> + (node->flags & LPM_TREE_NODE_FLAG_IM)) {\n>> + ret = -ENOENT;\n>> + goto out;\n>> + }\n>> +\n>> + trie->n_entries--;\n>> +\n>> + /* If the node we are removing is not a leaf node, simply mark it\n>> + * as intermediate and we are done.\n>> + */\n>> + if (rcu_access_pointer(node->child[0]) ||\n>> + rcu_access_pointer(node->child[1])) {\n>> + node->flags |= LPM_TREE_NODE_FLAG_IM;\n>> + goto out;\n>> + }\n>> +\n>> + /* trim should now point to the slot holding the start of a path\n>> from\n>> + * zero or more intermediate nodes to our leaf node for deletion.\n>> + */\n>> + while ((node = rcu_dereference_protected(\n>> + *trim, lockdep_is_held(&trie->lock)))) {\n>> + RCU_INIT_POINTER(*trim, NULL);\n>> + trim = rcu_access_pointer(node->child[0]) ?\n>> + &node->child[0] :\n>> + &node->child[1];\n>> + kfree_rcu(node, rcu);\n>\n>\n> can it be that some of the nodes this loop walks have\n> both child[0] and [1] ?\nNo, the loop above will push trim down the walk every time it\nencounters a node with two children. The only other trim assignment\nis the initial trim = &trie->root. But the only time we would skip\nthe assignment in the loop is if the node being removed is the root.\nIf the root had multiple children and is being removed, it would be\nhandled by the case that turns the node into an intermediate node\nrather than walking the trim path freeing things.","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=)","ozlabs.org; dkim=pass (2048-bit key;\n\tunprotected) header.d=gmail.com header.i=@gmail.com\n\theader.b=\"meAdlYoS\"; dkim-atps=neutral"],"Received":["from vger.kernel.org (vger.kernel.org [209.132.180.67])\n\tby ozlabs.org (Postfix) with ESMTP id 3xxR8C2Mp7z9s3T\n\tfor ;\n\tWed, 20 Sep 2017 01:08:11 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751519AbdISPII (ORCPT );\n\tTue, 19 Sep 2017 11:08:08 -0400","from mail-qk0-f193.google.com ([209.85.220.193]:34407 \"EHLO\n\tmail-qk0-f193.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751097AbdISPIH (ORCPT\n\t); Tue, 19 Sep 2017 11:08:07 -0400","by mail-qk0-f193.google.com with SMTP id d70so2420586qkc.1\n\tfor ; Tue, 19 Sep 2017 08:08:07 -0700 (PDT)","from mail-qt0-f176.google.com (mail-qt0-f176.google.com.\n\t[209.85.216.176]) by smtp.gmail.com with ESMTPSA id\n\tt90sm7005522qkl.77.2017.09.19.08.08.05 for \n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);\n\tTue, 19 Sep 2017 08:08:05 -0700 (PDT)","by mail-qt0-f176.google.com with SMTP id t46so358376qtj.2\n\tfor ; Tue, 19 Sep 2017 08:08:05 -0700 (PDT)","by 10.12.142.78 with HTTP; Tue, 19 Sep 2017 08:08:03 -0700 (PDT)"],"DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=gmail.com; s=20161025;\n\th=mime-version:in-reply-to:references:from:date:message-id:subject:to\n\t:cc; bh=o5wkNhDUYSlTRpCSghZwpYF6spRfh1NnbXFtXBJRrHQ=;\n\tb=meAdlYoS3wmLWpdWMEfQKZs6EsDil+MgKp4K2SRKGvXHMX2thJ7U+x/MRF+YLrmVKI\n\tERQrUpxZ8EBG4d4wGixcIAhUM2ImRotcdO+mXkp/RiOrNMRu6r2UaphHZjAUx5tSyT4l\n\tLQWVg88eFRBDxj6a+j9vAToDPWUT92VBeHDg+JPL3USEFzrDiLnrCkjJcfnM37k4vXrw\n\tgDOsWOA9POAIoNf6nY/gLjN6dxassXX1HsFVb6Vv4ihyXSU7OIkMl3N9bi8eORAChnz0\n\tmXI2120TaTHkTOcY6XFZGs2JTAH5Zuwx7xbwGX0/VkHOYXgMsnsvxY0qon+2EitdeiIu\n\ty/3g==","X-Google-DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/relaxed;\n\td=1e100.net; s=20161025;\n\th=x-gm-message-state:mime-version:in-reply-to:references:from:date\n\t:message-id:subject:to:cc;\n\tbh=o5wkNhDUYSlTRpCSghZwpYF6spRfh1NnbXFtXBJRrHQ=;\n\tb=ZBbn2F9gLzpy5Oy+883BhEEEOo+kE/gLjNJEyMVSHzTfv3/+GsdA+cgmdvoLcLl0al\n\tTzcqF3iKi3CDkTGM8a4+sTYWPizgrIih6QErQ2iyAtxGce6JfWkw5YAQiwDmeYh+yzIA\n\tFFfIK2oEZe5hM0HNy02GQGajrgx1e4eusVXA8fcIdpUE2xYlcEzWVjOBkHeAKfBKSZUV\n\tCDP/yjlmcqRGAIKOQRZl4OM9cdTFa9SJ1w42mg2bqX/KyWypvtmTIOdzRozcBFSaMRiS\n\t62+9i5DfUn486Z5BAVtLK+nhEhJfNQd0H7qByNoZhX9iOTb6M/lyuI6Zm+ijtrrk5yHw\n\tP8Iw==","X-Gm-Message-State":"AHPjjUgqDU3l+baoLALEInG51rcCaFCK/ttE+MeIWY2+GSAFtKbkmJVE\n\tXZqJH2xxnIj4AKg/GdYCZcdnE7zh","X-Received":["by 10.55.150.199 with SMTP id y190mr2536217qkd.180.1505833686235;\n\tTue, 19 Sep 2017 08:08:06 -0700 (PDT)","by 10.200.23.215 with SMTP id r23mr2391489qtk.220.1505833684735; \n\tTue, 19 Sep 2017 08:08:04 -0700 (PDT)"],"X-Google-Smtp-Source":"AOwi7QAqBrIxxknfG1h67cqr/v6Q1TcrgpZCMj08EMM9DNfqbchtPKETFpfjihiJaxhybPF/61CJ5Ri/HXF5hNa+v0M=","MIME-Version":"1.0","In-Reply-To":"<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>","References":"<20170918193057.37644-1-kraigatgoog@gmail.com>\n\t<20170918193057.37644-2-kraigatgoog@gmail.com>\n\t<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>","From":"Craig Gallek ","Date":"Tue, 19 Sep 2017 11:08:03 -0400","X-Gmail-Original-Message-ID":"","Message-ID":"","Subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","To":"Alexei Starovoitov ","Cc":"Daniel Mack , Daniel Borkmann ,\n\t\"David S . Miller\" , netdev ","Content-Type":"text/plain; charset=\"UTF-8\"","Sender":"netdev-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"netdev@vger.kernel.org"}},{"id":1771187,"web_url":"http://patchwork.ozlabs.org/comment/1771187/","msgid":"<59C141DC.9060200@iogearbox.net>","list_archive_url":null,"date":"2017-09-19T16:12:12","subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","submitter":{"id":65705,"url":"http://patchwork.ozlabs.org/api/people/65705/","name":"Daniel Borkmann","email":"daniel@iogearbox.net"},"content":"On 09/19/2017 05:08 PM, Craig Gallek wrote:\n> On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov wrote:\n>> On 9/18/17 12:30 PM, Craig Gallek wrote:\n[...]\n>>> +\n>>> + next_bit = extract_bit(key->data, node->prefixlen);\n>>> + /* If we hit a node that has more than one child or is a\n>>> valid\n>>> + * prefix itself, do not remove it. Reset the root of the\n>>> trim\n>>> + * path to its descendant on our path.\n>>> + */\n>>> + if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||\n>>> + (node->child[0] && node->child[1]))\n>>> + trim = &node->child[next_bit];\n>>> + node = rcu_dereference_protected(\n>>> + node->child[next_bit],\n>>> lockdep_is_held(&trie->lock));\n>>> + }\n>>> +\n>>> + if (!node || node->prefixlen != key->prefixlen ||\n>>> + (node->flags & LPM_TREE_NODE_FLAG_IM)) {\n>>> + ret = -ENOENT;\n>>> + goto out;\n>>> + }\n>>> +\n>>> + trie->n_entries--;\n>>> +\n>>> + /* If the node we are removing is not a leaf node, simply mark it\n>>> + * as intermediate and we are done.\n>>> + */\n>>> + if (rcu_access_pointer(node->child[0]) ||\n>>> + rcu_access_pointer(node->child[1])) {\n>>> + node->flags |= LPM_TREE_NODE_FLAG_IM;\n>>> + goto out;\n>>> + }\n>>> +\n>>> + /* trim should now point to the slot holding the start of a path\n>>> from\n>>> + * zero or more intermediate nodes to our leaf node for deletion.\n>>> + */\n>>> + while ((node = rcu_dereference_protected(\n>>> + *trim, lockdep_is_held(&trie->lock)))) {\n>>> + RCU_INIT_POINTER(*trim, NULL);\n>>> + trim = rcu_access_pointer(node->child[0]) ?\n>>> + &node->child[0] :\n>>> + &node->child[1];\n>>> + kfree_rcu(node, rcu);\n>>\n>> can it be that some of the nodes this loop walks have\n>> both child[0] and [1] ?\n> No, the loop above will push trim down the walk every time it\n> encounters a node with two children. The only other trim assignment\n> is the initial trim = &trie->root. But the only time we would skip\n> the assignment in the loop is if the node being removed is the root.\n> If the root had multiple children and is being removed, it would be\n> handled by the case that turns the node into an intermediate node\n> rather than walking the trim path freeing things.\n\nLooks good to me. We should probably still merge nodes once we turn\na real node into an im which just has a single child attached to it;\nparent can be im or real node. Thus, we don't need to traverse this\nextra one on lookup.\n\nAcked-by: Daniel Borkmann ","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 3xxSZM5FGBz9rvt\n\tfor ;\n\tWed, 20 Sep 2017 02:12:27 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751812AbdISQMZ (ORCPT );\n\tTue, 19 Sep 2017 12:12:25 -0400","from www62.your-server.de ([213.133.104.62]:47095 \"EHLO\n\twww62.your-server.de\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751283AbdISQMX (ORCPT\n\t); Tue, 19 Sep 2017 12:12:23 -0400","from [85.7.161.218] (helo=localhost.localdomain)\n\tby www62.your-server.de with esmtpsa (TLSv1.2:DHE-RSA-AES256-SHA:256)\n\t(Exim 4.85_2) (envelope-from )\n\tid 1duL89-0006im-Aa; Tue, 19 Sep 2017 18:12:13 +0200"],"Message-ID":"<59C141DC.9060200@iogearbox.net>","Date":"Tue, 19 Sep 2017 18:12:12 +0200","From":"Daniel Borkmann ","User-Agent":"Mozilla/5.0 (X11; Linux x86_64;\n\trv:31.0) Gecko/20100101 Thunderbird/31.7.0","MIME-Version":"1.0","To":"Craig Gallek , Alexei Starovoitov ","CC":"Daniel Mack ,\n\t\"David S . Miller\" , netdev ","Subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","References":"<20170918193057.37644-1-kraigatgoog@gmail.com>\n\t<20170918193057.37644-2-kraigatgoog@gmail.com>\n\t<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>\n\t","In-Reply-To":"","Content-Type":"text/plain; charset=utf-8; format=flowed","Content-Transfer-Encoding":"7bit","X-Authenticated-Sender":"daniel@iogearbox.net","X-Virus-Scanned":"Clear (ClamAV 0.99.2/23853/Tue Sep 19 14:42:49 2017)","Sender":"netdev-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"netdev@vger.kernel.org"}},{"id":1771336,"web_url":"http://patchwork.ozlabs.org/comment/1771336/","msgid":"<910eaafa-57a1-2a22-709e-a9107b108d9d@zonque.org>","list_archive_url":null,"date":"2017-09-19T19:48:16","subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","submitter":{"id":64053,"url":"http://patchwork.ozlabs.org/api/people/64053/","name":"Daniel Mack","email":"daniel@zonque.org"},"content":"Hi,\n\nThanks for working on this, Craig!\n\nOn 09/19/2017 06:12 PM, Daniel Borkmann wrote:\n> On 09/19/2017 05:08 PM, Craig Gallek wrote:\n>> On Mon, Sep 18, 2017 at 6:53 PM, Alexei Starovoitov wrote:\n>>> On 9/18/17 12:30 PM, Craig Gallek wrote:\n> [...]\n>>>> +\n>>>> + next_bit = extract_bit(key->data, node->prefixlen);\n>>>> + /* If we hit a node that has more than one child or is a\n>>>> valid\n>>>> + * prefix itself, do not remove it. Reset the root of the\n>>>> trim\n>>>> + * path to its descendant on our path.\n>>>> + */\n>>>> + if (!(node->flags & LPM_TREE_NODE_FLAG_IM) ||\n>>>> + (node->child[0] && node->child[1]))\n>>>> + trim = &node->child[next_bit];\n>>>> + node = rcu_dereference_protected(\n>>>> + node->child[next_bit],\n>>>> lockdep_is_held(&trie->lock));\n>>>> + }\n>>>> +\n>>>> + if (!node || node->prefixlen != key->prefixlen ||\n>>>> + (node->flags & LPM_TREE_NODE_FLAG_IM)) {\n>>>> + ret = -ENOENT;\n>>>> + goto out;\n>>>> + }\n>>>> +\n>>>> + trie->n_entries--;\n>>>> +\n>>>> + /* If the node we are removing is not a leaf node, simply mark it\n>>>> + * as intermediate and we are done.\n>>>> + */\n>>>> + if (rcu_access_pointer(node->child[0]) ||\n>>>> + rcu_access_pointer(node->child[1])) {\n>>>> + node->flags |= LPM_TREE_NODE_FLAG_IM;\n>>>> + goto out;\n>>>> + }\n>>>> +\n>>>> + /* trim should now point to the slot holding the start of a path\n>>>> from\n>>>> + * zero or more intermediate nodes to our leaf node for deletion.\n>>>> + */\n>>>> + while ((node = rcu_dereference_protected(\n>>>> + *trim, lockdep_is_held(&trie->lock)))) {\n>>>> + RCU_INIT_POINTER(*trim, NULL);\n>>>> + trim = rcu_access_pointer(node->child[0]) ?\n>>>> + &node->child[0] :\n>>>> + &node->child[1];\n>>>> + kfree_rcu(node, rcu);\n>>>\n>>> can it be that some of the nodes this loop walks have\n>>> both child[0] and [1] ?\n>> No, the loop above will push trim down the walk every time it\n>> encounters a node with two children. The only other trim assignment\n>> is the initial trim = &trie->root. But the only time we would skip\n>> the assignment in the loop is if the node being removed is the root.\n>> If the root had multiple children and is being removed, it would be\n>> handled by the case that turns the node into an intermediate node\n>> rather than walking the trim path freeing things.\n> \n> Looks good to me. We should probably still merge nodes once we turn\n> a real node into an im which just has a single child attached to it;\n> parent can be im or real node. Thus, we don't need to traverse this\n> extra one on lookup.\n\nRight, but only if the the parent of the node allows us to do that,\nbecause the 'next bit' in the lookup key has to match the slot index.\n\nTo illustrate, consider the following trie with no IM nodes:\n\n +----------------+\n | (1) (R) |\n | 192.168.0.0/16 |\n | value: 1 |\n | [0] [1] |\n +----------------+\n | |\n +----------------+ +------------------+\n | (2) | | (3) |\n | 192.168.0.0/23 | | 192.168.128.0/24 |\n | value: 2 | | value: 3 |\n | [0] [1] | | [0] [1] |\n +----------------+ +------------------+\n |\n +----------------+\n | (4) |\n | 192.168.1.0/24 |\n | value: 4 |\n | [0] [1] |\n +----------------+\n\nIf you now try to delete (2), the node has to stay around because (3)\nand (4) share the same value in bit 17 (1). If, however, (4) had a\nprefix of 192.168.0.0/24, then (2) should be removed completely, and (4)\nshould be directly attached to (1) as child[0].\n\nWith this implementation, a situation in which multiple IM nodes appear\nin a chain cannot emerge. And that again should make your trimming\nalgorithm simpler, because you only need to find an exact match, and\nthen handle three distinct cases:\n\na) the node as 0 children: simply remove it and nullify the pointer in\nthe parent\n\nb) the node has 1 child: apply logic I described above\n\nc) the node has 2 children: turn the node into an IM\n\n\nMakes sense?\n\n\nThanks,\nDaniel","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 3xxYYk246nz9sMN\n\tfor ;\n\tWed, 20 Sep 2017 05:57:14 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751730AbdIST5L (ORCPT );\n\tTue, 19 Sep 2017 15:57:11 -0400","from mail.bugwerft.de ([46.23.86.59]:50854 \"EHLO mail.bugwerft.de\"\n\trhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP\n\tid S1751556AbdIST5K (ORCPT );\n\tTue, 19 Sep 2017 15:57:10 -0400","from [192.168.178.170] (pD95EF90D.dip0.t-ipconnect.de\n\t[217.94.249.13])\n\tby mail.bugwerft.de (Postfix) with ESMTPSA id 66F2B28001A;\n\tTue, 19 Sep 2017 19:45:49 +0000 (UTC)"],"X-Greylist":"delayed 531 seconds by postgrey-1.27 at vger.kernel.org;\n\tTue, 19 Sep 2017 15:57:09 EDT","Subject":"Re: [PATCH net-next 1/3] bpf: Implement map_delete_elem for\n\tBPF_MAP_TYPE_LPM_TRIE","To":"Daniel Borkmann ,\n\tCraig Gallek , Alexei Starovoitov ","Cc":"\"David S . Miller\" , netdev ","References":"<20170918193057.37644-1-kraigatgoog@gmail.com>\n\t<20170918193057.37644-2-kraigatgoog@gmail.com>\n\t<3e537b56-d0f2-de9a-5bb1-f60fbfc11ca5@fb.com>\n\t\n\t<59C141DC.9060200@iogearbox.net>","From":"Daniel Mack ","Message-ID":"<910eaafa-57a1-2a22-709e-a9107b108d9d@zonque.org>","Date":"Tue, 19 Sep 2017 21:48:16 +0200","User-Agent":"Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101\n\tThunderbird/52.3.0","MIME-Version":"1.0","In-Reply-To":"<59C141DC.9060200@iogearbox.net>","Content-Type":"text/plain; charset=utf-8","Content-Language":"en-US","Content-Transfer-Encoding":"8bit","Sender":"netdev-owner@vger.kernel.org","Precedence":"bulk","List-ID":"","X-Mailing-List":"netdev@vger.kernel.org"}}]