src/peer_select.cc

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