diff options
| -rw-r--r-- | src/vppinfra.am | 11 | ||||
| -rw-r--r-- | src/vppinfra/flowhash_24_16.h | 77 | ||||
| -rw-r--r-- | src/vppinfra/flowhash_8_8.h | 67 | ||||
| -rw-r--r-- | src/vppinfra/flowhash_template.h | 597 | ||||
| -rw-r--r-- | src/vppinfra/test_flowhash_template.c | 257 |
5 files changed, 1009 insertions, 0 deletions
diff --git a/src/vppinfra.am b/src/vppinfra.am index bf21ea89144..2bb16b2bd9c 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -24,6 +24,7 @@ TESTS += test_bihash_template \ test_elf \ test_elog \ test_fifo \ + test_flowhash_template \ test_format \ test_fpool \ test_hash \ @@ -59,6 +60,7 @@ test_dlist_SOURCES = vppinfra/test_dlist.c test_elf_SOURCES = vppinfra/test_elf.c test_elog_SOURCES = vppinfra/test_elog.c test_fifo_SOURCES = vppinfra/test_fifo.c +test_flowhash_template_SOURCES = vppinfra/test_flowhash_template.c test_format_SOURCES = vppinfra/test_format.c test_fpool_SOURCES = vppinfra/test_fpool.c test_hash_SOURCES = vppinfra/test_hash.c @@ -92,6 +94,7 @@ test_dlist_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_elf_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_elog_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_fifo_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG +test_flowhash_template_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_format_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_fpool_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_hash_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG @@ -123,6 +126,7 @@ test_dlist_LDADD = libvppinfra.la test_elf_LDADD = libvppinfra.la test_elog_LDADD = libvppinfra.la test_fifo_LDADD = libvppinfra.la +test_flowhash_template_LDADD = libvppinfra.la test_format_LDADD = libvppinfra.la test_fpool_LDADD = libvppinfra.la test_hash_LDADD = libvppinfra.la @@ -154,6 +158,7 @@ test_dlist_LDFLAGS = -static test_elf_LDFLAGS = -static test_elog_LDFLAGS = -static test_fifo_LDFLAGS = -static +test_flowhash_template_LDFLAGS = -static test_format_LDFLAGS = -static test_fpool_LDFLAGS = -static test_hash_LDFLAGS = -static @@ -210,6 +215,9 @@ nobase_include_HEADERS = \ vppinfra/error_bootstrap.h \ vppinfra/fifo.h \ vppinfra/file.h \ + vppinfra/flowhash_template.h \ + vppinfra/flowhash_8_8.h \ + vppinfra/flowhash_24_16.h \ vppinfra/format.h \ vppinfra/graph.h \ vppinfra/hash.h \ @@ -281,6 +289,9 @@ CLIB_CORE = \ vppinfra/error.c \ vppinfra/fifo.c \ vppinfra/fheap.c \ + vppinfra/flowhash_8_8.h \ + vppinfra/flowhash_24_16.h \ + vppinfra/flowhash_template.h \ vppinfra/format.c \ vppinfra/pool.c \ vppinfra/graph.c \ diff --git a/src/vppinfra/flowhash_24_16.h b/src/vppinfra/flowhash_24_16.h new file mode 100644 index 00000000000..64ee0796c7a --- /dev/null +++ b/src/vppinfra/flowhash_24_16.h @@ -0,0 +1,77 @@ +/* + * 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. + */ + +#ifndef SRC_VPPINFRA_FLOWHASH_24_16_H_ +#define SRC_VPPINFRA_FLOWHASH_24_16_H_ + +#ifdef __included_flowhash_template_h__ +#undef __included_flowhash_template_h__ +#endif + +#include <vppinfra/clib.h> +#include <vppinfra/xxhash.h> +#include <vppinfra/crc32.h> + +typedef struct { + u64 as_u64[3]; +} flowhash_skey_24_16_t; + +typedef struct { + u64 as_u64[3]; +} flowhash_lkey_24_16_t; + +typedef struct { + u64 as_u64[2]; +} flowhash_value_24_16_t; + +#define FLOWHASH_TYPE _24_16 +#include <vppinfra/flowhash_template.h> +#undef FLOWHASH_TYPE + +static_always_inline +u32 flowhash_hash_24_16(flowhash_lkey_24_16_t *k) +{ +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) &k->as_u64[0], 24); +#else + u64 val = 0; + val ^= k->as_u64[0]; + val ^= k->as_u64[1]; + val ^= k->as_u64[2]; + return (u32)clib_xxhash (val); +#endif +} + +static_always_inline +u8 flowhash_cmp_key_24_16(flowhash_skey_24_16_t *a, + flowhash_lkey_24_16_t *b) +{ + u8 val = 0; + val |= (a->as_u64[0] != b->as_u64[0]); + val |= (a->as_u64[1] != b->as_u64[1]); + val |= (a->as_u64[2] != b->as_u64[2]); + return val; +} + +static_always_inline +void flowhash_cpy_key_24_16(flowhash_skey_24_16_t *dst, + flowhash_lkey_24_16_t *src) +{ + dst->as_u64[0] = src->as_u64[0]; + dst->as_u64[1] = src->as_u64[1]; + dst->as_u64[2] = src->as_u64[2]; +} + +#endif /* SRC_VPPINFRA_FLOWHASH_24_16_H_ */ diff --git a/src/vppinfra/flowhash_8_8.h b/src/vppinfra/flowhash_8_8.h new file mode 100644 index 00000000000..4a5cfc0a0c6 --- /dev/null +++ b/src/vppinfra/flowhash_8_8.h @@ -0,0 +1,67 @@ +/* + * 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. + */ + +#ifndef SRC_VPPINFRA_FLOWHASH_8_8_H_ +#define SRC_VPPINFRA_FLOWHASH_8_8_H_ + +#ifdef __included_flowhash_template_h__ +#undef __included_flowhash_template_h__ +#endif + +#include <vppinfra/clib.h> +#include <vppinfra/xxhash.h> +#include <vppinfra/crc32.h> + +typedef struct { + u64 as_u64[1]; +} flowhash_skey_8_8_t; + +typedef struct { + u64 as_u64[1]; +} flowhash_lkey_8_8_t; + +typedef struct { + u64 as_u64[1]; +} flowhash_value_8_8_t; + +#define FLOWHASH_TYPE _8_8 +#include <vppinfra/flowhash_template.h> +#undef FLOWHASH_TYPE + +static_always_inline +u32 flowhash_hash_8_8(flowhash_lkey_8_8_t *k) +{ +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) &k->as_u64[0], 8); +#else + return clib_xxhash (k->as_u64[0]); +#endif +} + +static_always_inline +u8 flowhash_cmp_key_8_8(flowhash_skey_8_8_t *a, + flowhash_lkey_8_8_t *b) +{ + return a->as_u64[0] != b->as_u64[0]; +} + +static_always_inline +void flowhash_cpy_key_8_8(flowhash_skey_8_8_t *dst, + flowhash_lkey_8_8_t *src) +{ + dst->as_u64[0] = src->as_u64[0]; +} + +#endif /* SRC_VPPINFRA_FLOWHASH_8_8_H_ */ diff --git a/src/vppinfra/flowhash_template.h b/src/vppinfra/flowhash_template.h new file mode 100644 index 00000000000..8f8fef2c495 --- /dev/null +++ b/src/vppinfra/flowhash_template.h @@ -0,0 +1,597 @@ +/* + * 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; + u32 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; + 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 ei; + 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) + { + /* 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__ */ diff --git a/src/vppinfra/test_flowhash_template.c b/src/vppinfra/test_flowhash_template.c new file mode 100644 index 00000000000..19ac4edf2e2 --- /dev/null +++ b/src/vppinfra/test_flowhash_template.c @@ -0,0 +1,257 @@ +/* + * Copyright (c) 2015 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. + */ + +#include <vppinfra/time.h> +#include <vppinfra/cache.h> +#include <vppinfra/error.h> + +#include <vppinfra/heap.h> +#include <vppinfra/format.h> +#include <vppinfra/random.h> +#include <vppinfra/hash.h> + +#include <vppinfra/flowhash_8_8.h> + +/* Not actually tested here. But included for compilation purposes. */ +#include <vppinfra/flowhash_24_16.h> + +typedef struct +{ + u64 seed; + u32 fixed_entries; + u32 collision_buckets; + u32 nitems; + u32 iterations; + u32 prefetch; + int non_random_keys; + uword *key_hash; + flowhash_lkey_8_8_t *keys; + flowhash_8_8_t *hash; + clib_time_t clib_time; + unformat_input_t *input; +} test_main_t; + +test_main_t test_main; + +static clib_error_t * +test_flowhash (test_main_t * tm) +{ + f64 before, delta; + u64 total; + u32 overflow; + int i, j; + uword *p; + tm->hash = flowhash_alloc_8_8 (tm->fixed_entries, tm->collision_buckets); + if (tm->hash == NULL) + return clib_error_return (0, "Could not alloc hash"); + + fformat (stdout, "Allocated hash memory size: %llu\n", + flowhash_memory_size (tm->hash)); + + fformat (stdout, "Pick %lld unique %s keys...\n", + tm->nitems, tm->non_random_keys ? "non-random" : "random"); + + for (i = 0; i < tm->nitems; i++) + { + flowhash_lkey_8_8_t rndkey; + if (tm->non_random_keys == 0) + { + again: + rndkey.as_u64[0] = random_u64 (&tm->seed); + if ((p = hash_get (tm->key_hash, rndkey.as_u64[0]))) + goto again; + } + else + rndkey.as_u64[0] = (u64) (i + 1) << 16; + + hash_set (tm->key_hash, rndkey.as_u64[0], i + 1); + vec_add1 (tm->keys, rndkey); + } + + hash_free (tm->key_hash); + + /* Additions */ + overflow = 0; + before = clib_time_now (&tm->clib_time); + fformat (stdout, "Adding %u items...\n", tm->nitems); + for (i = 0; i < tm->nitems; i++) + { + u32 hash = flowhash_hash_8_8 (&tm->keys[i]); + u32 ei; + flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei); + if (flowhash_is_overflow (ei)) + overflow++; + + /* Set value (No matter if success) */ + flowhash_value (tm->hash, ei)->as_u64[0] = i + 1; + + /* Save value until time > 1 */ + flowhash_timeout (tm->hash, ei) = 1; + } + + delta = clib_time_now (&tm->clib_time) - before; + total = tm->nitems; + fformat (stdout, "%lld additions in %.6f seconds\n", total, delta); + if (delta > 0) + fformat (stdout, "%.f additions per second\n", ((f64) total) / delta); + + fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1)); + fformat (stdout, "Flowhash counters:\n"); + fformat (stdout, " collision-lookup: %lu\n", + tm->hash->collision_lookup_counter); + fformat (stdout, " not-enough-buckets: %lu\n", + tm->hash->not_enough_buckets_counter); + fformat (stdout, " overflows: %lu\n", overflow); + + /* Lookups (very similar to additions) */ + overflow = 0; + before = clib_time_now (&tm->clib_time); + fformat (stdout, "Looking up %u items %u times...\n", tm->nitems, + tm->iterations); + + for (j = 0; j < tm->iterations; j++) + { + i = 0; + if (tm->prefetch) + for (; i < tm->nitems - tm->prefetch; i++) + { + u32 ei; + u32 hash = flowhash_hash_8_8 (&tm->keys[i + tm->prefetch]); + flowhash_prefetch (tm->hash, hash); + hash = flowhash_hash_8_8 (&tm->keys[i]); + flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei); + if (flowhash_is_overflow (ei)) + overflow++; + else if (flowhash_timeout (tm->hash, ei) != 1) + clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]); + else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1) + clib_warning ("Value mismatch for key %lld\n", + tm->keys[i].as_u64[0]); + } + + for (; i < tm->nitems; i++) + { + u32 ei; + u32 hash = flowhash_hash_8_8 (&tm->keys[i]); + flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei); + if (flowhash_is_overflow (ei)) + overflow++; + else if (flowhash_timeout (tm->hash, ei) != 1) + clib_warning ("Key not found: %lld\n", tm->keys[i].as_u64[0]); + else if (flowhash_value (tm->hash, ei)->as_u64[0] != i + 1) + clib_warning ("Value mismatch for key %lld\n", + tm->keys[i].as_u64[0]); + } + } + + delta = clib_time_now (&tm->clib_time) - before; + total = tm->nitems * tm->iterations; + fformat (stdout, "%lld lookups in %.6f seconds\n", total, delta); + if (delta > 0) + fformat (stdout, "%.f lookups per second\n", ((f64) total) / delta); + + /* Delete */ + for (i = 0; i < tm->nitems; i++) + { + u32 hash = flowhash_hash_8_8 (&tm->keys[i]); + u32 ei; + flowhash_get_8_8 (tm->hash, &tm->keys[i], hash, 1, &ei); + flowhash_timeout (tm->hash, ei) = 0; + } + + fformat (stdout, "%u elements in table\n", flowhash_elts_8_8 (tm->hash, 1)); + + vec_free (tm->keys); + flowhash_free_8_8 (tm->hash); + + return NULL; +} + +clib_error_t * +test_flowhash_main (test_main_t * tm) +{ + unformat_input_t *i = tm->input; + clib_error_t *error; + + while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) + { + if (unformat (i, "seed %u", &tm->seed)) + ; + else if (unformat (i, "fixed-entries %d", &tm->fixed_entries)) + ; + else if (unformat (i, "collision-buckets %d", &tm->collision_buckets)) + ; + else if (unformat (i, "non-random-keys")) + tm->non_random_keys = 1; + else if (unformat (i, "nitems %d", &tm->nitems)) + ; + else if (unformat (i, "prefetch %d", &tm->prefetch)) + ; + else if (unformat (i, "iterations %d", &tm->iterations)) + ; + else + return clib_error_return (0, "unknown input '%U'", + format_unformat_error, i); + } + + error = test_flowhash (tm); + return error; +} + +#ifdef CLIB_UNIX +int +main (int argc, char *argv[]) +{ + + unformat_input_t i; + clib_error_t *error; + test_main_t *tm = &test_main; + + clib_mem_init (0, 3ULL << 30); + + tm->fixed_entries = 8 << 20; + tm->collision_buckets = 1 << 20; + tm->seed = 0xdeadf00l; + tm->iterations = 1; + tm->input = &i; + tm->nitems = 1000; + tm->non_random_keys = 0; + tm->key_hash = hash_create (0, sizeof (uword)); + tm->prefetch = 0; + clib_time_init (&tm->clib_time); + + unformat_init_command_line (&i, argv); + error = test_flowhash_main (tm); + unformat_free (&i); + + if (error) + { + clib_error_report (error); + return 1; + } + return 0; + + return 0; +} +#endif /* CLIB_UNIX */ + + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |