/*
 * Copyright (c) 2000 Columbia University
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that: (1) source code distributions
 * retain the above copyright notice and this paragraph in its entirety, (2)
 * distributions including binary code include the above copyright notice and
 * this paragraph in its entirety in the documentation or other materials
 * provided with the distribution, and (3) all advertising materials mentioning
 * features or use of this software display the following acknowledgement:
 * ``This product includes software developed by Columbia University
 * and its contributors.'' Neither the name of the University nor the names 
 * of its contributors may be used to endorse or promote products derived 
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Written by Ping Pan, Columbia University, 2000
 *
 * The author would like to thank Bell Labs for providing time and freedom
 * to complete this work. Please forward bug fixes, enhancements and questions
 * to pingpan@cs.columbia.edu.
 */

/* This file is to manage all YESSIR flow tables (all hashed).
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/param.h>
#include <sys/socket.h>
#include <net/if.h>
#include <netinet/in.h>

#include "queue.h"
#include "table.h"
#include "yestat.h"
#include "yes_var.h"


yessirTable	*yestab = NULL;		/* yessir flow table */
yessirTime	*yestime = NULL;	/* soft-state timer table */
RIFM		*rifm = NULL;		/* rif table */

/* YESSIR flow table management:
 *
 * Note: the next few refill/depletion rotuines are used to
 * get/free the buckets for the flow tables. All flow level memeory
 * allocation and free activities take place with these routines.
 * To debug memory related problems (if any), break on the rotines here.
 */

/* init the yessir flow tables: get memory, clean it up,
 * and allocate a fixed number of buckets to all flow tables,
 * yessir flow table, outgoing table, timer table and pending queue.
 */
int
yes_tabinit()
{
	yestab = (yessirTable *)malloc(sizeof(yessirTable));
	if (yestab == NULL) {
		msglog("tabinit: no memory");
		return 0;
	}
	memset((char *)yestab, 0, sizeof(yessirTable));

	if (!yes_refill_ftab(YESSIR_FBL_SIZE) || 
	    !yes_refill_otab(YESSIR_FBL_SIZE) ||
	    !yes_refill_ttab(YESSIR_FBL_SIZE) ||
	    !yes_refill_ptab(YESSIR_FBL_SIZE)) {
		msglog("tabinit: refill failed");
		return 0;
	}
	return -1;
}


/* the routine is called during flow processing...
 * fill up the free bucket pools if below watermark.
 */
int
yestab_refill()
{
	if (yestab->flow_fbl.cnt < YESSIR_FBL_WATERMARK)
		yes_refill_ftab(YESSIR_REFILL_SIZE);

	if (yestab->out_fbl.cnt < YESSIR_FBL_WATERMARK)
		yes_refill_otab(YESSIR_REFILL_SIZE);

	if (yestab->time_fbl.cnt < YESSIR_FBL_WATERMARK)
		yes_refill_ttab(YESSIR_REFILL_SIZE);

	if (yestab->pending_fbl.cnt < YESSIR_FBL_WATERMARK)
		yes_refill_ptab(YESSIR_REFILL_SIZE);

	return -1;
}


/* The next few routines on refill and depletion are pretty much identical.
 * It's designed fort easy tracing and debugging. To reduce the chance of
 * memeory leak etc., all flow entries get and release their memory from here.
 */

/* refill the flow table */
int
yes_refill_ftab(int num)
{
	LIFO		*fbl = (LIFO *)&yestab->flow_fbl;
	yesEntry	*ye;
	int		i;

	yestat->refill_flow_tab++;
	for (i=0; i < num; i++) {
		ye = (yesEntry *)malloc(sizeof(yesEntry));
		if (ye == NULL) {
			yestat->refill_flow_failed++;
			return 0;
		}
		memset((char *)ye, 0, sizeof(yesEntry));
		QA_LIFO(fbl, ye);
		yestab->max_flow++;
	}
	return -1;
}

/* refill the out-going flow table pool... */
int
yes_refill_otab(int num)
{
	LIFO		*fbl = (LIFO *)&yestab->out_fbl;
	yesOutEntry	*yoe;
	int		i;

	yestat->refill_oentry_tab++;
	for (i=0; i < num; i++) {
		yoe = (yesOutEntry *)malloc(sizeof(yesOutEntry));
		if (yoe == NULL) {
			yestat->refill_oentry_failed++;
			return 0;
		}
		memset((char *)yoe, 0, sizeof(yesOutEntry));
		QA_LIFO(fbl, yoe);
		yestab->max_out_entry++;
	}
	return -1;
}


