2 * $Id: peer_select.cc,v 1.149 2008/01/20 08:54:28 amosjeffries Exp $
4 * DEBUG: section 44 Peer Selection Algorithm
5 * AUTHOR: Duane Wessels
7 * SQUID Web Proxy Cache http://www.squid-cache.org/
8 * ----------------------------------------------------------
10 * Squid is the result of efforts by numerous individuals from
11 * the Internet community; see the CONTRIBUTORS file for full
12 * details. Many organizations have provided support for Squid's
13 * development; see the SPONSORS file for full details. Squid is
14 * Copyrighted (C) 2001 by the Regents of the University of
15 * California; see the COPYRIGHT file for full details. Squid
16 * incorporates software developed and/or copyrighted by other
17 * sources; see the CREDITS file for full details.
19 * This program is free software; you can redistribute it and/or modify
20 * it under the terms of the GNU General Public License as published by
21 * the Free Software Foundation; either version 2 of the License, or
22 * (at your option) any later version.
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
37 #include "PeerSelectState.h"
40 #include "HttpRequest.h"
41 #include "ACLChecklist.h"
44 #include "SquidTime.h"
46 const char *hier_strings
[] =
56 "CLOSEST_PARENT_MISS",
78 static const char *DirectStr
[] =
86 static void peerSelectFoo(ps_state
*);
87 static void peerPingTimeout(void *data
);
88 static void peerSelectCallback(ps_state
* psstate
);
89 static IRCB peerHandlePingReply
;
90 static void peerSelectStateFree(ps_state
* psstate
);
91 static void peerIcpParentMiss(peer
*, icp_common_t
*, ps_state
*);
93 static void peerHtcpParentMiss(peer
*, htcpReplyData
*, ps_state
*);
94 static void peerHandleHtcpReply(peer
*, peer_t
, htcpReplyData
*, void *);
96 static int peerCheckNetdbDirect(ps_state
* psstate
);
97 static void peerGetSomeNeighbor(ps_state
*);
98 static void peerGetSomeNeighborReplies(ps_state
*);
99 static void peerGetSomeDirect(ps_state
*);
100 static void peerGetSomeParent(ps_state
*);
101 static void peerGetAllParents(ps_state
*);
102 static void peerAddFwdServer(FwdServer
**, peer
*, hier_code
);
104 CBDATA_CLASS_INIT(ps_state
);
107 peerSelectStateFree(ps_state
* psstate
)
109 if (psstate
->acl_checklist
) {
110 debugs(44, 1, "calling aclChecklistFree() from peerSelectStateFree");
111 delete (psstate
->acl_checklist
);
114 HTTPMSGUNLOCK(psstate
->request
);
116 if (psstate
->entry
) {
117 assert(psstate
->entry
->ping_status
!= PING_WAITING
);
118 psstate
->entry
->unlock();
119 psstate
->entry
= NULL
;
126 peerSelectIcpPing(HttpRequest
* request
, int direct
, StoreEntry
* entry
)
130 assert(entry
->ping_status
== PING_NONE
);
131 assert(direct
!= DIRECT_YES
);
132 debugs(44, 3, "peerSelectIcpPing: " << entry
->url() );
134 if (!request
->flags
.hierarchical
&& direct
!= DIRECT_NO
)
137 if (EBIT_TEST(entry
->flags
, KEY_PRIVATE
) && !neighbors_do_private_keys
)
138 if (direct
!= DIRECT_NO
)
141 n
= neighborsCount(request
);
143 debugs(44, 3, "peerSelectIcpPing: counted " << n
<< " neighbors");
150 peerSelect(HttpRequest
* request
,
158 debugs(44, 3, "peerSelect: " << entry
->url() );
160 debugs(44, 3, "peerSelect: " << RequestMethodStr(request
->method
));
162 psstate
= new ps_state
;
164 psstate
->request
= HTTPMSGLOCK(request
);
166 psstate
->entry
= entry
;
168 psstate
->callback
= callback
;
170 psstate
->callback_data
= cbdataReference(callback_data
);
172 psstate
->direct
= DIRECT_UNKNOWN
;
174 #if USE_CACHE_DIGESTS
176 request
->hier
.peer_select_start
= current_time
;
181 psstate
->entry
->lock();
183 peerSelectFoo(psstate
);
187 peerCheckNeverDirectDone(int answer
, void *data
)
189 ps_state
*psstate
= (ps_state
*) data
;
190 psstate
->acl_checklist
= NULL
;
191 debugs(44, 3, "peerCheckNeverDirectDone: " << answer
);
192 psstate
->never_direct
= answer
? 1 : -1;
193 peerSelectFoo(psstate
);
197 peerCheckAlwaysDirectDone(int answer
, void *data
)
199 ps_state
*psstate
= (ps_state
*)data
;
200 psstate
->acl_checklist
= NULL
;
201 debugs(44, 3, "peerCheckAlwaysDirectDone: " << answer
);
202 psstate
->always_direct
= answer
? 1 : -1;
203 peerSelectFoo(psstate
);
207 peerSelectCallback(ps_state
* psstate
)
209 StoreEntry
*entry
= psstate
->entry
;
210 FwdServer
*fs
= psstate
->servers
;
215 debugs(44, 3, "peerSelectCallback: " << entry
->url() );
217 if (entry
->ping_status
== PING_WAITING
)
218 eventDelete(peerPingTimeout
, psstate
);
220 entry
->ping_status
= PING_DONE
;
224 debugs(44, 1, "Failed to select source for '" << entry
->url() << "'" );
225 debugs(44, 1, " always_direct = " << psstate
->always_direct
);
226 debugs(44, 1, " never_direct = " << psstate
->never_direct
);
227 debugs(44, 1, " timedout = " << psstate
->ping
.timedout
);
230 psstate
->ping
.stop
= current_time
;
231 psstate
->request
->hier
.ping
= psstate
->ping
;
232 callback
= psstate
->callback
;
233 psstate
->callback
= NULL
;
235 if (cbdataReferenceValidDone(psstate
->callback_data
, &cbdata
)) {
236 psstate
->servers
= NULL
;
237 callback(fs
, cbdata
);
240 peerSelectStateFree(psstate
);
244 peerCheckNetdbDirect(ps_state
* psstate
)
250 if (psstate
->direct
== DIRECT_NO
)
253 myrtt
= netdbHostRtt(psstate
->request
->GetHost());
255 debugs(44, 3, "peerCheckNetdbDirect: MY RTT = " << myrtt
<< " msec");
256 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_rtt = " << Config
.minDirectRtt
<< " msec");
259 if (myrtt
&& myrtt
<= Config
.minDirectRtt
)
262 myhops
= netdbHostHops(psstate
->request
->GetHost());
264 debugs(44, 3, "peerCheckNetdbDirect: MY hops = " << myhops
);
265 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_hops = " << Config
.minDirectHops
);
268 if (myhops
&& myhops
<= Config
.minDirectHops
)
271 p
= whichPeer(psstate
->closest_parent_miss
);
276 debugs(44, 3, "peerCheckNetdbDirect: closest_parent_miss RTT = " << psstate
->ping
.p_rtt
<< " msec");
278 if (myrtt
&& myrtt
<= psstate
->ping
.p_rtt
)
285 peerSelectFoo(ps_state
* ps
)
287 StoreEntry
*entry
= ps
->entry
;
288 HttpRequest
*request
= ps
->request
;
289 debugs(44, 3, "peerSelectFoo: '" << RequestMethodStr(request
->method
) << " " << request
->GetHost() << "'");
291 if (ps
->direct
== DIRECT_UNKNOWN
) {
292 if (ps
->always_direct
== 0 && Config
.accessList
.AlwaysDirect
) {
293 ps
->acl_checklist
= aclChecklistCreate(
294 Config
.accessList
.AlwaysDirect
,
297 ps
->acl_checklist
->nonBlockingCheck(peerCheckAlwaysDirectDone
,
300 } else if (ps
->always_direct
> 0) {
301 ps
->direct
= DIRECT_YES
;
302 } else if (ps
->never_direct
== 0 && Config
.accessList
.NeverDirect
) {
303 ps
->acl_checklist
= aclChecklistCreate(
304 Config
.accessList
.NeverDirect
,
307 ps
->acl_checklist
->nonBlockingCheck(peerCheckNeverDirectDone
,
310 } else if (ps
->never_direct
> 0) {
311 ps
->direct
= DIRECT_NO
;
312 } else if (request
->flags
.accelerated
) {
313 ps
->direct
= DIRECT_NO
;
314 } else if (request
->flags
.loopdetect
) {
315 ps
->direct
= DIRECT_YES
;
316 } else if (peerCheckNetdbDirect(ps
)) {
317 ps
->direct
= DIRECT_YES
;
319 ps
->direct
= DIRECT_MAYBE
;
322 debugs(44, 3, "peerSelectFoo: direct = " << DirectStr
[ps
->direct
]);
327 } else if (entry
->ping_status
== PING_NONE
) {
328 peerGetSomeNeighbor(ps
);
330 if (entry
->ping_status
== PING_WAITING
)
332 } else if (entry
->ping_status
== PING_WAITING
) {
333 peerGetSomeNeighborReplies(ps
);
334 entry
->ping_status
= PING_DONE
;
337 switch (ps
->direct
) {
340 peerGetSomeDirect(ps
);
344 peerGetSomeParent(ps
);
345 peerGetAllParents(ps
);
350 if (Config
.onoff
.prefer_direct
)
351 peerGetSomeDirect(ps
);
353 if (request
->flags
.hierarchical
|| !Config
.onoff
.nonhierarchical_direct
)
354 peerGetSomeParent(ps
);
356 if (!Config
.onoff
.prefer_direct
)
357 peerGetSomeDirect(ps
);
362 peerSelectCallback(ps
);
366 * peerGetSomeNeighbor
368 * Selects a neighbor (parent or sibling) based on one of the
372 * Netdb RTT estimates
376 peerGetSomeNeighbor(ps_state
* ps
)
378 StoreEntry
*entry
= ps
->entry
;
379 HttpRequest
*request
= ps
->request
;
381 hier_code code
= HIER_NONE
;
382 assert(entry
->ping_status
== PING_NONE
);
384 if (ps
->direct
== DIRECT_YES
) {
385 entry
->ping_status
= PING_DONE
;
389 #if USE_CACHE_DIGESTS
390 if ((p
= neighborsDigestSelect(request
))) {
391 if (neighborType(p
, request
) == PEER_PARENT
)
392 code
= CD_PARENT_HIT
;
394 code
= CD_SIBLING_HIT
;
397 if ((p
= netdbClosestParent(request
))) {
398 code
= CLOSEST_PARENT
;
399 } else if (peerSelectIcpPing(request
, ps
->direct
, entry
)) {
400 debugs(44, 3, "peerSelect: Doing ICP pings");
401 ps
->ping
.start
= current_time
;
402 ps
->ping
.n_sent
= neighborsUdpPing(request
,
406 &ps
->ping
.n_replies_expected
,
409 if (ps
->ping
.n_sent
== 0)
410 debugs(44, 0, "WARNING: neighborsUdpPing returned 0");
411 debugs(44, 3, "peerSelect: " << ps
->ping
.n_replies_expected
<<
412 " ICP replies expected, RTT " << ps
->ping
.timeout
<<
416 if (ps
->ping
.n_replies_expected
> 0) {
417 entry
->ping_status
= PING_WAITING
;
418 eventAdd("peerPingTimeout",
421 0.001 * ps
->ping
.timeout
,
427 if (code
!= HIER_NONE
) {
429 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
430 peerAddFwdServer(&ps
->servers
, p
, code
);
433 entry
->ping_status
= PING_DONE
;
437 * peerGetSomeNeighborReplies
439 * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
442 peerGetSomeNeighborReplies(ps_state
* ps
)
444 HttpRequest
*request
= ps
->request
;
446 hier_code code
= HIER_NONE
;
447 assert(ps
->entry
->ping_status
== PING_WAITING
);
448 assert(ps
->direct
!= DIRECT_YES
);
450 if (peerCheckNetdbDirect(ps
)) {
451 code
= CLOSEST_DIRECT
;
452 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << request
->GetHost());
453 peerAddFwdServer(&ps
->servers
, NULL
, code
);
458 code
= ps
->hit_type
== PEER_PARENT
? PARENT_HIT
: SIBLING_HIT
;
461 if (!ps
->closest_parent_miss
.IsAnyAddr()) {
462 p
= whichPeer(ps
->closest_parent_miss
);
463 code
= CLOSEST_PARENT_MISS
;
464 } else if (!ps
->first_parent_miss
.IsAnyAddr()) {
465 p
= whichPeer(ps
->first_parent_miss
);
466 code
= FIRST_PARENT_MISS
;
469 if (p
&& code
!= HIER_NONE
) {
470 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
471 peerAddFwdServer(&ps
->servers
, p
, code
);
479 * Simply adds a 'direct' entry to the FwdServers list if this
480 * request can be forwarded directly to the origin server
483 peerGetSomeDirect(ps_state
* ps
)
485 if (ps
->direct
== DIRECT_NO
)
488 /* WAIS is not implemented natively */
489 if (ps
->request
->protocol
== PROTO_WAIS
)
492 peerAddFwdServer(&ps
->servers
, NULL
, HIER_DIRECT
);
496 peerGetSomeParent(ps_state
* ps
)
499 HttpRequest
*request
= ps
->request
;
500 hier_code code
= HIER_NONE
;
501 debugs(44, 3, "peerGetSomeParent: " << RequestMethodStr(request
->method
) << " " << request
->GetHost());
503 if (ps
->direct
== DIRECT_YES
)
506 if ((p
= getDefaultParent(request
))) {
507 code
= DEFAULT_PARENT
;
508 } else if ((p
= peerUserHashSelectParent(request
))) {
509 code
= USERHASH_PARENT
;
510 } else if ((p
= peerSourceHashSelectParent(request
))) {
511 code
= SOURCEHASH_PARENT
;
512 } else if ((p
= carpSelectParent(request
))) {
514 } else if ((p
= getRoundRobinParent(request
))) {
515 code
= ROUNDROBIN_PARENT
;
516 } else if ((p
= getWeightedRoundRobinParent(request
))) {
517 code
= ROUNDROBIN_PARENT
;
518 } else if ((p
= getFirstUpParent(request
))) {
519 code
= FIRSTUP_PARENT
;
520 } else if ((p
= getAnyParent(request
))) {
521 code
= ANY_OLD_PARENT
;
524 if (code
!= HIER_NONE
) {
525 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
526 peerAddFwdServer(&ps
->servers
, p
, code
);
530 /* Adds alive parents. Used as a last resort for never_direct.
533 peerGetAllParents(ps_state
* ps
)
536 HttpRequest
*request
= ps
->request
;
537 /* Add all alive parents */
539 for (p
= Config
.peers
; p
; p
= p
->next
) {
540 /* XXX: neighbors.c lacks a public interface for enumerating
541 * parents to a request so we have to dig some here..
544 if (neighborType(p
, request
) != PEER_PARENT
)
547 if (!peerHTTPOkay(p
, request
))
550 debugs(15, 3, "peerGetAllParents: adding alive parent " << p
->host
);
552 peerAddFwdServer(&ps
->servers
, p
, ANY_OLD_PARENT
);
555 /* XXX: should add dead parents here, but it is currently
556 * not possible to find out which parents are dead or which
557 * simply are not configured to handle the request.
559 /* Add default parent as a last resort */
560 if ((p
= getDefaultParent(request
))) {
561 peerAddFwdServer(&ps
->servers
, p
, DEFAULT_PARENT
);
566 peerPingTimeout(void *data
)
568 ps_state
*psstate
= (ps_state
*)data
;
569 StoreEntry
*entry
= psstate
->entry
;
572 debugs(44, 3, "peerPingTimeout: '" << entry
->url() << "'" );
574 if (!cbdataReferenceValid(psstate
->callback_data
)) {
575 /* request aborted */
576 entry
->ping_status
= PING_DONE
;
577 cbdataReferenceDone(psstate
->callback_data
);
578 peerSelectStateFree(psstate
);
582 PeerStats
.timeouts
++;
583 psstate
->ping
.timedout
= 1;
584 peerSelectFoo(psstate
);
590 memset(&PeerStats
, '\0', sizeof(PeerStats
));
591 assert(sizeof(hier_strings
) == (HIER_MAX
+ 1) * sizeof(char *));
595 peerIcpParentMiss(peer
* p
, icp_common_t
* header
, ps_state
* ps
)
600 if (Config
.onoff
.query_icmp
) {
601 if (header
->flags
& ICP_FLAG_SRC_RTT
) {
602 rtt
= header
->pad
& 0xFFFF;
603 hops
= (header
->pad
>> 16) & 0xFFFF;
605 if (rtt
> 0 && rtt
< 0xFFFF)
606 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
608 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
609 ps
->closest_parent_miss
= p
->in_addr
;
610 ps
->ping
.p_rtt
= rtt
;
615 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
616 if (p
->options
.closest_only
)
619 /* set FIRST_MISS if there is no CLOSEST parent */
620 if (!ps
->closest_parent_miss
.IsAnyAddr())
623 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
628 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
629 ps
->first_parent_miss
= p
->in_addr
;
630 ps
->ping
.w_rtt
= rtt
;
635 peerHandleIcpReply(peer
* p
, peer_t type
, icp_common_t
* header
, void *data
)
637 ps_state
*psstate
= (ps_state
*)data
;
638 icp_opcode op
= header
->getOpCode();
639 debugs(44, 3, "peerHandleIcpReply: " << icp_opcode_str
[op
] << " " << psstate
->entry
->url() );
640 #if USE_CACHE_DIGESTS && 0
641 /* do cd lookup to count false misses */
644 peerNoteDigestLookup(request
, p
,
645 peerDigestLookup(p
, request
, psstate
->entry
));
649 psstate
->ping
.n_recv
++;
651 if (op
== ICP_MISS
|| op
== ICP_DECHO
) {
652 if (type
== PEER_PARENT
)
653 peerIcpParentMiss(p
, header
, psstate
);
654 } else if (op
== ICP_HIT
) {
656 psstate
->hit_type
= type
;
657 peerSelectFoo(psstate
);
661 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
664 peerSelectFoo(psstate
);
669 peerHandleHtcpReply(peer
* p
, peer_t type
, htcpReplyData
* htcp
, void *data
)
671 ps_state
*psstate
= (ps_state
*)data
;
672 debugs(44, 3, "peerHandleHtcpReply: " <<
673 (htcp
->hit
? "HIT" : "MISS") << " " <<
674 psstate
->entry
->url() );
675 psstate
->ping
.n_recv
++;
679 psstate
->hit_type
= type
;
680 peerSelectFoo(psstate
);
684 if (type
== PEER_PARENT
)
685 peerHtcpParentMiss(p
, htcp
, psstate
);
687 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
690 peerSelectFoo(psstate
);
694 peerHtcpParentMiss(peer
* p
, htcpReplyData
* htcp
, ps_state
* ps
)
699 if (Config
.onoff
.query_icmp
) {
700 if (htcp
->cto
.rtt
> 0) {
701 rtt
= (int) htcp
->cto
.rtt
* 1000;
702 hops
= (int) htcp
->cto
.hops
* 1000;
703 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
705 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
706 ps
->closest_parent_miss
= p
->in_addr
;
707 ps
->ping
.p_rtt
= rtt
;
712 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
713 if (p
->options
.closest_only
)
716 /* set FIRST_MISS if there is no CLOSEST parent */
717 if (!ps
->closest_parent_miss
.IsAnyAddr())
720 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
725 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
726 ps
->first_parent_miss
= p
->in_addr
;
727 ps
->ping
.w_rtt
= rtt
;
734 peerHandlePingReply(peer
* p
, peer_t type
, protocol_t proto
, void *pingdata
, void *data
)
736 if (proto
== PROTO_ICP
)
737 peerHandleIcpReply(p
, type
, (icp_common_t
*)pingdata
, data
);
741 else if (proto
== PROTO_HTCP
)
742 peerHandleHtcpReply(p
, type
, (htcpReplyData
*)pingdata
, data
);
747 debugs(44, 1, "peerHandlePingReply: unknown protocol_t " << proto
);
751 peerAddFwdServer(FwdServer
** FSVR
, peer
* p
, hier_code code
)
753 FwdServer
*fs
= (FwdServer
*)memAllocate(MEM_FWD_SERVER
);
754 debugs(44, 5, "peerAddFwdServer: adding " <<
755 (p
? p
->host
: "DIRECT") << " " <<
756 hier_strings
[code
] );
757 fs
->_peer
= cbdataReference(p
);
761 FSVR
= &(*FSVR
)->next
;
767 ps_state::operator new(size_t)
769 CBDATA_INIT_TYPE(ps_state
);
770 return cbdataAlloc(ps_state
);
773 ps_state::ps_state() : request (NULL
),
779 callback_data (NULL
),
782 closest_parent_miss(),
787 ; // no local defaults.
790 ping_data::ping_data() :
793 n_replies_expected(0),