[thirdparty/squid.git] / src / peer_select.cc


/*
 * $Id: peer_select.cc,v 1.46 1998/04/08 19:28:48 wessels Exp $
 *
 * DEBUG: section 44    Peer Selection Algorithm
 * AUTHOR: Duane Wessels
 *
 * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
 * --------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from the
 *  Internet community.  Development is led by Duane Wessels of the
 *  National Laboratory for Applied Network Research and funded by
 *  the National Science Foundation.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *  
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *  
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *  
 */

#include "squid.h"

const char *hier_strings[] =
{
    "NONE",
    "DIRECT",
    "SIBLING_HIT",
    "PARENT_HIT",
    "DEFAULT_PARENT",
    "SINGLE_PARENT",
    "FIRST_UP_PARENT",
    "NO_PARENT_DIRECT",
    "FIRST_PARENT_MISS",
    "CLOSEST_PARENT_MISS",
    "CLOSEST_DIRECT",
    "NO_DIRECT_FAIL",
    "SOURCE_FASTEST",
    "ROUNDROBIN_PARENT",
#if SQUID_PEER_DIGEST
    "CACHE_DIGEST_HIT",
#endif
    "INVALID CODE"
};

static struct {
    int timeouts;
} PeerStats;

static char *DirectStr[] =
{
    "DIRECT_NO",
    "DIRECT_MAYBE",
    "DIRECT_YES"
};

static void peerSelectFoo(ps_state *);
static void peerSelectCheckAS(ps_state *);
static void peerPingTimeout(void *data);
static void peerSelectCallbackFail(ps_state * psstate);
static IRCB peerHandleIcpReply;
static IPH peerSelectCheckASDone;
static void peerSelectStateFree(ps_state * psstate);
static void peerIcpParentMiss(peer *, icp_common_t *, ps_state *);
static int peerCheckNetdbDirect(ps_state * psstate);

static void
peerSelectStateFree(ps_state * psstate)
{
    if (psstate->acl_checklist) {
	debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
	aclChecklistFree(psstate->acl_checklist);
    }
    requestUnlink(psstate->request);
    psstate->request = NULL;
    cbdataFree(psstate);
}

int
peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
{
    int n;
    if (entry == NULL)
	return 0;
    debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
    if (entry->ping_status != PING_NONE)
	return 0;
    assert(direct != DIRECT_YES);
    if (!EBIT_TEST(entry->flag, HIERARCHICAL) && direct != DIRECT_NO)
	return 0;
    if (EBIT_TEST(entry->flag, KEY_PRIVATE) && !neighbors_do_private_keys)
	if (direct != DIRECT_NO)
	    return 0;
    n = neighborsCount(request);
    debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
    return n;
}


peer *
peerGetSomeParent(request_t * request, hier_code * code)
{
    peer *p;
    debug(44, 3) ("peerGetSomeParent: called.\n");
    if ((p = getDefaultParent(request))) {
	*code = DEFAULT_PARENT;
	return p;
    }
    if ((p = getRoundRobinParent(request))) {
	*code = ROUNDROBIN_PARENT;
	return p;
    }
    if ((p = getFirstUpParent(request))) {
	*code = FIRSTUP_PARENT;
	return p;
    }
    return NULL;
}

void
peerSelect(request_t * request,
    StoreEntry * entry,
    PSC * callback,
    PSC * fail_callback,
    void *callback_data)
{
    ps_state *psstate = xcalloc(1, sizeof(ps_state));
    if (entry)
	debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
    else
	debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
    cbdataAdd(psstate, MEM_NONE);
    psstate->request = requestLink(request);
    psstate->entry = entry;
    psstate->callback = callback;
    psstate->fail_callback = fail_callback;
    psstate->callback_data = callback_data;
    cbdataLock(callback_data);
    peerSelectCheckAS(psstate);
#if SQUID_PEER_DIGEST
    request->hier.peer_select_start = current_time;
#endif
}

static void
peerSelectCheckASDone(const ipcache_addrs * ia, void *data)
{
    ps_state *psstate = data;
    peerSelectFoo(psstate);
}

static void
peerSelectCheckAS(ps_state * psstate)
{
    request_t *request = psstate->request;

/* XXXX Just a quick hack to get the destination address to the 
 * ipcache, because peerSelectIcpPing requires non-blocking ACL
 * check. 
 * We should handle AS acl's differently than cache_host ones.   */

    ipcache_nbgethostbyname(request->host,
	peerSelectCheckASDone,
	psstate);
    return;
}


