binding.c

mobile ip 在linux下的一种实现

/* $Id: binding.c,v 1.33 2001/02/17 15:29:55 jm Exp $
 * Mobility bindings used in FAs and HAs.
 *
 * Dynamic hierarchial IP tunnel
 * Copyright (C) 1998-2001, Dynamics group
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See README and COPYING for
 * more details.
 */

#define DEBUG_FLAG 'B'

#include "owntypes.h"

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <time.h>
#include <assert.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#include "binding.h"
#include "debug.h"

/* Home and foreign agents keep track of
 * registered mobile nodes with mobility bindings. */

/*
 * Bindings have a lifetime. The current time in seconds
 * since 0:00:00 UTC, January 1, 1970 can be retrieved with the time
 * system call (see man 2 time). The expiration time for a binding
 * is set in exp_time. When the current time is equal to or
 * more than exp_time the binding should be removed.
 *
 * Both foreign and home agents need to know where to forward
 * packets destined for the mobile node; this is indicated by the
 * lower_addr field. The session key for the tunnel is stored
 * in the key field. The corresponding security parameter index for
 * authentication method used is stored in the spi field.
 */

struct bindingtable {
	struct hashtable *hashtable;    /* hash table for bindings */
	unsigned int hashtablesize;     /* number of entries in hash table */
	struct list *shorttimelist;     /* short time list (STL) table */
	unsigned int shorttimelistsize; /* amount of entries in STL table */
	struct list longtimelist;	/* should be empty all the time */
	struct list noexptimelist;	/* entries that do not expire */
	unsigned int firstindex;        /* entry to be reported next */
	unsigned int currentindex;	/* current time index */
};

/* defines */

#define ASSERT assert

#ifndef FALSE
#define FALSE 0
#endif

#ifndef TRUE
#define TRUE 1
#endif

/* Test cases */

/*#define BINDING_TEST_CASE_I05*/
/*TEST CASE I10: MANUALLY*/
/*#define BINDING_TEST_CASE_I12*/

/* prototypes */

static int binding_hash(void *key, const int tablesize);
static int binding_compare(void *key, struct node *cmprd);
static int binding_getexpired_alreadyexpired(struct bindingtable *table,
					     int idx, int *checklongtimelist,
					     int *listempty);
static int binding_getexpired_advance(struct bindingtable *table, int advance,
				      int idx, int *checklongtimelist);
static int binding_getexpired_checkmaxadvancetime(struct bindingtable *table,
						  int left, int *advance);
static void binding_check_longtimelist(struct bindingtable *table,
				       const int advance);

/* "Ixx" are test case IDs to help in the design of the test module */

/* Init binding table
 *
 * INPUT VALUES:
 *
 * I01) maxbindings is negative
 * I02) maxbindings is zero
 * I03) maxlifetime is negative
 * I04) maxlifetime is zero (valid value)
 * I05) not enough memory for struct bindingtable (difficult to test autom.)
 *      - requires changes in code, will be tested manually
 * I06) maxbindings is too large for malloc to succeed (not enough memory)
 * I07) maxlifetime is too large for malloc to succeed (not enough memory)
 * I08) realistic values
 */

/**
 * binding_init:
 * @maxbindings:
 * @maxlifetime:
 *
 * Initializes a bindingtable for storing bindings.
 *
 * Returns: A reference that is used in further operations on 
 *          the bindingtable.
 */
struct bindingtable *
binding_init(const int maxbindings, const int maxlifetime)
{
	int i;
	struct bindingtable *table;

	if (maxbindings < 1) {
		DEBUG(DEBUG_FLAG,
		      "binding_init: maxbindings must be at least 1\n");
		return NULL;
	}
	if (maxlifetime < 0) {
		DEBUG(DEBUG_FLAG,
		      "binding_init: maxlifetime must be positive\n");
		return NULL;
	}
#ifdef BINDING_TEST_CASE_I05
	table = NULL;
#else
	table = malloc(sizeof(struct bindingtable));
#endif
	if (table == NULL) {
		DEBUG(DEBUG_FLAG,
			"binding_init: not enough memory for "
			"struct bindingtable\n");
		return NULL;
	}

	i = (maxbindings > MAX_BINDING_HASH ? MAX_BINDING_HASH : maxbindings);
	table->hashtablesize = hashtable_find_prime(2 * i);
	ASSERT(table->hashtablesize > 0);
	ASSERT(table->hashtablesize >= 2 * i);
	table->hashtable = hashtable_init(table->hashtablesize);
	if (table->hashtable == NULL) {
		DEBUG(DEBUG_FLAG,
			"binding_init: hash table creation failed\n");
		free(table);
		return NULL;
	}
	if (maxlifetime >= MAX_BINDING_SHORT_LIST)
		table->shorttimelistsize = MAX_BINDING_SHORT_LIST;
	else
		table->shorttimelistsize = maxlifetime + 1;
	table->shorttimelist = malloc(table->shorttimelistsize *
				      sizeof(struct list));
	if (table->shorttimelist == NULL) {
		DEBUG(DEBUG_FLAG,
			"binding_init: not enough memory for "
			"a table of %d 'struct list' items\n",
			table->shorttimelistsize);
		hashtable_destroy(table->hashtable);
		free(table);
		return NULL;
	}
	for (i = 0; i < table->shorttimelistsize; i++) {
		list_init(&table->shorttimelist[i]);
	}
	list_init(&table->longtimelist);
	list_init(&table->noexptimelist);
	table->firstindex = 0;
	table->currentindex = 0;
	return table;
}

