source: mainline/uspace/srv/net/inetsrv/reass.c

/*
 * Copyright (c) 2012 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup inet
 * @{
 */
/**
 * @file
 * @brief Datagram reassembly.
 */

#include <errno.h>
#include <fibril_synch.h>
#include <io/log.h>
#include <macros.h>
#include <mem.h>
#include <stdlib.h>

#include "inetsrv.h"
#include "inet_std.h"
#include "reass.h"

/** Datagram being reassembled.
 *
 * Uniquely identified by (source address, destination address, protocol,
 * identification) per RFC 791 sec. 2.3 / Fragmentation.
 */
typedef struct {
        link_t map_link;
        /** List of fragments, @c reass_frag_t */
        list_t frags;
} reass_dgram_t;

/** One datagram fragment */
typedef struct {
        link_t dgram_link;
        inet_packet_t packet;
} reass_frag_t;

/** Datagram map, list of reass_dgram_t */
static LIST_INITIALIZE(reass_dgram_map);
/** Protects access to @c reass_dgram_map */
static FIBRIL_MUTEX_INITIALIZE(reass_dgram_map_lock);

static reass_dgram_t *reass_dgram_new(void);
static reass_dgram_t *reass_dgram_get(inet_packet_t *);
static errno_t reass_dgram_insert_frag(reass_dgram_t *, inet_packet_t *);
static bool reass_dgram_complete(reass_dgram_t *);
static void reass_dgram_remove(reass_dgram_t *);
static errno_t reass_dgram_deliver(reass_dgram_t *);
static void reass_dgram_destroy(reass_dgram_t *);

/** Queue packet for datagram reassembly.
 *
 * @param packet        Packet
 * @return              EOK on success or ENOMEM.
 */
errno_t inet_reass_queue_packet(inet_packet_t *packet)
{
        reass_dgram_t *rdg;
        errno_t rc;

        log_msg(LOG_DEFAULT, LVL_DEBUG, "inet_reass_queue_packet()");

        fibril_mutex_lock(&reass_dgram_map_lock);

        /* Get existing or new datagram */
        rdg = reass_dgram_get(packet);
        if (rdg == NULL) {
                /* Only happens when we are out of memory */
                fibril_mutex_unlock(&reass_dgram_map_lock);
                log_msg(LOG_DEFAULT, LVL_DEBUG, "Allocation failed, packet dropped.");
                return ENOMEM;
        }

        /* Insert fragment into the datagram */
        rc = reass_dgram_insert_frag(rdg, packet);
        if (rc != EOK)
                return ENOMEM;

        /* Check if datagram is complete */
        if (reass_dgram_complete(rdg)) {
                /* Remove it from the map */
                reass_dgram_remove(rdg);
                fibril_mutex_unlock(&reass_dgram_map_lock);

                /* Deliver complete datagram */
                rc = reass_dgram_deliver(rdg);
                reass_dgram_destroy(rdg);
                return rc;
        }

        fibril_mutex_unlock(&reass_dgram_map_lock);
        return EOK;
}

/** Get datagram reassembly structure for packet.
 *
 * @param packet        Packet
 * @return              Datagram reassembly structure matching @a packet
 */
static reass_dgram_t *reass_dgram_get(inet_packet_t *packet)
{
        assert(fibril_mutex_is_locked(&reass_dgram_map_lock));

        list_foreach(reass_dgram_map, map_link, reass_dgram_t, rdg) {
                link_t *f1_link = list_first(&rdg->frags);
                assert(f1_link != NULL);

                reass_frag_t *f1 = list_get_instance(f1_link, reass_frag_t,
                    dgram_link);

                if ((inet_addr_compare(&f1->packet.src, &packet->src)) &&
                    (inet_addr_compare(&f1->packet.dest, &packet->dest)) &&
                    (f1->packet.proto == packet->proto) &&
                    (f1->packet.ident == packet->ident)) {
                        /* Match */
                        return rdg;
                }
        }

        /* No existing reassembly structure. Create a new one. */
        return reass_dgram_new();
}

/** Create new datagram reassembly structure.
 *
 * @return New datagram reassembly structure.
 */
static reass_dgram_t *reass_dgram_new(void)
{
        reass_dgram_t *rdg;

        rdg = calloc(1, sizeof(reass_dgram_t));
        if (rdg == NULL)
                return NULL;

        list_append(&rdg->map_link, &reass_dgram_map);
        list_initialize(&rdg->frags);

        return rdg;
}

static reass_frag_t *reass_frag_new(void)
{
        reass_frag_t *frag;

        frag = calloc(1, sizeof(reass_frag_t));
        if (frag == NULL)
                return NULL;

        link_initialize(&frag->dgram_link);

        return frag;
}

