src/dpdk/lib/librte_efd/rte_efd.c
static inline int
efd_compute_update(struct rte_efd_table * const table,
		const unsigned int socket_id, const void *key,
		const efd_value_t value, uint32_t * const chunk_id,
		uint32_t * const group_id, uint32_t * const bin_id,
		uint8_t * const new_bin_choice,
		struct efd_online_group_entry * const entry)
{
	unsigned int i;
	int ret;
	uint32_t new_idx;
	void *new_k, *slot_id = NULL;
	int status = EXIT_SUCCESS;
	unsigned int found = 0;

	efd_compute_ids(table, key, chunk_id, bin_id);

	struct efd_offline_chunk_rules * const chunk =
			&table->offline_chunks[*chunk_id];
	struct efd_offline_group_rules *new_group;

	uint8_t current_choice = efd_get_choice(table, socket_id,
			*chunk_id, *bin_id);
	uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
	struct efd_offline_group_rules * const current_group =
			&chunk->group_rules[current_group_id];
	uint8_t bin_size = 0;
	uint8_t key_changed_index = 0;
	efd_value_t key_changed_previous_value = 0;
	uint32_t key_idx_previous = 0;

	/* Scan the current group and see if the key is already present */
	for (i = 0; i < current_group->num_rules; i++) {
		if (current_group->bin_id[i] == *bin_id)
			bin_size++;
		else
			continue;

		void *key_stored = EFD_KEY(current_group->key_idx[i], table);
		if (found == 0 && unlikely(memcmp(key_stored, key,
				table->key_len) == 0)) {
			/* Key is already present */

			/*
			 * If previous value is same as new value,
			 * no additional work is required
			 */
			if (current_group->value[i] == value)
				return RTE_EFD_UPDATE_NO_CHANGE;

			key_idx_previous = current_group->key_idx[i];
			key_changed_previous_value = current_group->value[i];
			key_changed_index = i;
			current_group->value[i] = value;
			found = 1;
		}
	}

	if (found == 0) {
		/* Key does not exist. Insert the rule into the bin/group */
		if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
			RTE_LOG(ERR, EFD,
					"Fatal: No room remaining for insert into "
					"chunk %u group %u bin %u\n",
					*chunk_id,
					current_group_id, *bin_id);
			return RTE_EFD_UPDATE_FAILED;
		}

		if (unlikely(current_group->num_rules ==
				(EFD_MAX_GROUP_NUM_RULES - 1))) {
			RTE_LOG(INFO, EFD, "Warn: Insert into last "
					"available slot in chunk %u "
					"group %u bin %u\n", *chunk_id,
					current_group_id, *bin_id);
			status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
		}

		if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
			return RTE_EFD_UPDATE_FAILED;

