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


/*
 * $Id: peer_select.cc,v 1.95 1998/12/16 06:34:55 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.  Squid is Copyrighted (C) 1998 by
 *  Duane Wessels and the University of California San Diego.  Please
 *  see the COPYRIGHT file for full details.  Squid incorporates
 *  software developed and/or copyrighted by other sources.  Please see
 *  the CREDITS file for full details.
 *
 *  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., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 */

#include "squid.h"

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

static struct {
    int timeouts;
} PeerStats;

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

static void peerSelectFoo(ps_state *);
static void peerPingTimeout(void *data);
static void peerSelectCallback(ps_state * psstate);
static IRCB peerHandlePingReply;
static void peerSelectStateFree(ps_state * psstate);
static void peerIcpParentMiss(peer *, icp_common_t *, ps_state *);
#if USE_HTCP
static void peerHtcpParentMiss(peer *, htcpReplyData *, ps_state *);
static void peerHandleHtcpReply(peer *, peer_t, htcpReplyData *, void *);
#endif
static int peerCheckNetdbDirect(ps_state * psstate);
static void peerGetSomeNeighbor(ps_state *);
static void peerGetSomeNeighborReplies(ps_state *);
static void peerGetSomeDirect(ps_state *);
static void peerGetSomeParent(ps_state *);
static void peerAddFwdServer(FwdServer **, peer *, hier_code);

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;
    if (psstate->entry) {
	assert(psstate->entry->ping_status != PING_WAITING);
	storeUnlockObject(psstate->entry);
	psstate->entry = NULL;
    }
    cbdataFree(psstate);
}

int
peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
{
    int n;
    assert(entry);
    assert(entry->ping_status == PING_NONE);
    assert(direct != DIRECT_YES);
    debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
    if (!request->flags.hierarchical && direct != DIRECT_NO)
	return 0;
    if (EBIT_TEST(entry->flags, 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;
}


void
peerSelect(request_t * request,
    StoreEntry * entry,
    PSC * 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, cbdataXfree, 0);
    psstate->request = requestLink(request);
    psstate->entry = entry;
    psstate->callback = callback;
    psstate->callback_data = callback_data;
    psstate->direct = DIRECT_UNKNOWN;
#if USE_CACHE_DIGESTS
    request->hier.peer_select_start = current_time;
#endif
    if (psstate->entry)
	storeLockObject(psstate->entry);
    cbdataLock(callback_data);
    peerSelectFoo(psstate);
}

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)
{
    StoreEntry *entry = psstate->entry;
    FwdServer *fs = psstate->servers;
    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;
    }
    if (fs == NULL) {
	debug(44, 1) ("Failed to select source for '%s'\n", storeUrl(entry));
	debug(44, 1) ("  always_direct = %d\n", psstate->always_direct);
	debug(44, 1) ("   never_direct = %d\n", psstate->never_direct);
	debug(44, 1) ("       timedout = %d\n", psstate->ping.timedout);
    }
    psstate->ping.stop = current_time;
    psstate->request->hier.ping = psstate->ping;
    if (cbdataValid(data)) {
	psstate->servers = NULL;
	psstate->callback(fs, data);
    }
    cbdataUnlock(data);
    peerSelectStateFree(psstate);
}

