src/peer_select.cc

   1
   2 /*
   3  * $Id: peer_select.cc,v 1.90 1998/11/12 06:33:32 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     "NO_PARENT_DIRECT",
  48     "FIRST_PARENT_MISS",
  49     "CLOSEST_PARENT_MISS",
  50     "CLOSEST_PARENT",
  51     "CLOSEST_DIRECT",
  52     "NO_DIRECT_FAIL",
  53     "SOURCE_FASTEST",
  54     "ROUNDROBIN_PARENT",
  55 #if USE_CACHE_DIGESTS
  56     "CACHE_DIGEST_HIT",
  57     "NO_CACHE_DIGEST_DIRECT",
  58 #endif
  59 #if USE_CARP
  60     "CARP",
  61 #endif
  62     "ANY_PARENT",
  63     "INVALID CODE"
  64 };
  65
  66 static struct {
  67     int timeouts;
  68 } PeerStats;
  69
  70 static char *DirectStr[] =
  71 {
  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 peerSelectCallbackFail(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
  89 static void
  90 peerSelectStateFree(ps_state * psstate)
  91 {
  92     if (psstate->acl_checklist) {
  93         debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
  94         aclChecklistFree(psstate->acl_checklist);
  95     }
  96     requestUnlink(psstate->request);
  97     psstate->request = NULL;
  98     if (psstate->entry) {
  99         assert(psstate->entry->ping_status != PING_WAITING);
 100         storeUnlockObject(psstate->entry);
 101         psstate->entry = NULL;
 102     }
 103     cbdataFree(psstate);
 104 }
 105
 106 int
 107 peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
 108 {
 109     int n;
 110     if (entry == NULL)
 111         return 0;
 112     debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
 113     if (entry->ping_status != PING_NONE)
 114         return 0;
 115     assert(direct != DIRECT_YES);
 116     if (!request->flags.hierarchical && direct != DIRECT_NO)
 117         return 0;
 118     if (EBIT_TEST(entry->flags, KEY_PRIVATE) && !neighbors_do_private_keys)
 119         if (direct != DIRECT_NO)
 120             return 0;
 121     n = neighborsCount(request);
 122     debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
 123     return n;
 124 }
 125
 126
 127 peer *
 128 peerGetSomeParent(request_t * request, hier_code * code)
 129 {
 130     peer *p;
 131     debug(44, 3) ("peerGetSomeParent: %s %s\n",
 132         RequestMethodStr[request->method],
 133         request->host);
 134     if ((p = getDefaultParent(request))) {
 135         *code = DEFAULT_PARENT;
 136         return p;
 137     }
 138     if ((p = getRoundRobinParent(request))) {
 139         *code = ROUNDROBIN_PARENT;
 140         return p;
 141     }
 142     if ((p = getFirstUpParent(request))) {
 143         *code = FIRSTUP_PARENT;
 144         return p;
 145     }
 146     if ((p = getAnyParent(request))) {
 147         *code = ANY_OLD_PARENT;
 148         return p;
 149     }
 150     return NULL;
 151 }
 152
 153 void
 154 peerSelect(request_t * request,
 155     StoreEntry * entry,
 156     PSC * callback,
 157     PSC * fail_callback,
 158     void *callback_data)
 159 {
 160     ps_state *psstate = xcalloc(1, sizeof(ps_state));
 161     if (entry)
 162         debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
 163     else
 164         debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
 165     cbdataAdd(psstate, MEM_NONE);
 166     psstate->request = requestLink(request);
 167     psstate->entry = entry;
 168     psstate->callback = callback;
 169     psstate->fail_callback = fail_callback;
 170     psstate->callback_data = callback_data;
 171 #if USE_CACHE_DIGESTS
 172     request->hier.peer_select_start = current_time;
 173 #endif
 174     if (psstate->entry)
 175         storeLockObject(psstate->entry);
 176     cbdataLock(callback_data);
 177     peerSelectFoo(psstate);
 178 }
 179
 180 static void
 181 peerCheckNeverDirectDone(int answer, void *data)
 182 {
 183     ps_state *psstate = data;
 184     psstate->acl_checklist = NULL;
 185     debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
 186     psstate->never_direct = answer ? 1 : -1;
 187     peerSelectFoo(psstate);
 188 }
 189
 190 static void
 191 peerCheckAlwaysDirectDone(int answer, void *data)
 192 {
 193     ps_state *psstate = data;
 194     psstate->acl_checklist = NULL;
 195     debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
 196     psstate->always_direct = answer ? 1 : -1;
 197     peerSelectFoo(psstate);
 198 }
 199
 200 static void
 201 peerSelectCallback(ps_state * psstate, peer * p)
 202 {
 203     StoreEntry *entry = psstate->entry;
 204     void *data = psstate->callback_data;
 205     if (entry) {
 206         debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
 207         if (entry->ping_status == PING_WAITING)
 208             eventDelete(peerPingTimeout, psstate);
 209         entry->ping_status = PING_DONE;
 210     }
 211     psstate->ping.stop = current_time;
 212     if (cbdataValid(data))
 213         psstate->callback(p, data);
 214     cbdataUnlock(data);
 215     peerSelectStateFree(psstate);
 216 }
 217
 218 static void
 219 peerSelectCallbackFail(ps_state * psstate)
 220 {
 221     request_t *request = psstate->request;
 222     void *data = psstate->callback_data;
 223     const char *url = psstate->entry ? storeUrl(psstate->entry) : urlCanonical(request);
 224     if (psstate->entry)
 225         psstate->entry->ping_status = PING_DONE;
 226     debug(44, 1) ("Failed to select source for '%s'\n", url);
 227     debug(44, 1) ("  always_direct = %d\n", psstate->always_direct);
 228     debug(44, 1) ("   never_direct = %d\n", psstate->never_direct);
 229     debug(44, 1) ("       timedout = %d\n", psstate->ping.timedout);
 230     if (cbdataValid(data))
 231         psstate->fail_callback(NULL, data);
 232     cbdataUnlock(data);
 233     peerSelectStateFree(psstate);
 234 }
 235
 236 static int
 237 peerCheckNetdbDirect(ps_state * psstate)
 238 {
 239     peer *p = whichPeer(&psstate->closest_parent_miss);
 240     int myrtt;
 241     int myhops;
 242     if (p == NULL)
 243         return 0;
 244     myrtt = netdbHostRtt(psstate->request->host);
 245     debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d msec\n", myrtt);
 246     debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d msec\n",
 247         psstate->ping.p_rtt);
 248     if (myrtt && myrtt < psstate->ping.p_rtt)
 249         return 1;
 250     myhops = netdbHostHops(psstate->request->host);
 251     debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
 252     debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
 253         Config.minDirectHops);
 254     if (myhops && myhops <= Config.minDirectHops)
 255         return 1;
 256     return 0;
 257 }
 258
 259 static void
 260 peerSelectFoo(ps_state * psstate)
 261 {
 262     peer *p;
 263     hier_code code;
 264     StoreEntry *entry = psstate->entry;
 265     request_t *request = psstate->request;
 266     int direct;
 267     debug(44, 3) ("peerSelectFoo: '%s %s'\n",
 268         RequestMethodStr[request->method],
 269         request->host);
 270     if (psstate->always_direct == 0 && Config.accessList.AlwaysDirect) {
 271         psstate->acl_checklist = aclChecklistCreate(
 272             Config.accessList.AlwaysDirect,
 273             request,
 274             request->client_addr,
 275             NULL,               /* user agent */
 276             NULL);              /* ident */
 277         aclNBCheck(psstate->acl_checklist,
 278             peerCheckAlwaysDirectDone,
 279             psstate);
 280         return;
 281     } else if (psstate->always_direct > 0) {
 282         direct = DIRECT_YES;
 283     } else if (psstate->never_direct == 0 && Config.accessList.NeverDirect) {
 284         psstate->acl_checklist = aclChecklistCreate(
 285             Config.accessList.NeverDirect,
 286             request,
 287             request->client_addr,
 288             NULL,               /* user agent */
 289             NULL);              /* ident */
 290         aclNBCheck(psstate->acl_checklist,
 291             peerCheckNeverDirectDone,
 292             psstate);
 293         return;
 294     } else if (psstate->never_direct > 0) {
 295         direct = DIRECT_NO;
 296     } else if (request->flags.loopdetect) {
 297         direct = DIRECT_YES;
 298     } else {
 299         direct = DIRECT_MAYBE;
 300     }
 301     debug(44, 3) ("peerSelectFoo: direct = %s\n", DirectStr[direct]);
 302     if (direct == DIRECT_YES) {
 303         debug(44, 3) ("peerSelectFoo: DIRECT\n");
 304         hierarchyNote(&request->hier, DIRECT, &psstate->ping, request->host);
 305         peerSelectCallback(psstate, NULL);
 306         return;
 307     }
 308     if ((p = getSingleParent(request))) {
 309         code = SINGLE_PARENT;
 310         debug(44, 3) ("peerSelectFoo: %s/%s\n", hier_strings[code], p->host);
 311         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 312         peerSelectCallback(psstate, p);
 313         return;
 314     }
 315     if (!request->flags.hierarchical && direct != DIRECT_NO) {
 316         debug(44, 3) ("peerSelectFoo: DIRECT for non-hierarchical request\n");
 317         hierarchyNote(&request->hier, DIRECT, &psstate->ping, request->host);
 318         peerSelectCallback(psstate, NULL);
 319         return;
 320     }
 321 #if USE_CACHE_DIGESTS
 322     else if ((p = neighborsDigestSelect(request, entry))) {
 323         debug(44, 2) ("peerSelect: Using Cache Digest\n");
 324         request->hier.alg = PEER_SA_DIGEST;
 325         code = CACHE_DIGEST_HIT;
 326         debug(44, 2) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 327         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 328         peerSelectCallback(psstate, p);
 329         return;
 330     }
 331 #endif
 332 #if USE_CARP
 333     else if ((p = carpSelectParent(request))) {
 334         hierarchyNote(&request->hier, CARP, &psstate->ping, p->host);
 335         peerSelectCallback(psstate, p);
 336         return;
 337     }
 338 #endif
 339     else if ((p = netdbClosestParent(request))) {
 340         request->hier.alg = PEER_SA_NETDB;
 341         code = CLOSEST_PARENT;
 342         debug(44, 2) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 343         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 344         peerSelectCallback(psstate, p);
 345         return;
 346     } else if (peerSelectIcpPing(request, direct, entry)) {
 347         assert(entry->ping_status == PING_NONE);
 348         request->hier.alg = PEER_SA_ICP;
 349         debug(44, 3) ("peerSelect: Doing ICP pings\n");
 350         psstate->ping.start = current_time;
 351         psstate->ping.n_sent = neighborsUdpPing(request,
 352             entry,
 353             peerHandlePingReply,
 354             psstate,
 355             &psstate->ping.n_replies_expected,
 356             &psstate->ping.timeout);
 357         if (psstate->ping.n_sent == 0)
 358             debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
 359         debug(44, 3) ("peerSelectFoo: %d ICP replies expected, RTT %d msec\n",
 360             psstate->ping.n_replies_expected, psstate->ping.timeout);
 361         if (psstate->ping.n_replies_expected > 0) {
 362             entry->ping_status = PING_WAITING;
 363             eventAdd("peerPingTimeout",
 364                 peerPingTimeout,
 365                 psstate,
 366                 0.001 * psstate->ping.timeout,
 367                 0);
 368             return;
 369         }
 370     }
 371     debug(44, 3) ("peerSelectFoo: After peerSelectIcpPing.\n");
 372     if (peerCheckNetdbDirect(psstate)) {
 373         code = CLOSEST_DIRECT;
 374         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
 375         hierarchyNote(&request->hier, code, &psstate->ping, request->host);
 376         peerSelectCallback(psstate, NULL);
 377     } else if ((p = whichPeer(&psstate->closest_parent_miss))) {
 378         code = CLOSEST_PARENT_MISS;
 379         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 380         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 381         peerSelectCallback(psstate, p);
 382     } else if ((p = whichPeer(&psstate->first_parent_miss))) {
 383         code = FIRST_PARENT_MISS;
 384         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 385         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 386         peerSelectCallback(psstate, p);
 387     } else if (Config.onoff.prefer_direct && direct != DIRECT_NO) {
 388         code = DIRECT;
 389         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
 390         hierarchyNote(&request->hier, code, &psstate->ping, request->host);
 391         peerSelectCallback(psstate, NULL);
 392     } else if ((p = peerGetSomeParent(request, &code))) {
 393         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 394         hierarchyNote(&request->hier, code, &psstate->ping, p->host);
 395         peerSelectCallback(psstate, p);
 396     } else if (direct != DIRECT_NO) {
 397         code = DIRECT;
 398         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
 399         hierarchyNote(&request->hier, code, &psstate->ping, request->host);
 400         peerSelectCallback(psstate, NULL);
 401     } else {
 402         code = NO_DIRECT_FAIL;
 403         hierarchyNote(&request->hier, code, &psstate->ping, NULL);
 404         peerSelectCallbackFail(psstate);
 405     }
 406 }
 407
 408 static void
 409 peerPingTimeout(void *data)
 410 {
 411     ps_state *psstate = data;
 412     StoreEntry *entry = psstate->entry;
 413     if (entry)
 414         debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
 415     entry->ping_status = PING_TIMEOUT;
 416     if (!cbdataValid(psstate->callback_data)) {
 417         /* request aborted */
 418         cbdataUnlock(psstate->callback_data);
 419         peerSelectStateFree(psstate);
 420         return;
 421     }
 422     PeerStats.timeouts++;
 423     psstate->ping.timedout = 1;
 424     peerSelectFoo(psstate);
 425 }
 426
 427 void
 428 peerSelectInit(void)
 429 {
 430     memset(&PeerStats, '\0', sizeof(PeerStats));
 431     assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
 432 }
 433
 434 static void
 435 peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
 436 {
 437     int rtt;
 438     int hops;
 439     if (Config.onoff.query_icmp) {
 440         if (header->flags & ICP_FLAG_SRC_RTT) {
 441             rtt = header->pad & 0xFFFF;
 442             hops = (header->pad >> 16) & 0xFFFF;
 443             if (rtt > 0 && rtt < 0xFFFF)
 444                 netdbUpdatePeer(ps->request, p, rtt, hops);
 445             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 446                 ps->closest_parent_miss = p->in_addr;
 447                 ps->ping.p_rtt = rtt;
 448             }
 449         }
 450     }
 451     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 452     if (p->options.closest_only)
 453         return;
 454     /* set FIRST_MISS if there is no CLOSEST parent */
 455     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 456         return;
 457     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 458     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 459         ps->first_parent_miss = p->in_addr;
 460         ps->ping.w_rtt = rtt;
 461     }
 462 }
 463
 464 static void
 465 peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
 466 {
 467     ps_state *psstate = data;
 468     icp_opcode op = header->opcode;
 469     request_t *request = psstate->request;
 470     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 471         icp_opcode_str[op],
 472         storeUrl(psstate->entry));
 473 #if USE_CACHE_DIGESTS && 0
 474     /* do cd lookup to count false misses */
 475     if (p && request)
 476         peerNoteDigestLookup(request, p,
 477             peerDigestLookup(p, request, psstate->entry));
 478 #endif
 479     psstate->ping.n_recv++;
 480     if (op == ICP_MISS || op == ICP_DECHO) {
 481         if (type == PEER_PARENT)
 482             peerIcpParentMiss(p, header, psstate);
 483     } else if (op == ICP_HIT) {
 484         hierarchyNote(&request->hier,
 485             type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT,
 486             &psstate->ping,
 487             p->host);
 488         peerSelectCallback(psstate, p);
 489         return;
 490     } else if (op == ICP_SECHO) {
 491         hierarchyNote(&request->hier,
 492             SOURCE_FASTEST,
 493             &psstate->ping,
 494             request->host);
 495         peerSelectCallback(psstate, NULL);
 496         return;
 497     }
 498     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 499         return;
 500     peerSelectFoo(psstate);
 501 }
 502
 503 #if USE_HTCP
 504 static void
 505 peerHandleHtcpReply(peer * p, peer_t type, htcpReplyData * htcp, void *data)
 506 {
 507     ps_state *psstate = data;
 508     request_t *request = psstate->request;
 509     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 510         htcp->hit ? "HIT" : "MISS",
 511         storeUrl(psstate->entry));
 512     psstate->ping.n_recv++;
 513     if (htcp->hit) {
 514         hierarchyNote(&request->hier,
 515             type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT,
 516             &psstate->ping,
 517             p->host);
 518         peerSelectCallback(psstate, p);
 519         return;
 520     }
 521     if (type == PEER_PARENT)
 522         peerHtcpParentMiss(p, htcp, psstate);
 523     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 524         return;
 525     peerSelectFoo(psstate);
 526 }
 527
 528 static void
 529 peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
 530 {
 531     int rtt;
 532     int hops;
 533     if (Config.onoff.query_icmp) {
 534         if (htcp->cto.rtt > 0) {
 535             rtt = (int) htcp->cto.rtt * 1000;
 536             hops = (int) htcp->cto.hops * 1000;
 537             netdbUpdatePeer(ps->request, p, rtt, hops);
 538             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 539                 ps->closest_parent_miss = p->in_addr;
 540                 ps->ping.p_rtt = rtt;
 541             }
 542         }
 543     }
 544     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 545     if (p->options.closest_only)
 546         return;
 547     /* set FIRST_MISS if there is no CLOSEST parent */
 548     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 549         return;
 550     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 551     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 552         ps->first_parent_miss = p->in_addr;
 553         ps->ping.w_rtt = rtt;
 554     }
 555 }
 556 #endif
 557
 558 static void
 559 peerHandlePingReply(peer * p, peer_t type, protocol_t proto, void *pingdata, void *data)
 560 {
 561     if (proto == PROTO_ICP)
 562         peerHandleIcpReply(p, type, pingdata, data);
 563 #if USE_HTCP
 564     else if (proto == PROTO_HTCP)
 565         peerHandleHtcpReply(p, type, pingdata, data);
 566 #endif
 567     else
 568         debug(44, 1) ("peerHandlePingReply: unknown protocol_t %d\n", (int) proto);
 569 }