source: lib/hash_toeplitz.c

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivendag_formatrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file was 6f7cd4b, checked in by Richard Sanger <rsanger@…>, 5 years ago

Makes a couple of modifications to the DPDK RSS hash key patch

  • Ensure CUSTOM_HASHER still returns -1 to libtrace
  • Rework to allow any size of hash
  • Rework to malloc the key I'm not 100% convinced DPDK does not hold on to the reference.
  • Also fixes a bug in the fallback libtrace hasher handling. Which was always sending packets to the same thread.
  • Property mode set to 100644
File size: 6.4 KB
Line 
1/*
2 *
3 * Copyright (c) 2007-2016 The University of Waikato, Hamilton, New Zealand.
4 * All rights reserved.
5 *
6 * This file is part of libtrace.
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 *
11 * libtrace is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * libtrace is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 * GNU Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
23 *
24 *
25 */
26
27
28/**
29 * A implementation of Microsofts RSS standard for hashing.
30 * See http://msdn.microsoft.com/en-us/library/windows/hardware/ff570726%28v=vs.85%29.aspx
31 * and the Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS
32 * white paper.
33 *
34 */
35#include "hash_toeplitz.h"
36#include <string.h>
37#include <stdlib.h>
38#include <time.h>
39#include <stdio.h>
40 
41static inline uint8_t get_bit(uint8_t byte, size_t num) {
42        return byte & (0x80>>num);
43}
44
45/**
46 * Takes a key of length 40 bytes == (320bits)
47 * and expands it into 320 32 bit ints
48 * each shifted left by 1 byte more than the last
49 */
50void toeplitz_hash_expand_key(toeplitz_conf_t *conf) {
51        size_t i = 0, j;
52        // Don't destroy the existing key
53        char *key_cpy = malloc(40);
54        memcpy(key_cpy, conf->key, 40);
55       
56        do {
57                conf->key_cache[i] = *((uint32_t *) key_cpy);
58               
59                for (j = 0; j < 39 ; ++j) {
60                        key_cpy[j] <<= 1;
61                        key_cpy[j] |= (0x80 & key_cpy[j+1])>>7;
62                }
63                key_cpy[39] <<= 1;
64                ++i;
65        } while (i < 320);
66        free(key_cpy);
67}
68
69
70/**
71 * Creates a random unidirectional RSS key - a ip or ip+port combination in
72 * the opposite directions will most likely get different hashes.
73 * @param key An array of bytes to retrieve the RSS key
74 * @param num The number of bytes in key
75 */
76void toeplitz_ncreate_unikey(uint8_t *key, size_t num) {
77        size_t i;
78        unsigned int seed = time(NULL);
79        for (i = 0; i < num; i++) {
80                key[i] = (uint8_t) rand_r(&seed);
81        }
82}
83
84/**
85 * Creates a random 40 byte unidirectional RSS key - a ip or ip+port combination
86 * in the opposite directions will most likely get different hashes.
87 * @param key must have 40 bytes of space to retrieve random the key
88 */
89void toeplitz_create_unikey(uint8_t *key) {
90        toeplitz_ncreate_unikey(key, 40);
91}
92
93/**
94 * Create a bidirectional RSS key, i.e. ip and ip+port configurations
95 * in opposite directions will receive the same hash
96 * @param key must have 40 bytes of space to retrieve random the key
97 * @param num The number of bytes in the key, must be a multiple of 2
98 */
99void toeplitz_ncreate_bikey(uint8_t *key, size_t num) {
100        unsigned int seed = time(NULL);
101        size_t i;
102        if (num % 2 != 0) {
103                perror("Can not create a bidirectional key for an odd length key");
104        }
105        // Every thing is 16bit (port=16, ipv4=32, ipv6=128
106        // aligned so this will make the hash bidirectional
107        uint16_t bi_key = (uint16_t) rand_r(&seed);
108        uint16_t *bi_rep = (uint16_t *) key;
109        for (i = 0; i < num/2; i++) {
110                bi_rep[i] = bi_key;
111        }
112}
113
114/**
115 * Create a 40 byte bidirectional RSS key, i.e. ip and ip+port configurations
116 * in opposite directions will receive the same hash
117 * @param key An array of bytes to retrieve the RSS key
118 */
119void toeplitz_create_bikey(uint8_t *key) {
120        toeplitz_ncreate_bikey(key, 40);
121}
122
123void toeplitz_init_config(toeplitz_conf_t *conf, bool bidirectional)
124{
125        if (bidirectional) {
126                toeplitz_create_bikey(conf->key);
127        } else {
128                toeplitz_create_unikey(conf->key);
129        }
130        toeplitz_hash_expand_key(conf);
131        conf->hash_ipv4 = 1;
132        conf->hash_ipv6 = 1;
133        conf->hash_tcp_ipv4 = 1;
134        conf->x_hash_udp_ipv4 = 1;
135        conf->hash_tcp_ipv6 = 1;
136        conf->x_hash_udp_ipv6 = 1;
137}
138
139/**
140 * n is bits
141 */
142uint32_t toeplitz_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t offset, size_t n, uint32_t result)
143{
144        size_t byte;
145        size_t bit, i = 0;
146        const uint32_t * key_array = tc->key_cache + offset*8;
147        for (byte = 0; byte < n; ++byte) {
148                for (bit = 0; bit < 8; ++bit,++i) {
149                        if (get_bit(data[byte], bit))
150                                result ^= key_array[i];
151                }
152        }
153        return result;
154}
155
156uint32_t toeplitz_first_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t n)
157{
158        return toeplitz_hash(tc, data, 0, n, 0);
159}
160
161uint64_t toeplitz_hash_packet(const libtrace_packet_t * pkt, const toeplitz_conf_t *cnf) {
162        uint8_t proto;
163        uint16_t eth_type;
164        uint32_t remaining;
165        uint32_t res = 0; // shutup warning, logic was to complex for gcc to follow
166        void *layer3 = trace_get_layer3(pkt, &eth_type, &remaining);
167        void *transport = NULL;
168        size_t offset = 0;
169        bool accept_tcp = false, accept_udp = false;
170
171        if (cnf->hash_ipv6_ex || cnf->hash_tcp_ipv6_ex || cnf->x_hash_udp_ipv6_ex)
172        {
173                perror("We don't support ipv6 ex hashing yet\n");
174        }
175
176        if (layer3) {
177                switch (eth_type) {
178                        case TRACE_ETHERTYPE_IP:
179                                // The packet needs to include source and dest which
180                                // are at the very end of the header
181                                if ((cnf->hash_ipv4 || cnf->hash_tcp_ipv4 || cnf->x_hash_udp_ipv4)
182                                                && remaining >= sizeof(libtrace_ip_t)) {       
183                                        libtrace_ip_t * ip = (libtrace_ip_t *)layer3;
184                                        // Order here is src dst as required by RSS
185                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip->ip_src, 8);
186                                        offset = 8;
187                                        accept_tcp = cnf->hash_tcp_ipv4;
188                                        accept_udp = cnf->x_hash_udp_ipv4;
189                                }
190                                break;
191                        case TRACE_ETHERTYPE_IPV6:
192                                // TODO IPv6 EX
193                                if ((cnf->hash_ipv6 || cnf->hash_tcp_ipv6 || cnf->x_hash_udp_ipv6)
194                                                && remaining >= sizeof(libtrace_ip6_t)) {
195                                        libtrace_ip6_t * ip6 = (libtrace_ip6_t *)layer3;
196                                        // Order here is src dst as required by RSS
197                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip6->ip_src, 32);
198                                        offset = 32;
199                                        accept_tcp = cnf->hash_tcp_ipv6;
200                                        accept_udp = cnf->x_hash_udp_ipv6;
201                                }
202                                break;
203                        default:
204                                return 0;
205                }
206        }
207
208        transport = trace_get_transport(pkt, &proto, &remaining);
209
210        if (transport) {
211                switch(proto) {
212                        // Hash src & dst port
213                        case TRACE_IPPROTO_UDP:
214                                if (accept_udp && remaining >= 4) {
215                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
216                                }
217                                break;
218                        case TRACE_IPPROTO_TCP:
219                                if (accept_tcp && remaining >= 4) {
220                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
221                                }
222                                break;
223                }
224        }
225
226        return res;
227}
Note: See TracBrowser for help on using the repository browser.