For this section, we'll examine the neighbour selection algorithm in detail by running through two functions from the Squid source code. Knowledge of C is not necessarily required.
There are two primary functions to examine.
First, Squid calls protoDispatch()
for all requests to decide if the URL's IP address must
be learned.
If not, Squid calls the second function,
protoDispatchDNSHandle() directly. If it does need
to look up the address, then protoDispatchDNSHandle()
is called when the lookup completes.
Note that these functions have evolved considerably since the first Squid versions. As bugs have been pointed out, the code has been rearranged and rewritten in an attempt to accommodate everyone's needs.
First we examine protoDispatch():
343 protoData->inside_firewall = matchInsideFirewall(request->host);
344 protoData->hierarchical = BIT_TEST(entry->flag, HIERARCHICAL) ? 1 : 0;
345 protoData->single_parent = getSingleParent(request);
346 protoData->default_parent = getDefaultParent(request);
347 protoData->n_peers = neighboursCount(request);
Here we are assigning some variables for future reference. We
check if the origin server is inside our firewall (based only on the
domain names listed with inside_firewall). The request is
`hierarchical' if it does not match the hierarchy_stoplist,
and if the request method is GET. The `single_parent' will
be set if the only peer to which this request could be
forwarded is a parent cache. Similarly, the `default_parent' will
be set to the first parent cache found with the default flag set.
The `n_peers' variable indicates how many neighbour caches would
be queried if we decide to use ICP later on. Note that
getSingleParent(),
getDefaultParent(),
and neighboursCount()
all use the domain restrictions (i.e. cache_host_domain).
386 if (Config.firewall_ip_list) {
387 /* Have to look up the url address so we can compare it */
388 protoData->source_ping = Config.sourcePing;
389 protoData->direct_fetch = DIRECT_MAYBE;
390 protoData->ip_lookup_pending = 1;
391 ipcache_nbgethostbyname(request->host,
392 fd,
393 protoDispatchDNSHandle,
394 (void *) protoData);
The firewall configuration takes precedence over everything else.
First we see if the firewall_ip directive is configured. If so,
then we need to translate the URL hostname into an address before going
any further. At this point we're not sure if we can directly connect
to the origin server, so we set `direct_fetch' to maybe. The
neighbour selection process will continue in the
protoDispatchDNSHandle() function when the DNS lookup completes.
395 } else if (!protoData->inside_firewall) {
396 /* There are firewall restrictions, and this host is outside. */
397 /* No DNS lookups, call protoDispatchDNSHandle() directly */
398 protoData->source_ping = 0;
399 protoData->direct_fetch = DIRECT_NO;
400 protoDispatchDNSHandle(fd,
401 NULL,
402 (void *) protoData);
If we have reached this code segment then
there is no firewall_ip list, but
inside_firewall may still be configured.
If we know the request is not inside the firewall, then
we cannot contact the origin server directly. We must forward the
request to a neighbour cache. We do not need to look up the
IP address from the domain name. We call protoDispatchDNSHandle()
directly to continue the process.
403 } else if (matchLocalDomain(request->host) || !protoData->hierarchical) {
404 /* will fetch from source */
405 protoData->direct_fetch = DIRECT_YES;
406 protoData->ip_lookup_pending = 1;
407 ipcache_nbgethostbyname(request->host,
408 fd,
409 protoDispatchDNSHandle,
410 (void *) protoData);
If the request matches the local_domain list, or if this is a non-hierarchical request, we will connect to the origin server directly. First we look up the IP address.
411 } else if (protoData->n_peers == 0) {
412 /* will fetch from source */
413 protoData->direct_fetch = DIRECT_YES;
414 protoData->ip_lookup_pending = 1;
415 ipcache_nbgethostbyname(request->host,
416 fd,
417 protoDispatchDNSHandle,
418 (void *) protoData);
Recall that above we counted the number of neighbours that we would query. If the result is zero, then we will directly connect to the origin server. The `n_peers' value will be zero if the domain restrictions do not yield any appropriate neighbours for this request, or if Squid thinks the neighbour caches are down. Below we describe how Squid decides if a neighbour is down.
419 } else if (Config.local_ip_list) {
420 /* Have to look up the url address so we can compare it */
421 protoData->source_ping = Config.sourcePing;
422 protoData->direct_fetch = DIRECT_MAYBE;
423 protoData->ip_lookup_pending = 1;
424 ipcache_nbgethostbyname(request->host,
425 fd,
426 protoDispatchDNSHandle,
427 (void *) protoData);
Here we check the local_ip_list, if defined. Before calling
protoDispatchDNSHandle() we need to look up the IP address.
428 } else if (protoData->single_parent && Config.singleParentBypass &&
429 !(protoData->source_ping = Config.sourcePing)) {
430 /* will fetch from single parent */
431 protoData->direct_fetch = DIRECT_MAYBE;
432 protoDispatchDNSHandle(fd,
433 NULL,
434 (void *) protoData);
Here we look for the opportunity to use the `single parent' optimization.
In order for this to be used, the only peer to which this request
can be forwarded must be a parent, and the single_parent_bypass
configuration option must be enabled. Additionally, we will
not use this optimization if the source_ping feature is enabled.
If these three conditions are true, we do not need to look up the
IP address, so Squid calls protoDispatchDNSHandle() directly.
435 } else {
436 /* will use ping resolution */
437 protoData->source_ping = Config.sourcePing;
438 protoData->direct_fetch = DIRECT_MAYBE;
439 protoData->ip_lookup_pending = 1;
440 ipcache_nbgethostbyname(request->host,
441 fd,
442 protoDispatchDNSHandle,
443 (void *) protoData);
444 }
Finally, the last option is to query our neighbour caches with ICP.
This decision actually occurs in protoDispatchDNSHandle(), but we need
to look up the IP address here just in the event that we'll
contact the origin server later on.
Now we examine the protoDispatchDNSHandle() function,
called after completion (successful or failed) of the IP address
lookup, or if the lookup is unnecessary.
186 if (protoData->direct_fetch == DIRECT_YES) {
187 if (ia == NULL) {
188 protoDNSError(protoData->fd, entry);
189 return;
190 }
191 hierarchyNote(req, HIER_DIRECT, 0, req->host);
192 protoStart(protoData->fd, entry, NULL, req);
193 return;
194 }
The variable `ia' holds the result of the DNS lookup.
If we are supposed to directly connect to the origin server,
and if the DNS lookup failed (indicated by `ia' being equal to NULL),
then we cannot forward this request. If the DNS lookup was
successful, then we call protoStart() to start the
process of connecting to the server.
195 if (protoData->direct_fetch == DIRECT_MAYBE
196 && (Config.local_ip_list || Config.firewall_ip_list)) {
197 if (ia == NULL) {
198 debug(17, 3, "Unknown host: %s\n", req->host);
199 protoData->direct_fetch = DIRECT_NO;
200 } else if (Config.firewall_ip_list) {
201 srv_addr = ia->in_addrs[ia->cur];
202 if (ip_access_check(srv_addr, Config.firewall_ip_list) == IP_DENY) {
203 hierarchyNote(req, HIER_FIREWALL_IP_DIRECT, 0, req->host);
204 protoStart(protoData->fd, entry, NULL, req);
205 return;
206 } else {
215 protoData->direct_fetch = DIRECT_NO;
217 }
218 } else if (Config.local_ip_list) {
219 srv_addr = ia->in_addrs[ia->cur];
220 if (ip_access_check(srv_addr, Config.local_ip_list) == IP_DENY) {
221 hierarchyNote(req, HIER_LOCAL_IP_DIRECT, 0, req->host);
222 protoStart(protoData->fd, entry, NULL, req);
223 return;
224 }
225 }
226 }
This is where we check the origin server's IP address against the firewall_ip and local_ip lists. If the DNS lookup failed, then we set `direct_fetch' to no which requires that this request be forwarded to a neighbour cache if at all possible.
Otherwise, we first check the firewall_ip list. If the address matches the list then the origin server is inside the firewall, in which case we will make a direct connection. The firewall_ip list must be exhaustive. That is, if the IP address does not match the list, Squid assumes that the origin server is on the other side of the firewall. Again we set `direct_fetch' to no to require use of a neighbour cache.
If the address matches the local_ip list then we'll contact the origin server directly. If not, we continue:
227 if ((e = protoData->single_parent) && Config.singleParentBypass) {
228 /* Don't execute this block simply because direct == NO, we
229 * might have some DOWN peers and still need to ping them */
230 /* Only one parent for this host, and okay to skip pinging stuff */
231 hierarchyNote(req, HIER_SINGLE_PARENT, 0, e->host);
232 protoStart(protoData->fd, entry, e, req);
233 return;
234 }
Above we're using the single parent optimization if possible.
235 if (protoData->n_peers == 0 && protoData->direct_fetch == DIRECT_NO) {
236 if ((e = protoData->default_parent)) {
237 hierarchyNote(req, HIER_DEFAULT_PARENT, 0, e->host);
238 protoStart(protoData->fd, entry, e, req);
239 } else if ((e = getFirstUpParent(protoData->request))) {
240 hierarchyNote(req, HIER_FIRSTUP_PARENT, 0, e->host);
241 protoStart(protoData->fd, entry, e, req);
242 } else {
243 hierarchyNote(req, HIER_NO_DIRECT_FAIL, 0, req->host);
244 protoCantFetchObject(protoData->fd,
245 entry,
246 "No peers to query"
247 " and the host is beyond your firewall.");
248 }
249 return;
250 }
Above, we have reached a code point where we cannot connect directly to the origin server, and there are no neighbours to query (`n_peers' == 0), so we must select a suitable parent cache. First we try a default parent. If one is not available, we'll take the first parent cache which Squid believes to be up. Otherwise, we generate an error message.
251 if (!neighbours_do_private_keys && !protoData->hierarchical &&
252 (e = getFirstUpParent(req))) {
253 /* for private objects we should just fetch directly (because
254 * icpHandleUdp() won't properly deal with the ICP replies). */
255 hierarchyNote(req, HIER_FIRSTUP_PARENT, 0, e->host);
256 protoStart(protoData->fd, entry, e, req);
257 return;
This section of code Squid hopefully never uses anymore; it is called only when one of the neighbour caches does not support `private keys'. Squid can not use private keys if one of its neighbours is a Harvest-1.4 (or earlier) cache. Harvest-1.4 does not properly support the ICP Reqnum field which enables Squid to implement private cache keys.
258 } else if (protoData->direct_fetch == DIRECT_MAYBE && ia
259 && netdbHops(ia->in_addrs[ia->cur]) <= Config.minDirectHops) {
260 hierarchyNote(req, HIER_DIRECT, 0, req->host);
261 protoStart(protoData->fd, entry, NULL, req);
262 return;
This is where we check the minimum_direct_hops parameter. If our estimated hops is less than or equal to this value, then we forward the request directly and skip any ICP queries.
263 } else if (neighboursUdpPing(protoData)) {
264 /* call neighbourUdpPing and start timeout routine */
265 if (entry->ping_status != PING_NONE)
266 fatal_dump("protoDispatchDNSHandle: bad ping_status");
268 entry->ping_status = PING_WAITING;
269 commSetSelect(protoData->fd,
270 COMM_SELECT_TIMEOUT,
271 (PF) getFromDefaultSource,
272 (void *) entry,
273 Config.neighbourTimeout);
278 return;
279 }
Here we call the routine which sends ICP queries. If neighboursUdpPing()
returns zero, then it didn't really send any queries and we should continue
execution of this function. Also note that here we start the
two-second neighbour_timeout alarm.
280 if ((e = protoData->default_parent)) {
281 hierarchyNote(req, HIER_DEFAULT_PARENT, 0, e->host);
282 protoStart(protoData->fd, entry, e, req);
283 } else if ((e = getRoundRobinParent(req))) {
284 hierarchyNote(req, HIER_ROUNDROBIN_PARENT, 0, e->host);
285 protoStart(protoData->fd, entry, e, req);
If we reach this far, then we have not sent any ICP queries and it is time for desperate selection of an appropriate next-hop cache. If a default parent is defined, we'll take it. Otherwise, if a round-robin parent is defined we'll take that instead.
286 } else if (protoData->direct_fetch == DIRECT_NO) {
287 hierarchyNote(req, HIER_NO_DIRECT_FAIL, 0, req->host);
288 protoCantFetchObject(protoData->fd, entry,
289 "No neighbours or parents were queried "
290 "and the host is beyond your firewall.");
At this point we have decided that none of the peer caches should receive this request. If we also have decided that this request cannot be forwarded to the origin server directly, then we generate an error message.
291 } else if (ia == NULL) {
292 protoDNSError(protoData->fd, entry);
Here we know that we are allowed to connect to the origin server, but if the IP address lookup has failed, then we must generate an error message.
293 } else {
294 hierarchyNote(req, HIER_DIRECT, 0, req->host);
295 protoStart(protoData->fd, entry, NULL, req);
296 }
297 }
Finally, as a last resort, we have chosen to forward the request directly
to the origin server and we have an IP address for it, so off we
go with protoStart().
Squid tracks the reachability status of its neighbour caches. When using ICP, Squid marks a neighbour as down when the neighbour fails to reply to 20 consecutive ICP queries. As soon as a reply is received again, the neighbour is marked up.
In addition to ICP, Squid also monitors TCP connections. When a TCP connection to a neighbour fails, Squid marks the neighbour down and begins a process to periodically (every 80 seconds) retry a diagnostic TCP connection. When the diagnostic connection succeeds, the neighbour is marked up.
So, in order for Squid to consider a neighbour cache as up, these two conditions must be true: