lib/librte_hash/rte_hash.c

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2015 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 <string.h>
  35 #include <stdint.h>
  36 #include <errno.h>
  37 #include <stdio.h>
  38 #include <stdarg.h>
  39 #include <sys/queue.h>
  40
  41 #include <rte_common.h>
  42 #include <rte_memory.h>         /* for definition of RTE_CACHE_LINE_SIZE */
  43 #include <rte_log.h>
  44 #include <rte_memcpy.h>
  45 #include <rte_prefetch.h>
  46 #include <rte_branch_prediction.h>
  47 #include <rte_memzone.h>
  48 #include <rte_malloc.h>
  49 #include <rte_eal.h>
  50 #include <rte_eal_memconfig.h>
  51 #include <rte_per_lcore.h>
  52 #include <rte_errno.h>
  53 #include <rte_string_fns.h>
  54 #include <rte_cpuflags.h>
  55 #include <rte_log.h>
  56 #include <rte_rwlock.h>
  57 #include <rte_spinlock.h>
  58
  59 #include "rte_hash.h"
  60
  61 TAILQ_HEAD(rte_hash_list, rte_tailq_entry);
  62
  63 static struct rte_tailq_elem rte_hash_tailq = {
  64         .name = "RTE_HASH",
  65 };
  66 EAL_REGISTER_TAILQ(rte_hash_tailq)
  67
  68 /* Macro to enable/disable run-time checking of function parameters */
  69 #if defined(RTE_LIBRTE_HASH_DEBUG)
  70 #define RETURN_IF_TRUE(cond, retval) do { \
  71         if (cond) return (retval); \
  72 } while (0)
  73 #else
  74 #define RETURN_IF_TRUE(cond, retval)
  75 #endif
  76
  77 /* Hash function used if none is specified */
  78 #ifdef RTE_MACHINE_CPUFLAG_SSE4_2
  79 #include <rte_hash_crc.h>
  80 #define DEFAULT_HASH_FUNC       rte_hash_crc
  81 #else
  82 #include <rte_jhash.h>
  83 #define DEFAULT_HASH_FUNC       rte_jhash
  84 #endif
  85
  86 /* Signature bucket size is a multiple of this value */
  87 #define SIG_BUCKET_ALIGNMENT    16
  88
  89 /* Stoered key size is a multiple of this value */
  90 #define KEY_ALIGNMENT           16
  91
  92 /* The high bit is always set in real signatures */
  93 #define NULL_SIGNATURE          0
  94
  95 struct rte_hash {
  96         char name[RTE_HASH_NAMESIZE];   /**< Name of the hash. */
  97         uint32_t entries;               /**< Total table entries. */
  98         uint32_t bucket_entries;        /**< Bucket entries. */
  99         uint32_t key_len;               /**< Length of hash key. */
 100         rte_hash_function hash_func;    /**< Function used to calculate hash. */
 101         uint32_t hash_func_init_val;    /**< Init value used by hash_func. */
 102         uint32_t num_buckets;           /**< Number of buckets in table. */
 103         uint32_t bucket_bitmask;        /**< Bitmask for getting bucket index
 104                                                         from hash signature. */
 105         hash_sig_t sig_msb;     /**< MSB is always set in valid signatures. */
 106         uint8_t *sig_tbl;       /**< Flat array of hash signature buckets. */
 107         uint32_t sig_tbl_bucket_size;   /**< Signature buckets may be padded for
 108                                            alignment reasons, and this is the
 109                                            bucket size used by sig_tbl. */
 110         uint8_t *key_tbl;       /**< Flat array of key value buckets. */
 111         uint32_t key_tbl_key_size;      /**< Keys may be padded for alignment
 112                                            reasons, and this is the key size
 113                                            used by key_tbl. */
 114 };
 115
 116 /* Returns a pointer to the first signature in specified bucket. */
 117 static inline hash_sig_t *
 118 get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index)
 119 {
 120         return RTE_PTR_ADD(h->sig_tbl, (bucket_index *
 121                                         h->sig_tbl_bucket_size));
 122 }
 123
 124 /* Returns a pointer to the first key in specified bucket. */
 125 static inline uint8_t *
 126 get_key_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index)
 127 {
 128         return RTE_PTR_ADD(h->key_tbl, (bucket_index * h->bucket_entries *
 129                                         h->key_tbl_key_size));
 130 }
 131
 132 /* Returns a pointer to a key at a specific position in a specified bucket. */
 133 static inline void *
 134 get_key_from_bucket(const struct rte_hash *h, uint8_t *bkt, uint32_t pos)
 135 {
 136         return RTE_PTR_ADD(bkt, pos * h->key_tbl_key_size);
 137 }
 138
 139 /* Does integer division with rounding-up of result. */
 140 static inline uint32_t
 141 div_roundup(uint32_t numerator, uint32_t denominator)
 142 {
 143         return (numerator + denominator - 1) / denominator;
 144 }
 145
 146 /* Increases a size (if needed) to a multiple of alignment. */
 147 static inline uint32_t
 148 align_size(uint32_t val, uint32_t alignment)
 149 {
 150         return alignment * div_roundup(val, alignment);
 151 }
 152
 153 /* Returns the index into the bucket of the first occurrence of a signature. */
 154 static inline int
 155 find_first(uint32_t sig, const uint32_t *sig_bucket, uint32_t num_sigs)
 156 {
 157         uint32_t i;
 158         for (i = 0; i < num_sigs; i++) {
 159                 if (sig == sig_bucket[i])
 160                         return i;
 161         }
 162         return -1;
 163 }
 164
 165 struct rte_hash *
 166 rte_hash_find_existing(const char *name)
 167 {
 168         struct rte_hash *h = NULL;
 169         struct rte_tailq_entry *te;
 170         struct rte_hash_list *hash_list;
 171
 172         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 173
 174         rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
 175         TAILQ_FOREACH(te, hash_list, next) {
 176                 h = (struct rte_hash *) te->data;
 177                 if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0)
 178                         break;
 179         }
 180         rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
 181
 182         if (te == NULL) {
 183                 rte_errno = ENOENT;
 184                 return NULL;
 185         }
 186         return h;
 187 }
 188
 189 struct rte_hash *
 190 rte_hash_create(const struct rte_hash_parameters *params)
 191 {
 192         struct rte_hash *h = NULL;
 193         struct rte_tailq_entry *te;
 194         uint32_t num_buckets, sig_bucket_size, key_size,
 195                 hash_tbl_size, sig_tbl_size, key_tbl_size, mem_size;
 196         char hash_name[RTE_HASH_NAMESIZE];
 197         struct rte_hash_list *hash_list;
 198
 199         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 200
 201         /* Check for valid parameters */
 202         if ((params == NULL) ||
 203                         (params->entries > RTE_HASH_ENTRIES_MAX) ||
 204                         (params->bucket_entries > RTE_HASH_BUCKET_ENTRIES_MAX) ||
 205                         (params->entries < params->bucket_entries) ||
 206                         !rte_is_power_of_2(params->entries) ||
 207                         !rte_is_power_of_2(params->bucket_entries) ||
 208                         (params->key_len == 0) ||
 209                         (params->key_len > RTE_HASH_KEY_LENGTH_MAX)) {
 210                 rte_errno = EINVAL;
 211                 RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n");
 212                 return NULL;
 213         }
 214
 215         snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name);
 216
 217         /* Calculate hash dimensions */
 218         num_buckets = params->entries / params->bucket_entries;
 219         sig_bucket_size = align_size(params->bucket_entries *
 220                                      sizeof(hash_sig_t), SIG_BUCKET_ALIGNMENT);
 221         key_size =  align_size(params->key_len, KEY_ALIGNMENT);
 222
 223         hash_tbl_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE);
 224         sig_tbl_size = align_size(num_buckets * sig_bucket_size,
 225                                   RTE_CACHE_LINE_SIZE);
 226         key_tbl_size = align_size(num_buckets * key_size *
 227                                   params->bucket_entries, RTE_CACHE_LINE_SIZE);
 228
 229         /* Total memory required for hash context */
 230         mem_size = hash_tbl_size + sig_tbl_size + key_tbl_size;
 231
 232         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 233
 234         /* guarantee there's no existing */
 235         TAILQ_FOREACH(te, hash_list, next) {
 236                 h = (struct rte_hash *) te->data;
 237                 if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0)
 238                         break;
 239         }
 240         if (te != NULL)
 241                 goto exit;
 242
 243         te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0);
 244         if (te == NULL) {
 245                 RTE_LOG(ERR, HASH, "tailq entry allocation failed\n");
 246                 goto exit;
 247         }
 248
 249         h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size,
 250                                            RTE_CACHE_LINE_SIZE, params->socket_id);
 251         if (h == NULL) {
 252                 RTE_LOG(ERR, HASH, "memory allocation failed\n");
 253                 rte_free(te);
 254                 goto exit;
 255         }
 256
 257         /* Setup hash context */
 258         snprintf(h->name, sizeof(h->name), "%s", params->name);
 259         h->entries = params->entries;
 260         h->bucket_entries = params->bucket_entries;
 261         h->key_len = params->key_len;
 262         h->hash_func_init_val = params->hash_func_init_val;
 263         h->num_buckets = num_buckets;
 264         h->bucket_bitmask = h->num_buckets - 1;
 265         h->sig_msb = 1 << (sizeof(hash_sig_t) * 8 - 1);
 266         h->sig_tbl = (uint8_t *)h + hash_tbl_size;
 267         h->sig_tbl_bucket_size = sig_bucket_size;
 268         h->key_tbl = h->sig_tbl + sig_tbl_size;
 269         h->key_tbl_key_size = key_size;
 270         h->hash_func = (params->hash_func == NULL) ?
 271                 DEFAULT_HASH_FUNC : params->hash_func;
 272
 273         te->data = (void *) h;
 274
 275         TAILQ_INSERT_TAIL(hash_list, te, next);
 276
 277 exit:
 278         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 279
 280         return h;
 281 }
 282
 283 void
 284 rte_hash_free(struct rte_hash *h)
 285 {
 286         struct rte_tailq_entry *te;
 287         struct rte_hash_list *hash_list;
 288
 289         if (h == NULL)
 290                 return;
 291
 292         hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);
 293
 294         rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
 295
 296         /* find out tailq entry */
 297         TAILQ_FOREACH(te, hash_list, next) {
 298                 if (te->data == (void *) h)
 299                         break;
 300         }
 301
 302         if (te == NULL) {
 303                 rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 304                 return;
 305         }
 306
 307         TAILQ_REMOVE(hash_list, te, next);
 308
 309         rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
 310
 311         rte_free(h);
 312         rte_free(te);
 313 }
 314
 315 hash_sig_t
 316 rte_hash_hash(const struct rte_hash *h, const void *key)
 317 {
 318         /* calc hash result by key */
 319         return h->hash_func(key, h->key_len, h->hash_func_init_val);
 320 }
 321
 322 static inline int32_t
 323 __rte_hash_add_key_with_hash(const struct rte_hash *h,
 324                                 const void *key, hash_sig_t sig)
 325 {
 326         hash_sig_t *sig_bucket;
 327         uint8_t *key_bucket;
 328         uint32_t bucket_index, i;
 329         int32_t pos;
 330
 331         /* Get the hash signature and bucket index */
 332         sig |= h->sig_msb;
 333         bucket_index = sig & h->bucket_bitmask;
 334         sig_bucket = get_sig_tbl_bucket(h, bucket_index);
 335         key_bucket = get_key_tbl_bucket(h, bucket_index);
 336
 337         /* Check if key is already present in the hash */
 338         for (i = 0; i < h->bucket_entries; i++) {
 339                 if ((sig == sig_bucket[i]) &&
 340                     likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
 341                                   h->key_len) == 0)) {
 342                         return bucket_index * h->bucket_entries + i;
 343                 }
 344         }
 345
 346         /* Check if any free slot within the bucket to add the new key */
 347         pos = find_first(NULL_SIGNATURE, sig_bucket, h->bucket_entries);
 348
 349         if (unlikely(pos < 0))
 350                 return -ENOSPC;
 351
 352         /* Add the new key to the bucket */
 353         sig_bucket[pos] = sig;
 354         rte_memcpy(get_key_from_bucket(h, key_bucket, pos), key, h->key_len);
 355         return bucket_index * h->bucket_entries + pos;
 356 }
 357
 358 int32_t
 359 rte_hash_add_key_with_hash(const struct rte_hash *h,
 360                                 const void *key, hash_sig_t sig)
 361 {
 362         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 363         return __rte_hash_add_key_with_hash(h, key, sig);
 364 }
 365
 366 int32_t
 367 rte_hash_add_key(const struct rte_hash *h, const void *key)
 368 {
 369         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 370         return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key));
 371 }
 372
 373 static inline int32_t
 374 __rte_hash_del_key_with_hash(const struct rte_hash *h,
 375                                 const void *key, hash_sig_t sig)
 376 {
 377         hash_sig_t *sig_bucket;
 378         uint8_t *key_bucket;
 379         uint32_t bucket_index, i;
 380
 381         /* Get the hash signature and bucket index */
 382         sig = sig | h->sig_msb;
 383         bucket_index = sig & h->bucket_bitmask;
 384         sig_bucket = get_sig_tbl_bucket(h, bucket_index);
 385         key_bucket = get_key_tbl_bucket(h, bucket_index);
 386
 387         /* Check if key is already present in the hash */
 388         for (i = 0; i < h->bucket_entries; i++) {
 389                 if ((sig == sig_bucket[i]) &&
 390                     likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
 391                                   h->key_len) == 0)) {
 392                         sig_bucket[i] = NULL_SIGNATURE;
 393                         return bucket_index * h->bucket_entries + i;
 394                 }
 395         }
 396
 397         return -ENOENT;
 398 }
 399
 400 int32_t
 401 rte_hash_del_key_with_hash(const struct rte_hash *h,
 402                                 const void *key, hash_sig_t sig)
 403 {
 404         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 405         return __rte_hash_del_key_with_hash(h, key, sig);
 406 }
 407
 408 int32_t
 409 rte_hash_del_key(const struct rte_hash *h, const void *key)
 410 {
 411         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 412         return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
 413 }
 414
 415 static inline int32_t
 416 __rte_hash_lookup_with_hash(const struct rte_hash *h,
 417                         const void *key, hash_sig_t sig)
 418 {
 419         hash_sig_t *sig_bucket;
 420         uint8_t *key_bucket;
 421         uint32_t bucket_index, i;
 422
 423         /* Get the hash signature and bucket index */
 424         sig |= h->sig_msb;
 425         bucket_index = sig & h->bucket_bitmask;
 426         sig_bucket = get_sig_tbl_bucket(h, bucket_index);
 427         key_bucket = get_key_tbl_bucket(h, bucket_index);
 428
 429         /* Check if key is already present in the hash */
 430         for (i = 0; i < h->bucket_entries; i++) {
 431                 if ((sig == sig_bucket[i]) &&
 432                     likely(memcmp(key, get_key_from_bucket(h, key_bucket, i),
 433                                   h->key_len) == 0)) {
 434                         return bucket_index * h->bucket_entries + i;
 435                 }
 436         }
 437
 438         return -ENOENT;
 439 }
 440
 441 int32_t
 442 rte_hash_lookup_with_hash(const struct rte_hash *h,
 443                         const void *key, hash_sig_t sig)
 444 {
 445         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 446         return __rte_hash_lookup_with_hash(h, key, sig);
 447 }
 448
 449 int32_t
 450 rte_hash_lookup(const struct rte_hash *h, const void *key)
 451 {
 452         RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
 453         return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key));
 454 }
 455
 456 int
 457 rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
 458                       uint32_t num_keys, int32_t *positions)
 459 {
 460         uint32_t i, j, bucket_index;
 461         hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX];
 462
 463         RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) ||
 464                         (num_keys > RTE_HASH_LOOKUP_BULK_MAX) ||
 465                         (positions == NULL)), -EINVAL);
 466
 467         /* Get the hash signature and bucket index */
 468         for (i = 0; i < num_keys; i++) {
 469                 sigs[i] = h->hash_func(keys[i], h->key_len,
 470                                 h->hash_func_init_val) | h->sig_msb;
 471                 bucket_index = sigs[i] & h->bucket_bitmask;
 472
 473                 /* Pre-fetch relevant buckets */
 474                 rte_prefetch1((void *) get_sig_tbl_bucket(h, bucket_index));
 475                 rte_prefetch1((void *) get_key_tbl_bucket(h, bucket_index));
 476         }
 477
 478         /* Check if key is already present in the hash */
 479         for (i = 0; i < num_keys; i++) {
 480                 bucket_index = sigs[i] & h->bucket_bitmask;
 481                 hash_sig_t *sig_bucket = get_sig_tbl_bucket(h, bucket_index);
 482                 uint8_t *key_bucket = get_key_tbl_bucket(h, bucket_index);
 483
 484                 positions[i] = -ENOENT;
 485
 486                 for (j = 0; j < h->bucket_entries; j++) {
 487                         if ((sigs[i] == sig_bucket[j]) &&
 488                             likely(memcmp(keys[i],
 489                                           get_key_from_bucket(h, key_bucket, j),
 490                                           h->key_len) == 0)) {
 491                                 positions[i] = bucket_index *
 492                                         h->bucket_entries + j;
 493                                 break;
 494                         }
 495                 }
 496         }
 497
 498         return 0;
 499 }