FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
phash.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2005 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 #ifndef included_phash_h
39 #define included_phash_h
40 
41 #include <vppinfra/hash.h> /* for Bob's mixing functions */
42 
43 typedef struct
44 {
45  /* Maybe either pointer to vector or inline word. */
47 
48  /* Hash code (A, B). */
49  u32 a, b;
50 } phash_key_t;
51 
52 /* Table indexed by B. */
53 typedef struct
54 {
55  /* Vector of key indices with this same value of B. */
57 
58  /* hash=a^tabb[b].val_b */
60 
61  /* High watermark of who has visited this map node. */
63 } phash_tabb_t;
64 
65 always_inline void
67 {
68  vec_free (b->keys);
69  b->val_b = b->water_b = 0;
70 }
71 
72 typedef struct
73 {
74  /* b that currently occupies this hash */
76 
77  /* Queue position of parent that could use this hash. */
79 
80  /* What to change parent tab[b] to use this hash. */
82 
83  /* Original value of tab[b]. */
85 } phash_tabq_t;
86 
87 typedef struct
88 {
89  u8 a_bits, b_bits, s_bits, a_shift;
91  u32 *tab;
93 
94  /* Seed value for hash mixer. */
96 
98 
99  /* Key functions want 64 bit keys.
100  Use hash_mix64 rather than hash_mix32. */
101 #define PHASH_FLAG_MIX64 (1 << 0)
102 #define PHASH_FLAG_MIX32 (0 << 0)
103 
104  /* When b_bits is large enough (>= 12) we scramble. */
105 #define PHASH_FLAG_USE_SCRAMBLE (1 << 1)
106 
107  /* Slow mode gives smaller tables but at the expense of more run time. */
108 #define PHASH_FLAG_SLOW_MODE (0 << 2)
109 #define PHASH_FLAG_FAST_MODE (1 << 2)
110 
111  /* Generate minimal perfect hash instead of perfect hash. */
112 #define PHASH_FLAG_NON_MINIMAL (0 << 3)
113 #define PHASH_FLAG_MINIMAL (1 << 3)
114 
115  /* vec_len (keys) for minimal hash;
116  1 << s_bits for non-minimal hash. */
118 
119  /* Vector of keys. */
121 
122  /* Used by callbacks to identify keys. */
123  void *private;
124 
125  /* Key comparison callback. */
126  int (*key_is_equal) (void *private, uword key1, uword key2);
127 
128  /* Callback to reduce single key -> hash seeds. */
129  void (*key_seed1) (void *private, uword key, void *seed);
130 
131  /* Callback to reduce two key2 -> hash seeds. */
132  void (*key_seed2) (void *private, uword key1, uword key2, void *seed);
133 
134  /* Stuff used to compute perfect hash. */
136 
137  /* Stuff indexed by B. */
139 
140  /* Table of B ordered by number of keys in tabb[b]. */
142 
143  /* Unique key (or ~0 if none) for a given hash
144  H = A ^ scramble[tab[B].val_b]. */
146 
147  /* Stuff indexed by q. */
149 
150  /* Stats. */
151  u32 n_seed_trials, n_perfect_calls;
152 } phash_main_t;
153 
154 always_inline void
156 {
157  vec_free (pm->tabb);
158  vec_free (pm->tabq);
159  vec_free (pm->tabh);
160  vec_free (pm->tabb_sort);
161  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
162  vec_free (pm->scramble);
163 }
164 
165 always_inline void
167 {
169  vec_free (pm->tab);
170  vec_free (pm->keys);
171  clib_memset (pm, 0, sizeof (pm[0]));
172 }
173 
174 /* Slow hash computation for general keys. */
176 
177 /* Main routine to compute perfect hash. */
179 
180 /* Validates that hash is indeed perfect. */
182 
183 /* Unit test. */
184 int phash_test_main (unformat_input_t * input);
185 
186 #endif /* included_phash_h */
187 
188 /*
189  * fd.io coding-style-patch-verification: ON
190  *
191  * Local Variables:
192  * eval: (c-set-style "gnu")
193  * End:
194  */
phash_main_t::flags
u32 flags
Definition: phash.h:97
phash_main_t::scramble
u32 * scramble
Definition: phash.h:92
phash_main_t::tabb
phash_tabb_t * tabb
Definition: phash.h:138
phash_tabb_t
Definition: phash.h:53
phash_key_t::key
uword key
Definition: phash.h:46
phash_tabb_t::water_b
u32 water_b
Definition: phash.h:62
phash_main_t::s_bits
u8 s_bits
Definition: phash.h:89
phash_main_t::tabq
phash_tabq_t * tabq
Definition: phash.h:148
phash_main_t::tab
u32 * tab
Definition: phash.h:91
phash_main_t::hash_max
u32 hash_max
Definition: phash.h:117
phash_tabq_t::parent_q
u32 parent_q
Definition: phash.h:78
phash_main_t::n_seed_trials
u32 n_seed_trials
Definition: phash.h:151
unformat_input_t
struct _unformat_input_t unformat_input_t
phash_main_t::hash_seed
u64 hash_seed
Definition: phash.h:95
key
typedef key
Definition: ipsec_types.api:91
phash_main_t::tabb_sort
u32 * tabb_sort
Definition: phash.h:141
hash.h
phash_key_t
Definition: phash.h:43
phash_main_t
Definition: phash.h:87
uword
u64 uword
Definition: types.h:112
phash_find_perfect_hash
clib_error_t * phash_find_perfect_hash(phash_main_t *pm)
Definition: phash.c:822
phash_tabq_t::oldval_q
u32 oldval_q
Definition: phash.h:84
phash_test_main
int phash_test_main(unformat_input_t *input)
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
phash_main_free_working_memory
static void phash_main_free_working_memory(phash_main_t *pm)
Definition: phash.h:155
phash_validate
clib_error_t * phash_validate(phash_main_t *pm)
Definition: phash.c:981
u64
unsigned long u64
Definition: types.h:89
phash_tabb_t::keys
u32 * keys
Definition: phash.h:56
u32
unsigned int u32
Definition: types.h:88
phash_tabq_t::b_q
u32 b_q
Definition: phash.h:75
phash_main_free
static void phash_main_free(phash_main_t *pm)
Definition: phash.h:166
phash_main_t::tabh
u32 * tabh
Definition: phash.h:145
phash_tabq_t
Definition: phash.h:72
clib_memset
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
phash_main_t::keys
phash_key_t * keys
Definition: phash.h:120
b
vlib_buffer_t ** b
Definition: nat44_ei_out2in.c:717
u8
unsigned char u8
Definition: types.h:56
clib_error_t
Definition: clib_error.h:21
a
a
Definition: bitmap.h:525
phash_main_t::random_seed
u32 random_seed
Definition: phash.h:135
phash_tabq_t::newval_q
u32 newval_q
Definition: phash.h:81
phash_main_t::b_mask
u32 b_mask
Definition: phash.h:90
phash_key_t::b
u32 b
Definition: phash.h:49
phash_hash_slow
uword phash_hash_slow(phash_main_t *pm, uword key)
Definition: phash.c:924
phash_tabb_t::val_b
u32 val_b
Definition: phash.h:59
phash_tabb_free
static void phash_tabb_free(phash_tabb_t *b)
Definition: phash.h:66
PHASH_FLAG_USE_SCRAMBLE
#define PHASH_FLAG_USE_SCRAMBLE
Definition: phash.h:105