directiplookup.cc

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

// -*- c-basic-offset: 4 -*-
/*
 * directiplookup.{cc,hh} -- lookup for output port and next-hop gateway
 * in one to max. two DRAM accesses with potential CPU cache / TLB misses
 * Marko Zec
 *
 * Copyright (c) 2005 International Computer Science Institute
 * Copyright (c) 2005 University of Zagreb
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
 */

#include <click/config.h>
#include "directiplookup.hh"
#include <click/ipaddress.hh>
#include <click/straccum.hh>
#include <click/router.hh>
#include <click/error.hh>
CLICK_DECLS


// DIRECTIPLOOKUP::TABLE

// The DirectIPLookup table must be stored in a sub-object in the Linux
// kernel, because it's too large to be allocated all at once.

int
DirectIPLookup::Table::initialize()
{
    assert(!_tbl_0_23 && !_tbl_24_31 && !_vport && !_rtable && !_rt_hashtbl
	   && !_tbl_0_23_plen && !_tbl_24_31_plen);

    _tbl_24_31_capacity = 4096;
    _vport_capacity = 1024;
    _rtable_capacity = 2048;

    if ((_tbl_0_23 = (uint16_t *) CLICK_LALLOC((sizeof(uint16_t) + sizeof(uint8_t)) * (1 << 24)))
	&& (_tbl_24_31 = (uint16_t *) CLICK_LALLOC((sizeof(uint16_t) + sizeof(uint8_t)) * _tbl_24_31_capacity))
	&& (_vport = (VirtualPort *) CLICK_LALLOC(sizeof(VirtualPort) * _vport_capacity))
	&& (_rtable = (CleartextEntry *) CLICK_LALLOC(sizeof(CleartextEntry) * _rtable_capacity))
	&& (_rt_hashtbl = (int *) CLICK_LALLOC(sizeof(int) * PREF_HASHSIZE))) {
	_tbl_0_23_plen = (uint8_t *) (_tbl_0_23 + (1 << 24));
	_tbl_24_31_plen = (uint8_t *) (_tbl_24_31 + _tbl_24_31_capacity);
	return 0;
    } else
	return -ENOMEM;
}

void
DirectIPLookup::Table::cleanup()
{
    CLICK_LFREE(_tbl_0_23, (sizeof(uint16_t) + sizeof(uint8_t)) * (1 << 24));
    CLICK_LFREE(_tbl_24_31, (sizeof(uint16_t) + sizeof(uint8_t)) * _tbl_24_31_capacity);
    CLICK_LFREE(_vport, sizeof(VirtualPort) * _vport_capacity);
    CLICK_LFREE(_rtable, sizeof(CleartextEntry) * _rtable_capacity);
    CLICK_LFREE(_rt_hashtbl, sizeof(int) * PREF_HASHSIZE);
    _tbl_0_23 = _tbl_24_31 = 0;
    _vport = 0;
    _rtable = 0;
    _tbl_0_23_plen = _tbl_24_31_plen = 0;
    _rt_hashtbl = 0;
}


inline uint32_t
DirectIPLookup::Table::prefix_hash(uint32_t prefix, uint32_t len)
{
    // An arbitrary hash function - it'd better be good...
    uint32_t hash = prefix ^ (len << 5) ^ ((prefix >> (len >> 2)) - len);
    hash ^= (hash >> 23) ^ ((hash >> 15) * len) ^ ((prefix >> 17) * 53);
    hash -= (prefix >> 3) ^ ((hash >> len) * 7) ^ ((hash >> 11) * 103);
    hash =  (hash ^ (hash >> 17)) & (PREF_HASHSIZE - 1);

    return hash;
}

