vppinfra: move unused code to extras/deprecated/vppinfra

Type: improvement

Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: Id28299a188feefa1899d835fd499f018af95d81b

1 files changed, 0 insertions, 608 deletions

diff --git a/src/vppinfra/flowhash_template.h b/src/vppinfra/flowhash_template.h
deleted file mode 100644
index d7a621c1754..00000000000
--- a/src/vppinfra/flowhash_template.h
+++ /dev/null
@@ -1,608 +0,0 @@
-/*
- * Copyright (c) 2012 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.
- */
-
-/*
- * Author: Pierre Pfister <ppfister@cisco.com>
- *
- * DISCLAIMER !
- *
- *       This most likely is not the hash table you are looking for !!
- *
- *       This structure targets a very specific and quite narrow set of use-cases 
- *         that are not covered by other hash tables.
- *
- *       Read the following text carefully, or ask the author or one of VPP's
- *         committers to make sure this is what you are looking for.
- *
- *
- *  -- Abstract:
- * This hash table intends to provide a very fast lookup and insertion of
- * key-value pairs for flow tables (although it might be used for other
- * purposes), with additional support for lazy-timeouts.
- * In particular, it was designed to minimize blocking reads, register usage and
- * cache-lines accesses during a typical lookup.
- * This hash table therefore provides stateful packet processing
- * without performance degradation even when every single lookup has to fetch
- * memory from RAM.
- * This hash table is not thread-safe and requires executing a garbage
- * collection function to clean-up chained buckets.
- *
- *  -- Overview:
- *
- * One first aspect of this hash table is that it is self-contained in a single
- * bulk of memory. Each entry contains a key, a value, and a 32 bits timeout
- * value; occupies a full and single cache line; and is identified by a unique
- * 32 bits index. The entry index zero is reserved and used when an entry
- * could not be found nor inserted. Which means it is not necessary to
- * immediately check whether an insertion or lookup was successful before
- * behaving accordingly. One can just keep doing business as usual and
- * check for the error later.
- *
- * Each entry is associated with a timeout value (which unit or clock is up to
- * the user of the hash table). An entry which timeout is strictly smaller
- * than the current time is considered empty, whereas an entry which timeout is
- * greater or equal to the current time contains a valid key-value pair.
- *
- * Hash table lookup and insertion are equivalent:
- *  - An entry index is always returned (possibly index 0 if no entry could be
- *   found nor created).
- *  - The returned entry always has its key set to the provided key.
- *  - Timeout value will be greater than the provided current time whenever a
- *    valid entry was found, strictly smaller otherwise. In particular, one can
- *    not differentiate between an entry which was just created, and an entry
- *    which already existed in the past but got timeouted in between.
- *
- * As mentioned earlier, entry index zero is used as an invalid entry which may
- * be manipulated as a normal one. Entries which index go from 1 to
- * N (where N is a power of 2) are used as direct buckets, each containing a
- * single entry. In the absence of hash collision, a single entry which location
- * can deterministically be determined from the key-hash and the hash table
- * header is accessed (One single cache line, without indirection). This
- * allows for efficient pre-fetching of the key-value for more than 95% of
- * accesses.
- *
- * In order to handle hash collisions (i.e. when multiple keys
- * end-up in the same bucket), entries which index are greater than N are
- * grouped into M groups of 16 collision entries. Such groups are linked
- * with regular entries whenever a collision needs to be handled.
- * When looking up a key with a bucket where a collision occurred, unused bits
- * from the key hash are used to select two entries (from the collision bucket)
- * where the new entry might be inserted.
- *
- * Once an entry is inserted, it will never be moved as long as the entry
- * timeout value remains greater or equal to the provided current time value.
- * The entry index can therefore be stored in other data structure as a way
- * to bypass the hash lookup. But when doing so, one should check if the
- * present key is the actual looked-up key.
- *
- *  -- Garbage Collection:
- *
- *  Since there is no explicit element removal, a garbage collector mechanism
- *  is required in order to remove buckets used for hash collisions. This
- *  is done by calling the flowhash_gc function on a regular basis. Each call
- *  to this function examines a single fixed entry. It shall therefore be called
- *  as many times as there are fixed entries in the hash table in order to
- *  ensure a full inspection.
- *
- *  -- Time and timeout mechanism:
- *
- *  The hash table makes use of a time value between in [1, 2^32 - 1].
- *  The provided time value shall keep increasing, and looping is not handled.
- *  When seconds are used, the system should run for 136 years without any issue.
- *  If milliseconds are used, a shift should be operated on all timeout values
- *  on a regular basis (more than every 49 days).
- */
-
-#ifndef __included_flowhash_template_h__
-#define __included_flowhash_template_h__
-
-#include <vppinfra/clib.h>
-#include <vppinfra/mem.h>
-#include <vppinfra/cache.h>
-
-#ifndef FLOWHASH_TYPE
-#error FLOWHASH_TYPE not defined
-#endif
-
-#define _fv(a,b) a##b
-#define __fv(a,b) _fv(a,b)
-#define FV(a) __fv(a,FLOWHASH_TYPE)
-
-#define _fvt(a,b) a##b##_t
-#define __fvt(a,b) _fvt(a,b)
-#define FVT(a) __fvt(a,FLOWHASH_TYPE)
-
-/* Same for all flowhash variants */
-#ifndef __included_flowhash_common__
-
-#define FLOWHASH_INVALID_ENTRY_INDEX 0
-
-#define FLOWHASH_ENTRIES_PER_BUCKETS_LOG 4
-#define FLOWHASH_ENTRIES_PER_BUCKETS (1 << FLOWHASH_ENTRIES_PER_BUCKETS_LOG)
-
-#endif /* ifndef __included_flowhash_common__ */
-
- /**
-  * @brief Compare a stored key with a lookup key.
-  *
-  * This function must be defined to use this template. It must return 0
-  * when the two keys are identical, and a different value otherwise.
-  */
-static_always_inline
-u8 FV(flowhash_cmp_key)(FVT(flowhash_skey) *a, FVT(flowhash_lkey) *b);
-
- /**
-  * @brief Hash a lookup key into a 32 bit integer.
-  *
-  * This function must be defined to use this template.
-  * It must provides close to 32 bits of entropy distributed amongst
-  * all 32 bits of the provided value.
-  * Keys that are equal must have the same hash.
-  */
- static_always_inline
- u32 FV(flowhash_hash)(FVT(flowhash_lkey) *k);
-
-/**
- * @brief Copy a lookup key into a destination stored key.
- *
- * This function must be defined to use this template. It must modify the dst
- * key such that a later call to flowhash_cmp_key with the same arguments
- * would return 0.
- */
-static_always_inline
-void FV(flowhash_cpy_key)(FVT(flowhash_skey) *dst, FVT(flowhash_lkey) *src);
-
-/**
- * @brief One flow hash entry used for both direct buckets and collision
- *        buckets.
- */
-typedef struct {
-  /* Each entry is cache-line aligned. */
-  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
-
-  /* Key is first to take advantage of alignment. */
-  FVT(flowhash_skey) key;
-
-  /* Entry value. */
-  FVT(flowhash_value) value;
-
-  /* Timeout value */
-  u32 timeout;
-
-  /* Entry index to the chained bucket. */
-  u32 chained_entry_index;
-} FVT(flowhash_entry);
-
-typedef struct FVT(__flowhash_struct) {
-  /* Cache aligned to simplify allocation. */
-  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
-
-  /* Array going downward containing free bucket indices */
-  u32 free_buckets_indices[0];
-
-  /* Negative index of the first free bucket */
-  i32 free_buckets_position;
-
-  /* Number of fixed buckets minus one */
-  u32 fixed_entries_mask;
-
-  /* Allocated pointer for this hash table */
-  void *mem;
-
-  u32 collision_buckets_mask;
-  u32 total_entries;
-
-  u64 not_enough_buckets_counter;
-  u64 collision_lookup_counter;
-  u64 garbage_collection_counter;
-
-  u32 gc_counter;
-
-  /* Entry array containing:
-   * - 1 Dummy entry for error return
-   * - (buckets_mask + 1) Fixed buckets
-   * - chained_buckets Chained Buckets
-   */
-  FVT(flowhash_entry) entries[0];
-} FVT(flowhash);
-
-/* Same for all flowhash variants */
-#ifndef __included_flowhash_common__
-#define __included_flowhash_common__
-
-/**
- * @brief Test whether a returned entry index corresponds to an overflow event.
- */
-#define flowhash_is_overflow(ei) \
-    ((ei) == FLOWHASH_INVALID_ENTRY_INDEX)
-
-/**
- * @brief Iterate over all entries in the hash table.
- *
- * Iterate over all entries in the hash table, not including the first invalid
- * entry (at index 0), but including all chained hash collision buckets.
- *
- */
-#define flowhash_foreach_entry(h, ei) \
-      for (ei = 1; \
-           ei < (h)->total_entries; \
-           ei++)
-
-/**
- * @brief Iterate over all currently valid entries.
- *
- * Iterate over all entries in the hash table which timeout value is greater
- * or equal to the current time.
- */
-#define flowhash_foreach_valid_entry(h, ei, now) \
-    flowhash_foreach_entry(h, ei) \
-      if (((now) <= (h)->entries[ei].timeout))
-
-/**
- * @brief Timeout variable from a given entry.
- */
-#define flowhash_timeout(h, ei) (h)->entries[ei].timeout
-
-/**
- * @brief Indicates whether the entry is being used.
- */
-#define flowhash_is_timeouted(h, ei, time_now) \
-    ((time_now) > flowhash_timeout(h, ei))
-
-/**
- * @brief Get the key from the entry index, casted to the provided type.
- */
-#define flowhash_key(h, ei) (&(h)->entries[ei].key)
-
-/**
- * @brief Get the value from the entry index, casted to the provided type.
- */
-#define flowhash_value(h, ei) (&(h)->entries[ei].value)
-
-/**
- * @brief Get the number of octets allocated to this structure.
- */
-#define flowhash_memory_size(h) clib_mem_size((h)->mem)
-
-/**
- * @brief Test whether the entry index is in hash table boundaries.
- */
-#define flowhash_is_valid_entry_index(h, ei) (ei < (h)->total_entries)
-
-/**
- * @brief Adjust, if necessary, provided parameters such as being valid flowhash
- *        sizes.
- */
-static
-void flowhash_validate_sizes(u32 *fixed_entries, u32 *collision_buckets)
-{
-  /* Find power of two greater or equal to the provided value */
-  if (*fixed_entries < FLOWHASH_ENTRIES_PER_BUCKETS)
-    *fixed_entries = FLOWHASH_ENTRIES_PER_BUCKETS;
-  if (*fixed_entries > (1 << (32 - FLOWHASH_ENTRIES_PER_BUCKETS_LOG)))
-    *fixed_entries = (1 << (32 - FLOWHASH_ENTRIES_PER_BUCKETS_LOG));
-
-  *fixed_entries -= 1;
-  *fixed_entries |= *fixed_entries >> 16;
-  *fixed_entries |= *fixed_entries >> 8;
-  *fixed_entries |= *fixed_entries >> 4;
-  *fixed_entries |= *fixed_entries >> 2;
-  *fixed_entries |= *fixed_entries >> 1;
-  *fixed_entries += 1;
-
-  if (*collision_buckets != 0)
-    {
-      if (*collision_buckets < CLIB_CACHE_LINE_BYTES/sizeof(u32))
-        *collision_buckets = CLIB_CACHE_LINE_BYTES/sizeof(u32);
-
-      *collision_buckets -= 1;
-      *collision_buckets |= *collision_buckets >> 16;
-      *collision_buckets |= *collision_buckets >> 8;
-      *collision_buckets |= *collision_buckets >> 4;
-      *collision_buckets |= *collision_buckets >> 2;
-      *collision_buckets |= *collision_buckets >> 1;
-      *collision_buckets += 1;
-    }
-}
-
-/**
- * @brief Prefetch the the hash entry bucket.
- *
- * This should be performed approximately 200-300 cycles before lookup
- * if the table is located in RAM. Or 30-40 cycles before lookup
- * in case the table is located in L3.
- */
-#define flowhash_prefetch(h, hash) \
-    CLIB_PREFETCH (&(h)->entries[((hash) & (h)->fixed_entries_mask) + 1], \
-        	   sizeof((h)->entries[0]), LOAD)
-
-#endif /* ifndef __included_flowhash_common__ */
-
-/**
- * @brief Allocate a flowhash structure.
- *
- * @param[in] fixed_entries The number of fixed entries in the hash table.
- * @param[in] chained_buckets The number of chained buckets.
- *
- * fixed_entries and chained_buckets parameters may not be used as is but
- * modified in order to fit requirements.
- *
- * Since the flowhash does not support dynamic resizing, it is fairly
- * important to choose the parameters carefully. In particular the performance
- * gain from using this structure comes from an efficient lookup in the
- * absence of hash collision.
- * As a rule of thumbs, if the number of active entries (flows) is M,
- * there should be about 16*M fixed entries, and M/16 collision buckets.
- * Which represents 17*M allocated entries.
- *
- * For example:
- * M = 2^20 total_size ~= 1GiB    collision ~= 3%
- * M = 2^18 total_size ~= 250MiB  collision ~= 3%
- * M = 2^10 total_size ~= 1MiB    collision ~= 6%
- *
- */
-static_always_inline
-FVT(flowhash) *FV(flowhash_alloc)(u32 fixed_entries, u32 collision_buckets)
-{
-  FVT(flowhash) *h;
-  uword size;
-  void *mem;
-  u32 entries;
-
-  flowhash_validate_sizes(&fixed_entries, &collision_buckets);
-
-  entries = 1 + fixed_entries +
-      collision_buckets * FLOWHASH_ENTRIES_PER_BUCKETS;
-  size = sizeof(*h) + sizeof(h->entries[0]) * entries +
-      sizeof(h->free_buckets_indices[0]) * collision_buckets;
-
-  mem = clib_mem_alloc_aligned(size, CLIB_CACHE_LINE_BYTES);
-  h = mem + collision_buckets * sizeof(h->free_buckets_indices[0]);
-  h->mem = mem;
-
-  /* Fill free elements list */
-  int i;
-  clib_memset(h->entries, 0, sizeof(h->entries[0]) * entries);
-  for (i = 1; i <= collision_buckets; i++)
-    {
-      h->free_buckets_indices[-i] =
-          entries - i * FLOWHASH_ENTRIES_PER_BUCKETS;
-    }
-
-  /* Init buckets */
-  for (i=0; i < entries; i++)
-    {
-      h->entries[i].chained_entry_index = FLOWHASH_INVALID_ENTRY_INDEX;
-      h->entries[i].timeout = 0;
-    }
-
-  h->free_buckets_position = -collision_buckets;
-  h->fixed_entries_mask = fixed_entries - 1;
-  h->collision_buckets_mask = collision_buckets - 1;
-  h->total_entries = entries;
-  h->not_enough_buckets_counter = 0;
-  h->collision_lookup_counter = 0;
-  h->garbage_collection_counter = 0;
-  h->gc_counter = 0;
-
-  return h;
-}
-
-/**
- * @brief Free the flow hash memory.
- */
-static_always_inline
-void FV(flowhash_free)(FVT(flowhash) *h)
-{
-  clib_mem_free(h->mem);
-}
-
-static void
-FV(__flowhash_get_chained) (FVT(flowhash) *h, FVT(flowhash_lkey) *k,
-                            u32 hash, u32 time_now, u32 *ei);
-
-/**
- * @brief Retrieves an entry index corresponding to a provided key and its hash.
- *
- * @param h            The hash table pointer.
- * @param k[in]        A pointer to the key value.
- * @param hash[in]     The hash of the key.
- * @param time_now[in] The current time.
- * @param ei[out]      A pointer set to the found entry index.
- *
- * This function always sets ei value to a valid entry index which can then be
- * used to access the stored value as well as get or set its associated timeout.
- * The key stored in the returned entry is always set to the provided key.
- *
- * In case the provided key is not found, and no entry could be created
- * (either because there is no hash collision bucket available or
- * the candidate entries in the collision bucket were already used), ei is
- * set to the special value FLOWHASH_INVALID_ENTRY_INDEX (which can be tested
- * with the flowhash_is_overflow macro).
- *
- * The timeout value is never modified during a lookup.
- * - Use the flowhash_is_timeouted macro to test whether the returned entry
- *   was already valid, or is proposed for insertion.
- * - Use the flowhash_timeout macro to get and set the entry timeout value.
- *
- */
-static_always_inline
-void FV(flowhash_get) (FVT(flowhash) *h, FVT(flowhash_lkey) *k,
-                       u32 hash, u32 time_now, u32 *ei)
-{
-  *ei = (hash & h->fixed_entries_mask) + 1;
-
-  if (PREDICT_FALSE(FV(flowhash_cmp_key)(&h->entries[*ei].key, k) != 0))
-    {
-      if (PREDICT_TRUE(time_now > h->entries[*ei].timeout &&
-                       (h->entries[*ei].chained_entry_index ==
-                           FLOWHASH_INVALID_ENTRY_INDEX)))
-        {
-          FV(flowhash_cpy_key)(&h->entries[*ei].key, k);
-        }
-      else
-        {
-          FV(__flowhash_get_chained)(h, k, hash, time_now, ei);
-        }
-    }
-}
-
-static_always_inline void
-FV(__flowhash_get_chained) (FVT(flowhash) *h, FVT(flowhash_lkey) *k,
-                            u32 hash, u32 time_now, u32 *ei)
-{
-  h->collision_lookup_counter++;
-
-  if (h->entries[*ei].chained_entry_index == FLOWHASH_INVALID_ENTRY_INDEX)
-    {
-      /* No chained entry yet. Let's chain one. */
-      if (h->free_buckets_position == 0)
-        {
-          /* Oops. No more buckets available. */
-          h->not_enough_buckets_counter++;
-          *ei = FLOWHASH_INVALID_ENTRY_INDEX;
-          h->entries[FLOWHASH_INVALID_ENTRY_INDEX].timeout =
-              time_now - 1;
-          FV(flowhash_cpy_key)(
-              &h->entries[FLOWHASH_INVALID_ENTRY_INDEX].key, k);
-          return;
-        }
-
-      /* Forward link */
-      h->entries[*ei].chained_entry_index =
-          h->free_buckets_indices[h->free_buckets_position];
-
-      /* Backward link (for garbage collection) */
-      h->entries[h->free_buckets_indices[h->free_buckets_position]].
-              chained_entry_index = *ei;
-
-      /* Move pointer */
-      h->free_buckets_position++;
-    }
-
-  /* Get the two indexes where to look at. */
-  u32 bi0 = h->entries[*ei].chained_entry_index +
-      (hash >> (32 - FLOWHASH_ENTRIES_PER_BUCKETS_LOG));
-  u32 bi1 = bi0 + 1;
-  bi1 = (bi0 & (FLOWHASH_ENTRIES_PER_BUCKETS - 1)) ? bi1 :
-      bi1 - FLOWHASH_ENTRIES_PER_BUCKETS;
-
-  /* It is possible that we wait while comparing bi0 key.
-   * It's better to prefetch bi1 so we don't wait twice. */
-  CLIB_PREFETCH(&h->entries[bi1], sizeof (h->entries[0]), READ);
-
-  if (FV(flowhash_cmp_key)(&h->entries[bi0].key, k) == 0)
-    {
-      *ei = bi0;
-      return;
-    }
-
-  if (FV(flowhash_cmp_key)(&h->entries[bi1].key, k) == 0)
-    {
-      *ei = bi1;
-      return;
-    }
-
-  if (h->entries[*ei].timeout >= time_now)
-    {
-      *ei = FLOWHASH_INVALID_ENTRY_INDEX;
-      *ei = (time_now > h->entries[bi0].timeout) ? bi0 : *ei;
-      *ei = (time_now > h->entries[bi1].timeout) ? bi1 : *ei;
-    }
-
-  FV(flowhash_cpy_key)(&h->entries[*ei].key, k);
-}
-
-static_always_inline void
-FV(flowhash_gc)(FVT(flowhash) *h, u32 time_now,
-    u32 *freed_index, u32 *freed_len)
-{
-  u32 ei;
-  if (freed_index)
-    *freed_len = 0;
-
-  if (PREDICT_FALSE(h->collision_buckets_mask == (((u32)0) - 1)))
-    return;
-
-  /* prefetch two rounds in advance */
-  ei = 2 + h->fixed_entries_mask +
-      ((h->gc_counter + 2) & h->collision_buckets_mask) *
-        FLOWHASH_ENTRIES_PER_BUCKETS;
-  CLIB_PREFETCH(&h->entries[ei], sizeof (h->entries[0]), READ);
-
-  /* prefetch one round in advance */
-  ei = 2 + h->fixed_entries_mask +
-      ((h->gc_counter + 1) & h->collision_buckets_mask) *
-        FLOWHASH_ENTRIES_PER_BUCKETS;
-  if (h->entries[ei].chained_entry_index != FLOWHASH_INVALID_ENTRY_INDEX)
-    {
-      CLIB_PREFETCH(&h->entries[ei], 4 * CLIB_CACHE_LINE_BYTES, READ);
-    }
-
-  /* do GC */
-  ei = 2 + h->fixed_entries_mask +
-      ((h->gc_counter) & h->collision_buckets_mask) *
-      FLOWHASH_ENTRIES_PER_BUCKETS;
-  if (h->entries[ei].chained_entry_index != FLOWHASH_INVALID_ENTRY_INDEX)
-    {
-      u8 found = 0;
-      int i;
-      for (i=0; i<FLOWHASH_ENTRIES_PER_BUCKETS; i++)
-        {
-          if (time_now <= h->entries[ei + i].timeout)
-            {
-              found = 1;
-              break;
-            }
-        }
-
-      if (!found)
-        {
-          /* Tell caller we freed this */
-          if (freed_index)
-            {
-              *freed_index = ei;
-              *freed_len = FLOWHASH_ENTRIES_PER_BUCKETS;
-            }
-          /* The bucket is not used. Let's free it. */
-          h->free_buckets_position--;
-          /* Reset forward link */
-          h->entries[h->entries[ei].chained_entry_index].chained_entry_index =
-              FLOWHASH_INVALID_ENTRY_INDEX;
-          /* Reset back link */
-          h->entries[ei].chained_entry_index = FLOWHASH_INVALID_ENTRY_INDEX;
-          /* Free element */
-          h->free_buckets_indices[h->free_buckets_position] = ei;
-          /* Count the garbage collection event */
-          h->garbage_collection_counter++;
-        }
-    }
-
-  h->gc_counter++;
-}
-
-static_always_inline
-u32 FV(flowhash_elts)(FVT(flowhash) *h, u32 time_now)
-{
-  u32 tot = 0;
-  u32 ei;
-
-  flowhash_foreach_valid_entry(h, ei, time_now)
-    tot++;
-
-  return tot;
-}
-
-#endif /* __included_flowhash_template_h__ */