binding.c

mobile ip 在linux下的一种实现

 *    ) Bindingentry is invalid (cannot be checked)
 *
 */

/**
 * binding_remove:
 * @entry:
 *
 * Removes the bindingentry from the bindingtable.
 */
void
binding_remove(struct bindingentry *entry)
{
	ASSERT(entry != NULL);
	if (entry->hashnode.succ == NULL)
		return; /* already removed */
	list_remove(&entry->hashnode);
	list_remove(&entry->timenode);
}

/* Get the amount of units (for example seconds) until the next binding
 * is going to be expired
 * 0 = expired
 * -1 = no bindings
 *
 * INPUT VALUES:
 *
 * I19) No bindings in the table
 * I20) Expired binding with timeout of 0 (firstindex == currentindex)
 * I21) Earlier expired binding (firstindex != currentindex)
 * I22) Next binding to be expired is in shorttimelist
 * I23) Next binding to be expired is the first in longtimelist
 * I24) Next binding to be expired is not the first but in longtimelist
 *    ) Table is NULL
 *
 */

/**
 * binding_nextexpiretime:
 * @table:
 *
 * Get the amount of units (for example seconds) until the next binding
 * is going to be expired
 *
 * Returns: the amount of time units until the
 * next entry expires. 0 = expired, -1 = no bindings
 */

int
binding_nextexpiretime(struct bindingtable *table)
{
	int idx, time;
	struct bindingentry *entry;
	struct node *timenode;

	ASSERT(table != NULL);
	idx = table->firstindex;
	for (;;) {
		ASSERT(idx >= 0);
		ASSERT(idx < table->shorttimelistsize);
		if (list_is_empty(&table->shorttimelist[idx]) == FALSE) {
			return 0;
		}
		if (idx == table->currentindex) break;
		idx++;
		if (idx >= table->shorttimelistsize) {
			idx -= table->shorttimelistsize;
		}
		table->firstindex = idx;
	}
	ASSERT(table->firstindex == table->currentindex);
	idx = table->currentindex;
	for (time = 1; time < table->shorttimelistsize - 1; time++) {
		idx++;
		if (idx >= table->shorttimelistsize) {
			idx -= table->shorttimelistsize;
		}
		if (list_is_empty(&table->shorttimelist[idx]) == FALSE) {
			return time;
		}
	}
	if (list_is_empty(&table->longtimelist) == TRUE) {
		return -1;
	}
	DEBUG(DEBUG_FLAG,
		"binding_nextexpiretime: shorttimelist empty, using "
		"longtimelist (slower)\n");
	timenode = list_get_first(&table->longtimelist);
	if (timenode == NULL) {
		return -1;
	}
	time = (((unsigned int) (-1)) >> 1); /* large one :) */
	while (timenode != NULL) {
		entry = (struct bindingentry *)
			(((char *) timenode) - offsetof(struct bindingentry,
							timenode));
		ASSERT(entry->timeout >= 0);
		if (entry->timeout < time) {
			time = entry->timeout;
		}
		timenode = list_get_next(&entry->timenode);
	}
	if (time == (((unsigned int) (-1)) >> 1)) {
		return -1;
	}
	return time;
}

/* Advance time and check if there are expired bindings
 *
 * INPUT VALUES:
 *
 * I25) Time to advance is less than zero
 * I26) Time to advance is zero
 * I27) Time to advance is greater than zero
 * I28) Advancetime is longer than allowed (expired bindings)
 * I29) No bindings in the table
 * I30) No expired bindings
 * I31) Expired bindings in shorttimelist
 * I32) Expired bindings in longtimelist
 *    ) Table is NULL
 *
 */

/**
 * binding_getexpired:
 * @table:
 * @advance:
 * 
 * Advance the time by specified amount of units and
 * returns a bindingentry if there is at least one that is expired.
 * If there are no expired entries, %NULL is returned.
 *
 * Usually this function is first called once to advance the timer to current
 * time. If there are expired bindings, the function is repeated with advance
 * value of zero until there are no longer expired bindings.
 */
