rte_table_hash.h File Reference

#include <stdint.h>
#include "rte_table.h"

Go to the source code of this file.

Data Structures
struct	rte_table_hash_ext_params
struct	rte_table_hash_lru_params
struct	rte_table_hash_key8_lru_params
struct	rte_table_hash_key8_ext_params
struct	rte_table_hash_key16_lru_params
struct	rte_table_hash_key16_ext_params
struct	rte_table_hash_key32_lru_params
struct	rte_table_hash_key32_ext_params
struct	rte_table_hash_cuckoo_params

Typedefs
typedef uint64_t(*	rte_table_hash_op_hash )(void *key, uint32_t key_size, uint64_t seed)

Variables
struct rte_table_ops	rte_table_hash_ext_ops
struct rte_table_ops	rte_table_hash_ext_dosig_ops
struct rte_table_ops	rte_table_hash_lru_ops
struct rte_table_ops	rte_table_hash_lru_dosig_ops
struct rte_table_ops	rte_table_hash_key8_lru_ops
struct rte_table_ops	rte_table_hash_key8_lru_dosig_ops
struct rte_table_ops	rte_table_hash_key8_ext_ops
struct rte_table_ops	rte_table_hash_key8_ext_dosig_ops
struct rte_table_ops	rte_table_hash_key16_lru_ops
struct rte_table_ops	rte_table_hash_key16_lru_dosig_ops
struct rte_table_ops	rte_table_hash_key16_ext_ops
struct rte_table_ops	rte_table_hash_key16_ext_dosig_ops
struct rte_table_ops	rte_table_hash_key32_lru_ops
struct rte_table_ops	rte_table_hash_key32_ext_ops
struct rte_table_ops	rte_table_hash_cuckoo_dosig_ops

Detailed Description

RTE Table Hash

These tables use the exact match criterion to uniquely associate data to lookup keys.

Use-cases: Flow classification table, Address Resolution Protocol (ARP) table

Hash table types:

1. Entry add strategy on bucket full: a. Least Recently Used (LRU): One of the existing keys in the bucket is deleted and the new key is added in its place. The number of keys in each bucket never grows bigger than 4. The logic to pick the key to be dropped from the bucket is LRU. The hash table lookup operation maintains the order in which the keys in the same bucket are hit, so every time a key is hit, it becomes the new Most Recently Used (MRU) key, i.e. the most unlikely candidate for drop. When a key is added to the bucket, it also becomes the new MRU key. When a key needs to be picked and dropped, the most likely candidate for drop, i.e. the current LRU key, is always picked. The LRU logic requires maintaining specific data structures per each bucket. b. Extendible bucket (ext): The bucket is extended with space for 4 more keys. This is done by allocating additional memory at table init time, which is used to create a pool of free keys (the size of this pool is configurable and always a multiple of 4). On key add operation, the allocation of a group of 4 keys only happens successfully within the limit of free keys, otherwise the key add operation fails. On key delete operation, a group of 4 keys is freed back to the pool of free keys when the key to be deleted is the only key that was used within its group of 4 keys at that time. On key lookup operation, if the current bucket is in extended state and a match is not found in the first group of 4 keys, the search continues beyond the first group of 4 keys, potentially until all keys in this bucket are examined. The extendible bucket logic requires maintaining specific data structures per table and per each bucket.
2. Key signature computation: a. Pre-computed key signature: The key lookup operation is split between two CPU cores. The first CPU core (typically the CPU core performing packet RX) extracts the key from the input packet, computes the key signature and saves both the key and the key signature in the packet buffer as packet meta-data. The second CPU core reads both the key and the key signature from the packet meta-data and performs the bucket search step of the key lookup operation. b. Key signature computed on lookup (do-sig): The same CPU core reads the key from the packet meta-data, uses it to compute the key signature and also performs the bucket search step of the key lookup operation.
3. Key size: a. Configurable key size b. Single key size (8-byte, 16-byte or 32-byte key size)

Definition in file rte_table_hash.h.

Typedef Documentation

typedef uint64_t(* rte_table_hash_op_hash)(void *key, uint32_t key_size, uint64_t seed)

Hash function

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c, and examples/ip_pipeline/pipeline/pipeline_passthrough_be.c.

Definition at line 99 of file rte_table_hash.h.

Variable Documentation

struct rte_table_ops rte_table_hash_ext_ops

Extendible bucket hash table operations for pre-computed key signature

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c.

struct rte_table_ops rte_table_hash_ext_dosig_ops

Extendible bucket hash table operations for key signature computed on lookup ("do-sig")

struct rte_table_ops rte_table_hash_lru_ops

LRU hash table operations for pre-computed key signature

struct rte_table_ops rte_table_hash_lru_dosig_ops

LRU hash table operations for key signature computed on lookup ("do-sig")

struct rte_table_ops rte_table_hash_key8_lru_ops

LRU hash table operations for pre-computed key signature

struct rte_table_ops rte_table_hash_key8_lru_dosig_ops

LRU hash table operations for key signature computed on lookup ("do-sig")

struct rte_table_ops rte_table_hash_key8_ext_ops

Extendible bucket hash table operations for pre-computed key signature

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c.

struct rte_table_ops rte_table_hash_key8_ext_dosig_ops

Extendible bucket hash table operations for key signature computed on lookup ("do-sig")

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c, and examples/ip_pipeline/pipeline/pipeline_routing_be.c.

struct rte_table_ops rte_table_hash_key16_lru_ops

LRU hash table operations for pre-computed key signature

struct rte_table_ops rte_table_hash_key16_lru_dosig_ops

LRU hash table operations for key signature computed on lookup ("do-sig")

struct rte_table_ops rte_table_hash_key16_ext_ops

Extendible bucket operations for pre-computed key signature

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c.

struct rte_table_ops rte_table_hash_key16_ext_dosig_ops

Extendible bucket hash table operations for key signature computed on lookup ("do-sig")

Examples:

examples/ip_pipeline/pipeline/pipeline_flow_classification_be.c.

struct rte_table_ops rte_table_hash_key32_lru_ops

LRU hash table operations for pre-computed key signature

struct rte_table_ops rte_table_hash_key32_ext_ops

Extendible bucket hash table operations

struct rte_table_ops rte_table_hash_cuckoo_dosig_ops

Cuckoo hash table operations