static void
peerCheckNeverDirectDone(int answer, void *data)
{
    ps_state *psstate = data;
    psstate->acl_checklist = NULL;
    debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
    psstate->never_direct = answer ? 1 : -1;
    peerSelectFoo(psstate);
}

static void
peerCheckAlwaysDirectDone(int answer, void *data)
{
    ps_state *psstate = data;
    psstate->acl_checklist = NULL;
    debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
    psstate->always_direct = answer ? 1 : -1;
    peerSelectFoo(psstate);
}

static void
peerSelectCallback(ps_state * psstate, peer * p)
{
    StoreEntry *entry = psstate->entry;
    void *data = psstate->callback_data;
    if (entry) {
	debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
	if (entry->ping_status == PING_WAITING)
	    eventDelete(peerPingTimeout, psstate);
	entry->ping_status = PING_DONE;
    }
    psstate->icp.stop = current_time;
    if (cbdataValid(data))
	psstate->callback(p, data);
    cbdataUnlock(data);
    peerSelectStateFree(psstate);
}

static void
peerSelectCallbackFail(ps_state * psstate)
{
    request_t *request = psstate->request;
    void *data = psstate->callback_data;
    const char *url = psstate->entry ? storeUrl(psstate->entry) : urlCanonical(request, NULL);
    debug(44, 1) ("Failed to select source for '%s'\n", url);
    debug(44, 1) ("  always_direct = %d\n", psstate->always_direct);
    debug(44, 1) ("   never_direct = %d\n", psstate->never_direct);
    debug(44, 1) ("        timeout = %d\n", psstate->icp.timeout);
    if (cbdataValid(data))
	psstate->fail_callback(NULL, data);
    cbdataUnlock(data);
    peerSelectStateFree(psstate);
    /* XXX When this happens, the client request just hangs */
}

static int
peerCheckNetdbDirect(ps_state * psstate)
{
    peer *p = psstate->closest_parent_miss;
    int myrtt;
    int myhops;
    if (p == NULL)
	return 0;
    myrtt = netdbHostRtt(psstate->request->host);
    debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d\n", myrtt);
    debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d\n",
	psstate->icp.p_rtt);
    if (myrtt && myrtt < psstate->icp.p_rtt)
	return 1;
    myhops = netdbHostHops(psstate->request->host);
    debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
    debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
	Config.minDirectHops);
    if (myhops && myhops <= Config.minDirectHops)
	return 1;
    return 0;
}

