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_pkt *fp)
 207 {
 208         ipv4_frag_free(fp);
 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_pkt *fp,
 228         uint64_t tms)
 229 {
 230         ipv4_frag_free(fp);
 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, const struct ipv4_frag_key *key,
 244         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, 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,  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,  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_ */