<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <meta name="Generator" content="Microsoft Word 15 (filtered medium)"> <style></style> </head> <body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word"> <div class="WordSection1"> <o:p> </o:p> <o:p> </o:p> <div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt"> <div> <div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in"> From: Robin Jarry <rjarry@redhat.com> Sent: Tuesday, June 18, 2024 2:53 PM To: dev@dpdk.org; Jerin Jacob <jerinj@marvell.com>; Kiran Kumar Kokkilagadda <kirankumark@marvell.com>; Nithin Kumar Dabilpuram <ndabilpuram@marvell.com>; Zhirun Yan <yanzhirun_163@163.com> Subject: [EXTERNAL] [PATCH v3] graph: avoid id collisions<o:p></o:p> </div> </div> <o:p> </o:p> <div> The graph id is determined based on a global variable that is incremented every time a graph is created, and decremented every time a graph is destroyed. This only works if graphs are destroyed in the reverse order in which they have been created. <o:p></o:p> </div> <div> <o:p></o:p> </div> <div> <pre style="white-space:pre-wrap">The graph id is determined based on a global variable that is<o:p></o:p></pre> <pre>incremented every time a graph is created, and decremented every time<o:p></o:p></pre> <pre>a graph is destroyed. This only works if graphs are destroyed in the<o:p></o:p></pre> <pre>reverse order in which they have been created.<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre>The following code produces duplicate graph IDs which can lead to<o:p></o:p></pre> <pre>use-after-free bugs and other undefined behaviours:<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre> a = rte_graph_create(...); // id=0 graph_id=1<o:p></o:p></pre> <pre> b = rte_graph_create(...); // id=1 graph_id=2<o:p></o:p></pre> <pre> rte_graph_destroy(a); // graph_id=1<o:p></o:p></pre> <pre> c = rte_graph_create(...); // id=1 graph_id=2 (duplicate with b)<o:p></o:p></pre> <pre> rte_graph_destroy(c); // frees memory still used by b<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre>Remove the global counter. Make sure that the graph list is always<o:p></o:p></pre> <pre>ordered by increasing graph ids. When creating a new graph, pick a free<o:p></o:p></pre> <pre>id which is not allocated.<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre>Update unit tests to ensure it works as expected.<o:p></o:p></pre> <pre><o:p> </o:p></pre> <div style="mso-element:para-border-div;border:none;border-bottom:solid windowtext 1.0pt;padding:0in 0in 1.0pt 0in"> <pre style="border:none;padding:0in">Signed-off-by: Robin Jarry <<a href="mailto:rjarry@redhat.com">rjarry@redhat.com</a>><o:p></o:p></pre> </div> <pre><o:p> </o:p></pre> <pre>Acked-by: Kiran Kumar Kokkilagadda <a href="mailto:kirankumark@marvell.com">kirankumark@marvell.com</a><o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre>Notes:<o:p></o:p></pre> <pre> v3:<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> * Fixed invalid logic in graph_insert_ordered.<o:p></o:p></pre> <pre> * Updated unit test to ensure head/tail/middle insertion work (the test<o:p></o:p></pre> <pre> fails before fixing graph_insert_ordered).<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre> app/test/test_graph.c | 72 ++++++++++++++++++++++++++++++++++++<o:p></o:p></pre> <pre> lib/graph/graph.c | 86 ++++++++++++++++++++++++++++++++++---------<o:p></o:p></pre> <pre> 2 files changed, 141 insertions(+), 17 deletions(-)<o:p></o:p></pre> <pre><o:p> </o:p></pre> <pre>diff --git a/app/test/test_graph.c b/app/test/test_graph.c<o:p></o:p></pre> <pre>index b8409bc60497..2840a25b13b7 100644<o:p></o:p></pre> <pre>--- a/app/test/test_graph.c<o:p></o:p></pre> <pre>+++ b/app/test/test_graph.c<o:p></o:p></pre> <pre>@@ -696,6 +696,77 @@ test_graph_clone(void)<o:p></o:p></pre> <pre> return ret;<o:p></o:p></pre> <pre> }<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>+static int<o:p></o:p></pre> <pre>+test_graph_id_collisions(void)<o:p></o:p></pre> <pre>+{<o:p></o:p></pre> <pre>+ static const char *node_patterns[] = {"test_node_source1", "test_node00"};<o:p></o:p></pre> <pre>+ struct rte_graph_param gconf = {<o:p></o:p></pre> <pre>+ .socket_id = SOCKET_ID_ANY,<o:p></o:p></pre> <pre>+ .nb_node_patterns = 2,<o:p></o:p></pre> <pre>+ .node_patterns = node_patterns,<o:p></o:p></pre> <pre>+ };<o:p></o:p></pre> <pre>+ rte_graph_t g1, g2, g3, g4;<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ g1 = rte_graph_create("worker1", &gconf);<o:p></o:p></pre> <pre>+ if (g1 == RTE_GRAPH_ID_INVALID) {<o:p></o:p></pre> <pre>+ printf("Graph 1 creation failed with error = %d\n", rte_errno);<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ g2 = rte_graph_create("worker2", &gconf);<o:p></o:p></pre> <pre>+ if (g2 == RTE_GRAPH_ID_INVALID) {<o:p></o:p></pre> <pre>+ printf("Graph 2 creation failed with error = %d\n", rte_errno);<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ g3 = rte_graph_create("worker3", &gconf);<o:p></o:p></pre> <pre>+ if (g3 == RTE_GRAPH_ID_INVALID) {<o:p></o:p></pre> <pre>+ printf("Graph 3 creation failed with error = %d\n", rte_errno);<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (g1 == g2 || g2 == g3 || g1 == g3) {<o:p></o:p></pre> <pre>+ printf("Graph ids should be different\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (rte_graph_destroy(g2) < 0) {<o:p></o:p></pre> <pre>+ printf("Graph 2 suppression failed\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ g4 = rte_graph_create("worker4", &gconf);<o:p></o:p></pre> <pre>+ if (g4 == RTE_GRAPH_ID_INVALID) {<o:p></o:p></pre> <pre>+ printf("Graph 4 creation failed with error = %d\n", rte_errno);<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (g1 == g3 || g1 == g4 || g3 == g4) {<o:p></o:p></pre> <pre>+ printf("Graph ids should be different\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ g2 = rte_graph_clone(g1, "worker2", &gconf);<o:p></o:p></pre> <pre>+ if (g2 == RTE_GRAPH_ID_INVALID) {<o:p></o:p></pre> <pre>+ printf("Graph 4 creation failed with error = %d\n", rte_errno);<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (g1 == g2 || g1 == g3 || g1 == g4 || g2 == g3 || g2 == g4 || g3 == g4) {<o:p></o:p></pre> <pre>+ printf("Graph ids should be different\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (rte_graph_destroy(g1) < 0) {<o:p></o:p></pre> <pre>+ printf("Graph 1 suppression failed\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (rte_graph_destroy(g2) < 0) {<o:p></o:p></pre> <pre>+ printf("Graph 2 suppression failed\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (rte_graph_destroy(g3) < 0) {<o:p></o:p></pre> <pre>+ printf("Graph 3 suppression failed\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (rte_graph_destroy(g4) < 0) {<o:p></o:p></pre> <pre>+ printf("Graph 4 suppression failed\n");<o:p></o:p></pre> <pre>+ return -1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ return 0;<o:p></o:p></pre> <pre>+}<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre> static int<o:p></o:p></pre> <pre> test_graph_model_mcore_dispatch_node_lcore_affinity_set(void)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre>@@ -977,6 +1048,7 @@ static struct unit_test_suite graph_testsuite = {<o:p></o:p></pre> <pre> TEST_CASE(test_lookup_functions),<o:p></o:p></pre> <pre> TEST_CASE(test_create_graph),<o:p></o:p></pre> <pre> TEST_CASE(test_graph_clone),<o:p></o:p></pre> <pre>+ TEST_CASE(test_graph_id_collisions),<o:p></o:p></pre> <pre> TEST_CASE(test_graph_model_mcore_dispatch_node_lcore_affinity_set),<o:p></o:p></pre> <pre> TEST_CASE(test_graph_model_mcore_dispatch_core_bind_unbind),<o:p></o:p></pre> <pre> TEST_CASE(test_graph_worker_model_set_get),<o:p></o:p></pre> <pre>diff --git a/lib/graph/graph.c b/lib/graph/graph.c<o:p></o:p></pre> <pre>index 147bc6c685c5..d5b8c9f918cf 100644<o:p></o:p></pre> <pre>--- a/lib/graph/graph.c<o:p></o:p></pre> <pre>+++ b/lib/graph/graph.c<o:p></o:p></pre> <pre>@@ -19,11 +19,54 @@<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> static struct graph_head graph_list = STAILQ_HEAD_INITIALIZER(graph_list);<o:p></o:p></pre> <pre> static rte_spinlock_t graph_lock = RTE_SPINLOCK_INITIALIZER;<o:p></o:p></pre> <pre>-static rte_graph_t graph_id;<o:p></o:p></pre> <pre>-<o:p></o:p></pre> <pre>-#define GRAPH_ID_CHECK(id) ID_CHECK(id, graph_id)<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> /* Private functions */<o:p></o:p></pre> <pre>+static struct graph *<o:p></o:p></pre> <pre>+graph_from_id(rte_graph_t id)<o:p></o:p></pre> <pre>+{<o:p></o:p></pre> <pre>+ struct graph *graph;<o:p></o:p></pre> <pre>+ STAILQ_FOREACH(graph, &graph_list, next) {<o:p></o:p></pre> <pre>+ if (graph->id == id)<o:p></o:p></pre> <pre>+ return graph;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ rte_errno = EINVAL;<o:p></o:p></pre> <pre>+ return NULL;<o:p></o:p></pre> <pre>+}<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+static rte_graph_t<o:p></o:p></pre> <pre>+graph_next_free_id(void)<o:p></o:p></pre> <pre>+{<o:p></o:p></pre> <pre>+ struct graph *graph;<o:p></o:p></pre> <pre>+ rte_graph_t id = 0;<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ STAILQ_FOREACH(graph, &graph_list, next) {<o:p></o:p></pre> <pre>+ if (id < graph->id)<o:p></o:p></pre> <pre>+ break;<o:p></o:p></pre> <pre>+ id = graph->id + 1;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ return id;<o:p></o:p></pre> <pre>+}<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+static void<o:p></o:p></pre> <pre>+graph_insert_ordered(struct graph *graph)<o:p></o:p></pre> <pre>+{<o:p></o:p></pre> <pre>+ struct graph *after, *g;<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ after = NULL;<o:p></o:p></pre> <pre>+ STAILQ_FOREACH(g, &graph_list, next) {<o:p></o:p></pre> <pre>+ if (g->id < graph->id)<o:p></o:p></pre> <pre>+ after = g;<o:p></o:p></pre> <pre>+ else if (g->id > graph->id)<o:p></o:p></pre> <pre>+ break;<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+ if (after == NULL) {<o:p></o:p></pre> <pre>+ STAILQ_INSERT_HEAD(&graph_list, graph, next);<o:p></o:p></pre> <pre>+ } else {<o:p></o:p></pre> <pre>+ STAILQ_INSERT_AFTER(&graph_list, after, graph, next);<o:p></o:p></pre> <pre>+ }<o:p></o:p></pre> <pre>+}<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre> struct graph_head *<o:p></o:p></pre> <pre> graph_list_head_get(void)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre>@@ -279,7 +322,8 @@ rte_graph_model_mcore_dispatch_core_bind(rte_graph_t id, int lcore)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre> struct graph *graph;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(id);<o:p></o:p></pre> <pre>+ if (graph_from_id(id) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> if (!rte_lcore_is_enabled(lcore))<o:p></o:p></pre> <pre> SET_ERR_JMP(ENOLINK, fail, "lcore %d not enabled", lcore);<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>@@ -309,7 +353,8 @@ rte_graph_model_mcore_dispatch_core_unbind(rte_graph_t id)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre> struct graph *graph;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(id);<o:p></o:p></pre> <pre>+ if (graph_from_id(id) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> STAILQ_FOREACH(graph, &graph_list, next)<o:p></o:p></pre> <pre> if (graph->id == id)<o:p></o:p></pre> <pre> break;<o:p></o:p></pre> <pre>@@ -406,7 +451,7 @@ rte_graph_create(const char *name, struct rte_graph_param *prm)<o:p></o:p></pre> <pre> graph->socket = prm->socket_id;<o:p></o:p></pre> <pre> graph->src_node_count = src_node_count;<o:p></o:p></pre> <pre> graph->node_count = graph_nodes_count(graph);<o:p></o:p></pre> <pre>- graph->id = graph_id;<o:p></o:p></pre> <pre>+ graph->id = graph_next_free_id();<o:p></o:p></pre> <pre> graph->parent_id = RTE_GRAPH_ID_INVALID;<o:p></o:p></pre> <pre> graph->lcore_id = RTE_MAX_LCORE;<o:p></o:p></pre> <pre> graph->num_pkt_to_capture = prm->num_pkt_to_capture;<o:p></o:p></pre> <pre>@@ -422,8 +467,7 @@ rte_graph_create(const char *name, struct rte_graph_param *prm)<o:p></o:p></pre> <pre> goto graph_mem_destroy;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> /* All good, Lets add the graph to the list */<o:p></o:p></pre> <pre>- graph_id++;<o:p></o:p></pre> <pre>- STAILQ_INSERT_TAIL(&graph_list, graph, next);<o:p></o:p></pre> <pre>+ graph_insert_ordered(graph);<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> graph_spinlock_unlock();<o:p></o:p></pre> <pre> return graph->id;<o:p></o:p></pre> <pre>@@ -467,7 +511,6 @@ rte_graph_destroy(rte_graph_t id)<o:p></o:p></pre> <pre> graph_cleanup(graph);<o:p></o:p></pre> <pre> STAILQ_REMOVE(&graph_list, graph, graph, next);<o:p></o:p></pre> <pre> free(graph);<o:p></o:p></pre> <pre>- graph_id--;<o:p></o:p></pre> <pre> goto done;<o:p></o:p></pre> <pre> }<o:p></o:p></pre> <pre> graph = tmp;<o:p></o:p></pre> <pre>@@ -520,7 +563,7 @@ graph_clone(struct graph *parent_graph, const char *name, struct rte_graph_param<o:p></o:p></pre> <pre> graph->parent_id = parent_graph->id;<o:p></o:p></pre> <pre> graph->lcore_id = parent_graph->lcore_id;<o:p></o:p></pre> <pre> graph->socket = parent_graph->socket;<o:p></o:p></pre> <pre>- graph->id = graph_id;<o:p></o:p></pre> <pre>+ graph->id = graph_next_free_id();<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> /* Allocate the Graph fast path memory and populate the data */<o:p></o:p></pre> <pre> if (graph_fp_mem_create(graph))<o:p></o:p></pre> <pre>@@ -539,8 +582,7 @@ graph_clone(struct graph *parent_graph, const char *name, struct rte_graph_param<o:p></o:p></pre> <pre> goto graph_mem_destroy;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> /* All good, Lets add the graph to the list */<o:p></o:p></pre> <pre>- graph_id++;<o:p></o:p></pre> <pre>- STAILQ_INSERT_TAIL(&graph_list, graph, next);<o:p></o:p></pre> <pre>+ graph_insert_ordered(graph);<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> graph_spinlock_unlock();<o:p></o:p></pre> <pre> return graph->id;<o:p></o:p></pre> <pre>@@ -561,7 +603,8 @@ rte_graph_clone(rte_graph_t id, const char *name, struct rte_graph_param *prm)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre> struct graph *graph;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(id);<o:p></o:p></pre> <pre>+ if (graph_from_id(id) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> STAILQ_FOREACH(graph, &graph_list, next)<o:p></o:p></pre> <pre> if (graph->id == id)<o:p></o:p></pre> <pre> return graph_clone(graph, name, prm);<o:p></o:p></pre> <pre>@@ -587,7 +630,8 @@ rte_graph_id_to_name(rte_graph_t id)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre> struct graph *graph;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(id);<o:p></o:p></pre> <pre>+ if (graph_from_id(id) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> STAILQ_FOREACH(graph, &graph_list, next)<o:p></o:p></pre> <pre> if (graph->id == id)<o:p></o:p></pre> <pre> return graph->name;<o:p></o:p></pre> <pre>@@ -604,7 +648,8 @@ rte_graph_node_get(rte_graph_t gid, uint32_t nid)<o:p></o:p></pre> <pre> rte_graph_off_t off;<o:p></o:p></pre> <pre> rte_node_t count;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(gid);<o:p></o:p></pre> <pre>+ if (graph_from_id(gid) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> STAILQ_FOREACH(graph, &graph_list, next)<o:p></o:p></pre> <pre> if (graph->id == gid) {<o:p></o:p></pre> <pre> rte_graph_foreach_node(count, off, graph->graph,<o:p></o:p></pre> <pre>@@ -747,7 +792,8 @@ graph_scan_dump(FILE *f, rte_graph_t id, bool all)<o:p></o:p></pre> <pre> struct graph *graph;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> RTE_VERIFY(f);<o:p></o:p></pre> <pre>- GRAPH_ID_CHECK(id);<o:p></o:p></pre> <pre>+ if (graph_from_id(id) == NULL)<o:p></o:p></pre> <pre>+ goto fail;<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> STAILQ_FOREACH(graph, &graph_list, next) {<o:p></o:p></pre> <pre> if (all == true) {<o:p></o:p></pre> <pre>@@ -776,7 +822,13 @@ rte_graph_list_dump(FILE *f)<o:p></o:p></pre> <pre> rte_graph_t<o:p></o:p></pre> <pre> rte_graph_max_count(void)<o:p></o:p></pre> <pre> {<o:p></o:p></pre> <pre>- return graph_id;<o:p></o:p></pre> <pre>+ struct graph *graph;<o:p></o:p></pre> <pre>+ rte_graph_t count = 0;<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ STAILQ_FOREACH(graph, &graph_list, next)<o:p></o:p></pre> <pre>+ count++;<o:p></o:p></pre> <pre>+<o:p></o:p></pre> <pre>+ return count;<o:p></o:p></pre> <pre> }<o:p></o:p></pre> <pre> <o:p></o:p></pre> <pre> RTE_LOG_REGISTER_DEFAULT(rte_graph_logtype, INFO);<o:p></o:p></pre> <pre>-- <o:p></o:p></pre> <pre>2.45.2<o:p></o:p></pre> <pre><o:p> </o:p></pre> </div> </div> </div> </body> </html>