src/dpdk/lib/librte_efd/rte_efd.c
static inline int
efd_search_hash(struct rte_efd_table * const table,
		const struct efd_offline_group_rules * const off_group,
		struct efd_online_group_entry * const on_group)
{
	efd_hashfunc_t hash_idx;
	efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
	efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];

	uint32_t i, j, rule_id;
	uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
	uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
	uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];


	rte_prefetch0(off_group->value);

	/*
	 * Prepopulate the hash_val tables by running the two hash functions
	 * for each provided rule
	 */
	for (i = 0; i < off_group->num_rules; i++) {
		void *key_stored = EFD_KEY(off_group->key_idx[i], table);
		hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
		hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
	}

	for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
		hash_idx = on_group->hash_idx[i];
		start_hash_idx[i] = hash_idx;
		start_lookup_table[i] = on_group->lookup_table[i];

		do {
			efd_lookuptbl_t lookup_table = 0;
			efd_lookuptbl_t lookup_table_complement = 0;

			for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
				hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
					hash_val_b[rule_id]);

			/*
			 * The goal here is to find a hash function for this
			 * particular bit entry that meets the following criteria:
			 * The most significant bits of the hash result define a
			 * shift into the lookup table where the bit will be stored
			 */

			/* Iterate over each provided rule */
			for (rule_id = 0; rule_id < off_group->num_rules;
					rule_id++) {
				/*
				 * Use the few most significant bits (number based on
				 * EFD_LOOKUPTBL_SIZE) to see what position the
				 * expected bit should be set in the lookup_table
				 */
				uint32_t bucket_idx = hash_val[rule_id] >>
						EFD_LOOKUPTBL_SHIFT;

				/*
				 * Get the current bit of interest.
				 * This only find an appropriate hash function
				 * for one bit at a time of the rule
				 */
				efd_lookuptbl_t expected =
						(off_group->value[rule_id] >> i) & 0x1;

				/*
				 * Add the expected bit (if set) to a map
				 * (lookup_table). Also set its complement
				 * in lookup_table_complement
				 */
				lookup_table |= expected << bucket_idx;
				lookup_table_complement |= (1 - expected)
						<< bucket_idx;

				/*
				 * If ever the hash function of two different
				 * elements result in different values at the
				 * same location in the lookup_table,
				 * the current hash_idx is not valid.
				 */
				if (lookup_table & lookup_table_complement)
					break;
			}

			/*
			 * Check if the previous loop completed without
			 * breaking early
			 */
			if (rule_id == off_group->num_rules) {
				/*
				 * Current hash function worked, store it
				 * for the current group
				 */
				on_group->hash_idx[i] = hash_idx;
				on_group->lookup_table[i] = lookup_table;

				/*
				 * Make sure that the hash function has changed
				 * from the starting value
				 */
				hash_idx = start_hash_idx[i] + 1;
				break;
			}
			hash_idx++;

		} while (hash_idx != start_hash_idx[i]);

		/* Failed to find perfect hash for this group */
		if (hash_idx == start_hash_idx[i]) {
			/*
			 * Restore previous hash_idx and lookup_table
			 * for all value bits
			 */
			for (j = 0; j < i; j++) {
				on_group->hash_idx[j] = start_hash_idx[j];
				on_group->lookup_table[j] = start_lookup_table[j];
			}
			return 1;
		}
	}

	return 0;
}
/**
 * Search for a hash function for a group that satisfies all group results
 */
