/*

 *   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: 23c34a82cf085a4570b3d63f01ab92fa520b588e $

 *

 * @file protocols/radius/list.c

 * @brief Functions to deal with outgoing lists / sets of packets.

 *

 * @copyright 2000-2017 The FreeRADIUS server project

 */

RCSID("$Id: 23c34a82cf085a4570b3d63f01ab92fa520b588e $")

#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];

  uint8_t   *buffer;

  size_t    bufsize;

  size_t    used;

} 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;

  TALLOC_FREE(ps->buffer);

  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->socket.fd = -1;

  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;

  if (proto == IPPROTO_TCP) {

    ps->buffer = talloc_array(pl, uint8_t, RADIUS_MAX_PACKET_SIZE);

    if (ps->buffer) return false;

    ps->bufsize = RADIUS_MAX_PACKET_SIZE;

    ps->used = 0;

  }

  /*

   *  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.

 */

int fr_packet_list_recv(fr_packet_list_t *pl, fd_set *set, TALLOC_CTX *ctx, fr_packet_t **packet_p, uint32_t max_attributes, bool require_message_authenticator)

{

  int start;

  fr_packet_t *packet;

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

  start = pl->last_recv;

  do {

    fr_packet_socket_t *ps;

    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) {

      int rcode;

      ps = &pl->sockets[start];

      rcode = fr_tcp_read_packet(ps->socket.fd, ps->buffer, ps->bufsize,

               &ps->used, max_attributes, require_message_authenticator);

      if (rcode <= 0) return rcode;

      fr_assert(ps->used >= RADIUS_HEADER_LENGTH);

      packet = fr_packet_alloc(ctx, false);

      if (!packet) return -1;

      packet->data = talloc_memdup(packet, ps->buffer, rcode);

      if (!packet->data) {

        talloc_free(packet);

        return -1;

      }

      packet->data_len = rcode;

      packet->socket = ps->socket;

      if (ps->used == (size_t) rcode) {

        ps->used = 0;

      } else {

        fr_assert(ps->used > (size_t) rcode);

        memmove(ps->buffer, ps->buffer + rcode, ps->used - rcode);

        ps->used -= rcode;

      }

    } else {

      packet = fr_packet_recv(ctx, 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;

    *packet_p = packet;

    return 0;

  } while (start != pl->last_recv);

  return 0;

}

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;

}