flows.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362
  1. /*
  2. * Copyright (c) 2001-2010 Aaron Turner <aturner at synfin dot net>
  3. * Copyright (c) 2013-2024 Fred Klassen <tcpreplay at appneta dot com> - AppNeta
  4. *
  5. * The Tcpreplay Suite of tools is free software: you can redistribute it
  6. * and/or modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation, either version 3 of the
  8. * License, or with the authors permission any later version.
  9. *
  10. * The Tcpreplay Suite is distributed in the hope that it will be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with the Tcpreplay Suite. If not, see <http://www.gnu.org/licenses/>.
  17. */
  18. #include "flows.h"
  19. #include "tcpreplay_api.h"
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include <string.h>
  23. #define JUNIPER_FLAG_NO_L2 0x02 /* L2 header */
  24. #define JUNIPER_FLAG_EXT 0x80 /* Juniper extensions present */
  25. #define JUNIPER_PCAP_MAGIC "MGC"
  26. /* 5-tuple plus VLAN ID */
  27. typedef struct flow_entry_data {
  28. union {
  29. struct in_addr in;
  30. struct in6_addr in6;
  31. } src_ip;
  32. union {
  33. struct in_addr in;
  34. struct in6_addr in6;
  35. } dst_ip;
  36. uint16_t src_port;
  37. uint16_t dst_port;
  38. uint16_t vlan;
  39. uint8_t protocol;
  40. } flow_entry_data_t;
  41. typedef struct flow_hash_entry {
  42. uint32_t key;
  43. flow_entry_data_t data;
  44. struct timeval ts_last_seen;
  45. struct flow_hash_entry *next;
  46. } flow_hash_entry_t;
  47. struct flow_hash_table {
  48. size_t num_buckets;
  49. flow_hash_entry_t **buckets;
  50. };
  51. static bool is_power_of_2(size_t n)
  52. {
  53. return (n != 0 && ((n & (n - 1)) == 0));
  54. }
  55. /*
  56. * Perl's hash function
  57. *
  58. * We do extensive hashing to prevent hash table collisions.
  59. * It will save time in the long run.
  60. */
  61. static inline uint32_t hash_func(const void *key, size_t length)
  62. {
  63. register size_t i = length;
  64. register uint32_t hv = 0;
  65. register const u_char *s = (u_char *)key;
  66. while (i--) {
  67. hv += *s++;
  68. hv += (hv << 10);
  69. hv ^= (hv >> 6);
  70. }
  71. hv += (hv << 3);
  72. hv ^= (hv >> 11);
  73. hv += (hv << 15);
  74. return hv;
  75. }
  76. /*
  77. * add hash value to hash table bucket
  78. */
  79. static inline flow_hash_entry_t *hash_add_entry(flow_hash_table_t *fht, const uint32_t hv,
  80. const uint32_t key, const flow_entry_data_t *hash_entry)
  81. {
  82. flow_hash_entry_t *he;
  83. assert(hv < fht->num_buckets);
  84. he = safe_malloc(sizeof (*he));
  85. if (!he) {
  86. warn("out of memory");
  87. return NULL;
  88. }
  89. he->key = key;
  90. he->next = fht->buckets[hv];
  91. fht->buckets[hv] = he;
  92. memcpy(&he->data, hash_entry, sizeof(he->data));
  93. return he;
  94. }
  95. /*
  96. * Search for this entry in the hash table and
  97. * insert it if not found. Report whether this
  98. * is a new, existing or expired flow.
  99. *
  100. * Only check for expiry if 'expiry' is set
  101. */
  102. static inline flow_entry_type_t hash_put_data(flow_hash_table_t *fht, const uint32_t key,
  103. const flow_entry_data_t *hash_entry, const struct timeval *tv, const int expiry)
  104. {
  105. uint32_t hash_value = key & (fht->num_buckets - 1);
  106. flow_hash_entry_t *he;
  107. flow_entry_type_t res;
  108. for (he = fht->buckets[hash_value]; he; he = he->next) {
  109. /*
  110. * found an existing entry with similar hash. double
  111. * check to see if it is our flow or just a collision
  112. */
  113. if (he->key == key && !memcmp(&he->data, hash_entry, sizeof(he->data)))
  114. break;
  115. }
  116. if (he) {
  117. /* this is not a new flow */
  118. if (expiry && tv->tv_sec > (expiry + he->ts_last_seen.tv_sec))
  119. res = FLOW_ENTRY_EXPIRED;
  120. else
  121. res = FLOW_ENTRY_EXISTING;
  122. if (expiry)
  123. TIMEVAL_SET(&he->ts_last_seen, tv);
  124. } else {
  125. /* this is a new flow */
  126. if ((he = hash_add_entry(fht, hash_value, key, hash_entry)) != NULL) {
  127. res = FLOW_ENTRY_NEW;
  128. if (expiry)
  129. TIMEVAL_SET(&he->ts_last_seen, tv);
  130. } else
  131. res = FLOW_ENTRY_INVALID;
  132. }
  133. dbgx(2, "flow type=%d", (int)res);
  134. return res;
  135. }
  136. /*
  137. * Decode the packet, study it's flow status and report
  138. */
  139. flow_entry_type_t
  140. flow_decode(flow_hash_table_t *fht,
  141. const struct pcap_pkthdr *pkthdr,
  142. const u_char *pktdata,
  143. const int datalink,
  144. const int expiry,
  145. COUNTER packetnum)
  146. {
  147. uint32_t pkt_len = pkthdr->caplen;
  148. const u_char *packet = pktdata;
  149. uint32_t _U_ vlan_offset;
  150. uint32_t _U_ l2offset;
  151. uint16_t ether_type = 0;
  152. ipv4_hdr_t *ip_hdr = NULL;
  153. ipv6_hdr_t *ip6_hdr = NULL;
  154. tcp_hdr_t *tcp_hdr;
  155. udp_hdr_t *udp_hdr;
  156. icmpv4_hdr_t *icmp_hdr;
  157. flow_entry_data_t entry;
  158. uint32_t l2len = 0;
  159. uint8_t protocol;
  160. uint32_t hash;
  161. int ip_len;
  162. int res;
  163. assert(fht);
  164. assert(packet);
  165. /*
  166. * extract the 5-tuple and populate the entry data
  167. */
  168. memset(&entry, 0, sizeof(entry));
  169. res = get_l2len_protocol(packet,
  170. pkt_len,
  171. datalink,
  172. &ether_type,
  173. &l2len,
  174. &l2offset,
  175. &vlan_offset);
  176. if (res == -1) {
  177. warnx("flow_decode failed to determine %s header length for packet " COUNTER_SPEC "",
  178. pcap_datalink_val_to_description(datalink),
  179. packetnum);
  180. return FLOW_ENTRY_INVALID;
  181. }
  182. if (ether_type == ETHERTYPE_IP) {
  183. size_t required_len = sizeof(ipv4_hdr_t) + l2len;
  184. if (pkt_len < required_len) {
  185. warnx("flow_decode: packet " COUNTER_SPEC " needs at least %zd bytes for IPv4 header but only %d available",
  186. packetnum,
  187. required_len,
  188. pkt_len);
  189. return FLOW_ENTRY_INVALID;
  190. }
  191. ip_hdr = (ipv4_hdr_t *)(packet + l2len);
  192. if (ip_hdr->ip_v != 4) {
  193. warnx("flow_decode: packet " COUNTER_SPEC " IPv4 header version should be 4 but instead is %u",
  194. packetnum,
  195. ip_hdr->ip_v);
  196. return FLOW_ENTRY_NON_IP;
  197. }
  198. ip_len = ip_hdr->ip_hl * 4;
  199. protocol = ip_hdr->ip_p;
  200. entry.src_ip.in = ip_hdr->ip_src;
  201. entry.dst_ip.in = ip_hdr->ip_dst;
  202. } else if (ether_type == ETHERTYPE_IP6) {
  203. size_t required_len = sizeof(ipv6_hdr_t) + l2len;
  204. if (pkt_len < required_len) {
  205. warnx("flow_decode: packet " COUNTER_SPEC " needs at least %zd bytes for IPv6 header but only %d available",
  206. packetnum,
  207. required_len,
  208. pkt_len);
  209. return FLOW_ENTRY_INVALID;
  210. }
  211. uint8_t ip6_version = packet[0] >> 4;
  212. if (ip6_version != 6) {
  213. warnx("flow_decode: packet " COUNTER_SPEC " IPv6 header version should be 6 but instead is %u",
  214. packetnum,
  215. ip6_version);
  216. return FLOW_ENTRY_NON_IP;
  217. }
  218. ip6_hdr = (ipv6_hdr_t *)(packet + l2len);
  219. ip_len = sizeof(*ip6_hdr);
  220. protocol = ip6_hdr->ip_nh;
  221. if (protocol == 0) {
  222. struct tcpr_ipv6_ext_hdr_base *ext = (struct tcpr_ipv6_ext_hdr_base *)(ip6_hdr + 1);
  223. ip_len += (ext->ip_len + 1) * 8;
  224. protocol = ext->ip_nh;
  225. }
  226. memcpy(&entry.src_ip.in6, &ip6_hdr->ip_src, sizeof(entry.src_ip.in6));
  227. memcpy(&entry.dst_ip.in6, &ip6_hdr->ip_dst, sizeof(entry.dst_ip.in6));
  228. } else {
  229. return FLOW_ENTRY_NON_IP;
  230. }
  231. entry.protocol = protocol;
  232. switch (protocol) {
  233. case IPPROTO_UDP: {
  234. size_t required_len = sizeof(udp_hdr_t) + l2len + ip_len;
  235. if (pkt_len < required_len) {
  236. warnx("flow_decode: packet " COUNTER_SPEC " needs at least %zd bytes for UDP header but only %d available",
  237. packetnum,
  238. required_len,
  239. pkt_len);
  240. return FLOW_ENTRY_INVALID;
  241. }
  242. udp_hdr = (udp_hdr_t *)(packet + ip_len + l2len);
  243. entry.src_port = udp_hdr->uh_sport;
  244. entry.dst_port = udp_hdr->uh_dport;
  245. break;
  246. }
  247. case IPPROTO_TCP: {
  248. size_t required_len = sizeof(tcp_hdr_t) + l2len + ip_len;
  249. if (pkt_len < required_len) {
  250. warnx("flow_decode: packet " COUNTER_SPEC " needs at least %zd bytes for TCP header but only %d available",
  251. packetnum,
  252. required_len,
  253. pkt_len);
  254. return FLOW_ENTRY_INVALID;
  255. }
  256. tcp_hdr = (tcp_hdr_t *)(packet + ip_len + l2len);
  257. entry.src_port = tcp_hdr->th_sport;
  258. entry.dst_port = tcp_hdr->th_dport;
  259. break;
  260. }
  261. case IPPROTO_ICMP:
  262. case IPPROTO_ICMPV6: {
  263. size_t required_len = sizeof(icmpv4_hdr_t) + l2len + ip_len;
  264. if (pkt_len < required_len) {
  265. warnx("flow_decode: packet " COUNTER_SPEC " needs at least %zd bytes for %s header but only %d available",
  266. packetnum,
  267. required_len,
  268. (protocol == IPPROTO_ICMP) ? "ICMP" : "ICMPv6",
  269. pkt_len);
  270. return FLOW_ENTRY_INVALID;
  271. }
  272. icmp_hdr = (icmpv4_hdr_t *)(packet + ip_len + l2len);
  273. entry.src_port = icmp_hdr->icmp_type;
  274. entry.dst_port = icmp_hdr->icmp_code;
  275. break;
  276. }
  277. default:
  278. entry.src_port = 0;
  279. entry.dst_port = 0;
  280. }
  281. /* hash the 5-tuple */
  282. hash = hash_func(&entry, sizeof(entry));
  283. return hash_put_data(fht, hash, &entry, &pkthdr->ts, expiry);
  284. }
  285. static void flow_cache_clear(flow_hash_table_t *fht)
  286. {
  287. flow_hash_entry_t *fhe = NULL;
  288. flow_hash_entry_t *fhe_next = NULL;
  289. size_t i;
  290. for (i = 0; i < fht->num_buckets; i++) {
  291. if ((fhe = fht->buckets[i]) != NULL) {
  292. while (fhe) {
  293. fhe_next = fhe->next;
  294. safe_free(fhe);
  295. fhe = fhe_next;
  296. }
  297. fht->buckets[i] = NULL;
  298. }
  299. }
  300. }
  301. flow_hash_table_t *flow_hash_table_init(size_t n)
  302. {
  303. flow_hash_table_t *fht;
  304. if (!is_power_of_2(n))
  305. errx(-1, "invalid table size: %zu", n);
  306. fht = safe_malloc(sizeof(*fht));
  307. fht->num_buckets = n;
  308. fht->buckets = safe_malloc(sizeof(flow_hash_entry_t) * n);
  309. return fht;
  310. }
  311. void flow_hash_table_release(flow_hash_table_t *fht)
  312. {
  313. if (!fht)
  314. return;
  315. flow_cache_clear(fht);
  316. safe_free(fht->buckets);
  317. safe_free(fht);
  318. }