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