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 submitted this change. ( 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
M tests/gbproxy/gbproxy_test.c
M tests/gbproxy/gbproxy_test.ok
7 files changed, 79 insertions(+), 64 deletions(-)
Approvals:
Jenkins Builder: Verified
laforge: Looks good to me, approved
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..4cf7e41 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);
}
@@ -1624,11 +1624,12 @@
{
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 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;
diff --git a/tests/gbproxy/gbproxy_test.c b/tests/gbproxy/gbproxy_test.c
index bd5c8b5..c47bb34 100644
--- a/tests/gbproxy/gbproxy_test.c
+++ b/tests/gbproxy/gbproxy_test.c
@@ -131,7 +131,8 @@
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 fbd5366..978d91f 100644
--- a/tests/gbproxy/gbproxy_test.ok
+++ b/tests/gbproxy/gbproxy_test.ok
@@ -116,10 +116,10 @@
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 @@
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 @@
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 @@
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 @@
[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 @@
[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 @@
[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 @@
[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 @@
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
--
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: 2
Gerrit-Owner: laforge <laforge at osmocom.org>
Gerrit-Reviewer: Jenkins Builder
Gerrit-Reviewer: laforge <laforge at osmocom.org>
Gerrit-MessageType: merged
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osmocom.org/pipermail/gerrit-log/attachments/20201207/b8f8e5ce/attachment.htm>