source: lib/hash_toeplitz.c @ f051c1b

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

Adds more tests

  • Test hashing function is used
  • Test single threaded path works
  • Stress test with 100 threads
  • Test hash+singlethreaded works

Additionally fixes some bugs/compile warnings and removes some verbose debug printing

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