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 <freeradius-devel/autoconf.h>
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <signal.h>
  30
  31 #include <freeradius-devel/radiusd.h>
  32 #include <freeradius-devel/rad_assert.h>
  33 #include <freeradius-devel/request_list.h>
  34 #include <freeradius-devel/radius_snmp.h>
  35
  36 struct request_list_t {
  37         lrad_hash_table_t *ht;
  38         int collisions;
  39 };
  40
  41 typedef struct request_entry_t {
  42         struct request_entry_t *next;
  43         REQUEST                *request;
  44 } request_entry_t;
  45
  46
  47 #ifdef HAVE_PTHREAD_H
  48 static pthread_mutex_t  proxy_mutex;
  49 #else
  50 /*
  51  *      This is easier than ifdef's throughout the code.
  52  */
  53 #define pthread_mutex_lock(_x)
  54 #define pthread_mutex_unlock(_x)
  55 #endif
  56
  57 /*
  58  *      We keep track of packets we're proxying, keyed by
  59  *      source socket, and destination ip/port, and Id.
  60  */
  61 static rbtree_t         *proxy_tree;
  62
  63 /*
  64  *      We keep track of free/used Id's, by destination ip/port.
  65  *
  66  *      We need a different tree than above, because this one is NOT
  67  *      keyed by Id.  Instead, we use this one to allocate Id's.
  68  */
  69 static rbtree_t         *proxy_id_tree;
  70
  71 /*
  72  *      We keep the proxy FD's here.  The RADIUS Id's are marked
  73  *      "allocated" per Id, via a bit per proxy FD.
  74  */
  75 static int              proxy_fds[32];
  76 static rad_listen_t     *proxy_listeners[32];
  77
  78 /*
  79  *      We can use 256 RADIUS Id's per dst ipaddr/port, per server
  80  *      socket.  So, to allocate them, we key off of dst ipaddr/port,
  81  *      and then search the RADIUS Id's, looking for an unused socket.
  82  *
  83  *      We do NOT key off of socket fd's, here, either.  Instead,
  84  *      we look for a free Id from a sockfd, any sockfd.
  85  */
  86 typedef struct proxy_id_t {
  87         lrad_ipaddr_t   dst_ipaddr;
  88         int             dst_port;
  89
  90         /*
  91          *      FIXME: Allocate more proxy sockets when this gets full.
  92          */
  93         int             index;
  94         uint32_t        mask;   /* of FD's we know about. */
  95         uint32_t        id[1];  /* really id[256] */
  96 } proxy_id_t;
  97
  98
  99 /*
 100  *      Find a matching entry in the proxy ID tree.
 101  */
 102 static int proxy_id_cmp(const void *one, const void *two)
 103 {
 104         int rcode;
 105         const proxy_id_t *a = one;
 106         const proxy_id_t *b = two;
 107
 108         /*
 109          *      The following comparisons look weird, but it's
 110          *      the only way to make the comparisons work.
 111          */
 112         if (a->dst_port < b->dst_port) return -1;
 113         if (a->dst_port > b->dst_port) return +1;
 114
 115         if (a->dst_ipaddr.af < b->dst_ipaddr.af) return -1;
 116         if (a->dst_ipaddr.af > b->dst_ipaddr.af) return +1;
 117
 118         switch (a->dst_ipaddr.af) {
 119         case AF_INET:
 120                 rcode = memcmp(&a->dst_ipaddr.ipaddr.ip4addr,
 121                                &b->dst_ipaddr.ipaddr.ip4addr,
 122                                sizeof(a->dst_ipaddr.ipaddr.ip4addr));
 123                 break;
 124         case AF_INET6:
 125                 rcode = memcmp(&a->dst_ipaddr.ipaddr.ip6addr,
 126                                &b->dst_ipaddr.ipaddr.ip6addr,
 127                                sizeof(a->dst_ipaddr.ipaddr.ip6addr));
 128                 break;
 129         default:
 130                 return -1;      /* FIXME: die! */
 131                 break;
 132         }
 133         /*
 134          *      We could optimize this away, but the compiler should
 135          *      do that work for us, and this coding style helps us
 136          *      remember what to do if we add more checks later.
 137          */
 138         if (rcode != 0) return rcode;
 139
 140         /*
 141          *      Everything's equal.  Say so.
 142          */
 143         return 0;
 144 }
 145
 146
 147 static void packet_hash(RADIUS_PACKET *packet)
 148 {
 149         uint32_t hash;
 150
 151         hash = lrad_hash(&packet->src_port, sizeof(packet->src_port));
 152
 153         /*
 154          *      We shouldn't have to hash af, sockfd, code, or dst_port,
 155          *      as they're the same for one request_list_t
 156          */
 157 #if 0
 158         hash = lrad_hash_update(&packet->src_ipaddr.af,
 159                                 sizeof(packet->src_ipaddr.af), hash);
 160
 161         hash = lrad_hash_update(&packet->code, sizeof(packet->code), hash);
 162         hash = lrad_hash_update(&packet->sockfd, sizeof(packet->sockfd), hash);
 163         hash = lrad_hash_update(&packet->dst_port,
 164                                 sizeof(packet->dst_port), hash);
 165 #endif
 166
 167         /*
 168          *      The caller ensures that src & dst AF are the same.
 169          *
 170          *      We use dst IP in the hash, as the sockfd may be listening
 171          *      on "*", with udpfromto, to get multiple dst IP's.
 172          */
 173         switch (packet->src_ipaddr.af) {
 174         case AF_INET:
 175                 hash = lrad_hash_update(&packet->src_ipaddr.ipaddr.ip4addr,
 176                                         sizeof(packet->src_ipaddr.ipaddr.ip4addr),
 177                                         hash);
 178                 hash = lrad_hash_update(&packet->dst_ipaddr.ipaddr.ip4addr,
 179                                         sizeof(packet->dst_ipaddr.ipaddr.ip4addr),
 180                                         hash);
 181                 break;
 182         case AF_INET6:
 183                 hash = lrad_hash_update(&packet->src_ipaddr.ipaddr.ip6addr,
 184                                         sizeof(packet->src_ipaddr.ipaddr.ip6addr),
 185                                         hash);
 186                 hash = lrad_hash_update(&packet->dst_ipaddr.ipaddr.ip6addr,
 187                                         sizeof(packet->dst_ipaddr.ipaddr.ip6addr),
 188                                         hash);
 189                 break;
 190         default:
 191                 /* FIXME: die! */
 192                 break;
 193         }
 194
 195         /*
 196          *      Put the packet Id into the high byte of the hash,
 197          *      to minimize the number of possible collisions.
 198          *
 199          *      The hash table indexing is done via the low bits,
 200          *      so we shouldn't use those.
 201          */
 202         rad_assert((packet->id >= 0) && (packet->id < 256));
 203         packet->hash = packet->id << 24;
 204         packet->hash |= hash >> 8;
 205 }
 206
 207
 208 static int packet_cmp(const RADIUS_PACKET *a, const RADIUS_PACKET *b)
 209 {
 210
 211         if (a->id != b->id) return 0;
 212
 213         if (a->src_port != b->src_port) return 0;
 214
 215         switch (a->dst_ipaddr.af) {
 216         case AF_INET:
 217                 if (memcmp(&a->dst_ipaddr.ipaddr.ip4addr,
 218                            &b->dst_ipaddr.ipaddr.ip4addr,
 219                            sizeof(a->dst_ipaddr.ipaddr.ip4addr)) != 0)
 220                         return 0;
 221                 if (memcmp(&a->src_ipaddr.ipaddr.ip4addr,
 222                            &b->src_ipaddr.ipaddr.ip4addr,
 223                            sizeof(a->src_ipaddr.ipaddr.ip4addr)) != 0)
 224                         return 0;
 225                 break;
 226         case AF_INET6:
 227                 if (memcmp(&a->dst_ipaddr.ipaddr.ip6addr,
 228                            &b->dst_ipaddr.ipaddr.ip6addr,
 229                            sizeof(a->dst_ipaddr.ipaddr.ip6addr)) != 0)
 230                         return 0;
 231                 if (memcmp(&a->src_ipaddr.ipaddr.ip6addr,
 232                            &b->src_ipaddr.ipaddr.ip6addr,
 233                            sizeof(a->src_ipaddr.ipaddr.ip6addr)) != 0)
 234                         return 0;
 235                 break;
 236         default:
 237                 return 0;
 238                 break;
 239         }
 240
 241         /*
 242          *      These next comparisons should reall be assertions.
 243          */
 244         if (a->src_ipaddr.af != b->src_ipaddr.af) return 0;
 245
 246         if (a->dst_ipaddr.af != b->dst_ipaddr.af) return 0;
 247
 248         if (a->sockfd != b->sockfd) return 0;
 249
 250         if (a->code != b->code) return 0;
 251
 252         if (a->dst_port != b->dst_port) return 0;
 253
 254         /*
 255          *      Everything's equal.  Say so.
 256          */
 257         return 1;
 258 }
 259
 260 /*
 261  *      Compare two REQUEST data structures, based on a number
 262  *      of criteria, for proxied packets.
 263  */
 264 static int proxy_cmp(const void *one, const void *two)
 265 {
 266         int rcode;
 267         const REQUEST *a = one;
 268         const REQUEST *b = two;
 269
 270         rad_assert(a->magic == REQUEST_MAGIC);
 271         rad_assert(b->magic == REQUEST_MAGIC);
 272
 273         rad_assert(a->proxy != NULL);
 274         rad_assert(b->proxy != NULL);
 275
 276         /*
 277          *      The following code looks unreasonable, but it's
 278          *      the only way to make the comparisons work.
 279          */
 280         if (a->proxy->sockfd < b->proxy->sockfd) return -1;
 281         if (a->proxy->sockfd > b->proxy->sockfd) return +1;
 282
 283         if (a->proxy->id < b->proxy->id) return -1;
 284         if (a->proxy->id > b->proxy->id) return +1;
 285
 286         /*
 287          *      We've got to check packet codes, too.  But
 288          *      this should be done later, by someone else...
 289          */
 290         if (a->proxy->dst_ipaddr.af < b->proxy->dst_ipaddr.af) return -1;
 291         if (a->proxy->dst_ipaddr.af > b->proxy->dst_ipaddr.af) return +1;
 292
 293         if (a->proxy->dst_port < b->proxy->dst_port) return -1;
 294         if (a->proxy->dst_port > b->proxy->dst_port) return +1;
 295
 296         switch (a->proxy->dst_ipaddr.af) {
 297         case AF_INET:
 298                 rcode = memcmp(&a->proxy->dst_ipaddr.ipaddr.ip4addr,
 299                                &b->proxy->dst_ipaddr.ipaddr.ip4addr,
 300                                sizeof(a->proxy->dst_ipaddr.ipaddr.ip4addr));
 301                 break;
 302         case AF_INET6:
 303                 rcode = memcmp(&a->proxy->dst_ipaddr.ipaddr.ip6addr,
 304                                &b->proxy->dst_ipaddr.ipaddr.ip6addr,
 305                                sizeof(a->proxy->dst_ipaddr.ipaddr.ip6addr));
 306                 break;
 307         default:
 308                 return -1;      /* FIXME: die! */
 309                 break;
 310         }
 311         if (rcode != 0) return rcode;
 312
 313         /*
 314          *      FIXME: Check the Proxy-State attribute, too.
 315          *      This will help cut down on duplicates.
 316          */
 317
 318         /*
 319          *      Everything's equal.  Say so.
 320          */
 321         return 0;
 322 }
 323
 324
 325 /*
 326  *      Initialize the request list.
 327  */
 328 request_list_t *rl_init(void)
 329 {
 330         request_list_t *rl = rad_malloc(sizeof(*rl));
 331
 332         /*
 333          *      Initialize the request_list[] array.
 334          */
 335         memset(rl, 0, sizeof(*rl));
 336
 337         rl->ht = lrad_hash_table_create(10, NULL, 0);
 338         if (!rl->ht) {
 339                 rad_assert("FAIL" == NULL);
 340         }
 341         lrad_hash_table_set_data_size(rl->ht, sizeof(request_entry_t));
 342
 343         return rl;
 344 }
 345
 346 int rl_init_proxy(void)
 347 {
 348         /*
 349          *      Hacks, so that multiple users can call rl_init,
 350          *      and it won't get excited.
 351          *
 352          *      FIXME: Move proxy stuff to another struct entirely.
 353          */
 354         if (proxy_tree) return 0;
 355
 356         /*
 357          *      Create the tree for managing proxied requests and
 358          *      responses.
 359          */
 360         proxy_tree = rbtree_create(proxy_cmp, NULL, 1);
 361         if (!proxy_tree) {
 362                 rad_assert("FAIL" == NULL);
 363         }
 364
 365         /*
 366          *      Create the tree for allocating proxy ID's.
 367          */
 368         proxy_id_tree = rbtree_create(proxy_id_cmp, NULL, 0);
 369         if (!proxy_id_tree) {
 370                 rad_assert("FAIL" == NULL);
 371         }
 372
 373 #ifdef HAVE_PTHREAD_H
 374         /*
 375          *      For now, always create the mutex.
 376          *
 377          *      Later, we can only create it if there are multiple threads.
 378          */
 379         if (pthread_mutex_init(&proxy_mutex, NULL) != 0) {
 380                 radlog(L_ERR, "FATAL: Failed to initialize proxy mutex: %s",
 381                        strerror(errno));
 382                 exit(1);
 383         }
 384 #endif
 385
 386         /*
 387          *      The Id allocation table is done by bits, so we have
 388          *      32 bits per Id.  These bits indicate which entry
 389          *      in the proxy_fds array is used for that Id.
 390          *
 391          *      This design allows 256*32 = 8k requests to be
 392          *      outstanding to a home server, before something goes
 393          *      wrong.
 394          */
 395         {
 396                 int i;
 397                 rad_listen_t *listener;
 398
 399                 /*
 400                  *      Mark the Fd's as unused.
 401                  */
 402                 for (i = 0; i < 32; i++) proxy_fds[i] = -1;
 403
 404                 for (listener = mainconfig.listen;
 405                      listener != NULL;
 406                      listener = listener->next) {
 407                         if (listener->type == RAD_LISTEN_PROXY) {
 408                                 proxy_fds[listener->fd & 0x1f] = listener->fd;
 409                                 proxy_listeners[listener->fd & 0x1f] = listener;
 410                                 break;
 411                         }
 412                 }
 413         }
 414
 415         return 1;
 416 }
 417
 418 static int rl_free_entry(void *ctx, void *data)
 419 {
 420         request_entry_t *next, *entry = data;
 421         REQUEST *request;
 422
 423         ctx = ctx;              /* -Wunused */
 424
 425         for (entry = data; entry != NULL; entry = next) {
 426                 next = entry->next;
 427
 428 #ifdef HAVE_PTHREAD_H
 429                 /*
 430                  *      If someone is processing this request, kill
 431                  *      them, and mark the request as not being used.
 432                  */
 433                 if (request->child_pid != NO_SUCH_CHILD_PID) {
 434                         pthread_kill(request->child_pid, SIGKILL);
 435                         request->child_pid = NO_SUCH_CHILD_PID;
 436                 }
 437 #endif
 438                 request_free(&request);
 439                 if (entry != data) free(entry);
 440         }
 441
 442         return 0;
 443 }
 444
 445
 446 /*
 447  *      Delete everything in the request list.
 448  *
 449  *      This should be called only when debugging the server...
 450  */
 451 void rl_deinit(request_list_t *rl)
 452 {
 453         if (!rl) return;
 454
 455         if (proxy_tree) {
 456                 rbtree_free(proxy_tree);
 457                 proxy_tree = NULL;
 458
 459                 rbtree_free(proxy_id_tree);
 460                 proxy_id_tree = NULL;
 461         }
 462
 463         /*
 464          *      Delete everything in the table, too.
 465          */
 466         lrad_hash_table_walk(rl->ht, rl_free_entry, NULL);
 467
 468         lrad_hash_table_free(rl->ht);
 469
 470
 471         /*
 472          *      Just to ensure no one is using the memory.
 473          */
 474         memset(rl, 0, sizeof(*rl));
 475 }
 476
 477
 478 /*
 479  *      Delete a request from the proxy trees.
 480  */
 481 static void rl_delete_proxy(REQUEST *request, rbnode_t *node)
 482 {
 483         proxy_id_t      myid, *entry;
 484
 485         rad_assert(node != NULL);
 486
 487         rbtree_delete(proxy_tree, node);
 488
 489         myid.dst_ipaddr = request->proxy->dst_ipaddr;
 490         myid.dst_port = request->proxy->dst_port;
 491
 492         /*
 493          *      Find the Id in the array of allocated Id's,
 494          *      and delete it.
 495          */
 496         entry = rbtree_finddata(proxy_id_tree, &myid);
 497         if (entry) {
 498                 int i;
 499                 char buf[128];
 500
 501                 DEBUG3(" proxy: de-allocating destination %s port %d - Id %d",
 502                        inet_ntop(entry->dst_ipaddr.af,
 503                                  &entry->dst_ipaddr.ipaddr, buf, sizeof(buf)),
 504                        entry->dst_port,
 505                        request->proxy->id);
 506
 507                 /*
 508                  *      Find the proxy socket associated with this
 509                  *      Id.  We loop over all 32 proxy fd's, but we
 510                  *      partially index by proxy fd's, which means
 511                  *      that we almost always break out of the loop
 512                  *      quickly.
 513                  */
 514                 for (i = 0; i < 32; i++) {
 515                         int offset;
 516
 517                         offset = (request->proxy->sockfd + i) & 0x1f;
 518
 519                         if (proxy_fds[offset] == request->proxy->sockfd) {
 520
 521                                 entry->id[request->proxy->id] &= ~(1 << offset);
 522                                 break;
 523                         }
 524                 } /* else die horribly? */
 525         } else {
 526                 char buf[128];
 527
 528                 /*
 529                  *      Hmm... not sure what to do here.
 530                  */
 531                 DEBUG3(" proxy: FAILED TO FIND destination %s port %d - Id %d",
 532                        inet_ntop(myid.dst_ipaddr.af,
 533                                  &myid.dst_ipaddr.ipaddr, buf, sizeof(buf)),
 534                        myid.dst_port,
 535                        request->proxy->id);
 536         }
 537 }
 538
 539
 540 /*
 541  *      Yank a request from the tree, without free'ing it.
 542  */
 543 void rl_yank(request_list_t *rl, REQUEST *request)
 544 {
 545         request_entry_t *entry;
 546
 547 #ifdef WITH_SNMP
 548         /*
 549          *      Update the SNMP statistics.
 550          *
 551          *      Note that we do NOT do this in rad_respond(),
 552          *      as that function is called from child threads.
 553          *      Instead, we update the stats when a request is
 554          *      deleted, because only the main server thread calls
 555          *      this function...
 556          */
 557         if (mainconfig.do_snmp) {
 558                 switch (request->reply->code) {
 559                 case PW_AUTHENTICATION_ACK:
 560                   rad_snmp.auth.total_responses++;
 561                   rad_snmp.auth.total_access_accepts++;
 562                   break;
 563
 564                 case PW_AUTHENTICATION_REJECT:
 565                   rad_snmp.auth.total_responses++;
 566                   rad_snmp.auth.total_access_rejects++;
 567                   break;
 568
 569                 case PW_ACCESS_CHALLENGE:
 570                   rad_snmp.auth.total_responses++;
 571                   rad_snmp.auth.total_access_challenges++;
 572                   break;
 573
 574                 case PW_ACCOUNTING_RESPONSE:
 575                   rad_snmp.acct.total_responses++;
 576                   break;
 577
 578                 default:
 579                         break;
 580                 }
 581         }
 582 #endif
 583
 584         /*
 585          *      Delete the request from the list.
 586          */
 587         entry = lrad_hash_table_finddata(rl->ht, request->packet->hash);
 588
 589         /*
 590          *      The entry managed by the hash table is being deleted.
 591          */
 592         if (entry->request == request) {
 593                 if (entry->next) {
 594                         request_entry_t *next = entry->next;
 595                         entry->next = next->next;
 596                         entry->request = next->request;
 597                         free(next);
 598
 599                         rad_assert(rl->collisions > 0);
 600                         rl->collisions--;
 601                 } else {
 602                         lrad_hash_table_delete(rl->ht, request->packet->hash);
 603                 }
 604
 605         } else {                /* a secondary entry is being deleted */
 606                 request_entry_t *this, *next, **last;
 607
 608                 last = &entry->next;
 609                 for (this = entry->next; this != NULL; this = next) {
 610                         next = this->next;
 611
 612                         if (this->request != request) {
 613                                 last = &this->next;
 614                                 continue;
 615                         }
 616
 617                         *last = this->next;
 618                         free(this);
 619
 620                         rad_assert(rl->collisions > 0);
 621                         rl->collisions--;
 622                         break;
 623                 }
 624         }
 625
 626
 627         /*
 628          *      If there's a proxied packet, and we're still
 629          *      waiting for a reply, then delete the packet
 630          *      from the list of outstanding proxied requests.
 631          */
 632         if (request->proxy &&
 633             (request->proxy_outstanding > 0)) {
 634                 rbnode_t *node;
 635                 pthread_mutex_lock(&proxy_mutex);
 636                 node = rbtree_find(proxy_tree, request);
 637                 rl_delete_proxy(request, node);
 638                 pthread_mutex_unlock(&proxy_mutex);
 639         }
 640 }
 641
 642
 643 /*
 644  *      Delete a request from the tree.
 645  */
 646 void rl_delete(request_list_t *rl, REQUEST *request)
 647 {
 648         rl_yank(rl, request);
 649         request_free(&request);
 650 }
 651
 652
 653 /*
 654  *      Add a request to the request list.
 655  */
 656 int rl_add(request_list_t *rl, REQUEST *request)
 657 {
 658         request_entry_t *entry, myentry;
 659
 660         entry = lrad_hash_table_finddata(rl->ht, request->packet->hash);
 661         if (!entry) {
 662                 myentry.next = NULL;
 663                 myentry.request = request;
 664                 return lrad_hash_table_insert(rl->ht, request->packet->hash,
 665                                               &myentry);
 666         }
 667
 668         /*
 669          *      Collision: insert it into a linked list (yuck)
 670          */
 671         entry->next = rad_malloc(sizeof(*entry));
 672         entry->next->next = NULL;
 673         entry->next->request = request;
 674
 675         DEBUG3(" FYI: hash collision...");
 676
 677         rl->collisions++;
 678
 679         return 1;
 680 }
 681
 682 /*
 683  *      Look up a particular request, using:
 684  *
 685  *      Request ID, request code, source IP, source port,
 686  *
 687  *      Note that we do NOT use the request vector to look up requests.
 688  *
 689  *      We MUST NOT have two requests with identical (id/code/IP/port), and
 690  *      different vectors.  This is a serious error!
 691  */
 692 REQUEST *rl_find(request_list_t *rl, RADIUS_PACKET *packet)
 693 {
 694         request_entry_t *entry;
 695
 696         packet_hash(packet);
 697
 698         entry = lrad_hash_table_finddata(rl->ht, packet->hash);
 699         if (!entry) return NULL;
 700
 701         /*
 702          *      Call a packet comparison function?
 703          */
 704         while (entry && !packet_cmp(packet, entry->request->packet)) {
 705                 entry = entry->next;
 706         }
 707
 708         if (!entry) return NULL;
 709
 710         return entry->request;
 711 }
 712
 713 /*
 714  *      Add an entry to the proxy tree.
 715  *
 716  *      This is the ONLY function in this source file which may be called
 717  *      from a child thread.  It therefore needs mutexes...
 718  */
 719 int rl_add_proxy(REQUEST *request)
 720 {
 721         int             i, found, proxy;
 722         uint32_t        mask;
 723         proxy_id_t      myid, *entry;
 724         char            buf[128];
 725
 726         myid.dst_ipaddr = request->proxy->dst_ipaddr;
 727         myid.dst_port = request->proxy->dst_port;
 728
 729         /*
 730          *      Proxied requests get sent out the proxy FD ONLY.
 731          *
 732          *      FIXME: Once we allocate multiple proxy FD's, move this
 733          *      code to below, so we can have more than 256 requests
 734          *      outstanding.
 735          */
 736         request->proxy_outstanding = 1;
 737
 738         pthread_mutex_lock(&proxy_mutex);
 739
 740         /*
 741          *      Assign a proxy ID.
 742          */
 743         entry = rbtree_finddata(proxy_id_tree, &myid);
 744         if (!entry) {   /* allocate it */
 745                 entry = rad_malloc(sizeof(*entry) + sizeof(entry->id) * 255);
 746
 747                 entry->dst_ipaddr = request->proxy->dst_ipaddr;
 748                 entry->dst_port = request->proxy->dst_port;
 749                 entry->index = 0;
 750
 751                 DEBUG3(" proxy: creating destination %s port %d",
 752                        inet_ntop(entry->dst_ipaddr.af,
 753                                  &entry->dst_ipaddr.ipaddr, buf, sizeof(buf)),
 754                        entry->dst_port);
 755
 756                 /*
 757                  *      Insert the new home server entry into
 758                  *      the tree.
 759                  *
 760                  *      FIXME: We don't (currently) delete the
 761                  *      entries, so this is technically a
 762                  *      memory leak.
 763                  */
 764                 if (rbtree_insert(proxy_id_tree, entry) == 0) {
 765                         pthread_mutex_unlock(&proxy_mutex);
 766                         DEBUG2("ERROR: Failed to insert entry into proxy Id tree");
 767                         free(entry);
 768                         return 0;
 769                 }
 770
 771                 /*
 772                  *      Clear out bits in the array which DO have
 773                  *      proxy Fd's associated with them.  We do this
 774                  *      by getting the mask of bits which have proxy
 775                  *      fd's...  */
 776                 mask = 0;
 777                 for (i = 0; i < 32; i++) {
 778                         if (proxy_fds[i] != -1) {
 779                                 mask |= (1 << i);
 780                         }
 781                 }
 782                 rad_assert(mask != 0);
 783
 784                 /*
 785                  *      Set bits here indicate that the Fd is in use.
 786                  */
 787                 entry->mask = mask;
 788
 789                 mask = ~mask;
 790
 791                 /*
 792                  *      Set the bits which are unused (and therefore
 793                  *      allocated).  The clear bits indicate that the Id
 794                  *      for that FD is unused.
 795                  */
 796                 for (i = 0; i < 256; i++) {
 797                         entry->id[i] = mask;
 798                 }
 799         } /* else the entry already existed in the proxy Id tree */
 800
 801  retry:
 802         /*
 803          *      Try to find a free Id.
 804          */
 805         found = -1;
 806         for (i = 0; i < 256; i++) {
 807                 /*
 808                  *      Some bits are still zero..
 809                  */
 810                 if (entry->id[(i + entry->index) & 0xff] != (uint32_t) ~0) {
 811                         found = (i + entry->index) & 0xff;
 812                         break;
 813                 }
 814
 815                 /*
 816                  *      Hmm... do we want to re-use Id's, when we
 817                  *      haven't seen all of the responses?
 818                  */
 819         }
 820
 821         /*
 822          *      No free Id, try to get a new FD.
 823          */
 824         if (found < 0) {
 825                 rad_listen_t *proxy_listener;
 826
 827                 /*
 828                  *      First, see if there were FD's recently allocated,
 829                  *      which we don't know about.
 830                  */
 831                 mask = 0;
 832                 for (i = 0; i < 32; i++) {
 833                         if (proxy_fds[i] < 0) continue;
 834
 835                         mask |= (1 << i);
 836                 }
 837
 838                 /*
 839                  *      There ARE more FD's than we know about.
 840                  *      Update the masks for Id's, and re-try.
 841                  */
 842                 if (entry->mask != mask) {
 843                         /*
 844                          *      New mask always has more bits than
 845                          *      the old one, but never fewer bits.
 846                          */
 847                         rad_assert((entry->mask & mask) == entry->mask);
 848
 849                         /*
 850                          *      Clear the bits we already know about,
 851                          *      and then or in those bits into the
 852                          *      global mask.
 853                          */
 854                         mask ^= entry->mask;
 855                         entry->mask |= mask;
 856                         mask = ~mask;
 857
 858                         /*
 859                          *      Clear the bits in the Id's for the new
 860                          *      FD's.
 861                          */
 862                         for (i = 0; i < 256; i++) {
 863                                 entry->id[i] &= mask;
 864                         }
 865
 866                         /*
 867                          *      And try again to allocate an Id.
 868                          */
 869                         goto retry;
 870                 } /* else no new Fd's were allocated. */
 871
 872                 /*
 873                  *      If all Fd's are allocated, die.
 874                  */
 875                 if (~mask == 0) {
 876                         pthread_mutex_unlock(&proxy_mutex);
 877                         radlog(L_ERR|L_CONS, "ERROR: More than 8000 proxied requests outstanding for destination %s port %d",
 878                                inet_ntop(entry->dst_ipaddr.af,
 879                                          &entry->dst_ipaddr.ipaddr,
 880                                          buf, sizeof(buf)),
 881                                entry->dst_port);
 882                         return 0;
 883                 }
 884
 885                 /*
 886                  *      Allocate a new proxy Fd.  This function adds it
 887                  *      into the list of listeners.
 888                  */
 889                 proxy_listener = proxy_new_listener();
 890                 if (!proxy_listener) {
 891                         pthread_mutex_unlock(&proxy_mutex);
 892                         DEBUG2("ERROR: Failed to create a new socket for proxying requests.");
 893                         return 0;
 894                 }
 895
 896                 /*
 897                  *
 898                  */
 899                 found = -1;
 900                 proxy = proxy_listener->fd;
 901                 for (i = 0; i < 32; i++) {
 902                         /*
 903                          *      Found a free entry.  Save the socket,
 904                          *      and remember where we saved it.
 905                          */
 906                         if (proxy_fds[(proxy + i) & 0x1f] == -1) {
 907                                 proxy_fds[(proxy + i) & 0x1f] = proxy;
 908                                 found = (proxy + i) & 0x1f;
 909                                 break;
 910                         }
 911                 }
 912                 rad_assert(found >= 0); /* i.e. the mask had free bits. */
 913
 914                 mask = 1 << found;
 915                 entry->mask |= mask;
 916                 mask = ~mask;
 917
 918                 /*
 919                  *      Clear the relevant bits in the mask.
 920                  */
 921                 for (i = 0; i < 256; i++) {
 922                         entry->id[i] &= mask;
 923                 }
 924
 925                 /*
 926                  *      Pick a random Id to start from, as we've
 927                  *      just guaranteed that it's free.
 928                  */
 929                 found = lrad_rand() & 0xff;
 930         }
 931
 932         /*
 933          *      Mark next (hopefully unused) entry.
 934          */
 935         entry->index = (found + 1) & 0xff;
 936
 937         /*
 938          *      We now have to find WHICH proxy fd to use.
 939          */
 940         proxy = -1;
 941         for (i = 0; i < 32; i++) {
 942                 /*
 943                  *      FIXME: pick a random socket to use?
 944                  */
 945                 if ((entry->id[found] & (1 << i)) == 0) {
 946                         proxy = i;
 947                         break;
 948                 }
 949         }
 950
 951         /*
 952          *      There was no bit clear, which we had just checked above...
 953          */
 954         rad_assert(proxy != -1);
 955
 956         /*
 957          *      Mark the Id as allocated, for thei Fd.
 958          */
 959         entry->id[found] |= (1 << proxy);
 960         request->proxy->id = found;
 961
 962         rad_assert(proxy_fds[proxy] != -1);
 963         request->proxy->sockfd = proxy_fds[proxy];
 964         request->proxy_listener = proxy_listeners[proxy];
 965
 966         DEBUG3(" proxy: allocating destination %s port %d - Id %d",
 967                inet_ntop(entry->dst_ipaddr.af,
 968                          &entry->dst_ipaddr.ipaddr, buf, sizeof(buf)),
 969                entry->dst_port,
 970                request->proxy->id);
 971
 972         if (!rbtree_insert(proxy_tree, request)) {
 973                 pthread_mutex_unlock(&proxy_mutex);
 974                 DEBUG2("ERROR: Failed to insert entry into proxy tree");
 975                 return 0;
 976         }
 977
 978         pthread_mutex_unlock(&proxy_mutex);
 979
 980         return 1;
 981 }
 982
 983
 984 /*
 985  *      Look up a particular request, using:
 986  *
 987  *      Request Id, request code, source IP, source port,
 988  *
 989  *      Note that we do NOT use the request vector to look up requests.
 990  *
 991  *      We MUST NOT have two requests with identical (id/code/IP/port), and
 992  *      different vectors.  This is a serious error!
 993  */
 994 REQUEST *rl_find_proxy(RADIUS_PACKET *packet)
 995 {
 996         rbnode_t        *node;
 997         REQUEST         myrequest, *maybe = NULL;
 998         RADIUS_PACKET   myproxy;
 999
1000         /*
1001          *      If we use the socket FD as an indicator,
1002          *      then that implicitely contains information
1003          *      as to our src ipaddr/port, so we don't need
1004          *      to use that in the comparisons.
1005          */
1006         myproxy.sockfd = packet->sockfd;
1007         myproxy.id = packet->id;
1008         myproxy.dst_ipaddr = packet->src_ipaddr;
1009         myproxy.dst_port = packet->src_port;
1010
1011 #ifndef NDEBUG
1012         myrequest.magic = REQUEST_MAGIC;
1013 #endif
1014         myrequest.proxy = &myproxy;
1015
1016         pthread_mutex_lock(&proxy_mutex);
1017         node = rbtree_find(proxy_tree, &myrequest);
1018
1019         if (node) {
1020                 maybe = rbtree_node2data(proxy_tree, node);
1021                 rad_assert(maybe->proxy_outstanding > 0);
1022                 maybe->proxy_outstanding--;
1023
1024                 /*
1025                  *      Received all of the replies we expect.
1026                  *      delete it from both trees.
1027                  */
1028                 if (maybe->proxy_outstanding == 0) {
1029                         rl_delete_proxy(&myrequest, node);
1030                 }
1031         }
1032         pthread_mutex_unlock(&proxy_mutex);
1033
1034         return maybe;
1035 }
1036
1037
1038 /*
1039  *      Return the number of requests in the request list.
1040  */
1041 int rl_num_requests(request_list_t *rl)
1042 {
1043         return lrad_hash_table_num_elements(rl->ht) + rl->collisions;
1044 }
1045
1046
1047 /*
1048  *      See also radiusd.c
1049  */
1050 #define SLEEP_FOREVER (65536)
1051 typedef struct rl_walk_t {
1052         time_t  now;
1053         int     sleep_time;
1054         request_list_t *rl;
1055 } rl_walk_t;
1056
1057
1058 /*
1059  *  Refresh a request, by using cleanup_delay, max_request_time, etc.
1060  *
1061  *  When walking over the request list, all of the per-request
1062  *  magic is done here.
1063  */
1064 static int refresh_request(void *ctx, void *data)
1065 {
1066         int time_passed;
1067         rl_walk_t *info = (rl_walk_t *) ctx;
1068         child_pid_t child_pid;
1069         request_list_t *rl = info->rl;
1070         request_entry_t *entry = data;
1071         request_entry_t *next = entry->next;
1072         REQUEST *request = entry->request;
1073
1074         if (next) refresh_request(ctx, next);
1075
1076         rad_assert(request->magic == REQUEST_MAGIC);
1077
1078         time_passed = (int) (info->now - request->timestamp);
1079
1080         /*
1081          *      If the request is marked as a delayed reject, AND it's
1082          *      time to send the reject, then do so now.
1083          */
1084         if (request->finished &&
1085             ((request->options & RAD_REQUEST_OPTION_DELAYED_REJECT) != 0)) {
1086                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1087                 if (time_passed < mainconfig.reject_delay) {
1088                         goto reject_delay;
1089                 }
1090
1091         reject_packet:
1092                 /*
1093                  *      Clear the 'delayed reject' bit, so that we
1094                  *      don't do this again, and fall through to
1095                  *      setting cleanup delay.
1096                  */
1097                 request->listener->send(request->listener, request);
1098                 request->options &= ~RAD_REQUEST_OPTION_DELAYED_REJECT;
1099
1100                 /*
1101                  *      FIXME: Beware interaction with cleanup_delay,
1102                  *      where we might send a reject, and immediately
1103                  *      there-after clean it up!
1104                  */
1105         }
1106
1107         /*
1108          *      If the request is finished, AND more than cleanup_delay
1109          *      seconds have passed since it was received, clean it up.
1110          *
1111          *      OR, if this is a request which had the "don't cache"
1112          *      option set, then delete it immediately, as it CANNOT
1113          *      have a duplicate.
1114          */
1115         if ((request->finished &&
1116              (time_passed >= mainconfig.cleanup_delay)) ||
1117             ((request->options & RAD_REQUEST_OPTION_DONT_CACHE) != 0)) {
1118                 rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1119
1120                 /*
1121                  *  Request completed, delete it, and unlink it
1122                  *  from the currently 'alive' list of requests.
1123                  */
1124         cleanup:
1125                 DEBUG2("Cleaning up request %d ID %d with timestamp %08lx",
1126                                 request->number, request->packet->id,
1127                                 (unsigned long) request->timestamp);
1128
1129                 /*
1130                  *  Delete the request.
1131                  */
1132                 rl_delete(rl, request);
1133                 return 0;
1134         }
1135
1136         /*
1137          *      If more than max_request_time has passed since
1138          *      we received the request, kill it.
1139          */
1140         if (time_passed >= mainconfig.max_request_time) {
1141                 int number;
1142
1143                 child_pid = request->child_pid;
1144                 number = request->number;
1145
1146                 /*
1147                  *      There MUST be a RAD_PACKET reply.
1148                  */
1149                 rad_assert(request->reply != NULL);
1150
1151                 /*
1152                  *      If we've tried to proxy the request, and
1153                  *      the proxy server hasn't responded, then
1154                  *      we send a REJECT back to the caller.
1155                  *
1156                  *      For safety, we assert that there is no child
1157                  *      handling the request.  If the assertion fails,
1158                  *      it means that we've sent a proxied request to
1159                  *      the home server, and the child thread is still
1160                  *      sitting on the request!
1161                  */
1162                 if (request->proxy && !request->proxy_reply) {
1163                         rad_assert(request->child_pid == NO_SUCH_CHILD_PID);
1164
1165                         radlog(L_ERR, "Rejecting request %d due to lack of any response from home server %s port %d",
1166                                request->number,
1167                                client_name_old(&request->packet->src_ipaddr),
1168                                request->packet->src_port);
1169                         request_reject(request, REQUEST_FAIL_HOME_SERVER);
1170                         request->finished = TRUE;
1171                         return 0;
1172                 }
1173
1174                 if (mainconfig.kill_unresponsive_children) {
1175                         if (child_pid != NO_SUCH_CHILD_PID) {
1176                                 /*
1177                                  *  This request seems to have hung
1178                                  *   - kill it
1179                                  */
1180 #ifdef HAVE_PTHREAD_H
1181                                 radlog(L_ERR, "Killing unresponsive thread for request %d",
1182                                        request->number);
1183                                 pthread_cancel(child_pid);
1184 #endif
1185                         } /* else no proxy reply, quietly fail */
1186
1187                         /*
1188                          *      Maybe we haven't killed it.  In that
1189                          *      case, print a warning.
1190                          */
1191                 } else if ((child_pid != NO_SUCH_CHILD_PID) &&
1192                            ((request->options & RAD_REQUEST_OPTION_LOGGED_CHILD) == 0)) {
1193                         radlog(L_ERR, "WARNING: Unresponsive child (id %lu) for request %d",
1194                                (unsigned long)child_pid, number);
1195
1196                         /*
1197                          *  Set the option that we've sent a log message,
1198                          *  so that we don't send more than one message
1199                          *  per request.
1200                          */
1201                         request->options |= RAD_REQUEST_OPTION_LOGGED_CHILD;
1202                 }
1203
1204                 /*
1205                  *      Send a reject message for the request, mark it
1206                  *      finished, and forget about the child.
1207                  */
1208                 request_reject(request, REQUEST_FAIL_SERVER_TIMEOUT);
1209
1210                 request->child_pid = NO_SUCH_CHILD_PID;
1211
1212                 if (mainconfig.kill_unresponsive_children)
1213                         request->finished = TRUE;
1214                 return 0;
1215         } /* else the request is still allowed to be in the queue */
1216
1217         /*
1218          *      If the request is finished, set the cleanup delay.
1219          */
1220         if (request->finished) {
1221                 time_passed = mainconfig.cleanup_delay - time_passed;
1222                 goto setup_timeout;
1223         }
1224
1225         /*
1226          *      Set reject delay, if appropriate.
1227          */
1228         if ((request->packet->code == PW_AUTHENTICATION_REQUEST) &&
1229             (mainconfig.reject_delay > 0)) {
1230         reject_delay:
1231                 time_passed = mainconfig.reject_delay - time_passed;
1232
1233                 /*
1234                  *      This catches a corner case, apparently.
1235                  */
1236                 if ((request->reply->code == PW_AUTHENTICATION_REJECT) &&
1237                     (time_passed == 0)) goto reject_packet;
1238                 if (time_passed == 0) time_passed = 1;
1239                 goto setup_timeout;
1240         }
1241
1242         /*
1243          *      Accounting requests are always proxied
1244          *      asynchronously, authentication requests are
1245          *      always proxied synchronously.
1246          */
1247         if ((request->packet->code == PW_ACCOUNTING_REQUEST) &&
1248             (request->proxy && !request->proxy_reply) &&
1249             (info->now != request->proxy_start_time)) {
1250                 /*
1251                  *      We've tried to send it, but the home server
1252                  *      hasn't responded.
1253                  */
1254                 if (request->proxy_try_count == 0) {
1255                         request_reject(request, REQUEST_FAIL_HOME_SERVER2);
1256                         rad_assert(request->proxy->dst_ipaddr.af == AF_INET);
1257                         request->finished = TRUE;
1258                         goto cleanup; /* delete the request & continue */
1259                 }
1260
1261                 /*
1262                  *      Figure out how long we have to wait before
1263                  *      sending a re-transmit.
1264                  */
1265                 time_passed = (info->now - request->proxy_start_time) % mainconfig.proxy_retry_delay;
1266                 if (time_passed == 0) {
1267                         VALUE_PAIR *vp;
1268                         vp = pairfind(request->proxy->vps, PW_ACCT_DELAY_TIME);
1269                         if (!vp) {
1270                                 vp = paircreate(PW_ACCT_DELAY_TIME,
1271                                                 PW_TYPE_INTEGER);
1272                                 if (!vp) {
1273                                         radlog(L_ERR|L_CONS, "no memory");
1274                                         exit(1);
1275                                 }
1276                                 pairadd(&request->proxy->vps, vp);
1277                                 vp->lvalue = info->now - request->proxy_start_time;
1278                         } else {
1279                                 vp->lvalue += mainconfig.proxy_retry_delay;
1280                         }
1281
1282                         /*
1283                          *      This function takes care of re-transmits.
1284                          */
1285                         request->proxy_listener->send(request->proxy_listener, request);
1286                         request->proxy_try_count--;
1287                 }
1288                 time_passed = mainconfig.proxy_retry_delay - time_passed;
1289                 goto setup_timeout;
1290         }
1291
1292         /*
1293          *      The request is still alive, wake up when it's
1294          *      taken too long.
1295          */
1296         time_passed = mainconfig.max_request_time - time_passed;
1297
1298 setup_timeout:
1299         if (time_passed < info->sleep_time) {
1300                 info->sleep_time = time_passed;
1301         }
1302
1303         return 0;
1304 }
1305
1306
1307 /*
1308  *  Clean up the request list, every so often.
1309  *
1310  *  This is done by walking through ALL of the list, and
1311  *  - marking any requests which are finished, and expired
1312  *  - killing any processes which are NOT finished after a delay
1313  *  - deleting any marked requests.
1314  *
1315  *      Returns the number of millisends to sleep, before processing
1316  *      something.
1317  */
1318 int rl_clean_list(request_list_t *rl, time_t now)
1319 {
1320         rl_walk_t info;
1321
1322         info.now = now;
1323         info.sleep_time = SLEEP_FOREVER;
1324         info.rl = rl;
1325
1326         lrad_hash_table_walk(rl->ht, refresh_request, &info);
1327
1328         if (info.sleep_time < 0) info.sleep_time = 0;
1329
1330         return info.sleep_time;
1331 }