/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/**
 * $Id: ab15108eea328b709a49969ad465ce5d3a491efb $
 *
 * @file protocols/radius/list.c
 * @brief Functions to deal with outgoing lists / sets of packets.
 *
 * @copyright 2000-2017 The FreeRADIUS server project
 */

RCSID("$Id: ab15108eea328b709a49969ad465ce5d3a491efb $")

#include "radius.h"
#include "tcp.h"
#include "list.h"

#include <fcntl.h>
#include <freeradius-devel/util/udp.h>
#include <freeradius-devel/util/syserror.h>

/*
 *	See if two packets are identical.
 *
 *	Note that we do NOT compare the authentication vectors.
 *	That's because if the authentication vector is different,
 *	it means that the NAS has given up on the earlier request.
 */
int8_t fr_packet_cmp(void const *a_v, void const *b_v)
{
	fr_packet_t const *a = a_v, *b = b_v;
	int8_t ret;

	/*
	 *	256-way fanout for RADIUS IDs, then by FD.  And then
	 *	since there are sometimes multiple clients for one FD,
	 *	source port.  The comparison on dst_port is largely
	 *	redundant with the comparison on FD, but it's not
	 *	_completely_ redundant.
	 */
	CMP_RETURN(a, b, id);
	CMP_RETURN(a, b, socket.fd);
	CMP_RETURN(a, b, socket.inet.src_port);
	CMP_RETURN(a, b, socket.inet.dst_port);

	/*
	 *	Usually many client IPs, and few server IPs
	 */
	ret = fr_ipaddr_cmp(&a->socket.inet.src_ipaddr, &b->socket.inet.src_ipaddr);
	if (ret != 0) return ret;

	return fr_ipaddr_cmp(&a->socket.inet.dst_ipaddr, &b->socket.inet.dst_ipaddr);
}

/*
 *	Create a fake "request" from a reply, for later lookup.
 */
void fr_request_from_reply(fr_packet_t *request,
			   fr_packet_t const *reply)
{
	fr_socket_addr_swap(&request->socket, &reply->socket);
	request->id = reply->id;
}

/*
 *	We need to keep track of the socket & it's IP/port.
 */
typedef struct {
	fr_socket_t	socket;

	int		src_any;
	int		dst_any;
	void		*ctx;

	uint32_t	num_outgoing;

	bool		dont_use;

	uint8_t		id[32];
} fr_packet_socket_t;


#define FNV_MAGIC_PRIME (0x01000193)
#define MAX_SOCKETS (256)
#define SOCKOFFSET_MASK (MAX_SOCKETS - 1)
#define SOCK2OFFSET(_sockfd) ((_sockfd * FNV_MAGIC_PRIME) & SOCKOFFSET_MASK)

/*
 *	Structure defining a list of packets (incoming or outgoing)
 *	that should be managed.
 */
struct fr_packet_list_s {
	fr_rb_tree_t	*tree;

	int		alloc_id;
	uint32_t	num_outgoing;
	int		last_recv;
	int		num_sockets;

	fr_packet_socket_t sockets[MAX_SOCKETS];
};


/*
 *	Ugh.  Doing this on every sent/received packet is not nice.
 */
static fr_packet_socket_t *fr_socket_find(fr_packet_list_t *pl, int sockfd)
{
	int i, start;

	i = start = SOCK2OFFSET(sockfd);

	do {			/* make this hack slightly more efficient */
		if (pl->sockets[i].socket.fd == sockfd) return &pl->sockets[i];

		i = (i + 1) & SOCKOFFSET_MASK;
	} while (i != start);

	return NULL;
}

bool fr_packet_list_socket_freeze(fr_packet_list_t *pl, int sockfd)
{
	fr_packet_socket_t *ps;

	if (!pl) {
		fr_strerror_const("Invalid argument");
		return false;
	}

	ps = fr_socket_find(pl, sockfd);
	if (!ps) {
		fr_strerror_const("No such socket");
		return false;
	}

	ps->dont_use = true;
	return true;
}

bool fr_packet_list_socket_thaw(fr_packet_list_t *pl, int sockfd)
{
	fr_packet_socket_t *ps;

	if (!pl) return false;

	ps = fr_socket_find(pl, sockfd);
	if (!ps) return false;

	ps->dont_use = false;
	return true;
}


