[v4,03/29] graph: implement node operations
Checks
Commit Message
From: Jerin Jacob <jerinj@marvell.com>
Adding node-specific API implementation like cloning node, updating
edges for the node, shrinking edges of a node, retrieving edges of a
node.
Signed-off-by: Jerin Jacob <jerinj@marvell.com>
Signed-off-by: Kiran Kumar K <kirankumark@marvell.com>
Signed-off-by: Pavan Nikhilesh <pbhagavatula@marvell.com>
Signed-off-by: Nithin Dabilpuram <ndabilpuram@marvell.com>
---
lib/librte_graph/graph_private.h | 10 +
lib/librte_graph/node.c | 271 +++++++++++++++++++++++++
lib/librte_graph/rte_graph_version.map | 10 +
3 files changed, 291 insertions(+)
Comments
On 4/5/20 10:55 AM, jerinj@marvell.com wrote:
[...]
> diff --git a/lib/librte_graph/node.c b/lib/librte_graph/node.c
> index 336cd1c94..d04a0fce0 100644
> --- a/lib/librte_graph/node.c
> +++ b/lib/librte_graph/node.c
[...]
> +static rte_edge_t
> +edge_update(struct node *node, struct node *prev, rte_edge_t from,
> + const char **next_nodes, rte_edge_t nb_edges)
> +{
> + rte_edge_t i, max_edges, count = 0;
> + struct node *new_node;
> + bool need_realloc;
> + size_t sz;
> +
> + if (from == RTE_EDGE_ID_INVALID)
> + from = node->nb_edges;
> +
> + /* Don't create hole in next_nodes[] list */
> + if (from > node->nb_edges) {
> + rte_errno = ENOMEM;
> + goto fail;
> + }
> +
> + /* Remove me from list */
> + STAILQ_REMOVE(&node_list, node, node, next);
> +
> + /* Allocate the storage space for new node if required */
> + max_edges = from + nb_edges;
> + need_realloc = max_edges > node->nb_edges;
> + if (need_realloc) {
> + sz = sizeof(struct node) + (max_edges * RTE_NODE_NAMESIZE);
> + new_node = realloc(node, sz);
> + if (new_node == NULL) {
> + rte_errno = ENOMEM;
> + goto restore;
> + } else {
> + node = new_node;
> + }
> + }
> +
> + /* Update the new nodes name */
> + for (i = from; i < max_edges; i++, count++) {
> + if (rte_strscpy(node->next_nodes[i], next_nodes[count],
> + RTE_NODE_NAMESIZE) < 0) {
> + rte_errno = E2BIG;
> + goto restore;
> + }
> + }
> +restore:
> + /* Update the linked list to point new node address in prev node */
> + if (prev)
> + STAILQ_INSERT_AFTER(&node_list, prev, node, next);
> + else
> + STAILQ_INSERT_HEAD(&node_list, node, next);
AFAIU node_list keeps the list of nodes - so I guess you wanted here
"replace" the old node pointer with the new one. I have not yet seen
the usage of this function but it seems to me like you unconditionally
insert the updated node - possibly having node pointer present doubly or
with stale pointer. I might be missing something here.
> +
> + if (need_realloc)
> + node->nb_edges += max_edges;
It looks to me like this should be simple '='.
> +
> +fail:
> + return count;
> +}
[...]
> +rte_edge_t
> +rte_node_edge_update(rte_node_t id, rte_edge_t from, const char **next_nodes,
> + uint16_t nb_edges)
> +{
> + rte_edge_t rc = RTE_EDGE_ID_INVALID;
> + struct node *n, *prev;
> +
> + NODE_ID_CHECK(id);
> + graph_spinlock_lock();
> +
> + prev = NULL;
> + STAILQ_FOREACH(n, &node_list, next) {
> + if (n->id == id) {
> + rc = edge_update(n, prev, from, next_nodes, nb_edges);
> + break;
> + }
> + prev = n;
> + }
OK so in this context my comment above seems to be valid. When we find
the id we have: prev -> n, we call update() and in there we insert
new_node after prev so we end up with: prev -> n' -> n where n' might be
new address for n or just n when no realloc was performed.
Do I miss anything?
> +
> + graph_spinlock_unlock();
> +fail:
> + return rc;
> +}
> +
> +static rte_node_t
> +node_copy_edges(struct node *node, char *next_nodes[])
> +{
> + rte_edge_t i;
> +
> + for (i = 0; i < node->nb_edges; i++)
> + next_nodes[i] = node->next_nodes[i];
> +
> + return i;
> +}
> +
> +rte_node_t
> +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);
> + graph_spinlock_lock();
> +
> + STAILQ_FOREACH(node, &node_list, next) {
> + if (node->id == id) {
> + if (next_nodes == NULL)
> + rc = sizeof(char *) * node->nb_edges;
> + else
> + rc = node_copy_edges(node, next_nodes);
Do we want to ready for next_nodes not large enough?
> + break;
> + }
> + }
> +
> + graph_spinlock_unlock();
> +fail:
> + return rc;
> +}
[...]
With regards
Andrzej Ostruszka
> -----Original Message-----
> From: Andrzej Ostruszka <amo@semihalf.com>
> Sent: Monday, April 6, 2020 11:27 PM
> To: Jerin Jacob Kollanukkaran <jerinj@marvell.com>; Kiran Kumar Kokkilagadda
> <kirankumark@marvell.com>
> Cc: dev@dpdk.org; thomas@monjalon.net; david.marchand@redhat.com;
> mdr@ashroe.eu; mattias.ronnblom@ericsson.com; Pavan Nikhilesh
> Bhagavatula <pbhagavatula@marvell.com>; Nithin Kumar Dabilpuram
> <ndabilpuram@marvell.com>; xiao.w.wang@intel.com
> Subject: [EXT] Re: [dpdk-dev] [PATCH v4 03/29] graph: implement node
> operations
>
> External Email
>
> ----------------------------------------------------------------------
> On 4/5/20 10:55 AM, jerinj@marvell.com wrote:
> [...]
> > diff --git a/lib/librte_graph/node.c b/lib/librte_graph/node.c index
> > 336cd1c94..d04a0fce0 100644
> > --- a/lib/librte_graph/node.c
> > +++ b/lib/librte_graph/node.c
> [...]
> > +static rte_edge_t
> > +edge_update(struct node *node, struct node *prev, rte_edge_t from,
> > + const char **next_nodes, rte_edge_t nb_edges) {
> > + rte_edge_t i, max_edges, count = 0;
> > + struct node *new_node;
> > + bool need_realloc;
> > + size_t sz;
> > +
> > + if (from == RTE_EDGE_ID_INVALID)
> > + from = node->nb_edges;
> > +
> > + /* Don't create hole in next_nodes[] list */
> > + if (from > node->nb_edges) {
> > + rte_errno = ENOMEM;
> > + goto fail;
> > + }
> > +
> > + /* Remove me from list */
> > + STAILQ_REMOVE(&node_list, node, node, next);
This is where we will remove the node first unconditionally. Later we update the new node.
> > +
> > + /* Allocate the storage space for new node if required */
> > + max_edges = from + nb_edges;
> > + need_realloc = max_edges > node->nb_edges;
> > + if (need_realloc) {
> > + sz = sizeof(struct node) + (max_edges * RTE_NODE_NAMESIZE);
> > + new_node = realloc(node, sz);
> > + if (new_node == NULL) {
> > + rte_errno = ENOMEM;
> > + goto restore;
> > + } else {
> > + node = new_node;
> > + }
> > + }
> > +
> > + /* Update the new nodes name */
> > + for (i = from; i < max_edges; i++, count++) {
> > + if (rte_strscpy(node->next_nodes[i], next_nodes[count],
> > + RTE_NODE_NAMESIZE) < 0) {
> > + rte_errno = E2BIG;
> > + goto restore;
> > + }
> > + }
> > +restore:
> > + /* Update the linked list to point new node address in prev node */
> > + if (prev)
> > + STAILQ_INSERT_AFTER(&node_list, prev, node, next);
> > + else
> > + STAILQ_INSERT_HEAD(&node_list, node, next);
>
> AFAIU node_list keeps the list of nodes - so I guess you wanted here "replace"
> the old node pointer with the new one. I have not yet seen the usage of this
> function but it seems to me like you unconditionally insert the updated node -
> possibly having node pointer present doubly or with stale pointer. I might be
> missing something here.
>
See above.
> > +
> > + if (need_realloc)
> > + node->nb_edges += max_edges;
>
> It looks to me like this should be simple '='.
>
> > +
> > +fail:
> > + return count;
> > +}
> [...]
> > +rte_edge_t
> > +rte_node_edge_update(rte_node_t id, rte_edge_t from, const char
> **next_nodes,
> > + uint16_t nb_edges)
> > +{
> > + rte_edge_t rc = RTE_EDGE_ID_INVALID;
> > + struct node *n, *prev;
> > +
> > + NODE_ID_CHECK(id);
> > + graph_spinlock_lock();
> > +
> > + prev = NULL;
> > + STAILQ_FOREACH(n, &node_list, next) {
> > + if (n->id == id) {
> > + rc = edge_update(n, prev, from, next_nodes,
> nb_edges);
> > + break;
> > + }
> > + prev = n;
> > + }
>
> OK so in this context my comment above seems to be valid. When we find the id
> we have: prev -> n, we call update() and in there we insert new_node after prev
> so we end up with: prev -> n' -> n where n' might be new address for n or just n
> when no realloc was performed.
>
> Do I miss anything?
>
See above.
> > +
> > + graph_spinlock_unlock();
> > +fail:
> > + return rc;
> > +}
> > +
> > +static rte_node_t
> > +node_copy_edges(struct node *node, char *next_nodes[]) {
> > + rte_edge_t i;
> > +
> > + for (i = 0; i < node->nb_edges; i++)
> > + next_nodes[i] = node->next_nodes[i];
> > +
> > + return i;
> > +}
> > +
> > +rte_node_t
> > +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);
> > + graph_spinlock_lock();
> > +
> > + STAILQ_FOREACH(node, &node_list, next) {
> > + if (node->id == id) {
> > + if (next_nodes == NULL)
> > + rc = sizeof(char *) * node->nb_edges;
> > + else
> > + rc = node_copy_edges(node, next_nodes);
>
> Do we want to ready for next_nodes not large enough?
>
> > + break;
> > + }
> > + }
> > +
> > + graph_spinlock_unlock();
> > +fail:
> > + return rc;
> > +}
>
> [...]
>
> With regards
> Andrzej Ostruszka
On 4/7/20 4:43 AM, Kiran Kumar Kokkilagadda wrote:
[...]
>>> +static rte_edge_t
>>> +edge_update(struct node *node, struct node *prev, rte_edge_t from,
>>> + const char **next_nodes, rte_edge_t nb_edges) {
>>> + rte_edge_t i, max_edges, count = 0;
>>> + struct node *new_node;
>>> + bool need_realloc;
>>> + size_t sz;
>>> +
>>> + if (from == RTE_EDGE_ID_INVALID)
>>> + from = node->nb_edges;
>>> +
>>> + /* Don't create hole in next_nodes[] list */
>>> + if (from > node->nb_edges) {
>>> + rte_errno = ENOMEM;
>>> + goto fail;
>>> + }
>>> +
>>> + /* Remove me from list */
>>> + STAILQ_REMOVE(&node_list, node, node, next);
>
> This is where we will remove the node first unconditionally. Later we update the new node.
Thanks Kiran, don't know how I missed that :)
With regards
Andrzej Ostruszka
>
> > > +
> > > + if (need_realloc)
> > > + node->nb_edges += max_edges;
> >
> > It looks to me like this should be simple '='.
Yes. Will fix in v5
@@ -13,6 +13,16 @@
#include "rte_graph.h"
+
+#define ID_CHECK(id, id_max) \
+ do { \
+ if ((id) >= (id_max)) { \
+ rte_errno = EINVAL; \
+ goto fail; \
+ } \
+ } while (0)
+
+
/**
* @internal
*
@@ -17,6 +17,8 @@
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)
+
/* Private functions */
struct node_head *
node_list_head_get(void)
@@ -111,3 +113,272 @@ __rte_node_register(const struct rte_node_register *reg)
return RTE_NODE_ID_INVALID;
}
+static int
+clone_name(struct rte_node_register *reg, struct node *node, const char *name)
+{
+ ssize_t sz, rc;
+
+#define SZ RTE_NODE_NAMESIZE
+ rc = rte_strscpy(reg->name, node->name, SZ);
+ if (rc < 0)
+ goto fail;
+ sz = rc;
+ rc = rte_strscpy(reg->name + sz, "-", RTE_MAX((int16_t)(SZ - sz), 0));
+ if (rc < 0)
+ goto fail;
+ sz += rc;
+ sz = rte_strscpy(reg->name + sz, name, RTE_MAX((int16_t)(SZ - sz), 0));
+ if (sz < 0)
+ goto fail;
+
+ return 0;
+fail:
+ rte_errno = E2BIG;
+ return -rte_errno;
+}
+
+static rte_node_t
+node_clone(struct node *node, const char *name)
+{
+ rte_node_t rc = RTE_NODE_ID_INVALID;
+ struct rte_node_register *reg;
+ rte_edge_t i;
+
+ /* Don't allow to clone a node from a cloned node */
+ if (node->parent_id != RTE_NODE_ID_INVALID) {
+ rte_errno = EEXIST;
+ goto fail;
+ }
+
+ /* Check for duplicate name */
+ if (node_has_duplicate_entry(name))
+ goto fail;
+
+ reg = calloc(1, sizeof(*reg) + (sizeof(char *) * node->nb_edges));
+ if (reg == NULL) {
+ rte_errno = ENOMEM;
+ goto fail;
+ }
+
+ /* Clone the source node */
+ reg->flags = node->flags;
+ reg->process = node->process;
+ reg->init = node->init;
+ reg->fini = node->fini;
+ reg->nb_edges = node->nb_edges;
+ reg->parent_id = node->id;
+
+ for (i = 0; i < node->nb_edges; i++)
+ reg->next_nodes[i] = node->next_nodes[i];
+
+ /* Naming ceremony of the new node. name is node->name + "-" + name */
+ if (clone_name(reg, node, name))
+ goto free;
+
+ rc = __rte_node_register(reg);
+free:
+ free(reg);
+fail:
+ return rc;
+}
+
+rte_node_t
+rte_node_clone(rte_node_t id, const char *name)
+{
+ struct node *node;
+
+ NODE_ID_CHECK(id);
+ STAILQ_FOREACH(node, &node_list, next)
+ if (node->id == id)
+ return node_clone(node, name);
+
+fail:
+ return RTE_NODE_ID_INVALID;
+}
+
+rte_node_t
+rte_node_from_name(const char *name)
+{
+ struct node *node;
+
+ STAILQ_FOREACH(node, &node_list, next)
+ if (strncmp(node->name, name, RTE_NODE_NAMESIZE) == 0)
+ return node->id;
+
+ return RTE_NODE_ID_INVALID;
+}
+
+char *
+rte_node_id_to_name(rte_node_t id)
+{
+ struct node *node;
+
+ NODE_ID_CHECK(id);
+ STAILQ_FOREACH(node, &node_list, next)
+ if (node->id == id)
+ return node->name;
+
+fail:
+ return NULL;
+}
+
+rte_edge_t
+rte_node_edge_count(rte_node_t id)
+{
+ struct node *node;
+
+ NODE_ID_CHECK(id);
+ STAILQ_FOREACH(node, &node_list, next)
+ if (node->id == id)
+ return node->nb_edges;
+fail:
+ return RTE_EDGE_ID_INVALID;
+}
+
+static rte_edge_t
+edge_update(struct node *node, struct node *prev, rte_edge_t from,
+ const char **next_nodes, rte_edge_t nb_edges)
+{
+ rte_edge_t i, max_edges, count = 0;
+ struct node *new_node;
+ bool need_realloc;
+ size_t sz;
+
+ if (from == RTE_EDGE_ID_INVALID)
+ from = node->nb_edges;
+
+ /* Don't create hole in next_nodes[] list */
+ if (from > node->nb_edges) {
+ rte_errno = ENOMEM;
+ goto fail;
+ }
+
+ /* Remove me from list */
+ STAILQ_REMOVE(&node_list, node, node, next);
+
+ /* Allocate the storage space for new node if required */
+ max_edges = from + nb_edges;
+ need_realloc = max_edges > node->nb_edges;
+ if (need_realloc) {
+ sz = sizeof(struct node) + (max_edges * RTE_NODE_NAMESIZE);
+ new_node = realloc(node, sz);
+ if (new_node == NULL) {
+ rte_errno = ENOMEM;
+ goto restore;
+ } else {
+ node = new_node;
+ }
+ }
+
+ /* Update the new nodes name */
+ for (i = from; i < max_edges; i++, count++) {
+ if (rte_strscpy(node->next_nodes[i], next_nodes[count],
+ RTE_NODE_NAMESIZE) < 0) {
+ rte_errno = E2BIG;
+ goto restore;
+ }
+ }
+restore:
+ /* Update the linked list to point new node address in prev node */
+ if (prev)
+ STAILQ_INSERT_AFTER(&node_list, prev, node, next);
+ else
+ STAILQ_INSERT_HEAD(&node_list, node, next);
+
+ if (need_realloc)
+ node->nb_edges += max_edges;
+
+fail:
+ return count;
+}
+
+rte_edge_t
+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);
+ graph_spinlock_lock();
+
+ STAILQ_FOREACH(node, &node_list, next) {
+ if (node->id == id) {
+ if (node->nb_edges < size) {
+ rte_errno = E2BIG;
+ goto fail;
+ }
+ node->nb_edges = size;
+ rc = size;
+ break;
+ }
+ }
+
+fail:
+ graph_spinlock_unlock();
+ return rc;
+}
+
+rte_edge_t
+rte_node_edge_update(rte_node_t id, rte_edge_t from, const char **next_nodes,
+ uint16_t nb_edges)
+{
+ rte_edge_t rc = RTE_EDGE_ID_INVALID;
+ struct node *n, *prev;
+
+ NODE_ID_CHECK(id);
+ graph_spinlock_lock();
+
+ prev = NULL;
+ STAILQ_FOREACH(n, &node_list, next) {
+ if (n->id == id) {
+ rc = edge_update(n, prev, from, next_nodes, nb_edges);
+ break;
+ }
+ prev = n;
+ }
+
+ graph_spinlock_unlock();
+fail:
+ return rc;
+}
+
+static rte_node_t
+node_copy_edges(struct node *node, char *next_nodes[])
+{
+ rte_edge_t i;
+
+ for (i = 0; i < node->nb_edges; i++)
+ next_nodes[i] = node->next_nodes[i];
+
+ return i;
+}
+
+rte_node_t
+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);
+ graph_spinlock_lock();
+
+ STAILQ_FOREACH(node, &node_list, next) {
+ if (node->id == id) {
+ if (next_nodes == NULL)
+ rc = sizeof(char *) * node->nb_edges;
+ else
+ rc = node_copy_edges(node, next_nodes);
+ break;
+ }
+ }
+
+ graph_spinlock_unlock();
+fail:
+ return rc;
+}
+
+rte_node_t
+rte_node_max_count(void)
+{
+ return node_id;
+}
@@ -3,5 +3,15 @@ EXPERIMENTAL {
__rte_node_register;
+ rte_node_clone;
+ rte_node_edge_count;
+ rte_node_edge_get;
+ rte_node_edge_shrink;
+ rte_node_edge_update;
+ rte_node_from_name;
+ rte_node_id_to_name;
+ rte_node_list_dump;
+ rte_node_max_count;
+
local: *;
};