src/peer_select.cc

   1 /*
   2  * Copyright (C) 1996-2018 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /* DEBUG: section 44    Peer Selection Algorithm */
  10
  11 #include "squid.h"
  12 #include "acl/FilledChecklist.h"
  13 #include "base/InstanceId.h"
  14 #include "CachePeer.h"
  15 #include "carp.h"
  16 #include "client_side.h"
  17 #include "dns/LookupDetails.h"
  18 #include "errorpage.h"
  19 #include "event.h"
  20 #include "FwdState.h"
  21 #include "globals.h"
  22 #include "hier_code.h"
  23 #include "htcp.h"
  24 #include "http/Stream.h"
  25 #include "HttpRequest.h"
  26 #include "icmp/net_db.h"
  27 #include "ICP.h"
  28 #include "ip/tools.h"
  29 #include "ipcache.h"
  30 #include "neighbors.h"
  31 #include "peer_sourcehash.h"
  32 #include "peer_userhash.h"
  33 #include "PeerSelectState.h"
  34 #include "SquidConfig.h"
  35 #include "SquidTime.h"
  36 #include "Store.h"
  37
  38 /**
  39  * A CachePeer which has been selected as a possible destination.
  40  * Listed as pointers here so as to prevent duplicates being added but will
  41  * be converted to a set of IP address path options before handing back out
  42  * to the caller.
  43  *
  44  * Certain connection flags and outgoing settings will also be looked up and
  45  * set based on the received request and CachePeer settings before handing back.
  46  */
  47 class FwdServer
  48 {
  49     MEMPROXY_CLASS(FwdServer);
  50
  51 public:
  52     FwdServer(CachePeer *p, hier_code c) :
  53         _peer(p),
  54         code(c),
  55         next(nullptr)
  56     {}
  57
  58     CbcPointer<CachePeer> _peer;                /* NULL --> origin server */
  59     hier_code code;
  60     FwdServer *next;
  61 };
  62
  63 static struct {
  64     int timeouts;
  65 } PeerStats;
  66
  67 static const char *DirectStr[] = {
  68     "DIRECT_UNKNOWN",
  69     "DIRECT_NO",
  70     "DIRECT_MAYBE",
  71     "DIRECT_YES"
  72 };
  73
  74 /// a helper class to report a selected destination (for debugging)
  75 class PeerSelectionDumper
  76 {
  77 public:
  78     PeerSelectionDumper(const PeerSelector * const aSelector, const CachePeer * const aPeer, const hier_code aCode):
  79         selector(aSelector), peer(aPeer), code(aCode) {}
  80
  81     const PeerSelector * const selector; ///< selection parameters
  82     const CachePeer * const peer; ///< successful selection info
  83     const hier_code code; ///< selection algorithm
  84 };
  85
  86 CBDATA_CLASS_INIT(PeerSelector);
  87
  88 /// prints PeerSelectionDumper (for debugging)
  89 static std::ostream &
  90 operator <<(std::ostream &os, const PeerSelectionDumper &fsd)
  91 {
  92     os << hier_code_str[fsd.code];
  93
  94     if (fsd.peer)
  95         os << '/' << fsd.peer->host;
  96     else if (fsd.selector) // useful for DIRECT and gone PINNED destinations
  97         os << '#' << fsd.selector->request->url.host();
  98
  99     return os;
 100 }
 101
 102 PeerSelector::~PeerSelector()
 103 {
 104     while (servers) {
 105         FwdServer *next = servers->next;
 106         delete servers;
 107         servers = next;
 108     }
 109
 110     if (entry) {
 111         debugs(44, 3, entry->url());
 112
 113         if (entry->ping_status == PING_WAITING)
 114             eventDelete(HandlePingTimeout, this);
 115
 116         entry->ping_status = PING_DONE;
 117     }
 118
 119     if (acl_checklist) {
 120         debugs(44, DBG_IMPORTANT, "BUG: peer selector gone while waiting for a slow ACL");
 121         delete acl_checklist;
 122     }
 123
 124     HTTPMSGUNLOCK(request);
 125
 126     if (entry) {
 127         assert(entry->ping_status != PING_WAITING);
 128         entry->unlock("peerSelect");
 129         entry = NULL;
 130     }
 131
 132     delete lastError;
 133 }
 134
 135 static int
 136 peerSelectIcpPing(PeerSelector *ps, int direct, StoreEntry * entry)
 137 {
 138     assert(ps);
 139     HttpRequest *request = ps->request;
 140
 141     int n;
 142     assert(entry);
 143     assert(entry->ping_status == PING_NONE);
 144     assert(direct != DIRECT_YES);
 145     debugs(44, 3, entry->url());
 146
 147     if (!request->flags.hierarchical && direct != DIRECT_NO)
 148         return 0;
 149
 150     if (EBIT_TEST(entry->flags, KEY_PRIVATE) && !neighbors_do_private_keys)
 151         if (direct != DIRECT_NO)
 152             return 0;
 153
 154     n = neighborsCount(ps);
 155
 156     debugs(44, 3, "counted " << n << " neighbors");
 157
 158     return n;
 159 }
 160
 161 static void
 162 peerSelect(PeerSelectionInitiator *initiator,
 163            HttpRequest * request,
 164            AccessLogEntry::Pointer const &al,
 165            StoreEntry * entry)
 166 {
 167     if (entry)
 168         debugs(44, 3, *entry << ' ' << entry->url());
 169     else
 170         debugs(44, 3, request->method);
 171
 172     const auto selector = new PeerSelector(initiator);
 173
 174     selector->request = request;
 175     HTTPMSGLOCK(selector->request);
 176     selector->al = al;
 177
 178     selector->entry = entry;
 179
 180 #if USE_CACHE_DIGESTS
 181
 182     request->hier.peer_select_start = current_time;
 183
 184 #endif
 185
 186     if (selector->entry)
 187         selector->entry->lock("peerSelect");
 188
 189     selector->selectMore();
 190 }
 191
 192 void
 193 PeerSelectionInitiator::startSelectingDestinations(HttpRequest *request, const AccessLogEntry::Pointer &ale, StoreEntry *entry)
 194 {
 195     subscribed = true;
 196     peerSelect(this, request, ale, entry);
 197     // and wait for noteDestination() and/or noteDestinationsEnd() calls
 198 }
 199
 200 void
 201 PeerSelector::checkNeverDirectDone(const allow_t answer)
 202 {
 203     acl_checklist = nullptr;
 204     debugs(44, 3, answer);
 205     never_direct = answer;
 206     switch (answer) {
 207     case ACCESS_ALLOWED:
 208         /** if never_direct says YES, do that. */
 209         direct = DIRECT_NO;
 210         debugs(44, 3, "direct = " << DirectStr[direct] << " (never_direct allow)");
 211         break;
 212     case ACCESS_DENIED: // not relevant.
 213     case ACCESS_DUNNO:  // not relevant.
 214         break;
 215     case ACCESS_AUTH_REQUIRED:
 216         debugs(44, DBG_IMPORTANT, "WARNING: never_direct resulted in " << answer << ". Username ACLs are not reliable here.");
 217         break;
 218     }
 219     selectMore();
 220 }
 221
 222 void
 223 PeerSelector::CheckNeverDirectDone(allow_t answer, void *data)
 224 {
 225     static_cast<PeerSelector*>(data)->checkNeverDirectDone(answer);
 226 }
 227
 228 void
 229 PeerSelector::checkAlwaysDirectDone(const allow_t answer)
 230 {
 231     acl_checklist = nullptr;
 232     debugs(44, 3, answer);
 233     always_direct = answer;
 234     switch (answer) {
 235     case ACCESS_ALLOWED:
 236         /** if always_direct says YES, do that. */
 237         direct = DIRECT_YES;
 238         debugs(44, 3, "direct = " << DirectStr[direct] << " (always_direct allow)");
 239         break;
 240     case ACCESS_DENIED: // not relevant.
 241     case ACCESS_DUNNO:  // not relevant.
 242         break;
 243     case ACCESS_AUTH_REQUIRED:
 244         debugs(44, DBG_IMPORTANT, "WARNING: always_direct resulted in " << answer << ". Username ACLs are not reliable here.");
 245         break;
 246     }
 247     selectMore();
 248 }
 249
 250 void
 251 PeerSelector::CheckAlwaysDirectDone(allow_t answer, void *data)
 252 {
 253     static_cast<PeerSelector*>(data)->checkAlwaysDirectDone(answer);
 254 }
 255
 256 /// \returns true (after destroying "this") if the peer initiator is gone
 257 /// \returns false (without side effects) otherwise
 258 bool
 259 PeerSelector::selectionAborted()
 260 {
 261     if (interestedInitiator())
 262         return false;
 263
 264     debugs(44, 3, "Aborting peer selection: Initiator gone or lost interest.");
 265     delete this;
 266     return true;
 267 }
 268
 269 /// A single DNS resolution loop iteration: Converts selected FwdServer to IPs.
 270 void
 271 PeerSelector::resolveSelected()
 272 {
 273     if (selectionAborted())
 274         return;
 275
 276     FwdServer *fs = servers;
 277
 278     // Bug 3243: CVE 2009-0801
 279     // Bypass of browser same-origin access control in intercepted communication
 280     // To resolve this we must use only the original client destination when going DIRECT
 281     // on intercepted traffic which failed Host verification
 282     const HttpRequest *req = request;
 283     const bool isIntercepted = !req->flags.redirected &&
 284                                (req->flags.intercepted || req->flags.interceptTproxy);
 285     const bool useOriginalDst = Config.onoff.client_dst_passthru || !req->flags.hostVerified;
 286     const bool choseDirect = fs && fs->code == HIER_DIRECT;
 287     if (isIntercepted && useOriginalDst && choseDirect) {
 288         // check the client is still around before using any of its details
 289         if (req->clientConnectionManager.valid()) {
 290             // construct a "result" adding the ORIGINAL_DST to the set instead of DIRECT
 291             Comm::ConnectionPointer p = new Comm::Connection();
 292             p->remote = req->clientConnectionManager->clientConnection->local;
 293             fs->code = ORIGINAL_DST; // fs->code is DIRECT. This fixes the display.
 294             handlePath(p, *fs);
 295         }
 296
 297         // clear the used fs and continue
 298         servers = fs->next;
 299         delete fs;
 300         resolveSelected();
 301         return;
 302     }
 303
 304     // convert the list of FwdServer destinations into destinations IP addresses
 305     if (fs && wantsMoreDestinations()) {
 306         // send the next one off for DNS lookup.
 307         const char *host = fs->_peer.valid() ? fs->_peer->host : request->url.host();
 308         debugs(44, 2, "Find IP destination for: " << url() << "' via " << host);
 309         Dns::nbgethostbyname(host, this);
 310         return;
 311     }
 312
 313     // Bug 3605: clear any extra listed FwdServer destinations, when the options exceeds max_foward_tries.
 314     // due to the allocation method of fs, we must deallocate each manually.
 315     // TODO: use a std::list so we can get the size and abort adding whenever the selection loops reach Config.forward_max_tries
 316     if (fs) {
 317         assert(fs == servers);
 318         while (fs) {
 319             servers = fs->next;
 320             delete fs;
 321             fs = servers;
 322         }
 323     }
 324
 325     // done with DNS lookups. pass back to caller
 326
 327     debugs(44, 2, id << " found all " << foundPaths << " destinations for " << url());
 328     debugs(44, 2, "  always_direct = " << always_direct);
 329     debugs(44, 2, "   never_direct = " << never_direct);
 330     debugs(44, 2, "       timedout = " << ping.timedout);
 331
 332     ping.stop = current_time;
 333     request->hier.ping = ping; // final result
 334
 335     if (lastError && foundPaths) {
 336         // nobody cares about errors if we found destinations despite them
 337         debugs(44, 3, "forgetting the last error");
 338         delete lastError;
 339         lastError = nullptr;
 340     }
 341
 342     if (const auto initiator = interestedInitiator())
 343         initiator->noteDestinationsEnd(lastError);
 344     lastError = nullptr; // initiator owns the ErrorState object now
 345     delete this;
 346 }
 347
 348 void
 349 PeerSelector::noteLookup(const Dns::LookupDetails &details)
 350 {
 351     /* ignore lookup delays that occurred after the initiator moved on */
 352
 353     if (selectionAborted())
 354         return;
 355
 356     if (!wantsMoreDestinations())
 357         return;
 358
 359     request->recordLookup(details);
 360 }
 361
 362 void
 363 PeerSelector::noteIp(const Ip::Address &ip)
 364 {
 365     if (selectionAborted())
 366         return;
 367
 368     if (!wantsMoreDestinations())
 369         return;
 370
 371     const auto peer = servers->_peer.valid();
 372
 373     // for TPROXY spoofing, we must skip unusable addresses
 374     if (request->flags.spoofClientIp && !(peer && peer->options.no_tproxy) ) {
 375         if (ip.isIPv4() != request->client_addr.isIPv4())
 376             return; // cannot spoof the client address on this link
 377     }
 378
 379     Comm::ConnectionPointer p = new Comm::Connection();
 380     p->remote = ip;
 381     p->remote.port(peer ? peer->http_port : request->url.port());
 382     handlePath(p, *servers);
 383 }
 384
 385 void
 386 PeerSelector::noteIps(const Dns::CachedIps *ia, const Dns::LookupDetails &details)
 387 {
 388     if (selectionAborted())
 389         return;
 390
 391     FwdServer *fs = servers;
 392     if (!ia) {
 393         debugs(44, 3, "Unknown host: " << (fs->_peer.valid() ? fs->_peer->host : request->url.host()));
 394         // discard any previous error.
 395         delete lastError;
 396         lastError = NULL;
 397         if (fs->code == HIER_DIRECT) {
 398             lastError = new ErrorState(ERR_DNS_FAIL, Http::scServiceUnavailable, request);
 399             lastError->dnsError = details.error;
 400         }
 401     }
 402     // else noteIp() calls have already processed all IPs in *ia
 403
 404     servers = fs->next;
 405     delete fs;
 406
 407     // continue resolving selected peers
 408     resolveSelected();
 409 }
 410
 411 int
 412 PeerSelector::checkNetdbDirect()
 413 {
 414 #if USE_ICMP
 415     CachePeer *p;
 416     int myrtt;
 417     int myhops;
 418
 419     if (direct == DIRECT_NO)
 420         return 0;
 421
 422     /* base lookup on RTT and Hops if ICMP NetDB is enabled. */
 423
 424     myrtt = netdbHostRtt(request->url.host());
 425     debugs(44, 3, "MY RTT = " << myrtt << " msec");
 426     debugs(44, 3, "minimum_direct_rtt = " << Config.minDirectRtt << " msec");
 427
 428     if (myrtt && myrtt <= Config.minDirectRtt)
 429         return 1;
 430
 431     myhops = netdbHostHops(request->url.host());
 432
 433     debugs(44, 3, "MY hops = " << myhops);
 434     debugs(44, 3, "minimum_direct_hops = " << Config.minDirectHops);
 435
 436     if (myhops && myhops <= Config.minDirectHops)
 437         return 1;
 438
 439     p = whichPeer(closest_parent_miss);
 440
 441     if (p == NULL)
 442         return 0;
 443
 444     debugs(44, 3, "closest_parent_miss RTT = " << ping.p_rtt << " msec");
 445
 446     if (myrtt && myrtt <= ping.p_rtt)
 447         return 1;
 448
 449 #endif /* USE_ICMP */
 450
 451     return 0;
 452 }
 453
 454 void
 455 PeerSelector::selectMore()
 456 {
 457     if (selectionAborted())
 458         return;
 459
 460     debugs(44, 3, request->method << ' ' << request->url.host());
 461
 462     /** If we don't know whether DIRECT is permitted ... */
 463     if (direct == DIRECT_UNKNOWN) {
 464         if (always_direct == ACCESS_DUNNO) {
 465             debugs(44, 3, "direct = " << DirectStr[direct] << " (always_direct to be checked)");
 466             /** check always_direct; */
 467             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.AlwaysDirect, request, NULL);
 468             ch->al = al;
 469             acl_checklist = ch;
 470             acl_checklist->syncAle(request, nullptr);
 471             acl_checklist->nonBlockingCheck(CheckAlwaysDirectDone, this);
 472             return;
 473         } else if (never_direct == ACCESS_DUNNO) {
 474             debugs(44, 3, "direct = " << DirectStr[direct] << " (never_direct to be checked)");
 475             /** check never_direct; */
 476             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.NeverDirect, request, NULL);
 477             ch->al = al;
 478             acl_checklist = ch;
 479             acl_checklist->syncAle(request, nullptr);
 480             acl_checklist->nonBlockingCheck(CheckNeverDirectDone, this);
 481             return;
 482         } else if (request->flags.noDirect) {
 483             /** if we are accelerating, direct is not an option. */
 484             direct = DIRECT_NO;
 485             debugs(44, 3, "direct = " << DirectStr[direct] << " (forced non-direct)");
 486         } else if (request->flags.loopDetected) {
 487             /** if we are in a forwarding-loop, direct is not an option. */
 488             direct = DIRECT_YES;
 489             debugs(44, 3, "direct = " << DirectStr[direct] << " (forwarding loop detected)");
 490         } else if (checkNetdbDirect()) {
 491             direct = DIRECT_YES;
 492             debugs(44, 3, "direct = " << DirectStr[direct] << " (checkNetdbDirect)");
 493         } else {
 494             direct = DIRECT_MAYBE;
 495             debugs(44, 3, "direct = " << DirectStr[direct] << " (default)");
 496         }
 497
 498         debugs(44, 3, "direct = " << DirectStr[direct]);
 499     }
 500
 501     if (!entry || entry->ping_status == PING_NONE)
 502         selectPinned();
 503     if (entry == NULL) {
 504         (void) 0;
 505     } else if (entry->ping_status == PING_NONE) {
 506         selectSomeNeighbor();
 507
 508         if (entry->ping_status == PING_WAITING)
 509             return;
 510     } else if (entry->ping_status == PING_WAITING) {
 511         selectSomeNeighborReplies();
 512         entry->ping_status = PING_DONE;
 513     }
 514
 515     switch (direct) {
 516
 517     case DIRECT_YES:
 518         selectSomeDirect();
 519         break;
 520
 521     case DIRECT_NO:
 522         selectSomeParent();
 523         selectAllParents();
 524         break;
 525
 526     default:
 527
 528         if (Config.onoff.prefer_direct)
 529             selectSomeDirect();
 530
 531         if (request->flags.hierarchical || !Config.onoff.nonhierarchical_direct) {
 532             selectSomeParent();
 533             selectAllParents();
 534         }
 535
 536         if (!Config.onoff.prefer_direct)
 537             selectSomeDirect();
 538
 539         break;
 540     }
 541
 542     // end peer selection; start resolving selected peers
 543     resolveSelected();
 544 }
 545
 546 bool peerAllowedToUse(const CachePeer *, PeerSelector*);
 547
 548 /// Selects a pinned connection if it exists, is valid, and is allowed.
 549 void
 550 PeerSelector::selectPinned()
 551 {
 552     // TODO: Avoid all repeated calls. Relying on PING_DONE is not enough.
 553     if (!request->pinnedConnection())
 554         return;
 555     CachePeer *pear = request->pinnedConnection()->pinnedPeer();
 556     if (Comm::IsConnOpen(request->pinnedConnection()->validatePinnedConnection(request, pear))) {
 557         const bool usePinned = pear ? peerAllowedToUse(pear, this) : (direct != DIRECT_NO);
 558         if (usePinned) {
 559             addSelection(pear, PINNED);
 560             if (entry)
 561                 entry->ping_status = PING_DONE; // skip ICP
 562         }
 563     }
 564     // If the pinned connection is prohibited (for this request) or gone, then
 565     // the initiator must decide whether it is OK to open a new one instead.
 566 }
 567
 568 /**
 569  * Selects a neighbor (parent or sibling) based on one of the
 570  * following methods:
 571  *      Cache Digests
 572  *      CARP
 573  *      ICMP Netdb RTT estimates
 574  *      ICP/HTCP queries
 575  */
 576 void
 577 PeerSelector::selectSomeNeighbor()
 578 {
 579     CachePeer *p;
 580     hier_code code = HIER_NONE;
 581     assert(entry->ping_status == PING_NONE);
 582
 583     if (direct == DIRECT_YES) {
 584         entry->ping_status = PING_DONE;
 585         return;
 586     }
 587
 588 #if USE_CACHE_DIGESTS
 589     if ((p = neighborsDigestSelect(this))) {
 590         if (neighborType(p, request->url) == PEER_PARENT)
 591             code = CD_PARENT_HIT;
 592         else
 593             code = CD_SIBLING_HIT;
 594     } else
 595 #endif
 596         if ((p = netdbClosestParent(this))) {
 597             code = CLOSEST_PARENT;
 598         } else if (peerSelectIcpPing(this, direct, entry)) {
 599             debugs(44, 3, "Doing ICP pings");
 600             ping.start = current_time;
 601             ping.n_sent = neighborsUdpPing(request,
 602                                            entry,
 603                                            HandlePingReply,
 604                                            this,
 605                                            &ping.n_replies_expected,
 606                                            &ping.timeout);
 607
 608             if (ping.n_sent == 0)
 609                 debugs(44, DBG_CRITICAL, "WARNING: neighborsUdpPing returned 0");
 610             debugs(44, 3, ping.n_replies_expected <<
 611                    " ICP replies expected, RTT " << ping.timeout <<
 612                    " msec");
 613
 614             if (ping.n_replies_expected > 0) {
 615                 entry->ping_status = PING_WAITING;
 616                 eventAdd("PeerSelector::HandlePingTimeout",
 617                          HandlePingTimeout,
 618                          this,
 619                          0.001 * ping.timeout,
 620                          0);
 621                 return;
 622             }
 623         }
 624
 625     if (code != HIER_NONE) {
 626         assert(p);
 627         addSelection(p, code);
 628     }
 629
 630     entry->ping_status = PING_DONE;
 631 }
 632
 633 /// Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 634 void
 635 PeerSelector::selectSomeNeighborReplies()
 636 {
 637     CachePeer *p = NULL;
 638     hier_code code = HIER_NONE;
 639     assert(entry->ping_status == PING_WAITING);
 640     assert(direct != DIRECT_YES);
 641
 642     if (checkNetdbDirect()) {
 643         code = CLOSEST_DIRECT;
 644         addSelection(nullptr, code);
 645         return;
 646     }
 647
 648     if ((p = hit)) {
 649         code = hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 650     } else {
 651         if (!closest_parent_miss.isAnyAddr()) {
 652             p = whichPeer(closest_parent_miss);
 653             code = CLOSEST_PARENT_MISS;
 654         } else if (!first_parent_miss.isAnyAddr()) {
 655             p = whichPeer(first_parent_miss);
 656             code = FIRST_PARENT_MISS;
 657         }
 658     }
 659     if (p && code != HIER_NONE) {
 660         addSelection(p, code);
 661     }
 662 }
 663
 664 /// Adds a "direct" entry if the request can be forwarded to the origin server.
 665 void
 666 PeerSelector::selectSomeDirect()
 667 {
 668     if (direct == DIRECT_NO)
 669         return;
 670
 671     /* WAIS is not implemented natively */
 672     if (request->url.getScheme() == AnyP::PROTO_WAIS)
 673         return;
 674
 675     addSelection(nullptr, HIER_DIRECT);
 676 }
 677
 678 void
 679 PeerSelector::selectSomeParent()
 680 {
 681     CachePeer *p;
 682     hier_code code = HIER_NONE;
 683     debugs(44, 3, request->method << ' ' << request->url.host());
 684
 685     if (direct == DIRECT_YES)
 686         return;
 687
 688     if ((p = peerSourceHashSelectParent(this))) {
 689         code = SOURCEHASH_PARENT;
 690 #if USE_AUTH
 691     } else if ((p = peerUserHashSelectParent(this))) {
 692         code = USERHASH_PARENT;
 693 #endif
 694     } else if ((p = carpSelectParent(this))) {
 695         code = CARP;
 696     } else if ((p = getRoundRobinParent(this))) {
 697         code = ROUNDROBIN_PARENT;
 698     } else if ((p = getWeightedRoundRobinParent(this))) {
 699         code = ROUNDROBIN_PARENT;
 700     } else if ((p = getFirstUpParent(this))) {
 701         code = FIRSTUP_PARENT;
 702     } else if ((p = getDefaultParent(this))) {
 703         code = DEFAULT_PARENT;
 704     }
 705
 706     if (code != HIER_NONE) {
 707         addSelection(p, code);
 708     }
 709 }
 710
 711 /// Adds alive parents. Used as a last resort for never_direct.
 712 void
 713 PeerSelector::selectAllParents()
 714 {
 715     CachePeer *p;
 716     /* Add all alive parents */
 717
 718     for (p = Config.peers; p; p = p->next) {
 719         /* XXX: neighbors.c lacks a public interface for enumerating
 720          * parents to a request so we have to dig some here..
 721          */
 722
 723         if (neighborType(p, request->url) != PEER_PARENT)
 724             continue;
 725
 726         if (!peerHTTPOkay(p, this))
 727             continue;
 728
 729         addSelection(p, ANY_OLD_PARENT);
 730     }
 731
 732     /* XXX: should add dead parents here, but it is currently
 733      * not possible to find out which parents are dead or which
 734      * simply are not configured to handle the request.
 735      */
 736     /* Add default parent as a last resort */
 737     if ((p = getDefaultParent(this))) {
 738         addSelection(p, DEFAULT_PARENT);
 739     }
 740 }
 741
 742 void
 743 PeerSelector::handlePingTimeout()
 744 {
 745     debugs(44, 3, url());
 746
 747     if (entry)
 748         entry->ping_status = PING_DONE;
 749
 750     if (selectionAborted())
 751         return;
 752
 753     ++PeerStats.timeouts;
 754     ping.timedout = 1;
 755     selectMore();
 756 }
 757
 758 void
 759 PeerSelector::HandlePingTimeout(void *data)
 760 {
 761     static_cast<PeerSelector*>(data)->handlePingTimeout();
 762 }
 763
 764 void
 765 peerSelectInit(void)
 766 {
 767     memset(&PeerStats, '\0', sizeof(PeerStats));
 768 }
 769
 770 void
 771 PeerSelector::handleIcpParentMiss(CachePeer *p, icp_common_t *header)
 772 {
 773     int rtt;
 774
 775 #if USE_ICMP
 776     if (Config.onoff.query_icmp) {
 777         if (header->flags & ICP_FLAG_SRC_RTT) {
 778             rtt = header->pad & 0xFFFF;
 779             int hops = (header->pad >> 16) & 0xFFFF;
 780
 781             if (rtt > 0 && rtt < 0xFFFF)
 782                 netdbUpdatePeer(request->url, p, rtt, hops);
 783
 784             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 785                 closest_parent_miss = p->in_addr;
 786                 ping.p_rtt = rtt;
 787             }
 788         }
 789     }
 790 #endif /* USE_ICMP */
 791
 792     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 793     if (p->options.closest_only)
 794         return;
 795
 796     /* set FIRST_MISS if there is no CLOSEST parent */
 797     if (!closest_parent_miss.isAnyAddr())
 798         return;
 799
 800     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 801
 802     if (rtt < 1)
 803         rtt = 1;
 804
 805     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 806         first_parent_miss = p->in_addr;
 807         ping.w_rtt = rtt;
 808     }
 809 }
 810
 811 void
 812 PeerSelector::handleIcpReply(CachePeer *p, const peer_t type, icp_common_t *header)
 813 {
 814     icp_opcode op = header->getOpCode();
 815     debugs(44, 3, icp_opcode_str[op] << ' ' << url());
 816 #if USE_CACHE_DIGESTS && 0
 817     /* do cd lookup to count false misses */
 818
 819     if (p && request)
 820         peerNoteDigestLookup(request, p,
 821                              peerDigestLookup(p, this));
 822
 823 #endif
 824
 825     ++ping.n_recv;
 826
 827     if (op == ICP_MISS || op == ICP_DECHO) {
 828         if (type == PEER_PARENT)
 829             handleIcpParentMiss(p, header);
 830     } else if (op == ICP_HIT) {
 831         hit = p;
 832         hit_type = type;
 833         selectMore();
 834         return;
 835     }
 836
 837     if (ping.n_recv < ping.n_replies_expected)
 838         return;
 839
 840     selectMore();
 841 }
 842
 843 #if USE_HTCP
 844 void
 845 PeerSelector::handleHtcpReply(CachePeer *p, const peer_t type, HtcpReplyData *htcp)
 846 {
 847     debugs(44, 3, (htcp->hit ? "HIT" : "MISS") << ' ' << url());
 848     ++ping.n_recv;
 849
 850     if (htcp->hit) {
 851         hit = p;
 852         hit_type = type;
 853         selectMore();
 854         return;
 855     }
 856
 857     if (type == PEER_PARENT)
 858         handleHtcpParentMiss(p, htcp);
 859
 860     if (ping.n_recv < ping.n_replies_expected)
 861         return;
 862
 863     selectMore();
 864 }
 865
 866 void
 867 PeerSelector::handleHtcpParentMiss(CachePeer *p, HtcpReplyData *htcp)
 868 {
 869     int rtt;
 870
 871 #if USE_ICMP
 872     if (Config.onoff.query_icmp) {
 873         if (htcp->cto.rtt > 0) {
 874             rtt = (int) htcp->cto.rtt * 1000;
 875             int hops = (int) htcp->cto.hops * 1000;
 876             netdbUpdatePeer(request->url, p, rtt, hops);
 877
 878             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 879                 closest_parent_miss = p->in_addr;
 880                 ping.p_rtt = rtt;
 881             }
 882         }
 883     }
 884 #endif /* USE_ICMP */
 885
 886     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 887     if (p->options.closest_only)
 888         return;
 889
 890     /* set FIRST_MISS if there is no CLOSEST parent */
 891     if (!closest_parent_miss.isAnyAddr())
 892         return;
 893
 894     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 895
 896     if (rtt < 1)
 897         rtt = 1;
 898
 899     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 900         first_parent_miss = p->in_addr;
 901         ping.w_rtt = rtt;
 902     }
 903 }
 904
 905 #endif
 906
 907 void
 908 PeerSelector::HandlePingReply(CachePeer * p, peer_t type, AnyP::ProtocolType proto, void *pingdata, void *data)
 909 {
 910     if (proto == AnyP::PROTO_ICP)
 911         static_cast<PeerSelector*>(data)->handleIcpReply(p, type, static_cast<icp_common_t*>(pingdata));
 912
 913 #if USE_HTCP
 914
 915     else if (proto == AnyP::PROTO_HTCP)
 916         static_cast<PeerSelector*>(data)->handleHtcpReply(p, type, static_cast<HtcpReplyData*>(pingdata));
 917
 918 #endif
 919
 920     else
 921         debugs(44, DBG_IMPORTANT, "ERROR: ignoring an ICP reply with unknown protocol " << proto);
 922 }
 923
 924 void
 925 PeerSelector::addSelection(CachePeer *peer, const hier_code code)
 926 {
 927     // Find the end of the servers list. Bail on a duplicate destination.
 928     auto **serversTail = &servers;
 929     while (const auto server = *serversTail) {
 930         // There can be at most one PINNED destination.
 931         // Non-PINNED destinations are uniquely identified by their CachePeer
 932         // (even though a DIRECT destination might match a cache_peer address).
 933         const bool duplicate = (server->code == PINNED) ?
 934                                (code == PINNED) : (server->_peer == peer);
 935         if (duplicate) {
 936             debugs(44, 3, "skipping " << PeerSelectionDumper(this, peer, code) <<
 937                    "; have " << PeerSelectionDumper(this, server->_peer.get(), server->code));
 938             return;
 939         }
 940         serversTail = &server->next;
 941     }
 942
 943     debugs(44, 3, "adding " << PeerSelectionDumper(this, peer, code));
 944     *serversTail = new FwdServer(peer, code);
 945 }
 946
 947 PeerSelector::PeerSelector(PeerSelectionInitiator *initiator):
 948     request(nullptr),
 949     entry (NULL),
 950     always_direct(Config.accessList.AlwaysDirect?ACCESS_DUNNO:ACCESS_DENIED),
 951     never_direct(Config.accessList.NeverDirect?ACCESS_DUNNO:ACCESS_DENIED),
 952     direct(DIRECT_UNKNOWN),
 953     lastError(NULL),
 954     servers (NULL),
 955     first_parent_miss(),
 956     closest_parent_miss(),
 957     hit(NULL),
 958     hit_type(PEER_NONE),
 959     acl_checklist (NULL),
 960     initiator_(initiator)
 961 {
 962     ; // no local defaults.
 963 }
 964
 965 const SBuf
 966 PeerSelector::url() const
 967 {
 968     if (entry)
 969         return SBuf(entry->url());
 970
 971     if (request)
 972         return request->effectiveRequestUri();
 973
 974     static const SBuf noUrl("[no URL]");
 975     return noUrl;
 976 }
 977
 978 /// \returns valid/interested peer initiator or nil
 979 PeerSelectionInitiator *
 980 PeerSelector::interestedInitiator()
 981 {
 982     const auto initiator = initiator_.valid();
 983
 984     if (!initiator) {
 985         debugs(44, 3, id << " initiator gone");
 986         return nullptr;
 987     }
 988
 989     if (!initiator->subscribed) {
 990         debugs(44, 3, id << " initiator lost interest");
 991         return nullptr;
 992     }
 993
 994     debugs(44, 7, id);
 995     return initiator;
 996 }
 997
 998 bool
 999 PeerSelector::wantsMoreDestinations() const {
1000     const auto maxCount = Config.forward_max_tries;
1001     return maxCount >= 0 && foundPaths <
1002            static_cast<std::make_unsigned<decltype(maxCount)>::type>(maxCount);
1003 }
1004
1005 void
1006 PeerSelector::handlePath(Comm::ConnectionPointer &path, FwdServer &fs)
1007 {
1008     ++foundPaths;
1009
1010     path->peerType = fs.code;
1011     path->setPeer(fs._peer.get());
1012
1013     // check for a configured outgoing address for this destination...
1014     getOutgoingAddress(request, path);
1015
1016     request->hier.ping = ping; // may be updated later
1017
1018     debugs(44, 2, id << " found " << path << ", destination #" << foundPaths << " for " << url());
1019     debugs(44, 2, "  always_direct = " << always_direct);
1020     debugs(44, 2, "   never_direct = " << never_direct);
1021     debugs(44, 2, "       timedout = " << ping.timedout);
1022
1023     if (const auto initiator = interestedInitiator())
1024         initiator->noteDestination(path);
1025 }
1026
1027 InstanceIdDefinitions(PeerSelector, "PeerSelector");
1028
1029 ping_data::ping_data() :
1030     n_sent(0),
1031     n_recv(0),
1032     n_replies_expected(0),
1033     timeout(0),
1034     timedout(0),
1035     w_rtt(0),
1036     p_rtt(0)
1037 {
1038     start.tv_sec = 0;
1039     start.tv_usec = 0;
1040     stop.tv_sec = 0;
1041     stop.tv_usec = 0;
1042 }
1043