March 2023 - gerrit-log - lists.osmocom.org

[S] Change in libosmo-sccp[master]: cosmetic: sccp.h: Fix trailing whitespace
by fixeria 10 Mar '23

10 Mar '23

Attention is currently required from: pespin. fixeria has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31827 ) Change subject: cosmetic: sccp.h: Fix trailing whitespace ...................................................................... Patch Set 1: Code-Review+2 -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31827 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: I6b9cb5acffdf690f65e14dbdda7213b2e75c7ee1 Gerrit-Change-Number: 31827 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: fixeria <vyanitskiy(a)sysmocom.de> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 19:21:11 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[S] Change in libosmo-sccp[master]: sccp_scpc.c: Simplify conn_create()
by fixeria 10 Mar '23

10 Mar '23

Attention is currently required from: pespin. fixeria has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 ) Change subject: sccp_scpc.c: Simplify conn_create() ...................................................................... Patch Set 1: Code-Review+1 -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Iee333fb38d7a37877c37c1de9719a6b67d9e8ed3 Gerrit-Change-Number: 31826 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: dexter <pmaier(a)sysmocom.de> Gerrit-Reviewer: fixeria <vyanitskiy(a)sysmocom.de> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 19:21:02 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[S] Change in libosmo-sccp[master]: Avoid allocating conn_id 0x00FFFFFF
by fixeria 10 Mar '23

10 Mar '23

Attention is currently required from: neels, laforge, pespin, daniel. fixeria has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 ) Change subject: Avoid allocating conn_id 0x00FFFFFF ...................................................................... Patch Set 1: Code-Review+1 -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Ifcf710ef6024286a1cc3473d6ea3f858552b9926 Gerrit-Change-Number: 31825 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: daniel <dwillmann(a)sysmocom.de> Gerrit-Reviewer: dexter <pmaier(a)sysmocom.de> Gerrit-Reviewer: fixeria <vyanitskiy(a)sysmocom.de> Gerrit-Reviewer: laforge <laforge(a)osmocom.org> Gerrit-Reviewer: neels <nhofmeyr(a)sysmocom.de> Gerrit-Attention: neels <nhofmeyr(a)sysmocom.de> Gerrit-Attention: laforge <laforge(a)osmocom.org> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Attention: daniel <dwillmann(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 19:13:01 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[M] Change in libosmo-sccp[master]: Implement sccp_instance->connections as rbtree
by fixeria 10 Mar '23

10 Mar '23

Attention is currently required from: pespin. fixeria has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31828 ) Change subject: Implement sccp_instance->connections as rbtree ...................................................................... Patch Set 1: Code-Review+1 -- 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 <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: fixeria <vyanitskiy(a)sysmocom.de> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 19:12:52 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[M] Change in libosmo-sccp[master]: Implement sccp_instance->connections as rbtree
by pespin 10 Mar '23

10 Mar '23

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 <pespin(a)sysmocom.de> Gerrit-MessageType: newchange

1 0

[S] Change in libosmo-sccp[master]: cosmetic: sccp.h: Fix trailing whitespace
by pespin 10 Mar '23

10 Mar '23

pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31827 ) Change subject: cosmetic: sccp.h: Fix trailing whitespace ...................................................................... cosmetic: sccp.h: Fix trailing whitespace Change-Id: I6b9cb5acffdf690f65e14dbdda7213b2e75c7ee1 --- M include/osmocom/sccp/sccp.h 1 file changed, 10 insertions(+), 1 deletion(-) git pull ssh://gerrit.osmocom.org:29418/libosmo-sccp refs/changes/27/31827/1 diff --git a/include/osmocom/sccp/sccp.h b/include/osmocom/sccp/sccp.h index 9ff1067..fd911da 100644 --- a/include/osmocom/sccp/sccp.h +++ b/include/osmocom/sccp/sccp.h @@ -120,7 +120,7 @@ int sccp_connection_free(struct sccp_connection *connection); /** - * internal.. + * internal.. */ int sccp_connection_force_free(struct sccp_connection *conn); -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31827 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: I6b9cb5acffdf690f65e14dbdda7213b2e75c7ee1 Gerrit-Change-Number: 31827 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-MessageType: newchange

1 0

[S] Change in libosmo-sccp[master]: Avoid allocating conn_id 0x00FFFFFF
by dexter 10 Mar '23

10 Mar '23

Attention is currently required from: neels, laforge, pespin, daniel. dexter has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 ) Change subject: Avoid allocating conn_id 0x00FFFFFF ...................................................................... Patch Set 1: Code-Review+2 -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Ifcf710ef6024286a1cc3473d6ea3f858552b9926 Gerrit-Change-Number: 31825 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: daniel <dwillmann(a)sysmocom.de> Gerrit-Reviewer: dexter <pmaier(a)sysmocom.de> Gerrit-Reviewer: laforge <laforge(a)osmocom.org> Gerrit-Reviewer: neels <nhofmeyr(a)sysmocom.de> Gerrit-Attention: neels <nhofmeyr(a)sysmocom.de> Gerrit-Attention: laforge <laforge(a)osmocom.org> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Attention: daniel <dwillmann(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 15:47:01 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[S] Change in libosmo-sccp[master]: sccp_scpc.c: Simplify conn_create()
by dexter 10 Mar '23

10 Mar '23

Attention is currently required from: pespin. dexter has posted comments on this change. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 ) Change subject: sccp_scpc.c: Simplify conn_create() ...................................................................... Patch Set 1: Code-Review+2 -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Iee333fb38d7a37877c37c1de9719a6b67d9e8ed3 Gerrit-Change-Number: 31826 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: dexter <pmaier(a)sysmocom.de> Gerrit-Attention: pespin <pespin(a)sysmocom.de> Gerrit-Comment-Date: Fri, 10 Mar 2023 15:39:44 +0000 Gerrit-HasComments: No Gerrit-Has-Labels: Yes Gerrit-MessageType: comment

