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 --- include/osmocom/sgsn/gb_proxy.h | 4 ++-- 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 ++++++++--------- tests/gbproxy/gbproxy_test.c | 3 ++- tests/gbproxy/gbproxy_test.ok | 36 +++++++++++++++---------------- 7 files changed, 79 insertions(+), 64 deletions(-) diff --git a/include/osmocom/sgsn/gb_proxy.h b/include/osmocom/sgsn/gb_proxy.h index b0ab83d7c..95a3331ab 100644 --- a/include/osmocom/sgsn/gb_proxy.h +++ b/include/osmocom/sgsn/gb_proxy.h @@ -150,7 +150,7 @@ struct gbproxy_patch_state { /* One BVC inside an NSE */ struct gbproxy_bvc { /* linked to gbproxy_nse.bvcs */ - struct llist_head list; + struct hlist_node list; /* The NSE this BVC belongs to */ struct gbproxy_nse *nse; @@ -186,7 +186,7 @@ struct gbproxy_nse { uint16_t nsei; /* List of all BVCs in this NSE */ - struct llist_head bvcs; + DECLARE_HASHTABLE(bvcs, 10); }; struct gbproxy_tlli_state { 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; diff --git a/tests/gbproxy/gbproxy_test.c b/tests/gbproxy/gbproxy_test.c index bd5c8b531..c47bb34fe 100644 --- a/tests/gbproxy/gbproxy_test.c +++ b/tests/gbproxy/gbproxy_test.c @@ -131,7 +131,8 @@ static int dump_peers(FILE *stream, int indent, time_t now, hash_for_each(cfg->bss_nses, _nse, nse, list) { struct gbproxy_bvc *peer; - llist_for_each_entry(peer, &nse->bvcs, list) { + int _peer; + hash_for_each(nse->bvcs, _peer, peer, list) { struct gbproxy_link_info *link_info; struct gbproxy_patch_state *state = &peer->patch_state; gsm48_parse_ra(&raid, peer->ra); diff --git a/tests/gbproxy/gbproxy_test.ok b/tests/gbproxy/gbproxy_test.ok index fbd5366b0..978d91fad 100644 --- a/tests/gbproxy/gbproxy_test.ok +++ b/tests/gbproxy/gbproxy_test.ok @@ -116,10 +116,10 @@ Message for SGSN (NSEI=256 BVCI=0): Peers: NSEI 8192, BVCI 8194, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 - NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 + NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 PROCESSING BVC_RESET_ACK from NSEI 256 23 04 82 10 12 @@ -151,10 +151,10 @@ Message for SGSN (NSEI=256 BVCI=0): Peers: NSEI 8192, BVCI 8194, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 - NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 + NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 PROCESSING BVC_RESET_ACK from NSEI 256 23 04 82 10 02 @@ -186,10 +186,10 @@ Message for SGSN (NSEI=256 BVCI=0): Peers: NSEI 8192, BVCI 8194, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 - NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 + NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 PROCESSING BVC_RESET_ACK from NSEI 256 23 04 82 10 02 @@ -306,10 +306,10 @@ Peers: NSEI 8192, BVCI 8194, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 - NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 + NSEI 4096, BVCI 4114, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 Gbproxy global: PROCESSING BVC_RESET_ACK from NSEI 256 23 04 82 10 02 @@ -453,10 +453,10 @@ Message for BSS (NSEI=4096 BVCI=0): [L2]> [L3]> 23 04 82 20 02 Peers: - NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 4096, BVCI 4098, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 + NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 --- Send message from BSS 1 to SGSN and back, BVCI 1 --- PROCESSING (null) from NSEI 4096 @@ -587,11 +587,11 @@ Message for BSS (NSEI=8192 BVCI=0): [L2]> [L3]> 23 04 82 30 02 Peers: - NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 8192, BVCI 4098, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 + NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 TLLI-Cache: 0 --- Send message from BSS 1 to SGSN and back, BVCI 1 --- @@ -635,11 +635,11 @@ Message for SGSN (NSEI=256 BVCI=8194): [L2]> [L3]> Peers: - NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 8192, BVCI 4098, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 + NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 @@ -656,11 +656,11 @@ Message for BSS (NSEI=4096 BVCI=8194): [L2]> [L3]> Peers: - NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 - TLLI-Cache: 0 NSEI 8192, BVCI 4098, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 + NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 + TLLI-Cache: 0 NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 @@ -692,10 +692,10 @@ Message for BSS (NSEI=8192 BVCI=12290): Gbproxy global: Peers: - NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 + NSEI 8192, BVCI 4098, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 - NSEI 8192, BVCI 4098, not blocked, RAI 112-332-16464-96 + NSEI 8192, BVCI 12290, not blocked, RAI 112-332-16464-96 NSEI mismatch : 1 TLLI-Cache: 0 NSEI 4096, BVCI 8194, not blocked, RAI 112-332-16464-96 -- cgit v1.2.3