static int
peerCheckNetdbDirect(ps_state * psstate)
{
    peer *p = whichPeer(&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 msec\n", myrtt);
    debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d msec\n",
	psstate->ping.p_rtt);
    if (myrtt && myrtt < psstate->ping.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 * ps)
{
    StoreEntry *entry = ps->entry;
    request_t *request = ps->request;
    debug(44, 3) ("peerSelectFoo: '%s %s'\n",
	RequestMethodStr[request->method],
	request->host);
    if (ps->direct == DIRECT_UNKNOWN) {
	if (ps->always_direct == 0 && Config.accessList.AlwaysDirect) {
	    ps->acl_checklist = aclChecklistCreate(
		Config.accessList.AlwaysDirect,
		request,
		request->client_addr,
		NULL,		/* user agent */
		NULL);		/* ident */
	    aclNBCheck(ps->acl_checklist,
		peerCheckAlwaysDirectDone,
		ps);
	    return;
	} else if (ps->always_direct > 0) {
	    ps->direct = DIRECT_YES;
	} else if (ps->never_direct == 0 && Config.accessList.NeverDirect) {
	    ps->acl_checklist = aclChecklistCreate(
		Config.accessList.NeverDirect,
		request,
		request->client_addr,
		NULL,		/* user agent */
		NULL);		/* ident */
	    aclNBCheck(ps->acl_checklist,
		peerCheckNeverDirectDone,
		ps);
	    return;
	} else if (ps->never_direct > 0) {
	    ps->direct = DIRECT_NO;
	} else if (request->flags.loopdetect) {
	    ps->direct = DIRECT_YES;
	} else {
	    ps->direct = DIRECT_MAYBE;
	}
	debug(44, 3) ("peerSelectFoo: direct = %s\n",
	    DirectStr[ps->direct]);
    }
    if (entry->ping_status == PING_NONE) {
	peerGetSomeNeighbor(ps);
	if (entry->ping_status == PING_WAITING)
	    return;
    } else if (entry->ping_status == PING_WAITING) {
	peerGetSomeNeighborReplies(ps);
	entry->ping_status = PING_DONE;
    }
    if (Config.onoff.prefer_direct)
	peerGetSomeDirect(ps);
    peerGetSomeParent(ps);
    if (!Config.onoff.prefer_direct)
	peerGetSomeDirect(ps);
    peerSelectCallback(ps);
}

/*
 * peerGetSomeNeighbor
 * 
 * Selects a neighbor (parent or sibling) based on one of the
 * following methods:
 *      Cache Digests
 *      CARP
 *      Netdb RTT estimates
 *      ICP/HTCP queries
 */
static void
peerGetSomeNeighbor(ps_state * ps)
{
    StoreEntry *entry = ps->entry;
    request_t *request = ps->request;
    peer *p;
    hier_code code = HIER_NONE;
    assert(entry->ping_status == PING_NONE);
    if (ps->direct == DIRECT_YES) {
	entry->ping_status = PING_DONE;
	return;
    }
#if USE_CACHE_DIGESTS
    if ((p = neighborsDigestSelect(request, entry))) {
	code = CACHE_DIGEST_HIT;
    } else
#endif
#if USE_CARP
    if ((p = carpSelectParent(request))) {
	code = CARP;
    } else
#endif
    if ((p = netdbClosestParent(request))) {
	code = CLOSEST_PARENT;
    } else if (peerSelectIcpPing(request, ps->direct, entry)) {
	debug(44, 3) ("peerSelect: Doing ICP pings\n");
	ps->ping.start = current_time;
	ps->ping.n_sent = neighborsUdpPing(request,
	    entry,
	    peerHandlePingReply,
	    ps,
	    &ps->ping.n_replies_expected,
	    &ps->ping.timeout);
	if (ps->ping.n_sent == 0)
	    debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
	debug(44, 3) ("peerSelect: %d ICP replies expected, RTT %d msec\n",
	    ps->ping.n_replies_expected, ps->ping.timeout);
	if (ps->ping.n_replies_expected > 0) {
	    entry->ping_status = PING_WAITING;
	    eventAdd("peerPingTimeout",
		peerPingTimeout,
		ps,
		0.001 * ps->ping.timeout,
		0);
	    return;
	}
    }
    if (code != HIER_NONE) {
	assert(p);
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	peerAddFwdServer(&ps->servers, p, code);
    }
    entry->ping_status = PING_DONE;
}

/*
 * peerGetSomeNeighborReplies
 * 
 * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 */
static void
peerGetSomeNeighborReplies(ps_state * ps)
{
    StoreEntry *entry = ps->entry;
    request_t *request = ps->request;
    peer *p = NULL;
    hier_code code = HIER_NONE;
    assert(entry->ping_status == PING_WAITING);
    assert(ps->direct != DIRECT_YES);
    if (peerCheckNetdbDirect(ps)) {
	code = CLOSEST_DIRECT;
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
	peerAddFwdServer(&ps->servers, NULL, code);
	return;
    }
    if ((p = ps->hit)) {
	code = ps->hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
    } else
#if ALLOW_SOURCE_PING
    if ((p = ps->secho)) {
	code = SOURCE_FASTEST;
    } else
#endif
    if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
	p = whichPeer(&ps->closest_parent_miss);
	code = CLOSEST_PARENT_MISS;
    } else if (ps->first_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
	p = whichPeer(&ps->first_parent_miss);
	code = FIRST_PARENT_MISS;
    }
    if (p && code != HIER_NONE) {
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	peerAddFwdServer(&ps->servers, p, code);
    }
}


/*
 * peerGetSomeDirect
 * 
 * Simply adds a 'direct' entry to the FwdServers list if this
 * request can be forwarded directly to the origin server
 */
static void
peerGetSomeDirect(ps_state * ps)
{
    if (ps->direct == DIRECT_NO)
	return;
    if (ps->request->protocol == PROTO_WAIS)
	/* Its not really DIRECT, now is it? */
	peerAddFwdServer(&ps->servers, Config.Wais.peer, DIRECT);
    else
	peerAddFwdServer(&ps->servers, NULL, DIRECT);
}

