1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
8 #include <rte_hash_crc.h>
10 #include "ip_frag_common.h"
12 #define PRIME_VALUE 0xeaad8405
14 #define IP_FRAG_TBL_POS(tbl, sig) \
15 ((tbl)->pkt + ((sig) & (tbl)->entry_mask))
17 #ifdef RTE_LIBRTE_IP_FRAG_TBL_STAT
18 #define IP_FRAG_TBL_STAT_UPDATE(s, f, v) ((s)->f += (v))
20 #define IP_FRAG_TBL_STAT_UPDATE(s, f, v) do {} while (0)
21 #endif /* IP_FRAG_TBL_STAT */
23 /* local frag table helper functions */
25 ip_frag_tbl_del(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
26 struct ip_frag_pkt *fp)
29 ip_frag_key_invalidate(&fp->key);
30 TAILQ_REMOVE(&tbl->lru, fp, lru);
32 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, del_num, 1);
36 ip_frag_tbl_add(struct rte_ip_frag_tbl *tbl, struct ip_frag_pkt *fp,
37 const struct ip_frag_key *key, uint64_t tms)
40 ip_frag_reset(fp, tms);
41 TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
43 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, add_num, 1);
47 ip_frag_tbl_reuse(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
48 struct ip_frag_pkt *fp, uint64_t tms)
51 ip_frag_reset(fp, tms);
52 TAILQ_REMOVE(&tbl->lru, fp, lru);
53 TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
54 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, reuse_num, 1);
59 ipv4_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2)
64 p = (const uint32_t *)&key->src_dst;
67 v = rte_hash_crc_4byte(p[0], PRIME_VALUE);
68 v = rte_hash_crc_4byte(p[1], v);
69 v = rte_hash_crc_4byte(key->id, v);
72 v = rte_jhash_3words(p[0], p[1], key->id, PRIME_VALUE);
73 #endif /* RTE_ARCH_X86 */
76 *v2 = (v << 7) + (v >> 14);
80 ipv6_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2)
85 p = (const uint32_t *) &key->src_dst;
88 v = rte_hash_crc_4byte(p[0], PRIME_VALUE);
89 v = rte_hash_crc_4byte(p[1], v);
90 v = rte_hash_crc_4byte(p[2], v);
91 v = rte_hash_crc_4byte(p[3], v);
92 v = rte_hash_crc_4byte(p[4], v);
93 v = rte_hash_crc_4byte(p[5], v);
94 v = rte_hash_crc_4byte(p[6], v);
95 v = rte_hash_crc_4byte(p[7], v);
96 v = rte_hash_crc_4byte(key->id, v);
99 v = rte_jhash_3words(p[0], p[1], p[2], PRIME_VALUE);
100 v = rte_jhash_3words(p[3], p[4], p[5], v);
101 v = rte_jhash_3words(p[6], p[7], key->id, v);
102 #endif /* RTE_ARCH_X86 */
105 *v2 = (v << 7) + (v >> 14);
109 ip_frag_process(struct ip_frag_pkt *fp, struct rte_ip_frag_death_row *dr,
110 struct rte_mbuf *mb, uint16_t ofs, uint16_t len, uint16_t more_frags)
114 fp->frag_size += len;
116 /* this is the first fragment. */
118 idx = (fp->frags[IP_FIRST_FRAG_IDX].mb == NULL) ?
119 IP_FIRST_FRAG_IDX : UINT32_MAX;
121 /* this is the last fragment. */
122 } else if (more_frags == 0) {
123 fp->total_size = ofs + len;
124 idx = (fp->frags[IP_LAST_FRAG_IDX].mb == NULL) ?
125 IP_LAST_FRAG_IDX : UINT32_MAX;
127 /* this is the intermediate fragment. */
128 } else if ((idx = fp->last_idx) <
129 sizeof (fp->frags) / sizeof (fp->frags[0])) {
134 * erroneous packet: either exceed max allowed number of fragments,
135 * or duplicate first/last fragment encountered.
137 if (idx >= sizeof (fp->frags) / sizeof (fp->frags[0])) {
139 /* report an error. */
140 if (fp->key.key_len == IPV4_KEYLEN)
141 IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
142 "ipv4_frag_pkt: %p, key: <%" PRIx64 ", %#x>, "
143 "total_size: %u, frag_size: %u, last_idx: %u\n"
144 "first fragment: ofs: %u, len: %u\n"
145 "last fragment: ofs: %u, len: %u\n\n",
147 fp, fp->key.src_dst[0], fp->key.id,
148 fp->total_size, fp->frag_size, fp->last_idx,
149 fp->frags[IP_FIRST_FRAG_IDX].ofs,
150 fp->frags[IP_FIRST_FRAG_IDX].len,
151 fp->frags[IP_LAST_FRAG_IDX].ofs,
152 fp->frags[IP_LAST_FRAG_IDX].len);
154 IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
155 "ipv4_frag_pkt: %p, key: <" IPv6_KEY_BYTES_FMT ", %#x>, "
156 "total_size: %u, frag_size: %u, last_idx: %u\n"
157 "first fragment: ofs: %u, len: %u\n"
158 "last fragment: ofs: %u, len: %u\n\n",
160 fp, IPv6_KEY_BYTES(fp->key.src_dst), fp->key.id,
161 fp->total_size, fp->frag_size, fp->last_idx,
162 fp->frags[IP_FIRST_FRAG_IDX].ofs,
163 fp->frags[IP_FIRST_FRAG_IDX].len,
164 fp->frags[IP_LAST_FRAG_IDX].ofs,
165 fp->frags[IP_LAST_FRAG_IDX].len);
167 /* free all fragments, invalidate the entry. */
168 ip_frag_free(fp, dr);
169 ip_frag_key_invalidate(&fp->key);
170 IP_FRAG_MBUF2DR(dr, mb);
175 fp->frags[idx].ofs = ofs;
176 fp->frags[idx].len = len;
177 fp->frags[idx].mb = mb;
181 /* not all fragments are collected yet. */
182 if (likely (fp->frag_size < fp->total_size)) {
185 /* if we collected all fragments, then try to reassemble. */
186 } else if (fp->frag_size == fp->total_size &&
187 fp->frags[IP_FIRST_FRAG_IDX].mb != NULL) {
188 if (fp->key.key_len == IPV4_KEYLEN)
189 mb = ipv4_frag_reassemble(fp);
191 mb = ipv6_frag_reassemble(fp);
194 /* errorenous set of fragments. */
197 /* report an error. */
198 if (fp->key.key_len == IPV4_KEYLEN)
199 IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
200 "ipv4_frag_pkt: %p, key: <%" PRIx64 ", %#x>, "
201 "total_size: %u, frag_size: %u, last_idx: %u\n"
202 "first fragment: ofs: %u, len: %u\n"
203 "last fragment: ofs: %u, len: %u\n\n",
205 fp, fp->key.src_dst[0], fp->key.id,
206 fp->total_size, fp->frag_size, fp->last_idx,
207 fp->frags[IP_FIRST_FRAG_IDX].ofs,
208 fp->frags[IP_FIRST_FRAG_IDX].len,
209 fp->frags[IP_LAST_FRAG_IDX].ofs,
210 fp->frags[IP_LAST_FRAG_IDX].len);
212 IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
213 "ipv4_frag_pkt: %p, key: <" IPv6_KEY_BYTES_FMT ", %#x>, "
214 "total_size: %u, frag_size: %u, last_idx: %u\n"
215 "first fragment: ofs: %u, len: %u\n"
216 "last fragment: ofs: %u, len: %u\n\n",
218 fp, IPv6_KEY_BYTES(fp->key.src_dst), fp->key.id,
219 fp->total_size, fp->frag_size, fp->last_idx,
220 fp->frags[IP_FIRST_FRAG_IDX].ofs,
221 fp->frags[IP_FIRST_FRAG_IDX].len,
222 fp->frags[IP_LAST_FRAG_IDX].ofs,
223 fp->frags[IP_LAST_FRAG_IDX].len);
225 /* free associated resources. */
226 ip_frag_free(fp, dr);
229 /* we are done with that entry, invalidate it. */
230 ip_frag_key_invalidate(&fp->key);
236 * Find an entry in the table for the corresponding fragment.
237 * If such entry is not present, then allocate a new one.
238 * If the entry is stale, then free and reuse it.
241 ip_frag_find(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
242 const struct ip_frag_key *key, uint64_t tms)
244 struct ip_frag_pkt *pkt, *free, *stale, *lru;
248 * Actually the two line below are totally redundant.
249 * they are here, just to make gcc 4.6 happy.
253 max_cycles = tbl->max_cycles;
255 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, find_num, 1);
257 if ((pkt = ip_frag_lookup(tbl, key, tms, &free, &stale)) == NULL) {
259 /*timed-out entry, free and invalidate it*/
261 ip_frag_tbl_del(tbl, dr, stale);
265 * we found a free entry, check if we can use it.
266 * If we run out of free entries in the table, then
267 * check if we have a timed out entry to delete.
269 } else if (free != NULL &&
270 tbl->max_entries <= tbl->use_entries) {
271 lru = TAILQ_FIRST(&tbl->lru);
272 if (max_cycles + lru->start < tms) {
273 ip_frag_tbl_del(tbl, dr, lru);
276 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat,
281 /* found a free entry to reuse. */
283 ip_frag_tbl_add(tbl, free, key, tms);
288 * we found the flow, but it is already timed out,
289 * so free associated resources, reposition it in the LRU list,
292 } else if (max_cycles + pkt->start < tms) {
293 ip_frag_tbl_reuse(tbl, dr, pkt, tms);
296 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, fail_total, (pkt == NULL));
303 ip_frag_lookup(struct rte_ip_frag_tbl *tbl,
304 const struct ip_frag_key *key, uint64_t tms,
305 struct ip_frag_pkt **free, struct ip_frag_pkt **stale)
307 struct ip_frag_pkt *p1, *p2;
308 struct ip_frag_pkt *empty, *old;
310 uint32_t i, assoc, sig1, sig2;
315 max_cycles = tbl->max_cycles;
316 assoc = tbl->bucket_entries;
318 if (tbl->last != NULL && ip_frag_key_cmp(key, &tbl->last->key) == 0)
321 /* different hashing methods for IPv4 and IPv6 */
322 if (key->key_len == IPV4_KEYLEN)
323 ipv4_frag_hash(key, &sig1, &sig2);
325 ipv6_frag_hash(key, &sig1, &sig2);
327 p1 = IP_FRAG_TBL_POS(tbl, sig1);
328 p2 = IP_FRAG_TBL_POS(tbl, sig2);
330 for (i = 0; i != assoc; i++) {
331 if (p1->key.key_len == IPV4_KEYLEN)
332 IP_FRAG_LOG(DEBUG, "%s:%d:\n"
333 "tbl: %p, max_entries: %u, use_entries: %u\n"
334 "ipv6_frag_pkt line0: %p, index: %u from %u\n"
335 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
337 tbl, tbl->max_entries, tbl->use_entries,
339 p1[i].key.src_dst[0], p1[i].key.id, p1[i].start);
341 IP_FRAG_LOG(DEBUG, "%s:%d:\n"
342 "tbl: %p, max_entries: %u, use_entries: %u\n"
343 "ipv6_frag_pkt line0: %p, index: %u from %u\n"
344 "key: <" IPv6_KEY_BYTES_FMT ", %#x>, start: %" PRIu64 "\n",
346 tbl, tbl->max_entries, tbl->use_entries,
348 IPv6_KEY_BYTES(p1[i].key.src_dst), p1[i].key.id, p1[i].start);
350 if (ip_frag_key_cmp(key, &p1[i].key) == 0)
352 else if (ip_frag_key_is_empty(&p1[i].key))
353 empty = (empty == NULL) ? (p1 + i) : empty;
354 else if (max_cycles + p1[i].start < tms)
355 old = (old == NULL) ? (p1 + i) : old;
357 if (p2->key.key_len == IPV4_KEYLEN)
358 IP_FRAG_LOG(DEBUG, "%s:%d:\n"
359 "tbl: %p, max_entries: %u, use_entries: %u\n"
360 "ipv6_frag_pkt line1: %p, index: %u from %u\n"
361 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
363 tbl, tbl->max_entries, tbl->use_entries,
365 p2[i].key.src_dst[0], p2[i].key.id, p2[i].start);
367 IP_FRAG_LOG(DEBUG, "%s:%d:\n"
368 "tbl: %p, max_entries: %u, use_entries: %u\n"
369 "ipv6_frag_pkt line1: %p, index: %u from %u\n"
370 "key: <" IPv6_KEY_BYTES_FMT ", %#x>, start: %" PRIu64 "\n",
372 tbl, tbl->max_entries, tbl->use_entries,
374 IPv6_KEY_BYTES(p2[i].key.src_dst), p2[i].key.id, p2[i].start);
376 if (ip_frag_key_cmp(key, &p2[i].key) == 0)
378 else if (ip_frag_key_is_empty(&p2[i].key))
379 empty = (empty == NULL) ?( p2 + i) : empty;
380 else if (max_cycles + p2[i].start < tms)
381 old = (old == NULL) ? (p2 + i) : old;