nmsg  0.9.0
ipreasm.c
1 /*
2  * ipreasm -- Routines for reassembly of fragmented IPv4 and IPv6 packets.
3  *
4  * Copyright (c) 2007 Jan Andres <jandres@gmx.net>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  */
10 
11 #include "nmsg_port_net.h"
12 
13 #include <assert.h>
14 #include <errno.h>
15 #include <fcntl.h>
16 #include <stddef.h>
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <unistd.h>
21 
22 #include <pcap.h>
23 
24 #include "ipreasm.h"
25 
26 #define REASM_IP_HASH_SIZE 1021U
27 
28 
29 enum entry_state {
30  STATE_ACTIVE,
31  STATE_INVALID
32 };
33 
34 
35 enum reasm_proto {
36  PROTO_IPV4,
37  PROTO_IPV6
38 };
39 
40 
41 /*
42  * This tuple uniquely identifies all fragments belonging to
43  * the same IPv4 packet.
44  */
45 struct reasm_id_ipv4 {
46  uint8_t ip_src[4], ip_dst[4];
47  uint16_t ip_id;
48  uint8_t ip_proto;
49 };
50 
51 
52 /*
53  * Same for IPv6.
54  */
55 struct reasm_id_ipv6 {
56  uint8_t ip_src[16], ip_dst[16];
57  uint32_t ip_id;
58 };
59 
60 
61 union reasm_id {
62  struct reasm_id_ipv4 ipv4;
63  struct reasm_id_ipv6 ipv6;
64 };
65 
66 
67 struct reasm_frag_entry {
68  unsigned len; /* payload length of this fragment */
69  unsigned offset; /* offset of this fragment into the payload of the reassembled packet */
70  unsigned data_offset; /* offset to the data pointer where payload starts */
71  unsigned char *data; /* payload starts at data + data_offset */
72  struct reasm_frag_entry *next;
73 };
74 
75 
76 /*
77  * Reception of a complete packet is detected by counting the number
78  * of "holes" that remain between the cached fragments. A hole is
79  * assumed to exist at the upper end of the packet until the final
80  * fragment has been received. When the number of holes drops to 0,
81  * all fragments have been received and the packet can be reassembled.
82  */
83 struct reasm_ip_entry {
84  union reasm_id id;
85  unsigned len, holes, frag_count, hash;
86  reasm_time_t timeout;
87  enum entry_state state;
88  enum reasm_proto protocol;
89  struct reasm_frag_entry *frags;
90  struct reasm_ip_entry *prev, *next;
91  struct reasm_ip_entry *time_prev, *time_next;
92 };
93 
94 
95 /*
96  * This struct contains some metadata, the main hash table, and a pointer
97  * to the first entry that will time out. A linked list is kept in the
98  * order in which packets will time out. Using a linked list for this
99  * purpose requires that packets are input in chronological order, and
100  * that a constant timeout value is used, which doesn't change even when
101  * the entry's state transitions from active to invalid.
102  */
103 struct reasm_ip {
104  struct reasm_ip_entry *table[REASM_IP_HASH_SIZE];
105  struct reasm_ip_entry *time_first, *time_last;
106  unsigned waiting, max_waiting, timed_out, dropped_frags;
107  reasm_time_t timeout;
108 };
109 
110 
111 /*
112  * Hash functions.
113  */
114 static unsigned reasm_ipv4_hash (const struct reasm_id_ipv4 *id);
115 static unsigned reasm_ipv6_hash (const struct reasm_id_ipv6 *id);
116 
117 /*
118  * Insert a new fragment to the correct position in the list of fragments.
119  * Check for fragment overlap and other error conditions. Update the
120  * "hole count".
121  */
122 static bool add_fragment (struct reasm_ip_entry *entry, struct reasm_frag_entry *frag, bool last_frag);
123 
124 /*
125  * Is the entry complete, ready for reassembly?
126  */
127 static bool is_complete (struct reasm_ip_entry *entry);
128 
129 /*
130  * Create the reassembled packet.
131  */
132 static void assemble (struct reasm_ip_entry *entry, unsigned char *out_packet, unsigned *output_len);
133 
134 /*
135  * Drop and free entries.
136  */
137 static void drop_entry (struct reasm_ip *reasm, struct reasm_ip_entry *entry);
138 static void free_entry (struct reasm_ip_entry *entry);
139 
140 /*
141  * Dispose of any entries which have expired before "now".
142  */
143 static void process_timeouts (struct reasm_ip *reasm, reasm_time_t now);
144 
145 /*
146  * Create fragment structure from IPv6 packet. Returns NULL if the input
147  * is not a fragment.
148  * This function is called by parse_packet(), don't call it directly.
149  */
150 static struct reasm_frag_entry *frag_from_ipv6 (const unsigned char *packet, unsigned frag_hdr_offset, uint32_t *ip_id, bool *last_frag);
151 
152 /*
153  * Compare packet identification tuples for specified protocol.
154  */
155 static bool reasm_id_equal (enum reasm_proto proto, const union reasm_id *left, const union reasm_id *right);
156 
157 /*
158  * Create fragment structure from an IPv4 or IPv6 packet. Returns NULL
159  * if the input is not a fragment.
160  */
161 static struct reasm_frag_entry *parse_packet (const unsigned char *packet, unsigned len, unsigned frag_hdr_offset, enum reasm_proto *protocol, union reasm_id *id, unsigned *hash, bool *last_frag);
162 
163 
164 static unsigned
165 reasm_ipv4_hash (const struct reasm_id_ipv4 *id)
166 {
167  unsigned hash = 0;
168  int i;
169 
170  for (i = 0; i < 4; i++) {
171  hash = 37U * hash + id->ip_src[i];
172  hash = 37U * hash + id->ip_dst[i];
173  }
174 
175  hash = 59U * hash + id->ip_id;
176 
177  hash = 47U * hash + id->ip_proto;
178 
179  return hash;
180 }
181 
182 
183 static unsigned
184 reasm_ipv6_hash (const struct reasm_id_ipv6 *id)
185 {
186  unsigned hash = 0;
187  int i;
188 
189  for (i = 0; i < 16; i++) {
190  hash = 37U * hash + id->ip_src[i];
191  hash = 37U * hash + id->ip_dst[i];
192  }
193 
194  hash = 59U * hash + id->ip_id;
195 
196  return hash;
197 }
198 
199 
200 bool
201 reasm_ip_next (struct reasm_ip *reasm, const unsigned char *packet, unsigned len, unsigned frag_hdr_offset, reasm_time_t timestamp, unsigned char *out_packet, unsigned *output_len)
202 {
203  enum reasm_proto proto;
204  union reasm_id id;
205  unsigned hash = 0;
206  bool last_frag = 0;
207  struct reasm_frag_entry *frag;
208  struct reasm_ip_entry *entry;
209 
210  process_timeouts (reasm, timestamp);
211 
212  frag = parse_packet (packet, len, frag_hdr_offset, &proto, &id, &hash, &last_frag);
213  if (frag == NULL) {
214  *output_len = 0;
215  return false; /* some packet that we don't recognize as a fragment */
216  }
217 
218  hash %= REASM_IP_HASH_SIZE;
219  entry = reasm->table[hash];
220  while (entry != NULL && (proto != entry->protocol || !reasm_id_equal (proto, &id, &entry->id)))
221  entry = entry->next;
222 
223  if (entry == NULL) {
224  struct reasm_frag_entry *list_head;
225 
226  entry = malloc (sizeof (*entry));
227  if (entry == NULL) {
228  free (frag);
229  abort ();
230  }
231 
232  list_head = malloc (sizeof (*list_head));
233  if (list_head == NULL) {
234  free (frag);
235  free (entry);
236  abort ();
237  }
238 
239  memset(entry, 0, sizeof *entry);
240  entry->id = id;
241  entry->len = 0;
242  entry->holes = 1;
243  entry->frags = list_head;
244  entry->hash = hash;
245  entry->protocol = proto;
246  entry->timeout = timestamp + reasm->timeout;
247  entry->state = STATE_ACTIVE;
248  entry->prev = NULL;
249  entry->next = reasm->table[hash];
250  entry->time_prev = reasm->time_last;
251  entry->time_next = NULL;
252 
253  memset(list_head, 0, sizeof *list_head);
254  list_head->len = 0;
255  list_head->offset = 0;
256  list_head->data_offset = 0;
257  list_head->data = NULL;
258 
259  if (entry->next != NULL)
260  entry->next->prev = entry;
261  reasm->table[hash] = entry;
262 
263  if (reasm->time_last != NULL)
264  reasm->time_last->time_next = entry;
265  else
266  reasm->time_first = entry;
267  reasm->time_last = entry;
268 
269  reasm->waiting++;
270  if (reasm->waiting > reasm->max_waiting)
271  reasm->max_waiting = reasm->waiting;
272  }
273 
274  if (entry->state != STATE_ACTIVE) {
275  reasm->dropped_frags++;
276  *output_len = 0;
277  free(frag->data);
278  free(frag);
279  return true;
280  }
281 
282  if (!add_fragment (entry, frag, last_frag)) {
283  entry->state = STATE_INVALID;
284  reasm->dropped_frags += entry->frag_count + 1;
285  *output_len = 0;
286  free(frag->data);
287  free(frag);
288  return true;
289  }
290 
291  if (!is_complete (entry)) {
292  *output_len = 0;
293  return true;
294  }
295 
296  assemble (entry, out_packet, output_len);
297  drop_entry (reasm, entry);
298  return true;
299 }
300 
301 
302 static bool
303 add_fragment (struct reasm_ip_entry *entry, struct reasm_frag_entry *frag, bool last_frag)
304 {
305  bool fit_left, fit_right;
306  struct reasm_frag_entry *cur, *next;
307 
308  /*
309  * When a fragment is inserted into the list, different cases can occur
310  * concerning the number of holes.
311  * - The new fragment can be inserted in the middle of a hole, such that
312  * it will split the hole in two. The number of holes increases by 1.
313  * - The new fragment can be attached to one end of a hole, such that
314  * the rest of the hole remains at the opposite side of the fragment.
315  * The number of holes remains constant.
316  * - The new fragment can fill a hole completely. The number of holes
317  * decreases by 1.
318  */
319 
320  /*
321  * If more fragments follow and the payload size is not an integer
322  * multiple of 8, the packet will never be reassembled completely.
323  */
324  if (!last_frag && (frag->len & 7) != 0)
325  return false;
326 
327  if (entry->len != 0 && frag->len + frag->offset > entry->len)
328  return false; /* fragment extends past end of packet */
329 
330  fit_left = false;
331  fit_right = false;
332 
333  if (last_frag) {
334  if (entry->len != 0)
335  return false;
336  entry->len = frag->offset + frag->len;
337  fit_right = true;
338  }
339 
340  cur = entry->frags;
341  next = cur->next;
342 
343  while (cur->next != NULL && cur->next->offset <= frag->offset)
344  cur = cur->next;
345  next = cur->next;
346 
347  /* Fragment is to be inserted between cur and next; next may be NULL. */
348 
349  /* Overlap checks. */
350  if (cur->offset + cur->len > frag->offset)
351  return false; /* overlaps with cur */
352  else if (cur->offset + cur->len == frag->offset)
353  fit_left = true;
354 
355  if (next != NULL) {
356  if (last_frag)
357  return false; /* next extends past end of packet */
358  if (frag->offset + frag->len > next->offset)
359  return false; /* overlaps with next */
360  else if (frag->offset + frag->len == next->offset)
361  fit_right = true;
362  }
363 
364  /*
365  * Everything's fine, insert it.
366  */
367  if (frag->len != 0) {
368  frag->next = cur->next;
369  cur->next = frag;
370 
371  if (fit_left && fit_right)
372  entry->holes--;
373  else if (!fit_left && !fit_right)
374  entry->holes++;
375 
376  entry->frag_count++;
377  } else {
378  /*
379  * If the fragment has zero size, we don't insert it into the list,
380  * but one case remains to be handled: If the zero-size fragment
381  * is the last fragment, and fits exactly with the fragment to its
382  * left, the number of holes decreases.
383  */
384  if (last_frag && fit_left)
385  entry->holes--;
386  }
387 
388 
389  return true;
390 }
391 
392 
393 struct reasm_ip *
394 reasm_ip_new (void)
395 {
396  struct reasm_ip *reasm = malloc (sizeof (*reasm));
397  if (reasm == NULL)
398  return NULL;
399 
400  memset (reasm, 0, sizeof (*reasm));
401  return reasm;
402 }
403 
404 
405 void
406 reasm_ip_free (struct reasm_ip *reasm)
407 {
408  while (reasm->time_first != NULL)
409  drop_entry (reasm, reasm->time_first);
410  free (reasm);
411 }
412 
413 
414 static bool
415 is_complete (struct reasm_ip_entry *entry)
416 {
417  return entry->holes == 0;
418 }
419 
420 
421 static void
422 assemble (struct reasm_ip_entry *entry, unsigned char *out_packet, unsigned *output_len)
423 {
424  struct reasm_frag_entry *frag = entry->frags->next; /* skip list head */
425  unsigned offset0 = frag->data_offset;
426 
427  switch (entry->protocol) {
428  case PROTO_IPV4:
429  break;
430  case PROTO_IPV6:
431  offset0 -= 8; /* size of frag header */
432  break;
433  default:
434  abort ();
435  }
436 
437  if (entry->len + offset0 > *output_len) {
438  /* The output buffer is too small. */
439  *output_len = 0;
440  return;
441  }
442 
443  *output_len = entry->len + offset0;
444 
445  /* copy the (unfragmentable) header from the first fragment received */
446  memcpy (out_packet, frag->data, offset0);
447 
448  /* join all the payload fragments together */
449  while (frag != NULL) {
450  memcpy (out_packet + offset0 + frag->offset, frag->data + frag->data_offset, frag->len);
451  frag = frag->next;
452  }
453 
454  /* some cleanups, e.g. update the length field of reassembled packet */
455  switch (entry->protocol) {
456  case PROTO_IPV4: {
457  struct nmsg_iphdr *ip_header = (struct nmsg_iphdr *) out_packet;
458  unsigned i, hl = 4 * ip_header->ip_hl;
459  int32_t sum = 0;
460  ip_header->ip_len = htons (offset0 + entry->len);
461  ip_header->ip_off = 0;
462  ip_header->ip_sum = 0;
463 
464  /* Recompute checksum. */
465  for (i = 0; i < hl; i += 2) {
466  uint16_t cur = (uint16_t) out_packet[i] << 8 | out_packet[i + 1];
467  sum += cur;
468  if ((sum & 0x80000000) != 0)
469  sum = (sum & 0xffff) + (sum >> 16);
470  }
471  while ((sum >> 16) != 0)
472  sum = (sum & 0xffff) + (sum >> 16);
473  ip_header->ip_sum = htons (~sum);
474  break;
475  }
476  case PROTO_IPV6: {
477  struct ip6_hdr *ip6_header = (struct ip6_hdr *) out_packet;
478  ip6_header->ip6_plen = htons (offset0 + entry->len - 40);
479  break;
480  }
481  default:
482  abort ();
483  }
484 }
485 
486 
487 static void
488 drop_entry (struct reasm_ip *reasm, struct reasm_ip_entry *entry)
489 {
490  if (entry->prev != NULL)
491  entry->prev->next = entry->next;
492  else
493  reasm->table[entry->hash] = entry->next;
494 
495  if (entry->next != NULL)
496  entry->next->prev = entry->prev;
497 
498  if (entry->time_prev != NULL)
499  entry->time_prev->time_next = entry->time_next;
500  else
501  reasm->time_first = entry->time_next;
502 
503  if (entry->time_next != NULL)
504  entry->time_next->time_prev = entry->time_prev;
505  else
506  reasm->time_last = entry->time_prev;
507 
508  reasm->waiting--;
509 
510  free_entry (entry);
511 }
512 
513 
514 static void
515 free_entry (struct reasm_ip_entry *entry)
516 {
517  struct reasm_frag_entry *frag = entry->frags, *next;
518  while (frag != NULL) {
519  next = frag->next;
520  if (frag->data != NULL)
521  free (frag->data);
522  free (frag);
523  frag = next;
524  }
525 
526  free (entry);
527 }
528 
529 
530 unsigned
531 reasm_ip_waiting (const struct reasm_ip *reasm)
532 {
533  return reasm->waiting;
534 }
535 
536 
537 unsigned
538 reasm_ip_max_waiting (const struct reasm_ip *reasm)
539 {
540  return reasm->max_waiting;
541 }
542 
543 
544 unsigned
545 reasm_ip_timed_out (const struct reasm_ip *reasm)
546 {
547  return reasm->timed_out;
548 }
549 
550 
551 unsigned
552 reasm_ip_dropped_frags (const struct reasm_ip *reasm)
553 {
554  return reasm->dropped_frags;
555 }
556 
557 
558 bool
559 reasm_ip_set_timeout (struct reasm_ip *reasm, reasm_time_t timeout)
560 {
561  if (reasm->time_first != NULL)
562  return false;
563 
564  reasm->timeout = timeout;
565  return true;
566 }
567 
568 
569 static void
570 process_timeouts (struct reasm_ip *reasm, reasm_time_t now)
571 {
572  while (reasm->time_first != NULL && reasm->time_first->timeout < now) {
573  reasm->timed_out++;
574  drop_entry (reasm, reasm->time_first);
575  }
576 }
577 
578 
579 static struct reasm_frag_entry *
580 frag_from_ipv6 (const unsigned char *packet, unsigned frag_hdr_offset, uint32_t *ip_id, bool *last_frag)
581 {
582  const struct ip6_hdr *ip6_header = (const struct ip6_hdr *) packet;
583  unsigned offset = 40; /* IPv6 header size */
584  uint8_t nxt = ip6_header->ip6_nxt;
585  unsigned total_len = 40 + ntohs (ip6_header->ip6_plen);
586  unsigned last_nxt = offsetof (struct ip6_hdr, ip6_nxt);
587  struct reasm_frag_entry *frag;
588  const struct ip6_frag *frag_header;
589  unsigned char *frag_data;
590 
591  /*
592  * IPv6 extension headers from RFC 2460:
593  * 0 Hop-by-Hop Options
594  * 43 Routing
595  * 44 Fragment
596  * 60 Destination Options
597  *
598  * We look out for the Fragment header; the other 3 header
599  * types listed above are recognized and considered safe to
600  * skip over if they occur before the Fragment header.
601  * Any unrecognized header will cause processing to stop and
602  * a subsequent Fragment header to stay unrecognized.
603  */
604  if (frag_hdr_offset != 0)
605  offset = frag_hdr_offset;
606  else {
607  while (nxt == IPPROTO_HOPOPTS || nxt == IPPROTO_ROUTING || nxt == IPPROTO_DSTOPTS) {
608  unsigned exthdr_len;
609 
610  if (offset + 2 > total_len)
611  return NULL; /* header extends past end of packet */
612 
613  exthdr_len = 8 + 8 * packet[offset + 1];
614  if (offset + exthdr_len > total_len)
615  return NULL; /* header extends past end of packet */
616 
617  nxt = packet[offset];
618  last_nxt = offset;
619  offset += exthdr_len;
620  }
621 
622  if (nxt != IPPROTO_FRAGMENT)
623  return NULL;
624  }
625 
626  if (offset + 8 > total_len)
627  return NULL; /* Fragment header extends past end of packet */
628 
629  frag = malloc (sizeof (*frag));
630  if (frag == NULL)
631  abort ();
632 
633  frag_header = (const struct ip6_frag *) (packet + offset);
634  offset += 8;
635 
636  frag_data = malloc (total_len);
637  if (frag_data == NULL)
638  abort ();
639  memcpy (frag_data, packet, total_len);
640 
641  /*
642  * The Fragment header will be removed on reassembly, so we have to
643  * replace the Next Header field of the previous header (which is
644  * currently IPPROTO_FRAGMENT), with the Next Header field of the
645  * Fragment header.
646  *
647  * XXX We really shouldn't manipulate the input packet in-place.
648  */
649  frag_data[last_nxt] = frag_header->ip6f_nxt;
650 
651  memset(frag, 0, sizeof *frag);
652  frag->len = total_len - offset;
653  frag->data_offset = offset;
654  frag->offset = ntohs (frag_header->ip6f_offlg & IP6F_OFF_MASK);
655  frag->data = frag_data;
656 
657  *ip_id = ntohl (frag_header->ip6f_ident);
658  *last_frag = (frag_header->ip6f_offlg & IP6F_MORE_FRAG) == 0;
659 
660  return frag;
661 }
662 
663 
664 static bool
665 reasm_id_equal (enum reasm_proto proto, const union reasm_id *left, const union reasm_id *right)
666 {
667  switch (proto) {
668  case PROTO_IPV4:
669  return memcmp (left->ipv4.ip_src, right->ipv4.ip_src, 4) == 0
670  && memcmp (left->ipv4.ip_dst, right->ipv4.ip_dst, 4) == 0
671  && left->ipv4.ip_id == right->ipv4.ip_id
672  && left->ipv4.ip_proto == right->ipv4.ip_proto;
673  case PROTO_IPV6:
674  return memcmp (left->ipv6.ip_src, right->ipv6.ip_src, 16) == 0
675  && memcmp (left->ipv6.ip_dst, right->ipv6.ip_dst, 16) == 0
676  && left->ipv6.ip_id == right->ipv6.ip_id;
677  default:
678  abort ();
679  }
680 }
681 
682 
683 static struct reasm_frag_entry *
684 parse_packet (const unsigned char *packet, unsigned len, unsigned frag_hdr_offset, enum reasm_proto *protocol, union reasm_id *id, unsigned *hash, bool *last_frag)
685 {
686  const struct nmsg_iphdr *ip_header = (const struct nmsg_iphdr *) packet;
687  struct reasm_frag_entry *frag = NULL;
688 
689  switch (ip_header->ip_v) {
690  case 4: {
691  uint16_t offset = ntohs (ip_header->ip_off);
692 
693  *protocol = PROTO_IPV4;
694  if (len >= (unsigned) ntohs (ip_header->ip_len) &&
695  (offset & (IP_MF | IP_OFFMASK)) != 0)
696  {
697  unsigned pl_hl, pl_len, pl_off;
698  u_char *frag_data;
699 
700  frag = malloc (sizeof (*frag));
701  if (frag == NULL)
702  abort ();
703 
704  pl_hl = ip_header->ip_hl * 4;
705  pl_len = ntohs (ip_header->ip_len);
706  pl_off = (offset & IP_OFFMASK) * 8;
707  frag_data = malloc (pl_len);
708  if (frag_data == NULL)
709  abort ();
710  memcpy (frag_data, packet, pl_len);
711 
712  frag->len = pl_len - pl_hl;
713  frag->offset = pl_off;
714  frag->data_offset = ip_header->ip_hl * 4;
715  frag->data = frag_data;
716 
717  *last_frag = (offset & IP_MF) == 0;
718 
719  memcpy (id->ipv4.ip_src, &ip_header->ip_src, 4);
720  memcpy (id->ipv4.ip_dst, &ip_header->ip_dst, 4);
721  id->ipv4.ip_id = ntohs (ip_header->ip_id);
722  id->ipv4.ip_proto = ip_header->ip_p;
723 
724  *hash = reasm_ipv4_hash (&id->ipv4);
725  }
726  break;
727  }
728 
729  case 6: {
730  const struct ip6_hdr *ip6_header =
731  (const struct ip6_hdr *) packet;
732  *protocol = PROTO_IPV6;
733  if (len >= (unsigned) ntohs (ip6_header->ip6_plen) + 40)
734  frag = frag_from_ipv6 (packet, frag_hdr_offset, &id->ipv6.ip_id, last_frag);
735  if (frag != NULL) {
736  memcpy (id->ipv6.ip_src, &ip6_header->ip6_src, 16);
737  memcpy (id->ipv6.ip_dst, &ip6_header->ip6_dst, 16);
738  *hash = reasm_ipv6_hash (&id->ipv6);
739  }
740  break;
741  }
742 
743  default:
744  break;
745  }
746 
747  return frag;
748 }