contrib/dpdk_rte_lpm/rte_lpm.c

62 #define VERIFY_DEPTH(depth) do {                                \
63 	if ((depth == 0) || (depth > RTE_LPM_MAX_DEPTH))        \
64 		rte_panic("LPM: Invalid depth (%u) at line %d", \
65 				(unsigned)(depth), __LINE__);   \
68 #define VERIFY_DEPTH(depth)
72  * Converts a given depth value to its corresponding mask value.
74  * depth  (IN)		: range = 1 - 32
78 depth_to_mask(uint8_t depth)
80 	VERIFY_DEPTH(depth);
85 	return (int)0x80000000 >> (depth - 1);
89  * Converts given depth value to its corresponding range value.
92 depth_to_range(uint8_t depth)
94 	VERIFY_DEPTH(depth);
97 	 * Calculate tbl24 range. (Note: 2^depth = 1 << depth)
99 	if (depth <= MAX_DEPTH_TBL24)
100 		return 1 << (MAX_DEPTH_TBL24 - depth);
102 	/* Else if depth is greater than 24 */
103 	return 1 << (RTE_LPM_MAX_DEPTH - depth);
283  * apply to a specific prefix depth (i.e. group 1 contains rules that apply to
284  * prefixes with a depth of 1 etc.). In the following code (depth - 1) is used
285  * to refer to depth 1 because even though the depth range is 1 - 32, depths
287  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
290 rule_add(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
296 	VERIFY_DEPTH(depth);
299 	if (lpm->rule_info[depth - 1].used_rules > 0) {
302 		rule_gindex = lpm->rule_info[depth - 1].first_rule;
306 		last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
328 		for (i = depth - 1; i > 0; i--) {
338 		lpm->rule_info[depth - 1].first_rule = rule_index;
342 	for (i = RTE_LPM_MAX_DEPTH; i > depth; i--) {
360 	lpm->rule_info[depth - 1].used_rules++;
367  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
370 rule_delete(struct rte_lpm *lpm, int32_t rule_index, uint8_t depth)
374 	VERIFY_DEPTH(depth);
377 			lpm->rules_tbl[lpm->rule_info[depth - 1].first_rule
378 			+ lpm->rule_info[depth - 1].used_rules - 1];
380 	for (i = depth; i < RTE_LPM_MAX_DEPTH; i++) {
389 	lpm->rule_info[depth - 1].used_rules--;
394  * NOTE: Valid range for depth parameter is 1 .. 32 inclusive.
397 rule_find(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth)
401 	VERIFY_DEPTH(depth);
403 	rule_gindex = lpm->rule_info[depth - 1].first_rule;
404 	last_rule = rule_gindex + lpm->rule_info[depth - 1].used_rules;
406 	/* Scan used rules at given depth to find rule. */
435 				.depth = 0,
466 add_depth_small(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
474 	tbl24_range = depth_to_range(depth);
482 				lpm->tbl24[i].depth <= depth)) {
488 				.depth = depth,
511 						lpm->tbl8[j].depth <= depth) {
516 						.depth = depth,
538 add_depth_big(struct rte_lpm *lpm, uint32_t ip_masked, uint8_t depth,
547 	tbl8_range = depth_to_range(depth);
567 				.depth = depth,
585 			.depth = 0,
612 				.depth = lpm->tbl24[tbl24_index].depth,
626 				.depth = depth,
644 				.depth = 0,
664 					lpm->tbl8[i].depth <= depth) {
667 					.depth = depth,
691 rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
698 	if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
701 	ip_masked = ip & depth_to_mask(depth);
705 	rule_index = rule_add(lpm, ip_masked, depth, next_hop);
719 	if (depth <= MAX_DEPTH_TBL24) {
720 		status = add_depth_small(lpm, ip_masked, depth, next_hop);
721 	} else { /* If depth > RTE_LPM_MAX_DEPTH_TBL24 */
722 		status = add_depth_big(lpm, ip_masked, depth, next_hop);
729 			//rule_delete(lpm, rule_index, depth);
743 rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
752 		(depth < 1) || (depth > RTE_LPM_MAX_DEPTH))
756 	ip_masked = ip & depth_to_mask(depth);
757 	rule_index = rule_find(lpm, ip_masked, depth);
769 find_previous_rule(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
776 	for (prev_depth = (uint8_t)(depth - 1); prev_depth > 0; prev_depth--) {
793 	uint8_t depth, uint32_t sub_rule_nhop, uint8_t sub_rule_depth)
799 	tbl24_range = depth_to_range(depth);
815 					lpm->tbl24[i].depth <= depth) {
821 				 * to be a rule with depth >= 25 in the
832 					if (lpm->tbl8[j].depth <= depth)
847 			.depth = sub_rule_depth,
853 			.depth = sub_rule_depth,
860 					lpm->tbl24[i].depth <= depth) {
866 				 * to be a rule with depth >= 25 in the
877 					if (lpm->tbl8[j].depth <= depth)
906 	 * this tbl8 does not contain any rule with a depth < RTE_LPM_MAX_DEPTH
912 		 * If first entry is valid check if the depth is less than 24
914 		 * are all of this depth.
916 		if (tbl8[tbl8_group_start].depth <= MAX_DEPTH_TBL24) {
920 				if (tbl8[i].depth !=
921 						tbl8[tbl8_group_start].depth) {
946 	uint8_t depth, uint32_t sub_rule_nhop, uint8_t sub_rule_depth)
963 	tbl8_range = depth_to_range(depth);
971 			if (lpm->tbl8[i].depth <= depth)
978 			.depth = sub_rule_depth,
988 			if (lpm->tbl8[i].depth <= depth)
1015 			.depth = lpm->tbl8[tbl8_recycle_index].depth,
1034 rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
1044 	if ((lpm == NULL) || (depth < 1) || (depth > RTE_LPM_MAX_DEPTH)) {
1048 	ip_masked = ip & depth_to_mask(depth);
1055 	rule_to_delete_index = rule_find(lpm, ip_masked, depth);
1065 	rule_delete(lpm, rule_to_delete_index, depth);
1074 	//sub_rule_index = find_previous_rule(lpm, ip, depth, &sub_rule_depth);
1077 	 * If the input depth value is less than 25 use function
1080 	if (depth <= MAX_DEPTH_TBL24) {
1081 		return delete_depth_small(lpm, ip_masked, depth,
1083 	} else { /* If depth > MAX_DEPTH_TBL24 */
1084 		return delete_depth_big(lpm, ip_masked, depth, sub_rule_nhop,