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: stable/11/tools/tools/netmap/pkt_hash.c 341434 2018-12-03 17:51:22Z vmaffione $ */
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(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 **/
207static uint32_t
208decode_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 *    */
282static uint32_t
283decode_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 **/
307static inline uint32_t
308decode_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 **/
335uint32_t
336pkt_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 **/
367static uint32_t
368decode_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