From patchwork Fri Oct 23 23:29:02 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Owen Hilyard X-Patchwork-Id: 82032 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 940EFA04B0; Sat, 24 Oct 2020 01:29:30 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D62146A57; Sat, 24 Oct 2020 01:29:27 +0200 (CEST) Received: from mail-qk1-f195.google.com (mail-qk1-f195.google.com [209.85.222.195]) by dpdk.org (Postfix) with ESMTP id 8877A68C3 for ; Sat, 24 Oct 2020 01:29:25 +0200 (CEST) Received: by mail-qk1-f195.google.com with SMTP id b69so3093380qkg.8 for ; Fri, 23 Oct 2020 16:29:25 -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=SE1n5XvzmTN7E2a8Kydc2TWonDAZlsuzqJifURyAdw2BHqgB6Y27Pt494Tsj+/p+Op DSS0QXm9OwTRdKDn0FeFRZiI0hl8FGUbFaUVBQFPuedw2PaqBFK7NjxtQUBDMzCpiE6B GGgn2RYkwj/a5EuaXRse30n7GmytOV3vRaNqk= 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=fuWzDfvQRP3+CgtBpayC2PD7ERAgOooVkxFXXCFMqg3lEiyTSOidScIAM5CCwTtisk 9dk3cgTH6SwS8+ccCkNEjdL8IW0BG8Ys2YNoNZsXqufJnbs6h96Qh26pRhrK481Nag7t HVHTQ24j/OEdvsOZeEOorB7sf/TJHoJxCIqCL/XceqxHTOGKAK1Ihd+6PL5J7odxRfIs Rw5qbH4tvu8nxdysSy2yrlEf70k3TzPnKIeVa7CzGIUDCkGvDcKpUSNjOc2IAuQqSNy8 GfQRkbiCLknu6sTpRkNKEuJuqA4qPydbv1v8Fx4JPgDnfrT6xxuXwPndzt1G7sSySEIs sAQA== X-Gm-Message-State: AOAM531pOOGPwM5B0/EDr9TNDx2+vEP/b5HhQoLXQCEouo5YUkWEynwj vF49GP6+vOTWkVvI0HM69mo1tg== X-Google-Smtp-Source: ABdhPJxg1/s92LLZuU2Spa+1mvmipOv2vCYGElB99XSwFGyTFYji9nabQAHpIA2FGbVqOa7G+PpXRQ== X-Received: by 2002:a37:617:: with SMTP id 23mr4601467qkg.256.1603495763865; Fri, 23 Oct 2020 16:29:23 -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.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 23 Oct 2020 16:29:23 -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:02 -0400 Message-Id: <20201023232903.37387-7-ohilyard@iol.unh.edu> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20201023232903.37387-6-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> MIME-Version: 1.0 Subject: [dts] [PATCH v2 7/7] 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()