void
DirectIPLookup::Table::flush()
{
    memset(_rt_hashtbl, -1, sizeof(int) * PREF_HASHSIZE);

    // _vport[0] is our "discard" port
    _vport_head = 0;
    _vport[0].ll_prev = -1;
    _vport[0].ll_next = -1;
    _vport[0].refcount = 1;		// _rtable[0] will point to _vport[0]
    _vport[0].gw = IPAddress(0);
    _vport[0].port = DISCARD_PORT;
    _vport_size = 1;
    _vport_empty_head = -1;

    // _rtable[0] is the default route entry
    _rt_hashtbl[prefix_hash(0, 0)] = 0;
    _rtable[0].ll_prev = -1;
    _rtable[0].ll_next = -1;
    _rtable[0].prefix = 0;
    _rtable[0].plen = 0;
    _rtable[0].vport = 0;
    _rtable_size = 1;
    _rt_empty_head = -1;

    // Bzeroed lookup tables resolve 0.0.0.0/0 to _vport[0]
    memset(_tbl_0_23, 0, (sizeof(uint16_t) + sizeof(uint8_t)) * (1 << 24));

    _tbl_24_31_size = 0;
    _tbl_24_31_empty_head = 0x8000;
}

String
DirectIPLookup::Table::dump() const
{
    StringAccum sa;
    for (uint32_t i = 0; i < PREF_HASHSIZE; i++)
	for (int rt_i = _rt_hashtbl[i]; rt_i >= 0; rt_i = _rtable[rt_i].ll_next) {
	    const CleartextEntry &rt = _rtable[rt_i];
	    if (_vport[rt.vport].port != -1) {
		IPRoute route = IPRoute(IPAddress(htonl(rt.prefix)), IPAddress::make_prefix(rt.plen), _vport[rt.vport].gw, _vport[rt.vport].port);
		route.unparse(sa, true) << '\n';
	    }
	}
    return sa.take_string();
}

int
DirectIPLookup::Table::vport_find(IPAddress gw, int16_t port)
{
    for (int vp = _vport_head; vp >= 0; vp = _vport[vp].ll_next)
	if (_vport[vp].gw == gw && _vport[vp].port == port)
	    return vp;
    if (_vport_empty_head < 0 && _vport_size == _vport_capacity) {
	if (_vport_capacity == vport_capacity_limit)
	    return -ENOMEM;
	VirtualPort *new_vport = (VirtualPort *) CLICK_LALLOC(sizeof(VirtualPort) * 2 * _vport_capacity);
	if (!new_vport)
	    return -ENOMEM;
	memcpy(new_vport, _vport, sizeof(VirtualPort) * _vport_capacity);
	CLICK_LFREE(_vport, sizeof(VirtualPort) * _vport_capacity);
	_vport = new_vport;
	_vport_capacity *= 2;
    }
    if (_vport_empty_head < 0) {
	_vport[_vport_size].ll_next = _vport_empty_head;
	_vport_empty_head = _vport_size;
	++_vport_size;
    }
    _vport[_vport_empty_head].refcount = 0;
    return _vport_empty_head;
}

void
DirectIPLookup::Table::vport_unref(uint16_t vport_i)
{
    if (--_vport[vport_i].refcount == 0) {
	int16_t prev, next;

	// Prune our entry from the vport list
	prev = _vport[vport_i].ll_prev;
	next = _vport[vport_i].ll_next;
	if (prev >= 0)
	    _vport[prev].ll_next = next;
	else
	    _vport_head = next;
	if (next >= 0)
	    _vport[next].ll_prev = prev;

	// Add the entry to empty vports list
	_vport[vport_i].ll_next = _vport_empty_head;
	_vport_empty_head = vport_i;
    }
}

int
DirectIPLookup::Table::find_entry(uint32_t prefix, uint32_t plen) const
{
    int hash = prefix_hash(prefix, plen);
    for (int rt_i = _rt_hashtbl[hash]; rt_i >= 0; rt_i = _rtable[rt_i].ll_next)
	if (_rtable[rt_i].prefix == prefix && _rtable[rt_i].plen == plen)
	    return rt_i;
    return -1;
}