static void
peerSelectFoo(ps_state * psstate)
{
    peer *p;
    hier_code code;
    StoreEntry *entry = psstate->entry;
    request_t *request = psstate->request;
    int direct;
    debug(44, 3) ("peerSelectFoo: '%s %s'\n",
	RequestMethodStr[request->method],
	request->host);
    if (psstate->never_direct == 0 && Config.accessList.NeverDirect) {
	psstate->acl_checklist = aclChecklistCreate(
	    Config.accessList.NeverDirect,
	    request,
	    request->client_addr,
	    NULL,		/* user agent */
	    NULL);		/* ident */
	aclNBCheck(psstate->acl_checklist,
	    peerCheckNeverDirectDone,
	    psstate);
	return;
    } else if (psstate->never_direct > 0) {
	direct = DIRECT_NO;
    } else if (psstate->always_direct == 0 && Config.accessList.AlwaysDirect) {
	psstate->acl_checklist = aclChecklistCreate(
	    Config.accessList.AlwaysDirect,
	    request,
	    request->client_addr,
	    NULL,		/* user agent */
	    NULL);		/* ident */
	aclNBCheck(psstate->acl_checklist,
	    peerCheckAlwaysDirectDone,
	    psstate);
	return;
    } else if (psstate->always_direct > 0) {
	direct = DIRECT_YES;
    } else {
	direct = DIRECT_MAYBE;
    }
    debug(44, 3) ("peerSelectFoo: direct = %s\n", DirectStr[direct]);
    if (direct == DIRECT_YES) {
	debug(44, 3) ("peerSelectFoo: DIRECT\n");
	hierarchyNote(&request->hier, DIRECT, &psstate->icp, request->host);
	peerSelectCallback(psstate, NULL);
	return;
    }
    psstate->single_parent = getSingleParent(request);
    if (psstate->single_parent != NULL) {
	debug(44, 3) ("peerSelect: found single parent, skipping ICP query\n");
    } else if (peerSelectIcpPing(request, direct, entry)) {
	assert(entry->ping_status == PING_NONE);
#if SQUID_PEER_DIGEST
	/* always check digests if any */
	/* @?@ optimize: track if there are any digested peers at all (global counter) */
	if (1) {
	    p = neighborsDigestSelect(request, entry);
	    if (p) {
		request->hier.cd_lookup = LOOKUP_HIT;
	    } else
	    if (request->hier.n_choices) {
		request->hier.cd_lookup = LOOKUP_MISS;
	    } else {
		request->hier.cd_lookup = LOOKUP_NONE;
	    }
	    debug(44, 3) ("peerSelect: %s digest lookup: %s choices: %d (%d)\n", 
		p ? p->host : "",
		lookup_t_str[request->hier.cd_lookup],
		request->hier.n_choices, request->hier.n_ichoices);
	}
	/* @?@ TEST: randomly choose a peer selection algorithm */
	if (request->hier.cd_lookup != LOOKUP_NONE && (squid_random() & 1)) {
	    debug(44, 3) ("peerSelect: Using Cache Digest\n");
	    request->hier.alg = PEER_SA_DIGEST;
	    if (request->hier.cd_lookup == LOOKUP_HIT) {
		assert(p);
		code = CACHE_DIGEST_HIT;
		debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
		hierarchyNote(&request->hier, code, &psstate->icp, p->host);
		peerSelectCallback(psstate, NULL);
		return;
	    }
	} else {
	    request->hier.alg = PEER_SA_ICP;
#endif
	    debug(44, 3) ("peerSelect: Doing ICP pings\n");
	    psstate->icp.start = current_time;
	    psstate->icp.n_sent = neighborsUdpPing(request,
		entry,
		peerHandleIcpReply,
		psstate,
		&psstate->icp.n_replies_expected);
	    if (psstate->icp.n_sent == 0)
		debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
	    if (psstate->icp.n_replies_expected > 0) {
		entry->ping_status = PING_WAITING;
		eventAdd("peerPingTimeout",
		    peerPingTimeout,
		    psstate,
		    Config.neighborTimeout);
		return;
	    }
#if SQUID_PEER_DIGEST
	}
#endif
    }
    debug(44, 3) ("peerSelectFoo: After peerSelectIcpPing.\n");
    if (peerCheckNetdbDirect(psstate)) {
	code = CLOSEST_DIRECT;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
	hierarchyNote(&request->hier, code, &psstate->icp, request->host);
	peerSelectCallback(psstate, NULL);
    } else if ((p = psstate->closest_parent_miss) != NULL) {
	code = CLOSEST_PARENT_MISS;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	peerSelectCallback(psstate, p);
    } else if ((p = psstate->first_parent_miss) != NULL) {
	code = FIRST_PARENT_MISS;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	peerSelectCallback(psstate, p);
    } else if ((p = psstate->single_parent)) {
	code = SINGLE_PARENT;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	peerSelectCallback(psstate, p);
    } else if (direct != DIRECT_NO) {
	code = DIRECT;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
	hierarchyNote(&request->hier, code, &psstate->icp, request->host);
	peerSelectCallback(psstate, NULL);
    } else if ((p = peerGetSomeParent(request, &code))) {
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	peerSelectCallback(psstate, p);
    } else {
	code = NO_DIRECT_FAIL;
	hierarchyNote(&request->hier, code, &psstate->icp, NULL);
	peerSelectCallbackFail(psstate);
    }
}

static void
peerPingTimeout(void *data)
{
    ps_state *psstate = data;
    StoreEntry *entry = psstate->entry;
    if (entry)
	debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
    entry->ping_status = PING_TIMEOUT;
    PeerStats.timeouts++;
    psstate->icp.timeout = 1;
    peerSelectFoo(psstate);
}

void
peerSelectInit(void)
{
    memset(&PeerStats, '\0', sizeof(PeerStats));
    assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
}

static void
peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
{
    int rtt;
    int hops;
    if (Config.onoff.query_icmp) {
	if (header->flags & ICP_FLAG_SRC_RTT) {
	    rtt = header->pad & 0xFFFF;
	    hops = (header->pad >> 16) & 0xFFFF;
	    if (rtt > 0 && rtt < 0xFFFF)
		netdbUpdatePeer(ps->request, p, rtt, hops);
	    if (rtt && (ps->icp.p_rtt == 0 || rtt < ps->icp.p_rtt)) {
		ps->closest_parent_miss = p;
		ps->icp.p_rtt = rtt;
	    }
	}
    }
    /* if closest-only is set, the don't allow FIRST_PARENT_MISS */
    if (EBIT_TEST(p->options, NEIGHBOR_CLOSEST_ONLY))
	return;
    /* set FIRST_MISS if thre is no CLOSEST parent */
    if (ps->closest_parent_miss != NULL)
	return;
    rtt = tvSubMsec(ps->icp.start, current_time) / p->weight;
    if (ps->icp.w_rtt == 0 || rtt < ps->icp.w_rtt) {
	ps->first_parent_miss = p;
	ps->icp.w_rtt = rtt;
    }
}

