src/peer_select.cc

   1
   2 /*
   3  * $Id: peer_select.cc,v 1.103 2000/01/03 19:32:33 wessels Exp $
   4  *
   5  * DEBUG: section 44    Peer Selection Algorithm
   6  * AUTHOR: Duane Wessels
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  Duane Wessels and the University of California San Diego.  Please
  16  *  see the COPYRIGHT file for full details.  Squid incorporates
  17  *  software developed and/or copyrighted by other sources.  Please see
  18  *  the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37
  38 const char *hier_strings[] =
  39 {
  40     "NONE",
  41     "DIRECT",
  42     "SIBLING_HIT",
  43     "PARENT_HIT",
  44     "DEFAULT_PARENT",
  45     "SINGLE_PARENT",
  46     "FIRST_UP_PARENT",
  47     "FIRST_PARENT_MISS",
  48     "CLOSEST_PARENT_MISS",
  49     "CLOSEST_PARENT",
  50     "CLOSEST_DIRECT",
  51     "NO_DIRECT_FAIL",
  52     "SOURCE_FASTEST",
  53     "ROUNDROBIN_PARENT",
  54 #if USE_CACHE_DIGESTS
  55     "CD_PARENT_HIT",
  56     "CD_SIBLING_HIT",
  57 #endif
  58 #if USE_CARP
  59     "CARP",
  60 #endif
  61     "ANY_PARENT",
  62     "INVALID CODE"
  63 };
  64
  65 static struct {
  66     int timeouts;
  67 } PeerStats;
  68
  69 static char *DirectStr[] =
  70 {
  71     "DIRECT_UNKNOWN",
  72     "DIRECT_NO",
  73     "DIRECT_MAYBE",
  74     "DIRECT_YES"
  75 };
  76
  77 static void peerSelectFoo(ps_state *);
  78 static void peerPingTimeout(void *data);
  79 static void peerSelectCallback(ps_state * psstate);
  80 static IRCB peerHandlePingReply;
  81 static void peerSelectStateFree(ps_state * psstate);
  82 static void peerIcpParentMiss(peer *, icp_common_t *, ps_state *);
  83 #if USE_HTCP
  84 static void peerHtcpParentMiss(peer *, htcpReplyData *, ps_state *);
  85 static void peerHandleHtcpReply(peer *, peer_t, htcpReplyData *, void *);
  86 #endif
  87 static int peerCheckNetdbDirect(ps_state * psstate);
  88 static void peerGetSomeNeighbor(ps_state *);
  89 static void peerGetSomeNeighborReplies(ps_state *);
  90 static void peerGetSomeDirect(ps_state *);
  91 static void peerGetSomeParent(ps_state *);
  92 static void peerAddFwdServer(FwdServer **, peer *, hier_code);
  93
  94 static void
  95 peerSelectStateFree(ps_state * psstate)
  96 {
  97     if (psstate->acl_checklist) {
  98         debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
  99         aclChecklistFree(psstate->acl_checklist);
 100     }
 101     requestUnlink(psstate->request);
 102     psstate->request = NULL;
 103     if (psstate->entry) {
 104         assert(psstate->entry->ping_status != PING_WAITING);
 105         storeUnlockObject(psstate->entry);
 106         psstate->entry = NULL;
 107     }
 108     cbdataFree(psstate);
 109 }
 110
 111 int
 112 peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
 113 {
 114     int n;
 115     assert(entry);
 116     assert(entry->ping_status == PING_NONE);
 117     assert(direct != DIRECT_YES);
 118     debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
 119     if (!request->flags.hierarchical && direct != DIRECT_NO)
 120         return 0;
 121     if (EBIT_TEST(entry->flags, KEY_PRIVATE) && !neighbors_do_private_keys)
 122         if (direct != DIRECT_NO)
 123             return 0;
 124     n = neighborsCount(request);
 125     debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
 126     return n;
 127 }
 128
 129
 130 void
 131 peerSelect(request_t * request,
 132     StoreEntry * entry,
 133     PSC * callback,
 134     void *callback_data)
 135 {
 136     ps_state *psstate = xcalloc(1, sizeof(ps_state));
 137     if (entry)
 138         debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
 139     else
 140         debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
 141     cbdataAdd(psstate, cbdataXfree, 0);
 142     psstate->request = requestLink(request);
 143     psstate->entry = entry;
 144     psstate->callback = callback;
 145     psstate->callback_data = callback_data;
 146     psstate->direct = DIRECT_UNKNOWN;
 147 #if USE_CACHE_DIGESTS
 148     request->hier.peer_select_start = current_time;
 149 #endif
 150     if (psstate->entry)
 151         storeLockObject(psstate->entry);
 152     cbdataLock(callback_data);
 153     peerSelectFoo(psstate);
 154 }
 155
 156 static void
 157 peerCheckNeverDirectDone(int answer, void *data)
 158 {
 159     ps_state *psstate = data;
 160     psstate->acl_checklist = NULL;
 161     debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
 162     psstate->never_direct = answer ? 1 : -1;
 163     peerSelectFoo(psstate);
 164 }
 165
 166 static void
 167 peerCheckAlwaysDirectDone(int answer, void *data)
 168 {
 169     ps_state *psstate = data;
 170     psstate->acl_checklist = NULL;
 171     debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
 172     psstate->always_direct = answer ? 1 : -1;
 173     peerSelectFoo(psstate);
 174 }
 175
 176 static void
 177 peerSelectCallback(ps_state * psstate)
 178 {
 179     StoreEntry *entry = psstate->entry;
 180     FwdServer *fs = psstate->servers;
 181     void *data = psstate->callback_data;
 182     if (entry) {
 183         debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
 184         if (entry->ping_status == PING_WAITING)
 185             eventDelete(peerPingTimeout, psstate);
 186         entry->ping_status = PING_DONE;
 187     }
 188     if (fs == NULL) {
 189         debug(44, 1) ("Failed to select source for '%s'\n", storeUrl(entry));
 190         debug(44, 1) ("  always_direct = %d\n", psstate->always_direct);
 191         debug(44, 1) ("   never_direct = %d\n", psstate->never_direct);
 192         debug(44, 1) ("       timedout = %d\n", psstate->ping.timedout);
 193     }
 194     psstate->ping.stop = current_time;
 195     psstate->request->hier.ping = psstate->ping;
 196     if (cbdataValid(data)) {
 197         psstate->servers = NULL;
 198         psstate->callback(fs, data);
 199     }
 200     cbdataUnlock(data);
 201     peerSelectStateFree(psstate);
 202 }
 203
 204 static int
 205 peerCheckNetdbDirect(ps_state * psstate)
 206 {
 207     peer *p = whichPeer(&psstate->closest_parent_miss);
 208     int myrtt;
 209     int myhops;
 210     if (p == NULL)
 211         return 0;
 212     myrtt = netdbHostRtt(psstate->request->host);
 213     debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d msec\n", myrtt);
 214     debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d msec\n",
 215         psstate->ping.p_rtt);
 216     if (myrtt && myrtt < psstate->ping.p_rtt)
 217         return 1;
 218     myhops = netdbHostHops(psstate->request->host);
 219     debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
 220     debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
 221         Config.minDirectHops);
 222     if (myhops && myhops <= Config.minDirectHops)
 223         return 1;
 224     return 0;
 225 }
 226
 227 static void
 228 peerSelectFoo(ps_state * ps)
 229 {
 230     StoreEntry *entry = ps->entry;
 231     request_t *request = ps->request;
 232     debug(44, 3) ("peerSelectFoo: '%s %s'\n",
 233         RequestMethodStr[request->method],
 234         request->host);
 235     if (ps->direct == DIRECT_UNKNOWN) {
 236         if (ps->always_direct == 0 && Config.accessList.AlwaysDirect) {
 237             ps->acl_checklist = aclChecklistCreate(
 238                 Config.accessList.AlwaysDirect,
 239                 request,
 240                 NULL,           /* user agent */
 241                 NULL);          /* ident */
 242             aclNBCheck(ps->acl_checklist,
 243                 peerCheckAlwaysDirectDone,
 244                 ps);
 245             return;
 246         } else if (ps->always_direct > 0) {
 247             ps->direct = DIRECT_YES;
 248         } else if (ps->never_direct == 0 && Config.accessList.NeverDirect) {
 249             ps->acl_checklist = aclChecklistCreate(
 250                 Config.accessList.NeverDirect,
 251                 request,
 252                 NULL,           /* user agent */
 253                 NULL);          /* ident */
 254             aclNBCheck(ps->acl_checklist,
 255                 peerCheckNeverDirectDone,
 256                 ps);
 257             return;
 258         } else if (ps->never_direct > 0) {
 259             ps->direct = DIRECT_NO;
 260         } else if (request->flags.loopdetect) {
 261             ps->direct = DIRECT_YES;
 262         } else {
 263             ps->direct = DIRECT_MAYBE;
 264         }
 265         debug(44, 3) ("peerSelectFoo: direct = %s\n",
 266             DirectStr[ps->direct]);
 267     }
 268     if (entry == NULL) {
 269         (void) 0;
 270     } else if (entry->ping_status == PING_NONE) {
 271         peerGetSomeNeighbor(ps);
 272         if (entry->ping_status == PING_WAITING)
 273             return;
 274     } else if (entry->ping_status == PING_WAITING) {
 275         peerGetSomeNeighborReplies(ps);
 276         entry->ping_status = PING_DONE;
 277     }
 278     if (Config.onoff.prefer_direct)
 279         peerGetSomeDirect(ps);
 280     peerGetSomeParent(ps);
 281     if (!Config.onoff.prefer_direct)
 282         peerGetSomeDirect(ps);
 283     peerSelectCallback(ps);
 284 }
 285
 286 /*
 287  * peerGetSomeNeighbor
 288  *
 289  * Selects a neighbor (parent or sibling) based on one of the
 290  * following methods:
 291  *      Cache Digests
 292  *      CARP
 293  *      Netdb RTT estimates
 294  *      ICP/HTCP queries
 295  */
 296 static void
 297 peerGetSomeNeighbor(ps_state * ps)
 298 {
 299     StoreEntry *entry = ps->entry;
 300     request_t *request = ps->request;
 301     peer *p;
 302     hier_code code = HIER_NONE;
 303     assert(entry->ping_status == PING_NONE);
 304     if (ps->direct == DIRECT_YES) {
 305         entry->ping_status = PING_DONE;
 306         return;
 307     }
 308 #if USE_CACHE_DIGESTS
 309     if ((p = neighborsDigestSelect(request, entry))) {
 310         if (neighborType(p, request) == PEER_PARENT)
 311             code = CD_PARENT_HIT;
 312         else
 313             code = CD_SIBLING_HIT;
 314     } else
 315 #endif
 316 #if USE_CARP
 317     if ((p = carpSelectParent(request))) {
 318         code = CARP;
 319     } else
 320 #endif
 321     if ((p = netdbClosestParent(request))) {
 322         code = CLOSEST_PARENT;
 323     } else if (peerSelectIcpPing(request, ps->direct, entry)) {
 324         debug(44, 3) ("peerSelect: Doing ICP pings\n");
 325         ps->ping.start = current_time;
 326         ps->ping.n_sent = neighborsUdpPing(request,
 327             entry,
 328             peerHandlePingReply,
 329             ps,
 330             &ps->ping.n_replies_expected,
 331             &ps->ping.timeout);
 332         if (ps->ping.n_sent == 0)
 333             debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
 334         debug(44, 3) ("peerSelect: %d ICP replies expected, RTT %d msec\n",
 335             ps->ping.n_replies_expected, ps->ping.timeout);
 336         if (ps->ping.n_replies_expected > 0) {
 337             entry->ping_status = PING_WAITING;
 338             eventAdd("peerPingTimeout",
 339                 peerPingTimeout,
 340                 ps,
 341                 0.001 * ps->ping.timeout,
 342                 0);
 343             return;
 344         }
 345     }
 346     if (code != HIER_NONE) {
 347         assert(p);
 348         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 349         peerAddFwdServer(&ps->servers, p, code);
 350     }
 351     entry->ping_status = PING_DONE;
 352 }
 353
 354 /*
 355  * peerGetSomeNeighborReplies
 356  *
 357  * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 358  */
 359 static void
 360 peerGetSomeNeighborReplies(ps_state * ps)
 361 {
 362     request_t *request = ps->request;
 363     peer *p = NULL;
 364     hier_code code = HIER_NONE;
 365     assert(ps->entry->ping_status == PING_WAITING);
 366     assert(ps->direct != DIRECT_YES);
 367     if (peerCheckNetdbDirect(ps)) {
 368         code = CLOSEST_DIRECT;
 369         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
 370         peerAddFwdServer(&ps->servers, NULL, code);
 371         return;
 372     }
 373     if ((p = ps->hit)) {
 374         code = ps->hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 375     } else
 376 #if ALLOW_SOURCE_PING
 377     if ((p = ps->secho)) {
 378         code = SOURCE_FASTEST;
 379     } else
 380 #endif
 381     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
 382         p = whichPeer(&ps->closest_parent_miss);
 383         code = CLOSEST_PARENT_MISS;
 384     } else if (ps->first_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
 385         p = whichPeer(&ps->first_parent_miss);
 386         code = FIRST_PARENT_MISS;
 387     }
 388     if (p && code != HIER_NONE) {
 389         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 390         peerAddFwdServer(&ps->servers, p, code);
 391     }
 392 }
 393
 394
 395 /*
 396  * peerGetSomeDirect
 397  *
 398  * Simply adds a 'direct' entry to the FwdServers list if this
 399  * request can be forwarded directly to the origin server
 400  */
 401 static void
 402 peerGetSomeDirect(ps_state * ps)
 403 {
 404     if (ps->direct == DIRECT_NO)
 405         return;
 406     if (ps->request->protocol == PROTO_WAIS)
 407         /* Its not really DIRECT, now is it? */
 408         peerAddFwdServer(&ps->servers, Config.Wais.peer, DIRECT);
 409     else
 410         peerAddFwdServer(&ps->servers, NULL, DIRECT);
 411 }
 412
 413 static void
 414 peerGetSomeParent(ps_state * ps)
 415 {
 416     peer *p;
 417     request_t *request = ps->request;
 418     hier_code code = HIER_NONE;
 419     debug(44, 3) ("peerGetSomeParent: %s %s\n",
 420         RequestMethodStr[request->method],
 421         request->host);
 422     if (ps->direct == DIRECT_YES)
 423         return;
 424     if ((p = getDefaultParent(request))) {
 425         code = DEFAULT_PARENT;
 426     } else if ((p = getRoundRobinParent(request))) {
 427         code = ROUNDROBIN_PARENT;
 428     } else if ((p = getFirstUpParent(request))) {
 429         code = FIRSTUP_PARENT;
 430     } else if ((p = getAnyParent(request))) {
 431         code = ANY_OLD_PARENT;
 432     }
 433     if (code != HIER_NONE) {
 434         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 435         peerAddFwdServer(&ps->servers, p, code);
 436     }
 437 }
 438
 439 static void
 440 peerPingTimeout(void *data)
 441 {
 442     ps_state *psstate = data;
 443     StoreEntry *entry = psstate->entry;
 444     if (entry)
 445         debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
 446     if (!cbdataValid(psstate->callback_data)) {
 447         /* request aborted */
 448         entry->ping_status = PING_DONE;
 449         cbdataUnlock(psstate->callback_data);
 450         peerSelectStateFree(psstate);
 451         return;
 452     }
 453     PeerStats.timeouts++;
 454     psstate->ping.timedout = 1;
 455     peerSelectFoo(psstate);
 456 }
 457
 458 void
 459 peerSelectInit(void)
 460 {
 461     memset(&PeerStats, '\0', sizeof(PeerStats));
 462     assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
 463 }
 464
 465 static void
 466 peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
 467 {
 468     int rtt;
 469     int hops;
 470     if (Config.onoff.query_icmp) {
 471         if (header->flags & ICP_FLAG_SRC_RTT) {
 472             rtt = header->pad & 0xFFFF;
 473             hops = (header->pad >> 16) & 0xFFFF;
 474             if (rtt > 0 && rtt < 0xFFFF)
 475                 netdbUpdatePeer(ps->request, p, rtt, hops);
 476             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 477                 ps->closest_parent_miss = p->in_addr;
 478                 ps->ping.p_rtt = rtt;
 479             }
 480         }
 481     }
 482     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 483     if (p->options.closest_only)
 484         return;
 485     /* set FIRST_MISS if there is no CLOSEST parent */
 486     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 487         return;
 488     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 489     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 490         ps->first_parent_miss = p->in_addr;
 491         ps->ping.w_rtt = rtt;
 492     }
 493 }
 494
 495 static void
 496 peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
 497 {
 498     ps_state *psstate = data;
 499     icp_opcode op = header->opcode;
 500     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 501         icp_opcode_str[op],
 502         storeUrl(psstate->entry));
 503 #if USE_CACHE_DIGESTS && 0
 504     /* do cd lookup to count false misses */
 505     if (p && request)
 506         peerNoteDigestLookup(request, p,
 507             peerDigestLookup(p, request, psstate->entry));
 508 #endif
 509     psstate->ping.n_recv++;
 510     if (op == ICP_MISS || op == ICP_DECHO) {
 511         if (type == PEER_PARENT)
 512             peerIcpParentMiss(p, header, psstate);
 513     } else if (op == ICP_HIT) {
 514         psstate->hit = p;
 515         psstate->hit_type = type;
 516         peerSelectFoo(psstate);
 517         return;
 518     }
 519 #if ALLOW_SOURCE_PING
 520     else if (op == ICP_SECHO) {
 521         psstate->secho = p;
 522         peerSelectFoo(psstate);
 523         return;
 524     }
 525 #endif
 526     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 527         return;
 528     peerSelectFoo(psstate);
 529 }
 530
 531 #if USE_HTCP
 532 static void
 533 peerHandleHtcpReply(peer * p, peer_t type, htcpReplyData * htcp, void *data)
 534 {
 535     ps_state *psstate = data;
 536     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 537         htcp->hit ? "HIT" : "MISS",
 538         storeUrl(psstate->entry));
 539     psstate->ping.n_recv++;
 540     if (htcp->hit) {
 541         psstate->hit = p;
 542         psstate->hit_type = type;
 543         peerSelectFoo(psstate);
 544         return;
 545     }
 546     if (type == PEER_PARENT)
 547         peerHtcpParentMiss(p, htcp, psstate);
 548     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 549         return;
 550     peerSelectFoo(psstate);
 551 }
 552
 553 static void
 554 peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
 555 {
 556     int rtt;
 557     int hops;
 558     if (Config.onoff.query_icmp) {
 559         if (htcp->cto.rtt > 0) {
 560             rtt = (int) htcp->cto.rtt * 1000;
 561             hops = (int) htcp->cto.hops * 1000;
 562             netdbUpdatePeer(ps->request, p, rtt, hops);
 563             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 564                 ps->closest_parent_miss = p->in_addr;
 565                 ps->ping.p_rtt = rtt;
 566             }
 567         }
 568     }
 569     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 570     if (p->options.closest_only)
 571         return;
 572     /* set FIRST_MISS if there is no CLOSEST parent */
 573     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 574         return;
 575     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 576     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 577         ps->first_parent_miss = p->in_addr;
 578         ps->ping.w_rtt = rtt;
 579     }
 580 }
 581 #endif
 582
 583 static void
 584 peerHandlePingReply(peer * p, peer_t type, protocol_t proto, void *pingdata, void *data)
 585 {
 586     if (proto == PROTO_ICP)
 587         peerHandleIcpReply(p, type, pingdata, data);
 588 #if USE_HTCP
 589     else if (proto == PROTO_HTCP)
 590         peerHandleHtcpReply(p, type, pingdata, data);
 591 #endif
 592     else
 593         debug(44, 1) ("peerHandlePingReply: unknown protocol_t %d\n", (int) proto);
 594 }
 595
 596 static void
 597 peerAddFwdServer(FwdServer ** FS, peer * p, hier_code code)
 598 {
 599     FwdServer *fs = memAllocate(MEM_FWD_SERVER);
 600     debug(44, 5) ("peerAddFwdServer: adding %s %s\n",
 601         p ? p->host : "DIRECT",
 602         hier_strings[code]);
 603     fs->peer = p;
 604     fs->code = code;
 605     cbdataLock(fs->peer);
 606     while (*FS)
 607         FS = &(*FS)->next;
 608     *FS = fs;
 609 }