bool fr_packet_list_socket_del(fr_packet_list_t *pl, int sockfd)
{
	fr_packet_socket_t *ps;

	if (!pl) return false;

	ps = fr_socket_find(pl, sockfd);
	if (!ps) return false;

	if (ps->num_outgoing != 0) return false;

	ps->socket.fd = -1;
	pl->num_sockets--;

	return true;
}


bool fr_packet_list_socket_add(fr_packet_list_t *pl, int sockfd, int proto,
			      fr_ipaddr_t *dst_ipaddr, uint16_t dst_port,
			      void *ctx)
{
	int i, start;
	struct sockaddr_storage	src;
	socklen_t		sizeof_src;
	fr_packet_socket_t	*ps;

	if (!pl || !dst_ipaddr || (dst_ipaddr->af == AF_UNSPEC)) {
		fr_strerror_const("Invalid argument");
		return false;
	}

	if (pl->num_sockets >= MAX_SOCKETS) {
		fr_strerror_const("Too many open sockets");
		return false;
	}

	ps = NULL;
	i = start = SOCK2OFFSET(sockfd);

	do {
		if (pl->sockets[i].socket.fd == -1) {
			ps =  &pl->sockets[i];
			break;
		}

		i = (i + 1) & SOCKOFFSET_MASK;
	} while (i != start);

	if (!ps) {
		fr_strerror_const("All socket entries are full");
		return false;
	}

	memset(ps, 0, sizeof(*ps));
	ps->ctx = ctx;
	ps->socket.type = (proto == IPPROTO_TCP) ? SOCK_STREAM : SOCK_DGRAM;

	/*
	 *	Get address family, etc. first, so we know if we
	 *	need to do udpfromto.
	 *
	 *	FIXME: udpfromto also does this, but it's not
	 *	a critical problem.
	 */
	sizeof_src = sizeof(src);
	memset(&src, 0, sizeof_src);
	if (getsockname(sockfd, (struct sockaddr *) &src, &sizeof_src) < 0) {
		fr_strerror_printf("%s", fr_syserror(errno));
		return false;
	}

	if (fr_ipaddr_from_sockaddr(&ps->socket.inet.src_ipaddr, &ps->socket.inet.src_port, &src, sizeof_src) < 0) {
		fr_strerror_const("Failed to get IP");
		return false;
	}

	ps->socket.inet.dst_ipaddr = *dst_ipaddr;
	ps->socket.inet.dst_port = dst_port;

	ps->src_any = fr_ipaddr_is_inaddr_any(&ps->socket.inet.src_ipaddr);
	if (ps->src_any < 0) return false;

	ps->dst_any = fr_ipaddr_is_inaddr_any(&ps->socket.inet.dst_ipaddr);
	if (ps->dst_any < 0) return false;

	/*
	 *	As the last step before returning.
	 */
	ps->socket.fd = sockfd;
	pl->num_sockets++;

	return true;
}

void fr_packet_list_free(fr_packet_list_t *pl)
{
	if (!pl) return;

	talloc_free(pl->tree);
	talloc_free(pl);
}


/*
 *	Caller is responsible for managing the packet entries.
 */
fr_packet_list_t *fr_packet_list_create(int alloc_id)
{
	int i;
	fr_packet_list_t	*pl;

	pl = talloc_zero(NULL, fr_packet_list_t);
	if (!pl) return NULL;
	pl->tree = fr_rb_inline_alloc(pl, fr_packet_t, node, fr_packet_cmp, NULL);	/* elements not talloc safe */
	if (!pl->tree) {
		fr_packet_list_free(pl);
		return NULL;
	}

	for (i = 0; i < MAX_SOCKETS; i++) {
		pl->sockets[i].socket.fd = -1;
	}

	pl->alloc_id = alloc_id;

	return pl;
}


/*
 *	If pl->alloc_id is set, then fr_packet_list_id_alloc() MUST
 *	be called before inserting the packet into the list!
 */
bool fr_packet_list_insert(fr_packet_list_t *pl,
			    fr_packet_t *request)
{
	if (!pl || !request) return 0;

	return fr_rb_insert(pl->tree, request);
}

fr_packet_t *fr_packet_list_find(fr_packet_list_t *pl, fr_packet_t *request)
{
	if (!pl || !request) return 0;

	return fr_rb_find(pl->tree, request);
}


/*
 *	This presumes that the reply has dst_ipaddr && dst_port set up
 *	correctly (i.e. real IP, or "*").
 */
