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