lib/librte_ip_frag/ip_frag_internal.c

   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          * errorneous packet: either exceeed 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 }