Search for a hash function for a group that satisfies all group results
Search for a hash function for a group that satisfies all group results
static inline int
efd_search_hash(struct rte_efd_table * const table,
		const struct efd_offline_group_rules * const off_group,
		struct efd_online_group_entry * const on_group)
{
	efd_hashfunc_t hash_idx;
	efd_hashfunc_t start_hash_idx[RTE_EFD_VALUE_NUM_BITS];
	efd_lookuptbl_t start_lookup_table[RTE_EFD_VALUE_NUM_BITS];
	uint32_t i, j, rule_id;
	uint32_t hash_val_a[EFD_MAX_GROUP_NUM_RULES];
	uint32_t hash_val_b[EFD_MAX_GROUP_NUM_RULES];
	uint32_t hash_val[EFD_MAX_GROUP_NUM_RULES];
	rte_prefetch0(off_group->value);
	for (i = 0; i < off_group->num_rules; i++) {
		void *key_stored = EFD_KEY(off_group->key_idx[i], table);
		hash_val_b[i] = EFD_HASHFUNCB(key_stored, table);
		hash_val_a[i] = EFD_HASHFUNCA(key_stored, table);
	}
	for (i = 0; i < RTE_EFD_VALUE_NUM_BITS; i++) {
		hash_idx = on_group->hash_idx[i];
		start_hash_idx[i] = hash_idx;
		start_lookup_table[i] = on_group->lookup_table[i];
		do {
			efd_lookuptbl_t lookup_table = 0;
			efd_lookuptbl_t lookup_table_complement = 0;
			for (rule_id = 0; rule_id < off_group->num_rules; rule_id++)
				hash_val[rule_id] = hash_val_a[rule_id] + (hash_idx *
					hash_val_b[rule_id]);
			for (rule_id = 0; rule_id < off_group->num_rules;
					rule_id++) {
				uint32_t bucket_idx = hash_val[rule_id] >>
						EFD_LOOKUPTBL_SHIFT;
				efd_lookuptbl_t expected =
						(off_group->value[rule_id] >> i) & 0x1;
				lookup_table |= expected << bucket_idx;
				lookup_table_complement |= (1 - expected)
						<< bucket_idx;
				if (lookup_table & lookup_table_complement)
					break;
			}
			if (rule_id == off_group->num_rules) {
				on_group->hash_idx[i] = hash_idx;
				on_group->lookup_table[i] = lookup_table;
				hash_idx = start_hash_idx[i] + 1;
				break;
			}
			hash_idx++;
		} while (hash_idx != start_hash_idx[i]);
		if (hash_idx == start_hash_idx[i]) {
			for (j = 0; j < i; j++) {
				on_group->hash_idx[j] = start_hash_idx[j];
				on_group->lookup_table[j] = start_lookup_table[j];
			}
			return 1;
		}
	}
	return 0;
}
static inline int efd_search_hash ( struct rte_efd_table * const table , const struct efd_offline_group_rules * const off_group , struct efd_online_group_entry * const on_group ) { efd_hashfunc_t hash_idx ; efd_hashfunc_t start_hash_idx [ RTE_EFD_VALUE_NUM_BITS ] ; efd_lookuptbl_t start_lookup_table [ RTE_EFD_VALUE_NUM_BITS ] ; uint32_t i , j , rule_id ; uint32_t hash_val_a [ EFD_MAX_GROUP_NUM_RULES ] ; uint32_t hash_val_b [ EFD_MAX_GROUP_NUM_RULES ] ; uint32_t hash_val [ EFD_MAX_GROUP_NUM_RULES ] ; rte_prefetch0 ( off_group -> value ) ; for ( i = 0 ; i < off_group -> num_rules ; i ++ ) { void * key_stored = EFD_KEY ( off_group -> key_idx [ i ] , table ) ; hash_val_b [ i ] = EFD_HASHFUNCB ( key_stored , table ) ; hash_val_a [ i ] = EFD_HASHFUNCA ( key_stored , table ) ; } for ( i = 0 ; i < RTE_EFD_VALUE_NUM_BITS ; i ++ ) { hash_idx = on_group -> hash_idx [ i ] ; start_hash_idx [ i ] = hash_idx ; start_lookup_table [ i ] = on_group -> lookup_table [ i ] ; do { efd_lookuptbl_t lookup_table = 0 ; efd_lookuptbl_t lookup_table_complement = 0 ; for ( rule_id = 0 ; rule_id < off_group -> num_rules ; rule_id ++ ) hash_val [ rule_id ] = hash_val_a [ rule_id ] + ( hash_idx * hash_val_b [ rule_id ] ) ; for ( rule_id = 0 ; rule_id < off_group -> num_rules ; rule_id ++ ) { uint32_t bucket_idx = hash_val [ rule_id ] >> EFD_LOOKUPTBL_SHIFT ; efd_lookuptbl_t expected = ( off_group -> value [ rule_id ] >> i ) & 0x1 ; lookup_table |= expected << bucket_idx ; lookup_table_complement |= ( 1 - expected ) << bucket_idx ; if ( lookup_table & lookup_table_complement ) break ; } if ( rule_id == off_group -> num_rules ) { on_group -> hash_idx [ i ] = hash_idx ; on_group -> lookup_table [ i ] = lookup_table ; hash_idx = start_hash_idx [ i ] + 1 ; break ; } hash_idx ++ ; } while ( hash_idx != start_hash_idx [ i ] ) ; if ( hash_idx == start_hash_idx [ i ] ) { for ( j = 0 ; j < i ; j ++ ) { on_group -> hash_idx [ j ] = start_hash_idx [ j ] ; on_group -> lookup_table [ j ] = start_lookup_table [ j ] ; } return 1 ; } } return 0 ; }
Search for a hash function for a group that satisfies all group results
Search for a hash function for a group that satisfies all group results
/*
	 * Prepopulate the hash_val tables by running the two hash functions
	 * for each provided rule
	 */ /*
			 * The goal here is to find a hash function for this
			 * particular bit entry that meets the following criteria:
			 * The most significant bits of the hash result define a
			 * shift into the lookup table where the bit will be stored
			 */ /* Iterate over each provided rule */ /*
				 * Use the few most significant bits (number based on
				 * EFD_LOOKUPTBL_SIZE) to see what position the
				 * expected bit should be set in the lookup_table
				 */ /*
				 * Get the current bit of interest.
				 * This only find an appropriate hash function
				 * for one bit at a time of the rule
				 */ /*
				 * Add the expected bit (if set) to a map
				 * (lookup_table). Also set its complement
				 * in lookup_table_complement
				 */ /*
				 * If ever the hash function of two different
				 * elements result in different values at the
				 * same location in the lookup_table,
				 * the current hash_idx is not valid.
				 */ /*
			 * Check if the previous loop completed without
			 * breaking early
			 */ /*
				 * Current hash function worked, store it
				 * for the current group
				 */ /*
				 * Make sure that the hash function has changed
				 * from the starting value
				 */ /* Failed to find perfect hash for this group */ /*
			 * Restore previous hash_idx and lookup_table
			 * for all value bits
			 */