static void
peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
{
    ps_state *psstate = data;
    icp_opcode op = header->opcode;
    request_t *request = psstate->request;
    debug(44, 3) ("peerHandleIcpReply: %s %s\n",
	icp_opcode_str[op],
	storeUrl(psstate->entry));
    psstate->icp.n_recv++;
    if (op == ICP_MISS || op == ICP_DECHO) {
	if (type == PEER_PARENT)
	    peerIcpParentMiss(p, header, psstate);
    } else if (op == ICP_HIT) {
	hierarchyNote(&request->hier,
	    type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT,
	    &psstate->icp,
	    p->host);
	peerSelectCallback(psstate, p);
	return;
    } else if (op == ICP_SECHO) {
	hierarchyNote(&request->hier,
	    SOURCE_FASTEST,
	    &psstate->icp,
	    request->host);
	peerSelectCallback(psstate, NULL);
	return;
    }
    if (psstate->icp.n_recv < psstate->icp.n_replies_expected)
	return;
    peerSelectFoo(psstate);
}
Commit	Line	Data
641941c0	1
062e2281	2	/*
39edba21	3	* $Id: peer_select.cc,v 1.46 1998/04/08 19:28:48 wessels Exp $
062e2281	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
	14	* the National Science Foundation.
	15	*
	16	* This program is free software; you can redistribute it and/or modify
	17	* it under the terms of the GNU General Public License as published by
	18	* the Free Software Foundation; either version 2 of the License, or
	19	* (at your option) any later version.
	20	*
	21	* This program is distributed in the hope that it will be useful,
	22	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	23	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	24	* GNU General Public License for more details.
	25	*
	26	* You should have received a copy of the GNU General Public License
	27	* along with this program; if not, write to the Free Software
	28	* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
	29	*
	30	*/
	31
	32	#include "squid.h"
	33
429fdbec	34	const char *hier_strings[] =
	35	{
	36	"NONE",
	37	"DIRECT",
	38	"SIBLING_HIT",
	39	"PARENT_HIT",
	40	"DEFAULT_PARENT",
	41	"SINGLE_PARENT",
	42	"FIRST_UP_PARENT",
	43	"NO_PARENT_DIRECT",
	44	"FIRST_PARENT_MISS",
	45	"CLOSEST_PARENT_MISS",
	46	"CLOSEST_DIRECT",
	47	"NO_DIRECT_FAIL",
	48	"SOURCE_FASTEST",
429fdbec	49	"ROUNDROBIN_PARENT",
b123df92	50	#if SQUID_PEER_DIGEST
c127134a	51	"CACHE_DIGEST_HIT",
c127134a	52	#endif
429fdbec	53	"INVALID CODE"
	54	};
	55
85034133	56	static struct {
75e88d56	57	int timeouts;
85034133	58	} PeerStats;
062e2281	59
f9e5a344	60	static char *DirectStr[] =
	61	{
	62	"DIRECT_NO",
	63	"DIRECT_MAYBE",
	64	"DIRECT_YES"
7b665aeb	65	};
75e88d56	66
f5b8bbc4	67	static void peerSelectFoo(ps_state *);
de7ba689	68	static void peerSelectCheckAS(ps_state *);
f5b8bbc4	69	static void peerPingTimeout(void *data);
f5b8bbc4	70	static void peerSelectCallbackFail(ps_state * psstate);
b3264694	71	static IRCB peerHandleIcpReply;
de7ba689	72	static IPH peerSelectCheckASDone;
f5b8bbc4	73	static void peerSelectStateFree(ps_state * psstate);
	74	static void peerIcpParentMiss(peer , icp_common_t , ps_state *);
	75	static int peerCheckNetdbDirect(ps_state * psstate);
