diff options
Diffstat (limited to 'cicn-plugin/cicn/cicn_pcs.c')
| -rw-r--r-- | cicn-plugin/cicn/cicn_pcs.c | 384 |
1 files changed, 384 insertions, 0 deletions
diff --git a/cicn-plugin/cicn/cicn_pcs.c b/cicn-plugin/cicn/cicn_pcs.c new file mode 100644 index 00000000..e3427a46 --- /dev/null +++ b/cicn-plugin/cicn/cicn_pcs.c @@ -0,0 +1,384 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* + * cicn_pcs.c: Opportunistic timeout code for the PIT/CS used in the cicn forwarder. + */ + +#include <stdlib.h> +#include <errno.h> +#include <assert.h> +#include <inttypes.h> + +#include <vlib/vlib.h> +#include <vppinfra/pool.h> + +#include <cicn/cicn.h> +#include <cicn/cicn_hashtb.h> +#include <cicn/cicn_pcs.h> + +/* + * Calling worker thread context, passed in and bundled up + * to be passed to the bucket scanning code to enable updating + * data-stuctures in the event of deletions. + */ +typedef struct cicn_pcs_worker_ctx_s +{ /* worker thread context */ + vlib_main_t *vm; /* vpp */ + cicn_pit_cs_t *pitcs; /* PIT/CS table */ + uint64_t h; /* hash */ + u32 *pec; /* PIT Expired Count */ + u32 *cec; /* CS Expired Count */ + + cicn_hashtb_h ht; /* derived from .pitcs */ +} cicn_pcs_worker_ctx_t; + +/* + * Overflow bucket context: as a bucket is scanned, maintain + * the location and count of occupied and empty (free) entries + * to enable bucket compaction. + */ +typedef struct cicn_hashtb_bucket_ctx_s +{ /* bucket context */ + cicn_hash_bucket_t *bucket; + int occupied[CICN_HASHTB_BUCKET_ENTRIES]; /* occupied */ + int noccupied; /* occupied */ + int empty[CICN_HASHTB_BUCKET_ENTRIES]; /* free */ + int nempty; /* free */ +} cicn_hashtb_bucket_ctx_t; + +/* + * Free an overflow bucket from a hashtable (derived + * from the static function in cicn_hashtb.c). + */ +static void +cicn_free_overflow_bucket (cicn_hashtb_h ht, cicn_hash_bucket_t * bucket) +{ + ASSERT (ht->ht_overflow_buckets_used > 0); + + pool_put (ht->ht_overflow_buckets, bucket); + ht->ht_overflow_buckets_used--; +} + +/* + * Scan a single bucket (8 entries) for timed-out entries. + * + * Recursive function, for scanning chain of buckets. + * - Bucket chains should be short, so recursion should not be deep. + * (If bucket chains are long, either hash table is dimensioned too small or + * hash function is not distributing names effectively.) + * - Find and clear out timed out entries on the way down the recursion. + * - Compact entries and free unused overflow buckets (if possible) on the + * way back up the recursion. + * + * + * Recursion in detail: + * - pre-recursion processing + * - scan of the supplied bucket and cleanup of expired entries + * - recursion processing: + * - if a bucket follows supplied bucket, recurse + * - post-recursion processing: + * - if supplied bucket is head of chain (pbctx == 0), done + * - if supplied bucket is non-head element of chain, try to compact + * entries into supplied parent of supplied bucket and free supplied + * bucket if it ends up empty. + * - buckets are freed from the tail backwards + * - recursive call can have caused supplied bucket to pick up new + * entries from its child, so need to rescan supplied bucket after + * the recursive call. + * + * Arguments are: + * wctx: worker context for updating datastructures + * at the vpp node level; + * pbctx: bucket context of the calling (parent) instance + * of cicn_pcs_timeout_opportunity(); + * bucket: the bucket to scan. + */ +static int +cicn_pcs_timeout_opportunity (cicn_pcs_worker_ctx_t * wctx, + cicn_hashtb_bucket_ctx_t * pbctx, + cicn_hash_bucket_t * bucket) +{ + int i, r; + uint16_t timeout; + cicn_hashtb_h ht; + cicn_hash_bucket_t *b; + cicn_hash_node_t *node; + cicn_hash_entry_t *entry; + cicn_pcs_entry_t *pcs; + cicn_hashtb_bucket_ctx_t bctx; + + /* + * Initialise the bucket context for this scan; + * if this bucket has an overflow entry, the context + * will be passed to it (and seen as pbctx). + */ + memset (&bctx, 0, sizeof (bctx)); + bctx.bucket = bucket; + + /* + * Scan the bucket for expired entries and release them, + * updating bctx with the location and count of occupied + * and empty entries. + */ + ht = wctx->ht; + for (i = 0; i < CICN_HASHTB_BUCKET_ENTRIES; i++) + { + entry = &bucket->hb_entries[i]; + if (entry->he_node == 0) + { + bctx.empty[bctx.nempty++] = i; + continue; + } + if (entry->he_flags & CICN_HASH_ENTRY_FLAG_OVERFLOW) + { + if (i != CICN_HASHTB_BUCKET_ENTRIES - 1) + assert (!(entry->he_flags & CICN_HASH_ENTRY_FLAG_OVERFLOW)); + bctx.occupied[bctx.noccupied++] = i; + break; + } + + if (entry->he_flags & CICN_HASH_ENTRY_FLAG_DELETED) + { + bctx.occupied[bctx.noccupied++] = i; + continue; + } + + if (entry->he_flags & CICN_HASH_ENTRY_FLAG_FAST_TIMEOUT) + { + timeout = cicn_infra_fast_timer; + } + else + { + timeout = cicn_infra_slow_timer; + } + if (cicn_infra_seq16_gt (entry->he_timeout, timeout)) + { + bctx.occupied[bctx.noccupied++] = i; + continue; + } + + /* + * Entry has timed out, update the relevant statistics + * at the vpp node level and release the resources; the entry + * is now counted as empty. + * Parallel to cicn_pcs_delete(): cannot call cicn_pcs_delete() + * since that can call cicn_hashtb_delete() and cause supplied + * bucket to get freed in middle of chain scan. + */ + node = pool_elt_at_index (ht->ht_nodes, entry->he_node); + pcs = cicn_pit_get_data (node); + switch (pcs->shared.entry_type) + { + default: + /* + * Should not happen, not sure how to signal this? + * Count the bucket as occupied and continue? or... + * assert(entry->he_flags & (CICN_CS_TYPE|CICN_PIT_TYPE)); + */ + bctx.occupied[bctx.noccupied++] = i; + continue; + + case CICN_PIT_TYPE: + wctx->pitcs->pcs_pit_count--; + (*wctx->pec)++; + break; + + case CICN_CS_TYPE: + wctx->pitcs->pcs_cs_count--; + /* Clean up CS LRU */ + cicn_cs_lru_dequeue (wctx->pitcs, node, pcs); + if (pcs->u.cs.cs_pkt_buf != 0) + { + BUFTRC (" CS-TO", pcs->u.cs.cs_pkt_buf); + vlib_buffer_free_one (wctx->vm, pcs->u.cs.cs_pkt_buf); + pcs->u.cs.cs_pkt_buf = 0; + } + (*wctx->cec)++; + break; + } + cicn_hashtb_init_entry (entry, 0, 0ll); + cicn_hashtb_free_node (ht, node); + + bctx.empty[bctx.nempty++] = i; + } + + /* recursion phase: recursively process child of this bucket, if any + * - entry conveniently points to the supplied bucket's last entry, + * which indicates if another bucket is present in the bucket chain + */ + r = AOK; + if (entry->he_flags & CICN_HASH_ENTRY_FLAG_OVERFLOW) + { + b = pool_elt_at_index (ht->ht_overflow_buckets, entry->he_node); + r = cicn_pcs_timeout_opportunity (wctx, &bctx, b); + if (r != AOK) + { + goto done; + } + } + + /* + * post-recursion phase, case 1: + * - supplied bucket is head bucket, no further compaction required + */ + if (pbctx == 0) + { + r = AOK; + goto done; + } + + /* + * post-recursion phase, case 2: + * - supplied bucket is non-head (aka overflow) bucket, try to compact + * supplied bucket's entries into supplied parent of supplied bucket + * - pbctx is parent, try to compact entries into it from this bucket + * if room exists + * - pbctx is guaranteed still valid since not considered for + * freeing until this routine returns. + * - because child of this this bucket may have compacted its entries + * into supplied bucket, rescan supplied bucket to reinitialise + * the context. + * - if supplied bucket ends up empty, free it + * - supplied bucket is empty through combination of its entries + * timing out, no child entries got compressed into it, + * and/or supplied buckets entries get compressed into parent + */ + + /* rescan */ + memset (&bctx, 0, sizeof (bctx)); + bctx.bucket = bucket; + for (i = 0; i < CICN_HASHTB_BUCKET_ENTRIES; i++) + { + entry = &bucket->hb_entries[i]; + if (entry->he_node == 0) + { + bctx.empty[bctx.nempty++] = i; + continue; + } + bctx.occupied[bctx.noccupied++] = i; + } + + /* + * Try to move any entries up to the parent bucket. + * Always set entry at the top of the loop before checking there is + * room in the parent so it will point to the first valid entry not + * moved up to the parent if the loop is exited before either all + * are copied or only an overflow bucket entry is left. + */ + for (entry = 0, i = 0; i < bctx.noccupied; i++) + { + entry = &bucket->hb_entries[bctx.occupied[i]]; + if (pbctx->nempty == 0) + { + break; + } + if (entry->he_flags & CICN_HASH_ENTRY_FLAG_OVERFLOW) + { + assert (i == bctx.noccupied - 1); + break; + } + + pbctx->bucket->hb_entries[pbctx->empty[--pbctx->nempty]] = *entry; + cicn_hashtb_init_entry (entry, 0, 0ll); + } + + /* + * How many are left in this bucket? + */ + switch (bctx.noccupied - i) + { + default: + /* + * Couldn't empty all the entries in this overflow bucket, + * maybe next time... + */ + break; + + case 0: + /* + * This overflow bucket is empty, clear the parent's overflow entry + * and release this bucket. + */ + cicn_hashtb_init_entry (&pbctx-> + bucket->hb_entries[CICN_HASHTB_BUCKET_ENTRIES - + 1], 0, 0ll); + cicn_free_overflow_bucket (ht, bucket); + break; + + case 1: + /* + * If it's an overflow bucket entry, can move it to the parent's + * overflow bucket entry (which points here) and free this bucket; + * similarly for a non-overflow bucket entry, unless the hashtable has + * CICN_HASHTB_FLAG_USE_SEVEN set, in which case there's nothing to be + * done - already checked the parent has no free space elsewhere. + */ + if ((entry->he_flags & CICN_HASH_ENTRY_FLAG_OVERFLOW) || + !(ht->ht_flags & CICN_HASHTB_FLAG_USE_SEVEN)) + { + pbctx->bucket->hb_entries[CICN_HASHTB_BUCKET_ENTRIES - 1] = *entry; + cicn_free_overflow_bucket (ht, bucket); + } + break; + } + + r = AOK; + +done: + return (r); +} + +/* + * Opportunistic timeout: + * given a hash value and some context, scan all the entries in the + * relevant hashtable bucket (and any overflow buckets it may have) + * for entries that have timed out and free them; + * as a side effect, try to compact and free any overflow buckets. + * + * Could perhaps be generalised to other functions requiring a scan + * of a hashtable bucket, or easily adapted to using a timer-wheel if + * opportunistic scanning was found to be inadeqaute. + */ +int +cicn_pcs_timeout (vlib_main_t * vm, + cicn_pit_cs_t * pitcs, uint64_t h, u32 * pec, u32 * cec) +{ + uint32_t bidx; + cicn_hashtb_h ht; + cicn_hash_bucket_t *bucket; + cicn_pcs_worker_ctx_t wctx; + + /* + * Construct the worker thread context passed to the actual scan + * routine - it needs to be able to update datastuctures. + */ + memset (&wctx, 0, sizeof (wctx)); + wctx.vm = vm; + wctx.pitcs = pitcs; + ht = pitcs->pcs_table; + wctx.ht = ht; + wctx.h = h; + wctx.pec = pec; + wctx.cec = cec; + + /* + * Locate the bucket in the table using some + * bits of the low half of the hash. + */ + bidx = (h & (ht->ht_bucket_count - 1)); + bucket = ht->ht_buckets + bidx; + + return (cicn_pcs_timeout_opportunity (&wctx, 0, bucket)); +} |