ipv4_frag.c

00001 /**
00002  * @file ipv4_frag.c
00003  * @brief IPv4 fragmentation and reassembly
00004  *
00005  * @section License
00006  *
00007  * Copyright (C) 2010-2017 Oryx Embedded SARL. All rights reserved.
00008  *
00009  * This file is part of CycloneTCP Open.
00010  *
00011  * This program is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU General Public License
00013  * as published by the Free Software Foundation; either version 2
00014  * of the License, or (at your option) any later version.
00015  *
00016  * This program is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  * GNU General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU General Public License
00022  * along with this program; if not, write to the Free Software Foundation,
00023  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00024  *
00025  * @section Description
00026  *
00027  * The Internet Protocol (IP) implements datagram fragmentation, so that
00028  * packets may be formed that can pass through a link with a smaller maximum
00029  * transmission unit (MTU) than the original datagram size. Refer to the
00030  * following RFCs for complete details:
00031  * - RFC 791: Internet Protocol specification
00032  * - RFC 815: IP datagram reassembly algorithms
00033  *
00034  * @author Oryx Embedded SARL (www.oryx-embedded.com)
00035  * @version 1.7.6
00036  **/
00037 
00038 //Switch to the appropriate trace level
00039 #define TRACE_LEVEL IPV4_TRACE_LEVEL
00040 
00041 //Dependencies
00042 #include "core/net.h"
00043 #include "core/ip.h"
00044 #include "ipv4/ipv4.h"
00045 #include "ipv4/ipv4_frag.h"
00046 #include "ipv4/icmp.h"
00047 #include "mibs/mib2_module.h"
00048 #include "debug.h"
00049 
00050 //Check TCP/IP stack configuration
00051 #if (IPV4_SUPPORT == ENABLED && IPV4_FRAG_SUPPORT == ENABLED)
00052 
00053 //Tick counter to handle periodic operations
00054 systime_t ipv4FragTickCounter;
00055 
00056 
00057 /**
00058  * @brief Fragment an IPv4 datagram into smaller packets
00059  * @param[in] interface Underlying network interface
00060  * @param[in] pseudoHeader IPv4 pseudo header
00061  * @param[in] id Fragment identification
00062  * @param[in] payload Multi-part buffer containing the payload
00063  * @param[in] payloadOffset Offset to the first payload byte
00064  * @param[in] timeToLive TTL value
00065  * @return Error code
00066  **/
00067 
00068 error_t ipv4FragmentDatagram(NetInterface *interface, Ipv4PseudoHeader *pseudoHeader,
00069    uint16_t id, const NetBuffer *payload, size_t payloadOffset, uint8_t timeToLive)
00070 {
00071    error_t error;
00072    size_t offset;
00073    size_t length;
00074    size_t payloadLength;
00075    size_t fragmentOffset;
00076    size_t maxFragmentSize;
00077    NetBuffer *fragment;
00078 
00079    //Retrieve the length of the payload
00080    payloadLength = netBufferGetLength(payload) - payloadOffset;
00081 
00082    //Allocate a memory buffer to hold IP fragments
00083    fragment = ipAllocBuffer(0, &fragmentOffset);
00084    //Failed to allocate memory?
00085    if(!fragment)
00086       return ERROR_OUT_OF_MEMORY;
00087 
00088    //Determine the maximum payload size for fragmented packets
00089    maxFragmentSize = interface->ipv4Context.linkMtu - sizeof(Ipv4Header);
00090    //The size shall be a multiple of 8-byte blocks
00091    maxFragmentSize -= (maxFragmentSize % 8);
00092 
00093    //Initialize error code
00094    error = NO_ERROR;
00095 
00096    //Split the payload into multiple IP fragments
00097    for(offset = 0; offset < payloadLength; offset += length)
00098    {
00099       //Flush the contents of the fragment
00100       error = netBufferSetLength(fragment, fragmentOffset);
00101       //Sanity check
00102       if(error)
00103          break;
00104 
00105       //Process the last fragment?
00106       if((payloadLength - offset) <= maxFragmentSize)
00107       {
00108          //Size of the current fragment
00109          length = payloadLength - offset;
00110          //Copy fragment data
00111          netBufferConcat(fragment, payload, payloadOffset + offset, length);
00112 
00113          //Do not set the MF flag for the last fragment
00114          error = ipv4SendPacket(interface, pseudoHeader, id,
00115             offset / 8, fragment, fragmentOffset, timeToLive);
00116       }
00117       else
00118       {
00119          //Size of the current fragment (must be a multiple of 8-byte blocks)
00120          length = maxFragmentSize;
00121          //Copy fragment data
00122          netBufferConcat(fragment, payload, payloadOffset + offset, length);
00123 
00124          //Fragmented packets must have the MF flag set
00125          error = ipv4SendPacket(interface, pseudoHeader, id,
00126             IPV4_FLAG_MF | (offset / 8), fragment, fragmentOffset, timeToLive);
00127       }
00128 
00129       //Failed to send current IP packet?
00130       if(error)
00131          break;
00132 
00133       //Number of IP datagram fragments that have been generated as a result
00134       //of fragmentation at this entity
00135       MIB2_INC_COUNTER32(mib2Base.ipGroup.ipFragCreates, 1);
00136    }
00137 
00138    //Check status code
00139    if(error)
00140    {
00141       //Number of IP datagrams that have been discarded because they needed
00142       //to be fragmented at this entity but could not be
00143       MIB2_INC_COUNTER32(mib2Base.ipGroup.ipFragFails, 1);
00144    }
00145    else
00146    {
00147       //Number of IP datagrams that have been successfully fragmented at
00148       //this entity
00149       MIB2_INC_COUNTER32(mib2Base.ipGroup.ipFragOKs, 1);
00150    }
00151 
00152    //Free previously allocated memory
00153    netBufferFree(fragment);
00154    //Return status code
00155    return error;
00156 }
00157 
00158 
00159 /**
00160  * @brief IPv4 datagram reassembly algorithm
00161  * @param[in] interface Underlying network interface
00162  * @param[in] packet Pointer to the IPv4 fragmented packet
00163  * @param[in] length Packet length including header and payload
00164  **/
00165 
00166 void ipv4ReassembleDatagram(NetInterface *interface,
00167    const Ipv4Header *packet, size_t length)
00168 {
00169    error_t error;
00170    uint16_t offset;
00171    uint16_t dataFirst;
00172    uint16_t dataLast;
00173    Ipv4FragDesc *frag;
00174    Ipv4HoleDesc *hole;
00175    Ipv4HoleDesc *prevHole;
00176 
00177    //Number of IP fragments received which needed to be reassembled
00178    MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmReqds, 1);
00179 
00180    //Get the length of the payload
00181    length -= packet->headerLength * 4;
00182    //Convert the fragment offset from network byte order
00183    offset = ntohs(packet->fragmentOffset);
00184 
00185    //Every fragment except the last must contain a multiple of 8 bytes of data
00186    if((offset & IPV4_FLAG_MF) && (length % 8))
00187    {
00188       //Number of failures detected by the IP reassembly algorithm
00189       MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00190       //Drop the incoming fragment
00191       return;
00192    }
00193 
00194    //Calculate the index of the first byte
00195    dataFirst = (offset & IPV4_OFFSET_MASK) * 8;
00196    //Calculate the index immediately following the last byte
00197    dataLast = dataFirst + (uint16_t) length;
00198 
00199    //Search for a matching IP datagram being reassembled
00200    frag = ipv4SearchFragQueue(interface, packet);
00201 
00202    //No matching entry in the reassembly queue?
00203    if(frag == NULL)
00204    {
00205       //Number of failures detected by the IP reassembly algorithm
00206       MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00207       //Drop the incoming fragment
00208       return;
00209    }
00210 
00211    //The very first fragment requires special handling
00212    if(!(offset & IPV4_OFFSET_MASK))
00213    {
00214       //Calculate the length of the IP header including options
00215       frag->headerLength = packet->headerLength * 4;
00216 
00217       //Enforce the size of the reconstructed datagram
00218       if((frag->headerLength + frag->dataLength) > IPV4_MAX_FRAG_DATAGRAM_SIZE)
00219       {
00220          //Number of failures detected by the IP reassembly algorithm
00221          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00222          //Drop the reconstructed datagram
00223          netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00224          //Exit immediately
00225          return;
00226       }
00227 
00228       //Make sure the IP header entirely fits in the first chunk
00229       if(frag->headerLength > frag->buffer.chunk[0].size)
00230       {
00231          //Number of failures detected by the IP reassembly algorithm
00232          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00233          //Drop the reconstructed datagram
00234          netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00235          //Exit immediately
00236          return;
00237       }
00238 
00239       //Fix the length of the first chunk
00240       frag->buffer.chunk[0].length = frag->headerLength;
00241       //Always take the IP header from the first fragment
00242       netBufferWrite((NetBuffer *) &frag->buffer, 0, packet, frag->headerLength);
00243    }
00244 
00245    //It may be necessary to increase the size of the buffer...
00246    if(dataLast > frag->dataLength)
00247    {
00248       //Enforce the size of the reconstructed datagram
00249       if((frag->headerLength + dataLast) > IPV4_MAX_FRAG_DATAGRAM_SIZE)
00250       {
00251          //Number of failures detected by the IP reassembly algorithm
00252          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00253          //Drop the reconstructed datagram
00254          netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00255          //Exit immediately
00256          return;
00257       }
00258 
00259       //Adjust the size of the reconstructed datagram
00260       error = netBufferSetLength((NetBuffer *) &frag->buffer,
00261          frag->headerLength + dataLast + sizeof(Ipv4HoleDesc));
00262 
00263       //Any error to report?
00264       if(error)
00265       {
00266          //Number of failures detected by the IP reassembly algorithm
00267          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00268          //Drop the reconstructed datagram
00269          netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00270          //Exit immediately
00271          return;
00272       }
00273 
00274       //Actual length of the payload
00275       frag->dataLength = dataLast;
00276    }
00277 
00278    //Select the first hole descriptor from the list
00279    hole = ipv4FindHole(frag, frag->firstHole);
00280    //Keep track of the previous hole in the list
00281    prevHole = NULL;
00282 
00283    //Iterate through the hole descriptors
00284    while(hole != NULL)
00285    {
00286       //Save lower and upper boundaries for later use
00287       uint16_t holeFirst = hole->first;
00288       uint16_t holeLast = hole->last;
00289 
00290       //Check whether the newly arrived fragment
00291       //interacts with this hole in some way
00292       if(dataFirst < holeLast && dataLast > holeFirst)
00293       {
00294          //The current descriptor is no longer valid. We will destroy
00295          //it, and in the next two steps, we will determine whether
00296          //or not it is necessary to create any new hole descriptors
00297          if(prevHole != NULL)
00298             prevHole->next = hole->next;
00299          else
00300             frag->firstHole = hole->next;
00301 
00302          //Is there still a hole at the beginning of the segment?
00303          if(dataFirst > holeFirst)
00304          {
00305             //Create a new entry that describes this hole
00306             hole = ipv4FindHole(frag, holeFirst);
00307             hole->first = holeFirst;
00308             hole->last = dataFirst;
00309 
00310             //Insert the newly created entry into the hole descriptor list
00311             if(prevHole != NULL)
00312             {
00313                hole->next = prevHole->next;
00314                prevHole->next = hole->first;
00315             }
00316             else
00317             {
00318                hole->next = frag->firstHole;
00319                frag->firstHole = hole->first;
00320             }
00321 
00322             //Always keep track of the previous hole
00323             prevHole = hole;
00324          }
00325 
00326          //Is there still a hole at the end of the segment?
00327          if(dataLast < holeLast && (offset & IPV4_FLAG_MF))
00328          {
00329             //Create a new entry that describes this hole
00330             hole = ipv4FindHole(frag, dataLast);
00331             hole->first = dataLast;
00332             hole->last = holeLast;
00333 
00334             //Insert the newly created entry into the hole descriptor list
00335             if(prevHole != NULL)
00336             {
00337                hole->next = prevHole->next;
00338                prevHole->next = hole->first;
00339             }
00340             else
00341             {
00342                hole->next = frag->firstHole;
00343                frag->firstHole = hole->first;
00344             }
00345 
00346             //Always keep track of the previous hole
00347             prevHole = hole;
00348          }
00349       }
00350       else
00351       {
00352          //The newly arrived fragment does not interact with the current hole
00353          prevHole = hole;
00354       }
00355 
00356       //Select the next hole descriptor from the list
00357       hole = ipv4FindHole(frag, prevHole ? prevHole->next : frag->firstHole);
00358    }
00359 
00360    //Copy data from the fragment to the reassembly buffer
00361    netBufferWrite((NetBuffer *) &frag->buffer,
00362       frag->headerLength + dataFirst, IPV4_DATA(packet), length);
00363 
00364    //Dump hole descriptor list
00365    ipv4DumpHoleList(frag);
00366 
00367    //If the hole descriptor list is empty, the reassembly process is now complete
00368    if(!ipv4FindHole(frag, frag->firstHole))
00369    {
00370       //Discard the extra hole descriptor that follows the reconstructed datagram
00371       error = netBufferSetLength((NetBuffer *) &frag->buffer,
00372          frag->headerLength + frag->dataLength);
00373 
00374       //Check status code
00375       if(error)
00376       {
00377          //Number of failures detected by the IP reassembly algorithm
00378          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00379       }
00380       else
00381       {
00382          //Point to the IP header
00383          Ipv4Header *datagram = netBufferAt((NetBuffer *) &frag->buffer, 0);
00384 
00385          //Fix IP header
00386          datagram->totalLength = htons(frag->headerLength + frag->dataLength);
00387          datagram->fragmentOffset = 0;
00388          datagram->headerChecksum = 0;
00389 
00390          //Number of IP datagrams successfully reassembled
00391          MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmOKs, 1);
00392 
00393          //Pass the original IPv4 datagram to the higher protocol layer
00394          ipv4ProcessDatagram(interface, (NetBuffer *) &frag->buffer);
00395       }
00396 
00397       //Release previously allocated memory
00398       netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00399    }
00400 }
00401 
00402 
00403 /**
00404  * @brief Fragment reassembly timeout handler
00405  *
00406  * This routine must be periodically called by the TCP/IP stack to
00407  * handle IPv4 fragment reassembly timeout
00408  *
00409  * @param[in] interface Underlying network interface
00410  **/
00411 
00412 void ipv4FragTick(NetInterface *interface)
00413 {
00414    error_t error;
00415    uint_t i;
00416    systime_t time;
00417    Ipv4HoleDesc *hole;
00418 
00419    //Get current time
00420    time = osGetSystemTime();
00421 
00422    //Loop through the reassembly queue
00423    for(i = 0; i < IPV4_MAX_FRAG_DATAGRAMS; i++)
00424    {
00425       //Point to the current entry in the reassembly queue
00426       Ipv4FragDesc *frag = &interface->ipv4Context.fragQueue[i];
00427 
00428       //Make sure the entry is currently in use
00429       if(frag->buffer.chunkCount > 0)
00430       {
00431          //If the timer runs out, the partially-reassembled datagram must be
00432          //discarded and ICMP Time Exceeded message sent to the source host
00433          if((time - frag->timestamp) >= IPV4_FRAG_TIME_TO_LIVE)
00434          {
00435             //Debug message
00436             TRACE_INFO("IPv4 fragment reassembly timeout...\r\n");
00437             //Dump IP header contents for debugging purpose
00438             ipv4DumpHeader(frag->buffer.chunk[0].address);
00439 
00440             //Number of failures detected by the IP reassembly algorithm
00441             MIB2_INC_COUNTER32(mib2Base.ipGroup.ipReasmFails, 1);
00442 
00443             //Point to the first hole descriptor
00444             hole = ipv4FindHole(frag, frag->firstHole);
00445 
00446             //Make sure the fragment zero has been received
00447             //before sending an ICMP message
00448             if(hole != NULL && hole->first > 0)
00449             {
00450                //Fix the size of the reconstructed datagram
00451                error = netBufferSetLength((NetBuffer *) &frag->buffer,
00452                   frag->headerLength + hole->first);
00453 
00454                //Check status code
00455                if(!error)
00456                {
00457                   //Send an ICMP Time Exceeded message
00458                   icmpSendErrorMessage(interface, ICMP_TYPE_TIME_EXCEEDED,
00459                      ICMP_CODE_REASSEMBLY_TIME_EXCEEDED, 0, (NetBuffer *) &frag->buffer, 0);
00460                }
00461             }
00462 
00463             //Drop the partially reconstructed datagram
00464             netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00465          }
00466       }
00467    }
00468 }
00469 
00470 
00471 /**
00472  * @brief Search for a matching datagram in the reassembly queue
00473  * @param[in] interface Underlying network interface
00474  * @param[in] packet Incoming IPv4 packet
00475  * @return Matching fragment descriptor
00476  **/
00477 
00478 Ipv4FragDesc *ipv4SearchFragQueue(NetInterface *interface, const Ipv4Header *packet)
00479 {
00480    error_t error;
00481    uint_t i;
00482    Ipv4Header *datagram;
00483    Ipv4FragDesc *frag;
00484    Ipv4HoleDesc *hole;
00485 
00486    //Search for a matching IP datagram being reassembled
00487    for(i = 0; i < IPV4_MAX_FRAG_DATAGRAMS; i++)
00488    {
00489       //Point to the current entry in the reassembly queue
00490       frag = &interface->ipv4Context.fragQueue[i];
00491 
00492       //Check whether the current entry is used?
00493       if(frag->buffer.chunkCount > 0)
00494       {
00495          //Point to the corresponding datagram
00496          datagram = netBufferAt((NetBuffer *) &frag->buffer, 0);
00497 
00498          //Check source and destination addresses
00499          if(datagram->srcAddr != packet->srcAddr)
00500             continue;
00501          if(datagram->destAddr != packet->destAddr)
00502             continue;
00503          //Compare identification and protocol fields
00504          if(datagram->identification != packet->identification)
00505             continue;
00506          if(datagram->protocol != packet->protocol)
00507             continue;
00508 
00509          //A matching entry has been found in the reassembly queue
00510          return frag;
00511       }
00512    }
00513 
00514    //If the current packet does not match an existing entry
00515    //in the reassembly queue, then create a new entry
00516    for(i = 0; i < IPV4_MAX_FRAG_DATAGRAMS; i++)
00517    {
00518       //Point to the current entry in the reassembly queue
00519       frag = &interface->ipv4Context.fragQueue[i];
00520 
00521       //The current entry is free?
00522       if(!frag->buffer.chunkCount)
00523       {
00524          //Number of chunks that comprise the reassembly buffer
00525          frag->buffer.maxChunkCount = arraysize(frag->buffer.chunk);
00526 
00527          //Allocate sufficient memory to hold the IPv4 header and
00528          //the first hole descriptor
00529          error = netBufferSetLength((NetBuffer *) &frag->buffer,
00530             NET_MEM_POOL_BUFFER_SIZE + sizeof(Ipv4HoleDesc));
00531 
00532          //Failed to allocate memory?
00533          if(error)
00534          {
00535             //Clean up side effects
00536             netBufferSetLength((NetBuffer *) &frag->buffer, 0);
00537             //Exit immediately
00538             return NULL;
00539          }
00540 
00541          //Initial length of the reconstructed datagram
00542          frag->headerLength = packet->headerLength * 4;
00543          frag->dataLength = 0;
00544 
00545          //Fix the length of the first chunk
00546          frag->buffer.chunk[0].length = frag->headerLength;
00547          //Copy IPv4 header from the incoming fragment
00548          netBufferWrite((NetBuffer *) &frag->buffer, 0, packet, frag->headerLength);
00549 
00550          //Save current time
00551          frag->timestamp = osGetSystemTime();
00552          //Create a new entry in the hole descriptor list
00553          frag->firstHole = 0;
00554 
00555          //Point to first hole descriptor
00556          hole = ipv4FindHole(frag, frag->firstHole);
00557          //The entry describes the datagram as being completely missing
00558          hole->first = 0;
00559          hole->last = IPV4_INFINITY;
00560          hole->next = IPV4_INFINITY;
00561 
00562          //Dump hole descriptor list
00563          ipv4DumpHoleList(frag);
00564 
00565          //Return the matching fragment descriptor
00566          return frag;
00567       }
00568    }
00569 
00570    //The reassembly queue is full
00571    return NULL;
00572 }
00573 
00574 
00575 /**
00576  * @brief Flush IPv4 reassembly queue
00577  * @param[in] interface Underlying network interface
00578  **/
00579 
00580 void ipv4FlushFragQueue(NetInterface *interface)
00581 {
00582    uint_t i;
00583 
00584    //Loop through the reassembly queue
00585    for(i = 0; i < IPV4_MAX_FRAG_DATAGRAMS; i++)
00586    {
00587       //Drop any partially reconstructed datagram
00588       netBufferSetLength((NetBuffer *) &interface->ipv4Context.fragQueue[i].buffer, 0);
00589    }
00590 }
00591 
00592 
00593 /**
00594  * @brief Retrieve hole descriptor
00595  * @param[in] frag IPv4 fragment descriptor
00596  * @param[in] offset Offset of the hole
00597  * @return A pointer to the hole descriptor is returned if the
00598  *   specified offset is valid. Otherwise NULL is returned
00599  **/
00600 
00601 Ipv4HoleDesc *ipv4FindHole(Ipv4FragDesc *frag, uint16_t offset)
00602 {
00603    //Return a pointer to the hole descriptor
00604    return netBufferAt((NetBuffer *) &frag->buffer, frag->headerLength + offset);
00605 }
00606 
00607 
00608 /**
00609  * @brief Dump hole descriptor list
00610  * @param[in] frag IPv4 fragment descriptor
00611  **/
00612 
00613 void ipv4DumpHoleList(Ipv4FragDesc *frag)
00614 {
00615 //Check debugging level
00616 #if (TRACE_LEVEL >= TRACE_LEVEL_DEBUG)
00617    Ipv4HoleDesc *hole;
00618 
00619    //Debug message
00620    TRACE_DEBUG("Hole descriptor list:\r\n");
00621    //Select the first hole descriptor from the list
00622    hole = ipv4FindHole(frag, frag->firstHole);
00623 
00624    //Loop through the hole descriptor list
00625    while(hole != NULL)
00626    {
00627       //Display current hole
00628       TRACE_DEBUG("  %" PRIu16 " - %" PRIu16 "\r\n", hole->first, hole->last);
00629       //Select the next hole descriptor from the list
00630       hole = ipv4FindHole(frag, hole->next);
00631    }
00632 #endif
00633 }
00634 
00635 #endif
00636