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