[PATCH v2 1/3] graph: avoid global node ID counter

[PATCH v2 1/3] graph: avoid global node ID counter

[kirankumark]

From: Kiran Kumar K <kirankumark@marvell.com>

The node id is determined based on a global variable that is
incremented every time a node is created. Adding changes to
remove the global counter. Make sure that the node list is always
ordered by increasing node ids. When creating a new node, pick a free
id which is not allocated.

Signed-off-by: Kiran Kumar K <kirankumark@marvell.com>
---
 lib/graph/graph_private.h |  8 ----
 lib/graph/node.c          | 81 +++++++++++++++++++++++++++++++++------
 2 files changed, 69 insertions(+), 20 deletions(-)

diff --git a/lib/graph/graph_private.h b/lib/graph/graph_private.h
index da48d73587..fdaf5649b8 100644
--- a/lib/graph/graph_private.h
+++ b/lib/graph/graph_private.h
@@ -29,14 +29,6 @@ extern int rte_graph_logtype;
 #define graph_info(...) GRAPH_LOG(INFO, __VA_ARGS__)
 #define graph_dbg(...) GRAPH_LOG(DEBUG, __VA_ARGS__)
 
-#define ID_CHECK(id, id_max)                                                   \
-	do {                                                                   \
-		if ((id) >= (id_max)) {                                        \
-			rte_errno = EINVAL;                                    \
-			goto fail;                                             \
-		}                                                              \
-	} while (0)
-
 #define SET_ERR_JMP(err, where, fmt, ...)                                      \
 	do {                                                                   \
 		graph_err(fmt, ##__VA_ARGS__);                                 \
diff --git a/lib/graph/node.c b/lib/graph/node.c
index 63db629da8..0f382d744c 100644
--- a/lib/graph/node.c
+++ b/lib/graph/node.c
@@ -15,9 +15,51 @@
 #include "graph_private.h"
 
 static struct node_head node_list = STAILQ_HEAD_INITIALIZER(node_list);
-static rte_node_t node_id;
 
-#define NODE_ID_CHECK(id) ID_CHECK(id, node_id)
+static struct node *
+node_from_id(rte_node_t id)
+{
+	struct node *node;
+
+	STAILQ_FOREACH(node, &node_list, next) {
+		if (node->id == id)
+			return node;
+	}
+	rte_errno = EINVAL;
+	return NULL;
+}
+
+static rte_node_t
+next_next_free_id(void)
+{
+	struct node *node;
+	rte_node_t id = 0;
+
+	STAILQ_FOREACH(node, &node_list, next) {
+		if (id < node->id)
+			break;
+		id = node->id + 1;
+	}
+	return id;
+}
+
+static void
+node_insert_ordered(struct node *node)
+{
+	struct node *after, *g;
+
+	after = NULL;
+	STAILQ_FOREACH(g, &node_list, next) {
+		if (g->id < node->id)
+			after = g;
+		else if (g->id > node->id)
+			break;
+	}
+	if (after == NULL)
+		STAILQ_INSERT_HEAD(&node_list, node, next);
+	else
+		STAILQ_INSERT_AFTER(&node_list, after, node, next);
+}
 
 /* Private functions */
 struct node_head *
@@ -116,10 +158,10 @@ __rte_node_register(const struct rte_node_register *reg)
 	}
 
 	node->lcore_id = RTE_MAX_LCORE;
-	node->id = node_id++;
+	node->id = next_next_free_id();
 
-	/* Add the node at tail */
-	STAILQ_INSERT_TAIL(&node_list, node, next);
+	/* Add the node in ordered list */
+	node_insert_ordered(node);
 	graph_spinlock_unlock();
 
 	return node->id;
@@ -194,7 +236,9 @@ rte_node_clone(rte_node_t id, const char *name)
 {
 	struct node *node;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
+
 	STAILQ_FOREACH(node, &node_list, next)
 		if (node->id == id)
 			return node_clone(node, name);
@@ -220,7 +264,8 @@ rte_node_id_to_name(rte_node_t id)
 {
 	struct node *node;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 	STAILQ_FOREACH(node, &node_list, next)
 		if (node->id == id)
 			return node->name;
@@ -234,7 +279,8 @@ rte_node_edge_count(rte_node_t id)
 {
 	struct node *node;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 	STAILQ_FOREACH(node, &node_list, next)
 		if (node->id == id)
 			return node->nb_edges;
@@ -303,7 +349,8 @@ rte_node_edge_shrink(rte_node_t id, rte_edge_t size)
 	rte_edge_t rc = RTE_EDGE_ID_INVALID;
 	struct node *node;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 	graph_spinlock_lock();
 
 	STAILQ_FOREACH(node, &node_list, next) {
@@ -330,7 +377,8 @@ rte_node_edge_update(rte_node_t id, rte_edge_t from, const char **next_nodes,
 	rte_edge_t rc = RTE_EDGE_ID_INVALID;
 	struct node *n, *prev;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 	graph_spinlock_lock();
 
 	prev = NULL;
@@ -364,7 +412,8 @@ rte_node_edge_get(rte_node_t id, char *next_nodes[])
 	rte_node_t rc = RTE_NODE_ID_INVALID;
 	struct node *node;
 
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 	graph_spinlock_lock();
 
 	STAILQ_FOREACH(node, &node_list, next) {
@@ -388,7 +437,8 @@ node_scan_dump(FILE *f, rte_node_t id, bool all)
 	struct node *node;
 
 	RTE_ASSERT(f != NULL);
-	NODE_ID_CHECK(id);
+	if (node_from_id(id) == NULL)
+		goto fail;
 
 	STAILQ_FOREACH(node, &node_list, next) {
 		if (all == true) {
@@ -417,5 +467,12 @@ rte_node_list_dump(FILE *f)
 rte_node_t
 rte_node_max_count(void)
 {
+	rte_node_t node_id = 0;
+	struct node *node;
+
+	STAILQ_FOREACH(node, &node_list, next) {
+		if (node_id < node->id)
+			node_id = node->id;
+	}
 	return node_id;
 }
-- 
2.43.0

[PATCH v2 2/3] graph: add support for node free API

[kirankumark]

From: Kiran Kumar K <kirankumark@marvell.com>

Add support for rte_node_free API to free the node and its
memory, if node is not part of any of the created graphs.

Signed-off-by: Kiran Kumar K <kirankumark@marvell.com>
---
 lib/graph/graph.c         | 16 ++++++++++++++++
 lib/graph/graph_private.h | 13 +++++++++++++
 lib/graph/node.c          | 21 +++++++++++++++++++++
 lib/graph/rte_graph.h     | 15 +++++++++++++++
 lib/graph/version.map     |  3 +++
 5 files changed, 68 insertions(+)

diff --git a/lib/graph/graph.c b/lib/graph/graph.c
index dff8e690a8..3a2648a1fc 100644
--- a/lib/graph/graph.c
+++ b/lib/graph/graph.c
@@ -20,6 +20,22 @@
 static struct graph_head graph_list = STAILQ_HEAD_INITIALIZER(graph_list);
 static rte_spinlock_t graph_lock = RTE_SPINLOCK_INITIALIZER;
 
+uint8_t
+graph_is_node_active_in_graph(struct node *node)
+{
+	struct graph *graph;
+
+	STAILQ_FOREACH(graph, &graph_list, next) {
+		struct graph_node *graph_node;
+
+		STAILQ_FOREACH(graph_node, &graph->node_list, next)
+			if (graph_node->node == node)
+				return 1;
+	}
+
+	return 0;
+}
+
 /* Private functions */
 static struct graph *
 graph_from_id(rte_graph_t id)
diff --git a/lib/graph/graph_private.h b/lib/graph/graph_private.h
index fdaf5649b8..a29dad76d0 100644
--- a/lib/graph/graph_private.h
+++ b/lib/graph/graph_private.h
@@ -440,4 +440,17 @@ int graph_sched_wq_create(struct graph *_graph, struct graph *_parent_graph,
  */
 void graph_sched_wq_destroy(struct graph *_graph);
 
+/**
+ * @internal
+ *
+ * Check if given node present in any of the created graphs.
+ *
+ * @param node
+ *   The node object
+ *
+ * @return
+ *   0 if not present in any graph, else return 1.
+ */
+uint8_t graph_is_node_active_in_graph(struct node *_node);
+
 #endif /* _RTE_GRAPH_PRIVATE_H_ */
diff --git a/lib/graph/node.c b/lib/graph/node.c
index 0f382d744c..669c845a2b 100644
--- a/lib/graph/node.c
+++ b/lib/graph/node.c
@@ -476,3 +476,24 @@ rte_node_max_count(void)
 	}
 	return node_id;
 }
+
+int
+rte_node_free(rte_node_t id)
+{
+	struct node *node;
+
+	if (node_from_id(id) == NULL)
+		goto fail;
+
+	STAILQ_FOREACH(node, &node_list, next) {
+		if (id == node->id) {
+			if (graph_is_node_active_in_graph(node))
+				return -1;
+			STAILQ_REMOVE(&node_list, node, node, next);
+			free(node);
+			return 0;
+		}
+	}
+fail:
+	return -1;
+}
diff --git a/lib/graph/rte_graph.h b/lib/graph/rte_graph.h
index f5e575dbed..097d0dc9d5 100644
--- a/lib/graph/rte_graph.h
+++ b/lib/graph/rte_graph.h
@@ -22,6 +22,7 @@
 #include <stdio.h>
 
 #include <rte_common.h>
+#include <rte_compat.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -661,6 +662,20 @@ rte_node_is_invalid(rte_node_t id)
 	return (id == RTE_NODE_ID_INVALID);
 }
 
+/**
+ * Release the memory allocated for a node created using RTE_NODE_REGISTER or rte_node_clone,
+ * if it is not linked to any graphs.
+ *
+ * @param id
+ *   Node id to check.
+ *
+ * @return
+ *   - 0: Success.
+ *   -<0: Failure.
+ */
+__rte_experimental
+int rte_node_free(rte_node_t id);
+
 /**
  * Test the validity of edge id.
  *
diff --git a/lib/graph/version.map b/lib/graph/version.map
index 44fadc00fd..a793ea1d8e 100644
--- a/lib/graph/version.map
+++ b/lib/graph/version.map
@@ -58,4 +58,7 @@ EXPERIMENTAL {
 
 	# added in 24.11
 	rte_node_xstat_increment;
+
+	# added in 25.03
+	rte_node_free;
 };
-- 
2.43.0

Re: [PATCH v2 2/3] graph: add support for node free API

[Huichao Cai]

Do these newly added functions need to protect the linked list with spin lock graph_stpinlock_lock?

Re: [PATCH v2 2/3] graph: add support for node free API

[Huichao Cai]

By the way, I don't know where to consult about this issue at the moment.
Please forgive me for discussing this issue here. Can we set up a chat box on this
page instead of having to comment through email or git send email? Many email clients
cannot set the In Reply To header or do not currently have a git send email environment,
which is not conducive to the timeliness and convenience of comments.

[PATCH v2 3/3] test/graph: fix graph autotest second run test failure

[kirankumark]

From: Kiran Kumar K <kirankumark@marvell.com>

The graph autotest second run test is failing due to the
node name is already present in the node list. Adding changes
to free nodes at the time of test cleanup.

Fixes: 6b89650418fe ("test/graph: add functional tests")

Signed-off-by: Kiran Kumar K <kirankumark@marvell.com>
---
 app/test/test_graph.c | 96 ++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 90 insertions(+), 6 deletions(-)

diff --git a/app/test/test_graph.c b/app/test/test_graph.c
index 2840a25b13..e712dbebf7 100644
--- a/app/test/test_graph.c
+++ b/app/test/test_graph.c
@@ -68,6 +68,8 @@ static void *mbuf_p[MAX_NODES + 1][MBUFF_SIZE];
 static rte_graph_t graph_id;
 static uint64_t obj_stats[MAX_NODES + 1];
 static uint64_t fn_calls[MAX_NODES + 1];
+static uint32_t dummy_nodes_id[MAX_NODES];
+static int dummy_nodes_id_count;
 
 const char *node_patterns[] = {
 	"test_node_source1",	   "test_node00",
@@ -541,6 +543,66 @@ test_lookup_functions(void)
 	return 0;
 }
 
+static int
+test_node_id(void)
+{
+	uint32_t node_id, odummy_id, dummy_id, dummy_id1;
+
+	node_id = rte_node_from_name("test_node00");
+
+	dummy_id = rte_node_clone(node_id, "test_node_id00");
+	if (rte_node_is_invalid(dummy_id)) {
+		printf("Got invalid id when clone\n");
+		return -1;
+	}
+
+	dummy_id1 = rte_node_clone(node_id, "test_node_id01");
+	if (rte_node_is_invalid(dummy_id1)) {
+		printf("Got invalid id when clone\n");
+		return -1;
+	}
+
+	/* Expect next node id to be node_id + 1 */
+	if ((dummy_id + 1) != dummy_id1) {
+		printf("Node id didn't match, expected = %d got = %d\n",
+		       dummy_id+1, dummy_id1);
+		return -1;
+	}
+
+	odummy_id = dummy_id;
+	/* Free one of the cloned node */
+	if (rte_node_free(dummy_id)) {
+		printf("Failed to free node\n");
+		return -1;
+	}
+
+	/* Clone again, should get the same id, that is freed */
+	dummy_id = rte_node_clone(node_id, "test_node_id00");
+	if (rte_node_is_invalid(dummy_id)) {
+		printf("Got invalid id when clone\n");
+		return -1;
+	}
+
+	if (dummy_id != odummy_id) {
+		printf("Node id didn't match, expected = %d got = %d\n",
+		       odummy_id, dummy_id);
+		return -1;
+	}
+
+	/* Free the node */
+	if (rte_node_free(dummy_id)) {
+		printf("Failed to free node\n");
+		return -1;
+	}
+
+	if (rte_node_free(dummy_id1)) {
+		printf("Failed to free node\n");
+		return -1;
+	}
+
+	return 0;
+}
+
 static int
 test_node_clone(void)
 {
@@ -551,11 +613,12 @@ test_node_clone(void)
 	node_id = rte_node_from_name("test_node00");
 	tm->test_node[0].idx = node_id;
 
-	dummy_id = rte_node_clone(node_id, "test_node00");
-	if (rte_node_is_invalid(dummy_id)) {
+	dummy_nodes_id[dummy_nodes_id_count] = rte_node_clone(node_id, "test_node00");
+	if (rte_node_is_invalid(dummy_nodes_id[dummy_nodes_id_count])) {
 		printf("Got invalid id when clone, Expecting fail\n");
 		return -1;
 	}
+	dummy_nodes_id_count++;
 
 	/* Clone with same name, should fail */
 	dummy_id = rte_node_clone(node_id, "test_node00");
@@ -635,15 +698,15 @@ test_create_graph(void)
 		.nb_node_patterns = 6,
 		.node_patterns = node_patterns_dummy,
 	};
-	uint32_t dummy_node_id;
 	uint32_t node_id;
 
 	node_id = rte_node_from_name("test_node00");
-	dummy_node_id = rte_node_clone(node_id, "dummy_node");
-	if (rte_node_is_invalid(dummy_node_id)) {
+	dummy_nodes_id[dummy_nodes_id_count] = rte_node_clone(node_id, "dummy_node");
+	if (rte_node_is_invalid(dummy_nodes_id[dummy_nodes_id_count])) {
 		printf("Got invalid node id\n");
 		return -1;
 	}
+	dummy_nodes_id_count++;
 
 	graph_id = rte_graph_create("worker0", &gconf);
 	if (graph_id != RTE_GRAPH_ID_INVALID) {
@@ -1026,17 +1089,38 @@ graph_setup(void)
 	}
 	printf("test_node_clone: pass\n");
 
+	if (test_node_id()) {
+		printf("test_node_id: fail\n");
+		return -1;
+	}
+	printf("test_node_id: pass\n");
+
 	return 0;
 }
 
 static void
 graph_teardown(void)
 {
-	int id;
+	int id, i;
 
 	id = rte_graph_destroy(rte_graph_from_name("worker0"));
 	if (id)
 		printf("Graph Destroy failed\n");
+
+	for (i = 1; i < MAX_NODES; i++) {
+		if (rte_node_free(test_main.test_node[i].idx)) {
+			printf("Node free failed\n");
+			return;
+		}
+	}
+
+	for (i = 0; i < dummy_nodes_id_count; i++) {
+		if (rte_node_free(dummy_nodes_id[i])) {
+			printf("Node free failed\n");
+			return;
+		}
+	}
+	dummy_nodes_id_count = 0;
 }
 
 static struct unit_test_suite graph_testsuite = {
-- 
2.43.0

Re: [PATCH v2 1/3] graph: avoid global node ID counter

[Robin Jarry]

, Nov 11, 2024 at 08:34:
> From: Kiran Kumar K <kirankumark@marvell.com>
>
> The node id is determined based on a global variable that is
> incremented every time a node is created. Adding changes to
> remove the global counter. Make sure that the node list is always
> ordered by increasing node ids. When creating a new node, pick a free
> id which is not allocated.
>
> Signed-off-by: Kiran Kumar K <kirankumark@marvell.com>

Hi Kiran,

Thanks for the fix.

I think most of the accesses to the node_list is racy. Maybe we need to 
add a lock to protect that linked list from concurrent access?

> ---
>  lib/graph/graph_private.h |  8 ----
>  lib/graph/node.c          | 81 +++++++++++++++++++++++++++++++++------
>  2 files changed, 69 insertions(+), 20 deletions(-)
>
> diff --git a/lib/graph/graph_private.h b/lib/graph/graph_private.h
> index da48d73587..fdaf5649b8 100644
> --- a/lib/graph/graph_private.h
> +++ b/lib/graph/graph_private.h
> @@ -29,14 +29,6 @@ extern int rte_graph_logtype;
>  #define graph_info(...) GRAPH_LOG(INFO, __VA_ARGS__)
>  #define graph_dbg(...) GRAPH_LOG(DEBUG, __VA_ARGS__)
>  
> -#define ID_CHECK(id, id_max)                                                   \
> -	do {                                                                   \
> -		if ((id) >= (id_max)) {                                        \
> -			rte_errno = EINVAL;                                    \
> -			goto fail;                                             \
> -		}                                                              \
> -	} while (0)
> -
>  #define SET_ERR_JMP(err, where, fmt, ...)                                      \
>  	do {                                                                   \
>  		graph_err(fmt, ##__VA_ARGS__);                                 \
> diff --git a/lib/graph/node.c b/lib/graph/node.c
> index 63db629da8..0f382d744c 100644
> --- a/lib/graph/node.c
> +++ b/lib/graph/node.c
> @@ -15,9 +15,51 @@
>  #include "graph_private.h"
>  
>  static struct node_head node_list = STAILQ_HEAD_INITIALIZER(node_list);
> -static rte_node_t node_id;
>  
> -#define NODE_ID_CHECK(id) ID_CHECK(id, node_id)
> +static struct node *
> +node_from_id(rte_node_t id)
> +{
> +	struct node *node;
> +
> +	STAILQ_FOREACH(node, &node_list, next) {
> +		if (node->id == id)
> +			return node;
> +	}
> +	rte_errno = EINVAL;
> +	return NULL;
> +}
> +
> +static rte_node_t
> +next_next_free_id(void)
> +{
> +	struct node *node;
> +	rte_node_t id = 0;
> +
> +	STAILQ_FOREACH(node, &node_list, next) {
> +		if (id < node->id)
> +			break;
> +		id = node->id + 1;
> +	}
> +	return id;
> +}
> +
> +static void
> +node_insert_ordered(struct node *node)
> +{
> +	struct node *after, *g;
> +
> +	after = NULL;
> +	STAILQ_FOREACH(g, &node_list, next) {
> +		if (g->id < node->id)
> +			after = g;
> +		else if (g->id > node->id)
> +			break;
> +	}
> +	if (after == NULL)
> +		STAILQ_INSERT_HEAD(&node_list, node, next);
> +	else
> +		STAILQ_INSERT_AFTER(&node_list, after, node, next);
> +}
>  
>  /* Private functions */
>  struct node_head *
> @@ -116,10 +158,10 @@ __rte_node_register(const struct rte_node_register *reg)
>  	}
>  
>  	node->lcore_id = RTE_MAX_LCORE;
> -	node->id = node_id++;
> +	node->id = next_next_free_id();
>  
> -	/* Add the node at tail */
> -	STAILQ_INSERT_TAIL(&node_list, node, next);
> +	/* Add the node in ordered list */
> +	node_insert_ordered(node);
>  	graph_spinlock_unlock();
>  
>  	return node->id;
> @@ -194,7 +236,9 @@ rte_node_clone(rte_node_t id, const char *name)
>  {
>  	struct node *node;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
> +
>  	STAILQ_FOREACH(node, &node_list, next)
>  		if (node->id == id)
>  			return node_clone(node, name);
> @@ -220,7 +264,8 @@ rte_node_id_to_name(rte_node_t id)
>  {
>  	struct node *node;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  	STAILQ_FOREACH(node, &node_list, next)
>  		if (node->id == id)
>  			return node->name;
> @@ -234,7 +279,8 @@ rte_node_edge_count(rte_node_t id)
>  {
>  	struct node *node;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  	STAILQ_FOREACH(node, &node_list, next)
>  		if (node->id == id)
>  			return node->nb_edges;
> @@ -303,7 +349,8 @@ rte_node_edge_shrink(rte_node_t id, rte_edge_t size)
>  	rte_edge_t rc = RTE_EDGE_ID_INVALID;
>  	struct node *node;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  	graph_spinlock_lock();
>  
>  	STAILQ_FOREACH(node, &node_list, next) {
> @@ -330,7 +377,8 @@ rte_node_edge_update(rte_node_t id, rte_edge_t from, const char **next_nodes,
>  	rte_edge_t rc = RTE_EDGE_ID_INVALID;
>  	struct node *n, *prev;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  	graph_spinlock_lock();
>  
>  	prev = NULL;
> @@ -364,7 +412,8 @@ rte_node_edge_get(rte_node_t id, char *next_nodes[])
>  	rte_node_t rc = RTE_NODE_ID_INVALID;
>  	struct node *node;
>  
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  	graph_spinlock_lock();
>  
>  	STAILQ_FOREACH(node, &node_list, next) {
> @@ -388,7 +437,8 @@ node_scan_dump(FILE *f, rte_node_t id, bool all)
>  	struct node *node;
>  
>  	RTE_ASSERT(f != NULL);
> -	NODE_ID_CHECK(id);
> +	if (node_from_id(id) == NULL)
> +		goto fail;
>  
>  	STAILQ_FOREACH(node, &node_list, next) {
>  		if (all == true) {
> @@ -417,5 +467,12 @@ rte_node_list_dump(FILE *f)
>  rte_node_t
>  rte_node_max_count(void)
>  {
> +	rte_node_t node_id = 0;
> +	struct node *node;
> +
> +	STAILQ_FOREACH(node, &node_list, next) {
> +		if (node_id < node->id)
> +			node_id = node->id;
> +	}