1 /* 2 ** Copyright (c) 2015, Asim Jamshed, Robin Sommer, Seth Hall 3 ** and the International Computer Science Institute. All rights reserved. 4 ** 5 ** Redistribution and use in source and binary forms, with or without 6 ** modification, are permitted provided that the following conditions are met: 7 ** 8 ** (1) Redistributions of source code must retain the above copyright 9 ** notice, this list of conditions and the following disclaimer. 10 ** 11 ** (2) Redistributions in binary form must reproduce the above copyright 12 ** notice, this list of conditions and the following disclaimer in the 13 ** documentation and/or other materials provided with the distribution. 14 ** 15 ** 16 ** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 ** AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 ** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 ** ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 ** LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 ** CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 ** SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 ** INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 ** CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 ** ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 ** POSSIBILITY OF SUCH DAMAGE. 27 **/ 28 /* $FreeBSD$ */ 29 /* for func prototypes */ 30 #include "pkt_hash.h" 31 32 /* Make Linux headers choose BSD versions of some of the data structures */ 33 #define __FAVOR_BSD 34 35 /* for types */ 36 #include <sys/types.h> 37 /* for [n/h]to[h/n][ls] */ 38 #include <netinet/in.h> 39 /* iphdr */ 40 #include <netinet/ip.h> 41 /* ipv6hdr */ 42 #include <netinet/ip6.h> 43 /* tcphdr */ 44 #include <netinet/tcp.h> 45 /* udphdr */ 46 #include <netinet/udp.h> 47 /* eth hdr */ 48 #include <net/ethernet.h> 49 /* for memset */ 50 #include <string.h> 51 52 #include <stdio.h> 53 #include <assert.h> 54 55 //#include <libnet.h> 56 /*---------------------------------------------------------------------*/ 57 /** 58 * * The cache table is used to pick a nice seed for the hash value. It is 59 * * built only once when sym_hash_fn is called for the very first time 60 * */ 61 static void 62 build_sym_key_cache(uint32_t *cache, int cache_len) 63 { 64 static const uint8_t key[] = { 0x50, 0x6d }; 65 66 uint32_t result = (((uint32_t)key[0]) << 24) | 67 (((uint32_t)key[1]) << 16) | 68 (((uint32_t)key[0]) << 8) | 69 ((uint32_t)key[1]); 70 71 uint32_t idx = 32; 72 int i; 73 74 for (i = 0; i < cache_len; i++, idx++) { 75 uint8_t shift = (idx % 8); 76 uint32_t bit; 77 78 cache[i] = result; 79 bit = ((key[(idx/8) & 1] << shift) & 0x80) ? 1 : 0; 80 result = ((result << 1) | bit); 81 } 82 } 83 84 static void 85 build_byte_cache(uint32_t byte_cache[256][4]) 86 { 87 #define KEY_CACHE_LEN 96 88 int i, j, k; 89 uint32_t key_cache[KEY_CACHE_LEN]; 90 91 build_sym_key_cache(key_cache, KEY_CACHE_LEN); 92 93 for (i = 0; i < 4; i++) { 94 for (j = 0; j < 256; j++) { 95 uint8_t b = j; 96 byte_cache[j][i] = 0; 97 for (k = 0; k < 8; k++) { 98 if (b & 0x80) 99 byte_cache[j][i] ^= key_cache[8 * i + k]; 100 b <<= 1U; 101 } 102 } 103 } 104 } 105 106 107 /*---------------------------------------------------------------------*/ 108 /** 109 ** Computes symmetric hash based on the 4-tuple header data 110 **/ 111 static uint32_t 112 sym_hash_fn(uint32_t sip, uint32_t dip, uint16_t sp, uint32_t dp) 113 { 114 uint32_t rc = 0; 115 static int first_time = 1; 116 static uint32_t byte_cache[256][4]; 117 uint8_t *sip_b = (uint8_t *)&sip, 118 *dip_b = (uint8_t *)&dip, 119 *sp_b = (uint8_t *)&sp, 120 *dp_b = (uint8_t *)&dp; 121 122 if (first_time) { 123 build_byte_cache(byte_cache); 124 first_time = 0; 125 } 126 127 rc = byte_cache[sip_b[3]][0] ^ 128 byte_cache[sip_b[2]][1] ^ 129 byte_cache[sip_b[1]][2] ^ 130 byte_cache[sip_b[0]][3] ^ 131 byte_cache[dip_b[3]][0] ^ 132 byte_cache[dip_b[2]][1] ^ 133 byte_cache[dip_b[1]][2] ^ 134 byte_cache[dip_b[0]][3] ^ 135 byte_cache[sp_b[1]][0] ^ 136 byte_cache[sp_b[0]][1] ^ 137 byte_cache[dp_b[1]][2] ^ 138 byte_cache[dp_b[0]][3]; 139 140 return rc; 141 } 142 static uint32_t decode_gre_hash(const uint8_t *, uint8_t, uint8_t); 143 /*---------------------------------------------------------------------*/ 144 /** 145 ** Parser + hash function for the IPv4 packet 146 **/ 147 static uint32_t 148 decode_ip_n_hash(struct ip *iph, uint8_t hash_split, uint8_t seed) 149 { 150 uint32_t rc = 0; 151 152 if (hash_split == 2) { 153 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 154 ntohl(iph->ip_dst.s_addr), 155 ntohs(0xFFFD) + seed, 156 ntohs(0xFFFE) + seed); 157 } else { 158 struct tcphdr *tcph = NULL; 159 struct udphdr *udph = NULL; 160 161 switch (iph->ip_p) { 162 case IPPROTO_TCP: 163 tcph = (struct tcphdr *)((uint8_t *)iph + (iph->ip_hl<<2)); 164 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 165 ntohl(iph->ip_dst.s_addr), 166 ntohs(tcph->th_sport) + seed, 167 ntohs(tcph->th_dport) + seed); 168 break; 169 case IPPROTO_UDP: 170 udph = (struct udphdr *)((uint8_t *)iph + (iph->ip_hl<<2)); 171 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 172 ntohl(iph->ip_dst.s_addr), 173 ntohs(udph->uh_sport) + seed, 174 ntohs(udph->uh_dport) + seed); 175 break; 176 case IPPROTO_IPIP: 177 /* tunneling */ 178 rc = decode_ip_n_hash((struct ip *)((uint8_t *)iph + (iph->ip_hl<<2)), 179 hash_split, seed); 180 break; 181 case IPPROTO_GRE: 182 rc = decode_gre_hash((uint8_t *)iph + (iph->ip_hl<<2), 183 hash_split, seed); 184 break; 185 case IPPROTO_ICMP: 186 case IPPROTO_ESP: 187 case IPPROTO_PIM: 188 case IPPROTO_IGMP: 189 default: 190 /* 191 ** the hash strength (although weaker but) should still hold 192 ** even with 2 fields 193 **/ 194 rc = sym_hash_fn(ntohl(iph->ip_src.s_addr), 195 ntohl(iph->ip_dst.s_addr), 196 ntohs(0xFFFD) + seed, 197 ntohs(0xFFFE) + seed); 198 break; 199 } 200 } 201 return rc; 202 } 203 /*---------------------------------------------------------------------*/ 204 /** 205 ** Parser + hash function for the IPv6 packet 206 **/ 207 static uint32_t 208 decode_ipv6_n_hash(struct ip6_hdr *ipv6h, uint8_t hash_split, uint8_t seed) 209 { 210 uint32_t saddr, daddr; 211 uint32_t rc = 0; 212 213 /* Get only the first 4 octets */ 214 saddr = ipv6h->ip6_src.s6_addr[0] | 215 (ipv6h->ip6_src.s6_addr[1] << 8) | 216 (ipv6h->ip6_src.s6_addr[2] << 16) | 217 (ipv6h->ip6_src.s6_addr[3] << 24); 218 daddr = ipv6h->ip6_dst.s6_addr[0] | 219 (ipv6h->ip6_dst.s6_addr[1] << 8) | 220 (ipv6h->ip6_dst.s6_addr[2] << 16) | 221 (ipv6h->ip6_dst.s6_addr[3] << 24); 222 223 if (hash_split == 2) { 224 rc = sym_hash_fn(ntohl(saddr), 225 ntohl(daddr), 226 ntohs(0xFFFD) + seed, 227 ntohs(0xFFFE) + seed); 228 } else { 229 struct tcphdr *tcph = NULL; 230 struct udphdr *udph = NULL; 231 232 switch(ntohs(ipv6h->ip6_ctlun.ip6_un1.ip6_un1_nxt)) { 233 case IPPROTO_TCP: 234 tcph = (struct tcphdr *)(ipv6h + 1); 235 rc = sym_hash_fn(ntohl(saddr), 236 ntohl(daddr), 237 ntohs(tcph->th_sport) + seed, 238 ntohs(tcph->th_dport) + seed); 239 break; 240 case IPPROTO_UDP: 241 udph = (struct udphdr *)(ipv6h + 1); 242 rc = sym_hash_fn(ntohl(saddr), 243 ntohl(daddr), 244 ntohs(udph->uh_sport) + seed, 245 ntohs(udph->uh_dport) + seed); 246 break; 247 case IPPROTO_IPIP: 248 /* tunneling */ 249 rc = decode_ip_n_hash((struct ip *)(ipv6h + 1), 250 hash_split, seed); 251 break; 252 case IPPROTO_IPV6: 253 /* tunneling */ 254 rc = decode_ipv6_n_hash((struct ip6_hdr *)(ipv6h + 1), 255 hash_split, seed); 256 break; 257 case IPPROTO_GRE: 258 rc = decode_gre_hash((uint8_t *)(ipv6h + 1), hash_split, seed); 259 break; 260 case IPPROTO_ICMP: 261 case IPPROTO_ESP: 262 case IPPROTO_PIM: 263 case IPPROTO_IGMP: 264 default: 265 /* 266 ** the hash strength (although weaker but) should still hold 267 ** even with 2 fields 268 **/ 269 rc = sym_hash_fn(ntohl(saddr), 270 ntohl(daddr), 271 ntohs(0xFFFD) + seed, 272 ntohs(0xFFFE) + seed); 273 } 274 } 275 return rc; 276 } 277 /*---------------------------------------------------------------------*/ 278 /** 279 * * A temp solution while hash for other protocols are filled... 280 * * (See decode_vlan_n_hash & pkt_hdr_hash functions). 281 * */ 282 static uint32_t 283 decode_others_n_hash(struct ether_header *ethh, uint8_t seed) 284 { 285 uint32_t saddr, daddr, rc; 286 287 saddr = ethh->ether_shost[5] | 288 (ethh->ether_shost[4] << 8) | 289 (ethh->ether_shost[3] << 16) | 290 (ethh->ether_shost[2] << 24); 291 daddr = ethh->ether_dhost[5] | 292 (ethh->ether_dhost[4] << 8) | 293 (ethh->ether_dhost[3] << 16) | 294 (ethh->ether_dhost[2] << 24); 295 296 rc = sym_hash_fn(ntohl(saddr), 297 ntohl(daddr), 298 ntohs(0xFFFD) + seed, 299 ntohs(0xFFFE) + seed); 300 301 return rc; 302 } 303 /*---------------------------------------------------------------------*/ 304 /** 305 ** Parser + hash function for VLAN packet 306 **/ 307 static inline uint32_t 308 decode_vlan_n_hash(struct ether_header *ethh, uint8_t hash_split, uint8_t seed) 309 { 310 uint32_t rc = 0; 311 struct vlanhdr *vhdr = (struct vlanhdr *)(ethh + 1); 312 313 switch (ntohs(vhdr->proto)) { 314 case ETHERTYPE_IP: 315 rc = decode_ip_n_hash((struct ip *)(vhdr + 1), 316 hash_split, seed); 317 break; 318 case ETHERTYPE_IPV6: 319 rc = decode_ipv6_n_hash((struct ip6_hdr *)(vhdr + 1), 320 hash_split, seed); 321 break; 322 case ETHERTYPE_ARP: 323 default: 324 /* others */ 325 rc = decode_others_n_hash(ethh, seed); 326 break; 327 } 328 return rc; 329 } 330 331 /*---------------------------------------------------------------------*/ 332 /** 333 ** General parser + hash function... 334 **/ 335 uint32_t 336 pkt_hdr_hash(const unsigned char *buffer, uint8_t hash_split, uint8_t seed) 337 { 338 uint32_t rc = 0; 339 struct ether_header *ethh = (struct ether_header *)buffer; 340 341 switch (ntohs(ethh->ether_type)) { 342 case ETHERTYPE_IP: 343 rc = decode_ip_n_hash((struct ip *)(ethh + 1), 344 hash_split, seed); 345 break; 346 case ETHERTYPE_IPV6: 347 rc = decode_ipv6_n_hash((struct ip6_hdr *)(ethh + 1), 348 hash_split, seed); 349 break; 350 case ETHERTYPE_VLAN: 351 rc = decode_vlan_n_hash(ethh, hash_split, seed); 352 break; 353 case ETHERTYPE_ARP: 354 default: 355 /* others */ 356 rc = decode_others_n_hash(ethh, seed); 357 break; 358 } 359 360 return rc; 361 } 362 363 /*---------------------------------------------------------------------*/ 364 /** 365 ** Parser + hash function for the GRE packet 366 **/ 367 static uint32_t 368 decode_gre_hash(const uint8_t *grehdr, uint8_t hash_split, uint8_t seed) 369 { 370 uint32_t rc = 0; 371 int len = 4 + 2 * (!!(*grehdr & 1) + /* Checksum */ 372 !!(*grehdr & 2) + /* Routing */ 373 !!(*grehdr & 4) + /* Key */ 374 !!(*grehdr & 8)); /* Sequence Number */ 375 uint16_t proto = ntohs(*(uint16_t *)(void *)(grehdr + 2)); 376 377 switch (proto) { 378 case ETHERTYPE_IP: 379 rc = decode_ip_n_hash((struct ip *)(grehdr + len), 380 hash_split, seed); 381 break; 382 case ETHERTYPE_IPV6: 383 rc = decode_ipv6_n_hash((struct ip6_hdr *)(grehdr + len), 384 hash_split, seed); 385 break; 386 case 0x6558: /* Transparent Ethernet Bridging */ 387 rc = pkt_hdr_hash(grehdr + len, hash_split, seed); 388 break; 389 default: 390 /* others */ 391 break; 392 } 393 return rc; 394 } 395 /*---------------------------------------------------------------------*/ 396 397