/* refill the timer queue buckes */
int
yes_refill_ttab(int num)
{
	LIFO		*fbl = (LIFO *)&yestab->time_fbl;
	yesTimeEntry	*te;
	int		i;

	yestat->refill_time_tab++;
	for (i=0; i < num; i++) {
		te = (yesTimeEntry *)malloc(sizeof(yesTimeEntry));
		if (te == NULL) {
			yestat->refill_time_failed++;
			return 0;
		}
		memset((char *)te, 0, sizeof(yesTimeEntry));
		QA_LIFO(fbl, te);
		yestab->max_time_entry++;
	}
	return -1;
}


/* refill the pending queue */
int
yes_refill_ptab(int num)
{
	LIFO		*fbl = (LIFO *)&yestab->pending_fbl;
	yesPendingEntry	*pe;
	int		i;

	yestat->refill_pending_tab++;
	for (i=0; i < num; i++) {
		pe = (yesPendingEntry *)malloc(sizeof(yesPendingEntry));
		if (pe == NULL) {
			yestat->refill_pending_failed++;
			return 0;
		}
		memset((char *)pe, 0, sizeof(yesPendingEntry));
		QA_LIFO(fbl, pe);
		yestab->max_pending++;
	}
	return -1;
}


/* reduce the database tables: if we have more than enough of 
 * free buckets, return the extra buckets to the free memory.
 */
int
yestab_deplete()
{
	int	threshold, limit;

	/* prevent refill/depletion looping */
	limit = YESSIR_REFILL_SIZE + YESSIR_FBL_WATERMARK;
	threshold = (limit > YESSIR_FBL_SIZE ? limit : YESSIR_FBL_SIZE);

	if (yestab->flow_fbl.cnt > threshold)
		yes_deplete_ftab(threshold);

	if (yestab->out_fbl.cnt > threshold)
		yes_deplete_otab(threshold);

	if (yestab->time_fbl.cnt > threshold)
		yes_deplete_ttab(threshold);

	if (yestab->pending_fbl.cnt > threshold)
		yes_deplete_ptab(threshold);

	return -1;
}

int
yes_deplete_ftab(int threshold)
{
	LIFO		*fbl = (LIFO *)&yestab->flow_fbl;
	yesEntry	*ye;
	int		i;

	yestat->deplete_flow_tab++;
	for (i=fbl->cnt; i > threshold; i--) {
		QR_LIFO(fbl, threshold, ye);
		if (ye) {
			yestab->max_flow--;
			free(ye);
		}
	}
	return -1;
}

int
yes_deplete_otab(int threshold)
{
	LIFO		*fbl = (LIFO *)&yestab->out_fbl;
	yesOutEntry	*yoe;
	int		i;

	yestat->deplete_oentry_tab++;
	for (i=fbl->cnt; i > threshold; i--) {
		QR_LIFO(fbl, threshold, yoe);
		if (yoe) {
			yestab->max_out_entry--;
			free(yoe);
		}
	}
	return -1;
}

int
yes_deplete_ttab(int threshold)
{
	LIFO		*fbl = (LIFO *)&yestab->time_fbl;
	yesTimeEntry	*yte;
	int		i;

	yestat->deplete_tentry_tab++;
	for (i=fbl->cnt; i > threshold; i--) {
		QR_LIFO(fbl, threshold, yte);
		if (yte) {
			yestab->max_time_entry--;
			free(yte);
		}
	}
	return -1;
}


int
yes_deplete_ptab(int threshold)
{
	LIFO		*fbl = (LIFO *)&yestab->pending_fbl;
	yesPendingEntry	*pe;
	int		i;

	yestat->deplete_pentry_tab++;
	for (i=fbl->cnt; i > threshold; i--) {
		QR_LIFO(fbl, threshold, pe);
		if (pe) {
			yestab->max_pending--;
			free(pe);
		}
	}
	return -1;
}



/*
 * YESSIR entry add/delete/get
 */

