examples/ip_reassembly/ipv4_frag_tbl.h

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