![[first]](../icons/first.png){kind=icon}
![[previous]](../icons/n_left.png){kind=icon}
![[next]](../icons/n_right.png){kind=icon}
![[last]](../icons/last.png){kind=icon}
![[top]](../icons/n_top.png){kind=icon}
![[bottom]](../icons/bottom.png){kind=icon}
![[index]](../icons/index.png){kind=icon}
![[help]](../icons/help.png){kind=icon}
*/
1 /*
2 * INET An implementation of the TCP/IP protocol suite for the LINUX
3 * operating system. INET is implemented using the BSD Socket
4 * interface as the means of communication with the user level.
5 *
6 * The IP fragmentation functionality.
7 *
8 * Authors: Fred N. van Kempen <waltje@uWalt.NL.Mugnet.ORG>
9 * Alan Cox <Alan.Cox@linux.org>
10 *
11 * Fixes:
12 * Alan Cox : Split from ip.c , see ip_input.c for history.
13 */
14
15 #include <linux/config.h>
16 #include <linux/types.h>
17 #include <linux/mm.h>
18 #include <linux/sched.h>
19 #include <linux/skbuff.h>
20 #include <linux/ip.h>
21 #include <linux/icmp.h>
22 #include <linux/netdevice.h>
23 #include <net/sock.h>
24 #include <net/ip.h>
25 #include <net/icmp.h>
26 #include <linux/tcp.h>
27 #include <linux/udp.h>
28 #include <linux/firewall.h>
29 #include <linux/ip_fw.h>
30 #include <net/checksum.h>
31
32 /*
33 * Fragment cache limits. We will commit 256K at one time. Should we
34 * cross that limit we will prune down to 192K. This should cope with
35 * even the most extreme cases without allowing an attacker to measurably
36 * harm machine performance.
37 */
38
39 #define IPFRAG_HIGH_THRESH (256*1024)
40 #define IPFRAG_LOW_THRESH (192*1024)
41
42 /*
43 * This fragment handler is a bit of a heap. On the other hand it works quite
44 * happily and handles things quite well.
45 */
46
47 static struct ipq *ipqueue = NULL; /* IP fragment queue */
48
49 unsigned long ip_frag_mem = 0; /* Memory used for fragments */
50
51 /*
52 * Memory Tracking Functions
53 */
54
55 extern __inline__ void frag_kfree_skb(struct sk_buff *skb, int type)
/* ![[next]](../icons/right.png)
![[first]](../icons/n_first.png)
![[top]](../icons/top.png)
*/
56 {
57 unsigned long flags;
58 save_flags(flags);
59 cli();
60 ip_frag_mem-=skb->truesize;
61 restore_flags(flags);
62 kfree_skb(skb,type);
63 }
64
65 extern __inline__ void frag_kfree_s(void *ptr, int len)
/* ![[previous]](../icons/left.png)
*/
66 {
67 unsigned long flags;
68 save_flags(flags);
69 cli();
70 ip_frag_mem-=len;
71 restore_flags(flags);
72 kfree_s(ptr,len);
73 }
74
75 extern __inline__ void *frag_kmalloc(int size, int pri)
/* */
76 {
77 unsigned long flags;
78 void *vp=kmalloc(size,pri);
79 if(!vp)
80 return NULL;
81 save_flags(flags);
82 cli();
83 ip_frag_mem+=size;
84 restore_flags(flags);
85 return vp;
86 }
87
88 /*
89 * Create a new fragment entry.
90 */
91
92 static struct ipfrag *ip_frag_create(int offset, int end, struct sk_buff *skb, unsigned char *ptr)
/* */
93 {
94 struct ipfrag *fp;
95 unsigned long flags;
96
97 fp = (struct ipfrag *) frag_kmalloc(sizeof(struct ipfrag), GFP_ATOMIC);
98 if (fp == NULL)
99 {
100 NETDEBUG(printk("IP: frag_create: no memory left !\n"));
101 return(NULL);
102 }
103 memset(fp, 0, sizeof(struct ipfrag));
104
105 /* Fill in the structure. */
106 fp->offset = offset;
107 fp->end = end;
108 fp->len = end - offset;
109 fp->skb = skb;
110 fp->ptr = ptr;
111
112 /*
113 * Charge for the SKB as well.
114 */
115
116 save_flags(flags);
117 cli();
118 ip_frag_mem+=skb->truesize;
119 restore_flags(flags);
120
121 return(fp);
122 }
123
124
125 /*
126 * Find the correct entry in the "incomplete datagrams" queue for
127 * this IP datagram, and return the queue entry address if found.
128 */
129
130 static struct ipq *ip_find(struct iphdr *iph)
/* */
131 {
132 struct ipq *qp;
133 struct ipq *qplast;
134
135 cli();
136 qplast = NULL;
137 for(qp = ipqueue; qp != NULL; qplast = qp, qp = qp->next)
138 {
139 if (iph->id== qp->iph->id && iph->saddr == qp->iph->saddr &&
140 iph->daddr == qp->iph->daddr && iph->protocol == qp->iph->protocol)
141 {
142 del_timer(&qp->timer); /* So it doesn't vanish on us. The timer will be reset anyway */
143 sti();
144 return(qp);
145 }
146 }
147 sti();
148 return(NULL);
149 }
150
151
152 /*
153 * Remove an entry from the "incomplete datagrams" queue, either
154 * because we completed, reassembled and processed it, or because
155 * it timed out.
156 */
157
158 static void ip_free(struct ipq *qp)
/* */
159 {
160 struct ipfrag *fp;
161 struct ipfrag *xp;
162
163 /*
164 * Stop the timer for this entry.
165 */
166
167 del_timer(&qp->timer);
168
169 /* Remove this entry from the "incomplete datagrams" queue. */
170 cli();
171 if (qp->prev == NULL)
172 {
173 ipqueue = qp->next;
174 if (ipqueue != NULL)
175 ipqueue->prev = NULL;
176 }
177 else
178 {
179 qp->prev->next = qp->next;
180 if (qp->next != NULL)
181 qp->next->prev = qp->prev;
182 }
183
184 /* Release all fragment data. */
185
186 fp = qp->fragments;
187 while (fp != NULL)
188 {
189 xp = fp->next;
190 IS_SKB(fp->skb);
191 frag_kfree_skb(fp->skb,FREE_READ);
192 frag_kfree_s(fp, sizeof(struct ipfrag));
193 fp = xp;
194 }
195
196 /* Release the IP header. */
197 frag_kfree_s(qp->iph, 64 + 8);
198
199 /* Finally, release the queue descriptor itself. */
200 frag_kfree_s(qp, sizeof(struct ipq));
201 sti();
202 }
203
204
205 /*
206 * Oops- a fragment queue timed out. Kill it and send an ICMP reply.
207 */
208
209 static void ip_expire(unsigned long arg)
/* */
210 {
211 struct ipq *qp;
212
213 qp = (struct ipq *)arg;
214
215 /*
216 * Send an ICMP "Fragment Reassembly Timeout" message.
217 */
218
219 ip_statistics.IpReasmTimeout++;
220 ip_statistics.IpReasmFails++;
221 /* This if is always true... shrug */
222 if(qp->fragments!=NULL)
223 icmp_send(qp->fragments->skb,ICMP_TIME_EXCEEDED,
224 ICMP_EXC_FRAGTIME, 0, qp->dev);
225
226 /*
227 * Nuke the fragment queue.
228 */
229 ip_free(qp);
230 }
231
232 /*
233 * Memory limiting on fragments. Evictor trashes the oldest
234 * fragment queue until we are back under the low threshold
235 */
236
237 static void ip_evictor(void)
/* */
238 {
239 while(ip_frag_mem>IPFRAG_LOW_THRESH)
240 {
241 if(!ipqueue)
242 panic("ip_evictor: memcount");
243 ip_free(ipqueue);
244 }
245 }
246
247 /*
248 * Add an entry to the 'ipq' queue for a newly received IP datagram.
249 * We will (hopefully :-) receive all other fragments of this datagram
250 * in time, so we just create a queue for this datagram, in which we
251 * will insert the received fragments at their respective positions.
252 */
253
254 static struct ipq *ip_create(struct sk_buff *skb, struct iphdr *iph, struct device *dev)
/* */
255 {
256 struct ipq *qp;
257 int ihlen;
258
259 qp = (struct ipq *) frag_kmalloc(sizeof(struct ipq), GFP_ATOMIC);
260 if (qp == NULL)
261 {
262 NETDEBUG(printk("IP: create: no memory left !\n"));
263 return(NULL);
264 skb->dev = qp->dev;
265 }
266 memset(qp, 0, sizeof(struct ipq));
267
268 /*
269 * Allocate memory for the IP header (plus 8 octets for ICMP).
270 */
271
272 ihlen = iph->ihl * 4;
273 qp->iph = (struct iphdr *) frag_kmalloc(64 + 8, GFP_ATOMIC);
274 if (qp->iph == NULL)
275 {
276 NETDEBUG(printk("IP: create: no memory left !\n"));
277 frag_kfree_s(qp, sizeof(struct ipq));
278 return(NULL);
279 }
280
281 memcpy(qp->iph, iph, ihlen + 8);
282 qp->len = 0;
283 qp->ihlen = ihlen;
284 qp->fragments = NULL;
285 qp->dev = dev;
286
287 /* Start a timer for this entry. */
288 qp->timer.expires = jiffies + IP_FRAG_TIME; /* about 30 seconds */
289 qp->timer.data = (unsigned long) qp; /* pointer to queue */
290 qp->timer.function = ip_expire; /* expire function */
291 add_timer(&qp->timer);
292
293 /* Add this entry to the queue. */
294 qp->prev = NULL;
295 cli();
296 qp->next = ipqueue;
297 if (qp->next != NULL)
298 qp->next->prev = qp;
299 ipqueue = qp;
300 sti();
301 return(qp);
302 }
303
304
305 /*
306 * See if a fragment queue is complete.
307 */
308
309 static int ip_done(struct ipq *qp)
/* */
310 {
311 struct ipfrag *fp;
312 int offset;
313
314 /* Only possible if we received the final fragment. */
315 if (qp->len == 0)
316 return(0);
317
318 /* Check all fragment offsets to see if they connect. */
319 fp = qp->fragments;
320 offset = 0;
321 while (fp != NULL)
322 {
323 if (fp->offset > offset)
324 return(0); /* fragment(s) missing */
325 offset = fp->end;
326 fp = fp->next;
327 }
328
329 /* All fragments are present. */
330 return(1);
331 }
332
333
334 /*
335 * Build a new IP datagram from all its fragments.
336 *
337 * FIXME: We copy here because we lack an effective way of handling lists
338 * of bits on input. Until the new skb data handling is in I'm not going
339 * to touch this with a bargepole.
340 */
341
342 static struct sk_buff *ip_glue(struct ipq *qp)
/* */
343 {
344 struct sk_buff *skb;
345 struct iphdr *iph;
346 struct ipfrag *fp;
347 unsigned char *ptr;
348 int count, len;
349
350 /*
351 * Allocate a new buffer for the datagram.
352 */
353 len = qp->ihlen + qp->len;
354
355 if ((skb = dev_alloc_skb(len)) == NULL)
356 {
357 ip_statistics.IpReasmFails++;
358 NETDEBUG(printk("IP: queue_glue: no memory for gluing queue %p\n", qp));
359 ip_free(qp);
360 return(NULL);
361 }
362
363 /* Fill in the basic details. */
364 skb_put(skb,len);
365 skb->h.raw = skb->data;
366 skb->free = 1;
367
368 /* Copy the original IP headers into the new buffer. */
369 ptr = (unsigned char *) skb->h.raw;
370 memcpy(ptr, ((unsigned char *) qp->iph), qp->ihlen);
371 ptr += qp->ihlen;
372
373 count = 0;
374
375 /* Copy the data portions of all fragments into the new buffer. */
376 fp = qp->fragments;
377 while(fp != NULL)
378 {
379 if(count+fp->len > skb->len)
380 {
381 NETDEBUG(printk("Invalid fragment list: Fragment over size.\n"));
382 ip_free(qp);
383 frag_kfree_skb(skb,FREE_WRITE);
384 ip_statistics.IpReasmFails++;
385 return NULL;
386 }
387 memcpy((ptr + fp->offset), fp->ptr, fp->len);
388 count += fp->len;
389 fp = fp->next;
390 }
391
392 /* We glued together all fragments, so remove the queue entry. */
393 ip_free(qp);
394
395 /* Done with all fragments. Fixup the new IP header. */
396 iph = skb->h.iph;
397 iph->frag_off = 0;
398 iph->tot_len = htons((iph->ihl * 4) + count);
399 skb->ip_hdr = iph;
400
401 ip_statistics.IpReasmOKs++;
402 return(skb);
403 }
404
405
406 /*
407 * Process an incoming IP datagram fragment.
408 */
409
410 struct sk_buff *ip_defrag(struct iphdr *iph, struct sk_buff *skb, struct device *dev)
/* */
411 {
412 struct ipfrag *prev, *next, *tmp;
413 struct ipfrag *tfp;
414 struct ipq *qp;
415 struct sk_buff *skb2;
416 unsigned char *ptr;
417 int flags, offset;
418 int i, ihl, end;
419
420 ip_statistics.IpReasmReqds++;
421
422 /*
423 * Start by cleaning up the memory
424 */
425
426 if(ip_frag_mem>IPFRAG_HIGH_THRESH)
427 ip_evictor();
428 /*
429 * Find the entry of this IP datagram in the "incomplete datagrams" queue.
430 */
431
432 qp = ip_find(iph);
433
434 /* Is this a non-fragmented datagram? */
435 offset = ntohs(iph->frag_off);
436 flags = offset & ~IP_OFFSET;
437 offset &= IP_OFFSET;
438 if (((flags & IP_MF) == 0) && (offset == 0))
439 {
440 if (qp != NULL)
441 ip_free(qp); /* Huh? How could this exist?? */
442 return(skb);
443 }
444
445 offset <<= 3; /* offset is in 8-byte chunks */
446 ihl = iph->ihl * 4;
447
448 /*
449 * If the queue already existed, keep restarting its timer as long
450 * as we still are receiving fragments. Otherwise, create a fresh
451 * queue entry.
452 */
453
454 if (qp != NULL)
455 {
456 /* ANK. If the first fragment is received,
457 * we should remember the correct IP header (with options)
458 */
459 if (offset == 0)
460 {
461 qp->ihlen = ihl;
462 memcpy(qp->iph, iph, ihl+8);
463 }
464 del_timer(&qp->timer);
465 qp->timer.expires = jiffies + IP_FRAG_TIME; /* about 30 seconds */
466 qp->timer.data = (unsigned long) qp; /* pointer to queue */
467 qp->timer.function = ip_expire; /* expire function */
468 add_timer(&qp->timer);
469 }
470 else
471 {
472 /*
473 * If we failed to create it, then discard the frame
474 */
475 if ((qp = ip_create(skb, iph, dev)) == NULL)
476 {
477 skb->sk = NULL;
478 frag_kfree_skb(skb, FREE_READ);
479 ip_statistics.IpReasmFails++;
480 return NULL;
481 }
482 }
483
484 /*
485 * Determine the position of this fragment.
486 */
487
488 end = offset + ntohs(iph->tot_len) - ihl;
489
490 /*
491 * Point into the IP datagram 'data' part.
492 */
493
494 ptr = skb->data + ihl;
495
496 /*
497 * Is this the final fragment?
498 */
499
500 if ((flags & IP_MF) == 0)
501 qp->len = end;
502
503 /*
504 * Find out which fragments are in front and at the back of us
505 * in the chain of fragments so far. We must know where to put
506 * this fragment, right?
507 */
508
509 prev = NULL;
510 for(next = qp->fragments; next != NULL; next = next->next)
511 {
512 if (next->offset > offset)
513 break; /* bingo! */
514 prev = next;
515 }
516
517 /*
518 * We found where to put this one.
519 * Check for overlap with preceding fragment, and, if needed,
520 * align things so that any overlaps are eliminated.
521 */
522 if (prev != NULL && offset < prev->end)
523 {
524 i = prev->end - offset;
525 offset += i; /* ptr into datagram */
526 ptr += i; /* ptr into fragment data */
527 }
528
529 /*
530 * Look for overlap with succeeding segments.
531 * If we can merge fragments, do it.
532 */
533
534 for(tmp=next; tmp != NULL; tmp = tfp)
535 {
536 tfp = tmp->next;
537 if (tmp->offset >= end)
538 break; /* no overlaps at all */
539
540 i = end - next->offset; /* overlap is 'i' bytes */
541 tmp->len -= i; /* so reduce size of */
542 tmp->offset += i; /* next fragment */
543 tmp->ptr += i;
544 /*
545 * If we get a frag size of <= 0, remove it and the packet
546 * that it goes with.
547 */
548 if (tmp->len <= 0)
549 {
550 if (tmp->prev != NULL)
551 tmp->prev->next = tmp->next;
552 else
553 qp->fragments = tmp->next;
554
555 if (tfp->next != NULL)
556 tmp->next->prev = tmp->prev;
557
558 next=tfp; /* We have killed the original next frame */
559
560 frag_kfree_skb(tmp->skb,FREE_READ);
561 frag_kfree_s(tmp, sizeof(struct ipfrag));
562 }
563 }
564
565 /*
566 * Insert this fragment in the chain of fragments.
567 */
568
569 tfp = NULL;
570 tfp = ip_frag_create(offset, end, skb, ptr);
571
572 /*
573 * No memory to save the fragment - so throw the lot
574 */
575
576 if (!tfp)
577 {
578 skb->sk = NULL;
579 frag_kfree_skb(skb, FREE_READ);
580 return NULL;
581 }
582 tfp->prev = prev;
583 tfp->next = next;
584 if (prev != NULL)
585 prev->next = tfp;
586 else
587 qp->fragments = tfp;
588
589 if (next != NULL)
590 next->prev = tfp;
591
592 /*
593 * OK, so we inserted this new fragment into the chain.
594 * Check if we now have a full IP datagram which we can
595 * bump up to the IP layer...
596 */
597
598 if (ip_done(qp))
599 {
600 skb2 = ip_glue(qp); /* glue together the fragments */
601 return(skb2);
602 }
603 return(NULL);
604 }
605
606
607 /*
608 * This IP datagram is too large to be sent in one piece. Break it up into
609 * smaller pieces (each of size equal to the MAC header plus IP header plus
610 * a block of the data of the original IP data part) that will yet fit in a
611 * single device frame, and queue such a frame for sending by calling the
612 * ip_queue_xmit(). Note that this is recursion, and bad things will happen
613 * if this function causes a loop...
614 *
615 * Yes this is inefficient, feel free to submit a quicker one.
616 *
617 */
618
619 void ip_fragment(struct sock *sk, struct sk_buff *skb, struct device *dev, int is_frag)
/* ![[last]](../icons/n_last.png)
*/
620 {
621 struct iphdr *iph;
622 unsigned char *raw;
623 unsigned char *ptr;
624 struct sk_buff *skb2;
625 int left, mtu, hlen, len;
626 int offset;
627 unsigned long flags;
628
629 /*
630 * Point into the IP datagram header.
631 */
632
633 raw = skb->data;
634 #if 0
635 iph = (struct iphdr *) (raw + dev->hard_header_len);
636 skb->ip_hdr = iph;
637 #else
638 iph = skb->ip_hdr;
639 #endif
640
641 /*
642 * Setup starting values.
643 */
644
645 hlen = iph->ihl * 4;
646 left = ntohs(iph->tot_len) - hlen; /* Space per frame */
647 hlen += dev->hard_header_len; /* Total header size */
648 mtu = (dev->mtu - hlen); /* Size of data space */
649 ptr = (raw + hlen); /* Where to start from */
650
651 /*
652 * Check for any "DF" flag. [DF means do not fragment]
653 */
654
655 if (ntohs(iph->frag_off) & IP_DF)
656 {
657 ip_statistics.IpFragFails++;
658 printk("ip_queue_xmit: frag needed\n");
659 return;
660 }
661
662 /*
663 * The protocol doesn't seem to say what to do in the case that the
664 * frame + options doesn't fit the mtu. As it used to fall down dead
665 * in this case we were fortunate it didn't happen
666 */
667
668 if(mtu<8)
669 {
670 /* It's wrong but it's better than nothing */
671 icmp_send(skb,ICMP_DEST_UNREACH,ICMP_FRAG_NEEDED,dev->mtu, dev);
672 ip_statistics.IpFragFails++;
673 return;
674 }
675
676 /*
677 * Fragment the datagram.
678 */
679
680 /*
681 * The initial offset is 0 for a complete frame. When
682 * fragmenting fragments it's wherever this one starts.
683 */
684
685 if (is_frag & 2)
686 offset = (ntohs(iph->frag_off) & IP_OFFSET) << 3;
687 else
688 offset = 0;
689
690
691 /*
692 * Keep copying data until we run out.
693 */
694
695 while(left > 0)
696 {
697 len = left;
698 /* IF: it doesn't fit, use 'mtu' - the data space left */
699 if (len > mtu)
700 len = mtu;
701 /* IF: we are not sending upto and including the packet end
702 then align the next start on an eight byte boundary */
703 if (len < left)
704 {
705 len/=8;
706 len*=8;
707 }
708 /*
709 * Allocate buffer.
710 */
711
712 if ((skb2 = alloc_skb(len + hlen+15,GFP_ATOMIC)) == NULL)
713 {
714 NETDEBUG(printk("IP: frag: no memory for new fragment!\n"));
715 ip_statistics.IpFragFails++;
716 return;
717 }
718
719 /*
720 * Set up data on packet
721 */
722
723 skb2->arp = skb->arp;
724 if(skb->free==0)
725 printk("IP fragmenter: BUG free!=1 in fragmenter\n");
726 skb2->free = 1;
727 skb_put(skb2,len + hlen);
728 skb2->h.raw=(char *) skb2->data;
729 /*
730 * Charge the memory for the fragment to any owner
731 * it might possess
732 */
733
734 save_flags(flags);
735 if (sk)
736 {
737 cli();
738 sk->wmem_alloc += skb2->truesize;
739 skb2->sk=sk;
740 }
741 restore_flags(flags);
742 skb2->raddr = skb->raddr; /* For rebuild_header - must be here */
743
744 /*
745 * Copy the packet header into the new buffer.
746 */
747
748 memcpy(skb2->h.raw, raw, hlen);
749
750 /*
751 * Copy a block of the IP datagram.
752 */
753 memcpy(skb2->h.raw + hlen, ptr, len);
754 left -= len;
755
756 skb2->h.raw+=dev->hard_header_len;
757
758 /*
759 * Fill in the new header fields.
760 */
761 iph = (struct iphdr *)(skb2->h.raw/*+dev->hard_header_len*/);
762 iph->frag_off = htons((offset >> 3));
763 skb2->ip_hdr = iph;
764
765 /* ANK: dirty, but effective trick. Upgrade options only if
766 * the segment to be fragmented was THE FIRST (otherwise,
767 * options are already fixed) and make it ONCE
768 * on the initial skb, so that all the following fragments
769 * will inherit fixed options.
770 */
771 if (offset == 0)
772 ip_options_fragment(skb);
773
774 /*
775 * Added AC : If we are fragmenting a fragment thats not the
776 * last fragment then keep MF on each bit
777 */
778 if (left > 0 || (is_frag & 1))
779 iph->frag_off |= htons(IP_MF);
780 ptr += len;
781 offset += len;
782
783 /*
784 * Put this fragment into the sending queue.
785 */
786
787 ip_statistics.IpFragCreates++;
788
789 ip_queue_xmit(sk, dev, skb2, 2);
790 }
791 ip_statistics.IpFragOKs++;
792 }
793
794
![[bottom]](../icons/n_bottom.png){kind=icon}
*/