yesEntry
*yesget(struct in_addr *da, u_int32_t dp, struct in_addr *sa, u_int32_t sp)
{
	register yesEntry	*tmp_ye, *ye;
	register LIFO		*lifo;
	register int		n;

	n = da->s_addr + dp + sa->s_addr + sp;
	lifo = (LIFO *)&yestab->act_flow[YESSIR_HASH(n)];
	tmp_ye = (yesEntry *)(lifo->head);
	ye = NULL;

	for (ye = tmp_ye, n = 0; n < lifo->cnt; ye = ye->next, n++) {

		if ((ye->id.daddr == da->s_addr) && 
			(ye->id.dport == dp) && 
			(ye->id.saddr == sa->s_addr) && 
			(ye->id.sport == sp)) {
			return ye;
		}
	}
	return NULL;		/* no match */
}


yesEntry
*yesadd(struct in_addr *da, u_int32_t dp, struct in_addr *sa, u_int32_t sp)
{
	register yesEntry	*ye;
	register yesTimeEntry	*yte;
	register LIFO		*dst_hash, *src_hash, *dst_timeq, *src_timeq;
	u_int32_t		n, slot;
	struct timeval  	clk;

	yestab_refill();

	if (yestab->flow_fbl.cnt == 0) {
		yestat->no_memory++;
		return NULL;
	}

	n = da->s_addr + dp + sa->s_addr + sp;
	ye = (yesEntry *)NULL;

	/* get a flow entry */
	dst_hash = (LIFO *)&yestab->act_flow[YESSIR_HASH(n)];
	src_hash = (LIFO *)&yestab->flow_fbl;
	QM_LIFO(src_hash, dst_hash, ye);
	if (!ye) {
		yestat->add_flow_failed++;	/* never happens! */
		return NULL;
	}

	/* get a timer entry */
	timevalsub(&clk, &yestime->now, &yestime->init);
	if (clk.tv_sec < 0) {
		yestat->timer_outsync++;
		return NULL;
	}

	slot = YESSIR_TIMEQ(clk.tv_sec);

	yte = (yesTimeEntry *)NULL;

	dst_timeq = (LIFO *)&yestab->time_table[slot];
	src_timeq = (LIFO *)&yestab->time_fbl;
	QM_LIFO(src_timeq, dst_timeq, yte);

	if (!yte) {
		yestat->add_tentry_failed++;	/* never happens! */
		QM_LIFO(dst_hash, src_hash, ye);
		return NULL;
	}

	ye->id.daddr = da->s_addr;
	ye->id.saddr = sa->s_addr;
	ye->id.dport = dp;
	ye->id.sport = sp;

	ye->time_slot = slot;
	ye->max_round = YESSIR_RETRIES;
	ye->curr_round = 0;
	ye->in_if = 0;
	ye->fhandle = 0;
	ye->egress.cnt = 0;

	yte->yep = (int)ye;

	yestab->curr_flow++;

	return ye;
}


/* delete the flow from the pending queue, and the flow entry itself */
int
yesfree(yesEntry *ye)
{
	struct in_addr da, sa;
	u_int32_t dp, sp;

	da.s_addr = ye->id.daddr;
	sa.s_addr = ye->id.saddr;
	dp = ye->id.dport;
	sp = ye->id.sport;

	yesdel_pending(ye);

	return yesdel(&da, dp, &sa, sp);
}


/* delete a flow entry */
int
yesdel(struct in_addr *da, u_int32_t dp, struct in_addr *sa, u_int32_t sp)
{
	yesEntry	*ye;
	LIFO		*dst_hash, *src_hash;
	int		i, j;
	void		*head;
	u_int32_t 	daddr, saddr;

	daddr = da->s_addr;
	saddr = sa->s_addr;
	i = daddr + dp + saddr + sp;
	src_hash = (LIFO *)&yestab->act_flow[YESSIR_HASH(i)];
	dst_hash = (LIFO *)&yestab->flow_fbl;

	ye = (yesEntry *)(src_hash->head);
	head = (void *)&src_hash->head;

	/* locate the ye entry:
	 * walk through the hash chain... in case of collision
	 */
	for (j=0; j < src_hash->cnt; j++) {
		if ((ye->id.daddr == daddr) &&
			(ye->id.dport == dp) &&
			(ye->id.saddr == saddr) &&
			(ye->id.sport == sp)) {	/* got it */
			break;
		}
		head = &ye->next;
		ye = ye->next;
	}
	if (j == src_hash->cnt) {
		yestat->del_nonexist_flow++;
		return 0;
	}

	/* remove the egress entries and timer entry first 
	 */
	if (!yesdel_egress(ye))
		msglog("yessid: delete egress entry error");
	if (!yesdel_timer(ye))
		msglog("yessid: delete timer error");

	/* remove and clean the main entry
	 */
	*((u_int32_t *)head) = ((u_int32_t)ye->next);
	src_hash->cnt--;
	QA_LIFO(dst_hash, ye); 

	yestab->curr_flow--;

	yestab_deplete();		/* get extra space back */
	return -1;
}