/* Destroy all bindings
 *
 * NOTE! All entries must be removed before calling this!
 *
 * INPUT VALUES:
 *
 * I09) Table is empty
 * I10) Table is not empty (difficult to test automatically, assertions fail)
 *      - test will be done manually
 */

/**
 * binding_destroy:
 * @table:
 *
 * Destroy all bindings. binding_destroy() should be called to destroy a
 * bindingtable when it is not needed any more. All entries from the table
 * must be removed before doing this.
 */
void
binding_destroy(struct bindingtable *table)
{
	int i;

	ASSERT(table != NULL);
	for (i = 0; i < table->shorttimelistsize; i++) {
		ASSERT(list_is_empty(&table->shorttimelist[i]) == TRUE);
	}
	ASSERT(list_is_empty(&table->longtimelist) == TRUE);
	ASSERT(list_is_empty(&table->noexptimelist) == TRUE);
	free(table->shorttimelist);
	hashtable_destroy(table->hashtable);
	free(table);
}

/* Add binding
 *
 * INPUT VALUES:
 *
 * I11) Timeout is less than zero
 * I12) Unable to add to hashtable (this requires a buggy hash function)
 *      - requires changes in code, test will be done manually
 * I13) Timeout is longer than shorttimelistsize
 * I14) Timeout is longer than maxuseshortlist (expired bindings exist)
 * I15) Timeout is a reasonable value (~ less than firstindex - currentindex)
 *
 */

/**
 * binding_add:
 * @table:
 * @entry:
 *
 * Adds a bindingentry into the bindingtable.
 *
 * NOTE: Use binding_getexpired() to advance the timer to current time before
 * adding new bindings. And for optimal performance, process all expired
 * bindings before adding new ones.
 *
 * Returns: TRUE on success
 */
int
binding_add(struct bindingtable *table, struct bindingentry *entry)
{
	int idx, maxuseshortlist;
	struct list *addlist;

	ASSERT(table != NULL);
	ASSERT(entry != NULL);
	if (entry->timeout < 0) {
		DEBUG(DEBUG_FLAG,
			"binding_add: unable to add entry with timeout %d "
			"that is less than zero\n",
			entry->timeout);
		return FALSE;
	}
	DEBUG(DEBUG_FLAG,
	      "binding_add: entry = 0x%08x, &entry->mn_addr = 0x%08x\n",
	      (int) entry, (int) &entry->mn_addr);
	DEBUG(DEBUG_FLAG, "\tkey: (MN=%s,HA=", inet_ntoa(entry->mn_addr));
	DEBUG(DEBUG_FLAG, "%s)\n", inet_ntoa(entry->ha_addr));

	list_init_node(&entry->hashnode);
	list_init_node(&entry->timenode);

	if (hashtable_add(table->hashtable, binding_hash,
			  &entry->mn_addr, &entry->hashnode) == FALSE) {
		DEBUG(DEBUG_FLAG,
			"binding_add: unable to add entry to hashtable\n");
		return FALSE;
	}
	idx = table->currentindex;
	ASSERT(idx >= 0);
	ASSERT(idx < table->shorttimelistsize);
	maxuseshortlist = table->firstindex + (table->shorttimelistsize - 1) -
			  table->currentindex;
	if (maxuseshortlist >= table->shorttimelistsize) {
		maxuseshortlist -= table->shorttimelistsize;
	}
	DEBUG(DEBUG_FLAG,
	      "binding_add: shorttimelistsize = %d, maxuseshortlist = %d\n",
	      table->shorttimelistsize, maxuseshortlist);
	ASSERT(maxuseshortlist >= 0);
	ASSERT(maxuseshortlist < table->shorttimelistsize);
	if (entry->timeout >= INFINITE_TIMEOUT)
		addlist = &table->noexptimelist;
	else
		addlist = &table->longtimelist;
	if (entry->timeout >= table->shorttimelistsize) {
		DEBUG(DEBUG_FLAG,
			"binding_add: timeout %d longer than "
			"shorttimelistsize %d, long list used\n",
			entry->timeout, table->shorttimelistsize);
	} else if (entry->timeout > maxuseshortlist) {
		DEBUG(DEBUG_FLAG,
			"binding_add: timeout %d longer than "
			"maxuseshortlist %d, long list used\n"
			"binding_add: firstindex %d, currentindex %d\n",
			entry->timeout, maxuseshortlist,
			table->firstindex, table->currentindex);
	} else {
		ASSERT(entry->timeout < INFINITE_TIMEOUT);
		idx = idx + entry->timeout;
		if (idx >= table->shorttimelistsize) {
			idx -= table->shorttimelistsize;
		}
		ASSERT(idx >= 0);
		ASSERT(idx < table->shorttimelistsize);
		addlist = &table->shorttimelist[idx];
	}
	list_add_tail(addlist, &entry->timenode);
	return TRUE;
}

