src/peer_select.cc

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