fr_packet_t *fr_packet_list_find_byreply(fr_packet_list_t *pl, fr_packet_t *reply)
{
	fr_packet_t my_request, *request;
	fr_packet_socket_t *ps;

	if (!pl || !reply) return NULL;

	ps = fr_socket_find(pl, reply->socket.fd);
	if (!ps) return NULL;

	/*
	 *	TCP sockets are always bound to the correct src/dst IP/port
	 */
	if (ps->socket.type == SOCK_STREAM) {
		fr_socket_addr_swap(&reply->socket, &ps->socket);
		my_request.socket = ps->socket;
	} else {
		my_request.socket = ps->socket;

		if (!ps->src_any) my_request.socket.inet.src_ipaddr = reply->socket.inet.dst_ipaddr;
		my_request.socket.inet.dst_ipaddr = reply->socket.inet.src_ipaddr;
		my_request.socket.inet.dst_port = reply->socket.inet.src_port;
	}

	/*
	 *	Initialize request from reply, AND from the source
	 *	IP & port of this socket.  The client may have bound
	 *	the socket to 0, in which case it's some random port,
	 *	that is NOT in the original request->socket.inet.src_port.
	 */
	my_request.socket.fd = reply->socket.fd;
	my_request.id = reply->id;
	request = &my_request;

	return fr_rb_find(pl->tree, request);
}


bool fr_packet_list_yank(fr_packet_list_t *pl, fr_packet_t *request)
{
	if (!pl || !request) return false;

	return fr_rb_delete(pl->tree, request);
}

uint32_t fr_packet_list_num_elements(fr_packet_list_t *pl)
{
	if (!pl) return 0;

	return fr_rb_num_elements(pl->tree);
}


/*
 *	1 == ID was allocated & assigned
 *	0 == couldn't allocate ID.
 *
 *	Note that this ALSO assigns a socket to use, and updates
 *	packet->request->socket.inet.src_ipaddr && packet->request->socket.inet.src_port
 *
 *	In multi-threaded systems, the calls to id_alloc && id_free
 *	should be protected by a mutex.  This does NOT have to be
 *	the same mutex as the one protecting the insert/find/yank
 *	calls!
 *
 *	We assume that the packet has dst_ipaddr && dst_port
 *	already initialized.  We will use those to find an
 *	outgoing socket.  The request MAY also have src_ipaddr set.
 *
 *	We also assume that the sender doesn't care which protocol
 *	should be used.
 */