1 0

[S] Change in libosmo-sccp[master]: sccp_scpc.c: Simplify conn_create()
by pespin 10 Mar '23

10 Mar '23

pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 ) Change subject: sccp_scpc.c: Simplify conn_create() ...................................................................... sccp_scpc.c: Simplify conn_create() Drop local variable with no real use, dereference sccp_instance pointer once instead of potentially thousands of times. Change-Id: Iee333fb38d7a37877c37c1de9719a6b67d9e8ed3 --- M src/sccp_scoc.c 1 file changed, 18 insertions(+), 7 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmo-sccp refs/changes/26/31826/1 diff --git a/src/sccp_scoc.c b/src/sccp_scoc.c index 2430462..53cdf78 100644 --- a/src/sccp_scoc.c +++ b/src/sccp_scoc.c @@ -505,7 +505,7 @@ /* Search for next free connection ID and allocate conn */ static struct sccp_connection *conn_create(struct osmo_sccp_user *user) { - uint32_t conn_id; + struct osmo_sccp_instance *sccp = user->inst; /* SUA: RFC3868 sec 3.10.4: * The source reference number is a 4 octet long integer. @@ -520,13 +520,12 @@ */ do { /* Optimized modulo operation (% 0x00FFFFFE) using bitwise AND plus CMP: */ - user->inst->next_id = (user->inst->next_id + 1) & 0x00FFFFFF; - if (OSMO_UNLIKELY(user->inst->next_id == 0x00FFFFFF)) - user->inst->next_id = 0; - conn_id = user->inst->next_id; - } while (conn_find_by_id(user->inst, conn_id)); + sccp->next_id = (sccp->next_id + 1) & 0x00FFFFFF; + if (OSMO_UNLIKELY(sccp->next_id == 0x00FFFFFF)) + sccp->next_id = 0; + } while (conn_find_by_id(sccp, sccp->next_id)); - return conn_create_id(user, conn_id); + return conn_create_id(user, sccp->next_id); } static void conn_opt_data_clear_cache(struct sccp_connection *conn) -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31826 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Iee333fb38d7a37877c37c1de9719a6b67d9e8ed3 Gerrit-Change-Number: 31826 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-MessageType: newchange

1 0

[S] Change in libosmo-sccp[master]: Avoid allocating conn_id 0x00FFFFFF
by pespin 10 Mar '23

10 Mar '23

pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 ) Change subject: Avoid allocating conn_id 0x00FFFFFF ...................................................................... Avoid allocating conn_id 0x00FFFFFF The 0x00FFFFFF source local reference is reserved in M3UA/SCCP, hence avoid allocating a conn_id with that value since later on when reused as a source local reference it would fail to be encoded. Change-Id: Ifcf710ef6024286a1cc3473d6ea3f858552b9926 --- M src/sccp_scoc.c 1 file changed, 28 insertions(+), 3 deletions(-) git pull ssh://gerrit.osmocom.org:29418/libosmo-sccp refs/changes/25/31825/1 diff --git a/src/sccp_scoc.c b/src/sccp_scoc.c index 00e677c..2430462 100644 --- a/src/sccp_scoc.c +++ b/src/sccp_scoc.c @@ -507,10 +507,22 @@ { uint32_t conn_id; + /* SUA: RFC3868 sec 3.10.4: + * The source reference number is a 4 octet long integer. + * This is allocated by the source SUA instance. + * M3UA/SCCP: ITU-T Q.713 sec 3.3: + * The "source local reference" parameter field is a three-octet field containing a + * reference number which is generated and used by the local node to identify the + * connection section after the connection section is set up. + * The coding "all ones" is reserved for future use. + * Hence, as we currently use the connection ID also as local reference, + * let's simply use 24 bit ids to fit all link types (excluding 0x00ffffff). + */ do { - /* modulo 2^24 as we currently use the connection ID also as local - * reference, and that is limited to 24 bits */ - user->inst->next_id = (user->inst->next_id + 1) % (1 << 24); + /* Optimized modulo operation (% 0x00FFFFFE) using bitwise AND plus CMP: */ + user->inst->next_id = (user->inst->next_id + 1) & 0x00FFFFFF; + if (OSMO_UNLIKELY(user->inst->next_id == 0x00FFFFFF)) + user->inst->next_id = 0; conn_id = user->inst->next_id; } while (conn_find_by_id(user->inst, conn_id)); -- To view, visit https://gerrit.osmocom.org/c/libosmo-sccp/+/31825 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: libosmo-sccp Gerrit-Branch: master Gerrit-Change-Id: Ifcf710ef6024286a1cc3473d6ea3f858552b9926 Gerrit-Change-Number: 31825 Gerrit-PatchSet: 1 Gerrit-Owner: pespin <pespin(a)sysmocom.de> Gerrit-MessageType: newchange

1 0