struct bindingentry *
binding_getexpired(struct bindingtable *table, int advance)
{
	int idx, checklongtimelist, listempty, left;
	struct node *timenode;
	struct bindingentry *entry;

	DEBUG(DEBUG_FLAG,
	      "binding_getexpired: firstindex = %d, currentindex = %d, "
	      "advance = %d\n",
	      table->firstindex, table->currentindex, advance);
	if (advance < 0) {
		DEBUG(DEBUG_FLAG,
			"binding_getexpired: time to advance is %d that is "
			"less than zero, set to zero\n", advance);
		advance = 0;
	}
	idx = table->firstindex;
	checklongtimelist = FALSE;
	listempty = TRUE;
	idx = binding_getexpired_alreadyexpired(table, idx,
						&checklongtimelist,
						&listempty);
	ASSERT(idx == table->firstindex);
	left = advance;
	if (listempty == TRUE) {
		left = binding_getexpired_advance(table, left, idx,
						  &checklongtimelist);
		idx = table->firstindex;
	}
	left = binding_getexpired_checkmaxadvancetime(table, left, &advance);
	ASSERT(idx == table->firstindex);
	ASSERT(idx >= 0);
	ASSERT(idx < table->shorttimelistsize);
	table->currentindex = table->firstindex + left;
	if (table->currentindex >= table->shorttimelistsize) {
		table->currentindex -= table->shorttimelistsize;
	}
	ASSERT(table->currentindex >= 0);
	ASSERT(table->currentindex < table->shorttimelistsize);
	if (checklongtimelist == TRUE) {
		DEBUG(DEBUG_FLAG,
		      "binding_getexpired: binding_check_longtimelist()\n");
		binding_check_longtimelist(table, advance);
	}
	if (listempty == FALSE) {
		ASSERT(list_is_empty(&table->shorttimelist[idx]) == FALSE);
	}
	DEBUG(DEBUG_FLAG, "firstindex = %d, currentindex = %d, left = %d\n",
	      table->firstindex, table->currentindex, left);
	ASSERT(left >= 0);
	if (left == 0 && listempty == TRUE) {
		ASSERT(table->firstindex == table->currentindex);
		ASSERT(idx == table->firstindex);
	}
	timenode = list_get_first(&table->shorttimelist[idx]);
	if (timenode == NULL) {
		return NULL;
	}
	entry = (struct bindingentry *)
		(((char *) timenode) - offsetof(struct bindingentry,
						timenode));
	binding_remove(entry);
	return entry;
}

/**
 * binding_iterator:
 * @table: pointer to the binding table
 * @iterfunc: iterator function to be called for each binding entry
 * @data: argument for @iterfunc
 *
 * Iterate through each binding entry and call @iterfunc for each with @data
 * as the second argument.
 *
 * Returns: TRUE if the iteration was not stopped by iterator function
 * and FALSE if it was stopped.
 */
int
binding_iterator(struct bindingtable *table,
		 int (*iterfunc)(struct node *node, void *data),
		 void *data)
{
	if (table == NULL || table->hashtable == NULL)
		return 0;

	return hashtable_iterator(table->hashtable, iterfunc, data);
}


/**
 * binding_update:
 * @table: binding table
 * @entry: entry to be updated
 *
 * Updates the bindingentry timeout in the bindingtable. This needs to be
 * called when the lifetime of the binding has changed.
 *
 * Returns TRUE on success, FALSE on failure
 */
int
binding_update(struct bindingtable *table, struct bindingentry *entry)
{
	binding_remove(entry);
	return binding_add(table, entry);
}


/* Check for already expired bindings and update firstindex
 *
 * Sets listempty to FALSE if there are expired bindings
 * Sets checklongtimelist to TRUE if the longtimelist should be checked
 * (i.e. if the time is advanced)
 * Updates firstindex of the table
 * Returns the new index
 */

static int
binding_getexpired_alreadyexpired(struct bindingtable *table, int idx,
				  int *checklongtimelist, int *listempty)
{
	for (;;) {
		ASSERT(idx >= 0);
		ASSERT(idx < table->shorttimelistsize);
		if (list_is_empty(&table->shorttimelist[idx]) == FALSE) {
			*listempty = FALSE;
			break;
		}
		if (idx == table->currentindex) break;
		idx++;
		if (idx >= table->shorttimelistsize) {
			idx -= table->shorttimelistsize;
		}
		table->firstindex = idx;
		*checklongtimelist = TRUE;
	}
	ASSERT(idx == table->firstindex);
	return idx;
}

/* Advances the time to find the next expired binding
 *
 * Sets checklongtimelist to TRUE if the longtimelist should be checked
 * (i.e. if the time is advanced)
 * Updates firstindex and currentindex of the table
 * Returns the amount of time units left after advance
 */

static int
binding_getexpired_advance(struct bindingtable *table, int advance, int idx,
			   int *checklongtimelist)
{
	int i, left;

	left = advance;
	for (i = 0; i < advance; i++) {
		idx++;
		left--;
		if (idx >= table->shorttimelistsize) {
			idx -= table->shorttimelistsize;
		}
		if (idx == table->firstindex) {
			ASSERT(idx == table->currentindex);
			left = 0;
			idx = 0;
			table->currentindex = idx;
			break;
		}
		if (list_is_empty(&table->shorttimelist[idx]) == FALSE) {
			break;
		}
	}
	if (i > 0) {
		*checklongtimelist = TRUE;
	}
	table->firstindex = idx;
	table->currentindex = idx;
	return left;
}