bool fr_packet_list_id_alloc(fr_packet_list_t *pl, int proto,
			    fr_packet_t *request, void **pctx)
{
	int i, j, k, fd, id, start_i, start_j, start_k;
	int src_any = 0;
	int type;
	fr_packet_socket_t *ps= NULL;

	if ((request->socket.inet.dst_ipaddr.af == AF_UNSPEC) ||
	    (request->socket.inet.dst_port == 0)) {
		fr_strerror_const("No destination address/port specified");
		return false;
	}

	/*
	 *	Special case: unspec == "don't care"
	 */
	if (request->socket.inet.src_ipaddr.af == AF_UNSPEC) {
		memset(&request->socket.inet.src_ipaddr, 0, sizeof(request->socket.inet.src_ipaddr));
		request->socket.inet.src_ipaddr.af = request->socket.inet.dst_ipaddr.af;
	}

	src_any = fr_ipaddr_is_inaddr_any(&request->socket.inet.src_ipaddr);
	if (src_any < 0) {
		fr_strerror_const("Can't check src_ipaddr");
		return false;
	}

	/*
	 *	MUST specify a destination address.
	 */
	if (fr_ipaddr_is_inaddr_any(&request->socket.inet.dst_ipaddr) != 0) {
		fr_strerror_const("Must specify a dst_ipaddr");
		return false;
	}

	/*
	 *	FIXME: Go to an LRU system.  This prevents ID reuse
	 *	for as long as possible.  The main problem with that
	 *	approach is that it requires us to populate the
	 *	LRU/FIFO when we add a new socket, or a new destination,
	 *	which can be expensive.
	 *
	 *	The LRU can be avoided if the caller takes care to free
	 *	Id's only when all responses have been received, OR after
	 *	a timeout.
	 *
	 *	Right now, the random approach is almost OK... it's
	 *	brute-force over all of the available ID's, BUT using
	 *	random numbers for everything spreads the load a bit.
	 *
	 *	The old method had a hash lookup on allocation AND
	 *	on free.  The new method has brute-force on allocation,
	 *	and near-zero cost on free.
	 */

	id = fd = -1;
	if (request->id >= 0 && request->id < 256)
		id = request->id;
	start_i = fr_rand() & SOCKOFFSET_MASK;

	type = (proto == IPPROTO_TCP) ? SOCK_STREAM : SOCK_DGRAM;

#define ID_i ((i + start_i) & SOCKOFFSET_MASK)
	for (i = 0; i < MAX_SOCKETS; i++) {
		if (pl->sockets[ID_i].socket.fd == -1) continue; /* paranoia */

		ps = &(pl->sockets[ID_i]);

		/*
		 *	This socket is marked as "don't use for new
		 *	packets".  But we can still receive packets
		 *	that are outstanding.
		 */
		if (ps->dont_use) continue;

		/*
		 *	All IDs are allocated: ignore it.
		 */
		if (ps->num_outgoing == 256) continue;

		if (ps->socket.type != type) continue;

		/*
		 *	Address families don't match, skip it.
		 */
		if (ps->socket.inet.src_ipaddr.af != request->socket.inet.dst_ipaddr.af) continue;

		/*
		 *	MUST match dst port, if we have one.
		 */
		if ((ps->socket.inet.dst_port != 0) &&
		    (ps->socket.inet.dst_port != request->socket.inet.dst_port)) continue;

		/*
		 *	MUST match requested src port, if one has been given.
		 */
		if ((request->socket.inet.src_port != 0) &&
		    (ps->socket.inet.src_port != request->socket.inet.src_port)) continue;

		/*
		 *	We don't care about the source IP, but this
		 *	socket is link local, and the requested
		 *	destination is not link local.  Ignore it.
		 */
		if (src_any && (ps->socket.inet.src_ipaddr.af == AF_INET) &&
		    (((ps->socket.inet.src_ipaddr.addr.v4.s_addr >> 24) & 0xff) == 127) &&
		    (((request->socket.inet.dst_ipaddr.addr.v4.s_addr >> 24) & 0xff) != 127)) continue;

		/*
		 *	We're sourcing from *, and they asked for a
		 *	specific source address: ignore it.
		 */
		if (ps->src_any && !src_any) continue;

		/*
		 *	We're sourcing from a specific IP, and they
		 *	asked for a source IP that isn't us: ignore
		 *	it.
		 */
		if (!ps->src_any && !src_any &&
		    (fr_ipaddr_cmp(&request->socket.inet.src_ipaddr,
				   &ps->socket.inet.src_ipaddr) != 0)) continue;

		/*
		 *	UDP sockets are allowed to match
		 *	destination IPs exactly, OR a socket
		 *	with destination * is allowed to match
		 *	any requested destination.
		 *
		 *	TCP sockets must match the destination
		 *	exactly.  They *always* have dst_any=0,
		 *	so the first check always matches.
		 */
		if (!ps->dst_any &&
		    (fr_ipaddr_cmp(&request->socket.inet.dst_ipaddr,
				   &ps->socket.inet.dst_ipaddr) != 0)) continue;

		/*
		 *	Otherwise, this socket is OK to use.
		 */

		/*
		 *	An explicit ID was requested
		 */

		if (id != -1) {
			if  ((ps->id[(id >> 3) & 0x1f] & (1 << (id & 0x07))) != 0) continue;

			ps->id[(id >> 3) & 0x1f] |= (1 << (id & 0x07));
			fd = i;
			break;
		}

		/*
		 *	Look for a free Id, starting from a random number.
		 */
		start_j = fr_rand() & 0x1f;
#define ID_j ((j + start_j) & 0x1f)
		for (j = 0; j < 32; j++) {
			if (ps->id[ID_j] == 0xff) continue;


			start_k = fr_rand() & 0x07;
#define ID_k ((k + start_k) & 0x07)
			for (k = 0; k < 8; k++) {
				if ((ps->id[ID_j] & (1 << ID_k)) != 0) continue;

				ps->id[ID_j] |= (1 << ID_k);
				id = (ID_j * 8) + ID_k;
				fd = i;
				break;
			}
			if (fd >= 0) break;
		}
#undef ID_i
#undef ID_j
#undef ID_k
		break;
	}

	/*
	 *	Ask the caller to allocate a new ID.
	 */
	if (fd < 0) {
		fr_strerror_const("Failed finding socket, caller must allocate a new one");
		return false;
	}

	/*
	 *	Set the ID, source IP, and source port.
	 */
	request->id = id;

	request->socket.fd = ps->socket.fd;
	request->socket.inet.src_ipaddr = ps->socket.inet.src_ipaddr;
	request->socket.inet.src_port = ps->socket.inet.src_port;

	/*
	 *	If we managed to insert it, we're done.
	 */
	if (fr_packet_list_insert(pl, request)) {
		if (pctx) *pctx = ps->ctx;
		ps->num_outgoing++;
		pl->num_outgoing++;
		return true;
	}

	/*
	 *	Mark the ID as free.  This is the one line from
	 *	id_free() that we care about here.
	 */
	ps->id[(request->id >> 3) & 0x1f] &= ~(1 << (request->id & 0x07));

	request->id = -1;
	request->socket.fd = -1;
	request->socket.inet.src_ipaddr.af = AF_UNSPEC;
	request->socket.inet.src_port = 0;

	return false;
}

