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
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 *    */
61static void
62build_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
84static void
85build_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 **/
111static uint32_t
112sym_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}
142static uint32_t decode_gre_hash(const uint8_t *, uint8_t, uint8_t);
143/*---------------------------------------------------------------------*/
144/**
145 ** Parser + hash function for the IPv4 packet
146 **/
147static uint32_t
148decode_ip_n_hash(const struct ip *iph, uint8_t hash_split, uint8_t seed)
149{
150	uint32_t rc = 0;
151
152	if (iph->ip_hl < 5 || iph->ip_hl * 4 > iph->ip_len) {
153		rc = 0;
154	} else if (hash_split == 2) {
155		rc = sym_hash_fn(ntohl(iph->ip_src.s_addr),
156			ntohl(iph->ip_dst.s_addr),
157			ntohs(0xFFFD) + seed,
158			ntohs(0xFFFE) + seed);
159	} else {
160		const struct tcphdr *tcph = NULL;
161		const struct udphdr *udph = NULL;
162
163		switch (iph->ip_p) {
164		case IPPROTO_TCP:
165			tcph = (const struct tcphdr *)((const uint8_t *)iph + (iph->ip_hl<<2));
166			rc = sym_hash_fn(ntohl(iph->ip_src.s_addr),
167					 ntohl(iph->ip_dst.s_addr),
168					 ntohs(tcph->th_sport) + seed,
169					 ntohs(tcph->th_dport) + seed);
170			break;
171		case IPPROTO_UDP:
172			udph = (const struct udphdr *)((const uint8_t *)iph + (iph->ip_hl<<2));
173			rc = sym_hash_fn(ntohl(iph->ip_src.s_addr),
174					 ntohl(iph->ip_dst.s_addr),
175					 ntohs(udph->uh_sport) + seed,
176					 ntohs(udph->uh_dport) + seed);
177			break;
178		case IPPROTO_IPIP:
179			/* tunneling */
180			rc = decode_ip_n_hash((const struct ip *)((const uint8_t *)iph + (iph->ip_hl<<2)),
181					      hash_split, seed);
182			break;
183		case IPPROTO_GRE:
184			rc = decode_gre_hash((const uint8_t *)iph + (iph->ip_hl<<2),
185					hash_split, seed);
186			break;
187		case IPPROTO_ICMP:
188		case IPPROTO_ESP:
189		case IPPROTO_PIM:
190		case IPPROTO_IGMP:
191		default:
192			/*
193			 ** the hash strength (although weaker but) should still hold
194			 ** even with 2 fields
195			 **/
196			rc = sym_hash_fn(ntohl(iph->ip_src.s_addr),
197					 ntohl(iph->ip_dst.s_addr),
198					 ntohs(0xFFFD) + seed,
199					 ntohs(0xFFFE) + seed);
200			break;
201		}
202	}
203	return rc;
204}
205/*---------------------------------------------------------------------*/
206/**
207 ** Parser + hash function for the IPv6 packet
208 **/
209static uint32_t
210decode_ipv6_n_hash(const struct ip6_hdr *ipv6h, uint8_t hash_split, uint8_t seed)
211{
212	uint32_t saddr, daddr;
213	uint32_t rc = 0;
214
215	/* Get only the first 4 octets */
216	saddr = ipv6h->ip6_src.s6_addr[0] |
217		(ipv6h->ip6_src.s6_addr[1] << 8) |
218		(ipv6h->ip6_src.s6_addr[2] << 16) |
219		(ipv6h->ip6_src.s6_addr[3] << 24);
220	daddr = ipv6h->ip6_dst.s6_addr[0] |
221		(ipv6h->ip6_dst.s6_addr[1] << 8) |
222		(ipv6h->ip6_dst.s6_addr[2] << 16) |
223		(ipv6h->ip6_dst.s6_addr[3] << 24);
224
225	if (hash_split == 2) {
226		rc = sym_hash_fn(ntohl(saddr),
227				 ntohl(daddr),
228				 ntohs(0xFFFD) + seed,
229				 ntohs(0xFFFE) + seed);
230	} else {
231		const struct tcphdr *tcph = NULL;
232		const struct udphdr *udph = NULL;
233
234		switch(ntohs(ipv6h->ip6_ctlun.ip6_un1.ip6_un1_nxt)) {
235		case IPPROTO_TCP:
236			tcph = (const struct tcphdr *)(ipv6h + 1);
237			rc = sym_hash_fn(ntohl(saddr),
238					 ntohl(daddr),
239					 ntohs(tcph->th_sport) + seed,
240					 ntohs(tcph->th_dport) + seed);
241			break;
242		case IPPROTO_UDP:
243			udph = (const struct udphdr *)(ipv6h + 1);
244			rc = sym_hash_fn(ntohl(saddr),
245					 ntohl(daddr),
246					 ntohs(udph->uh_sport) + seed,
247					 ntohs(udph->uh_dport) + seed);
248			break;
249		case IPPROTO_IPIP:
250			/* tunneling */
251			rc = decode_ip_n_hash((const struct ip *)(ipv6h + 1),
252					      hash_split, seed);
253			break;
254		case IPPROTO_IPV6:
255			/* tunneling */
256			rc = decode_ipv6_n_hash((const struct ip6_hdr *)(ipv6h + 1),
257						hash_split, seed);
258			break;
259		case IPPROTO_GRE:
260			rc = decode_gre_hash((const uint8_t *)(ipv6h + 1), hash_split, seed);
261			break;
262		case IPPROTO_ICMP:
263		case IPPROTO_ESP:
264		case IPPROTO_PIM:
265		case IPPROTO_IGMP:
266		default:
267			/*
268			 ** the hash strength (although weaker but) should still hold
269			 ** even with 2 fields
270			 **/
271			rc = sym_hash_fn(ntohl(saddr),
272					 ntohl(daddr),
273					 ntohs(0xFFFD) + seed,
274					 ntohs(0xFFFE) + seed);
275		}
276	}
277	return rc;
278}
279/*---------------------------------------------------------------------*/
280/**
281 *  *  A temp solution while hash for other protocols are filled...
282 *   * (See decode_vlan_n_hash & pkt_hdr_hash functions).
283 *    */
284static uint32_t
285decode_others_n_hash(const struct ether_header *ethh, uint8_t seed)
286{
287	uint32_t saddr, daddr, rc;
288
289	saddr = ethh->ether_shost[5] |
290		(ethh->ether_shost[4] << 8) |
291		(ethh->ether_shost[3] << 16) |
292		(ethh->ether_shost[2] << 24);
293	daddr = ethh->ether_dhost[5] |
294		(ethh->ether_dhost[4] << 8) |
295		(ethh->ether_dhost[3] << 16) |
296		(ethh->ether_dhost[2] << 24);
297
298	rc = sym_hash_fn(ntohl(saddr),
299			 ntohl(daddr),
300			 ntohs(0xFFFD) + seed,
301			 ntohs(0xFFFE) + seed);
302
303	return rc;
304}
305/*---------------------------------------------------------------------*/
306/**
307 ** Parser + hash function for VLAN packet
308 **/
309static inline uint32_t
310decode_vlan_n_hash(const struct ether_header *ethh, uint8_t hash_split, uint8_t seed)
311{
312	uint32_t rc = 0;
313	const struct vlanhdr *vhdr = (const struct vlanhdr *)(ethh + 1);
314
315	switch (ntohs(vhdr->proto)) {
316	case ETHERTYPE_IP:
317		rc = decode_ip_n_hash((const struct ip *)(vhdr + 1),
318				      hash_split, seed);
319		break;
320	case ETHERTYPE_IPV6:
321		rc = decode_ipv6_n_hash((const struct ip6_hdr *)(vhdr + 1),
322					hash_split, seed);
323		break;
324	case ETHERTYPE_ARP:
325	default:
326		/* others */
327		rc = decode_others_n_hash(ethh, seed);
328		break;
329	}
330	return rc;
331}
332
333/*---------------------------------------------------------------------*/
334/**
335 ** General parser + hash function...
336 **/
337uint32_t
338pkt_hdr_hash(const unsigned char *buffer, uint8_t hash_split, uint8_t seed)
339{
340	uint32_t rc = 0;
341	const struct ether_header *ethh = (const struct ether_header *)buffer;
342
343	switch (ntohs(ethh->ether_type)) {
344	case ETHERTYPE_IP:
345		rc = decode_ip_n_hash((const struct ip *)(ethh + 1),
346				      hash_split, seed);
347		break;
348	case ETHERTYPE_IPV6:
349		rc = decode_ipv6_n_hash((const struct ip6_hdr *)(ethh + 1),
350					hash_split, seed);
351		break;
352	case ETHERTYPE_VLAN:
353		rc = decode_vlan_n_hash(ethh, hash_split, seed);
354		break;
355	case ETHERTYPE_ARP:
356	default:
357		/* others */
358		rc = decode_others_n_hash(ethh, seed);
359		break;
360	}
361
362	return rc;
363}
364
365/*---------------------------------------------------------------------*/
366/**
367 ** Parser + hash function for the GRE packet
368 **/
369static uint32_t
370decode_gre_hash(const uint8_t *grehdr, uint8_t hash_split, uint8_t seed)
371{
372	uint32_t rc = 0;
373	int len = 4 + 2 * (!!(*grehdr & 1) + /* Checksum */
374			   !!(*grehdr & 2) + /* Routing */
375			   !!(*grehdr & 4) + /* Key */
376			   !!(*grehdr & 8)); /* Sequence Number */
377	uint16_t proto = ntohs(*(const uint16_t *)(const void *)(grehdr + 2));
378
379	switch (proto) {
380	case ETHERTYPE_IP:
381		rc = decode_ip_n_hash((const struct ip *)(grehdr + len),
382				      hash_split, seed);
383		break;
384	case ETHERTYPE_IPV6:
385		rc = decode_ipv6_n_hash((const struct ip6_hdr *)(grehdr + len),
386					hash_split, seed);
387		break;
388	case 0x6558: /* Transparent Ethernet Bridging */
389		rc = pkt_hdr_hash(grehdr + len, hash_split, seed);
390		break;
391	default:
392		/* others */
393		break;
394	}
395	return rc;
396}
397/*---------------------------------------------------------------------*/
398
399