[ceph.git] / ceph / src / spdk / dpdk / lib / librte_acl / acl_gen.c

/* SPDX-License-Identifier: BSD-3-Clause
 * Copyright(c) 2010-2014 Intel Corporation
 */

#include <rte_acl.h>
#include "acl.h"

#define	QRANGE_MIN	((uint8_t)INT8_MIN)

#define	RTE_ACL_VERIFY(exp)	do {                                          \
	if (!(exp))                                                           \
		rte_panic("line %d\tassert \"" #exp "\" failed\n", __LINE__); \
} while (0)

struct acl_node_counters {
	int32_t match;
	int32_t match_used;
	int32_t single;
	int32_t quad;
	int32_t quad_vectors;
	int32_t dfa;
	int32_t dfa_gr64;
};

struct rte_acl_indices {
	int32_t dfa_index;
	int32_t quad_index;
	int32_t single_index;
	int32_t match_index;
	int32_t match_start;
};

static void
acl_gen_log_stats(const struct rte_acl_ctx *ctx,
	const struct acl_node_counters *counts,
	const struct rte_acl_indices *indices,
	size_t max_size)
{
	RTE_LOG(DEBUG, ACL, "Gen phase for ACL \"%s\":\n"
		"runtime memory footprint on socket %d:\n"
		"single nodes/bytes used: %d/%zu\n"
		"quad nodes/vectors/bytes used: %d/%d/%zu\n"
		"DFA nodes/group64/bytes used: %d/%d/%zu\n"
		"match nodes/bytes used: %d/%zu\n"
		"total: %zu bytes\n"
		"max limit: %zu bytes\n",
		ctx->name, ctx->socket_id,
		counts->single, counts->single * sizeof(uint64_t),
		counts->quad, counts->quad_vectors,
		(indices->quad_index - indices->dfa_index) * sizeof(uint64_t),
		counts->dfa, counts->dfa_gr64,
		indices->dfa_index * sizeof(uint64_t),
		counts->match,
		counts->match * sizeof(struct rte_acl_match_results),
		ctx->mem_sz,
		max_size);
}

static uint64_t
acl_dfa_gen_idx(const struct rte_acl_node *node, uint32_t index)
{
	uint64_t idx;
	uint32_t i;

	idx = 0;
	for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) {
		RTE_ACL_VERIFY(node->dfa_gr64[i] < RTE_ACL_DFA_GR64_NUM);
		RTE_ACL_VERIFY(node->dfa_gr64[i] < node->fanout);
		idx |= (i - node->dfa_gr64[i]) <<
			(6 + RTE_ACL_DFA_GR64_BIT * i);
	}

	return idx << (CHAR_BIT * sizeof(index)) | index | node->node_type;
}

static void
acl_dfa_fill_gr64(const struct rte_acl_node *node,
	const uint64_t src[RTE_ACL_DFA_SIZE], uint64_t dst[RTE_ACL_DFA_SIZE])
{
	uint32_t i;

	for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) {
		memcpy(dst + node->dfa_gr64[i] * RTE_ACL_DFA_GR64_SIZE,
			src + i * RTE_ACL_DFA_GR64_SIZE,
			RTE_ACL_DFA_GR64_SIZE * sizeof(dst[0]));
	}
}

static uint32_t
acl_dfa_count_gr64(const uint64_t array_ptr[RTE_ACL_DFA_SIZE],
	uint8_t gr64[RTE_ACL_DFA_GR64_NUM])
{
	uint32_t i, j, k;

	k = 0;
	for (i = 0; i != RTE_ACL_DFA_GR64_NUM; i++) {
		gr64[i] = i;
		for (j = 0; j != i; j++) {
			if (memcmp(array_ptr + i * RTE_ACL_DFA_GR64_SIZE,
					array_ptr + j * RTE_ACL_DFA_GR64_SIZE,
					RTE_ACL_DFA_GR64_SIZE *
					sizeof(array_ptr[0])) == 0)
				break;
		}
		gr64[i] = (j != i) ? gr64[j] : k++;
	}

	return k;
}

static uint32_t
acl_node_fill_dfa(const struct rte_acl_node *node,
	uint64_t dfa[RTE_ACL_DFA_SIZE], uint64_t no_match, int32_t resolved)
{
	uint32_t n, x;
	uint32_t ranges, last_bit;
	struct rte_acl_node *child;
	struct rte_acl_bitset *bits;

	ranges = 0;
	last_bit = 0;

	for (n = 0; n < RTE_ACL_DFA_SIZE; n++)
		dfa[n] = no_match;

	for (x = 0; x < node->num_ptrs; x++) {

		child = node->ptrs[x].ptr;
		if (child == NULL)
			continue;

		bits = &node->ptrs[x].values;
		for (n = 0; n < RTE_ACL_DFA_SIZE; n++) {

			if (bits->bits[n / (sizeof(bits_t) * CHAR_BIT)] &
				(1 << (n % (sizeof(bits_t) * CHAR_BIT)))) {

				dfa[n] = resolved ? child->node_index : x;
				ranges += (last_bit == 0);
				last_bit = 1;
			} else {
				last_bit = 0;
			}
		}
	}

	return ranges;
}

