4 * Copyright(c) 2010-2013 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 #ifndef _IPV4_FRAG_TBL_H_
36 #define _IPV4_FRAG_TBL_H_
40 * IPv4 fragments table.
42 * Implementation of IPv4 fragment table create/destroy/find/update.
47 * The ipv4_frag_tbl is a simple hash table:
48 * The basic idea is to use two hash functions and <bucket_entries>
49 * associativity. This provides 2 * <bucket_entries> possible locations in
50 * the hash table for each key. Sort of simplified Cuckoo hashing,
51 * when the collision occurs and all 2 * <bucket_entries> are occupied,
52 * instead of resinserting existing keys into alternative locations, we just
54 * Another thing timing: entries that resides in the table longer then
55 * <max_cycles> are considered as invalid, and could be removed/replaced
57 * <key, data> pair is stored together, all add/update/lookup opearions are not
61 #include <rte_jhash.h>
62 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
63 #include <rte_hash_crc.h>
64 #endif /* RTE_MACHINE_CPUFLAG_SSE4_2 */
66 #define PRIME_VALUE 0xeaad8405
68 TAILQ_HEAD(ipv4_pkt_list, ipv4_frag_pkt);
70 struct ipv4_frag_tbl_stat {
71 uint64_t find_num; /* total # of find/insert attempts. */
72 uint64_t add_num; /* # of add ops. */
73 uint64_t del_num; /* # of del ops. */
74 uint64_t reuse_num; /* # of reuse (del/add) ops. */
75 uint64_t fail_total; /* total # of add failures. */
76 uint64_t fail_nospace; /* # of 'no space' add failures. */
77 } __rte_cache_aligned;
79 struct ipv4_frag_tbl {
80 uint64_t max_cycles; /* ttl for table entries. */
81 uint32_t entry_mask; /* hash value mask. */
82 uint32_t max_entries; /* max entries allowed. */
83 uint32_t use_entries; /* entries in use. */
84 uint32_t bucket_entries; /* hash assocaitivity. */
85 uint32_t nb_entries; /* total size of the table. */
86 uint32_t nb_buckets; /* num of associativity lines. */
87 struct ipv4_frag_pkt *last; /* last used entry. */
88 struct ipv4_pkt_list lru; /* LRU list for table entries. */
89 struct ipv4_frag_tbl_stat stat; /* statistics counters. */
90 struct ipv4_frag_pkt pkt[0]; /* hash table. */
93 #define IPV4_FRAG_TBL_POS(tbl, sig) \
94 ((tbl)->pkt + ((sig) & (tbl)->entry_mask))
96 #define IPV4_FRAG_HASH_FNUM 2
98 #ifdef IPV4_FRAG_TBL_STAT
99 #define IPV4_FRAG_TBL_STAT_UPDATE(s, f, v) ((s)->f += (v))
101 #define IPV4_FRAG_TBL_STAT_UPDATE(s, f, v) do {} while (0)
102 #endif /* IPV4_FRAG_TBL_STAT */
105 ipv4_frag_hash(const struct ipv4_frag_key *key, uint32_t *v1, uint32_t *v2)
110 p = (const uint32_t *)&key->src_dst;
112 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
113 v = rte_hash_crc_4byte(p[0], PRIME_VALUE);
114 v = rte_hash_crc_4byte(p[1], v);
115 v = rte_hash_crc_4byte(key->id, v);
118 v = rte_jhash_3words(p[0], p[1], key->id, PRIME_VALUE);
119 #endif /* RTE_MACHINE_CPUFLAG_SSE4_2 */
122 *v2 = (v << 7) + (v >> 14);
126 * Update the table, after we finish processing it's entry.
129 ipv4_frag_inuse(struct ipv4_frag_tbl *tbl, const struct ipv4_frag_pkt *fp)
131 if (IPV4_FRAG_KEY_EMPTY(&fp->key)) {
132 TAILQ_REMOVE(&tbl->lru, fp, lru);
138 * For the given key, try to find an existing entry.
139 * If such entry doesn't exist, will return free and/or timed-out entry,
140 * that can be used for that key.
142 static inline struct ipv4_frag_pkt *
143 ipv4_frag_lookup(struct ipv4_frag_tbl *tbl,
144 const struct ipv4_frag_key *key, uint64_t tms,
145 struct ipv4_frag_pkt **free, struct ipv4_frag_pkt **stale)
147 struct ipv4_frag_pkt *p1, *p2;
148 struct ipv4_frag_pkt *empty, *old;
150 uint32_t i, assoc, sig1, sig2;
155 max_cycles = tbl->max_cycles;
156 assoc = tbl->bucket_entries;
158 if (tbl->last != NULL && IPV4_FRAG_KEY_CMP(&tbl->last->key, key) == 0)
161 ipv4_frag_hash(key, &sig1, &sig2);
162 p1 = IPV4_FRAG_TBL_POS(tbl, sig1);
163 p2 = IPV4_FRAG_TBL_POS(tbl, sig2);
165 for (i = 0; i != assoc; i++) {
167 IPV4_FRAG_LOG(DEBUG, "%s:%d:\n"
168 "tbl: %p, max_entries: %u, use_entries: %u\n"
169 "ipv4_frag_pkt line0: %p, index: %u from %u\n"
170 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
172 tbl, tbl->max_entries, tbl->use_entries,
174 p1[i].key.src_dst, p1[i].key.id, p1[i].start);
176 if (IPV4_FRAG_KEY_CMP(&p1[i].key, key) == 0)
178 else if (IPV4_FRAG_KEY_EMPTY(&p1[i].key))
179 empty = (empty == NULL) ? (p1 + i) : empty;
180 else if (max_cycles + p1[i].start < tms)
181 old = (old == NULL) ? (p1 + i) : old;
183 IPV4_FRAG_LOG(DEBUG, "%s:%d:\n"
184 "tbl: %p, max_entries: %u, use_entries: %u\n"
185 "ipv4_frag_pkt line1: %p, index: %u from %u\n"
186 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
188 tbl, tbl->max_entries, tbl->use_entries,
190 p2[i].key.src_dst, p2[i].key.id, p2[i].start);
192 if (IPV4_FRAG_KEY_CMP(&p2[i].key, key) == 0)
194 else if (IPV4_FRAG_KEY_EMPTY(&p2[i].key))
195 empty = (empty == NULL) ?( p2 + i) : empty;
196 else if (max_cycles + p2[i].start < tms)
197 old = (old == NULL) ? (p2 + i) : old;
206 ipv4_frag_tbl_del(struct ipv4_frag_tbl *tbl, struct ipv4_frag_pkt *fp)
209 IPV4_FRAG_KEY_INVALIDATE(&fp->key);
210 TAILQ_REMOVE(&tbl->lru, fp, lru);
212 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, del_num, 1);
216 ipv4_frag_tbl_add(struct ipv4_frag_tbl *tbl, struct ipv4_frag_pkt *fp,
217 const struct ipv4_frag_key *key, uint64_t tms)
220 ipv4_frag_reset(fp, tms);
221 TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
223 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, add_num, 1);
227 ipv4_frag_tbl_reuse(struct ipv4_frag_tbl *tbl, struct ipv4_frag_pkt *fp,
231 ipv4_frag_reset(fp, tms);
232 TAILQ_REMOVE(&tbl->lru, fp, lru);
233 TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
234 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, reuse_num, 1);
238 * Find an entry in the table for the corresponding fragment.
239 * If such entry is not present, then allocate a new one.
240 * If the entry is stale, then free and reuse it.
242 static inline struct ipv4_frag_pkt *
243 ipv4_frag_find(struct ipv4_frag_tbl *tbl, const struct ipv4_frag_key *key,
246 struct ipv4_frag_pkt *pkt, *free, *stale, *lru;
250 * Actually the two line below are totally redundant.
251 * they are here, just to make gcc 4.6 happy.
255 max_cycles = tbl->max_cycles;
257 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, find_num, 1);
259 if ((pkt = ipv4_frag_lookup(tbl, key, tms, &free, &stale)) == NULL) {
261 /*timed-out entry, free and invalidate it*/
263 ipv4_frag_tbl_del(tbl, stale);
267 * we found a free entry, check if we can use it.
268 * If we run out of free entries in the table, then
269 * check if we have a timed out entry to delete.
271 } else if (free != NULL &&
272 tbl->max_entries <= tbl->use_entries) {
273 lru = TAILQ_FIRST(&tbl->lru);
274 if (max_cycles + lru->start < tms) {
275 ipv4_frag_tbl_del(tbl, lru);
278 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat,
283 /* found a free entry to reuse. */
285 ipv4_frag_tbl_add(tbl, free, key, tms);
290 * we found the flow, but it is already timed out,
291 * so free associated resources, reposition it in the LRU list,
294 } else if (max_cycles + pkt->start < tms) {
295 ipv4_frag_tbl_reuse(tbl, pkt, tms);
298 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, fail_total, (pkt == NULL));
305 * Create a new IPV4 Frag table.
307 * Number of buckets in the hash table.
308 * @param bucket_entries
309 * Number of entries per bucket (e.g. hash associativity).
310 * Should be power of two.
312 * Maximum number of entries that could be stored in the table.
313 * The value should be less or equal then bucket_num * bucket_entries.
315 * Maximum TTL in cycles for each fragmented packet.
317 * The *socket_id* argument is the socket identifier in the case of
318 * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA constraints.
320 * The pointer to the new allocated mempool, on success. NULL on error.
322 static struct ipv4_frag_tbl *
323 ipv4_frag_tbl_create(uint32_t bucket_num, uint32_t bucket_entries,
324 uint32_t max_entries, uint64_t max_cycles, int socket_id)
326 struct ipv4_frag_tbl *tbl;
330 nb_entries = rte_align32pow2(bucket_num);
331 nb_entries *= bucket_entries;
332 nb_entries *= IPV4_FRAG_HASH_FNUM;
334 /* check input parameters. */
335 if (rte_is_power_of_2(bucket_entries) == 0 ||
336 nb_entries > UINT32_MAX || nb_entries == 0 ||
337 nb_entries < max_entries) {
338 RTE_LOG(ERR, USER1, "%s: invalid input parameter\n", __func__);
342 sz = sizeof (*tbl) + nb_entries * sizeof (tbl->pkt[0]);
343 if ((tbl = rte_zmalloc_socket(__func__, sz, CACHE_LINE_SIZE,
344 socket_id)) == NULL) {
346 "%s: allocation of %zu bytes at socket %d failed do\n",
347 __func__, sz, socket_id);
351 RTE_LOG(INFO, USER1, "%s: allocated of %zu bytes at socket %d\n",
352 __func__, sz, socket_id);
354 tbl->max_cycles = max_cycles;
355 tbl->max_entries = max_entries;
356 tbl->nb_entries = (uint32_t)nb_entries;
357 tbl->nb_buckets = bucket_num;
358 tbl->bucket_entries = bucket_entries;
359 tbl->entry_mask = (tbl->nb_entries - 1) & ~(tbl->bucket_entries - 1);
361 TAILQ_INIT(&(tbl->lru));
366 ipv4_frag_tbl_destroy( struct ipv4_frag_tbl *tbl)
372 ipv4_frag_tbl_dump_stat(FILE *f, const struct ipv4_frag_tbl *tbl)
374 uint64_t fail_total, fail_nospace;
376 fail_total = tbl->stat.fail_total;
377 fail_nospace = tbl->stat.fail_nospace;
379 fprintf(f, "max entries:\t%u;\n"
380 "entries in use:\t%u;\n"
381 "finds/inserts:\t%" PRIu64 ";\n"
382 "entries added:\t%" PRIu64 ";\n"
383 "entries deleted by timeout:\t%" PRIu64 ";\n"
384 "entries reused by timeout:\t%" PRIu64 ";\n"
385 "total add failures:\t%" PRIu64 ";\n"
386 "add no-space failures:\t%" PRIu64 ";\n"
387 "add hash-collisions failures:\t%" PRIu64 ";\n",
396 fail_total - fail_nospace);
400 #endif /* _IPV4_FRAG_TBL_H_ */