static void
peerGetSomeParent(ps_state * ps)
{
    peer *p;
    request_t *request = ps->request;
    hier_code code = HIER_NONE;
    debug(44, 3) ("peerGetSomeParent: %s %s\n",
	RequestMethodStr[request->method],
	request->host);
    if ((p = getDefaultParent(request))) {
	code = DEFAULT_PARENT;
    } else if ((p = getRoundRobinParent(request))) {
	code = ROUNDROBIN_PARENT;
    } else if ((p = getFirstUpParent(request))) {
	code = FIRSTUP_PARENT;
    } else if ((p = getAnyParent(request))) {
	code = ANY_OLD_PARENT;
    }
    if (code != HIER_NONE) {
	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	peerAddFwdServer(&ps->servers, p, code);
    }
}

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;
    if (!cbdataValid(psstate->callback_data)) {
	/* request aborted */
	cbdataUnlock(psstate->callback_data);
	peerSelectStateFree(psstate);
	return;
    }
    PeerStats.timeouts++;
    psstate->ping.timedout = 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->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
		ps->closest_parent_miss = p->in_addr;
		ps->ping.p_rtt = rtt;
	    }
	}
    }
    /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
    if (p->options.closest_only)
	return;
    /* set FIRST_MISS if there is no CLOSEST parent */
    if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
	return;
    rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
    if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
	ps->first_parent_miss = p->in_addr;
	ps->ping.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;
    debug(44, 3) ("peerHandleIcpReply: %s %s\n",
	icp_opcode_str[op],
	storeUrl(psstate->entry));
#if USE_CACHE_DIGESTS && 0
    /* do cd lookup to count false misses */
    if (p && request)
	peerNoteDigestLookup(request, p,
	    peerDigestLookup(p, request, psstate->entry));
#endif
    psstate->ping.n_recv++;
    if (op == ICP_MISS || op == ICP_DECHO) {
	if (type == PEER_PARENT)
	    peerIcpParentMiss(p, header, psstate);
    } else if (op == ICP_HIT) {
	psstate->hit = p;
	psstate->hit_type = type;
	peerSelectFoo(psstate);
	return;
    }
#if ALLOW_SOURCE_PING
    else if (op == ICP_SECHO) {
	psstate->secho = p;
	peerSelectFoo(psstate);
	return;
    }
#endif
    if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
	return;
    peerSelectFoo(psstate);
}

#if USE_HTCP
static void
peerHandleHtcpReply(peer * p, peer_t type, htcpReplyData * htcp, void *data)
{
    ps_state *psstate = data;
    request_t *request = psstate->request;
    debug(44, 3) ("peerHandleIcpReply: %s %s\n",
	htcp->hit ? "HIT" : "MISS",
	storeUrl(psstate->entry));
    psstate->ping.n_recv++;
    if (htcp->hit) {
	psstate->hit = p;
	psstate->hit_type = type;
	peerSelectFoo(psstate);
	return;
    }
    if (type == PEER_PARENT)
	peerHtcpParentMiss(p, htcp, psstate);
    if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
	return;
    peerSelectFoo(psstate);
}

static void
peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
{
    int rtt;
    int hops;
    if (Config.onoff.query_icmp) {
	if (htcp->cto.rtt > 0) {
	    rtt = (int) htcp->cto.rtt * 1000;
	    hops = (int) htcp->cto.hops * 1000;
	    netdbUpdatePeer(ps->request, p, rtt, hops);
	    if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
		ps->closest_parent_miss = p->in_addr;
		ps->ping.p_rtt = rtt;
	    }
	}
    }
    /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
    if (p->options.closest_only)
	return;
    /* set FIRST_MISS if there is no CLOSEST parent */
    if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
	return;
    rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
    if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
	ps->first_parent_miss = p->in_addr;
	ps->ping.w_rtt = rtt;
    }
}
#endif

static void
peerHandlePingReply(peer * p, peer_t type, protocol_t proto, void *pingdata, void *data)
{
    if (proto == PROTO_ICP)
	peerHandleIcpReply(p, type, pingdata, data);
#if USE_HTCP
    else if (proto == PROTO_HTCP)
	peerHandleHtcpReply(p, type, pingdata, data);
#endif
    else
	debug(44, 1) ("peerHandlePingReply: unknown protocol_t %d\n", (int) proto);
}

static void
peerAddFwdServer(FwdServer ** FS, peer * p, hier_code code)
{
    FwdServer *fs = memAllocate(MEM_FWD_SERVER);
    debug(44, 5) ("peerAddFwdServer: adding %s %s\n",
	p ? p->host : "DIRECT",
	hier_strings[code]);
    fs->peer = p;
    fs->code = code;
    cbdataLock(fs->peer);
    while (*FS)
	FS = &(*FS)->next;
    *FS = fs;
}
Commit	Line	Data
641941c0	1
062e2281	2	/*
c971344c	3	* $Id: peer_select.cc,v 1.95 1998/12/16 06:34:55 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/
e25c139f	9	* ----------------------------------------------------------
062e2281	10	*
	11	* Squid is the result of efforts by numerous individuals from the
	12	* Internet community. Development is led by Duane Wessels of the
e25c139f	13	* National Laboratory for Applied Network Research and funded by the
	14	* National Science Foundation. Squid is Copyrighted (C) 1998 by
	15	* Duane Wessels and the University of California San Diego. Please
	16	* see the COPYRIGHT file for full details. Squid incorporates
	17	* software developed and/or copyrighted by other sources. Please see
	18	* the CREDITS file for full details.
062e2281	19	*
	20	* This program is free software; you can redistribute it and/or modify
	21	* it under the terms of the GNU General Public License as published by
	22	* the Free Software Foundation; either version 2 of the License, or
	23	* (at your option) any later version.
	24	*
	25	* This program is distributed in the hope that it will be useful,
	26	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	27	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	28	* GNU General Public License for more details.
	29	*
	30	* You should have received a copy of the GNU General Public License
	31	* along with this program; if not, write to the Free Software
cbdec147	32	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
e25c139f	33	*
062e2281	34	*/
	35
	36	#include "squid.h"
	37