348b2031	76
	77	static void
	78	peerSelectStateFree(ps_state * psstate)
	79	{
	80	if (psstate->acl_checklist) {
51fdcbd5	81	debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
348b2031	82	aclChecklistFree(psstate->acl_checklist);
	83	}
	84	requestUnlink(psstate->request);
8407afee	85	psstate->request = NULL;
8407afee	86	cbdataFree(psstate);
348b2031	87	}
062e2281	88
	89	int
	90	peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
	91	{
7b665aeb	92	int n;
93775f90	93	if (entry == NULL)
93775f90	94	return 0;
9fb13bb6	95	debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
062e2281	96	if (entry->ping_status != PING_NONE)
062e2281	97	return 0;
9bd6a36d	98	assert(direct != DIRECT_YES);
79a15e0a	99	if (!EBIT_TEST(entry->flag, HIERARCHICAL) && direct != DIRECT_NO)
062e2281	100	return 0;
79a15e0a	101	if (EBIT_TEST(entry->flag, KEY_PRIVATE) && !neighbors_do_private_keys)
062e2281	102	if (direct != DIRECT_NO)
062e2281	103	return 0;
7b665aeb	104	n = neighborsCount(request);
f9e5a344	105	debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
7b665aeb	106	return n;
062e2281	107	}
	108
	109
	110	peer *
	111	peerGetSomeParent(request_t * request, hier_code * code)
	112	{
	113	peer *p;
de7ba689	114	debug(44, 3) ("peerGetSomeParent: called.\n");
062e2281	115	if ((p = getDefaultParent(request))) {
429fdbec	116	*code = DEFAULT_PARENT;
062e2281	117	return p;
062e2281	118	}
062e2281	119	if ((p = getRoundRobinParent(request))) {
429fdbec	120	*code = ROUNDROBIN_PARENT;
062e2281	121	return p;
	122	}
	123	if ((p = getFirstUpParent(request))) {
429fdbec	124	*code = FIRSTUP_PARENT;
062e2281	125	return p;
	126	}
	127	return NULL;
	128	}
	129
	130	void
93775f90	131	peerSelect(request_t * request,
b6c0e933	132	StoreEntry * entry,
582b6456	133	PSC * callback,
582b6456	134	PSC * fail_callback,
b6c0e933	135	void *callback_data)
75e88d56	136	{
b6c0e933	137	ps_state *psstate = xcalloc(1, sizeof(ps_state));
86b389fc	138	if (entry)
9fb13bb6	139	debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
86b389fc	140	else
f9e5a344	141	debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
3f6c0fb2	142	cbdataAdd(psstate, MEM_NONE);
b6c0e933	143	psstate->request = requestLink(request);
	144	psstate->entry = entry;
	145	psstate->callback = callback;
	146	psstate->fail_callback = fail_callback;
	147	psstate->callback_data = callback_data;
8407afee	148	cbdataLock(callback_data);
de7ba689	149	peerSelectCheckAS(psstate);
39edba21	150	#if SQUID_PEER_DIGEST
	151	request->hier.peer_select_start = current_time;
	152	#endif
de7ba689	153	}
	154
	155	static void
	156	peerSelectCheckASDone(const ipcache_addrs * ia, void *data)
	157	{
	158	ps_state *psstate = data;
b6c0e933	159	peerSelectFoo(psstate);
75e88d56	160	}
75e88d56	161
de7ba689	162	static void
	163	peerSelectCheckAS(ps_state * psstate)
	164	{
	165	request_t *request = psstate->request;
	166
	167	/* XXXX Just a quick hack to get the destination address to the
	168	* ipcache, because peerSelectIcpPing requires non-blocking ACL
	169	* check.
	170	* We should handle AS acl's differently than cache_host ones. */
	171
	172	ipcache_nbgethostbyname(request->host,
	173	peerSelectCheckASDone,
	174	psstate);
	175	return;
	176	}
	177
	178
75e88d56	179	static void
	180	peerCheckNeverDirectDone(int answer, void *data)
	181	{
b6c0e933	182	ps_state *psstate = data;
348b2031	183	psstate->acl_checklist = NULL;
a3d5953d	184	debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
b6c0e933	185	psstate->never_direct = answer ? 1 : -1;
b6c0e933	186	peerSelectFoo(psstate);
75e88d56	187	}
	188
	189	static void
	190	peerCheckAlwaysDirectDone(int answer, void *data)
	191	{
b6c0e933	192	ps_state *psstate = data;
348b2031	193	psstate->acl_checklist = NULL;
a3d5953d	194	debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
7b665aeb	195	psstate->always_direct = answer ? 1 : -1;
b6c0e933	196	peerSelectFoo(psstate);
75e88d56	197	}
75e88d56	198
93775f90	199	static void
b6c0e933	200	peerSelectCallback(ps_state * psstate, peer * p)
93775f90	201	{
b6c0e933	202	StoreEntry *entry = psstate->entry;
8407afee	203	void *data = psstate->callback_data;
b6c0e933	204	if (entry) {
9fb13bb6	205	debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
b6c0e933	206	if (entry->ping_status == PING_WAITING)
	207	eventDelete(peerPingTimeout, psstate);
	208	entry->ping_status = PING_DONE;
	209	}
ee1679df	210	psstate->icp.stop = current_time;
8407afee	211	if (cbdataValid(data))
365e5b34	212	psstate->callback(p, data);
8407afee	213	cbdataUnlock(data);
348b2031	214	peerSelectStateFree(psstate);
93775f90	215	}
	216
	217	static void
