src/peer_select.cc

   1 /*
   2  * Copyright (C) 1996-2021 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 "CachePeer.h"
  16 #include "carp.h"
  17 #include "client_side.h"
  18 #include "dns/LookupDetails.h"
  19 #include "errorpage.h"
  20 #include "event.h"
  21 #include "FwdState.h"
  22 #include "globals.h"
  23 #include "hier_code.h"
  24 #include "htcp.h"
  25 #include "http/Stream.h"
  26 #include "HttpRequest.h"
  27 #include "icmp/net_db.h"
  28 #include "ICP.h"
  29 #include "ip/tools.h"
  30 #include "ipcache.h"
  31 #include "neighbors.h"
  32 #include "peer_sourcehash.h"
  33 #include "peer_userhash.h"
  34 #include "PeerSelectState.h"
  35 #include "SquidConfig.h"
  36 #include "SquidTime.h"
  37 #include "Store.h"
  38 #include "util.h" // for tvSubDsec() which should be in SquidTime.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->host;
  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, "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 = NULL;
 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     p->remote.port(peer ? peer->http_port : request->url.port());
 534     handlePath(p, *servers);
 535 }
 536
 537 void
 538 PeerSelector::noteIps(const Dns::CachedIps *ia, const Dns::LookupDetails &details)
 539 {
 540     if (selectionAborted())
 541         return;
 542
 543     FwdServer *fs = servers;
 544     if (!ia) {
 545         debugs(44, 3, "Unknown host: " << (fs->_peer.valid() ? fs->_peer->host : request->url.host()));
 546         // discard any previous error.
 547         delete lastError;
 548         lastError = NULL;
 549         if (fs->code == HIER_DIRECT) {
 550             lastError = new ErrorState(ERR_DNS_FAIL, Http::scServiceUnavailable, request, al);
 551             lastError->dnsError = details.error;
 552         }
 553     }
 554     // else noteIp() calls have already processed all IPs in *ia
 555
 556     servers = fs->next;
 557     delete fs;
 558
 559     // continue resolving selected peers
 560     resolveSelected();
 561 }
 562
 563 int
 564 PeerSelector::checkNetdbDirect()
 565 {
 566 #if USE_ICMP
 567     CachePeer *p;
 568     int myrtt;
 569     int myhops;
 570
 571     if (direct == DIRECT_NO)
 572         return 0;
 573
 574     /* base lookup on RTT and Hops if ICMP NetDB is enabled. */
 575
 576     myrtt = netdbHostRtt(request->url.host());
 577     debugs(44, 3, "MY RTT = " << myrtt << " msec");
 578     debugs(44, 3, "minimum_direct_rtt = " << Config.minDirectRtt << " msec");
 579
 580     if (myrtt && myrtt <= Config.minDirectRtt)
 581         return 1;
 582
 583     myhops = netdbHostHops(request->url.host());
 584
 585     debugs(44, 3, "MY hops = " << myhops);
 586     debugs(44, 3, "minimum_direct_hops = " << Config.minDirectHops);
 587
 588     if (myhops && myhops <= Config.minDirectHops)
 589         return 1;
 590
 591     p = whichPeer(closest_parent_miss);
 592
 593     if (p == NULL)
 594         return 0;
 595
 596     debugs(44, 3, "closest_parent_miss RTT = " << ping.p_rtt << " msec");
 597
 598     if (myrtt && myrtt <= ping.p_rtt)
 599         return 1;
 600
 601 #endif /* USE_ICMP */
 602
 603     return 0;
 604 }
 605
 606 void
 607 PeerSelector::selectMore()
 608 {
 609     if (selectionAborted())
 610         return;
 611
 612     debugs(44, 3, request->method << ' ' << request->url.host());
 613
 614     /** If we don't know whether DIRECT is permitted ... */
 615     if (direct == DIRECT_UNKNOWN) {
 616         if (always_direct == ACCESS_DUNNO) {
 617             debugs(44, 3, "direct = " << DirectStr[direct] << " (always_direct to be checked)");
 618             /** check always_direct; */
 619             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.AlwaysDirect, request, NULL);
 620             ch->al = al;
 621             acl_checklist = ch;
 622             acl_checklist->syncAle(request, nullptr);
 623             acl_checklist->nonBlockingCheck(CheckAlwaysDirectDone, this);
 624             return;
 625         } else if (never_direct == ACCESS_DUNNO) {
 626             debugs(44, 3, "direct = " << DirectStr[direct] << " (never_direct to be checked)");
 627             /** check never_direct; */
 628             ACLFilledChecklist *ch = new ACLFilledChecklist(Config.accessList.NeverDirect, request, NULL);
 629             ch->al = al;
 630             acl_checklist = ch;
 631             acl_checklist->syncAle(request, nullptr);
 632             acl_checklist->nonBlockingCheck(CheckNeverDirectDone, this);
 633             return;
 634         } else if (request->flags.noDirect) {
 635             /** if we are accelerating, direct is not an option. */
 636             direct = DIRECT_NO;
 637             debugs(44, 3, "direct = " << DirectStr[direct] << " (forced non-direct)");
 638         } else if (request->flags.loopDetected) {
 639             /** if we are in a forwarding-loop, direct is not an option. */
 640             direct = DIRECT_YES;
 641             debugs(44, 3, "direct = " << DirectStr[direct] << " (forwarding loop detected)");
 642         } else if (checkNetdbDirect()) {
 643             direct = DIRECT_YES;
 644             debugs(44, 3, "direct = " << DirectStr[direct] << " (checkNetdbDirect)");
 645         } else {
 646             direct = DIRECT_MAYBE;
 647             debugs(44, 3, "direct = " << DirectStr[direct] << " (default)");
 648         }
 649
 650         debugs(44, 3, "direct = " << DirectStr[direct]);
 651     }
 652
 653     if (!entry || entry->ping_status == PING_NONE)
 654         selectPinned();
 655     if (entry == NULL) {
 656         (void) 0;
 657     } else if (entry->ping_status == PING_NONE) {
 658         selectSomeNeighbor();
 659
 660         if (entry->ping_status == PING_WAITING)
 661             return;
 662     } else if (entry->ping_status == PING_WAITING) {
 663         selectSomeNeighborReplies();
 664         cancelPingTimeoutMonitoring();
 665         entry->ping_status = PING_DONE;
 666     }
 667
 668     switch (direct) {
 669
 670     case DIRECT_YES:
 671         selectSomeDirect();
 672         break;
 673
 674     case DIRECT_NO:
 675         selectSomeParent();
 676         selectAllParents();
 677         break;
 678
 679     default:
 680
 681         if (Config.onoff.prefer_direct)
 682             selectSomeDirect();
 683
 684         if (request->flags.hierarchical || !Config.onoff.nonhierarchical_direct) {
 685             selectSomeParent();
 686             selectAllParents();
 687         }
 688
 689         if (!Config.onoff.prefer_direct)
 690             selectSomeDirect();
 691
 692         break;
 693     }
 694
 695     // end peer selection; start resolving selected peers
 696     resolveSelected();
 697 }
 698
 699 bool peerAllowedToUse(const CachePeer *, PeerSelector*);
 700
 701 /// Selects a pinned connection if it exists, is valid, and is allowed.
 702 void
 703 PeerSelector::selectPinned()
 704 {
 705     // TODO: Avoid all repeated calls. Relying on PING_DONE is not enough.
 706     if (!request->pinnedConnection())
 707         return;
 708
 709     const auto peer = request->pinnedConnection()->pinnedPeer();
 710     const auto usePinned = peer ? peerAllowedToUse(peer, this) : (direct != DIRECT_NO);
 711     // If the pinned connection is prohibited (for this request) then
 712     // the initiator must decide whether it is OK to open a new one instead.
 713     request->pinnedConnection()->pinning.peerAccessDenied = !usePinned;
 714
 715     addSelection(peer, PINNED);
 716     if (entry)
 717         entry->ping_status = PING_DONE; // skip ICP
 718 }
 719
 720 /**
 721  * Selects a neighbor (parent or sibling) based on one of the
 722  * following methods:
 723  *      Cache Digests
 724  *      CARP
 725  *      ICMP Netdb RTT estimates
 726  *      ICP/HTCP queries
 727  */
 728 void
 729 PeerSelector::selectSomeNeighbor()
 730 {
 731     CachePeer *p;
 732     hier_code code = HIER_NONE;
 733     assert(entry->ping_status == PING_NONE);
 734
 735     if (direct == DIRECT_YES) {
 736         entry->ping_status = PING_DONE;
 737         return;
 738     }
 739
 740 #if USE_CACHE_DIGESTS
 741     if ((p = neighborsDigestSelect(this))) {
 742         if (neighborType(p, request->url) == PEER_PARENT)
 743             code = CD_PARENT_HIT;
 744         else
 745             code = CD_SIBLING_HIT;
 746     } else
 747 #endif
 748         if ((p = netdbClosestParent(this))) {
 749             code = CLOSEST_PARENT;
 750         } else if (peerSelectIcpPing(this, direct, entry)) {
 751             debugs(44, 3, "Doing ICP pings");
 752             ping.start = current_time;
 753             ping.n_sent = neighborsUdpPing(request,
 754                                            entry,
 755                                            HandlePingReply,
 756                                            this,
 757                                            &ping.n_replies_expected,
 758                                            &ping.timeout);
 759             // TODO: Refactor neighborsUdpPing() to guarantee positive timeouts.
 760             if (ping.timeout < 0)
 761                 ping.timeout = 0;
 762
 763             if (ping.n_sent == 0)
 764                 debugs(44, DBG_CRITICAL, "WARNING: neighborsUdpPing returned 0");
 765             debugs(44, 3, ping.n_replies_expected <<
 766                    " ICP replies expected, RTT " << ping.timeout <<
 767                    " msec");
 768
 769             if (ping.n_replies_expected > 0) {
 770                 startPingWaiting();
 771                 return;
 772             }
 773         }
 774
 775     if (code != HIER_NONE) {
 776         assert(p);
 777         addSelection(p, code);
 778     }
 779
 780     entry->ping_status = PING_DONE;
 781 }
 782
 783 /// Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 784 void
 785 PeerSelector::selectSomeNeighborReplies()
 786 {
 787     CachePeer *p = NULL;
 788     hier_code code = HIER_NONE;
 789     assert(entry->ping_status == PING_WAITING);
 790     assert(direct != DIRECT_YES);
 791
 792     if (checkNetdbDirect()) {
 793         code = CLOSEST_DIRECT;
 794         addSelection(nullptr, code);
 795         return;
 796     }
 797
 798     if ((p = hit)) {
 799         code = hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 800     } else {
 801         if (!closest_parent_miss.isAnyAddr()) {
 802             p = whichPeer(closest_parent_miss);
 803             code = CLOSEST_PARENT_MISS;
 804         } else if (!first_parent_miss.isAnyAddr()) {
 805             p = whichPeer(first_parent_miss);
 806             code = FIRST_PARENT_MISS;
 807         }
 808     }
 809     if (p && code != HIER_NONE) {
 810         addSelection(p, code);
 811     }
 812 }
 813
 814 /// Adds a "direct" entry if the request can be forwarded to the origin server.
 815 void
 816 PeerSelector::selectSomeDirect()
 817 {
 818     if (direct == DIRECT_NO)
 819         return;
 820
 821     /* WAIS is not implemented natively */
 822     if (request->url.getScheme() == AnyP::PROTO_WAIS)
 823         return;
 824
 825     addSelection(nullptr, HIER_DIRECT);
 826 }
 827
 828 void
 829 PeerSelector::selectSomeParent()
 830 {
 831     CachePeer *p;
 832     hier_code code = HIER_NONE;
 833     debugs(44, 3, request->method << ' ' << request->url.host());
 834
 835     if (direct == DIRECT_YES)
 836         return;
 837
 838     if ((p = peerSourceHashSelectParent(this))) {
 839         code = SOURCEHASH_PARENT;
 840 #if USE_AUTH
 841     } else if ((p = peerUserHashSelectParent(this))) {
 842         code = USERHASH_PARENT;
 843 #endif
 844     } else if ((p = carpSelectParent(this))) {
 845         code = CARP;
 846     } else if ((p = getRoundRobinParent(this))) {
 847         code = ROUNDROBIN_PARENT;
 848     } else if ((p = getWeightedRoundRobinParent(this))) {
 849         code = ROUNDROBIN_PARENT;
 850     } else if ((p = getFirstUpParent(this))) {
 851         code = FIRSTUP_PARENT;
 852     } else if ((p = getDefaultParent(this))) {
 853         code = DEFAULT_PARENT;
 854     }
 855
 856     if (code != HIER_NONE) {
 857         addSelection(p, code);
 858     }
 859 }
 860
 861 /// Adds alive parents. Used as a last resort for never_direct.
 862 void
 863 PeerSelector::selectAllParents()
 864 {
 865     CachePeer *p;
 866     /* Add all alive parents */
 867
 868     for (p = Config.peers; p; p = p->next) {
 869         /* XXX: neighbors.c lacks a public interface for enumerating
 870          * parents to a request so we have to dig some here..
 871          */
 872
 873         if (neighborType(p, request->url) != PEER_PARENT)
 874             continue;
 875
 876         if (!peerHTTPOkay(p, this))
 877             continue;
 878
 879         addSelection(p, ANY_OLD_PARENT);
 880     }
 881
 882     /* XXX: should add dead parents here, but it is currently
 883      * not possible to find out which parents are dead or which
 884      * simply are not configured to handle the request.
 885      */
 886     /* Add default parent as a last resort */
 887     if ((p = getDefaultParent(this))) {
 888         addSelection(p, DEFAULT_PARENT);
 889     }
 890 }
 891
 892 void
 893 PeerSelector::handlePingTimeout()
 894 {
 895     debugs(44, 3, url());
 896
 897     // do nothing if ping reply came while handlePingTimeout() was queued
 898     if (!entry || entry->ping_status != PING_WAITING)
 899         return;
 900
 901     entry->ping_status = PING_DONE;
 902
 903     if (selectionAborted())
 904         return;
 905
 906     ++PeerStats.timeouts;
 907     ping.timedout = 1;
 908     selectMore();
 909 }
 910
 911 void
 912 PeerSelector::HandlePingTimeout(PeerSelector *selector)
 913 {
 914     selector->handlePingTimeout();
 915 }
 916
 917 void
 918 peerSelectInit(void)
 919 {
 920     memset(&PeerStats, '\0', sizeof(PeerStats));
 921 }
 922
 923 void
 924 PeerSelector::handleIcpParentMiss(CachePeer *p, icp_common_t *header)
 925 {
 926     int rtt;
 927
 928 #if USE_ICMP
 929     if (Config.onoff.query_icmp) {
 930         if (header->flags & ICP_FLAG_SRC_RTT) {
 931             rtt = header->pad & 0xFFFF;
 932             int hops = (header->pad >> 16) & 0xFFFF;
 933
 934             if (rtt > 0 && rtt < 0xFFFF)
 935                 netdbUpdatePeer(request->url, p, rtt, hops);
 936
 937             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
 938                 closest_parent_miss = p->in_addr;
 939                 ping.p_rtt = rtt;
 940             }
 941         }
 942     }
 943 #endif /* USE_ICMP */
 944
 945     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 946     if (p->options.closest_only)
 947         return;
 948
 949     /* set FIRST_MISS if there is no CLOSEST parent */
 950     if (!closest_parent_miss.isAnyAddr())
 951         return;
 952
 953     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
 954
 955     if (rtt < 1)
 956         rtt = 1;
 957
 958     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
 959         first_parent_miss = p->in_addr;
 960         ping.w_rtt = rtt;
 961     }
 962 }
 963
 964 void
 965 PeerSelector::handleIcpReply(CachePeer *p, const peer_t type, icp_common_t *header)
 966 {
 967     icp_opcode op = header->getOpCode();
 968     debugs(44, 3, icp_opcode_str[op] << ' ' << url());
 969 #if USE_CACHE_DIGESTS && 0
 970     /* do cd lookup to count false misses */
 971
 972     if (p && request)
 973         peerNoteDigestLookup(request, p,
 974                              peerDigestLookup(p, this));
 975
 976 #endif
 977
 978     ++ping.n_recv;
 979
 980     if (op == ICP_MISS || op == ICP_DECHO) {
 981         if (type == PEER_PARENT)
 982             handleIcpParentMiss(p, header);
 983     } else if (op == ICP_HIT) {
 984         hit = p;
 985         hit_type = type;
 986         selectMore();
 987         return;
 988     }
 989
 990     if (ping.n_recv < ping.n_replies_expected)
 991         return;
 992
 993     selectMore();
 994 }
 995
 996 #if USE_HTCP
 997 void
 998 PeerSelector::handleHtcpReply(CachePeer *p, const peer_t type, HtcpReplyData *htcp)
 999 {
1000     debugs(44, 3, (htcp->hit ? "HIT" : "MISS") << ' ' << url());
1001     ++ping.n_recv;
1002
1003     if (htcp->hit) {
1004         hit = p;
1005         hit_type = type;
1006         selectMore();
1007         return;
1008     }
1009
1010     if (type == PEER_PARENT)
1011         handleHtcpParentMiss(p, htcp);
1012
1013     if (ping.n_recv < ping.n_replies_expected)
1014         return;
1015
1016     selectMore();
1017 }
1018
1019 void
1020 PeerSelector::handleHtcpParentMiss(CachePeer *p, HtcpReplyData *htcp)
1021 {
1022     int rtt;
1023
1024 #if USE_ICMP
1025     if (Config.onoff.query_icmp) {
1026         if (htcp->cto.rtt > 0) {
1027             rtt = (int) htcp->cto.rtt * 1000;
1028             int hops = (int) htcp->cto.hops * 1000;
1029             netdbUpdatePeer(request->url, p, rtt, hops);
1030
1031             if (rtt && (ping.p_rtt == 0 || rtt < ping.p_rtt)) {
1032                 closest_parent_miss = p->in_addr;
1033                 ping.p_rtt = rtt;
1034             }
1035         }
1036     }
1037 #endif /* USE_ICMP */
1038
1039     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
1040     if (p->options.closest_only)
1041         return;
1042
1043     /* set FIRST_MISS if there is no CLOSEST parent */
1044     if (!closest_parent_miss.isAnyAddr())
1045         return;
1046
1047     rtt = (tvSubMsec(ping.start, current_time) - p->basetime) / p->weight;
1048
1049     if (rtt < 1)
1050         rtt = 1;
1051
1052     if (first_parent_miss.isAnyAddr() || rtt < ping.w_rtt) {
1053         first_parent_miss = p->in_addr;
1054         ping.w_rtt = rtt;
1055     }
1056 }
1057
1058 #endif
1059
1060 void
1061 PeerSelector::HandlePingReply(CachePeer * p, peer_t type, AnyP::ProtocolType proto, void *pingdata, void *data)
1062 {
1063     if (proto == AnyP::PROTO_ICP)
1064         static_cast<PeerSelector*>(data)->handleIcpReply(p, type, static_cast<icp_common_t*>(pingdata));
1065
1066 #if USE_HTCP
1067
1068     else if (proto == AnyP::PROTO_HTCP)
1069         static_cast<PeerSelector*>(data)->handleHtcpReply(p, type, static_cast<HtcpReplyData*>(pingdata));
1070
1071 #endif
1072
1073     else
1074         debugs(44, DBG_IMPORTANT, "ERROR: ignoring an ICP reply with unknown protocol " << proto);
1075 }
1076
1077 void
1078 PeerSelector::addSelection(CachePeer *peer, const hier_code code)
1079 {
1080     // Find the end of the servers list. Bail on a duplicate destination.
1081     auto **serversTail = &servers;
1082     while (const auto server = *serversTail) {
1083         // There can be at most one PINNED destination.
1084         // Non-PINNED destinations are uniquely identified by their CachePeer
1085         // (even though a DIRECT destination might match a cache_peer address).
1086         // TODO: We may still add duplicates because the same peer could have
1087         // been removed from `servers` already (and given to the requestor).
1088         const bool duplicate = (server->code == PINNED) ?
1089                                (code == PINNED) : (server->_peer == peer);
1090         if (duplicate) {
1091             debugs(44, 3, "skipping " << PeerSelectionDumper(this, peer, code) <<
1092                    "; have " << PeerSelectionDumper(this, server->_peer.get(), server->code));
1093             return;
1094         }
1095         serversTail = &server->next;
1096     }
1097
1098     debugs(44, 3, "adding " << PeerSelectionDumper(this, peer, code));
1099     *serversTail = new FwdServer(peer, code);
1100 }
1101
1102 PeerSelector::PeerSelector(PeerSelectionInitiator *initiator):
1103     request(nullptr),
1104     entry (NULL),
1105     always_direct(Config.accessList.AlwaysDirect?ACCESS_DUNNO:ACCESS_DENIED),
1106     never_direct(Config.accessList.NeverDirect?ACCESS_DUNNO:ACCESS_DENIED),
1107     direct(DIRECT_UNKNOWN),
1108     lastError(NULL),
1109     servers (NULL),
1110     first_parent_miss(),
1111     closest_parent_miss(),
1112     hit(NULL),
1113     hit_type(PEER_NONE),
1114     acl_checklist (NULL),
1115     initiator_(initiator)
1116 {
1117     ; // no local defaults.
1118 }
1119
1120 const SBuf
1121 PeerSelector::url() const
1122 {
1123     if (entry)
1124         return SBuf(entry->url());
1125
1126     if (request)
1127         return request->effectiveRequestUri();
1128
1129     static const SBuf noUrl("[no URL]");
1130     return noUrl;
1131 }
1132
1133 /// \returns valid/interested peer initiator or nil
1134 PeerSelectionInitiator *
1135 PeerSelector::interestedInitiator()
1136 {
1137     const auto initiator = initiator_.valid();
1138
1139     if (!initiator) {
1140         debugs(44, 3, id << " initiator gone");
1141         return nullptr;
1142     }
1143
1144     if (!initiator->subscribed) {
1145         debugs(44, 3, id << " initiator lost interest");
1146         return nullptr;
1147     }
1148
1149     debugs(44, 7, id);
1150     return initiator;
1151 }
1152
1153 bool
1154 PeerSelector::wantsMoreDestinations() const {
1155     const auto maxCount = Config.forward_max_tries;
1156     return maxCount >= 0 && foundPaths <
1157            static_cast<std::make_unsigned<decltype(maxCount)>::type>(maxCount);
1158 }
1159
1160 void
1161 PeerSelector::handlePath(const Comm::ConnectionPointer &path, FwdServer &fs)
1162 {
1163     ++foundPaths;
1164
1165     if (path) {
1166         path->peerType = fs.code;
1167         path->setPeer(fs._peer.get());
1168
1169         // check for a configured outgoing address for this destination...
1170         getOutgoingAddress(request, path);
1171         debugs(44, 2, id << " found " << path << ", destination #" << foundPaths << " for " << url());
1172     } else
1173         debugs(44, 2, id << " found pinned, destination #" << foundPaths << " for " << url());
1174
1175     request->hier.ping = ping; // may be updated later
1176
1177     debugs(44, 2, "  always_direct = " << always_direct);
1178     debugs(44, 2, "   never_direct = " << never_direct);
1179     debugs(44, 2, "       timedout = " << ping.timedout);
1180
1181     if (const auto initiator = interestedInitiator())
1182         initiator->noteDestination(path);
1183 }
1184
1185 InstanceIdDefinitions(PeerSelector, "PeerSelector");
1186
1187 ping_data::ping_data() :
1188     n_sent(0),
1189     n_recv(0),
1190     n_replies_expected(0),
1191     timeout(0),
1192     timedout(0),
1193     w_rtt(0),
1194     p_rtt(0),
1195     monitorRegistration(PingMonitor().npos())
1196 {
1197     start.tv_sec = 0;
1198     start.tv_usec = 0;
1199     stop.tv_sec = 0;
1200     stop.tv_usec = 0;
1201 }
1202
1203 timeval
1204 ping_data::deadline() const
1205 {
1206     timeval timeInterval;
1207     timeInterval.tv_sec = timeout / 1000;
1208     timeInterval.tv_usec = (timeout % 1000) * 1000;
1209
1210     timeval result;
1211     tvAdd(result, start, timeInterval);
1212     return result;
1213 }
1214