/* add an egress entry */
yesOutEntry
*yesadd_egress(yesEntry *ye)
{
	LIFO 		*fbl, *lifo;
	yesOutEntry	*yoe;

	lifo = (LIFO *)&ye->egress;
	fbl = (LIFO *)&yestab->out_fbl;

	QM_LIFO(fbl, lifo, yoe); 

	/* clean it up */
	if (yoe) {
		yoe->out_if = 0;
		yoe->rhandle = 0;
		yoe->req_ftype = 0;
		yoe->eff_ftype = 0;
		yoe->status = 0;
	}

	return yoe;
}


/* release the all egress entries. (Be aware: all memory are dirty)
 */
int
yesdel_egress(yesEntry *ye)
{
	LIFO	*src_hash, *dst_hash;
	int	cnt;

	if ((cnt = ye->egress.cnt) == 0)
		return -1;

	src_hash = (LIFO *)&ye->egress;
	dst_hash = (LIFO *)&yestab->out_fbl;
	QMM_LIFO(src_hash, dst_hash, cnt, yesOutEntry);
	return -1;
}


/* release the soft-state timer entry  */
int
yesdel_timer(yesEntry *ye)
{
	LIFO		*fbl, *lifo;
	yesTimeEntry	*yte;
	void		*head;
	int		n;

	fbl = (LIFO *)&yestab->time_fbl;
	lifo = (LIFO *)&yestab->time_table[ye->time_slot];

	yte = (yesTimeEntry *)lifo->head;
	head = (void *)&lifo->head;

	while (n < lifo->cnt) {
		if (yte->yep == (int)ye) {
			*((u_int32_t *)head) = ((u_int32_t)yte->next);
			lifo->cnt--;
			QA_LIFO(fbl, yte);
			return -1;
		}
		head = &yte->next;
		yte = yte->next;
		n++;
	}
	return 0;
}


/* 
 * Insert a yessir entry to a pending queue: 
 */

void
yesenq_resv(yesEntry *ye)
{
	LIFO		*fbl = (LIFO *)&yestab->pending_fbl;
	FIFO		*dst_fifo = (FIFO *)&yestab->pending_q;
	yesPendingEntry	*pe;

	/* get a free bucket */
	QR_LIFO(fbl, 0, pe);
	if (!pe) {
		yestat->no_pending_bucket++;
		return;
	}

	yestab->curr_pending++;

	pe->yep = (int)ye;
	pe->tries = 0;

	/* add the entry to the head of the pending queue */
	QA_FIFO(dst_fifo, pe, yesPendingEntry);

	return;
}

/* remove a yessir entry from the pending queue.
 */

void
yesdel_pending(yesEntry *ye)
{
	LIFO		*fbl = (LIFO *)&yestab->pending_fbl;
	FIFO		*fifo = (FIFO *)&yestab->pending_q;
	yesPendingEntry	*pe, *old_pe;
	u_int32_t	i;

	old_pe = NULL;
	pe = (yesPendingEntry *)fifo->head;

	for (i=0; i < yestab->curr_pending; i++) {

		if (pe->yep == (int)ye) {
			if (!old_pe)
				fifo->head = pe->next;
			else
				old_pe->next = pe->next;

			QA_LIFO(fbl, pe);
			yestab->curr_pending--;
			return;
		}
		old_pe = pe;
		pe = pe->next;
	}
	yestat->no_pending_entry++;
	return;
}


/*
 * RIF entry management: add/get/delete
 *
 */

/* refill the rif table */
int
rif_refill()
{
	RIF	*rif;
	LIFO	*fbl;
	int	i, num;

	fbl = (LIFO *)&rifm->if_fbl;
	if (fbl->cnt >= RIF_FBL_WATERMARK)
		return -1;

	num = RIF_REFILL_SIZE;
	rifm->refill_cnt++;

	for (i=0; i < num; i++) {
		rif = (RIF *)malloc(sizeof(RIF));
		if (rif == NULL) {
			rifm->refill_fail++;
			return 0;
		}
		memset((char *)rif, 0, sizeof(RIF));
		QA_LIFO(fbl, rif);
		rifm->max_if++;
	}
	return -1;
}