b6c0e933	218	peerSelectCallbackFail(ps_state * psstate)
93775f90	219	{
b6c0e933	220	request_t *request = psstate->request;
8407afee	221	void *data = psstate->callback_data;
9fb13bb6	222	const char *url = psstate->entry ? storeUrl(psstate->entry) : urlCanonical(request, NULL);
a3d5953d	223	debug(44, 1) ("Failed to select source for '%s'\n", url);
	224	debug(44, 1) (" always_direct = %d\n", psstate->always_direct);
	225	debug(44, 1) (" never_direct = %d\n", psstate->never_direct);
	226	debug(44, 1) (" timeout = %d\n", psstate->icp.timeout);
8407afee	227	if (cbdataValid(data))
365e5b34	228	psstate->fail_callback(NULL, data);
8407afee	229	cbdataUnlock(data);
348b2031	230	peerSelectStateFree(psstate);
063347b4	231	/* XXX When this happens, the client request just hangs */
93775f90	232	}
93775f90	233
b3264694	234	static int
	235	peerCheckNetdbDirect(ps_state * psstate)
	236	{
	237	peer *p = psstate->closest_parent_miss;
	238	int myrtt;
	239	int myhops;
	240	if (p == NULL)
	241	return 0;
	242	myrtt = netdbHostRtt(psstate->request->host);
437e2060	243	debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d\n", myrtt);
437e2060	244	debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d\n",
b3264694	245	psstate->icp.p_rtt);
	246	if (myrtt && myrtt < psstate->icp.p_rtt)
	247	return 1;
	248	myhops = netdbHostHops(psstate->request->host);
437e2060	249	debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
437e2060	250	debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
b3264694	251	Config.minDirectHops);
	252	if (myhops && myhops <= Config.minDirectHops)
	253	return 1;
	254	return 0;
	255	}
	256
