source: lib/hash_toeplitz.c @ 8c42377

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivelibtrace4ndag_formatpfringrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 8c42377 was 8c42377, checked in by Richard Sanger <rsangerarj@…>, 7 years ago

Fix some BSD warnings/errors

  • Property mode set to 100644
File size: 4.6 KB
Line 
1/**
2 * A implementation of Microsofts RSS standard for hashing.
3 * See http://msdn.microsoft.com/en-us/library/windows/hardware/ff570726%28v=vs.85%29.aspx
4 * and the Scalable Networking: Eliminating the Receive Processing Bottleneck—Introducing RSS
5 * white paper.
6 *
7 */
8#include "hash_toeplitz.h"
9#include <string.h>
10#include <stdlib.h>
11#include <time.h>
12
13static inline uint8_t get_bit(uint8_t byte, size_t num) {
14        return byte & (0x80>>num);
15}
16
17/**
18 * Takes a key of length 40 bytes == (320bits)
19 * and expands it into 320 32 bit ints
20 * each shifted left by 1 byte more than the last
21 */
22void toeplitz_hash_expand_key(toeplitz_conf_t *conf) {
23        size_t i = 0, j;
24        // Don't destroy the existing key
25        char *key_cpy = malloc(40);
26        memcpy(key_cpy, conf->key, 40);
27       
28        do {
29                conf->key_cache[i] = *((uint32_t *) key_cpy);
30               
31                for (j = 0; j < 39 ; ++j) {
32                        key_cpy[j] <<= 1;
33                        key_cpy[j] |= (0x80 & key_cpy[j+1])>>7;
34                }
35                key_cpy[39] <<= 1;
36                ++i;
37        } while (i < 320);
38        free(key_cpy);
39}
40
41
42/**
43 * Creates a random unidirectional RSS key - a ip or ip+port combination in
44 * the opposite directions will most likely get different hashes.
45 * @param key must have 40 bytes of space to retrieve random the key
46 */ 
47void toeplitz_create_unikey(uint8_t *key) {
48        int i;
49        unsigned int seed = time(NULL);
50        for (i = 0; i < 40; i++) {
51                key[i] = (uint8_t) rand_r(&seed);
52        }
53}
54
55/**
56 * Create a bidirectional RSS key, i.e. ip and ip+port configurations
57 * in opposite directions will receive the same hash
58 * @param key must have 40 bytes of space to retrieve random the key
59 */
60void toeplitz_create_bikey(uint8_t *key) {
61        unsigned int seed = time(NULL);
62        int i;
63        // Every thing is 16bit (port=16, ipv4=32, ipv6=128
64        // aligned so this will make the hash bidirectional
65        uint16_t bi_key = (uint16_t) rand_r(&seed);
66        uint16_t *bi_rep = (uint16_t *) key;
67        for (i = 0; i < 20; i++) {
68                bi_rep[i] = bi_key;
69        }
70}
71
72inline void toeplitz_init_config(toeplitz_conf_t *conf, bool bidirectional)
73{
74        if (bidirectional) {
75                toeplitz_create_bikey(conf->key);
76        } else {
77                toeplitz_create_unikey(conf->key);
78        }
79        toeplitz_hash_expand_key(conf);
80}
81
82/**
83 * n is bits
84 */
85inline uint32_t toeplitz_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t offset, size_t n, uint32_t result)
86{
87        size_t byte;
88        size_t bit, i = 0;
89        const uint32_t * key_array = tc->key_cache + offset*8;
90        for (byte = 0; byte < n; ++byte) {
91                for (bit = 0; bit < 8; ++bit,++i) {
92                        if (get_bit(data[byte], bit))
93                                result ^= key_array[i];
94                }
95        }
96        return result;
97}
98
99inline uint32_t toeplitz_first_hash(const toeplitz_conf_t *tc, const uint8_t *data, size_t n)
100{
101        return toeplitz_hash(tc, data, 0, n, 0);
102}
103
104inline uint64_t toeplitz_hash_packet(const libtrace_packet_t * pkt, const toeplitz_conf_t *cnf) {
105        uint8_t proto;
106        uint16_t eth_type;
107        uint32_t remaining;
108        uint32_t res = 0; // shutup warning, logic was to complex for gcc to follow
109        void *layer3 = trace_get_layer3(pkt, &eth_type, &remaining);
110        void *transport = NULL;
111        size_t offset = 0;
112        bool accept_tcp = false, accept_udp = false;
113
114        if (cnf->hash_ipv6_ex || cnf->hash_tcp_ipv6_ex || cnf->x_hash_udp_ipv6_ex)
115        {
116                perror("We don't support ipv6 ex hashing yet\n");
117        }
118
119        if (layer3) {
120                switch (eth_type) {
121                        case TRACE_ETHERTYPE_IP:
122                                // The packet needs to include source and dest which
123                                // are at the very end of the header
124                                if ((cnf->hash_ipv4 || cnf->hash_tcp_ipv4 || cnf->x_hash_udp_ipv4)
125                                                && remaining >= sizeof(libtrace_ip_t)) {       
126                                        libtrace_ip_t * ip = (libtrace_ip_t *)layer3;
127                                        // Order here is src dst as required by RSS
128                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip->ip_src, 8);
129                                        offset = 8;
130                                        accept_tcp = cnf->hash_tcp_ipv4;
131                                        accept_udp = cnf->x_hash_udp_ipv4;
132                                }
133                                break;
134                        case TRACE_ETHERTYPE_IPV6:
135                                // TODO IPv6 EX
136                                if ((cnf->hash_ipv6 || cnf->hash_tcp_ipv6 || cnf->x_hash_udp_ipv6)
137                                                && remaining >= sizeof(libtrace_ip6_t)) {
138                                        libtrace_ip6_t * ip6 = (libtrace_ip6_t *)layer3;
139                                        // Order here is src dst as required by RSS
140                                        res = toeplitz_first_hash(cnf, (uint8_t *)&ip6->ip_src, 32);
141                                        offset = 32;
142                                        accept_tcp = cnf->hash_tcp_ipv6;
143                                        accept_udp = cnf->x_hash_udp_ipv6;
144                                }
145                                break;
146                        default:
147                                return 0;
148                }
149        }
150
151        transport = trace_get_transport(pkt, &proto, &remaining);
152
153        if (transport) {
154                switch(proto) {
155                        // Hash src & dst port
156                        case TRACE_IPPROTO_UDP:
157                                if (accept_udp && remaining >= 4) {
158                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
159                                }
160                                break;
161                        case TRACE_IPPROTO_TCP:
162                                if (accept_tcp && remaining >= 4) {
163                                        res = toeplitz_hash(cnf, (uint8_t *)transport, offset, 4, res);
164                                }
165                                break;
166                }
167        }
168
169        return res;
170}
Note: See TracBrowser for help on using the repository browser.