/* Fetch binding
 *
 * INPUT VALUES:
 *
 * I16) Bindingentry is not found
 * I17) Bindingentry is found
 *
 */

/**
 * binding_fetch:
 * @table:
 * @key:
 *
 * Fetch binding.
 * 
 * Returns: a bindingentry structur if any binding for the requested
 * mobile node is found.  
 */
struct bindingentry *
binding_fetch(struct bindingtable *table, struct bindingkey *key)
{
	struct bindingentry *entry;
	struct node *node;

	DEBUG(DEBUG_FLAG, "binding_fetch: key: (MN=%s,HA=",
	      inet_ntoa(key->mn_addr));
	DEBUG(DEBUG_FLAG, "%s,privHA=%i)\n", inet_ntoa(key->ha_addr),
	      key->priv_ha);
	node = hashtable_fetch(table->hashtable, binding_hash, key,
			       binding_compare);
	if (node == NULL) {
		DEBUG(DEBUG_FLAG, "binding_fetch: entry %08x,%08x not found in"
		      " the hashtable\n", key->mn_addr.s_addr,
		      key->ha_addr.s_addr);
		return NULL;
	}
	entry = (struct bindingentry *)
		(((char *) node) - offsetof(struct bindingentry, hashnode));
	return entry;
}


static struct bindingentry *found_binding;

static int fetch_iter2(struct node *node, void *data)
{
	struct bindingentry *entry = (struct bindingentry *) node;
	struct in_addr *addr = (struct in_addr *) data;

	if (entry->mn_addr.s_addr == addr->s_addr) {
		found_binding = entry;
		return 0;
	}
	return 1;
}

/**
 * binding_fetch2:
 * @table:
 * @mn_addr:
 * 
 * This function is like binding_fetch(), but it does not use the full
 * binding key (only @mn_addr). It is a temporary fix due to the binding key
 * change. It should also be noted, that this function has to go through all
 * the binding entries as it cannot use hashtable without proper key.
 *
 * Returns: a bindingentry structure
 * if any binding for the requested mobile node is found.
 */
struct bindingentry *
binding_fetch2(struct bindingtable *table, struct in_addr *mn_addr)
{
	found_binding = NULL;
	hashtable_iterator(table->hashtable, fetch_iter2, mn_addr);
	if (found_binding == NULL) {
		DEBUG(DEBUG_FLAG, "binding_fetch2: entry %08x not found in "
		      "hashtable\n", mn_addr->s_addr);
		return NULL;
	}
	return found_binding;
}


static int fetch_iter_func(struct node *node, void *data)
{
	struct bindingentry *entry = (struct bindingentry *) node;
	int (*func)(struct bindingentry *) = data;

	if (func(entry)) {
		found_binding = entry;
		return 0;
	}
	return 1;
}


/**
 * binding_fetch_func:
 * @table: pointer to the binding table
 * @func: function to be used to select the binding
 * 
 * This function is like binding_fetch(), but it goes through all the binding
 * entries until a correct one is found. The given @func is used to decide
 * which binding entry is selected.
 *
 * Returns: a bindingentry structure for the selected binding or NULL if no
 * binding is selected.
 */
struct bindingentry *
binding_fetch_func(struct bindingtable *table,
		   int (*func)(struct bindingentry *binding))
{
	found_binding = NULL;
	hashtable_iterator(table->hashtable, fetch_iter_func, func);
	if (found_binding == NULL) {
		DEBUG(DEBUG_FLAG, "binding_fetch_func: entry not found in "
		      "hashtable\n");
		return NULL;
	}
	return found_binding;
}


/* Remove binding
 *
 * INPUT VALUES:
 *
 * I18) Bindingentry is valid
 *    ) Bindingentry is NULL