aboutsummaryrefslogtreecommitdiffstats
path: root/resources/libraries/python/VppCounters.py
blob: b65b58c89bb15d31ea43225fa457e25d9978aae7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
# Copyright (c) 2016 Cisco and/or its affiliates.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at:
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""VPP counters utilities library."""

import time

from robot.api import logger
from resources.libraries.python.PapiExecutor import PapiExecutor
from resources.libraries.python.topology import NodeType, Topology
from resources.libraries.python.VatExecutor import VatExecutor, VatTerminal


class VppCounters(object):
    """VPP counters utilities."""

    def __init__(self):
        self._stats_table = None

    @staticmethod
    def vpp_show_errors(node):
        """Run "show errors" debug CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script("show_errors.vat", node, json_out=False)
        vat.script_should_have_passed()

    @staticmethod
    def vpp_show_errors_verbose(node):
        """Run "show errors verbose" debug CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script("show_errors_verbose.vat", node, json_out=False)
        vat.script_should_have_passed()

    @staticmethod
    def vpp_show_errors_on_all_duts(nodes, verbose=False):
        """Show errors on all DUTs.

        :param nodes: VPP nodes.
        :param verbose: If True show verbose output.
        :type nodes: dict
        :type verbose: bool
        """

        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                if verbose:
                    VppCounters.vpp_show_errors_verbose(node)
                else:
                    VppCounters.vpp_show_errors(node)

    @staticmethod
    def vpp_show_runtime(node):
        """Run "show runtime" CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script("show_runtime.vat", node, json_out=False)
        logger.info(vat.get_script_stdout())
        vat.script_should_have_passed()

    @staticmethod
    def show_runtime_counters_on_all_duts(nodes):
        """Clear VPP runtime counters on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        """
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.vpp_show_runtime(node)

    @staticmethod
    def vpp_show_runtime_verbose(node):
        """Run "show runtime verbose" CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script("show_runtime_verbose.vat", node, json_out=False)
        logger.info(vat.get_script_stdout())
        vat.script_should_have_passed()

    @staticmethod
    def vpp_show_hardware_detail(node):
        """Run "show hardware-interfaces detail" debug CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script("show_hardware_detail.vat", node, json_out=False)
        vat.script_should_have_passed()

    @staticmethod
    def vpp_clear_runtime(node):
        """Run "clear runtime" CLI command.

        :param node: Node to run command on.
        :type node: dict
        """
        cmd = 'cli_inband'
        cmd_reply = 'cli_inband_reply'
        err_msg = "Failed to run '{cmd}' PAPI command on host {host}!".format(
            host=node['host'], cmd=cmd)
        args = dict(cmd='clear runtime')
        with PapiExecutor(node) as papi_exec:
            papi_resp = papi_exec.add(cmd, **args).execute_should_pass(err_msg)
        data = papi_resp.reply[0]['api_reply'][cmd_reply]
        if data['retval'] != 0:
            raise RuntimeError("Failed to clear runtime on host {host}".
                               format(host=node['host']))

    @staticmethod
    def clear_runtime_counters_on_all_duts(nodes):
        """Run "clear runtime" CLI command on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        """
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.vpp_clear_runtime(node)

    @staticmethod
    def vpp_clear_interface_counters(node):
        """Clear interface counters on VPP node.

        :param node: Node to clear interface counters on.
        :type node: dict
        """
        cmd = 'cli_inband'
        cmd_reply = 'cli_inband_reply'
        err_msg = "Failed to run '{cmd}' PAPI command on host {host}!".format(
            host=node['host'], cmd=cmd)
        args = dict(cmd='clear interfaces')
        with PapiExecutor(node) as papi_exec:
            papi_resp = papi_exec.add(cmd, **args).execute_should_pass(err_msg)
        data = papi_resp.reply[0]['api_reply'][cmd_reply]
        if data['retval'] != 0:
            raise RuntimeError("Failed to clear interfaces on host {host}".
                               format(host=node['host']))

    @staticmethod
    def clear_interface_counters_on_all_duts(nodes):
        """Clear interface counters on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        """
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.vpp_clear_interface_counters(node)

    @staticmethod
    def vpp_clear_hardware_counters(node):
        """Clear interface hardware counters on VPP node.

        :param node: Node to clear hardware counters on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script('clear_hardware.vat', node)
        vat.script_should_have_passed()

    @staticmethod
    def clear_hardware_counters_on_all_duts(nodes):
        """Clear hardware counters on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        """
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.vpp_clear_hardware_counters(node)

    @staticmethod
    def vpp_clear_errors_counters(node):
        """Clear errors counters on VPP node.

        :param node: Node to clear errors counters on.
        :type node: dict
        """
        vat = VatExecutor()
        vat.execute_script('clear_errors.vat', node)
        vat.script_should_have_passed()

    @staticmethod
    def clear_error_counters_on_all_duts(nodes):
        """Clear VPP errors counters on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        """
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.vpp_clear_errors_counters(node)

    def vpp_dump_stats_table(self, node):
        """Dump stats table on VPP node.

        :param node: Node to dump stats table on.
        :type node: dict
        :returns: Stats table.
        """
        with VatTerminal(node) as vat:
            vat.vat_terminal_exec_cmd('want_stats enable')
            for _ in range(0, 12):
                stats_table = vat.vat_terminal_exec_cmd('dump_stats_table')
                if stats_table['interface_counters']:
                    self._stats_table = stats_table
                    return stats_table
                time.sleep(1)
            return None

    def vpp_get_ipv4_interface_counter(self, node, interface):
        """

        :param node: Node to get interface IPv4 counter on.
        :param interface: Interface name.
        :type node: dict
        :type interface: str
        :returns: Interface IPv4 counter.
        :rtype: int
        """
        return self.vpp_get_ipv46_interface_counter(node, interface, False)

    def vpp_get_ipv6_interface_counter(self, node, interface):
        """

        :param node: Node to get interface IPv6 counter on.
        :param interface: Interface name.
        :type node: dict
        :type interface: str
        :returns: Interface IPv6 counter.
        :rtype: int
        """
        return self.vpp_get_ipv46_interface_counter(node, interface, True)

    def vpp_get_ipv46_interface_counter(self, node, interface, is_ipv6=True):
        """Return interface IPv4/IPv6 counter.

        :param node: Node to get interface IPv4/IPv6 counter on.
        :param interface: Interface name.
        :param is_ipv6: Specify IP version.
        :type node: dict
        :type interface: str
        :type is_ipv6: bool
        :returns: Interface IPv4/IPv6 counter.
        :rtype: int
        """
        version = 'ip6' if is_ipv6 else 'ip4'
        topo = Topology()
        if_index = topo.get_interface_sw_index(node, interface)
        if if_index is None:
            logger.trace('{i} sw_index not found.'.format(i=interface))
            return 0

        if_counters = self._stats_table.get('interface_counters')
        if not if_counters:
            logger.trace('No interface counters.')
            return 0
        for counter in if_counters:
            if counter['vnet_counter_type'] == version:
                data = counter['data']
                return data[if_index]
        logger.trace('{i} {v} counter not found.'.format(
            i=interface, v=version))
        return 0

    @staticmethod
    def show_vpp_statistics(node):
        """Show [error, hardware, interface] stats.

        :param node: VPP node.
        :type node: dict
        """
        VppCounters.vpp_show_errors(node)
        VppCounters.vpp_show_hardware_detail(node)
        VppCounters.vpp_show_runtime(node)

    @staticmethod
    def show_statistics_on_all_duts(nodes, sleeptime=5):
        """Show VPP statistics on all DUTs.

        :param nodes: VPP nodes.
        :type nodes: dict
        :param sleeptime: Time to wait for traffic to arrive back to TG.
        :type sleeptime: int
        """
        logger.trace('Waiting for statistics to be collected')
        time.sleep(sleeptime)
        for node in nodes.values():
            if node['type'] == NodeType.DUT:
                VppCounters.show_vpp_statistics(node)
n> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = k[1].a = 0; k += 2; n_keys_left -= 2; } if (n_keys_left >= 1) { u64 x0, y0, z0; x0 = y0 = z0 = seed; x0 += k[0].key; hash_mix64 (x0, y0, z0); k[0].b = z0 & b_mask; k[0].a = z0 >> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = 0; k += 1; n_keys_left -= 1; } } static void init_keys_indirect_u32 (phash_main_t * pm) { int n_keys_left, b_mask, a_shift; u32 seed; phash_key_t *k; seed = pm->hash_seed; b_mask = (1 << pm->b_bits) - 1; a_shift = BITS (seed) - pm->a_bits; k = pm->keys; n_keys_left = vec_len (pm->keys); while (n_keys_left >= 2) { u32 xyz[6]; u32 x0, y0, z0; u32 x1, y1, z1; pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz); x0 = y0 = z0 = seed; x1 = y1 = z1 = seed; x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; x1 += xyz[3]; y1 += xyz[4]; z1 += xyz[5]; hash_mix32 (x0, y0, z0); hash_mix32 (x1, y1, z1); k[0].b = z0 & b_mask; k[1].b = z1 & b_mask; k[0].a = z0 >> a_shift; k[1].a = z1 >> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = k[1].a = 0; k += 2; n_keys_left -= 2; } if (n_keys_left >= 1) { u32 xyz[3]; u32 x0, y0, z0; pm->key_seed1 (pm->private, k[0].key, &xyz); x0 = y0 = z0 = seed; x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; hash_mix32 (x0, y0, z0); k[0].b = z0 & b_mask; k[0].a = z0 >> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = 0; k += 1; n_keys_left -= 1; } } static void init_keys_indirect_u64 (phash_main_t * pm) { int n_keys_left, b_mask, a_shift; u64 seed; phash_key_t *k; seed = pm->hash_seed; b_mask = (1 << pm->b_bits) - 1; a_shift = BITS (seed) - pm->a_bits; k = pm->keys; n_keys_left = vec_len (pm->keys); while (n_keys_left >= 2) { u64 xyz[6]; u64 x0, y0, z0; u64 x1, y1, z1; pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz); x0 = y0 = z0 = seed; x1 = y1 = z1 = seed; x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; x1 += xyz[3]; y1 += xyz[4]; z1 += xyz[5]; hash_mix64 (x0, y0, z0); hash_mix64 (x1, y1, z1); k[0].b = z0 & b_mask; k[1].b = z1 & b_mask; k[0].a = z0 >> a_shift; k[1].a = z1 >> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = k[1].a = 0; k += 2; n_keys_left -= 2; } if (n_keys_left >= 1) { u64 xyz[3]; u64 x0, y0, z0; pm->key_seed1 (pm->private, k[0].key, &xyz); x0 = y0 = z0 = seed; x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; hash_mix64 (x0, y0, z0); k[0].b = z0 & b_mask; k[0].a = z0 >> a_shift; if (PREDICT_FALSE (a_shift >= BITS (z0))) k[0].a = 0; k += 1; n_keys_left -= 1; } } /* * insert keys into table according to key->b * check if the initial hash might work */ static int init_tabb (phash_main_t * pm) { int no_collisions; phash_tabb_t *tb; phash_key_t *k, *l; if (pm->key_seed1) { if (pm->flags & PHASH_FLAG_MIX64) init_keys_indirect_u64 (pm); else init_keys_indirect_u32 (pm); } else { if (pm->flags & PHASH_FLAG_MIX64) init_keys_direct_u64 (pm); else init_keys_direct_u32 (pm); } if (!pm->tabb) vec_resize (pm->tabb, 1 << pm->b_bits); else vec_foreach (tb, pm->tabb) phash_tabb_free (tb); /* Two keys with the same (a,b) guarantees a collision */ no_collisions = 1; vec_foreach (k, pm->keys) { u32 i, *ki; tb = pm->tabb + k->b; ki = tb->keys; for (i = 0; i < vec_len (ki); i++) { l = pm->keys + ki[i]; if (k->a == l->a) { /* Given keys are supposed to be unique. */ if (pm->key_is_equal && pm->key_is_equal (pm->private, l->key, k->key)) clib_error ("duplicate keys"); no_collisions = 0; goto done; } } vec_add1 (tb->keys, k - pm->keys); } done: return no_collisions; } /* Try to apply an augmenting list */ static int apply (phash_main_t * pm, u32 tail, u32 rollback) { phash_key_t *k; phash_tabb_t *pb; phash_tabq_t *q_child, *q_parent; u32 ki, i, hash, child, parent; u32 stabb; /* scramble[tab[b]] */ int no_collision; no_collision = 1; /* Walk from child to parent until root is reached. */ for (child = tail - 1; child; child = parent) { q_child = &pm->tabq[child]; parent = q_child->parent_q; q_parent = &pm->tabq[parent]; /* find parent's list of siblings */ ASSERT (q_parent->b_q < vec_len (pm->tabb)); pb = pm->tabb + q_parent->b_q; /* erase old hash values */ stabb = pm->scramble[pb->val_b]; for (i = 0; i < vec_len (pb->keys); i++) { ki = pb->keys[i]; k = pm->keys + ki; hash = k->a ^ stabb; /* Erase hash for all of child's siblings. */ if (ki == pm->tabh[hash]) pm->tabh[hash] = ~0; } /* change pb->val_b, which will change the hashes of all parent siblings */ pb->val_b = rollback ? q_child->oldval_q : q_child->newval_q; /* set new hash values */ stabb = pm->scramble[pb->val_b]; for (i = 0; i < vec_len (pb->keys); i++) { ki = pb->keys[i]; k = pm->keys + ki; hash = k->a ^ stabb; if (rollback) { if (parent == 0) continue; /* root never had a hash */ } else if (pm->tabh[hash] != ~0) { /* Very rare case: roll back any changes. */ apply (pm, tail, /* rollback changes */ 1); no_collision = 0; goto done; } pm->tabh[hash] = ki; } } done: return no_collision; } /* ------------------------------------------------------------------------------- augment(): Add item to the mapping. Construct a spanning tree of *b*s with *item* as root, where each parent can have all its hashes changed (by some new val_b) with at most one collision, and each child is the b of that collision. I got this from Tarjan's "Data Structures and Network Algorithms". The path from *item* to a *b* that can be remapped with no collision is an "augmenting path". Change values of tab[b] along the path so that the unmapped key gets mapped and the unused hash value gets used. Assuming 1 key per b, if m out of n hash values are still unused, you should expect the transitive closure to cover n/m nodes before an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect this approach to take about nlogn time to map all single-key b's. ------------------------------------------------------------------------------- high_water: a value higher than any now in tabb[].water_b. */ static int augment (phash_main_t * pm, u32 b_root, u32 high_water) { u32 q; /* current position walking through the queue */ u32 tail; /* tail of the queue. 0 is the head of the queue. */ phash_tabb_t *tb_parent, *tb_child, *tb_hit; phash_key_t *k_parent, *k_child; u32 v, v_limit; /* possible value for myb->val_b */ u32 i, ki, hash; v_limit = 1 << ((pm->flags & PHASH_FLAG_USE_SCRAMBLE) ? pm->s_bits : BITS (u8)); /* Initialize the root of the spanning tree. */ pm->tabq[0].b_q = b_root; tail = 1; /* construct the spanning tree by walking the queue, add children to tail */ for (q = 0; q < tail; q++) { if ((pm->flags & PHASH_FLAG_FAST_MODE) && !(pm->flags & PHASH_FLAG_MINIMAL) && q == 1) break; /* don't do transitive closure */ tb_parent = pm->tabb + pm->tabq[q].b_q; /* the b for this node */ for (v = 0; v < v_limit; v++) { tb_child = 0; for (i = 0; i < vec_len (tb_parent->keys); i++) { ki = tb_parent->keys[i]; k_parent = pm->keys + ki; hash = k_parent->a ^ pm->scramble[v]; if (hash >= pm->hash_max) goto try_next_v; /* hash code out of bounds => we can't use this v */ ki = pm->tabh[hash]; if (ki == ~0) continue; k_child = pm->keys + ki; tb_hit = pm->tabb + k_child->b; if (tb_child) { /* Hit at most one child b. */ if (tb_child == tb_hit) goto try_next_v; } else { /* Remember this as child b. */ tb_child = tb_hit; if (tb_hit->water_b == high_water) goto try_next_v; /* already explored */ } } /* tb_parent with v has either one or zero collisions. */ /* add child b to the queue of reachable things */ if (tb_child) tb_child->water_b = high_water; pm->tabq[tail].b_q = tb_child ? tb_child - pm->tabb : ~0; pm->tabq[tail].newval_q = v; /* how to make parent (myb) use this hash */ pm->tabq[tail].oldval_q = tb_parent->val_b; /* need this for rollback */ pm->tabq[tail].parent_q = q; ++tail; /* Found a v with no collisions? */ if (!tb_child) { /* Try to apply the augmenting path. */ if (apply (pm, tail, /* rollback */ 0)) return 1; /* success, item was added to the perfect hash */ --tail; /* don't know how to handle such a child! */ } try_next_v: ; } } return 0; } static phash_tabb_t *sort_tabb; static int phash_tabb_compare (void *a1, void *a2) { u32 *b1 = a1; u32 *b2 = a2; phash_tabb_t *tb1, *tb2; tb1 = sort_tabb + b1[0]; tb2 = sort_tabb + b2[0]; return ((int) vec_len (tb2->keys) - (int) vec_len (tb1->keys)); } /* find a mapping that makes this a perfect hash */ static int perfect (phash_main_t * pm) { u32 i; /* clear any state from previous attempts */ if (vec_bytes (pm->tabh)) clib_memset (pm->tabh, ~0, vec_bytes (pm->tabh)); vec_validate (pm->tabb_sort, vec_len (pm->tabb) - 1); for (i = 0; i < vec_len (pm->tabb_sort); i++) pm->tabb_sort[i] = i; sort_tabb = pm->tabb; vec_sort_with_function (pm->tabb_sort, phash_tabb_compare); /* In descending order by number of keys, map all *b*s */ for (i = 0; i < vec_len (pm->tabb_sort); i++) { if (!augment (pm, pm->tabb_sort[i], i + 1)) return 0; } /* Success! We found a perfect hash of all keys into 0..nkeys-1. */ return 1; } /* * Find initial a_bits = log2 (a_max), b_bits = log2 (b_max). * Initial a_max and b_max values were found empirically. Some factors: * * If s_max<256 there is no scramble, so tab[b] needs to cover 0..s_max-1. * * a_max and b_max must be powers of 2 because the values in 0..a_max-1 and * 0..b_max-1 are produced by applying a bitmask to the initial hash function. * * a_max must be less than s_max, in fact less than n_keys, because otherwise * there would often be no i such that a^scramble[i] is in 0..n_keys-1 for * all the *a*s associated with a given *b*, so there would be no legal * value to assign to tab[b]. This only matters when we're doing a minimal * perfect hash. * * It takes around 800 trials to find distinct (a,b) with nkey=s_max*(5/8) * and a_max*b_max = s_max*s_max/32. * * Values of b_max less than s_max/4 never work, and s_max/2 always works. * * We want b_max as small as possible because it is the number of bytes in * the huge array we must create for the perfect hash. * * When nkey <= s_max*(5/8), b_max=s_max/4 works much more often with * a_max=s_max/8 than with a_max=s_max/4. Above s_max*(5/8), b_max=s_max/4 * doesn't seem to care whether a_max=s_max/8 or a_max=s_max/4. I think it * has something to do with 5/8 = 1/8 * 5. For example examine 80000, * 85000, and 90000 keys with different values of a_max. This only matters * if we're doing a minimal perfect hash. * * When a_max*b_max <= 1<<U32BITS, the initial hash must produce one integer. * Bigger than that it must produce two integers, which increases the * cost of the hash per character hashed. */ static void guess_initial_parameters (phash_main_t * pm) { u32 s_bits, s_max, a_max, b_max, n_keys; int is_minimal, is_fast_mode; const u32 b_max_use_scramble_threshold = 4096; is_minimal = (pm->flags & PHASH_FLAG_MINIMAL) != 0; is_fast_mode = (pm->flags & PHASH_FLAG_FAST_MODE) != 0; n_keys = vec_len (pm->keys); s_bits = max_log2 (n_keys); s_max = 1 << s_bits; a_max = 0; if (is_minimal) { switch (s_bits) { case 0: a_max = 1; b_max = 1; case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: /* * Was: a_max = is_minimal ? s_max / 2 : s_max; * However, we know that is_minimal must be true, so the * if-arm of the ternary expression is always executed. */ a_max = s_max / 2; b_max = s_max / 2; break; case 9: case 10: case 11: case 12: case 13: case 14: case 15: case 16: case 17: if (is_fast_mode) { a_max = s_max / 2; b_max = s_max / 4; } else if (s_max / 4 < b_max_use_scramble_threshold) { if (n_keys <= s_max * 0.52) a_max = b_max = s_max / 8; else a_max = b_max = s_max / 4; } else { a_max = ((n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : (n_keys <= s_max * (3.0 / 4.0)) ? s_max / 4 : s_max / 2); b_max = s_max / 4; /* always give the small size a shot */ } break; case 18: if (is_fast_mode) a_max = b_max = s_max / 2; else { a_max = s_max / 8; /* never require the multiword hash */ b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2; } break; case 19: case 20: a_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : s_max / 2; b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2; break; default: /* Just find a hash as quick as possible. We'll be thrashing virtual memory at this size. */ a_max = b_max = s_max / 2; break; } } else { /* Non-minimal perfect hash. */ if (is_fast_mode && n_keys > s_max * 0.8) { s_max *= 2; s_bits += 1; } if (s_max / 4 <= (1 << 14)) b_max = ((n_keys <= s_max * 0.56) ? s_max / 32 : (n_keys <= s_max * 0.74) ? s_max / 16 : s_max / 8); else b_max = ((n_keys <= s_max * 0.6) ? s_max / 16 : (n_keys <= s_max * 0.8) ? s_max / 8 : s_max / 4); if (is_fast_mode && b_max < s_max / 8) b_max = s_max / 8; if (a_max < 1) a_max = 1; if (b_max < 1) b_max = 1; } ASSERT (s_max == (1 << s_bits)); ASSERT (is_pow2 (a_max)); ASSERT (is_pow2 (b_max)); pm->s_bits = s_bits; pm->a_bits = min_log2 (a_max); pm->b_bits = min_log2 (b_max); if (b_max >= b_max_use_scramble_threshold) pm->flags |= PHASH_FLAG_USE_SCRAMBLE; } /* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */ /* permute(0)=0. This is intended and useful. */ always_inline u32 scramble_permute (u32 x, u32 nbits) { int i; int mask = (1 << nbits) - 1; int const2 = 1 + nbits / 2; int const3 = 1 + nbits / 3; int const4 = 1 + nbits / 4; int const5 = 1 + nbits / 5; for (i = 0; i < 20; i++) { x = (x + (x << const2)) & mask; x = (x ^ (x >> const3)); x = (x + (x << const4)) & mask; x = (x ^ (x >> const5)); } return x; } /* initialize scramble[] with distinct random values in 0..smax-1 */ static void scramble_init (phash_main_t * pm) { u32 i; /* fill scramble[] with distinct random integers in 0..smax-1 */ vec_validate (pm->scramble, (1 << (pm->s_bits < 8 ? 8 : pm->s_bits)) - 1); for (i = 0; i < vec_len (pm->scramble); i++) pm->scramble[i] = scramble_permute (i, pm->s_bits); } /* Try to find a perfect hash function. */ clib_error_t * phash_find_perfect_hash (phash_main_t * pm) { clib_error_t *error = 0; u32 max_a_bits, n_tries_this_a_b, want_minimal; /* guess initial values for s_max, a_max and b_max */ guess_initial_parameters (pm); want_minimal = pm->flags & PHASH_FLAG_MINIMAL; new_s: if (pm->b_bits == 0) pm->a_bits = pm->s_bits; max_a_bits = pm->s_bits - want_minimal; if (max_a_bits < 1) max_a_bits = 1; pm->hash_max = want_minimal ? vec_len (pm->keys) : (1 << pm->s_bits); scramble_init (pm); /* Allocate working memory. */ vec_free (pm->tabh); vec_validate_init_empty (pm->tabh, pm->hash_max - 1, ~0); vec_free (pm->tabq); vec_validate (pm->tabq, 1 << pm->b_bits); /* Actually find the perfect hash */ n_tries_this_a_b = 0; while (1) { /* Choose random hash seeds until keys become unique. */ pm->hash_seed = random_u64 (&pm->random_seed); pm->n_seed_trials++; if (init_tabb (pm)) { /* Found unique (A, B). */ /* Hash may already be perfect. */ if (pm->b_bits == 0) goto done; pm->n_perfect_calls++; if (perfect (pm)) goto done; goto increase_b; } /* Keep trying with different seed value. */ n_tries_this_a_b++; if (n_tries_this_a_b < 2048) continue; /* Try to put more bits in (A,B) to make distinct (A,B) more likely */ if (pm->a_bits < max_a_bits) pm->a_bits++; else if (pm->b_bits < pm->s_bits) { increase_b: vec_resize (pm->tabb, vec_len (pm->tabb)); vec_resize (pm->tabq, vec_len (pm->tabq)); pm->b_bits++; } else { /* Can't increase (A, B) any more, so try increasing S. */ goto new_s; } } done: /* Construct mapping table for hash lookups. */ if (!error) { u32 b, v; pm->a_shift = ((pm->flags & PHASH_FLAG_MIX64) ? 64 : 32) - pm->a_bits; pm->b_mask = (1 << pm->b_bits) - 1; vec_resize (pm->tab, vec_len (pm->tabb)); for (b = 0; b < vec_len (pm->tabb); b++) { v = pm->tabb[b].val_b; /* Apply scramble now for small enough value of b_bits. */ if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE)) v = pm->scramble[v]; pm->tab[b] = v; } } /* Free working memory. */ phash_main_free_working_memory (pm); return error; } /* Slow hash computation for general keys. */ uword phash_hash_slow (phash_main_t * pm, uword key) { u32 a, b, v; if (pm->flags & PHASH_FLAG_MIX64) { u64 x0, y0, z0; x0 = y0 = z0 = pm->hash_seed; if (pm->key_seed1) { u64 xyz[3]; pm->key_seed1 (pm->private, key, &xyz); x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; } else x0 += key; hash_mix64 (x0, y0, z0); a = z0 >> pm->a_shift; b = z0 & pm->b_mask; } else { u32 x0, y0, z0; x0 = y0 = z0 = pm->hash_seed; if (pm->key_seed1) { u32 xyz[3]; pm->key_seed1 (pm->private, key, &xyz); x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2]; } else x0 += key; hash_mix32 (x0, y0, z0); a = z0 >> pm->a_shift; b = z0 & pm->b_mask; } v = pm->tab[b]; if (pm->flags & PHASH_FLAG_USE_SCRAMBLE) v = pm->scramble[v]; return a ^ v; } /* Verify that perfect hash is perfect. */ clib_error_t * phash_validate (phash_main_t * pm) { phash_key_t *k; uword *unique_bitmap = 0; clib_error_t *error = 0; vec_foreach (k, pm->keys) { uword h = phash_hash_slow (pm, k->key); if (h >= pm->hash_max) { error = clib_error_return (0, "hash out of range %wd", h); goto done; } if (clib_bitmap_get (unique_bitmap, h)) { error = clib_error_return (0, "hash non-unique"); goto done; } unique_bitmap = clib_bitmap_ori (unique_bitmap, h); } done: clib_bitmap_free (unique_bitmap); return error; } /* * fd.io coding-style-patch-verification: ON * * Local Variables: * eval: (c-set-style "gnu") * End: */