src/lib/packet.c

   1 /*
   2  * packet.c     Generic packet manipulation functions.
   3  *
   4  * Version:     $Id$
   5  *
   6  *   This library is free software; you can redistribute it and/or
   7  *   modify it under the terms of the GNU Lesser General Public
   8  *   License as published by the Free Software Foundation; either
   9  *   version 2.1 of the License, or (at your option) any later version.
  10  *
  11  *   This library is distributed in the hope that it will be useful,
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  *   Lesser General Public License for more details.
  15  *
  16  *   You should have received a copy of the GNU Lesser General Public
  17  *   License along with this library; if not, write to the Free Software
  18  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  *
  20  * Copyright 2000-2006  The FreeRADIUS server project
  21  */
  22
  23 #include        <freeradius-devel/ident.h>
  24 RCSID("$Id$")
  25
  26 #include        <freeradius-devel/libradius.h>
  27
  28 #ifdef WITH_UDPFROMTO
  29 #include        <freeradius-devel/udpfromto.h>
  30 #endif
  31
  32 #include <fcntl.h>
  33
  34 /*
  35  *      Take the key fields of a request packet, and convert it to a
  36  *      hash.
  37  */
  38 uint32_t fr_request_packet_hash(const RADIUS_PACKET *packet)
  39 {
  40         uint32_t hash;
  41
  42         if (packet->hash) return packet->hash;
  43
  44         hash = fr_hash(&packet->sockfd, sizeof(packet->sockfd));
  45         hash = fr_hash_update(&packet->src_port, sizeof(packet->src_port),
  46                                 hash);
  47         hash = fr_hash_update(&packet->dst_port,
  48                                 sizeof(packet->dst_port), hash);
  49         hash = fr_hash_update(&packet->src_ipaddr.af,
  50                                 sizeof(packet->src_ipaddr.af), hash);
  51
  52         /*
  53          *      The caller ensures that src & dst AF are the same.
  54          */
  55         switch (packet->src_ipaddr.af) {
  56         case AF_INET:
  57                 hash = fr_hash_update(&packet->src_ipaddr.ipaddr.ip4addr,
  58                                         sizeof(packet->src_ipaddr.ipaddr.ip4addr),
  59                                         hash);
  60                 hash = fr_hash_update(&packet->dst_ipaddr.ipaddr.ip4addr,
  61                                         sizeof(packet->dst_ipaddr.ipaddr.ip4addr),
  62                                         hash);
  63                 break;
  64         case AF_INET6:
  65                 hash = fr_hash_update(&packet->src_ipaddr.ipaddr.ip6addr,
  66                                         sizeof(packet->src_ipaddr.ipaddr.ip6addr),
  67                                         hash);
  68                 hash = fr_hash_update(&packet->dst_ipaddr.ipaddr.ip6addr,
  69                                         sizeof(packet->dst_ipaddr.ipaddr.ip6addr),
  70                                         hash);
  71                 break;
  72         default:
  73                 break;
  74         }
  75
  76         return fr_hash_update(&packet->id, sizeof(packet->id), hash);
  77 }
  78
  79
  80 /*
  81  *      Take the key fields of a reply packet, and convert it to a
  82  *      hash.
  83  *
  84  *      i.e. take a reply packet, and find the hash of the request packet
  85  *      that asked for the reply.  To do this, we hash the reverse fields
  86  *      of the request.  e.g. where the request does (src, dst), we do
  87  *      (dst, src)
  88  */
  89 uint32_t fr_reply_packet_hash(const RADIUS_PACKET *packet)
  90 {
  91         uint32_t hash;
  92
  93         hash = fr_hash(&packet->sockfd, sizeof(packet->sockfd));
  94         hash = fr_hash_update(&packet->id, sizeof(packet->id), hash);
  95         hash = fr_hash_update(&packet->src_port, sizeof(packet->src_port),
  96                                 hash);
  97         hash = fr_hash_update(&packet->dst_port,
  98                                 sizeof(packet->dst_port), hash);
  99         hash = fr_hash_update(&packet->src_ipaddr.af,
 100                                 sizeof(packet->src_ipaddr.af), hash);
 101
 102         /*
 103          *      The caller ensures that src & dst AF are the same.
 104          */
 105         switch (packet->src_ipaddr.af) {
 106         case AF_INET:
 107                 hash = fr_hash_update(&packet->dst_ipaddr.ipaddr.ip4addr,
 108                                         sizeof(packet->dst_ipaddr.ipaddr.ip4addr),
 109                                         hash);
 110                 hash = fr_hash_update(&packet->src_ipaddr.ipaddr.ip4addr,
 111                                         sizeof(packet->src_ipaddr.ipaddr.ip4addr),
 112                                         hash);
 113                 break;
 114         case AF_INET6:
 115                 hash = fr_hash_update(&packet->dst_ipaddr.ipaddr.ip6addr,
 116                                         sizeof(packet->dst_ipaddr.ipaddr.ip6addr),
 117                                         hash);
 118                 hash = fr_hash_update(&packet->src_ipaddr.ipaddr.ip6addr,
 119                                         sizeof(packet->src_ipaddr.ipaddr.ip6addr),
 120                                         hash);
 121                 break;
 122         default:
 123                 break;
 124         }
 125
 126         return fr_hash_update(&packet->id, sizeof(packet->id), hash);
 127 }
 128
 129
 130 /*
 131  *      See if two packets are identical.
 132  *
 133  *      Note that we do NOT compare the authentication vectors.
 134  *      That's because if the authentication vector is different,
 135  *      it means that the NAS has given up on the earlier request.
 136  */
 137 int fr_packet_cmp(const RADIUS_PACKET *a, const RADIUS_PACKET *b)
 138 {
 139         int rcode;
 140
 141         rcode = a->id - b->id;
 142         if (rcode != 0) return rcode;
 143
 144         rcode = (int) a->src_port - (int) b->src_port;
 145         if (rcode != 0) return rcode;
 146
 147         rcode = (int) a->dst_port - (int) b->dst_port;
 148         if (rcode != 0) return rcode;
 149
 150         rcode = a->sockfd - b->sockfd;
 151         if (rcode != 0) return rcode;
 152
 153         rcode = fr_ipaddr_cmp(&a->src_ipaddr, &b->src_ipaddr);
 154         if (rcode != 0) return rcode;
 155
 156         return fr_ipaddr_cmp(&a->dst_ipaddr, &b->dst_ipaddr);
 157 }
 158
 159 int fr_inaddr_any(fr_ipaddr_t *ipaddr)
 160 {
 161
 162         if (ipaddr->af == AF_INET) {
 163                 if (ipaddr->ipaddr.ip4addr.s_addr == INADDR_ANY) {
 164                         return 1;
 165                 }
 166
 167 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 168         } else if (ipaddr->af == AF_INET6) {
 169                 if (IN6_IS_ADDR_UNSPECIFIED(&(ipaddr->ipaddr.ip6addr))) {
 170                         return 1;
 171                 }
 172 #endif
 173
 174         } else {
 175                 fr_strerror_printf("Unknown address family");
 176                 return -1;
 177         }
 178
 179         return 0;
 180 }
 181
 182
 183 /*
 184  *      Create a fake "request" from a reply, for later lookup.
 185  */
 186 void fr_request_from_reply(RADIUS_PACKET *request,
 187                              const RADIUS_PACKET *reply)
 188 {
 189         request->sockfd = reply->sockfd;
 190         request->id = reply->id;
 191         request->src_port = reply->dst_port;
 192         request->dst_port = reply->src_port;
 193         request->src_ipaddr = reply->dst_ipaddr;
 194         request->dst_ipaddr = reply->src_ipaddr;
 195 }
 196
 197
 198 int fr_nonblock(UNUSED int fd)
 199 {
 200         int flags = 0;
 201
 202 #ifdef O_NONBLOCK
 203
 204         flags = fcntl(fd, F_GETFL, NULL);
 205         if (flags >= 0) {
 206                 flags |= O_NONBLOCK;
 207                 return fcntl(fd, F_SETFL, flags);
 208         }
 209 #endif
 210         return flags;
 211 }
 212
 213 /*
 214  *      Open a socket on the given IP and port.
 215  */
 216 int fr_socket(fr_ipaddr_t *ipaddr, int port)
 217 {
 218         int sockfd;
 219         struct sockaddr_storage salocal;
 220         socklen_t       salen;
 221
 222         if ((port < 0) || (port > 65535)) {
 223                 fr_strerror_printf("Port %d is out of allowed bounds", port);
 224                 return -1;
 225         }
 226
 227         sockfd = socket(ipaddr->af, SOCK_DGRAM, 0);
 228         if (sockfd < 0) {
 229                 fr_strerror_printf("cannot open socket: %s", strerror(errno));
 230                 return sockfd;
 231         }
 232
 233 #ifdef WITH_UDPFROMTO
 234         /*
 235          *      Initialize udpfromto for all sockets.
 236          */
 237         if (udpfromto_init(sockfd) != 0) {
 238                 close(sockfd);
 239                 fr_strerror_printf("cannot initialize udpfromto: %s", strerror(errno));
 240                 return -1;
 241         }
 242 #endif
 243
 244         if (fr_nonblock(sockfd) < 0) {
 245                 close(sockfd);
 246                 return -1;
 247         }
 248
 249         if (!fr_ipaddr2sockaddr(ipaddr, port, &salocal, &salen)) {
 250                 return sockfd;
 251         }
 252
 253 #ifdef HAVE_STRUCT_SOCKADDR_IN6
 254         if (ipaddr->af == AF_INET6) {
 255                 /*
 256                  *      Listening on '::' does NOT get you IPv4 to
 257                  *      IPv6 mapping.  You've got to listen on an IPv4
 258                  *      address, too.  This makes the rest of the server
 259                  *      design a little simpler.
 260                  */
 261 #ifdef IPV6_V6ONLY
 262
 263                 if (IN6_IS_ADDR_UNSPECIFIED(&ipaddr->ipaddr.ip6addr)) {
 264                         int on = 1;
 265
 266                         setsockopt(sockfd, IPPROTO_IPV6, IPV6_V6ONLY,
 267                                    (char *)&on, sizeof(on));
 268                 }
 269 #endif /* IPV6_V6ONLY */
 270         }
 271 #endif /* HAVE_STRUCT_SOCKADDR_IN6 */
 272
 273         if (ipaddr->af == AF_INET) {
 274                 UNUSED int flag;
 275
 276 #if defined(IP_MTU_DISCOVER) && defined(IP_PMTUDISC_DONT)
 277                 /*
 278                  *      Disable PMTU discovery.  On Linux, this
 279                  *      also makes sure that the "don't fragment"
 280                  *      flag is zero.
 281                  */
 282                 flag = IP_PMTUDISC_DONT;
 283                 setsockopt(sockfd, IPPROTO_IP, IP_MTU_DISCOVER,
 284                            &flag, sizeof(flag));
 285 #endif
 286
 287 #if defined(IP_DONTFRAG)
 288                 /*
 289                  *      Ensure that the "don't fragment" flag is zero.
 290                  */
 291                 flag = 0;
 292                 setsockopt(sockfd, IPPROTO_IP, IP_DONTFRAG,
 293                            &flag, sizeof(flag));
 294 #endif
 295         }
 296
 297         if (bind(sockfd, (struct sockaddr *) &salocal, salen) < 0) {
 298                 close(sockfd);
 299                 fr_strerror_printf("cannot bind socket: %s", strerror(errno));
 300                 return -1;
 301         }
 302
 303         return sockfd;
 304 }
 305
 306
 307 /*
 308  *      We need to keep track of the socket & it's IP/port.
 309  */
 310 typedef struct fr_packet_socket_t {
 311         int             sockfd;
 312         void            *ctx;
 313
 314         int             num_outgoing;
 315
 316         int             src_any;
 317         fr_ipaddr_t     src_ipaddr;
 318         int             src_port;
 319
 320         int             dst_any;
 321         fr_ipaddr_t     dst_ipaddr;
 322         int             dst_port;
 323
 324         int             dont_use;
 325
 326 #ifdef WITH_TCP
 327         int             proto;
 328 #endif
 329
 330         uint8_t         id[32];
 331 } fr_packet_socket_t;
 332
 333
 334 #define FNV_MAGIC_PRIME (0x01000193)
 335 #define MAX_SOCKETS (256)
 336 #define SOCKOFFSET_MASK (MAX_SOCKETS - 1)
 337 #define SOCK2OFFSET(sockfd) ((sockfd * FNV_MAGIC_PRIME) & SOCKOFFSET_MASK)
 338
 339 #define MAX_QUEUES (8)
 340
 341 /*
 342  *      Structure defining a list of packets (incoming or outgoing)
 343  *      that should be managed.
 344  */
 345 struct fr_packet_list_t {
 346         rbtree_t        *tree;
 347
 348         int             alloc_id;
 349         int             num_outgoing;
 350         int             last_recv;
 351         int             num_sockets;
 352
 353         fr_packet_socket_t sockets[MAX_SOCKETS];
 354 };
 355
 356
 357 /*
 358  *      Ugh.  Doing this on every sent/received packet is not nice.
 359  */
 360 static fr_packet_socket_t *fr_socket_find(fr_packet_list_t *pl,
 361                                           int sockfd)
 362 {
 363         int i, start;
 364
 365         i = start = SOCK2OFFSET(sockfd);
 366
 367         do {                    /* make this hack slightly more efficient */
 368                 if (pl->sockets[i].sockfd == sockfd) return &pl->sockets[i];
 369
 370                 i = (i + 1) & SOCKOFFSET_MASK;
 371         } while (i != start);
 372
 373         return NULL;
 374 }
 375
 376 int fr_packet_list_socket_freeze(fr_packet_list_t *pl, int sockfd)
 377 {
 378         fr_packet_socket_t *ps;
 379
 380         if (!pl) {
 381                 fr_strerror_printf("Invalid argument");
 382                 return 0;
 383         }
 384
 385         ps = fr_socket_find(pl, sockfd);
 386         if (!ps) {
 387                 fr_strerror_printf("No such socket");
 388                 return 0;
 389         }
 390
 391         ps->dont_use = 1;
 392         return 1;
 393 }
 394
 395 int fr_packet_list_socket_thaw(fr_packet_list_t *pl, int sockfd)
 396 {
 397         fr_packet_socket_t *ps;
 398
 399         if (!pl) return 0;
 400
 401         ps = fr_socket_find(pl, sockfd);
 402         if (!ps) return 0;
 403
 404         ps->dont_use = 0;
 405         return 1;
 406 }
 407
 408 int fr_packet_list_socket_remove(fr_packet_list_t *pl, int sockfd,
 409                                  void **pctx)
 410 {
 411         fr_packet_socket_t *ps;
 412
 413         if (!pl) return 0;
 414
 415         ps = fr_socket_find(pl, sockfd);
 416         if (!ps) return 0;
 417
 418         /*
 419          *      FIXME: Allow the caller forcibly discard these?
 420          */
 421         if (ps->num_outgoing != 0) return 0;
 422
 423         ps->sockfd = -1;
 424         pl->num_sockets--;
 425         if (pctx) *pctx = ps->ctx;
 426
 427         return 1;
 428 }
 429
 430 int fr_packet_list_socket_add(fr_packet_list_t *pl, int sockfd, int proto,
 431                               fr_ipaddr_t *dst_ipaddr, int dst_port,
 432                               void *ctx)
 433 {
 434         int i, start;
 435         struct sockaddr_storage src;
 436         socklen_t               sizeof_src;
 437         fr_packet_socket_t      *ps;
 438
 439         if (!pl || !dst_ipaddr || (dst_ipaddr->af == AF_UNSPEC)) {
 440                 fr_strerror_printf("Invalid argument");
 441                 return 0;
 442         }
 443
 444         if (pl->num_sockets >= MAX_SOCKETS) {
 445                 fr_strerror_printf("Too many open sockets");
 446                 return 0;
 447         }
 448
 449 #ifndef WITH_TCP
 450         if (proto != IPPROTO_UDP) {
 451                 fr_strerror_printf("only UDP is supported");
 452                 return 0;
 453         }
 454 #endif
 455
 456         ps = NULL;
 457         i = start = SOCK2OFFSET(sockfd);
 458
 459         do {
 460                 if (pl->sockets[i].sockfd == -1) {
 461                         ps =  &pl->sockets[i];
 462                         break;
 463                 }
 464
 465                 i = (i + 1) & SOCKOFFSET_MASK;
 466         } while (i != start);
 467
 468         if (!ps) {
 469                 fr_strerror_printf("All socket entries are full");
 470                 return 0;
 471         }
 472
 473         memset(ps, 0, sizeof(*ps));
 474         ps->ctx = ctx;
 475 #ifdef WITH_TCP
 476         ps->proto = proto;
 477 #endif
 478
 479         /*
 480          *      Get address family, etc. first, so we know if we
 481          *      need to do udpfromto.
 482          *
 483          *      FIXME: udpfromto also does this, but it's not
 484          *      a critical problem.
 485          */
 486         sizeof_src = sizeof(src);
 487         memset(&src, 0, sizeof_src);
 488         if (getsockname(sockfd, (struct sockaddr *) &src,
 489                         &sizeof_src) < 0) {
 490                 fr_strerror_printf("%s", strerror(errno));
 491                 return 0;
 492         }
 493
 494         if (!fr_sockaddr2ipaddr(&src, sizeof_src, &ps->src_ipaddr,
 495                                 &ps->src_port)) {
 496                 fr_strerror_printf("Failed to get IP");
 497                 return 0;
 498         }
 499
 500         ps->dst_ipaddr = *dst_ipaddr;
 501         ps->dst_port = dst_port;
 502
 503         ps->src_any = fr_inaddr_any(&ps->src_ipaddr);
 504         if (ps->src_any < 0) return 0;
 505
 506         ps->dst_any = fr_inaddr_any(&ps->dst_ipaddr);
 507         if (ps->dst_any < 0) return 0;
 508
 509         /*
 510          *      As the last step before returning.
 511          */
 512         ps->sockfd = sockfd;
 513         pl->num_sockets++;
 514
 515         return 1;
 516 }
 517
 518 static int packet_entry_cmp(const void *one, const void *two)
 519 {
 520         const RADIUS_PACKET * const *a = one;
 521         const RADIUS_PACKET * const *b = two;
 522
 523         return fr_packet_cmp(*a, *b);
 524 }
 525
 526 void fr_packet_list_free(fr_packet_list_t *pl)
 527 {
 528         if (!pl) return;
 529
 530         rbtree_free(pl->tree);
 531         free(pl);
 532 }
 533
 534
 535 /*
 536  *      Caller is responsible for managing the packet entries.
 537  */
 538 fr_packet_list_t *fr_packet_list_create(int alloc_id)
 539 {
 540         int i;
 541         fr_packet_list_t        *pl;
 542
 543         pl = malloc(sizeof(*pl));
 544         if (!pl) return NULL;
 545         memset(pl, 0, sizeof(*pl));
 546
 547         pl->tree = rbtree_create(packet_entry_cmp, NULL, 0);
 548         if (!pl->tree) {
 549                 fr_packet_list_free(pl);
 550                 return NULL;
 551         }
 552
 553         for (i = 0; i < MAX_SOCKETS; i++) {
 554                 pl->sockets[i].sockfd = -1;
 555         }
 556
 557         pl->alloc_id = alloc_id;
 558
 559         return pl;
 560 }
 561
 562
 563 /*
 564  *      If pl->alloc_id is set, then fr_packet_list_id_alloc() MUST
 565  *      be called before inserting the packet into the list!
 566  */
 567 int fr_packet_list_insert(fr_packet_list_t *pl,
 568                             RADIUS_PACKET **request_p)
 569 {
 570         if (!pl || !request_p || !*request_p) return 0;
 571
 572         return rbtree_insert(pl->tree, request_p);
 573 }
 574
 575 RADIUS_PACKET **fr_packet_list_find(fr_packet_list_t *pl,
 576                                       RADIUS_PACKET *request)
 577 {
 578         if (!pl || !request) return 0;
 579
 580         return rbtree_finddata(pl->tree, &request);
 581 }
 582
 583
 584 /*
 585  *      This presumes that the reply has dst_ipaddr && dst_port set up
 586  *      correctly (i.e. real IP, or "*").
 587  */
 588 RADIUS_PACKET **fr_packet_list_find_byreply(fr_packet_list_t *pl,
 589                                               RADIUS_PACKET *reply)
 590 {
 591         RADIUS_PACKET my_request, *request;
 592         fr_packet_socket_t *ps;
 593
 594         if (!pl || !reply) return NULL;
 595
 596         ps = fr_socket_find(pl, reply->sockfd);
 597         if (!ps) return NULL;
 598
 599         /*
 600          *      Initialize request from reply, AND from the source
 601          *      IP & port of this socket.  The client may have bound
 602          *      the socket to 0, in which case it's some random port,
 603          *      that is NOT in the original request->src_port.
 604          */
 605         my_request.sockfd = reply->sockfd;
 606         my_request.id = reply->id;
 607
 608         if (ps->src_any) {
 609                 my_request.src_ipaddr = ps->src_ipaddr;
 610         } else {
 611                 my_request.src_ipaddr = reply->dst_ipaddr;
 612         }
 613         my_request.src_port = ps->src_port;
 614
 615         my_request.dst_ipaddr = reply->src_ipaddr;
 616         my_request.dst_port = reply->src_port;
 617
 618         request = &my_request;
 619
 620         return rbtree_finddata(pl->tree, &request);
 621 }
 622
 623
 624 void fr_packet_list_yank(fr_packet_list_t *pl, RADIUS_PACKET *request)
 625 {
 626         rbnode_t *node;
 627
 628         if (!pl || !request) return;
 629
 630         node = rbtree_find(pl->tree, &request);
 631         if (!node) return;
 632
 633         rbtree_delete(pl->tree, node);
 634 }
 635
 636 int fr_packet_list_num_elements(fr_packet_list_t *pl)
 637 {
 638         if (!pl) return 0;
 639
 640         return rbtree_num_elements(pl->tree);
 641 }
 642
 643
 644 /*
 645  *      1 == ID was allocated & assigned
 646  *      0 == error allocating memory
 647  *      -1 == all ID's are used, caller should open a new socket.
 648  *
 649  *      Note that this ALSO assigns a socket to use, and updates
 650  *      packet->request->src_ipaddr && packet->request->src_port
 651  *
 652  *      In multi-threaded systems, the calls to id_alloc && id_free
 653  *      should be protected by a mutex.  This does NOT have to be
 654  *      the same mutex as the one protecting the insert/find/yank
 655  *      calls!
 656  *
 657  *      We assume that the packet has dst_ipaddr && dst_port
 658  *      already initialized.  We will use those to find an
 659  *      outgoing socket.  The request MAY also have src_ipaddr set.
 660  *
 661  *      We also assume that the sender doesn't care which protocol
 662  *      should be used.
 663  */
 664 int fr_packet_list_id_alloc(fr_packet_list_t *pl, int proto,
 665                             RADIUS_PACKET *request, void **pctx)
 666 {
 667         int i, j, k, fd, id, start_i, start_j, start_k;
 668         int src_any = 0;
 669         fr_packet_socket_t *ps;
 670
 671         if ((request->dst_ipaddr.af == AF_UNSPEC) ||
 672             (request->dst_port == 0)) {
 673                 fr_strerror_printf("No destination address/port specified");
 674                 return 0;
 675         }
 676
 677 #ifndef WITH_TCP
 678         if ((proto != 0) && (proto != IPPROTO_UDP)) {
 679                 fr_strerror_printf("Invalid destination protocol");
 680                 return 0;
 681         }
 682 #endif
 683
 684         /*
 685          *      Special case: unspec == "don't care"
 686          */
 687         if (request->src_ipaddr.af == AF_UNSPEC) {
 688                 memset(&request->src_ipaddr, 0, sizeof(request->src_ipaddr));
 689                 request->src_ipaddr.af = request->dst_ipaddr.af;
 690         }
 691
 692         src_any = fr_inaddr_any(&request->src_ipaddr);
 693         if (src_any < 0) return 0;
 694
 695         /*
 696          *      MUST specify a destination address.
 697          */
 698         if (fr_inaddr_any(&request->dst_ipaddr) != 0) return 0;
 699
 700         /*
 701          *      FIXME: Go to an LRU system.  This prevents ID re-use
 702          *      for as long as possible.  The main problem with that
 703          *      approach is that it requires us to populate the
 704          *      LRU/FIFO when we add a new socket, or a new destination,
 705          *      which can be expensive.
 706          *
 707          *      The LRU can be avoided if the caller takes care to free
 708          *      Id's only when all responses have been received, OR after
 709          *      a timeout.
 710          *
 711          *      Right now, the random approach is almost OK... it's
 712          *      brute-force over all of the available ID's, BUT using
 713          *      random numbers for everything spreads the load a bit.
 714          *
 715          *      The old method had a hash lookup on allocation AND
 716          *      on free.  The new method has brute-force on allocation,
 717          *      and near-zero cost on free.
 718          */
 719
 720         id = fd = -1;
 721         start_i = fr_rand() & SOCKOFFSET_MASK;
 722
 723 #define ID_i ((i + start_i) & SOCKOFFSET_MASK)
 724         for (i = 0; i < MAX_SOCKETS; i++) {
 725                 if (pl->sockets[ID_i].sockfd == -1) continue; /* paranoia */
 726
 727                 ps = &(pl->sockets[ID_i]);
 728
 729                 /*
 730                  *      This socket is marked as "don't use for new
 731                  *      packets".  But we can still receive packets
 732                  *      that are outstanding.
 733                  */
 734                 if (ps->dont_use) continue;
 735
 736                 /*
 737                  *      All IDs are allocated: ignore it.
 738                  */
 739                 if (ps->num_outgoing == 256) continue;
 740
 741 #ifdef WITH_TCP
 742                 if (ps->proto != proto) continue;
 743 #endif
 744
 745                 /*
 746                  *      Address families don't match, skip it.
 747                  */
 748                 if (ps->src_ipaddr.af != request->dst_ipaddr.af) continue;
 749
 750                 /*
 751                  *      MUST match dst port, if we have one.
 752                  */
 753                 if ((ps->dst_port != 0) &&
 754                     (ps->dst_port != request->dst_port)) continue;
 755
 756                 /*
 757                  *      MUST match requested src port, if one has been given.
 758                  */
 759                 if ((request->src_port != 0) &&
 760                     (ps->src_port != request->src_port)) continue;
 761
 762                 /*
 763                  *      We're sourcing from *, and they asked for a
 764                  *      specific source address: ignore it.
 765                  */
 766                 if (ps->src_any && !src_any) continue;
 767
 768                 /*
 769                  *      We're sourcing from a specific IP, and they
 770                  *      asked for a source IP that isn't us: ignore
 771                  *      it.
 772                  */
 773                 if (!ps->src_any && !src_any &&
 774                     (fr_ipaddr_cmp(&request->src_ipaddr,
 775                                    &ps->src_ipaddr) != 0)) continue;
 776
 777                 /*
 778                  *      UDP sockets are allowed to match
 779                  *      destination IPs exactly, OR a socket
 780                  *      with destination * is allowed to match
 781                  *      any requested destination.
 782                  *
 783                  *      TCP sockets must match the destination
 784                  *      exactly.  They *always* have dst_any=0,
 785                  *      so the first check always matches.
 786                  */
 787                 if (!ps->dst_any &&
 788                     (fr_ipaddr_cmp(&request->dst_ipaddr,
 789                                    &ps->dst_ipaddr) != 0)) continue;
 790
 791                 /*
 792                  *      Otherwise, this socket is OK to use.
 793                  */
 794
 795                 /*
 796                  *      Look for a free Id, starting from a random number.
 797                  */
 798                 start_j = fr_rand() & 0x1f;
 799 #define ID_j ((j + start_j) & 0x1f)
 800                 for (j = 0; j < 32; j++) {
 801                         if (ps->id[ID_j] == 0xff) continue;
 802
 803
 804                         start_k = fr_rand() & 0x07;
 805 #define ID_k ((k + start_k) & 0x07)
 806                         for (k = 0; k < 8; k++) {
 807                                 if ((ps->id[ID_j] & (1 << ID_k)) != 0) continue;
 808
 809                                 ps->id[ID_j] |= (1 << ID_k);
 810                                 id = (ID_j * 8) + ID_k;
 811                                 fd = i;
 812                                 break;
 813                         }
 814                         if (fd >= 0) break;
 815                 }
 816 #undef ID_i
 817 #undef ID_j
 818 #undef ID_k
 819                 if (fd >= 0) break;
 820                 break;
 821         }
 822
 823         /*
 824          *      Ask the caller to allocate a new ID.
 825          */
 826         if (fd < 0) return 0;
 827
 828         ps->num_outgoing++;
 829         pl->num_outgoing++;
 830
 831         /*
 832          *      Set the ID, source IP, and source port.
 833          */
 834         request->id = id;
 835
 836         request->sockfd = ps->sockfd;
 837         request->src_ipaddr = ps->src_ipaddr;
 838         request->src_port = ps->src_port;
 839
 840         if (pctx) *pctx = ps->ctx;
 841
 842         return 1;
 843 }
 844
 845 /*
 846  *      Should be called AFTER yanking it from the list, so that
 847  *      any newly inserted entries don't collide with this one.
 848  */
 849 int fr_packet_list_id_free(fr_packet_list_t *pl,
 850                              RADIUS_PACKET *request)
 851 {
 852         fr_packet_socket_t *ps;
 853
 854         if (!pl || !request) return 0;
 855
 856         ps = fr_socket_find(pl, request->sockfd);
 857         if (!ps) return 0;
 858
 859 #if 0
 860         if (!ps->id[(request->id >> 3) & 0x1f] & (1 << (request->id & 0x07))) {
 861                 exit(1);
 862         }
 863 #endif
 864
 865         ps->id[(request->id >> 3) & 0x1f] &= ~(1 << (request->id & 0x07));
 866
 867         ps->num_outgoing--;
 868         pl->num_outgoing--;
 869
 870         return 1;
 871 }
 872
 873 int fr_packet_list_walk(fr_packet_list_t *pl, void *ctx,
 874                           fr_hash_table_walk_t callback)
 875 {
 876         if (!pl || !callback) return 0;
 877
 878         return rbtree_walk(pl->tree, InOrder, callback, ctx);
 879 }
 880
 881 int fr_packet_list_fd_set(fr_packet_list_t *pl, fd_set *set)
 882 {
 883         int i, maxfd;
 884
 885         if (!pl || !set) return 0;
 886
 887         maxfd = -1;
 888
 889         for (i = 0; i < MAX_SOCKETS; i++) {
 890                 if (pl->sockets[i].sockfd == -1) continue;
 891                 FD_SET(pl->sockets[i].sockfd, set);
 892                 if (pl->sockets[i].sockfd > maxfd) {
 893                         maxfd = pl->sockets[i].sockfd;
 894                 }
 895         }
 896
 897         if (maxfd < 0) return -1;
 898
 899         return maxfd + 1;
 900 }
 901
 902 /*
 903  *      Round-robins the receivers, without priority.
 904  *
 905  *      FIXME: Add sockfd, if -1, do round-robin, else do sockfd
 906  *              IF in fdset.
 907  */
 908 RADIUS_PACKET *fr_packet_list_recv(fr_packet_list_t *pl, fd_set *set)
 909 {
 910         int start;
 911         RADIUS_PACKET *packet;
 912
 913         if (!pl || !set) return NULL;
 914
 915         start = pl->last_recv;
 916         do {
 917                 start++;
 918                 start &= SOCKOFFSET_MASK;
 919
 920                 if (pl->sockets[start].sockfd == -1) continue;
 921
 922                 if (!FD_ISSET(pl->sockets[start].sockfd, set)) continue;
 923
 924 #ifdef WITH_TCP
 925                 if (pl->sockets[start].proto == IPPROTO_TCP) {
 926                         packet = fr_tcp_recv(pl->sockets[start].sockfd, 0);
 927                 } else
 928 #endif
 929                 packet = rad_recv(pl->sockets[start].sockfd, 0);
 930                 if (!packet) continue;
 931
 932                 /*
 933                  *      Call fr_packet_list_find_byreply().  If it
 934                  *      doesn't find anything, discard the reply.
 935                  */
 936
 937                 pl->last_recv = start;
 938                 return packet;
 939         } while (start != pl->last_recv);
 940
 941         return NULL;
 942 }
 943
 944 int fr_packet_list_num_incoming(fr_packet_list_t *pl)
 945 {
 946         int num_elements;
 947
 948         if (!pl) return 0;
 949
 950         num_elements = rbtree_num_elements(pl->tree);
 951         if (num_elements < pl->num_outgoing) return 0; /* panic! */
 952
 953         return num_elements - pl->num_outgoing;
 954 }
 955
 956 int fr_packet_list_num_outgoing(fr_packet_list_t *pl)
 957 {
 958         if (!pl) return 0;
 959
 960         return pl->num_outgoing;
 961 }