diff options
| author | Pau Espin Pedrol <pespin@sysmocom.de> | 2023-03-13 17:57:42 +0100 |
|---|---|---|
| committer | Pau Espin Pedrol <pespin@sysmocom.de> | 2023-03-15 10:45:13 +0100 |
| commit | a4fd6d937151c2f321533d20f78c052caa9b6bf1 (patch) | |
| tree | eb896a31184a91161115ad8214399d9322f815ae /include | |
| parent | 08a7db6cd3c9b09bc566c7536d2b73972d8679a8 (diff) | |
bsc_subscriber: Optimize lookup of bsub by TMSI
It was found that on a busy osmo-bsc process (>1000 concurrent calls
spead over different BTSs), a good amount of time is spent iterating the
subscribers list trying to find a subscriber based on a TMSI (1.60% of
total CPU time used by osmo-bsc).
This patch introduces a new rbtree under struct bsc_subscr_store which
allows storing all the busbs ordered by TMSI.
This way, lookup time changes O(N) -> O(log(N)), at the expense of
increased insert/deletion time O(1) -> O(log(N)).
Related: SYS#6200
Change-Id: If27429e715ef4b327177e427249e68321a6e83cc
Diffstat (limited to 'include')
| -rw-r--r-- | include/osmocom/bsc/bsc_subscriber.h | 6 |
1 files changed, 6 insertions, 0 deletions
diff --git a/include/osmocom/bsc/bsc_subscriber.h b/include/osmocom/bsc/bsc_subscriber.h index 7ec457bf4..1fa00162d 100644 --- a/include/osmocom/bsc/bsc_subscriber.h +++ b/include/osmocom/bsc/bsc_subscriber.h @@ -5,6 +5,7 @@ #include <stdint.h> #include <osmocom/core/linuxlist.h> +#include <osmocom/core/linuxrbtree.h> #include <osmocom/core/use_count.h> #include <osmocom/gsm/protocol/gsm_23_003.h> #include <osmocom/gsm/gsm48.h> @@ -14,6 +15,8 @@ struct gsm_bts; struct bsc_subscr_store { struct llist_head bsub_list; /* list containing "struct bsc_subscr" */ + /* rbtree root of 'struct bsc_subscr', ordered by tmsi */ + struct rb_root bsub_tree_tmsi; }; struct bsc_subscr_store *bsc_subscr_store_alloc(void *ctx); @@ -21,6 +24,8 @@ struct bsc_subscr_store *bsc_subscr_store_alloc(void *ctx); struct bsc_subscr { struct bsc_subscr_store *store; /* backpointer to "struct bsc_subscr_store" */ struct llist_head entry; /* entry in (struct bsc_subscr_store)->bsub_list */ + /* entry in (struct bsc_subscr_store)->bsub_tree_tmsi. Inserted if tmsi != GSM_RESERVED_TMSI: */ + struct rb_node node_tmsi; struct osmo_use_count use_count; char imsi[GSM23003_IMSI_MAX_DIGITS+1]; @@ -49,6 +54,7 @@ struct bsc_subscr *bsc_subscr_find_by_imsi(struct bsc_subscr_store *bsubst, const char *imsi, const char *use_token); +int bsc_subscr_set_tmsi(struct bsc_subscr *bsub, uint32_t tmsi); void bsc_subscr_set_imsi(struct bsc_subscr *bsub, const char *imsi); void bsc_subscr_set_imei(struct bsc_subscr *bsub, const char *imei); |