From 17f520d2cff8d69962824f28810f36e949a7184d Mon Sep 17 00:00:00 2001 From: Konstantin Ananyev Date: Tue, 20 Jan 2015 18:41:07 +0000 Subject: [PATCH] acl: add comments about internal layout Signed-off-by: Konstantin Ananyev Acked-by: Neil Horman --- lib/librte_acl/acl.h | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/lib/librte_acl/acl.h b/lib/librte_acl/acl.h index 217bab32b4..4dadab5f14 100644 --- a/lib/librte_acl/acl.h +++ b/lib/librte_acl/acl.h @@ -67,6 +67,44 @@ struct rte_acl_bitset { #define RTE_ACL_NODE_TYPE (7U << RTE_ACL_TYPE_SHIFT) #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. -- 2.20.1