/*
 * 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);
}

/** @}
 */