/*
*  Counts the number of groups of sequential bits that are
*  either 0 or 1, as specified by the zero_one parameter. This is used to
*  calculate the number of ranges in a node to see if it fits in a quad range
*  node.
*/
static int
acl_count_sequential_groups(struct rte_acl_bitset *bits, int zero_one)
{
	int n, ranges, last_bit;

	ranges = 0;
	last_bit = zero_one ^ 1;

	for (n = QRANGE_MIN; n < UINT8_MAX + 1; n++) {
		if (bits->bits[n / (sizeof(bits_t) * 8)] &
				(1U << (n % (sizeof(bits_t) * 8)))) {
			if (zero_one == 1 && last_bit != 1)
				ranges++;
			last_bit = 1;
		} else {
			if (zero_one == 0 && last_bit != 0)
				ranges++;
			last_bit = 0;
		}
	}
	for (n = 0; n < QRANGE_MIN; n++) {
		if (bits->bits[n / (sizeof(bits_t) * 8)] &
				(1 << (n % (sizeof(bits_t) * 8)))) {
			if (zero_one == 1 && last_bit != 1)
				ranges++;
			last_bit = 1;
		} else {
			if (zero_one == 0 && last_bit != 0)
				ranges++;
			last_bit = 0;
		}
	}

	return ranges;
}

/*
 * Count number of ranges spanned by the node's pointers
 */
static int
acl_count_fanout(struct rte_acl_node *node)
{
	uint32_t n;
	int ranges;

	if (node->fanout != 0)
		return node->fanout;

	ranges = acl_count_sequential_groups(&node->values, 0);

	for (n = 0; n < node->num_ptrs; n++) {
		if (node->ptrs[n].ptr != NULL)
			ranges += acl_count_sequential_groups(
				&node->ptrs[n].values, 1);
	}

	node->fanout = ranges;
	return node->fanout;
}

/*
 * Determine the type of nodes and count each type
 */
static void
acl_count_trie_types(struct acl_node_counters *counts,
	struct rte_acl_node *node, uint64_t no_match, int force_dfa)
{
	uint32_t n;
	int num_ptrs;
	uint64_t dfa[RTE_ACL_DFA_SIZE];

	/* skip if this node has been counted */
	if (node->node_type != (uint32_t)RTE_ACL_NODE_UNDEFINED)
		return;

	if (node->match_flag != 0 || node->num_ptrs == 0) {
		counts->match++;
		node->node_type = RTE_ACL_NODE_MATCH;
		return;
	}

	num_ptrs = acl_count_fanout(node);

	/* Force type to dfa */
	if (force_dfa)
		num_ptrs = RTE_ACL_DFA_SIZE;

	/* determine node type based on number of ranges */
	if (num_ptrs == 1) {
		counts->single++;
		node->node_type = RTE_ACL_NODE_SINGLE;
	} else if (num_ptrs <= RTE_ACL_QUAD_MAX) {
		counts->quad++;
		counts->quad_vectors += node->fanout;
		node->node_type = RTE_ACL_NODE_QRANGE;
	} else {
		counts->dfa++;
		node->node_type = RTE_ACL_NODE_DFA;
		if (force_dfa != 0) {
			/* always expand to a max number of nodes. */
			for (n = 0; n != RTE_DIM(node->dfa_gr64); n++)
				node->dfa_gr64[n] = n;
			node->fanout = n;
		} else {
			acl_node_fill_dfa(node, dfa, no_match, 0);
			node->fanout = acl_dfa_count_gr64(dfa, node->dfa_gr64);
		}
		counts->dfa_gr64 += node->fanout;
	}

	/*
	 * recursively count the types of all children
	 */
	for (n = 0; n < node->num_ptrs; n++) {
		if (node->ptrs[n].ptr != NULL)
			acl_count_trie_types(counts, node->ptrs[n].ptr,
				no_match, 0);
	}
}

