examples/ip_reassembly/ipv4_frag_tbl.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2013 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
  35 #ifndef _IPV4_FRAG_TBL_H_
  36 #define _IPV4_FRAG_TBL_H_
  37
  38 /**
  39  * @file
  40  * IPv4 fragments table.
  41  *
  42  * Implementation of IPv4 fragment table create/destroy/find/update.
  43  *
  44  */
  45
  46 /*
  47  * The ipv4_frag_tbl is a simple hash table:
  48  * The basic idea is to use two hash functions and <bucket_entries>
  49  * associativity. This provides 2 * <bucket_entries> possible locations in
  50  * the hash table for each key. Sort of simplified Cuckoo hashing,
  51  * when the collision occurs and all 2 * <bucket_entries> are occupied,
  52  * instead of resinserting existing keys into alternative locations, we just
  53  * return a faiure.
  54  * Another thing timing: entries that resides in the table longer then
  55  * <max_cycles> are considered as invalid, and could be removed/replaced
  56  * byt the new ones.
  57  * <key, data> pair is stored together, all add/update/lookup opearions are not
  58  * MT safe.
  59  */
  60
  61 #include <rte_jhash.h>
  62 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
  63 #include <rte_hash_crc.h>
  64 #endif /* RTE_MACHINE_CPUFLAG_SSE4_2 */
  65
  66 #define PRIME_VALUE     0xeaad8405
  67
  68 TAILQ_HEAD(ipv4_pkt_list, ipv4_frag_pkt);
  69
  70 struct ipv4_frag_tbl_stat {
  71         uint64_t find_num;      /* total # of find/insert attempts. */
  72         uint64_t add_num;       /* # of add ops. */
  73         uint64_t del_num;       /* # of del ops. */
  74         uint64_t reuse_num;     /* # of reuse (del/add) ops. */
  75         uint64_t fail_total;    /* total # of add failures. */
  76         uint64_t fail_nospace;  /* # of 'no space' add failures. */
  77 } __rte_cache_aligned;
  78
  79 struct ipv4_frag_tbl {
  80         uint64_t             max_cycles;      /* ttl for table entries. */
  81         uint32_t             entry_mask;      /* hash value mask. */
  82         uint32_t             max_entries;     /* max entries allowed. */
  83         uint32_t             use_entries;     /* entries in use. */
  84         uint32_t             bucket_entries;  /* hash assocaitivity. */
  85         uint32_t             nb_entries;      /* total size of the table. */
  86         uint32_t             nb_buckets;      /* num of associativity lines. */
  87         struct ipv4_frag_pkt *last;           /* last used entry. */
  88         struct ipv4_pkt_list lru;             /* LRU list for table entries. */
  89         struct ipv4_frag_tbl_stat stat;       /* statistics counters. */
  90         struct ipv4_frag_pkt pkt[0];          /* hash table. */
  91 };
  92
  93 #define IPV4_FRAG_TBL_POS(tbl, sig)     \
  94         ((tbl)->pkt + ((sig) & (tbl)->entry_mask))
  95
  96 #define IPV4_FRAG_HASH_FNUM     2
  97
  98 #ifdef IPV4_FRAG_TBL_STAT
  99 #define IPV4_FRAG_TBL_STAT_UPDATE(s, f, v)      ((s)->f += (v))
 100 #else
 101 #define IPV4_FRAG_TBL_STAT_UPDATE(s, f, v)      do {} while (0)
 102 #endif /* IPV4_FRAG_TBL_STAT */
 103
 104 static inline void
 105 ipv4_frag_hash(const struct ipv4_frag_key *key, uint32_t *v1, uint32_t *v2)
 106 {
 107         uint32_t v;
 108         const uint32_t *p;
 109
 110         p = (const uint32_t *)&key->src_dst;
 111
 112 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
 113         v = rte_hash_crc_4byte(p[0], PRIME_VALUE);
 114         v = rte_hash_crc_4byte(p[1], v);
 115         v = rte_hash_crc_4byte(key->id, v);
 116 #else
 117
 118         v = rte_jhash_3words(p[0], p[1], key->id, PRIME_VALUE);
 119 #endif /* RTE_MACHINE_CPUFLAG_SSE4_2 */
 120
 121         *v1 =  v;
 122         *v2 = (v << 7) + (v >> 14);
 123 }
 124
 125 /*
 126  * Update the table, after we finish processing it's entry.
 127  */
 128 static inline void
 129 ipv4_frag_inuse(struct ipv4_frag_tbl *tbl, const struct  ipv4_frag_pkt *fp)
 130 {
 131         if (IPV4_FRAG_KEY_EMPTY(&fp->key)) {
 132                 TAILQ_REMOVE(&tbl->lru, fp, lru);
 133                 tbl->use_entries--;
 134         }
 135 }
 136
 137 /*
 138  * For the given key, try to find an existing entry.
 139  * If such entry doesn't exist, will return free and/or timed-out entry,
 140  * that can be used for that key.
 141  */
 142 static inline struct  ipv4_frag_pkt *
 143 ipv4_frag_lookup(struct ipv4_frag_tbl *tbl,
 144         const struct ipv4_frag_key *key, uint64_t tms,
 145         struct ipv4_frag_pkt **free, struct ipv4_frag_pkt **stale)
 146 {
 147         struct ipv4_frag_pkt *p1, *p2;
 148         struct ipv4_frag_pkt *empty, *old;
 149         uint64_t max_cycles;
 150         uint32_t i, assoc, sig1, sig2;
 151
 152         empty = NULL;
 153         old = NULL;
 154
 155         max_cycles = tbl->max_cycles;
 156         assoc = tbl->bucket_entries;
 157
 158         if (tbl->last != NULL && IPV4_FRAG_KEY_CMP(&tbl->last->key, key) == 0)
 159                 return (tbl->last);
 160
 161         ipv4_frag_hash(key, &sig1, &sig2);
 162         p1 = IPV4_FRAG_TBL_POS(tbl, sig1);
 163         p2 = IPV4_FRAG_TBL_POS(tbl, sig2);
 164
 165         for (i = 0; i != assoc; i++) {
 166
 167                 IPV4_FRAG_LOG(DEBUG, "%s:%d:\n"
 168                 "tbl: %p, max_entries: %u, use_entries: %u\n"
 169                 "ipv4_frag_pkt line0: %p, index: %u from %u\n"
 170                 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
 171                 __func__, __LINE__,
 172                 tbl, tbl->max_entries, tbl->use_entries,
 173                 p1, i, assoc,
 174                 p1[i].key.src_dst, p1[i].key.id, p1[i].start);
 175
 176                 if (IPV4_FRAG_KEY_CMP(&p1[i].key, key) == 0)
 177                         return (p1 + i);
 178                 else if (IPV4_FRAG_KEY_EMPTY(&p1[i].key))
 179                         empty = (empty == NULL) ? (p1 + i) : empty;
 180                 else if (max_cycles + p1[i].start < tms)
 181                         old = (old == NULL) ? (p1 + i) : old;
 182
 183                 IPV4_FRAG_LOG(DEBUG, "%s:%d:\n"
 184                 "tbl: %p, max_entries: %u, use_entries: %u\n"
 185                 "ipv4_frag_pkt line1: %p, index: %u from %u\n"
 186                 "key: <%" PRIx64 ", %#x>, start: %" PRIu64 "\n",
 187                 __func__, __LINE__,
 188                 tbl, tbl->max_entries, tbl->use_entries,
 189                 p2, i, assoc,
 190                 p2[i].key.src_dst, p2[i].key.id, p2[i].start);
 191
 192                 if (IPV4_FRAG_KEY_CMP(&p2[i].key, key) == 0)
 193                         return (p2 + i);
 194                 else if (IPV4_FRAG_KEY_EMPTY(&p2[i].key))
 195                         empty = (empty == NULL) ?( p2 + i) : empty;
 196                 else if (max_cycles + p2[i].start < tms)
 197                         old = (old == NULL) ? (p2 + i) : old;
 198         }
 199
 200         *free = empty;
 201         *stale = old;
 202         return (NULL);
 203 }
 204
 205 static inline void
 206 ipv4_frag_tbl_del(struct ipv4_frag_tbl *tbl, struct ipv4_frag_death_row *dr,
 207         struct ipv4_frag_pkt *fp)
 208 {
 209         ipv4_frag_free(fp, dr);
 210         IPV4_FRAG_KEY_INVALIDATE(&fp->key);
 211         TAILQ_REMOVE(&tbl->lru, fp, lru);
 212         tbl->use_entries--;
 213         IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, del_num, 1);
 214 }
 215
 216 static inline void
 217 ipv4_frag_tbl_add(struct ipv4_frag_tbl *tbl,  struct ipv4_frag_pkt *fp,
 218         const struct ipv4_frag_key *key, uint64_t tms)
 219 {
 220         fp->key = key[0];
 221         ipv4_frag_reset(fp, tms);
 222         TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
 223         tbl->use_entries++;
 224         IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, add_num, 1);
 225 }
 226
 227 static inline void
 228 ipv4_frag_tbl_reuse(struct ipv4_frag_tbl *tbl, struct ipv4_frag_death_row *dr,
 229         struct ipv4_frag_pkt *fp, uint64_t tms)
 230 {
 231         ipv4_frag_free(fp, dr);
 232         ipv4_frag_reset(fp, tms);
 233         TAILQ_REMOVE(&tbl->lru, fp, lru);
 234         TAILQ_INSERT_TAIL(&tbl->lru, fp, lru);
 235         IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, reuse_num, 1);
 236 }
 237
 238 /*
 239  * Find an entry in the table for the corresponding fragment.
 240  * If such entry is not present, then allocate a new one.
 241  * If the entry is stale, then free and reuse it.
 242  */
 243 static inline struct ipv4_frag_pkt *
 244 ipv4_frag_find(struct ipv4_frag_tbl *tbl, struct ipv4_frag_death_row *dr,
 245         const struct ipv4_frag_key *key, uint64_t tms)
 246 {
 247         struct ipv4_frag_pkt *pkt, *free, *stale, *lru;
 248         uint64_t max_cycles;
 249
 250         /*
 251          * Actually the two line below are totally redundant.
 252          * they are here, just to make gcc 4.6 happy.
 253          */
 254         free = NULL;
 255         stale = NULL;
 256         max_cycles = tbl->max_cycles;
 257
 258         IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, find_num, 1);
 259
 260         if ((pkt = ipv4_frag_lookup(tbl, key, tms, &free, &stale)) == NULL) {
 261
 262                 /*timed-out entry, free and invalidate it*/
 263                 if (stale != NULL) {
 264                         ipv4_frag_tbl_del(tbl, dr, stale);
 265                         free = stale;
 266
 267                 /*
 268                  * we found a free entry, check if we can use it.
 269                  * If we run out of free entries in the table, then
 270                  * check if we have a timed out entry to delete.
 271                  */
 272                 } else if (free != NULL &&
 273                                 tbl->max_entries <= tbl->use_entries) {
 274                         lru = TAILQ_FIRST(&tbl->lru);
 275                         if (max_cycles + lru->start < tms) {
 276                                 ipv4_frag_tbl_del(tbl, dr, lru);
 277                         } else {
 278                                 free = NULL;
 279                                 IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat,
 280                                         fail_nospace, 1);
 281                         }
 282                 }
 283
 284                 /* found a free entry to reuse. */
 285                 if (free != NULL) {
 286                         ipv4_frag_tbl_add(tbl,  free, key, tms);
 287                         pkt = free;
 288                 }
 289
 290         /*
 291          * we found the flow, but it is already timed out,
 292          * so free associated resources, reposition it in the LRU list,
 293          * and reuse it.
 294          */
 295         } else if (max_cycles + pkt->start < tms) {
 296                 ipv4_frag_tbl_reuse(tbl, dr, pkt, tms);
 297         }
 298
 299         IPV4_FRAG_TBL_STAT_UPDATE(&tbl->stat, fail_total, (pkt == NULL));
 300
 301         tbl->last = pkt;
 302         return (pkt);
 303 }
 304
 305 /*
 306  * Create a new IPV4 Frag table.
 307  * @param bucket_num
 308  *  Number of buckets in the hash table.
 309  * @param bucket_entries
 310  *  Number of entries per bucket (e.g. hash associativity).
 311  *  Should be power of two.
 312  * @param max_entries
 313  *   Maximum number of entries that could be stored in the table.
 314  *   The value should be less or equal then bucket_num * bucket_entries.
 315  * @param max_cycles
 316  *   Maximum TTL in cycles for each fragmented packet.
 317  * @param socket_id
 318  *  The *socket_id* argument is the socket identifier in the case of
 319  *  NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA constraints.
 320  * @return
 321  *   The pointer to the new allocated mempool, on success. NULL on error.
 322  */
 323 static struct ipv4_frag_tbl *
 324 ipv4_frag_tbl_create(uint32_t bucket_num, uint32_t bucket_entries,
 325         uint32_t max_entries, uint64_t max_cycles, int socket_id)
 326 {
 327         struct ipv4_frag_tbl *tbl;
 328         size_t sz;
 329         uint64_t nb_entries;
 330
 331         nb_entries = rte_align32pow2(bucket_num);
 332         nb_entries *= bucket_entries;
 333         nb_entries *= IPV4_FRAG_HASH_FNUM;
 334
 335         /* check input parameters. */
 336         if (rte_is_power_of_2(bucket_entries) == 0 ||
 337                         nb_entries > UINT32_MAX || nb_entries == 0 ||
 338                         nb_entries < max_entries) {
 339                 RTE_LOG(ERR, USER1, "%s: invalid input parameter\n", __func__);
 340                 return (NULL);
 341         }
 342
 343         sz = sizeof (*tbl) + nb_entries * sizeof (tbl->pkt[0]);
 344         if ((tbl = rte_zmalloc_socket(__func__, sz, CACHE_LINE_SIZE,
 345                         socket_id)) == NULL) {
 346                 RTE_LOG(ERR, USER1,
 347                         "%s: allocation of %zu bytes at socket %d failed do\n",
 348                         __func__, sz, socket_id);
 349                 return (NULL);
 350         }
 351
 352         RTE_LOG(INFO, USER1, "%s: allocated of %zu bytes at socket %d\n",
 353                 __func__, sz, socket_id);
 354
 355         tbl->max_cycles = max_cycles;
 356         tbl->max_entries = max_entries;
 357         tbl->nb_entries = (uint32_t)nb_entries;
 358         tbl->nb_buckets = bucket_num;
 359         tbl->bucket_entries = bucket_entries;
 360         tbl->entry_mask = (tbl->nb_entries - 1) & ~(tbl->bucket_entries  - 1);
 361
 362         TAILQ_INIT(&(tbl->lru));
 363         return (tbl);
 364 }
 365
 366 static inline void
 367 ipv4_frag_tbl_destroy( struct ipv4_frag_tbl *tbl)
 368 {
 369         rte_free(tbl);
 370 }
 371
 372 static void
 373 ipv4_frag_tbl_dump_stat(FILE *f, const struct ipv4_frag_tbl *tbl)
 374 {
 375         uint64_t fail_total, fail_nospace;
 376
 377         fail_total = tbl->stat.fail_total;
 378         fail_nospace = tbl->stat.fail_nospace;
 379
 380         fprintf(f, "max entries:\t%u;\n"
 381                 "entries in use:\t%u;\n"
 382                 "finds/inserts:\t%" PRIu64 ";\n"
 383                 "entries added:\t%" PRIu64 ";\n"
 384                 "entries deleted by timeout:\t%" PRIu64 ";\n"
 385                 "entries reused by timeout:\t%" PRIu64 ";\n"
 386                 "total add failures:\t%" PRIu64 ";\n"
 387                 "add no-space failures:\t%" PRIu64 ";\n"
 388                 "add hash-collisions failures:\t%" PRIu64 ";\n",
 389                 tbl->max_entries,
 390                 tbl->use_entries,
 391                 tbl->stat.find_num,
 392                 tbl->stat.add_num,
 393                 tbl->stat.del_num,
 394                 tbl->stat.reuse_num,
 395                 fail_total,
 396                 fail_nospace,
 397                 fail_total - fail_nospace);
 398 }
 399
 400
 401 #endif /* _IPV4_FRAG_TBL_H_ */