int
DirectIPLookup::Table::add_route(const IPRoute& route, bool allow_replace, IPRoute* old_route, ErrorHandler *errh)
{
    uint32_t prefix = ntohl(route.addr.addr());
    uint32_t plen = route.prefix_len();

    int rt_i = find_entry(prefix, plen);
    if (rt_i >= 0) {
	// Attempt to replace an existing route.
	// Save the old route if requested so that a rollback can be performed.
	if ((rt_i != 0 || (rt_i == 0 && _vport[0].port != DISCARD_PORT)) &&
	    old_route)
	    *old_route = IPRoute(IPAddress(htonl(_rtable[rt_i].prefix)),
				 IPAddress::make_prefix(_rtable[rt_i].plen),
				 _vport[_rtable[rt_i].vport].gw,
				 _vport[_rtable[rt_i].vport].port);
	if (rt_i == 0) {
	    // We actually only update the vport entry for the default route
	    if (_vport[0].port != DISCARD_PORT && !allow_replace)
		return -EEXIST;
	    _vport[0].gw = route.gw;
	    _vport[0].port = route.port;
	    return 0;
	}
	// Check if we allow for atomic route replacements at all
	if (!allow_replace)
	    return -EEXIST;
	vport_unref(_rtable[rt_i].vport);

    } else {
	// Attempt to allocate a new _rtable[] entry.
	if (_rt_empty_head < 0 && _rtable_size == _rtable_capacity) {
	    CleartextEntry *new_rtable = (CleartextEntry *) CLICK_LALLOC(sizeof(CleartextEntry) * _rtable_capacity * 2);
	    if (!new_rtable)
		return -ENOMEM;
	    memcpy(new_rtable, _rtable, sizeof(CleartextEntry) * _rtable_capacity);
	    CLICK_LFREE(_rtable, sizeof(CleartextEntry) * _rtable_capacity);
	    _rtable = new_rtable;
	    _rtable_capacity *= 2;
	}
	if (_rt_empty_head < 0) {
	    _rtable[_rtable_size].ll_next = _rt_empty_head;
	    _rt_empty_head = _rtable_size;
	    ++_rtable_size;
	}
	rt_i = _rt_empty_head;
    }

    // find vport index
    int vport_i = vport_find(route.gw, route.port);
    if (vport_i < 0)
	return vport_i;

    // find overflow table space
    int start = prefix >> 8;
    int end = start + (plen < 24 ? 1 << (24 - plen) : 1);
    if (plen > 24 && !(_tbl_0_23[start] & 0x8000)
	&& (_tbl_24_31_empty_head & 0x8000) != 0) {
	if (_tbl_24_31_size == _tbl_24_31_capacity
	    && _tbl_24_31_capacity >= tbl_24_31_capacity_limit)
	    return -ENOMEM;
	if (_tbl_24_31_size == _tbl_24_31_capacity) {
	    uint16_t *new_tbl = (uint16_t *) CLICK_LALLOC((sizeof(uint16_t) + sizeof(uint8_t)) * 2 * _tbl_24_31_capacity);
	    if (!new_tbl)
		return -ENOMEM;
	    memcpy(new_tbl, _tbl_24_31, sizeof(uint16_t) * _tbl_24_31_capacity);
	    memcpy(new_tbl + _tbl_24_31_capacity, _tbl_24_31_plen, sizeof(uint8_t) * _tbl_24_31_capacity);
	    CLICK_LFREE(_tbl_24_31, (sizeof(uint16_t) + sizeof(uint8_t)) * _tbl_24_31_capacity);
	    _tbl_24_31 = new_tbl;
	    _tbl_24_31_plen = (uint8_t *) (new_tbl + 2 * _tbl_24_31_capacity);
	    _tbl_24_31_capacity *= 2;
	}
	_tbl_24_31_empty_head = _tbl_24_31_size >> 8;
	_tbl_24_31[_tbl_24_31_empty_head << 8] = 0x8000;
	_tbl_24_31_size += 256;
    }

    // At this point we have successfully allocated all memory.
    if (rt_i == _rt_empty_head) {
	_rt_empty_head = _rtable[rt_i].ll_next;

	_rtable[rt_i].prefix = prefix;	// in host-order format
	_rtable[rt_i].plen = plen;

	// Insert the new entry in our hashtable
	uint32_t hash = prefix_hash(prefix, plen);
	_rtable[rt_i].ll_prev = -1;
	_rtable[rt_i].ll_next = _rt_hashtbl[hash];
	if (_rt_hashtbl[hash] >= 0)
	    _rtable[_rt_hashtbl[hash]].ll_prev = rt_i;
	_rt_hashtbl[hash] = rt_i;
    }

    if (vport_i == _vport_empty_head) {
	_vport_empty_head = _vport[vport_i].ll_next;
	_vport[vport_i].refcount = 0;
	_vport[vport_i].gw = route.gw;
	_vport[vport_i].port = route.port;

	// Add the entry to the vport linked list