pespin has uploaded this change for review. ( https://gerrit.osmocom.org/c/osmo-bsc/+/38050?usp=email ) Change subject: Convert bts->depends_on from bitmask to llist ...................................................................... Convert bts->depends_on from bitmask to llist The amount of dependencies on each BTS is usually zero or a small number, hence the computation cost is mostly similar regardless of using a llist or a bitmask buffer. Right now, even if the dependency chains are (almost) empty, the iprevious code allocated (N * 256/8) bytes, where N is the amount of bts configured. Since we are now planning to increase the amount of bts (N) from uint8_t to uint16_t, that means with this change we will then avoid: * Increasing memory use to O(N * 65536/8). * Having to adapt code operating on bitmask (size) Related: SYS#7062 Change-Id: I59e37d6baa020aeafdffc2c3538e988effd37620 --- M include/osmocom/bsc/bts.h M src/osmo-bsc/bts.c M src/osmo-bsc/bts_vty.c 3 files changed, 45 insertions(+), 45 deletions(-) git pull ssh://gerrit.osmocom.org:29418/osmo-bsc refs/changes/50/38050/1 diff --git a/include/osmocom/bsc/bts.h b/include/osmocom/bsc/bts.h index e9634ee..112c17c 100644 --- a/include/osmocom/bsc/bts.h +++ b/include/osmocom/bsc/bts.h @@ -326,6 +326,12 @@ struct gprs_rlc_cfg rlc_cfg; }; +/* See (struct gsm_bts *)->depends_on */ +struct bts_depends_on_entry { + struct llist_head list; + uint8_t bts_nr; /* See (struct gsm_bts *)->nr */ +}; + /* One BTS */ struct gsm_bts { /* list header in net->bts_list */ @@ -596,8 +602,8 @@ /* supported codecs beside FR */ struct bts_codec_conf codec; - /* BTS dependencies bit field */ - uint32_t depends_on[256/(8*4)]; + /* BTS dependencies bit field, list of "struct bts_depends_on_entry" */ + struct llist_head depends_on; /* full and half rate multirate config */ struct amr_multirate_conf mr_full; @@ -832,8 +838,8 @@ /* dependency handling */ void bts_depend_mark(struct gsm_bts *bts, int dep); void bts_depend_clear(struct gsm_bts *bts, int dep); -int bts_depend_check(struct gsm_bts *bts); -int bts_depend_is_depedency(struct gsm_bts *base, struct gsm_bts *other); +bool bts_depend_check(struct gsm_bts *bts); +bool bts_depend_is_depedency(struct gsm_bts *base, struct gsm_bts *other); int gsm_bts_get_radio_link_timeout(const struct gsm_bts *bts); void gsm_bts_set_radio_link_timeout(struct gsm_bts *bts, int value); diff --git a/src/osmo-bsc/bts.c b/src/osmo-bsc/bts.c index 8cc9e9a..29b6ffe 100644 --- a/src/osmo-bsc/bts.c +++ b/src/osmo-bsc/bts.c @@ -343,6 +343,7 @@ INIT_LLIST_HEAD(&bts->neighbors); INIT_LLIST_HEAD(&bts->oml_fail_rep); INIT_LLIST_HEAD(&bts->chan_rqd_queue); + INIT_LLIST_HEAD(&bts->depends_on); /* Don't pin the BTS to any MGW by default: */ bts->mgw_pool_target = -1; @@ -869,37 +870,38 @@ } } -/* Assume there are only 256 possible bts */ -osmo_static_assert(sizeof(((struct gsm_bts *) 0)->nr) == 1, _bts_nr_is_256); -static void depends_calc_index_bit(int bts_nr, int *idx, int *bit) -{ - *idx = bts_nr / (8 * 4); - *bit = bts_nr % (8 * 4); -} - void bts_depend_mark(struct gsm_bts *bts, int dep) { - int idx, bit; - depends_calc_index_bit(dep, &idx, &bit); + struct bts_depends_on_entry *entry; + entry = talloc_zero(bts, struct bts_depends_on_entry); + entry->bts_nr = dep; + llist_add_tail(&entry->list, &bts->depends_on); +} - bts->depends_on[idx] |= 1U << bit; +static struct bts_depends_on_entry *bts_depend_find_entry(struct gsm_bts *bts, int dep) +{ + struct bts_depends_on_entry *entry; + llist_for_each_entry(entry, &bts->trx_list, list) { + if (entry->bts_nr == dep) + return entry; + } + return NULL; } void bts_depend_clear(struct gsm_bts *bts, int dep) { - int idx, bit; - depends_calc_index_bit(dep, &idx, &bit); - - bts->depends_on[idx] &= ~(1U << bit); + struct bts_depends_on_entry *entry; + entry = bts_depend_find_entry(bts, dep); + if (!entry) + return; + llist_del(&entry->list); + talloc_free(entry); } -int bts_depend_is_depedency(struct gsm_bts *base, struct gsm_bts *other) +bool bts_depend_is_depedency(struct gsm_bts *base, struct gsm_bts *other) { - int idx, bit; - depends_calc_index_bit(other->nr, &idx, &bit); - - /* Check if there is a depends bit */ - return (base->depends_on[idx] & (1U << bit)) > 0; + struct bts_depends_on_entry *entry = bts_depend_find_entry(base, other->nr); + return !!entry; } static bool bts_is_online(const struct gsm_bts *bts) @@ -914,7 +916,7 @@ return bts->mo.nm_state.operational == NM_OPSTATE_ENABLED; } -int bts_depend_check(struct gsm_bts *bts) +bool bts_depend_check(struct gsm_bts *bts) { struct gsm_bts *other_bts; @@ -923,9 +925,9 @@ continue; if (bts_is_online(other_bts)) continue; - return 0; + return false; } - return 1; + return true; } /* get the radio link timeout (based on SACCH decode errors, according diff --git a/src/osmo-bsc/bts_vty.c b/src/osmo-bsc/bts_vty.c index 24224f6..4b94781 100644 --- a/src/osmo-bsc/bts_vty.c +++ b/src/osmo-bsc/bts_vty.c @@ -4490,6 +4490,14 @@ vty_out(vty, "%s", VTY_NEWLINE); } +static void config_write_bts_depends_on(struct vty *vty, const char *prefix, const struct gsm_bts *bts) +{ + struct bts_depends_on_entry *entry; + llist_for_each_entry(entry, &bts->depends_on, list) { + vty_out(vty, "%sdepends-on-bts %u%s", prefix, entry->bts_nr, VTY_NEWLINE); + } +} + static void config_write_bts_single(struct vty *vty, struct gsm_bts *bts) { int i; @@ -4775,23 +4783,7 @@ vty_out(vty, " %sforce-combined-si%s", bts->force_combined_si ? "" : "no ", VTY_NEWLINE); - for (i = 0; i < ARRAY_SIZE(bts->depends_on); ++i) { - int j; - - if (bts->depends_on[i] == 0) - continue; - - for (j = 0; j < sizeof(bts->depends_on[i]) * 8; ++j) { - int bts_nr; - - if ((bts->depends_on[i] & (1<<j)) == 0) - continue; - - bts_nr = (i * sizeof(bts->depends_on[i]) * 8) + j; - vty_out(vty, " depends-on-bts %d%s", bts_nr, VTY_NEWLINE); - } - } - + config_write_bts_depends_on(vty, " ", bts); ho_vty_write_bts(vty, bts); if (bts->top_acch_cap.overpower_db > 0) { -- To view, visit https://gerrit.osmocom.org/c/osmo-bsc/+/38050?usp=email To unsubscribe, or for help writing mail filters, visit https://gerrit.osmocom.org/settings?usp=email Gerrit-MessageType: newchange Gerrit-Project: osmo-bsc Gerrit-Branch: master Gerrit-Change-Id: I59e37d6baa020aeafdffc2c3538e988effd37620 Gerrit-Change-Number: 38050 Gerrit-PatchSet: 1 Gerrit-Owner: pespin &lt;pespin(a)sysmocom.de&gt;