pespin has submitted this change. ( 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 previous 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, 52 insertions(+), 46 deletions(-)
Approvals: Jenkins Builder: Verified pespin: Looks good to me, approved
diff --git a/include/osmocom/bsc/bts.h b/include/osmocom/bsc/bts.h index e9634ee..f2f7217 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; @@ -830,10 +836,10 @@ }
/* dependency handling */ -void bts_depend_mark(struct gsm_bts *bts, int dep); +int 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..28d4c65 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,43 @@ } }
-/* 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) +int bts_depend_mark(struct gsm_bts *bts, int dep) { - *idx = bts_nr / (8 * 4); - *bit = bts_nr % (8 * 4); + struct bts_depends_on_entry *entry; + entry = talloc_zero(bts, struct bts_depends_on_entry); + if (!entry) { + LOG_BTS(bts, DNM, LOGL_ERROR, "Alloc of struct bts_depends_on_entry failed"); + return -1; + } + entry->bts_nr = dep; + llist_add_tail(&entry->list, &bts->depends_on); + return 0; }
-void bts_depend_mark(struct gsm_bts *bts, int dep) +static struct bts_depends_on_entry *bts_depend_find_entry(const 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; + 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 +921,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 +930,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..3c0c2ef 100644 --- a/src/osmo-bsc/bts_vty.c +++ b/src/osmo-bsc/bts_vty.c @@ -2633,7 +2633,8 @@ return CMD_WARNING; }
- bts_depend_mark(bts, dep); + if (bts_depend_mark(bts, dep) < 0) + return CMD_WARNING; return CMD_SUCCESS; }
@@ -4490,6 +4491,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 +4784,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) {