delay_pools.c

-

/*
 * $Id: delay_pools.c,v 1.7.2.9 1999/05/12 18:49:19 wessels Exp $
 *
 * DEBUG: section 77    Delay Pools
 * AUTHOR: David Luyer <[e-mail]>
 *
 * 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 "config.h"

#if DELAY_POOLS
#include "squid.h"

struct _class1DelayPool {
    int aggregate;
};

struct _class2DelayPool {
    int aggregate;
    /* OK: -1 is terminator.  individual[255] is always host 255. */
    /* 255 entries + 1 terminator byte */
    unsigned char individual_map[256];
    unsigned char individual_255_used;
    /* 256 entries */
    int individual[256];
};

struct _class3DelayPool {
    int aggregate;
    /* OK: -1 is terminator.  network[255] is always host 255. */
    /* 255 entries + 1 terminator byte */
    unsigned char network_map[256];
    unsigned char network_255_used;
    /* 256 entries */
    int network[256];
    /* 256 sets of (255 entries + 1 terminator byte) */
    unsigned char individual_map[256][256];
    /* Pack this into one bit per net */
    unsigned char individual_255_used[32];
    /* largest entry = (255<<8)+255 = 65535 */
    int individual[65536];
};

typedef struct _class1DelayPool class1DelayPool;
typedef struct _class2DelayPool class2DelayPool;
typedef struct _class3DelayPool class3DelayPool;

union _delayPool {
    class1DelayPool *class1;
    class2DelayPool *class2;
    class3DelayPool *class3;
};

typedef union _delayPool delayPool;

static delayPool *delay_data = NULL;
static fd_set delay_no_delay;
static time_t delay_pools_last_update = 0;
static hash_table *delay_id_ptr_hash = NULL;

static OBJH delayPoolStats;

static unsigned int
delayIdPtrHash(const void *key, unsigned int n)
{
    /* Hashes actual POINTER VALUE.
     * Assumes <= 256 hash buckets & even hash size.
     * Assumes the most variation in pointers to inside
     * medium size objects occurs in the 2nd and 3rd
     * least significant bytes.
     */
    const char *ptr = (char *) &key;
#if SIZEOF_VOID_P == 4
    return (ptr[1] ^ ptr[2]) & (n - 1);
#elif SIZEOF_VOID_P == 8
#if WORDS_BIGENDIAN
    return (ptr[5] ^ ptr[6]) & (n - 1);
#else
    return (ptr[1] ^ ptr[2]) & (n - 1);
#endif
#else
#error What kind of a sick architecture are you on anyway?
#endif
}

static int
delayIdPtrHashCmp(const void *a, const void *b)
{
    /*
     * Compare POINTER VALUE.
     * Note, we can't subtract void pointers, but we don't need
     * to anyway.  All we need is a test for equality.
     */
    return a != b;
}

void
delayPoolsInit(void)
{
    delay_pools_last_update = getCurrentTime();
    FD_ZERO(&delay_no_delay);
    cachemgrRegister("delay", "Delay Pool Levels", delayPoolStats, 0, 1);
}

void
delayInitDelayData(unsigned short pools)
{
    if (!pools)
	return;
    delay_data = xcalloc(pools, sizeof(delayPool));
    eventAdd("delayPoolsUpdate", delayPoolsUpdate, NULL, 1.0, 1);
    delay_id_ptr_hash = hash_create(delayIdPtrHashCmp, 256, delayIdPtrHash);
}

static void
delayIdZero(void *hlink)
{
    hash_link *h = hlink;
    delay_id *id = (delay_id *) h->key;
    *id = 0;
    xfree(h);
}

void
delayFreeDelayData()
{
    safe_free(delay_data);
    if (!delay_id_ptr_hash)
	return;
    hashFreeItems(delay_id_ptr_hash, delayIdZero);
    hashFreeMemory(delay_id_ptr_hash);
    delay_id_ptr_hash = NULL;
}

void
delayRegisterDelayIdPtr(delay_id * loc)
{
    hash_link *lnk;
    if (!delay_id_ptr_hash)
	return;
    if (*loc == 0)
	return;
    lnk = xmalloc(sizeof(hash_link));
    lnk->key = (char *) loc;
    hash_join(delay_id_ptr_hash, lnk);
}

void
delayUnregisterDelayIdPtr(delay_id * loc)
{
    hash_link *lnk;
    if (!delay_id_ptr_hash)
	return;
    /*
     * If we went through a reconfigure, then all the delay_id's
     * got set to zero, and they were removed from our hash
     * table.
     */
    if (*loc == 0)
	return;
    lnk = hash_lookup(delay_id_ptr_hash, loc);
    assert(lnk);
    hash_remove_link(delay_id_ptr_hash, lnk);
    xxfree(lnk);
}

void
delayCreateDelayPool(unsigned short pool, u_char class)
{
    switch (class) {
    case 1:
	delay_data[pool].class1 = xmalloc(sizeof(class1DelayPool));
	break;
    case 2:
	delay_data[pool].class2 = xmalloc(sizeof(class2DelayPool));
	break;
    case 3:
	delay_data[pool].class3 = xmalloc(sizeof(class3DelayPool));
	break;
    default:
	assert(0);
    }
}

