Branch data Line data Source code
1 : : /* SPDX-License-Identifier: BSD-3-Clause
2 : : * Copyright(c) 2010-2014 Intel Corporation
3 : : */
4 : :
5 : : #include <stddef.h>
6 : :
7 : : #include <rte_jhash.h>
8 : : #include <rte_hash_crc.h>
9 : :
10 : : #include "ip_frag_common.h"
11 : :
12 : : #define IP_FRAG_TBL_POS(tbl, sig) \
13 : : ((tbl)->pkt + ((sig) & (tbl)->entry_mask))
14 : :
15 : : static inline void
16 : : ip_frag_tbl_add(struct rte_ip_frag_tbl *tbl, struct ip_frag_pkt *fp,
17 : : const struct ip_frag_key *key, uint64_t tms)
18 : : {
19 : 459 : fp->key = key[0];
20 : : ip_frag_reset(fp, tms);
21 : 459 : TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
22 : 459 : tbl->use_entries++;
23 : : IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, add_num, 1);
24 : : }
25 : :
26 : : static inline void
27 : 0 : ip_frag_tbl_reuse(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
28 : : struct ip_frag_pkt *fp, uint64_t tms)
29 : : {
30 : : ip_frag_free(fp, dr);
31 : : ip_frag_reset(fp, tms);
32 [ # # ]: 0 : TAILQ_REMOVE(&tbl->lru, fp, lru);
33 : 0 : TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
34 : : IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, reuse_num, 1);
35 : 0 : }
36 : :
37 : :
38 : : static inline void
39 : 231 : ipv4_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2, uint32_t seed)
40 : : {
41 : : uint32_t v;
42 : : const uint32_t *p;
43 : :
44 : : p = (const uint32_t *)&key->src_dst;
45 : :
46 : : #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
47 : 231 : v = rte_hash_crc_4byte(p[0], seed);
48 : 231 : v = rte_hash_crc_4byte(p[1], v);
49 : 231 : v = rte_hash_crc_4byte(key->id, v);
50 : : #else
51 : :
52 : : v = rte_jhash_3words(p[0], p[1], key->id, seed);
53 : : #endif /* RTE_ARCH_X86 */
54 : :
55 : 231 : *v1 = v;
56 : 231 : *v2 = (v << 7) + (v >> 14);
57 : 231 : }
58 : :
59 : : static inline void
60 : 228 : ipv6_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2, uint32_t seed)
61 : : {
62 : : uint32_t v;
63 : : const uint32_t *p;
64 : :
65 : : p = (const uint32_t *) &key->src_dst;
66 : :
67 : : #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64)
68 : 228 : v = rte_hash_crc_4byte(p[0], seed);
69 : 228 : v = rte_hash_crc_4byte(p[1], v);
70 : 228 : v = rte_hash_crc_4byte(p[2], v);
71 : 228 : v = rte_hash_crc_4byte(p[3], v);
72 : 228 : v = rte_hash_crc_4byte(p[4], v);
73 : 228 : v = rte_hash_crc_4byte(p[5], v);
74 : 228 : v = rte_hash_crc_4byte(p[6], v);
75 : 228 : v = rte_hash_crc_4byte(p[7], v);
76 : 228 : v = rte_hash_crc_4byte(key->id, v);
77 : : #else
78 : :
79 : : v = rte_jhash_3words(p[0], p[1], p[2], seed);
80 : : v = rte_jhash_3words(p[3], p[4], p[5], v);
81 : : v = rte_jhash_3words(p[6], p[7], key->id, v);
82 : : #endif /* RTE_ARCH_X86 */
83 : :
84 : 228 : *v1 = v;
85 : 228 : *v2 = (v << 7) + (v >> 14);
86 : 228 : }
87 : :
88 : : struct rte_mbuf *
89 : 2278 : ip_frag_process(struct ip_frag_pkt *fp, struct rte_ip_frag_death_row *dr,
90 : : struct rte_mbuf *mb, uint16_t ofs, uint16_t len, uint16_t more_frags)
91 : : {
92 : : uint32_t i, idx;
93 : :
94 : : /*
95 : : * Scan the fragments already collected for this datagram before
96 : : * storing the new one. The stored set is kept free of duplicates and
97 : : * overlaps, so a single pass is sufficient.
98 : : */
99 [ + + ]: 10655 : for (i = 0; i != fp->last_idx; i++) {
100 [ + + ]: 8382 : if (fp->frags[i].mb == NULL)
101 : 2931 : continue;
102 : :
103 : : /*
104 : : * Exact duplicate: carries no new data. Reassembly tolerates
105 : : * duplicates (RFC 791), so drop only this mbuf and keep the
106 : : * entry.
107 : : */
108 [ + + + - ]: 5451 : if (fp->frags[i].ofs == ofs && fp->frags[i].len == len) {
109 : 1 : IP_FRAG_MBUF2DR(dr, mb);
110 : 1 : return NULL;
111 : : }
112 : :
113 : : /*
114 : : * Overlap with an existing fragment. Per RFC 8200 section 4.5
115 : : * (and RFC 5722) the datagram must be discarded; the same is
116 : : * applied to IPv4. Free all collected fragments, drop this one,
117 : : * and invalidate the entry.
118 : : */
119 [ + + + + ]: 5450 : if (ofs < fp->frags[i].ofs + fp->frags[i].len && fp->frags[i].ofs < ofs + len) {
120 : : IP_FRAG_LOG(DEBUG,
121 : : "%s:%d overlap ofs: %u len: %u\n"
122 : : "fragment: %p ofs: %u len %u\n\n",
123 : : __func__, __LINE__, ofs, len,
124 : : fp, fp->frags[i].ofs, fp->frags[i].len);
125 : : ip_frag_free(fp, dr);
126 : : ip_frag_key_invalidate(&fp->key);
127 : 4 : IP_FRAG_MBUF2DR(dr, mb);
128 : 4 : return NULL;
129 : : }
130 : : }
131 : :
132 : 2273 : fp->frag_size += len;
133 : :
134 : : /* this is the first fragment. */
135 [ + + ]: 2273 : if (ofs == 0) {
136 : 457 : idx = (fp->frags[IP_FIRST_FRAG_IDX].mb == NULL) ?
137 [ - + ]: 457 : IP_FIRST_FRAG_IDX : UINT32_MAX;
138 : :
139 : : /* this is the last fragment. */
140 [ + + ]: 1816 : } else if (more_frags == 0) {
141 : 454 : fp->total_size = ofs + len;
142 : 454 : idx = (fp->frags[IP_LAST_FRAG_IDX].mb == NULL) ?
143 [ - + ]: 454 : IP_LAST_FRAG_IDX : UINT32_MAX;
144 : :
145 : : /* this is the intermediate fragment. */
146 [ + + ]: 1362 : } else if ((idx = fp->last_idx) < RTE_DIM(fp->frags)) {
147 : 1361 : fp->last_idx++;
148 : : }
149 : :
150 : : /*
151 : : * erroneous packet: either exceed max allowed number of fragments,
152 : : * or duplicate first/last fragment encountered.
153 : : */
154 [ + + ]: 1362 : if (idx >= RTE_DIM(fp->frags)) {
155 : :
156 : : /* report an error. */
157 : : if (fp->key.key_len == IPV4_KEYLEN)
158 : : IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
159 : : "ipv4_frag_pkt: %p, key: <%" PRIx64 ", %#x>, "
160 : : "total_size: %u, frag_size: %u, last_idx: %u\n"
161 : : "first fragment: ofs: %u, len: %u\n"
162 : : "last fragment: ofs: %u, len: %u\n\n",
163 : : __func__, __LINE__,
164 : : fp, fp->key.src_dst[0], fp->key.id,
165 : : fp->total_size, fp->frag_size, fp->last_idx,
166 : : fp->frags[IP_FIRST_FRAG_IDX].ofs,
167 : : fp->frags[IP_FIRST_FRAG_IDX].len,
168 : : fp->frags[IP_LAST_FRAG_IDX].ofs,
169 : : fp->frags[IP_LAST_FRAG_IDX].len);
170 : : else
171 : : IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
172 : : "ipv6_frag_pkt: %p, key: <" IPv6_KEY_BYTES_FMT ", %#x>, "
173 : : "total_size: %u, frag_size: %u, last_idx: %u\n"
174 : : "first fragment: ofs: %u, len: %u\n"
175 : : "last fragment: ofs: %u, len: %u\n\n",
176 : : __func__, __LINE__,
177 : : fp, IPv6_KEY_BYTES(fp->key.src_dst), fp->key.id,
178 : : fp->total_size, fp->frag_size, fp->last_idx,
179 : : fp->frags[IP_FIRST_FRAG_IDX].ofs,
180 : : fp->frags[IP_FIRST_FRAG_IDX].len,
181 : : fp->frags[IP_LAST_FRAG_IDX].ofs,
182 : : fp->frags[IP_LAST_FRAG_IDX].len);
183 : :
184 : : /* free all fragments, invalidate the entry. */
185 : : ip_frag_free(fp, dr);
186 : : ip_frag_key_invalidate(&fp->key);
187 : 1 : IP_FRAG_MBUF2DR(dr, mb);
188 : :
189 : 1 : return NULL;
190 : : }
191 : :
192 : 2272 : fp->frags[idx].ofs = ofs;
193 : 2272 : fp->frags[idx].len = len;
194 : 2272 : fp->frags[idx].mb = mb;
195 : :
196 : : mb = NULL;
197 : :
198 : : /* not all fragments are collected yet. */
199 [ + + ]: 2272 : if (likely (fp->frag_size < fp->total_size)) {
200 : : return mb;
201 : :
202 : : /* if we collected all fragments, then try to reassemble. */
203 [ + - ]: 452 : } else if (fp->frag_size == fp->total_size &&
204 [ + - ]: 452 : fp->frags[IP_FIRST_FRAG_IDX].mb != NULL) {
205 [ + + ]: 452 : if (fp->key.key_len == IPV4_KEYLEN)
206 : 227 : mb = ipv4_frag_reassemble(fp);
207 : : else
208 : 225 : mb = ipv6_frag_reassemble(fp);
209 : : }
210 : :
211 : : /* errorenous set of fragments. */
212 [ - + ]: 452 : if (mb == NULL) {
213 : :
214 : : /* report an error. */
215 : : if (fp->key.key_len == IPV4_KEYLEN)
216 : : IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
217 : : "ipv4_frag_pkt: %p, key: <%" PRIx64 ", %#x>, "
218 : : "total_size: %u, frag_size: %u, last_idx: %u\n"
219 : : "first fragment: ofs: %u, len: %u\n"
220 : : "last fragment: ofs: %u, len: %u\n\n",
221 : : __func__, __LINE__,
222 : : fp, fp->key.src_dst[0], fp->key.id,
223 : : fp->total_size, fp->frag_size, fp->last_idx,
224 : : fp->frags[IP_FIRST_FRAG_IDX].ofs,
225 : : fp->frags[IP_FIRST_FRAG_IDX].len,
226 : : fp->frags[IP_LAST_FRAG_IDX].ofs,
227 : : fp->frags[IP_LAST_FRAG_IDX].len);
228 : : else
229 : : IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
230 : : "ipv6_frag_pkt: %p, key: <" IPv6_KEY_BYTES_FMT ", %#x>, "
231 : : "total_size: %u, frag_size: %u, last_idx: %u\n"
232 : : "first fragment: ofs: %u, len: %u\n"
233 : : "last fragment: ofs: %u, len: %u\n\n",
234 : : __func__, __LINE__,
235 : : fp, IPv6_KEY_BYTES(fp->key.src_dst), fp->key.id,
236 : : fp->total_size, fp->frag_size, fp->last_idx,
237 : : fp->frags[IP_FIRST_FRAG_IDX].ofs,
238 : : fp->frags[IP_FIRST_FRAG_IDX].len,
239 : : fp->frags[IP_LAST_FRAG_IDX].ofs,
240 : : fp->frags[IP_LAST_FRAG_IDX].len);
241 : :
242 : : /* free associated resources. */
243 : : ip_frag_free(fp, dr);
244 : : }
245 : :
246 : : /* we are done with that entry, invalidate it. */
247 : : ip_frag_key_invalidate(&fp->key);
248 : 452 : return mb;
249 : : }
250 : :
251 : :
252 : : /*
253 : : * Find an entry in the table for the corresponding fragment.
254 : : * If such entry is not present, then allocate a new one.
255 : : * If the entry is stale, then free and reuse it.
256 : : */
257 : : struct ip_frag_pkt *
258 : 2278 : ip_frag_find(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
259 : : const struct ip_frag_key *key, uint64_t tms)
260 : : {
261 : : struct ip_frag_pkt *pkt, *free, *stale, *lru;
262 : : uint64_t max_cycles;
263 : :
264 : : /*
265 : : * Actually the two line below are totally redundant.
266 : : * they are here, just to make gcc 4.6 happy.
267 : : */
268 : 2278 : free = NULL;
269 : 2278 : stale = NULL;
270 : 2278 : max_cycles = tbl->max_cycles;
271 : :
272 : : IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, find_num, 1);
273 : :
274 [ + + ]: 2278 : if ((pkt = ip_frag_lookup(tbl, key, tms, &free, &stale)) == NULL) {
275 : :
276 : : /*timed-out entry, free and invalidate it*/
277 [ - + ]: 459 : if (stale != NULL) {
278 : 0 : ip_frag_tbl_del(tbl, dr, stale);
279 : 0 : free = stale;
280 : :
281 : : /*
282 : : * we found a free entry, check if we can use it.
283 : : * If we run out of free entries in the table, then
284 : : * check if we have a timed out entry to delete.
285 : : */
286 [ + - ]: 459 : } else if (free != NULL &&
287 [ - + ]: 459 : tbl->max_entries <= tbl->use_entries) {
288 : 0 : lru = TAILQ_FIRST(&tbl->lru);
289 [ # # ]: 0 : if (max_cycles + lru->start < tms) {
290 : 0 : ip_frag_tbl_del(tbl, dr, lru);
291 : : } else {
292 : 0 : free = NULL;
293 : : IP_FRAG_TBL_STAT_UPDATE(&tbl->stat,
294 : : fail_nospace, 1);
295 : : }
296 : : }
297 : :
298 : : /* found a free entry to reuse. */
299 [ + - ]: 459 : if (free != NULL) {
300 : : ip_frag_tbl_add(tbl, free, key, tms);
301 : 459 : pkt = free;
302 : : }
303 : :
304 : : /*
305 : : * we found the flow, but it is already timed out,
306 : : * so free associated resources, reposition it in the LRU list,
307 : : * and reuse it.
308 : : */
309 [ - + ]: 1819 : } else if (max_cycles + pkt->start < tms) {
310 : 0 : ip_frag_tbl_reuse(tbl, dr, pkt, tms);
311 : : }
312 : :
313 : : IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, fail_total, (pkt == NULL));
314 : :
315 : 2278 : tbl->last = pkt;
316 : 2278 : return pkt;
317 : : }
318 : :
319 : : struct ip_frag_pkt *
320 : 2278 : ip_frag_lookup(struct rte_ip_frag_tbl *tbl,
321 : : const struct ip_frag_key *key, uint64_t tms,
322 : : struct ip_frag_pkt **free, struct ip_frag_pkt **stale)
323 : : {
324 : : struct ip_frag_pkt *p1, *p2;
325 : : struct ip_frag_pkt *empty, *old;
326 : : uint64_t max_cycles;
327 : : uint32_t i, assoc, sig1, sig2;
328 : :
329 : : empty = NULL;
330 : : old = NULL;
331 : :
332 : 2278 : max_cycles = tbl->max_cycles;
333 : 2278 : assoc = tbl->bucket_entries;
334 : :
335 [ + + + + ]: 2278 : if (tbl->last != NULL && ip_frag_key_cmp(key, &tbl->last->key) == 0)
336 : : return tbl->last;
337 : :
338 : : /* different hashing methods for IPv4 and IPv6 */
339 [ + + ]: 459 : if (key->key_len == IPV4_KEYLEN)
340 : 231 : ipv4_frag_hash(key, &sig1, &sig2, tbl->seed);
341 : : else
342 : 228 : ipv6_frag_hash(key, &sig1, &sig2, tbl->seed);
343 : :
344 : 459 : p1 = IP_FRAG_TBL_POS(tbl, sig1);
345 : 459 : p2 = IP_FRAG_TBL_POS(tbl, sig2);
346 : :
347 [ + + ]: 4131 : for (i = 0; i != assoc; i++) {
348 : : if (p1->key.key_len == IPV4_KEYLEN)
349 : : IP_FRAG_LOG(DEBUG, "%s:%d:\n"
350 : : "tbl: %p, max_entries: %u, use_entries: %u\n"
351 : : "ipv4_frag_pkt line0: %p, index: %u from %u\n"
352 : : "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
353 : : __func__, __LINE__,
354 : : tbl, tbl->max_entries, tbl->use_entries,
355 : : p1, i, assoc,
356 : : p1[i].key.src_dst[0], p1[i].key.id, p1[i].start);
357 : : else
358 : : IP_FRAG_LOG(DEBUG, "%s:%d:\n"
359 : : "tbl: %p, max_entries: %u, use_entries: %u\n"
360 : : "ipv6_frag_pkt line0: %p, index: %u from %u\n"
361 : : "key: <" IPv6_KEY_BYTES_FMT ", %#x>, start: %" PRIu64 "\n",
362 : : __func__, __LINE__,
363 : : tbl, tbl->max_entries, tbl->use_entries,
364 : : p1, i, assoc,
365 : : IPv6_KEY_BYTES(p1[i].key.src_dst), p1[i].key.id, p1[i].start);
366 : :
367 [ - + ]: 3672 : if (ip_frag_key_cmp(key, &p1[i].key) == 0)
368 : 0 : return p1 + i;
369 [ + - ]: 3672 : else if (ip_frag_key_is_empty(&p1[i].key))
370 [ + + ]: 3672 : empty = (empty == NULL) ? (p1 + i) : empty;
371 [ # # ]: 0 : else if (max_cycles + p1[i].start < tms)
372 [ # # ]: 0 : old = (old == NULL) ? (p1 + i) : old;
373 : :
374 : : if (p2->key.key_len == IPV4_KEYLEN)
375 : : IP_FRAG_LOG(DEBUG, "%s:%d:\n"
376 : : "tbl: %p, max_entries: %u, use_entries: %u\n"
377 : : "ipv4_frag_pkt line1: %p, index: %u from %u\n"
378 : : "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
379 : : __func__, __LINE__,
380 : : tbl, tbl->max_entries, tbl->use_entries,
381 : : p2, i, assoc,
382 : : p2[i].key.src_dst[0], p2[i].key.id, p2[i].start);
383 : : else
384 : : IP_FRAG_LOG(DEBUG, "%s:%d:\n"
385 : : "tbl: %p, max_entries: %u, use_entries: %u\n"
386 : : "ipv6_frag_pkt line1: %p, index: %u from %u\n"
387 : : "key: <" IPv6_KEY_BYTES_FMT ", %#x>, start: %" PRIu64 "\n",
388 : : __func__, __LINE__,
389 : : tbl, tbl->max_entries, tbl->use_entries,
390 : : p2, i, assoc,
391 : : IPv6_KEY_BYTES(p2[i].key.src_dst), p2[i].key.id, p2[i].start);
392 : :
393 [ - + ]: 3672 : if (ip_frag_key_cmp(key, &p2[i].key) == 0)
394 : 0 : return p2 + i;
395 [ + - ]: 3672 : else if (ip_frag_key_is_empty(&p2[i].key))
396 [ - + ]: 3672 : empty = (empty == NULL) ?( p2 + i) : empty;
397 [ # # ]: 0 : else if (max_cycles + p2[i].start < tms)
398 [ # # ]: 0 : old = (old == NULL) ? (p2 + i) : old;
399 : : }
400 : :
401 : 459 : *free = empty;
402 : 459 : *stale = old;
403 : 459 : return NULL;
404 : : }
|
