pespin has uploaded this change for review.
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 change 31828. To unsubscribe, or for help writing mail filters, visit settings.