vppinfra/vppinfra/pfhash.h

   1 /*
   2   Copyright (c) 2013 Cisco and/or its affiliates.
   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 #ifndef included_clib_pfhash_h
  18 #define included_clib_pfhash_h
  19
  20
  21 #include <vppinfra/clib.h>
  22 #include <vppinfra/hash.h>
  23 #include <vppinfra/pool.h>
  24
  25 #if defined(CLIB_HAVE_VEC128) && ! defined (__ALTIVEC__)
  26
  27 typedef struct
  28 {
  29   /* 3 x 16 = 48 key bytes */
  30   union
  31   {
  32     u32x4 k_u32x4[3];
  33     u64 k_u64[6];
  34   } kb;
  35   /* 3 x 4 = 12 value bytes */
  36   u32 values[3];
  37   u32 pad;
  38 } pfhash_kv_16_t;
  39
  40 typedef struct
  41 {
  42   /* 5 x 8 = 40 key bytes */
  43   union
  44   {
  45     u64 k_u64[5];
  46   } kb;
  47
  48   /* 5 x 4 = 20 value bytes */
  49   u32 values[5];
  50   u32 pad;
  51 } pfhash_kv_8_t;
  52
  53 typedef struct
  54 {
  55   /* 4 x 8 = 32 key bytes */
  56   union
  57   {
  58     u64 k_u64[4];
  59   } kb;
  60
  61   /* 4 x 8 = 32 value bytes */
  62   u64 values[4];
  63 } pfhash_kv_8v8_t;
  64
  65 typedef struct
  66 {
  67   /* 8 x 4 = 32 key bytes */
  68   union
  69   {
  70     u32x4 k_u32x4[2];
  71     u32 kb[8];
  72   } kb;
  73
  74   /* 8 x 4 = 32 value bytes */
  75   u32 values[8];
  76 } pfhash_kv_4_t;
  77
  78 typedef union
  79 {
  80   pfhash_kv_16_t kv16;
  81   pfhash_kv_8_t kv8;
  82   pfhash_kv_8v8_t kv8v8;
  83   pfhash_kv_4_t kv4;
  84 } pfhash_kv_t;
  85
  86 typedef struct
  87 {
  88   /* Bucket vector */
  89   u32 *buckets;
  90 #define PFHASH_BUCKET_OVERFLOW (u32)~0
  91
  92   /* Pool of key/value pairs */
  93   pfhash_kv_t *kvp;
  94
  95   /* overflow plain-o-hash */
  96   uword *overflow_hash;
  97
  98   /* Pretty-print name */
  99   u8 *name;
 100
 101   u32 key_size;
 102   u32 value_size;
 103
 104   u32 overflow_count;
 105   u32 nitems;
 106   u32 nitems_in_overflow;
 107 } pfhash_t;
 108
 109 void pfhash_init (pfhash_t * p, char *name, u32 key_size, u32 value_size,
 110                   u32 nbuckets);
 111 void pfhash_free (pfhash_t * p);
 112 u64 pfhash_get (pfhash_t * p, u32 bucket, void *key);
 113 void pfhash_set (pfhash_t * p, u32 bucket, void *key, void *value);
 114 void pfhash_unset (pfhash_t * p, u32 bucket, void *key);
 115
 116 format_function_t format_pfhash;
 117
 118 static inline void
 119 pfhash_prefetch_bucket (pfhash_t * p, u32 bucket)
 120 {
 121   CLIB_PREFETCH (&p->buckets[bucket], CLIB_CACHE_LINE_BYTES, LOAD);
 122 }
 123
 124 static inline u32
 125 pfhash_read_bucket_prefetch_kv (pfhash_t * p, u32 bucket)
 126 {
 127   u32 bucket_contents = p->buckets[bucket];
 128   if (PREDICT_TRUE ((bucket_contents & PFHASH_BUCKET_OVERFLOW) == 0))
 129     CLIB_PREFETCH (&p->kvp[bucket_contents], CLIB_CACHE_LINE_BYTES, LOAD);
 130   return bucket_contents;
 131 }
 132
 133 /*
 134  * pfhash_search_kv_16
 135  * See if the supplied 16-byte key matches one of three 16-byte (key,value) pairs.
 136  * Return the indicated value, or ~0 if no match
 137  *
 138  * Note: including the overflow test, the fast path is 35 instrs
 139  * on x86_64. Elves will steal your keyboard in the middle of the night if
 140  * you "improve" it without checking the generated code!
 141  */
 142 static inline u32
 143 pfhash_search_kv_16 (pfhash_t * p, u32 bucket_contents, u32x4 * key)
 144 {
 145   u32x4 diff0, diff1, diff2;
 146   u32 is_equal0, is_equal1, is_equal2;
 147   u32 no_match;
 148   pfhash_kv_16_t *kv;
 149   u32 rv;
 150
 151   if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
 152     {
 153       uword *hp;
 154       hp = hash_get_mem (p->overflow_hash, key);
 155       if (hp)
 156         return hp[0];
 157       return (u32) ~ 0;
 158     }
 159
 160   kv = &p->kvp[bucket_contents].kv16;
 161
 162   diff0 = u32x4_sub (kv->kb.k_u32x4[0], key[0]);
 163   diff1 = u32x4_sub (kv->kb.k_u32x4[1], key[0]);
 164   diff2 = u32x4_sub (kv->kb.k_u32x4[2], key[0]);
 165
 166   no_match = is_equal0 = (i16) u32x4_zero_byte_mask (diff0);
 167   is_equal1 = (i16) u32x4_zero_byte_mask (diff1);
 168   no_match |= is_equal1;
 169   is_equal2 = (i16) u32x4_zero_byte_mask (diff2);
 170   no_match |= is_equal2;
 171   /* If any of the three items matched, no_match will be zero after this line */
 172   no_match = ~no_match;
 173
 174   rv = (is_equal0 & kv->values[0])
 175     | (is_equal1 & kv->values[1]) | (is_equal2 & kv->values[2]) | no_match;
 176
 177   return rv;
 178 }
 179
 180 static inline u32
 181 pfhash_search_kv_8 (pfhash_t * p, u32 bucket_contents, u64 * key)
 182 {
 183   pfhash_kv_8_t *kv;
 184   u32 rv = (u32) ~ 0;
 185
 186   if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
 187     {
 188       uword *hp;
 189       hp = hash_get_mem (p->overflow_hash, key);
 190       if (hp)
 191         return hp[0];
 192       return (u32) ~ 0;
 193     }
 194
 195   kv = &p->kvp[bucket_contents].kv8;
 196
 197   rv = (kv->kb.k_u64[0] == key[0]) ? kv->values[0] : rv;
 198   rv = (kv->kb.k_u64[1] == key[0]) ? kv->values[1] : rv;
 199   rv = (kv->kb.k_u64[2] == key[0]) ? kv->values[2] : rv;
 200   rv = (kv->kb.k_u64[3] == key[0]) ? kv->values[3] : rv;
 201   rv = (kv->kb.k_u64[4] == key[0]) ? kv->values[4] : rv;
 202
 203   return rv;
 204 }
 205
 206 static inline u64
 207 pfhash_search_kv_8v8 (pfhash_t * p, u32 bucket_contents, u64 * key)
 208 {
 209   pfhash_kv_8v8_t *kv;
 210   u64 rv = (u64) ~ 0;
 211
 212   if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
 213     {
 214       uword *hp;
 215       hp = hash_get_mem (p->overflow_hash, key);
 216       if (hp)
 217         return hp[0];
 218       return (u64) ~ 0;
 219     }
 220
 221   kv = &p->kvp[bucket_contents].kv8v8;
 222
 223   rv = (kv->kb.k_u64[0] == key[0]) ? kv->values[0] : rv;
 224   rv = (kv->kb.k_u64[1] == key[0]) ? kv->values[1] : rv;
 225   rv = (kv->kb.k_u64[2] == key[0]) ? kv->values[2] : rv;
 226   rv = (kv->kb.k_u64[3] == key[0]) ? kv->values[3] : rv;
 227
 228   return rv;
 229 }
 230
 231 static inline u32
 232 pfhash_search_kv_4 (pfhash_t * p, u32 bucket_contents, u32 * key)
 233 {
 234   u32x4 vector_key;
 235   u32x4 is_equal[2];
 236   u32 zbm[2], winner_index;
 237   pfhash_kv_4_t *kv;
 238
 239   if (PREDICT_FALSE (bucket_contents == PFHASH_BUCKET_OVERFLOW))
 240     {
 241       uword *hp;
 242       hp = hash_get_mem (p->overflow_hash, key);
 243       if (hp)
 244         return hp[0];
 245       return (u32) ~ 0;
 246     }
 247
 248   kv = &p->kvp[bucket_contents].kv4;
 249
 250   vector_key = u32x4_splat (key[0]);
 251
 252   is_equal[0] = u32x4_is_equal (kv->kb.k_u32x4[0], vector_key);
 253   is_equal[1] = u32x4_is_equal (kv->kb.k_u32x4[1], vector_key);
 254   zbm[0] = ~u32x4_zero_byte_mask (is_equal[0]) & 0xFFFF;
 255   zbm[1] = ~u32x4_zero_byte_mask (is_equal[1]) & 0xFFFF;
 256
 257   if (PREDICT_FALSE ((zbm[0] == 0) && (zbm[1] == 0)))
 258     return (u32) ~ 0;
 259
 260   winner_index = min_log2 (zbm[0]) >> 2;
 261   winner_index = zbm[1] ? (4 + (min_log2 (zbm[1]) >> 2)) : winner_index;
 262
 263   return kv->values[winner_index];
 264 }
 265
 266 #endif /* CLIB_HAVE_VEC128 */
 267
 268 #endif /* included_clib_pfhash_h */
 269
 270 /*
 271  * fd.io coding-style-patch-verification: ON
 272  *
 273  * Local Variables:
 274  * eval: (c-set-style "gnu")
 275  * End:
 276  */