src/peer_select.cc

   1 /*
   2  * Copyright (C) 1996-2019 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 Acl::Answer 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(Acl::Answer answer, void *data)
 224 {
 225     static_cast<PeerSelector*>(data)->checkNeverDirectDone(answer);
 226 }
 227
 228 void
 229 PeerSelector::checkAlwaysDirectDone(const Acl::Answer 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(Acl::Answer 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     if (fs && fs->code == PINNED) {
 305         // Nil path signals a PINNED destination selection. Our initiator should
 306         // borrow and use clientConnectionManager's pinned connection object
 307         // (regardless of that connection destination).
 308         handlePath(nullptr, *fs);
 309         servers = fs->next;
 310         delete fs;
 311         resolveSelected();
 312         return;
 313     }
 314
 315     // convert the list of FwdServer destinations into destinations IP addresses
 316     if (fs && wantsMoreDestinations()) {
 317         // send the next one off for DNS lookup.
 318         const char *host = fs->_peer.valid() ? fs->_peer->host : request->url.host();
 319         debugs(44, 2, "Find IP destination for: " << url() << "' via " << host);
 320         Dns::nbgethostbyname(host, this);
 321         return;
 322     }
 323
 324     // Bug 3605: clear any extra listed FwdServer destinations, when the options exceeds max_foward_tries.
 325     // due to the allocation method of fs, we must deallocate each manually.
 326     // TODO: use a std::list so we can get the size and abort adding whenever the selection loops reach Config.forward_max_tries
 327     if (fs) {
 328         assert(fs == servers);
 329         while (fs) {
 330             servers = fs->next;
 331             delete fs;
 332             fs = servers;
 333         }
 334     }
 335
 336     // done with DNS lookups. pass back to caller
 337
 338     debugs(44, 2, id << " found all " << foundPaths << " destinations for " << url());
 339     debugs(44, 2, "  always_direct = " << always_direct);
 340     debugs(44, 2, "   never_direct = " << never_direct);
 341     debugs(44, 2, "       timedout = " << ping.timedout);
 342
 343     ping.stop = current_time;
 344     request->hier.ping = ping; // final result
 345
 346     if (lastError && foundPaths) {
 347         // nobody cares about errors if we found destinations despite them
 348         debugs(44, 3, "forgetting the last error");
 349         delete lastError;
 350         lastError = nullptr;
 351     }
 352
 353     if (const auto initiator = interestedInitiator())
 354         initiator->noteDestinationsEnd(lastError);
 355     lastError = nullptr; // initiator owns the ErrorState object now
 356     delete this;
 357 }
 358
 359 void
 360 PeerSelector::noteLookup(const Dns::LookupDetails &details)
 361 {
 362     /* ignore lookup delays that occurred after the initiator moved on */
 363
 364     if (selectionAborted())
 365         return;
 366
 367     if (!wantsMoreDestinations())
 368         return;
 369
 370     request->recordLookup(details);
 371 }
 372
 373 void
 374 PeerSelector::noteIp(const Ip::Address &ip)
 375 {
 376     if (selectionAborted())
 377         return;
 378
 379     if (!wantsMoreDestinations())
 380         return;
 381
 382     const auto peer = servers->_peer.valid();
 383
 384     // for TPROXY spoofing, we must skip unusable addresses
 385     if (request->flags.spoofClientIp && !(peer && peer->options.no_tproxy) ) {
 386         if (ip.isIPv4() != request->client_addr.isIPv4())
 387             return; // cannot spoof the client address on this link
 388     }
 389
 390     Comm::ConnectionPointer p = new Comm::Connection();
 391     p->remote = ip;
 392     p->remote.port(peer ? peer->http_port : request->url.port());
 393     handlePath(p, *servers);
 394 }
 395
 396 void
 397 PeerSelector::noteIps(const Dns::CachedIps *ia, const Dns::LookupDetails &details)
 398 {
 399     if (selectionAborted())
 400         return;
 401
 402     FwdServer *fs = servers;
 403     if (!ia) {
 404         debugs(44, 3, "Unknown host: " << (fs->_peer.valid() ? fs->_peer->host : request->url.host()));
 405         // discard any previous error.
 406         delete lastError;
 407         lastError = NULL;
 408         if (fs->code == HIER_DIRECT) {
 409             lastError = new ErrorState(ERR_DNS_FAIL, Http::scServiceUnavailable, request, al);
 410             lastError->dnsError = details.error;
 411         }
 412     }
 413     // else noteIp() calls have already processed all IPs in *ia
 414
 415     servers = fs->next;
 416     delete fs;
 417
 418     // continue resolving selected peers
 419     resolveSelected();
 420 }
 421
 422 int
 423 PeerSelector::checkNetdbDirect()
 424 {
 425 #if USE_ICMP
 426     CachePeer *p;
 427     int myrtt;
 428     int myhops;
 429
 430     if (direct == DIRECT_NO)
 431         return 0;
 432
 433     /* base lookup on RTT and Hops if ICMP NetDB is enabled. */
 434
 435     myrtt = netdbHostRtt(request->url.host());
 436     debugs(44, 3, "MY RTT = " << myrtt << " msec");
 437     debugs(44, 3, "minimum_direct_rtt = " << Config.minDirectRtt << " msec");
 438
 439     if (myrtt && myrtt <= Config.minDirectRtt)
 440         return 1;
 441
 442     myhops = netdbHostHops(request->url.host());
 443
 444     debugs(44, 3, "MY hops = " << myhops);
 445     debugs(44, 3, "minimum_direct_hops = " << Config.minDirectHops);
 446
 447     if (myhops && myhops <= Config.minDirectHops)
 448         return 1;
 449
 450     p = whichPeer(closest_parent_miss);
 451
 452     if (p == NULL)
 453         return 0;
 454
 455     debugs(44, 3, "closest_parent_miss RTT = " << ping.p_rtt << " msec");
 456
 457     if (myrtt && myrtt <= ping.p_rtt)
 458         return 1;
 459
 460 #endif /* USE_ICMP */
 461
 462     return 0;
 463 }
 464
 465 void
 466 PeerSelector::selectMore()
 467 {
 468     if (selectionAborted())
 469         return;
 470
 471     debugs(44, 3, request->method << ' ' << request->url.host());
 472
 473     /** If we don't know whether DIRECT is permitted ... */
 474     if (direct == DIRECT_UNKNOWN) {
 475         if (always_direct == ACCESS_DUNNO) {
 476             debugs(44, 3, "direct = " << DirectStr[direct] << " (always_direct to be checked)");
 477             /** check always_direct; */
 478             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.AlwaysDirect, request, NULL);
 479             ch->al = al;
 480             acl_checklist = ch;
 481             acl_checklist->syncAle(request, nullptr);
 482             acl_checklist->nonBlockingCheck(CheckAlwaysDirectDone, this);
 483             return;
 484         } else if (never_direct == ACCESS_DUNNO) {
 485             debugs(44, 3, "direct = " << DirectStr[direct] << " (never_direct to be checked)");
 486             /** check never_direct; */
 487             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.NeverDirect, request, NULL);
 488             ch->al = al;
 489             acl_checklist = ch;
 490             acl_checklist->syncAle(request, nullptr);
 491             acl_checklist->nonBlockingCheck(CheckNeverDirectDone, this);
 492             return;
 493         } else if (request->flags.noDirect) {
 494             /** if we are accelerating, direct is not an option. */
 495             direct = DIRECT_NO;
 496             debugs(44, 3, "direct = " << DirectStr[direct] << " (forced non-direct)");
 497         } else if (request->flags.loopDetected) {
 498             /** if we are in a forwarding-loop, direct is not an option. */
 499             direct = DIRECT_YES;
 500             debugs(44, 3, "direct = " << DirectStr[direct] << " (forwarding loop detected)");
 501         } else if (checkNetdbDirect()) {
 502             direct = DIRECT_YES;
 503             debugs(44, 3, "direct = " << DirectStr[direct] << " (checkNetdbDirect)");
 504         } else {
 505             direct = DIRECT_MAYBE;
 506             debugs(44, 3, "direct = " << DirectStr[direct] << " (default)");
 507         }
 508
 509         debugs(44, 3, "direct = " << DirectStr[direct]);
 510     }
 511
 512     if (!entry || entry->ping_status == PING_NONE)
 513         selectPinned();
 514     if (entry == NULL) {
 515         (void) 0;
 516     } else if (entry->ping_status == PING_NONE) {
 517         selectSomeNeighbor();
 518
 519         if (entry->ping_status == PING_WAITING)
 520             return;
 521     } else if (entry->ping_status == PING_WAITING) {
 522         selectSomeNeighborReplies();
 523         entry->ping_status = PING_DONE;
 524     }
 525
 526     switch (direct) {
 527
 528     case DIRECT_YES:
 529         selectSomeDirect();
 530         break;
 531
 532     case DIRECT_NO:
 533         selectSomeParent();
 534         selectAllParents();
 535         break;
 536
 537     default:
 538
 539         if (Config.onoff.prefer_direct)
 540             selectSomeDirect();
 541
 542         if (request->flags.hierarchical || !Config.onoff.nonhierarchical_direct) {
 543             selectSomeParent();
 544             selectAllParents();
 545         }
 546
 547         if (!Config.onoff.prefer_direct)
 548             selectSomeDirect();
 549
 550         break;
 551     }
 552
 553     // end peer selection; start resolving selected peers
 554     resolveSelected();
 555 }
 556
 557 bool peerAllowedToUse(const CachePeer *, PeerSelector*);
 558
 559 /// Selects a pinned connection if it exists, is valid, and is allowed.
 560 void
 561 PeerSelector::selectPinned()
 562 {
 563     // TODO: Avoid all repeated calls. Relying on PING_DONE is not enough.
 564     if (!request->pinnedConnection())
 565         return;
 566
 567     if (Comm::IsConnOpen(request->pinnedConnection()->validatePinnedConnection(request))) {
 568         const auto pear = request->pinnedConnection()->pinnedPeer();
 569         const bool usePinned = pear ? peerAllowedToUse(pear, this) : (direct != DIRECT_NO);
 570         if (usePinned) {
 571             addSelection(pear, PINNED);
 572             if (entry)
 573                 entry->ping_status = PING_DONE; // skip ICP
 574         }
 575     }
 576     // If the pinned connection is prohibited (for this request) or gone, then
 577     // the initiator must decide whether it is OK to open a new one instead.
 578 }
 579
 580 /**
 581  * Selects a neighbor (parent or sibling) based on one of the
 582  * following methods:
 583  *      Cache Digests
 584  *      CARP
 585  *      ICMP Netdb RTT estimates
 586  *      ICP/HTCP queries
 587  */
 588 void
 589 PeerSelector::selectSomeNeighbor()
 590 {
 591     CachePeer *p;
 592     hier_code code = HIER_NONE;
 593     assert(entry->ping_status == PING_NONE);
 594
 595     if (direct == DIRECT_YES) {
 596         entry->ping_status = PING_DONE;
 597         return;
 598     }
 599
 600 #if USE_CACHE_DIGESTS
 601     if ((p = neighborsDigestSelect(this))) {
 602         if (neighborType(p, request->url) == PEER_PARENT)
 603             code = CD_PARENT_HIT;
 604         else
 605             code = CD_SIBLING_HIT;
 606     } else
 607 #endif
 608         if ((p = netdbClosestParent(this))) {
 609             code = CLOSEST_PARENT;
 610         } else if (peerSelectIcpPing(this, direct, entry)) {
 611             debugs(44, 3, "Doing ICP pings");
 612             ping.start = current_time;
 613             ping.n_sent = neighborsUdpPing(request,
 614                                            entry,
 615                                            HandlePingReply,
 616                                            this,
 617                                            &ping.n_replies_expected,
 618                                            &ping.timeout);
 619
 620             if (ping.n_sent == 0)
 621                 debugs(44, DBG_CRITICAL, "WARNING: neighborsUdpPing returned 0");
 622             debugs(44, 3, ping.n_replies_expected <<
 623                    " ICP replies expected, RTT " << ping.timeout <<
 624                    " msec");
 625
 626             if (ping.n_replies_expected > 0) {
 627                 entry->ping_status = PING_WAITING;
 628                 eventAdd("PeerSelector::HandlePingTimeout",
 629                          HandlePingTimeout,
 630                          this,
 631                          0.001 * ping.timeout,
 632                          0);
 633                 return;
 634             }
 635         }
 636
 637     if (code != HIER_NONE) {
 638         assert(p);
 639         addSelection(p, code);
 640     }
 641
 642     entry->ping_status = PING_DONE;
 643 }
 644
 645 /// Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 646 void
 647 PeerSelector::selectSomeNeighborReplies()
 648 {
 649     CachePeer *p = NULL;
 650     hier_code code = HIER_NONE;
 651     assert(entry->ping_status == PING_WAITING);
 652     assert(direct != DIRECT_YES);
 653
 654     if (checkNetdbDirect()) {
 655         code = CLOSEST_DIRECT;
 656         addSelection(nullptr, code);
 657         return;
 658     }
 659
 660     if ((p = hit)) {
 661         code = hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 662     } else {
 663         if (!closest_parent_miss.isAnyAddr()) {
 664             p = whichPeer(closest_parent_miss);
 665             code = CLOSEST_PARENT_MISS;
 666         } else if (!first_parent_miss.isAnyAddr()) {
 667             p = whichPeer(first_parent_miss);
 668             code = FIRST_PARENT_MISS;
 669         }
 670     }
 671     if (p && code != HIER_NONE) {
 672         addSelection(p, code);
 673     }
 674 }
 675
 676 /// Adds a "direct" entry if the request can be forwarded to the origin server.
 677 void
 678 PeerSelector::selectSomeDirect()
 679 {
 680     if (direct == DIRECT_NO)
 681         return;
 682
 683     /* WAIS is not implemented natively */
 684     if (request->url.getScheme() == AnyP::PROTO_WAIS)
 685         return;
 686
 687     addSelection(nullptr, HIER_DIRECT);
 688 }
 689
 690 void
 691 PeerSelector::selectSomeParent()
 692 {
 693     CachePeer *p;
 694     hier_code code = HIER_NONE;
 695     debugs(44, 3, request->method << ' ' << request->url.host());
 696
 697     if (direct == DIRECT_YES)
 698         return;
 699
 700     if ((p = peerSourceHashSelectParent(this))) {
 701         code = SOURCEHASH_PARENT;
 702 #if USE_AUTH
 703     } else if ((p = peerUserHashSelectParent(this))) {
 704         code = USERHASH_PARENT;
 705 #endif
 706     } else if ((p = carpSelectParent(this))) {
 707         code = CARP;
 708     } else if ((p = getRoundRobinParent(this))) {
 709         code = ROUNDROBIN_PARENT;
 710     } else if ((p = getWeightedRoundRobinParent(this))) {
 711         code = ROUNDROBIN_PARENT;
 712     } else if ((p = getFirstUpParent(this))) {
 713         code = FIRSTUP_PARENT;
 714     } else if ((p = getDefaultParent(this))) {
 715         code = DEFAULT_PARENT;
 716     }
 717
 718     if (code != HIER_NONE) {
 719         addSelection(p, code);
 720     }
 721 }
 722
 723 /// Adds alive parents. Used as a last resort for never_direct.
 724 void
 725 PeerSelector::selectAllParents()
 726 {
 727     CachePeer *p;
 728     /* Add all alive parents */
 729
 730     for (p = Config.peers; p; p = p->next) {
 731         /* XXX: neighbors.c lacks a public interface for enumerating
 732          * parents to a request so we have to dig some here..
 733          */
 734
 735         if (neighborType(p, request->url) != PEER_PARENT)
 736             continue;
 737
 738         if (!peerHTTPOkay(p, this))
 739             continue;
 740
 741         addSelection(p, ANY_OLD_PARENT);
 742     }
 743
 744     /* XXX: should add dead parents here, but it is currently
 745      * not possible to find out which parents are dead or which
 746      * simply are not configured to handle the request.
 747      */
 748     /* Add default parent as a last resort */
 749     if ((p = getDefaultParent(this))) {
 750         addSelection(p, DEFAULT_PARENT);
 751     }
 752 }
 753
 754 void
 755 PeerSelector::handlePingTimeout()
 756 {
 757     debugs(44, 3, url());
 758
 759     if (entry)
 760         entry->ping_status = PING_DONE;
 761
 762     if (selectionAborted())
 763         return;
 764
 765     ++PeerStats.timeouts;
 766     ping.timedout = 1;
 767     selectMore();
 768 }
 769
 770 void
 771 PeerSelector::HandlePingTimeout(void *data)
 772 {
 773     static_cast<PeerSelector*>(data)->handlePingTimeout();
 774 }
 775
 776 void
 777 peerSelectInit(void)
 778 {
 779     memset(&PeerStats, '\0', sizeof(PeerStats));
 780 }
 781
 782 void
 783 PeerSelector::handleIcpParentMiss(CachePeer *p, icp_common_t *header)
 784 {
 785     int rtt;
 786
 787 #if USE_ICMP
 788     if (Config.onoff.query_icmp) {
 789         if (header->flags & ICP_FLAG_SRC_RTT) {
 790             rtt = header->pad & 0xFFFF;
 791             int hops = (header->pad >> 16) & 0xFFFF;
 792
 793             if (rtt > 0 && rtt < 0xFFFF)
 794                 netdbUpdatePeer(request->url, p, rtt, hops);
 795
 796             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 797                 closest_parent_miss = p->in_addr;
 798                 ping.p_rtt = rtt;
 799             }
 800         }
 801     }
 802 #endif /* USE_ICMP */
 803
 804     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 805     if (p->options.closest_only)
 806         return;
 807
 808     /* set FIRST_MISS if there is no CLOSEST parent */
 809     if (!closest_parent_miss.isAnyAddr())
 810         return;
 811
 812     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 813
 814     if (rtt < 1)
 815         rtt = 1;
 816
 817     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 818         first_parent_miss = p->in_addr;
 819         ping.w_rtt = rtt;
 820     }
 821 }
 822
 823 void
 824 PeerSelector::handleIcpReply(CachePeer *p, const peer_t type, icp_common_t *header)
 825 {
 826     icp_opcode op = header->getOpCode();
 827     debugs(44, 3, icp_opcode_str[op] << ' ' << url());
 828 #if USE_CACHE_DIGESTS && 0
 829     /* do cd lookup to count false misses */
 830
 831     if (p && request)
 832         peerNoteDigestLookup(request, p,
 833                              peerDigestLookup(p, this));
 834
 835 #endif
 836
 837     ++ping.n_recv;
 838
 839     if (op == ICP_MISS || op == ICP_DECHO) {
 840         if (type == PEER_PARENT)
 841             handleIcpParentMiss(p, header);
 842     } else if (op == ICP_HIT) {
 843         hit = p;
 844         hit_type = type;
 845         selectMore();
 846         return;
 847     }
 848
 849     if (ping.n_recv < ping.n_replies_expected)
 850         return;
 851
 852     selectMore();
 853 }
 854
 855 #if USE_HTCP
 856 void
 857 PeerSelector::handleHtcpReply(CachePeer *p, const peer_t type, HtcpReplyData *htcp)
 858 {
 859     debugs(44, 3, (htcp->hit ? "HIT" : "MISS") << ' ' << url());
 860     ++ping.n_recv;
 861
 862     if (htcp->hit) {
 863         hit = p;
 864         hit_type = type;
 865         selectMore();
 866         return;
 867     }
 868
 869     if (type == PEER_PARENT)
 870         handleHtcpParentMiss(p, htcp);
 871
 872     if (ping.n_recv < ping.n_replies_expected)
 873         return;
 874
 875     selectMore();
 876 }
 877
 878 void
 879 PeerSelector::handleHtcpParentMiss(CachePeer *p, HtcpReplyData *htcp)
 880 {
 881     int rtt;
 882
 883 #if USE_ICMP
 884     if (Config.onoff.query_icmp) {
 885         if (htcp->cto.rtt > 0) {
 886             rtt = (int) htcp->cto.rtt * 1000;
 887             int hops = (int) htcp->cto.hops * 1000;
 888             netdbUpdatePeer(request->url, p, rtt, hops);
 889
 890             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 891                 closest_parent_miss = p->in_addr;
 892                 ping.p_rtt = rtt;
 893             }
 894         }
 895     }
 896 #endif /* USE_ICMP */
 897
 898     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 899     if (p->options.closest_only)
 900         return;
 901
 902     /* set FIRST_MISS if there is no CLOSEST parent */
 903     if (!closest_parent_miss.isAnyAddr())
 904         return;
 905
 906     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 907
 908     if (rtt < 1)
 909         rtt = 1;
 910
 911     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 912         first_parent_miss = p->in_addr;
 913         ping.w_rtt = rtt;
 914     }
 915 }
 916
 917 #endif
 918
 919 void
 920 PeerSelector::HandlePingReply(CachePeer * p, peer_t type, AnyP::ProtocolType proto, void *pingdata, void *data)
 921 {
 922     if (proto == AnyP::PROTO_ICP)
 923         static_cast<PeerSelector*>(data)->handleIcpReply(p, type, static_cast<icp_common_t*>(pingdata));
 924
 925 #if USE_HTCP
 926
 927     else if (proto == AnyP::PROTO_HTCP)
 928         static_cast<PeerSelector*>(data)->handleHtcpReply(p, type, static_cast<HtcpReplyData*>(pingdata));
 929
 930 #endif
 931
 932     else
 933         debugs(44, DBG_IMPORTANT, "ERROR: ignoring an ICP reply with unknown protocol " << proto);
 934 }
 935
 936 void
 937 PeerSelector::addSelection(CachePeer *peer, const hier_code code)
 938 {
 939     // Find the end of the servers list. Bail on a duplicate destination.
 940     auto **serversTail = &servers;
 941     while (const auto server = *serversTail) {
 942         // There can be at most one PINNED destination.
 943         // Non-PINNED destinations are uniquely identified by their CachePeer
 944         // (even though a DIRECT destination might match a cache_peer address).
 945         const bool duplicate = (server->code == PINNED) ?
 946                                (code == PINNED) : (server->_peer == peer);
 947         if (duplicate) {
 948             debugs(44, 3, "skipping " << PeerSelectionDumper(this, peer, code) <<
 949                    "; have " << PeerSelectionDumper(this, server->_peer.get(), server->code));
 950             return;
 951         }
 952         serversTail = &server->next;
 953     }
 954
 955     debugs(44, 3, "adding " << PeerSelectionDumper(this, peer, code));
 956     *serversTail = new FwdServer(peer, code);
 957 }
 958
 959 PeerSelector::PeerSelector(PeerSelectionInitiator *initiator):
 960     request(nullptr),
 961     entry (NULL),
 962     always_direct(Config.accessList.AlwaysDirect?ACCESS_DUNNO:ACCESS_DENIED),
 963     never_direct(Config.accessList.NeverDirect?ACCESS_DUNNO:ACCESS_DENIED),
 964     direct(DIRECT_UNKNOWN),
 965     lastError(NULL),
 966     servers (NULL),
 967     first_parent_miss(),
 968     closest_parent_miss(),
 969     hit(NULL),
 970     hit_type(PEER_NONE),
 971     acl_checklist (NULL),
 972     initiator_(initiator)
 973 {
 974     ; // no local defaults.
 975 }
 976
 977 const SBuf
 978 PeerSelector::url() const
 979 {
 980     if (entry)
 981         return SBuf(entry->url());
 982
 983     if (request)
 984         return request->effectiveRequestUri();
 985
 986     static const SBuf noUrl("[no URL]");
 987     return noUrl;
 988 }
 989
 990 /// \returns valid/interested peer initiator or nil
 991 PeerSelectionInitiator *
 992 PeerSelector::interestedInitiator()
 993 {
 994     const auto initiator = initiator_.valid();
 995
 996     if (!initiator) {
 997         debugs(44, 3, id << " initiator gone");
 998         return nullptr;
 999     }
1000
1001     if (!initiator->subscribed) {
1002         debugs(44, 3, id << " initiator lost interest");
1003         return nullptr;
1004     }
1005
1006     debugs(44, 7, id);
1007     return initiator;
1008 }
1009
1010 bool
1011 PeerSelector::wantsMoreDestinations() const {
1012     const auto maxCount = Config.forward_max_tries;
1013     return maxCount >= 0 && foundPaths <
1014            static_cast<std::make_unsigned<decltype(maxCount)>::type>(maxCount);
1015 }
1016
1017 void
1018 PeerSelector::handlePath(const Comm::ConnectionPointer &path, FwdServer &fs)
1019 {
1020     ++foundPaths;
1021
1022     if (path) {
1023         path->peerType = fs.code;
1024         path->setPeer(fs._peer.get());
1025
1026         // check for a configured outgoing address for this destination...
1027         getOutgoingAddress(request, path);
1028         debugs(44, 2, id << " found " << path << ", destination #" << foundPaths << " for " << url());
1029     } else
1030         debugs(44, 2, id << " found pinned, destination #" << foundPaths << " for " << url());
1031
1032     request->hier.ping = ping; // may be updated later
1033
1034     debugs(44, 2, "  always_direct = " << always_direct);
1035     debugs(44, 2, "   never_direct = " << never_direct);
1036     debugs(44, 2, "       timedout = " << ping.timedout);
1037
1038     if (const auto initiator = interestedInitiator())
1039         initiator->noteDestination(path);
1040 }
1041
1042 InstanceIdDefinitions(PeerSelector, "PeerSelector");
1043
1044 ping_data::ping_data() :
1045     n_sent(0),
1046     n_recv(0),
1047     n_replies_expected(0),
1048     timeout(0),
1049     timedout(0),
1050     w_rtt(0),
1051     p_rtt(0)
1052 {
1053     start.tv_sec = 0;
1054     start.tv_usec = 0;
1055     stop.tv_sec = 0;
1056     stop.tv_usec = 0;
1057 }
1058