{"id":815139,"url":"http://patchwork.ozlabs.org/api/1.2/patches/815139/?format=json","web_url":"http://patchwork.ozlabs.org/project/netdev/patch/20170918193057.37644-3-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-3-kraigatgoog@gmail.com>","list_archive_url":null,"date":"2017-09-18T19:30:56","name":"[net-next,2/3] bpf: Add uniqueness invariant to trivial lpm test implementation","commit_ref":null,"pull_url":null,"state":"accepted","archived":true,"hash":"973888a36e4caa2f1bf5ab3ad756929f3e3b35f4","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-3-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/815139/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/815139/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 3xwx2D2bH1z9s7p\n\tfor ;\n\tTue, 19 Sep 2017 05:31:16 +1000 (AEST)","(majordomo@vger.kernel.org) by vger.kernel.org via listexpand\n\tid S1751611AbdIRTbO (ORCPT );\n\tMon, 18 Sep 2017 15:31:14 -0400","from mail-qt0-f178.google.com ([209.85.216.178]:45520 \"EHLO\n\tmail-qt0-f178.google.com\" rhost-flags-OK-OK-OK-OK) by vger.kernel.org\n\twith ESMTP id S1751057AbdIRTbB (ORCPT\n\t); Mon, 18 Sep 2017 15:31:01 -0400","by mail-qt0-f178.google.com with SMTP id t46so1666376qtj.2\n\tfor ; Mon, 18 Sep 2017 12:31:01 -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.30.59\n\t(version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128);\n\tMon, 18 Sep 2017 12:30:59 -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=twLbRwJvi1BHrf+mNf9S6riOhUOYfWslpI2WmXJaQio=;\n\tb=hUYPs/hhGka132iJkSWzL87risNN+fkAb2rPCDYSzobfN8EQI6WcSqtMurV95nO+ae\n\tb7Pp0QpePCMBDv737ZGqvp2FbWafqjA8wwcEvTo5wROihA9rBg7xCbECQ/8/A914Qtep\n\tDX0vBwRV8vGLX8lRZz3Il2BI/QxVmX2Za4L5GFdp+FBIgj6bP+gozmXBYgmM99/0FCQJ\n\tFujn+GKvlB/WnBEqMg+H8aiyO5GPig+SMXK1nu9i7T2hOPVVtKjTmCuu2TXMqCbHiUde\n\tq2AdfTIXl6ZXO22yr4TSjzw20l3MDbWL7lUVq5yhwJkqjIGtSWb5PM6a/nm3Ar91YwP5\n\tfang==","X-Gm-Message-State":"AHPjjUgFFz0fyg0eC+JNXtUTPsc4dzHk6byvxVIfRj5mGyXsFBKbdvbO\n\t8s5wGxm++Mg/VaQj","X-Google-Smtp-Source":"AOwi7QD60Y3YzNTcDCU38XsgpdrbDgfTBt4nF1xVJVtKNh8e+Cey8xVDTGqPfjsXlfxWDFXXtbGEwQ==","X-Received":"by 10.200.1.206 with SMTP id b14mr27762758qtg.66.1505763060995; \n\tMon, 18 Sep 2017 12:31:00 -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 2/3] bpf: Add uniqueness invariant to trivial lpm\n\ttest 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"},"content":"From: Craig Gallek \n\nThe 'trivial' lpm implementation in this test allows equivalent nodes\nto be added (that is, nodes consisting of the same prefix and prefix\nlength). For lookup operations, this is fine because insertion happens\nat the head of the (singly linked) list and the first, best match is\nreturned. In order to support deletion, the tlpm data structue must\nfirst enforce uniqueness. This change modifies the insertion algorithm\nto search for equivalent nodes and remove them. Note: the\nBPF_MAP_TYPE_LPM_TRIE already has a uniqueness invariant that is\nimplemented as node replacement.\n\nSigned-off-by: Craig Gallek \n---\n tools/testing/selftests/bpf/test_lpm_map.c | 14 +++++++++++++-\n 1 file changed, 13 insertions(+), 1 deletion(-)","diff":"diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c\nindex e97565243d59..a5ed7c4f1819 100644\n--- a/tools/testing/selftests/bpf/test_lpm_map.c\n+++ b/tools/testing/selftests/bpf/test_lpm_map.c\n@@ -31,6 +31,10 @@ struct tlpm_node {\n \tuint8_t key[];\n };\n \n+static struct tlpm_node *tlpm_match(struct tlpm_node *list,\n+\t\t\t\t const uint8_t *key,\n+\t\t\t\t size_t n_bits);\n+\n static struct tlpm_node *tlpm_add(struct tlpm_node *list,\n \t\t\t\t const uint8_t *key,\n \t\t\t\t size_t n_bits)\n@@ -38,9 +42,17 @@ static struct tlpm_node *tlpm_add(struct tlpm_node *list,\n \tstruct tlpm_node *node;\n \tsize_t n;\n \n+\tn = (n_bits + 7) / 8;\n+\n+\t/* 'overwrite' an equivalent entry if one already exists */\n+\tnode = tlpm_match(list, key, n_bits);\n+\tif (node && node->n_bits == n_bits) {\n+\t\tmemcpy(node->key, key, n);\n+\t\treturn list;\n+\t}\n+\n \t/* add new entry with @key/@n_bits to @list and return new head */\n \n-\tn = (n_bits + 7) / 8;\n \tnode = malloc(sizeof(*node) + n);\n \tassert(node);\n \n","prefixes":["net-next","2/3"]}