		new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
					table->key_len);
		rte_prefetch0(new_k);
		new_idx = (uint32_t) ((uintptr_t) slot_id);

		rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
		current_group->key_idx[current_group->num_rules] = new_idx;
		current_group->value[current_group->num_rules] = value;
		current_group->bin_id[current_group->num_rules] = *bin_id;
		current_group->num_rules++;
		table->num_rules++;
		bin_size++;
	} else {
		uint32_t last = current_group->num_rules - 1;
		/* Swap the key with the last key inserted*/
		current_group->key_idx[key_changed_index] =
				current_group->key_idx[last];
		current_group->value[key_changed_index] =
				current_group->value[last];
		current_group->bin_id[key_changed_index] =
				current_group->bin_id[last];

		/*
		 * Key to be updated will always be available
		 * at the end of the group
		 */
		current_group->key_idx[last] = key_idx_previous;
		current_group->value[last] = value;
		current_group->bin_id[last] = *bin_id;
	}

	*new_bin_choice = current_choice;
	*group_id = current_group_id;
	new_group = current_group;

	/* Group need to be rebalanced when it starts to get loaded */
	if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {

		/*
		 * Subtract the number of entries in the bin from
		 * the original group
		 */
		current_group->num_rules -= bin_size;

		/*
		 * Figure out which of the available groups that this bin
		 * can map to is the smallest (using the current group
		 * as baseline)
		 */
		uint8_t smallest_choice = current_choice;
		uint8_t smallest_size = current_group->num_rules;
		uint32_t smallest_group_id = current_group_id;
		unsigned char choice;

		for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
				choice++) {
			uint32_t test_group_id =
					efd_bin_to_group[choice][*bin_id];
			uint32_t num_rules =
					chunk->group_rules[test_group_id].num_rules;
			if (num_rules < smallest_size) {
				smallest_choice = choice;
				smallest_size = num_rules;
				smallest_group_id = test_group_id;
			}
		}

		*new_bin_choice = smallest_choice;
		*group_id = smallest_group_id;
		new_group = &chunk->group_rules[smallest_group_id];
		current_group->num_rules += bin_size;

	}

	uint8_t choice = 0;
	for (;;) {
		if (current_group != new_group &&
				new_group->num_rules + bin_size >
					EFD_MAX_GROUP_NUM_RULES) {
			RTE_LOG(DEBUG, EFD,
					"Unable to move_groups to dest group "
					"containing %u entries."
					"bin_size:%u choice:%02x\n",
					new_group->num_rules, bin_size,
					choice - 1);
			goto next_choice;
		}
		move_groups(*bin_id, bin_size, new_group, current_group);
		/*
		 * Recompute the hash function for the modified group,
		 * and return it to the caller
		 */
		ret = efd_search_hash(table, new_group, entry);

		if (!ret)
			return status;

		RTE_LOG(DEBUG, EFD,
				"Failed to find perfect hash for group "
				"containing %u entries. bin_size:%u choice:%02x\n",
				new_group->num_rules, bin_size, choice - 1);
		/* Restore groups modified to their previous state */
		revert_groups(current_group, new_group, bin_size);

next_choice:
		if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
			break;
		*new_bin_choice = choice;
		*group_id = efd_bin_to_group[choice][*bin_id];
		new_group = &chunk->group_rules[*group_id];
		choice++;
	}

	if (!found) {
		current_group->num_rules--;
		table->num_rules--;
	} else
		current_group->value[current_group->num_rules - 1] =
			key_changed_previous_value;
	return RTE_EFD_UPDATE_FAILED;
}
/**
 * Computes an updated table entry where the supplied key points to a new host.
 * If no entry exists, one is inserted.
 *
 * This function does NOT modify the online table(s)
 * This function DOES modify the offline table
 *
 * @param table
 *   EFD table to reference
 * @param socket_id
 *   Socket ID to use to lookup existing values (ideally caller's socket id)
 * @param key
 *   Key to insert
 * @param value
 *   Value to associate with key
 * @param chunk_id
 *   Chunk ID of the chunk that was modified
 * @param group_id
 *   Group ID of the group that was modified
 * @param bin_id
 *   Bin ID that was modified
 * @param new_bin_choice
 *   Newly chosen permutation which this bin will use
 * @param entry
 *   Newly computed online entry to apply later with efd_apply_update
 *
 * @return
 *   RTE_EFD_UPDATE_WARN_GROUP_FULL
 *     Operation is insert, and the last available space in the
 *     key's group was just used. Future inserts may fail as groups fill up.
 *     This operation was still successful, and entry contains a valid update
 *   RTE_EFD_UPDATE_FAILED
 *     Either the EFD failed to find a suitable perfect hash or the group was full
 *     This is a fatal error, and the table is now in an indeterminate state
 *   RTE_EFD_UPDATE_NO_CHANGE
 *     Operation resulted in no change to the table (same value already exists)
 *   0
 *     Insert or update was successful, and the new efd_online_group_entry
 *     is stored in *entry
 *
 * @warning
 *   Note that entry will be UNCHANGED if the update has no effect, and thus any
 *   subsequent use of the entry content will likely be invalid
 */
Computes an updated table entry where the supplied key points to a new host.
If no entry exists, one is inserted.

This function does NOT modify the online table(s)
This function DOES modify the offline table



@return
RTE_EFD_UPDATE_WARN_GROUP_FULL
Operation is insert, and the last available space in the
key's group was just used. Future inserts may fail as groups fill up.
This operation was still successful, and entry contains a valid update
RTE_EFD_UPDATE_FAILED
Either the EFD failed to find a suitable perfect hash or the group was full
This is a fatal error, and the table is now in an indeterminate state
RTE_EFD_UPDATE_NO_CHANGE
Operation resulted in no change to the table (same value already exists)
0
Insert or update was successful, and the new efd_online_group_entry
is stored in *entry

