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 #ifdef RTE_LIBRTE_IP_FRAG_TBL_STAT
  18 #define IP_FRAG_TBL_STAT_UPDATE(s, f, v)        ((s)->f += (v))
  19 #else
  20 #define IP_FRAG_TBL_STAT_UPDATE(s, f, v)        do {} while (0)
  21 #endif /* IP_FRAG_TBL_STAT */
  22
  23 /* local frag table helper functions */
  24 static inline void
  25 ip_frag_tbl_del(struct rte_ip_frag_tbl *tbl, struct rte_ip_frag_death_row *dr,
  26         struct ip_frag_pkt *fp)
  27 {
  28         ip_frag_free(fp, dr);
  29         ip_frag_key_invalidate(&fp->key);
  30         TAILQ_REMOVE(&tbl->lru, fp, lru);
  31         tbl->use_entries--;
  32         IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, del_num, 1);
  33 }
  34
  35 static inline void
  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)
  38 {
  39         fp->key = key[0];
  40         ip_frag_reset(fp, tms);
  41         TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
  42         tbl->use_entries++;
  43         IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, add_num, 1);
  44 }
  45
  46 static inline void
  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)
  49 {
  50         ip_frag_free(fp, dr);
  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);
  55 }
  56
  57
  58 static inline void
  59 ipv4_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2)
  60 {
  61         uint32_t v;
  62         const uint32_t *p;
  63
  64         p = (const uint32_t *)&key->src_dst;
  65
  66 #ifdef RTE_ARCH_X86
  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);
  70 #else
  71
  72         v = rte_jhash_3words(p[0], p[1], key->id, PRIME_VALUE);
  73 #endif /* RTE_ARCH_X86 */
  74
  75         *v1 =  v;
  76         *v2 = (v << 7) + (v >> 14);
  77 }
  78
  79 static inline void
  80 ipv6_frag_hash(const struct ip_frag_key *key, uint32_t *v1, uint32_t *v2)
  81 {
  82         uint32_t v;
  83         const uint32_t *p;
  84
  85         p = (const uint32_t *) &key->src_dst;
  86
  87 #ifdef RTE_ARCH_X86
  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);
  97 #else
  98
  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 */
 103
 104         *v1 =  v;
 105         *v2 = (v << 7) + (v >> 14);
 106 }
 107
 108 struct rte_mbuf *
 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)
 111 {
 112         uint32_t idx;
 113
 114         fp->frag_size += len;
 115
 116         /* this is the first fragment. */
 117         if (ofs == 0) {
 118                 idx = (fp->frags[IP_FIRST_FRAG_IDX].mb == NULL) ?
 119                                 IP_FIRST_FRAG_IDX : UINT32_MAX;
 120
 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;
 126
 127         /* this is the intermediate fragment. */
 128         } else if ((idx = fp->last_idx) <
 129                 sizeof (fp->frags) / sizeof (fp->frags[0])) {
 130                 fp->last_idx++;
 131         }
 132
 133         /*
 134          * erroneous packet: either exceed max allowed number of fragments,
 135          * or duplicate first/last fragment encountered.
 136          */
 137         if (idx >= sizeof (fp->frags) / sizeof (fp->frags[0])) {
 138
 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",
 146                                 __func__, __LINE__,
 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);
 153                 else
 154                         IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
 155                                 "ipv6_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",
 159                                 __func__, __LINE__,
 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);
 166
 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);
 171
 172                 return NULL;
 173         }
 174
 175         fp->frags[idx].ofs = ofs;
 176         fp->frags[idx].len = len;
 177         fp->frags[idx].mb = mb;
 178
 179         mb = NULL;
 180
 181         /* not all fragments are collected yet. */
 182         if (likely (fp->frag_size < fp->total_size)) {
 183                 return mb;
 184
 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);
 190                 else
 191                         mb = ipv6_frag_reassemble(fp);
 192         }
 193
 194         /* errorenous set of fragments. */
 195         if (mb == NULL) {
 196
 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",
 204                                 __func__, __LINE__,
 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);
 211                 else
 212                         IP_FRAG_LOG(DEBUG, "%s:%d invalid fragmented packet:\n"
 213                                 "ipv6_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",
 217                                 __func__, __LINE__,
 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);
 224
 225                 /* free associated resources. */
 226                 ip_frag_free(fp, dr);
 227         }
 228
 229         /* we are done with that entry, invalidate it. */
 230         ip_frag_key_invalidate(&fp->key);
 231         return mb;
 232 }
 233
 234
 235 /*
 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.
 239  */
 240 struct ip_frag_pkt *
 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)
 243 {
 244         struct ip_frag_pkt *pkt, *free, *stale, *lru;
 245         uint64_t max_cycles;
 246
 247         /*
 248          * Actually the two line below are totally redundant.
 249          * they are here, just to make gcc 4.6 happy.
 250          */
 251         free = NULL;
 252         stale = NULL;
 253         max_cycles = tbl->max_cycles;
 254
 255         IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, find_num, 1);
 256
 257         if ((pkt = ip_frag_lookup(tbl, key, tms, &free, &stale)) == NULL) {
 258
 259                 /*timed-out entry, free and invalidate it*/
 260                 if (stale != NULL) {
 261                         ip_frag_tbl_del(tbl, dr, stale);
 262                         free = stale;
 263
 264                 /*
 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.
 268                  */
 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);
 274                         } else {
 275                                 free = NULL;
 276                                 IP_FRAG_TBL_STAT_UPDATE(&tbl->stat,
 277                                         fail_nospace, 1);
 278                         }
 279                 }
 280
 281                 /* found a free entry to reuse. */
 282                 if (free != NULL) {
 283                         ip_frag_tbl_add(tbl,  free, key, tms);
 284                         pkt = free;
 285                 }
 286
 287         /*
 288          * we found the flow, but it is already timed out,
 289          * so free associated resources, reposition it in the LRU list,
 290          * and reuse it.
 291          */
 292         } else if (max_cycles + pkt->start < tms) {
 293                 ip_frag_tbl_reuse(tbl, dr, pkt, tms);
 294         }
 295
 296         IP_FRAG_TBL_STAT_UPDATE(&tbl->stat, fail_total, (pkt == NULL));
 297
 298         tbl->last = pkt;
 299         return pkt;
 300 }
 301
 302 struct ip_frag_pkt *
 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)
 306 {
 307         struct ip_frag_pkt *p1, *p2;
 308         struct ip_frag_pkt *empty, *old;
 309         uint64_t max_cycles;
 310         uint32_t i, assoc, sig1, sig2;
 311
 312         empty = NULL;
 313         old = NULL;
 314
 315         max_cycles = tbl->max_cycles;
 316         assoc = tbl->bucket_entries;
 317
 318         if (tbl->last != NULL && ip_frag_key_cmp(key, &tbl->last->key) == 0)
 319                 return tbl->last;
 320
 321         /* different hashing methods for IPv4 and IPv6 */
 322         if (key->key_len == IPV4_KEYLEN)
 323                 ipv4_frag_hash(key, &sig1, &sig2);
 324         else
 325                 ipv6_frag_hash(key, &sig1, &sig2);
 326
 327         p1 = IP_FRAG_TBL_POS(tbl, sig1);
 328         p2 = IP_FRAG_TBL_POS(tbl, sig2);
 329
 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                                         "ipv4_frag_pkt line0: %p, index: %u from %u\n"
 335                         "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
 336                                         __func__, __LINE__,
 337                                         tbl, tbl->max_entries, tbl->use_entries,
 338                                         p1, i, assoc,
 339                         p1[i].key.src_dst[0], p1[i].key.id, p1[i].start);
 340                 else
 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",
 345                                         __func__, __LINE__,
 346                                         tbl, tbl->max_entries, tbl->use_entries,
 347                                         p1, i, assoc,
 348                         IPv6_KEY_BYTES(p1[i].key.src_dst), p1[i].key.id, p1[i].start);
 349
 350                 if (ip_frag_key_cmp(key, &p1[i].key) == 0)
 351                         return p1 + i;
 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;
 356
 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                                         "ipv4_frag_pkt line1: %p, index: %u from %u\n"
 361                         "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
 362                                         __func__, __LINE__,
 363                                         tbl, tbl->max_entries, tbl->use_entries,
 364                                         p2, i, assoc,
 365                         p2[i].key.src_dst[0], p2[i].key.id, p2[i].start);
 366                 else
 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",
 371                                         __func__, __LINE__,
 372                                         tbl, tbl->max_entries, tbl->use_entries,
 373                                         p2, i, assoc,
 374                         IPv6_KEY_BYTES(p2[i].key.src_dst), p2[i].key.id, p2[i].start);
 375
 376                 if (ip_frag_key_cmp(key, &p2[i].key) == 0)
 377                         return p2 + i;
 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;
 382         }
 383
 384         *free = empty;
 385         *stale = old;
 386         return NULL;
 387 }