From patchwork Sun Aug 12 15:57:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tal Bar X-Patchwork-Id: 10563757 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 77347139A for ; Sun, 12 Aug 2018 20:38:47 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 54F9129044 for ; Sun, 12 Aug 2018 20:38:47 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 486D629073; Sun, 12 Aug 2018 20:38:47 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=2.0 tests=BAD_ENC_HEADER,BAYES_00, DKIM_SIGNED,MAILING_LIST_MULTI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.ozlabs.org (lists.ozlabs.org [203.11.71.2]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 18FD329044 for ; Sun, 12 Aug 2018 20:38:42 +0000 (UTC) Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 41pW0c1bNtzF0WK for ; Mon, 13 Aug 2018 06:38:40 +1000 (AEST) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="fXmsnjm8"; dkim-atps=neutral X-Original-To: linux-mlxsw@lists.ozlabs.org Delivered-To: linux-mlxsw@lists.ozlabs.org Authentication-Results: lists.ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=mellanox.com (client-ip=40.107.5.59; helo=eur03-ve1-obe.outbound.protection.outlook.com; envelope-from=talb@mellanox.com; receiver=) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="fXmsnjm8"; dkim-atps=neutral Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50059.outbound.protection.outlook.com [40.107.5.59]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 41pVzz0fs5zF0Qs for ; Mon, 13 Aug 2018 06:38:06 +1000 (AEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Mellanox.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=deX/8myK9bvxCyOTuj/mDNxhSfID5+/4XKDMntYW5wA=; b=fXmsnjm8vU4//JAWPT/cZMA0QDI0xlETY6z5gMB1KsBtA4y9If9I/rSQ3z52Io9txQhvbos3WncrXQcTN84pnZUToyIvQRMLBIrs+F+Gc3XiHvFuo1joyxKCfKOMfQ8F/7s10aE/AJjfD/HuNwvKCN1uuSvXyxIxyBXudWd0r5Y= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=talb@mellanox.com; Received: from dev-r-vrt-156.mtr.labs.mlnx (37.142.13.130) by DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1038.19; Sun, 12 Aug 2018 15:57:41 +0000 From: Tal Bar To: idosch@mellanox.com, jiri@mellanox.com Subject: [net-next mlxsw v10 1/3] lib: Introduce manager for priority base pruning lookups between tables Date: Sun, 12 Aug 2018 18:57:19 +0300 Message-Id: <1534089441-20653-2-git-send-email-talb@mellanox.com> X-Mailer: git-send-email 2.8.0 In-Reply-To: <1534089441-20653-1-git-send-email-talb@mellanox.com> References: <1534089441-20653-1-git-send-email-talb@mellanox.com> MIME-Version: 1.0 X-Originating-IP: [37.142.13.130] X-ClientProxiedBy: AM4PR05CA0001.eurprd05.prod.outlook.com (2603:10a6:205::14) To DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 8bce3899-8003-442a-8948-08d6006c5637 X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989117)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:DB6PR05MB3287; X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 3:IivhiKnZaGJLoy1C4iEy2vjiUj0/XrWePQBhBaTh4HD12/wJtJv9zHJL15EKwSBXNYz7WAGAczAJPxMDRCSlWdVC+PocLG05XSniwzEfxBGioClFxk+z+EY9gRXv5ni+kIObuAmQQ/YIkiqC1D3yjV5GrmBT+bUj6uHu2+dd7g4duFEU2Y97iI1jz3AhqwLvqPjMdotURlgIsn0h/bfEUxZ3QgW+W6Elo88fta9BbhoOU7SsnIllXmZ8Yg4Gt2io; 25:uBZKMNG/ScDL11b9pqcUnNmQCT5TExIObuFQmjirk09C9r/qS5ljLtT8+xEU3bgacMLcPMnJFsJ5VQ2WcI9Xac2G6trOdFzH7uZtq4QD774H5lv9PZ0zVnS30DFug/dra4DoX7W5NPR2mpTZzwxaed9zkZLJTgTYUUceiQZCIMdfgOiVEH89gS7b52L7O2KeMKD7kkPZMed3WqUZC8PrKGRRTvXNrrZRofQkNsP73qdVqSEZV91NB2FMVWiPx9FdQexs2/TyUkDxxYDS9rW5zyA+97tEeKRp797YsUhCI/9eVAX1KbXrMjBs4tAXmque4rgpLGUC6Ep++55F9SdyuQ==; 31:YaU1gkIGUB5743EIh9d+mBDHYlMluX6CgGI2XI3YTWz4IicDFvSRNOY665PKSEtH0DkirigRgmDAM+5y63+7MPQvZ5BBF/2C7Qlxc7v8q79OrUP24aVxJT+/LGZr7TEY7nGmsiNKXh+VQ1Ni/BJoLRE8+diF0HNSthYobefB7a9qmFh7JVioBiIJDazR2KgEhaWfTVFWQify2+LLVi4ru0V24IrX5iJRzd8kGtP4HsY= X-MS-TrafficTypeDiagnostic: DB6PR05MB3287: X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 20:aAq60a+8QknMhej9E0WhMuOok1c3Al2fSGTPSfqvRKyIY7PTG/+S14RBGhj3eRPgd+qut0fH3ygejzCVDrsbc/Ynj7J5iqS+54xWAWDjYK0hqMY7Mk+VlC8w2UYH5cdZyQ5a9p305+ZrQNcZ1I/EEUB0XAKZ2Un1vLLKh1GhqwEOhitIkEb+wcs74ZnJPPYLuTKtS2fefiSEEad+jIFg1OnObD+wZRx55xyVsfgLsBiMU3uKiasU2lDXUdi2Xq9KYMXhA/MvLUCJbeL8Zl4mmeSI70E17ov8/fK8FHwIsAzxv98eF4Cytf1PlSjfClgthcRTV+GljBozRVZV7OzJAEbm6WugpiQOJ33fGTcreT0GcgAYRsVO/8VIGjNkyy2vflb54+wRW7Sv89VSmb1WnKYmliO6h+TnNMpfbqnBlHisZtvoi1WK+qK3swY26WkJAhKGGkOB9h02k4KBEQnENJu572AmYrlFJcEsZE4iO8O9y+q1Ys+PPxqbbhMIXPBT; 4:4tpo+6wzuznhv6VpAehwLSUJ8txBrdkKVjMWpETqfLN3bkh7vWTLy2wkjd59oWGWCHhPBTr/MEr4acxcH2RvYcoDs1sTeRO65G+TzhYXF3Pv7NVJ6rtbshhl1SeYjy5JHG1Qib5xT+axIXqL1YJRBm6IHwTUAkIlvfxVahvM5jJxH0qrB26othHlRvKf63Oa4d74J7UUFUDWKA9oDMHXH6EPazYX8ycviJ6g4QQBStxLmjsMhJcsi/KDbYNYSVHAjy2X932sVOz5CDAfzeNwWbsen4hag2RWuhR2SeF5I2ZyfVMm7VBOZI7sL69qAP8A X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(9452136761055); X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(10201501046)(3231311)(944501410)(52105095)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123564045)(20161123558120)(20161123560045)(6072148)(201708071742011)(7699016); SRVR:DB6PR05MB3287; BCL:0; PCL:0; RULEID:; SRVR:DB6PR05MB3287; X-Forefront-PRVS: 0762FFD075 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(396003)(346002)(376002)(136003)(366004)(39860400002)(199004)(189003)(6512007)(53946003)(6636002)(2616005)(19627235002)(16200700003)(50226002)(6506007)(45954006)(386003)(81166006)(81156014)(53936002)(956004)(6116002)(68736007)(575784001)(8676002)(86362001)(8936002)(6486002)(2906002)(3846002)(11346002)(14444005)(5660300001)(16526019)(52116002)(106356001)(50466002)(48376002)(47776003)(66066001)(25786009)(36756003)(316002)(16586007)(305945005)(4326008)(6666003)(26005)(7736002)(476003)(478600001)(105586002)(85306007)(446003)(107886003)(486006)(76176011)(51416003)(97736004)(569006); DIR:OUT; SFP:1101; SCL:1; SRVR:DB6PR05MB3287; H:dev-r-vrt-156.mtr.labs.mlnx; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; Received-SPF: None (protection.outlook.com: mellanox.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; DB6PR05MB3287; 23:E49WOgqKPKdQatcv1o88n//tKg6mQbMl9d3+SImcE?= 6C/QofdHtmeFboEeueEl/Rn0gs0iwZOFimzakwXx0OTqMwD3TSIBVv63COgydlKTm2j0DwTL+XhF9/n3qodMFhFY09s5HKQFv+HHdHHVaEDVlv7tOXvfxfjV/cY9N8E9el0mfyksI7lJnixgMdKEMHE3pl9QtcnjCeQeqUnHFQyTajjtteivUB+GBpnAosNv4EAhNx1XiaC60ftC2qR4mSYinD4ub3SJ7Ks0IjgoMaaopCsK8aTsClDE0DKcwSwbEK2SWcRebklWM0ydJapYDXMBYm6EA/rWq6YTwDeoxJqT9v6kUXZJHnkBpQWvRfqWz7MVh/QieavyF/MRCr1N91uHCwiMWvtOMT3Hw7rdv+t61bGCyyAttRZCoNTaaKpMaG0Xs8v8SChTqGkYxCpvDCSmOz6H1vvYP3EfHZlf34iPvulPMV6x1+3a+IOd9N/A5EaE5xzzlsTkgHOU5bJlmbIq9MBXsq6jpaHe3F1bnTbNnxyQ3UF9w1r0kL6pyB94e9vksWQh2kZbPA6l1DSyuLjYNT+jtTjDgscyXU7M0OtWxwdldwCrWCFnhXVfhF6QFAShXnmI3zr2F0F3SJlRMZeD9OJjbmAEGtHemlu0xeRt+ZgNByPETgyRXFkaVE6mtwPR4JTJcYNDV7y0T7+HzBB5HuEAn+4+fkx7ibDN1VwsjZt7M2dEGiLlx0lCLGOmzWqvUgROWpgIr0EAQYdAY7CwoAoPe89Xkxt27dcb10EUsL4yzLljIbCcEMfdAPKXTmII+O9tbexcnXH6olzo9gwn6OnmWlhZ1OrAH7XEvmTKynaXS8ekpXEIK01+APbq8fxPU7qIFjvtgE0eGhiNAytJR4j0VJi86Y1UcALDdyeE3TjLAAqSK3f8d7rADhux/POc6c+xofQKO5v3puA8YgEu72bEgAlJgnocj/c9n/pu4l+fPmeG4n6J8wu48oeLtIr0lzB7t6/nboObddScSpcy+HAWluURouZMYC92HAgKwtWKFVNXCFf8D43CYcb1XDQZcYG9k6JrvipjtWCxUEscrsCjUCHv//htH0mtgexbKmPfE9kDeHqKdpfwwSfwniFftGLFpxqG0tX3u0JE07RFbovR3HQ5s56B0kWcaIkoBVoJxMpoWGfzVPDkfX5X059XdjaLadrzF50NabRqYH5xd1enEdW+ejHGcIBCs6/EW5HEpqCIdZHDRKqLIQ+FJ/W+x7GJYbvJwIpHfU7M83iWjsO9mOzt6V/SasdO0zLtvPxmGpuhTAduiGw0GqwCcfyzYRtGwgHnJzMT4lLYdjJfTr1cXhWI6XUIexg1PtOHA== X-Microsoft-Antispam-Message-Info: y//j/OLfk3hr5v6RV96PLLtANsonkbdJGQ7rXxZ+1oVrxafa+0u1v7P+gt63Pqi8JrkXB081Y/2vQ/w/eZ3xO1R+0KE5G40aXtCH3FHHL8pLS/EQ4dAjSAWhDtbOaY84gUQrDQm0POXQXbkUf8b+2VnXu9QVnDmt5v6dRUJV/qvyquR6DkxAP6gJ3xg+AhEFIprhy4cxIQ+eB4AbvY4SFcFezhkPtvWcBlzg5oORbxeLALd9DnWxBWjaa4ehuWnN+2oEd/Wv2mCJaSNUjH7LPXMbQSasVtna4iQosHIXBm3sobMhMSr22+2/l2xKYvnHLDByJMZLzUeCfVLXWthUqyxzr42rFEsGf2nm9BN5jNs= X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 6:7KsAUGVKYYB32Cjdc+UcQKoigEKAIzIKny9slBllQ9PG6AApPvDlWBtdH9UZmWZQ9Avxv4+MJJkhKiG8EMk8QIkvzrIC13kSyRy4RC/X80Q3Q7wsaZn6zdG3NalzTYvoLhIE0w9fl2CY0TOH/JfKvlumstGyL6B87dF3JzPBnv7r7l+Ck9hamfjONo2LiCW31432bNYzN/90WhEFnk5KC4O10LyZjNhC0i8IpGGZD2w2buZxhZOSsX4TSqIe6OO38wJQd8YU7FKlMAbYEpY/LvsFuMG52wJVGAgEifZQbfi2YYQ7IVldRmTxlBmejyg2btcLsvxMcNQslmbjf93iuRypFgnN1gSCLcqKO6BUEeMAMjlrIcXcn+l/IV1u0P3xfSZXk373vqnpqHu71/igPEsKfRLulw8RzSi75VaYq3Kyw3XJstuH3Zx0IVaO3uRUHd5NDJAz3eS9ucW3txP2eg==; 5:INRdgXADEd58MJOTs7hyH68PvYg/3HhBpC7/OmJ/I26HMz4KWtlQwjXV3hKFWDGIfsBojduCk34CLfsG2VEXmBMNDe2CwF3AIgF9XBSgao5WKPLl/xOoh8fQjFNZiQUL3yPNh300EwWY6AcQPnekjlbxb4ViPYIJOafsorlAjuk=; 7:YlA4kCjQx0qwwJJ1rmtF6+AH2ToRV8HjNkLg//jgtI9Tys++379xqlXnGe4EmBtJu9qyjEOkTv5LuQHpq2yVYzq6TqJkaHPlL3kjafbPK0Lxw7H3P2fn1TV0AVeyQJTDFJAuaTwKPfknJWH4a9g8KP0PlE4ekIT6LHg3mR/5KLzT2LmYJK5Plk9/2gfpEvB1ygcTInK0ckCiHNmct354m3+Ogmfta/jC0lIrRa/MFqMeilMTQr/ArEXemKJa4M9M SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: Mellanox.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Aug 2018 15:57:41.3716 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 8bce3899-8003-442a-8948-08d6006c5637 X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: a652971c-7d2e-4d9b-a6a4-d149256f461b X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR05MB3287 X-BeenThere: linux-mlxsw@lists.ozlabs.org X-Mailman-Version: 2.1.27 Precedence: list List-Id: mlxsw driver development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-internal@mellanox.com Errors-To: linux-mlxsw-bounces+patchwork-linux-mlxsw=patchwork.kernel.org@lists.ozlabs.org X-Virus-Scanned: ClamAV using ClamSMTP An object (e.g. packet) needs to be evaluated against a data base of prune items (represented by {key, mask, priority}), so that the matching item with the highest priority is selected to continue processing the object. Items with different masks are stored in different tables. One way to find this item is to perform multiple (on all the tables) exact match lookups, each with a different mask. It is possible to reduce the number of lookups by pruning tables where we know that an higher priority match does not exist. The prune library aim: reduce number of lookups (by prune) between tables within same prune items set (The prune object). As mentioned above pruning saves time complexity by doing lookups only on the relevant tables, this eliminates the need to search for exact match in other tables based on item priority and mask. In order to achieve this goal the prune library: 1. Maintain a prune vector for each item. 2. Calculate the prune vector of an inserted item i to table x and the prune vector of an affected items by this rule. If there is a matching item j in other table z with lower priority item, item i set to prune table z (e.g. no need for further lookups). Since item j was pruning table x the prune library also calculate item j prune vector not to prune table x. For further details please check: Documentation/prune.txt Alongside this, a testing module is introduced as well. Signed-off-by: Tal Bar --- Documentation/00-INDEX | 2 + Documentation/prune.rst | 445 +++++++++++++++ MAINTAINERS | 8 + include/linux/prune.h | 83 +++ lib/Kconfig | 8 +- lib/Kconfig.debug | 10 + lib/Makefile | 3 + lib/prune.c | 1445 +++++++++++++++++++++++++++++++++++++++++++++++ lib/test_prune.c | 1214 +++++++++++++++++++++++++++++++++++++++ 9 files changed, 3217 insertions(+), 1 deletion(-) create mode 100644 Documentation/prune.rst create mode 100644 include/linux/prune.h create mode 100644 lib/prune.c create mode 100644 lib/test_prune.c diff --git a/Documentation/00-INDEX b/Documentation/00-INDEX index 2754fe8..ccd6cd8 100644 --- a/Documentation/00-INDEX +++ b/Documentation/00-INDEX @@ -326,6 +326,8 @@ preempt-locking.txt - info on locking under a preemptive kernel. process/ - how to work with the mainline kernel development process. +prune/ + - info on what prune aim, why and when to use it. pps/ - directory with information on the pulse-per-second support pti/ diff --git a/Documentation/prune.rst b/Documentation/prune.rst new file mode 100644 index 0000000..6445a45 --- /dev/null +++ b/Documentation/prune.rst @@ -0,0 +1,445 @@ +===== +Prune +===== + +Prune is a library which determines which table needs to be searched. +The user can create tables with specific masks. The tables contain items with +a bit field key and priority. Since similar items can be inserted to different +tables, there is a need to prune between the tables. +Pruning saves time complexity so that there won't be any need to search (lookup) +in other tables. + +Database +======== +Each prune object has a list of tables with mask. +The mask is a property of the table which determines which item can be add to it. +Each table consists of: + +- List of items, each item having its own prune vector. +- List of the corresponding intersection tables (with other tables) with mask. + The intersection mask is equal to the mask of table x which intersects with + the mask of table z. + +Each intersection table consists of: + +- Hash table for intersecting entries +- Each entry contain two lists: + - Items of the table owner (my items). + - Items of other tables (neighbor items) in the prune object. + +Prune Calculation Algorithm +=========================== +As previously explained, each item has a prune-vector +which consists of a table identifier and its prune decision on this table +(i.e. should we perform lookup on this table). + +A single operation of adding or removing an item from a table may affect other +items in other tables (i.e. compatible-item). + +Inserting Item 'R' to Table 'T' +-------------------------------- +1) Calculate item 'R' prune vector. + Iterate over all the intersection tables of table 'T' and for each table: + + a) Intersect 'R' key with intersection table mask and use it as a key into the intersection table's hash table to retrieve entry 'I'. + b) In 'I' iterate on neighbor items, for each item 'K' with lower priority number (higher priority) than 'R', set the prune decision not to prune the table which 'K' belongs to within the prune vector of 'R'. + c) Add entry for 'R' under my items. + d) Return the updated prune vector of 'R'. + +2) Calculate the prune-vector of all compatible items in the other tables. + Iterate over all the tables in the prune object (besides 'T'). for each table 'Y' find the intersection table which intersects between 'T' and 'Y': + + a) Intersect 'R' key with intersection table mask and use it as key into the intersection table's hash table to retrieve entry 'I'. + b) Add entry for 'R' under neighbor items of 'I'. + c) Iterate on my items for each item 'K' with higher priority number (lower priority) than 'R', set the prune decision not to prune the table which 'R' belongs to. + d) Send notification with these specific changes. + +Deleting Item 'R' from Table 'T' +--------------------------------- +1) Remove item 'R' from table 'T' and its references from all intersection tables. + Iterate over all intersection tables of 'T' and for each table 'Y': + + a) Intersect 'R' key with intersection table mask and use it as a key into the intersection table's hash table to retrieve entry 'I'. + b) Remove 'R' from my items. If my items and neighbor items are empty remove entry 'I' from the intersection table. + +2) Calculate the prune-vector of all compatible items in the other tables. + Iterate over all tables in the prune object (besides 'T'). for each table 'Y' find the intersection table which intersects between 'Y' and 'T': + + a) Intersect 'R' key with intersection table mask and use it as a key into the intersection table's hash table to retrieve entry 'I'. + b) In 'I' remove item 'R' from neighbor items. + c) Iterate on my items in entry 'I', for each item 'K' check if there isn't any item 'J' under neighbor items with better priority. Set 'K' item to prune item 'R' table -> 'T'. + d) Send notification with these specific changes. + +Functional Example +------------------- +Legend: +~~~~~~~ +- y^z: Donates to intersection between table 'y' and 'z' where 'y' is the main table. +- [{--R: Calculate my own prune vector +R->K: Calculate other items (K) prune vector in the prune object + +Insert item 'R' +~~~~~~~~~~~~~~~~ +- R->R: Insert an item 'R' to a table, calculate its own prune-vector. +- R->K: 'R' is inserted to a table, and we have to calculate the prune-vectors of other compatible items (in different tables). + +Removing item 'R' +~~~~~~~~~~~~~~~~~~ +- R->K: 'R' is removed from a table, this might impact the prune-vectors of other compatible items (in different tables). + +Adding table 'T' +~~~~~~~~~~~~~~~~~~ +- By adding table 'T' to the prune object, prune vector item should be added to the prune-vector of all the items in the prune object. + +Remove table 'T' +~~~~~~~~~~~~~~~~~ + - By removing table 'T' from the prune object, prune vector item should be removed from the prune-vector of all the items in the prune object. diff --git a/MAINTAINERS b/MAINTAINERS index 38f4438..fd1dae2 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -11504,6 +11504,14 @@ F: include/linux/sysctl.h F: kernel/sysctl.c F: tools/testing/selftests/sysctl/ +PRUNE +M: Tal Bar +L: netdev@vger.kernel.org +S: Supported +F: lib/prune.c +F: lib/test_prune.c +F: include/linux/prune.h + PS3 NETWORK SUPPORT M: Geoff Levand L: netdev@vger.kernel.org diff --git a/include/linux/prune.h b/include/linux/prune.h new file mode 100644 index 0000000..4334dc9 --- /dev/null +++ b/include/linux/prune.h @@ -0,0 +1,83 @@ +/* SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause */ +/* + * include/linux/prune.h - Manager for priority based pruning lookups + * between tables. + * Copyright (c) 2018 Mellanox Technologies. All rights reserved. + */ + +#ifndef _PRUNE_H +#define _PRUNE_H + +struct prune_table; +struct prune; + +/** + * struct prune_item - holds the configured item settings. + * @key: Pointer to bitmap. + * @priv: Pointer to user data. + * @table: Table which the item belongs to. + * @list: A node in prune_item_notify_list. + * @priority: Lower number means higher priority. + * + * This structure returned in case of change in the item prune_vector. + * User can retrieve the prune_vector using this structure. + */ +struct prune_item { + unsigned long *key; + void *priv; + struct prune_table *table; + struct list_head list; + unsigned int priority; +}; + +/** + * struct prune_vector_item - Define if a table should be prune or not. + * @table: The table which should be pruned. + * @list: Node in the item prune vector. + * @pruned: True if the item is pruning this table. + * + * This structure used as a node of the item prune_vector. + */ +struct prune_vector_item { + struct prune_table *table; + struct list_head list; + bool pruned; +}; + +/** + * struct prune_ops - Define the management hooks for prune object. + * + * @prune_item_notify: Called if there is a change in a the prune vector of an + * item or items, the notification can be sent on one item + * or more. + * @prune_item_notify.prune_item_notify_list: A list of prune_item structs + * (read-only)which their pruned + * vector has been changed with + * {table,pruned} attributes below. + * @prune_item_notify.table: The table which should be pruned. + * @prune_item_notify.pruned: True if the item prune the table. + * + * The table and the decision to be pruned or not is equal across all + * items in the notification list. + */ +struct prune_ops { + void (*prune_item_notify)(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned); +}; + +struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops, + void *priv); +void prune_destroy(struct prune *prune); +struct prune_table *prune_table_create(struct prune *prune, unsigned long *mask, + unsigned int mask_len, void *priv); +int prune_table_destroy(struct prune_table *table); +struct prune_item *prune_item_create(struct prune *prune, + struct prune_table *table, + unsigned long priority, + unsigned long *key, + void *priv, + bool *non_def_prune_vector); +int prune_item_destroy(struct prune_item *item); +void *prune_table_priv(struct prune_table *table); +struct list_head *prune_item_prune_vector(struct prune_item *item); +#endif diff --git a/lib/Kconfig b/lib/Kconfig index 706836e..0c408b7 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -308,7 +308,7 @@ config GENERIC_ALLOCATOR # config REED_SOLOMON tristate - + config REED_SOLOMON_ENC8 bool @@ -592,6 +592,12 @@ config PARMAN config PRIME_NUMBERS tristate +config PRUNE + tristate "prune" + help + This option enables the use of prune manager library for priority + based pruning lookups between tables. + config STRING_SELFTEST tristate "Test string functions" diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index d3d82ec..fc697ee 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1844,6 +1844,16 @@ config TEST_PARMAN If unsure, say N. +config TEST_PRUNE + tristate "Perform selftest on pruning tables manager" + default n + depends on PRUNE + help + Enable this option to test pruning tables manager + (or module load). + + If unsure, say N. + config TEST_LKM tristate "Test module loading with 'hello world' module" default n diff --git a/lib/Makefile b/lib/Makefile index 60d0d5f..40e826c 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -70,6 +70,7 @@ obj-$(CONFIG_TEST_UUID) += test_uuid.o obj-$(CONFIG_TEST_PARMAN) += test_parman.o obj-$(CONFIG_TEST_KMOD) += test_kmod.o obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o +obj-$(CONFIG_TEST_PRUNE) += test_prune.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG @@ -251,6 +252,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o obj-$(CONFIG_PARMAN) += parman.o +obj-$(CONFIG_PRUNE) += prune.o + # GCC library routines obj-$(CONFIG_GENERIC_LIB_ASHLDI3) += ashldi3.o obj-$(CONFIG_GENERIC_LIB_ASHRDI3) += ashrdi3.o diff --git a/lib/prune.c b/lib/prune.c new file mode 100644 index 0000000..58e6f78 --- /dev/null +++ b/lib/prune.c @@ -0,0 +1,1445 @@ +// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause +/* + * lib/prune.c - Manager for priority based pruning lookups between tables. + * Copyright (c) 2018 Mellanox Technologies. All rights reserved. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* + * struct prune_table_entry - hold the item configuration and its prune vector. + * @prune_vector: List of struct prune_vector_item. + * @list: Node in table's entry list. + * @item: The item returned to the library user. + */ +struct prune_table_entry { + struct list_head prune_vector; + struct list_head list; + struct prune_item item; +}; + +/* + * struct prune_intersec_table_list_elem - An element in intersec_table_elem_list + * or neigh_table_elem_list. + * @entry: A pointer to an entry in the prune table. + * @list: A node in the corresponding list {intersec_, neigh_}table_elem_list. + * + * This element is used to reference prune entries from the intersection table. + */ +struct prune_intersec_table_list_elem { + struct prune_table_entry *entry; + struct list_head list; +}; + +/* + * struct prune_intersec_table - Represent the intersection of two prune tables. + * @entry_ht: Hash-table of prune_intersec_table_entry. + * @neigh_table: A pointer to the table which this table intersects. + * @list: Node of table's intersec_table_list. + * @mask: Intersection mask of the the two tables. + * + * This structure is used to find the intersection of new prune item with an + * existing one, and check whether the new item should be pruned or not. + */ +struct prune_intersec_table { + struct rhashtable entry_ht; + struct prune_table *neigh_table; + struct list_head list; + unsigned long mask[0]; + /* mask has to be always the last item */ +}; + +/* + * struct prune_intersec_table_entry - Represents an entry in intersection + * table. + * @ht_node: A node in the hash-table of the intersection + * table. + * @ht_key: The key used for the entry in the hash-table. + * created by the intersection of two prune items + * keys. + * @intersec_table: A pointer to the intersection table which owns + * this entry. + * @intersec_table_elem_list: Contain pointers of entries in prune table which + * the intersection table of this entry belongs to. + * @neigh_table_elem_list: Contain list of entries in the neighbor table + * pointed by the neigh_table field in + * prune_intersec_table struct. + * + * The structure is used to find the intersection of new prune item with the + * current one, and check whether the new item should be pruned or not. + */ +struct prune_intersec_table_entry { + struct rhash_head ht_node; + unsigned long *ht_key; + struct prune_intersec_table *intersec_table; + struct list_head intersec_table_elem_list; + struct list_head neigh_table_elem_list; +}; + +/* + * struct prune_table - Contains the prune items added by the user. + * @prune: A pointer to prune object which hold the table. + * @priv: User data. + * @entry_list: A list of prune_table_entry. + * @intersec_table_list: List of intersection tables of this table with the + * other tables in the prune object. + * @list: Node of table_list in struct prune. + * @mask: The mask given b the user. + * + * This structure used to identify the prune vector and which tables need to be + * pruned. + */ +struct prune_table { + struct prune *prune; + void *priv; + struct list_head entry_list; + struct list_head intersec_table_list; + struct list_head list; + unsigned long mask[0]; + /* mask has to be always the last item */ +}; + +/* + * struct prune - Represents the prune object. + * @ops: the operations that this prune object support. + * @intersec_tables_ht_params: hold hash table attributes of the intersection + * table. + * @table_list: A list of prune table fo this prune object. + * @priv: User data. + * @mask_len: The mask len in bits which this prune object + * support. + */ +struct prune { + const struct prune_ops *ops; + struct rhashtable_params intersec_tables_ht_params; + struct list_head table_list; + void *priv; + unsigned int mask_len; +}; + +static unsigned int +prune_intersec_table_entry_key_len(const struct prune_intersec_table_entry * + intersec_entry) +{ + return intersec_entry->intersec_table->neigh_table->prune->mask_len; +} + +static struct rhashtable_params +prune_intersec_table_entry_rht_params(struct prune_intersec_table * + intersec_table) +{ + return intersec_table->neigh_table->prune->intersec_tables_ht_params; +} + +static size_t prune_mask_size(unsigned int nbits) +{ + return BITS_TO_LONGS(nbits) * sizeof(unsigned long); +} + +static u32 prune_intersec_ht_hash(const void *data, u32 len, u32 seed) +{ + u32 jash_len = prune_mask_size(len); + const unsigned long * const *ht_key = data; + + return jhash(*ht_key, jash_len, seed); +} + +static int prune_intersec_ht_cmp(struct rhashtable_compare_arg *arg, + const void *obj) +{ + const struct prune_intersec_table_entry *intersec_entry = obj; + const unsigned long * const *ht_key = arg->key; + unsigned int key_len; + + key_len = prune_intersec_table_entry_key_len(intersec_entry); + + return !bitmap_equal(*ht_key, intersec_entry->ht_key, key_len); +} + +static struct rhashtable_params intersec_tables_ht_params = { + .key_offset = offsetof(struct prune_intersec_table_entry, ht_key), + .head_offset = offsetof(struct prune_intersec_table_entry, ht_node), + .obj_cmpfn = prune_intersec_ht_cmp, + .hashfn = prune_intersec_ht_hash, + .automatic_shrinking = true, +}; + +static void prune_table_prune_vector_fini(struct prune_table_entry *entry); + +static int prune_table_prune_vector_init(struct prune *prune, + struct prune_table_entry *entry) +{ + struct prune_table *table; + + INIT_LIST_HEAD(&entry->prune_vector); + + list_for_each_entry(table, &prune->table_list, list) { + struct prune_vector_item *vector_item; + + vector_item = kmalloc(sizeof(*vector_item), GFP_KERNEL); + if (!vector_item) { + prune_table_prune_vector_fini(entry); + return -ENOMEM; + } + vector_item->pruned = true; + vector_item->table = table; + list_add_tail(&vector_item->list, &entry->prune_vector); + } + return 0; +} + +static void prune_table_prune_vector_fini(struct prune_table_entry *entry) +{ + struct list_head *pos, *tmp; + + list_for_each_safe(pos, tmp, &entry->prune_vector) { + struct prune_vector_item *vector_item; + + vector_item = list_entry(pos, typeof(*vector_item), list); + list_del(&vector_item->list); + kfree(vector_item); + } +} + +static struct prune_table_entry * +prune_table_entry_init(struct prune *prune, unsigned long *key, + unsigned int priority, void *priv) +{ + struct prune_table_entry *entry; + int err; + + entry = kzalloc(sizeof(*entry), GFP_KERNEL); + if (!entry) + goto err_entry_alloc; + + entry->item.key = key; + entry->item.priority = priority; + entry->item.priv = priv; + + err = prune_table_prune_vector_init(prune, entry); + if (err) + goto err_vector_init; + + return entry; + +err_vector_init: + kfree(entry); +err_entry_alloc: + return NULL; +} + +static void prune_table_entry_fini(struct prune_table_entry *entry) +{ + prune_table_prune_vector_fini(entry); + kfree(entry); +} + +static bool prune_vector_item_update(const struct list_head *table_prune_list, + struct prune_table *corresponding_table, + bool is_prune) +{ + struct prune_vector_item *vector_item; + + list_for_each_entry(vector_item, table_prune_list, list) { + /* Find the corresponding prune item and set it */ + if (vector_item->table == corresponding_table && + vector_item->pruned != is_prune) { + vector_item->pruned = is_prune; + return true; + } + } + return false; +} + +static bool +prune_vector_set(struct prune_table *table, + struct prune_table *neigh_table, + const struct prune_table_entry *entry, + struct prune_intersec_table_list_elem *neigh_item, + struct prune_intersec_table_list_elem *intersec_item, + bool neigh_items) +{ + const struct list_head *prune_list; + bool not_prune; + + if (neigh_items) { + /* Should not continue pruning in case neighbor priority is + * lower (more important) then the new item + */ + not_prune = neigh_item->entry->item.priority < entry->item.priority; + + } else { + /* Should not continue pruning in case my priority is higher + * (less important) then the new item + */ + not_prune = intersec_item->entry->item.priority > entry->item.priority; + } + prune_list = neigh_items ? &entry->prune_vector : &intersec_item->entry->prune_vector; + if (not_prune) + return prune_vector_item_update(prune_list, neigh_table, false); + + return false; +} + +static void +prune_item_notify_list_fini(struct list_head *prune_item_notify_list) +{ + struct list_head *pos, *tmp; + + list_for_each_safe(pos, tmp, prune_item_notify_list) { + struct prune_item *item; + + item = list_entry(pos, typeof(*item), list); + list_del(&item->list); + } +} + +static void +prune_item_notify_list_add(struct prune_intersec_table_list_elem *intersec_item, + struct list_head *prune_item_notify_list) +{ + struct prune_table_entry *entry = intersec_item->entry; + + list_add_tail(&entry->item.list, prune_item_notify_list); +} + +/* + * prune_item_add_prune_vector_calc - Calculate the prune vector due to a new + * item add flow + * @table: The table which the new item belongs to + * @intersec_table: The intersection table of the table above + * @ht_key: A key to store the current masked key + * @entry: The entry which is being added + * @neigh: If true search the neigh_table_elem_list + * @prune_item_notify_list: The notification list which will returned due to + * changes in other items in the prune object + * + * Return: True if the item prune vector has changed. + */ +static bool +prune_item_add_prune_vector_calc(struct prune_table *table, + struct prune_intersec_table *intersec_table, + unsigned long *ht_key, + const struct prune_table_entry *entry, + bool neigh, + struct list_head *prune_item_notify_list) +{ + struct prune_intersec_table_entry *intersec_entry; + struct rhashtable_params rht_params; + bool prune_vector_chng = false; + + bitmap_clear(ht_key, 0, table->prune->mask_len); + bitmap_and(ht_key, entry->item.key, intersec_table->mask, + table->prune->mask_len); + + rht_params = table->prune->intersec_tables_ht_params; + intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht, + &ht_key, rht_params); + if (!intersec_entry) + return false; + + if (neigh) { + struct prune_intersec_table_list_elem *neigh_item; + /* Iterate on neigh_table_elem_list. In case there is a entry + * with higher priority we should not prune the neighbor table. + */ + list_for_each_entry(neigh_item, + &intersec_entry->neigh_table_elem_list, + list) { + prune_vector_chng |= prune_vector_set(table, + intersec_table->neigh_table, + entry, + neigh_item, + NULL, + neigh); + } + } else { + struct prune_intersec_table_list_elem *intersec_item; + /* For my items need to update to prune vector + * corresponding to the new item + */ + list_for_each_entry(intersec_item, + &intersec_entry->intersec_table_elem_list, + list) { + if (prune_vector_set(table, + intersec_table->neigh_table, + entry, + NULL, + intersec_item, + neigh)) { + prune_item_notify_list_add(intersec_item, + prune_item_notify_list); + } + } + } + return prune_vector_chng; +} + +static bool +prune_neigh_item_prio_lower(struct prune_table *table, + const struct prune_table_entry *neigh_entry, + const struct prune_table_entry *entry) +{ + if (neigh_entry->item.priority < entry->item.priority) + return true; + else + return false; +} + +static bool prune_neigh_list_item_lower_prio(struct prune_table *table, + struct prune_intersec_table_list_elem *intersec_item, + struct prune_intersec_table_entry *intersec_entry) +{ + struct prune_intersec_table_list_elem *neigh_item; + + list_for_each_entry(neigh_item, &intersec_entry->neigh_table_elem_list, + list) { + if (prune_neigh_item_prio_lower(table, neigh_item->entry, + intersec_item->entry)) + return true; + } + return false; +} + +/* + * prune_item_del_prune_vector_calc - Calculate the prune vector due to an item + * delete flow + * @table: The table which the new item belongs to + * @intersec_table: The intersection table of the table above + * @ht_key: A key to store the current masked key + * @deleted_entry: The entry which is being deleted + * @prune_item_notify_list: The notification list which will returned due to + * changes in other items in the prune object + */ +static void +prune_item_del_prune_vector_calc(struct prune_table *table, + struct prune_intersec_table *intersec_table, + unsigned long *ht_key, + const struct prune_table_entry *deleted_entry, + struct list_head *prune_item_notify_list) +{ + struct prune_intersec_table_list_elem *intersec_item; + struct prune_intersec_table_entry *intersec_entry; + struct rhashtable_params rht_params; + + bitmap_clear(ht_key, 0, table->prune->mask_len); + bitmap_and(ht_key, deleted_entry->item.key, intersec_table->mask, + table->prune->mask_len); + + rht_params = table->prune->intersec_tables_ht_params; + intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht, + &ht_key, rht_params); + if (!intersec_entry) + return; + + /* Check if one of the items in the neighbor list have higher prio if so + * don't prune + */ + list_for_each_entry(intersec_item, + &intersec_entry->intersec_table_elem_list, list) { + /* Check if there is an item in my neighbor list with higher + * (less important) priority if so --> don't prune + */ + bool notify = false; + + if (!prune_neigh_list_item_lower_prio(table, intersec_item, + intersec_entry)) { + const struct list_head *prune_list; + /* Update intersec_item prune vector for the + * corresponding table to prune due to delete flow + */ + prune_list = &intersec_item->entry->prune_vector; + notify = prune_vector_item_update(prune_list, table, + true); + } + if (notify) + prune_item_notify_list_add(intersec_item, + prune_item_notify_list); + } +} + +static int +prune_item_add_prune_vector_set(struct prune_table *table, + struct prune_table_entry *entry, + bool *notify) +{ + unsigned int mask_len = table->prune->mask_len; + struct prune_intersec_table *intersec_table; + unsigned long *ht_key; + + ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL); + if (!ht_key) + return -ENOMEM; + + *notify = false; + list_for_each_entry(intersec_table, &table->intersec_table_list, list) { + *notify |= prune_item_add_prune_vector_calc(table, + intersec_table, + ht_key, entry, + true, + NULL); + } + kfree(ht_key); + return 0; +} + +static void +prune_neigh_prune_vector_calc(struct prune_table *table, + struct prune_table *curr_table, + unsigned long *ht_key, + const struct prune_table_entry *entry, + bool add_item, + struct list_head *prune_item_notify_list) +{ + struct prune_intersec_table *intersec_table; + + /* Search the corresponding intersection table with + * this table and update the prune vector of items in + * the intersection table if there is no higher + * priority items in their neighbor table. + */ + list_for_each_entry(intersec_table, &curr_table->intersec_table_list, + list) { + if (intersec_table->neigh_table == table) { + /* This is the corresponding table */ + if (add_item) + prune_item_add_prune_vector_calc(table, + intersec_table, + ht_key, + entry, + false, + prune_item_notify_list); + else + prune_item_del_prune_vector_calc(table, + intersec_table, + ht_key, + entry, + prune_item_notify_list); + } + } +} + +static int +prune_neigh_table_prune_vector_set(struct prune_table *table, + const struct prune_table_entry *entry, + bool add_item) +{ + struct list_head prune_item_notify_list; + struct prune_table *curr_table; + unsigned long *ht_key; + + ht_key = kzalloc(prune_mask_size(table->prune->mask_len), GFP_KERNEL); + if (!ht_key) + return -ENOMEM; + + INIT_LIST_HEAD(&prune_item_notify_list); + + list_for_each_entry(curr_table, &table->prune->table_list, list) { + if (curr_table != table) + prune_neigh_prune_vector_calc(table, curr_table, + ht_key, entry, add_item, + &prune_item_notify_list); + } + if (!list_empty(&prune_item_notify_list)) { + table->prune->ops->prune_item_notify(&prune_item_notify_list, + entry->item.table, + add_item ? false : true); + prune_item_notify_list_fini(&prune_item_notify_list); + } + kfree(ht_key); + return 0; +} + +static struct prune_table_entry * +prune_table_entry_create(struct prune *prune, struct prune_table *table, + unsigned long *key, unsigned long priority, void *priv, + bool *notify) +{ + struct prune_table_entry *entry; + int err; + + if (bitmap_subset(key, table->mask, prune->mask_len) != 1) + return ERR_PTR(-EPERM); + + entry = prune_table_entry_init(prune, key, priority, priv); + if (!entry) + return ERR_PTR(-ENOMEM); + + err = prune_item_add_prune_vector_set(table, entry, notify); + if (err) { + prune_table_entry_fini(entry); + return ERR_PTR(err); + } + list_add_tail(&entry->list, &table->entry_list); + entry->item.table = table; + + return entry; +} + +static void prune_table_entry_destroy(struct prune_table_entry *entry) +{ + list_del(&entry->list); + prune_table_entry_fini(entry); +} + +static struct prune_intersec_table_entry * +prune_intersec_entry_create(unsigned long *intersec_table_mask, + unsigned long *item_key, + struct prune_intersec_table *intersec_table, + unsigned int mask_len) +{ + struct prune_intersec_table_entry *intersec_entry; + + intersec_entry = kzalloc(sizeof(*intersec_entry), GFP_KERNEL); + if (!intersec_entry) + goto err_entry_alloc; + + intersec_entry->ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL); + if (!intersec_entry->ht_key) + goto err_ht_key_alloc; + + intersec_entry->intersec_table = intersec_table; + + bitmap_and(intersec_entry->ht_key, intersec_table_mask, item_key, + mask_len); + + INIT_LIST_HEAD(&intersec_entry->intersec_table_elem_list); + INIT_LIST_HEAD(&intersec_entry->neigh_table_elem_list); + + return intersec_entry; + +err_ht_key_alloc: + kfree(intersec_entry); +err_entry_alloc: + return ERR_PTR(-ENOMEM); +} + +static void +prune_intersec_entry_destroy(struct prune_intersec_table_entry *intersec_entry) +{ + WARN_ON(!list_empty(&intersec_entry->intersec_table_elem_list)); + WARN_ON(!list_empty(&intersec_entry->neigh_table_elem_list)); + + kfree(intersec_entry); +} + +static struct prune_intersec_table_list_elem * +prune_intersec_item_create(struct prune_table_entry *entry, + struct prune_intersec_table_entry *intersec_entry, + bool neigh) +{ + struct prune_intersec_table_list_elem *intersec_item; + + intersec_item = kmalloc(sizeof(*intersec_item), GFP_KERNEL); + if (!intersec_item) + return ERR_PTR(-ENOMEM); + + intersec_item->entry = entry; + if (!neigh) + list_add_tail(&intersec_item->list, + &intersec_entry->intersec_table_elem_list); + else + list_add_tail(&intersec_item->list, + &intersec_entry->neigh_table_elem_list); + + return intersec_item; +} + +static void +prune_intersec_item_destroy(struct prune_intersec_table_list_elem *intersec_item) +{ + list_del(&intersec_item->list); + kfree(intersec_item); +} + +static int prune_intersec_item_add(struct prune_intersec_table *intersec_table, + struct prune_table_entry *entry, + bool neigh) +{ + unsigned int mask_len = entry->item.table->prune->mask_len; + struct prune_intersec_table_list_elem *intersec_item; + struct prune_intersec_table_entry *intersec_entry; + struct rhashtable_params rht_params; + unsigned long *ht_key; + bool found = true; + int err = 0; + + ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL); + if (!ht_key) + return -ENOMEM; + + bitmap_and(ht_key, intersec_table->mask, entry->item.key, mask_len); + + rht_params = prune_intersec_table_entry_rht_params(intersec_table); + + intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht, + &ht_key, rht_params); + kfree(ht_key); + + if (!intersec_entry) { + /* create new intersec entry since there ins't already one */ + intersec_entry = prune_intersec_entry_create(intersec_table->mask, + entry->item.key, + intersec_table, + mask_len); + if (IS_ERR(intersec_entry)) { + err = PTR_ERR(intersec_entry); + goto err_entry_alloc; + } + found = false; + } + intersec_item = prune_intersec_item_create(entry, intersec_entry, neigh); + if (IS_ERR(intersec_item)) + goto err_prune_intersec_item_create; + + if (!found) { + err = rhashtable_insert_fast(&intersec_table->entry_ht, + &intersec_entry->ht_node, + rht_params); + if (err) + goto err_rhashtable_insert; + } + return 0; + +err_rhashtable_insert: + prune_intersec_item_destroy(intersec_item); +err_prune_intersec_item_create: + if (!found) + prune_intersec_entry_destroy(intersec_entry); +err_entry_alloc: + return err; +} + +static int +prune_intersec_item_del(struct prune_intersec_table *intersec_table, + struct prune_table_entry *remove_entry, + bool neigh) +{ + unsigned int mask_len = remove_entry->item.table->prune->mask_len; + struct prune_intersec_table_entry *intersec_entry; + struct rhashtable_params rht_params; + struct list_head *pos, *tmp; + unsigned long *ht_key; + + ht_key = kzalloc(prune_mask_size(mask_len), GFP_KERNEL); + if (!ht_key) + return -ENOMEM; + + bitmap_and(ht_key, intersec_table->mask, remove_entry->item.key, + mask_len); + + rht_params = prune_intersec_table_entry_rht_params(intersec_table); + intersec_entry = rhashtable_lookup_fast(&intersec_table->entry_ht, + &ht_key, rht_params); + if (!intersec_entry) { + kfree(ht_key); + return -EPERM; + } + if (!neigh) { + list_for_each_safe(pos, tmp, + &intersec_entry->intersec_table_elem_list) { + struct prune_intersec_table_list_elem *intersec_item; + + intersec_item = list_entry(pos, typeof(*intersec_item), + list); + if (intersec_item->entry == remove_entry) { + prune_intersec_item_destroy(intersec_item); + break; + } + } + } else { + list_for_each_safe(pos, tmp, + &intersec_entry->neigh_table_elem_list) { + struct prune_intersec_table_list_elem *neigh_item; + + neigh_item = list_entry(pos, typeof(*neigh_item), list); + if (remove_entry == neigh_item->entry) { + prune_intersec_item_destroy(neigh_item); + break; + } + } + } + if (list_empty(&intersec_entry->intersec_table_elem_list) && + list_empty(&intersec_entry->neigh_table_elem_list)) { + rhashtable_remove_fast(&intersec_table->entry_ht, + &intersec_entry->ht_node, + rht_params); + prune_intersec_entry_destroy(intersec_entry); + } + kfree(ht_key); + return 0; +} + +static struct prune_intersec_table * +prune_intersec_table_create(struct prune *prune, + struct prune_table *neigh_table, + struct prune_table *table) +{ + struct prune_intersec_table *intersec_table; + unsigned int mask_len = prune->mask_len; + int err; + + intersec_table = kmalloc(sizeof(*intersec_table) + prune_mask_size(mask_len), + GFP_KERNEL); + if (!intersec_table) + return NULL; + + bitmap_and(intersec_table->mask, neigh_table->mask, table->mask, + prune->mask_len); + intersec_table->neigh_table = neigh_table; + + err = rhashtable_init(&intersec_table->entry_ht, + &prune->intersec_tables_ht_params); + if (err) + goto err_rhashtable_init; + + list_add(&intersec_table->list, &table->intersec_table_list); + + return intersec_table; + +err_rhashtable_init: + kfree(intersec_table); + return NULL; +} + +static void prune_intersec_rht_free(void *ptr, void *arg) +{ + struct prune_intersec_table_entry *rht_node = ptr; + struct list_head *pos, *tmp; + + list_for_each_safe(pos, tmp, &rht_node->intersec_table_elem_list) { + struct prune_intersec_table_list_elem *intersec_item; + + intersec_item = list_entry(pos, typeof(*intersec_item), list); + prune_intersec_item_destroy(intersec_item); + } + list_for_each_safe(pos, tmp, &rht_node->neigh_table_elem_list) { + struct prune_intersec_table_list_elem *neigh_item; + + neigh_item = list_entry(pos, typeof(*neigh_item), list); + prune_intersec_item_destroy(neigh_item); + } + kfree(rht_node->ht_key); + kfree(rht_node); +} + +static void +prune_intersec_table_destroy(struct prune_intersec_table *intersec_table) +{ + rhashtable_free_and_destroy(&intersec_table->entry_ht, + prune_intersec_rht_free, + NULL); + list_del(&intersec_table->list); + kfree(intersec_table); +} + +/* + * prune_intersec_table_items_commit - Update the item of the current table to + * the neighbor items in the intersection + * table + * @table: The table which its items needs to be updated in the + * intersection table + * @intersec_table: The intersection table which needs to be updated + * @add_to_neigh_items: True if items need to be add to neigh_table_elem_list + */ +static int prune_intersec_table_items_commit(struct prune_table *table, + struct prune_intersec_table *intersec_table, + bool add_to_neigh_items) +{ + struct prune_table_entry *entry; + int err; + + list_for_each_entry(entry, &table->entry_list, list) { + err = prune_intersec_item_add(intersec_table, entry, + add_to_neigh_items); + if (err) + goto err_prune_intersec_item_add; + } + return 0; + +err_prune_intersec_item_add: + list_for_each_entry_continue_reverse(entry, &table->entry_list, list) { + prune_intersec_item_del(intersec_table, entry, + add_to_neigh_items); + } + return err; +} + +static int prune_intersec_table_items_revert(struct prune_table *table, + struct prune_intersec_table *intersec_table, + bool del_from_neigh_items) +{ + struct prune_table_entry *entry; + int err; + + list_for_each_entry(entry, &table->entry_list, list) { + err = prune_intersec_item_del(intersec_table, entry, + del_from_neigh_items); + if (err) + return err; + } + return 0; +} + +static int prune_intersec_table_add(struct prune *prune, + struct prune_table *new_table, + struct prune_table *table) +{ + struct prune_intersec_table *intersec_table_old; + struct prune_intersec_table *intersec_table_new; + int err = 0; + + intersec_table_old = prune_intersec_table_create(prune, new_table, + table); + if (!intersec_table_old) + goto err_allocate_intersec_table_old; + + intersec_table_new = prune_intersec_table_create(prune, table, + new_table); + if (!intersec_table_new) + goto err_allocate_intersec_table_new; + + err = prune_intersec_table_items_commit(table, intersec_table_old, + false); + if (err) + goto err_prune_intersec_table_items_commit_old; + + err = prune_intersec_table_items_commit(table, intersec_table_new, + true); + if (err) + goto err_prune_intersec_table_items_commit_new; + return 0; + +err_prune_intersec_table_items_commit_new: + if (prune_intersec_table_items_revert(table, intersec_table_old, false)) + WARN_ON(1); +err_prune_intersec_table_items_commit_old: + prune_intersec_table_destroy(intersec_table_new); +err_allocate_intersec_table_new: + prune_intersec_table_destroy(intersec_table_old); +err_allocate_intersec_table_old: + return err ? err : -ENOMEM; +} + +static int prune_intersec_table_fini(struct prune_table *table); + +/* + * prune_intersec_table_init - Add new intersection table to all tables and + * initialize it. + * @prune: The prune object which the intersection should be part of + * object. + * @new_table: + * + * Return: 0 in case of success, negative number to indicate an error. + */ +static int prune_intersec_table_init(struct prune *prune, + struct prune_table *new_table) +{ + struct prune_table *table; + int err; + + list_for_each_entry(table, &prune->table_list, list) { + err = prune_intersec_table_add(prune, new_table, table); + if (err) + goto err_prune_intersec_table_add; + } + return 0; + +err_prune_intersec_table_add: + list_for_each_entry_continue_reverse(table, &prune->table_list, list) + prune_intersec_table_fini(table); + + return err; +} + +static int prune_intersec_table_del(unsigned int mask_len, + struct prune_table *table, + struct prune_table *table_removed) +{ + struct list_head *intersec_pos, *tmp; + unsigned long *curr_mask; + int err; + + curr_mask = kzalloc(prune_mask_size(mask_len), GFP_KERNEL); + if (!curr_mask) + return -ENOMEM; + + bitmap_and(curr_mask, table->mask, table_removed->mask, mask_len); + + list_for_each_safe(intersec_pos, tmp, &table->intersec_table_list) { + struct prune_intersec_table *intersec_table; + + intersec_table = list_entry(intersec_pos, + typeof(*intersec_table), + list); + if (bitmap_equal(curr_mask, intersec_table->mask, + mask_len)) { + prune_intersec_table_destroy(intersec_table); + err = 0; + goto end; + } + } + goto err_flow; + +err_flow: + err = -EPERM; + WARN_ON(1); /* Didn't found the wanted intersection table */ +end: + kfree(curr_mask); + return err; +} + +static int prune_intersec_table_fini(struct prune_table *table) +{ + struct prune_table *curr_table; + struct list_head *pos, *tmp; + int err; + + /* Remove the intersection table from neighbor tables */ + list_for_each_entry(curr_table, &table->prune->table_list, list) { + if (curr_table != table) { + err = prune_intersec_table_del(table->prune->mask_len, + curr_table, table); + if (err) + return err; + } + } + /* Remove all intersection tables from this table */ + list_for_each_safe(pos, tmp, &table->intersec_table_list) { + struct prune_intersec_table *intersec_table; + + intersec_table = list_entry(pos, typeof(*intersec_table), + list); + prune_intersec_table_destroy(intersec_table); + } + WARN_ON_ONCE(!list_empty(&table->intersec_table_list)); + + return 0; +} + +static int +prune_intersec_list_item_add(struct prune_table *item_added_table, + struct prune_table *table, + struct prune_table_entry *entry, + bool neigh_item) +{ + struct prune_intersec_table *intersec_table; + int err; + + list_for_each_entry(intersec_table, &table->intersec_table_list, + list) { + /* Add the item only to the corresponding tables */ + if (!neigh_item || + intersec_table->neigh_table == item_added_table) { + err = prune_intersec_item_add(intersec_table, + entry, + neigh_item); + if (err) + return err; + } + } + return 0; +} + +static int +prune_intersec_list_item_del(struct prune_table *remove_item_table, + struct prune_table *table, + struct prune_table_entry *remove_entry, + bool neigh_item) +{ + struct prune_intersec_table *intersec_table; + int err; + + list_for_each_entry(intersec_table, &table->intersec_table_list, + list) { + if (intersec_table->neigh_table == remove_item_table || + !neigh_item) { + err = prune_intersec_item_del(intersec_table, + remove_entry, + neigh_item); + if (err) + return err; + } + } + return 0; +} + +static void prune_table_item_vector_del(struct prune_table *table, + struct prune_table *del_table); + +static int prune_table_item_vector_add(struct prune_table *table, + struct prune_table *new_table) +{ + struct prune_table_entry *entry; + + list_for_each_entry(entry, &table->entry_list, list) { + struct prune_vector_item *vector_item; + + vector_item = kmalloc(sizeof(*vector_item), GFP_KERNEL); + if (!vector_item) { + prune_table_item_vector_del(table, new_table); + return -ENOMEM; + } + vector_item->pruned = true; + vector_item->table = new_table; + list_add_tail(&vector_item->list, &entry->prune_vector); + } + return 0; +} + +static void prune_table_item_vector_del(struct prune_table *table, + struct prune_table *del_table) +{ + struct prune_table_entry *entry; + + list_for_each_entry(entry, &table->entry_list, list) { + struct list_head *pos, *tmp; + + list_for_each_safe(pos, tmp, &entry->prune_vector) { + struct prune_vector_item *vector_item; + + vector_item = list_entry(pos, typeof(*vector_item), + list); + if (vector_item->table == del_table) { + list_del(&vector_item->list); + kfree(vector_item); + break; + } + } + } +} + +/* + * prune_item_prune_table_add - Add new vector_item to each entry in each table + * @prune: The prune object which contains all tables + * @new_table: The new table which needs to be pointed by the vector_item + */ +static int prune_item_prune_table_add(struct prune *prune, + struct prune_table *new_table) +{ + struct prune_table *table; + int err; + + list_for_each_entry(table, &prune->table_list, list) { + err = prune_table_item_vector_add(table, new_table); + if (err) + return err; + } + return 0; +} + +/* + * prune_item_prune_table_del - Delete vector_item from each entry in each table + * @prune: The prune object which contains all tables + * @del_table: The table which needs to be deleted from the vector_item + */ +static void prune_item_prune_table_del(struct prune *prune, + struct prune_table *del_table) +{ + struct prune_table *table; + + list_for_each_entry(table, &prune->table_list, list) { + if (del_table != table) + prune_table_item_vector_del(table, del_table); + } +} + +static void +prune_intersec_tables_ht_params_init(struct prune *prune, unsigned int mask_len) +{ + memcpy(&prune->intersec_tables_ht_params, &intersec_tables_ht_params, + sizeof(intersec_tables_ht_params)); + prune->intersec_tables_ht_params.key_len = mask_len; +} + +static struct prune_table *prune_table_init(struct prune *prune, + unsigned long *mask, void *priv) +{ + struct prune_table *table; + + table = kmalloc(sizeof(*table) + prune_mask_size(prune->mask_len), + GFP_KERNEL); + if (!table) + return ERR_PTR(-ENOMEM); + + bitmap_copy(table->mask, mask, prune->mask_len); + table->priv = priv; + table->prune = prune; + INIT_LIST_HEAD(&table->entry_list); + INIT_LIST_HEAD(&table->intersec_table_list); + + return table; +} + +static void prune_table_fini(struct prune_table *table) +{ + WARN_ON(!list_empty(&table->entry_list)); + WARN_ON(!list_empty(&table->intersec_table_list)); + + kfree(table); +} + +/** + * prune_create - Create a prune object which manages the pruning vector + * between tables. + * @mask_len: Set the mask length (nbits) for all tables in the prune + * object. + * @ops: Caller-specific callbacks. + * @priv: Pointer to a private user data. + * + * Return: A pointer to newly created prune instance in case of success, + * otherwise it returns NULL. + */ +struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops, + void *priv) +{ + struct prune *prune; + + if (!ops || !mask_len) + return NULL; + + prune = kmalloc(sizeof(*prune), GFP_KERNEL); + if (!prune) + return NULL; + + prune->priv = priv; + prune->mask_len = mask_len; + INIT_LIST_HEAD(&prune->table_list); + prune->ops = ops; + prune_intersec_tables_ht_params_init(prune, mask_len); + + return prune; +} +EXPORT_SYMBOL(prune_create); + +/** + * prune_destroy - Destroy the prune object. + * @prune: Prune object. + */ +void prune_destroy(struct prune *prune) +{ + WARN_ON(!list_empty(&prune->table_list)); + + kfree(prune); +} +EXPORT_SYMBOL(prune_destroy); + +/** + * prune_table_create - Creates a new table and adds it to the prune object. + * @prune: Prune object. + * @mask: Table mask - all items key should match this mask. + * @mask_len: The length of mask - number of bits. + * @priv: User data. + * + * Return: A pointer to newly created prune table instance in case of success, + * otherwise it returns pointer to an error. + * + * Note: It's the user responsibility to care of synchronization. + */ + +struct prune_table *prune_table_create(struct prune *prune, unsigned long *mask, + unsigned int mask_len, void *priv) +{ + struct prune_table *table; + int err; + + if (WARN_ON(prune->mask_len != mask_len)) + return ERR_PTR(-EINVAL); + + table = prune_table_init(prune, mask, priv); + if (IS_ERR(table)) + return table; + + /* Enlarge the prune vector of all item with the new table */ + err = prune_item_prune_table_add(prune, table); + if (err) + goto err_table_add; + + err = prune_intersec_table_init(prune, table); + if (err) + goto err_table_build; + + list_add_tail(&table->list, &prune->table_list); + + return table; + +err_table_build: + prune_item_prune_table_del(prune, table); +err_table_add: + kfree(table); + return ERR_PTR(err); +} +EXPORT_SYMBOL(prune_table_create); + +/** + * prune_table_destroy - Removes the table from the prune object and destroys + * it. + * @table: Table to be removed. + * + * Return: 0 in case of success, negative number to indicate an error. + * + * Note: It's the user responsibility to care of synchronization. + */ +int prune_table_destroy(struct prune_table *table) +{ + int err; + + err = prune_intersec_table_fini(table); + if (err) + return err; + + prune_item_prune_table_del(table->prune, table); + + list_del(&table->list); + + prune_table_fini(table); + + return 0; +} +EXPORT_SYMBOL(prune_table_destroy); + +/** + * prune_item_create - Creates a new item and adds it to a table. + * @prune: Prune object. + * @table: Add the item to this table. + * @key: Item key (bitmap) - must be correspond to table + * mask and length (not copied by the library). + * @priority: Item priority. + * @priv: User data. + * @non_def_prune_vector: If true, this item don't prunes all tables in + * the prune object [out]. + * + * Return: A pointer to newly created prune item instance in case of success, + * otherwise it returns pointer to an error. + * + * Note: It's the user responsibility to care of synchronization. + */ +struct prune_item *prune_item_create(struct prune *prune, + struct prune_table *table, + unsigned long priority, + unsigned long *key, + void *priv, + bool *non_def_prune_vector) +{ + struct prune_table_entry *entry; + struct prune_table *curr_table; + int err; + + entry = prune_table_entry_create(prune, table, key, priority, priv, + non_def_prune_vector); + if (IS_ERR(entry)) + return ERR_CAST(entry); + + /* Add the item to the intersection tables of all tables*/ + list_for_each_entry(curr_table, &prune->table_list, list) { + err = prune_intersec_list_item_add(table, curr_table, entry, + curr_table != table ? + true : false); + if (err) + goto err_prune_intersec_list_item_add; + } + /* Update prune vector of the corresponding items of the neighbor + * tables + */ + err = prune_neigh_table_prune_vector_set(table, entry, true); + if (err) + goto err_prune_neigh_table_prune_vector_set; + + return &entry->item; + +err_prune_neigh_table_prune_vector_set: +err_prune_intersec_list_item_add: + list_for_each_entry_continue_reverse(curr_table, &prune->table_list, + list) { + prune_intersec_list_item_del(table, curr_table, entry, + curr_table != table ? true : false); + } + prune_table_entry_destroy(entry); + return ERR_PTR(err); +} +EXPORT_SYMBOL(prune_item_create); + +/** + * prune_item_destroy - removes the item from a table and destroys it. + * @item: The item to remove. + * + * Return: 0 in case of success, negative number to indicate an error. + * + * Note: It's the user responsibility to care of synchronization. + */ +int prune_item_destroy(struct prune_item *item) +{ + struct prune_table_entry *entry; + struct prune_table *curr_table; + struct prune_table *table; + struct prune *prune; + int err; + + table = item->table; + prune = table->prune; + + entry = container_of(item, struct prune_table_entry, item); + /* Remove the item from tables in the intersection tables */ + list_for_each_entry(curr_table, &prune->table_list, list) { + err = prune_intersec_list_item_del(table, curr_table, entry, + curr_table != table ? + true : false); + if (err) + return err; + } + + /* Update prune vector of the corresponding items of the neighbor + * prune_table + */ + err = prune_neigh_table_prune_vector_set(table, entry, false); + if (err) + return err; + + prune_table_entry_destroy(entry); + + return 0; +} +EXPORT_SYMBOL(prune_item_destroy); + +/** + * prune_table_priv - Retrieves the priv from the table. + * @table: The table which its priv is wanted. + * + * Return: A pointer to the priv field in the prune table. + * + * Note: It's the user responsibility to care of synchronization. + */ +void *prune_table_priv(struct prune_table *table) +{ + return table->priv; +} +EXPORT_SYMBOL(prune_table_priv); + +/** + * prune_item_prune_vector - Retrieves the prune vector of the item. + * @item: The table item its prune vector is wanted. + * + * Return: A pointer to the head of the prune vector list. + * + * Note: It's the user responsibility to care of synchronization. + */ +struct list_head *prune_item_prune_vector(struct prune_item *item) +{ + struct prune_table_entry *entry; + + entry = container_of(item, struct prune_table_entry, item); + return &entry->prune_vector; +} +EXPORT_SYMBOL(prune_item_prune_vector); + +MODULE_LICENSE("Dual BSD/GPL"); +MODULE_AUTHOR("Tal Bar "); +MODULE_DESCRIPTION("Prune lookup table manager"); diff --git a/lib/test_prune.c b/lib/test_prune.c new file mode 100644 index 0000000..8bf43af --- /dev/null +++ b/lib/test_prune.c @@ -0,0 +1,1214 @@ +// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause +/* + * lib/test_prune.c - Test module for prune + * Copyright (c) 2018 Mellanox Technologies. All rights reserved. + */ + +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + +#include +#include +#include +#include +#include +#include + +#define TABLES_2 (2) +#define TABLES_3 (3) +#define TABLES_4 (4) +#define ITEMS_3 (3) +#define ITEMS_6 (6) +#define ITEMS_8 (8) + +struct test_prune_table_attr { + unsigned long *mask; + unsigned int mask_len; /* Number of bits */ + unsigned int table_id; +}; + +struct test_prune_item { + unsigned long priority; /* Lower number means higher priority */ + unsigned long *key; + void *priv; + bool non_def_prune_vector; +}; + +struct test_prune_vector_item { + unsigned int table_id; + bool is_pruned; /* True if the item is pruning this table */ +}; + +static inline size_t prune_mask_size(unsigned int nbits) +{ + return BITS_TO_LONGS(nbits) * sizeof(unsigned long); +} + +static void test_prune_notification_print(struct prune_item *item, bool print) +{ + struct prune_vector_item *vector_item; + struct list_head *prune_vector; + struct prune_table *table; + void *priv; + int i; + + if (print) { + pr_info("item prio: %u\n", item->priority); + pr_info("item mask: %lu\n", *item->key); + pr_info("item from table: %p\n", item->table); + + prune_vector = prune_item_prune_vector(item); + + i = 0; + list_for_each_entry(vector_item, prune_vector, list) { + table = vector_item->table; + priv = prune_table_priv(table); + pr_info("i = [%d], table priv: %lu\t %s pruned\t pruned table *: %p\n", + i, + (uintptr_t)priv, + vector_item->pruned ? "" : "not", + table); + i++; + } + } +} + +static bool test_prune_check_prune_vector(struct prune_item *item, + bool *prune_val_arr, + int arr_len, + bool non_def_prune_vector) +{ + #define MAX_CASE (5) + struct prune_vector_item *vector_item; + struct list_head *prune_vector = prune_item_prune_vector(item); + bool case_passed = true; + int table_id = 0; + bool pruned; + void *priv; + + list_for_each_entry(vector_item, prune_vector, list) { + pruned = vector_item->pruned; + priv = prune_table_priv(vector_item->table); + + if (!non_def_prune_vector && pruned) { + continue; + } else if (!non_def_prune_vector && !pruned) { + WARN(1, "test didn't pass un pruned table in default prune-vector"); + return false; + } + + if (table_id == arr_len || table_id > MAX_CASE) { + WARN(1, "test didn't pass too many items in prune vector"); + return false; + } + + switch (table_id) { + case MAX_CASE - 5: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[0]; + break; + case MAX_CASE - 4: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[1]; + break; + case MAX_CASE - 3: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[2]; + break; + case MAX_CASE - 2: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[3]; + break; + case MAX_CASE - 1: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[4]; + break; + case MAX_CASE: + case_passed = + (uintptr_t)priv == table_id && + pruned == prune_val_arr[5]; + break; + default: + case_passed = false; + break; + } + table_id++; + + if (!case_passed) { + WARN(1, "test didn't pass for table [%d]", table_id); + return case_passed; + } + } + return case_passed; +} + +static bool test_prune_check_case(struct prune_item *item, + unsigned int prio, + bool *prune_val_arr, + int arr_len, + int test_case) +{ + bool case_passed = true; + + if (item->priority != prio) { + WARN(1, "test case [%d] didn't pass. Incorrect priority [%u]", + test_case, item->priority); + return false; + } + + case_passed = test_prune_check_prune_vector(item, prune_val_arr, + arr_len, true); + if (!case_passed) + WARN(1, "test case [%d] didn't pass", test_case); + + return case_passed; +} + +static void +test_prune_subsequent_notify(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned) +{ + bool prune_value_case0[2] = {true, false}; + bool prune_value_case1[3] = {true, false, false}; + bool prune_value_case2[3] = {true, true, false}; + bool prune_value_case3[3] = {true, true, true}; + struct prune_item *item; + static int test_case; + + list_for_each_entry(item, prune_item_notify_list, list) { + test_prune_notification_print(item, false); + + switch (test_case) { + case 0: + test_prune_check_case(item, 10, + prune_value_case0, + ARRAY_SIZE(prune_value_case0), + test_case); + break; + case 1: + test_prune_check_case(item, 10, + prune_value_case1, + ARRAY_SIZE(prune_value_case1), + test_case); + break; + case 2: + test_prune_check_case(item, 5, + prune_value_case2, + ARRAY_SIZE(prune_value_case2), + test_case); + break; + case 3: + test_prune_check_case(item, 8, + prune_value_case3, + ARRAY_SIZE(prune_value_case3), + test_case); + break; + default: + WARN(1, "unexpected test case %d", test_case); + break; + } + test_case++; + } +} + +static void +test_prune_flows_1_notify(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned) +{ + bool prune_value_arr_case0[2] = {false, true}; + bool prune_value_arr_case1[2] = {true, true}; + bool prune_value_arr_case2[2] = {true, true}; + struct prune_item *item; + static int test_case; + + list_for_each_entry(item, prune_item_notify_list, list) { + test_prune_notification_print(item, false); + + switch (test_case) { + case 0: + test_prune_check_case(item, 10, + prune_value_arr_case0, + ARRAY_SIZE(prune_value_arr_case0), + test_case); + break; + case 1: + test_prune_check_case(item, 7, + prune_value_arr_case1, + ARRAY_SIZE(prune_value_arr_case1), + test_case); + break; + case 2: + test_prune_check_case(item, 10, + prune_value_arr_case2, + ARRAY_SIZE(prune_value_arr_case2), + test_case); + break; + default: + WARN(1, "unexpected test case %d", test_case); + break; + } + test_case++; + } +} + +static void +test_prune_flows_2_notify(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned) +{ + bool prune_value_arr_case0[2] = {false, true}; + bool prune_value_arr_case1[3] = {true, false, true}; + bool prune_value_arr_case2[3] = {true, true, true}; + struct prune_item *item; + static int test_case; + + list_for_each_entry(item, prune_item_notify_list, list) { + test_prune_notification_print(item, false); + + switch (test_case) { + case 0: + test_prune_check_case(item, 7, + prune_value_arr_case0, + ARRAY_SIZE(prune_value_arr_case0), + test_case); + break; + case 1: + test_prune_check_case(item, 7, + prune_value_arr_case1, + ARRAY_SIZE(prune_value_arr_case1), + test_case); + break; + case 2: + test_prune_check_case(item, 5, + prune_value_arr_case2, + ARRAY_SIZE(prune_value_arr_case2), + test_case); + break; + default: + WARN(1, "unexpected test case %d", test_case); + break; + } + test_case++; + } +} + +static void +test_prune_basic_notify(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned) +{ + bool prune_value_arr_case0[3] = {true, false, true}; + bool prune_value_arr_case1[3] = {true, false, false}; + bool prune_value_arr_case2[3] = {true, true, false}; + bool prune_value_arr_case3[3] = {true, false, true}; + bool prune_value_arr_case4[3] = {true, true, true}; + struct prune_item *item; + static int test_case; + + list_for_each_entry(item, prune_item_notify_list, list) { + test_prune_notification_print(item, false); + + switch (test_case) { + case 0: + test_prune_check_case(item, 3, + prune_value_arr_case0, + ARRAY_SIZE(prune_value_arr_case0), + test_case); + break; + case 1: + test_prune_check_case(item, 3, + prune_value_arr_case1, + ARRAY_SIZE(prune_value_arr_case1), + test_case); + break; + case 2: + test_prune_check_case(item, 2, + prune_value_arr_case2, + ARRAY_SIZE(prune_value_arr_case2), + test_case); + break; + case 3: + test_prune_check_case(item, 3, + prune_value_arr_case3, + ARRAY_SIZE(prune_value_arr_case3), + test_case); + break; + case 4: + test_prune_check_case(item, 2, + prune_value_arr_case4, + ARRAY_SIZE(prune_value_arr_case4), + test_case); + break; + default: + WARN(1, "unexpected test case %d", test_case); + break; + } + test_case++; + if (test_case == 10) + return; + } +} + +static const struct prune_ops test_prune_add_new_table_subsequent_ops = { + .prune_item_notify = test_prune_subsequent_notify +}; + +static const struct prune_ops test_prune_flows_add_delete_items_1_ops = { + .prune_item_notify = test_prune_flows_1_notify +}; + +static const struct prune_ops test_prune_flows_add_delete_items_2_ops = { + .prune_item_notify = test_prune_flows_2_notify +}; + +static const struct prune_ops test_prune_basic_ops = { + .prune_item_notify = test_prune_basic_notify +}; + +static int table_attr_create(struct test_prune_table_attr *table_attr, + unsigned int mask_len, + unsigned int table_cnt) +{ + unsigned long i, j; + + for (i = 0; i < table_cnt; i++) { + table_attr[i].mask = kcalloc(1, prune_mask_size(mask_len), + GFP_KERNEL); + if (!table_attr[i].mask) { + if (i > 0) { + for (j = i - 1; j == 0; j--) + kfree(table_attr[j].mask); + } + return -ENOMEM; + } + table_attr[i].mask_len = mask_len; + table_attr[i].table_id = i; + } + return 0; +} + +static void table_attr_destroy(struct test_prune_table_attr *table_attr, + unsigned int table_cnt) +{ + int i; + + for (i = 0; i < table_cnt; i++) + kfree(table_attr[i].mask); +} + +static void prune_item_arr_destroy(struct test_prune_item *pi_arr, + unsigned int pi_cnt) +{ + int i; + + for (i = 0; i < pi_cnt; i++) + kfree(pi_arr[i].key); +} + +static int test_prune_item_arr_create(struct test_prune_item *tpi_arr, + unsigned int pi_cnt, + unsigned int pi_nbits) +{ + int i, j = 0; + + for (i = 0; i < pi_cnt; i++) { + tpi_arr[i].key = kcalloc(1, prune_mask_size(pi_nbits), + GFP_KERNEL); + if (!tpi_arr[i].key) { + if (i > 0) + for (j = i - 1; j > -1; j--) + kfree(tpi_arr[j].key); + return -ENOMEM; + } + bitmap_clear(tpi_arr[i].key, 0, pi_nbits); + } + return 0; +} + +/* + * Basic test: test add / remove table and item without checking their prune + * vector + */ +static int test_prune_basic(void) +{ + struct test_prune_table_attr table_attr[TABLES_3]; + struct prune_table *table_arr[TABLES_3]; + struct test_prune_item tpi_arr[ITEMS_3]; + struct prune_item *item_arr[ITEMS_3]; + unsigned int nbits = 40; + struct prune *prune; + int err; + + prune = prune_create(nbits, &test_prune_basic_ops, NULL); + if (IS_ERR(prune)) + return PTR_ERR(prune); + + err = table_attr_create(table_attr, nbits, TABLES_3); + if (err) + return err; + + err = test_prune_item_arr_create(tpi_arr, ITEMS_3, nbits); + if (err) + return err; + + bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len); + bitmap_set(table_attr[0].mask, 0, 2); + table_arr[0] = prune_table_create(prune, table_attr[0].mask, + table_attr[0].mask_len, + (int *)(uintptr_t)table_attr[0].table_id); + if (IS_ERR(table_arr[0])) + return PTR_ERR(table_arr[0]); + + bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len); + bitmap_set(table_attr[1].mask, 1, 2); + table_arr[1] = prune_table_create(prune, table_attr[1].mask, + table_attr[1].mask_len, + (int *)(uintptr_t)table_attr[1].table_id); + if (IS_ERR(table_arr[1])) + return PTR_ERR(table_arr[1]); + + bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len); + bitmap_set(table_attr[2].mask, 2, 2); + table_arr[2] = prune_table_create(prune, table_attr[2].mask, + table_attr[2].mask_len, + (int *)(uintptr_t)table_attr[2].table_id); + if (IS_ERR(table_arr[2])) + return PTR_ERR(table_arr[2]); + + tpi_arr[0].priority = 3; + tpi_arr[0].priv = NULL; + bitmap_set(tpi_arr[0].key, 0, 2); + item_arr[0] = prune_item_create(prune, table_arr[0], + tpi_arr[0].priority, tpi_arr[0].key, + tpi_arr[0].priv, + &tpi_arr[0].non_def_prune_vector); + if (IS_ERR(item_arr[0])) + return -EBADE; + + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[0], NULL, 0, + tpi_arr[0].non_def_prune_vector)) + return -EBADE; + + tpi_arr[1].priority = 2; + tpi_arr[1].priv = NULL; + bitmap_set(tpi_arr[1].key, 1, 2); + item_arr[1] = prune_item_create(prune, table_arr[1], + tpi_arr[1].priority, + tpi_arr[1].key, tpi_arr[1].priv, + &tpi_arr[1].non_def_prune_vector); + if (IS_ERR(item_arr[1])) + return -EBADE; + + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[1], NULL, 0, + tpi_arr[1].non_def_prune_vector)) + return -EBADE; + + tpi_arr[2].priority = 1; + tpi_arr[2].priv = NULL; + bitmap_set(tpi_arr[2].key, 2, 2); + + item_arr[2] = prune_item_create(prune, table_arr[2], + tpi_arr[2].priority, + tpi_arr[2].key, tpi_arr[2].priv, + &tpi_arr[2].non_def_prune_vector); + if (IS_ERR(item_arr[1])) + return -EBADE; + + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[2], NULL, 0, + tpi_arr[2].non_def_prune_vector)) + return -EBADE; + + err = prune_item_destroy(item_arr[2]); + if (err) + return err; + + err = prune_item_destroy(item_arr[0]); + if (err) + return err; + + err = prune_item_destroy(item_arr[1]); + if (err) + return err; + + prune_table_destroy(table_arr[0]); + + prune_table_destroy(table_arr[1]); + + prune_table_destroy(table_arr[2]); + + prune_destroy(prune); + + prune_item_arr_destroy(tpi_arr, ITEMS_3); + table_attr_destroy(table_attr, TABLES_3); + + return 0; +} + +static int test_prune_flows_add_delete_items_1(void) +{ + struct test_prune_table_attr table_attr[TABLES_2]; + struct prune_table *table_arr[TABLES_2]; + struct test_prune_item tpi_arr[ITEMS_3]; + struct prune_item *item_arr[ITEMS_3]; + bool prune_val_arr_2[2] = {true, false}; + unsigned int nbits = 40; + struct prune *prune; + int err; + + prune = prune_create(nbits, &test_prune_flows_add_delete_items_1_ops, + NULL); + + if (IS_ERR(prune)) + return PTR_ERR(prune); + + err = table_attr_create(table_attr, nbits, TABLES_2); + if (err) + return err; + + err = test_prune_item_arr_create(tpi_arr, ITEMS_3, nbits); + if (err) + return err; + + /* Create table with mask u.u.u.x.x - table 0*/ + bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len); + bitmap_set(table_attr[0].mask, 0, 24); /* Set care on #1-3 byte*/ + table_arr[0] = prune_table_create(prune, table_attr[0].mask, + table_attr[0].mask_len, + (int *)(uintptr_t)table_attr[0].table_id); + if (IS_ERR(table_arr[0])) + return PTR_ERR(table_arr[0]); + + /* Create table with mask x.u.u.u.x */ + bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len); + bitmap_set(table_attr[1].mask, 8, 24); /* Set care on #2-4 byte*/ + table_arr[1] = prune_table_create(prune, table_attr[1].mask, + table_attr[1].mask_len, + (int *)(uintptr_t)table_attr[1].table_id); + if (IS_ERR(table_arr[0])) + return PTR_ERR(table_arr[0]); + + /* Create item0 x.2.3.4.x prio 5 */ + tpi_arr[0].priority = 5; + tpi_arr[0].priv = NULL; + bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte*/ + bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte*/ + bitmap_set(tpi_arr[0].key, 29, 1); /* Set 4 on #4 byte*/ + + /* Create item1 x.2.3.5.x prio 10*/ + tpi_arr[1].priority = 10; + tpi_arr[1].priv = NULL; + bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte*/ + bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte*/ + bitmap_set(tpi_arr[1].key, 29, 1); /* Set 5 on #4 byte*/ + bitmap_set(tpi_arr[1].key, 31, 1); /* Set 5 on #4 byte*/ + + /* Add item0: x.2.3.4.x to table 1 */ + item_arr[0] = prune_item_create(prune, table_arr[1], + tpi_arr[0].priority, + tpi_arr[0].key, tpi_arr[0].priv, + &tpi_arr[0].non_def_prune_vector); + if (IS_ERR(item_arr[0])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[0], NULL, 0, + tpi_arr[0].non_def_prune_vector)) + return -EBADE; + + /* Expected prune vector for item1 and item2 + * table 0 pruned + * table 1 pruned + * --> Shoudn't not get notification + */ + + /* Add item1: x.2.3.5.x to table 1 */ + item_arr[1] = prune_item_create(prune, table_arr[1], + tpi_arr[1].priority, + tpi_arr[1].key, tpi_arr[1].priv, + &tpi_arr[1].non_def_prune_vector); + if (IS_ERR(item_arr[1])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[1], NULL, 0, + tpi_arr[1].non_def_prune_vector)) + return -EBADE; + + /* Expected prune vector for both item + * table 0 pruned + * table 1 pruned + * --> Shoudn't not get notification + */ + + /* Create item2 1.2.3.x.x prio 7 */ + tpi_arr[2].priority = 7; + tpi_arr[2].priv = NULL; + bitmap_set(tpi_arr[2].key, 7, 1); /* Set 1 on #1 byte*/ + bitmap_set(tpi_arr[2].key, 14, 1); /* Set 2 on #2 byte*/ + bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte*/ + + /* Add item2: 1.2.3.x.x prio 7 to table 0 */ + item_arr[2] = prune_item_create(prune, table_arr[0], + tpi_arr[2].priority, + tpi_arr[2].key, tpi_arr[2].priv, + &tpi_arr[2].non_def_prune_vector); + if (IS_ERR(item_arr[2])) + return -EBADE; + + if (!test_prune_check_prune_vector(item_arr[2], prune_val_arr_2, 2, + tpi_arr[2].non_def_prune_vector)) + return -EBADE; + + /* Expected prune vector per item + * item0 in table 1 (x.2.3.4.x prio 10): + * table 0 pruned (no change) + * table 1 pruned (no change) + * --> shoudn't not get notification + * item1 in table 1 (x.2.3.5.x prio 5): + * table 0 not pruned (changed) + * table 1 pruned (changed) + * --> Should get notification + * item2 in table 0 (1.2.3.x.x prio 7): + * table 0 pruned (no change) + * table 1 not pruned (no change) + * --> Should get notification + */ + + /* Delete item: 0: (x.2.3.4.x prio 10 from table 1 */ + err = prune_item_destroy(item_arr[0]); + if (err) + return err; + + /* Expected prune vector + * item0: item is deleted + * item1 table 1 (x.2.3.5.x prio 5): + * table 0 not pruned + * table 1 pruned + * item2 table 0 (1.2.3.x.x prio 7): + * table 0 pruned + * table 1 pruned (changed) + */ + + /* Delete item: 2: (1.2.3.x.x prio 7) from table 0 */ + err = prune_item_destroy(item_arr[2]); + if (err) + return err; + + /* Expected prune vector + * item0: item is deleted + * item1 table 1 (x.2.3.5.x prio 5): + * table 0 pruned (changed) + * table 1 pruned + * item2 item is deleted + * + */ + + /* Delete item: 1: (x.2.3.5.x prio 5) from table 1 */ + err = prune_item_destroy(item_arr[1]); + if (err) + return err; + + err = prune_table_destroy(table_arr[0]); + if (err) + return err; + + err = prune_table_destroy(table_arr[1]); + if (err) + return err; + + prune_destroy(prune); + + prune_item_arr_destroy(tpi_arr, ITEMS_3); + table_attr_destroy(table_attr, TABLES_2); + + return 0; +} + +static int test_prune_flows_add_delete_item_2(void) +{ + bool prune_val_arr_3[3] = {false, false, true}; + bool prune_val_arr_5[3] = {false, true, true}; + struct test_prune_table_attr table_attr[TABLES_3]; + struct prune_table *table_arr[TABLES_3]; + struct test_prune_item tpi_arr[ITEMS_6]; + struct prune_item *item_arr[ITEMS_6]; + unsigned int nbits = 40; + struct prune *prune; + int err; + + prune = prune_create(nbits, &test_prune_flows_add_delete_items_2_ops, + NULL); + if (IS_ERR(prune)) + return PTR_ERR(prune); + + err = table_attr_create(table_attr, nbits, TABLES_3); + if (err) + return err; + + err = test_prune_item_arr_create(tpi_arr, ITEMS_6, nbits); + if (err) + return err; + + /* Tables: + * table 0: x.x.u.u.u + * table 1: u.u.u.x.x + * table 2: x.u.x.x.x + */ + + /* Create table with mask x.x.u.u.u - table 0 */ + bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len); + bitmap_set(table_attr[0].mask, 16, 24); /* Set care on #3-5 byte*/ + + /* Create table with mask u.u.u.x.x - table 1 */ + bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len); + bitmap_set(table_attr[1].mask, 0, 24); /* Set care on #1-3 byte*/ + + /* Create table with mask x.u.x.x.x - table 2 */ + bitmap_clear(table_attr[2].mask, 2, table_attr[2].mask_len); + bitmap_set(table_attr[2].mask, 8, 8); /* Set care on #2 byte*/ + + /* Create rules */ + /* Create item0 x.x.3.5.5 prio 7 */ + tpi_arr[0].priority = 7; + tpi_arr[0].priv = NULL; + bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */ + bitmap_set(tpi_arr[0].key, 29, 1); /* Set 5 on #4 byte */ + bitmap_set(tpi_arr[0].key, 31, 1); /* Set 5 on #4 byte */ + bitmap_set(tpi_arr[0].key, 37, 1); /* Set 5 on #5 byte */ + bitmap_set(tpi_arr[0].key, 39, 1); /* Set 5 on #5 byte */ + + /* Create item1 1.2.3.x.x prio 7 */ + tpi_arr[1].priority = 7; + tpi_arr[1].priv = NULL; + bitmap_set(tpi_arr[1].key, 7, 1); /* Set 1 on #1 byte */ + bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */ + + /* Create item2 x.x.3.5.x prio 3 */ + tpi_arr[2].priority = 3; + tpi_arr[2].priv = NULL; + bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */ + bitmap_set(tpi_arr[2].key, 29, 1); /* Set 5 on #4 byte */ + bitmap_set(tpi_arr[2].key, 31, 1); /* Set 5 on #4 byte */ + + /* Create item3 x.2.x.x.x prio 10 */ + tpi_arr[3].priority = 10; + tpi_arr[3].priv = NULL; + bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */ + + /* Create item4 x.x.x.x.6 prio 7 */ + tpi_arr[4].priority = 7; + tpi_arr[4].priv = NULL; + bitmap_set(tpi_arr[4].key, 37, 2); /* Set 6 on #5 byte */ + + /* Create item5 2.2.3.x.x prio 5 */ + tpi_arr[5].priority = 5; + tpi_arr[5].priv = NULL; + bitmap_set(tpi_arr[5].key, 7, 1); /* Set 2 on #1 byte */ + bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[5].key, 22, 2); /* Set 3 on #3 byte */ + + table_arr[0] = prune_table_create(prune, table_attr[0].mask, + table_attr[0].mask_len, + (int *)(uintptr_t)table_attr[0].table_id); + if (IS_ERR(table_arr[0])) + return PTR_ERR(table_arr[0]); + + item_arr[0] = prune_item_create(prune, table_arr[0], + tpi_arr[0].priority, + tpi_arr[0].key, tpi_arr[0].priv, + &tpi_arr[0].non_def_prune_vector); + if (IS_ERR(item_arr[0])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[0], NULL, 0, + tpi_arr[0].non_def_prune_vector)) + return -EBADE; + + table_arr[1] = prune_table_create(prune, table_attr[1].mask, + table_attr[1].mask_len, + (int *)(uintptr_t)table_attr[1].table_id); + if (IS_ERR(table_arr[1])) + return PTR_ERR(table_arr[1]); + + item_arr[1] = prune_item_create(prune, table_arr[1], + tpi_arr[1].priority, + tpi_arr[1].key, tpi_arr[1].priv, + &tpi_arr[1].non_def_prune_vector); + if (IS_ERR(item_arr[1])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[1], NULL, 0, + tpi_arr[1].non_def_prune_vector)) + return -EBADE; + + item_arr[2] = prune_item_create(prune, table_arr[0], + tpi_arr[2].priority, + tpi_arr[2].key, tpi_arr[2].priv, + &tpi_arr[2].non_def_prune_vector); + if (IS_ERR(item_arr[2])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[2], NULL, 0, + tpi_arr[2].non_def_prune_vector)) + return -EBADE; + + table_arr[2] = prune_table_create(prune, table_attr[2].mask, + table_attr[2].mask_len, + (int *)(uintptr_t)table_attr[2].table_id); + if (IS_ERR(table_arr[2])) + return PTR_ERR(table_arr[2]); + + item_arr[3] = prune_item_create(prune, table_arr[2], + tpi_arr[3].priority, + tpi_arr[3].key, tpi_arr[3].priv, + &tpi_arr[3].non_def_prune_vector); + if (IS_ERR(item_arr[3])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[3], prune_val_arr_3, 3, + tpi_arr[3].non_def_prune_vector)) + return -EBADE; + + item_arr[4] = prune_item_create(prune, table_arr[0], + tpi_arr[4].priority, + tpi_arr[4].key, tpi_arr[4].priv, + &tpi_arr[4].non_def_prune_vector); + if (IS_ERR(item_arr[4])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[4], NULL, 0, + tpi_arr[4].non_def_prune_vector)) + return -EBADE; + + item_arr[5] = prune_item_create(prune, table_arr[1], + tpi_arr[5].priority, + tpi_arr[5].key, tpi_arr[5].priv, + &tpi_arr[5].non_def_prune_vector); + if (IS_ERR(item_arr[5])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[5], prune_val_arr_5, 3, + &tpi_arr[5].non_def_prune_vector)) + return -EBADE; + + /* Free resources */ + err = prune_item_destroy(item_arr[0]); + if (err) + return err; + + err = prune_item_destroy(item_arr[1]); + if (err) + return err; + + err = prune_item_destroy(item_arr[2]); + if (err) + return err; + + err = prune_item_destroy(item_arr[3]); + if (err) + return err; + + err = prune_table_destroy(table_arr[2]); + if (err) + return err; + + err = prune_item_destroy(item_arr[4]); + if (err) + return err; + + err = prune_table_destroy(table_arr[0]); + if (err) + return err; + + err = prune_item_destroy(item_arr[5]); + if (err) + return err; + + err = prune_table_destroy(table_arr[1]); + if (err) + return err; + + prune_destroy(prune); + + prune_item_arr_destroy(tpi_arr, ITEMS_6); + table_attr_destroy(table_attr, TABLES_3); + + return 0; +} + +static int test_prune_add_new_table_with_item_subsequent_to_curr_tables(void) +{ + struct test_prune_table_attr table_attr[TABLES_3]; + struct prune_table *table_arr[TABLES_3]; + struct test_prune_item tpi_arr[ITEMS_8]; + struct prune_item *item_arr[ITEMS_8]; + bool prune_val_arr_5[2] = {false, true}; + unsigned int nbits = 40; + struct prune *prune; + int err; + + prune = prune_create(nbits, &test_prune_add_new_table_subsequent_ops, + NULL); + if (IS_ERR(prune)) + return PTR_ERR(prune); + + err = table_attr_create(table_attr, nbits, TABLES_3); + if (err) + return err; + + err = test_prune_item_arr_create(tpi_arr, ITEMS_8, nbits); + if (err) + return err; + + /* Tables: + * table 0: u.u.u.x.x + * table 1: x.u.u.u.x + * table 2: x.x.u.u.u + */ + + /* Create table with mask u.u.u.x.x - table 0 */ + bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len); + bitmap_set(table_attr[0].mask, 0, 24); /* Set care on #1-3 byte*/ + table_arr[0] = prune_table_create(prune, table_attr[0].mask, + table_attr[0].mask_len, + (int *)(uintptr_t)table_attr[0].table_id); + if (IS_ERR(table_arr[0])) + return PTR_ERR(table_arr[0]); + + /* Create table with mask x.u.u.u.x table 1 */ + bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len); + bitmap_set(table_attr[1].mask, 8, 24); /* Set care on #2-4 byte*/ + table_arr[1] = prune_table_create(prune, table_attr[1].mask, + table_attr[1].mask_len, + (int *)(uintptr_t)table_attr[1].table_id); + if (IS_ERR(table_arr[1])) + return PTR_ERR(table_arr[1]); + + /* Create rules */ + /* Create item0 1.2.3.x.x prio 10 */ + tpi_arr[0].priority = 10; + tpi_arr[0].priv = NULL; + bitmap_set(tpi_arr[0].key, 7, 1); /* Set 1 on #1 byte */ + bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */ + + /* Create item1 x.2.3.4.x prio 3 */ + tpi_arr[1].priority = 3; + tpi_arr[1].priv = NULL; + bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */ + bitmap_set(tpi_arr[1].key, 29, 1); /* Set 4 on #4 byte */ + + /* Create item2 x.x.3.9.9 prio 1 */ + tpi_arr[2].priority = 1; + tpi_arr[2].priv = NULL; + bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */ + bitmap_set(tpi_arr[2].key, 28, 1); /* Set 9 on #4 byte */ + bitmap_set(tpi_arr[2].key, 31, 1); /* Set 9 on #4 byte */ + bitmap_set(tpi_arr[2].key, 36, 1); /* Set 9 on #5 byte */ + bitmap_set(tpi_arr[2].key, 39, 1); /* Set 9 on #5 byte */ + + /* Create item3 2.2.4.x.x prio 5 */ + tpi_arr[3].priority = 5; + tpi_arr[3].priv = NULL; + bitmap_set(tpi_arr[3].key, 6, 1); /* Set 2 on #1 byte */ + bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[3].key, 21, 1); /* Set 4 on #3 byte */ + + /* Create item4 x.x.4.5.x prio 2 */ + tpi_arr[4].priority = 2; + tpi_arr[4].priv = NULL; + bitmap_set(tpi_arr[4].key, 21, 1); /* Set 4 on #3 byte */ + bitmap_set(tpi_arr[4].key, 29, 1); /* Set 5 on #4 byte */ + bitmap_set(tpi_arr[4].key, 31, 1); /* Set 5 on #4 byte */ + + /* Create item5 x.2.4.7.x prio 8 */ + tpi_arr[5].priority = 8; + tpi_arr[5].priv = NULL; + bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[5].key, 21, 1); /* Set 4 on #3 byte */ + bitmap_set(tpi_arr[5].key, 29, 3); /* Set 7 on #4 byte */ + + /* Create item6 x.2.x.9.x prio 8 */ + tpi_arr[6].priority = 8; + tpi_arr[6].priv = NULL; + bitmap_set(tpi_arr[6].key, 14, 1); /* Set 2 on #2 byte */ + bitmap_set(tpi_arr[6].key, 28, 1); /* Set 9 on #4 byte */ + bitmap_set(tpi_arr[6].key, 31, 1); /* Set 9 on #4 byte */ + + item_arr[0] = prune_item_create(prune, table_arr[0], + tpi_arr[0].priority, + tpi_arr[0].key, tpi_arr[0].priv, + &tpi_arr[0].non_def_prune_vector); + if (IS_ERR(item_arr[0])) + return -EBADE; + /* default prune vector */ + if (!test_prune_check_prune_vector(item_arr[0], NULL, 0, + tpi_arr[0].non_def_prune_vector)) + return -EBADE; + + item_arr[1] = prune_item_create(prune, table_arr[1], + tpi_arr[1].priority, + tpi_arr[1].key, tpi_arr[1].priv, + &tpi_arr[1].non_def_prune_vector); + if (IS_ERR(item_arr[1])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[1], NULL, 0, + tpi_arr[1].non_def_prune_vector)) + return -EBADE; + + item_arr[3] = prune_item_create(prune, table_arr[0], + tpi_arr[3].priority, + tpi_arr[3].key, tpi_arr[3].priv, + &tpi_arr[3].non_def_prune_vector); + if (IS_ERR(item_arr[3])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[3], NULL, 0, + tpi_arr[3].non_def_prune_vector)) + return -EBADE; + + item_arr[5] = prune_item_create(prune, table_arr[1], + tpi_arr[5].priority, + tpi_arr[5].key, tpi_arr[5].priv, + &tpi_arr[5].non_def_prune_vector); + if (IS_ERR(item_arr[5])) + return -EBADE; + + if (!test_prune_check_prune_vector(item_arr[5], prune_val_arr_5, 2, + tpi_arr[5].non_def_prune_vector)) + return -EBADE; + + item_arr[6] = prune_item_create(prune, table_arr[1], + tpi_arr[6].priority, + tpi_arr[6].key, tpi_arr[6].priv, + &tpi_arr[6].non_def_prune_vector); + if (IS_ERR(item_arr[6])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[6], NULL, 0, + tpi_arr[6].non_def_prune_vector)) + return -EBADE; + + /* Create table with mask x.x.u.u.u table 2 */ + bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len); + bitmap_set(table_attr[2].mask, 16, 24); /* Set care on #2-5 byte*/ + table_arr[2] = prune_table_create(prune, table_attr[2].mask, + table_attr[2].mask_len, + (int *)(uintptr_t)table_attr[2].table_id); + if (IS_ERR(table_arr[2])) + return PTR_ERR(table_arr[2]); + + item_arr[2] = prune_item_create(prune, table_arr[2], + tpi_arr[2].priority, + tpi_arr[2].key, tpi_arr[2].priv, + &tpi_arr[2].non_def_prune_vector); + if (IS_ERR(item_arr[2])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[2], NULL, 0, + tpi_arr[2].non_def_prune_vector)) + return -EBADE; + + item_arr[4] = prune_item_create(prune, table_arr[2], + tpi_arr[4].priority, + tpi_arr[4].key, tpi_arr[4].priv, + &tpi_arr[4].non_def_prune_vector); + if (IS_ERR(item_arr[4])) + return -EBADE; + /* Default prune vector */ + if (!test_prune_check_prune_vector(item_arr[4], NULL, 0, + tpi_arr[4].non_def_prune_vector)) + return -EBADE; + + err = prune_item_destroy(item_arr[0]); + if (err) + return err; + + err = prune_item_destroy(item_arr[1]); + if (err) + return err; + + err = prune_item_destroy(item_arr[2]); + if (err) + return err; + + err = prune_item_destroy(item_arr[3]); + if (err) + return err; + + err = prune_item_destroy(item_arr[4]); + if (err) + return err; + + err = prune_table_destroy(table_arr[2]); + if (err) + return err; + + err = prune_item_destroy(item_arr[5]); + if (err) + return err; + + err = prune_item_destroy(item_arr[6]); + if (err) + return err; + + err = prune_table_destroy(table_arr[0]); + if (err) + return err; + + err = prune_table_destroy(table_arr[1]); + if (err) + return err; + + prune_destroy(prune); + + prune_item_arr_destroy(tpi_arr, ITEMS_8); + table_attr_destroy(table_attr, TABLES_3); + + return 0; +} + +static int test_prune(void) +{ + int err; + + err = test_prune_basic(); + if (err) + return err; + + err = test_prune_flows_add_delete_items_1(); + if (err) + return err; + + err = test_prune_add_new_table_with_item_subsequent_to_curr_tables(); + if (err) + return err; + + err = test_prune_flows_add_delete_item_2(); + if (err) + return err; + + return 0; +} + +static int __init test_prune_init(void) +{ + return test_prune(); +} + +static void __exit test_prune_exit(void) +{ +} + +module_init(test_prune_init); +module_exit(test_prune_exit); + +MODULE_LICENSE("Dual BSD/GPL"); +MODULE_AUTHOR("Tal Bar "); +MODULE_DESCRIPTION("Test module for prune"); From patchwork Sun Aug 12 15:57:20 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tal Bar X-Patchwork-Id: 10563753 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 6A61D15A6 for ; Sun, 12 Aug 2018 20:38:29 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 5875829044 for ; Sun, 12 Aug 2018 20:38:29 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 4AB3F29073; Sun, 12 Aug 2018 20:38:29 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=2.0 tests=BAD_ENC_HEADER,BAYES_00, DKIM_SIGNED,MAILING_LIST_MULTI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.ozlabs.org (lists.ozlabs.org [203.11.71.2]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id CD99129044 for ; Sun, 12 Aug 2018 20:38:27 +0000 (UTC) Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 41pW0K5KgczF0Rr for ; Mon, 13 Aug 2018 06:38:25 +1000 (AEST) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="f1MFflZ0"; dkim-atps=neutral X-Original-To: linux-mlxsw@lists.ozlabs.org Delivered-To: linux-mlxsw@lists.ozlabs.org Authentication-Results: lists.ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=mellanox.com (client-ip=40.107.5.59; helo=eur03-ve1-obe.outbound.protection.outlook.com; envelope-from=talb@mellanox.com; receiver=) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="f1MFflZ0"; dkim-atps=neutral Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50059.outbound.protection.outlook.com [40.107.5.59]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 41pVzt49d4zF0Rr for ; Mon, 13 Aug 2018 06:38:02 +1000 (AEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Mellanox.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=SuRitTGPGl/c3O4EwHk/ewAjUDMqrfaGqmKfYysPcAo=; b=f1MFflZ0NVExYzm2G8p9LusTHk2bBqWE49UXAjrokeUa3CeIwe52nOsYBv199cSKS9NcETMRAnKfWKAO2CRNAwViXHzzZFM6Nz18TK/+u0IQUbj05WRc/flUHDXN/OlUgVV2ixYkQK6TNTTPia+n8pPsIMkS1pRd7jzAKBVy/V0= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=talb@mellanox.com; Received: from dev-r-vrt-156.mtr.labs.mlnx (37.142.13.130) by DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1038.19; Sun, 12 Aug 2018 15:57:42 +0000 From: Tal Bar To: idosch@mellanox.com, jiri@mellanox.com Subject: [net-next mlxsw v10 2/3] lib: Add debugfs utility to prune library Date: Sun, 12 Aug 2018 18:57:20 +0300 Message-Id: <1534089441-20653-3-git-send-email-talb@mellanox.com> X-Mailer: git-send-email 2.8.0 In-Reply-To: <1534089441-20653-1-git-send-email-talb@mellanox.com> References: <1534089441-20653-1-git-send-email-talb@mellanox.com> MIME-Version: 1.0 X-Originating-IP: [37.142.13.130] X-ClientProxiedBy: AM4PR05CA0001.eurprd05.prod.outlook.com (2603:10a6:205::14) To DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: b1b83d8e-d815-43f2-4b58-08d6006c572c X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989117)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:DB6PR05MB3287; X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 3:594Wc3bMFbdfv3RDGCcs+z4JES3m+kQeyga5oKc0KF+D0WKRrNQCwVZBDFk9ITWha0fmi6hCEoYMmk5ft+q9xodUUhr0QSIp/AFNe6x1wQRQ40cpOSZ2UwcETSwIJpJ74jCbhm2rSQTGzuE+f6oKZGb+IGw4pyTv4boKuaUJ7ugUNUkh8y7awxcnkm2VvVZ/VrsY1NWpRKwoJO/rJXO+OsMj5St9qsL8/fmCCqbhXtBcJ+jLdGTalejZg5sIQh+T; 25:gq/St1kNRA+YJ09TAsdFXD3aOyszLl3CC2NOu138T9HQtWrCVzpUWIwKWKVF230JAlEKCoHxgTEYkaOzNdMekFqLfrB7f7uXvvddKsWiGk78oV9an5DvsHs+upUfI0yTbETEiewB9WgRpUObSxRpSSb9Bp7hfsEqDFgUsBaYfBSBQSt7KuB9pDRYGCU4JmD1iy7VU6zfYlpngTatNiJjkQHYQphzKtiC52jGSAIDAskmZZBLGoG+tw8kHfYKI+vZcWWVPqwthWUlE/11rVqOyh0413Rpi0G1HBEAUEL0tVG2cO6wUFLYuXZKmuLoYWrcIkbTu+nUpXZLGjoDDki//g==; 31:NFGK7SF6ZiDFSXS8BxnCpMAxITXi6nGVHUV56/ZPUOlzweSHEh7P1Ev6vZIwqypg7mfVViatlrNy2R18qo+fHPUTFMdqLFMxw4+qoCZPgvZHFnyVWKo6EG633cCPDzZkuMxF3HxQsRFFPDiN7HLg/6mr0bzwEmX+Nl5PDLJrJri/dJ6ZDkfyvJAp/2oWtgViuDNPzyynejVb3Y9Iom8mhqEXi8Zx5Myynh+NtycV2ZU= X-MS-TrafficTypeDiagnostic: DB6PR05MB3287: X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 20:hNAvb4EYfdV0zVW+m/PZ5rX3ZvA30InsCusEuLTNtA9An9WLmrM/HVFF4U6Ykroi5AKZEAyu6xQvmUiZ4L+nHxZUtOybVhuLjEPJzRZ3SI9nUy0SKWd0C3Q4P5r2slhX3kukDqjZNFV94qUvP1iKmXFUMnwLqPM8SHzLW14m84gUUhS/QpQwaStrQgFBa9kD0udYze9Eapg+z28c6CsIjeSxrVEPMWX4mlwRlLeo6U6szUvMkKtj2QGyBl523CYoYdxLkOLNufBnFEL+LY/4E5knJWC12XM0Nwg3VkeZSxDvNnhHHPQpSjDvduiCgq7bzrNH06C/Kmbjt3JaVjWRRCVqqbt5rvFPyVe2zDZEPxnjyjRfi+k5Gg/izkPT0GA45FUAbLlVWKQBz6l1LDwf7YgMAkbig4aTHv0rolGBmgIV6SGVd/tjfi5bMmUJNoLKk2NiJqdYPWi8TnGm+AwkTcwH/LKyp9Nqrl54XfDY2IsZeJ/sjlN3OaZuB/gfNhua; 4:ameJAawgyQgtYIsPqZLOQwSwILjDJWZIkFGBP2hQJV4mOXH83eWjPjqEBFm7OJezm3nKTIIYXwc4zhaSIw0vPu3ab96R+Ro5MyO4qDYwMIkAoxbjc1LIfx9BXRlXP/hVKot13ED+AYEYXJVWAaWns+WnHY0nlC/qRnL72o1Vsy10ylrSX8IsZqwRYS3ETDJyGZW1IJe+cPCZhuH1yGagCJDYIn7iz22DJVT5aDQk2HgEO+vR8PMkDOTUGeLrll/qC9cbE31pRnopBvaNp9oOlQ== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(10201501046)(3231311)(944501410)(52105095)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123564045)(20161123558120)(20161123560045)(6072148)(201708071742011)(7699016); SRVR:DB6PR05MB3287; BCL:0; PCL:0; RULEID:; SRVR:DB6PR05MB3287; X-Forefront-PRVS: 0762FFD075 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(396003)(346002)(376002)(136003)(366004)(39860400002)(45074003)(199004)(189003)(6512007)(6636002)(2616005)(50226002)(6506007)(386003)(81166006)(81156014)(53936002)(956004)(6116002)(68736007)(575784001)(8676002)(86362001)(8936002)(6486002)(2906002)(3846002)(11346002)(14444005)(5660300001)(16526019)(52116002)(106356001)(50466002)(48376002)(47776003)(66066001)(25786009)(36756003)(316002)(16586007)(305945005)(4326008)(6666003)(26005)(7736002)(476003)(478600001)(105586002)(85306007)(446003)(107886003)(486006)(76176011)(51416003)(97736004); DIR:OUT; SFP:1101; SCL:1; SRVR:DB6PR05MB3287; H:dev-r-vrt-156.mtr.labs.mlnx; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; Received-SPF: None (protection.outlook.com: mellanox.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; DB6PR05MB3287; 23:QSEjTVY4KVke/X2ruHk8OZ0jjc+fNSDzp1mAJnCw7?= hQW/OF+mp4JJMU9kvDdw+iIyaio/z3Eac5wvplY0AzEui6aXehjhi6YDO5uENPzfC3kKqw4+nb1zTuGpyBUIKlpx2xUkGrpHb+QglQCTqRr71mXGMYm1cO6hm4KLE64BCEUnUjB+A8gYQuzXOdDjKcXi5ePPCQtIN616HOZmtX0R5jhsBwNoKYiqlmDbjVp3weuz7fGOfSPH35EaLFZg07e9pPRO5bTN3TZvWBbCoSexw9gzLg42aTy1ed/rk91w5aFGcjIKdWu9MTOh5awd4swIkkKXtUqTAnNRmXJaC8HgyQoIg1Asp2vBn13yS1Xd56EzMua3hDA3ymf6OI8d80gwz/XBLsZePiyxntwy9bw6laKop2wHn96uH/tWekvav8yGt0R3bz8Lr8cbkuaH0wy8S3l3HNxfgOXTKqBqj9bjfJw00PQhYcMEUXO9OY7p1k52JeFI3YYFnY9hyJo7M0GT0OQTXkwWsCSkUopslOjX+XR8eBIowVUrLUmcM5lbSx+kKfpvAGDGC4X+9k2eNwDHiEKw0BMUTUf5kDil7c0XCr4YGB8dfHourmrNNnnMg/vw4ll/tmOxBO6s1xRj4Dph5at3BNXJTP0iSJ/8fg92sxz+B73WhJWiZl0KRWXVSib9FAZLEsB5eYdISdi1tCjQXeJFakx0Yj9DDEVgszUQyfA9gizYIrDtmF1RJHlL5hVYSATZ5JCr1kNYqLNx1zeoIb61iPC3ZbqLRupZKr41UQanrQpaZ9/MaGT3lK6EbJ+3D59dlLFbV1qN+pkiM2+qTL3b0xTtWFcoHIeTQQ3TBZBDBpJrtr2Nok9ZKIVGHu5sORnZdUyILChGBYAqJW50/Vla5futWXWjcwkq+X6e/Woa0jJYHlBLDrf1KIOP2hbCXgJAHsE/ziuXCw5FGx2nLaeJExvdTFcpteIDj5AanUycS5l5EYrY9abaVZNNxV1CZ/BdPyAp5sgLROVJp6oQMLIsqvmR8a70JCl6MSBkOcE0zEZJdgn2hDH79ZPLRZiq4S3nOY+DvLrmYwQsPqFbaSULAEA5wKKpZtOGbgOT7cmqvd7iJX8ecS4c0s5WxoKZG5JOdap+owhX0uQDX98X9m5o78tzXh+uQcd54mBhQARc9XgGfHjAxL/1rGHaYjBA4ZOlgvbzJJ20JFI6wbhj+4xZGLtGjaKnynxUuC4ek0vCg6M/OSkRRSxezqu6YbZSpMrJXZetRoZsVeQArUB X-Microsoft-Antispam-Message-Info: 1YzMHqan4ZRL8ei/6irFkH6fXtUna/QSL/cIUFuE79xczBzh9/vbuV/v1sJ8kcuNDJQIFttfxXf4STO/w68HOjGoQZOFO39jDBGfve3OdGVTYcyy/nO0xXXH+lEPkwAT/5q+QvL3NGQSNRY9fXDdWD2DDvwjlkDM8Te/bJ0LXhvGlFyJTpS6I8n0SJTlCiajbeeNs3xUeWJDgpgs+Jqk6iAdTwaz3rzDwfv+L1+BUB1NqEjFF2lK06xAMO2WU1wvdPJtB0C0myp6JjWaxoazfQfInZUPoENtkxvdbXSZwyKhvS+jcuLvXxOINwKhPOOaqFCe2KMEs9H7QVi4sKd06zsbcjbasHb7um+amxuBq4Q= X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 6:vjcXcncJBR0STsqpY9fOwT3Y8K8+IqVk6W4Rp9flApEMcTLqX4SRswXHHlgmVCCJDM7MZCiBvMqXq1s5td1hWR6Vpq7GirHNNm/AWqe0Vc/+NhmkBliTlyqDxga/YXW+j/IftG0hKdsSDJqTsV25ZOi1UtW46ohbZNR6+B8kbM1u1Dzg6KxHK2aKa9GK9JgM1InNCoJrt2X2pVMRL2vMx3kgbQSY7MaUbSIzZ4vbPuIhn/a8FIYe6ZW1Qn6oQkzOmz2s4E1Q0d65P74fOarIWiAW7mUA5m1wmn2EujAcjUkQTGvDdvn49ez2CqCOHm6VH12x8ZqfZ8MuM1rGi0/gUyyUvHWMX80k7vORM5jmsCWnaudxMlS4ZN4HYnSqRALcZjDkNfsfaiEwmmmFgrX1MDulv2mdN8GMueB+wdBP/nuWlN4unIlt6KlClyuFzbqWFohdB34KETx5KLpUJTYvAw==; 5:QAEwE1SCINSkljlSQXoS7zMGxFlNpAbkkOYE/0elYs6ErEBUadmVUOWiD7t+B8TyrxtD5p90/k9qVn+7cXVjpd+yn0bMc+2Vu/36qaPiDwPSAyF1XWAzhBSLD2ZvqfEv6XqXHDVTjzNoeXvrUcks2reYHXS0JneQbnR0rfffVQQ=; 7:uXjyEI0jYE8MuUEu8qhdwVdqsML8egBTKVmND5/nKh40okgs5UoF07sYulFSua7hW/4SQx+6COrG2smDuVanrCCivDANH6QKWw5Ehl6QxM8pZ6TzJqC7PRkdhHp+Rah1LEYGx7oQHENlrnI0Brje2OV54EW+7clf3rkKzfNbOOe4we0UH8y+3v8EdN0zW8EgCZkpcA3VlEx2JJRrtjJoS9gnfEng8Tx7lks65I+h5/ZlgeHMZa0XXrjbwDpTEDqn SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: Mellanox.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Aug 2018 15:57:42.9746 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: b1b83d8e-d815-43f2-4b58-08d6006c572c X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: a652971c-7d2e-4d9b-a6a4-d149256f461b X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR05MB3287 X-BeenThere: linux-mlxsw@lists.ozlabs.org X-Mailman-Version: 2.1.27 Precedence: list List-Id: mlxsw driver development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-internal@mellanox.com Errors-To: linux-mlxsw-bounces+patchwork-linux-mlxsw=patchwork.kernel.org@lists.ozlabs.org X-Virus-Scanned: ClamAV using ClamSMTP This patch provides a debugfs /sys/kernel/debug/prune_debug to represent the prune object state so admin can investigate why for some entries there is latency due to needed lookups. In order to check the current status user should: "cat /sys/kernel/debug/prune_debug" An example output: prune ----- prune priv: (null) number of table in prune object: 2 table info ---------- table id: 0000000021cafe9f table priv: (null) table mask: 16777215 item info --------- item key: 12599424 item prio: 7 item priv: (null) item prune vector: table: (null) is pruned: Yes table: 00000000db28e393 is pruned: No intersec table info ------------------- table mask: 16776960 niegh table priv: 00000000db28e393 intersec entry info ------------------- mask: 12599296 intersec element info: entry prio: 12599424 entry prio: 7 neigh element info: entry key: 549470208 entry prio: 5 entry key: 2696953856 entry prio: 10 table info ---------- table id: 0000000041acfd40 table priv: 00000000db28e393 table mask: 4294967040 item info --------- item key: 549470208 item prio: 5 item priv: (null) item prune vector: table: (null) is pruned: Yes table: 00000000db28e393 is pruned: Yes item info --------- item key: 2696953856 item prio: 10 item priv: (null) item prune vector: table: (null) is pruned: No table: 00000000db28e393 is pruned: Yes intersec table info ------------------- table mask: 16776960 niegh table priv: (null) intersec entry info ------------------- mask: 12599296 intersec element info: entry prio: 549470208 entry prio: 5 entry prio: 2696953856 entry prio: 10 neigh element info: entry key: 12599424 entry prio: 7 Signed-off-by: Tal Bar --- include/linux/prune.h | 2 + lib/prune.c | 323 ++++++++++++++++++++++++++++++++++++++++++++++---- lib/test_prune.c | 4 +- 3 files changed, 307 insertions(+), 22 deletions(-) diff --git a/include/linux/prune.h b/include/linux/prune.h index 4334dc9..64f0b84 100644 --- a/include/linux/prune.h +++ b/include/linux/prune.h @@ -65,6 +65,8 @@ struct prune_ops { struct prune_table *table, bool pruned); }; +int prune_init(void); +void prune_fini(void); struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops, void *priv); void prune_destroy(struct prune *prune); diff --git a/lib/prune.c b/lib/prune.c index 58e6f78..896f7a2 100644 --- a/lib/prune.c +++ b/lib/prune.c @@ -9,10 +9,24 @@ #include #include #include +#include #include #include #include #include +#include +#include +#include +#include + +/* + * dentry for debugsfs purpose + */ +static struct dentry *dentry; +/* + * The list of all allocated prune objects + */ +static struct list_head prune_object_list; /* * struct prune_table_entry - hold the item configuration and its prune vector. @@ -42,6 +56,7 @@ struct prune_intersec_table_list_elem { /* * struct prune_intersec_table - Represent the intersection of two prune tables. * @entry_ht: Hash-table of prune_intersec_table_entry. + * @items_list: A walker for items_ht. * @neigh_table: A pointer to the table which this table intersects. * @list: Node of table's intersec_table_list. * @mask: Intersection mask of the the two tables. @@ -51,6 +66,7 @@ struct prune_intersec_table_list_elem { */ struct prune_intersec_table { struct rhashtable entry_ht; + struct list_head items_list; struct prune_table *neigh_table; struct list_head list; unsigned long mask[0]; @@ -72,6 +88,7 @@ struct prune_intersec_table { * @neigh_table_elem_list: Contain list of entries in the neighbor table * pointed by the neigh_table field in * prune_intersec_table struct. + * @list: Node of items_list in struct prune_intersec_table. * * The structure is used to find the intersection of new prune item with the * current one, and check whether the new item should be pruned or not. @@ -82,6 +99,7 @@ struct prune_intersec_table_entry { struct prune_intersec_table *intersec_table; struct list_head intersec_table_elem_list; struct list_head neigh_table_elem_list; + struct list_head list; }; /* @@ -116,6 +134,7 @@ struct prune_table { * @priv: User data. * @mask_len: The mask len in bits which this prune object * support. + * @list: Node in prune_object_list. */ struct prune { const struct prune_ops *ops; @@ -123,6 +142,211 @@ struct prune { struct list_head table_list; void *priv; unsigned int mask_len; + struct list_head list; +}; + +static void prune_vector_items_dump(struct seq_file *seq, + struct prune_table_entry *entry) +{ + struct prune_vector_item *vector_item; + + seq_puts(seq, "\t\titem prune vector:\n"); + list_for_each_entry_rcu(vector_item, &entry->prune_vector, list) { + seq_printf(seq, "\t\t\ttable: %p\t is pruned: %s\n", + vector_item->table->priv, + vector_item->pruned ? "Yes" : "No"); + } +} + +static void prune_table_items_dump(struct seq_file *seq, + struct prune_table *table) +{ + struct prune_table_entry *entry; + char *buf; + + buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + + list_for_each_entry_rcu(entry, &table->entry_list, list) { + seq_puts(seq, "\t\titem info\n"); + seq_puts(seq, "\t\t---------\n"); + if (buf) { + bitmap_print_to_pagebuf(false, buf, entry->item.key, + table->prune->mask_len); + seq_printf(seq, "\t\titem key: %s\n", buf); + } + seq_printf(seq, "\t\titem prio: %u\n", entry->item.priority); + seq_printf(seq, "\t\titem priv: %p\n", entry->item.priv); + + prune_vector_items_dump(seq, entry); + } + kfree(buf); +} + +static void +prune_intersec_item_list_dump(struct seq_file *seq, + struct prune_intersec_table *intersec_table) +{ + struct prune_intersec_table_entry *intersec_entry; + struct prune_intersec_table_list_elem *intersec_item; + struct prune_intersec_table_list_elem *neigh_item; + unsigned int mask_len = intersec_table->neigh_table->prune->mask_len; + char *buf; + + buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + + list_for_each_entry_rcu(intersec_entry, &intersec_table->items_list, + list) { + seq_puts(seq, "\t\t\tintersec entry info\n"); + seq_puts(seq, "\t\t\t-------------------\n"); + if (buf) { + bitmap_print_to_pagebuf(false, buf, + intersec_entry->ht_key, + mask_len); + seq_printf(seq, "\t\t\t\t mask: %s\n", + buf); + } + seq_puts(seq, "\t\t\t\t intersec element info:\n"); + list_for_each_entry_rcu(intersec_item, + &intersec_entry->intersec_table_elem_list, + list) { + seq_printf(seq, "\t\t\t\t\tentry prio: %lu\n", + *intersec_item->entry->item.key); + seq_printf(seq, "\t\t\t\t\tentry prio: %u\n\n", + intersec_item->entry->item.priority); + } + seq_puts(seq, "\t\t\t\t neigh element info:\n"); + list_for_each_entry_rcu(neigh_item, + &intersec_entry->neigh_table_elem_list, + list) { + if (buf) { + bitmap_print_to_pagebuf(false, buf, + neigh_item->entry->item.key, + mask_len); + seq_printf(seq, "\t\titem key: %s\n", buf); + } + seq_printf(seq, "\t\t\t\t\tentry prio: %u\n\n", + neigh_item->entry->item.priority); + } + } + kfree(buf); +} + +static void prune_intersec_tables_dump(struct seq_file *seq, + struct prune_table *table) +{ + struct prune_intersec_table *intersec_table; + + list_for_each_entry_rcu(intersec_table, &table->intersec_table_list, + list) { + seq_puts(seq, "\t\tintersec table info\n"); + seq_puts(seq, "\t\t-------------------\n"); + seq_printf(seq, "\t\ttable mask: %lu\n", *intersec_table->mask); + seq_printf(seq, "\t\tniegh table priv: %p\n", + intersec_table->neigh_table->priv); + prune_intersec_item_list_dump(seq, intersec_table); + } +} + +static void prune_table_dump(struct seq_file *seq, struct prune *prune) +{ + struct prune_table *table; + unsigned int table_cnt = 0; + char *buf; + + buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + + list_for_each_entry_rcu(table, &prune->table_list, list) { + seq_puts(seq, "\ttable info\n"); + seq_puts(seq, "\t----------\n"); + seq_printf(seq, "\ttable id: %p\n", table); + seq_printf(seq, "\ttable priv: %p\n", table->priv); + if (buf) { + bitmap_print_to_pagebuf(false, buf, table->mask, + table->prune->mask_len); + seq_printf(seq, "\ttable mask: %s\n", buf); + } + prune_table_items_dump(seq, table); + seq_puts(seq, "\n"); + prune_intersec_tables_dump(seq, table); + seq_puts(seq, "\n\n"); + table_cnt++; + } + seq_printf(seq, "Number of tables in prune object: %d\n", table_cnt); + + kfree(buf); +} + +static void prune_obj_dump(struct seq_file *seq, struct prune *prune) +{ + seq_puts(seq, "prune\n"); + seq_puts(seq, "-----\n"); + seq_printf(seq, "prune priv: %p\n", prune->priv); + prune_table_dump(seq, prune); + seq_puts(seq, "\n\n"); +} + +static void *prune_seq_start(struct seq_file *seq, loff_t *pos) +{ + struct prune *prune; + loff_t n = *pos; + + rcu_read_lock(); + if (!list_empty(&prune_object_list)) { + if (n-- == 0) { + prune = list_first_entry(&prune_object_list, + typeof(*prune), + list); + return prune; + } + } + return NULL; +} + +static void *prune_seq_next(struct seq_file *seq, void *v, loff_t *pos) +{ + struct prune *prev_prune_obj = v; + struct prune *next_prune_obj = NULL; + + ++(*pos); + + next_prune_obj = list_next_entry(prev_prune_obj, list); + if (&next_prune_obj->list == &prune_object_list) + return NULL; + else + return next_prune_obj; +} + +static void prune_seq_stop(struct seq_file *seq, void *v) +{ + rcu_read_unlock(); /*unlock the rcu_lock taken at start */ +} + +static int prune_seq_show(struct seq_file *seq, void *v) +{ + struct prune *prune = v; + + prune_obj_dump(seq, prune); + return 0; +} + +static const struct seq_operations prune_seq_ops = { + .start = prune_seq_start, + .next = prune_seq_next, + .stop = prune_seq_stop, + .show = prune_seq_show, +}; + +static int prune_open(struct inode *inode, struct file *file) +{ + return seq_open(file, &prune_seq_ops); +} + +static const struct file_operations prune_fops = { + .owner = THIS_MODULE, + .open = prune_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, }; static unsigned int @@ -179,7 +403,7 @@ static int prune_table_prune_vector_init(struct prune *prune, { struct prune_table *table; - INIT_LIST_HEAD(&entry->prune_vector); + INIT_LIST_HEAD_RCU(&entry->prune_vector); list_for_each_entry(table, &prune->table_list, list) { struct prune_vector_item *vector_item; @@ -191,7 +415,7 @@ static int prune_table_prune_vector_init(struct prune *prune, } vector_item->pruned = true; vector_item->table = table; - list_add_tail(&vector_item->list, &entry->prune_vector); + list_add_tail_rcu(&vector_item->list, &entry->prune_vector); } return 0; } @@ -204,7 +428,8 @@ static void prune_table_prune_vector_fini(struct prune_table_entry *entry) struct prune_vector_item *vector_item; vector_item = list_entry(pos, typeof(*vector_item), list); - list_del(&vector_item->list); + list_del_rcu(&vector_item->list); + synchronize_rcu(); kfree(vector_item); } } @@ -578,7 +803,9 @@ prune_table_entry_create(struct prune *prune, struct prune_table *table, prune_table_entry_fini(entry); return ERR_PTR(err); } - list_add_tail(&entry->list, &table->entry_list); + + list_add_tail_rcu(&entry->list, &table->entry_list); + entry->item.table = table; return entry; @@ -586,7 +813,8 @@ prune_table_entry_create(struct prune *prune, struct prune_table *table, static void prune_table_entry_destroy(struct prune_table_entry *entry) { - list_del(&entry->list); + list_del_rcu(&entry->list); + synchronize_rcu(); prune_table_entry_fini(entry); } @@ -611,8 +839,8 @@ prune_intersec_entry_create(unsigned long *intersec_table_mask, bitmap_and(intersec_entry->ht_key, intersec_table_mask, item_key, mask_len); - INIT_LIST_HEAD(&intersec_entry->intersec_table_elem_list); - INIT_LIST_HEAD(&intersec_entry->neigh_table_elem_list); + INIT_LIST_HEAD_RCU(&intersec_entry->intersec_table_elem_list); + INIT_LIST_HEAD_RCU(&intersec_entry->neigh_table_elem_list); return intersec_entry; @@ -644,11 +872,11 @@ prune_intersec_item_create(struct prune_table_entry *entry, intersec_item->entry = entry; if (!neigh) - list_add_tail(&intersec_item->list, - &intersec_entry->intersec_table_elem_list); + list_add_tail_rcu(&intersec_item->list, + &intersec_entry->intersec_table_elem_list); else - list_add_tail(&intersec_item->list, - &intersec_entry->neigh_table_elem_list); + list_add_tail_rcu(&intersec_item->list, + &intersec_entry->neigh_table_elem_list); return intersec_item; } @@ -656,7 +884,8 @@ prune_intersec_item_create(struct prune_table_entry *entry, static void prune_intersec_item_destroy(struct prune_intersec_table_list_elem *intersec_item) { - list_del(&intersec_item->list); + list_del_rcu(&intersec_item->list); + synchronize_rcu(); kfree(intersec_item); } @@ -669,6 +898,7 @@ static int prune_intersec_item_add(struct prune_intersec_table *intersec_table, struct prune_intersec_table_entry *intersec_entry; struct rhashtable_params rht_params; unsigned long *ht_key; + unsigned long *mask; bool found = true; int err = 0; @@ -676,6 +906,7 @@ static int prune_intersec_item_add(struct prune_intersec_table *intersec_table, if (!ht_key) return -ENOMEM; + mask = intersec_table->mask; bitmap_and(ht_key, intersec_table->mask, entry->item.key, mask_len); rht_params = prune_intersec_table_entry_rht_params(intersec_table); @@ -686,7 +917,7 @@ static int prune_intersec_item_add(struct prune_intersec_table *intersec_table, if (!intersec_entry) { /* create new intersec entry since there ins't already one */ - intersec_entry = prune_intersec_entry_create(intersec_table->mask, + intersec_entry = prune_intersec_entry_create(mask, entry->item.key, intersec_table, mask_len); @@ -706,6 +937,8 @@ static int prune_intersec_item_add(struct prune_intersec_table *intersec_table, rht_params); if (err) goto err_rhashtable_insert; + list_add_tail_rcu(&intersec_entry->list, + &intersec_table->items_list); } return 0; @@ -772,6 +1005,8 @@ prune_intersec_item_del(struct prune_intersec_table *intersec_table, rhashtable_remove_fast(&intersec_table->entry_ht, &intersec_entry->ht_node, rht_params); + list_del_rcu(&intersec_entry->list); + synchronize_rcu(); prune_intersec_entry_destroy(intersec_entry); } kfree(ht_key); @@ -801,7 +1036,9 @@ prune_intersec_table_create(struct prune *prune, if (err) goto err_rhashtable_init; - list_add(&intersec_table->list, &table->intersec_table_list); + list_add_tail_rcu(&intersec_table->list, &table->intersec_table_list); + + INIT_LIST_HEAD_RCU(&intersec_table->items_list); return intersec_table; @@ -827,6 +1064,8 @@ static void prune_intersec_rht_free(void *ptr, void *arg) neigh_item = list_entry(pos, typeof(*neigh_item), list); prune_intersec_item_destroy(neigh_item); } + list_del_rcu(&rht_node->list); + synchronize_rcu(); kfree(rht_node->ht_key); kfree(rht_node); } @@ -837,7 +1076,8 @@ prune_intersec_table_destroy(struct prune_intersec_table *intersec_table) rhashtable_free_and_destroy(&intersec_table->entry_ht, prune_intersec_rht_free, NULL); - list_del(&intersec_table->list); + list_del_rcu(&intersec_table->list); + synchronize_rcu(); kfree(intersec_table); } @@ -916,6 +1156,7 @@ static int prune_intersec_table_add(struct prune *prune, true); if (err) goto err_prune_intersec_table_items_commit_new; + return 0; err_prune_intersec_table_items_commit_new: @@ -1090,7 +1331,7 @@ static int prune_table_item_vector_add(struct prune_table *table, } vector_item->pruned = true; vector_item->table = new_table; - list_add_tail(&vector_item->list, &entry->prune_vector); + list_add_tail_rcu(&vector_item->list, &entry->prune_vector); } return 0; } @@ -1173,8 +1414,8 @@ static struct prune_table *prune_table_init(struct prune *prune, bitmap_copy(table->mask, mask, prune->mask_len); table->priv = priv; table->prune = prune; - INIT_LIST_HEAD(&table->entry_list); - INIT_LIST_HEAD(&table->intersec_table_list); + INIT_LIST_HEAD_RCU(&table->entry_list); + INIT_LIST_HEAD_RCU(&table->intersec_table_list); return table; } @@ -1212,10 +1453,11 @@ struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops, prune->priv = priv; prune->mask_len = mask_len; - INIT_LIST_HEAD(&prune->table_list); + INIT_LIST_HEAD_RCU(&prune->table_list); prune->ops = ops; prune_intersec_tables_ht_params_init(prune, mask_len); + list_add_tail_rcu(&prune->list, &prune_object_list); return prune; } EXPORT_SYMBOL(prune_create); @@ -1228,6 +1470,8 @@ void prune_destroy(struct prune *prune) { WARN_ON(!list_empty(&prune->table_list)); + list_del_rcu(&prune->list); + synchronize_rcu(); kfree(prune); } EXPORT_SYMBOL(prune_destroy); @@ -1267,7 +1511,7 @@ struct prune_table *prune_table_create(struct prune *prune, unsigned long *mask, if (err) goto err_table_build; - list_add_tail(&table->list, &prune->table_list); + list_add_tail_rcu(&table->list, &prune->table_list); return table; @@ -1298,7 +1542,8 @@ int prune_table_destroy(struct prune_table *table) prune_item_prune_table_del(table->prune, table); - list_del(&table->list); + list_del_rcu(&table->list); + synchronize_rcu(); prune_table_fini(table); @@ -1440,6 +1685,42 @@ struct list_head *prune_item_prune_vector(struct prune_item *item) } EXPORT_SYMBOL(prune_item_prune_vector); +static struct dentry *prune_debugfs_create(void) +{ + dentry = debugfs_create_file("prune_debug", 0644, NULL, NULL, + &prune_fops); + if (!dentry) + pr_warn("Failed to create the debugfs prune file\n"); + + return dentry; +} + +static void prune_debugfs_destroy(struct dentry *dentry) +{ + debugfs_remove(dentry); +} + +int prune_init(void) +{ + INIT_LIST_HEAD_RCU(&prune_object_list); +#ifdef CONFIG_DEBUG_FS + dentry = prune_debugfs_create(); + if (!dentry) + return -EINVAL; + +#endif + return 0; +} +EXPORT_SYMBOL(prune_init); + +void prune_fini(void) +{ +#ifdef CONFIG_DEBUG_FS + prune_debugfs_destroy(dentry); +#endif +} +EXPORT_SYMBOL(prune_fini); + MODULE_LICENSE("Dual BSD/GPL"); MODULE_AUTHOR("Tal Bar "); MODULE_DESCRIPTION("Prune lookup table manager"); diff --git a/lib/test_prune.c b/lib/test_prune.c index 8bf43af..85d8c32 100644 --- a/lib/test_prune.c +++ b/lib/test_prune.c @@ -1199,11 +1199,13 @@ static int test_prune(void) static int __init test_prune_init(void) { - return test_prune(); + prune_init(); + return test_prune(); } static void __exit test_prune_exit(void) { + prune_fini(); } module_init(test_prune_init); From patchwork Sun Aug 12 15:57:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tal Bar X-Patchwork-Id: 10563751 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id CC143139A for ; Sun, 12 Aug 2018 20:38:19 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B7E0C28F8D for ; Sun, 12 Aug 2018 20:38:19 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id AAAAE28F94; Sun, 12 Aug 2018 20:38:19 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=2.0 tests=BAD_ENC_HEADER,BAYES_00, DKIM_SIGNED,MAILING_LIST_MULTI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from lists.ozlabs.org (lists.ozlabs.org [203.11.71.2]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 57FFC28F8D for ; Sun, 12 Aug 2018 20:38:17 +0000 (UTC) Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 41pW066yMYzF0Rr for ; Mon, 13 Aug 2018 06:38:14 +1000 (AEST) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="Ao/nqQOF"; dkim-atps=neutral X-Original-To: linux-mlxsw@lists.ozlabs.org Delivered-To: linux-mlxsw@lists.ozlabs.org Authentication-Results: lists.ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=mellanox.com (client-ip=40.107.5.59; helo=eur03-ve1-obe.outbound.protection.outlook.com; envelope-from=talb@mellanox.com; receiver=) Authentication-Results: lists.ozlabs.org; dmarc=pass (p=none dis=none) header.from=mellanox.com Authentication-Results: lists.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=Mellanox.com header.i=@Mellanox.com header.b="Ao/nqQOF"; dkim-atps=neutral Received: from EUR03-VE1-obe.outbound.protection.outlook.com (mail-eopbgr50059.outbound.protection.outlook.com [40.107.5.59]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 41pVzn35TBzF0Rr for ; Mon, 13 Aug 2018 06:37:56 +1000 (AEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Mellanox.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=0Ka7O5xQOKm+eLieFcr5yx93qJvbqJnzHFejozaO4BM=; b=Ao/nqQOF2y3LMjQQoZ0PqjFBHIYju+3bLF7cZqfnjutF2c1J7ioZH+pQcoKOgU5p07iaUDEE8ZImQ3NRMR5JVuwR3UKvY3AdA9yDNzcKzDjlapSfaR+4jwiCeSklDRAsM9YO9jlUi54iObW1yTtuvQFW9VCIbzaqCa5P8K6dP8s= Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=talb@mellanox.com; Received: from dev-r-vrt-156.mtr.labs.mlnx (37.142.13.130) by DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1038.19; Sun, 12 Aug 2018 15:57:44 +0000 From: Tal Bar To: idosch@mellanox.com, jiri@mellanox.com Subject: [net-next mlxsw v10 3/3] mlxsw: spectrum_acl: Add utilization of the prune library Date: Sun, 12 Aug 2018 18:57:21 +0300 Message-Id: <1534089441-20653-4-git-send-email-talb@mellanox.com> X-Mailer: git-send-email 2.8.0 In-Reply-To: <1534089441-20653-1-git-send-email-talb@mellanox.com> References: <1534089441-20653-1-git-send-email-talb@mellanox.com> MIME-Version: 1.0 X-Originating-IP: [37.142.13.130] X-ClientProxiedBy: AM4PR05CA0001.eurprd05.prod.outlook.com (2603:10a6:205::14) To DB6PR05MB3287.eurprd05.prod.outlook.com (2603:10a6:6:1b::29) X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: c31e1bfc-0f28-453a-48fa-08d6006c57f8 X-MS-Office365-Filtering-HT: Tenant X-Microsoft-Antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989117)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:DB6PR05MB3287; X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 3:p62oDnLqAdwh8IFj2w2Gxy1XtU7ilqW18mI64RklxC3FpVJhcd+r1JZOd3USwNXfBhn3isA02y6LNLSF6jZiEXJbzAT8krGseXoheU0J8rWWW/E7b+ZI7MyaO6H8LUCmjufMVGYV5/NDKeus0MHUHB4UqmuWCKOGCdEMHoRk/CJmySwHDQqUtP61MUvCI0DgHMnySZ+Bs7mJOy5zL2Zcd6l6YKWq016HBwufDR1O2lcKjYYvAdrhnS2Gpo5qK6Vl; 25:CzAyv4gU+CC72MSBJKWc/Od0OZuEQBtXfc1kuFcH+Z5yXGKVeWYkqP8K42EUYBPD8BlCFTl7JSEoPfB2HwLG0bM+L5XSMNSfDontu1xxKOFeYWqITdzQVO9H3i1gN6by2U/vEKXG762mrZr0z8PMN3RS/tWyca0S2H7h+/ImX1RKGoF5v9ztX0meGtkkBG4CLK78Au3dMbby0Vs6HAOeT2qaKI9rWpJuud++rHzX8fq1vhbRZ20GXJb0nEw+iz35t14AD71rQznSZKDlZJKe/Xi7d/cF8TsNsfND+F/sLMhxL57icWiPNlSbT2+PbO3yy+akb8v6m/sHz1liJLomGg==; 31:eVVvK0lbR8N5nmtqmrpuNM1JTlrulqGUdomNxDjQ2MOq3pxXfHqF1Iz2W767oSOjCSoKvsxEH7cMS351xjBCo6KH1nSaR+y+E5o4S8rixAP5kArH67qXEnWxtlqAODfC5Awhu0fmsqeMDOUzzOgtnKKmlMrlnJMvSLn7xQmmJf2LMg5kM60bdix9v424B+zactidgEMnRqoYlFPG/+8s4PuhJQuYwzhkWggrj8pVu0U= X-MS-TrafficTypeDiagnostic: DB6PR05MB3287: X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 20:R+P/trnGqEhDzdsot5AyHePIOdScngv5JR52dc20Pf22PERCgLBJNvfgXcVl+7jv/5b2tOdpDdZrj8ScbYeKOLbfds8W128CRPhLhNHhIDTnsbsXqYJB/nLBXMip8mcrJcxS/s7nYZuJOCMziYmaAu1v8rXxbos32vkeNU1e6tB0LOUsbQVIpllQuQWA5xR96Cg3mVQTtuRrYD/pfd1QRSqkVvEyDxbEY+NWrhpgNWRzEzKp7dXi3EguwMDY9kfdevHs7hlnWJapbEtOLvtRvbhleHv87wjg8YKm2WWt7JhLI69Ke7lC+kHmyTGxUtWsAPWfA9wOaAwRZoXtxhcgTp9R08BhRoGUneaoa2nkkUkTq1HoRB3L+N2LLoFiwd5nFsMGeP1gbecnwy06hoIzrUKlFwtIEi0xpN2QryVW8a7Lw9dnnydNBwZLTbaMVXo5P6l4ppnDKiZikeXusOhOquMC+dF9gU0sB18H9StPL66oI4vhgfnIXs84wiYcKW3g; 4:2D2JdW7ycKypBv16ey7ezfyG6ahVgOX46HGk9O/tOrDX8ZfqsV12nR+VH4oExDYt/Uu4zQP7Ej/mssqmrCQYVmSAEpVu5NBcLe2+MB4L9+e8McWFxb58efXXvaK1bEoDsde5tH7vDaLRGdlrHelfhMSyiLuWA0EGlPvNi18zfXQbKWE2E4mxmp4763PQkNY0Vd3ai7/t8bTLH3ksOWAjPEoq03HV6K14cEqN/QlPlQYg2zbj0nyIt6Qx2x40o0tZF9cYgjWnDIKKFTFu0pzrlA== X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-MS-Exchange-SenderADCheck: 1 X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(10201501046)(3231311)(944501410)(52105095)(93006095)(93001095)(6055026)(149027)(150027)(6041310)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123562045)(20161123564045)(20161123558120)(20161123560045)(6072148)(201708071742011)(7699016); SRVR:DB6PR05MB3287; BCL:0; PCL:0; RULEID:; SRVR:DB6PR05MB3287; X-Forefront-PRVS: 0762FFD075 X-Forefront-Antispam-Report: SFV:NSPM; SFS:(10009020)(396003)(346002)(376002)(136003)(366004)(39860400002)(199004)(189003)(6512007)(53946003)(6636002)(2616005)(50226002)(6506007)(386003)(81166006)(81156014)(53936002)(956004)(6116002)(68736007)(8676002)(86362001)(8936002)(6486002)(2906002)(3846002)(11346002)(14444005)(5660300001)(16526019)(52116002)(106356001)(50466002)(48376002)(47776003)(66066001)(25786009)(36756003)(316002)(16586007)(305945005)(4326008)(6666003)(26005)(7736002)(476003)(478600001)(105586002)(85306007)(446003)(107886003)(486006)(76176011)(51416003)(97736004); DIR:OUT; SFP:1101; SCL:1; SRVR:DB6PR05MB3287; H:dev-r-vrt-156.mtr.labs.mlnx; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; Received-SPF: None (protection.outlook.com: mellanox.com does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; DB6PR05MB3287; 23:sIStNIeyxVtNkUpYUi1cVsABUuq21ZmtMtOBRl+pV?= 39WrFQToPNZN01eb1Iivivhm4nKl0hv/N1Q0HExIef9GPBMULGLtJKJE5pa5qeTRKarD19B98O6WzcyED3DuzSIWF5m8lU3hpmPS2kTLBLnyPQPAdvNFoh0SQWqSHLXWDDm91dtWrybfp25Ufxa3Es5+UU+/uRXhU80J85SNsxMWKqhOvcpYxEt6XHKsg6Rv3Ibx0eZWPS7ZG4kpoeIdMSi2VOOQRLgTf/ViAiVg2h9pTRoteaOu1XC0jm2SFh48NzEILrzcnLrcBxtzqhWH8AnpoZj+TzejD2+fVvayUFkBHTackdGTXhkT8x9UlAw7KHbbu6duTUdgBh5j9L5jnN83lpsF4CgH2209W9tOFDiGolYZYI/S/O5wyyXznQZtqMWQtFP0tmWNkVm8g8j3Tf+/dFXijkqMs9KOKjF3de6pSt0IBC4FQuNp8ao7ZCWYOn9r/Ue7xBrWDnor+52IQB6uAsVAI93U/CIEzuu817C8OUtIRXyOxv4ZcFy14hSJLzYD6IhEfqxiH893RNYx8xNtsh6Ds1O/9ucFq75OzKoDqX1d9mcCObBrkfNFna/31AwRkZBbo1ik7R8meKUi0Vt/M1z4c7OZ+3kKnNAj9PvEbjBfCv+VdiWNrJhGHfpHEmkCW1hub3/gwhazh1CC4UY0D7pLhRrYqLXaRGq2iJlUPe9l9x6RBDRsDN5zVKi/Pl40trnM8wtKt1/kmYANl93LlFFndypxz0ozdPbhsua++Jj9y73+iydpTcsyUY+d3KXCZWikRN+O6XDm6hwQ/BmdcE/y+SaOc+NypdlXzDtWayU9sYzmrGLwnEnzaQDcgCEAJBvGWvtEc+VA8OosOPI9AxPMjWoyTZO96jKJ9s4jO+Y9gGMcRoJUJ09IgVbWJlWDgI7pYe7UUNigFGHx09+Z6/HEi7nkrK4xEhPuw5BUfgmgBbk5MnGIbn2CazKY9BxWNnipxvjWIATgJQL1TgXwJsaHeNJ0yTkbwRIgwq1oTh/ny+PM9WMSLr2wvX4kqlLoRFlvw27i80mE3qw+NX/bQi1loTDdwAQcTfVPabkgcoxi22Gd9qxrLtWHX3yTjVIFrQn2Bdqg8Lk6iEFiwSKv0pfAz3yDBWCTAiQygg2J/Y9DFytxsfmKiFRykymLHoQZBADHZGkth0iz9dhtXwR4vTa8wzX3q4GQiN0IJ1Hgw== X-Microsoft-Antispam-Message-Info: ScLBWJbWHtNDY4EMsXZk/KZxNQJYRim9a9BLBsdAfLfHtDJZLrPWT02manHiifkb6KG+sbaOhHDEXjQ3Rooi9V0qv1aR64Vw1AvWHwFqrS0S59sNV7pNqMkf1YEtUhVl77vWtFr5UR5c/MycCpbWUmLGGeUAXz57tx052sU7bka58auz2wL1aOF7bNKTO1X03ZGSTBWPP1gVLgksz4o1huev9Sv60kHRhfhmYW1fbFe+TYUQiZ10+dR2ayVszbklW70MtFFv4VDaVIm7DcBjwJVEJDzju9GXuUGBBYRW1fjfSx18gtejMBqj9WfHx4j7Liv8wpAw5kuI9ax37S028IFJ0Hodo9KCJzcap5BKoUg= X-Microsoft-Exchange-Diagnostics: 1; DB6PR05MB3287; 6:pGuyELImLhKjNm+4FUQPZAppDAwrFcvzdkqjHwzISgbDEzltOERCHqEaz1h2IgOO42jVf50P06BNcp+joL/N3dTrfMpvK8uhrzqxMZSYZCcrAeUN4Ci3XcssRIC5P7d+uW+Lx3BoAndxKANJ3IxDkvdcNvhBPRhmAs+HyQs3f/yse5rvWSrA7KGO9SSx9nKolTr7GyTLAM2OoEDe/yIIxgplIBo/JEbQcoMZCndM9P1mYtLIjlJBmw3hCMeeoORY60dtYd1AOieJPLj/80tKZBF0yHci4u/ajL63WTfZmpo2uAOMZnNlecPg+gui7joTjLCqL5C1s/XQ5qKorMJJFYzRNBAEza3BIRf6r7hRmrJ0dKCo81QnR9H0P4VQk382c7o1NRsF1RL/rnBAp2SWNoenJz6rh9F/LjQU7e66HOsGpuACCse9twPZfrhCspuzW68MN/3Bkf0B72aBns9Mew==; 5:AseC/F/bhUX42fytfIW4GblmoaAdBJYU3No9i+rqwtE25olPuEZoAPb5VoX2/i72qmjOuJeeoQ3mNk8gVOkerbn7l6pfH39kBuIQTOBQ+gms8zbPKoIri2Pi97iVh7V0fr1XdVMwy4IO0VnZ9CUvfuqa2sUDv5YgQEVhwcBGPnU=; 7:i+eE6Mij66WePjvPhB5QDS3THLrkV7TF3eP/nPR5XsH9gtdgg+xcZBotAqtVHtIIZ6ieZiKb5XA7dLF/jkF25F2GwDGMmzHdnHPm7tPurOQ41T5VzrJhnUsOSmXxiQKSku3V9rLVT8Xm87Wm4RCsh8eRO341I9Q2IlJbmOGoC7fV81r0YThWl0csEAHax07CxTUp96XjBXcYiZ1EO50EC4PwcTRiYR9JEpsQ1PVt2kpOJs0eRBTas/Ly2OZVCojn SpamDiagnosticOutput: 1:99 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: Mellanox.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Aug 2018 15:57:44.3125 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: c31e1bfc-0f28-453a-48fa-08d6006c57f8 X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: a652971c-7d2e-4d9b-a6a4-d149256f461b X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB6PR05MB3287 X-BeenThere: linux-mlxsw@lists.ozlabs.org X-Mailman-Version: 2.1.27 Precedence: list List-Id: mlxsw driver development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: linux-internal@mellanox.com Errors-To: linux-mlxsw-bounces+patchwork-linux-mlxsw=patchwork.kernel.org@lists.ozlabs.org X-Virus-Scanned: ClamAV using ClamSMTP A packet needs to be evaluated against a data base of rules. For A-TCAM the ASIC has to do up to 16 lookups, 1 per ERP. In order to reduce the number of lookups the driver utilize the prube library. In Spectrum-2 the every rule has a prune_vector and a ctcam_prune. The prune_vector instruct the ASIC which ERPs are not relevant for further lookups and the ctcam_prune instructs the ASIC to do lookup on the C-TCAM. The driver set the vector according to rule priority and the ctcam_prune of the matched rule. That increase the performance, since ASIC make only the needed lookups. There is a special case for 8 key blocks region type. The ASIC support prune vector of all 1's (prune) or all 0's (do lookup). In the driver we choose to set all 0's therefore the performance will be less then optimal but correct. Signed-off-by: Tal Bar --- drivers/net/ethernet/mellanox/mlxsw/Kconfig | 1 + drivers/net/ethernet/mellanox/mlxsw/reg.h | 16 ++- .../ethernet/mellanox/mlxsw/spectrum1_acl_tcam.c | 3 +- .../ethernet/mellanox/mlxsw/spectrum2_acl_tcam.c | 154 ++++++++++++++++++++- drivers/net/ethernet/mellanox/mlxsw/spectrum_acl.c | 8 ++ .../ethernet/mellanox/mlxsw/spectrum_acl_atcam.c | 138 ++++++++++++++++-- .../ethernet/mellanox/mlxsw/spectrum_acl_ctcam.c | 7 +- .../net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c | 61 +++++++- .../ethernet/mellanox/mlxsw/spectrum_acl_tcam.c | 9 +- .../ethernet/mellanox/mlxsw/spectrum_acl_tcam.h | 42 +++++- 10 files changed, 408 insertions(+), 31 deletions(-) diff --git a/drivers/net/ethernet/mellanox/mlxsw/Kconfig b/drivers/net/ethernet/mellanox/mlxsw/Kconfig index 8a291eb..7e6b518 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/Kconfig +++ b/drivers/net/ethernet/mellanox/mlxsw/Kconfig @@ -80,6 +80,7 @@ config MLXSW_SPECTRUM depends on IPV6_GRE || IPV6_GRE=n select GENERIC_ALLOCATOR select PARMAN + select PRUNE select MLXFW default m ---help--- diff --git a/drivers/net/ethernet/mellanox/mlxsw/reg.h b/drivers/net/ethernet/mellanox/mlxsw/reg.h index 6e8b619..4931cdf 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/reg.h +++ b/drivers/net/ethernet/mellanox/mlxsw/reg.h @@ -2760,13 +2760,24 @@ MLXSW_ITEM32(reg, ptce3, large_entry_key_id, 0x98, 0, 24); */ MLXSW_ITEM32(reg, ptce3, action_pointer, 0xA0, 0, 24); +static inline void +mlxsw_reg_ptce3_prune_vector_pack(char *payload, + unsigned long *prune_vector, + unsigned long size) +{ + unsigned long bit; + + for_each_set_bit(bit, prune_vector, size) + mlxsw_reg_ptce3_prune_vector_set(payload, bit, true); +} + static inline void mlxsw_reg_ptce3_pack(char *payload, bool valid, enum mlxsw_reg_ptce3_op op, u32 priority, const char *tcam_region_info, const char *key, u8 erp_id, - bool large_exists, u32 lkey_id, - u32 action_pointer) + bool prune_ctcam, bool large_exists, + u32 lkey_id, u32 action_pointer) { MLXSW_REG_ZERO(ptce3, payload); mlxsw_reg_ptce3_v_set(payload, valid); @@ -2775,6 +2786,7 @@ static inline void mlxsw_reg_ptce3_pack(char *payload, bool valid, mlxsw_reg_ptce3_tcam_region_info_memcpy_to(payload, tcam_region_info); mlxsw_reg_ptce3_flex2_key_blocks_memcpy_to(payload, key); mlxsw_reg_ptce3_erp_id_set(payload, erp_id); + mlxsw_reg_ptce3_prune_ctcam_set(payload, prune_ctcam); mlxsw_reg_ptce3_large_exists_set(payload, large_exists); mlxsw_reg_ptce3_large_entry_key_id_set(payload, lkey_id); mlxsw_reg_ptce3_action_pointer_set(payload, action_pointer); diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum1_acl_tcam.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum1_acl_tcam.c index 2a9eac9..e1ddaf4 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum1_acl_tcam.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum1_acl_tcam.c @@ -30,7 +30,8 @@ struct mlxsw_sp1_acl_tcam_entry { static int mlxsw_sp1_acl_ctcam_region_entry_insert(struct mlxsw_sp_acl_ctcam_region *cregion, struct mlxsw_sp_acl_ctcam_entry *centry, - const char *mask) + const char *key, const char *mask, + u32 priority) { return 0; } diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum2_acl_tcam.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum2_acl_tcam.c index 8ca77f3..835108a 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum2_acl_tcam.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum2_acl_tcam.c @@ -2,6 +2,7 @@ /* Copyright (c) 2018 Mellanox Technologies. All rights reserved */ #include +#include #include "spectrum.h" #include "spectrum_acl_tcam.h" @@ -27,14 +28,139 @@ struct mlxsw_sp2_acl_tcam_entry { struct mlxsw_afa_block *act_block; }; +struct mlxsw_afa_block * +mlxsw_sp2_acl_tcam_aentry_act_block(struct mlxsw_sp_acl_atcam_entry *aentry) +{ + struct mlxsw_sp2_acl_tcam_entry *entry; + + entry = container_of(aentry, struct mlxsw_sp2_acl_tcam_entry, aentry); + return entry->act_block; +} + +void +mlxsw_sp2_acl_tcam_prune_vector_bit_set(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry *aentry, + bool pruned) +{ + if (pruned) + __set_bit(mlxsw_sp_acl_erp_index(erp), aentry->prune_bitmap); + else + __clear_bit(mlxsw_sp_acl_erp_index(erp), aentry->prune_bitmap); +} + +static void +mlxsw_sp2_acl_tcam_prune_update(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry *aentry) +{ + struct mlxsw_sp_acl_atcam_region *aregion; + struct mlxsw_sp *mlxsw_sp; + u32 priority; + int err; + + aregion = mlxsw_sp_acl_erp_aregion(erp); + mlxsw_sp = aregion->region->mlxsw_sp; + priority = aentry->prune_item->priority; + + err = mlxsw_sp_acl_tcam_priority_get(mlxsw_sp, + aentry->prune_item->priority, + &priority, true); + if (err) { + WARN(err, "Failed to retrieve rule priority while updating rule with priority %u\n", + aentry->prune_item->priority); + return; + } + err = mlxsw_sp_acl_atcam_region_entry_update(mlxsw_sp, aregion, aentry, + priority); + if (err) { + WARN(err, "Failed to updating prune vector while update rule with priority %u\n", + aentry->prune_item->priority); + return; + } +} + +static void +mlxsw_sp2_acl_tcam_prune_ctcam_update(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry *aentry, + bool pruned) +{ + bool ctcam_pruned = aentry->num_ctcam_erps_scan > 0 ? true : false; + + pruned ? aentry->num_ctcam_erps_scan-- : aentry->num_ctcam_erps_scan++; + + if ((aentry->num_ctcam_erps_scan > 0 && !ctcam_pruned) || + (ctcam_pruned & !aentry->num_ctcam_erps_scan)) + mlxsw_sp2_acl_tcam_prune_update(erp, aentry); +} + +static void +mlxsw_sp2_acl_tcam_prune_vector_update(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry *aentry, + bool pruned) +{ + mlxsw_sp2_acl_tcam_prune_vector_bit_set(erp, aentry, pruned); + mlxsw_sp2_acl_tcam_prune_update(erp, aentry); +} + +static void +mlxsw_sp2_acl_tcam_prune_notification_handler(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry + *aentry, + bool pruned) +{ + enum mlxsw_sp_acl_atcam_region_type region_type; + bool ctcam_erp, ctcam_entry; + + region_type = mlxsw_sp_acl_erp_region_type(aentry->erp); + ctcam_entry = mlxsw_sp_acl_erp_is_ctcam_erp(aentry->erp); + ctcam_erp = mlxsw_sp_acl_erp_is_ctcam_erp(erp); + + /* Discard notification: + * For ctcam rule prune vector is irrelevant + * For 8KB region type we should always not prune + */ + if (!ctcam_entry && region_type != MLXSW_SP_ACL_ATCAM_REGION_TYPE_8KB) { + if (ctcam_erp) + mlxsw_sp2_acl_tcam_prune_ctcam_update(erp, aentry, + pruned); + else + mlxsw_sp2_acl_tcam_prune_vector_update(erp, aentry, + pruned); + } +} + +static void +mlxsw_sp2_acl_atcam_entry_prune_notify(struct list_head *prune_item_notify_list, + struct prune_table *table, bool pruned) +{ + struct mlxsw_sp_acl_atcam_entry *aentry; + struct mlxsw_sp_acl_erp *erp; + struct prune_item *item; + + list_for_each_entry(item, prune_item_notify_list, list) { + aentry = item->priv; + erp = prune_table_priv(table); + mlxsw_sp2_acl_tcam_prune_notification_handler(erp, aentry, + pruned); + } +} + +static const struct prune_ops mlxsw_sp2_acl_atcam_prune_ops = { + .prune_item_notify = mlxsw_sp2_acl_atcam_entry_prune_notify +}; + static int mlxsw_sp2_acl_ctcam_region_entry_insert(struct mlxsw_sp_acl_ctcam_region *cregion, struct mlxsw_sp_acl_ctcam_entry *centry, - const char *mask) + const char *key, + const char *mask, + u32 priority) { struct mlxsw_sp_acl_atcam_region *aregion; struct mlxsw_sp_acl_atcam_entry *aentry; + struct prune_item *prune_item; struct mlxsw_sp_acl_erp *erp; + bool non_def_prune_vector; + int err; aregion = mlxsw_sp_acl_tcam_cregion_aregion(cregion); aentry = mlxsw_sp_acl_tcam_centry_aentry(centry); @@ -44,7 +170,25 @@ mlxsw_sp2_acl_ctcam_region_entry_insert(struct mlxsw_sp_acl_ctcam_region *cregio return PTR_ERR(erp); aentry->erp = erp; + bitmap_from_arr32(aentry->key_bitmap, (void *) key, + MLXSW_SP_ACL_TCAM_MASK_LEN); + + prune_item = prune_item_create(aregion->region->prune, + mlxsw_sp_acl_erp_prune_table(erp), + priority, aentry->key_bitmap, aentry, + &non_def_prune_vector); + if (IS_ERR(prune_item)) { + err = PTR_ERR(prune_item); + goto err_prune_item_create; + } + aentry->prune_item = prune_item; + aentry->num_ctcam_erps_scan = 0; + return 0; + +err_prune_item_create: + mlxsw_sp_acl_erp_put(aregion, erp); + return err; } static void @@ -53,10 +197,15 @@ mlxsw_sp2_acl_ctcam_region_entry_remove(struct mlxsw_sp_acl_ctcam_region *cregio { struct mlxsw_sp_acl_atcam_region *aregion; struct mlxsw_sp_acl_atcam_entry *aentry; + int err; aregion = mlxsw_sp_acl_tcam_cregion_aregion(cregion); aentry = mlxsw_sp_acl_tcam_centry_aentry(centry); + err = prune_item_destroy(aentry->prune_item); + WARN(err, "Failed to destroy prune item while removing rule with priority %u\n", + aentry->prune_item->priority); + mlxsw_sp_acl_erp_put(aregion, aentry->erp); } @@ -148,7 +297,8 @@ mlxsw_sp2_acl_tcam_region_init(struct mlxsw_sp *mlxsw_sp, void *region_priv, return mlxsw_sp_acl_atcam_region_init(mlxsw_sp, &tcam->atcam, ®ion->aregion, _region, - &mlxsw_sp2_acl_ctcam_region_ops); + &mlxsw_sp2_acl_ctcam_region_ops, + &mlxsw_sp2_acl_atcam_prune_ops); } static void diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl.c index 2658a51..ed8270d 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl.c @@ -8,6 +8,7 @@ #include #include #include +#include #include #include @@ -847,6 +848,10 @@ int mlxsw_sp_acl_init(struct mlxsw_sp *mlxsw_sp) if (err) goto err_acl_ops_init; + err = prune_init(); + if (err) + goto err_prune_init; + /* Create the delayed work for the rule activity_update */ INIT_DELAYED_WORK(&acl->rule_activity_update.dw, mlxsw_sp_acl_rul_activity_update_work); @@ -854,6 +859,8 @@ int mlxsw_sp_acl_init(struct mlxsw_sp *mlxsw_sp) mlxsw_core_schedule_dw(&acl->rule_activity_update.dw, 0); return 0; +err_prune_init: + mlxsw_sp_acl_tcam_fini(mlxsw_sp, &acl->tcam); err_acl_ops_init: mlxsw_sp_fid_put(fid); err_fid_get: @@ -870,6 +877,7 @@ void mlxsw_sp_acl_fini(struct mlxsw_sp *mlxsw_sp) struct mlxsw_sp_acl *acl = mlxsw_sp->acl; cancel_delayed_work_sync(&mlxsw_sp->acl->rule_activity_update.dw); + prune_fini(); mlxsw_sp_acl_tcam_fini(mlxsw_sp, &acl->tcam); WARN_ON(!list_empty(&acl->rules)); mlxsw_sp_fid_put(acl->dummy_fid); diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_atcam.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_atcam.c index 2dda028..97dedbf 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_atcam.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_atcam.c @@ -7,6 +7,7 @@ #include #include #include +#include #include "reg.h" #include "core.h" @@ -317,7 +318,9 @@ mlxsw_sp_acl_atcam_region_init(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam *atcam, struct mlxsw_sp_acl_atcam_region *aregion, struct mlxsw_sp_acl_tcam_region *region, - const struct mlxsw_sp_acl_ctcam_region_ops *ops) + const struct mlxsw_sp_acl_ctcam_region_ops *ops, + const struct prune_ops + *mlxsw_acl_atcam_prune_ops) { int err; @@ -339,9 +342,17 @@ mlxsw_sp_acl_atcam_region_init(struct mlxsw_sp *mlxsw_sp, region, ops); if (err) goto err_ctcam_region_init; + region->prune = prune_create(MLXSW_SP_ACL_TCAM_MASK_LEN, + mlxsw_acl_atcam_prune_ops, region); + if (IS_ERR(region->prune)) { + err = PTR_ERR(region->prune); + goto err_prune_create; + } return 0; +err_prune_create: + mlxsw_sp_acl_ctcam_region_fini(&aregion->cregion); err_ctcam_region_init: mlxsw_sp_acl_erp_region_fini(aregion); err_erp_region_init: @@ -353,6 +364,7 @@ mlxsw_sp_acl_atcam_region_init(struct mlxsw_sp *mlxsw_sp, void mlxsw_sp_acl_atcam_region_fini(struct mlxsw_sp_acl_atcam_region *aregion) { + prune_destroy(aregion->region->prune); mlxsw_sp_acl_ctcam_region_fini(&aregion->cregion); mlxsw_sp_acl_erp_region_fini(aregion); aregion->ops->fini(aregion); @@ -376,19 +388,16 @@ static int mlxsw_sp_acl_atcam_region_entry_insert(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam_region *aregion, struct mlxsw_sp_acl_atcam_entry *aentry, - struct mlxsw_sp_acl_rule_info *rulei) + struct mlxsw_sp_acl_rule_info *rulei, + u32 priority) { struct mlxsw_sp_acl_tcam_region *region = aregion->region; u8 erp_id = mlxsw_sp_acl_erp_id(aentry->erp); struct mlxsw_sp_acl_atcam_lkey_id *lkey_id; char ptce3_pl[MLXSW_REG_PTCE3_LEN]; - u32 kvdl_index, priority; + u32 kvdl_index; int err; - err = mlxsw_sp_acl_tcam_priority_get(mlxsw_sp, rulei, &priority, true); - if (err) - return err; - lkey_id = aregion->ops->lkey_id_get(aregion, rulei, erp_id); if (IS_ERR(lkey_id)) return PTR_ERR(lkey_id); @@ -398,8 +407,11 @@ mlxsw_sp_acl_atcam_region_entry_insert(struct mlxsw_sp *mlxsw_sp, mlxsw_reg_ptce3_pack(ptce3_pl, true, MLXSW_REG_PTCE3_OP_WRITE_WRITE, priority, region->tcam_region_info, aentry->ht_key.enc_key, erp_id, + !(aentry->num_ctcam_erps_scan > 0), refcount_read(&lkey_id->refcnt) != 1, lkey_id->id, kvdl_index); + mlxsw_reg_ptce3_prune_vector_pack(ptce3_pl, aentry->prune_bitmap, + MLXSW_SP_ACL_ERP_MAX_PER_REGION); err = mlxsw_reg_write(mlxsw_sp->core, MLXSW_REG(ptce3), ptce3_pl); if (err) goto err_ptce3_write; @@ -411,6 +423,35 @@ mlxsw_sp_acl_atcam_region_entry_insert(struct mlxsw_sp *mlxsw_sp, return err; } +int +mlxsw_sp_acl_atcam_region_entry_update(struct mlxsw_sp *mlxsw_sp, + struct mlxsw_sp_acl_atcam_region *aregion, + struct mlxsw_sp_acl_atcam_entry *aentry, + u32 priority) +{ + struct mlxsw_sp_acl_tcam_region *region = aregion->region; + struct mlxsw_sp_acl_atcam_lkey_id *lkey_id; + char ptce3_pl[MLXSW_REG_PTCE3_LEN]; + struct mlxsw_afa_block *act_block; + u32 kvdl_index; + u8 erp_id; + + erp_id = mlxsw_sp_acl_erp_id(aentry->erp); + lkey_id = aentry->lkey_id; + act_block = mlxsw_sp2_acl_tcam_aentry_act_block(aentry); + kvdl_index = mlxsw_afa_block_first_kvdl_index(act_block); + + mlxsw_reg_ptce3_pack(ptce3_pl, true, MLXSW_REG_PTCE3_OP_WRITE_UPDATE, + priority, region->tcam_region_info, + aentry->ht_key.enc_key, erp_id, + !(aentry->num_ctcam_erps_scan > 0), + refcount_read(&lkey_id->refcnt) != 1, lkey_id->id, + kvdl_index); + mlxsw_reg_ptce3_prune_vector_pack(ptce3_pl, aentry->prune_bitmap, + MLXSW_SP_ACL_ERP_MAX_PER_REGION); + return mlxsw_reg_write(mlxsw_sp->core, MLXSW_REG(ptce3), ptce3_pl); +} + static void mlxsw_sp_acl_atcam_region_entry_remove(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam_region *aregion, @@ -423,12 +464,56 @@ mlxsw_sp_acl_atcam_region_entry_remove(struct mlxsw_sp *mlxsw_sp, mlxsw_reg_ptce3_pack(ptce3_pl, false, MLXSW_REG_PTCE3_OP_WRITE_WRITE, 0, region->tcam_region_info, aentry->ht_key.enc_key, - erp_id, refcount_read(&lkey_id->refcnt) != 1, + erp_id, !(aentry->num_ctcam_erps_scan > 0), + refcount_read(&lkey_id->refcnt) != 1, lkey_id->id, 0); mlxsw_reg_write(mlxsw_sp->core, MLXSW_REG(ptce3), ptce3_pl); aregion->ops->lkey_id_put(aregion, lkey_id); } +void mlxsw_sp_acl_atcam_prune_vector_to_bitmap(bool non_def_prune_vector, + struct mlxsw_sp_acl_atcam_entry + *aentry) +{ + enum mlxsw_sp_acl_atcam_region_type region_type; + struct prune_vector_item *vector_item; + struct list_head *prune_vector_list; + struct mlxsw_sp_acl_erp *erp; + struct prune_table *table; + + region_type = mlxsw_sp_acl_erp_region_type(aentry->erp); + if (region_type == MLXSW_SP_ACL_ATCAM_REGION_TYPE_8KB) { + /* Note: For SP-2 a region with 8 key blocks must be set to + * either to all 1's or all 0's. + * The driver set it to all 0's so this rule doesn't prune + * any other rules. + */ + bitmap_zero(aentry->prune_bitmap, + MLXSW_SP_ACL_ERP_MAX_PER_REGION); + return; + } + bitmap_fill(aentry->prune_bitmap, MLXSW_SP_ACL_ERP_MAX_PER_REGION); + + if (!non_def_prune_vector) /* prune all erps */ + return; + + /* set the relevant erps for further lookups */ + prune_vector_list = prune_item_prune_vector(aentry->prune_item); + list_for_each_entry(vector_item, prune_vector_list, list) { + if (!vector_item->pruned) { + table = vector_item->table; + erp = prune_table_priv(table); + if (mlxsw_sp_acl_erp_is_ctcam_erp(erp)) { + /* look-up towards the CTCAM */ + aentry->num_ctcam_erps_scan++; + continue; + } + mlxsw_sp2_acl_tcam_prune_vector_bit_set(erp, aentry, + false); + } + } +} + static int __mlxsw_sp_acl_atcam_entry_add(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam_region *aregion, @@ -436,21 +521,32 @@ __mlxsw_sp_acl_atcam_entry_add(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_rule_info *rulei) { struct mlxsw_sp_acl_tcam_region *region = aregion->region; - char mask[MLXSW_REG_PTCEX_FLEX_KEY_BLOCKS_LEN] = { 0 }; struct mlxsw_afk *afk = mlxsw_sp_acl_afk(mlxsw_sp->acl); + char mask[MLXSW_REG_PTCEX_FLEX_KEY_BLOCKS_LEN] = { 0 }; + struct prune_item *prune_item; struct mlxsw_sp_acl_erp *erp; unsigned int blocks_count; + bool non_def_prune_vector; + u32 priority; int err; blocks_count = mlxsw_afk_key_info_blocks_count_get(region->key_info); mlxsw_afk_encode(afk, region->key_info, &rulei->values, aentry->ht_key.enc_key, mask, 0, blocks_count - 1); + err = mlxsw_sp_acl_tcam_priority_get(mlxsw_sp, rulei->priority, + &priority, true); + if (err) + return err; + erp = mlxsw_sp_acl_erp_get(aregion, mask, false); if (IS_ERR(erp)) return PTR_ERR(erp); + aentry->erp = erp; aentry->ht_key.erp_id = mlxsw_sp_acl_erp_id(erp); + bitmap_from_arr32(aentry->key_bitmap, (void *) aentry->ht_key.enc_key, + MLXSW_SP_ACL_TCAM_MASK_LEN); /* We can't insert identical rules into the A-TCAM, so fail and * let the rule spill into C-TCAM @@ -461,14 +557,30 @@ __mlxsw_sp_acl_atcam_entry_add(struct mlxsw_sp *mlxsw_sp, if (err) goto err_rhashtable_insert; + prune_item = prune_item_create(aregion->region->prune, + mlxsw_sp_acl_erp_prune_table(erp), + rulei->priority, aentry->key_bitmap, + aentry, &non_def_prune_vector); + if (IS_ERR(prune_item)) { + err = PTR_ERR(prune_item); + goto err_prune_item_create; + } + aentry->prune_item = prune_item; + aentry->num_ctcam_erps_scan = 0; + + mlxsw_sp_acl_atcam_prune_vector_to_bitmap(non_def_prune_vector, + aentry); err = mlxsw_sp_acl_atcam_region_entry_insert(mlxsw_sp, aregion, aentry, - rulei); + rulei, priority); if (err) goto err_rule_insert; return 0; err_rule_insert: + if (!prune_item_destroy(aentry->prune_item)) + WARN(1, "Failed to destroy prune item\n"); +err_prune_item_create: rhashtable_remove_fast(&aregion->entries_ht, &aentry->ht_node, mlxsw_sp_acl_atcam_entries_ht_params); err_rhashtable_insert: @@ -481,7 +593,13 @@ __mlxsw_sp_acl_atcam_entry_del(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam_region *aregion, struct mlxsw_sp_acl_atcam_entry *aentry) { + int err; + mlxsw_sp_acl_atcam_region_entry_remove(mlxsw_sp, aregion, aentry); + err = prune_item_destroy(aentry->prune_item); + WARN(err, "Failed to destroy prune item while removing rule with priority %u\n", + aentry->prune_item->priority); + rhashtable_remove_fast(&aregion->entries_ht, &aentry->ht_node, mlxsw_sp_acl_atcam_entries_ht_params); mlxsw_sp_acl_erp_put(aregion, aentry->erp); diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_ctcam.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_ctcam.c index e3c6fe8..79c7a7f 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_ctcam.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_ctcam.c @@ -53,8 +53,8 @@ mlxsw_sp_acl_ctcam_region_entry_insert(struct mlxsw_sp *mlxsw_sp, char *key; int err; - err = mlxsw_sp_acl_tcam_priority_get(mlxsw_sp, rulei, &priority, - fillup_priority); + err = mlxsw_sp_acl_tcam_priority_get(mlxsw_sp, rulei->priority, + &priority, fillup_priority); if (err) return err; @@ -67,7 +67,8 @@ mlxsw_sp_acl_ctcam_region_entry_insert(struct mlxsw_sp *mlxsw_sp, mlxsw_afk_encode(afk, region->key_info, &rulei->values, key, mask, 0, blocks_count - 1); - err = cregion->ops->entry_insert(cregion, centry, mask); + err = cregion->ops->entry_insert(cregion, centry, key, mask, + rulei->priority); if (err) return err; diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c index 0a4fd3c..762af2d11 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_erp.c @@ -10,6 +10,7 @@ #include #include #include +#include #include "core.h" #include "reg.h" @@ -18,7 +19,6 @@ /* gen_pool_alloc() returns 0 when allocation fails, so use an offset */ #define MLXSW_SP_ACL_ERP_GENALLOC_OFFSET 0x100 -#define MLXSW_SP_ACL_ERP_MAX_PER_REGION 16 struct mlxsw_sp_acl_erp_core { unsigned int erpt_entries_size[MLXSW_SP_ACL_ATCAM_REGION_TYPE_MAX + 1]; @@ -35,12 +35,13 @@ struct mlxsw_sp_acl_erp_key { struct mlxsw_sp_acl_erp { struct mlxsw_sp_acl_erp_key key; u8 id; - u8 index; + u8 index; /* used for erp index in prune vector */ refcount_t refcnt; DECLARE_BITMAP(mask_bitmap, MLXSW_SP_ACL_TCAM_MASK_LEN); struct list_head list; struct rhash_head ht_node; struct mlxsw_sp_acl_erp_table *erp_table; + struct prune_table *prune_table; }; struct mlxsw_sp_acl_erp_master_mask { @@ -129,6 +130,28 @@ u8 mlxsw_sp_acl_erp_id(const struct mlxsw_sp_acl_erp *erp) return erp->id; } +u8 mlxsw_sp_acl_erp_index(const struct mlxsw_sp_acl_erp *erp) +{ + return erp->index; +} +struct prune_table * +mlxsw_sp_acl_erp_prune_table(const struct mlxsw_sp_acl_erp *erp) +{ + return erp->prune_table; +} + +enum mlxsw_sp_acl_atcam_region_type +mlxsw_sp_acl_erp_region_type(const struct mlxsw_sp_acl_erp *erp) +{ + return erp->erp_table->aregion->type; +} + +struct mlxsw_sp_acl_atcam_region * +mlxsw_sp_acl_erp_aregion(const struct mlxsw_sp_acl_erp *erp) +{ + return erp->erp_table->aregion; +} + static unsigned int mlxsw_sp_acl_erp_table_entry_size(const struct mlxsw_sp_acl_erp_table *erp_table) { @@ -245,6 +268,7 @@ mlxsw_sp_acl_erp_generic_create(struct mlxsw_sp_acl_erp_table *erp_table, struct mlxsw_sp_acl_erp_key *key) { struct mlxsw_sp_acl_erp *erp; + struct prune *prune; int err; erp = kzalloc(sizeof(*erp), GFP_KERNEL); @@ -272,8 +296,19 @@ mlxsw_sp_acl_erp_generic_create(struct mlxsw_sp_acl_erp_table *erp_table, if (err) goto err_rhashtable_insert; + prune = erp_table->aregion->region->prune; + erp->prune_table = prune_table_create(prune, erp->mask_bitmap, + MLXSW_SP_ACL_TCAM_MASK_LEN, + erp); + if (IS_ERR(erp->prune_table)) { + err = PTR_ERR(erp->prune_table); + goto err_prune_table_create; + } return erp; +err_prune_table_create: + rhashtable_remove_fast(&erp_table->erp_ht, &erp->ht_node, + mlxsw_sp_acl_erp_ht_params); err_rhashtable_insert: mlxsw_sp_acl_erp_master_mask_clear(erp_table, erp); err_master_mask_set: @@ -288,8 +323,12 @@ mlxsw_sp_acl_erp_generic_create(struct mlxsw_sp_acl_erp_table *erp_table, static void mlxsw_sp_acl_erp_generic_destroy(struct mlxsw_sp_acl_erp *erp) { + int err; struct mlxsw_sp_acl_erp_table *erp_table = erp->erp_table; + err = prune_table_destroy(erp->prune_table); + WARN(err, "Failed to destroy prune table\n"); + rhashtable_remove_fast(&erp_table->erp_ht, &erp->ht_node, mlxsw_sp_acl_erp_ht_params); mlxsw_sp_acl_erp_master_mask_clear(erp_table, erp); @@ -688,6 +727,7 @@ __mlxsw_sp_acl_erp_ctcam_mask_create(struct mlxsw_sp_acl_erp_table *erp_table, struct mlxsw_sp_acl_erp_key *key) { struct mlxsw_sp_acl_erp *erp; + struct prune *prune; int err; erp = kzalloc(sizeof(*erp), GFP_KERNEL); @@ -710,6 +750,15 @@ __mlxsw_sp_acl_erp_ctcam_mask_create(struct mlxsw_sp_acl_erp_table *erp_table, if (err) goto err_rhashtable_insert; + prune = erp_table->aregion->region->prune; + erp->prune_table = prune_table_create(prune, erp->mask_bitmap, + MLXSW_SP_ACL_TCAM_MASK_LEN, + erp); + if (IS_ERR(erp->prune_table)) { + err = PTR_ERR(erp->prune_table); + goto err_prune_table_create; + } + err = mlxsw_sp_acl_erp_region_ctcam_enable(erp_table); if (err) goto err_erp_region_ctcam_enable; @@ -720,6 +769,9 @@ __mlxsw_sp_acl_erp_ctcam_mask_create(struct mlxsw_sp_acl_erp_table *erp_table, return erp; err_erp_region_ctcam_enable: + if (prune_table_destroy(erp->prune_table)) + WARN(1, "Failed to destroy prune table err %d\n", err); +err_prune_table_create: rhashtable_remove_fast(&erp_table->erp_ht, &erp->ht_node, mlxsw_sp_acl_erp_ht_params); err_rhashtable_insert: @@ -765,8 +817,12 @@ static void mlxsw_sp_acl_erp_ctcam_mask_destroy(struct mlxsw_sp_acl_erp *erp) { struct mlxsw_sp_acl_erp_table *erp_table = erp->erp_table; + int err; mlxsw_sp_acl_erp_region_ctcam_disable(erp_table); + err = prune_table_destroy(erp->prune_table); + WARN(err, "Failed to destroy prune table\n"); + rhashtable_remove_fast(&erp_table->erp_ht, &erp->ht_node, mlxsw_sp_acl_erp_ht_params); mlxsw_sp_acl_erp_master_mask_clear(erp_table, erp); @@ -862,7 +918,6 @@ mlxsw_sp_acl_erp_second_mask_create(struct mlxsw_sp_acl_erp_table *erp_table, err = PTR_ERR(erp); goto err_erp_create; } - err = mlxsw_sp_acl_erp_index_get(erp_table, &erp->index); if (err) goto err_erp_index_get; diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.c b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.c index e171513..2b392e9 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.c +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.c @@ -8,6 +8,7 @@ #include #include #include +#include #include "reg.h" #include "core.h" @@ -82,8 +83,8 @@ void mlxsw_sp_acl_tcam_fini(struct mlxsw_sp *mlxsw_sp, } int mlxsw_sp_acl_tcam_priority_get(struct mlxsw_sp *mlxsw_sp, - struct mlxsw_sp_acl_rule_info *rulei, - u32 *priority, bool fillup_priority) + u32 rule_priority, u32 *priority, + bool fillup_priority) { u64 max_priority; @@ -96,11 +97,11 @@ int mlxsw_sp_acl_tcam_priority_get(struct mlxsw_sp *mlxsw_sp, return -EIO; max_priority = MLXSW_CORE_RES_GET(mlxsw_sp->core, KVD_SIZE); - if (rulei->priority > max_priority) + if (rule_priority > max_priority) return -EINVAL; /* Unlike in TC, in HW, higher number means higher priority. */ - *priority = max_priority - rulei->priority; + *priority = max_priority - rule_priority; return 0; } diff --git a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.h b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.h index 219a4e2..3b67782 100644 --- a/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.h +++ b/drivers/net/ethernet/mellanox/mlxsw/spectrum_acl_tcam.h @@ -6,6 +6,7 @@ #include #include +#include #include "reg.h" #include "spectrum.h" @@ -27,9 +28,8 @@ int mlxsw_sp_acl_tcam_init(struct mlxsw_sp *mlxsw_sp, void mlxsw_sp_acl_tcam_fini(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_tcam *tcam); int mlxsw_sp_acl_tcam_priority_get(struct mlxsw_sp *mlxsw_sp, - struct mlxsw_sp_acl_rule_info *rulei, - u32 *priority, bool fillup_priority); - + u32 rule_priority, u32 *priority, + bool fillup_priority); struct mlxsw_sp_acl_profile_ops { size_t ruleset_priv_size; int (*ruleset_add)(struct mlxsw_sp *mlxsw_sp, @@ -58,6 +58,7 @@ mlxsw_sp_acl_tcam_profile_ops(struct mlxsw_sp *mlxsw_sp, #define MLXSW_SP_ACL_TCAM_REGION_BASE_COUNT 16 #define MLXSW_SP_ACL_TCAM_REGION_RESIZE_STEP 16 +#define MLXSW_SP_ACL_ERP_MAX_PER_REGION 16 #define MLXSW_SP_ACL_TCAM_CATCHALL_PRIO (~0U) @@ -75,6 +76,7 @@ struct mlxsw_sp_acl_tcam_region { char tcam_region_info[MLXSW_REG_PXXX_TCAM_REGION_INFO_LEN]; struct mlxsw_afk_key_info *key_info; struct mlxsw_sp *mlxsw_sp; + struct prune *prune; unsigned long priv[0]; /* priv has to be always the last item */ }; @@ -96,7 +98,9 @@ struct mlxsw_sp_acl_ctcam_entry { struct mlxsw_sp_acl_ctcam_region_ops { int (*entry_insert)(struct mlxsw_sp_acl_ctcam_region *cregion, struct mlxsw_sp_acl_ctcam_entry *centry, - const char *mask); + const char *key, + const char *mask, + u32 priority); void (*entry_remove)(struct mlxsw_sp_acl_ctcam_region *cregion, struct mlxsw_sp_acl_ctcam_entry *centry); }; @@ -168,6 +172,11 @@ struct mlxsw_sp_acl_atcam_entry { struct mlxsw_sp_acl_ctcam_entry centry; struct mlxsw_sp_acl_atcam_lkey_id *lkey_id; struct mlxsw_sp_acl_erp *erp; + struct prune_item *prune_item; + DECLARE_BITMAP(key_bitmap, MLXSW_SP_ACL_TCAM_MASK_LEN); + DECLARE_BITMAP(prune_bitmap, MLXSW_SP_ACL_ERP_MAX_PER_REGION); + /* Counts the number of ctcam erps that the rule should scan */ + unsigned int num_ctcam_erps_scan; }; static inline struct mlxsw_sp_acl_atcam_region * @@ -189,7 +198,9 @@ mlxsw_sp_acl_atcam_region_init(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam *atcam, struct mlxsw_sp_acl_atcam_region *aregion, struct mlxsw_sp_acl_tcam_region *region, - const struct mlxsw_sp_acl_ctcam_region_ops *ops); + const struct mlxsw_sp_acl_ctcam_region_ops *ops, + const struct prune_ops + *mlxsw_acl_atcam_prune_ops); void mlxsw_sp_acl_atcam_region_fini(struct mlxsw_sp_acl_atcam_region *aregion); void mlxsw_sp_acl_atcam_chunk_init(struct mlxsw_sp_acl_atcam_region *aregion, struct mlxsw_sp_acl_atcam_chunk *achunk, @@ -208,11 +219,22 @@ int mlxsw_sp_acl_atcam_init(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam *atcam); void mlxsw_sp_acl_atcam_fini(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam *atcam); - +int +mlxsw_sp_acl_atcam_region_entry_update(struct mlxsw_sp *mlxsw_sp, + struct mlxsw_sp_acl_atcam_region *aregion, + struct mlxsw_sp_acl_atcam_entry *aentry, + u32 priority); struct mlxsw_sp_acl_erp; bool mlxsw_sp_acl_erp_is_ctcam_erp(const struct mlxsw_sp_acl_erp *erp); u8 mlxsw_sp_acl_erp_id(const struct mlxsw_sp_acl_erp *erp); +u8 mlxsw_sp_acl_erp_index(const struct mlxsw_sp_acl_erp *erp); +struct prune_table * +mlxsw_sp_acl_erp_prune_table(const struct mlxsw_sp_acl_erp *erp); +enum mlxsw_sp_acl_atcam_region_type +mlxsw_sp_acl_erp_region_type(const struct mlxsw_sp_acl_erp *erp); +struct mlxsw_sp_acl_atcam_region * +mlxsw_sp_acl_erp_aregion(const struct mlxsw_sp_acl_erp *erp); struct mlxsw_sp_acl_erp * mlxsw_sp_acl_erp_get(struct mlxsw_sp_acl_atcam_region *aregion, const char *mask, bool ctcam); @@ -225,4 +247,12 @@ int mlxsw_sp_acl_erps_init(struct mlxsw_sp *mlxsw_sp, void mlxsw_sp_acl_erps_fini(struct mlxsw_sp *mlxsw_sp, struct mlxsw_sp_acl_atcam *atcam); +struct mlxsw_afa_block; + +struct mlxsw_afa_block * +mlxsw_sp2_acl_tcam_aentry_act_block(struct mlxsw_sp_acl_atcam_entry *aentry); +void +mlxsw_sp2_acl_tcam_prune_vector_bit_set(struct mlxsw_sp_acl_erp *erp, + struct mlxsw_sp_acl_atcam_entry *aentry, + bool pruned); #endif