From patchwork Fri Oct 23 23:29:03 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Owen Hilyard X-Patchwork-Id: 82033 Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1251AA04B0; Sat, 24 Oct 2020 01:29:32 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 0AAA96883; Sat, 24 Oct 2020 01:29:29 +0200 (CEST) Received: from mail-qk1-f193.google.com (mail-qk1-f193.google.com [209.85.222.193]) by dpdk.org (Postfix) with ESMTP id 8DD4D6889 for ; Sat, 24 Oct 2020 01:29:26 +0200 (CEST) Received: by mail-qk1-f193.google.com with SMTP id r7so3107623qkf.3 for ; Fri, 23 Oct 2020 16:29:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=iol.unh.edu; s=unh-iol; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=CUeHhS4dJYTiXvGsKOwHPqfsHVQImc+AuhGy9C9p7Vk=; b=N7vZrZVl12qSXQxQojGw+AZRFl2QFIiiyVHLHvc6LO4zJLX8TlBuV+wfJU23GyKwsG 3dosqx4XXKTyzvfT8480e00uvjmAKjPrGfAfQo3kyAhohChM25gqi+XSsRHkiIyYxr8Z 67iONlIn4kqXagM84rA2iNBjyX8arCsGG2fdY= 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:mime-version:content-transfer-encoding; bh=CUeHhS4dJYTiXvGsKOwHPqfsHVQImc+AuhGy9C9p7Vk=; b=OvWaD1CI4EdAWGDYVuX5tXN/g1aHlvbsA8wpWuctjSbKRHL5zaLszOglPlFxZoFdhS vEyc923FogKig1aOGDcO125UCYe4caupO37MpkEgWpSkp10pewSksnMedLzdH1Tjdffk +xfqpkGdlDZk8bxVA/zDk2Nke+DuxPIzj17ANusoJ/ZAhx4NeKv7IITQPOLXwyNXAS47 jedfRLJcCR42eF+zZDJJ7CBoF5k2jRbU3RvWgyVkXvyt2gTqH4s0kl0Td7MH1EZmNdXU +Ork3BM2ru3aqu0a3C53WNmt+irk7WVdfoFJ4uBf2rloeYrynKuY1vI0FfGHRvM3RekK kE+w== X-Gm-Message-State: AOAM530D2GjMHmlKRmiZp+4Y2doXuJAE/PWoMpQFKAZlsBRVvxoLoolo DWBjnn+QJdLu9O8s4HVz9AKlnw== X-Google-Smtp-Source: ABdhPJz8cTSEL/q9gS6h3MhWxcAsKwXmNGJy5GndkwgOO2lp4X94S5Eg+EOpR8IRA2RwVx4F5uHK+g== X-Received: by 2002:a37:e202:: with SMTP id g2mr5020987qki.450.1603495764922; Fri, 23 Oct 2020 16:29:24 -0700 (PDT) Received: from ohilyard-Alienware-m17.iol.unh.edu (nt-238-66.w4.unh.edu. [132.177.238.66]) by smtp.googlemail.com with ESMTPSA id j16sm1851673qkg.26.2020.10.23.16.29.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 23 Oct 2020 16:29:24 -0700 (PDT) From: Owen Hilyard To: ohilyard@iol.unh.edu, dts@dpdk.org, lijuan.tu@intel.com Cc: shall@iol.unh.edu, lihongx.ma@intel.com, lylavoie@iol.unh.edu, zhaoyan.chen@intel.com, yuan.peng@intel.com Date: Fri, 23 Oct 2020 19:29:03 -0400 Message-Id: <20201023232903.37387-8-ohilyard@iol.unh.edu> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20201023232903.37387-7-ohilyard@iol.unh.edu> References: <20201023232903.37387-1-ohilyard@iol.unh.edu> <20201023232903.37387-2-ohilyard@iol.unh.edu> <20201023232903.37387-3-ohilyard@iol.unh.edu> <20201023232903.37387-4-ohilyard@iol.unh.edu> <20201023232903.37387-5-ohilyard@iol.unh.edu> <20201023232903.37387-6-ohilyard@iol.unh.edu> <20201023232903.37387-7-ohilyard@iol.unh.edu> MIME-Version: 1.0 Subject: [dts] [PATCH v2] rte flow: add flow test generator X-BeenThere: dts@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: test suite reviews and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dts-bounces@dpdk.org Sender: "dts" This file contains the actual generation logic for tests. The actual implimentation of the generation logic makes heavy use of the functional programming features in python due to the need to allow delayed execution through the entire chain of items. This is accomplished using a mixture of generator functions and the aformentioned functional programming capabilities. This delayed execution allows a for a much greater number of flow rules to be generated without causing issues in memory, since at most the program is storing a few dozen stack frames, instead of potentially a few thousand flow rules. This allows the generation logic to, with the proper parameters, generate all possible flow rules (ignoring properties). This would normally result in 2.5 million flow rules needing to be resident in memory before any properties could be changed. The approach of fully fuzzing the parser was not taken because, by my estimate, it would result in more than 11,479,792,543,757,705,936,896 flow rules. Signed-off-by: Owen Hilyard --- framework/flow/generator.py | 165 ++++++++++++++++++++++++++++++++++++ 1 file changed, 165 insertions(+) create mode 100644 framework/flow/generator.py diff --git a/framework/flow/generator.py b/framework/flow/generator.py new file mode 100644 index 0000000..0fe52b2 --- /dev/null +++ b/framework/flow/generator.py @@ -0,0 +1,165 @@ +# BSD LICENSE +# +# Copyright(c) 2020 Intel Corporation. All rights reserved. +# Copyright © 2018[, 2019] The University of New Hampshire. All rights reserved. +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# * Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in +# the documentation and/or other materials provided with the +# distribution. +# * Neither the name of Intel Corporation nor the names of its +# contributors may be used to endorse or promote products derived +# from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +from __future__ import annotations + +import copy +import itertools +import os +import sys +import time +from typing import List, Set, Generator, Iterable, FrozenSet, Tuple + +import numpy as np + +from flow.flow import Flow +from flow.flow_pattern_items import PATTERN_ITEMS_TYPE_CLASS_MAPPING, PatternFlowItem, \ + PATTERN_OPERATION_TYPES, TUNNELING_PROTOCOL_TYPES, ALWAYS_ALLOWED_ITEMS, FlowItemEnd, FlowItemVxlan, FlowItemIpv4, \ + FlowItemEth, FlowItemGre, L3_FLOW_TYPES, FlowItemVlan, FlowItemUdp +from flow.flow_rule import FlowItemType + + +def get_valid_next_protocols(current_protocol, protocol_stack, type_denylist): + return list(filter( + lambda patent_item: patent_item not in type_denylist and patent_item not in {p.type for p in protocol_stack}, + current_protocol.valid_parent_items)) + + +def _generate(type_denylist=None) -> List[List[PatternFlowItem]]: + if type_denylist is None: + type_denylist = set() + UNUSED_PATTERN_ITEMS = {PATTERN_ITEMS_TYPE_CLASS_MAPPING[i] for i in type_denylist} + + patterns: List[List[PatternFlowItem]] = [] + for pattern_item in [clazz for clazz in PATTERN_ITEMS_TYPE_CLASS_MAPPING.values() if + clazz not in UNUSED_PATTERN_ITEMS]: + protocol_stack = [] + if protocol_stack.count(pattern_item) >= 2: + continue + + current_protocol = pattern_item() + valid_next_protocols = get_valid_next_protocols(current_protocol, protocol_stack, type_denylist) + while len(valid_next_protocols) > 0: + protocol_stack.append(current_protocol) + current_protocol = PATTERN_ITEMS_TYPE_CLASS_MAPPING[list(valid_next_protocols)[0]]() + valid_next_protocols = get_valid_next_protocols(current_protocol, protocol_stack, type_denylist) + + protocol_stack.append(current_protocol) + + patterns.append(list(reversed(protocol_stack))) # This will place the lowest level protocols first + return patterns + + +def convert_protocol_stack_to_flow_pattern(protocol_stack): + return Flow(pattern_items=protocol_stack) + + +def _get_patterns_with_type_denylist(type_denylist: Set): + return [convert_protocol_stack_to_flow_pattern(protocol_stack) for protocol_stack in (_generate( + type_denylist=type_denylist + ))] + + +def _get_normal_protocol_patterns() -> List[Flow]: + return _get_patterns_with_type_denylist( + PATTERN_OPERATION_TYPES | ALWAYS_ALLOWED_ITEMS | {FlowItemType.ANY, + FlowItemType.END}) + + +def _get_tunnelled_protocol_patterns(patterns: List[Flow]) -> Generator[Flow]: + VXLAN_FLOW = Flow(pattern_items=[FlowItemEth(), FlowItemIpv4(), FlowItemUdp(), FlowItemVxlan()]) + for pattern in patterns: + yield VXLAN_FLOW / pattern + + GRE_FLOW = Flow(pattern_items=[FlowItemEth(), FlowItemIpv4(), FlowItemGre()]) + for pattern in patterns: + if len(pattern.pattern_items) >= 2: + if pattern.pattern_items[1].type in L3_FLOW_TYPES: + yield GRE_FLOW / pattern + + +def get_patterns() -> Iterable[Iterable[Flow]]: + patterns: List[Flow] = _get_normal_protocol_patterns() + + # The flow with only an ethernet header was a consequence of the + # generation algorithm, but isn't that useful to test since we can't + # create a failing case without getting each NIC to write arbitrary + # bytes over the link. + eth_only_flow = Flow(pattern_items=[FlowItemEth()]) + patterns.remove(eth_only_flow) + + # tunnelled_patterns = _get_tunnelled_protocol_patterns(patterns) + + return patterns + + +def add_properties_to_patterns(patterns: Iterable[Flow]) -> Iterable[Tuple[Flow, FrozenSet[str], FrozenSet[str], str]]: + test_property_flow_iters = map(lambda f: f.get_test_property_flows(), patterns) + for iterator in test_property_flow_iters: + yield from iterator + + +def get_patterns_with_properties() -> Iterable[Tuple[Flow, FrozenSet[str], FrozenSet[str], str]]: + base_patterns = get_patterns() + return add_properties_to_patterns(base_patterns) + + +def create_test_function_strings(test_configurations: Iterable[Tuple[Flow, FrozenSet[str], FrozenSet[str], str]]) -> \ + Iterable[str]: + """ + This will break if the __str__ methods of frozenset ever changes or if % formatting syntax is removed. + + @param test_configurations: An iterable with test configurations to convert into test case strings. + @return: An iterable containing strings that are function parameters. + """ + function_template = \ + """ +def test_%s(self): + self.do_test_with_queue_action("%s", %s, %s) + """ + return map(lambda test_configuration: function_template % ( + test_configuration[-1], test_configuration[0], test_configuration[1], test_configuration[2],), + test_configurations) + + +def main(): + """ + Run this file (python3 generator.py) from the flow directory to print + out the pattern functions which are normally automatically generated + and added to the RTE Flow test suite at runtime. + """ + pattern_tests = list(get_patterns_with_properties()) + pattern_functions = create_test_function_strings(pattern_tests) + print("\n".join(pattern_functions)) + + +if __name__ == "__main__": + main()