429fdbec	38	const char *hier_strings[] =
	39	{
	40	"NONE",
	41	"DIRECT",
	42	"SIBLING_HIT",
	43	"PARENT_HIT",
	44	"DEFAULT_PARENT",
	45	"SINGLE_PARENT",
	46	"FIRST_UP_PARENT",
429fdbec	47	"FIRST_PARENT_MISS",
429fdbec	48	"CLOSEST_PARENT_MISS",
69c95dd3	49	"CLOSEST_PARENT",
429fdbec	50	"CLOSEST_DIRECT",
	51	"NO_DIRECT_FAIL",
	52	"SOURCE_FASTEST",
429fdbec	53	"ROUNDROBIN_PARENT",
6cfa8966	54	#if USE_CACHE_DIGESTS
c127134a	55	"CACHE_DIGEST_HIT",
afd88fbe	56	#endif
	57	#if USE_CARP
	58	"CARP",
c127134a	59	#endif
6a655df0	60	"ANY_PARENT",
429fdbec	61	"INVALID CODE"
	62	};
	63
85034133	64	static struct {
75e88d56	65	int timeouts;
85034133	66	} PeerStats;
062e2281	67
f9e5a344	68	static char *DirectStr[] =
f9e5a344	69	{
db1cd23c	70	"DIRECT_UNKNOWN",
f9e5a344	71	"DIRECT_NO",
	72	"DIRECT_MAYBE",
	73	"DIRECT_YES"
7b665aeb	74	};
75e88d56	75
f5b8bbc4	76	static void peerSelectFoo(ps_state *);
f5b8bbc4	77	static void peerPingTimeout(void *data);
db1cd23c	78	static void peerSelectCallback(ps_state * psstate);
86aebcda	79	static IRCB peerHandlePingReply;
f5b8bbc4	80	static void peerSelectStateFree(ps_state * psstate);
f5b8bbc4	81	static void peerIcpParentMiss(peer , icp_common_t , ps_state *);
44e237d0	82	#if USE_HTCP
	83	static void peerHtcpParentMiss(peer , htcpReplyData , ps_state *);
	84	static void peerHandleHtcpReply(peer , peer_t, htcpReplyData , void *);
	85	#endif
f5b8bbc4	86	static int peerCheckNetdbDirect(ps_state * psstate);
db1cd23c	87	static void peerGetSomeNeighbor(ps_state *);
	88	static void peerGetSomeNeighborReplies(ps_state *);
	89	static void peerGetSomeDirect(ps_state *);
	90	static void peerGetSomeParent(ps_state *);
db1cd23c	91	static void peerAddFwdServer(FwdServer *, peer , hier_code);
348b2031	92
	93	static void
	94	peerSelectStateFree(ps_state * psstate)
	95	{
	96	if (psstate->acl_checklist) {
51fdcbd5	97	debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
348b2031	98	aclChecklistFree(psstate->acl_checklist);
	99	}
	100	requestUnlink(psstate->request);
8407afee	101	psstate->request = NULL;
73a201f8	102	if (psstate->entry) {
6898e7b0	103	assert(psstate->entry->ping_status != PING_WAITING);
0cdcddb9	104	storeUnlockObject(psstate->entry);
0cdcddb9	105	psstate->entry = NULL;
73a201f8	106	}
8407afee	107	cbdataFree(psstate);
348b2031	108	}
062e2281	109
	110	int
	111	peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
	112	{
7b665aeb	113	int n;
db1cd23c	114	assert(entry);
db1cd23c	115	assert(entry->ping_status == PING_NONE);
9bd6a36d	116	assert(direct != DIRECT_YES);
db1cd23c	117	debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
92695e5e	118	if (!request->flags.hierarchical && direct != DIRECT_NO)
062e2281	119	return 0;
d46a87a8	120	if (EBIT_TEST(entry->flags, KEY_PRIVATE) && !neighbors_do_private_keys)
062e2281	121	if (direct != DIRECT_NO)
062e2281	122	return 0;
7b665aeb	123	n = neighborsCount(request);
f9e5a344	124	debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
7b665aeb	125	return n;
062e2281	126	}
	127
	128
