src/peer_select.cc

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