neels has uploaded this change for review. ( https://gerrit.osmocom.org/c/osmo-hnbgw/+/36889?usp=email )

Change subject: add hnb_persistent hashtable: optimize lookup by cell id ......................................................................

add hnb_persistent hashtable: optimize lookup by cell id

Mainly the new nft counters do a lot of hnb_persistent lookups.

Add a hashtable to optimize looking up hnb_persistent instances. So far we iterate the linear list of hnb_persistent for each and every counter returned from nft_kpi.c, and also for every HNBAP HNB* operation.

Related: SYS#6773 Change-Id: Iecb81eba28263ecf90a09c108995f6fb6f5f81f2 --- M include/osmocom/hnbgw/hnbgw.h M src/osmo-hnbgw/hnbgw.c 2 files changed, 56 insertions(+), 2 deletions(-)

git pull ssh://gerrit.osmocom.org:29418/osmo-hnbgw refs/changes/89/36889/1

diff --git a/include/osmocom/hnbgw/hnbgw.h b/include/osmocom/hnbgw/hnbgw.h index 46506ca..edfd496 100644 --- a/include/osmocom/hnbgw/hnbgw.h +++ b/include/osmocom/hnbgw/hnbgw.h @@ -175,6 +175,7 @@ }; const char *umts_cell_id_name(const struct umts_cell_id *ucid); int umts_cell_id_from_str(struct umts_cell_id *ucid, const char *instr); +uint32_t umts_cell_id_hash(const struct umts_cell_id *ucid);

/*! are both given umts_cell_id euqal? */ static inline bool umts_cell_id_equal(const struct umts_cell_id *a, const struct umts_cell_id *b) @@ -367,6 +368,8 @@ struct hnb_persistent { /*! Entry in HNBGW-global list of hnb_persistent */ struct llist_head list; + /*! Entry in hash table g_hnbgw->hnb_persistent_by_id. */ + struct hlist_node node_by_id; /*! back-pointer to hnb_context. Can be NULL if no context at this point */ struct hnb_context *ctx;

@@ -451,8 +454,12 @@ struct osmo_stream_srv_link *iuh; /* list of struct hnb_context */ struct llist_head hnb_list; + /* list of struct hnb_persistent */ struct llist_head hnb_persistent_list; + /* optimized lookup for hnb_persistent, by cell id string */ + DECLARE_HASHTABLE(hnb_persistent_by_id, 5); + struct osmo_timer_list store_uptime_timer; /* list of struct ue_context */ struct llist_head ue_list; diff --git a/src/osmo-hnbgw/hnbgw.c b/src/osmo-hnbgw/hnbgw.c index f14ee13..5bd4c80 100644 --- a/src/osmo-hnbgw/hnbgw.c +++ b/src/osmo-hnbgw/hnbgw.c @@ -242,6 +242,32 @@ ucid->sac, ucid->cid); }

+/* source: http://www.cse.yorku.ca/~oz/hash.html */ +static inline void mkhash_init(uint32_t *hash) +{ + *hash = 5381; +} +static inline void mkhash_add(uint32_t *hash, int32_t val) +{ + uint32_t h = *hash; + h = ((h << 5) + h) ^ val; /* (h * 33) ^ val */ + *hash = h; +} + +/* Useful to index a hash table by struct umts_cell_id. */ +uint32_t umts_cell_id_hash(const struct umts_cell_id *ucid) +{ + uint32_t hash; + mkhash_init(&hash); + mkhash_add(&hash, ucid->mcc); + mkhash_add(&hash, ucid->mnc); + mkhash_add(&hash, ucid->lac); + mkhash_add(&hash, ucid->rac); + mkhash_add(&hash, ucid->sac); + mkhash_add(&hash, ucid->cid); + return hash; +} + /* parse a string representation of an umts_cell_id into its decoded representation */ int umts_cell_id_from_str(struct umts_cell_id *ucid, const char *instr) { @@ -542,6 +568,7 @@ osmo_stat_item_group_set_name(hnbp->statg, hnbp->id_str);

llist_add(&hnbp->list, &g_hnbgw->hnb_persistent_list); + hash_add(g_hnbgw->hnb_persistent_by_id, &hnbp->node_by_id, umts_cell_id_hash(&hnbp->id));

if (g_hnbgw->nft_kpi.active) nft_kpi_hnb_persistent_init(hnbp); @@ -558,8 +585,8 @@ struct hnb_persistent *hnb_persistent_find_by_id(const struct umts_cell_id *id) { struct hnb_persistent *hnbp; - - llist_for_each_entry(hnbp, &g_hnbgw->hnb_persistent_list, list) { + uint32_t id_hash = umts_cell_id_hash(id); + hash_for_each_possible(g_hnbgw->hnb_persistent_by_id, hnbp, node_by_id, id_hash) { if (umts_cell_id_equal(&hnbp->id, id)) return hnbp; } @@ -635,6 +662,7 @@ nft_kpi_hnb_stop(hnbp); nft_kpi_hnb_persistent_remove(hnbp); llist_del(&hnbp->list); + hash_del(&hnbp->node_by_id); talloc_free(hnbp); }

@@ -994,7 +1022,10 @@

g_hnbgw->next_ue_ctx_id = 23; INIT_LLIST_HEAD(&g_hnbgw->hnb_list); + INIT_LLIST_HEAD(&g_hnbgw->hnb_persistent_list); + hash_init(g_hnbgw->hnb_persistent_by_id); + INIT_LLIST_HEAD(&g_hnbgw->ue_list); INIT_LLIST_HEAD(&g_hnbgw->sccp.users);