93775f90	257	static void
b6c0e933	258	peerSelectFoo(ps_state * psstate)
062e2281	259	{
	260	peer *p;
	261	hier_code code;
b6c0e933	262	StoreEntry *entry = psstate->entry;
b6c0e933	263	request_t *request = psstate->request;
75e88d56	264	int direct;
7b665aeb	265	debug(44, 3) ("peerSelectFoo: '%s %s'\n",
b6c0e933	266	RequestMethodStr[request->method],
b6c0e933	267	request->host);
eeeb6107	268	if (psstate->never_direct == 0 && Config.accessList.NeverDirect) {
348b2031	269	psstate->acl_checklist = aclChecklistCreate(
348b2031	270	Config.accessList.NeverDirect,
75e88d56	271	request,
	272	request->client_addr,
	273	NULL, /* user agent */
348b2031	274	NULL); /* ident */
348b2031	275	aclNBCheck(psstate->acl_checklist,
75e88d56	276	peerCheckNeverDirectDone,
b6c0e933	277	psstate);
75e88d56	278	return;
b6c0e933	279	} else if (psstate->never_direct > 0) {
75e88d56	280	direct = DIRECT_NO;
eeeb6107	281	} else if (psstate->always_direct == 0 && Config.accessList.AlwaysDirect) {
348b2031	282	psstate->acl_checklist = aclChecklistCreate(
348b2031	283	Config.accessList.AlwaysDirect,
75e88d56	284	request,
	285	request->client_addr,
	286	NULL, /* user agent */
348b2031	287	NULL); /* ident */
348b2031	288	aclNBCheck(psstate->acl_checklist,
75e88d56	289	peerCheckAlwaysDirectDone,
b6c0e933	290	psstate);
75e88d56	291	return;
b6c0e933	292	} else if (psstate->always_direct > 0) {
75e88d56	293	direct = DIRECT_YES;
	294	} else {
	295	direct = DIRECT_MAYBE;
	296	}
7b665aeb	297	debug(44, 3) ("peerSelectFoo: direct = %s\n", DirectStr[direct]);
062e2281	298	if (direct == DIRECT_YES) {
7b665aeb	299	debug(44, 3) ("peerSelectFoo: DIRECT\n");
a4394ebd	300	hierarchyNote(&request->hier, DIRECT, &psstate->icp, request->host);
b6c0e933	301	peerSelectCallback(psstate, NULL);
062e2281	302	return;
062e2281	303	}
a369131d	304	psstate->single_parent = getSingleParent(request);
a369131d	305	if (psstate->single_parent != NULL) {
	306	debug(44, 3) ("peerSelect: found single parent, skipping ICP query\n");
	307	} else if (peerSelectIcpPing(request, direct, entry)) {
9bd6a36d	308	assert(entry->ping_status == PING_NONE);
b123df92	309	#if SQUID_PEER_DIGEST
	310	/* always check digests if any */
	311	/* @?@ optimize: track if there are any digested peers at all (global counter) */
	312	if (1) {
	313	p = neighborsDigestSelect(request, entry);
	314	if (p) {
	315	request->hier.cd_lookup = LOOKUP_HIT;
	316	} else
	317	if (request->hier.n_choices) {
	318	request->hier.cd_lookup = LOOKUP_MISS;
	319	} else {
	320	request->hier.cd_lookup = LOOKUP_NONE;
	321	}
	322	debug(44, 3) ("peerSelect: %s digest lookup: %s choices: %d (%d)\n",
	323	p ? p->host : "",
	324	lookup_t_str[request->hier.cd_lookup],
	325	request->hier.n_choices, request->hier.n_ichoices);
	326	}
	327	/* @?@ TEST: randomly choose a peer selection algorithm */
	328	if (request->hier.cd_lookup != LOOKUP_NONE && (squid_random() & 1)) {
c127134a	329	debug(44, 3) ("peerSelect: Using Cache Digest\n");
b123df92	330	request->hier.alg = PEER_SA_DIGEST;
	331	if (request->hier.cd_lookup == LOOKUP_HIT) {
	332	assert(p);
c127134a	333	code = CACHE_DIGEST_HIT;
	334	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	335	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	336	peerSelectCallback(psstate, NULL);
b123df92	337	return;
c127134a	338	}
c127134a	339	} else {
b123df92	340	request->hier.alg = PEER_SA_ICP;
c127134a	341	#endif
	342	debug(44, 3) ("peerSelect: Doing ICP pings\n");
	343	psstate->icp.start = current_time;
	344	psstate->icp.n_sent = neighborsUdpPing(request,
	345	entry,
	346	peerHandleIcpReply,
b6c0e933	347	psstate,
c127134a	348	&psstate->icp.n_replies_expected);
	349	if (psstate->icp.n_sent == 0)
	350	debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
	351	if (psstate->icp.n_replies_expected > 0) {
	352	entry->ping_status = PING_WAITING;
	353	eventAdd("peerPingTimeout",
	354	peerPingTimeout,
	355	psstate,
	356	Config.neighborTimeout);
	357	return;
	358	}
b123df92	359	#if SQUID_PEER_DIGEST
062e2281	360	}
c127134a	361	#endif
062e2281	362	}
de7ba689	363	debug(44, 3) ("peerSelectFoo: After peerSelectIcpPing.\n");
b3264694	364	if (peerCheckNetdbDirect(psstate)) {
	365	code = CLOSEST_DIRECT;
	366	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
	367	hierarchyNote(&request->hier, code, &psstate->icp, request->host);
	368	peerSelectCallback(psstate, NULL);
a200bbd2	369	} else if ((p = psstate->closest_parent_miss) != NULL) {
b3264694	370	code = CLOSEST_PARENT_MISS;
	371	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	372	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	373	peerSelectCallback(psstate, p);
a200bbd2	374	} else if ((p = psstate->first_parent_miss) != NULL) {
429fdbec	375	code = FIRST_PARENT_MISS;
a3d5953d	376	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
a4394ebd	377	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
b6c0e933	378	peerSelectCallback(psstate, p);
a369131d	379	} else if ((p = psstate->single_parent)) {
	380	code = SINGLE_PARENT;
	381	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	382	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
	383	peerSelectCallback(psstate, p);
93775f90	384	} else if (direct != DIRECT_NO) {
429fdbec	385	code = DIRECT;
a3d5953d	386	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
a4394ebd	387	hierarchyNote(&request->hier, code, &psstate->icp, request->host);
b6c0e933	388	peerSelectCallback(psstate, NULL);
93775f90	389	} else if ((p = peerGetSomeParent(request, &code))) {
a3d5953d	390	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
a4394ebd	391	hierarchyNote(&request->hier, code, &psstate->icp, p->host);
b6c0e933	392	peerSelectCallback(psstate, p);
93775f90	393	} else {
429fdbec	394	code = NO_DIRECT_FAIL;
a4394ebd	395	hierarchyNote(&request->hier, code, &psstate->icp, NULL);
b6c0e933	396	peerSelectCallbackFail(psstate);
062e2281	397	}
	398	}
	399