/* Check the maximum time able to advance
 *
 * Makes advance smaller if too high
 * Returns the time left to advance
 */

static int
binding_getexpired_checkmaxadvancetime(struct bindingtable *table, int left,
				       int *advance)
{
	int maxadvancetime;

	maxadvancetime = table->firstindex - table->currentindex;
	if (maxadvancetime <= 0) {
		maxadvancetime += table->shorttimelistsize - 1;
	}
	DEBUG(DEBUG_FLAG,
	      "maxadvancetime = %d, firstindex = %d, currentindex = %d\n",
	      maxadvancetime, table->firstindex, table->currentindex);
	ASSERT(maxadvancetime < table->shorttimelistsize);
	if (left > maxadvancetime) {
		DEBUG(DEBUG_FLAG,
			"binding_getexpired_checkmaxadvancetime: time to "
			"advance is %d\n"
			"that is more than allowed because of expired "
			"bindings\n",
			*advance);
		left = maxadvancetime + left - *advance;
		*advance = maxadvancetime;
	}
	return left;
}

/* Check longtimelist */

/* NOTE:
 * To reduce debug-message flood: do _not_ use DEBUG_FLAG 'B'
 * when running the system as this function might be called quite frequently.
 * The printings are mainly to notify the administrator that
 * the system is using a slower method (longtimelist) and the
 * efficiency could be improved.
 */

static void
binding_check_longtimelist(struct bindingtable *table, const int advance)
{
	int maxuseshortlist;
	struct node *timenode;
	struct bindingentry *entry;

	if (advance < 0) {
		DEBUG(DEBUG_FLAG,
			"binding_check_longtimelist: time to advance is %d "
			"that is less than zero\n", advance);
		return;
	}
	timenode = list_get_first(&table->longtimelist);
	if (timenode == NULL) return;
	DEBUG(DEBUG_FLAG,
	      "binding_check_longtimelist: list is not empty!\n");
	maxuseshortlist = table->firstindex +
		(table->shorttimelistsize - 1) - table->currentindex;
	if (maxuseshortlist >= table->shorttimelistsize) {
		maxuseshortlist -= table->shorttimelistsize;
	}
	DEBUG(DEBUG_FLAG, "maxuseshortlist = %d\n", maxuseshortlist);
	ASSERT(maxuseshortlist >= 0);
	ASSERT(maxuseshortlist <= table->shorttimelistsize - 1);
	do {
		entry = (struct bindingentry *)
			(((char *) timenode) - offsetof(struct bindingentry,
							timenode));
		timenode = list_get_next(&entry->timenode);
		ASSERT(entry->timeout >= 0);
		if (entry->timeout >= INFINITE_TIMEOUT)
			continue; /* this entry will not expire */
		if (entry->timeout < advance) {
			DEBUG(DEBUG_FLAG,
				"binding_check_longtimelist: timeout %d lower "
				"than advance %d, set to zero\n",
				entry->timeout, advance);
			entry->timeout = 0;
		} else {
			DEBUG(DEBUG_FLAG,
				"binding_check_longtimelist: updating timeout "
				"%d to %d\n",
				entry->timeout, entry->timeout - advance);
			entry->timeout -= advance;
		}
		if (entry->timeout < maxuseshortlist) {
			binding_remove(entry);
			binding_add(table, entry);
		}
	} while (timenode != NULL);
}

/* Hash Function used in bindings */

static int
binding_hash(void *key, const int tablesize)
{
	struct bindingkey *bkey;

	bkey = (struct bindingkey *) key;
	/* The key is a bindingentry structure */
	return (int) (((__u32)bkey->mn_addr.s_addr +
		       (__u32)bkey->ha_addr.s_addr) % tablesize);
}

/* compare function used in bindings */

static int
binding_compare(void *key, struct node *cmprd)
{
	struct bindingkey *bkey;
	struct bindingentry *entry;

	bkey = (struct bindingkey *) key;
	entry = (struct bindingentry *)
		(((char *) cmprd) - offsetof(struct bindingentry, hashnode));
	if (entry->mn_addr.s_addr == bkey->mn_addr.s_addr &&
	    entry->ha_addr.s_addr == bkey->ha_addr.s_addr &&
	    entry->priv_ha == bkey->priv_ha)
		return TRUE;
	return FALSE;
}