lib/librte_ip_frag/ip_frag_internal.c

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