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