062e2281	129	void
93775f90	130	peerSelect(request_t * request,
b6c0e933	131	StoreEntry * entry,
582b6456	132	PSC * callback,
b6c0e933	133	void *callback_data)
75e88d56	134	{
b6c0e933	135	ps_state *psstate = xcalloc(1, sizeof(ps_state));
86b389fc	136	if (entry)
9fb13bb6	137	debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
86b389fc	138	else
f9e5a344	139	debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
db1cd23c	140	cbdataAdd(psstate, cbdataXfree, 0);
b6c0e933	141	psstate->request = requestLink(request);
	142	psstate->entry = entry;
	143	psstate->callback = callback;
b6c0e933	144	psstate->callback_data = callback_data;
db1cd23c	145	psstate->direct = DIRECT_UNKNOWN;
6cfa8966	146	#if USE_CACHE_DIGESTS
39edba21	147	request->hier.peer_select_start = current_time;
39edba21	148	#endif
2395cb21	149	if (psstate->entry)
0cdcddb9	150	storeLockObject(psstate->entry);
395b813e	151	cbdataLock(callback_data);
b6c0e933	152	peerSelectFoo(psstate);
75e88d56	153	}
	154
	155	static void
	156	peerCheckNeverDirectDone(int answer, void *data)
	157	{
b6c0e933	158	ps_state *psstate = data;
348b2031	159	psstate->acl_checklist = NULL;
a3d5953d	160	debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
b6c0e933	161	psstate->never_direct = answer ? 1 : -1;
b6c0e933	162	peerSelectFoo(psstate);
75e88d56	163	}
	164
	165	static void
	166	peerCheckAlwaysDirectDone(int answer, void *data)
	167	{
b6c0e933	168	ps_state *psstate = data;
348b2031	169	psstate->acl_checklist = NULL;
a3d5953d	170	debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
7b665aeb	171	psstate->always_direct = answer ? 1 : -1;
b6c0e933	172	peerSelectFoo(psstate);
75e88d56	173	}
75e88d56	174
93775f90	175	static void
db1cd23c	176	peerSelectCallback(ps_state * psstate)
93775f90	177	{
b6c0e933	178	StoreEntry *entry = psstate->entry;
db1cd23c	179	FwdServer *fs = psstate->servers;
8407afee	180	void *data = psstate->callback_data;
b6c0e933	181	if (entry) {
9fb13bb6	182	debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
b6c0e933	183	if (entry->ping_status == PING_WAITING)
	184	eventDelete(peerPingTimeout, psstate);
	185	entry->ping_status = PING_DONE;
	186	}
db1cd23c	187	if (fs == NULL) {
	188	debug(44, 1) ("Failed to select source for '%s'\n", storeUrl(entry));
	189	debug(44, 1) (" always_direct = %d\n", psstate->always_direct);
	190	debug(44, 1) (" never_direct = %d\n", psstate->never_direct);
	191	debug(44, 1) (" timedout = %d\n", psstate->ping.timedout);
	192	}
44e237d0	193	psstate->ping.stop = current_time;
0bdf2621	194	psstate->request->hier.ping = psstate->ping;
db1cd23c	195	if (cbdataValid(data)) {
	196	psstate->servers = NULL;
	197	psstate->callback(fs, data);
	198	}
8407afee	199	cbdataUnlock(data);
348b2031	200	peerSelectStateFree(psstate);
93775f90	201	}
93775f90	202
b3264694	203	static int
	204	peerCheckNetdbDirect(ps_state * psstate)
	205	{
85223cd7	206	peer *p = whichPeer(&psstate->closest_parent_miss);
b3264694	207	int myrtt;
	208	int myhops;
	209	if (p == NULL)
	210	return 0;
	211	myrtt = netdbHostRtt(psstate->request->host);
0f8df3b0	212	debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d msec\n", myrtt);
0f8df3b0	213	debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d msec\n",
44e237d0	214	psstate->ping.p_rtt);
44e237d0	215	if (myrtt && myrtt < psstate->ping.p_rtt)
b3264694	216	return 1;
b3264694	217	myhops = netdbHostHops(psstate->request->host);
437e2060	218	debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
437e2060	219	debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
b3264694	220	Config.minDirectHops);
	221	if (myhops && myhops <= Config.minDirectHops)
	222	return 1;
	223	return 0;
	224	}
	225
