src/main/request_list.c

   1 /*
   2  * request_list.c       Hide the handling of the REQUEST list from
   3  *                      the main server.
   4  *
   5  * Version:     $Id$
   6  *
   7  *   This program is free software; you can redistribute it and/or modify
   8  *   it under the terms of the GNU General Public License as published by
   9  *   the Free Software Foundation; either version 2 of the License, or
  10  *   (at your option) any later version.
  11  *
  12  *   This program is distributed in the hope that it will be useful,
  13  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *   GNU General Public License for more details.
  16  *
  17  *   You should have received a copy of the GNU General Public License
  18  *   along with this program; if not, write to the Free Software
  19  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  * Copyright 2003-2004  The FreeRADIUS server project
  22  */
  23 static const char rcsid[] = "$Id$";
  24
  25 #include "autoconf.h"
  26 #include "libradius.h"
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #include "radiusd.h"
  32 #include "rad_assert.h"
  33 #include "request_list.h"
  34 #include "radius_snmp.h"
  35
  36
  37 /*
  38  *      We keep the incoming requests in an array, indexed by ID.
  39  *
  40  *      Each array element contains a linked list of containers of
  41  *      active requests, a count of the number of requests, and a time
  42  *      at which the first request in the list must be serviced.
  43  *
  44  *      Note that we ALSO keep a tree view of the same data, below.
  45  *      Both views are needed for the server to work optimally.
  46  */
  47 typedef struct REQNODE {
  48         struct REQNODE *prev, *next;
  49         REQUEST *req;
  50 } REQNODE;
  51
  52 typedef struct REQUESTINFO {
  53         REQNODE *first_request;
  54         REQNODE *last_request;
  55         int request_count;
  56         time_t last_cleaned_list;
  57 } REQUESTINFO;
  58
  59 static REQUESTINFO      request_list[256];
  60
  61 /*
  62  *      Remember the next request at which we start walking
  63  *      the list.
  64  */
  65 static REQUEST *last_request = NULL;
  66
  67 /*
  68  *      It MAY make more sense here to key off of the packet ID, just
  69  *      like the request_list.  Then again, saving another 8 lookups
  70  *      (on average) isn't much of a problem.
  71  *
  72  *      The "request_cmp" function keys off of the packet ID first,
  73  *      so the first 8 layers of the tree will be the fanned-out
  74  *      tree for packet ID's.
  75  */
  76 static rbtree_t         *request_tree;
  77
  78 #ifdef HAVE_PTHREAD_H
  79 static pthread_mutex_t  proxy_mutex;
  80 #else
  81 /*
  82  *      This is easier than ifdef's throughout the code.
  83  */
  84 #define pthread_mutex_lock(_x)
  85 #define pthread_mutex_unlock(_x)
  86 #endif
  87
  88 /*
  89  *      We keep track of packets we're proxying, keyed by
  90  *      source socket, and destination ip/port, and Id.
  91  */
  92 static rbtree_t         *proxy_tree;
  93
  94 /*
  95  *      We keep track of free/used Id's, by destination ip/port.
  96  *
  97  *      We need a different tree than above, because this one is NOT
  98  *      keyed by Id.  Instead, we use this one to allocate Id's.
  99  */
 100 static rbtree_t         *proxy_id_tree;
 101
 102 /*
 103  *      We keep the proxy FD's here.  The RADIUS Id's are marked
 104  *      "allocated" per Id, via a bit per proxy FD.
 105  */
 106 static int              proxy_fds[32];
 107
 108 static uint32_t         proxy_ipaddr;
 109
 110 /*
 111  *      We can use 256 RADIUS Id's per dst ipaddr/port, per server
 112  *      socket.  So, to allocate them, we key off of dst ipaddr/port,
 113  *      and then search the RADIUS Id's, looking for an unused socket.
 114  *
 115  *      We do NOT key off of socket fd's, here, either.  Instead,
 116  *      we look for a free Id from a sockfd, any sockfd.
 117  */
 118 typedef struct proxy_id_t {
 119         uint32_t        dst_ipaddr;
 120         int             dst_port;
 121
 122         /*
 123          *      FIXME: Allocate more proxy sockets when this gets full.
 124          */
 125         int             index;
 126         uint32_t        mask;   /* of FD's we know about. */
 127         uint32_t        id[1];  /* really id[256] */
 128 } proxy_id_t;
 129
 130
 131 /*
 132  *      Find a matching entry in the proxy ID tree.
 133  */
 134 static int proxy_id_cmp(const void *one, const void *two)
 135 {
 136         const proxy_id_t *a = one;
 137         const proxy_id_t *b = two;
 138
 139         /*
 140          *      The following comparisons look weird, but it's
 141          *      the only way to make the comparisons work.
 142          */
 143         if (a->dst_ipaddr < b->dst_ipaddr) return -1;
 144         if (a->dst_ipaddr > b->dst_ipaddr) return +1;
 145
 146         if (a->dst_port < b->dst_port) return -1;
 147         if (a->dst_port > b->dst_port) return +1;
 148
 149         /*
 150          *      Everything's equal.  Say so.
 151          */
 152         return 0;
 153 }
 154
 155
 156 /*
 157  *      Compare two REQUEST data structures, based on a number
 158  *      of criteria.
 159  */
 160 static int request_cmp(const void *one, const void *two)
 161 {
 162         const REQUEST *a = one;
 163         const REQUEST *b = two;
 164
 165         /*
 166          *      The following comparisons look weird, but it's
 167          *      the only way to make the comparisons work.
 168          */
 169
 170         /*
 171          *      If the packets didn't arrive on the same socket,
 172          *      they're not identical, no matter what their src/dst
 173          *      ip/ports say.
 174          */
 175         if (a->packet->sockfd < b->packet->sockfd) return -1;
 176         if (a->packet->sockfd > b->packet->sockfd) return +1;
 177
 178         if (a->packet->id < b->packet->id) return -1;
 179         if (a->packet->id > b->packet->id) return +1;
 180
 181         if (a->packet->code < b->packet->code) return -1;
 182         if (a->packet->code > b->packet->code) return +1;
 183
 184         if (a->packet->src_ipaddr < b->packet->src_ipaddr) return -1;
 185         if (a->packet->src_ipaddr > b->packet->src_ipaddr) return +1;
 186
 187         if (a->packet->src_port < b->packet->src_port) return -1;
 188         if (a->packet->src_port > b->packet->src_port) return +1;
 189
 190         /*
 191          *      Hmm... we may be listening on IPADDR_ANY, in which case
 192          *      the destination IP is important, too.
 193          */
 194         if (a->packet->dst_ipaddr < b->packet->dst_ipaddr) return -1;
 195         if (a->packet->dst_ipaddr > b->packet->dst_ipaddr) return +1;
 196
 197         if (a->packet->dst_port < b->packet->dst_port) return -1;
 198         if (a->packet->dst_port > b->packet->dst_port) return +1;
 199
 200         /*
 201          *      Everything's equal.  Say so.
 202          */
 203         return 0;
 204 }
 205
 206 /*
 207  *      Compare two REQUEST data structures, based on a number
 208  *      of criteria, for proxied packets.
 209  */
 210 static int proxy_cmp(const void *one, const void *two)
 211 {
 212         const REQUEST *a = one;
 213         const REQUEST *b = two;
 214
 215         rad_assert(a->magic == REQUEST_MAGIC);
 216         rad_assert(b->magic == REQUEST_MAGIC);
 217
 218         rad_assert(a->proxy != NULL);
 219         rad_assert(b->proxy != NULL);
 220
 221         /*
 222          *      The following code looks unreasonable, but it's
 223          *      the only way to make the comparisons work.
 224          */
 225         if (a->proxy->sockfd < b->proxy->sockfd) return -1;
 226         if (a->proxy->sockfd > b->proxy->sockfd) return +1;
 227
 228         if (a->proxy->id < b->proxy->id) return -1;
 229         if (a->proxy->id > b->proxy->id) return +1;
 230
 231         /*
 232          *      We've got to check packet codes, too.  But
 233          *      this should be done later, by someone else...
 234          */
 235
 236         if (a->proxy->dst_ipaddr < b->proxy->dst_ipaddr) return -1;
 237         if (a->proxy->dst_ipaddr > b->proxy->dst_ipaddr) return +1;
 238
 239         if (a->proxy->dst_port < b->proxy->dst_port) return -1;
 240         if (a->proxy->dst_port > b->proxy->dst_port) return +1;
 241
 242         /*
 243          *      FIXME: Check the Proxy-State attribute, too.
 244          *      This will help cut down on duplicates.
 245          */
 246
 247         /*
 248          *      Everything's equal.  Say so.
 249          */
 250         return 0;
 251 }
 252
 253 void rl_free(void)
 254 {
 255         rbtree_free(request_tree);
 256         rbtree_free(proxy_tree);
 257 }
 258
 259
 260 /*
 261  *      Initialize the request list.
 262  */
 263 int rl_init(void)
 264 {
 265         /*
 266          *      Initialize the request_list[] array.
 267          */
 268         memset(request_list, 0, sizeof(request_list));
 269
 270         request_tree = rbtree_create(request_cmp, NULL, 0);
 271         if (!request_tree) {
 272                 rad_assert("FAIL" == NULL);
 273         }
 274
 275         /*
 276          *      Create the tree for managing proxied requests and
 277          *      responses.
 278          */
 279         proxy_tree = rbtree_create(proxy_cmp, NULL, 1);
 280         if (!proxy_tree) {
 281                 rad_assert("FAIL" == NULL);
 282         }
 283
 284         /*
 285          *      Create the tree for allocating proxy ID's.
 286          */
 287         proxy_id_tree = rbtree_create(proxy_id_cmp, NULL, 0);
 288         if (!proxy_id_tree) {
 289                 rad_assert("FAIL" == NULL);
 290         }
 291
 292 #ifdef HAVE_PTHREAD_H
 293         /*
 294          *      For now, always create the mutex.
 295          *
 296          *      Later, we can only create it if there are multiple threads.
 297          */
 298         if (pthread_mutex_init(&proxy_mutex, NULL) != 0) {
 299                 radlog(L_ERR, "FATAL: Failed to initialize proxy mutex: %s",
 300                        strerror(errno));
 301                 exit(1);
 302         }
 303 #endif
 304
 305         /*
 306          *      The Id allocation table is done by bits, so we have
 307          *      32 bits per Id.  These bits indicate which entry
 308          *      in the proxy_fds array is used for that Id.
 309          *
 310          *      This design allows 256*32 = 8k requests to be
 311          *      outstanding to a home server, before something goes
 312          *      wrong.
 313          */
 314         {
 315                 int i;
 316                 rad_listen_t *listener;
 317
 318                 /*
 319                  *      Mark the Fd's as unused.
 320                  */
 321                 for (i = 0; i < 32; i++) proxy_fds[i] = -1;
 322
 323                 for (listener = mainconfig.listen;
 324                      listener != NULL;
 325                      listener = listener->next) {
 326                         if (listener->type == RAD_LISTEN_PROXY) {
 327                                 proxy_ipaddr = listener->ipaddr;
 328                                 proxy_fds[listener->fd & 0x1f] = listener->fd;
 329                                 break;
 330                         }
 331                 }
 332         }
 333
 334         return 1;
 335 }
 336
 337
 338 /*
 339  *      Delete a request from the proxy trees.
 340  */
 341 static void rl_delete_proxy(REQUEST *request, rbnode_t *node)
 342 {
 343         proxy_id_t      myid, *entry;
 344
 345         rad_assert(node != NULL);
 346
 347         rbtree_delete(proxy_tree, node);
 348
 349         myid.dst_ipaddr = request->proxy->dst_ipaddr;
 350         myid.dst_port = request->proxy->dst_port;
 351
 352         /*
 353          *      Find the Id in the array of allocated Id's,
 354          *      and delete it.
 355          */
 356         entry = rbtree_finddata(proxy_id_tree, &myid);
 357         if (entry) {
 358                 int i;
 359
 360                 DEBUG3(" proxy: de-allocating %08x:%d %d",
 361                        entry->dst_ipaddr,
 362                        entry->dst_port,
 363                        request->proxy->id);
 364
 365                 /*
 366                  *      Find the proxy socket associated with this
 367                  *      Id.  We loop over all 32 proxy fd's, but we
 368                  *      partially index by proxy fd's, which means
 369                  *      that we almost always break out of the loop
 370                  *      quickly.
 371                  */
 372                 for (i = 0; i < 32; i++) {
 373                         int offset;
 374
 375                         offset = (request->proxy->sockfd + i) & 0x1f;
 376
 377                         if (proxy_fds[offset] == request->proxy->sockfd) {
 378
 379                                 entry->id[request->proxy->id] &= ~(1 << offset);
 380                                 break;
 381                         }
 382                 } /* else die horribly? */
 383         } else {
 384                 /*
 385                  *      Hmm... not sure what to do here.
 386                  */
 387                 DEBUG3(" proxy: FAILED TO FIND %08x:%d %d",
 388                        myid.dst_ipaddr,
 389                        myid.dst_port,
 390                        request->proxy->id);
 391         }
 392 }
 393
 394
 395 /*
 396  *      Delete a particular request.
 397  */
 398 void rl_delete(REQUEST *request)
 399 {
 400         int id;
 401         REQNODE *prev, *next;
 402
 403         prev = ((REQNODE *) request->container)->prev;
 404         next = ((REQNODE *) request->container)->next;
 405
 406         id = request->packet->id;
 407
 408         /*
 409          *      Update the last request we touched.
 410          *
 411          *      This is so the periodic "walk & clean list"
 412          *      function, below, doesn't walk over all requests
 413          *      all of the time.  Rather, it tries to amortize
 414          *      the cost...
 415          */
 416         if (last_request == request) {
 417                 last_request = rl_next(last_request);
 418         }
 419
 420
 421         if (prev == NULL) {
 422                 request_list[id].first_request = next;
 423         } else {
 424                 prev->next = next;
 425         }
 426
 427         if (next == NULL) {
 428                 request_list[id].last_request = prev;
 429         } else {
 430                 next->prev = prev;
 431         }
 432
 433         free(request->container);
 434
 435 #ifdef WITH_SNMP
 436         /*
 437          *      Update the SNMP statistics.
 438          *
 439          *      Note that we do NOT do this in rad_respond(),
 440          *      as that function is called from child threads.
 441          *      Instead, we update the stats when a request is
 442          *      deleted, because only the main server thread calls
 443          *      this function...
 444          */
 445         if (mainconfig.do_snmp) {
 446                 switch (request->reply->code) {
 447                 case PW_AUTHENTICATION_ACK:
 448                   rad_snmp.auth.total_responses++;
 449                   rad_snmp.auth.total_access_accepts++;
 450                   break;
 451
 452                 case PW_AUTHENTICATION_REJECT:
 453                   rad_snmp.auth.total_responses++;
 454                   rad_snmp.auth.total_access_rejects++;
 455                   break;
 456
 457                 case PW_ACCESS_CHALLENGE:
 458                   rad_snmp.auth.total_responses++;
 459                   rad_snmp.auth.total_access_challenges++;
 460                   break;
 461
 462                 case PW_ACCOUNTING_RESPONSE:
 463                   rad_snmp.acct.total_responses++;
 464                   break;
 465
 466                 default:
 467                         break;
 468                 }
 469         }
 470 #endif
 471
 472         /*
 473          *      Delete the request from the tree.
 474          */
 475         {
 476                 rbnode_t *node;
 477
 478                 node = rbtree_find(request_tree, request);
 479                 rad_assert(node != NULL);
 480                 rbtree_delete(request_tree, node);
 481
 482
 483                 /*
 484                  *      If there's a proxied packet, and we're still
 485                  *      waiting for a reply, then delete the packet
 486                  *      from the list of outstanding proxied requests.
 487                  */
 488                 if (request->proxy &&
 489                     (request->proxy_outstanding > 0)) {
 490                         pthread_mutex_lock(&proxy_mutex);
 491                         node = rbtree_find(proxy_tree, request);
 492                         rl_delete_proxy(request, node);
 493                         pthread_mutex_unlock(&proxy_mutex);
 494                 }
 495         }
 496
 497         request_free(&request);
 498         request_list[id].request_count--;
 499
 500 }
 501
 502 /*
 503  *      Add a request to the request list.
 504  */
 505 void rl_add(REQUEST *request)
 506 {
 507         int id = request->packet->id;
 508         REQNODE *node;
 509
 510         rad_assert(request->container == NULL);
 511
 512         request->container = rad_malloc(sizeof(REQNODE));
 513         node = (REQNODE *) request->container;
 514         node->req = request;
 515
 516         node->prev = NULL;
 517         node->next = NULL;
 518
 519         if (!request_list[id].first_request) {
 520                 rad_assert(request_list[id].request_count == 0);
 521
 522                 request_list[id].first_request = node;
 523                 request_list[id].last_request = node;
 524         } else {
 525                 rad_assert(request_list[id].request_count != 0);
 526
 527                 node->prev = request_list[id].last_request;
 528                 request_list[id].last_request->next = node;
 529                 request_list[id].last_request = node;
 530         }
 531
 532         /*
 533          *      Insert the request into the tree.
 534          */
 535         if (rbtree_insert(request_tree, request) == 0) {
 536                 rad_assert("FAIL" == NULL);
 537         }
 538
 539         request_list[id].request_count++;
 540 }
 541
 542 /*
 543  *      Look up a particular request, using:
 544  *
 545  *      Request ID, request code, source IP, source port,
 546  *
 547  *      Note that we do NOT use the request vector to look up requests.
 548  *
 549  *      We MUST NOT have two requests with identical (id/code/IP/port), and
 550  *      different vectors.  This is a serious error!
 551  */
 552 REQUEST *rl_find(RADIUS_PACKET *packet)
 553 {
 554         REQUEST myrequest;
 555
 556         myrequest.packet = packet;
 557
 558         return rbtree_finddata(request_tree, &myrequest);
 559 }
 560
 561 /*
 562  *      See mainconfig.c
 563  */
 564 extern int proxy_new_listener(void);
 565
 566 /*
 567  *      Add an entry to the proxy tree.
 568  *
 569  *      This is the ONLY function in this source file which may be called
 570  *      from a child thread.  It therefore needs mutexes...
 571  */
 572 int rl_add_proxy(REQUEST *request)
 573 {
 574         int             i, found, proxy;
 575         uint32_t        mask;
 576         proxy_id_t      myid, *entry;
 577
 578         myid.dst_ipaddr = request->proxy->dst_ipaddr;
 579         myid.dst_port = request->proxy->dst_port;
 580
 581         /*
 582          *      Proxied requests get sent out the proxy FD ONLY.
 583          *
 584          *      FIXME: Once we allocate multiple proxy FD's, move this
 585          *      code to below, so we can have more than 256 requests
 586          *      outstanding.
 587          */
 588         request->proxy_outstanding = 1;
 589
 590         pthread_mutex_lock(&proxy_mutex);
 591
 592         /*
 593          *      Assign a proxy ID.
 594          */
 595         entry = rbtree_finddata(proxy_id_tree, &myid);
 596         if (!entry) {   /* allocate it */
 597                 entry = rad_malloc(sizeof(*entry) + sizeof(entry->id) * 255);
 598
 599                 entry->dst_ipaddr = request->proxy->dst_ipaddr;
 600                 entry->dst_port = request->proxy->dst_port;
 601                 entry->index = 0;
 602
 603                 DEBUG3(" proxy: creating %08x:%d",
 604                        entry->dst_ipaddr,
 605                        entry->dst_port);
 606
 607                 /*
 608                  *      Insert the new home server entry into
 609                  *      the tree.
 610                  *
 611                  *      FIXME: We don't (currently) delete the
 612                  *      entries, so this is technically a
 613                  *      memory leak.
 614                  */
 615                 if (rbtree_insert(proxy_id_tree, entry) == 0) {
 616                         DEBUG2("ERROR: Failed to insert entry into proxy Id tree");
 617                         free(entry);
 618                         return 0;
 619                 }
 620
 621                 /*
 622                  *      Clear out bits in the array which DO have
 623                  *      proxy Fd's associated with them.  We do this
 624                  *      by getting the mask of bits which have proxy
 625                  *      fd's...  */
 626                 mask = 0;
 627                 for (i = 0; i < 32; i++) {
 628                         if (proxy_fds[i] != -1) {
 629                                 mask |= (1 << i);
 630                         }
 631                 }
 632                 rad_assert(mask != 0);
 633
 634                 /*
 635                  *      Set bits here indicate that the Fd is in use.
 636                  */
 637                 entry->mask = mask;
 638
 639                 mask = ~mask;
 640
 641                 /*
 642                  *      Set the bits which are unused (and therefore
 643                  *      allocated).  The clear bits indicate that the Id
 644                  *      for that FD is unused.
 645                  */
 646                 for (i = 0; i < 256; i++) {
 647                         entry->id[i] = mask;
 648                 }
 649         } /* else the entry already existed in the proxy Id tree */
 650
 651  retry:
 652         /*
 653          *      Try to find a free Id.
 654          */
 655         found = -1;
 656         for (i = 0; i < 256; i++) {
 657                 /*
 658                  *      Some bits are still zero..
 659                  */
 660                 if (entry->id[(i + entry->index) & 0xff] != (uint32_t) ~0) {
 661                         found = (i + entry->index) & 0xff;
 662                         break;
 663                 }
 664
 665                 /*
 666                  *      Hmm... do we want to re-use Id's, when we
 667                  *      haven't seen all of the responses?
 668                  */
 669         }
 670
 671         /*
 672          *      No free Id, try to get a new FD.
 673          */
 674         if (found < 0) {
 675                 /*
 676                  *      First, see if there were FD's recently allocated,
 677                  *      which we don't know about.
 678                  */
 679                 mask = 0;
 680                 for (i = 0; i < 32; i++) {
 681                         if (proxy_fds[i] < 0) continue;
 682
 683                         mask |= (1 << i);
 684                 }
 685
 686                 /*
 687                  *      There ARE more FD's than we know about.
 688                  *      Update the masks for Id's, and re-try.
 689                  */
 690                 if (entry->mask != mask) {
 691                         /*
 692                          *      New mask always has more bits than
 693                          *      the old one, but never fewer bits.
 694                          */
 695                         rad_assert((entry->mask & mask) == entry->mask);
 696
 697                         /*
 698                          *      Clear the bits we already know about,
 699                          *      and then or in those bits into the
 700                          *      global mask.
 701                          */
 702                         mask ^= entry->mask;
 703                         entry->mask |= mask;
 704                         mask = ~mask;
 705
 706                         /*
 707                          *      Clear the bits in the Id's for the new
 708                          *      FD's.
 709                          */
 710                         for (i = 0; i < 256; i++) {
 711                                 entry->id[i] &= mask;
 712                         }
 713
 714                         /*
 715                          *      And try again to allocate an Id.
 716                          */
 717                         goto retry;
 718                 } /* else no new Fd's were allocated. */
 719
 720                 /*
 721                  *      If all Fd's are allocated, die.
 722                  */
 723                 if (~mask == 0) {
 724                         radlog(L_ERR|L_CONS, "ERROR: More than 8000 proxied requests outstanding for home server %08x:%d",
 725                                ntohs(entry->dst_ipaddr), entry->dst_port);
 726                         return 0;
 727                 }
 728
 729                 /*
 730                  *      Allocate a new proxy Fd.  This function adds it
 731                  *      into the list of listeners.
 732                  */
 733                 proxy = proxy_new_listener();
 734                 if (proxy < 0) {
 735                         DEBUG2("ERROR: Failed to create a new socket for proxying requests.");
 736                         return 0;
 737                 }
 738
 739                 /*
 740                  *
 741                  */
 742                 found = -1;
 743                 for (i = 0; i < 32; i++) {
 744                         /*
 745                          *      Found a free entry.  Save the socket,
 746                          *      and remember where we saved it.
 747                          */
 748                         if (proxy_fds[(proxy + i) & 0x1f] == -1) {
 749                                 proxy_fds[(proxy + i) & 0x1f] = proxy;
 750                                 found = (proxy + i) & 0x1f;
 751                                 break;
 752                         }
 753                 }
 754                 rad_assert(found >= 0); /* i.e. the mask had free bits. */
 755
 756                 mask = 1 << found;
 757                 entry->mask |= mask;
 758                 mask = ~mask;
 759
 760                 /*
 761                  *      Clear the relevant bits in the mask.
 762                  */
 763                 for (i = 0; i < 256; i++) {
 764                         entry->id[i] &= mask;
 765                 }
 766
 767                 /*
 768                  *      Pick a random Id to start from, as we've
 769                  *      just guaranteed that it's free.
 770                  */
 771                 found = lrad_rand() & 0xff;
 772         }
 773
 774         /*
 775          *      Mark next (hopefully unused) entry.
 776          */
 777         entry->index = (found + 1) & 0xff;
 778
 779         /*
 780          *      We now have to find WHICH proxy fd to use.
 781          */
 782         proxy = -1;
 783         for (i = 0; i < 32; i++) {
 784                 /*
 785                  *      FIXME: pick a random socket to use?
 786                  */
 787                 if ((entry->id[found] & (1 << i)) == 0) {
 788                         proxy = i;
 789                         break;
 790                 }
 791         }
 792
 793         /*
 794          *      There was no bit clear, which we had just checked above...
 795          */
 796         rad_assert(proxy != -1);
 797
 798         /*
 799          *      Mark the Id as allocated, for thei Fd.
 800          */
 801         entry->id[found] |= (1 << proxy);
 802         request->proxy->id = found;
 803         request->proxy->src_ipaddr = proxy_ipaddr;
 804
 805         rad_assert(proxy_fds[proxy] != -1);
 806         request->proxy->sockfd = proxy_fds[proxy];
 807
 808         DEBUG3(" proxy: allocating %08x:%d %d",
 809                entry->dst_ipaddr,
 810                entry->dst_port,
 811                request->proxy->id);
 812
 813         if (!rbtree_insert(proxy_tree, request)) {
 814                 DEBUG2("ERROR: Failed to insert entry into proxy tree");
 815                 return 0;
 816         }
 817
 818         pthread_mutex_unlock(&proxy_mutex);
 819
 820         return 1;
 821 }
 822
 823
 824 /*
 825  *      Look up a particular request, using:
 826  *
 827  *      Request Id, request code, source IP, source port,
 828  *
 829  *      Note that we do NOT use the request vector to look up requests.
 830  *
 831  *      We MUST NOT have two requests with identical (id/code/IP/port), and
 832  *      different vectors.  This is a serious error!
 833  */
 834 REQUEST *rl_find_proxy(RADIUS_PACKET *packet)
 835 {
 836         rbnode_t        *node;
 837         REQUEST         myrequest, *maybe = NULL;
 838         RADIUS_PACKET   myproxy;
 839
 840         /*
 841          *      If we use the socket FD as an indicator,
 842          *      then that implicitely contains information
 843          *      as to our src ipaddr/port, so we don't need
 844          *      to use that in the comparisons.
 845          */
 846         myproxy.sockfd = packet->sockfd;
 847         myproxy.id = packet->id;
 848         myproxy.dst_ipaddr = packet->src_ipaddr;
 849         myproxy.dst_port = packet->src_port;
 850
 851 #ifndef NDEBUG
 852         myrequest.magic = REQUEST_MAGIC;
 853 #endif
 854         myrequest.proxy = &myproxy;
 855
 856         pthread_mutex_lock(&proxy_mutex);
 857         node = rbtree_find(proxy_tree, &myrequest);
 858
 859         if (node) {
 860                 maybe = rbtree_node2data(proxy_tree, node);
 861                 rad_assert(maybe->proxy_outstanding > 0);
 862                 maybe->proxy_outstanding--;
 863
 864                 /*
 865                  *      Received all of the replies we expect.
 866                  *      delete it from both trees.
 867                  */
 868                 if (maybe->proxy_outstanding == 0) {
 869                         rl_delete_proxy(&myrequest, node);
 870                 }
 871         }
 872         pthread_mutex_unlock(&proxy_mutex);
 873
 874         return maybe;
 875 }
 876
 877
 878 /*
 879  *      Walk over all requests, performing a callback for each request.
 880  */
 881 int rl_walk(RL_WALK_FUNC walker, void *data)
 882 {
 883         int id, rcode;
 884         REQNODE *curreq, *next;
 885
 886         /*
 887          *      Walk over all 256 ID's.
 888          */
 889         for (id = 0; id < 256; id++) {
 890
 891                 /*
 892                  *      Walk over the request list for each ID.
 893                  */
 894                 for (curreq = request_list[id].first_request;
 895                                 curreq != NULL ;
 896                                 curreq = next) {
 897                         /*
 898                          *      The callback MIGHT delete the current
 899                          *      request, so we CANNOT depend on curreq->next
 900                          *      to be there, when going to the next element
 901                          *      in the 'for' loop.
 902                          */
 903                         next = curreq->next;
 904
 905                         rcode = walker(curreq->req, data);
 906                         if (rcode != RL_WALK_CONTINUE) {
 907                                 return rcode;
 908                         }
 909                 }
 910         }
 911
 912         return 0;
 913 }
 914
 915
 916 /*
 917  *      Walk from one request to the next.
 918  */
 919 REQUEST *rl_next(REQUEST *request)
 920 {
 921         int id, start_id;
 922         int count;
 923
 924         /*
 925          *      If we were passed a request, then go to the "next" one.
 926          */
 927         if (request != NULL) {
 928                 rad_assert(request->magic == REQUEST_MAGIC);
 929
 930                 /*
 931                  *      It has a "next", return it.
 932                  */
 933                 if (((REQNODE *)request->container)->next != NULL) {
 934                         return ((REQNODE *)request->container)->next->req;
 935                 } else {
 936                         /*
 937                          *      No "next", increment the ID, and look
 938                          *      at that one.
 939                          */
 940                         start_id = request->packet->id + 1;
 941                         start_id &= 0xff;
 942                         count = 255;
 943                 }
 944         } else {
 945                 /*
 946                  *      No input request, start looking at ID 0.
 947                  */
 948                 start_id = 0;
 949                 count = 256;
 950         }
 951
 952         /*
 953          *      Check all ID's, wrapping around at 255.
 954          */
 955         for (id = start_id; id < (start_id + count); id++) {
 956
 957                 /*
 958                  *      This ID has a request, return it.
 959                  */
 960                 if (request_list[id & 0xff].first_request != NULL) {
 961                         rad_assert(request_list[id&0xff].first_request->req != request);
 962
 963                         return request_list[id & 0xff].first_request->req;
 964                 }
 965         }
 966
 967         /*
 968          *      No requests at all in the list. Nothing to do.
 969          */
 970         DEBUG3("rl_next:  returning NULL");
 971         return NULL;
 972 }
 973
 974
 975 /*
 976  *      Return the number of requests in the request list.
 977  */
 978 int rl_num_requests(void)
 979 {
 980         int id;
 981         int request_count = 0;
 982
 983         for (id = 0; id < 256; id++) {
 984                 request_count += request_list[id].request_count;
 985         }
 986
 987         return request_count;
 988 }
 989
 990
 991 typedef struct rl_walk_t {
 992         time_t  now;
 993         time_t  smallest;
 994 } rl_walk_t;
 995
 996
 997 /*
 998  *  Refresh a request, by using proxy_retry_delay, cleanup_delay,
 999  *  max_request_time, etc.
1000  *
1001  *  When walking over the request list, all of the per-request
1002  *  magic is done here.
1003  */
1004 static int refresh_request(REQUEST *request, void *data)
1005 {
1006         rl_walk_t *info = (rl_walk_t *) data;
1007         time_t difference;
1008         child_pid_t child_pid;
1009
1010         rad_assert(request->magic == REQUEST_MAGIC);
1011
1012         /*
1013          *  If the request is marked as a delayed reject, AND it's
1014          *  time to send the reject, then do so now.
1015          */
1016         if (request->finished &&
1017             ((request->options & RAD_REQUEST_OPTION_DELAYED_REJECT) != 0)) {
1018                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1019
1020                 difference = info->now - request->timestamp;
1021                 if (difference >= (time_t) mainconfig.reject_delay) {
1022
1023                         /*
1024                          *  Clear the 'delayed reject' bit, so that we
1025                          *  don't do this again.
1026                          */
1027                         request->options &= ~RAD_REQUEST_OPTION_DELAYED_REJECT;
1028                         rad_send(request->reply, request->packet,
1029                                  request->secret);
1030                 }
1031         }
1032
1033         /*
1034          *  If the request has finished processing, AND it's child has
1035          *  been cleaned up, AND it's time to clean up the request,
1036          *  OR, it's an accounting request.  THEN, go delete it.
1037          *
1038          *  If this is a request which had the "don't cache" option
1039          *  set, then delete it immediately, as it CANNOT have a
1040          *  duplicate.
1041          */
1042         if (request->finished &&
1043             ((request->timestamp + mainconfig.cleanup_delay <= info->now) ||
1044              ((request->options & RAD_REQUEST_OPTION_DONT_CACHE) != 0))) {
1045                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1046
1047                 /*
1048                  *  Request completed, delete it, and unlink it
1049                  *  from the currently 'alive' list of requests.
1050                  */
1051                 DEBUG2("Cleaning up request %d ID %d with timestamp %08lx",
1052                                 request->number, request->packet->id,
1053                                 (unsigned long) request->timestamp);
1054
1055                 /*
1056                  *  Delete the request.
1057                  */
1058                 rl_delete(request);
1059                 return RL_WALK_CONTINUE;
1060         }
1061
1062         /*
1063          *  Maybe the child process handling the request has hung:
1064          *  kill it, and continue.
1065          */
1066         if ((request->timestamp + mainconfig.max_request_time) <= info->now) {
1067                 int number;
1068
1069                 child_pid = request->child_pid;
1070                 number = request->number;
1071
1072                 /*
1073                  *      There MUST be a RAD_PACKET reply.
1074                  */
1075                 rad_assert(request->reply != NULL);
1076
1077                 /*
1078                  *      If we've tried to proxy the request, and
1079                  *      the proxy server hasn't responded, then
1080                  *      we send a REJECT back to the caller.
1081                  *
1082                  *      For safety, we assert that there is no child
1083                  *      handling the request.  If the assertion fails,
1084                  *      it means that we've sent a proxied request to
1085                  *      the home server, and the child thread is still
1086                  *      sitting on the request!
1087                  */
1088                 if (request->proxy && !request->proxy_reply) {
1089                         rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1090
1091                         radlog(L_ERR, "Rejecting request %d due to lack of any response from home server %s:%d",
1092                                request->number,
1093                                client_name(request->packet->src_ipaddr),
1094                                request->packet->src_port);
1095                         request_reject(request);
1096                         request->finished = TRUE;
1097                         return RL_WALK_CONTINUE;
1098                 }
1099
1100                 if (mainconfig.kill_unresponsive_children) {
1101                         if (child_pid != NO_SUCH_CHILD_PID) {
1102                                 /*
1103                                  *  This request seems to have hung
1104                                  *   - kill it
1105                                  */
1106 #ifdef HAVE_PTHREAD_H
1107                                 radlog(L_ERR, "Killing unresponsive thread for request %d",
1108                                        request->number);
1109                                 pthread_cancel(child_pid);
1110 #endif
1111                         } /* else no proxy reply, quietly fail */
1112
1113                         /*
1114                          *      Maybe we haven't killed it.  In that
1115                          *      case, print a warning.
1116                          */
1117                 } else if ((child_pid != NO_SUCH_CHILD_PID) &&
1118                            ((request->options & RAD_REQUEST_OPTION_LOGGED_CHILD) == 0)) {
1119                         radlog(L_ERR, "WARNING: Unresponsive child (id %lu) for request %d",
1120                                (unsigned long)child_pid, number);
1121
1122                         /*
1123                          *  Set the option that we've sent a log message,
1124                          *  so that we don't send more than one message
1125                          *  per request.
1126                          */
1127                         request->options |= RAD_REQUEST_OPTION_LOGGED_CHILD;
1128                 }
1129
1130                 /*
1131                  *  Send a reject message for the request, mark it
1132                  *  finished, and forget about the child.
1133                  */
1134                 request_reject(request);
1135                 request->child_pid = NO_SUCH_CHILD_PID;
1136                 if (mainconfig.kill_unresponsive_children)
1137                         request->finished = TRUE;
1138                 return RL_WALK_CONTINUE;
1139         } /* the request has been in the queue for too long */
1140
1141         /*
1142          *  If the request is still being processed, then due to the
1143          *  above check, it's still within it's time limit.  In that
1144          *  case, don't do anything.
1145          */
1146         if (request->child_pid != NO_SUCH_CHILD_PID) {
1147                 return RL_WALK_CONTINUE;
1148         }
1149
1150         /*
1151          *  The request is finished.
1152          */
1153         if (request->finished) goto setup_timeout;
1154
1155         /*
1156          *  We're not proxying requests at all.
1157          */
1158         if (!mainconfig.proxy_requests) goto setup_timeout;
1159
1160         /*
1161          *  We're proxying synchronously, so we don't retry it here.
1162          *  Some other code takes care of retrying the proxy requests.
1163          */
1164         if (mainconfig.proxy_synchronous) goto setup_timeout;
1165
1166         /*
1167          *  The proxy retry delay is zero, meaning don't retry.
1168          */
1169         if (mainconfig.proxy_retry_delay == 0) goto setup_timeout;
1170
1171         /*
1172          *  There is no proxied request for this packet, so there's
1173          *  no proxy retries.
1174          */
1175         if (!request->proxy) goto setup_timeout;
1176
1177         /*
1178          *  We've already seen the proxy reply, so we don't need
1179          *  to send another proxy request.
1180          */
1181         if (request->proxy_reply) goto setup_timeout;
1182
1183         /*
1184          *  It's not yet time to re-send this proxied request.
1185          */
1186         if (request->proxy_next_try > info->now) goto setup_timeout;
1187
1188         /*
1189          *  If the proxy retry count is zero, then
1190          *  we've sent the last try, and have NOT received
1191          *  a reply from the end server.  In that case,
1192          *  we don't bother trying again, but just mark
1193          *  the request as finished, and go to the next one.
1194          */
1195         if (request->proxy_try_count == 0) {
1196                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1197                 request_reject(request);
1198                 realm_disable(request->proxy->dst_ipaddr,request->proxy->dst_port);
1199                 request->finished = TRUE;
1200                 goto setup_timeout;
1201         }
1202
1203         /*
1204          *  We're trying one more time, so count down
1205          *  the tries, and set the next try time.
1206          */
1207         request->proxy_try_count--;
1208         request->proxy_next_try = info->now + mainconfig.proxy_retry_delay;
1209
1210         /* Fix up Acct-Delay-Time */
1211         if (request->proxy->code == PW_ACCOUNTING_REQUEST) {
1212                 VALUE_PAIR *delaypair;
1213                 delaypair = pairfind(request->proxy->vps, PW_ACCT_DELAY_TIME);
1214
1215                 if (!delaypair) {
1216                         delaypair = paircreate(PW_ACCT_DELAY_TIME, PW_TYPE_INTEGER);
1217                         if (!delaypair) {
1218                                 radlog(L_ERR|L_CONS, "no memory");
1219                                 exit(1);
1220                         }
1221                         pairadd(&request->proxy->vps, delaypair);
1222                 }
1223                 delaypair->lvalue = info->now - request->proxy->timestamp;
1224
1225                 /* Must recompile the valuepairs to wire format */
1226                 free(request->proxy->data);
1227                 request->proxy->data = NULL;
1228         } /* proxy accounting request */
1229
1230         /*
1231          *  Assert that we have NOT seen the proxy reply yet.
1232          *
1233          *  If we HAVE seen it, then we SHOULD NOT be bugging the
1234          *  home server!
1235          */
1236         rad_assert(request->proxy_reply == NULL);
1237
1238         /*
1239          *  Send the proxy packet.
1240          */
1241         request->proxy_outstanding++;
1242         rad_send(request->proxy, NULL, request->proxysecret);
1243
1244 setup_timeout:
1245         /*
1246          *  Don't do more long-term checks, if we've got to wake
1247          *  up now.
1248          */
1249         if (info->smallest == 0) {
1250                 return RL_WALK_CONTINUE;
1251         }
1252
1253         /*
1254          *  The request is finished.  Wake up when it's time to
1255          *  clean it up.
1256          */
1257         if (request->finished) {
1258                 difference = (request->timestamp + mainconfig.cleanup_delay) - info->now;
1259
1260                 /*
1261                  *  If the request is marked up to be rejected later,
1262                  *  then wake up later.
1263                  */
1264                 if ((request->options & RAD_REQUEST_OPTION_DELAYED_REJECT) != 0) {
1265                         if (difference >= (time_t) mainconfig.reject_delay) {
1266                                 difference = (time_t) mainconfig.reject_delay;
1267                         }
1268                 }
1269
1270         } else if (request->proxy && !request->proxy_reply) {
1271                 /*
1272                  *  The request is NOT finished, but there is an
1273                  *  outstanding proxy request, with no matching
1274                  *  proxy reply.
1275                  *
1276                  *  Wake up when it's time to re-send
1277                  *  the proxy request.
1278                  *
1279                  *  But in synchronous proxy, we don't retry but we update
1280                  *  the next retry time as NAS has not resent the request
1281                  *  in the given retry window.
1282                  */
1283                 if (mainconfig.proxy_synchronous) {
1284                         /*
1285                          *      If the retry_delay * count has passed,
1286                          *      then mark the realm dead.
1287                          */
1288                         if (info->now > (request->timestamp + (mainconfig.proxy_retry_delay * mainconfig.proxy_retry_count))) {
1289                                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1290                                 request_reject(request);
1291
1292                                 realm_disable(request->proxy->dst_ipaddr,
1293                                               request->proxy->dst_port);
1294                                 request->finished = TRUE;
1295                                 goto setup_timeout;
1296                         }
1297                         request->proxy_next_try = info->now + mainconfig.proxy_retry_delay;
1298                 }
1299                 difference = request->proxy_next_try - info->now;
1300         } else {
1301                 /*
1302                  *  The request is NOT finished.
1303                  *
1304                  *  Wake up when it's time to kill the errant
1305                  *  thread/process.
1306                  */
1307                 difference = (request->timestamp + mainconfig.max_request_time) - info->now;
1308         }
1309
1310         /*
1311          *  If the server is CPU starved, then we CAN miss a time
1312          *  for servicing requests.  In which case the 'difference'
1313          *  value will be negative.  select() doesn't like that,
1314          *  so we fix it.
1315          */
1316         if (difference < 0) {
1317                 difference = 0;
1318         }
1319
1320         /*
1321          *  Update the 'smallest' time.
1322          */
1323         if ((info->smallest < 0) ||
1324                 (difference < info->smallest)) {
1325                 info->smallest = difference;
1326         }
1327
1328         return RL_WALK_CONTINUE;
1329 }
1330
1331
1332 /*
1333  *  Clean up the request list, every so often.
1334  *
1335  *  This is done by walking through ALL of the list, and
1336  *  - marking any requests which are finished, and expired
1337  *  - killing any processes which are NOT finished after a delay
1338  *  - deleting any marked requests.
1339  */
1340 struct timeval *rl_clean_list(time_t now)
1341 {
1342         /*
1343          *  Static variables, so that we don't do all of this work
1344          *  more than once per second.
1345          *
1346          *  Note that we have 'tv' and 'last_tv'.  'last_tv' is
1347          *  pointed to by 'last_tv_ptr', and depending on the
1348          *  system implementation of select(), it MAY be modified.
1349          *
1350          *  In that was, we want to use the ORIGINAL value, from
1351          *  'tv', and wipe out the (possibly modified) last_tv.
1352          */
1353         static time_t last_cleaned_list = 0;
1354         static struct timeval tv, *last_tv_ptr = NULL;
1355         static struct timeval last_tv;
1356
1357         rl_walk_t info;
1358
1359         info.now = now;
1360         info.smallest = -1;
1361
1362         /*
1363          *  If we've already set up the timeout or cleaned the
1364          *  request list this second, then don't do it again.  We
1365          *  simply return the sleep delay from last time.
1366          *
1367          *  Note that if we returned NULL last time, there was nothing
1368          *  to do.  BUT we've been woken up since then, which can only
1369          *  happen if we received a packet.  And if we've received a
1370          *  packet, then there's some work to do in the future.
1371          *
1372          *  FIXME: We can probably use gettimeofday() for finer clock
1373          *  resolution, as the current method will cause it to sleep
1374          *  too long...
1375          */
1376         if ((last_tv_ptr != NULL) &&
1377             (last_cleaned_list == now) &&
1378             (tv.tv_sec != 0)) {
1379                 int i;
1380
1381                 /*
1382                  *  If we're NOT walking the entire request list,
1383                  *  then we want to iteratively check the request
1384                  *  list.
1385                  *
1386                  *  If there is NO previous request, go look for one.
1387                  */
1388                 if (!last_request)
1389                         last_request = rl_next(last_request);
1390
1391                 /*
1392                  *  On average, there will be one request per
1393                  *  'cleanup_delay' requests, which needs to be
1394                  *  serviced.
1395                  *
1396                  *  And only do this servicing, if we have a request
1397                  *  to service.
1398                  */
1399                 if (last_request)
1400                         for (i = 0; i < mainconfig.cleanup_delay; i++) {
1401                                 REQUEST *next;
1402
1403                                 /*
1404                                  *  This function call MAY delete the
1405                                  *  request pointed to by 'last_request'.
1406                                  */
1407                                 next = rl_next(last_request);
1408                                 refresh_request(last_request, &info);
1409                                 last_request = next;
1410
1411                                 /*
1412                                  *  Nothing to do any more, exit.
1413                                  */
1414                                 if (!last_request)
1415                                         break;
1416                         }
1417
1418                 last_tv = tv;
1419                 DEBUG2("Waking up in %d seconds...",
1420                                 (int) last_tv_ptr->tv_sec);
1421                 return last_tv_ptr;
1422         }
1423         last_cleaned_list = now;
1424         last_request = NULL;
1425         DEBUG2("--- Walking the entire request list ---");
1426
1427         /*
1428          *  Hmmm... this is Big Magic.  We make it seem like
1429          *  there's an additional second to wait, for a whole
1430          *  host of reasons which I can't explain adequately,
1431          *  but which cause the code to Just Work Right.
1432          */
1433         info.now--;
1434
1435         rl_walk(refresh_request, &info);
1436
1437         /*
1438          *  We haven't found a time at which we need to wake up.
1439          *  Return NULL, so that the select() call will sleep forever.
1440          */
1441         if (info.smallest < 0) {
1442                 /*
1443                  *  If we're not proxying, then there really isn't anything
1444                  *  to do.
1445                  *
1446                  *  If we ARE proxying, then we can safely sleep
1447                  *  forever if we're told to NEVER send proxy retries
1448                  *  ourselves, until the NAS kicks us again.
1449                  *
1450                  *  Otherwise, there are no outstanding requests, then
1451                  *  we can sleep forever.  This happens when we get
1452                  *  woken up with a bad packet.  It's discarded, so if
1453                  *  there are no live requests, we can safely sleep
1454                  *  forever.
1455                  */
1456                 if ((!mainconfig.proxy_requests) ||
1457                     mainconfig.proxy_synchronous ||
1458                     (rl_num_requests() == 0)) {
1459                         DEBUG2("Nothing to do.  Sleeping until we see a request.");
1460                         last_tv_ptr = NULL;
1461                         return NULL;
1462                 }
1463
1464                 /*
1465                  *  We ARE proxying.  In that case, we avoid a race condition
1466                  *  where a child thread handling a request proxies the
1467                  *  packet, and sets the retry delay.  In that case, we're
1468                  *  supposed to wake up in N seconds, but we can't, as
1469                  *  we're sleeping forever.
1470                  *
1471                  *  Instead, we prevent the problem by waking up anyhow
1472                  *  at the 'proxy_retry_delay' time, even if there's
1473                  *  nothing to do.  In the worst case, this will cause
1474                  *  the server to wake up every N seconds, to do a small
1475                  *  amount of unnecessary work.
1476                  */
1477                 info.smallest = mainconfig.proxy_retry_delay;
1478         }
1479         /*
1480          *  Set the time (in seconds) for how long we're
1481          *  supposed to sleep.
1482          */
1483         tv.tv_sec = info.smallest;
1484         tv.tv_usec = 0;
1485         DEBUG2("Waking up in %d seconds...", (int) info.smallest);
1486
1487         /*
1488          *  Remember how long we should sleep for.
1489          */
1490         last_tv = tv;
1491         last_tv_ptr = &last_tv;
1492         return last_tv_ptr;
1493 }