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