/* deplete the rif table */
int
rif_deplete()
{
	RIF	*rif;
	LIFO	*fbl;
	int	limit, threshold, i;

	limit = RIF_REFILL_SIZE + RIF_FBL_WATERMARK;
	threshold = (limit > RIF_FBL_SIZE ? limit : RIF_FBL_SIZE);

	rifm->deplete_cnt++;
	fbl = (LIFO *)&rifm->if_fbl;

	for (i=fbl->cnt; i > threshold; i--) {
		QR_LIFO(fbl, threshold, rif);
		if (rif) {
			rifm->max_if--;
			free(rif);
		}
		else {
			rifm->deplete_fail++;
			return 0;
		}
	}
	return -1;
}


RIF
*rif_add(u_int16_t index)
{
	RIF	*rif;
	LIFO	*dst_hash, *src_hash;

	rif_refill();
	if (rifm->if_fbl.cnt == 0) {
		rifm->no_if_space++;
		return NULL;
	}

	rif = (RIF *)NULL;
	dst_hash = (LIFO *)&rifm->act_if[RIF_HASH(index)];
	src_hash = (LIFO *)&rifm->if_fbl;
	QM_LIFO(src_hash, dst_hash, rif);	
	if (!rif) {
		rifm->add_if_failed++;
		return NULL;
	}

	rifm->curr_if++;

	rif->if_index = index;
	rif->status = RIF_NEW;

	rif->test = 0;
	rif->state = 0;
	rif->if_type = 0;
	rif->if_physical = 0;
	rif->if_hdrlen = 0;
	rif->if_addrlen = 0;
	rif->if_addrs = 0;
	rif->if_flags = 0;
	rif->if_mtu = 0;
	rif->link_bw = 0;
	rif->int_addr = 0;
	rif->int_mask = 0;
	rif->int_dstaddr = 0;
	rif->rx_pkt = 0;
	rif->rx_byte = 0;
	rif->rx_err = 0;
	rif->tx_pkt = 0;
	rif->tx_byte = 0;
	rif->tx_err = 0;
	rif->max_resv_bw = 0;
	rif->avail_bw = 0;

	return rif;
}


RIF
*rif_get(u_int16_t if_index)
{
	LIFO	*lifo;
	RIF	*rif, *tmp_rif;
	int	n;

	lifo = (LIFO *)&rifm->act_if[RIF_HASH(if_index)];
	tmp_rif = (RIF *)(lifo->head);

	for (rif = tmp_rif, n = 0; n < lifo->cnt; rif = rif->next, n++) {
		if (rif->if_index == if_index)
			return rif;
	}
	return NULL;
}
			

int
rif_del(RIF *org_rif)
{
	LIFO	*dst_hash, *src_hash;
	RIF 	*rif;
	void	*head;
	int	index, i;

	index = org_rif->if_index;
	src_hash = (LIFO *)&rifm->act_if[RIF_HASH(index)];
	dst_hash = (LIFO *)&rifm->if_fbl;

	head = (void *)&src_hash->head;
	rif = (RIF *)src_hash->head;

	/* walk through the hash chain... in case of collision */
	for (i=0; i < src_hash->cnt; i++) {
		if (rif->if_index == index)
			break;

		head = &rif->next;
		rif = rif->next;
	}
	if (i == src_hash->cnt) {
		msglog("rif: delete non-exist rif");
		return 0;
	}

	*((u_int32_t *)head) = ((u_int32_t)rif->next);
	src_hash->cnt--;
	rif_cleanup(rif);
	QA_LIFO(dst_hash, rif); 

	rifm->curr_if--;
	rif_deplete();		/* get extra space */

	return -1;
}


void
rif_cleanup(RIF *rif)
{
	rif->test = 0;
	rif->state = 0;
	rif->if_type = 0;	/* ethernet... etc. */
	rif->if_physical = 0;	/* AUI ? */
	rif->if_addrs = 0;	/* addr bitmap */
	rif->if_flags = 0;
	rif->if_mtu = 0;
	rif->link_bw = 0;
	rif->avail_bw = 0;

	rif->int_addr = 0;	/* interface address */
	rif->int_mask = 0;
	rif->int_dstaddr = 0;

	rif->rx_pkt = 0;
	rif->rx_byte = 0;
	rif->rx_err = 0;
	rif->tx_pkt = 0;
	rif->tx_byte = 0;
	rif->tx_err = 0;

	return;
}