peer_select.c

-

/*
 * $Id: peer_select.c,v 1.98.2.3 1999/05/11 20:37:05 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,
		request->my_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,
		request->my_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 == NULL) {
	(void) 0;
    } else 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);