From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 24BF9A00C5; Thu, 15 Sep 2022 16:13:10 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 03CB14021D; Thu, 15 Sep 2022 16:13:10 +0200 (CEST) Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by mails.dpdk.org (Postfix) with ESMTP id 5743840156 for ; Thu, 15 Sep 2022 16:13:07 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1663251187; x=1694787187; h=date:from:to:cc:subject:message-id:references: in-reply-to:mime-version; bh=qPJrp/cbhzu5qKU/IB8zWShF7SHDJ1sO+2Mu+OxkZBE=; b=lxar0XbBVs0d6/jzlIY2Nygkv/daP+rdh6+tlwC12wuMf5xLn1X2NERE 3ZMezrY6U+nNR118ZxqqRj9UvPLj5mtM492jUFwR59QqfGjXIZX9QJs3q Z8lgywO+Wlwxh6uB1zvqFrzx8gkRcOHVS4waOAHcdPh6h1N1xILUVtPHf uWnwNf5CXniwaBF8GNOHIw1xqBV1PGzWMS8y2hvBI4a6lD1o5QWHiekZj 5PtPRpv7hu8L3piB+tk4A/f5wzHvuc29U+eqDCu5Nmc4OOlorPfpbqFJ2 qauQF8iC5KuJ95aQ6+47QTni2gcDPh2jUFUJgY7P0TYnQZnrqsGQhqhYA A==; X-IronPort-AV: E=McAfee;i="6500,9779,10470"; a="279108533" X-IronPort-AV: E=Sophos;i="5.93,318,1654585200"; d="scan'208";a="279108533" Received: from orsmga008.jf.intel.com ([10.7.209.65]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 15 Sep 2022 07:13:06 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.93,318,1654585200"; d="scan'208";a="647839954" Received: from fmsmsx602.amr.corp.intel.com ([10.18.126.82]) by orsmga008.jf.intel.com with ESMTP; 15 Sep 2022 07:13:05 -0700 Received: from fmsmsx607.amr.corp.intel.com (10.18.126.87) by fmsmsx602.amr.corp.intel.com (10.18.126.82) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Thu, 15 Sep 2022 07:13:05 -0700 Received: from fmsmsx609.amr.corp.intel.com (10.18.126.89) by fmsmsx607.amr.corp.intel.com (10.18.126.87) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Thu, 15 Sep 2022 07:13:05 -0700 Received: from fmsedg601.ED.cps.intel.com (10.1.192.135) by fmsmsx609.amr.corp.intel.com (10.18.126.89) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31 via Frontend Transport; Thu, 15 Sep 2022 07:13:05 -0700 Received: from NAM10-BN7-obe.outbound.protection.outlook.com (104.47.70.105) by edgegateway.intel.com (192.55.55.70) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2375.31; Thu, 15 Sep 2022 07:13:04 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=ZIJBspenZvayGnzXzwHrqP8JFLkZ45z9fZ5Jqu8sDEg0GoNAecYAQDfoULBXY8Bh7+/kOa9iF3eGJ5UiWzW7ZwKgak1a1i+SsYsjD4B0VCjH9oJE3k9/+2wbr/0kq53qBgxeyj6PqiPPDQ46Q3F+SDj8iWE24b6FfF+cJTtE964vzNBCdBiHsRo7MlSSUDSUt+EdGIIjAGrOWAnVvVpeb9rEileaSFBrkZ7YZqCLBxrAsWpo4je8MeQG7B8v+OxRw9fnq/cGEMzE2RUgAfrHU2/ek3WYQMtDgOTMRUtvaK0Brv0rPS/CEXJcp7uOHp/8V9+Z2JdFuLtSNqeDMn/PTQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=IzfZaEul0RcNCW9GiWvQ2CkJKUTyd9g1Plz1ueXzvv8=; b=MmlqokowUtGuu68kRN9Va7eW1WC7Yk1GBnle3lgq6gnFauI0wgf18UMnOQRHzlGD6cF2oRN2WWxQGEVNHBcu6vcRfP5y/8gBCkscCbyiQHeKR/MaLFuxdXBSEM1/Q173zJdwUTLEK+OH6rvCajxCzxxlHIQFmYUM2IatS3cp1TDmDBK2NrgvzUW2Zs+oEvvFIf2JZbJM3wkXbBRWgQEXJ1sccpVjfsLSjdLauiju9xZuZRjQi3uepG2MJ/vrYUmJAI5iV6+seWY9YfKqOzlTELx77QYfCS9ytLdqmYzbaKErLBssDUy/zVwULmQFEi+SqSEi07q/wLfvXKCZw7xMBw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none Authentication-Results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=intel.com; Received: from MWHPR11MB1629.namprd11.prod.outlook.com (2603:10b6:301:d::21) by LV2PR11MB6022.namprd11.prod.outlook.com (2603:10b6:408:17c::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5612.22; Thu, 15 Sep 2022 14:13:02 +0000 Received: from MWHPR11MB1629.namprd11.prod.outlook.com ([fe80::13c:8120:d994:16d2]) by MWHPR11MB1629.namprd11.prod.outlook.com ([fe80::13c:8120:d994:16d2%6]) with mapi id 15.20.5612.022; Thu, 15 Sep 2022 14:13:02 +0000 Date: Thu, 15 Sep 2022 15:12:52 +0100 From: Bruce Richardson To: Leyi Rong CC: , , , , , , Subject: Re: [PATCH v4 1/2] member: implement NitroSketch mode Message-ID: References: <20220810074518.1695013-1-leyi.rong@intel.com> <20220915130342.1497512-1-leyi.rong@intel.com> <20220915130342.1497512-2-leyi.rong@intel.com> Content-Type: text/plain; charset="us-ascii" Content-Disposition: inline In-Reply-To: <20220915130342.1497512-2-leyi.rong@intel.com> X-ClientProxiedBy: LO4P265CA0082.GBRP265.PROD.OUTLOOK.COM (2603:10a6:600:2bd::15) To MWHPR11MB1629.namprd11.prod.outlook.com (2603:10b6:301:d::21) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: MWHPR11MB1629:EE_|LV2PR11MB6022:EE_ X-MS-Office365-Filtering-Correlation-Id: 50610677-d438-404c-ec71-08da9724668e X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: YSAOTfPnoKOWratO/FzPyKhHCuwl8+t/CZbrRD7OWRSDM0h0CR8nCgphUcVTuoPt3SlCg7EPCLG6IvwUZVrs03dgczKJ8U6Vr5ESl72D5REim4bem50G9ZYoa0y+sCs5hR0OXGayGvnnKNhbz4heLrddSfH7D02dNeeoZyOpQ7I0KXzGethWKm98tMNYLLSV8HMbmFHy3vP1KmJPEjHr4QZoaFj5bVU9KEghATLh4tH9nkdAhlkMoJKkhUnahyIrpnFrf+rrf7loN44cYGauBzkE7gIzvss6MUO8JfYFFpdGIke2Lw2gjWNbIFhCz1WNxDUO4GJQ3+ejZvb4DIC0KfR9AbliGwMGYRdrTmvq++DyvrKMplAUTckcMwnaWwQzB7qu/08YxV3gVzsKUKetjBzvMeaz0PmZ6cIY9s7feEVjfftpuy2ectAdzP8v+7VQ+epyxvFeFTiefxJgzT9BfZtkfHOsV7qupmRQcoj4ar/dMK7pUUcAkx33BlJ3llJQETCLLRxIyQA4wwooNnr3lqkZFHsZ2BTe+TFmADIDR2B5o8AUERPZxQfkZ1LMlQSc9gV64O79+GCZbZC4Zbp3Y5V5z60npuW+q48nneZYvhO4JkrLW6nRFGM2M9gyMcqUQCDZZN8HRGSXEBQsroZqTW/nvf2ld2MKw5XIOzBohiBosAALGiD0sPz3m5aXFMqOte4evZqnQavPUDB/kV1iiOK3iPijCRS2G3Cb28RS3TA= X-Forefront-Antispam-Report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MWHPR11MB1629.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230022)(396003)(39860400002)(366004)(346002)(136003)(376002)(451199015)(316002)(6486002)(83380400001)(966005)(6636002)(6506007)(478600001)(6512007)(38100700002)(86362001)(4326008)(44832011)(26005)(8936002)(6862004)(8676002)(82960400001)(66556008)(66946007)(5660300002)(66476007)(6666004)(41300700001)(2906002)(186003); DIR:OUT; SFP:1102; X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1 X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?AG/YCSUoiV/sXyyJ8KoSbcLPmb9zs0p1xIOVwA+VhoWm3wAxbyYm95KB0dRt?= =?us-ascii?Q?V5jM0kvPA1jeR1w+Qw6Kw4Q4xuGInSWYIw0N+wHH80iE2KbwHV+GfV4XEWMt?= =?us-ascii?Q?hzX1bMsXqILBXTOWk8YassV75HRTLrfZFFce4y4nhQABJQcY+T+Nj115R+M4?= =?us-ascii?Q?R1DatXIVTuHag5ugzNM+6Ptv+InnEmj/s1/PmkGSBw8otQ5VQGhccEUH2OVZ?= =?us-ascii?Q?aSrV4sfsQgpvadK8BYM39e0ANvNUHya+8OveV8j3litA6TkZdFC3IyK26lx/?= =?us-ascii?Q?l8ue15X3GFJRdngq3rtFHKYrPplMTC0Pd2FEcyXIgR3T69ZvvU6+4NoElp0G?= =?us-ascii?Q?HgK3MU7Ol0YagZCZH2Ad1ouQBmH+ozXUrcpvwnFBiGE+sNKqXfhLsAmBf/yY?= =?us-ascii?Q?3qUbuWpbzJsa0b0YXrKqsjFEvSTjJXuJH/KwOJAl0kT1Olnqopl1JBqKZAh5?= =?us-ascii?Q?vT60d9G3xw1a3Nx+2pzDCG+epaVLAuspVKQU/iz5W8YpC4Kd+93RbpCea5nO?= =?us-ascii?Q?KeN14qNa7Ax5UzMwnQ1q4k+B38ayrLrRJCFknSmuZKEFYiNdIQM7s6Hwrcvr?= =?us-ascii?Q?QwxJ/QSpdIhCVAM83sW7Jp//C5o13+hjCOLVZXqOoUso09sdxb+NZz0pZphw?= =?us-ascii?Q?SZ6mjJbUi4ryA+jIrEi+9MYgRfH8s9igTauZYipldl7Ug3lZVknDgGdIX6mn?= =?us-ascii?Q?PsAkixdn4lDNbDipr5SCvsTk3jViLkKsheA1xHwWrgHyv6jApb6/RsQwUhJp?= =?us-ascii?Q?ch6RevF/5/91IOxhnGA5PHfbMyQgUkiDNtb1OXkkVk+jSxq0Fu9cb3+tqavR?= =?us-ascii?Q?/Vuctrd3S1d6GMalgDZXsRG8ud09JrTdGA7/W4pEHcLDRfNclw3IpestsQa1?= =?us-ascii?Q?X4ARIFgGr6JpOR9GkwR9yZRWhb8mMnUOILVYNj39eVfkRe/NuZoxDQN29KEB?= =?us-ascii?Q?3BcaNpU/0kr+ft8bhUcAumg80VEhtWHCPsrcmEr0+8+t3MVHPhHRtsUaTrRY?= =?us-ascii?Q?o4xniTXfmkUPsRk5PNCRiWDQe4NqSyhXci7LCg11cxOXW/iEInNnuNV/DTBU?= =?us-ascii?Q?UtD8kbWGPzHmgNaIRxpUiq13HPngzCtfnWDAdOEA6LlsGrYT9A9cebqFMlDi?= =?us-ascii?Q?du5nsYPqZKQoKgs3k3ohH2N1zUa0Nmk6XiP/hKhJPi52enjc6ANWXeDM/Q5v?= =?us-ascii?Q?IpG3z9tTNPKadSd54woqXR+MQNuU7uw1nkbz4ukvHkxxtcsetQFqdR6CO+6j?= =?us-ascii?Q?6WtqumCc0pkHI7SppfyJD8AnSiI7bSOVl4Uc0vQxBzqjv6ac5AQYAbuKa3f0?= =?us-ascii?Q?nImpRudxS3uGV8UGUvjaFrr+hThSELz1PEWMucAO3+UTabA+coWuuOps1z5h?= =?us-ascii?Q?Jm3fyQ90GKKMkzKielxVXZRciM4ndWzPzXiaVY4i9y8t+0D+i0jvgX3clGL3?= =?us-ascii?Q?WL8kD+V7RZdbgD8Z8mruZbtJn1534lHWDmpvulwR6rJkCPrvXHrnmIY6FsXg?= =?us-ascii?Q?+LbeLSyPAOdUsBBzwZ3vHTKnkMTM0kUHR9+CWF0ESwDqBPGHwHGiCm+7s2Fk?= =?us-ascii?Q?2B3ed8bGNFBetzdQeqeOlfXpgflRD3G4Ho+aPiAa1tBuUoAGL7aGHfVXfuGc?= =?us-ascii?Q?Yw=3D=3D?= X-MS-Exchange-CrossTenant-Network-Message-Id: 50610677-d438-404c-ec71-08da9724668e X-MS-Exchange-CrossTenant-AuthSource: MWHPR11MB1629.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-OriginalArrivalTime: 15 Sep 2022 14:13:02.4574 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-MailboxType: HOSTED X-MS-Exchange-CrossTenant-UserPrincipalName: 6/YkXmUjy1P2vGBUvJTvPspNwStdhQ9dH4plbDxe/Vun8Xkw+WlowNkahl0i40UDzMBQ67r2Qh0tU0r+tTofpIt902OZw6fQ1SQfm+rNEtk= X-MS-Exchange-Transport-CrossTenantHeadersStamped: LV2PR11MB6022 X-OriginatorOrg: intel.com X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org On Thu, Sep 15, 2022 at 09:03:41PM +0800, Leyi Rong wrote: > Sketching algorithm provide high-fidelity approximate measurements and > appears as a promising alternative to traditional approaches such as > packet sampling. > > NitroSketch [1] is a software sketching framework that optimizes > performance, provides accuracy guarantees, and supports a variety of > sketches. > > This commit adds a new data structure called sketch into > membership library. This new data structure is an efficient > way to profile the traffic for heavy hitters. Also use min-heap > structure to maintain the top-k flow keys. > > [1] Zaoxing Liu, Ran Ben-Basat, Gil Einziger, Yaron Kassner, Vladimir > Braverman, Roy Friedman, Vyas Sekar, "NitroSketch: Robust and General > Sketch-based Monitoring in Software Switches", in ACM SIGCOMM 2019. > https://dl.acm.org/doi/pdf/10.1145/3341302.3342076 > > Signed-off-by: Alan Liu > Signed-off-by: Yipeng Wang > Signed-off-by: Leyi Rong > --- Couple of comments below on the meson.build file. /Bruce > lib/member/meson.build | 42 +- > lib/member/rte_member.c | 75 ++++ > lib/member/rte_member.h | 154 ++++++- > lib/member/rte_member_heap.h | 424 ++++++++++++++++++ > lib/member/rte_member_sketch.c | 594 ++++++++++++++++++++++++++ > lib/member/rte_member_sketch.h | 97 +++++ > lib/member/rte_member_sketch_avx512.c | 70 +++ > lib/member/rte_member_sketch_avx512.h | 35 ++ > lib/member/rte_xxh64_avx512.h | 117 +++++ > lib/member/version.map | 9 + > 10 files changed, 1613 insertions(+), 4 deletions(-) > create mode 100644 lib/member/rte_member_heap.h > create mode 100644 lib/member/rte_member_sketch.c > create mode 100644 lib/member/rte_member_sketch.h > create mode 100644 lib/member/rte_member_sketch_avx512.c > create mode 100644 lib/member/rte_member_sketch_avx512.h > create mode 100644 lib/member/rte_xxh64_avx512.h > > diff --git a/lib/member/meson.build b/lib/member/meson.build > index e06fddc240..3df0fbc7a6 100644 > --- a/lib/member/meson.build > +++ b/lib/member/meson.build > @@ -7,6 +7,46 @@ if is_windows > subdir_done() > endif > > -sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c') > +sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c', 'rte_member_sketch.c') At this point, with 4 entries I'd suggest reworking this to a vertical list. sources = files( 'rte_member.c', .... ) > headers = files('rte_member.h') > deps += ['hash'] > +includes += include_directories('../hash', '../ring') > + Use dependencies rather than include-paths. Having a dependency on hash means that your code will be compiled with the hash include paths already present. Similarly you can add "ring" to the deps variable and drop this line. > +# compile AVX512 version if: > +# we are building 64-bit binary AND binutils can generate proper code I think this comment is no longer necessary. The condition itself is clear. The following comment can be kept though as it explains what is being done at a higher level than the code. > +if dpdk_conf.has('RTE_ARCH_X86_64') and binutils_ok > + # compile AVX512 version if either: > + # a. we have AVX512 supported in minimum instruction set > + # baseline > + # b. it's not minimum instruction set, but supported by > + # compiler > + # > + # in former case, just add avx512 C file to files list > + # in latter case, compile c file to static lib, using correct > + # compiler flags, and then have the .o file from static lib > + # linked into main lib. > + > + #check if all required flags already enabled > + sketch_avx512_flags = ['__AVX512F__', '__AVX512DQ__', '__AVX512IFMA__'] > + > + sketch_avx512_on = true > + foreach f:sketch_avx512_flags > + if cc.get_define(f, args: machine_args) == '' > + sketch_avx512_on = false > + endif > + endforeach > + > + if sketch_avx512_on == true > + cflags += ['-DCC_AVX512_SUPPORT'] > + sources += files('rte_member_sketch_avx512.c') > + elif cc.has_multi_arguments('-mavx512f', '-mavx512dq', '-mavx512ifma') > + sketch_avx512_tmp = static_library('sketch_avx512_tmp', > + 'rte_member_sketch_avx512.c', > + include_directories: includes, > + dependencies: static_rte_eal, > + c_args: cflags + > + ['-mavx512f', '-mavx512dq', '-mavx512ifma']) > + objs += sketch_avx512_tmp.extract_objects('rte_member_sketch_avx512.c') > + cflags += ['-DCC_AVX512_SUPPORT'] Logic looks correct here now, but beware of your indentation. You are mixing tabs and spaces. Meson files should have spaces only, no tabs. > + endif > +endif