From 993d3f4d9a6cd16ec811937fc6e2eb19280adda9 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Sat, 5 Dec 2020 10:14:49 +0100 Subject: gbproxy: convert nse->bvcs from llist_head to hashtable For the common lookup-by-bvci, this should reduce the computational complexity significantly. Depends: libosmocore.git I8ef73a62fe9846ce45058eb21cf999dd3eed5741 Change-Id: Ic8e9279fd61a3c514fc3203429f36a468f0e81d3 --- src/gbproxy/gb_proxy.c | 19 +++++++++--------- src/gbproxy/gb_proxy_ctrl.c | 13 +++++++----- src/gbproxy/gb_proxy_peer.c | 48 +++++++++++++++++++++++++++------------------ src/gbproxy/gb_proxy_vty.c | 20 +++++++++---------- 4 files changed, 57 insertions(+), 43 deletions(-) (limited to 'src') diff --git a/src/gbproxy/gb_proxy.c b/src/gbproxy/gb_proxy.c index c37b21ad4..4cf7e4195 100644 --- a/src/gbproxy/gb_proxy.c +++ b/src/gbproxy/gb_proxy.c @@ -1184,7 +1184,7 @@ static int gbprox_rx_paging(struct gbproxy_config *cfg, struct msgb *msg, struct struct gbproxy_bvc *bvc; unsigned int n_nses = 0; int errctr = GBPROX_GLOB_CTR_PROTO_ERR_SGSN; - int i; + int i, j; /* FIXME: Handle paging logic to only page each matching NSE */ @@ -1206,7 +1206,7 @@ static int gbprox_rx_paging(struct gbproxy_config *cfg, struct msgb *msg, struct errctr = GBPROX_GLOB_CTR_INV_RAI; /* iterate over all bvcs and dispatch the paging to each matching one */ hash_for_each(cfg->bss_nses, i, nse, list) { - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { if (!memcmp(bvc->ra, TLVP_VAL(tp, BSSGP_IE_ROUTEING_AREA), 6)) { LOGPNSE(nse, LOGL_INFO, "routing to NSE (RAI match)\n"); gbprox_relay2nse(msg, nse, ns_bvci); @@ -1220,7 +1220,7 @@ static int gbprox_rx_paging(struct gbproxy_config *cfg, struct msgb *msg, struct errctr = GBPROX_GLOB_CTR_INV_LAI; /* iterate over all bvcs and dispatch the paging to each matching one */ hash_for_each(cfg->bss_nses, i, nse, list) { - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { if (!memcmp(bvc->ra, TLVP_VAL(tp, BSSGP_IE_LOCATION_AREA), 5)) { LOGPNSE(nse, LOGL_INFO, "routing to NSE (LAI match)\n"); gbprox_relay2nse(msg, nse, ns_bvci); @@ -1233,7 +1233,7 @@ static int gbprox_rx_paging(struct gbproxy_config *cfg, struct msgb *msg, struct } else if (TLVP_PRES_LEN(tp, BSSGP_IE_BSS_AREA_ID, 1)) { /* iterate over all bvcs and dispatch the paging to each matching one */ hash_for_each(cfg->bss_nses, i, nse, list) { - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { LOGPNSE(nse, LOGL_INFO, "routing to NSE (broadcast)\n"); gbprox_relay2nse(msg, nse, ns_bvci); n_nses++; @@ -1265,7 +1265,7 @@ static int rx_reset_from_sgsn(struct gbproxy_config *cfg, struct gbproxy_nse *nse; struct gbproxy_bvc *bvc; uint16_t ptp_bvci; - int i; + int i, j; if (!TLVP_PRES_LEN(tp, BSSGP_IE_BVCI, 2)) { rate_ctr_inc(&cfg->ctrg-> @@ -1295,7 +1295,7 @@ static int rx_reset_from_sgsn(struct gbproxy_config *cfg, * among all the BSS's that we multiplex, it needs to * be relayed */ hash_for_each(cfg->bss_nses, i, nse, list) { - llist_for_each_entry(bvc, &nse->bvcs, list) + hash_for_each(nse->bvcs, j, bvc, list) gbprox_relay2peer(msg, bvc, ns_bvci); } @@ -1624,11 +1624,12 @@ void gbprox_reset(struct gbproxy_config *cfg) { struct gbproxy_nse *nse; struct hlist_node *ntmp; - int i; + int i, j; hash_for_each_safe(cfg->bss_nses, i, ntmp, nse, list) { - struct gbproxy_bvc *bvc, *tmp; - llist_for_each_entry_safe(bvc, tmp, &nse->bvcs, list) + struct gbproxy_bvc *bvc; + struct hlist_node *tmp; + hash_for_each_safe(nse->bvcs, j, tmp, bvc, list) gbproxy_bvc_free(bvc); gbproxy_nse_free(nse); diff --git a/src/gbproxy/gb_proxy_ctrl.c b/src/gbproxy/gb_proxy_ctrl.c index 829041296..157695d26 100644 --- a/src/gbproxy/gb_proxy_ctrl.c +++ b/src/gbproxy/gb_proxy_ctrl.c @@ -85,13 +85,13 @@ static int get_gbproxy_state(struct ctrl_cmd *cmd, void *data) { struct gbproxy_config *cfg = data; struct gbproxy_nse *nse_peer; - int i; + int i, j; cmd->reply = talloc_strdup(cmd, ""); hash_for_each(cfg->bss_nses, i, nse_peer, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse_peer->bvcs, list) { + hash_for_each(nse_peer->bvcs, j, bvc, list) { struct gprs_ra_id raid; gsm48_parse_ra(&raid, bvc->ra); @@ -112,11 +112,14 @@ static int get_num_peers(struct ctrl_cmd *cmd, void *data) { struct gbproxy_config *cfg = data; struct gbproxy_nse *nse_peer; + struct gbproxy_bvc *bvc; uint32_t count = 0; - int i; + int i, j; - hash_for_each(cfg->bss_nses, i, nse_peer, list) - count += llist_count(&nse_peer->bvcs); + hash_for_each(cfg->bss_nses, i, nse_peer, list) { + hash_for_each(nse_peer->bvcs, j, bvc, list) + count++; + } cmd->reply = talloc_strdup(cmd, ""); cmd->reply = talloc_asprintf_append(cmd->reply, "%u", count); diff --git a/src/gbproxy/gb_proxy_peer.c b/src/gbproxy/gb_proxy_peer.c index 00bff2088..f5a4376cc 100644 --- a/src/gbproxy/gb_proxy_peer.c +++ b/src/gbproxy/gb_proxy_peer.c @@ -90,7 +90,7 @@ struct gbproxy_bvc *gbproxy_bvc_by_bvci(struct gbproxy_config *cfg, uint16_t bvc hash_for_each(cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each_possible(nse->bvcs, bvc, list, bvci) { if (bvc->bvci == bvci) return bvc; } @@ -104,9 +104,15 @@ struct gbproxy_bvc *gbproxy_bvc_by_nsei(struct gbproxy_config *cfg, uint16_t nsei) { struct gbproxy_nse *nse = gbproxy_nse_by_nsei(cfg, nsei); + struct gbproxy_bvc *bvc; + int i; + + if (!nse || hash_empty(nse->bvcs)) + return NULL; - if (nse && !llist_empty(&nse->bvcs)) - return llist_first_entry(&nse->bvcs, struct gbproxy_bvc, list); + /* return the first entry we find */ + hash_for_each(nse->bvcs, i, bvc, list) + return bvc; return NULL; } @@ -117,11 +123,11 @@ struct gbproxy_bvc *gbproxy_bvc_by_rai(struct gbproxy_config *cfg, const uint8_t *ra) { struct gbproxy_nse *nse; - int i; + int i, j; hash_for_each(cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { if (!memcmp(bvc->ra, ra, 6)) return bvc; } @@ -136,11 +142,11 @@ struct gbproxy_bvc *gbproxy_bvc_by_lai(struct gbproxy_config *cfg, const uint8_t *la) { struct gbproxy_nse *nse; - int i; + int i, j; hash_for_each(cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { if (!memcmp(bvc->ra, la, 5)) return bvc; } @@ -154,11 +160,11 @@ struct gbproxy_bvc *gbproxy_bvc_by_lac(struct gbproxy_config *cfg, const uint8_t *la) { struct gbproxy_nse *nse; - int i; + int i, j; hash_for_each(cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { if (!memcmp(bvc->ra + 3, la + 3, 2)) return bvc; } @@ -232,7 +238,7 @@ struct gbproxy_bvc *gbproxy_bvc_alloc(struct gbproxy_nse *nse, uint16_t bvci) } bvc->nse = nse; - llist_add(&bvc->list, &nse->bvcs); + hash_add(nse->bvcs, &bvc->list, bvc->bvci); INIT_LLIST_HEAD(&bvc->patch_state.logical_links); @@ -249,7 +255,7 @@ void gbproxy_bvc_free(struct gbproxy_bvc *bvc) if (!bvc) return; - llist_del(&bvc->list); + hash_del(&bvc->list); osmo_timer_del(&bvc->clean_stale_timer); gbproxy_delete_link_infos(bvc); @@ -261,8 +267,8 @@ void gbproxy_bvc_free(struct gbproxy_bvc *bvc) void gbproxy_bvc_move(struct gbproxy_bvc *bvc, struct gbproxy_nse *nse) { - llist_del(&bvc->list); - llist_add(&bvc->list, &nse->bvcs); + hash_del(&bvc->list); + hash_add(nse->bvcs, &bvc->list, bvc->bvci); bvc->nse = nse; } @@ -272,16 +278,17 @@ void gbproxy_bvc_move(struct gbproxy_bvc *bvc, struct gbproxy_nse *nse) * \param[in] bvci if 0: remove all BVCs; if != 0: BVCI of the single BVC to clean up */ int gbproxy_cleanup_bvcs(struct gbproxy_config *cfg, uint16_t nsei, uint16_t bvci) { - int i, counter = 0; + int i, j, counter = 0; struct gbproxy_nse *nse; struct hlist_node *ntmp; OSMO_ASSERT(cfg); hash_for_each_safe(cfg->bss_nses, i, ntmp, nse, list) { - struct gbproxy_bvc *bvc, *tmp; + struct gbproxy_bvc *bvc; + struct hlist_node *btmp; if (nse->nsei != nsei) continue; - llist_for_each_entry_safe(bvc, tmp, &nse->bvcs, list) { + hash_for_each_safe(nse->bvcs, j, btmp, bvc, list) { if (bvci && bvc->bvci != bvci) continue; @@ -307,20 +314,23 @@ struct gbproxy_nse *gbproxy_nse_alloc(struct gbproxy_config *cfg, uint16_t nsei) hash_add(cfg->bss_nses, &nse->list, nsei); - INIT_LLIST_HEAD(&nse->bvcs); + hash_init(nse->bvcs); return nse; } void gbproxy_nse_free(struct gbproxy_nse *nse) { - struct gbproxy_bvc *bvc, *tmp; + struct gbproxy_bvc *bvc; + struct hlist_node *tmp; + int i; + if (!nse) return; hash_del(&nse->list); - llist_for_each_entry_safe(bvc, tmp, &nse->bvcs, list) + hash_for_each_safe(nse->bvcs, i, tmp, bvc, list) gbproxy_bvc_free(bvc); talloc_free(nse); diff --git a/src/gbproxy/gb_proxy_vty.c b/src/gbproxy/gb_proxy_vty.c index da8afdc19..47ac9b9a2 100644 --- a/src/gbproxy/gb_proxy_vty.c +++ b/src/gbproxy/gb_proxy_vty.c @@ -422,7 +422,7 @@ DEFUN(cfg_gbproxy_link_list_clean_stale_timer, "Frequency at which the periodic timer is fired (in seconds)\n") { struct gbproxy_nse *nse; - int i; + int i, j; g_cfg->clean_stale_timer_freq = (unsigned int) atoi(argv[0]); /* Re-schedule running timers soon in case prev frequency was really big @@ -431,7 +431,7 @@ DEFUN(cfg_gbproxy_link_list_clean_stale_timer, the same time */ hash_for_each(g_cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) + hash_for_each(nse->bvcs, j, bvc, list) osmo_timer_schedule(&bvc->clean_stale_timer, random() % 5, random() % 1000000); } @@ -446,12 +446,12 @@ DEFUN(cfg_gbproxy_link_list_no_clean_stale_timer, { struct gbproxy_nse *nse; - int i; + int i, j; g_cfg->clean_stale_timer_freq = 0; hash_for_each(g_cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) + hash_for_each(nse->bvcs, j, bvc, list) osmo_timer_del(&bvc->clean_stale_timer); } @@ -582,14 +582,14 @@ DEFUN(show_gbproxy, show_gbproxy_cmd, "show gbproxy [stats]", { struct gbproxy_nse *nse; int show_stats = argc >= 1; - int i; + int i, j; if (show_stats) vty_out_rate_ctr_group(vty, "", g_cfg->ctrg); hash_for_each(g_cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { gbprox_vty_print_bvc(vty, bvc); if (show_stats) @@ -605,14 +605,14 @@ DEFUN(show_gbproxy_links, show_gbproxy_links_cmd, "show gbproxy links", struct gbproxy_nse *nse; time_t now; struct timespec ts = {0,}; - int i; + int i, j; osmo_clock_gettime(CLOCK_MONOTONIC, &ts); now = ts.tv_sec; hash_for_each(g_cfg->bss_nses, i, nse, list) { struct gbproxy_bvc *bvc; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { struct gbproxy_link_info *link_info; struct gbproxy_patch_state *state = &bvc->patch_state; @@ -707,12 +707,12 @@ DEFUN(delete_gb_nsei, delete_gb_nsei_cmd, } else { struct gbproxy_nse *nse; struct gbproxy_bvc *bvc; - int i; + int i, j; counter = 0; hash_for_each(g_cfg->bss_nses, i, nse, list) { if (nse->nsei != nsei) continue; - llist_for_each_entry(bvc, &nse->bvcs, list) { + hash_for_each(nse->bvcs, j, bvc, list) { vty_out(vty, "BVC: "); gbprox_vty_print_bvc(vty, bvc); counter += 1; -- cgit v1.2.3