src/peer_select.cc

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