From 7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Mon, 19 Dec 2016 23:05:39 +0100 Subject: Reorganize source tree to use single autotools instance Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion --- src/vppinfra/bihash_24_8.h | 85 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 85 insertions(+) create mode 100644 src/vppinfra/bihash_24_8.h (limited to 'src/vppinfra/bihash_24_8.h') diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h new file mode 100644 index 00000000..353f06bf --- /dev/null +++ b/src/vppinfra/bihash_24_8.h @@ -0,0 +1,85 @@ +/* + * 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. + */ +#undef BIHASH_TYPE + +#define BIHASH_TYPE _24_8 +#define BIHASH_KVP_PER_PAGE 4 + +#ifndef __included_bihash_24_8_h__ +#define __included_bihash_24_8_h__ + +#include +#include +#include +#include + +typedef struct +{ + u64 key[3]; + u64 value; +} clib_bihash_kv_24_8_t; + +static inline int +clib_bihash_is_free_24_8 (const clib_bihash_kv_24_8_t * v) +{ + /* Free values are memset to 0xff, check a bit... */ + if (v->key[0] == ~0ULL && v->value == ~0ULL) + return 1; + return 0; +} + +static inline u64 +clib_bihash_hash_24_8 (const clib_bihash_kv_24_8_t * v) +{ +#if __SSE4_2__ + u32 value = 0; + value = _mm_crc32_u64 (value, v->key[0]); + value = _mm_crc32_u64 (value, v->key[1]); + value = _mm_crc32_u64 (value, v->key[2]); + return value; +#else + u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2]; + return clib_xxhash (tmp); +#endif +} + +static inline u8 * +format_bihash_kvp_24_8 (u8 * s, va_list * args) +{ + clib_bihash_kv_24_8_t *v = va_arg (*args, clib_bihash_kv_24_8_t *); + + s = format (s, "key %llu %llu %llu value %llu", + v->key[0], v->key[1], v->key[2], v->value); + return s; +} + +static inline int +clib_bihash_key_compare_24_8 (const u64 * a, const u64 * b) +{ + return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) == 0; +} + +#undef __included_bihash_template_h__ +#include + +#endif /* __included_bihash_24_8_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ -- cgit 1.2.3-korg From 0f68c79a9d8533d492c8221f924b14cf4e222136 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Wed, 26 Apr 2017 13:05:05 +0200 Subject: Add crc32c inline function, allows compilation on 32-bit systems 32-bit code still can use crc32c instructions, but it operates on 32 registers Change-Id: I9bb6b0b59635d6ea6a753584676ebcf59c8f6584 Signed-off-by: Damjan Marion --- src/plugins/acl/bihash_40_8.h | 9 ++----- src/plugins/lb/lbhash.h | 2 +- src/vnet/bfd/bfd_main.c | 2 +- src/vppinfra.am | 1 + src/vppinfra/bihash_24_8.h | 7 ++---- src/vppinfra/bihash_8_8.h | 7 ++---- src/vppinfra/crc32.h | 58 +++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 67 insertions(+), 19 deletions(-) create mode 100644 src/vppinfra/crc32.h (limited to 'src/vppinfra/bihash_24_8.h') diff --git a/src/plugins/acl/bihash_40_8.h b/src/plugins/acl/bihash_40_8.h index ba3dfbea..1dfb6a1e 100644 --- a/src/plugins/acl/bihash_40_8.h +++ b/src/plugins/acl/bihash_40_8.h @@ -24,6 +24,7 @@ #include #include #include +#include typedef struct { @@ -44,13 +45,7 @@ static inline u64 clib_bihash_hash_40_8 (const clib_bihash_kv_40_8_t * v) { #if __SSE4_2__ - u32 value = 0; - value = _mm_crc32_u64 (value, v->key[0]); - value = _mm_crc32_u64 (value, v->key[1]); - value = _mm_crc32_u64 (value, v->key[2]); - value = _mm_crc32_u64 (value, v->key[3]); - value = _mm_crc32_u64 (value, v->key[4]); - return value; + return clib_crc32c ((u8 *) v->key, 40); #else u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2] ^ v->key[3] ^ v->key[4]; return clib_xxhash (tmp); diff --git a/src/plugins/lb/lbhash.h b/src/plugins/lb/lbhash.h index ca3cc143..c514fb57 100644 --- a/src/plugins/lb/lbhash.h +++ b/src/plugins/lb/lbhash.h @@ -101,7 +101,7 @@ void lb_hash_free(lb_hash_t *h) vec_free(mem); } -#if __SSE4_2__ +#if __SSE4_2__ && !defined (__i386__) static_always_inline u32 lb_hash_hash(u64 k0, u64 k1, u64 k2, u64 k3, u64 k4) { diff --git a/src/vnet/bfd/bfd_main.c b/src/vnet/bfd/bfd_main.c index 66b31ce5..b58a5132 100644 --- a/src/vnet/bfd/bfd_main.c +++ b/src/vnet/bfd/bfd_main.c @@ -39,7 +39,7 @@ static u64 bfd_calc_echo_checksum (u32 discriminator, u64 expire_time, u32 secret) { u64 checksum = 0; -#if __SSE4_2__ +#if __SSE4_2__ && !defined (__i386__) checksum = _mm_crc32_u64 (0, discriminator); checksum = _mm_crc32_u64 (checksum, expire_time); checksum = _mm_crc32_u64 (checksum, secret); diff --git a/src/vppinfra.am b/src/vppinfra.am index fed1981e..3939d3ce 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -168,6 +168,7 @@ nobase_include_HEADERS = \ vppinfra/cache.h \ vppinfra/clib.h \ vppinfra/cpu.h \ + vppinfra/crc32.h \ vppinfra/dlist.h \ vppinfra/elf.h \ vppinfra/elf_clib.h \ diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index 353f06bf..655dab80 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -24,6 +24,7 @@ #include #include #include +#include typedef struct { @@ -44,11 +45,7 @@ static inline u64 clib_bihash_hash_24_8 (const clib_bihash_kv_24_8_t * v) { #if __SSE4_2__ - u32 value = 0; - value = _mm_crc32_u64 (value, v->key[0]); - value = _mm_crc32_u64 (value, v->key[1]); - value = _mm_crc32_u64 (value, v->key[2]); - return value; + return clib_crc32c ((u8 *) v->key, 24); #else u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2]; return clib_xxhash (tmp); diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index d70da596..b5c17461 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -24,10 +24,7 @@ #include #include #include - -#if __SSE4_2__ -#include -#endif +#include /** 8 octet key, 8 octet key value pair */ typedef struct @@ -55,7 +52,7 @@ clib_bihash_hash_8_8 (clib_bihash_kv_8_8_t * v) { /* Note: to torture-test linear scan, make this fn return a constant */ #if __SSE4_2__ - return _mm_crc32_u64 (0, v->key); + return clib_crc32c ((u8 *) & v->key, 8); #else return clib_xxhash (v->key); #endif diff --git a/src/vppinfra/crc32.h b/src/vppinfra/crc32.h new file mode 100644 index 00000000..abb2953f --- /dev/null +++ b/src/vppinfra/crc32.h @@ -0,0 +1,58 @@ +/* + * 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. + */ + +#ifndef __included_crc32_h__ +#define __included_crc32_h__ + +#if __SSE4_2__ +#include + +static_always_inline u32 +clib_crc32c (u8 * s, int len) +{ + u32 v = 0; + +#if __x86_64__ + for (; len >= 8; len -= 8, s += 8) + v = _mm_crc32_u64 (v, *((u64 *) s)); +#else + /* workaround weird GCC bug when using _mm_crc32_u32 + which happens with -O2 optimization */ + volatile ("":::"memory"); +#endif + + for (; len >= 4; len -= 4, s += 4) + v = _mm_crc32_u32 (v, *((u32 *) s)); + + for (; len >= 2; len -= 2, s += 2) + v = _mm_crc32_u16 (v, *((u16 *) s)); + + for (; len >= 1; len -= 1, s += 1) + v = _mm_crc32_u8 (v, *((u16 *) s)); + + return v; +} + +#endif + +#endif /* __included_crc32_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ -- cgit 1.2.3-korg From b4bd28a490012ecbce292561da404d4e9b02d24b Mon Sep 17 00:00:00 2001 From: Christophe Fontaine Date: Wed, 31 May 2017 11:27:19 +0200 Subject: Remove calls to crc_u32 and add clib_crc32c for armv8+crc crc_u32 was not defined for non x86_64 with SSE4.2 processors. Calls to "crc_u32" are removed and replaced by either a call to clib_crc32c or a call to clib_xxhash, as the result is not used as a check value but as a hash. Change-Id: I3af4d68e2e5ebd0c9b0a6090f848d043cb0f20a2 Signed-off-by: Christophe Fontaine --- src/plugins/flowprobe/node.c | 13 ++++++++++--- src/vnet/map/map.c | 42 ++++++++++++++++-------------------------- src/vppinfra/bihash_16_8.h | 30 ++++-------------------------- src/vppinfra/bihash_24_8.h | 4 ++-- src/vppinfra/bihash_48_8.h | 38 ++++---------------------------------- src/vppinfra/crc32.h | 26 +++++++++++++++++++++++++- 6 files changed, 61 insertions(+), 92 deletions(-) (limited to 'src/vppinfra/bihash_24_8.h') diff --git a/src/plugins/flowprobe/node.c b/src/plugins/flowprobe/node.c index 6a539db9..80bfa9b5 100644 --- a/src/plugins/flowprobe/node.c +++ b/src/plugins/flowprobe/node.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include @@ -258,10 +259,16 @@ static inline u32 flowprobe_hash (flowprobe_key_t * k) { flowprobe_main_t *fm = &flowprobe_main; - int i; u32 h = 0; - for (i = 0; i < sizeof (k->as_u32) / sizeof (u32); i++) - h = crc_u32 (k->as_u32[i], h); + +#ifdef clib_crc32c_uses_intrinsics + h = clib_crc32c ((u8 *) k->as_u32, FLOWPROBE_KEY_IN_U32); +#else + u64 tmp = + k->as_u32[0] ^ k->as_u32[1] ^ k->as_u32[2] ^ k->as_u32[3] ^ k->as_u32[4]; + h = clib_xxhash (tmp); +#endif + return h >> (32 - fm->ht_log2len); } diff --git a/src/vnet/map/map.c b/src/vnet/map/map.c index 8579cdf6..d246f6c8 100644 --- a/src/vnet/map/map.c +++ b/src/vnet/map/map.c @@ -19,29 +19,10 @@ #include #include #include +#include #include "map.h" -#ifdef __SSE4_2__ -static inline u32 -crc_u32 (u32 data, u32 value) -{ - __asm__ volatile ("crc32l %[data], %[value];":[value] "+r" (value):[data] - "rm" (data)); - return value; -} -#else -#include - -static inline u32 -crc_u32 (u32 data, u32 value) -{ - u64 tmp = ((u64) data << 32) | (u64) value; - return (u32) clib_xxhash (tmp); -} -#endif - - /* * This code supports the following MAP modes: * @@ -1488,10 +1469,12 @@ map_ip4_reass_get (u32 src, u32 dst, u16 fragment_id, }; u32 h = 0; - h = crc_u32 (k.as_u32[0], h); - h = crc_u32 (k.as_u32[1], h); - h = crc_u32 (k.as_u32[2], h); - h = crc_u32 (k.as_u32[3], h); +#ifdef clib_crc32c_uses_intrinsics + h = clib_crc32c ((u8 *) k.as_u32, 16); +#else + u64 tmp = k.as_u32[0] ^ k.as_u32[1] ^ k.as_u32[2] ^ k.as_u32[3]; + h = clib_xxhash (tmp); +#endif h = h >> (32 - mm->ip4_reass_ht_log2len); f64 now = vlib_time_now (mm->vlib_main); @@ -1660,8 +1643,15 @@ map_ip6_reass_get (ip6_address_t * src, ip6_address_t * dst, u32 fragment_id, u32 h = 0; int i; - for (i = 0; i < 10; i++) - h = crc_u32 (k.as_u32[i], h); + +#ifdef clib_crc32c_uses_intrinsics + h = clib_crc32c ((u8 *) k.as_u32, 40); +#else + u64 tmp = + k.as_u64[0] ^ k.as_u64[1] ^ k.as_u64[2] ^ k.as_u64[3] ^ k.as_u64[4]; + h = clib_xxhash (tmp); +#endif + h = h >> (32 - mm->ip6_reass_ht_log2len); f64 now = vlib_time_now (mm->vlib_main); diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h index ce80f70e..6b1b563e 100644 --- a/src/vppinfra/bihash_16_8.h +++ b/src/vppinfra/bihash_16_8.h @@ -24,6 +24,7 @@ #include #include #include +#include typedef struct { @@ -40,39 +41,16 @@ clib_bihash_is_free_16_8 (clib_bihash_kv_16_8_t * v) return 0; } -#if __SSE4_2__ -#ifndef __defined_crc_u32__ -#define __defined_crc_u32__ -static inline u32 -crc_u32 (u32 data, u32 value) -{ - __asm__ volatile ("crc32l %[data], %[value];":[value] "+r" (value):[data] - "rm" (data)); - return value; -} -#endif /* __defined_crc_u32__ */ - static inline u64 clib_bihash_hash_16_8 (clib_bihash_kv_16_8_t * v) { - u32 *dp = (u32 *) & v->key[0]; - u32 value = 0; - - value = crc_u32 (dp[0], value); - value = crc_u32 (dp[1], value); - value = crc_u32 (dp[2], value); - value = crc_u32 (dp[3], value); - - return value; -} +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) v->key, 16); #else -static inline u64 -clib_bihash_hash_16_8 (clib_bihash_kv_16_8_t * v) -{ u64 tmp = v->key[0] ^ v->key[1]; return clib_xxhash (tmp); -} #endif +} static inline u8 * format_bihash_kvp_16_8 (u8 * s, va_list * args) diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index 655dab80..db77daa4 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -20,11 +20,11 @@ #ifndef __included_bihash_24_8_h__ #define __included_bihash_24_8_h__ +#include #include #include #include #include -#include typedef struct { @@ -44,7 +44,7 @@ clib_bihash_is_free_24_8 (const clib_bihash_kv_24_8_t * v) static inline u64 clib_bihash_hash_24_8 (const clib_bihash_kv_24_8_t * v) { -#if __SSE4_2__ +#ifdef clib_crc32c_uses_intrinsics return clib_crc32c ((u8 *) v->key, 24); #else u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2]; diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h index 1a6e7691..48079e0a 100644 --- a/src/vppinfra/bihash_48_8.h +++ b/src/vppinfra/bihash_48_8.h @@ -21,6 +21,7 @@ #ifndef __included_bihash_48_8_h__ #define __included_bihash_48_8_h__ +#include #include #include #include @@ -41,48 +42,17 @@ clib_bihash_is_free_48_8 (const clib_bihash_kv_48_8_t * v) return 0; } -#if __SSE4_2__ -#ifndef __defined_crc_u32__ -#define __defined_crc_u32__ -static inline u32 -crc_u32 (u32 data, u32 value) -{ - __asm__ volatile ("crc32l %[data], %[value];":[value] "+r" (value):[data] - "rm" (data)); - return value; -} -#endif /* __defined_crc_u32__ */ - static inline u64 clib_bihash_hash_48_8 (const clib_bihash_kv_48_8_t * v) { - const u32 *dp = (const u32 *) &v->key[0]; - u32 value = 0; - - value = crc_u32 (dp[0], value); - value = crc_u32 (dp[1], value); - value = crc_u32 (dp[2], value); - value = crc_u32 (dp[3], value); - value = crc_u32 (dp[4], value); - value = crc_u32 (dp[5], value); - value = crc_u32 (dp[6], value); - value = crc_u32 (dp[7], value); - value = crc_u32 (dp[8], value); - value = crc_u32 (dp[9], value); - value = crc_u32 (dp[10], value); - value = crc_u32 (dp[11], value); - - return value; -} +#ifdef clib_crc32c_uses_intrinsics + return clib_crc32c ((u8 *) v->key, 48); #else -static inline u64 -clib_bihash_hash_48_8 (const clib_bihash_kv_48_8_t * v) -{ u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2] ^ v->key[3] ^ v->key[4] ^ v->key[5]; return clib_xxhash (tmp); -} #endif +} static inline u8 * format_bihash_kvp_48_8 (u8 * s, va_list * args) diff --git a/src/vppinfra/crc32.h b/src/vppinfra/crc32.h index abb2953f..5a47236a 100644 --- a/src/vppinfra/crc32.h +++ b/src/vppinfra/crc32.h @@ -17,6 +17,7 @@ #define __included_crc32_h__ #if __SSE4_2__ +#define clib_crc32c_uses_intrinsics #include static_always_inline u32 @@ -45,8 +46,31 @@ clib_crc32c (u8 * s, int len) return v; } -#endif +#elif __ARM_FEATURE_CRC32 +#define clib_crc32c_with_intrinsics +#include + +static_always_inline u32 +clib_crc32c (u8 * s, int len) +{ + u32 v = 0; + + for (; len >= 8; len -= 8, s += 8) + v = __crc32cd (v, *((u64 *) s)); + + for (; len >= 4; len -= 4, s += 4) + v = __crc32cw (v, *((u32 *) s)); + + for (; len >= 2; len -= 2, s += 2) + v = __crc32ch (v, *((u16 *) s)); + + for (; len >= 1; len -= 1, s += 1) + v = __crc32cb (v, *((u8 *) s)); + return v; +} + +#endif #endif /* __included_crc32_h__ */ /* -- cgit 1.2.3-korg From 908a5ea6e247b4a15f0ec7e8ee8ebff799abdc4f Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Fri, 14 Jul 2017 12:42:21 -0400 Subject: Add a bihash prefetchable bucket-level cache According to Maciek, the easiest way to leverage the csit "performance trend" job is to actually merge the patch once verified. Manual testing indicates that the patch improves l2 path performance. Other use-cases are TBD. It's possible that we'll need to back out the patch depending on what happens. Change-Id: Ic0a0363de35ef9be953ad7709c57c3936b73fd5a Signed-off-by: Dave Barach --- src/vnet/fib/ip6_fib.c | 4 +- src/vnet/fib/ip6_fib.h | 2 +- src/vnet/l2/l2_fib.c | 8 +- src/vppinfra.am | 2 + src/vppinfra/bihash_16_8.h | 3 + src/vppinfra/bihash_24_8.h | 3 + src/vppinfra/bihash_48_8.h | 3 + src/vppinfra/bihash_8_8.h | 3 + src/vppinfra/bihash_template.c | 78 ++++++++++++-- src/vppinfra/bihash_template.h | 206 ++++++++++++++++++++++++++++++++---- src/vppinfra/test_bihash_template.c | 61 +++++++++-- 11 files changed, 329 insertions(+), 44 deletions(-) (limited to 'src/vppinfra/bihash_24_8.h') diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c index 527f9114..8fde6f9f 100644 --- a/src/vnet/fib/ip6_fib.c +++ b/src/vnet/fib/ip6_fib.c @@ -200,7 +200,7 @@ ip6_fib_table_lookup (u32 fib_index, const ip6_address_t *addr, u32 len) { - const ip6_fib_table_instance_t *table; + ip6_fib_table_instance_t *table; BVT(clib_bihash_kv) kv, value; int i, n_p, rv; u64 fib; @@ -246,7 +246,7 @@ ip6_fib_table_lookup_exact_match (u32 fib_index, const ip6_address_t *addr, u32 len) { - const ip6_fib_table_instance_t *table; + ip6_fib_table_instance_t *table; BVT(clib_bihash_kv) kv, value; ip6_address_t *mask; u64 fib; diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h index 9789da4f..aad8305c 100644 --- a/src/vnet/fib/ip6_fib.h +++ b/src/vnet/fib/ip6_fib.h @@ -68,7 +68,7 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im, u32 fib_index, const ip6_address_t * dst) { - const ip6_fib_table_instance_t *table; + ip6_fib_table_instance_t *table; int i, len; int rv; BVT(clib_bihash_kv) kv, value; diff --git a/src/vnet/l2/l2_fib.c b/src/vnet/l2/l2_fib.c index 4ed16987..7e59b098 100644 --- a/src/vnet/l2/l2_fib.c +++ b/src/vnet/l2/l2_fib.c @@ -66,7 +66,7 @@ l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key, { l2fib_main_t *msm = &l2fib_main; BVT (clib_bihash) * h = &msm->mac_table; - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; BVT (clib_bihash_value) * v; l2fib_entry_key_t key; l2fib_entry_result_t result; @@ -108,7 +108,7 @@ show_l2fib (vlib_main_t * vm, l2fib_main_t *msm = &l2fib_main; l2_bridge_domain_t *bd_config; BVT (clib_bihash) * h = &msm->mac_table; - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; BVT (clib_bihash_value) * v; l2fib_entry_key_t key; l2fib_entry_result_t result; @@ -961,7 +961,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt, if (i < (h->nbuckets - 3)) { - clib_bihash_bucket_t *b = &h->buckets[i + 3]; + BVT (clib_bihash_bucket) * b = &h->buckets[i + 3]; CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD); b = &h->buckets[i + 1]; if (b->offset) @@ -972,7 +972,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt, } } - clib_bihash_bucket_t *b = &h->buckets[i]; + BVT (clib_bihash_bucket) * b = &h->buckets[i]; if (b->offset == 0) continue; BVT (clib_bihash_value) * v = diff --git a/src/vppinfra.am b/src/vppinfra.am index 785445a6..533bacd6 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -42,6 +42,8 @@ TESTS += test_bihash_template \ test_zvec endif +TESTS += test_bihash_template + noinst_PROGRAMS = $(TESTS) check_PROGRAMS = $(TESTS) diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h index 6b1b563e..361665be 100644 --- a/src/vppinfra/bihash_16_8.h +++ b/src/vppinfra/bihash_16_8.h @@ -13,9 +13,12 @@ * limitations under the License. */ #undef BIHASH_TYPE +#undef BIHASH_KVP_CACHE_SIZE +#undef BIHASH_KVP_PER_PAGE #define BIHASH_TYPE _16_8 #define BIHASH_KVP_PER_PAGE 4 +#define BIHASH_KVP_CACHE_SIZE 5 #ifndef __included_bihash_16_8_h__ #define __included_bihash_16_8_h__ diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index db77daa4..d0be028c 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -13,9 +13,12 @@ * limitations under the License. */ #undef BIHASH_TYPE +#undef BIHASH_KVP_CACHE_SIZE +#undef BIHASH_KVP_PER_PAGE #define BIHASH_TYPE _24_8 #define BIHASH_KVP_PER_PAGE 4 +#define BIHASH_KVP_CACHE_SIZE 3 #ifndef __included_bihash_24_8_h__ #define __included_bihash_24_8_h__ diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h index 48079e0a..107bcace 100644 --- a/src/vppinfra/bihash_48_8.h +++ b/src/vppinfra/bihash_48_8.h @@ -14,9 +14,12 @@ */ #undef BIHASH_TYPE +#undef BIHASH_KVP_CACHE_SIZE +#undef BIHASH_KVP_PER_PAGE #define BIHASH_TYPE _48_8 #define BIHASH_KVP_PER_PAGE 4 +#define BIHASH_KVP_CACHE_SIZE 2 #ifndef __included_bihash_48_8_h__ #define __included_bihash_48_8_h__ diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index 68049351..f81002d6 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -13,9 +13,12 @@ * limitations under the License. */ #undef BIHASH_TYPE +#undef BIHASH_KVP_CACHE_SIZE +#undef BIHASH_KVP_PER_PAGE #define BIHASH_TYPE _8_8 #define BIHASH_KVP_PER_PAGE 4 +#define BIHASH_KVP_CACHE_SIZE 5 #ifndef __included_bihash_8_8_h__ #define __included_bihash_8_8_h__ diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 004e8a9a..e3a5759d 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -19,12 +19,15 @@ void BV (clib_bihash_init) (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size) { void *oldheap; + int i; nbuckets = 1 << (max_log2 (nbuckets)); h->name = (u8 *) name; h->nbuckets = nbuckets; h->log2_nbuckets = max_log2 (nbuckets); + h->cache_hits = 0; + h->cache_misses = 0; h->mheap = mheap_alloc (0 /* use VM */ , memory_size); @@ -33,6 +36,9 @@ void BV (clib_bihash_init) h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES, CLIB_CACHE_LINE_BYTES); + for (i = 0; i < nbuckets; i++) + BV (clib_bihash_reset_cache) (h->buckets + i); + clib_mem_set_heap (oldheap); } @@ -87,10 +93,10 @@ BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v, } static inline void -BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) +BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b) { BVT (clib_bihash_value) * v; - clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8))); + BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8))); void *oldheap; BVT (clib_bihash_value) * working_copy; u32 thread_index = os_get_thread_index (); @@ -129,6 +135,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) clib_mem_set_heap (oldheap); + /* Turn off the cache */ + BV (clib_bihash_cache_enable_disable) (b, 0); + v = BV (clib_bihash_get_value) (h, b->offset); clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages)); @@ -235,7 +244,7 @@ int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add) { u32 bucket_index; - clib_bihash_bucket_t *b, tmp_b; + BVT (clib_bihash_bucket) * b, tmp_b; BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy; int rv = 0; int i, limit; @@ -276,6 +285,7 @@ int BV (clib_bihash_add_del) goto unlock; } + /* Note: this leaves the cache disabled */ BV (make_working_copy) (h, b); v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); @@ -405,19 +415,22 @@ expand_ok: BV (value_free) (h, v, old_log2_pages); unlock: + BV (clib_bihash_reset_cache) (b); + BV (clib_bihash_cache_enable_disable) (b, 1 /* enable */ ); CLIB_MEMORY_BARRIER (); h->writer_lock[0] = 0; return rv; } int BV (clib_bihash_search) - (const BVT (clib_bihash) * h, + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) { u64 hash; u32 bucket_index; BVT (clib_bihash_value) * v; - clib_bihash_bucket_t *b; + BVT (clib_bihash_kv) * kvp; + BVT (clib_bihash_bucket) * b; int i, limit; ASSERT (valuep); @@ -430,6 +443,22 @@ int BV (clib_bihash_search) if (b->offset == 0) return -1; + /* Check the cache, if currently enabled */ + if (PREDICT_TRUE (b->cache_lru & (1 << 15))) + { + limit = BIHASH_KVP_CACHE_SIZE; + kvp = b->cache; + for (i = 0; i < limit; i++) + { + if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key)) + { + *valuep = kvp[i]; + h->cache_hits++; + return 0; + } + } + } + hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); @@ -442,18 +471,50 @@ int BV (clib_bihash_search) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) { + u8 cache_slot; *valuep = v->kvp[i]; + + /* Shut off the cache */ + BV (clib_bihash_cache_enable_disable) (b, 0); + CLIB_MEMORY_BARRIER (); + + cache_slot = BV (clib_bihash_get_lru) (b); + b->cache[cache_slot] = v->kvp[i]; + BV (clib_bihash_update_lru) (b, cache_slot); + + /* Reenable the cache */ + BV (clib_bihash_cache_enable_disable) (b, 1); + h->cache_misses++; return 0; } } return -1; } +u8 *BV (format_bihash_lru) (u8 * s, va_list * args) +{ + int i; + BVT (clib_bihash_bucket) * b = va_arg (*args, BVT (clib_bihash_bucket) *); + u16 cache_lru = b->cache_lru; + + s = format (s, "cache %s, order ", cache_lru & (1 << 15) ? "on" : "off"); + + for (i = 0; i < BIHASH_KVP_CACHE_SIZE; i++) + s = format (s, "[%d] ", ((cache_lru >> (3 * i)) & 7)); + return (s); +} + +void +BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, u8 slot) +{ + BV (clib_bihash_update_lru) (b, slot); +} + u8 *BV (format_bihash) (u8 * s, va_list * args) { BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *); int verbose = va_arg (*args, int); - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; BVT (clib_bihash_value) * v; int i, j, k; u64 active_elements = 0; @@ -503,7 +564,8 @@ u8 *BV (format_bihash) (u8 * s, va_list * args) s = format (s, " %lld active elements\n", active_elements); s = format (s, " %d free lists\n", vec_len (h->freelists)); s = format (s, " %d linear search buckets\n", h->linear_buckets); - + s = format (s, " %lld cache hits, %lld cache misses\n", + h->cache_hits, h->cache_misses); return s; } @@ -511,7 +573,7 @@ void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h, void *callback, void *arg) { int i, j, k; - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; BVT (clib_bihash_value) * v; void (*fp) (BVT (clib_bihash_kv) *, void *) = callback; diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 4ea14ff0..feb6fb68 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -48,12 +48,10 @@ typedef struct BV (clib_bihash_value) }; } BVT (clib_bihash_value); -/* - * This is shared across all uses of the template, so it needs - * a "personal" #include recursion block - */ -#ifndef __defined_clib_bihash_bucket_t__ -#define __defined_clib_bihash_bucket_t__ +#if BIHASH_KVP_CACHE_SIZE > 5 +#error Requested KVP cache LRU data exceeds 16 bits +#endif + typedef struct { union @@ -62,36 +60,139 @@ typedef struct { u32 offset; u8 linear_search; - u8 pad[2]; u8 log2_pages; + u16 cache_lru; }; u64 as_u64; }; -} clib_bihash_bucket_t; -#endif /* __defined_clib_bihash_bucket_t__ */ + BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE]; +} BVT (clib_bihash_bucket); typedef struct { BVT (clib_bihash_value) * values; - clib_bihash_bucket_t *buckets; + BVT (clib_bihash_bucket) * buckets; volatile u32 *writer_lock; BVT (clib_bihash_value) ** working_copies; int *working_copy_lengths; - clib_bihash_bucket_t saved_bucket; + BVT (clib_bihash_bucket) saved_bucket; u32 nbuckets; u32 log2_nbuckets; u32 linear_buckets; u8 *name; + u64 cache_hits; + u64 cache_misses; + BVT (clib_bihash_value) ** freelists; void *mheap; } BVT (clib_bihash); -static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h, +static inline void +BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot) +{ + u16 value, tmp, mask; + u8 found_lru_pos; + u16 save_hi; + + if (BIHASH_KVP_CACHE_SIZE < 2) + return; + + ASSERT (slot < BIHASH_KVP_CACHE_SIZE); + + /* First, find the slot in cache_lru */ + mask = slot; + if (BIHASH_KVP_CACHE_SIZE > 1) + mask |= slot << 3; + if (BIHASH_KVP_CACHE_SIZE > 2) + mask |= slot << 6; + if (BIHASH_KVP_CACHE_SIZE > 3) + mask |= slot << 9; + if (BIHASH_KVP_CACHE_SIZE > 4) + mask |= slot << 12; + + value = b->cache_lru; + tmp = value ^ mask; + + /* Already the most-recently used? */ + if ((tmp & 7) == 0) + return; + + found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0; + if (BIHASH_KVP_CACHE_SIZE > 2) + found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos; + if (BIHASH_KVP_CACHE_SIZE > 3) + found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos; + if (BIHASH_KVP_CACHE_SIZE > 4) + found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos; + + ASSERT (found_lru_pos); + + /* create a mask to kill bits in or above slot */ + mask = 0xFFFF << found_lru_pos; + mask <<= found_lru_pos; + mask <<= found_lru_pos; + mask ^= 0xFFFF; + tmp = value & mask; + + /* Save bits above slot */ + mask ^= 0xFFFF; + mask <<= 3; + save_hi = value & mask; + + value = save_hi | (tmp << 3) | slot; + + b->cache_lru = value; +} + +void +BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, + u8 slot); + +static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b) +{ + return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7; +} + +static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b) +{ + u16 initial_lru_value; + + memset (b->cache, 0xff, sizeof (b->cache)); + + /* + * We'll want the cache to be loaded from slot 0 -> slot N, so + * the initial LRU order is reverse index order. + */ + if (BIHASH_KVP_CACHE_SIZE == 1) + initial_lru_value = 0; + else if (BIHASH_KVP_CACHE_SIZE == 2) + initial_lru_value = (0 << 3) | (1 << 0); + else if (BIHASH_KVP_CACHE_SIZE == 3) + initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0); + else if (BIHASH_KVP_CACHE_SIZE == 4) + initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0); + else if (BIHASH_KVP_CACHE_SIZE == 5) + initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0); + + b->cache_lru = initial_lru_value; +} + +static inline void BV (clib_bihash_cache_enable_disable) + (BVT (clib_bihash_bucket) * b, u8 enable) +{ + BVT (clib_bihash_bucket) tmp_b; + tmp_b.as_u64 = b->as_u64; + tmp_b.cache_lru &= 0x7FFF; + tmp_b.cache_lru |= enable << 15; + b->as_u64 = tmp_b.as_u64; +} + +static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h, uword offset) { u8 *hp = h->mheap; @@ -100,7 +201,7 @@ static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h, return (void *) vp; } -static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h, +static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h, void *v) { u8 *hp, *vp; @@ -119,7 +220,7 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h); int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add); -int BV (clib_bihash_search) (const BVT (clib_bihash) * h, +int BV (clib_bihash_search) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_v, BVT (clib_bihash_kv) * return_v); @@ -128,18 +229,19 @@ void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h, format_function_t BV (format_bihash); format_function_t BV (format_bihash_kvp); - +format_function_t BV (format_bihash_lru); static inline int BV (clib_bihash_search_inline) - (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result) { u64 hash; u32 bucket_index; BVT (clib_bihash_value) * v; - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; + BVT (clib_bihash_kv) * kvp; int i, limit; - hash = BV (clib_bihash_hash) (kvp); + hash = BV (clib_bihash_hash) (key_result); bucket_index = hash & (h->nbuckets - 1); b = &h->buckets[bucket_index]; @@ -147,6 +249,22 @@ static inline int BV (clib_bihash_search_inline) if (b->offset == 0) return -1; + /* Check the cache, if currently enabled */ + if (PREDICT_TRUE (b->cache_lru & (1 << 15))) + { + limit = BIHASH_KVP_CACHE_SIZE; + kvp = b->cache; + for (i = 0; i < limit; i++) + { + if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key)) + { + *key_result = kvp[i]; + h->cache_hits++; + return 0; + } + } + } + hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); @@ -159,9 +277,22 @@ static inline int BV (clib_bihash_search_inline) for (i = 0; i < limit; i++) { - if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key)) + if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key)) { - *kvp = v->kvp[i]; + u8 cache_slot; + *key_result = v->kvp[i]; + + /* Shut off the cache */ + BV (clib_bihash_cache_enable_disable) (b, 0); + CLIB_MEMORY_BARRIER (); + + cache_slot = BV (clib_bihash_get_lru) (b); + b->cache[cache_slot] = v->kvp[i]; + BV (clib_bihash_update_lru) (b, cache_slot); + + /* Reenable the cache */ + BV (clib_bihash_cache_enable_disable) (b, 1); + h->cache_misses++; return 0; } } @@ -169,13 +300,14 @@ static inline int BV (clib_bihash_search_inline) } static inline int BV (clib_bihash_search_inline_2) - (const BVT (clib_bihash) * h, + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) { u64 hash; u32 bucket_index; BVT (clib_bihash_value) * v; - clib_bihash_bucket_t *b; + BVT (clib_bihash_bucket) * b; + BVT (clib_bihash_kv) * kvp; int i, limit; ASSERT (valuep); @@ -188,6 +320,22 @@ static inline int BV (clib_bihash_search_inline_2) if (b->offset == 0) return -1; + /* Check the cache, if currently enabled */ + if (PREDICT_TRUE (b->cache_lru & (1 << 15))) + { + limit = BIHASH_KVP_CACHE_SIZE; + kvp = b->cache; + for (i = 0; i < limit; i++) + { + if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key)) + { + *valuep = kvp[i]; + h->cache_hits++; + return 0; + } + } + } + hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); @@ -201,14 +349,26 @@ static inline int BV (clib_bihash_search_inline_2) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) { + u8 cache_slot; *valuep = v->kvp[i]; + + /* Shut off the cache */ + BV (clib_bihash_cache_enable_disable) (b, 0); + CLIB_MEMORY_BARRIER (); + + cache_slot = BV (clib_bihash_get_lru) (b); + b->cache[cache_slot] = v->kvp[i]; + BV (clib_bihash_update_lru) (b, cache_slot); + + /* Reenable the cache */ + BV (clib_bihash_cache_enable_disable) (b, 1); + h->cache_misses++; return 0; } } return -1; } - #endif /* __included_bihash_template_h__ */ /** @endcond */ diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index 1e262430..589c815d 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -236,12 +236,45 @@ test_bihash (test_main_t * tm) return 0; } +clib_error_t * +test_bihash_cache (test_main_t * tm) +{ + u32 lru; + BVT (clib_bihash_bucket) _b, *b = &_b; + + BV (clib_bihash_reset_cache) (b); + + fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b); + + BV (clib_bihash_update_lru_not_inline) (b, 3); + + fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b); + + BV (clib_bihash_update_lru) (b, 1); + + fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b); + + lru = BV (clib_bihash_get_lru) (b); + + fformat (stdout, "least-recently-used is %d\n", lru); + + BV (clib_bihash_update_lru) (b, 4); + + fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b); + + lru = BV (clib_bihash_get_lru) (b); + + fformat (stdout, "least-recently-used is %d\n", lru); + + return 0; +} + clib_error_t * test_bihash_main (test_main_t * tm) { unformat_input_t *i = tm->input; clib_error_t *error; - int test_vec64 = 0; + int which = 0; while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) { @@ -261,7 +294,10 @@ test_bihash_main (test_main_t * tm) else if (unformat (i, "search %d", &tm->search_iter)) ; else if (unformat (i, "vec64")) - test_vec64 = 1; + which = 1; + else if (unformat (i, "cache")) + which = 2; + else if (unformat (i, "verbose")) tm->verbose = 1; else @@ -269,10 +305,23 @@ test_bihash_main (test_main_t * tm) format_unformat_error, i); } - if (test_vec64) - error = test_bihash_vec64 (tm); - else - error = test_bihash (tm); + switch (which) + { + case 0: + error = test_bihash (tm); + break; + + case 1: + error = test_bihash_vec64 (tm); + break; + + case 2: + error = test_bihash_cache (tm); + break; + + default: + return clib_error_return (0, "no such test?"); + } return error; } -- cgit 1.2.3-korg From b7f1faa7fbd4575f28766e552a73810c6de0ace3 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Tue, 29 Aug 2017 11:43:37 -0400 Subject: Add fixed-size, preallocated pool support Simply call pool_init_fixed(...) before using the pool. Note that fixed, preallocated pools live in individually-mmap'ed address segments, except for the free element bitmap. A large fixed pool can exceed 4gb. Fix tcp buffer allocator leak, remove broken assert Change-Id: I4421082e12a77c41c6e20f7747f3150dcd01fc26 Signed-off-by: Dave Barach --- src/svm/svm_fifo_segment.c | 2 +- src/vnet/session/application_interface.c | 19 +++++ src/vnet/session/session.c | 32 +++----- src/vnet/session/session_cli.c | 4 +- src/vnet/tcp/tcp.c | 24 +++--- src/vnet/tcp/tcp_output.c | 42 ++++++---- src/vppinfra.am | 26 +++--- src/vppinfra/bihash_24_8.h | 2 +- src/vppinfra/pool.c | 131 +++++++++++++++++++++++++++++++ src/vppinfra/pool.h | 119 +++++++++++++++++++++------- src/vppinfra/test_fpool.c | 69 ++++++++++++++++ src/vppinfra/tw_timer_16t_1w_2048sl.h | 1 + src/vppinfra/tw_timer_16t_2w_512sl.h | 3 +- src/vppinfra/tw_timer_1t_3w_1024sl_ov.h | 1 + src/vppinfra/tw_timer_2t_1w_2048sl.h | 1 + src/vppinfra/tw_timer_4t_3w_256sl.h | 1 + src/vppinfra/tw_timer_4t_3w_4sl_ov.h | 1 + src/vppinfra/tw_timer_template.c | 116 +++++++++++++++++++++++++-- src/vppinfra/tw_timer_template.h | 24 +++++- 19 files changed, 520 insertions(+), 98 deletions(-) create mode 100644 src/vppinfra/pool.c create mode 100644 src/vppinfra/test_fpool.c (limited to 'src/vppinfra/bihash_24_8.h') diff --git a/src/svm/svm_fifo_segment.c b/src/svm/svm_fifo_segment.c index 6600a423..97d9976b 100644 --- a/src/svm/svm_fifo_segment.c +++ b/src/svm/svm_fifo_segment.c @@ -461,7 +461,7 @@ svm_fifo_segment_free_fifo (svm_fifo_segment_private_t * s, svm_fifo_t * f, freelist_index = f->freelist_index; - ASSERT (freelist_index > 0 && freelist_index < vec_len (fsh->free_fifos)); + ASSERT (freelist_index < vec_len (fsh->free_fifos)); ssvm_lock_non_recursive (sh, 2); oldheap = ssvm_push_heap (sh); diff --git a/src/vnet/session/application_interface.c b/src/vnet/session/application_interface.c index 566a52d7..8dbc3a1a 100644 --- a/src/vnet/session/application_interface.c +++ b/src/vnet/session/application_interface.c @@ -207,11 +207,22 @@ unformat_vnet_uri (unformat_input_t * input, va_list * args) return 0; } +static u8 *cache_uri; +static session_type_t cache_sst; +static transport_endpoint_t *cache_tep; + int parse_uri (char *uri, session_type_t * sst, transport_endpoint_t * tep) { unformat_input_t _input, *input = &_input; + if (cache_uri && !strncmp (uri, (char *) cache_uri, vec_len (cache_uri))) + { + *sst = cache_sst; + *tep = *cache_tep; + return 0; + } + /* Make sure */ uri = (char *) format (0, "%s%c", uri, 0); @@ -224,6 +235,14 @@ parse_uri (char *uri, session_type_t * sst, transport_endpoint_t * tep) } unformat_free (input); + vec_free (cache_uri); + cache_uri = (u8 *) uri; + cache_sst = *sst; + if (cache_tep) + clib_mem_free (cache_tep); + cache_tep = clib_mem_alloc (sizeof (*tep)); + *cache_tep = *tep; + return 0; } diff --git a/src/vnet/session/session.c b/src/vnet/session/session.c index dcd141f1..17644e29 100644 --- a/src/vnet/session/session.c +++ b/src/vnet/session/session.c @@ -889,32 +889,24 @@ session_manager_main_enable (vlib_main_t * vm) session_vpp_event_queue_allocate (smm, i); /* Preallocate sessions */ - if (num_threads == 1) + if (smm->preallocated_sessions) { - for (i = 0; i < smm->preallocated_sessions; i++) + if (num_threads == 1) { - stream_session_t *ss __attribute__ ((unused)); - pool_get_aligned (smm->sessions[0], ss, CLIB_CACHE_LINE_BYTES); + pool_init_fixed (smm->sessions[0], smm->preallocated_sessions); } - - for (i = 0; i < smm->preallocated_sessions; i++) - pool_put_index (smm->sessions[0], i); - } - else - { - int j; - preallocated_sessions_per_worker = smm->preallocated_sessions / - (num_threads - 1); - - for (j = 1; j < num_threads; j++) + else { - for (i = 0; i < preallocated_sessions_per_worker; i++) + int j; + preallocated_sessions_per_worker = + (1.1 * (f64) smm->preallocated_sessions / + (f64) (num_threads - 1)); + + for (j = 1; j < num_threads; j++) { - stream_session_t *ss __attribute__ ((unused)); - pool_get_aligned (smm->sessions[j], ss, CLIB_CACHE_LINE_BYTES); + pool_init_fixed (smm->sessions[j], + preallocated_sessions_per_worker); } - for (i = 0; i < preallocated_sessions_per_worker; i++) - pool_put_index (smm->sessions[j], i); } } diff --git a/src/vnet/session/session_cli.c b/src/vnet/session/session_cli.c index 028dc9d8..d9f516be 100755 --- a/src/vnet/session/session_cli.c +++ b/src/vnet/session/session_cli.c @@ -115,8 +115,8 @@ unformat_stream_session_id (unformat_input_t * input, va_list * args) { *proto = TRANSPORT_PROTO_UDP; } - else if (unformat (input, "%U:%d->%U:%d", unformat_ip4_address, &lcl->ip4, - lcl_port, unformat_ip4_address, &rmt->ip4, rmt_port)) + if (unformat (input, "%U:%d->%U:%d", unformat_ip4_address, &lcl->ip4, + lcl_port, unformat_ip4_address, &rmt->ip4, rmt_port)) { *is_ip4 = 1; tuple_is_set = 1; diff --git a/src/vnet/tcp/tcp.c b/src/vnet/tcp/tcp.c index 0a826a52..a4c13084 100644 --- a/src/vnet/tcp/tcp.c +++ b/src/vnet/tcp/tcp.c @@ -1150,6 +1150,10 @@ tcp_timer_establish_handler (u32 conn_index) else { tc = tcp_connection_get (conn_index, vlib_get_thread_index ()); + /* note: the connection may have already disappeared */ + if (PREDICT_FALSE (tc == 0)) + return; + ASSERT (tc->state == TCP_STATE_SYN_RCVD); } tc->timers[TCP_TIMER_ESTABLISH] = TCP_TIMER_HANDLE_INVALID; @@ -1244,7 +1248,7 @@ tcp_main_enable (vlib_main_t * vm) vlib_thread_main_t *vtm = vlib_get_thread_main (); clib_error_t *error = 0; u32 num_threads; - int i, thread; + int thread; tcp_connection_t *tc __attribute__ ((unused)); u32 preallocated_connections_per_thread; @@ -1297,21 +1301,17 @@ tcp_main_enable (vlib_main_t * vm) } for (; thread < num_threads; thread++) { - for (i = 0; i < preallocated_connections_per_thread; i++) - pool_get (tm->connections[thread], tc); - - for (i = 0; i < preallocated_connections_per_thread; i++) - pool_put_index (tm->connections[thread], i); + if (preallocated_connections_per_thread) + pool_init_fixed (tm->connections[thread], + preallocated_connections_per_thread); } /* - * Preallocate half-open connections + * Use a preallocated half-open connection pool? */ - for (i = 0; i < tm->preallocated_half_open_connections; i++) - pool_get (tm->half_open_connections, tc); - - for (i = 0; i < tm->preallocated_half_open_connections; i++) - pool_put_index (tm->half_open_connections, i); + if (tm->preallocated_half_open_connections) + pool_init_fixed (tm->half_open_connections, + tm->preallocated_half_open_connections); /* Initialize per worker thread tx buffers (used for control messages) */ vec_validate (tm->tx_buffers, num_threads - 1); diff --git a/src/vnet/tcp/tcp_output.c b/src/vnet/tcp/tcp_output.c index 02555513..15a9dcb4 100644 --- a/src/vnet/tcp/tcp_output.c +++ b/src/vnet/tcp/tcp_output.c @@ -440,13 +440,16 @@ tcp_init_mss (tcp_connection_t * tc) always_inline int tcp_alloc_tx_buffers (tcp_main_t * tm, u8 thread_index, u32 n_free_buffers) { + u32 current_length = vec_len (tm->tx_buffers[thread_index]); + vec_validate (tm->tx_buffers[thread_index], - vec_len (tm->tx_buffers[thread_index]) + n_free_buffers - 1); + current_length + n_free_buffers - 1); _vec_len (tm->tx_buffers[thread_index]) = - vlib_buffer_alloc_from_free_list (vlib_get_main (), - tm->tx_buffers[thread_index], - n_free_buffers, - VLIB_BUFFER_DEFAULT_FREE_LIST_INDEX); + current_length + vlib_buffer_alloc_from_free_list (vlib_get_main (), + tm->tx_buffers + [thread_index], + n_free_buffers, + VLIB_BUFFER_DEFAULT_FREE_LIST_INDEX); /* buffer shortage, report failure */ if (vec_len (tm->tx_buffers[thread_index]) == 0) { @@ -1293,11 +1296,17 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn) if (is_syn) { tc = tcp_half_open_connection_get (index); + /* Note: the connection may have transitioned to ESTABLISHED... */ + if (PREDICT_FALSE (tc == 0)) + return; tc->timers[TCP_TIMER_RETRANSMIT_SYN] = TCP_TIMER_HANDLE_INVALID; } else { tc = tcp_connection_get (index, thread_index); + /* Note: the connection may have been closed and pool_put */ + if (PREDICT_FALSE (tc == 0)) + return; tc->timers[TCP_TIMER_RETRANSMIT] = TCP_TIMER_HANDLE_INVALID; } @@ -1332,25 +1341,27 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn) TCP_EVT_DBG (TCP_EVT_CC_EVT, tc, 1); - /* Send one segment */ + /* Send one segment. Note that n_bytes may be zero due to buffer shortfall */ n_bytes = tcp_prepare_retransmit_segment (tc, 0, tc->snd_mss, &b); - ASSERT (n_bytes); - bi = vlib_get_buffer_index (vm, b); + /* TODO be less aggressive about this */ scoreboard_clear (&tc->sack_sb); if (n_bytes == 0) { - clib_warning ("could not retransmit anything"); - clib_warning ("%U", format_tcp_connection, tc, 2); - + if (b) + { + clib_warning ("retransmit fail: %U", format_tcp_connection, tc, + 2); + ASSERT (tc->rto_boff > 1 && tc->snd_una == tc->snd_congestion); + } /* Try again eventually */ tcp_retransmit_timer_set (tc); - ASSERT (0 || (tc->rto_boff > 1 - && tc->snd_una == tc->snd_congestion)); return; } + bi = vlib_get_buffer_index (vm, b); + /* For first retransmit, record timestamp (Eifel detection RFC3522) */ if (tc->rto_boff == 1) tc->snd_rxt_ts = tcp_time_now (); @@ -1378,7 +1389,10 @@ tcp_timer_retransmit_handler_i (u32 index, u8 is_syn) tc->rto = clib_min (tc->rto << 1, TCP_RTO_MAX); if (PREDICT_FALSE (tcp_get_free_buffer_index (tm, &bi))) - return; + { + clib_warning ("tcp_get_free_buffer_index FAIL"); + return; + } b = vlib_get_buffer (vm, bi); tcp_init_buffer (vm, b); tcp_push_hdr_i (tc, b, tc->state, 1); diff --git a/src/vppinfra.am b/src/vppinfra.am index 533bacd6..8f01114c 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -18,10 +18,11 @@ TESTS = if ENABLE_TESTS TESTS += test_bihash_template \ test_dlist \ - test_elog \ test_elf \ + test_elog \ test_fifo \ test_format \ + test_fpool \ test_hash \ test_heap \ test_longjmp \ @@ -42,17 +43,16 @@ TESTS += test_bihash_template \ test_zvec endif -TESTS += test_bihash_template - noinst_PROGRAMS = $(TESTS) check_PROGRAMS = $(TESTS) test_bihash_template_SOURCES = vppinfra/test_bihash_template.c test_dlist_SOURCES = vppinfra/test_dlist.c -test_elog_SOURCES = vppinfra/test_elog.c test_elf_SOURCES = vppinfra/test_elf.c +test_elog_SOURCES = vppinfra/test_elog.c test_fifo_SOURCES = vppinfra/test_fifo.c test_format_SOURCES = vppinfra/test_format.c +test_fpool_SOURCES = vppinfra/test_fpool.c test_hash_SOURCES = vppinfra/test_hash.c test_heap_SOURCES = vppinfra/test_heap.c test_longjmp_SOURCES = vppinfra/test_longjmp.c @@ -61,8 +61,8 @@ test_md5_SOURCES = vppinfra/test_md5.c test_mheap_SOURCES = vppinfra/test_mheap.c test_pool_iterate_SOURCES = vppinfra/test_pool_iterate.c test_ptclosure_SOURCES = vppinfra/test_ptclosure.c -test_random_SOURCES = vppinfra/test_random.c test_random_isaac_SOURCES = vppinfra/test_random_isaac.c +test_random_SOURCES = vppinfra/test_random.c test_serialize_SOURCES = vppinfra/test_serialize.c test_slist_SOURCES = vppinfra/test_slist.c test_socket_SOURCES = vppinfra/test_socket.c @@ -76,10 +76,11 @@ test_zvec_SOURCES = vppinfra/test_zvec.c # So we'll need -DDEBUG to enable ASSERTs test_bihash_template_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_dlist_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG -test_elog_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_format_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG +test_fpool_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_hash_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_heap_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_longjmp_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG @@ -90,9 +91,9 @@ test_pool_iterate_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_ptclosure_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_random_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_random_isaac_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG -test_socket_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_serialize_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_slist_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG +test_socket_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_time_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_timing_wheel_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_tw_timer_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG @@ -101,10 +102,11 @@ test_zvec_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_bihash_template_LDADD = libvppinfra.la test_dlist_LDADD = libvppinfra.la -test_elog_LDADD = libvppinfra.la test_elf_LDADD = libvppinfra.la +test_elog_LDADD = libvppinfra.la test_fifo_LDADD = libvppinfra.la test_format_LDADD = libvppinfra.la +test_fpool_LDADD = libvppinfra.la test_hash_LDADD = libvppinfra.la test_heap_LDADD = libvppinfra.la test_longjmp_LDADD = libvppinfra.la @@ -113,8 +115,8 @@ test_md5_LDADD = libvppinfra.la test_mheap_LDADD = libvppinfra.la test_pool_iterate_LDADD = libvppinfra.la test_ptclosure_LDADD = libvppinfra.la -test_random_LDADD = libvppinfra.la test_random_isaac_LDADD = libvppinfra.la +test_random_LDADD = libvppinfra.la test_serialize_LDADD = libvppinfra.la test_slist_LDADD = libvppinfra.la test_socket_LDADD = libvppinfra.la @@ -126,10 +128,11 @@ test_zvec_LDADD = libvppinfra.la test_bihash_template_LDFLAGS = -static test_dlist_LDFLAGS = -static -test_elog_LDFLAGS = -static test_elf_LDFLAGS = -static +test_elog_LDFLAGS = -static test_fifo_LDFLAGS = -static test_format_LDFLAGS = -static +test_fpool_LDFLAGS = -static test_hash_LDFLAGS = -static test_heap_LDFLAGS = -static test_longjmp_LDFLAGS = -static @@ -138,8 +141,8 @@ test_md5_LDFLAGS = -static test_mheap_LDFLAGS = -static test_pool_iterate_LDFLAGS = -static test_ptclosure_LDFLAGS = -static -test_random_LDFLAGS = -static test_random_isaac_LDFLAGS = -static +test_random_LDFLAGS = -static test_serialize_LDFLAGS = -static test_slist_LDFLAGS = -static test_socket_LDFLAGS = -static @@ -247,6 +250,7 @@ CLIB_CORE = \ vppinfra/fifo.c \ vppinfra/fheap.c \ vppinfra/format.c \ + vppinfra/pool.c \ vppinfra/graph.c \ vppinfra/hash.c \ vppinfra/heap.c \ diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h index d0be028c..173168fe 100644 --- a/src/vppinfra/bihash_24_8.h +++ b/src/vppinfra/bihash_24_8.h @@ -18,7 +18,7 @@ #define BIHASH_TYPE _24_8 #define BIHASH_KVP_PER_PAGE 4 -#define BIHASH_KVP_CACHE_SIZE 3 +#define BIHASH_KVP_CACHE_SIZE 0 #ifndef __included_bihash_24_8_h__ #define __included_bihash_24_8_h__ diff --git a/src/vppinfra/pool.c b/src/vppinfra/pool.c new file mode 100644 index 00000000..ed83b41a --- /dev/null +++ b/src/vppinfra/pool.c @@ -0,0 +1,131 @@ +/* + * 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. + */ +/* + Copyright (c) 2001, 2002, 2003, 2004 Eliot Dresselhaus + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +*/ + +#include + +void +_pool_init_fixed (void **pool_ptr, u32 elt_size, u32 max_elts) +{ + u8 *mmap_base; + u64 vector_size; + u64 free_index_size; + u64 total_size; + u64 page_size; + pool_header_t *fh; + vec_header_t *vh; + u8 *v; + u32 *fi; + u32 i; + u32 set_bits; + + ASSERT (elt_size); + ASSERT (max_elts); + + vector_size = pool_aligned_header_bytes + vec_header_bytes (0) + + (u64) elt_size *max_elts; + + free_index_size = vec_header_bytes (0) + sizeof (u32) * max_elts; + + /* Round up to a cache line boundary */ + vector_size = (vector_size + CLIB_CACHE_LINE_BYTES - 1) + & ~(CLIB_CACHE_LINE_BYTES - 1); + + free_index_size = (free_index_size + CLIB_CACHE_LINE_BYTES - 1) + & ~(CLIB_CACHE_LINE_BYTES - 1); + + total_size = vector_size + free_index_size; + + /* Round up to an even number of pages */ + page_size = clib_mem_get_page_size (); + total_size = (total_size + page_size - 1) & ~(page_size - 1); + + /* mmap demand zero memory */ + + mmap_base = mmap (0, total_size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + + if (mmap_base == MAP_FAILED) + { + clib_unix_warning ("mmap"); + *pool_ptr = 0; + } + + /* First comes the pool header */ + fh = (pool_header_t *) mmap_base; + /* Find the user vector pointer */ + v = (u8 *) (mmap_base + pool_aligned_header_bytes); + /* Finally, the vector header */ + vh = _vec_find (v); + + fh->free_bitmap = 0; /* No free elts (yet) */ + fh->max_elts = max_elts; + fh->mmap_base = mmap_base; + fh->mmap_size = total_size; + + vh->len = max_elts; + + /* Build the free-index vector */ + vh = (vec_header_t *) (v + vector_size); + vh->len = max_elts; + fi = (u32 *) (vh + 1); + + fh->free_indices = fi; + + /* Set the entire free bitmap */ + clib_bitmap_alloc (fh->free_bitmap, max_elts); + memset (fh->free_bitmap, 0xff, vec_len (fh->free_bitmap) * sizeof (uword)); + + /* Clear any extraneous set bits */ + set_bits = vec_len (fh->free_bitmap) * BITS (uword); + + for (i = max_elts; i < set_bits; i++) + fh->free_bitmap = clib_bitmap_set (fh->free_bitmap, i, 0); + + /* Create the initial free vector */ + for (i = 0; i < max_elts; i++) + fi[i] = (max_elts - 1) - i; + + *pool_ptr = v; +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/pool.h b/src/vppinfra/pool.h index 56536b77..62d5b54e 100644 --- a/src/vppinfra/pool.h +++ b/src/vppinfra/pool.h @@ -56,6 +56,16 @@ typedef struct /** Vector of free indices. One element for each set bit in bitmap. */ u32 *free_indices; + + /* The following fields are set for fixed-size, preallocated pools */ + + /** Maximum size of the pool, in elements */ + u32 max_elts; + + /** mmap segment info: base + length */ + u8 *mmap_base; + u64 mmap_size; + } pool_header_t; /** Align pool header so that pointers are naturally aligned. */ @@ -69,6 +79,15 @@ pool_header (void *v) return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *)); } +extern void _pool_init_fixed (void **, u32, u32); +extern void fpool_free (void *); + +/** initialize a fixed-size, preallocated pool */ +#define pool_init_fixed(pool,max_elts) \ +{ \ + _pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts); \ +} + /** Validate a pool */ always_inline void pool_validate (void *v) @@ -98,7 +117,7 @@ pool_header_validate_index (void *v, uword index) do { \ uword __pool_validate_index = (i); \ vec_validate_ha ((v), __pool_validate_index, \ - pool_aligned_header_bytes, /* align */ 0); \ + pool_aligned_header_bytes, /* align */ 0); \ pool_header_validate_index ((v), __pool_validate_index); \ } while (0) @@ -166,34 +185,40 @@ pool_free_elts (void *v) First search free list. If nothing is free extend vector of objects. */ -#define pool_get_aligned(P,E,A) \ -do { \ - pool_header_t * _pool_var (p) = pool_header (P); \ - uword _pool_var (l); \ - \ - _pool_var (l) = 0; \ - if (P) \ - _pool_var (l) = vec_len (_pool_var (p)->free_indices); \ - \ - if (_pool_var (l) > 0) \ - { \ - /* Return free element from free list. */ \ +#define pool_get_aligned(P,E,A) \ +do { \ + pool_header_t * _pool_var (p) = pool_header (P); \ + uword _pool_var (l); \ + \ + _pool_var (l) = 0; \ + if (P) \ + _pool_var (l) = vec_len (_pool_var (p)->free_indices); \ + \ + if (_pool_var (l) > 0) \ + { \ + /* Return free element from free list. */ \ uword _pool_var (i) = _pool_var (p)->free_indices[_pool_var (l) - 1]; \ - (E) = (P) + _pool_var (i); \ - _pool_var (p)->free_bitmap = \ + (E) = (P) + _pool_var (i); \ + _pool_var (p)->free_bitmap = \ clib_bitmap_andnoti (_pool_var (p)->free_bitmap, _pool_var (i)); \ - _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1; \ - } \ - else \ - { \ - /* Nothing on free list, make a new element and return it. */ \ - P = _vec_resize (P, \ - /* length_increment */ 1, \ + _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1; \ + } \ + else \ + { \ + /* fixed-size, preallocated pools cannot expand */ \ + if ((P) && _pool_var(p)->max_elts) \ + { \ + clib_warning ("can't expand fixed-size pool"); \ + os_out_of_memory(); \ + } \ + /* Nothing on free list, make a new element and return it. */ \ + P = _vec_resize (P, \ + /* length_increment */ 1, \ /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \ - pool_aligned_header_bytes, \ - /* align */ (A)); \ - E = vec_end (P) - 1; \ - } \ + pool_aligned_header_bytes, \ + /* align */ (A)); \ + E = vec_end (P) - 1; \ + } \ } while (0) /** Allocate an object E from a pool P (unspecified alignment). */ @@ -207,7 +232,11 @@ do { \ \ _pool_var (l) = 0; \ if (P) \ + { \ + if (_pool_var (p)->max_elts) \ + return 0; \ _pool_var (l) = vec_len (_pool_var (p)->free_indices); \ + } \ \ /* Free elements, certainly won't expand */ \ if (_pool_var (l) > 0) \ @@ -248,7 +277,16 @@ do { \ /* Add element to free bitmap and to free list. */ \ _pool_var (p)->free_bitmap = \ clib_bitmap_ori (_pool_var (p)->free_bitmap, _pool_var (l)); \ - vec_add1 (_pool_var (p)->free_indices, _pool_var (l)); \ + /* Preallocated pool? */ \ + if (_pool_var (p)->max_elts) \ + { \ + ASSERT(_pool_var(l) < _pool_var (p)->max_elts); \ + _pool_var(p)->free_indices[_vec_len(_pool_var(p)->free_indices)] = \ + _pool_var(l); \ + _vec_len(_pool_var(p)->free_indices) += 1; \ + } \ + else \ + vec_add1 (_pool_var (p)->free_indices, _pool_var (l)); \ } while (0) /** Free pool element with given index. */ @@ -262,6 +300,17 @@ do { \ #define pool_alloc_aligned(P,N,A) \ do { \ pool_header_t * _p; \ + \ + if ((P)) \ + { \ + _p = pool_header (P); \ + if (_p->max_elts) \ + { \ + clib_warning ("Can't expand fixed-size pool"); \ + os_out_of_memory(); \ + } \ + } \ + \ (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]), \ pool_aligned_header_bytes, \ (A)); \ @@ -281,8 +330,20 @@ _pool_free (void *v) if (!v) return v; clib_bitmap_free (p->free_bitmap); - vec_free (p->free_indices); - vec_free_h (v, pool_aligned_header_bytes); + + if (p->max_elts) + { + int rv; + + rv = munmap (p->mmap_base, p->mmap_size); + if (rv) + clib_unix_warning ("munmap"); + } + else + { + vec_free (p->free_indices); + vec_free_h (v, pool_aligned_header_bytes); + } return 0; } diff --git a/src/vppinfra/test_fpool.c b/src/vppinfra/test_fpool.c new file mode 100644 index 00000000..e2d67f16 --- /dev/null +++ b/src/vppinfra/test_fpool.c @@ -0,0 +1,69 @@ +/* + * 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. +*/ + +#include + +/* can be a very large size */ +#define NELTS 1024 + +int +main (int argc, char *argv[]) +{ + u32 *junk = 0; + int i; + u32 *tp = 0; + u32 *indices = 0; + + clib_mem_init (0, 3ULL << 30); + + vec_validate (indices, NELTS - 1); + _vec_len (indices) = 0; + + pool_init_fixed (tp, NELTS); + + for (i = 0; i < NELTS; i++) + { + pool_get (tp, junk); + vec_add1 (indices, junk - tp); + *junk = i; + } + + for (i = 0; i < NELTS; i++) + { + junk = pool_elt_at_index (tp, indices[i]); + ASSERT (*junk == i); + } + + fformat (stdout, "%d pool elts before deletes\n", pool_elts (tp)); + + pool_put_index (tp, indices[12]); + pool_put_index (tp, indices[43]); + + fformat (stdout, "%d pool elts after deletes\n", pool_elts (tp)); + + pool_validate (tp); + + pool_free (tp); + return 0; +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_16t_1w_2048sl.h b/src/vppinfra/tw_timer_16t_1w_2048sl.h index 66cf7d37..761646b3 100644 --- a/src/vppinfra/tw_timer_16t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_16t_1w_2048sl.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 diff --git a/src/vppinfra/tw_timer_16t_2w_512sl.h b/src/vppinfra/tw_timer_16t_2w_512sl.h index 00587b8e..029f529d 100644 --- a/src/vppinfra/tw_timer_16t_2w_512sl.h +++ b/src/vppinfra/tw_timer_16t_2w_512sl.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 2 #define TW_SLOTS_PER_RING 512 @@ -36,7 +37,7 @@ #define LOG2_TW_TIMERS_PER_OBJECT 4 #define TW_SUFFIX _16t_2w_512sl #define TW_FAST_WHEEL_BITMAP 0 -#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 1 #include diff --git a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h index e5e4cc19..0b455e02 100644 --- a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h +++ b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 1024 diff --git a/src/vppinfra/tw_timer_2t_1w_2048sl.h b/src/vppinfra/tw_timer_2t_1w_2048sl.h index 98b548b3..6ae86688 100644 --- a/src/vppinfra/tw_timer_2t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_2t_1w_2048sl.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 diff --git a/src/vppinfra/tw_timer_4t_3w_256sl.h b/src/vppinfra/tw_timer_4t_3w_256sl.h index 07203de8..16c41bcd 100644 --- a/src/vppinfra/tw_timer_4t_3w_256sl.h +++ b/src/vppinfra/tw_timer_4t_3w_256sl.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 256 diff --git a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h index 20a01d05..845ffeac 100644 --- a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h +++ b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h @@ -27,6 +27,7 @@ #undef TW_OVERFLOW_VECTOR #undef TW_FAST_WHEEL_BITMAP #undef TW_TIMER_ALLOW_DUPLICATE_STOP +#undef TW_START_STOP_TRACE_SIZE #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 4 diff --git a/src/vppinfra/tw_timer_template.c b/src/vppinfra/tw_timer_template.c index c0a9685a..aba00142 100644 --- a/src/vppinfra/tw_timer_template.c +++ b/src/vppinfra/tw_timer_template.c @@ -18,6 +18,87 @@ * * */ +#if TW_START_STOP_TRACE_SIZE > 0 + +void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id, + u32 pool_index, u32 handle) +{ + TWT (trace) * t = &tw->traces[tw->trace_index]; + + t->timer_id = timer_id; + t->pool_index = pool_index; + t->handle = handle; + + tw->trace_index++; + if (tw->trace_index == TW_START_STOP_TRACE_SIZE) + { + tw->trace_index = 0; + tw->trace_wrapped++; + } +} + +void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle) +{ + u32 i, start_pos; + TWT (trace) * t; + char *s = "bogus!"; + + /* reverse search for the supplied handle */ + + start_pos = tw->trace_index; + if (start_pos == 0) + start_pos = TW_START_STOP_TRACE_SIZE - 1; + else + start_pos--; + + for (i = start_pos; i > 0; i--) + { + t = &tw->traces[i]; + if (t->handle == handle) + { + switch (t->timer_id) + { + case 0xFF: + s = "stopped"; + break; + case 0xFE: + s = "expired"; + break; + default: + s = "started"; + break; + } + fformat (stderr, "handle 0x%x (%d) %s at trace %d\n", + handle, handle, s, i); + } + } + if (tw->trace_wrapped > 0) + { + for (i = TW_START_STOP_TRACE_SIZE; i >= tw->trace_index; i--) + { + t = &tw->traces[i]; + if (t->handle == handle) + { + switch (t->timer_id) + { + case 0xFF: + s = "stopped"; + break; + case 0xFE: + s = "expired"; + break; + default: + s = "started"; + break; + } + fformat (stderr, "handle 0x%x (%d) %s at trace %d\n", + handle, handle, s, i); + } + } + } +} +#endif /* TW_START_STOP_TRACE_SIZE > 0 */ + static inline u32 TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id) { @@ -127,6 +208,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, t->expiration_time = tw->current_tick + interval; ts = &tw->overflow; timer_addhead (tw->timers, ts->head_index, t - tw->timers); +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers); +#endif return t - tw->timers; } #endif @@ -177,7 +261,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_ring_offset]; timer_addhead (tw->timers, ts->head_index, t - tw->timers); - +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers); +#endif return t - tw->timers; } #endif @@ -193,7 +279,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset]; timer_addhead (tw->timers, ts->head_index, t - tw->timers); - +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers); +#endif return t - tw->timers; } #else @@ -208,6 +296,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, #if TW_FAST_WHEEL_BITMAP tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap, fast_ring_offset, 1); +#endif +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers); #endif return t - tw->timers; } @@ -265,6 +356,9 @@ void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) if (pool_is_free_index (tw->timers, handle)) return; #endif +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, ~0, ~0, handle); +#endif t = pool_elt_at_index (tw->timers, handle); @@ -302,6 +396,7 @@ TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, tw->timer_interval = timer_interval_in_seconds; tw->ticks_per_second = 1.0 / timer_interval_in_seconds; tw->first_expires_tick = ~0ULL; + vec_validate (tw->expired_timer_handles, 0); _vec_len (tw->expired_timer_handles) = 0; @@ -476,6 +571,9 @@ static inline new_glacier_ring_offset == 0)) { vec_add1 (callback_vector, t->user_handle); +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers); +#endif pool_put (tw->timers, t); } /* Timer moves to the glacier ring */ @@ -536,6 +634,9 @@ static inline t->fast_ring_offset == 0)) { vec_add1 (callback_vector, t->user_handle); +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers); +#endif pool_put (tw->timers, t); } /* Timer expires during slow-wheel tick 0 */ @@ -587,6 +688,9 @@ static inline if (PREDICT_FALSE (t->fast_ring_offset == 0)) { vec_add1 (callback_vector, t->user_handle); +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers); +#endif pool_put (tw->timers, t); } else /* typical case */ @@ -620,6 +724,9 @@ static inline t = pool_elt_at_index (tw->timers, next_index); next_index = t->next; vec_add1 (callback_vector, t->user_handle); +#if TW_START_STOP_TRACE_SIZE > 0 + TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers); +#endif pool_put (tw->timers, t); } @@ -628,10 +735,7 @@ static inline { /* The callback is optional. We return the u32 * handle vector */ if (tw->expired_timer_callback) - { - tw->expired_timer_callback (callback_vector); - _vec_len (callback_vector) = 0; - } + tw->expired_timer_callback (callback_vector); tw->expired_timer_handles = callback_vector; } diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h index 0404e3f4..0217644d 100644 --- a/src/vppinfra/tw_timer_template.h +++ b/src/vppinfra/tw_timer_template.h @@ -170,6 +170,13 @@ typedef enum } tw_ring_index_t; #endif /* __defined_tw_timer_wheel_slot__ */ +typedef CLIB_PACKED (struct + { + u8 timer_id; + u32 pool_index; + u32 handle; + }) TWT (trace); + typedef struct { /** Timer pool */ @@ -211,11 +218,20 @@ typedef struct /** expired timer callback, receives a vector of handles */ void (*expired_timer_callback) (u32 * expired_timer_handles); - /** vector of expired timers */ + /** vectors of expired timers */ u32 *expired_timer_handles; /** maximum expirations */ u32 max_expirations; + + /** current trace index */ +#if TW_START_STOP_TRACE_SIZE > 0 + /* Start/stop/expire tracing */ + u32 trace_index; + u32 trace_wrapped; + TWT (trace) traces[TW_START_STOP_TRACE_SIZE]; +#endif + } TWT (tw_timer_wheel); u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, @@ -236,6 +252,12 @@ u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw); #endif +#if TW_START_STOP_TRACE_SIZE > 0 +void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle); +void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id, + u32 pool_index, u32 handle); +#endif + /* * fd.io coding-style-patch-verification: ON * -- cgit 1.2.3-korg