1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
/*-
* BSD LICENSE
*
* Copyright(c) 2010-2017 Intel Corporation. All rights reserved.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
* * Neither the name of Intel Corporation nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef __INCLUDE_RTE_TABLE_HASH_H__
#define __INCLUDE_RTE_TABLE_HASH_H__
#ifdef __cplusplus
extern "C" {
#endif
/**
* @file
* RTE Table Hash
*
* These tables use the exact match criterion to uniquely associate data to
* lookup keys.
*
* 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. Use-cases: flow cache, etc.
* 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. Use-cases: flow table, etc.
* 2. Key size:
* a. Configurable key size
* b. Single key size (8-byte, 16-byte or 32-byte key size)
*
***/
#include <stdint.h>
#include "rte_table.h"
/** Hash function */
typedef uint64_t (*rte_table_hash_op_hash)(
void *key,
void *key_mask,
uint32_t key_size,
uint64_t seed);
/** Hash table parameters */
struct rte_table_hash_params {
/** Name */
const char *name;
/** Key size (number of bytes) */
uint32_t key_size;
/** Byte offset within packet meta-data where the key is located */
uint32_t key_offset;
/** Key mask */
uint8_t *key_mask;
/** Number of keys */
uint32_t n_keys;
/** Number of buckets */
uint32_t n_buckets;
/** Hash function */
rte_table_hash_op_hash f_hash;
/** Seed value for the hash function */
uint64_t seed;
};
/** Extendible bucket hash table operations */
extern struct rte_table_ops rte_table_hash_ext_ops;
extern struct rte_table_ops rte_table_hash_key8_ext_ops;
extern struct rte_table_ops rte_table_hash_key16_ext_ops;
extern struct rte_table_ops rte_table_hash_key32_ext_ops;
/** LRU hash table operations */
extern struct rte_table_ops rte_table_hash_lru_ops;
extern struct rte_table_ops rte_table_hash_key8_lru_ops;
extern struct rte_table_ops rte_table_hash_key16_lru_ops;
extern struct rte_table_ops rte_table_hash_key32_lru_ops;
/** Cuckoo hash table operations */
extern struct rte_table_ops rte_table_hash_cuckoo_ops;
#ifdef __cplusplus
}
#endif
#endif
|
