uspace/srv/net/inetsrv/reass.c

   1 /*
   2  * Copyright (c) 2012 Jiri Svoboda
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup inet
  30  * @{
  31  */
  32 /**
  33  * @file
  34  * @brief Datagram reassembly.
  35  */
  36
  37 #include <errno.h>
  38 #include <fibril_synch.h>
  39 #include <io/log.h>
  40 #include <macros.h>
  41 #include <mem.h>
  42 #include <stdlib.h>
  43
  44 #include "inetsrv.h"
  45 #include "inet_std.h"
  46 #include "reass.h"
  47
  48 /** Datagram being reassembled.
  49  *
  50  * Uniquely identified by (source address, destination address, protocol,
  51  * identification) per RFC 791 sec. 2.3 / Fragmentation.
  52  */
  53 typedef struct {
  54         link_t map_link;
  55         /** List of fragments, @c reass_frag_t */
  56         list_t frags;
  57 } reass_dgram_t;
  58
  59 /** One datagram fragment */
  60 typedef struct {
  61         link_t dgram_link;
  62         inet_packet_t packet;
  63 } reass_frag_t;
  64
  65 /** Datagram map, list of reass_dgram_t */
  66 static LIST_INITIALIZE(reass_dgram_map);
  67 /** Protects access to @c reass_dgram_map */
  68 static FIBRIL_MUTEX_INITIALIZE(reass_dgram_map_lock);
  69
  70 static reass_dgram_t *reass_dgram_new(void);
  71 static reass_dgram_t *reass_dgram_get(inet_packet_t *);
  72 static int reass_dgram_insert_frag(reass_dgram_t *, inet_packet_t *);
  73 static bool reass_dgram_complete(reass_dgram_t *);
  74 static void reass_dgram_remove(reass_dgram_t *);
  75 static int reass_dgram_deliver(reass_dgram_t *);
  76 static void reass_dgram_destroy(reass_dgram_t *);
  77
  78 /** Queue packet for datagram reassembly.
  79  *
  80  * @param packet        Packet
  81  * @return              EOK on success or ENOMEM.
  82  */
  83 int inet_reass_queue_packet(inet_packet_t *packet)
  84 {
  85         reass_dgram_t *rdg;
  86         int rc;
  87
  88         log_msg(LOG_DEFAULT, LVL_DEBUG, "inet_reass_queue_packet()");
  89
  90         fibril_mutex_lock(&reass_dgram_map_lock);
  91
  92         /* Get existing or new datagram */
  93         rdg = reass_dgram_get(packet);
  94         if (rdg == NULL) {
  95                 /* Only happens when we are out of memory */
  96                 fibril_mutex_unlock(&reass_dgram_map_lock);
  97                 log_msg(LOG_DEFAULT, LVL_DEBUG, "Allocation failed, packet dropped.");
  98                 return ENOMEM;
  99         }
 100
 101         /* Insert fragment into the datagram */
 102         rc = reass_dgram_insert_frag(rdg, packet);
 103         if (rc != EOK)
 104                 return ENOMEM;
 105
 106         /* Check if datagram is complete */
 107         if (reass_dgram_complete(rdg)) {
 108                 /* Remove it from the map */
 109                 reass_dgram_remove(rdg);
 110                 fibril_mutex_unlock(&reass_dgram_map_lock);
 111
 112                 /* Deliver complete datagram */
 113                 rc = reass_dgram_deliver(rdg);
 114                 reass_dgram_destroy(rdg);
 115                 return rc;
 116         }
 117
 118         fibril_mutex_unlock(&reass_dgram_map_lock);
 119         return EOK;
 120 }
 121
 122 /** Get datagram reassembly structure for packet.
 123  *
 124  * @param packet        Packet
 125  * @return              Datagram reassembly structure matching @a packet
 126  */
 127 static reass_dgram_t *reass_dgram_get(inet_packet_t *packet)
 128 {
 129         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 130
 131         list_foreach(reass_dgram_map, link) {
 132                 reass_dgram_t *rdg = list_get_instance(link, reass_dgram_t,
 133                     map_link);
 134
 135                 link_t *f1_link = list_first(&rdg->frags);
 136                 assert(f1_link != NULL);
 137
 138                 reass_frag_t *f1 = list_get_instance(f1_link, reass_frag_t,
 139                     dgram_link);
 140
 141                 if (f1->packet.src.ipv4 == packet->src.ipv4 &&
 142                     f1->packet.dest.ipv4 == packet->dest.ipv4 &&
 143                     f1->packet.proto == packet->proto &&
 144                     f1->packet.ident == packet->ident) {
 145                         /* Match */
 146                         return rdg;
 147                 }
 148         }
 149
 150         /* No existing reassembly structure. Create a new one. */
 151         return reass_dgram_new();
 152 }
 153
 154 /** Create new datagram reassembly structure.
 155  *
 156  * @return New datagram reassembly structure.
 157  */
 158 static reass_dgram_t *reass_dgram_new(void)
 159 {
 160         reass_dgram_t *rdg;
 161
 162         rdg = calloc(1, sizeof(reass_dgram_t));
 163         if (rdg == NULL)
 164                 return NULL;
 165
 166         link_initialize(&rdg->map_link);
 167         list_initialize(&rdg->frags);
 168
 169         return rdg;
 170 }
 171
 172 static reass_frag_t *reass_frag_new(void)
 173 {
 174         reass_frag_t *frag;
 175
 176         frag = calloc(1, sizeof(reass_frag_t));
 177         if (frag == NULL)
 178                 return NULL;
 179
 180         link_initialize(&frag->dgram_link);
 181
 182         return frag;
 183 }
 184
 185 static int reass_dgram_insert_frag(reass_dgram_t *rdg, inet_packet_t *packet)
 186 {
 187         reass_frag_t *frag;
 188         void *data_copy;
 189         link_t *link;
 190
 191         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 192
 193         frag = reass_frag_new();
 194
 195         /* Clone the packet */
 196
 197         data_copy = malloc(packet->size);
 198         if (data_copy == NULL)
 199                 return ENOMEM;
 200
 201         frag->packet = *packet;
 202         frag->packet.data = data_copy;
 203
 204         /*
 205          * XXX Make resource-consuming attacks harder, eliminate any duplicate
 206          * data immediately. Possibly eliminate redundant packet headers.
 207          */
 208
 209         /*
 210          * Insert into the list, which is sorted by offs member ascending.
 211          */
 212
 213         link = list_first(&rdg->frags);
 214         while (link != NULL) {
 215                 reass_frag_t *qf = list_get_instance(link, reass_frag_t,
 216                     dgram_link);
 217
 218                 if (qf->packet.offs >= packet->offs)
 219                         break;
 220
 221                 link = link->next;
 222         }
 223
 224         if (link != NULL)
 225                 list_insert_after(&frag->dgram_link, link);
 226         else
 227                 list_append(&frag->dgram_link, &rdg->frags);
 228
 229         return EOK;
 230 }
 231
 232 /** Check if datagram is complete.
 233  *
 234  * @param rdg           Datagram reassembly structure
 235  * @return              @c true if complete, @c false if not
 236  */
 237 static bool reass_dgram_complete(reass_dgram_t *rdg)
 238 {
 239         reass_frag_t *frag, *prev;
 240         link_t *link;
 241
 242         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 243         assert(!list_empty(&rdg->frags));
 244
 245         /* First fragment must be at offset zero */
 246         frag = list_get_instance(list_first(&rdg->frags), reass_frag_t,
 247             dgram_link);
 248         if (frag->packet.offs != 0)
 249                 return false;
 250
 251         prev = frag;
 252         while (true) {
 253                 link = frag->dgram_link.next;
 254                 if (link == NULL)
 255                         return false;
 256
 257                 /* Each next fragment must follow immediately or overlap */
 258                 frag = list_get_instance(link, reass_frag_t, dgram_link);
 259                 if (frag->packet.offs > prev->packet.offs + prev->packet.size)
 260                         return false;
 261
 262                 /* No more fragments - datagram is complete */
 263                 if (!frag->packet.mf)
 264                         return true;
 265
 266                 prev = frag;
 267         }
 268
 269         return false;
 270 }
 271
 272 /** Remove datagram from reassembly map.
 273  *
 274  * @param rdg           Datagram reassembly structure
 275  */
 276 static void reass_dgram_remove(reass_dgram_t *rdg)
 277 {
 278         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 279         list_remove(&rdg->map_link);
 280 }
 281
 282 /** Deliver complete datagram.
 283  *
 284  * @param rdg           Datagram reassembly structure.
 285  */
 286 static int reass_dgram_deliver(reass_dgram_t *rdg)
 287 {
 288         size_t dgram_size;
 289         size_t fragoff_limit;
 290         inet_dgram_t dgram;
 291         reass_frag_t *frag;
 292         uint8_t proto;
 293
 294         /*
 295          * Potentially there could be something beyond the first packet
 296          * that has !MF. Make sure we ignore that.
 297          */
 298         frag = NULL;
 299         list_foreach(rdg->frags, link) {
 300                 frag = list_get_instance(link, reass_frag_t, dgram_link);
 301
 302                 if (!frag->packet.mf)
 303                         break;
 304         }
 305
 306         assert(frag != NULL);
 307         assert(!frag->packet.mf);
 308
 309         dgram_size = frag->packet.offs + frag->packet.size;
 310
 311         /* Upper bound for fragment offset field */
 312         fragoff_limit = 1 << (FF_FRAGOFF_h - FF_FRAGOFF_l);
 313
 314         /* Verify that total size of datagram is within reasonable bounds */
 315         if (dgram_size > FRAG_OFFS_UNIT * fragoff_limit)
 316                 return ELIMIT;
 317
 318         dgram.data = calloc(dgram_size, 1);
 319         if (dgram.data == NULL)
 320                 return ENOMEM;
 321
 322         dgram.size = dgram_size;
 323         dgram.src = frag->packet.src;
 324         dgram.dest = frag->packet.dest;
 325         dgram.tos = frag->packet.tos;
 326         proto = frag->packet.proto;
 327
 328         /* Pull together data from individual fragments */
 329
 330         size_t doffs = 0;
 331
 332         frag = NULL;
 333         list_foreach(rdg->frags, link) {
 334                 frag = list_get_instance(link, reass_frag_t, dgram_link);
 335
 336                 size_t cb, ce;
 337
 338                 cb = max(doffs, frag->packet.offs);
 339                 ce = min(dgram_size, frag->packet.offs + frag->packet.size);
 340
 341                 if (ce > cb) {
 342                         memcpy(dgram.data + cb,
 343                             frag->packet.data + cb - frag->packet.offs,
 344                             ce - cb);
 345                 }
 346
 347                 if (!frag->packet.mf)
 348                         break;
 349         }
 350
 351         return inet_recv_dgram_local(&dgram, proto);
 352 }
 353
 354 /** Destroy datagram reassembly structure.
 355  *
 356  * @param rdg           Datagram reassembly structure.
 357  */
 358 static void reass_dgram_destroy(reass_dgram_t *rdg)
 359 {
 360         while (!list_empty(&rdg->frags)) {
 361                 link_t *flink = list_first(&rdg->frags);
 362                 reass_frag_t *frag = list_get_instance(flink, reass_frag_t,
 363                     dgram_link);
 364
 365                 list_remove(&frag->dgram_link);
 366                 free(frag->packet.data);
 367                 free(frag);
 368         }
 369
 370         free(rdg);
 371 }
 372
 373 /** @}
 374  */