cipv6_fragmenter.c

00001 /*
00002  * Copyright (c) 2013-2017, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 /**
00018  *
00019  * \file cipv6_fragmenter.c
00020  * \brief Packet Fragmentation and Reassembly.
00021  *
00022  */
00023 
00024 #include "nsconfig.h"
00025 #include "ns_types.h"
00026 #include "string.h"
00027 #include "ns_trace.h"
00028 #include "randLIB.h"
00029 #include "Core/include/socket.h"
00030 #include "6LoWPAN/IPHC_Decode/cipv6.h"
00031 #include "6LoWPAN/Fragmentation/cipv6_fragmenter.h"
00032 #include "NWK_INTERFACE/Include/protocol.h"
00033 #include "nsdynmemLIB.h"
00034 #include "6LoWPAN/Mesh/mesh.h"
00035 #include "6LoWPAN/IPHC_Decode/iphc_decompress.h"
00036 #include "nwk_stats_api.h"
00037 #include "NWK_INTERFACE/Include/protocol_stats.h"
00038 #include "common_functions.h"
00039 #include "6LoWPAN/MAC/mac_helper.h"
00040 
00041 #define TRACE_GROUP "6frg"
00042 
00043 typedef struct {
00044     uint16_t ttl;   /*!< Reassembly timer (seconds) */
00045     uint16_t tag;   /*!< Fragmentation datagram TAG ID */
00046     uint16_t size;  /*!< Datagram Total Size (uncompressed) */
00047     uint16_t orig_size; /*!< Datagram Original Size (compressed) */
00048     uint16_t frag_max;  /*!< Maximum fragment size (MAC payload) */
00049     uint16_t offset; /*!< Data offset from datagram start */
00050     int16_t pattern; /*!< Size of compressed LoWPAN headers */
00051     buffer_t *buf;
00052     ns_list_link_t      link; /*!< List link entry */
00053 } reassembly_entry_t;
00054 
00055 typedef NS_LIST_HEAD (reassembly_entry_t, link) reassembly_list_t;
00056 
00057 typedef struct {
00058     int8_t interface_id;
00059     uint16_t timeout;
00060     reassembly_list_t rx_list;
00061     reassembly_list_t free_list;
00062     reassembly_entry_t *entry_pointer_buffer;
00063     ns_list_link_t      link; /*!< List link entry */
00064 } reassembly_interface_t;
00065 
00066 static NS_LIST_DEFINE(reassembly_interface_list, reassembly_interface_t, link);
00067 
00068 
00069 /* Reassembly structures and helpers - basically the same as in
00070  * ipv6_fragmentation.c, as we are also using a variation of RFC 815, but there
00071  * are enough minor differences that it doesn't seem worth trying to share code.
00072  */
00073 
00074 /* We reassemble into the datagram buffer in basically the style of RFC 815 */
00075 /* An 6-byte hole descriptor is placed directly in buffer holes */
00076 /* We link them them by buffer offset (relative to start of fragmentable section) */
00077 /* Note the possible need to align means we can't use more than 7 bytes */
00078 typedef struct hole {
00079     uint16_t first;
00080     uint16_t last;
00081     uint16_t next;
00082 } hole_t;
00083 
00084 /* Given the offset of a hole in the datagram buffer, return an aligned pointer
00085  * to put a hole_t in it. We assume a "normal" platform requiring 2-byte
00086  * alignment for hole_t, and letting us manipulate uintptr_t in the conventional
00087  * fashion.
00088  */
00089 static hole_t *hole_pointer(const buffer_t *buf, uint16_t offset)
00090 {
00091     uintptr_t ptr = (uintptr_t)(buffer_data_pointer(buf) + offset);
00092 
00093     return (hole_t *)((ptr + 1) & ~(uintptr_t) 1);
00094 }
00095 
00096 static void delete_hole(buffer_t *buf, uint16_t hole, uint16_t *prev_ptr)
00097 {
00098     hole_t *hole_ptr = hole_pointer(buf, hole);
00099 
00100     *prev_ptr = hole_ptr->next;
00101 }
00102 
00103 static hole_t *create_hole(buffer_t *buf, uint16_t first, uint16_t last, uint16_t *prev_ptr)
00104 {
00105     hole_t *hole_ptr = hole_pointer(buf, first);
00106     hole_ptr->first = first;
00107     hole_ptr->last = last;
00108     hole_ptr->next = *prev_ptr;
00109 
00110     *prev_ptr = first;
00111     return hole_ptr;
00112 }
00113 
00114 /*
00115  * RFC 4944 is oddly designed - it has blurred the header compression
00116  * and fragmentation layers. The datagram_size and datagram_offset field are
00117  * specified in terms of the uncompressed IPv6 datagram, not the actual 6LoWPAN
00118  * payload.
00119  *
00120  * This complicates reassembly if you don't decompress first; we don't because
00121  * the original upper layer works on IPHC headers directly, rather than native
00122  * IPv6.
00123  *
00124  * To handle the general case, including arbitrary fragment order so we don't
00125  * always know the 6LoWPAN size of the first fragment, the reassembly buffer
00126  * always leaves space for the uncompressed IPv6 header, and 1 byte more for a
00127  * 6LoWPAN "uncompressed IPv6" dispatch byte. This means non-first fragments
00128  * are always placed at buffer_data_pointer() + datagram_offset.
00129  *
00130  * This routine doesn't explicitly distinguish the compressed and uncompressed
00131  * cases - the difference arises purely from the output of "iphc_header_scan",
00132  * which sets "pattern" to the difference between IPv6 and 6LoWPAN size -
00133  * but to aid understanding, here's what it ends up doing in the two cases:
00134  *
00135  * IPHC compressed case
00136  * --------------------
00137  *
00138  *   -4         0                0x50
00139  *    +---------+--------+--------+       0x50 bytes of 6LoWPAN data
00140  *    |  FRAG1  |  IPHC  |  data1 |       0x70 bytes of uncompressed IPv6 data
00141  *    +---------+--------+--------+       "pattern" = 0x70 - 0x50 = 0x20
00142  *
00143  *   -5          0            0x60        (datagram_size = 0xD0)
00144  *    +----------+-------------+
00145  *    |FRAGN 0x70|    data2    |
00146  *    +----------+-------------+
00147  *
00148  * During assembly, the data pointer points at the "0" position representing the
00149  * virtual start of the IPv6 packet:
00150  *
00151  *   -1 0        0x20             0x70           0xD0
00152  *    +-+---------+--------+--------+-------------+
00153  *    | | padding |  IPHC  |  data1 |    data2    |
00154  *    +-+---------+--------+--------+-------------+
00155  *
00156  * On completion of assembly, the start pointer moves forward to point at the
00157  * IPHC header. (This means buffer size is slightly inefficient for an IPHC
00158  * upper layer, but it does reserve headroom for decompression to native IPv6.)
00159  *
00160  *  -0x21         0               0x50           0xB0
00161  *    +-----------+--------+--------+-------------+
00162  *    | headroom  |  IPHC  |  data1 |    data2    |
00163  *    +-----------+--------+--------+-------------+
00164 
00165  * Uncompressed case
00166  * -----------------
00167 
00168  *   -4         0 1             0x71  D = "Uncompressed IPv6" dispatch type 0x41
00169  *    +---------+-+--------------+    0x71 bytes of 6LoWPAN data
00170  *    |  FRAG1  |D|    data1     |    0x70 bytes of uncompressed IPv6 data
00171  *    +---------+-+--------------+    "pattern" = 0x70 - 0x71 = -1
00172  *
00173  *    -5         0              0x60        (datagram_size = 0xD0)
00174  *    +----------+---------------+
00175  *    |FRAGN 0x70|     data2     |
00176  *    +----------+---------------+
00177  *
00178  * During assembly, the data pointer points at the "0" position representing the
00179  * start of the IPv6 packet:
00180  *
00181  *   -1 0             0x70            0xD0
00182  *    +-+--------------+---------------+
00183  *    |D|    data1     |     data2     |
00184  *    +-+--------------+---------------+
00185  *
00186  * On completion of assembly, the start pointer moves back to point to the
00187  * 6LoWPAN dispatch byte:
00188  *
00189  *    0 1             0x71            0xD1
00190  *    +-+--------------+---------------+
00191  *    |D|    data1     |     data2     |
00192  *    +-+--------------+---------------+
00193 
00194  * (And if it's neither of these cases, a "native" 6LoWPAN reassembly happens
00195  * with "pattern" set to 0 - what probably should have happened in the first
00196  * place; offsets are treated as 6LoWPAN offsets from the start of the
00197  * fragmented 6LoWPAN data).
00198  */
00199 
00200 //Discover
00201 static reassembly_interface_t *reassembly_interface_discover(int8_t interfaceId)
00202 {
00203 
00204     ns_list_foreach(reassembly_interface_t, interface_ptr, &reassembly_interface_list) {
00205         if (interfaceId == interface_ptr->interface_id) {
00206             return interface_ptr;
00207         }
00208     }
00209 
00210     return NULL;
00211 }
00212 
00213 static void reassembly_entry_free(reassembly_interface_t *interface_ptr, reassembly_entry_t *entry)
00214 {
00215     ns_list_remove(&interface_ptr->rx_list, entry);
00216     ns_list_add_to_start(&interface_ptr->free_list, entry);
00217     if (entry->buf) {
00218         entry->buf = buffer_free(entry->buf);
00219     }
00220 }
00221 
00222 static void reassembly_list_free(reassembly_interface_t *interface_ptr )
00223 {
00224     ns_list_foreach_safe(reassembly_entry_t, reassembly_entry, &interface_ptr->rx_list) {
00225         reassembly_entry_free(interface_ptr, reassembly_entry);
00226     }
00227 }
00228 
00229 
00230 static reassembly_entry_t *reassembly_already_action(reassembly_list_t *reassembly_list, buffer_t *buf, uint16_t tag, uint16_t size)
00231 {
00232     ns_list_foreach(reassembly_entry_t, reassembly_entry, reassembly_list) {
00233         if ((reassembly_entry->tag == tag) && (reassembly_entry->size == size) &&
00234                 reassembly_entry->buf->src_sa.addr_type == buf->src_sa .addr_type  &&
00235                 reassembly_entry->buf->dst_sa.addr_type == buf->dst_sa .addr_type ) {
00236             /* Type will be either long or short 802.15.4 - we skip the PAN ID */
00237             if (memcmp(reassembly_entry->buf->src_sa.address + 2, buf->src_sa .address  + 2, addr_len_from_type(buf->src_sa .addr_type ) - 2) == 0 &&
00238                     memcmp(reassembly_entry->buf->dst_sa.address + 2, buf->dst_sa .address  + 2, addr_len_from_type(buf->dst_sa .addr_type ) - 2) == 0) {
00239                 return reassembly_entry;
00240             }
00241         }
00242     }
00243 
00244     return NULL;
00245 
00246 }
00247 
00248 static reassembly_entry_t *lowpan_adaptation_reassembly_get(reassembly_interface_t *interface_ptr)
00249 {
00250     reassembly_entry_t *entry = ns_list_get_first(&interface_ptr->free_list);
00251     if (!entry) {
00252         return NULL;
00253     }
00254 
00255     ns_list_remove(&interface_ptr->free_list, entry);
00256     memset(entry, 0, sizeof(reassembly_entry_t));
00257     //Add to first
00258     ns_list_add_to_start(&interface_ptr->rx_list, entry);
00259 
00260     return entry;
00261 }
00262 
00263 
00264 buffer_t *cipv6_frag_reassembly(int8_t interface_id, buffer_t *buf)
00265 {
00266     reassembly_interface_t *interface_ptr = reassembly_interface_discover(interface_id);
00267     if (!interface_ptr) {
00268         return buffer_free(buf);
00269     }
00270 
00271     uint16_t datagram_size, datagram_tag;
00272     uint16_t fragment_first;
00273     uint8_t frag_header;
00274 
00275     uint8_t *ptr = buffer_data_pointer(buf);
00276 
00277     frag_header = ptr[0];
00278     datagram_size = common_read_16_bit(ptr) & 0x07FF;
00279 
00280     if (datagram_size == 0) {
00281         goto resassembly_error;
00282     }
00283 
00284     ptr += 2;
00285     datagram_tag = common_read_16_bit(ptr);
00286     ptr += 2;
00287     if (frag_header & LOWPAN_FRAGN_BIT) {
00288         fragment_first = *ptr++ << 3;
00289     } else {
00290         fragment_first = 0;
00291     }
00292 
00293     /* Consume the fragment header. We don't distinguish FRAG1/FRAGN after this
00294      * point (we treat FRAGN with offset 0 the same as FRAG1)
00295      */
00296     buffer_data_pointer_set(buf, ptr);
00297     reassembly_entry_t *frag_ptr = reassembly_already_action(&interface_ptr->rx_list, buf, datagram_tag, datagram_size);
00298 
00299     if (!frag_ptr) {
00300 
00301         frag_ptr = lowpan_adaptation_reassembly_get(interface_ptr);
00302         if (!frag_ptr) {
00303             goto resassembly_error;
00304         }
00305 
00306         buffer_t *reassembly_buffer = buffer_get(1 + ((datagram_size+7) & ~7));
00307         if (!reassembly_buffer) {
00308             //Put allocated back to free
00309             reassembly_entry_free(interface_ptr, frag_ptr);
00310             goto resassembly_error;
00311         }
00312 
00313         // Allocate the reassembly buffer.
00314         // Allow 1 byte extra for an "Uncompressed IPv6" dispatch byte - the
00315         // 6LoWPAN data can be 1 byte longer than the IPv6 data.
00316         // Also, round datagram size up to a multiple of 8 to ensure we have
00317         // room for a final hole descriptor (it can spill past the indicated
00318         // datagram size if the last fragment is smaller than 8 bytes).
00319 
00320         reassembly_buffer->src_sa  = buf->src_sa ;
00321         reassembly_buffer->dst_sa  = buf->dst_sa ;
00322         frag_ptr->ttl = interface_ptr->timeout;
00323         frag_ptr->tag = datagram_tag;
00324         frag_ptr->size = datagram_size;
00325         // Set buffer length and adjust start pointer, so it represents the
00326         // uncompressed IPv6 packet. (See comment block before this function).
00327         buffer_data_length_set(reassembly_buffer, 1 + datagram_size);
00328         buffer_data_strip_header(reassembly_buffer, 1);
00329         // Write initial hole descriptor into buffer
00330         frag_ptr->offset = 0xffff;
00331         create_hole(reassembly_buffer, 0, datagram_size - 1, &frag_ptr->offset );
00332         frag_ptr->buf = reassembly_buffer;
00333     }
00334 
00335     /* For the first link fragment, work out and remember the "pattern"
00336      * (difference between6LoWPAN and IPv6 size), and also copy the buffer
00337      * header metadata.
00338      */
00339     uint16_t lowpan_size, ipv6_size;
00340     if (fragment_first == 0) {
00341         uint16_t uncompressed_header_size;
00342         uint8_t compressed_header_size;
00343         compressed_header_size = iphc_header_scan(buf, &uncompressed_header_size);
00344         lowpan_size = buffer_data_length(buf);
00345         ipv6_size = lowpan_size - compressed_header_size + uncompressed_header_size;
00346         frag_ptr->pattern = ipv6_size - lowpan_size;
00347 
00348         /* Clone the buffer header from this first fragment, preserving only size + pointers */
00349         /* Also the security flag - this fragment's flag is merged in later */
00350         bool buf_security = frag_ptr->buf->options.ll_security_bypass_rx;
00351         buffer_copy_metadata(frag_ptr->buf, buf, true);
00352         frag_ptr->buf->options.ll_security_bypass_rx = buf_security;
00353     } else {
00354         ipv6_size = lowpan_size = buffer_data_length(buf);
00355     }
00356 
00357     uint16_t fragment_last = fragment_first + ipv6_size - 1;
00358     if (fragment_last >= datagram_size) {
00359         tr_err("Frag out-of-range: last=%u, size=%u", fragment_last, datagram_size);
00360         //Free Current entry
00361         reassembly_entry_free(interface_ptr, frag_ptr);
00362         goto resassembly_error;
00363     }
00364 
00365     /* Hole-filling algorithm, basically as per RFC 815, but with added
00366      * checks for overlap. The hole list is kept sorted, as per
00367      * ipv6_fragmentation.c, but that's not relevant in this version.
00368      */
00369     uint16_t hole_off = frag_ptr->offset;
00370     uint16_t *prev_ptr = &frag_ptr->offset;
00371     do {
00372         hole_t *hole = hole_pointer(frag_ptr->buf, hole_off);
00373         uint_fast16_t hole_first = hole->first;
00374         uint_fast16_t hole_last = hole->last;
00375 
00376         /* Fragment is beyond this hole - move to next (RFC 815 step 2) */
00377         /* Fragment is before this hole - move to next (RFC 815 step 3) */
00378         if (fragment_first > hole_last || fragment_last < hole_first) {
00379             prev_ptr = &hole->next;
00380             hole_off = hole->next;
00381             continue;
00382         }
00383 
00384         /* If any of the fragment lies outside the hole, it indicates a problem;
00385          * we only expect repeat data from retransmission, so fragments should
00386          * always lie entirely within a hole or existing data, not straddle
00387          * them. If we see this happen then junk existing data, making this the
00388          * first fragment of a new reassembly (RFC 4944).
00389          */
00390         if (fragment_first < hole_first || fragment_last > hole_last) {
00391             tr_err("Frag overlap: hole %"PRIuFAST16"-%"PRIuFAST16", frag %"PRIu16"-%"PRIu16, hole_first, hole_last, fragment_first, fragment_last);
00392             protocol_stats_update(STATS_FRAG_RX_ERROR, 1);
00393             /* Forget previous data by marking as "all hole" */
00394             frag_ptr->offset = 0xffff;
00395             create_hole(frag_ptr->buf, hole_off = hole_first = 0, hole_last = datagram_size - 1, prev_ptr = &frag_ptr->offset);
00396         }
00397 
00398         /* Unhook this hole from the hole list (RFC 815 step 4) */
00399         delete_hole(frag_ptr->buf, hole_off, prev_ptr);
00400 
00401         /* Create a new hole in front if necessary (RFC 815 step 5) */
00402         if (fragment_first > hole_first) {
00403             prev_ptr = &create_hole(frag_ptr->buf, hole_first, fragment_first - 1, prev_ptr)->next;
00404         }
00405 
00406         /* Create a following hole if necessary (RFC 815 step 6) */
00407         if (fragment_last < hole_last) {
00408             create_hole(frag_ptr->buf, fragment_last + 1, hole_last, prev_ptr);
00409         }
00410 
00411         /* Unlike RFC 815, we're now done. We don't allow overlaps, so we finish
00412          * as soon as we identify one hole that it entirely or partially fills */
00413         break;
00414     } while (hole_off != 0xffff);
00415 
00416     /* Hole list updated, can now copy in the fragment data -  to make sure the
00417      * initial fragment goes in the right place we use the end offset, rather
00418      * than the start offset. */
00419     memcpy(buffer_data_pointer(frag_ptr->buf) + fragment_last + 1 - lowpan_size, buffer_data_pointer(buf), lowpan_size);
00420 
00421     /* Combine the "improper security" flags, so reassembled buffer's flag is set if any fragment wasn't secure */
00422     /* XXX should have some sort of overall "merge buffer metadata" routine handling this and whatever else */
00423     frag_ptr->buf->options.ll_security_bypass_rx |= buf->options .ll_security_bypass_rx ;
00424 
00425     /* We've finished with the original fragment buffer */
00426     buf = buffer_free(buf);
00427 
00428     /* Completion check - any holes left? */
00429     if (frag_ptr->offset != 0xffff) {
00430         /* Not yet complete - processing finished on this fragment */
00431         return NULL;
00432     }
00433 
00434     /* No more holes, so our reassembly is complete */
00435     buf = frag_ptr->buf ;
00436     frag_ptr->buf = NULL;
00437     reassembly_entry_free(interface_ptr, frag_ptr);
00438 
00439     /* Buffer start pointer is currently at the "start of uncompressed IPv6
00440      * packet" position. Move it either forwards or backwards to match
00441      * the IPHC data (could be compressed, or uncompressed with added dispatch
00442      * byte).
00443      */
00444     buf->buf_ptr  += frag_ptr->pattern;
00445     buf->info  = (buffer_info_t)(B_DIR_UP | B_FROM_FRAGMENTATION | B_TO_IPV6_TXRX);
00446     return buf;
00447 
00448 resassembly_error:
00449     protocol_stats_update(STATS_FRAG_RX_ERROR, 1);
00450     return buffer_free(buf);
00451 }
00452 
00453 static void reassembly_entry_timer_update(reassembly_interface_t *interface_ptr, uint16_t seconds)
00454 {
00455     ns_list_foreach_safe(reassembly_entry_t, reassembly_entry, &interface_ptr->rx_list) {
00456         if (reassembly_entry->ttl > seconds) {
00457             reassembly_entry->ttl -= seconds;
00458         } else {
00459             protocol_stats_update(STATS_FRAG_RX_ERROR, 1);
00460             tr_debug("Reassembly TO: src %s size %u",
00461                      trace_sockaddr(&reassembly_entry->buf->src_sa, true),
00462                      reassembly_entry->size);
00463             reassembly_entry_free(interface_ptr, reassembly_entry);
00464         }
00465     }
00466 }
00467 
00468 void cipv6_frag_timer(uint16_t seconds)
00469 {
00470     ns_list_foreach(reassembly_interface_t, interface_ptr, &reassembly_interface_list) {
00471         reassembly_entry_timer_update(interface_ptr, seconds);
00472     }
00473 }
00474 
00475 int8_t reassembly_interface_free(int8_t interface_id)
00476 {
00477     //Discover
00478     reassembly_interface_t *interface_ptr = reassembly_interface_discover(interface_id);
00479     if (!interface_ptr) {
00480         return -1;
00481     }
00482 
00483     ns_list_remove(&reassembly_interface_list, interface_ptr);
00484 
00485     //Free Dynamic allocated entry buffer
00486     ns_dyn_mem_free(interface_ptr->entry_pointer_buffer);
00487     ns_dyn_mem_free(interface_ptr);
00488 
00489     return 0;
00490 }
00491 
00492 
00493 int8_t reassembly_interface_init(int8_t interface_id, uint8_t reassembly_session_limit, uint16_t reassembly_timeout)
00494 {
00495 
00496     if (!reassembly_session_limit || !reassembly_timeout) {
00497         return -2;
00498     }
00499 
00500     //Remove old interface
00501     reassembly_interface_free(interface_id);
00502 
00503     //Allocate new
00504     reassembly_interface_t *interface_ptr = ns_dyn_mem_alloc(sizeof(reassembly_interface_t));
00505     reassembly_entry_t *reassemply_ptr = ns_dyn_mem_alloc(sizeof(reassembly_entry_t) * reassembly_session_limit);
00506     if (!interface_ptr || !reassemply_ptr) {
00507         ns_dyn_mem_free(interface_ptr);
00508         ns_dyn_mem_free(reassemply_ptr);
00509         return -1;
00510     }
00511 
00512     memset(interface_ptr, 0 ,sizeof(reassembly_interface_t));
00513     interface_ptr->interface_id = interface_id;
00514     interface_ptr->timeout = reassembly_timeout;
00515     interface_ptr->entry_pointer_buffer = reassemply_ptr;
00516     ns_list_init(&interface_ptr->free_list);
00517     ns_list_init(&interface_ptr->rx_list);
00518 
00519     for (uint8_t i=0; i<reassembly_session_limit ; i++) {
00520         ns_list_add_to_end(&interface_ptr->free_list, reassemply_ptr);
00521         reassemply_ptr++;
00522     }
00523 
00524     ns_list_add_to_end(&reassembly_interface_list, interface_ptr);
00525 
00526     return 0;
00527 }
00528 
00529 int8_t reassembly_interface_reset(int8_t interface_id)
00530 {
00531     //Discover
00532     reassembly_interface_t *interface_ptr = reassembly_interface_discover(interface_id);
00533     if (!interface_ptr) {
00534         return -1;
00535     }
00536 
00537     //Free Reaasembled queue
00538     reassembly_list_free(interface_ptr);
00539     return 0;
00540 }
00541