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
);
103 static void peerSelectPinned(ps_state
* ps
);
105 CBDATA_CLASS_INIT(ps_state
);
108 peerSelectStateFree(ps_state
* psstate
)
110 if (psstate
->acl_checklist
) {
111 debugs(44, 1, "calling aclChecklistFree() from peerSelectStateFree");
112 delete (psstate
->acl_checklist
);
115 HTTPMSGUNLOCK(psstate
->request
);
117 if (psstate
->entry
) {
118 assert(psstate
->entry
->ping_status
!= PING_WAITING
);
119 psstate
->entry
->unlock();
120 psstate
->entry
= NULL
;
127 peerSelectIcpPing(HttpRequest
* request
, int direct
, StoreEntry
* entry
)
131 assert(entry
->ping_status
== PING_NONE
);
132 assert(direct
!= DIRECT_YES
);
133 debugs(44, 3, "peerSelectIcpPing: " << entry
->url() );
135 if (!request
->flags
.hierarchical
&& direct
!= DIRECT_NO
)
138 if (EBIT_TEST(entry
->flags
, KEY_PRIVATE
) && !neighbors_do_private_keys
)
139 if (direct
!= DIRECT_NO
)
142 n
= neighborsCount(request
);
144 debugs(44, 3, "peerSelectIcpPing: counted " << n
<< " neighbors");
151 peerSelect(HttpRequest
* request
,
159 debugs(44, 3, "peerSelect: " << entry
->url() );
161 debugs(44, 3, "peerSelect: " << RequestMethodStr(request
->method
));
163 psstate
= new ps_state
;
165 psstate
->request
= HTTPMSGLOCK(request
);
167 psstate
->entry
= entry
;
169 psstate
->callback
= callback
;
171 psstate
->callback_data
= cbdataReference(callback_data
);
173 psstate
->direct
= DIRECT_UNKNOWN
;
175 #if USE_CACHE_DIGESTS
177 request
->hier
.peer_select_start
= current_time
;
182 psstate
->entry
->lock();
184 peerSelectFoo(psstate
);
188 peerCheckNeverDirectDone(int answer
, void *data
)
190 ps_state
*psstate
= (ps_state
*) data
;
191 psstate
->acl_checklist
= NULL
;
192 debugs(44, 3, "peerCheckNeverDirectDone: " << answer
);
193 psstate
->never_direct
= answer
? 1 : -1;
194 peerSelectFoo(psstate
);
198 peerCheckAlwaysDirectDone(int answer
, void *data
)
200 ps_state
*psstate
= (ps_state
*)data
;
201 psstate
->acl_checklist
= NULL
;
202 debugs(44, 3, "peerCheckAlwaysDirectDone: " << answer
);
203 psstate
->always_direct
= answer
? 1 : -1;
204 peerSelectFoo(psstate
);
208 peerSelectCallback(ps_state
* psstate
)
210 StoreEntry
*entry
= psstate
->entry
;
211 FwdServer
*fs
= psstate
->servers
;
216 debugs(44, 3, "peerSelectCallback: " << entry
->url() );
218 if (entry
->ping_status
== PING_WAITING
)
219 eventDelete(peerPingTimeout
, psstate
);
221 entry
->ping_status
= PING_DONE
;
225 debugs(44, 1, "Failed to select source for '" << entry
->url() << "'" );
226 debugs(44, 1, " always_direct = " << psstate
->always_direct
);
227 debugs(44, 1, " never_direct = " << psstate
->never_direct
);
228 debugs(44, 1, " timedout = " << psstate
->ping
.timedout
);
231 psstate
->ping
.stop
= current_time
;
232 psstate
->request
->hier
.ping
= psstate
->ping
;
233 callback
= psstate
->callback
;
234 psstate
->callback
= NULL
;
236 if (cbdataReferenceValidDone(psstate
->callback_data
, &cbdata
)) {
237 psstate
->servers
= NULL
;
238 callback(fs
, cbdata
);
241 peerSelectStateFree(psstate
);
245 peerCheckNetdbDirect(ps_state
* psstate
)
251 if (psstate
->direct
== DIRECT_NO
)
254 myrtt
= netdbHostRtt(psstate
->request
->GetHost());
256 debugs(44, 3, "peerCheckNetdbDirect: MY RTT = " << myrtt
<< " msec");
257 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_rtt = " << Config
.minDirectRtt
<< " msec");
260 if (myrtt
&& myrtt
<= Config
.minDirectRtt
)
263 myhops
= netdbHostHops(psstate
->request
->GetHost());
265 debugs(44, 3, "peerCheckNetdbDirect: MY hops = " << myhops
);
266 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_hops = " << Config
.minDirectHops
);
269 if (myhops
&& myhops
<= Config
.minDirectHops
)
272 p
= whichPeer(psstate
->closest_parent_miss
);
277 debugs(44, 3, "peerCheckNetdbDirect: closest_parent_miss RTT = " << psstate
->ping
.p_rtt
<< " msec");
279 if (myrtt
&& myrtt
<= psstate
->ping
.p_rtt
)
286 peerSelectFoo(ps_state
* ps
)
288 StoreEntry
*entry
= ps
->entry
;
289 HttpRequest
*request
= ps
->request
;
290 debugs(44, 3, "peerSelectFoo: '" << RequestMethodStr(request
->method
) << " " << request
->GetHost() << "'");
292 if (ps
->direct
== DIRECT_UNKNOWN
) {
293 if (ps
->always_direct
== 0 && Config
.accessList
.AlwaysDirect
) {
294 ps
->acl_checklist
= aclChecklistCreate(
295 Config
.accessList
.AlwaysDirect
,
298 ps
->acl_checklist
->nonBlockingCheck(peerCheckAlwaysDirectDone
,
301 } else if (ps
->always_direct
> 0) {
302 ps
->direct
= DIRECT_YES
;
303 } else if (ps
->never_direct
== 0 && Config
.accessList
.NeverDirect
) {
304 ps
->acl_checklist
= aclChecklistCreate(
305 Config
.accessList
.NeverDirect
,
308 ps
->acl_checklist
->nonBlockingCheck(peerCheckNeverDirectDone
,
311 } else if (ps
->never_direct
> 0) {
312 ps
->direct
= DIRECT_NO
;
313 } else if (request
->flags
.accelerated
) {
314 ps
->direct
= DIRECT_NO
;
315 } else if (request
->flags
.loopdetect
) {
316 ps
->direct
= DIRECT_YES
;
317 } else if (peerCheckNetdbDirect(ps
)) {
318 ps
->direct
= DIRECT_YES
;
320 ps
->direct
= DIRECT_MAYBE
;
323 debugs(44, 3, "peerSelectFoo: direct = " << DirectStr
[ps
->direct
]);
326 if (!entry
|| entry
->ping_status
== PING_NONE
)
327 peerSelectPinned(ps
);
330 } else if (entry
->ping_status
== PING_NONE
) {
331 peerGetSomeNeighbor(ps
);
333 if (entry
->ping_status
== PING_WAITING
)
335 } else if (entry
->ping_status
== PING_WAITING
) {
336 peerGetSomeNeighborReplies(ps
);
337 entry
->ping_status
= PING_DONE
;
340 switch (ps
->direct
) {
343 peerGetSomeDirect(ps
);
347 peerGetSomeParent(ps
);
348 peerGetAllParents(ps
);
353 if (Config
.onoff
.prefer_direct
)
354 peerGetSomeDirect(ps
);
356 if (request
->flags
.hierarchical
|| !Config
.onoff
.nonhierarchical_direct
)
357 peerGetSomeParent(ps
);
359 if (!Config
.onoff
.prefer_direct
)
360 peerGetSomeDirect(ps
);
365 peerSelectCallback(ps
);
371 * Selects a pinned connection
373 int peerAllowedToUse(const peer
* p
, HttpRequest
* request
);
375 peerSelectPinned(ps_state
* ps
)
377 HttpRequest
*request
= ps
->request
;
379 if (!request
->pinnedConnection())
381 if (request
->pinnedConnection()->validatePinnedConnection(request
) != -1) {
382 peer
= request
->pinnedConnection()->pinnedPeer();
383 if (peer
&& peerAllowedToUse(peer
, request
)) {
384 peerAddFwdServer(&ps
->servers
, peer
, PINNED
);
386 ps
->entry
->ping_status
= PING_DONE
; /* Skip ICP */
387 } else if (!peer
&& ps
->direct
!= DIRECT_NO
) {
388 peerAddFwdServer(&ps
->servers
, NULL
, PINNED
);
390 ps
->entry
->ping_status
= PING_DONE
; /* Skip ICP */
396 * peerGetSomeNeighbor
398 * Selects a neighbor (parent or sibling) based on one of the
402 * Netdb RTT estimates
406 peerGetSomeNeighbor(ps_state
* ps
)
408 StoreEntry
*entry
= ps
->entry
;
409 HttpRequest
*request
= ps
->request
;
411 hier_code code
= HIER_NONE
;
412 assert(entry
->ping_status
== PING_NONE
);
414 if (ps
->direct
== DIRECT_YES
) {
415 entry
->ping_status
= PING_DONE
;
419 #if USE_CACHE_DIGESTS
420 if ((p
= neighborsDigestSelect(request
))) {
421 if (neighborType(p
, request
) == PEER_PARENT
)
422 code
= CD_PARENT_HIT
;
424 code
= CD_SIBLING_HIT
;
427 if ((p
= netdbClosestParent(request
))) {
428 code
= CLOSEST_PARENT
;
429 } else if (peerSelectIcpPing(request
, ps
->direct
, entry
)) {
430 debugs(44, 3, "peerSelect: Doing ICP pings");
431 ps
->ping
.start
= current_time
;
432 ps
->ping
.n_sent
= neighborsUdpPing(request
,
436 &ps
->ping
.n_replies_expected
,
439 if (ps
->ping
.n_sent
== 0)
440 debugs(44, 0, "WARNING: neighborsUdpPing returned 0");
441 debugs(44, 3, "peerSelect: " << ps
->ping
.n_replies_expected
<<
442 " ICP replies expected, RTT " << ps
->ping
.timeout
<<
446 if (ps
->ping
.n_replies_expected
> 0) {
447 entry
->ping_status
= PING_WAITING
;
448 eventAdd("peerPingTimeout",
451 0.001 * ps
->ping
.timeout
,
457 if (code
!= HIER_NONE
) {
459 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
460 peerAddFwdServer(&ps
->servers
, p
, code
);
463 entry
->ping_status
= PING_DONE
;
467 * peerGetSomeNeighborReplies
469 * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
472 peerGetSomeNeighborReplies(ps_state
* ps
)
474 HttpRequest
*request
= ps
->request
;
476 hier_code code
= HIER_NONE
;
477 assert(ps
->entry
->ping_status
== PING_WAITING
);
478 assert(ps
->direct
!= DIRECT_YES
);
480 if (peerCheckNetdbDirect(ps
)) {
481 code
= CLOSEST_DIRECT
;
482 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << request
->GetHost());
483 peerAddFwdServer(&ps
->servers
, NULL
, code
);
488 code
= ps
->hit_type
== PEER_PARENT
? PARENT_HIT
: SIBLING_HIT
;
491 if (!ps
->closest_parent_miss
.IsAnyAddr()) {
492 p
= whichPeer(ps
->closest_parent_miss
);
493 code
= CLOSEST_PARENT_MISS
;
494 } else if (!ps
->first_parent_miss
.IsAnyAddr()) {
495 p
= whichPeer(ps
->first_parent_miss
);
496 code
= FIRST_PARENT_MISS
;
499 if (p
&& code
!= HIER_NONE
) {
500 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
501 peerAddFwdServer(&ps
->servers
, p
, code
);
509 * Simply adds a 'direct' entry to the FwdServers list if this
510 * request can be forwarded directly to the origin server
513 peerGetSomeDirect(ps_state
* ps
)
515 if (ps
->direct
== DIRECT_NO
)
518 /* WAIS is not implemented natively */
519 if (ps
->request
->protocol
== PROTO_WAIS
)
522 peerAddFwdServer(&ps
->servers
, NULL
, HIER_DIRECT
);
526 peerGetSomeParent(ps_state
* ps
)
529 HttpRequest
*request
= ps
->request
;
530 hier_code code
= HIER_NONE
;
531 debugs(44, 3, "peerGetSomeParent: " << RequestMethodStr(request
->method
) << " " << request
->GetHost());
533 if (ps
->direct
== DIRECT_YES
)
536 if ((p
= getDefaultParent(request
))) {
537 code
= DEFAULT_PARENT
;
538 } else if ((p
= peerUserHashSelectParent(request
))) {
539 code
= USERHASH_PARENT
;
540 } else if ((p
= peerSourceHashSelectParent(request
))) {
541 code
= SOURCEHASH_PARENT
;
542 } else if ((p
= carpSelectParent(request
))) {
544 } else if ((p
= getRoundRobinParent(request
))) {
545 code
= ROUNDROBIN_PARENT
;
546 } else if ((p
= getWeightedRoundRobinParent(request
))) {
547 code
= ROUNDROBIN_PARENT
;
548 } else if ((p
= getFirstUpParent(request
))) {
549 code
= FIRSTUP_PARENT
;
550 } else if ((p
= getAnyParent(request
))) {
551 code
= ANY_OLD_PARENT
;
554 if (code
!= HIER_NONE
) {
555 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
556 peerAddFwdServer(&ps
->servers
, p
, code
);
560 /* Adds alive parents. Used as a last resort for never_direct.
563 peerGetAllParents(ps_state
* ps
)
566 HttpRequest
*request
= ps
->request
;
567 /* Add all alive parents */
569 for (p
= Config
.peers
; p
; p
= p
->next
) {
570 /* XXX: neighbors.c lacks a public interface for enumerating
571 * parents to a request so we have to dig some here..
574 if (neighborType(p
, request
) != PEER_PARENT
)
577 if (!peerHTTPOkay(p
, request
))
580 debugs(15, 3, "peerGetAllParents: adding alive parent " << p
->host
);
582 peerAddFwdServer(&ps
->servers
, p
, ANY_OLD_PARENT
);
585 /* XXX: should add dead parents here, but it is currently
586 * not possible to find out which parents are dead or which
587 * simply are not configured to handle the request.
589 /* Add default parent as a last resort */
590 if ((p
= getDefaultParent(request
))) {
591 peerAddFwdServer(&ps
->servers
, p
, DEFAULT_PARENT
);
596 peerPingTimeout(void *data
)
598 ps_state
*psstate
= (ps_state
*)data
;
599 StoreEntry
*entry
= psstate
->entry
;
602 debugs(44, 3, "peerPingTimeout: '" << entry
->url() << "'" );
604 if (!cbdataReferenceValid(psstate
->callback_data
)) {
605 /* request aborted */
606 entry
->ping_status
= PING_DONE
;
607 cbdataReferenceDone(psstate
->callback_data
);
608 peerSelectStateFree(psstate
);
612 PeerStats
.timeouts
++;
613 psstate
->ping
.timedout
= 1;
614 peerSelectFoo(psstate
);
620 memset(&PeerStats
, '\0', sizeof(PeerStats
));
621 assert(sizeof(hier_strings
) == (HIER_MAX
+ 1) * sizeof(char *));
625 peerIcpParentMiss(peer
* p
, icp_common_t
* header
, ps_state
* ps
)
630 if (Config
.onoff
.query_icmp
) {
631 if (header
->flags
& ICP_FLAG_SRC_RTT
) {
632 rtt
= header
->pad
& 0xFFFF;
633 hops
= (header
->pad
>> 16) & 0xFFFF;
635 if (rtt
> 0 && rtt
< 0xFFFF)
636 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
638 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
639 ps
->closest_parent_miss
= p
->in_addr
;
640 ps
->ping
.p_rtt
= rtt
;
645 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
646 if (p
->options
.closest_only
)
649 /* set FIRST_MISS if there is no CLOSEST parent */
650 if (!ps
->closest_parent_miss
.IsAnyAddr())
653 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
658 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
659 ps
->first_parent_miss
= p
->in_addr
;
660 ps
->ping
.w_rtt
= rtt
;
665 peerHandleIcpReply(peer
* p
, peer_t type
, icp_common_t
* header
, void *data
)
667 ps_state
*psstate
= (ps_state
*)data
;
668 icp_opcode op
= header
->getOpCode();
669 debugs(44, 3, "peerHandleIcpReply: " << icp_opcode_str
[op
] << " " << psstate
->entry
->url() );
670 #if USE_CACHE_DIGESTS && 0
671 /* do cd lookup to count false misses */
674 peerNoteDigestLookup(request
, p
,
675 peerDigestLookup(p
, request
, psstate
->entry
));
679 psstate
->ping
.n_recv
++;
681 if (op
== ICP_MISS
|| op
== ICP_DECHO
) {
682 if (type
== PEER_PARENT
)
683 peerIcpParentMiss(p
, header
, psstate
);
684 } else if (op
== ICP_HIT
) {
686 psstate
->hit_type
= type
;
687 peerSelectFoo(psstate
);
691 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
694 peerSelectFoo(psstate
);
699 peerHandleHtcpReply(peer
* p
, peer_t type
, htcpReplyData
* htcp
, void *data
)
701 ps_state
*psstate
= (ps_state
*)data
;
702 debugs(44, 3, "peerHandleHtcpReply: " <<
703 (htcp
->hit
? "HIT" : "MISS") << " " <<
704 psstate
->entry
->url() );
705 psstate
->ping
.n_recv
++;
709 psstate
->hit_type
= type
;
710 peerSelectFoo(psstate
);
714 if (type
== PEER_PARENT
)
715 peerHtcpParentMiss(p
, htcp
, psstate
);
717 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
720 peerSelectFoo(psstate
);
724 peerHtcpParentMiss(peer
* p
, htcpReplyData
* htcp
, ps_state
* ps
)
729 if (Config
.onoff
.query_icmp
) {
730 if (htcp
->cto
.rtt
> 0) {
731 rtt
= (int) htcp
->cto
.rtt
* 1000;
732 hops
= (int) htcp
->cto
.hops
* 1000;
733 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
735 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
736 ps
->closest_parent_miss
= p
->in_addr
;
737 ps
->ping
.p_rtt
= rtt
;
742 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
743 if (p
->options
.closest_only
)
746 /* set FIRST_MISS if there is no CLOSEST parent */
747 if (!ps
->closest_parent_miss
.IsAnyAddr())
750 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
755 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
756 ps
->first_parent_miss
= p
->in_addr
;
757 ps
->ping
.w_rtt
= rtt
;
764 peerHandlePingReply(peer
* p
, peer_t type
, protocol_t proto
, void *pingdata
, void *data
)
766 if (proto
== PROTO_ICP
)
767 peerHandleIcpReply(p
, type
, (icp_common_t
*)pingdata
, data
);
771 else if (proto
== PROTO_HTCP
)
772 peerHandleHtcpReply(p
, type
, (htcpReplyData
*)pingdata
, data
);
777 debugs(44, 1, "peerHandlePingReply: unknown protocol_t " << proto
);
781 peerAddFwdServer(FwdServer
** FSVR
, peer
* p
, hier_code code
)
783 FwdServer
*fs
= (FwdServer
*)memAllocate(MEM_FWD_SERVER
);
784 debugs(44, 5, "peerAddFwdServer: adding " <<
785 (p
? p
->host
: "DIRECT") << " " <<
786 hier_strings
[code
] );
787 fs
->_peer
= cbdataReference(p
);
791 FSVR
= &(*FSVR
)->next
;
797 ps_state::operator new(size_t)
799 CBDATA_INIT_TYPE(ps_state
);
800 return cbdataAlloc(ps_state
);
803 ps_state::ps_state() : request (NULL
),
809 callback_data (NULL
),
812 closest_parent_miss(),
817 ; // no local defaults.
820 ping_data::ping_data() :
823 n_replies_expected(0),