summaryrefslogtreecommitdiff
path: root/lib/librte_acl
diff options
context:
space:
mode:
authorKonstantin Ananyev <konstantin.ananyev@intel.com>2015-01-20 18:41:07 +0000
committerThomas Monjalon <thomas.monjalon@6wind.com>2015-01-28 17:12:16 +0100
commit17f520d2cff8d69962824f28810f36e949a7184d (patch)
tree792adf24973d24ba743a0c00f8e425ddba92f8a3 /lib/librte_acl
parentf3d24368effab93d76e131a99e0ae857df5f819d (diff)
downloaddpdk-17f520d2cff8d69962824f28810f36e949a7184d.zip
dpdk-17f520d2cff8d69962824f28810f36e949a7184d.tar.gz
dpdk-17f520d2cff8d69962824f28810f36e949a7184d.tar.xz
acl: add comments about internal layout
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com> Acked-by: Neil Horman <nhorman@tuxdriver.com>
Diffstat (limited to 'lib/librte_acl')
-rw-r--r--lib/librte_acl/acl.h38
1 files changed, 38 insertions, 0 deletions
diff --git a/lib/librte_acl/acl.h b/lib/librte_acl/acl.h
index 217bab3..4dadab5 100644
--- a/lib/librte_acl/acl.h
+++ b/lib/librte_acl/acl.h
@@ -68,6 +68,44 @@ struct rte_acl_bitset {
#define RTE_ACL_NODE_UNDEFINED UINT32_MAX
/*
+ * ACL RT structure is a set of multibit tries (with stride == 8)
+ * represented by an array of transitions. The next position is calculated
+ * based on the current position and the input byte.
+ * Each transition is 64 bit value with the following format:
+ * | node_type_specific : 32 | node_type : 3 | node_addr : 29 |
+ * For all node types except RTE_ACL_NODE_MATCH, node_addr is an index
+ * to the start of the node in the transtions array.
+ * Few different node types are used:
+ * RTE_ACL_NODE_MATCH:
+ * node_addr value is and index into an array that contains the return value
+ * and its priority for each category.
+ * Upper 32 bits of the transition value are not used for that node type.
+ * RTE_ACL_NODE_QRANGE:
+ * that node consist of up to 5 transitions.
+ * Upper 32 bits are interpreted as 4 signed character values which
+ * are ordered from smallest(INT8_MIN) to largest (INT8_MAX).
+ * These values define 5 ranges:
+ * INT8_MIN <= range[0] <= ((int8_t *)&transition)[4]
+ * ((int8_t *)&transition)[4] < range[1] <= ((int8_t *)&transition)[5]
+ * ((int8_t *)&transition)[5] < range[2] <= ((int8_t *)&transition)[6]
+ * ((int8_t *)&transition)[6] < range[3] <= ((int8_t *)&transition)[7]
+ * ((int8_t *)&transition)[7] < range[4] <= INT8_MAX
+ * So for input byte value within range[i] i-th transition within that node
+ * will be used.
+ * RTE_ACL_NODE_SINGLE:
+ * always transitions to the same node regardless of the input value.
+ * RTE_ACL_NODE_DFA:
+ * that node consits of up to 256 transitions.
+ * In attempt to conserve space all transitions are divided into 4 consecutive
+ * groups, by 64 transitions per group:
+ * group64[i] contains transitions[i * 64, .. i * 64 + 63].
+ * Upper 32 bits are interpreted as 4 unsigned character values one per group,
+ * which contain index to the start of the given group within the node.
+ * So to calculate transition index within the node for given input byte value:
+ * input_byte - ((uint8_t *)&transition)[4 + input_byte / 64].
+ */
+
+/*
* Structure of a node is a set of ptrs and each ptr has a bit map
* of values associated with this transition.
*/