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 | |
---|
13 | static 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 | */ |
---|
22 | void 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 | */ |
---|
47 | void 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 | */ |
---|
60 | void 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 | |
---|
72 | 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 | */ |
---|
85 | 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 | |
---|
99 | 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 | |
---|
104 | 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, ð_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 | } |
---|