void
delayInitDelayPool(unsigned short pool, u_char class, delaySpecSet * rates)
{
    /* delaySetSpec may be pointer to partial structure so MUST pass by
     * reference.
     */
    switch (class) {
    case 1:
	delay_data[pool].class1->aggregate = (rates->aggregate.max_bytes *
	    Config.Delay.initial) / 100;
	break;
    case 2:
	delay_data[pool].class2->aggregate = (rates->aggregate.max_bytes *
	    Config.Delay.initial) / 100;
	delay_data[pool].class2->individual_map[0] = 255;
	delay_data[pool].class2->individual_255_used = 0;
	break;
    case 3:
	delay_data[pool].class3->aggregate = (rates->aggregate.max_bytes *
	    Config.Delay.initial) / 100;
	delay_data[pool].class3->network_map[0] = 255;
	delay_data[pool].class3->network_255_used = 0;
	memset(&delay_data[pool].class3->individual_255_used, '\0',
	    sizeof(delay_data[pool].class3->individual_255_used));
	break;
    default:
	assert(0);
    }
}

void
delayFreeDelayPool(unsigned short pool)
{
    /* this is a union - and all free() cares about is the pointer location */
    safe_free(delay_data[pool].class1);
}

void
delaySetNoDelay(int fd)
{
    FD_SET(fd, &delay_no_delay);
}

void
delayClearNoDelay(int fd)
{
    FD_CLR(fd, &delay_no_delay);
}

int
delayIsNoDelay(int fd)
{
    return FD_ISSET(fd, &delay_no_delay);
}

static delay_id
delayId(unsigned short pool, unsigned short position)
{
    return (pool << 16) | position;
}

delay_id
delayClient(request_t * r)
{
    aclCheck_t ch;
    int i;
    int j;
    unsigned int host;
    unsigned short pool, position;
    unsigned char class, net;

    memset(&ch, '\0', sizeof(ch));
    ch.src_addr = r->client_addr;
    ch.my_addr = r->my_addr;
    ch.request = r;
    for (pool = 0; pool < Config.Delay.pools; pool++) {
	if (aclCheckFast(Config.Delay.access[pool], &ch))
	    break;
    }
    if (pool == Config.Delay.pools)
	return delayId(0, 0);
    class = Config.Delay.class[pool];
    if (class == 0)
	return delayId(0, 0);
    if (class == 1)
	return delayId(pool + 1, 0);
    if (class == 2) {
	host = ntohl(ch.src_addr.s_addr) & 0xff;
	if (host == 255) {
	    if (!delay_data[pool].class2->individual_255_used) {
		delay_data[pool].class2->individual_255_used = 1;
		delay_data[pool].class2->individual[255] =
		    (Config.Delay.rates[pool]->individual.max_bytes *
		    Config.Delay.initial) / 100;
	    }
	    return delayId(pool + 1, 255);
	}
	for (i = 0;; i++) {
	    if (delay_data[pool].class2->individual_map[i] == host)
		break;
	    if (delay_data[pool].class2->individual_map[i] == 255) {
		delay_data[pool].class2->individual_map[i] = host;
		delay_data[pool].class2->individual_map[i + 1] = 255;
		delay_data[pool].class2->individual[i] =
		    (Config.Delay.rates[pool]->individual.max_bytes *
		    Config.Delay.initial) / 100;
		break;
	    }
	}
	return delayId(pool + 1, i);
    }
    /* class == 3 */
    host = ntohl(ch.src_addr.s_addr) & 0xffff;
    net = host >> 8;
    host &= 0xff;
    if (net == 255) {
	i = 255;
	if (!delay_data[pool].class3->network_255_used) {
	    delay_data[pool].class3->network_255_used = 1;
	    delay_data[pool].class3->network[255] =
		(Config.Delay.rates[pool]->network.max_bytes *
		Config.Delay.initial) / 100;
	}
    } else {
	for (i = 0;; i++) {
	    if (delay_data[pool].class3->network_map[i] == net)
		break;
	    if (delay_data[pool].class3->network_map[i] == 255) {
		delay_data[pool].class3->network_map[i] = net;
		delay_data[pool].class3->individual_map[i][0] = 255;
		delay_data[pool].class3->network_map[i + 1] = 255;
		delay_data[pool].class3->network[i] =
		    (Config.Delay.rates[pool]->network.max_bytes *
		    Config.Delay.initial) / 100;
		break;
	    }
	}
    }
    position = i << 8;
    if (host == 255) {
	position |= 255;
	if (!(delay_data[pool].class3->individual_255_used[i / 8] & (1 << (i % 8)))) {
	    delay_data[pool].class3->individual_255_used[i / 8] |= (1 << (i % 8));
	    delay_data[pool].class3->individual[position] =
		(Config.Delay.rates[pool]->individual.max_bytes *
		Config.Delay.initial) / 100;
	}
	return delayId(pool + 1, position);
    }
    for (j = 0;; j++) {
	if (delay_data[pool].class3->individual_map[i][j] == host) {
	    position |= j;
	    break;
	}
	if (delay_data[pool].class3->individual_map[i][j] == 255) {
	    delay_data[pool].class3->individual_map[i][j] = host;
	    delay_data[pool].class3->individual_map[i][j + 1] = 255;
	    delay_data[pool].class3->individual[position |= j] =
		(Config.Delay.rates[pool]->individual.max_bytes *
		Config.Delay.initial) / 100;
	    break;
	}
    }
    return delayId(pool + 1, position);
}

static void
delayUpdateClass1(class1DelayPool * class1, delaySpecSet * rates, int incr)
{
    /* delaySetSpec may be pointer to partial structure so MUST pass by
     * reference.
     */
    if (rates->aggregate.restore_bps != -1 &&
	(class1->aggregate += rates->aggregate.restore_bps * incr) >
	rates->aggregate.max_bytes)
	class1->aggregate = rates->aggregate.max_bytes;
}

static void
delayUpdateClass2(class2DelayPool * class2, delaySpecSet * rates, int incr)
{
    int restore_bytes;
    unsigned char i;
    /* delaySetSpec may be pointer to partial structure so MUST pass by
     * reference.
     */
    if (rates->aggregate.restore_bps != -1 &&