LPM match support for EBPF back-end (#1962)

* Support LPM in ebpf
p4lang · Jun 21, 2019 · 522fd89 · 522fd89
1 parent a1d8952
commit 522fd89
Show file tree

Hide file tree

Showing 11 changed files with 485 additions and 25 deletions.
diff --git a/backends/ebpf/README.md b/backends/ebpf/README.md
@@ -182,7 +182,11 @@ dataplane/control-plane APIs.
 Our eBPF programs require a Linux kernel with version 4.15 or newer.
 In addition the following packages and programs are required to run the full test suite:
 
-- Clang 3.3 and llvm 3.7.1 or later are required. (Note: In some versions of Ubuntu Xenial (16.04.4) CMake crashes when checking for llvm. Until the bugfix is committed upstream, workarounds are available in the following issue: https://github.com/p4lang/p4c/issues/1376
+- Clang 3.3 and llvm 3.7.1 or later are required. (Note: In some
+  versions of Ubuntu Xenial (16.04.4) CMake crashes when checking for
+  llvm. Until the bugfix is committed upstream, workarounds are
+  available in the following issue:
+  https://github.com/p4lang/p4c/issues/1376
 
 - libpcap-dev to parse and generate .pcap files.
 
@@ -224,7 +228,7 @@ Here are some limitations imposed on the P4 programs:
 
 * arithmetic on data wider than 32 bits is not supported
 
-* eBPF does not offer support for ternary or LPM tables
+* eBPF does not offer support for ternary table matches
 
 ### Translating P4 to C
 

diff --git a/backends/ebpf/ebpfTable.cpp b/backends/ebpf/ebpfTable.cpp
@@ -119,7 +119,8 @@ void EBPFTable::emitKeyType(CodeBuilder* builder) {
 
             auto mtdecl = program->refMap->getDeclaration(c->matchType->path, true);
             auto matchType = mtdecl->getNode()->to<IR::Declaration_ID>();
-            if (matchType->name.name != P4::P4CoreLibrary::instance.exactMatch.name)
+            if (matchType->name.name != P4::P4CoreLibrary::instance.exactMatch.name &&
+                matchType->name.name != P4::P4CoreLibrary::instance.lpmMatch.name)
                 ::error("Match of type %1% not supported", c->matchType);
         }
     }
@@ -228,40 +229,55 @@ void EBPFTable::emitInstance(CodeBuilder* builder) {
             return;
         }
 
-        bool isHash;
+        TableKind tableKind;
         auto extBlock = block->to<IR::ExternBlock>();
         if (extBlock->type->name.name == program->model.array_table.name) {
-            isHash = false;
+            tableKind = TableHash;
         } else if (extBlock->type->name.name == program->model.hash_table.name) {
-            isHash = true;
+            tableKind = TableArray;
         } else {
             ::error("%1%: implementation must be one of %2% or %3%",
                     impl, program->model.array_table.name, program->model.hash_table.name);
             return;
         }
 
+        // If any key field is LPM we will generate an LPM table
+        for (auto it : keyGenerator->keyElements) {
+            auto mtdecl = program->refMap->getDeclaration(it->matchType->path, true);
+            auto matchType = mtdecl->getNode()->to<IR::Declaration_ID>();
+            if (matchType->name.name == P4::P4CoreLibrary::instance.lpmMatch.name) {
+                if (tableKind == TableLPMTrie) {
+                    ::error(ErrorType::ERR_UNSUPPORTED,
+                            "only one LPM field allowed", it->matchType);
+                    return;
+                }
+                tableKind = TableLPMTrie;
+            }
+        }
+
         auto sz = extBlock->getParameterValue(program->model.array_table.size.name);
         if (sz == nullptr || !sz->is<IR::Constant>()) {
-            ::error("Expected an integer argument for %1%; is the model corrupted?", expr);
+            ::error(ErrorType::ERR_UNSUPPORTED,
+                    "Expected an integer argument; is the model corrupted?", expr);
             return;
         }
         auto cst = sz->to<IR::Constant>();
         if (!cst->fitsInt()) {
-            ::error("%1%: size too large", cst);
+            ::error(ErrorType::ERR_UNSUPPORTED, "size too large", cst);
             return;
         }
         int size = cst->asInt();
         if (size <= 0) {
-            ::error("%1%: negative size", cst);
+            ::error(ErrorType::ERR_INVALID, "negative size", cst);
             return;
         }
 
         cstring name = EBPFObject::externalName(table->container);
-        builder->target->emitTableDecl(builder, name, isHash,
+        builder->target->emitTableDecl(builder, name, tableKind,
                                        cstring("struct ") + keyTypeName,
                                        cstring("struct ") + valueTypeName, size);
     }
-    builder->target->emitTableDecl(builder, defaultActionMapName, false,
+    builder->target->emitTableDecl(builder, defaultActionMapName, TableArray,
                                    program->arrayIndexType,
                                    cstring("struct ") + valueTypeName, 1);
 }
@@ -471,24 +487,26 @@ EBPFCounterTable::EBPFCounterTable(const EBPFProgram* program, const IR::ExternB
         EBPFTableBase(program, name, codeGen) {
     auto sz = block->getParameterValue(program->model.counterArray.max_index.name);
     if (sz == nullptr || !sz->is<IR::Constant>()) {
-        ::error("Expected an integer argument for parameter %1% or %2%; is the model corrupted?",
+        ::error(ErrorType::ERR_INVALID,
+                "(%2%): expected an integer argument; is the model corrupted?",
                 program->model.counterArray.max_index, name);
         return;
     }
     auto cst = sz->to<IR::Constant>();
     if (!cst->fitsInt()) {
-        ::error("%1%: size too large", cst);
+        ::error(ErrorType::ERR_OVERLIMIT, "%1%: size too large", cst);
         return;
     }
     size = cst->asInt();
     if (size <= 0) {
-        ::error("%1%: negative size", cst);
+        ::error(ErrorType::ERR_OVERLIMIT, "%1%: negative size", cst);
         return;
     }
 
     auto sprs = block->getParameterValue(program->model.counterArray.sparse.name);
     if (sprs == nullptr || !sprs->is<IR::BoolLiteral>()) {
-        ::error("Expected an integer argument for parameter %1% or %2%; is the model corrupted?",
+        ::error(ErrorType::ERR_INVALID,
+                "(%2%): Expected an integer argument; is the model corrupted?",
                 program->model.counterArray.sparse, name);
         return;
     }
@@ -497,8 +515,9 @@ EBPFCounterTable::EBPFCounterTable(const EBPFProgram* program, const IR::ExternB
 }
 
 void EBPFCounterTable::emitInstance(CodeBuilder* builder) {
+    TableKind kind = isHash ? TableHash : TableArray;
     builder->target->emitTableDecl(
-        builder, dataMapName, isHash, keyTypeName, valueTypeName, size);
+        builder, dataMapName, kind, keyTypeName, valueTypeName, size);
 }
 
 void EBPFCounterTable::emitCounterIncrement(CodeBuilder* builder,
@@ -558,7 +577,8 @@ EBPFCounterTable::emitMethodInvocation(CodeBuilder* builder, const P4::ExternMet
         emitCounterIncrement(builder, method->expr);
         return;
     }
-    ::error("%1%: Unexpected method for %2%", method->expr, program->model.counterArray.name);
+    ::error(ErrorType::ERR_UNSUPPORTED,
+            "Unexpected method for %2%", method->expr, program->model.counterArray.name);
 }
 
 void EBPFCounterTable::emitTypes(CodeBuilder* builder) {

diff --git a/backends/ebpf/p4include/ebpf_model.p4 b/backends/ebpf/p4include/ebpf_model.p4
@@ -42,7 +42,8 @@ extern CounterArray {
 
 /**
  Implementation property for tables indicating that tables must be implemented
- using EBPF array map.
+ using EBPF array map.  However, if a table uses an LPM match type, the implementation
+ is only used for the size, and the table used is an LPM trie.
 */
 extern array_table {
     /// @param size: maximum number of entries in table

diff --git a/backends/ebpf/target.cpp b/backends/ebpf/target.cpp
@@ -44,10 +44,18 @@ void KernelSamplesTarget::emitUserTableUpdate(Util::SourceCodeBuilder* builder,
 }
 
 void KernelSamplesTarget::emitTableDecl(Util::SourceCodeBuilder* builder,
-                                        cstring tblName, bool isHash,
+                                        cstring tblName, TableKind tableKind,
                                         cstring keyType, cstring valueType,
                                         unsigned size) const {
-    cstring kind = isHash ? "BPF_MAP_TYPE_HASH" : "BPF_MAP_TYPE_ARRAY";
+    cstring kind;
+    if (tableKind == TableHash)
+        kind = "BPF_MAP_TYPE_HASH";
+    else if (tableKind == TableArray)
+        kind = "BPF_MAP_TYPE_ARRAY";
+    else if (tableKind == TableLPMTrie)
+        kind = "BPF_MAP_TYPE_LPM_TRIE";
+    else
+        BUG("%1%: unsupported table kind", tableKind);
     builder->appendFormat("REGISTER_TABLE(%s, %s, ", tblName.c_str(), kind.c_str());
     builder->appendFormat("sizeof(%s), sizeof(%s), %d)",
                           keyType.c_str(), valueType.c_str(), size);
@@ -79,6 +87,16 @@ void TestTarget::emitIncludes(Util::SourceCodeBuilder* builder) const {
     builder->newline();
 }
 
+void TestTarget::emitTableDecl(Util::SourceCodeBuilder* builder,
+                               cstring tblName, TableKind,
+                               cstring keyType, cstring valueType,
+                               unsigned size) const {
+    builder->appendFormat("REGISTER_TABLE(%s, 0 /* unused */,", tblName.c_str());
+    builder->appendFormat("sizeof(%s), sizeof(%s), %d)",
+                          keyType.c_str(), valueType.c_str(), size);
+    builder->newline();
+}
+
 //////////////////////////////////////////////////////////////
 
 void BccTarget::emitTableLookup(Util::SourceCodeBuilder* builder, cstring tblName,
@@ -109,9 +127,18 @@ void BccTarget::emitIncludes(Util::SourceCodeBuilder* builder) const {
 }
 
 void BccTarget::emitTableDecl(Util::SourceCodeBuilder* builder,
-                              cstring tblName, bool isHash,
+                              cstring tblName, TableKind tableKind,
                               cstring keyType, cstring valueType, unsigned size) const {
-    cstring kind = isHash ? "hash" : "array";
+    cstring kind;
+    if (tableKind == TableHash)
+        kind = "hash";
+    else if (tableKind == TableArray)
+        kind = "array";
+    else if (tableKind == TableLPMTrie)
+        kind = "lpm_trie";
+    else
+        BUG("%1%: unsupported table kind", tableKind);
+
     builder->appendFormat("BPF_TABLE(\"%s\", %s, %s, %s, %d);",
                           kind.c_str(), keyType.c_str(), valueType.c_str(), tblName.c_str(), size);
     builder->newline();

diff --git a/backends/ebpf/target.h b/backends/ebpf/target.h
@@ -26,6 +26,12 @@ limitations under the License.
 
 namespace EBPF {
 
+enum TableKind {
+    TableHash,
+    TableArray,
+    TableLPMTrie  // longest prefix match trie
+};
+
 class Target {
  protected:
     explicit Target(cstring name) : name(name) {}
@@ -45,7 +51,7 @@ class Target {
     virtual void emitUserTableUpdate(Util::SourceCodeBuilder* builder, cstring tblName,
                                      cstring key, cstring value) const = 0;
     virtual void emitTableDecl(Util::SourceCodeBuilder* builder,
-                               cstring tblName, bool isHash,
+                               cstring tblName, TableKind tableKind,
                                cstring keyType, cstring valueType, unsigned size) const = 0;
     virtual void emitMain(Util::SourceCodeBuilder* builder,
                           cstring functionName,
@@ -74,7 +80,7 @@ class KernelSamplesTarget : public Target {
     void emitUserTableUpdate(Util::SourceCodeBuilder* builder, cstring tblName,
                              cstring key, cstring value) const override;
     void emitTableDecl(Util::SourceCodeBuilder* builder,
-                       cstring tblName, bool isHash,
+                       cstring tblName, TableKind tableKind,
                        cstring keyType, cstring valueType, unsigned size) const override;
     void emitMain(Util::SourceCodeBuilder* builder,
                   cstring functionName,
@@ -103,7 +109,7 @@ class BccTarget : public Target {
     void emitUserTableUpdate(Util::SourceCodeBuilder* builder, cstring tblName,
                              cstring key, cstring value) const override;
     void emitTableDecl(Util::SourceCodeBuilder* builder,
-                       cstring tblName, bool isHash,
+                       cstring tblName, TableKind tableKind,
                        cstring keyType, cstring valueType, unsigned size) const override;
     void emitMain(Util::SourceCodeBuilder* builder,
                   cstring functionName,
@@ -123,6 +129,9 @@ class TestTarget : public EBPF::KernelSamplesTarget {
  public:
     TestTarget() : KernelSamplesTarget("Userspace Test") {}
     void emitIncludes(Util::SourceCodeBuilder* builder) const override;
+    void emitTableDecl(Util::SourceCodeBuilder* builder,
+                       cstring tblName, TableKind tableKind,
+                       cstring keyType, cstring valueType, unsigned size) const override;
     cstring dataOffset(cstring base) const override
     { return cstring("((void*)(long)")+ base + "->data)"; }
     cstring dataEnd(cstring base) const override

diff --git a/testdata/p4_16_samples/lpm_ebpf.p4 b/testdata/p4_16_samples/lpm_ebpf.p4
@@ -0,0 +1,80 @@
+/*
+Copyright 2013-present Barefoot Networks, Inc.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+#include <ebpf_model.p4>
+#include <core.p4>
+
+#include "ebpf_headers.p4"
+
+struct Headers_t
+{
+    Ethernet_h ethernet;
+    IPv4_h     ipv4;
+}
+
+parser prs(packet_in p, out Headers_t headers)
+{
+    state start
+    {
+        p.extract(headers.ethernet);
+        transition select(headers.ethernet.etherType)
+        {
+            16w0x800 : ip;
+            default : reject;
+        }
+    }
+
+    state ip
+    {
+        p.extract(headers.ipv4);
+        transition accept;
+    }
+}
+
+control pipe(inout Headers_t headers, out bool pass)
+{
+    action Reject(IPv4Address add)
+    {
+        pass = false;
+        headers.ipv4.srcAddr = add;
+    }
+
+    table Check_src_ip {
+        key = { headers.ipv4.srcAddr : lpm; }
+        actions =
+        {
+            Reject;
+            NoAction;
+        }
+
+        implementation = hash_table(1024);
+        const default_action = NoAction;
+    }
+
+    apply {
+        pass = true;
+
+        if (!headers.ipv4.isValid())
+        {
+            pass = false;
+            return;
+        }
+
+        Check_src_ip.apply();
+    }
+}
+
+ebpfFilter(prs(), pipe()) main;