d9586c3c	400	static void
93775f90	401	peerPingTimeout(void *data)
062e2281	402	{
b6c0e933	403	ps_state *psstate = data;
b6c0e933	404	StoreEntry *entry = psstate->entry;
86b389fc	405	if (entry)
9fb13bb6	406	debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
93775f90	407	entry->ping_status = PING_TIMEOUT;
75e88d56	408	PeerStats.timeouts++;
b6c0e933	409	psstate->icp.timeout = 1;
b6c0e933	410	peerSelectFoo(psstate);
85034133	411	}
	412
	413	void
	414	peerSelectInit(void)
	415	{
75e88d56	416	memset(&PeerStats, '\0', sizeof(PeerStats));
9bdbfe33	417	assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
062e2281	418	}
93775f90	419
b3264694	420	static void
	421	peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
	422	{
	423	int rtt;
	424	int hops;
	425	if (Config.onoff.query_icmp) {
79a15e0a	426	if (header->flags & ICP_FLAG_SRC_RTT) {
b3264694	427	rtt = header->pad & 0xFFFF;
	428	hops = (header->pad >> 16) & 0xFFFF;
	429	if (rtt > 0 && rtt < 0xFFFF)
	430	netdbUpdatePeer(ps->request, p, rtt, hops);
	431	if (rtt && (ps->icp.p_rtt == 0 \|\| rtt < ps->icp.p_rtt)) {
	432	ps->closest_parent_miss = p;
	433	ps->icp.p_rtt = rtt;
	434	}
	435	}
	436	}
	437	/* if closest-only is set, the don't allow FIRST_PARENT_MISS */
79a15e0a	438	if (EBIT_TEST(p->options, NEIGHBOR_CLOSEST_ONLY))
b3264694	439	return;
	440	/* set FIRST_MISS if thre is no CLOSEST parent */
	441	if (ps->closest_parent_miss != NULL)
	442	return;
	443	rtt = tvSubMsec(ps->icp.start, current_time) / p->weight;
	444	if (ps->icp.w_rtt == 0 \|\| rtt < ps->icp.w_rtt) {
	445	ps->first_parent_miss = p;
	446	ps->icp.w_rtt = rtt;
	447	}
	448	}
93775f90	449
b6c0e933	450	static void
b3264694	451	peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
93775f90	452	{
b6c0e933	453	ps_state *psstate = data;
b3264694	454	icp_opcode op = header->opcode;
b6c0e933	455	request_t *request = psstate->request;
f9e5a344	456	debug(44, 3) ("peerHandleIcpReply: %s %s\n",
27cd7235	457	icp_opcode_str[op],
9fb13bb6	458	storeUrl(psstate->entry));
b6c0e933	459	psstate->icp.n_recv++;
27cd7235	460	if (op == ICP_MISS \|\| op == ICP_DECHO) {
b3264694	461	if (type == PEER_PARENT)
b3264694	462	peerIcpParentMiss(p, header, psstate);
a7c05555	463	} else if (op == ICP_HIT) {
a4394ebd	464	hierarchyNote(&request->hier,
429fdbec	465	type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT,
b6c0e933	466	&psstate->icp,
93775f90	467	p->host);
b6c0e933	468	peerSelectCallback(psstate, p);
93775f90	469	return;
27cd7235	470	} else if (op == ICP_SECHO) {
a4394ebd	471	hierarchyNote(&request->hier,
429fdbec	472	SOURCE_FASTEST,
b6c0e933	473	&psstate->icp,
b6c0e933	474	request->host);
4f92c80c	475	peerSelectCallback(psstate, NULL);
93775f90	476	return;
93775f90	477	}
b6c0e933	478	if (psstate->icp.n_recv < psstate->icp.n_replies_expected)
93775f90	479	return;
b6c0e933	480	peerSelectFoo(psstate);
93775f90	481	}