From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <shreyansh.jain@nxp.com>
Received: from NAM02-CY1-obe.outbound.protection.outlook.com
(mail-cys01nam02on0041.outbound.protection.outlook.com [104.47.37.41])
by dpdk.org (Postfix) with ESMTP id A98DE90F8
for <dev@dpdk.org>; Wed, 23 Aug 2017 16:02:48 +0200 (CEST)
Received: from CY1PR03CA0035.namprd03.prod.outlook.com (10.174.128.45) by
CY1PR03MB2267.namprd03.prod.outlook.com (10.166.207.19) with Microsoft SMTP
Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id
15.1.1362.18; Wed, 23 Aug 2017 14:02:47 +0000
Received: from BN1AFFO11FD035.protection.gbl (2a01:111:f400:7c10::129) by
CY1PR03CA0035.outlook.office365.com (2603:10b6:600::45) with Microsoft SMTP
Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id
15.1.1362.18 via Frontend Transport; Wed, 23 Aug 2017 14:02:47 +0000
Authentication-Results: spf=fail (sender IP is 192.88.168.50)
smtp.mailfrom=nxp.com; nxp.com; dkim=none (message not signed)
header.d=none;nxp.com; dmarc=fail action=none header.from=nxp.com;
Received-SPF: Fail (protection.outlook.com: domain of nxp.com does not
designate 192.88.168.50 as permitted sender) receiver=protection.outlook.com;
client-ip=192.88.168.50; helo=tx30smr01.am.freescale.net;
Received: from tx30smr01.am.freescale.net (192.88.168.50) by
BN1AFFO11FD035.mail.protection.outlook.com (10.58.52.159) with Microsoft SMTP
Server (version=TLS1_0, cipher=TLS_RSA_WITH_AES_256_CBC_SHA) id 15.1.1341.15
via Frontend Transport; Wed, 23 Aug 2017 14:02:46 +0000
Received: from Tophie.ap.freescale.net ([10.232.14.39])
by tx30smr01.am.freescale.net (8.14.3/8.14.0) with ESMTP id v7NE2Q2t004389;
Wed, 23 Aug 2017 07:02:44 -0700
From: Shreyansh Jain <shreyansh.jain@nxp.com>
To: <dev@dpdk.org>
CC: <ferruh.yigit@intel.com>, <hemant.agrawal@nxp.com>
Date: Wed, 23 Aug 2017 19:41:42 +0530
Message-ID: <20170823141213.25476-10-shreyansh.jain@nxp.com>
X-Mailer: git-send-email 2.9.3
In-Reply-To: <20170823141213.25476-1-shreyansh.jain@nxp.com>
References: <1499179471-19145-1-git-send-email-shreyansh.jain@nxp.com>
<20170823141213.25476-1-shreyansh.jain@nxp.com>
X-EOPAttributedMessage: 0
X-Matching-Connectors: 131479705672367290;
(91ab9b29-cfa4-454e-5278-08d120cd25b8); ()
X-Forefront-Antispam-Report: CIP:192.88.168.50; IPV:NLI; CTRY:US; EFV:NLI;
SFV:NSPM;
SFS:(10009020)(6009001)(336005)(39380400002)(39860400002)(2980300002)(1109001)(1110001)(339900001)(189002)(199003)(6916009)(1076002)(36756003)(104016004)(47776003)(86362001)(2906002)(2950100002)(77096006)(50226002)(5003940100001)(50986999)(189998001)(97736004)(33646002)(498600001)(48376002)(54906002)(81156014)(81166006)(5660300001)(76176999)(53936002)(85426001)(4326008)(8676002)(8936002)(50466002)(356003)(8656003)(106466001)(105606002)(2351001)(110136004)(626005)(68736007)(305945005);
DIR:OUT; SFP:1101; SCL:1; SRVR:CY1PR03MB2267; H:tx30smr01.am.freescale.net;
FPR:; SPF:Fail; PTR:InfoDomainNonexistent; MX:1; A:1; LANG:en;
X-Microsoft-Exchange-Diagnostics: 1; BN1AFFO11FD035;
1:j2PEqtp3GHatnaP01yOJGJP6aClWQmW8JM1DhSv8vduA6OWfT55Bd36EOEcm9CWN7+Hzlw7gCxUxGLp4fHxZ8riMFmCsQw2wbSp7AuzITylizsKBVJBEadOm+jmjuE3j
MIME-Version: 1.0
Content-Type: text/plain
X-MS-PublicTrafficType: Email
X-MS-Office365-Filtering-Correlation-Id: c712b414-2e8c-4772-db59-08d4ea2fa23a
X-Microsoft-Antispam: UriScan:; BCL:0; PCL:0;
RULEID:(300000500095)(300135000095)(300000501095)(300135300095)(22001)(300000502095)(300135100095)(300000503095)(300135400095)(2017052603185)(201703131430075)(201703131517081)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095);
SRVR:CY1PR03MB2267;
X-Microsoft-Exchange-Diagnostics: 1; CY1PR03MB2267;
3:3+zlQubi7HSpETzLgxKt3p85wxX52uRwBDoBkXg866u1TSVpsIwcAWf8tF37cPNi9gGwTyN7ZHedtgIuPnRRopHdGWTo6Qrln43WDAGtbe9TA0tTeflbT5nF/8HNjJ+ZsHKxmTiAlHjQTMbBxGLPf/t1zMAaZG32o8ChI+hjhqdIMn7QG7pVehXlYqk/YHC2VqRID3+8DtG8yxLzbhz8TKBJmJkxWaAuY9/V5YKRXw4Bv4ziqrwdEoMPORWvbgQqymvVsZJErG3fSvGpdui+Tl986b5mZ41T7qp4Y8BtHzSLc5/8wEgkULgjJSPF8c/jVBbVmBBYRjkWW//8UXmL/9i1A6MLX1LFPZRgr8qqky4=;
25:Vg9gg71Xa898khIqrZhBgai0X+oXhw0mesV5qkMQE9ZMlsDDz/+Kxb9oASrgmhf+vqM+7j331bwsJBw63Bc8ph82lk/BxXQn3qbnU1TSI4woCWrl+7qPRDDJZFq6skM0F6Ij/dWKzuhJU5aSK1pSMT4/KYlZMrnPdRD/iADqNlCbm7km9vBMNDaqyPQ6MVzcYoUTzOvgPlxtKh0QTd2t+vy3+M1DIsz9V8VNCx4KlnkiKv7DaI22aHWYSbxtMo4bUtkI+/kuGt31SQ4w06twWUM1SI/f4xaZiDtIcFz4QBslCEvd57ah/VYtDIMqiw7yLSBfYxwrrPbcuWNmjf/xRw==
X-MS-TrafficTypeDiagnostic: CY1PR03MB2267:
X-Microsoft-Exchange-Diagnostics: 1; CY1PR03MB2267;
31:cOniNyFF4eauoFzscLsHdUKqEeNhb6O6PGbFjsFt23MYhK8mhLwDl+LurpNmJHbO06ILW03s12iq0yMybxOOmQLDGUCDjwAR54FDsjPZQCPzU7V5DZmgMZ5hnPdRR9+W23tjdBow7qQ5ge1xxZFkKCg+/AEr6E4sB332zOOD4F9nO1owSjiaxOZ4th/WbgylmM0OK1zBwkoqWxsAsXbSBcDQ31etUTLNc2iHKXPK4is=;
4:4D8RlxKgnkpuMsZZ+tAEB2w73DoOurNE2zRGaVmZ9jUd19ae6OhmJM/m9usCQY56vPjjcWOIHBM/d9nP3QvLmpbeofqOePrK/GxRlyR1aRW61NeElqqsT4kaWv+nMc/j7R1QnFh7jUQBFaF7wD5KnQw1lNGtC09foYx/vdo2z265XppYN10BKsukNFUHf43Bolirerh7r1c2cGWnxU52EQn9fMjx1PlXHDSCU2UwnSQWSsTQ+GGqo67dY1AtDj5zJIUuAB7xsF93SbQAhkKnNVJWoKXP4dN7LpTIokODLDo=
X-Exchange-Antispam-Report-Test: UriScan:(185117386973197);
X-Microsoft-Antispam-PRVS: <CY1PR03MB22673DDDBD247AFD3B96338790850@CY1PR03MB2267.namprd03.prod.outlook.com>
X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0;
RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6095135)(601004)(2401047)(8121501046)(13018025)(5005006)(13016025)(93006095)(93001095)(100000703101)(100105400095)(10201501046)(3002001)(6055026)(6096035)(20161123565025)(20161123559100)(20161123563025)(20161123556025)(201703131430075)(201703131433075)(201703131441075)(201703131448075)(201703161259150)(20161123561025)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);
SRVR:CY1PR03MB2267; BCL:0; PCL:0;
RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(400006)(100000804101)(100110200095)(100000805101)(100110500095);
SRVR:CY1PR03MB2267;
X-Forefront-PRVS: 040866B734
X-Microsoft-Exchange-Diagnostics: =?us-ascii?Q?1; CY1PR03MB2267;
23:QzcsxIBK7VRHCyTOuAEkL90xKXb4KuXE34+vQQ0Yk?=
=?us-ascii?Q?4EiE4b9WFncT7kaRi9yvpyKG28VWpzddJJ85H3S4z0lngyP8jkRvGY63536y?=
=?us-ascii?Q?/NVtwruc/0+m4SYM46yXUIQiHA+GSCYH5Z5UVYYRwcAOSXUKOFuDwE+K5azk?=
=?us-ascii?Q?+M3gcTP0pKksrdN8NbEfyIry1Ync9dg8qva6BfkfElsfGqZMfjoK0Cbv7Wl7?=
=?us-ascii?Q?/G/DWZ5X3AU2/ZgA1AZV4RXfIoQX0dfUg8dK+Eb+85jTWABzDhGp0jA4F6yd?=
=?us-ascii?Q?62ruKA3uEOMGYmP0y3AYVqgN9xoujB5aY7NrBZxfE0/4vuSzTD6bOKoqRAvn?=
=?us-ascii?Q?OMc8an16P153wmBPf3f88FLWnt2RBL6Em0NiqpXNiUZJEMOEUYRn21zyudUf?=
=?us-ascii?Q?XC5heHg6EOwodtQX0Y25/LQaYBJxAB7EUqiH4DjOMjUherm2c2wA6WhDtZdm?=
=?us-ascii?Q?QnLJk6V0L+L4o2GRnEU9dApVgvaiM5k6Wh9a4gOzzg1unwoqhBhVUSbbw2uR?=
=?us-ascii?Q?+Ec1TVyjBozdi1dM3YzEoWWjJbT9hBAJUQC7Iv4OzaRUq4V8rt7oYhHqD/XR?=
=?us-ascii?Q?ih7ARLBL1iCfP8EAjQC/C0+eYnxXGbn4rGxNZQZHuNqhLrgrbRv1UGeNaJEH?=
=?us-ascii?Q?BqlbbfuwoGQcuxdHHYqgtYnrjnVEFB4KuXAweXGBTPpgd7Qr1GHHY7WATKZp?=
=?us-ascii?Q?Rl2Yn7kND1J0RCesruAGQbqAT1BG7hOLfuYrtUDUzlTWVp75yIbg7+oUBauL?=
=?us-ascii?Q?8d5F3C64Q5d87bQLvHGv5Zm2XwkQ/y1uDZSaxMjQOKcq2CdAHXfp8YeZIMYx?=
=?us-ascii?Q?ndAldbkd/dgaQyq0cI7viBLNZ1dkI2pIKkNtZohF73g2myHIE0xGhoDPt1/M?=
=?us-ascii?Q?A6fS6sZPaDQiLH9cW2Z9iWLRsB3oMq1Hn7/g0QJNM+qXZA2Cu9MylkG/vPGx?=
=?us-ascii?Q?h5Zmpv0o+0zxZpgaGDhnCVVeF42HaZFMRc5VFu6ms8BCVrfIYyhqPYBSCB2m?=
=?us-ascii?Q?1C0asz7gerjDnYPy3Ntqagk0IoGB+z9Rh+vO6wf4kqtr7myL4T+Csudof1ig?=
=?us-ascii?Q?u6q5ELsKXoDNUOYrm1JTjWoWFZhp3CW5P5k08j+Z8LznUS5fYr7MWoVss4qx?=
=?us-ascii?Q?qnsBOJPq8S3jVuKwyItlCCYb2A5kGBJ?=
X-Microsoft-Exchange-Diagnostics: 1; CY1PR03MB2267;
6:D8oWBEde2yNoXW5ZrW5bf+GheEOaEMjuClgZDTznvq90xFuAkL0DcpXoKa654HnSeJAzoQPh9NAmfOq+7hEY2i4kitVUqt3vODL3to+H/AB8pnfQDd/tWQ8Prf2lv6nv6HcvZRCqI2W/YOBqrO9xxDv8ecVbghqTn/cJX0Oa+V8lCL37P7Nwb8emd4r5um8zf9RIHM6t62W4mlbRCMP4H1mZuCdcSptfXLAMnkXEMhig8NYlJAkWSI/MBr/5UNsVDLBRhsT26vDi74hoCVdm5OlSUas4f/vMMv3dq8eQYAL7lJqdV3xGvx8BRdIOiLOA90Q1/mpzntfYFsDHiU0LtQ==;
5:sZhZeo0R8xuO6W53UUsbM7lKLRZl6vJhj4r9PPDG9/7NXDQsaw98caJtv1Nxs+fi8kqJmQ4MAPAl8c6ENoffGzdJqhXan79cX7ghR9IfjtonyrQm/nBS8fMYzA9kYBfPB2K75DyBMeT5RCJWeH8rBA==;
24:jpWDBVSA2d/rG3eMtuzzXcQaN1khlB65Gxc15SXXrNlVYUZFR05hGXHAs788KDYzT3GkfY6lIh/LToHnMmkEss5tvQGfEj66hJDtrFXgrBE=;
7:kPFYt3qL3dv5eDs+GCxImmW+ZvXa+5+gjT44O53Ha82zWK0JtLPMn8ugkrXw6nMy/QzSiUzC58/cWGAsH3vQe9K8HnuSFS1+ge4jQu6RV99dV/0F/J00G+U/QVwkqIHJRVwCHnUYxB0Nwos+II/eNDPyBt5mNUNYMbswHvZcUrg8fYRfPcrJfohdEphWUCRXEkpjWsbSZnVdmpihU+uzgjOEvQ7ZIzD0q5PCkJqAKE8=
SpamDiagnosticOutput: 1:99
SpamDiagnosticMetadata: NSPM
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 Aug 2017 14:02:46.9247 (UTC)
X-MS-Exchange-CrossTenant-Id: 5afe0b00-7697-4969-b663-5eab37d5f47e
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=5afe0b00-7697-4969-b663-5eab37d5f47e; Ip=[192.88.168.50];
Helo=[tx30smr01.am.freescale.net]
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1PR03MB2267
Subject: [dpdk-dev] [PATCH v3 09/40] bus/dpaa: add routines for managing a
RB tree
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
X-List-Received-Date: Wed, 23 Aug 2017 14:02:49 -0000
QMAN frames are managed over a RB tree data structure.
This patch introduces necessary routines for implementing a RB tree.
Signed-off-by: Geoff Thorpe <geoff.thorpe@nxp.com>
Signed-off-by: Hemant Agrawal <hemant.agrawal@nxp.com>
Signed-off-by: Shreyansh Jain <shreyansh.jain@nxp.com>
---
drivers/bus/dpaa/include/dpaa_rbtree.h | 143 +++++++++++++++++++++++++++++++++
1 file changed, 143 insertions(+)
create mode 100644 drivers/bus/dpaa/include/dpaa_rbtree.h
diff --git a/drivers/bus/dpaa/include/dpaa_rbtree.h b/drivers/bus/dpaa/include/dpaa_rbtree.h
new file mode 100644
index 0000000..f8c9b59
--- /dev/null
+++ b/drivers/bus/dpaa/include/dpaa_rbtree.h
@@ -0,0 +1,143 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright 2017 NXP.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ * * Neither the name of NXP nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef __DPAA_RBTREE_H
+#define __DPAA_RBTREE_H
+
+#include <rte_common.h>
+/************/
+/* RB-trees */
+/************/
+
+/* Linux has a good RB-tree implementation, that we can't use (GPL). It also has
+ * a flat/hooked-in interface that virtually requires license-contamination in
+ * order to write a caller-compatible implementation. Instead, I've created an
+ * RB-tree encapsulation on top of linux's primitives (it does some of the work
+ * the client logic would normally do), and this gives us something we can
+ * reimplement on LWE. Unfortunately there's no good+free RB-tree
+ * implementations out there that are license-compatible and "flat" (ie. no
+ * dynamic allocation). I did find a malloc-based one that I could convert, but
+ * that will be a task for later on. For now, LWE's RB-tree is implemented using
+ * an ordered linked-list.
+ *
+ * Note, the only linux-esque type is "struct rb_node", because it's used
+ * statically in the exported header, so it can't be opaque. Our version doesn't
+ * include a "rb_parent_color" field because we're doing linked-list instead of
+ * a true rb-tree.
+ */
+
+struct rb_node {
+ struct rb_node *prev, *next;
+};
+
+struct dpa_rbtree {
+ struct rb_node *head, *tail;
+};
+
+#define DPAA_RBTREE { NULL, NULL }
+static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
+{
+ tree->head = tree->tail = NULL;
+}
+
+#define QMAN_NODE2OBJ(ptr, type, node_field) \
+ (type *)((char *)ptr - offsetof(type, node_field))
+
+#define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
+static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
+{ \
+ struct rb_node *node = tree->head; \
+ if (!node) { \
+ tree->head = tree->tail = &obj->node_field; \
+ obj->node_field.prev = obj->node_field.next = NULL; \
+ return 0; \
+ } \
+ while (node) { \
+ type *item = QMAN_NODE2OBJ(node, type, node_field); \
+ if (obj->val_field == item->val_field) \
+ return -EBUSY; \
+ if (obj->val_field < item->val_field) { \
+ if (tree->head == node) \
+ tree->head = &obj->node_field; \
+ else \
+ node->prev->next = &obj->node_field; \
+ obj->node_field.prev = node->prev; \
+ obj->node_field.next = node; \
+ node->prev = &obj->node_field; \
+ return 0; \
+ } \
+ node = node->next; \
+ } \
+ obj->node_field.prev = tree->tail; \
+ obj->node_field.next = NULL; \
+ tree->tail->next = &obj->node_field; \
+ tree->tail = &obj->node_field; \
+ return 0; \
+} \
+static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
+{ \
+ if (tree->head == &obj->node_field) { \
+ if (tree->tail == &obj->node_field) \
+ /* Only item in the list */ \
+ tree->head = tree->tail = NULL; \
+ else { \
+ /* Is the head, next != NULL */ \
+ tree->head = tree->head->next; \
+ tree->head->prev = NULL; \
+ } \
+ } else { \
+ if (tree->tail == &obj->node_field) { \
+ /* Is the tail, prev != NULL */ \
+ tree->tail = tree->tail->prev; \
+ tree->tail->next = NULL; \
+ } else { \
+ /* Is neither the head nor the tail */ \
+ obj->node_field.prev->next = obj->node_field.next; \
+ obj->node_field.next->prev = obj->node_field.prev; \
+ } \
+ } \
+} \
+static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
+{ \
+ struct rb_node *node = tree->head; \
+ while (node) { \
+ type *item = QMAN_NODE2OBJ(node, type, node_field); \
+ if (val == item->val_field) \
+ return item; \
+ if (val < item->val_field) \
+ return NULL; \
+ node = node->next; \
+ } \
+ return NULL; \
+}
+
+#endif /* __DPAA_RBTREE_H */
--
2.9.3