src/peer_select.cc

   1 /*
   2  * Copyright (C) 1996-2020 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     const auto peer = request->pinnedConnection()->pinnedPeer();
 568     const auto usePinned = peer ? peerAllowedToUse(peer, this) : (direct != DIRECT_NO);
 569     // If the pinned connection is prohibited (for this request) then
 570     // the initiator must decide whether it is OK to open a new one instead.
 571     request->pinnedConnection()->pinning.peerAccessDenied = !usePinned;
 572
 573     addSelection(peer, PINNED);
 574     if (entry)
 575         entry->ping_status = PING_DONE; // skip ICP
 576 }
 577
 578 /**
 579  * Selects a neighbor (parent or sibling) based on one of the
 580  * following methods:
 581  *      Cache Digests
 582  *      CARP
 583  *      ICMP Netdb RTT estimates
 584  *      ICP/HTCP queries
 585  */
 586 void
 587 PeerSelector::selectSomeNeighbor()
 588 {
 589     CachePeer *p;
 590     hier_code code = HIER_NONE;
 591     assert(entry->ping_status == PING_NONE);
 592
 593     if (direct == DIRECT_YES) {
 594         entry->ping_status = PING_DONE;
 595         return;
 596     }
 597
 598 #if USE_CACHE_DIGESTS
 599     if ((p = neighborsDigestSelect(this))) {
 600         if (neighborType(p, request->url) == PEER_PARENT)
 601             code = CD_PARENT_HIT;
 602         else
 603             code = CD_SIBLING_HIT;
 604     } else
 605 #endif
 606         if ((p = netdbClosestParent(this))) {
 607             code = CLOSEST_PARENT;
 608         } else if (peerSelectIcpPing(this, direct, entry)) {
 609             debugs(44, 3, "Doing ICP pings");
 610             ping.start = current_time;
 611             ping.n_sent = neighborsUdpPing(request,
 612                                            entry,
 613                                            HandlePingReply,
 614                                            this,
 615                                            &ping.n_replies_expected,
 616                                            &ping.timeout);
 617
 618             if (ping.n_sent == 0)
 619                 debugs(44, DBG_CRITICAL, "WARNING: neighborsUdpPing returned 0");
 620             debugs(44, 3, ping.n_replies_expected <<
 621                    " ICP replies expected, RTT " << ping.timeout <<
 622                    " msec");
 623
 624             if (ping.n_replies_expected > 0) {
 625                 entry->ping_status = PING_WAITING;
 626                 eventAdd("PeerSelector::HandlePingTimeout",
 627                          HandlePingTimeout,
 628                          this,
 629                          0.001 * ping.timeout,
 630                          0);
 631                 return;
 632             }
 633         }
 634
 635     if (code != HIER_NONE) {
 636         assert(p);
 637         addSelection(p, code);
 638     }
 639
 640     entry->ping_status = PING_DONE;
 641 }
 642
 643 /// Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 644 void
 645 PeerSelector::selectSomeNeighborReplies()
 646 {
 647     CachePeer *p = NULL;
 648     hier_code code = HIER_NONE;
 649     assert(entry->ping_status == PING_WAITING);
 650     assert(direct != DIRECT_YES);
 651
 652     if (checkNetdbDirect()) {
 653         code = CLOSEST_DIRECT;
 654         addSelection(nullptr, code);
 655         return;
 656     }
 657
 658     if ((p = hit)) {
 659         code = hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 660     } else {
 661         if (!closest_parent_miss.isAnyAddr()) {
 662             p = whichPeer(closest_parent_miss);
 663             code = CLOSEST_PARENT_MISS;
 664         } else if (!first_parent_miss.isAnyAddr()) {
 665             p = whichPeer(first_parent_miss);
 666             code = FIRST_PARENT_MISS;
 667         }
 668     }
 669     if (p && code != HIER_NONE) {
 670         addSelection(p, code);
 671     }
 672 }
 673
 674 /// Adds a "direct" entry if the request can be forwarded to the origin server.
 675 void
 676 PeerSelector::selectSomeDirect()
 677 {
 678     if (direct == DIRECT_NO)
 679         return;
 680
 681     /* WAIS is not implemented natively */
 682     if (request->url.getScheme() == AnyP::PROTO_WAIS)
 683         return;
 684
 685     addSelection(nullptr, HIER_DIRECT);
 686 }
 687
 688 void
 689 PeerSelector::selectSomeParent()
 690 {
 691     CachePeer *p;
 692     hier_code code = HIER_NONE;
 693     debugs(44, 3, request->method << ' ' << request->url.host());
 694
 695     if (direct == DIRECT_YES)
 696         return;
 697
 698     if ((p = peerSourceHashSelectParent(this))) {
 699         code = SOURCEHASH_PARENT;
 700 #if USE_AUTH
 701     } else if ((p = peerUserHashSelectParent(this))) {
 702         code = USERHASH_PARENT;
 703 #endif
 704     } else if ((p = carpSelectParent(this))) {
 705         code = CARP;
 706     } else if ((p = getRoundRobinParent(this))) {
 707         code = ROUNDROBIN_PARENT;
 708     } else if ((p = getWeightedRoundRobinParent(this))) {
 709         code = ROUNDROBIN_PARENT;
 710     } else if ((p = getFirstUpParent(this))) {
 711         code = FIRSTUP_PARENT;
 712     } else if ((p = getDefaultParent(this))) {
 713         code = DEFAULT_PARENT;
 714     }
 715
 716     if (code != HIER_NONE) {
 717         addSelection(p, code);
 718     }
 719 }
 720
 721 /// Adds alive parents. Used as a last resort for never_direct.
 722 void
 723 PeerSelector::selectAllParents()
 724 {
 725     CachePeer *p;
 726     /* Add all alive parents */
 727
 728     for (p = Config.peers; p; p = p->next) {
 729         /* XXX: neighbors.c lacks a public interface for enumerating
 730          * parents to a request so we have to dig some here..
 731          */
 732
 733         if (neighborType(p, request->url) != PEER_PARENT)
 734             continue;
 735
 736         if (!peerHTTPOkay(p, this))
 737             continue;
 738
 739         addSelection(p, ANY_OLD_PARENT);
 740     }
 741
 742     /* XXX: should add dead parents here, but it is currently
 743      * not possible to find out which parents are dead or which
 744      * simply are not configured to handle the request.
 745      */
 746     /* Add default parent as a last resort */
 747     if ((p = getDefaultParent(this))) {
 748         addSelection(p, DEFAULT_PARENT);
 749     }
 750 }
 751
 752 void
 753 PeerSelector::handlePingTimeout()
 754 {
 755     debugs(44, 3, url());
 756
 757     if (entry)
 758         entry->ping_status = PING_DONE;
 759
 760     if (selectionAborted())
 761         return;
 762
 763     ++PeerStats.timeouts;
 764     ping.timedout = 1;
 765     selectMore();
 766 }
 767
 768 void
 769 PeerSelector::HandlePingTimeout(void *data)
 770 {
 771     static_cast<PeerSelector*>(data)->handlePingTimeout();
 772 }
 773
 774 void
 775 peerSelectInit(void)
 776 {
 777     memset(&PeerStats, '\0', sizeof(PeerStats));
 778 }
 779
 780 void
 781 PeerSelector::handleIcpParentMiss(CachePeer *p, icp_common_t *header)
 782 {
 783     int rtt;
 784
 785 #if USE_ICMP
 786     if (Config.onoff.query_icmp) {
 787         if (header->flags & ICP_FLAG_SRC_RTT) {
 788             rtt = header->pad & 0xFFFF;
 789             int hops = (header->pad >> 16) & 0xFFFF;
 790
 791             if (rtt > 0 && rtt < 0xFFFF)
 792                 netdbUpdatePeer(request->url, p, rtt, hops);
 793
 794             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 795                 closest_parent_miss = p->in_addr;
 796                 ping.p_rtt = rtt;
 797             }
 798         }
 799     }
 800 #endif /* USE_ICMP */
 801
 802     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 803     if (p->options.closest_only)
 804         return;
 805
 806     /* set FIRST_MISS if there is no CLOSEST parent */
 807     if (!closest_parent_miss.isAnyAddr())
 808         return;
 809
 810     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 811
 812     if (rtt < 1)
 813         rtt = 1;
 814
 815     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 816         first_parent_miss = p->in_addr;
 817         ping.w_rtt = rtt;
 818     }
 819 }
 820
 821 void
 822 PeerSelector::handleIcpReply(CachePeer *p, const peer_t type, icp_common_t *header)
 823 {
 824     icp_opcode op = header->getOpCode();
 825     debugs(44, 3, icp_opcode_str[op] << ' ' << url());
 826 #if USE_CACHE_DIGESTS && 0
 827     /* do cd lookup to count false misses */
 828
 829     if (p && request)
 830         peerNoteDigestLookup(request, p,
 831                              peerDigestLookup(p, this));
 832
 833 #endif
 834
 835     ++ping.n_recv;
 836
 837     if (op == ICP_MISS || op == ICP_DECHO) {
 838         if (type == PEER_PARENT)
 839             handleIcpParentMiss(p, header);
 840     } else if (op == ICP_HIT) {
 841         hit = p;
 842         hit_type = type;
 843         selectMore();
 844         return;
 845     }
 846
 847     if (ping.n_recv < ping.n_replies_expected)
 848         return;
 849
 850     selectMore();
 851 }
 852
 853 #if USE_HTCP
 854 void
 855 PeerSelector::handleHtcpReply(CachePeer *p, const peer_t type, HtcpReplyData *htcp)
 856 {
 857     debugs(44, 3, (htcp->hit ? "HIT" : "MISS") << ' ' << url());
 858     ++ping.n_recv;
 859
 860     if (htcp->hit) {
 861         hit = p;
 862         hit_type = type;
 863         selectMore();
 864         return;
 865     }
 866
 867     if (type == PEER_PARENT)
 868         handleHtcpParentMiss(p, htcp);
 869
 870     if (ping.n_recv < ping.n_replies_expected)
 871         return;
 872
 873     selectMore();
 874 }
 875
 876 void
 877 PeerSelector::handleHtcpParentMiss(CachePeer *p, HtcpReplyData *htcp)
 878 {
 879     int rtt;
 880
 881 #if USE_ICMP
 882     if (Config.onoff.query_icmp) {
 883         if (htcp->cto.rtt > 0) {
 884             rtt = (int) htcp->cto.rtt * 1000;
 885             int hops = (int) htcp->cto.hops * 1000;
 886             netdbUpdatePeer(request->url, p, rtt, hops);
 887
 888             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 889                 closest_parent_miss = p->in_addr;
 890                 ping.p_rtt = rtt;
 891             }
 892         }
 893     }
 894 #endif /* USE_ICMP */
 895
 896     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 897     if (p->options.closest_only)
 898         return;
 899
 900     /* set FIRST_MISS if there is no CLOSEST parent */
 901     if (!closest_parent_miss.isAnyAddr())
 902         return;
 903
 904     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 905
 906     if (rtt < 1)
 907         rtt = 1;
 908
 909     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 910         first_parent_miss = p->in_addr;
 911         ping.w_rtt = rtt;
 912     }
 913 }
 914
 915 #endif
 916
 917 void
 918 PeerSelector::HandlePingReply(CachePeer * p, peer_t type, AnyP::ProtocolType proto, void *pingdata, void *data)
 919 {
 920     if (proto == AnyP::PROTO_ICP)
 921         static_cast<PeerSelector*>(data)->handleIcpReply(p, type, static_cast<icp_common_t*>(pingdata));
 922
 923 #if USE_HTCP
 924
 925     else if (proto == AnyP::PROTO_HTCP)
 926         static_cast<PeerSelector*>(data)->handleHtcpReply(p, type, static_cast<HtcpReplyData*>(pingdata));
 927
 928 #endif
 929
 930     else
 931         debugs(44, DBG_IMPORTANT, "ERROR: ignoring an ICP reply with unknown protocol " << proto);
 932 }
 933
 934 void
 935 PeerSelector::addSelection(CachePeer *peer, const hier_code code)
 936 {
 937     // Find the end of the servers list. Bail on a duplicate destination.
 938     auto **serversTail = &servers;
 939     while (const auto server = *serversTail) {
 940         // There can be at most one PINNED destination.
 941         // Non-PINNED destinations are uniquely identified by their CachePeer
 942         // (even though a DIRECT destination might match a cache_peer address).
 943         const bool duplicate = (server->code == PINNED) ?
 944                                (code == PINNED) : (server->_peer == peer);
 945         if (duplicate) {
 946             debugs(44, 3, "skipping " << PeerSelectionDumper(this, peer, code) <<
 947                    "; have " << PeerSelectionDumper(this, server->_peer.get(), server->code));
 948             return;
 949         }
 950         serversTail = &server->next;
 951     }
 952
 953     debugs(44, 3, "adding " << PeerSelectionDumper(this, peer, code));
 954     *serversTail = new FwdServer(peer, code);
 955 }
 956
 957 PeerSelector::PeerSelector(PeerSelectionInitiator *initiator):
 958     request(nullptr),
 959     entry (NULL),
 960     always_direct(Config.accessList.AlwaysDirect?ACCESS_DUNNO:ACCESS_DENIED),
 961     never_direct(Config.accessList.NeverDirect?ACCESS_DUNNO:ACCESS_DENIED),
 962     direct(DIRECT_UNKNOWN),
 963     lastError(NULL),
 964     servers (NULL),
 965     first_parent_miss(),
 966     closest_parent_miss(),
 967     hit(NULL),
 968     hit_type(PEER_NONE),
 969     acl_checklist (NULL),
 970     initiator_(initiator)
 971 {
 972     ; // no local defaults.
 973 }
 974
 975 const SBuf
 976 PeerSelector::url() const
 977 {
 978     if (entry)
 979         return SBuf(entry->url());
 980
 981     if (request)
 982         return request->effectiveRequestUri();
 983
 984     static const SBuf noUrl("[no URL]");
 985     return noUrl;
 986 }
 987
 988 /// \returns valid/interested peer initiator or nil
 989 PeerSelectionInitiator *
 990 PeerSelector::interestedInitiator()
 991 {
 992     const auto initiator = initiator_.valid();
 993
 994     if (!initiator) {
 995         debugs(44, 3, id << " initiator gone");
 996         return nullptr;
 997     }
 998
 999     if (!initiator->subscribed) {
1000         debugs(44, 3, id << " initiator lost interest");
1001         return nullptr;
1002     }
1003
1004     debugs(44, 7, id);
1005     return initiator;
1006 }
1007
1008 bool
1009 PeerSelector::wantsMoreDestinations() const {
1010     const auto maxCount = Config.forward_max_tries;
1011     return maxCount >= 0 && foundPaths <
1012            static_cast<std::make_unsigned<decltype(maxCount)>::type>(maxCount);
1013 }
1014
1015 void
1016 PeerSelector::handlePath(const Comm::ConnectionPointer &path, FwdServer &fs)
1017 {
1018     ++foundPaths;
1019
1020     if (path) {
1021         path->peerType = fs.code;
1022         path->setPeer(fs._peer.get());
1023
1024         // check for a configured outgoing address for this destination...
1025         getOutgoingAddress(request, path);
1026         debugs(44, 2, id << " found " << path << ", destination #" << foundPaths << " for " << url());
1027     } else
1028         debugs(44, 2, id << " found pinned, destination #" << foundPaths << " for " << url());
1029
1030     request->hier.ping = ping; // may be updated later
1031
1032     debugs(44, 2, "  always_direct = " << always_direct);
1033     debugs(44, 2, "   never_direct = " << never_direct);
1034     debugs(44, 2, "       timedout = " << ping.timedout);
1035
1036     if (const auto initiator = interestedInitiator())
1037         initiator->noteDestination(path);
1038 }
1039
1040 InstanceIdDefinitions(PeerSelector, "PeerSelector");
1041
1042 ping_data::ping_data() :
1043     n_sent(0),
1044     n_recv(0),
1045     n_replies_expected(0),
1046     timeout(0),
1047     timedout(0),
1048     w_rtt(0),
1049     p_rtt(0)
1050 {
1051     start.tv_sec = 0;
1052     start.tv_usec = 0;
1053     stop.tv_sec = 0;
1054     stop.tv_usec = 0;
1055 }
1056