93775f90	226	static void
511f47bb	227	peerSelectFoo(ps_state * ps)
062e2281	228	{
511f47bb	229	StoreEntry *entry = ps->entry;
511f47bb	230	request_t *request = ps->request;
7b665aeb	231	debug(44, 3) ("peerSelectFoo: '%s %s'\n",
b6c0e933	232	RequestMethodStr[request->method],
b6c0e933	233	request->host);
511f47bb	234	if (ps->direct == DIRECT_UNKNOWN) {
	235	if (ps->always_direct == 0 && Config.accessList.AlwaysDirect) {
	236	ps->acl_checklist = aclChecklistCreate(
	237	Config.accessList.AlwaysDirect,
	238	request,
	239	request->client_addr,
	240	NULL, /* user agent */
	241	NULL); /* ident */
	242	aclNBCheck(ps->acl_checklist,
	243	peerCheckAlwaysDirectDone,
	244	ps);
db1cd23c	245	return;
511f47bb	246	} else if (ps->always_direct > 0) {
	247	ps->direct = DIRECT_YES;
	248	} else if (ps->never_direct == 0 && Config.accessList.NeverDirect) {
	249	ps->acl_checklist = aclChecklistCreate(
	250	Config.accessList.NeverDirect,
	251	request,
	252	request->client_addr,
	253	NULL, /* user agent */
	254	NULL); /* ident */
	255	aclNBCheck(ps->acl_checklist,
	256	peerCheckNeverDirectDone,
	257	ps);
	258	return;
	259	} else if (ps->never_direct > 0) {
	260	ps->direct = DIRECT_NO;
	261	} else if (request->flags.loopdetect) {
	262	ps->direct = DIRECT_YES;
	263	} else {
	264	ps->direct = DIRECT_MAYBE;
	265	}
c971344c	266	debug(44, 3) ("peerSelectFoo: direct = %s\n",
511f47bb	267	DirectStr[ps->direct]);
db1cd23c	268	}
db1cd23c	269	if (entry->ping_status == PING_NONE) {
511f47bb	270	peerGetSomeNeighbor(ps);
db1cd23c	271	if (entry->ping_status == PING_WAITING)
	272	return;
	273	} else if (entry->ping_status == PING_WAITING) {
511f47bb	274	peerGetSomeNeighborReplies(ps);
db1cd23c	275	entry->ping_status = PING_DONE;
	276	}
	277	if (Config.onoff.prefer_direct)
511f47bb	278	peerGetSomeDirect(ps);
511f47bb	279	peerGetSomeParent(ps);
db1cd23c	280	if (!Config.onoff.prefer_direct)
511f47bb	281	peerGetSomeDirect(ps);
511f47bb	282	peerSelectCallback(ps);
db1cd23c	283	}
	284
	285	/*
	286	* peerGetSomeNeighbor
	287	*
	288	* Selects a neighbor (parent or sibling) based on one of the
	289	* following methods:
	290	* Cache Digests
	291	* CARP
	292	* Netdb RTT estimates
	293	* ICP/HTCP queries
	294	*/
	295	static void
	296	peerGetSomeNeighbor(ps_state * ps)
	297	{
	298	StoreEntry *entry = ps->entry;
	299	request_t *request = ps->request;
	300	peer *p;
	301	hier_code code = HIER_NONE;
	302	assert(entry->ping_status == PING_NONE);
	303	if (ps->direct == DIRECT_YES) {
	304	entry->ping_status = PING_DONE;
124511e5	305	return;
124511e5	306	}
6cfa8966	307	#if USE_CACHE_DIGESTS
db1cd23c	308	if ((p = neighborsDigestSelect(request, entry))) {
69c95dd3	309	code = CACHE_DIGEST_HIT;
db1cd23c	310	} else
afd88fbe	311	#endif
afd88fbe	312	#if USE_CARP
db1cd23c	313	if ((p = carpSelectParent(request))) {
	314	code = CARP;
	315	} else
c127134a	316	#endif
db1cd23c	317	if ((p = netdbClosestParent(request))) {
69c95dd3	318	code = CLOSEST_PARENT;
db1cd23c	319	} else if (peerSelectIcpPing(request, ps->direct, entry)) {
69c95dd3	320	debug(44, 3) ("peerSelect: Doing ICP pings\n");
db1cd23c	321	ps->ping.start = current_time;
db1cd23c	322	ps->ping.n_sent = neighborsUdpPing(request,
69c95dd3	323	entry,
86aebcda	324	peerHandlePingReply,
db1cd23c	325	ps,
	326	&ps->ping.n_replies_expected,
	327	&ps->ping.timeout);
	328	if (ps->ping.n_sent == 0)
69c95dd3	329	debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
db1cd23c	330	debug(44, 3) ("peerSelect: %d ICP replies expected, RTT %d msec\n",
	331	ps->ping.n_replies_expected, ps->ping.timeout);
	332	if (ps->ping.n_replies_expected > 0) {
69c95dd3	333	entry->ping_status = PING_WAITING;
	334	eventAdd("peerPingTimeout",
	335	peerPingTimeout,
db1cd23c	336	ps,
db1cd23c	337	0.001 * ps->ping.timeout,
52040193	338	0);
69c95dd3	339	return;
062e2281	340	}
062e2281	341	}
db1cd23c	342	if (code != HIER_NONE) {
	343	assert(p);
	344	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
	345	peerAddFwdServer(&ps->servers, p, code);
	346	}
	347	entry->ping_status = PING_DONE;
	348	}
	349
	350	/*
	351	* peerGetSomeNeighborReplies
	352	*
	353	* Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
	354	*/
	355	static void
	356	peerGetSomeNeighborReplies(ps_state * ps)
	357	{
	358	StoreEntry *entry = ps->entry;
	359	request_t *request = ps->request;
	360	peer *p = NULL;
	361	hier_code code = HIER_NONE;
	362	assert(entry->ping_status == PING_WAITING);
	363	assert(ps->direct != DIRECT_YES);
	364	if (peerCheckNetdbDirect(ps)) {
b3264694	365	code = CLOSEST_DIRECT;
b3264694	366	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
db1cd23c	367	peerAddFwdServer(&ps->servers, NULL, code);
	368	return;
	369	}
	370	if ((p = ps->hit)) {
	371	code = ps->hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
	372	} else
	373	#if ALLOW_SOURCE_PING
	374	if ((p = ps->secho)) {
	375	code = SOURCE_FASTEST;
	376	} else
	377	#endif
	378	if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
	379	p = whichPeer(&ps->closest_parent_miss);
b3264694	380	code = CLOSEST_PARENT_MISS;
db1cd23c	381	} else if (ps->first_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
db1cd23c	382	p = whichPeer(&ps->first_parent_miss);
429fdbec	383	code = FIRST_PARENT_MISS;
db1cd23c	384	}
db1cd23c	385	if (p && code != HIER_NONE) {
a3d5953d	386	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
db1cd23c	387	peerAddFwdServer(&ps->servers, p, code);
	388	}
	389	}
	390
	391
	392	/*
	393	* peerGetSomeDirect
	394	*
	395	* Simply adds a 'direct' entry to the FwdServers list if this
	396	* request can be forwarded directly to the origin server
	397	*/
	398	static void
	399	peerGetSomeDirect(ps_state * ps)
	400	{
	401	if (ps->direct == DIRECT_NO)
	402	return;
	403	if (ps->request->protocol == PROTO_WAIS)
	404	/* Its not really DIRECT, now is it? */
	405	peerAddFwdServer(&ps->servers, Config.Wais.peer, DIRECT);
	406	else
	407	peerAddFwdServer(&ps->servers, NULL, DIRECT);
	408	}
	409
	410	static void
	411	peerGetSomeParent(ps_state * ps)
	412	{
	413	peer *p;
	414	request_t *request = ps->request;
	415	hier_code code = HIER_NONE;
	416	debug(44, 3) ("peerGetSomeParent: %s %s\n",
	417	RequestMethodStr[request->method],
	418	request->host);
	419	if ((p = getDefaultParent(request))) {
	420	code = DEFAULT_PARENT;
	421	} else if ((p = getRoundRobinParent(request))) {
	422	code = ROUNDROBIN_PARENT;
	423	} else if ((p = getFirstUpParent(request))) {
	424	code = FIRSTUP_PARENT;
	425	} else if ((p = getAnyParent(request))) {
	426	code = ANY_OLD_PARENT;
	427	}
	428	if (code != HIER_NONE) {
a3d5953d	429	debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
db1cd23c	430	peerAddFwdServer(&ps->servers, p, code);
062e2281	431	}
	432	}
	433
