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