neels has submitted this change. ( 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 by cell id. 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. Also improves lookups for HNBAP HNB* operations (rare). A follow-up patch uses a better hash function from libosmocore (jhash.h). Related: SYS#6773 Change-Id: Iecb81eba28263ecf90a09c108995f6fb6f5f81f2 --- M include/osmocom/hnbgw/hnbgw.h M src/osmo-hnbgw/hnbgw.c 2 files changed, 62 insertions(+), 3 deletions(-) Approvals: Jenkins Builder: Verified neels: Looks good to me, approved diff --git a/include/osmocom/hnbgw/hnbgw.h b/include/osmocom/hnbgw/hnbgw.h index 3c0d4bc..666088c 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; @@ -453,8 +456,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 0a9242a..43162fc 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_add(hnbp); @@ -558,12 +585,11 @@ 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; } - return NULL; } @@ -639,6 +665,7 @@ nft_kpi_hnb_persistent_remove(hnbp); rate_ctr_group_free(hnbp->ctrs); llist_del(&hnbp->list); + hash_del(&hnbp->node_by_id); talloc_free(hnbp); } @@ -998,7 +1025,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); -- To view, visit https://gerrit.osmocom.org/c/osmo-hnbgw/+/36889?usp=email To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: osmo-hnbgw Gerrit-Branch: master Gerrit-Change-Id: Iecb81eba28263ecf90a09c108995f6fb6f5f81f2 Gerrit-Change-Number: 36889 Gerrit-PatchSet: 6 Gerrit-Owner: neels &lt;nhofmeyr(a)sysmocom.de&gt; Gerrit-Reviewer: Jenkins Builder Gerrit-Reviewer: laforge &lt;laforge(a)osmocom.org&gt; Gerrit-Reviewer: neels &lt;nhofmeyr(a)sysmocom.de&gt; Gerrit-Reviewer: pespin &lt;pespin(a)sysmocom.de&gt; Gerrit-MessageType: merged