d9586c3c	434	static void
93775f90	435	peerPingTimeout(void *data)
062e2281	436	{
b6c0e933	437	ps_state *psstate = data;
b6c0e933	438	StoreEntry *entry = psstate->entry;
fefb0227	439	if (entry)
	440	debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
	441	entry->ping_status = PING_TIMEOUT;
73a201f8	442	if (!cbdataValid(psstate->callback_data)) {
	443	/* request aborted */
	444	cbdataUnlock(psstate->callback_data);
0cdcddb9	445	peerSelectStateFree(psstate);
73a201f8	446	return;
73a201f8	447	}
75e88d56	448	PeerStats.timeouts++;
44e237d0	449	psstate->ping.timedout = 1;
b6c0e933	450	peerSelectFoo(psstate);
85034133	451	}
	452
	453	void
	454	peerSelectInit(void)
	455	{
75e88d56	456	memset(&PeerStats, '\0', sizeof(PeerStats));
9bdbfe33	457	assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
062e2281	458	}
93775f90	459
b3264694	460	static void
	461	peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
	462	{
	463	int rtt;
	464	int hops;
	465	if (Config.onoff.query_icmp) {
79a15e0a	466	if (header->flags & ICP_FLAG_SRC_RTT) {
b3264694	467	rtt = header->pad & 0xFFFF;
	468	hops = (header->pad >> 16) & 0xFFFF;
	469	if (rtt > 0 && rtt < 0xFFFF)
	470	netdbUpdatePeer(ps->request, p, rtt, hops);
44e237d0	471	if (rtt && (ps->ping.p_rtt == 0 \|\| rtt < ps->ping.p_rtt)) {
85223cd7	472	ps->closest_parent_miss = p->in_addr;
44e237d0	473	ps->ping.p_rtt = rtt;
b3264694	474	}
	475	}
	476	}
18ec72b2	477	/* if closest-only is set, then don't allow FIRST_PARENT_MISS */
cd196bc8	478	if (p->options.closest_only)
b3264694	479	return;
85223cd7	480	/* set FIRST_MISS if there is no CLOSEST parent */
85223cd7	481	if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
b3264694	482	return;
44e237d0	483	rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
44e237d0	484	if (ps->ping.w_rtt == 0 \|\| rtt < ps->ping.w_rtt) {
85223cd7	485	ps->first_parent_miss = p->in_addr;
44e237d0	486	ps->ping.w_rtt = rtt;
b3264694	487	}
b3264694	488	}
93775f90	489
b6c0e933	490	static void
b3264694	491	peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
93775f90	492	{
b6c0e933	493	ps_state *psstate = data;
b3264694	494	icp_opcode op = header->opcode;
f9e5a344	495	debug(44, 3) ("peerHandleIcpReply: %s %s\n",
27cd7235	496	icp_opcode_str[op],
9fb13bb6	497	storeUrl(psstate->entry));
69c95dd3	498	#if USE_CACHE_DIGESTS && 0
26b164ac	499	/* do cd lookup to count false misses */
3ab66981	500	if (p && request)
4b4cd312	501	peerNoteDigestLookup(request, p,
3ab66981	502	peerDigestLookup(p, request, psstate->entry));
26b164ac	503	#endif
44e237d0	504	psstate->ping.n_recv++;
27cd7235	505	if (op == ICP_MISS \|\| op == ICP_DECHO) {
b3264694	506	if (type == PEER_PARENT)
b3264694	507	peerIcpParentMiss(p, header, psstate);
a7c05555	508	} else if (op == ICP_HIT) {
db1cd23c	509	psstate->hit = p;
	510	psstate->hit_type = type;
	511	peerSelectFoo(psstate);
93775f90	512	return;
db1cd23c	513	}
	514	#if ALLOW_SOURCE_PING
	515	else if (op == ICP_SECHO) {
	516	psstate->secho = p;
	517	peerSelectFoo(psstate);
93775f90	518	return;
93775f90	519	}
db1cd23c	520	#endif
44e237d0	521	if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
93775f90	522	return;
b6c0e933	523	peerSelectFoo(psstate);
93775f90	524	}
86aebcda	525
	526	#if USE_HTCP
	527	static void
