This is merely a historical archive of years 2008-2021, before the migration to mailman3.
A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/gerrit-log@lists.osmocom.org/.
laforge gerrit-no-reply at lists.osmocom.orglaforge has uploaded this change for review. ( https://gerrit.osmocom.org/c/osmo-sgsn/+/21551 ) Change subject: gbproxy: convert nse->bvcs from llist_head to hashtable ...................................................................... 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 --- M include/osmocom/sgsn/gb_proxy.h M src/gbproxy/gb_proxy.c M src/gbproxy/gb_proxy_ctrl.c M src/gbproxy/gb_proxy_peer.c M src/gbproxy/gb_proxy_vty.c 5 files changed, 58 insertions(+), 44 deletions(-) git pull ssh://gerrit.osmocom.org:29418/osmo-sgsn refs/changes/51/21551/1 diff --git a/include/osmocom/sgsn/gb_proxy.h b/include/osmocom/sgsn/gb_proxy.h index b0ab83d..95a3331 100644 --- a/include/osmocom/sgsn/gb_proxy.h +++ b/include/osmocom/sgsn/gb_proxy.h @@ -150,7 +150,7 @@ /* 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 @@ 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 c37b21a..ef2273d 100644 --- a/src/gbproxy/gb_proxy.c +++ b/src/gbproxy/gb_proxy.c @@ -1184,7 +1184,7 @@ 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 @@ 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 @@ 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 @@ } 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 @@ 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 @@ * 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); } @@ -1627,8 +1627,9 @@ int i; 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, i, 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 8290412..157695d 100644 --- a/src/gbproxy/gb_proxy_ctrl.c +++ b/src/gbproxy/gb_proxy_ctrl.c @@ -85,13 +85,13 @@ { 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 @@ { 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 00bff20..f5a4376 100644 --- a/src/gbproxy/gb_proxy_peer.c +++ b/src/gbproxy/gb_proxy_peer.c @@ -90,7 +90,7 @@ 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 @@ uint16_t nsei) { struct gbproxy_nse *nse = gbproxy_nse_by_nsei(cfg, nsei); + struct gbproxy_bvc *bvc; + int i; - if (nse && !llist_empty(&nse->bvcs)) - return llist_first_entry(&nse->bvcs, struct gbproxy_bvc, list); + if (!nse || hash_empty(nse->bvcs)) + return NULL; + + /* return the first entry we find */ + hash_for_each(nse->bvcs, i, bvc, list) + return bvc; return NULL; } @@ -117,11 +123,11 @@ 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 @@ 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 @@ 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 @@ } 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 @@ 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_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 @@ * \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 @@ 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 da8afdc..47ac9b9 100644 --- a/src/gbproxy/gb_proxy_vty.c +++ b/src/gbproxy/gb_proxy_vty.c @@ -422,7 +422,7 @@ "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 @@ 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 @@ { 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 @@ { 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 @@ 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 @@ } 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; -- To view, visit https://gerrit.osmocom.org/c/osmo-sgsn/+/21551 To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings Gerrit-Project: osmo-sgsn Gerrit-Branch: master Gerrit-Change-Id: Ic8e9279fd61a3c514fc3203429f36a468f0e81d3 Gerrit-Change-Number: 21551 Gerrit-PatchSet: 1 Gerrit-Owner: laforge <laforge at osmocom.org> Gerrit-MessageType: newchange -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.osmocom.org/pipermail/gerrit-log/attachments/20201205/af645229/attachment.htm>