[M] Change in libosmo-sccp[master]: Implement sccp_instance->connections as rbtree

pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31828 ) Change subject: Implement sccp_instance->connections as rbtree ...................................................................... Implement sccp_instance->connections as rbtree As a result we move from: INSERT=O(1) SEARCH=O(n) REMOVE=O(1) to: INSERT=O(log(N)) SEARCH=O(log(N)) REMOVE=O(log(N)) So we get rid of O(n) complexity every time we need to find a conn object based on conn_id. When a big number of SCCP conns is handled, this saves a lot of CPU time every time a conn needs to be looked up, for instance each time a message is received. For instance, given 1500 SCCP conns, searching is ~10 steps while it took 1500 steps beforehand. Morever, since when creating a new conn_id the code looks if it exists prior to it, that means in practice inserting used to took O(n), while now it takes O(log(N)). Change-Id: I28ac67038207e2fad89ea291629cec5b2f912461 --- M src/sccp_internal.h M src/sccp_scoc.c M src/sccp_user.c 3 files changed, 83 insertions(+), 14 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmo-sccp refs/changes/28/31828/1 diff --git a/src/sccp_internal.h b/src/sccp_internal.h index 23b3ef3..bfdca34 100644 --- a/src/sccp_internal.h +++ b/src/sccp_internal.h @@ -2,6 +2,8 @@ #include <osmocom/core/fsm.h> #include <osmocom/core/prim.h> +#include <osmocom/core/linuxlist.h> +#include <osmocom/core/linuxrbtree.h> #include <osmocom/sigtran/sccp_sap.h> #include <osmocom/sigtran/osmo_ss7.h> #include <osmocom/sigtran/protocol/mtp.h> @@ -42,8 +44,8 @@ struct osmo_sccp_instance { /* entry in global list of ss7 instances */ struct llist_head list; - /* list of 'struct sccp_connection' in this instance */ - struct llist_head connections; + /* rbtree root of 'struct sccp_connection' in this instance */ + struct rb_root connections; /* list of SCCP users in this instance */ struct llist_head users; /* routing context to be used in all outbound messages */ diff --git a/src/sccp_scoc.c b/src/sccp_scoc.c index 53cdf78..db1db23 100644 --- a/src/sccp_scoc.c +++ b/src/sccp_scoc.c @@ -52,6 +52,7 @@ #include <osmocom/core/msgb.h> #include <osmocom/core/utils.h> #include <osmocom/core/linuxlist.h> +#include <osmocom/core/linuxrbtree.h> #include <osmocom/core/logging.h> #include <osmocom/core/timer.h> #include <osmocom/core/fsm.h> @@ -72,8 +73,8 @@ /* a logical connection within the SCCP instance */ struct sccp_connection { - /* part of osmo_sccp_instance.list */ - struct llist_head list; + /* entry in (struct sccp_instance)->connections */ + struct rb_node node; /* which instance are we part of? */ struct osmo_sccp_instance *inst; /* which user owns us? */ @@ -452,14 +453,47 @@ static struct sccp_connection *conn_find_by_id(const struct osmo_sccp_instance *inst, uint32_t id) { struct sccp_connection *conn; + const struct rb_node *node = inst->connections.rb_node; - llist_for_each_entry(conn, &inst->connections, list) { - if (conn->conn_id == id) + while (node) { + conn = container_of(node, struct sccp_connection, node); + if (id < conn->conn_id) + node = node->rb_left; + else if (id > conn->conn_id) + node = node->rb_right; + else return conn; } return NULL; } +static int conn_add_node(struct osmo_sccp_instance *inst, struct sccp_connection *conn) +{ + struct rb_node **n = &(inst->connections.rb_node); + struct rb_node *parent = NULL; + + while (*n) { + struct sccp_connection *it; + + it = container_of(*n, struct sccp_connection, node); + + parent = *n; + if (conn->conn_id < it->conn_id) { + n = &((*n)->rb_left); + } else if (conn->conn_id > it->conn_id) { + n = &((*n)->rb_right); + } else { + LOGP(DLSCCP, LOGL_ERROR, + "Trying to reserve already reserved conn_id %u\n", conn->conn_id); + return -EEXIST; + } + } + + rb_link_node(&conn->node, parent, n); + rb_insert_color(&conn->node, &inst->connections); + return 0; +} + bool osmo_sccp_conn_id_exists(const struct osmo_sccp_instance *inst, uint32_t id) { return conn_find_by_id(inst, id) ? true : false; @@ -477,7 +511,10 @@ conn->inst = user->inst; conn->user = user; - llist_add_tail(&conn->list, &user->inst->connections); + if (conn_add_node(user->inst, conn) < 0) { + talloc_free(conn); + return NULL; + } INIT_TIMER(&conn->t_conn, conn_tmr_cb, conn); INIT_TIMER(&conn->t_ias, tx_inact_tmr_cb, conn); @@ -494,7 +531,7 @@ conn->fi = osmo_fsm_inst_alloc(&sccp_scoc_fsm, conn, conn, LOGL_DEBUG, name); if (!conn->fi) { - llist_del(&conn->list); + rb_erase(&conn->node, &user->inst->connections); talloc_free(conn); return NULL; } @@ -545,7 +582,7 @@ conn_stop_connect_timer(conn); conn_stop_inact_timers(conn); conn_stop_release_timers(conn); - llist_del(&conn->list); + rb_erase(&conn->node, &conn->inst->connections); osmo_fsm_inst_term(conn->fi, OSMO_FSM_TERM_REQUEST, NULL); @@ -1934,10 +1971,12 @@ void sccp_scoc_flush_connections(struct osmo_sccp_instance *inst) { - struct sccp_connection *conn, *conn2; - - llist_for_each_entry_safe(conn, conn2, &inst->connections, list) + struct rb_node *node; + while ((node = rb_first(&inst->connections))) { + struct sccp_connection *conn = container_of(node, struct sccp_connection, node); conn_destroy(conn); + } + } #include <osmocom/vty/vty.h> @@ -1970,11 +2009,14 @@ void sccp_scoc_show_connections(struct vty *vty, struct osmo_sccp_instance *inst) { struct sccp_connection *conn; + struct rb_node *node; vty_out(vty, "I Local Conn. Remote %s", VTY_NEWLINE); vty_out(vty, "O Ref SSN PC State Ref SSN PC %s", VTY_NEWLINE); vty_out(vty, "- ------ --- ------- ---------------- ------ --- -------%s", VTY_NEWLINE); - llist_for_each_entry(conn, &inst->connections, list) + for (node = rb_first(&inst->connections); node; node = rb_next(node)) { + conn = container_of(node, struct sccp_connection, node); vty_show_connection(vty, conn); + } } diff --git a/src/sccp_user.c b/src/sccp_user.c index 839ef64..64e2d31 100644 --- a/src/sccp_user.c +++ b/src/sccp_user.c @@ -229,7 +229,6 @@ inst->ss7 = ss7; inst->priv = priv; - INIT_LLIST_HEAD(&inst->connections); INIT_LLIST_HEAD(&inst->users); inst->ss7_user.inst = ss7; -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31828 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: I28ac67038207e2fad89ea291629cec5b2f912461 Gerrit-Change-Number: 31828 Gerrit-PatchSet: 1 Gerrit-Owner: pespin &lt;pespin(a)sysmocom.de&gt; Gerrit-MessageType: newchange