2 * $Id: peer_select.cc,v 1.148 2007/12/14 23:11:47 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",
80 static const char *DirectStr
[] =
88 static void peerSelectFoo(ps_state
*);
89 static void peerPingTimeout(void *data
);
90 static void peerSelectCallback(ps_state
* psstate
);
91 static IRCB peerHandlePingReply
;
92 static void peerSelectStateFree(ps_state
* psstate
);
93 static void peerIcpParentMiss(peer
*, icp_common_t
*, ps_state
*);
95 static void peerHtcpParentMiss(peer
*, htcpReplyData
*, ps_state
*);
96 static void peerHandleHtcpReply(peer
*, peer_t
, htcpReplyData
*, void *);
98 static int peerCheckNetdbDirect(ps_state
* psstate
);
99 static void peerGetSomeNeighbor(ps_state
*);
100 static void peerGetSomeNeighborReplies(ps_state
*);
101 static void peerGetSomeDirect(ps_state
*);
102 static void peerGetSomeParent(ps_state
*);
103 static void peerGetAllParents(ps_state
*);
104 static void peerAddFwdServer(FwdServer
**, peer
*, hier_code
);
106 CBDATA_CLASS_INIT(ps_state
);
109 peerSelectStateFree(ps_state
* psstate
)
111 if (psstate
->acl_checklist
) {
112 debugs(44, 1, "calling aclChecklistFree() from peerSelectStateFree");
113 delete (psstate
->acl_checklist
);
116 HTTPMSGUNLOCK(psstate
->request
);
118 if (psstate
->entry
) {
119 assert(psstate
->entry
->ping_status
!= PING_WAITING
);
120 psstate
->entry
->unlock();
121 psstate
->entry
= NULL
;
128 peerSelectIcpPing(HttpRequest
* request
, int direct
, StoreEntry
* entry
)
132 assert(entry
->ping_status
== PING_NONE
);
133 assert(direct
!= DIRECT_YES
);
134 debugs(44, 3, "peerSelectIcpPing: " << entry
->url() );
136 if (!request
->flags
.hierarchical
&& direct
!= DIRECT_NO
)
139 if (EBIT_TEST(entry
->flags
, KEY_PRIVATE
) && !neighbors_do_private_keys
)
140 if (direct
!= DIRECT_NO
)
143 n
= neighborsCount(request
);
145 debugs(44, 3, "peerSelectIcpPing: counted " << n
<< " neighbors");
152 peerSelect(HttpRequest
* request
,
160 debugs(44, 3, "peerSelect: " << entry
->url() );
162 debugs(44, 3, "peerSelect: " << RequestMethodStr
[request
->method
]);
164 psstate
= new ps_state
;
166 psstate
->request
= HTTPMSGLOCK(request
);
168 psstate
->entry
= entry
;
170 psstate
->callback
= callback
;
172 psstate
->callback_data
= cbdataReference(callback_data
);
174 psstate
->direct
= DIRECT_UNKNOWN
;
176 #if USE_CACHE_DIGESTS
178 request
->hier
.peer_select_start
= current_time
;
183 psstate
->entry
->lock();
185 peerSelectFoo(psstate
);
189 peerCheckNeverDirectDone(int answer
, void *data
)
191 ps_state
*psstate
= (ps_state
*) data
;
192 psstate
->acl_checklist
= NULL
;
193 debugs(44, 3, "peerCheckNeverDirectDone: " << answer
);
194 psstate
->never_direct
= answer
? 1 : -1;
195 peerSelectFoo(psstate
);
199 peerCheckAlwaysDirectDone(int answer
, void *data
)
201 ps_state
*psstate
= (ps_state
*)data
;
202 psstate
->acl_checklist
= NULL
;
203 debugs(44, 3, "peerCheckAlwaysDirectDone: " << answer
);
204 psstate
->always_direct
= answer
? 1 : -1;
205 peerSelectFoo(psstate
);
209 peerSelectCallback(ps_state
* psstate
)
211 StoreEntry
*entry
= psstate
->entry
;
212 FwdServer
*fs
= psstate
->servers
;
217 debugs(44, 3, "peerSelectCallback: " << entry
->url() );
219 if (entry
->ping_status
== PING_WAITING
)
220 eventDelete(peerPingTimeout
, psstate
);
222 entry
->ping_status
= PING_DONE
;
226 debugs(44, 1, "Failed to select source for '" << entry
->url() << "'" );
227 debugs(44, 1, " always_direct = " << psstate
->always_direct
);
228 debugs(44, 1, " never_direct = " << psstate
->never_direct
);
229 debugs(44, 1, " timedout = " << psstate
->ping
.timedout
);
232 psstate
->ping
.stop
= current_time
;
233 psstate
->request
->hier
.ping
= psstate
->ping
;
234 callback
= psstate
->callback
;
235 psstate
->callback
= NULL
;
237 if (cbdataReferenceValidDone(psstate
->callback_data
, &cbdata
)) {
238 psstate
->servers
= NULL
;
239 callback(fs
, cbdata
);
242 peerSelectStateFree(psstate
);
246 peerCheckNetdbDirect(ps_state
* psstate
)
252 if (psstate
->direct
== DIRECT_NO
)
255 myrtt
= netdbHostRtt(psstate
->request
->GetHost());
257 debugs(44, 3, "peerCheckNetdbDirect: MY RTT = " << myrtt
<< " msec");
258 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_rtt = " << Config
.minDirectRtt
<< " msec");
261 if (myrtt
&& myrtt
<= Config
.minDirectRtt
)
264 myhops
= netdbHostHops(psstate
->request
->GetHost());
266 debugs(44, 3, "peerCheckNetdbDirect: MY hops = " << myhops
);
267 debugs(44, 3, "peerCheckNetdbDirect: minimum_direct_hops = " << Config
.minDirectHops
);
270 if (myhops
&& myhops
<= Config
.minDirectHops
)
273 p
= whichPeer(psstate
->closest_parent_miss
);
278 debugs(44, 3, "peerCheckNetdbDirect: closest_parent_miss RTT = " << psstate
->ping
.p_rtt
<< " msec");
280 if (myrtt
&& myrtt
<= psstate
->ping
.p_rtt
)
287 peerSelectFoo(ps_state
* ps
)
289 StoreEntry
*entry
= ps
->entry
;
290 HttpRequest
*request
= ps
->request
;
291 debugs(44, 3, "peerSelectFoo: '" << RequestMethodStr
[request
->method
] << " " << request
->GetHost() << "'");
293 if (ps
->direct
== DIRECT_UNKNOWN
) {
294 if (ps
->always_direct
== 0 && Config
.accessList
.AlwaysDirect
) {
295 ps
->acl_checklist
= aclChecklistCreate(
296 Config
.accessList
.AlwaysDirect
,
299 ps
->acl_checklist
->nonBlockingCheck(peerCheckAlwaysDirectDone
,
302 } else if (ps
->always_direct
> 0) {
303 ps
->direct
= DIRECT_YES
;
304 } else if (ps
->never_direct
== 0 && Config
.accessList
.NeverDirect
) {
305 ps
->acl_checklist
= aclChecklistCreate(
306 Config
.accessList
.NeverDirect
,
309 ps
->acl_checklist
->nonBlockingCheck(peerCheckNeverDirectDone
,
312 } else if (ps
->never_direct
> 0) {
313 ps
->direct
= DIRECT_NO
;
314 } else if (request
->flags
.accelerated
) {
315 ps
->direct
= DIRECT_NO
;
316 } else if (request
->flags
.loopdetect
) {
317 ps
->direct
= DIRECT_YES
;
318 } else if (peerCheckNetdbDirect(ps
)) {
319 ps
->direct
= DIRECT_YES
;
321 ps
->direct
= DIRECT_MAYBE
;
324 debugs(44, 3, "peerSelectFoo: direct = " << DirectStr
[ps
->direct
]);
329 } else if (entry
->ping_status
== PING_NONE
) {
330 peerGetSomeNeighbor(ps
);
332 if (entry
->ping_status
== PING_WAITING
)
334 } else if (entry
->ping_status
== PING_WAITING
) {
335 peerGetSomeNeighborReplies(ps
);
336 entry
->ping_status
= PING_DONE
;
339 switch (ps
->direct
) {
342 peerGetSomeDirect(ps
);
346 peerGetSomeParent(ps
);
347 peerGetAllParents(ps
);
352 if (Config
.onoff
.prefer_direct
)
353 peerGetSomeDirect(ps
);
355 if (request
->flags
.hierarchical
|| !Config
.onoff
.nonhierarchical_direct
)
356 peerGetSomeParent(ps
);
358 if (!Config
.onoff
.prefer_direct
)
359 peerGetSomeDirect(ps
);
364 peerSelectCallback(ps
);
368 * peerGetSomeNeighbor
370 * Selects a neighbor (parent or sibling) based on one of the
374 * Netdb RTT estimates
378 peerGetSomeNeighbor(ps_state
* ps
)
380 StoreEntry
*entry
= ps
->entry
;
381 HttpRequest
*request
= ps
->request
;
383 hier_code code
= HIER_NONE
;
384 assert(entry
->ping_status
== PING_NONE
);
386 if (ps
->direct
== DIRECT_YES
) {
387 entry
->ping_status
= PING_DONE
;
391 #if USE_CACHE_DIGESTS
392 if ((p
= neighborsDigestSelect(request
))) {
393 if (neighborType(p
, request
) == PEER_PARENT
)
394 code
= CD_PARENT_HIT
;
396 code
= CD_SIBLING_HIT
;
399 if ((p
= netdbClosestParent(request
))) {
400 code
= CLOSEST_PARENT
;
401 } else if (peerSelectIcpPing(request
, ps
->direct
, entry
)) {
402 debugs(44, 3, "peerSelect: Doing ICP pings");
403 ps
->ping
.start
= current_time
;
404 ps
->ping
.n_sent
= neighborsUdpPing(request
,
408 &ps
->ping
.n_replies_expected
,
411 if (ps
->ping
.n_sent
== 0)
412 debugs(44, 0, "WARNING: neighborsUdpPing returned 0");
413 debugs(44, 3, "peerSelect: " << ps
->ping
.n_replies_expected
<<
414 " ICP replies expected, RTT " << ps
->ping
.timeout
<<
418 if (ps
->ping
.n_replies_expected
> 0) {
419 entry
->ping_status
= PING_WAITING
;
420 eventAdd("peerPingTimeout",
423 0.001 * ps
->ping
.timeout
,
429 if (code
!= HIER_NONE
) {
431 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
432 peerAddFwdServer(&ps
->servers
, p
, code
);
435 entry
->ping_status
= PING_DONE
;
439 * peerGetSomeNeighborReplies
441 * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
444 peerGetSomeNeighborReplies(ps_state
* ps
)
446 HttpRequest
*request
= ps
->request
;
448 hier_code code
= HIER_NONE
;
449 assert(ps
->entry
->ping_status
== PING_WAITING
);
450 assert(ps
->direct
!= DIRECT_YES
);
452 if (peerCheckNetdbDirect(ps
)) {
453 code
= CLOSEST_DIRECT
;
454 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << request
->GetHost());
455 peerAddFwdServer(&ps
->servers
, NULL
, code
);
460 code
= ps
->hit_type
== PEER_PARENT
? PARENT_HIT
: SIBLING_HIT
;
463 if (!ps
->closest_parent_miss
.IsAnyAddr()) {
464 p
= whichPeer(ps
->closest_parent_miss
);
465 code
= CLOSEST_PARENT_MISS
;
466 } else if (!ps
->first_parent_miss
.IsAnyAddr()) {
467 p
= whichPeer(ps
->first_parent_miss
);
468 code
= FIRST_PARENT_MISS
;
471 if (p
&& code
!= HIER_NONE
) {
472 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
473 peerAddFwdServer(&ps
->servers
, p
, code
);
481 * Simply adds a 'direct' entry to the FwdServers list if this
482 * request can be forwarded directly to the origin server
485 peerGetSomeDirect(ps_state
* ps
)
487 if (ps
->direct
== DIRECT_NO
)
490 /* WAIS is not implemented natively */
491 if (ps
->request
->protocol
== PROTO_WAIS
)
494 peerAddFwdServer(&ps
->servers
, NULL
, HIER_DIRECT
);
498 peerGetSomeParent(ps_state
* ps
)
501 HttpRequest
*request
= ps
->request
;
502 hier_code code
= HIER_NONE
;
503 debugs(44, 3, "peerGetSomeParent: " << RequestMethodStr
[request
->method
] << " " << request
->GetHost());
505 if (ps
->direct
== DIRECT_YES
)
508 if ((p
= getDefaultParent(request
))) {
509 code
= DEFAULT_PARENT
;
512 } else if ((p
= carpSelectParent(request
))) {
516 } else if ((p
= getRoundRobinParent(request
))) {
517 code
= ROUNDROBIN_PARENT
;
518 } else if ((p
= getWeightedRoundRobinParent(request
))) {
519 code
= ROUNDROBIN_PARENT
;
520 } else if ((p
= getFirstUpParent(request
))) {
521 code
= FIRSTUP_PARENT
;
522 } else if ((p
= getAnyParent(request
))) {
523 code
= ANY_OLD_PARENT
;
526 if (code
!= HIER_NONE
) {
527 debugs(44, 3, "peerSelect: " << hier_strings
[code
] << "/" << p
->host
);
528 peerAddFwdServer(&ps
->servers
, p
, code
);
532 /* Adds alive parents. Used as a last resort for never_direct.
535 peerGetAllParents(ps_state
* ps
)
538 HttpRequest
*request
= ps
->request
;
539 /* Add all alive parents */
541 for (p
= Config
.peers
; p
; p
= p
->next
) {
542 /* XXX: neighbors.c lacks a public interface for enumerating
543 * parents to a request so we have to dig some here..
546 if (neighborType(p
, request
) != PEER_PARENT
)
549 if (!peerHTTPOkay(p
, request
))
552 debugs(15, 3, "peerGetAllParents: adding alive parent " << p
->host
);
554 peerAddFwdServer(&ps
->servers
, p
, ANY_OLD_PARENT
);
557 /* XXX: should add dead parents here, but it is currently
558 * not possible to find out which parents are dead or which
559 * simply are not configured to handle the request.
561 /* Add default parent as a last resort */
562 if ((p
= getDefaultParent(request
))) {
563 peerAddFwdServer(&ps
->servers
, p
, DEFAULT_PARENT
);
568 peerPingTimeout(void *data
)
570 ps_state
*psstate
= (ps_state
*)data
;
571 StoreEntry
*entry
= psstate
->entry
;
574 debugs(44, 3, "peerPingTimeout: '" << entry
->url() << "'" );
576 if (!cbdataReferenceValid(psstate
->callback_data
)) {
577 /* request aborted */
578 entry
->ping_status
= PING_DONE
;
579 cbdataReferenceDone(psstate
->callback_data
);
580 peerSelectStateFree(psstate
);
584 PeerStats
.timeouts
++;
585 psstate
->ping
.timedout
= 1;
586 peerSelectFoo(psstate
);
592 memset(&PeerStats
, '\0', sizeof(PeerStats
));
593 assert(sizeof(hier_strings
) == (HIER_MAX
+ 1) * sizeof(char *));
597 peerIcpParentMiss(peer
* p
, icp_common_t
* header
, ps_state
* ps
)
602 if (Config
.onoff
.query_icmp
) {
603 if (header
->flags
& ICP_FLAG_SRC_RTT
) {
604 rtt
= header
->pad
& 0xFFFF;
605 hops
= (header
->pad
>> 16) & 0xFFFF;
607 if (rtt
> 0 && rtt
< 0xFFFF)
608 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
610 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
611 ps
->closest_parent_miss
= p
->in_addr
;
612 ps
->ping
.p_rtt
= rtt
;
617 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
618 if (p
->options
.closest_only
)
621 /* set FIRST_MISS if there is no CLOSEST parent */
622 if (!ps
->closest_parent_miss
.IsAnyAddr())
625 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
630 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
631 ps
->first_parent_miss
= p
->in_addr
;
632 ps
->ping
.w_rtt
= rtt
;
637 peerHandleIcpReply(peer
* p
, peer_t type
, icp_common_t
* header
, void *data
)
639 ps_state
*psstate
= (ps_state
*)data
;
640 icp_opcode op
= header
->getOpCode();
641 debugs(44, 3, "peerHandleIcpReply: " << icp_opcode_str
[op
] << " " << psstate
->entry
->url() );
642 #if USE_CACHE_DIGESTS && 0
643 /* do cd lookup to count false misses */
646 peerNoteDigestLookup(request
, p
,
647 peerDigestLookup(p
, request
, psstate
->entry
));
651 psstate
->ping
.n_recv
++;
653 if (op
== ICP_MISS
|| op
== ICP_DECHO
) {
654 if (type
== PEER_PARENT
)
655 peerIcpParentMiss(p
, header
, psstate
);
656 } else if (op
== ICP_HIT
) {
658 psstate
->hit_type
= type
;
659 peerSelectFoo(psstate
);
663 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
666 peerSelectFoo(psstate
);
671 peerHandleHtcpReply(peer
* p
, peer_t type
, htcpReplyData
* htcp
, void *data
)
673 ps_state
*psstate
= (ps_state
*)data
;
674 debugs(44, 3, "peerHandleHtcpReply: " <<
675 (htcp
->hit
? "HIT" : "MISS") << " " <<
676 psstate
->entry
->url() );
677 psstate
->ping
.n_recv
++;
681 psstate
->hit_type
= type
;
682 peerSelectFoo(psstate
);
686 if (type
== PEER_PARENT
)
687 peerHtcpParentMiss(p
, htcp
, psstate
);
689 if (psstate
->ping
.n_recv
< psstate
->ping
.n_replies_expected
)
692 peerSelectFoo(psstate
);
696 peerHtcpParentMiss(peer
* p
, htcpReplyData
* htcp
, ps_state
* ps
)
701 if (Config
.onoff
.query_icmp
) {
702 if (htcp
->cto
.rtt
> 0) {
703 rtt
= (int) htcp
->cto
.rtt
* 1000;
704 hops
= (int) htcp
->cto
.hops
* 1000;
705 netdbUpdatePeer(ps
->request
, p
, rtt
, hops
);
707 if (rtt
&& (ps
->ping
.p_rtt
== 0 || rtt
< ps
->ping
.p_rtt
)) {
708 ps
->closest_parent_miss
= p
->in_addr
;
709 ps
->ping
.p_rtt
= rtt
;
714 /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
715 if (p
->options
.closest_only
)
718 /* set FIRST_MISS if there is no CLOSEST parent */
719 if (!ps
->closest_parent_miss
.IsAnyAddr())
722 rtt
= (tvSubMsec(ps
->ping
.start
, current_time
) - p
->basetime
) / p
->weight
;
727 if (ps
->first_parent_miss
.IsAnyAddr() || rtt
< ps
->ping
.w_rtt
) {
728 ps
->first_parent_miss
= p
->in_addr
;
729 ps
->ping
.w_rtt
= rtt
;
736 peerHandlePingReply(peer
* p
, peer_t type
, protocol_t proto
, void *pingdata
, void *data
)
738 if (proto
== PROTO_ICP
)
739 peerHandleIcpReply(p
, type
, (icp_common_t
*)pingdata
, data
);
743 else if (proto
== PROTO_HTCP
)
744 peerHandleHtcpReply(p
, type
, (htcpReplyData
*)pingdata
, data
);
749 debugs(44, 1, "peerHandlePingReply: unknown protocol_t " << proto
);
753 peerAddFwdServer(FwdServer
** FSVR
, peer
* p
, hier_code code
)
755 FwdServer
*fs
= (FwdServer
*)memAllocate(MEM_FWD_SERVER
);
756 debugs(44, 5, "peerAddFwdServer: adding " <<
757 (p
? p
->host
: "DIRECT") << " " <<
758 hier_strings
[code
] );
759 fs
->_peer
= cbdataReference(p
);
763 FSVR
= &(*FSVR
)->next
;
769 ps_state::operator new(size_t)
771 CBDATA_INIT_TYPE(ps_state
);
772 return cbdataAlloc(ps_state
);
775 ps_state::ps_state() : request (NULL
),
781 callback_data (NULL
),
784 closest_parent_miss(),
789 ; // no local defaults.
792 ping_data::ping_data() :
795 n_replies_expected(0),