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

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(-)
  

, 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;
> +	}