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 errno_t 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 errno_t 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 errno_t inet_reass_queue_packet(inet_packet_t *packet)
  84 {
  85         reass_dgram_t *rdg;
  86         errno_t 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, map_link, reass_dgram_t, rdg) {
 132                 link_t *f1_link = list_first(&rdg->frags);
 133                 assert(f1_link != NULL);
 134
 135                 reass_frag_t *f1 = list_get_instance(f1_link, reass_frag_t,
 136                     dgram_link);
 137
 138                 if ((inet_addr_compare(&f1->packet.src, &packet->src)) &&
 139                     (inet_addr_compare(&f1->packet.dest, &packet->dest)) &&
 140                     (f1->packet.proto == packet->proto) &&
 141                     (f1->packet.ident == packet->ident)) {
 142                         /* Match */
 143                         return rdg;
 144                 }
 145         }
 146
 147         /* No existing reassembly structure. Create a new one. */
 148         return reass_dgram_new();
 149 }
 150
 151 /** Create new datagram reassembly structure.
 152  *
 153  * @return New datagram reassembly structure.
 154  */
 155 static reass_dgram_t *reass_dgram_new(void)
 156 {
 157         reass_dgram_t *rdg;
 158
 159         rdg = calloc(1, sizeof(reass_dgram_t));
 160         if (rdg == NULL)
 161                 return NULL;
 162
 163         list_append(&rdg->map_link, &reass_dgram_map);
 164         list_initialize(&rdg->frags);
 165
 166         return rdg;
 167 }
 168
 169 static reass_frag_t *reass_frag_new(void)
 170 {
 171         reass_frag_t *frag;
 172
 173         frag = calloc(1, sizeof(reass_frag_t));
 174         if (frag == NULL)
 175                 return NULL;
 176
 177         link_initialize(&frag->dgram_link);
 178
 179         return frag;
 180 }
 181
 182 static errno_t reass_dgram_insert_frag(reass_dgram_t *rdg, inet_packet_t *packet)
 183 {
 184         reass_frag_t *frag;
 185         void *data_copy;
 186         link_t *link;
 187
 188         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 189
 190         frag = reass_frag_new();
 191
 192         /* Clone the packet */
 193
 194         data_copy = malloc(packet->size);
 195         if (data_copy == NULL) {
 196                 free(frag);
 197                 return ENOMEM;
 198         }
 199
 200         memcpy(data_copy, packet->data, packet->size);
 201
 202         frag->packet = *packet;
 203         frag->packet.data = data_copy;
 204
 205         /*
 206          * XXX Make resource-consuming attacks harder, eliminate any duplicate
 207          * data immediately. Possibly eliminate redundant packet headers.
 208          */
 209
 210         /*
 211          * Insert into the list, which is sorted by offs member ascending.
 212          */
 213
 214         link = list_first(&rdg->frags);
 215         while (link != NULL) {
 216                 reass_frag_t *qf = list_get_instance(link, reass_frag_t,
 217                     dgram_link);
 218
 219                 if (qf->packet.offs >= packet->offs)
 220                         break;
 221
 222                 link = list_next(link, &rdg->frags);
 223         }
 224
 225         if (link != NULL)
 226                 list_insert_after(&frag->dgram_link, link);
 227         else
 228                 list_append(&frag->dgram_link, &rdg->frags);
 229
 230         return EOK;
 231 }
 232
 233 /** Check if datagram is complete.
 234  *
 235  * @param rdg           Datagram reassembly structure
 236  * @return              @c true if complete, @c false if not
 237  */
 238 static bool reass_dgram_complete(reass_dgram_t *rdg)
 239 {
 240         reass_frag_t *frag, *prev;
 241         link_t *link;
 242
 243         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 244         assert(!list_empty(&rdg->frags));
 245
 246         link = list_first(&rdg->frags);
 247         assert(link != NULL);
 248
 249         frag = list_get_instance(link, reass_frag_t,
 250             dgram_link);
 251
 252         /* First fragment must be at offset zero */
 253         if (frag->packet.offs != 0)
 254                 return false;
 255
 256         prev = frag;
 257
 258         while (true) {
 259                 link = list_next(link, &rdg->frags);
 260                 if (link == NULL)
 261                         break;
 262
 263                 /* Each next fragment must follow immediately or overlap */
 264                 frag = list_get_instance(link, reass_frag_t, dgram_link);
 265                 if (frag->packet.offs > prev->packet.offs + prev->packet.size)
 266                         return false;
 267
 268                 /* No more fragments - datagram is complete */
 269                 if (!frag->packet.mf)
 270                         return true;
 271
 272                 prev = frag;
 273         }
 274
 275         return false;
 276 }
 277
 278 /** Remove datagram from reassembly map.
 279  *
 280  * @param rdg           Datagram reassembly structure
 281  */
 282 static void reass_dgram_remove(reass_dgram_t *rdg)
 283 {
 284         assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
 285         list_remove(&rdg->map_link);
 286 }
 287
 288 /** Deliver complete datagram.
 289  *
 290  * @param rdg           Datagram reassembly structure.
 291  */
 292 static errno_t reass_dgram_deliver(reass_dgram_t *rdg)
 293 {
 294         size_t dgram_size;
 295         size_t fragoff_limit;
 296         inet_dgram_t dgram;
 297         uint8_t proto;
 298         reass_frag_t *frag;
 299         errno_t rc;
 300
 301         /*
 302          * Potentially there could be something beyond the first packet
 303          * that has !MF. Make sure we ignore that.
 304          */
 305         frag = NULL;
 306         list_foreach(rdg->frags, dgram_link, reass_frag_t, cfrag) {
 307                 if (!cfrag->packet.mf) {
 308                         frag = cfrag;
 309                         break;
 310                 }
 311         }
 312
 313         assert(frag != NULL);
 314         assert(!frag->packet.mf);
 315
 316         dgram_size = frag->packet.offs + frag->packet.size;
 317
 318         /* Upper bound for fragment offset field */
 319         fragoff_limit = 1 << (FF_FRAGOFF_h - FF_FRAGOFF_l + 1);
 320
 321         /* Verify that total size of datagram is within reasonable bounds */
 322         if (dgram_size > FRAG_OFFS_UNIT * fragoff_limit)
 323                 return ELIMIT;
 324
 325         dgram.data = calloc(dgram_size, 1);
 326         if (dgram.data == NULL)
 327                 return ENOMEM;
 328
 329         /* XXX What if different fragments came from different link? */
 330         dgram.iplink = frag->packet.link_id;
 331         dgram.size = dgram_size;
 332         dgram.src = frag->packet.src;
 333         dgram.dest = frag->packet.dest;
 334         dgram.tos = frag->packet.tos;
 335         proto = frag->packet.proto;
 336
 337         /* Pull together data from individual fragments */
 338
 339         size_t doffs = 0;
 340
 341         list_foreach(rdg->frags, dgram_link, reass_frag_t, cfrag) {
 342                 size_t cb, ce;
 343
 344                 cb = max(doffs, cfrag->packet.offs);
 345                 ce = min(dgram_size, cfrag->packet.offs + cfrag->packet.size);
 346
 347                 if (ce > cb) {
 348                         memcpy(dgram.data + cb,
 349                             cfrag->packet.data + cb - cfrag->packet.offs,
 350                             ce - cb);
 351                 }
 352
 353                 if (!cfrag->packet.mf)
 354                         break;
 355         }
 356
 357         rc = inet_recv_dgram_local(&dgram, proto);
 358         free(dgram.data);
 359         return rc;
 360 }
 361
 362 /** Destroy datagram reassembly structure.
 363  *
 364  * @param rdg           Datagram reassembly structure.
 365  */
 366 static void reass_dgram_destroy(reass_dgram_t *rdg)
 367 {
 368         while (!list_empty(&rdg->frags)) {
 369                 link_t *flink = list_first(&rdg->frags);
 370                 reass_frag_t *frag = list_get_instance(flink, reass_frag_t,
 371                     dgram_link);
 372
 373                 list_remove(&frag->dgram_link);
 374                 free(frag->packet.data);
 375                 free(frag);
 376         }
 377
 378         free(rdg);
 379 }
 380
 381 /** @}
 382  */