source: lib/hash_toeplitz.c @ 89e2ff7

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivendag_formatrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 89e2ff7 was ee6e802, checked in by Shane Alcock <salcock@…>, 4 years ago

Updated copyright blurb on all source files

In some cases, this meant adding copyright blurbs to files that
had never had them before.

  • Property mode set to 100644
File size: 5.5 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 must have 40 bytes of space to retrieve random the key
74 */ 
75void toeplitz_create_unikey(uint8_t *key) {
76        int i;
77        unsigned int seed = time(NULL);
78        for (i = 0; i < 40; i++) {
79                key[i] = (uint8_t) rand_r(&seed);
80        }
81}
82
83/**
84 * Create a bidirectional RSS key, i.e. ip and ip+port configurations
85 * in opposite directions will receive the same hash
86 * @param key must have 40 bytes of space to retrieve random the key
87 */
88void toeplitz_create_bikey(uint8_t *key) {
89        unsigned int seed = time(NULL);
90        int i;
91        // Every thing is 16bit (port=16, ipv4=32, ipv6=128
92        // aligned so this will make the hash bidirectional
93        uint16_t bi_key = (uint16_t) rand_r(&seed);
94        uint16_t *bi_rep = (uint16_t *) key;
95        for (i = 0; i < 20; i++) {
96                bi_rep[i] = bi_key;
97        }
98}
99
100void toeplitz_init_config(toeplitz_conf_t *conf, bool bidirectional)
101{
102        if (bidirectional) {
103                toeplitz_create_bikey(conf->key);
104        } else {
105                toeplitz_create_unikey(conf->key);
106        }
107        toeplitz_hash_expand_key(conf);
108}
109
110/**
111 * n is bits
112 */
113uint32_t toeplitz_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t offset, size_t n, uint32_t result)
114{
115        size_t byte;
116        size_t bit, i = 0;
117        const uint32_t * key_array = tc->key_cache + offset*8;
118        for (byte = 0; byte < n; ++byte) {
119                for (bit = 0; bit < 8; ++bit,++i) {
120                        if (get_bit(data[byte], bit))
121                                result ^= key_array[i];
122                }
123        }
124        return result;
125}
126
127uint32_t toeplitz_first_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t n)
128{
129        return toeplitz_hash(tc, data, 0, n, 0);
130}
131
132uint64_t toeplitz_hash_packet(const libtrace_packet_t * pkt, const toeplitz_conf_t *cnf) {
133        uint8_t proto;
134        uint16_t eth_type;
135        uint32_t remaining;
136        uint32_t res = 0; // shutup warning, logic was to complex for gcc to follow
137        void *layer3 = trace_get_layer3(pkt, &eth_type, &remaining);
138        void *transport = NULL;
139        size_t offset = 0;
140        bool accept_tcp = false, accept_udp = false;
141
142        if (cnf->hash_ipv6_ex || cnf->hash_tcp_ipv6_ex || cnf->x_hash_udp_ipv6_ex)
143        {
144                perror("We don't support ipv6 ex hashing yet\n");
145        }
146
147        if (layer3) {
148                switch (eth_type) {
149                        case TRACE_ETHERTYPE_IP:
150                                // The packet needs to include source and dest which
151                                // are at the very end of the header
152                                if ((cnf->hash_ipv4 || cnf->hash_tcp_ipv4 || cnf->x_hash_udp_ipv4)
153                                                && remaining >= sizeof(libtrace_ip_t)) {       
154                                        libtrace_ip_t * ip = (libtrace_ip_t *)layer3;
155                                        // Order here is src dst as required by RSS
156                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip->ip_src, 8);
157                                        offset = 8;
158                                        accept_tcp = cnf->hash_tcp_ipv4;
159                                        accept_udp = cnf->x_hash_udp_ipv4;
160                                }
161                                break;
162                        case TRACE_ETHERTYPE_IPV6:
163                                // TODO IPv6 EX
164                                if ((cnf->hash_ipv6 || cnf->hash_tcp_ipv6 || cnf->x_hash_udp_ipv6)
165                                                && remaining >= sizeof(libtrace_ip6_t)) {
166                                        libtrace_ip6_t * ip6 = (libtrace_ip6_t *)layer3;
167                                        // Order here is src dst as required by RSS
168                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip6->ip_src, 32);
169                                        offset = 32;
170                                        accept_tcp = cnf->hash_tcp_ipv6;
171                                        accept_udp = cnf->x_hash_udp_ipv6;
172                                }
173                                break;
174                        default:
175                                return 0;
176                }
177        }
178
179        transport = trace_get_transport(pkt, &proto, &remaining);
180
181        if (transport) {
182                switch(proto) {
183                        // Hash src & dst port
184                        case TRACE_IPPROTO_UDP:
185                                if (accept_udp && remaining >= 4) {
186                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
187                                }
188                                break;
189                        case TRACE_IPPROTO_TCP:
190                                if (accept_tcp && remaining >= 4) {
191                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
192                                }
193                                break;
194                }
195        }
196
197        return res;
198}
Note: See TracBrowser for help on using the repository browser.