44e237d0	528	peerHandleHtcpReply(peer * p, peer_t type, htcpReplyData * htcp, void *data)
86aebcda	529	{
86aebcda	530	ps_state *psstate = data;
44e237d0	531	request_t *request = psstate->request;
	532	debug(44, 3) ("peerHandleIcpReply: %s %s\n",
	533	htcp->hit ? "HIT" : "MISS",
	534	storeUrl(psstate->entry));
	535	psstate->ping.n_recv++;
	536	if (htcp->hit) {
db1cd23c	537	psstate->hit = p;
	538	psstate->hit_type = type;
	539	peerSelectFoo(psstate);
44e237d0	540	return;
	541	}
	542	if (type == PEER_PARENT)
	543	peerHtcpParentMiss(p, htcp, psstate);
	544	if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
	545	return;
	546	peerSelectFoo(psstate);
	547	}
	548
	549	static void
	550	peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
	551	{
	552	int rtt;
	553	int hops;
	554	if (Config.onoff.query_icmp) {
	555	if (htcp->cto.rtt > 0) {
	556	rtt = (int) htcp->cto.rtt * 1000;
	557	hops = (int) htcp->cto.hops * 1000;
	558	netdbUpdatePeer(ps->request, p, rtt, hops);
	559	if (rtt && (ps->ping.p_rtt == 0 \|\| rtt < ps->ping.p_rtt)) {
	560	ps->closest_parent_miss = p->in_addr;
	561	ps->ping.p_rtt = rtt;
	562	}
	563	}
	564	}
	565	/* if closest-only is set, then don't allow FIRST_PARENT_MISS */
cd196bc8	566	if (p->options.closest_only)
44e237d0	567	return;
	568	/* set FIRST_MISS if there is no CLOSEST parent */
	569	if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
	570	return;
	571	rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
	572	if (ps->ping.w_rtt == 0 \|\| rtt < ps->ping.w_rtt) {
	573	ps->first_parent_miss = p->in_addr;
	574	ps->ping.w_rtt = rtt;
	575	}
86aebcda	576	}
	577	#endif
	578
	579	static void
9ef28b60	580	peerHandlePingReply(peer * p, peer_t type, protocol_t proto, void pingdata, void data)
86aebcda	581	{
86aebcda	582	if (proto == PROTO_ICP)
9ef28b60	583	peerHandleIcpReply(p, type, pingdata, data);
86aebcda	584	#if USE_HTCP
86aebcda	585	else if (proto == PROTO_HTCP)
9ef28b60	586	peerHandleHtcpReply(p, type, pingdata, data);
86aebcda	587	#endif
	588	else
	589	debug(44, 1) ("peerHandlePingReply: unknown protocol_t %d\n", (int) proto);
	590	}
db1cd23c	591
	592	static void
	593	peerAddFwdServer(FwdServer ** FS, peer * p, hier_code code)
	594	{
	595	FwdServer *fs = memAllocate(MEM_FWD_SERVER);
	596	debug(44, 5) ("peerAddFwdServer: adding %s %s\n",
	597	p ? p->host : "DIRECT",
	598	hier_strings[code]);
	599	fs->peer = p;
	600	fs->code = code;
	601	cbdataLock(fs->peer);
	602	while (*FS)
	603	FS = &(*FS)->next;
	604	*FS = fs;
	605	}