static void
acl_add_ptrs(struct rte_acl_node *node, uint64_t *node_array, uint64_t no_match,
	int resolved)
{
	uint32_t x;
	int32_t m;
	uint64_t *node_a, index, dfa[RTE_ACL_DFA_SIZE];

	acl_node_fill_dfa(node, dfa, no_match, resolved);

	/*
	 * Rather than going from 0 to 256, the range count and
	 * the layout are from 80-ff then 0-7f due to signed compare
	 * for SSE (cmpgt).
	 */
	if (node->node_type == RTE_ACL_NODE_QRANGE) {

		m = 0;
		node_a = node_array;
		index = dfa[QRANGE_MIN];
		*node_a++ = index;

		for (x = QRANGE_MIN + 1; x < UINT8_MAX + 1; x++) {
			if (dfa[x] != index) {
				index = dfa[x];
				*node_a++ = index;
				node->transitions[m++] = (uint8_t)(x - 1);
			}
		}

		for (x = 0; x < INT8_MAX + 1; x++) {
			if (dfa[x] != index) {
				index = dfa[x];
				*node_a++ = index;
				node->transitions[m++] = (uint8_t)(x - 1);
			}
		}

		/* fill unused locations with max value - nothing is greater */
		for (; m < RTE_ACL_QUAD_SIZE; m++)
			node->transitions[m] = INT8_MAX;

		RTE_ACL_VERIFY(m <= RTE_ACL_QUAD_SIZE);

	} else if (node->node_type == RTE_ACL_NODE_DFA && resolved) {
		acl_dfa_fill_gr64(node, dfa, node_array);
	}
}

/*
 * Routine that allocates space for this node and recursively calls
 * to allocate space for each child. Once all the children are allocated,
 * then resolve all transitions for this node.
 */
static void
acl_gen_node(struct rte_acl_node *node, uint64_t *node_array,
	uint64_t no_match, struct rte_acl_indices *index, int num_categories)
{
	uint32_t n, sz, *qtrp;
	uint64_t *array_ptr;
	struct rte_acl_match_results *match;

	if (node->node_index != RTE_ACL_NODE_UNDEFINED)
		return;

	array_ptr = NULL;

	switch (node->node_type) {
	case RTE_ACL_NODE_DFA:
		array_ptr = &node_array[index->dfa_index];
		node->node_index = acl_dfa_gen_idx(node, index->dfa_index);
		sz = node->fanout * RTE_ACL_DFA_GR64_SIZE;
		index->dfa_index += sz;
		for (n = 0; n < sz; n++)
			array_ptr[n] = no_match;
		break;
	case RTE_ACL_NODE_SINGLE:
		node->node_index = RTE_ACL_QUAD_SINGLE | index->single_index |
			node->node_type;
		array_ptr = &node_array[index->single_index];
		index->single_index += 1;
		array_ptr[0] = no_match;
		break;
	case RTE_ACL_NODE_QRANGE:
		array_ptr = &node_array[index->quad_index];
		acl_add_ptrs(node, array_ptr, no_match, 0);
		qtrp = (uint32_t *)node->transitions;
		node->node_index = qtrp[0];
		node->node_index <<= sizeof(index->quad_index) * CHAR_BIT;
		node->node_index |= index->quad_index | node->node_type;
		index->quad_index += node->fanout;
		break;
	case RTE_ACL_NODE_MATCH:
		match = ((struct rte_acl_match_results *)
			(node_array + index->match_start));
		for (n = 0; n != RTE_DIM(match->results); n++)
			RTE_ACL_VERIFY(match->results[0] == 0);
		memcpy(match + index->match_index, node->mrt,
			sizeof(*node->mrt));
		node->node_index = index->match_index | node->node_type;
		index->match_index += 1;
		break;
	case RTE_ACL_NODE_UNDEFINED:
		RTE_ACL_VERIFY(node->node_type !=
			(uint32_t)RTE_ACL_NODE_UNDEFINED);
		break;
	}

	/* recursively allocate space for all children */
	for (n = 0; n < node->num_ptrs; n++) {
		if (node->ptrs[n].ptr != NULL)
			acl_gen_node(node->ptrs[n].ptr,
				node_array,
				no_match,
				index,
				num_categories);
	}

	/* All children are resolved, resolve this node's pointers */
	switch (node->node_type) {
	case RTE_ACL_NODE_DFA:
		acl_add_ptrs(node, array_ptr, no_match, 1);
		break;
	case RTE_ACL_NODE_SINGLE:
		for (n = 0; n < node->num_ptrs; n++) {
			if (node->ptrs[n].ptr != NULL)
				array_ptr[0] = node->ptrs[n].ptr->node_index;
		}
		break;
	case RTE_ACL_NODE_QRANGE:
		acl_add_ptrs(node, array_ptr, no_match, 1);
		break;
	case RTE_ACL_NODE_MATCH:
		break;
	case RTE_ACL_NODE_UNDEFINED:
		RTE_ACL_VERIFY(node->node_type !=
			(uint32_t)RTE_ACL_NODE_UNDEFINED);
		break;
	}
}

