/*
 * Copyright (c) 2001-2022 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
 *
 * This software is available to you under a choice of one of two
 * licenses.  You may choose to be licensed under the terms of the GNU
 * General Public License (GPL) Version 2, available from the file
 * COPYING in the main directory of this source tree, or the
 * BSD license below:
 *
 *     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 SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */


#include "ip_frag.h"

#include <assert.h>
#include <list>
#include "utils/bullseye.h"
#include "vma/event/event_handler_manager.h"
#include "mem_buf_desc.h"

//#define IP_FRAG_DEBUG 1

#ifdef IP_FRAG_DEBUG
#define frag_dbg(fmt, args...) \
	vlog_printf(VLOG_WARNING, "%s:%d : " fmt "\n", __FUNCTION__, __LINE__,  ##args)
#else
#define frag_dbg(fmt, args...)
#endif

#define frag_err(fmt, args...) \
	vlog_printf(VLOG_ERROR, "%s:%d : " fmt "\n", __FUNCTION__, __LINE__,  ##args)

#define frag_panic(fmt, args...) \
	do { vlog_printf(VLOG_PANIC, "%s:%d : " fmt "\n", __FUNCTION__, __LINE__,  ##args); throw; } while (0)


#ifdef IP_FRAG_DEBUG
static int debug_drop_every_n_pkt=0; // 0 - Disabled, 1/N is the number of packet dropped
static int debug_drop_index=0;       // counter

static int g_ip_frag_count_check = 0;
  #define MEMBUF_DEBUG_REF_INC(__p_desc__)		{g_ip_frag_count_check++; if (__p_desc__->n_ref_count!=0) frag_panic("REF_INC: p=%p\n", __p_desc__); __p_desc__->n_ref_count++;}
  #define MEMBUF_DEBUG_REF_DEC(__p_desc__)      	{mem_buf_desc_t* frag_list = __p_desc__; while (frag_list) { MEMBUF_DEBUG_REF_DEC_1(frag_list); frag_list = frag_list->p_next_desc; }}
  #define MEMBUF_DEBUG_REF_DEC_1(__p_desc__)		{g_ip_frag_count_check--; __p_desc__->n_ref_count--; if (__p_desc__->n_ref_count!=0) frag_panic("REF_DEC: p=%p\n", __p_desc__);}
  #define PRINT_STATISTICS()				{print_statistics();}
#else
  #define MEMBUF_DEBUG_REF_INC(__p_desc__)
  #define MEMBUF_DEBUG_REF_DEC(__p_desc__)
  #define PRINT_STATISTICS()
#endif


ip_frag_manager * g_p_ip_frag_manager = NULL;

ip_frag_hole_desc *hole_base = NULL;
ip_frag_hole_desc *hole_free_list_head = NULL;
int hole_free_list_count = 0;

ip_frag_desc *desc_base = NULL;
ip_frag_desc *desc_free_list_head = NULL;
int desc_free_list_count = 0;


ip_frag_manager::ip_frag_manager() : lock_spin("ip_frag_manager")
{
	frag_dbg("");
	m_frag_counter = 0;
	int i;

	
	frag_dbg("NOTE: ip frag periodic timer is disabled until HW supports ip frag offload");
	// g_p_event_handler_manager->register_timer_event(IP_FRAG_CLEANUP_INT, this, PERIODIC_TIMER, 0);

	frag_dbg("Created new IPFRAG MANAGER instance");
	/* allocate hole list */
	desc_base = new ip_frag_desc_t [IP_FRAG_MAX_DESC];
	BULLSEYE_EXCLUDE_BLOCK_START
	if (!desc_base) {
		frag_dbg("Failed to allocate descriptor");
		free_frag_resources();
		throw_vma_exception("Failed to allocate descriptor");
	}
	hole_base = new ip_frag_hole_desc [IP_FRAG_MAX_HOLES];
	if (!hole_base) {
		frag_dbg("Failed to allocate hole descriptor");
		free_frag_resources();
		throw_vma_exception("Failed to allocate hole descriptor");
	}
	BULLSEYE_EXCLUDE_BLOCK_END
	for (i = 0; i < IP_FRAG_MAX_DESC; i++) {
		free_frag_desc(&desc_base[i]);
	}
	for (i = 0; i < IP_FRAG_MAX_HOLES; i++) {
		free_hole_desc(&hole_base[i]);
	}
}

void ip_frag_manager::free_frag_resources(void)
{

        ip_frags_list_t::iterator i;
	ip_frag_desc_t *desc;

	frag_dbg("NOTE: ip frag periodic timer is disabled until HW supports ip frag offload");
	// g_p_event_handler_manager->unregister_timer_event(this, NULL);

	lock();

	while (m_frags.size() > 0) {
		i = m_frags.begin();
		desc = i->second;
		destroy_frag_desc(desc);
		free_frag_desc(desc);
		m_frags.erase(i);
	}

	owner_desc_map_t temp_buff_map = m_return_descs;
	m_return_descs.clear();

	unlock();

	// Must call cq_mgr outside the lock to avoid ABBA deadlock
	return_buffers_to_owners(temp_buff_map);

	delete [] desc_base;
	delete [] hole_base;
	frag_dbg("Deleted IPFRAG MANAGER instance");
}

ip_frag_manager::~ip_frag_manager()
{
	free_frag_resources();
}

#if _BullseyeCoverage
    #pragma BullseyeCoverage off
#endif

void ip_frag_manager::print_statistics()
{
	frag_dbg("free desc=%d, free holes=%d, map size=%d, frags=%d", desc_free_list_count, hole_free_list_count, m_frags.size(), g_ip_frag_count_check);
}

void ip_frag_manager::free_frag(mem_buf_desc_t *frag)
{
	mem_buf_desc_t *tail;

	// There are cases that we might not have a frag list at all to release
	// This is instead of checking the pointer before all calls to free_frag()
	if (!frag)
		return;

	// Change packet size - it will force packet to be discarded
	frag->sz_data = IP_FRAG_FREED;

	// Return to owner does post_recv() which deals with linked buffers automatically
	MEMBUF_DEBUG_REF_DEC(frag);

	tail = frag;
	while (tail->p_next_desc) {
		tail = tail->p_next_desc;
	}
	tail->p_next_desc = m_return_descs[frag->p_desc_owner];
	m_return_descs[frag->p_desc_owner] = frag;

}


//FIXME: use preallocated descriptors!!! instead of malloc
ip_frag_hole_desc* ip_frag_manager::alloc_hole_desc()
{
	struct ip_frag_hole_desc *ret;
	ret = hole_free_list_head;
	if (!ret)
		return NULL;

	// unlink from hole's free list
	hole_free_list_head = ret->next;
	hole_free_list_count--;

	// clear hole struct
	ret->data_first = 0;
	ret->data_last  = 0;
	ret->next = 0;
	return ret;
}

void ip_frag_manager::free_hole_desc(struct ip_frag_hole_desc *p)
{
	// link in head of free list
	p->next = hole_free_list_head;
	hole_free_list_head = p;
	++hole_free_list_count;
}

ip_frag_desc_t *ip_frag_manager::alloc_frag_desc()
{
	ip_frag_desc_t *ret;
	ret = desc_free_list_head;
	if (!ret)
		return NULL;

	// unlink from hole's free list
	desc_free_list_head = ret->next;
	--desc_free_list_count;

	ret->next = 0;
	return ret;
}

void ip_frag_manager::free_frag_desc(ip_frag_desc_t *p)
{
	// link in head of free list
	p->next = desc_free_list_head;
	desc_free_list_head = p;
	desc_free_list_count++;
}

void ip_frag_manager::destroy_frag_desc(ip_frag_desc_t *desc)
{
	struct ip_frag_hole_desc *phole, *pphole;

	// free holes
	phole = desc->hole_list;
	while (phole) {
		pphole = phole;
		phole = phole->next;
		free_hole_desc(pphole);
	}

	// free frags
	free_frag(desc->frag_list);
}


/**
 * first fragment for given address is detected - setup
 */
ip_frag_desc_t *ip_frag_manager::new_frag_desc(ip_frag_key_t &key)
{
	ip_frag_desc_t *desc = NULL;
	struct ip_frag_hole_desc *hole = NULL;

	hole = alloc_hole_desc();
	if (!hole){
		frag_dbg("NULL hole");
		return NULL;
	}
	hole->first = IP_FRAG_NINF;
	hole->last  = IP_FRAG_INF;

	desc = alloc_frag_desc();
	if (!desc) {
		frag_dbg("NULL desc");
		free_hole_desc(hole);
		return NULL;
	}
	desc->ttl = IP_FRAG_TTL;
	desc->frag_list = 0;
	desc->hole_list = hole;
	desc->frag_counter = m_frag_counter;

	m_frags[key]  = desc;
	return desc;
}

/**
 * Complexity of the algorithm:
 * O(1) if packets are coming in order or reverse order
 * O(n^2) for random fragments, where n is number of fragments
 * returns: 0 if finished OK (if the packet is complete - put it in ret)
 * 		   -1 if finished not OK and this packet needs to be droped
 */
int ip_frag_manager::add_frag(iphdr *hdr, mem_buf_desc_t *frag, mem_buf_desc_t **ret)
{
	ip_frag_key_t key;
	ip_frags_list_t::iterator i;
	ip_frag_desc_t *desc;
	struct ip_frag_hole_desc *phole, *phole_prev;
	struct ip_frag_hole_desc *new_hole;
	uint16_t frag_off, frag_first, frag_last;
	bool more_frags;

	assert(hdr);
	assert(frag);

	key.ip_id       = hdr->id;  //id is in network order!
	key.src_ip      = hdr->saddr;
	key.dst_ip      = hdr->daddr;
	key.ipproto     = hdr->protocol;

	frag_dbg("Fragment: %d.%d.%d.%d->%d.%d.%d.%d id=%x size=%d",
		 NIPQUAD(key.src_ip),
		 NIPQUAD(key.dst_ip),
		 (int)key.ip_id, (int)ntohs(hdr->tot_len));

#ifdef IP_FRAG_DEBUG
	if (debug_drop_every_n_pkt && ((++debug_drop_index) % debug_drop_every_n_pkt == 0)) {
		frag_dbg("XXX debug force dropped XXX");
		return -1;
	}
#endif

	lock();

	MEMBUF_DEBUG_REF_INC(frag);
	PRINT_STATISTICS();

	frag_off = ntohs(hdr->frag_off);
	more_frags = frag_off & MORE_FRAGMENTS_FLAG;
	frag_first = (frag_off & FRAGMENT_OFFSET) * 8;
	frag_last = frag_first + ntohs(hdr->tot_len) - (hdr->ihl<<2) - 1; // frag starts from 0!!!
	frag_dbg("> fragment: %d-%d, %s more frags", frag_first, frag_last, more_frags?"pending":"no");

	m_frag_counter++;

	i = m_frags.find(key);

	if (i == m_frags.end()) {
		/* new fragment */
		frag_dbg("> new fragmented packet");
		desc = new_frag_desc(key);
	}
	else {
		desc = i->second;
		if ((m_frag_counter - desc->frag_counter) > IP_FRAG_SPACE) {
			// discard this packet
			frag_dbg("expiring packet fragments id=%x", i->first);
			destroy_frag_desc(desc);
			free_frag_desc(desc);
			m_frags.erase(i);
			i = m_frags.end();
			// Add new fregment
			frag_dbg("> new fragmented packet");
			desc = new_frag_desc(key);
		}
		else {
			frag_dbg("> old fragmented packet");
	}
	}
	if (desc==NULL) {
		MEMBUF_DEBUG_REF_DEC(frag);
		PRINT_STATISTICS();
		unlock();
		return -1;
	}

	//desc->last_frag_counter = m_frag_counter;

	/* 8 step reassembly algorithm as described in RFC 815 */
	//step 1
	phole_prev = 0; phole = desc->hole_list;
	while (phole) {
		//step 2 and step 3
		if (frag_first >= phole->first && frag_last <= phole->last) {
			break;
		}
		phole_prev = phole;
		phole = phole->next;
	}
	if (!phole) {   // the right hole wasn't found
		MEMBUF_DEBUG_REF_DEC(frag);
		PRINT_STATISTICS();
		unlock();
		return -1;
	}

	frag_dbg("> found hole: %d-%d", phole->first, phole->last);

	// step 4 - remove hole from list
	if (phole_prev)
		phole_prev->next = phole->next;
	else
		desc->hole_list	= phole->next;

	// step 5
	if (frag_first > phole->first) {
		new_hole                = alloc_hole_desc();
		if (!new_hole) {
			free_hole_desc(phole); // phole was removed from the list in step 4!
			MEMBUF_DEBUG_REF_DEC(frag);
			PRINT_STATISTICS();
			unlock();
			return -1;
		}
		new_hole->first         = phole->first;
		new_hole->last          = frag_first-1;
		new_hole->data_first    = phole->data_first;
		new_hole->data_last     = frag;

		new_hole->next = phole->next;
		if (phole_prev)
			phole_prev->next = new_hole;
		else
			desc->hole_list	= new_hole;

		phole_prev = new_hole;
	}

	//step 6
	if (frag_last < phole->last && more_frags) {
		new_hole                = alloc_hole_desc();
		if (!new_hole) {
			free_hole_desc(phole);  // phole was removed from the list in step 4!
			MEMBUF_DEBUG_REF_DEC(frag);
			PRINT_STATISTICS();
			unlock();
			return -1;
		}

		new_hole->first         = frag_last + 1;
		new_hole->last          = phole->last;
		new_hole->data_first    = frag;
		new_hole->data_last     = phole->data_last;

		new_hole->next = phole->next;
		if (phole_prev)
			phole_prev->next = new_hole;
		else
			desc->hole_list	= new_hole;
	}

	// link frag
	if (phole->data_first)
		phole->data_first->p_next_desc = frag;
	else
		desc->frag_list	= frag;
	frag->p_next_desc = phole->data_last;

	free_hole_desc(phole);

	if (!desc->hole_list) {
		//step 8 - datagram assembly completed
		if (i == m_frags.end())
			i = m_frags.find(key);
		if (i == m_frags.end()){
			MEMBUF_DEBUG_REF_DEC(frag);
			frag_panic("frag desc lost from map???");
			//coverity unreachable
			/*unlock();
			return -1;*/
		}
		MEMBUF_DEBUG_REF_DEC(desc->frag_list);
		m_frags.erase(i);
		*ret = desc->frag_list;
		free_frag_desc(desc);
		frag_dbg("> PACKET ASSEMBLED");
		PRINT_STATISTICS();
		unlock();
		return 0;
	}
	frag_dbg("> need more packets");

	*ret = NULL;
	PRINT_STATISTICS();
	unlock();
	return 0;
}

void ip_frag_manager::return_buffers_to_owners(const owner_desc_map_t &buff_map)
{
	// Assume locked !!!
	owner_desc_map_t::const_iterator iter;

	for (iter = buff_map.begin(); iter != buff_map.end(); ++iter) {
		if(g_buffer_pool_rx)
			g_buffer_pool_rx->put_buffers_thread_safe(iter->second);
	}
}


void ip_frag_manager::handle_timer_expired(void* user_data)
{
	NOT_IN_USE(user_data);
	ip_frags_list_t::iterator iter, iter_temp;
	ip_frag_desc_t *desc;
	uint64_t delta =0;

	lock();
	if (m_frag_counter > IP_FRAG_SPACE) {
		delta = m_frag_counter - IP_FRAG_SPACE;
		m_frag_counter -= delta;
	}

	frag_dbg("calling handle_timer_expired, m_frag_counter=%ld, delta=%ld", m_frag_counter, delta);
	PRINT_STATISTICS();

	iter = m_frags.begin();
	while (iter != m_frags.end()) {
		desc = iter->second;
		desc->frag_counter -= delta;
		if (desc->frag_counter<0 || (desc->ttl <= 0)) {	//discard this packet
			frag_dbg("expiring packet fragments desc=%p (frag_counter=%d, ttl=%d)", desc, desc->frag_counter, desc->ttl);
			destroy_frag_desc(desc);
			free_frag_desc(desc);
			iter_temp = iter++;
			m_frags.erase(iter_temp);
		}
		else {
			iter++;
		}

		--desc->ttl;
	}

	owner_desc_map_t temp_buff_map = m_return_descs;
	m_return_descs.clear();

	PRINT_STATISTICS();
	unlock();

	// Must call cq_mgr outside the lock to avoid ABBA deadlock
	return_buffers_to_owners(temp_buff_map);
}

#if _BullseyeCoverage
    #pragma BullseyeCoverage on
#endif
