VNFs/DPPD-PROX/hash_utils.c

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //     http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 */
  16
  17 #include <rte_common.h>
  18 #ifndef __rte_cache_aligned
  19 #include <rte_memory.h>
  20 #endif
  21
  22 #include <string.h>
  23 #include <rte_hash_crc.h>
  24 #include <rte_table_hash.h>
  25 #include <rte_version.h>
  26
  27 #include "hash_utils.h"
  28
  29 /* These opaque structure definitions were copied from DPDK lib/librte_table/rte_table_hash_key8.c */
  30
  31 struct rte_bucket_4_8 {
  32         /* Cache line 0 */
  33         uint64_t signature;
  34         uint64_t lru_list;
  35         struct rte_bucket_4_8 *next;
  36         uint64_t next_valid;
  37
  38         uint64_t key[4];
  39
  40         /* Cache line 1 */
  41         uint8_t data[0];
  42 };
  43
  44 struct rte_table_hash_key8 {
  45 #if RTE_VERSION >= RTE_VERSION_NUM(2,1,0,0)
  46         struct rte_table_stats stats;
  47 #endif
  48         /* Input parameters */
  49         uint32_t n_buckets;
  50 #if RTE_VERSION < RTE_VERSION_NUM(17,11,0,0)
  51         uint32_t n_entries_per_bucket;
  52 #endif
  53         uint32_t key_size;
  54         uint32_t entry_size;
  55         uint32_t bucket_size;
  56 #if RTE_VERSION < RTE_VERSION_NUM(17,11,0,0)
  57         uint32_t signature_offset;
  58 #endif
  59         uint32_t key_offset;
  60 #if RTE_VERSION >= RTE_VERSION_NUM(2,2,0,0)
  61         uint64_t key_mask;
  62 #endif
  63         rte_table_hash_op_hash f_hash;
  64         uint64_t seed;
  65
  66         /* Extendible buckets */
  67         uint32_t n_buckets_ext;
  68         uint32_t stack_pos;
  69         uint32_t *stack;
  70
  71         /* Lookup table */
  72         uint8_t memory[0] __rte_cache_aligned;
  73 };
  74
  75 /* These opaque structure definitions were copied from DPDK lib/librte_table/rte_table_hash_ext.c */
  76
  77 struct bucket {
  78         union {
  79                 uintptr_t next;
  80                 uint64_t lru_list;
  81         };
  82         uint16_t sig[4];
  83         uint32_t key_pos[4];
  84 };
  85
  86 #define BUCKET_NEXT(bucket)                                             \
  87         ((void *) ((bucket)->next & (~1LU)))
  88
  89 struct grinder {
  90         struct bucket *bkt;
  91         uint64_t sig;
  92         uint64_t match;
  93         uint32_t key_index;
  94 };
  95
  96 struct rte_table_hash_ext {
  97 #if RTE_VERSION >= RTE_VERSION_NUM(2,1,0,0)
  98         struct rte_table_stats stats;
  99 #endif
 100         /* Input parameters */
 101         uint32_t key_size;
 102         uint32_t entry_size;
 103         uint32_t n_keys;
 104         uint32_t n_buckets;
 105         uint32_t n_buckets_ext;
 106         rte_table_hash_op_hash f_hash;
 107         uint64_t seed;
 108         uint32_t signature_offset;
 109         uint32_t key_offset;
 110
 111         /* Internal */
 112         uint64_t bucket_mask;
 113         uint32_t key_size_shl;
 114         uint32_t data_size_shl;
 115         uint32_t key_stack_tos;
 116         uint32_t bkt_ext_stack_tos;
 117
 118         /* Grinder */
 119         struct grinder grinders[64];
 120
 121         /* Tables */
 122         struct bucket *buckets;
 123         struct bucket *buckets_ext;
 124         uint8_t *key_mem;
 125         uint8_t *data_mem;
 126         uint32_t *key_stack;
 127         uint32_t *bkt_ext_stack;
 128
 129         /* Table memory */
 130         uint8_t memory[0] __rte_cache_aligned;
 131 };
 132
 133 uint64_t get_bucket(void* table, uint32_t bucket_idx, void** key, void** entries)
 134 {
 135         struct rte_table_hash_ext *t = (struct rte_table_hash_ext *) table;
 136         struct bucket *bkt0, *bkt, *bkt_prev;
 137         uint64_t sig;
 138         uint32_t bkt_index, i;
 139         uint8_t n = 0;
 140         bkt_index = bucket_idx & t->bucket_mask;
 141         bkt0 = &t->buckets[bkt_index];
 142         sig = (bucket_idx >> 16) | 1LLU;
 143
 144         /* Key is present in the bucket */
 145         for (bkt = bkt0; bkt != NULL; bkt = BUCKET_NEXT(bkt)) {
 146                 for (i = 0; i < 4; i++) {
 147                         uint64_t bkt_sig = (uint64_t) bkt->sig[i];
 148                         uint32_t bkt_key_index = bkt->key_pos[i];
 149                         uint8_t *bkt_key =
 150                                 &t->key_mem[bkt_key_index << t->key_size_shl];
 151
 152                         if (sig == bkt_sig) {
 153                                 key[n] = bkt_key;
 154                                 entries[n++] = &t->data_mem[bkt_key_index << t->data_size_shl];
 155                                 /* Assume no more than 4 entries in total (including extended state) */
 156                                 if (n == 4)
 157                                         return t->n_buckets;
 158                         }
 159                 }
 160         }
 161         return t->n_buckets;
 162 }
 163
 164 uint64_t get_bucket_key8(void* table, uint32_t bucket_idx, void** key, void** entries)
 165 {
 166         struct rte_bucket_4_8 *bucket, *bucket0;
 167         struct rte_table_hash_key8* f = table;
 168         uint8_t n = 0;
 169
 170         bucket0 = (struct rte_bucket_4_8 *) &f->memory[bucket_idx * f->bucket_size];
 171         for (bucket = bucket0; bucket != NULL; bucket = bucket->next) {
 172                 uint64_t mask;
 173
 174                 for (uint8_t i = 0, mask = 1LLU; i < 4; i++, mask <<= 1) {
 175                         uint64_t bucket_signature = bucket->signature;
 176
 177                         if (bucket_signature & mask) {
 178                                 key[n] = &bucket->key[i];
 179                                 entries[n++] = &bucket->data[i *f->entry_size];
 180                                 /* Assume no more than 4 entries
 181                                    in total (including extended state) */
 182                                 if (n == 4)
 183                                         return f->n_buckets;
 184                         }
 185                 }
 186         }
 187         return f->n_buckets;
 188 }
 189
 190 uint64_t hash_crc32(void* key, __attribute__((unused))void *key_mask, uint32_t key_size, uint64_t seed)
 191 {
 192         return rte_hash_crc(key, key_size, seed);
 193 }