static void
acl_calc_counts_indices(struct acl_node_counters *counts,
	struct rte_acl_indices *indices,
	struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
	uint64_t no_match)
{
	uint32_t n;

	memset(indices, 0, sizeof(*indices));
	memset(counts, 0, sizeof(*counts));

	/* Get stats on nodes */
	for (n = 0; n < num_tries; n++) {
		acl_count_trie_types(counts, node_bld_trie[n].trie,
			no_match, 1);
	}

	indices->dfa_index = RTE_ACL_DFA_SIZE + 1;
	indices->quad_index = indices->dfa_index +
		counts->dfa_gr64 * RTE_ACL_DFA_GR64_SIZE;
	indices->single_index = indices->quad_index + counts->quad_vectors;
	indices->match_start = indices->single_index + counts->single + 1;
	indices->match_start = RTE_ALIGN(indices->match_start,
		(XMM_SIZE / sizeof(uint64_t)));
	indices->match_index = 1;
}

/*
 * Generate the runtime structure using build structure
 */
int
rte_acl_gen(struct rte_acl_ctx *ctx, struct rte_acl_trie *trie,
	struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
	uint32_t num_categories, uint32_t data_index_sz, size_t max_size)
{
	void *mem;
	size_t total_size;
	uint64_t *node_array, no_match;
	uint32_t n, match_index;
	struct rte_acl_match_results *match;
	struct acl_node_counters counts;
	struct rte_acl_indices indices;

	no_match = RTE_ACL_NODE_MATCH;

	/* Fill counts and indices arrays from the nodes. */
	acl_calc_counts_indices(&counts, &indices,
		node_bld_trie, num_tries, no_match);

	/* Allocate runtime memory (align to cache boundary) */
	total_size = RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE) +
		indices.match_start * sizeof(uint64_t) +
		(counts.match + 1) * sizeof(struct rte_acl_match_results) +
		XMM_SIZE;

	if (total_size > max_size) {
		RTE_LOG(DEBUG, ACL,
			"Gen phase for ACL ctx \"%s\" exceeds max_size limit, "
			"bytes required: %zu, allowed: %zu\n",
			ctx->name, total_size, max_size);
		return -ERANGE;
	}

	mem = rte_zmalloc_socket(ctx->name, total_size, RTE_CACHE_LINE_SIZE,
			ctx->socket_id);
	if (mem == NULL) {
		RTE_LOG(ERR, ACL,
			"allocation of %zu bytes on socket %d for %s failed\n",
			total_size, ctx->socket_id, ctx->name);
		return -ENOMEM;
	}

	/* Fill the runtime structure */
	match_index = indices.match_start;
	node_array = (uint64_t *)((uintptr_t)mem +
		RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE));

	/*
	 * Setup the NOMATCH node (a SINGLE at the
	 * highest index, that points to itself)
	 */

	node_array[RTE_ACL_DFA_SIZE] = RTE_ACL_DFA_SIZE | RTE_ACL_NODE_SINGLE;

	for (n = 0; n < RTE_ACL_DFA_SIZE; n++)
		node_array[n] = no_match;

	/* NOMATCH result at index 0 */
	match = ((struct rte_acl_match_results *)(node_array + match_index));
	memset(match, 0, sizeof(*match));

	for (n = 0; n < num_tries; n++) {

		acl_gen_node(node_bld_trie[n].trie, node_array, no_match,
			&indices, num_categories);

		if (node_bld_trie[n].trie->node_index == no_match)
			trie[n].root_index = 0;
		else
			trie[n].root_index = node_bld_trie[n].trie->node_index;
	}

	ctx->mem = mem;
	ctx->mem_sz = total_size;
	ctx->data_indexes = mem;
	ctx->num_tries = num_tries;
	ctx->num_categories = num_categories;
	ctx->match_index = match_index;
	ctx->no_match = no_match;
	ctx->idle = node_array[RTE_ACL_DFA_SIZE];
	ctx->trans_table = node_array;
	memcpy(ctx->trie, trie, sizeof(ctx->trie));

	acl_gen_log_stats(ctx, &counts, &indices, max_size);
	return 0;
}
Commit	Line	Data
11fdf7f2 TL	1	/* SPDX-License-Identifier: BSD-3-Clause
11fdf7f2 TL	2	* Copyright(c) 2010-2014 Intel Corporation
7c673cae FG	3	*/
	4
	5	#include <rte_acl.h>
	6	#include "acl.h"
	7
	8	#define QRANGE_MIN ((uint8_t)INT8_MIN)
	9
	10	#define RTE_ACL_VERIFY(exp) do { \
	11	if (!(exp)) \
	12	rte_panic("line %d\tassert \"" #exp "\" failed\n", __LINE__); \
	13	} while (0)
	14
	15	struct acl_node_counters {
	16	int32_t match;
	17	int32_t match_used;
	18	int32_t single;
	19	int32_t quad;
	20	int32_t quad_vectors;
	21	int32_t dfa;
	22	int32_t dfa_gr64;
	23	};
	24
	25	struct rte_acl_indices {
	26	int32_t dfa_index;
	27	int32_t quad_index;
	28	int32_t single_index;
	29	int32_t match_index;
	30	int32_t match_start;
	31	};
	32
	33	static void
	34	acl_gen_log_stats(const struct rte_acl_ctx *ctx,
	35	const struct acl_node_counters *counts,
	36	const struct rte_acl_indices *indices,
	37	size_t max_size)
	38	{
	39	RTE_LOG(DEBUG, ACL, "Gen phase for ACL \"%s\":\n"
	40	"runtime memory footprint on socket %d:\n"
	41	"single nodes/bytes used: %d/%zu\n"
	42	"quad nodes/vectors/bytes used: %d/%d/%zu\n"
	43	"DFA nodes/group64/bytes used: %d/%d/%zu\n"
	44	"match nodes/bytes used: %d/%zu\n"
	45	"total: %zu bytes\n"
	46	"max limit: %zu bytes\n",
	47	ctx->name, ctx->socket_id,
	48	counts->single, counts->single * sizeof(uint64_t),
	49	counts->quad, counts->quad_vectors,
	50	(indices->quad_index - indices->dfa_index) * sizeof(uint64_t),
	51	counts->dfa, counts->dfa_gr64,
	52	indices->dfa_index * sizeof(uint64_t),
	53	counts->match,
	54	counts->match * sizeof(struct rte_acl_match_results),
	55	ctx->mem_sz,
	56	max_size);
	57	}
	58
	59	static uint64_t
	60	acl_dfa_gen_idx(const struct rte_acl_node *node, uint32_t index)
	61	{
	62	uint64_t idx;
	63	uint32_t i;
	64
	65	idx = 0;
	66	for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) {
67	RTE_ACL_VERIFY(node->dfa_gr64[i] < RTE_ACL_DFA_GR64_NUM);
68	RTE_ACL_VERIFY(node->dfa_gr64[i] < node->fanout);
69	idx \|= (i - node->dfa_gr64[i]) <<
70	(6 + RTE_ACL_DFA_GR64_BIT * i);
71	}
72
73	return idx << (CHAR_BIT * sizeof(index)) \| index \| node->node_type;
74	}
75
76	static void
77	acl_dfa_fill_gr64(const struct rte_acl_node *node,
78	const uint64_t src[RTE_ACL_DFA_SIZE], uint64_t dst[RTE_ACL_DFA_SIZE])
79	{
80	uint32_t i;
81
82	for (i = 0; i != RTE_DIM(node->dfa_gr64); i++) {
83	memcpy(dst + node->dfa_gr64[i] * RTE_ACL_DFA_GR64_SIZE,
84	src + i * RTE_ACL_DFA_GR64_SIZE,
85	RTE_ACL_DFA_GR64_SIZE * sizeof(dst[0]));
86	}
87	}
88
89	static uint32_t
90	acl_dfa_count_gr64(const uint64_t array_ptr[RTE_ACL_DFA_SIZE],
91	uint8_t gr64[RTE_ACL_DFA_GR64_NUM])
92	{
93	uint32_t i, j, k;
94
95	k = 0;
96	for (i = 0; i != RTE_ACL_DFA_GR64_NUM; i++) {
97	gr64[i] = i;
98	for (j = 0; j != i; j++) {
99	if (memcmp(array_ptr + i * RTE_ACL_DFA_GR64_SIZE,
100	array_ptr + j * RTE_ACL_DFA_GR64_SIZE,
101	RTE_ACL_DFA_GR64_SIZE *
102	sizeof(array_ptr[0])) == 0)
103	break;
104	}
105	gr64[i] = (j != i) ? gr64[j] : k++;
106	}
107
108	return k;
109	}
110
111	static uint32_t
112	acl_node_fill_dfa(const struct rte_acl_node *node,
113	uint64_t dfa[RTE_ACL_DFA_SIZE], uint64_t no_match, int32_t resolved)
114	{
115	uint32_t n, x;
116	uint32_t ranges, last_bit;
117	struct rte_acl_node *child;
118	struct rte_acl_bitset *bits;
119
120	ranges = 0;
121	last_bit = 0;
122
123	for (n = 0; n < RTE_ACL_DFA_SIZE; n++)
124	dfa[n] = no_match;
125
126	for (x = 0; x < node->num_ptrs; x++) {
127
128	child = node->ptrs[x].ptr;
129	if (child == NULL)
130	continue;
131
132	bits = &node->ptrs[x].values;
133	for (n = 0; n < RTE_ACL_DFA_SIZE; n++) {
134
135	if (bits->bits[n / (sizeof(bits_t) * CHAR_BIT)] &
136	(1 << (n % (sizeof(bits_t) * CHAR_BIT)))) {
137
138	dfa[n] = resolved ? child->node_index : x;
139	ranges += (last_bit == 0);
140	last_bit = 1;
141	} else {
142	last_bit = 0;
143	}
144	}
145	}
146
147	return ranges;
148	}
149
150	/*
151	* Counts the number of groups of sequential bits that are
152	* either 0 or 1, as specified by the zero_one parameter. This is used to
153	* calculate the number of ranges in a node to see if it fits in a quad range
154	* node.
155	*/
156	static int
157	acl_count_sequential_groups(struct rte_acl_bitset *bits, int zero_one)
158	{
159	int n, ranges, last_bit;
160
161	ranges = 0;
162	last_bit = zero_one ^ 1;
163
164	for (n = QRANGE_MIN; n < UINT8_MAX + 1; n++) {
165	if (bits->bits[n / (sizeof(bits_t) * 8)] &
9f95a23c	166	(1U << (n % (sizeof(bits_t) * 8)))) {
7c673cae FG	167	if (zero_one == 1 && last_bit != 1)
	168	ranges++;
	169	last_bit = 1;
	170	} else {
	171	if (zero_one == 0 && last_bit != 0)
	172	ranges++;
	173	last_bit = 0;
	174	}
	175	}
	176	for (n = 0; n < QRANGE_MIN; n++) {
	177	if (bits->bits[n / (sizeof(bits_t) * 8)] &
	178	(1 << (n % (sizeof(bits_t) * 8)))) {
	179	if (zero_one == 1 && last_bit != 1)
	180	ranges++;
	181	last_bit = 1;
	182	} else {
	183	if (zero_one == 0 && last_bit != 0)
	184	ranges++;
	185	last_bit = 0;
	186	}
	187	}
	188
	189	return ranges;
	190	}
	191
	192	/*
	193	* Count number of ranges spanned by the node's pointers
	194	*/
	195	static int
	196	acl_count_fanout(struct rte_acl_node *node)
	197	{
	198	uint32_t n;
	199	int ranges;
	200
	201	if (node->fanout != 0)
	202	return node->fanout;
	203
	204	ranges = acl_count_sequential_groups(&node->values, 0);
	205
	206	for (n = 0; n < node->num_ptrs; n++) {
	207	if (node->ptrs[n].ptr != NULL)
	208	ranges += acl_count_sequential_groups(
	209	&node->ptrs[n].values, 1);
	210	}
	211
	212	node->fanout = ranges;
	213	return node->fanout;
	214	}
	215
	216	/*
	217	* Determine the type of nodes and count each type
	218	*/
	219	static void
	220	acl_count_trie_types(struct acl_node_counters *counts,
	221	struct rte_acl_node *node, uint64_t no_match, int force_dfa)
	222	{
	223	uint32_t n;
	224	int num_ptrs;
	225	uint64_t dfa[RTE_ACL_DFA_SIZE];
	226
	227	/* skip if this node has been counted */
	228	if (node->node_type != (uint32_t)RTE_ACL_NODE_UNDEFINED)
	229	return;
	230
231	if (node->match_flag != 0 \|\| node->num_ptrs == 0) {
232	counts->match++;
233	node->node_type = RTE_ACL_NODE_MATCH;
234	return;
235	}
236
237	num_ptrs = acl_count_fanout(node);
238
239	/* Force type to dfa */
240	if (force_dfa)
241	num_ptrs = RTE_ACL_DFA_SIZE;
242
243	/* determine node type based on number of ranges */
244	if (num_ptrs == 1) {
245	counts->single++;
246	node->node_type = RTE_ACL_NODE_SINGLE;
247	} else if (num_ptrs <= RTE_ACL_QUAD_MAX) {
248	counts->quad++;
249	counts->quad_vectors += node->fanout;
250	node->node_type = RTE_ACL_NODE_QRANGE;
251	} else {
252	counts->dfa++;
253	node->node_type = RTE_ACL_NODE_DFA;
254	if (force_dfa != 0) {
255	/* always expand to a max number of nodes. */
256	for (n = 0; n != RTE_DIM(node->dfa_gr64); n++)
257	node->dfa_gr64[n] = n;
258	node->fanout = n;
259	} else {
260	acl_node_fill_dfa(node, dfa, no_match, 0);
261	node->fanout = acl_dfa_count_gr64(dfa, node->dfa_gr64);
262	}
263	counts->dfa_gr64 += node->fanout;
264	}
265
266	/*
267	* recursively count the types of all children
268	*/
269	for (n = 0; n < node->num_ptrs; n++) {
270	if (node->ptrs[n].ptr != NULL)
271	acl_count_trie_types(counts, node->ptrs[n].ptr,
272	no_match, 0);
273	}
274	}
275
276	static void
277	acl_add_ptrs(struct rte_acl_node node, uint64_t node_array, uint64_t no_match,
278	int resolved)
279	{
280	uint32_t x;
281	int32_t m;
282	uint64_t *node_a, index, dfa[RTE_ACL_DFA_SIZE];
283
284	acl_node_fill_dfa(node, dfa, no_match, resolved);
285
286	/*
287	* Rather than going from 0 to 256, the range count and
288	* the layout are from 80-ff then 0-7f due to signed compare
289	* for SSE (cmpgt).
290	*/
291	if (node->node_type == RTE_ACL_NODE_QRANGE) {
292
293	m = 0;
294	node_a = node_array;
295	index = dfa[QRANGE_MIN];
296	*node_a++ = index;
297
298	for (x = QRANGE_MIN + 1; x < UINT8_MAX + 1; x++) {
299	if (dfa[x] != index) {
300	index = dfa[x];
301	*node_a++ = index;
302	node->transitions[m++] = (uint8_t)(x - 1);
303	}
304	}
305
306	for (x = 0; x < INT8_MAX + 1; x++) {
307	if (dfa[x] != index) {
308	index = dfa[x];
309	*node_a++ = index;
310	node->transitions[m++] = (uint8_t)(x - 1);
311	}
312	}
313
314	/* fill unused locations with max value - nothing is greater */
315	for (; m < RTE_ACL_QUAD_SIZE; m++)
316	node->transitions[m] = INT8_MAX;
317
318	RTE_ACL_VERIFY(m <= RTE_ACL_QUAD_SIZE);
319
320	} else if (node->node_type == RTE_ACL_NODE_DFA && resolved) {
321	acl_dfa_fill_gr64(node, dfa, node_array);
322	}
323	}
324
325	/*
326	* Routine that allocates space for this node and recursively calls
327	* to allocate space for each child. Once all the children are allocated,
328	* then resolve all transitions for this node.
329	*/
330	static void
331	acl_gen_node(struct rte_acl_node node, uint64_t node_array,
332	uint64_t no_match, struct rte_acl_indices *index, int num_categories)
333	{
334	uint32_t n, sz, *qtrp;
335	uint64_t *array_ptr;
336	struct rte_acl_match_results *match;
337
338	if (node->node_index != RTE_ACL_NODE_UNDEFINED)
339	return;
340
341	array_ptr = NULL;
342
343	switch (node->node_type) {
344	case RTE_ACL_NODE_DFA:
345	array_ptr = &node_array[index->dfa_index];
346	node->node_index = acl_dfa_gen_idx(node, index->dfa_index);
347	sz = node->fanout * RTE_ACL_DFA_GR64_SIZE;
348	index->dfa_index += sz;
349	for (n = 0; n < sz; n++)
350	array_ptr[n] = no_match;
351	break;
352	case RTE_ACL_NODE_SINGLE:
353	node->node_index = RTE_ACL_QUAD_SINGLE \| index->single_index \|
354	node->node_type;
355	array_ptr = &node_array[index->single_index];
356	index->single_index += 1;
357	array_ptr[0] = no_match;
358	break;
359	case RTE_ACL_NODE_QRANGE:
360	array_ptr = &node_array[index->quad_index];
361	acl_add_ptrs(node, array_ptr, no_match, 0);
362	qtrp = (uint32_t *)node->transitions;
363	node->node_index = qtrp[0];
364	node->node_index <<= sizeof(index->quad_index) * CHAR_BIT;
365	node->node_index \|= index->quad_index \| node->node_type;
366	index->quad_index += node->fanout;
367	break;
368	case RTE_ACL_NODE_MATCH:
369	match = ((struct rte_acl_match_results *)
370	(node_array + index->match_start));
371	for (n = 0; n != RTE_DIM(match->results); n++)
372	RTE_ACL_VERIFY(match->results[0] == 0);
373	memcpy(match + index->match_index, node->mrt,
374	sizeof(*node->mrt));
375	node->node_index = index->match_index \| node->node_type;
376	index->match_index += 1;
377	break;
378	case RTE_ACL_NODE_UNDEFINED:
379	RTE_ACL_VERIFY(node->node_type !=
380	(uint32_t)RTE_ACL_NODE_UNDEFINED);
381	break;
382	}
383
384	/* recursively allocate space for all children */
385	for (n = 0; n < node->num_ptrs; n++) {
386	if (node->ptrs[n].ptr != NULL)
387	acl_gen_node(node->ptrs[n].ptr,
388	node_array,
389	no_match,
390	index,
391	num_categories);
392	}
393
394	/* All children are resolved, resolve this node's pointers */
395	switch (node->node_type) {
396	case RTE_ACL_NODE_DFA:
397	acl_add_ptrs(node, array_ptr, no_match, 1);
398	break;
399	case RTE_ACL_NODE_SINGLE:
400	for (n = 0; n < node->num_ptrs; n++) {
401	if (node->ptrs[n].ptr != NULL)
402	array_ptr[0] = node->ptrs[n].ptr->node_index;
403	}
404	break;
405	case RTE_ACL_NODE_QRANGE:
406	acl_add_ptrs(node, array_ptr, no_match, 1);
407	break;
408	case RTE_ACL_NODE_MATCH:
409	break;
410	case RTE_ACL_NODE_UNDEFINED:
411	RTE_ACL_VERIFY(node->node_type !=
412	(uint32_t)RTE_ACL_NODE_UNDEFINED);
413	break;
414	}
415	}
416
417	static void
418	acl_calc_counts_indices(struct acl_node_counters *counts,
419	struct rte_acl_indices *indices,
420	struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
421	uint64_t no_match)
422	{
423	uint32_t n;
424
425	memset(indices, 0, sizeof(*indices));
426	memset(counts, 0, sizeof(*counts));
427
428	/* Get stats on nodes */
429	for (n = 0; n < num_tries; n++) {
430	acl_count_trie_types(counts, node_bld_trie[n].trie,
431	no_match, 1);
432	}
433
434	indices->dfa_index = RTE_ACL_DFA_SIZE + 1;
435	indices->quad_index = indices->dfa_index +
436	counts->dfa_gr64 * RTE_ACL_DFA_GR64_SIZE;
437	indices->single_index = indices->quad_index + counts->quad_vectors;
438	indices->match_start = indices->single_index + counts->single + 1;
439	indices->match_start = RTE_ALIGN(indices->match_start,
440	(XMM_SIZE / sizeof(uint64_t)));
441	indices->match_index = 1;
442	}
443
444	/*
445	* Generate the runtime structure using build structure
446	*/
447	int
448	rte_acl_gen(struct rte_acl_ctx ctx, struct rte_acl_trie trie,
449	struct rte_acl_bld_trie *node_bld_trie, uint32_t num_tries,
450	uint32_t num_categories, uint32_t data_index_sz, size_t max_size)
451	{
452	void *mem;
453	size_t total_size;
454	uint64_t *node_array, no_match;
455	uint32_t n, match_index;
456	struct rte_acl_match_results *match;
457	struct acl_node_counters counts;
458	struct rte_acl_indices indices;
459
460	no_match = RTE_ACL_NODE_MATCH;
461
462	/* Fill counts and indices arrays from the nodes. */
463	acl_calc_counts_indices(&counts, &indices,
464	node_bld_trie, num_tries, no_match);
465
466	/* Allocate runtime memory (align to cache boundary) */
467	total_size = RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE) +
468	indices.match_start * sizeof(uint64_t) +
469	(counts.match + 1) * sizeof(struct rte_acl_match_results) +
470	XMM_SIZE;
471
472	if (total_size > max_size) {
473	RTE_LOG(DEBUG, ACL,
474	"Gen phase for ACL ctx \"%s\" exceeds max_size limit, "
475	"bytes required: %zu, allowed: %zu\n",
476	ctx->name, total_size, max_size);
477	return -ERANGE;
478	}
479
480	mem = rte_zmalloc_socket(ctx->name, total_size, RTE_CACHE_LINE_SIZE,
481	ctx->socket_id);
482	if (mem == NULL) {
483	RTE_LOG(ERR, ACL,
484	"allocation of %zu bytes on socket %d for %s failed\n",
485	total_size, ctx->socket_id, ctx->name);
486	return -ENOMEM;
487	}
488
489	/* Fill the runtime structure */
490	match_index = indices.match_start;
491	node_array = (uint64_t *)((uintptr_t)mem +
492	RTE_ALIGN(data_index_sz, RTE_CACHE_LINE_SIZE));
493
494	/*
495	* Setup the NOMATCH node (a SINGLE at the
496	* highest index, that points to itself)
497	*/
498
499	node_array[RTE_ACL_DFA_SIZE] = RTE_ACL_DFA_SIZE \| RTE_ACL_NODE_SINGLE;
500
501	for (n = 0; n < RTE_ACL_DFA_SIZE; n++)
502	node_array[n] = no_match;
503
504	/* NOMATCH result at index 0 */
505	match = ((struct rte_acl_match_results *)(node_array + match_index));
506	memset(match, 0, sizeof(*match));
507
508	for (n = 0; n < num_tries; n++) {
509
510	acl_gen_node(node_bld_trie[n].trie, node_array, no_match,
511	&indices, num_categories);
512
513	if (node_bld_trie[n].trie->node_index == no_match)
514	trie[n].root_index = 0;
515	else
516	trie[n].root_index = node_bld_trie[n].trie->node_index;
517	}
518
519	ctx->mem = mem;
520	ctx->mem_sz = total_size;
521	ctx->data_indexes = mem;
522	ctx->num_tries = num_tries;
523	ctx->num_categories = num_categories;
524	ctx->match_index = match_index;
525	ctx->no_match = no_match;
526	ctx->idle = node_array[RTE_ACL_DFA_SIZE];
527	ctx->trans_table = node_array;
528	memcpy(ctx->trie, trie, sizeof(ctx->trie));
529
530	acl_gen_log_stats(ctx, &counts, &indices, max_size);
531	return 0;
532	}