diff options
author | Jacob Erlbeck <jerlbeck@sysmocom.de> | 2014-08-07 18:35:30 +0200 |
---|---|---|
committer | Jacob Erlbeck <jerlbeck@sysmocom.de> | 2014-08-13 10:42:27 +0200 |
commit | 2dec9851bd13e053790502275bf03ace25efbf76 (patch) | |
tree | b8a2d38135666fe101fdd4dc8b7a78ba663675d7 /openbsc/src | |
parent | f494620c551c85887e66157558d7c9e14e97cf3a (diff) |
gbproxy: Optimize gbprox_remove_stale_tllis
The current implementation of this function is O(N), where N is the
number of entries.
The new implementation is O(D), where D is the number of entries that
are going to be deleted.
Sponsored-by: On-Waves ehf
Diffstat (limited to 'openbsc/src')
-rw-r--r-- | openbsc/src/gprs/gb_proxy.c | 48 |
1 files changed, 33 insertions, 15 deletions
diff --git a/openbsc/src/gprs/gb_proxy.c b/openbsc/src/gprs/gb_proxy.c index 435e8ed7e..203a15ba6 100644 --- a/openbsc/src/gprs/gb_proxy.c +++ b/openbsc/src/gprs/gb_proxy.c @@ -559,32 +559,50 @@ static void gbprox_attach_tlli_info(struct gbproxy_peer *peer, time_t now, int gbprox_remove_stale_tllis(struct gbproxy_peer *peer, time_t now) { struct gbproxy_patch_state *state = &peer->patch_state; - struct gbproxy_tlli_info *tlli_info = NULL, *nxt; - int count = 0; + int exceeded_max_len = 0; int deleted_count = 0; + int check_for_age; - llist_for_each_entry_safe(tlli_info, nxt, &state->enabled_tllis, list) { - int is_stale = 0; - time_t age = now - tlli_info->timestamp; + if (peer->cfg->tlli_max_len > 0) + exceeded_max_len = + state->enabled_tllis_count - peer->cfg->tlli_max_len; - count += 1; + check_for_age = peer->cfg->tlli_max_age > 0; - if (peer->cfg->tlli_max_len > 0) - is_stale = is_stale || count > peer->cfg->tlli_max_len; + for (; exceeded_max_len > 0; exceeded_max_len--) { + struct gbproxy_tlli_info *tlli_info; + OSMO_ASSERT(!llist_empty(&state->enabled_tllis)); + tlli_info = llist_entry(state->enabled_tllis.prev, + struct gbproxy_tlli_info, + list); + LOGP(DGPRS, LOGL_INFO, + "Removing TLLI %08x from list " + "(stale, length %d, max_len exceeded)\n", + tlli_info->tlli, state->enabled_tllis_count); - if (peer->cfg->tlli_max_age > 0) - is_stale = is_stale || age > peer->cfg->tlli_max_age; + gbprox_delete_tlli(peer, tlli_info); + deleted_count += 1; + } - if (!is_stale) + while (check_for_age && !llist_empty(&state->enabled_tllis)) { + time_t age; + struct gbproxy_tlli_info *tlli_info; + tlli_info = llist_entry(state->enabled_tllis.prev, + struct gbproxy_tlli_info, + list); + age = now - tlli_info->timestamp; + /* age < 0 only happens after system time jumps, discard entry */ + if (age <= peer->cfg->tlli_max_age && age >= 0) { + check_for_age = 0; continue; + } LOGP(DGPRS, LOGL_INFO, - "Removing TLLI %08x from list (stale)\n", - tlli_info->tlli); + "Removing TLLI %08x from list " + "(stale, age %d, max_age exceeded)\n", + tlli_info->tlli, (int)age); gbprox_delete_tlli(peer, tlli_info); - tlli_info = NULL; - deleted_count += 1; } |