@warning
Note that entry will be UNCHANGED if the update has no effect, and thus any
subsequent use of the entry content will likely be invalid
Computes an updated table entry where the supplied key points to a new host . If no entry exists one is inserted . This function does NOT modify the online table ( s ) This function DOES modify the offline table @return RTE_EFD_UPDATE_WARN_GROUP_FULL Operation is insert and the last available space in the key ' s group was just used . Future inserts may fail as groups fill up . This operation was still successful and entry contains a valid update RTE_EFD_UPDATE_FAILED Either the EFD failed to find a suitable perfect hash or the group was full This is a fatal error and the table is now in an indeterminate state RTE_EFD_UPDATE_NO_CHANGE Operation resulted in no change to the table ( same value already exists ) 0 Insert or update was successful and the new efd_online_group_entry is stored in * entry @warning Note that entry will be UNCHANGED if the update has no effect and thus any subsequent use of the entry content will likely be invalid
static inline int
efd_compute_update(struct rte_efd_table * const table,
		const unsigned int socket_id, const void *key,
		const efd_value_t value, uint32_t * const chunk_id,
		uint32_t * const group_id, uint32_t * const bin_id,
		uint8_t * const new_bin_choice,
		struct efd_online_group_entry * const entry)
{
	unsigned int i;
	int ret;
	uint32_t new_idx;
	void *new_k, *slot_id = NULL;
	int status = EXIT_SUCCESS;
	unsigned int found = 0;
	efd_compute_ids(table, key, chunk_id, bin_id);
	struct efd_offline_chunk_rules * const chunk =
			&table->offline_chunks[*chunk_id];
	struct efd_offline_group_rules *new_group;
	uint8_t current_choice = efd_get_choice(table, socket_id,
			*chunk_id, *bin_id);
	uint32_t current_group_id = efd_bin_to_group[current_choice][*bin_id];
	struct efd_offline_group_rules * const current_group =
			&chunk->group_rules[current_group_id];
	uint8_t bin_size = 0;
	uint8_t key_changed_index = 0;
	efd_value_t key_changed_previous_value = 0;
	uint32_t key_idx_previous = 0;
	for (i = 0; i < current_group->num_rules; i++) {
		if (current_group->bin_id[i] == *bin_id)
			bin_size++;
		else
			continue;
		void *key_stored = EFD_KEY(current_group->key_idx[i], table);
		if (found == 0 && unlikely(memcmp(key_stored, key,
				table->key_len) == 0)) {
			if (current_group->value[i] == value)
				return RTE_EFD_UPDATE_NO_CHANGE;
			key_idx_previous = current_group->key_idx[i];
			key_changed_previous_value = current_group->value[i];
			key_changed_index = i;
			current_group->value[i] = value;
			found = 1;
		}
	}
	if (found == 0) {
		if (unlikely(current_group->num_rules >= EFD_MAX_GROUP_NUM_RULES)) {
			RTE_LOG(ERR, EFD,
					"Fatal: No room remaining for insert into "
					"chunk %u group %u bin %u\n",
					*chunk_id,
					current_group_id, *bin_id);
			return RTE_EFD_UPDATE_FAILED;
		}
		if (unlikely(current_group->num_rules ==
				(EFD_MAX_GROUP_NUM_RULES - 1))) {
			RTE_LOG(INFO, EFD, "Warn: Insert into last "
					"available slot in chunk %u "
					"group %u bin %u\n", *chunk_id,
					current_group_id, *bin_id);
			status = RTE_EFD_UPDATE_WARN_GROUP_FULL;
		}
		if (rte_ring_sc_dequeue(table->free_slots, &slot_id) != 0)
			return RTE_EFD_UPDATE_FAILED;
		new_k = RTE_PTR_ADD(table->keys, (uintptr_t) slot_id *
					table->key_len);
		rte_prefetch0(new_k);
		new_idx = (uint32_t) ((uintptr_t) slot_id);
		rte_memcpy(EFD_KEY(new_idx, table), key, table->key_len);
		current_group->key_idx[current_group->num_rules] = new_idx;
		current_group->value[current_group->num_rules] = value;
		current_group->bin_id[current_group->num_rules] = *bin_id;
		current_group->num_rules++;
		table->num_rules++;
		bin_size++;
	} else {
		uint32_t last = current_group->num_rules - 1;
		current_group->key_idx[key_changed_index] =
				current_group->key_idx[last];
		current_group->value[key_changed_index] =
				current_group->value[last];
		current_group->bin_id[key_changed_index] =
				current_group->bin_id[last];
		current_group->key_idx[last] = key_idx_previous;
		current_group->value[last] = value;
		current_group->bin_id[last] = *bin_id;
	}
	*new_bin_choice = current_choice;
	*group_id = current_group_id;
	new_group = current_group;
	if (current_group->num_rules > EFD_MIN_BALANCED_NUM_RULES) {
		current_group->num_rules -= bin_size;
		uint8_t smallest_choice = current_choice;
		uint8_t smallest_size = current_group->num_rules;
		uint32_t smallest_group_id = current_group_id;
		unsigned char choice;
		for (choice = 0; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS;
				choice++) {
			uint32_t test_group_id =
					efd_bin_to_group[choice][*bin_id];
			uint32_t num_rules =
					chunk->group_rules[test_group_id].num_rules;
			if (num_rules < smallest_size) {
				smallest_choice = choice;
				smallest_size = num_rules;
				smallest_group_id = test_group_id;
			}
		}
		*new_bin_choice = smallest_choice;
		*group_id = smallest_group_id;
		new_group = &chunk->group_rules[smallest_group_id];
		current_group->num_rules += bin_size;
	}
	uint8_t choice = 0;
	for (;;) {
		if (current_group != new_group &&
				new_group->num_rules + bin_size >
					EFD_MAX_GROUP_NUM_RULES) {
			RTE_LOG(DEBUG, EFD,
					"Unable to move_groups to dest group "
					"containing %u entries."
					"bin_size:%u choice:%02x\n",
					new_group->num_rules, bin_size,
					choice - 1);
			goto next_choice;
		}
		move_groups(*bin_id, bin_size, new_group, current_group);
		ret = efd_search_hash(table, new_group, entry);
		if (!ret)
			return status;
		RTE_LOG(DEBUG, EFD,
				"Failed to find perfect hash for group "
				"containing %u entries. bin_size:%u choice:%02x\n",
				new_group->num_rules, bin_size, choice - 1);
		revert_groups(current_group, new_group, bin_size);
next_choice:
		if (choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS)
			break;
		*new_bin_choice = choice;
		*group_id = efd_bin_to_group[choice][*bin_id];
		new_group = &chunk->group_rules[*group_id];
		choice++;
	}
	if (!found) {
		current_group->num_rules--;
		table->num_rules--;
	} else
		current_group->value[current_group->num_rules - 1] =
			key_changed_previous_value;
	return RTE_EFD_UPDATE_FAILED;
}
static inline int efd_compute_update ( struct rte_efd_table * const table , const unsigned int socket_id , const void * key , const efd_value_t value , uint32_t * const chunk_id , uint32_t * const group_id , uint32_t * const bin_id , uint8_t * const new_bin_choice , struct efd_online_group_entry * const entry ) { unsigned int i ; int ret ; uint32_t new_idx ; void * new_k , * slot_id = NULL ; int status = EXIT_SUCCESS ; unsigned int found = 0 ; efd_compute_ids ( table , key , chunk_id , bin_id ) ; struct efd_offline_chunk_rules * const chunk = & table -> offline_chunks [ * chunk_id ] ; struct efd_offline_group_rules * new_group ; uint8_t current_choice = efd_get_choice ( table , socket_id , * chunk_id , * bin_id ) ; uint32_t current_group_id = efd_bin_to_group [ current_choice ] [ * bin_id ] ; struct efd_offline_group_rules * const current_group = & chunk -> group_rules [ current_group_id ] ; uint8_t bin_size = 0 ; uint8_t key_changed_index = 0 ; efd_value_t key_changed_previous_value = 0 ; uint32_t key_idx_previous = 0 ; for ( i = 0 ; i < current_group -> num_rules ; i ++ ) { if ( current_group -> bin_id [ i ] == * bin_id ) bin_size ++ ; else continue ; void * key_stored = EFD_KEY ( current_group -> key_idx [ i ] , table ) ; if ( found == 0 && unlikely ( memcmp ( key_stored , key , table -> key_len ) == 0 ) ) { if ( current_group -> value [ i ] == value ) return RTE_EFD_UPDATE_NO_CHANGE ; key_idx_previous = current_group -> key_idx [ i ] ; key_changed_previous_value = current_group -> value [ i ] ; key_changed_index = i ; current_group -> value [ i ] = value ; found = 1 ; } } if ( found == 0 ) { if ( unlikely ( current_group -> num_rules >= EFD_MAX_GROUP_NUM_RULES ) ) { RTE_LOG ( ERR , EFD , " " " \n " , * chunk_id , current_group_id , * bin_id ) ; return RTE_EFD_UPDATE_FAILED ; } if ( unlikely ( current_group -> num_rules == ( EFD_MAX_GROUP_NUM_RULES - 1 ) ) ) { RTE_LOG ( INFO , EFD , " " " " " \n " , * chunk_id , current_group_id , * bin_id ) ; status = RTE_EFD_UPDATE_WARN_GROUP_FULL ; } if ( rte_ring_sc_dequeue ( table -> free_slots , & slot_id ) != 0 ) return RTE_EFD_UPDATE_FAILED ; new_k = RTE_PTR_ADD ( table -> keys , ( uintptr_t ) slot_id * table -> key_len ) ; rte_prefetch0 ( new_k ) ; new_idx = ( uint32_t ) ( ( uintptr_t ) slot_id ) ; rte_memcpy ( EFD_KEY ( new_idx , table ) , key , table -> key_len ) ; current_group -> key_idx [ current_group -> num_rules ] = new_idx ; current_group -> value [ current_group -> num_rules ] = value ; current_group -> bin_id [ current_group -> num_rules ] = * bin_id ; current_group -> num_rules ++ ; table -> num_rules ++ ; bin_size ++ ; } else { uint32_t last = current_group -> num_rules - 1 ; current_group -> key_idx [ key_changed_index ] = current_group -> key_idx [ last ] ; current_group -> value [ key_changed_index ] = current_group -> value [ last ] ; current_group -> bin_id [ key_changed_index ] = current_group -> bin_id [ last ] ; current_group -> key_idx [ last ] = key_idx_previous ; current_group -> value [ last ] = value ; current_group -> bin_id [ last ] = * bin_id ; } * new_bin_choice = current_choice ; * group_id = current_group_id ; new_group = current_group ; if ( current_group -> num_rules > EFD_MIN_BALANCED_NUM_RULES ) { current_group -> num_rules -= bin_size ; uint8_t smallest_choice = current_choice ; uint8_t smallest_size = current_group -> num_rules ; uint32_t smallest_group_id = current_group_id ; unsigned char choice ; for ( choice = 0 ; choice < EFD_CHUNK_NUM_BIN_TO_GROUP_SETS ; choice ++ ) { uint32_t test_group_id = efd_bin_to_group [ choice ] [ * bin_id ] ; uint32_t num_rules = chunk -> group_rules [ test_group_id ] . num_rules ; if ( num_rules < smallest_size ) { smallest_choice = choice ; smallest_size = num_rules ; smallest_group_id = test_group_id ; } } * new_bin_choice = smallest_choice ; * group_id = smallest_group_id ; new_group = & chunk -> group_rules [ smallest_group_id ] ; current_group -> num_rules += bin_size ; } uint8_t choice = 0 ; for ( ; ; ) { if ( current_group != new_group && new_group -> num_rules + bin_size > EFD_MAX_GROUP_NUM_RULES ) { RTE_LOG ( DEBUG , EFD , " " " " " \n " , new_group -> num_rules , bin_size , choice - 1 ) ; goto next_choice ; } move_groups ( * bin_id , bin_size , new_group , current_group ) ; ret = efd_search_hash ( table , new_group , entry ) ; if ( ! ret ) return status ; RTE_LOG ( DEBUG , EFD , " " " \n " , new_group -> num_rules , bin_size , choice - 1 ) ; revert_groups ( current_group , new_group , bin_size ) ; next_choice : if ( choice == EFD_CHUNK_NUM_BIN_TO_GROUP_SETS ) break ; * new_bin_choice = choice ; * group_id = efd_bin_to_group [ choice ] [ * bin_id ] ; new_group = & chunk -> group_rules [ * group_id ] ; choice ++ ; } if ( ! found ) { current_group -> num_rules -- ; table -> num_rules -- ; } else current_group -> value [ current_group -> num_rules - 1 ] = key_changed_previous_value ; return RTE_EFD_UPDATE_FAILED ; }
Computes an updated table entry where the supplied key points to a new host.
Computes an updated table entry where the supplied key points to a new host .
/* Scan the current group and see if the key is already present */ /* Key is already present */ /*
			 * If previous value is same as new value,
			 * no additional work is required
			 */ /* Key does not exist. Insert the rule into the bin/group */ /* Swap the key with the last key inserted*/ /*
		 * Key to be updated will always be available
		 * at the end of the group
		 */ /* Group need to be rebalanced when it starts to get loaded */ /*
		 * Subtract the number of entries in the bin from
		 * the original group
		 */ /*
		 * Figure out which of the available groups that this bin
		 * can map to is the smallest (using the current group
		 * as baseline)
		 */ /*
		 * Recompute the hash function for the modified group,
		 * and return it to the caller
		 */ /* Restore groups modified to their previous state */