summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorDave Barach <dave@barachs.net>2018-02-23 07:45:36 -0500
committerDave Barach <dave@barachs.net>2018-02-23 08:02:18 -0500
commit30765e77ac98913abefbdb9e8325a2b3f1e11082 (patch)
treee6d4c0d579913ad6dee9148dc5da72d660612312 /src
parent4ef4226282685a049aad439080ca5478da09ac06 (diff)
Add prefetch inlines, update bi-hash doc tags
Change-Id: I2e9d01ccba5288e89b886464436097d3cb7d2d18 Signed-off-by: Dave Barach <dave@barachs.net>
Diffstat (limited to 'src')
-rw-r--r--src/vppinfra/bihash_doc.h49
-rw-r--r--src/vppinfra/bihash_template.h53
2 files changed, 90 insertions, 12 deletions
diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h
index e6ab9db6d30..a7e70e9695c 100644
--- a/src/vppinfra/bihash_doc.h
+++ b/src/vppinfra/bihash_doc.h
@@ -78,7 +78,9 @@ typedef struct
u8 *name; /**< hash table name */
BVT (clib_bihash_value) ** freelists;
/**< power of two freelist vector */
- void *mheap; /**< clib memory heap */
+ uword alloc_arena; /**< memory allocation arena */
+ uword alloc_arena_next; /**< first available mem chunk */
+ uword alloc_arena_size; /**< size of the arena */
} clib_bihash_t;
/** Get pointer to value page given its clib mheap offset */
@@ -117,16 +119,51 @@ void clib_bihash_free (clib_bihash * h);
int clib_bihash_add_del (clib_bihash * h, clib_bihash_kv * add_v, int is_add);
+/** Search a bi-hash table, use supplied hash code
+
+ @param h - the bi-hash table to search
+ @param hash - the hash code
+ @param in_out_kv - (key,value) pair containing the search key
+ @returns 0 on success (with in_out_kv set), < 0 on error
+*/
+int clib_bihash_search_inline_with_hash
+ (clib_bihash * h, u64 hash, clib_bihash_kv * in_out_kv);
+
/** Search a bi-hash table
@param h - the bi-hash table to search
- @param search_v - (key,value) pair containing the search key
- @param return_v - (key,value) pair which matches search_v.key
- @returns 0 on success (with return_v set), < 0 on error
+ @param in_out_kv - (key,value) pair containing the search key
+ @returns 0 on success (with in_out_kv set), < 0 on error
+*/
+int clib_bihash_search_inline (clib_bihash * h, clib_bihash_kv * in_out_kv);
+
+/** Prefetch a bi-hash bucket given a hash code
+
+ @param h - the bi-hash table to search
+ @param hash - the hash code
+ @note see also clib_bihash_hash to compute the code
*/
-int clib_bihash_search (clib_bihash * h,
- clib_bihash_kv * search_v, clib_bihash_kv * return_v);
+void clib_bihash_prefetch_bucket (clib_bihash * h, u64 hash);
+/** Prefetch bi-hash (key,value) data given a hash code
+
+ @param h - the bi-hash table to search
+ @param hash - the hash code
+ @note assumes that the bucket has been prefetched, see
+ clib_bihash_prefetch_bucket
+*/
+void clib_bihash_prefetch_data (clib_bihash * h, u64 hash);
+
+/** Search a bi-hash table
+
+ @param h - the bi-hash table to search
+ @param search_key - (key,value) pair containing the search key
+ @param valuep - (key,value) set to search result
+ @returns 0 on success (with valuep set), < 0 on error
+ @note used in situations where key modification is not desired
+*/
+int clib_bihash_search_inline_2
+ (clib_bihash * h, clib_bihash_kv * search_key, clib_bihash_kv * valuep);
/** Visit active (key,value) pairs in a bi-hash table
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 81d9ffad41e..2101d44defe 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -26,6 +26,7 @@
#include <vppinfra/heap.h>
#include <vppinfra/format.h>
#include <vppinfra/pool.h>
+#include <vppinfra/cache.h>
#ifndef BIHASH_TYPE
#error BIHASH_TYPE not defined
@@ -91,7 +92,7 @@ typedef struct
BVT (clib_bihash_value) ** freelists;
/*
- * Backing store allocation. Since bihash mananges its own
+ * Backing store allocation. Since bihash manages its own
* freelists, we simple dole out memory at alloc_arena_next.
*/
uword alloc_arena;
@@ -269,10 +270,9 @@ 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)
- (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
+static inline int BV (clib_bihash_search_inline_with_hash)
+ (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result)
{
- u64 hash;
u32 bucket_index;
BVT (clib_bihash_value) * v;
BVT (clib_bihash_bucket) * b;
@@ -281,8 +281,6 @@ static inline int BV (clib_bihash_search_inline)
#endif
int i, limit;
- hash = BV (clib_bihash_hash) (key_result);
-
bucket_index = hash & (h->nbuckets - 1);
b = &h->buckets[bucket_index];
@@ -343,6 +341,49 @@ static inline int BV (clib_bihash_search_inline)
return -1;
}
+static inline int BV (clib_bihash_search_inline)
+ (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
+{
+ u64 hash;
+
+ hash = BV (clib_bihash_hash) (key_result);
+
+ return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result);
+}
+
+static inline void BV (clib_bihash_prefetch_bucket)
+ (BVT (clib_bihash) * h, u64 hash)
+{
+ u32 bucket_index;
+ BVT (clib_bihash_bucket) * b;
+
+ bucket_index = hash & (h->nbuckets - 1);
+ b = &h->buckets[bucket_index];
+
+ CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, READ);
+}
+
+static inline void BV (clib_bihash_prefetch_data)
+ (BVT (clib_bihash) * h, u64 hash)
+{
+ u32 bucket_index;
+ BVT (clib_bihash_value) * v;
+ BVT (clib_bihash_bucket) * b;
+
+ bucket_index = hash & (h->nbuckets - 1);
+ b = &h->buckets[bucket_index];
+
+ if (PREDICT_FALSE (b->offset == 0))
+ return;
+
+ hash >>= h->log2_nbuckets;
+ v = BV (clib_bihash_get_value) (h, b->offset);
+
+ v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
+
+ CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, READ);
+}
+
static inline int BV (clib_bihash_search_inline_2)
(BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
.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. AUTOMAKE_OPTIONS = foreign ACLOCAL_AMFLAGS = -I m4 AM_LIBTOOLFLAGS = --quiet AM_CXXFLAGS = -Wall -std=gnu++11 -I${top_srcdir} -I${top_builddir}/vpp-api/vapi/ -I$(top_srcdir)/vpp-api/ -I${libdir}/../include -O0 AM_LDFLAGS = -shared -no-undefined bin_PROGRAMS = noinst_LTLIBRARIES = CLEANDIRS = lib_LTLIBRARIES = libvom.la libvom_la_DEPENDENCIES = libvom_la_LIBADD = \ $(top_builddir)/vpp-api/vapi/libvapiclient.la \ -lpthread \ -lboost_thread \ $(BOOST_SYSTEM_LIB) \ $(BOOST_FILESYSTEM_LIB) \ $(BOOST_ASIO_LIB) \ -lm -lrt libvom_la_SOURCES = \ types.cpp \ acl_binding_cmds.cpp \ acl_binding.cpp \ acl_l2_rule.cpp \ acl_l3_rule.cpp \ acl_list_cmds.cpp \ acl_list.cpp \ acl_types.cpp \ arp_proxy_binding_cmds.cpp \ arp_proxy_binding.cpp \ arp_proxy_config_cmds.cpp \ arp_proxy_config.cpp \ bridge_domain_cmds.cpp \ bridge_domain.cpp \ bridge_domain_arp_entry.cpp \ bridge_domain_arp_entry_cmds.cpp \ bridge_domain_entry_cmds.cpp \ bridge_domain_entry.cpp \ client_db.cpp \ cmd.cpp \ connection.cpp \ dhcp_config_cmds.cpp \ dhcp_config.cpp \ hw_cmds.cpp \ hw.cpp \ inspect.cpp \ interface_cmds.cpp \ interface.cpp \ interface_factory.cpp \ interface_ip6_nd_cmds.cpp \ interface_span_cmds.cpp \ interface_span.cpp \ interface_types.cpp \ ip_unnumbered_cmds.cpp \ ip_unnumbered.cpp \ l2_binding_cmds.cpp \ l2_binding.cpp \ l3_binding_cmds.cpp \ l3_binding.cpp \ lldp_binding_cmds.cpp \ lldp_binding.cpp \ lldp_global_cmds.cpp \ lldp_global.cpp \ logger.cpp \ nat_static.cpp \ nat_static_cmds.cpp \ nat_binding.cpp \ nat_binding_cmds.cpp \ neighbour.cpp \ neighbour_cmds.cpp \ object_base.cpp \ om.cpp \ prefix.cpp \ ra_config.cpp \ ra_prefix.cpp \ route.cpp \ route_cmds.cpp \ route_domain.cpp \ route_domain_cmds.cpp \ sub_interface_cmds.cpp \ sub_interface.cpp \ tap_interface.cpp \ tap_interface_cmds.cpp \ vxlan_tunnel_cmds.cpp \ vxlan_tunnel.cpp vomincludedir = $(includedir)/vom vominclude_HEADERS = \ acl_binding.hpp \ acl_l2_rule.hpp \ acl_l3_rule.hpp \ acl_list.hpp \ acl_types.hpp \ arp_proxy_binding.hpp \ arp_proxy_config.hpp \ bridge_domain.hpp \ bridge_domain_arp_entry.hpp \ bridge_domain_entry.hpp \ client_db.hpp \ cmd.hpp \ connection.hpp \ dhcp_config.hpp \ dhcp_config_cmds.hpp \ dump_cmd.hpp \ enum_base.hpp \ event_cmd.hpp \ hw.hpp \ inspect.hpp \ interface.hpp \ interface_cmds.hpp \ interface_ip6_nd.hpp \ interface_span.hpp \ ip_unnumbered.hpp \ l2_binding.hpp \ l3_binding.hpp \ lldp_binding.hpp \ lldp_global.hpp \ logger.hpp \ nat_static.hpp \ nat_binding.hpp \ neighbour.hpp \ object_base.hpp \ om.hpp \ prefix.hpp \ ra_config.hpp \ ra_prefix.hpp \ route.hpp \ route_domain.hpp \ rpc_cmd.hpp \ singular_db.hpp \ sub_interface.hpp \ tap_interface.hpp \ types.hpp \ vxlan_tunnel.hpp # vi:syntax=automake