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);