/*
 *	Should be called AFTER yanking it from the list, so that
 *	any newly inserted entries don't collide with this one.
 */
bool fr_packet_list_id_free(fr_packet_list_t *pl,
			    fr_packet_t *request, bool yank)
{
	fr_packet_socket_t *ps;

	if (!pl || !request) return false;

	if (yank && !fr_packet_list_yank(pl, request)) return false;

	ps = fr_socket_find(pl, request->socket.fd);
	if (!ps) return false;

	ps->id[(request->id >> 3) & 0x1f] &= ~(1 << (request->id & 0x07));

	ps->num_outgoing--;
	pl->num_outgoing--;

	request->id = -1;
	request->socket.inet.src_ipaddr.af = AF_UNSPEC; /* id_alloc checks this */
	request->socket.inet.src_port = 0;

	return true;
}

int fr_packet_list_fd_set(fr_packet_list_t *pl, fd_set *set)
{
	int i, maxfd;

	if (!pl || !set) return 0;

	maxfd = -1;

	for (i = 0; i < MAX_SOCKETS; i++) {
		if (pl->sockets[i].socket.fd == -1) continue;
		FD_SET(pl->sockets[i].socket.fd, set);
		if (pl->sockets[i].socket.fd > maxfd) {
			maxfd = pl->sockets[i].socket.fd;
		}
	}

	if (maxfd < 0) return -1;

	return maxfd + 1;
}

/*
 *	Round-robins the receivers, without priority.
 *
 *	FIXME: Add socket.fd, if -1, do round-robin, else do socket.fd
 *		IF in fdset.
 */
fr_packet_t *fr_packet_list_recv(fr_packet_list_t *pl, fd_set *set, uint32_t max_attributes, bool require_message_authenticator)
{
	int start;
	fr_packet_t *packet;

	if (!pl || !set) return NULL;

	start = pl->last_recv;
	do {
		start++;
		start &= SOCKOFFSET_MASK;

		if (pl->sockets[start].socket.fd == -1) continue;

		if (!FD_ISSET(pl->sockets[start].socket.fd, set)) continue;

		if (pl->sockets[start].socket.type == SOCK_STREAM) {
			packet = fr_tcp_recv(pl->sockets[start].socket.fd, false);
		} else
			packet = fr_packet_recv(NULL, pl->sockets[start].socket.fd, UDP_FLAGS_NONE,
						       max_attributes, require_message_authenticator);
		if (!packet) continue;

		/*
		 *	Call fr_packet_list_find_byreply().  If it
		 *	doesn't find anything, discard the reply.
		 */

		pl->last_recv = start;
		packet->socket.type = pl->sockets[start].socket.type;
		return packet;
	} while (start != pl->last_recv);

	return NULL;
}

uint32_t fr_packet_list_num_incoming(fr_packet_list_t *pl)
{
	uint32_t num_elements;

	if (!pl) return 0;

	num_elements = fr_rb_num_elements(pl->tree);
	if (num_elements < pl->num_outgoing) return 0; /* panic! */

	return num_elements - pl->num_outgoing;
}

uint32_t fr_packet_list_num_outgoing(fr_packet_list_t *pl)
{
	if (!pl) return 0;

	return pl->num_outgoing;
}
