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