static errno_t reass_dgram_insert_frag(reass_dgram_t *rdg, inet_packet_t *packet)
{
        reass_frag_t *frag;
        void *data_copy;
        link_t *link;

        assert(fibril_mutex_is_locked(&reass_dgram_map_lock));

        frag = reass_frag_new();

        /* Clone the packet */

        data_copy = malloc(packet->size);
        if (data_copy == NULL) {
                free(frag);
                return ENOMEM;
        }

        memcpy(data_copy, packet->data, packet->size);

        frag->packet = *packet;
        frag->packet.data = data_copy;

        /*
         * XXX Make resource-consuming attacks harder, eliminate any duplicate
         * data immediately. Possibly eliminate redundant packet headers.
         */

        /*
         * Insert into the list, which is sorted by offs member ascending.
         */

        link = list_first(&rdg->frags);
        while (link != NULL) {
                reass_frag_t *qf = list_get_instance(link, reass_frag_t,
                    dgram_link);

                if (qf->packet.offs >= packet->offs)
                        break;

                link = list_next(link, &rdg->frags);
        }

        if (link != NULL)
                list_insert_after(&frag->dgram_link, link);
        else
                list_append(&frag->dgram_link, &rdg->frags);

        return EOK;
}

/** Check if datagram is complete.
 *
 * @param rdg           Datagram reassembly structure
 * @return              @c true if complete, @c false if not
 */
static bool reass_dgram_complete(reass_dgram_t *rdg)
{
        reass_frag_t *frag, *prev;
        link_t *link;

        assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
        assert(!list_empty(&rdg->frags));

        link = list_first(&rdg->frags);
        assert(link != NULL);

        frag = list_get_instance(link, reass_frag_t,
            dgram_link);

        /* First fragment must be at offset zero */
        if (frag->packet.offs != 0)
                return false;

        prev = frag;

        while (true) {
                link = list_next(link, &rdg->frags);
                if (link == NULL)
                        break;

                /* Each next fragment must follow immediately or overlap */
                frag = list_get_instance(link, reass_frag_t, dgram_link);
                if (frag->packet.offs > prev->packet.offs + prev->packet.size)
                        return false;

                /* No more fragments - datagram is complete */
                if (!frag->packet.mf)
                        return true;

                prev = frag;
        }

        return false;
}

/** Remove datagram from reassembly map.
 *
 * @param rdg           Datagram reassembly structure
 */
static void reass_dgram_remove(reass_dgram_t *rdg)
{
        assert(fibril_mutex_is_locked(&reass_dgram_map_lock));
        list_remove(&rdg->map_link);
}

/** Deliver complete datagram.
 *
 * @param rdg           Datagram reassembly structure.
 */
static errno_t reass_dgram_deliver(reass_dgram_t *rdg)
{
        size_t dgram_size;
        size_t fragoff_limit;
        inet_dgram_t dgram;
        uint8_t proto;
        reass_frag_t *frag;
        errno_t rc;

        /*
         * Potentially there could be something beyond the first packet
         * that has !MF. Make sure we ignore that.
         */
        frag = NULL;
        list_foreach(rdg->frags, dgram_link, reass_frag_t, cfrag) {
                if (!cfrag->packet.mf) {
                        frag = cfrag;
                        break;
                }
        }

        assert(frag != NULL);
        assert(!frag->packet.mf);

        dgram_size = frag->packet.offs + frag->packet.size;

        /* Upper bound for fragment offset field */
        fragoff_limit = 1 << (FF_FRAGOFF_h - FF_FRAGOFF_l + 1);

        /* Verify that total size of datagram is within reasonable bounds */
        if (dgram_size > FRAG_OFFS_UNIT * fragoff_limit)
                return ELIMIT;

        dgram.data = calloc(dgram_size, 1);
        if (dgram.data == NULL)
                return ENOMEM;

        /* XXX What if different fragments came from different link? */
        dgram.iplink = frag->packet.link_id;
        dgram.size = dgram_size;
        dgram.src = frag->packet.src;
        dgram.dest = frag->packet.dest;
        dgram.tos = frag->packet.tos;
        proto = frag->packet.proto;

        /* Pull together data from individual fragments */

        size_t doffs = 0;

        list_foreach(rdg->frags, dgram_link, reass_frag_t, cfrag) {
                size_t cb, ce;

                cb = max(doffs, cfrag->packet.offs);
                ce = min(dgram_size, cfrag->packet.offs + cfrag->packet.size);

                if (ce > cb) {
                        memcpy(dgram.data + cb,
                            cfrag->packet.data + cb - cfrag->packet.offs,
                            ce - cb);
                }

                if (!cfrag->packet.mf)
                        break;
        }

        rc = inet_recv_dgram_local(&dgram, proto);
        free(dgram.data);
        return rc;
}

/** Destroy datagram reassembly structure.
 *
 * @param rdg           Datagram reassembly structure.
 */
static void reass_dgram_destroy(reass_dgram_t *rdg)
{
        while (!list_empty(&rdg->frags)) {
                link_t *flink = list_first(&rdg->frags);
                reass_frag_t *frag = list_get_instance(flink, reass_frag_t,
                    dgram_link);

                list_remove(&frag->dgram_link);
                free(frag->packet.data);
                free(frag);
        }

        free(rdg);
}

/** @}
 */