FD.io VPP  v18.07-34-g55fbdb9
Vector Packet Processing
phash.c
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 /* This is all stolen from Bob Jenkins and reworked for clib. Thanks
39  once again Bob for the great work. */
40 
41 /*
42 ------------------------------------------------------------------------------
43 perfect.c: code to generate code for a hash for perfect hashing.
44 (c) Bob Jenkins, September 1996, December 1999
45 You may use this code in any way you wish, and it is free. No warranty.
46 I hereby place this in the public domain.
47 Source is http://burtleburtle.net/bob/c/perfect.c
48 
49 This generates a minimal perfect hash function. That means, given a
50 set of n keys, this determines a hash function that maps each of
51 those keys into a value in 0..n-1 with no collisions.
52 
53 The perfect hash function first uses a normal hash function on the key
54 to determine (a,b) such that the pair (a,b) is distinct for all
55 keys, then it computes a^scramble[tab[b]] to get the final perfect hash.
56 tab[] is an array of 1-byte values and scramble[] is a 256-term array of
57 2-byte or 4-byte values. If there are n keys, the length of tab[] is a
58 power of two between n/3 and n.
59 
60 I found the idea of computing distinct (a,b) values in "Practical minimal
61 perfect hash functions for large databases", Fox, Heath, Chen, and Daoud,
62 Communications of the ACM, January 1992. They found the idea in Chichelli
63 (CACM Jan 1980). Beyond that, our methods differ.
64 
65 The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in
66 0..*blen*-1. A fast hash function determines both a and b
67 simultaneously. Any decent hash function is likely to produce
68 hashes so that (a,b) is distinct for all pairs. I try the hash
69 using different values of *salt* until all pairs are distinct.
70 
71 The final hash is (a XOR scramble[tab[b]]). *scramble* is a
72 predetermined mapping of 0..255 into 0..smax-1. *tab* is an
73 array that we fill in in such a way as to make the hash perfect.
74 
75 First we fill in all values of *tab* that are used by more than one
76 key. We try all possible values for each position until one works.
77 
78 This leaves m unmapped keys and m values that something could hash to.
79 If you treat unmapped keys as lefthand nodes and unused hash values
80 as righthand nodes, and draw a line connecting each key to each hash
81 value it could map to, you get a bipartite graph. We attempt to
82 find a perfect matching in this graph. If we succeed, we have
83 determined a perfect hash for the whole set of keys.
84 
85 *scramble* is used because (a^tab[i]) clusters keys around *a*.
86 ------------------------------------------------------------------------------
87 */
88 
89 #include <vppinfra/bitmap.h>
90 #include <vppinfra/format.h>
91 #include <vppinfra/phash.h>
92 #include <vppinfra/random.h>
93 
94 static void
96 {
97  int n_keys_left, b_mask, a_shift;
98  u32 seed;
99  phash_key_t *k;
100 
101  seed = pm->hash_seed;
102  b_mask = (1 << pm->b_bits) - 1;
103  a_shift = BITS (seed) - pm->a_bits;
104 
105  k = pm->keys;
106  n_keys_left = vec_len (pm->keys);
107 
108  while (n_keys_left >= 2)
109  {
110  u32 x0, y0, z0;
111  u32 x1, y1, z1;
112 
113  x0 = y0 = z0 = seed;
114  x1 = y1 = z1 = seed;
115  x0 += (u32) k[0].key;
116  x1 += (u32) k[1].key;
117 
118  hash_mix32 (x0, y0, z0);
119  hash_mix32 (x1, y1, z1);
120 
121  k[0].b = z0 & b_mask;
122  k[1].b = z1 & b_mask;
123  k[0].a = z0 >> a_shift;
124  k[1].a = z1 >> a_shift;
125  if (PREDICT_FALSE (a_shift >= BITS (z0)))
126  k[0].a = k[1].a = 0;
127 
128  k += 2;
129  n_keys_left -= 2;
130  }
131 
132  if (n_keys_left >= 1)
133  {
134  u32 x0, y0, z0;
135 
136  x0 = y0 = z0 = seed;
137  x0 += k[0].key;
138 
139  hash_mix32 (x0, y0, z0);
140 
141  k[0].b = z0 & b_mask;
142  k[0].a = z0 >> a_shift;
143  if (PREDICT_FALSE (a_shift >= BITS (z0)))
144  k[0].a = 0;
145 
146  k += 1;
147  n_keys_left -= 1;
148  }
149 }
150 
151 static void
153 {
154  int n_keys_left, b_mask, a_shift;
155  u64 seed;
156  phash_key_t *k;
157 
158  seed = pm->hash_seed;
159  b_mask = (1 << pm->b_bits) - 1;
160  a_shift = BITS (seed) - pm->a_bits;
161 
162  k = pm->keys;
163  n_keys_left = vec_len (pm->keys);
164 
165  while (n_keys_left >= 2)
166  {
167  u64 x0, y0, z0;
168  u64 x1, y1, z1;
169 
170  x0 = y0 = z0 = seed;
171  x1 = y1 = z1 = seed;
172  x0 += (u64) k[0].key;
173  x1 += (u64) k[1].key;
174 
175  hash_mix64 (x0, y0, z0);
176  hash_mix64 (x1, y1, z1);
177 
178  k[0].b = z0 & b_mask;
179  k[1].b = z1 & b_mask;
180  k[0].a = z0 >> a_shift;
181  k[1].a = z1 >> a_shift;
182  if (PREDICT_FALSE (a_shift >= BITS (z0)))
183  k[0].a = k[1].a = 0;
184 
185  k += 2;
186  n_keys_left -= 2;
187  }
188 
189  if (n_keys_left >= 1)
190  {
191  u64 x0, y0, z0;
192 
193  x0 = y0 = z0 = seed;
194  x0 += k[0].key;
195 
196  hash_mix64 (x0, y0, z0);
197 
198  k[0].b = z0 & b_mask;
199  k[0].a = z0 >> a_shift;
200  if (PREDICT_FALSE (a_shift >= BITS (z0)))
201  k[0].a = 0;
202 
203  k += 1;
204  n_keys_left -= 1;
205  }
206 }
207 
208 static void
210 {
211  int n_keys_left, b_mask, a_shift;
212  u32 seed;
213  phash_key_t *k;
214 
215  seed = pm->hash_seed;
216  b_mask = (1 << pm->b_bits) - 1;
217  a_shift = BITS (seed) - pm->a_bits;
218 
219  k = pm->keys;
220  n_keys_left = vec_len (pm->keys);
221 
222  while (n_keys_left >= 2)
223  {
224  u32 xyz[6];
225  u32 x0, y0, z0;
226  u32 x1, y1, z1;
227 
228  pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
229 
230  x0 = y0 = z0 = seed;
231  x1 = y1 = z1 = seed;
232  x0 += xyz[0];
233  y0 += xyz[1];
234  z0 += xyz[2];
235  x1 += xyz[3];
236  y1 += xyz[4];
237  z1 += xyz[5];
238 
239  hash_mix32 (x0, y0, z0);
240  hash_mix32 (x1, y1, z1);
241 
242  k[0].b = z0 & b_mask;
243  k[1].b = z1 & b_mask;
244  k[0].a = z0 >> a_shift;
245  k[1].a = z1 >> a_shift;
246  if (PREDICT_FALSE (a_shift >= BITS (z0)))
247  k[0].a = k[1].a = 0;
248 
249  k += 2;
250  n_keys_left -= 2;
251  }
252 
253  if (n_keys_left >= 1)
254  {
255  u32 xyz[3];
256  u32 x0, y0, z0;
257 
258  pm->key_seed1 (pm->private, k[0].key, &xyz);
259 
260  x0 = y0 = z0 = seed;
261  x0 += xyz[0];
262  y0 += xyz[1];
263  z0 += xyz[2];
264 
265  hash_mix32 (x0, y0, z0);
266 
267  k[0].b = z0 & b_mask;
268  k[0].a = z0 >> a_shift;
269  if (PREDICT_FALSE (a_shift >= BITS (z0)))
270  k[0].a = 0;
271 
272  k += 1;
273  n_keys_left -= 1;
274  }
275 }
276 
277 static void
279 {
280  int n_keys_left, b_mask, a_shift;
281  u64 seed;
282  phash_key_t *k;
283 
284  seed = pm->hash_seed;
285  b_mask = (1 << pm->b_bits) - 1;
286  a_shift = BITS (seed) - pm->a_bits;
287 
288  k = pm->keys;
289  n_keys_left = vec_len (pm->keys);
290 
291  while (n_keys_left >= 2)
292  {
293  u64 xyz[6];
294  u64 x0, y0, z0;
295  u64 x1, y1, z1;
296 
297  pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
298 
299  x0 = y0 = z0 = seed;
300  x1 = y1 = z1 = seed;
301  x0 += xyz[0];
302  y0 += xyz[1];
303  z0 += xyz[2];
304  x1 += xyz[3];
305  y1 += xyz[4];
306  z1 += xyz[5];
307 
308  hash_mix64 (x0, y0, z0);
309  hash_mix64 (x1, y1, z1);
310 
311  k[0].b = z0 & b_mask;
312  k[1].b = z1 & b_mask;
313  k[0].a = z0 >> a_shift;
314  k[1].a = z1 >> a_shift;
315  if (PREDICT_FALSE (a_shift >= BITS (z0)))
316  k[0].a = k[1].a = 0;
317 
318  k += 2;
319  n_keys_left -= 2;
320  }
321 
322  if (n_keys_left >= 1)
323  {
324  u64 xyz[3];
325  u64 x0, y0, z0;
326 
327  pm->key_seed1 (pm->private, k[0].key, &xyz);
328 
329  x0 = y0 = z0 = seed;
330  x0 += xyz[0];
331  y0 += xyz[1];
332  z0 += xyz[2];
333 
334  hash_mix64 (x0, y0, z0);
335 
336  k[0].b = z0 & b_mask;
337  k[0].a = z0 >> a_shift;
338  if (PREDICT_FALSE (a_shift >= BITS (z0)))
339  k[0].a = 0;
340 
341  k += 1;
342  n_keys_left -= 1;
343  }
344 }
345 
346 /*
347  * insert keys into table according to key->b
348  * check if the initial hash might work
349  */
350 static int
352 {
353  int no_collisions;
354  phash_tabb_t *tb;
355  phash_key_t *k, *l;
356 
357  if (pm->key_seed1)
358  {
359  if (pm->flags & PHASH_FLAG_MIX64)
361  else
363  }
364  else
365  {
366  if (pm->flags & PHASH_FLAG_MIX64)
368  else
370  }
371 
372  if (!pm->tabb)
373  vec_resize (pm->tabb, 1 << pm->b_bits);
374  else
375  vec_foreach (tb, pm->tabb) phash_tabb_free (tb);
376 
377  /* Two keys with the same (a,b) guarantees a collision */
378  no_collisions = 1;
379  vec_foreach (k, pm->keys)
380  {
381  u32 i, *ki;
382 
383  tb = pm->tabb + k->b;
384  ki = tb->keys;
385  for (i = 0; i < vec_len (ki); i++)
386  {
387  l = pm->keys + ki[i];
388  if (k->a == l->a)
389  {
390  /* Given keys are supposed to be unique. */
391  if (pm->key_is_equal
392  && pm->key_is_equal (pm->private, l->key, k->key))
393  clib_error ("duplicate keys");
394  no_collisions = 0;
395  goto done;
396  }
397  }
398 
399  vec_add1 (tb->keys, k - pm->keys);
400  }
401 
402 done:
403  return no_collisions;
404 }
405 
406 /* Try to apply an augmenting list */
407 static int
408 apply (phash_main_t * pm, u32 tail, u32 rollback)
409 {
410  phash_key_t *k;
411  phash_tabb_t *pb;
412  phash_tabq_t *q_child, *q_parent;
413  u32 ki, i, hash, child, parent;
414  u32 stabb; /* scramble[tab[b]] */
415  int no_collision;
416 
417  no_collision = 1;
418 
419  /* Walk from child to parent until root is reached. */
420  for (child = tail - 1; child; child = parent)
421  {
422  q_child = &pm->tabq[child];
423  parent = q_child->parent_q;
424  q_parent = &pm->tabq[parent];
425 
426  /* find parent's list of siblings */
427  ASSERT (q_parent->b_q < vec_len (pm->tabb));
428  pb = pm->tabb + q_parent->b_q;
429 
430  /* erase old hash values */
431  stabb = pm->scramble[pb->val_b];
432  for (i = 0; i < vec_len (pb->keys); i++)
433  {
434  ki = pb->keys[i];
435  k = pm->keys + ki;
436  hash = k->a ^ stabb;
437 
438  /* Erase hash for all of child's siblings. */
439  if (ki == pm->tabh[hash])
440  pm->tabh[hash] = ~0;
441  }
442 
443  /* change pb->val_b, which will change the hashes of all parent siblings */
444  pb->val_b = rollback ? q_child->oldval_q : q_child->newval_q;
445 
446  /* set new hash values */
447  stabb = pm->scramble[pb->val_b];
448  for (i = 0; i < vec_len (pb->keys); i++)
449  {
450  ki = pb->keys[i];
451  k = pm->keys + ki;
452 
453  hash = k->a ^ stabb;
454  if (rollback)
455  {
456  if (parent == 0)
457  continue; /* root never had a hash */
458  }
459  else if (pm->tabh[hash] != ~0)
460  {
461  /* Very rare case: roll back any changes. */
462  apply (pm, tail, /* rollback changes */ 1);
463  no_collision = 0;
464  goto done;
465  }
466  pm->tabh[hash] = ki;
467  }
468  }
469 
470 done:
471  return no_collision;
472 }
473 
474 
475 /*
476 -------------------------------------------------------------------------------
477 augment(): Add item to the mapping.
478 
479 Construct a spanning tree of *b*s with *item* as root, where each
480 parent can have all its hashes changed (by some new val_b) with
481 at most one collision, and each child is the b of that collision.
482 
483 I got this from Tarjan's "Data Structures and Network Algorithms". The
484 path from *item* to a *b* that can be remapped with no collision is
485 an "augmenting path". Change values of tab[b] along the path so that
486 the unmapped key gets mapped and the unused hash value gets used.
487 
488 Assuming 1 key per b, if m out of n hash values are still unused,
489 you should expect the transitive closure to cover n/m nodes before
490 an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect
491 this approach to take about nlogn time to map all single-key b's.
492 -------------------------------------------------------------------------------
493 
494 high_water: a value higher than any now in tabb[].water_b.
495 */
496 static int
497 augment (phash_main_t * pm, u32 b_root, u32 high_water)
498 {
499  u32 q; /* current position walking through the queue */
500  u32 tail; /* tail of the queue. 0 is the head of the queue. */
501  phash_tabb_t *tb_parent, *tb_child, *tb_hit;
502  phash_key_t *k_parent, *k_child;
503  u32 v, v_limit; /* possible value for myb->val_b */
504  u32 i, ki, hash;
505 
506  v_limit =
507  1 << ((pm->flags & PHASH_FLAG_USE_SCRAMBLE) ? pm->s_bits : BITS (u8));
508 
509  /* Initialize the root of the spanning tree. */
510  pm->tabq[0].b_q = b_root;
511  tail = 1;
512 
513  /* construct the spanning tree by walking the queue, add children to tail */
514  for (q = 0; q < tail; q++)
515  {
516  if ((pm->flags & PHASH_FLAG_FAST_MODE)
517  && !(pm->flags & PHASH_FLAG_MINIMAL) && q == 1)
518  break; /* don't do transitive closure */
519 
520  tb_parent = pm->tabb + pm->tabq[q].b_q; /* the b for this node */
521 
522  for (v = 0; v < v_limit; v++)
523  {
524  tb_child = 0;
525 
526  for (i = 0; i < vec_len (tb_parent->keys); i++)
527  {
528  ki = tb_parent->keys[i];
529  k_parent = pm->keys + ki;
530 
531  hash = k_parent->a ^ pm->scramble[v];
532  if (hash >= pm->hash_max)
533  goto try_next_v; /* hash code out of bounds => we can't use this v */
534 
535  ki = pm->tabh[hash];
536  if (ki == ~0)
537  continue;
538 
539  k_child = pm->keys + ki;
540  tb_hit = pm->tabb + k_child->b;
541 
542  if (tb_child)
543  {
544  /* Hit at most one child b. */
545  if (tb_child == tb_hit)
546  goto try_next_v;
547  }
548  else
549  {
550  /* Remember this as child b. */
551  tb_child = tb_hit;
552  if (tb_hit->water_b == high_water)
553  goto try_next_v; /* already explored */
554  }
555  }
556 
557  /* tb_parent with v has either one or zero collisions. */
558 
559  /* add childb to the queue of reachable things */
560  if (tb_child)
561  tb_child->water_b = high_water;
562  pm->tabq[tail].b_q = tb_child ? tb_child - pm->tabb : ~0;
563  pm->tabq[tail].newval_q = v; /* how to make parent (myb) use this hash */
564  pm->tabq[tail].oldval_q = tb_parent->val_b; /* need this for rollback */
565  pm->tabq[tail].parent_q = q;
566  ++tail;
567 
568  /* Found a v with no collisions? */
569  if (!tb_child)
570  {
571  /* Try to apply the augmenting path. */
572  if (apply (pm, tail, /* rollback */ 0))
573  return 1; /* success, item was added to the perfect hash */
574  --tail; /* don't know how to handle such a child! */
575  }
576 
577  try_next_v:
578  ;
579  }
580  }
581  return 0;
582 }
583 
584 
586 
587 static int
588 phash_tabb_compare (void *a1, void *a2)
589 {
590  u32 *b1 = a1;
591  u32 *b2 = a2;
592  phash_tabb_t *tb1, *tb2;
593 
594  tb1 = sort_tabb + b1[0];
595  tb2 = sort_tabb + b2[0];
596 
597  return ((int) vec_len (tb2->keys) - (int) vec_len (tb1->keys));
598 }
599 
600 /* find a mapping that makes this a perfect hash */
601 static int
603 {
604  u32 i;
605 
606  /* clear any state from previous attempts */
607  if (vec_bytes (pm->tabh))
608  memset (pm->tabh, ~0, vec_bytes (pm->tabh));
609 
610  vec_validate (pm->tabb_sort, vec_len (pm->tabb) - 1);
611  for (i = 0; i < vec_len (pm->tabb_sort); i++)
612  pm->tabb_sort[i] = i;
613 
614  sort_tabb = pm->tabb;
615 
617 
618  /* In descending order by number of keys, map all *b*s */
619  for (i = 0; i < vec_len (pm->tabb_sort); i++)
620  {
621  if (!augment (pm, pm->tabb_sort[i], i + 1))
622  return 0;
623  }
624 
625  /* Success! We found a perfect hash of all keys into 0..nkeys-1. */
626  return 1;
627 }
628 
629 
630 /*
631  * Find initial a_bits = log2 (a_max), b_bits = log2 (b_max).
632  * Initial a_max and b_max values were found empirically. Some factors:
633  *
634  * If s_max<256 there is no scramble, so tab[b] needs to cover 0..s_max-1.
635  *
636  * a_max and b_max must be powers of 2 because the values in 0..a_max-1 and
637  * 0..b_max-1 are produced by applying a bitmask to the initial hash function.
638  *
639  * a_max must be less than s_max, in fact less than n_keys, because otherwise
640  * there would often be no i such that a^scramble[i] is in 0..n_keys-1 for
641  * all the *a*s associated with a given *b*, so there would be no legal
642  * value to assign to tab[b]. This only matters when we're doing a minimal
643  * perfect hash.
644  *
645  * It takes around 800 trials to find distinct (a,b) with nkey=s_max*(5/8)
646  * and a_max*b_max = s_max*s_max/32.
647  *
648  * Values of b_max less than s_max/4 never work, and s_max/2 always works.
649  *
650  * We want b_max as small as possible because it is the number of bytes in
651  * the huge array we must create for the perfect hash.
652  *
653  * When nkey <= s_max*(5/8), b_max=s_max/4 works much more often with
654  * a_max=s_max/8 than with a_max=s_max/4. Above s_max*(5/8), b_max=s_max/4
655  * doesn't seem to care whether a_max=s_max/8 or a_max=s_max/4. I think it
656  * has something to do with 5/8 = 1/8 * 5. For example examine 80000,
657  * 85000, and 90000 keys with different values of a_max. This only matters
658  * if we're doing a minimal perfect hash.
659  *
660  * When a_max*b_max <= 1<<U32BITS, the initial hash must produce one integer.
661  * Bigger than that it must produce two integers, which increases the
662  * cost of the hash per character hashed.
663  */
664 static void
666 {
667  u32 s_bits, s_max, a_max, b_max, n_keys;
668  int is_minimal, is_fast_mode;
669  const u32 b_max_use_scramble_threshold = 4096;
670 
671  is_minimal = (pm->flags & PHASH_FLAG_MINIMAL) != 0;
672  is_fast_mode = (pm->flags & PHASH_FLAG_FAST_MODE) != 0;
673 
674  n_keys = vec_len (pm->keys);
675  s_bits = max_log2 (n_keys);
676  s_max = 1 << s_bits;
677  a_max = 0;
678 
679  if (is_minimal)
680  {
681  switch (s_bits)
682  {
683  case 0:
684  a_max = 1;
685  b_max = 1;
686  case 1:
687  case 2:
688  case 3:
689  case 4:
690  case 5:
691  case 6:
692  case 7:
693  case 8:
694  /*
695  * Was: a_max = is_minimal ? s_max / 2 : s_max;
696  * However, we know that is_minimal must be true, so the
697  * if-arm of the ternary expression is always executed.
698  */
699  a_max = s_max / 2;
700  b_max = s_max / 2;
701  break;
702  case 9:
703  case 10:
704  case 11:
705  case 12:
706  case 13:
707  case 14:
708  case 15:
709  case 16:
710  case 17:
711  if (is_fast_mode)
712  {
713  a_max = s_max / 2;
714  b_max = s_max / 4;
715  }
716  else if (s_max / 4 < b_max_use_scramble_threshold)
717  {
718  if (n_keys <= s_max * 0.52)
719  a_max = b_max = s_max / 8;
720  else
721  a_max = b_max = s_max / 4;
722  }
723  else
724  {
725  a_max = ((n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 :
726  (n_keys <=
727  s_max * (3.0 / 4.0)) ? s_max / 4 : s_max / 2);
728  b_max = s_max / 4; /* always give the small size a shot */
729  }
730  break;
731  case 18:
732  if (is_fast_mode)
733  a_max = b_max = s_max / 2;
734  else
735  {
736  a_max = s_max / 8; /* never require the multiword hash */
737  b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
738  }
739  break;
740  case 19:
741  case 20:
742  a_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : s_max / 2;
743  b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
744  break;
745  default:
746  /* Just find a hash as quick as possible.
747  We'll be thrashing virtual memory at this size. */
748  a_max = b_max = s_max / 2;
749  break;
750  }
751  }
752  else
753  {
754  /* Non-minimal perfect hash. */
755  if (is_fast_mode && n_keys > s_max * 0.8)
756  {
757  s_max *= 2;
758  s_bits += 1;
759  }
760 
761  if (s_max / 4 <= (1 << 14))
762  b_max = ((n_keys <= s_max * 0.56) ? s_max / 32 :
763  (n_keys <= s_max * 0.74) ? s_max / 16 : s_max / 8);
764  else
765  b_max = ((n_keys <= s_max * 0.6) ? s_max / 16 :
766  (n_keys <= s_max * 0.8) ? s_max / 8 : s_max / 4);
767 
768  if (is_fast_mode && b_max < s_max / 8)
769  b_max = s_max / 8;
770 
771  if (a_max < 1)
772  a_max = 1;
773  if (b_max < 1)
774  b_max = 1;
775  }
776 
777  ASSERT (s_max == (1 << s_bits));
778  ASSERT (is_pow2 (a_max));
779  ASSERT (is_pow2 (b_max));
780  pm->s_bits = s_bits;
781  pm->a_bits = min_log2 (a_max);
782  pm->b_bits = min_log2 (b_max);
783  if (b_max >= b_max_use_scramble_threshold)
785 }
786 
787 /* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */
788 /* permute(0)=0. This is intended and useful. */
791 {
792  int i;
793  int mask = (1 << nbits) - 1;
794  int const2 = 1 + nbits / 2;
795  int const3 = 1 + nbits / 3;
796  int const4 = 1 + nbits / 4;
797  int const5 = 1 + nbits / 5;
798  for (i = 0; i < 20; i++)
799  {
800  x = (x + (x << const2)) & mask;
801  x = (x ^ (x >> const3));
802  x = (x + (x << const4)) & mask;
803  x = (x ^ (x >> const5));
804  }
805  return x;
806 }
807 
808 /* initialize scramble[] with distinct random values in 0..smax-1 */
809 static void
811 {
812  u32 i;
813 
814  /* fill scramble[] with distinct random integers in 0..smax-1 */
815  vec_validate (pm->scramble, (1 << (pm->s_bits < 8 ? 8 : pm->s_bits)) - 1);
816  for (i = 0; i < vec_len (pm->scramble); i++)
817  pm->scramble[i] = scramble_permute (i, pm->s_bits);
818 }
819 
820 /* Try to find a perfect hash function. */
821 clib_error_t *
823 {
824  clib_error_t *error = 0;
825  u32 max_a_bits, n_tries_this_a_b, want_minimal;
826 
827  /* guess initial values for s_max, a_max and b_max */
829 
830  want_minimal = pm->flags & PHASH_FLAG_MINIMAL;
831 
832 new_s:
833  if (pm->b_bits == 0)
834  pm->a_bits = pm->s_bits;
835 
836  max_a_bits = pm->s_bits - want_minimal;
837  if (max_a_bits < 1)
838  max_a_bits = 1;
839 
840  pm->hash_max = want_minimal ? vec_len (pm->keys) : (1 << pm->s_bits);
841 
842  scramble_init (pm);
843 
844  /* Allocate working memory. */
845  vec_free (pm->tabh);
846  vec_validate_init_empty (pm->tabh, pm->hash_max - 1, ~0);
847  vec_free (pm->tabq);
848  vec_validate (pm->tabq, 1 << pm->b_bits);
849 
850  /* Actually find the perfect hash */
851  n_tries_this_a_b = 0;
852  while (1)
853  {
854  /* Choose random hash seeds until keys become unique. */
855  pm->hash_seed = random_u64 (&pm->random_seed);
856  pm->n_seed_trials++;
857  if (init_tabb (pm))
858  {
859  /* Found unique (A, B). */
860 
861  /* Hash may already be perfect. */
862  if (pm->b_bits == 0)
863  goto done;
864 
865  pm->n_perfect_calls++;
866  if (perfect (pm))
867  goto done;
868 
869  goto increase_b;
870  }
871 
872  /* Keep trying with different seed value. */
873  n_tries_this_a_b++;
874  if (n_tries_this_a_b < 2048)
875  continue;
876 
877  /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
878  if (pm->a_bits < max_a_bits)
879  pm->a_bits++;
880  else if (pm->b_bits < pm->s_bits)
881  {
882  increase_b:
883  vec_resize (pm->tabb, vec_len (pm->tabb));
884  vec_resize (pm->tabq, vec_len (pm->tabq));
885  pm->b_bits++;
886  }
887  else
888  {
889  /* Can't increase (A, B) any more, so try increasing S. */
890  goto new_s;
891  }
892  }
893 
894 done:
895  /* Construct mapping table for hash lookups. */
896  if (!error)
897  {
898  u32 b, v;
899 
900  pm->a_shift = ((pm->flags & PHASH_FLAG_MIX64) ? 64 : 32) - pm->a_bits;
901  pm->b_mask = (1 << pm->b_bits) - 1;
902 
903  vec_resize (pm->tab, vec_len (pm->tabb));
904  for (b = 0; b < vec_len (pm->tabb); b++)
905  {
906  v = pm->tabb[b].val_b;
907 
908  /* Apply scramble now for small enough value of b_bits. */
909  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
910  v = pm->scramble[v];
911 
912  pm->tab[b] = v;
913  }
914  }
915 
916  /* Free working memory. */
918 
919  return error;
920 }
921 
922 /* Slow hash computation for general keys. */
923 uword
925 {
926  u32 a, b, v;
927 
928  if (pm->flags & PHASH_FLAG_MIX64)
929  {
930  u64 x0, y0, z0;
931 
932  x0 = y0 = z0 = pm->hash_seed;
933 
934  if (pm->key_seed1)
935  {
936  u64 xyz[3];
937  pm->key_seed1 (pm->private, key, &xyz);
938  x0 += xyz[0];
939  y0 += xyz[1];
940  z0 += xyz[2];
941  }
942  else
943  x0 += key;
944 
945  hash_mix64 (x0, y0, z0);
946 
947  a = z0 >> pm->a_shift;
948  b = z0 & pm->b_mask;
949  }
950  else
951  {
952  u32 x0, y0, z0;
953 
954  x0 = y0 = z0 = pm->hash_seed;
955 
956  if (pm->key_seed1)
957  {
958  u32 xyz[3];
959  pm->key_seed1 (pm->private, key, &xyz);
960  x0 += xyz[0];
961  y0 += xyz[1];
962  z0 += xyz[2];
963  }
964  else
965  x0 += key;
966 
967  hash_mix32 (x0, y0, z0);
968 
969  a = z0 >> pm->a_shift;
970  b = z0 & pm->b_mask;
971  }
972 
973  v = pm->tab[b];
974  if (pm->flags & PHASH_FLAG_USE_SCRAMBLE)
975  v = pm->scramble[v];
976  return a ^ v;
977 }
978 
979 /* Verify that perfect hash is perfect. */
980 clib_error_t *
982 {
983  phash_key_t *k;
984  uword *unique_bitmap = 0;
985  clib_error_t *error = 0;
986 
987  vec_foreach (k, pm->keys)
988  {
989  uword h = phash_hash_slow (pm, k->key);
990 
991  if (h >= pm->hash_max)
992  {
993  error = clib_error_return (0, "hash out of range %wd", h);
994  goto done;
995  }
996 
997  if (clib_bitmap_get (unique_bitmap, h))
998  {
999  error = clib_error_return (0, "hash non-unique");
1000  goto done;
1001  }
1002 
1003  unique_bitmap = clib_bitmap_ori (unique_bitmap, h);
1004  }
1005 
1006 done:
1007  clib_bitmap_free (unique_bitmap);
1008  return error;
1009 }
1010 
1011 /*
1012  * fd.io coding-style-patch-verification: ON
1013  *
1014  * Local Variables:
1015  * eval: (c-set-style "gnu")
1016  * End:
1017  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:437
static void init_keys_indirect_u32(phash_main_t *pm)
Definition: phash.c:209
void * private
Definition: phash.h:123
u32 water_b
Definition: phash.h:62
clib_error_t * phash_validate(phash_main_t *pm)
Definition: phash.c:981
u8 a_shift
Definition: phash.h:89
a
Definition: bitmap.h:538
u32 random_seed
Definition: phash.h:135
#define clib_error(format, args...)
Definition: error.h:62
#define PHASH_FLAG_FAST_MODE
Definition: phash.h:109
uword key
Definition: phash.h:46
unsigned long u64
Definition: types.h:89
u32 * tab
Definition: phash.h:91
u32 b
Definition: phash.h:49
u32 parent_q
Definition: phash.h:78
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:523
static void phash_main_free_working_memory(phash_main_t *pm)
Definition: phash.h:155
int i
static void guess_initial_parameters(phash_main_t *pm)
Definition: phash.c:665
u32 n_perfect_calls
Definition: phash.h:151
static u64 random_u64(u64 *seed)
64-bit random number generator Again, constants courtesy of Donald Knuth.
Definition: random.h:126
u32 * tabh
Definition: phash.h:145
#define vec_bytes(v)
Number of data bytes in vector.
static int phash_tabb_compare(void *a1, void *a2)
Definition: phash.c:588
unsigned char u8
Definition: types.h:56
static uword min_log2(uword x)
Definition: clib.h:138
u32 oldval_q
Definition: phash.h:84
static void init_keys_direct_u32(phash_main_t *pm)
Definition: phash.c:95
#define PHASH_FLAG_MINIMAL
Definition: phash.h:113
#define always_inline
Definition: clib.h:92
clib_error_t * phash_find_perfect_hash(phash_main_t *pm)
Definition: phash.c:822
#define clib_error_return(e, args...)
Definition: error.h:99
static int augment(phash_main_t *pm, u32 b_root, u32 high_water)
Definition: phash.c:497
u32 n_seed_trials
Definition: phash.h:151
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
Definition: vec.h:240
unsigned int u32
Definition: types.h:88
u32 a
Definition: phash.h:49
static u32 scramble_permute(u32 x, u32 nbits)
Definition: phash.c:790
#define v
Definition: acl.c:491
u8 s_bits
Definition: phash.h:89
#define PREDICT_FALSE(x)
Definition: clib.h:105
static int init_tabb(phash_main_t *pm)
Definition: phash.c:351
phash_key_t * keys
Definition: phash.h:120
void(* key_seed2)(void *private, uword key1, uword key2, void *seed)
Definition: phash.h:132
static int perfect(phash_main_t *pm)
Definition: phash.c:602
u32 hash_max
Definition: phash.h:117
u32 flags
Definition: phash.h:97
#define hash_mix64(a0, b0, c0)
Definition: hash.h:531
u32 val_b
Definition: phash.h:59
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:339
u64 hash_seed
Definition: phash.h:95
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
void(* key_seed1)(void *private, uword key, void *seed)
Definition: phash.h:129
u32 * keys
Definition: phash.h:56
static uword clib_bitmap_get(uword *ai, uword i)
Gets the ith bit value from a bitmap.
Definition: bitmap.h:197
#define ASSERT(truth)
static int apply(phash_main_t *pm, u32 tail, u32 rollback)
Definition: phash.c:408
Bitmaps built as vectors of machine words.
#define clib_bitmap_free(v)
Free a bitmap.
Definition: bitmap.h:92
u8 a_bits
Definition: phash.h:89
phash_tabq_t * tabq
Definition: phash.h:148
static uword is_pow2(uword x)
Definition: clib.h:229
u32 b_mask
Definition: phash.h:90
u32 b_q
Definition: phash.h:75
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
#define PHASH_FLAG_MIX64
Definition: phash.h:101
static uword max_log2(uword x)
Definition: clib.h:185
u64 uword
Definition: types.h:112
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:982
static phash_tabb_t * sort_tabb
Definition: phash.c:585
uword phash_hash_slow(phash_main_t *pm, uword key)
Definition: phash.c:924
Linear Congruential Random Number Generator.
int(* key_is_equal)(void *private, uword key1, uword key2)
Definition: phash.h:126
#define vec_foreach(var, vec)
Vector iterator.
static void init_keys_indirect_u64(phash_main_t *pm)
Definition: phash.c:278
u32 * tabb_sort
Definition: phash.h:141
u32 newval_q
Definition: phash.h:81
u8 b_bits
Definition: phash.h:89
static void init_keys_direct_u64(phash_main_t *pm)
Definition: phash.c:152
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment)
Definition: vec.h:486
#define BITS(x)
Definition: clib.h:58
static void scramble_init(phash_main_t *pm)
Definition: phash.c:810
#define PHASH_FLAG_USE_SCRAMBLE
Definition: phash.h:105
phash_tabb_t * tabb
Definition: phash.h:138
static void phash_tabb_free(phash_tabb_t *b)
Definition: phash.h:66
u32 * scramble
Definition: phash.h:92