summaryrefslogtreecommitdiffstats
path: root/src/vppinfra.am
diff options
context:
space:
mode:
authorPierre Pfister <ppfister@cisco.com>2018-01-12 09:41:16 +0100
committerDave Barach <openvpp@barachs.net>2018-02-01 12:48:05 +0000
commit953f551e3629a3b96c678a35f5e6f507ea67cd84 (patch)
treee615a27746f273c5646d4e1a0065627a31889a44 /src/vppinfra.am
parentbe9b41ba3887452c864d1423ea03ed4ee2b9153c (diff)
Add flowhash hash table to vppinfra
This hash table intends to provide an alternative to the widely used bihash table in places where either: - Hash entry timeout is required - The hash table data does not fit in CPU cache Although the bihash table is very fast, each lookup requires accessing two cache lines in a serialized fashion. It works fine when the hash table is in cache, but hits a wall when it does not. The 'flowhash' table uses a simplified design (at the cost of a less good bucket auto-scaling) where each access only requires a single memory lookup (in the absence of collision). The hash table also uses a reduced number of registers. In practice, a VPP node implementing a stateful feature would typically: - prefetch buffer metadata (in-cache) - prefetch packet header (in-cache) - compute hash & prefetch hash bucket (possibly in RAM) - read/write key and value from bucket Using this hash table, it is possible to pipeline accesses in a way that does not exhaust CPU's line field buffers, even when the requested value is located in RAM (i.e. not in cache). Measurements showed it was possible to scale to tens of millions of flows (with a full 5-tuple matching and 32B value, i.e. 1 cache line per flow) with no performance degradation when the hash table grows to the point it doesn't fit in cache anymore. I have used this table in a couple of non-open-sourced projects, but think it might be useful to lb, nat, and possibly other VPP subsystems. More information in the .h file. Change-Id: I2b13dde0eabd868b75da1cedbfca0bf74d705102 Signed-off-by: Pierre Pfister <ppfister@cisco.com>
Diffstat (limited to 'src/vppinfra.am')
-rw-r--r--src/vppinfra.am11
1 files changed, 11 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 \