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