rp.c

/*
 * Copyright (c) 1998-2001
 * University of Southern California/Information Sciences Institute.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the project nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "defs.h"


/*
 * The hash function. Stollen from Eddy's (eddy@isi.edu)
 * implementation (for compatibility ;)
 */
#define SEED1   1103515245
#define SEED2   12345
#define RP_HASH_VALUE(G, M, C) (((SEED1) * (((SEED1) * ((G) & (M)) + (SEED2)) ^ (C)) + (SEED2)) % 0x80000000)

cand_rp_t               *cand_rp_list;
grp_mask_t              *grp_mask_list;
cand_rp_t               *segmented_cand_rp_list;
grp_mask_t              *segmented_grp_mask_list;
uint16_t                 curr_bsr_fragment_tag;
uint8_t                  curr_bsr_priority;
uint32_t                 curr_bsr_address;
uint32_t                 curr_bsr_hash_mask;
uint16_t                 pim_bootstrap_timer;   /* For electing the BSR and
						 * sending Cand-RP-set msgs */
uint8_t                  my_bsr_priority;
uint32_t                 my_bsr_address;
uint32_t                 my_bsr_hash_mask;
uint8_t                  cand_bsr_flag = FALSE; /* Set to TRUE if I am
						 * a candidate BSR */
uint32_t                 my_cand_rp_address;
uint8_t                  my_cand_rp_priority;
uint16_t                 my_cand_rp_holdtime;
uint16_t                 my_cand_rp_adv_period; /* The locally configured
						 * Cand-RP adv. period. */
uint16_t                 pim_cand_rp_adv_timer;
uint8_t                  cand_rp_flag  = FALSE;  /* Candidate RP flag */
struct cand_rp_adv_message_ cand_rp_adv_message;
uint32_t                 rp_my_ipv4_hashmask;


/*
 * Local functions definition.
 */
static cand_rp_t  *add_cand_rp          (cand_rp_t **used_cand_rp_list, uint32_t address);
static grp_mask_t *add_grp_mask         (grp_mask_t **used_grp_mask_list,
					 uint32_t group_addr,
					 uint32_t group_mask,
					 uint32_t hash_mask);
static void       delete_grp_mask_entry (cand_rp_t **used_cand_rp_list,
					 grp_mask_t **used_grp_mask_list,
					 grp_mask_t *grp_mask_delete);
static void       delete_rp_entry       (cand_rp_t **used_cand_rp_list,
					 grp_mask_t **used_grp_mask_list,
					 cand_rp_t *cand_rp_ptr);


void init_rp_and_bsr(void)
{
    /* TODO: if the grplist is not NULL, remap all groups ASAP! */
    delete_rp_list(&cand_rp_list, &grp_mask_list);
    delete_rp_list(&segmented_cand_rp_list, &segmented_grp_mask_list);

    if (cand_bsr_flag == FALSE) {
	/*
	 * If I am not candidat BSR, initialize the "current BSR"
	 * as having the lowest priority.
	 */
	curr_bsr_fragment_tag = 0;
	curr_bsr_priority = 0;             /* Lowest priority */
	curr_bsr_address  = INADDR_ANY_N;  /* Lowest priority */
	MASKLEN_TO_MASK(RP_DEFAULT_IPV4_HASHMASKLEN, curr_bsr_hash_mask);
	SET_TIMER(pim_bootstrap_timer, PIM_BOOTSTRAP_TIMEOUT);
    } else {
	curr_bsr_fragment_tag = RANDOM();
	curr_bsr_priority = my_bsr_priority;
	curr_bsr_address = my_bsr_address;
	curr_bsr_hash_mask = my_bsr_hash_mask;
	SET_TIMER(pim_bootstrap_timer, bootstrap_initial_delay());
    }

    if (cand_rp_flag != FALSE) {
	MASKLEN_TO_MASK(RP_DEFAULT_IPV4_HASHMASKLEN, rp_my_ipv4_hashmask);
	/* Setup the Cand-RP-Adv-Timer */
	SET_TIMER(pim_cand_rp_adv_timer, RANDOM() % my_cand_rp_adv_period);
    }
}


uint16_t bootstrap_initial_delay(void)
{
    uint32_t addr_delay;
    uint32_t delay;
    uint32_t log_mask;
    int32_t  log_of_2;
    uint8_t  best_priority;

    /*
     * The bootstrap timer initial value (if Cand-BSR).
     * It depends of the bootstrap router priority:
     * higher priority has shorter value:
     *
     * delay = 5 + 2 * log_2(1 + best_priority - myPriority) + addr_delay;
     *
     *    best_priority = Max(storedPriority, myPriority);
     *    if (best_priority == myPriority)
     *        addr_delay = log_2(bestAddr - myAddr)/16;
     *    else
     *        addr_delay = 2 - (myAddr/2^31);
     */

    best_priority = max(curr_bsr_priority, my_bsr_priority);
    if (best_priority == my_bsr_priority) {
	addr_delay = ntohl(curr_bsr_address) - ntohl(my_bsr_address);
	/* Calculate the integer part of log_2 of (bestAddr - myAddr) */
	/* To do so, have to find the position number of the first bit
	 * from left which is `1`
	 */
	log_mask = sizeof(addr_delay) << 3;
	log_mask = (1 << (log_mask - 1));  /* Set the leftmost bit to `1` */
	for (log_of_2 = (sizeof(addr_delay) << 3) - 1 ; log_of_2; log_of_2--) {
	    if (addr_delay & log_mask)
		break;

	    log_mask >>= 1;  /* Start shifting `1` on right */
	}
	addr_delay = log_of_2 / 16;
    } else {
	addr_delay = 2 - (ntohl(my_bsr_address) / ( 1 << 31));
    }

    delay = 1 + best_priority - my_bsr_priority;
    /* Calculate log_2(delay) */
    log_mask = sizeof(delay) << 3;
    log_mask = (1 << (log_mask - 1));  /* Set the leftmost bit to `1` */
    for (log_of_2 = (sizeof(delay) << 3) - 1 ; log_of_2; log_of_2--) {
	if (delay & log_mask)
	    break;

	log_mask >>= 1;  /* Start shifting `1` on right */
    }

    delay = 5 + 2 * log_of_2 + addr_delay;

    return (uint16_t)delay;
}


static cand_rp_t *add_cand_rp(cand_rp_t **used_cand_rp_list, uint32_t address)
{
    cand_rp_t *prev = NULL;
    cand_rp_t *next;
    cand_rp_t *ptr;
    rpentry_t *entry;
    uint32_t addr_h = ntohl(address);

    /* The ordering is the bigger first */
    for (next = *used_cand_rp_list; next; prev = next, next = next->next) {
	if (ntohl(next->rpentry->address) > addr_h)
	    continue;

	if (next->rpentry->address == address)
	    return next;
	else
	    break;
    }

    /* Create and insert the new entry between prev and next */
    ptr = (cand_rp_t *)calloc(1, sizeof(cand_rp_t));
    if (!ptr)
	logit(LOG_ERR, 0, "Ran out of memory in add_cand_rp()");
    ptr->rp_grp_next = NULL;
    ptr->next = next;
    ptr->prev = prev;
    if (next)
	next->prev = ptr;
    if (prev == NULL)
	*used_cand_rp_list = ptr;
    else
	prev->next = ptr;

    entry = (rpentry_t *)calloc(1, sizeof(rpentry_t));
    if (!entry)
	logit(LOG_ERR, 0, "Ran out of memory in add_cand_rp()");
    ptr->rpentry = entry;
    entry->next = NULL;
    entry->prev  = NULL;
    entry->address = address;
    entry->mrtlink = NULL;
    entry->incoming = NO_VIF;
    entry->upstream = NULL;
    /* TODO: setup the metric and the preference as ~0 (the lowest)? */
    entry->metric = ~0;
    entry->preference = ~0;
    RESET_TIMER(entry->timer);
    entry->cand_rp = ptr;

    /* TODO: XXX: check whether there is a route to that RP: if return value
     * is FALSE, then no route.
     */
    if (local_address(entry->address) == NO_VIF)
	/* TODO: check for error and delete */
	set_incoming(entry, PIM_IIF_RP);
    else
	/* TODO: XXX: CHECK!!! */
	entry->incoming = reg_vif_num;

    return ptr;
}


static grp_mask_t *add_grp_mask(grp_mask_t **used_grp_mask_list, uint32_t group_addr, uint32_t group_mask, uint32_t hash_mask)
{
    grp_mask_t *prev = NULL;
    grp_mask_t *next;
    grp_mask_t *ptr;
    uint32_t prefix_h = ntohl(group_addr & group_mask);

    /* The ordering of group_addr is: bigger first */
    for (next = *used_grp_mask_list; next; prev = next, next = next->next) {
	if (ntohl(next->group_addr & next->group_mask) > prefix_h)
	    continue;

	/* The ordering of group_mask is: bigger (longer) first */
	if ((next->group_addr & next->group_mask) == (group_addr & group_mask)) {
	    if (ntohl(next->group_mask) > ntohl(group_mask))
		continue;
	    else if (next->group_mask == group_mask)
		return next;
	    else
		break;
	}
    }

    ptr = (grp_mask_t *)calloc(1, sizeof(grp_mask_t));
    if (!ptr)
	logit(LOG_ERR, 0, "Ran out of memory in add_grp_mask()");

    ptr->grp_rp_next = (rp_grp_entry_t *)NULL;
    ptr->next = next;
    ptr->prev = prev;
    if (next)
	next->prev = ptr;
    if (prev == NULL)
	*used_grp_mask_list = ptr;
    else
	prev->next = ptr;

    ptr->group_addr = group_addr;
    ptr->group_mask = group_mask;
    ptr->hash_mask  = hash_mask;
    ptr->group_rp_number = 0;
    ptr->fragment_tag = 0;

    return ptr;
}


/* TODO: XXX: BUG: a remapping for some groups currently using some other
 * grp_mask may be required by the addition of the new entry!!!
 * Remapping all groups might be a costly process...
 */
rp_grp_entry_t *add_rp_grp_entry(cand_rp_t  **used_cand_rp_list,
				 grp_mask_t **used_grp_mask_list,
				 uint32_t rp_addr,
				 uint8_t  rp_priority,
				 uint16_t rp_holdtime,
				 uint32_t group_addr,
				 uint32_t group_mask,
				 uint32_t bsr_hash_mask,
				 uint16_t fragment_tag)
{
    cand_rp_t *cand_rp_ptr;
    grp_mask_t *mask_ptr;
    rpentry_t *rpentry_ptr;
    rp_grp_entry_t *entry_next;
    rp_grp_entry_t *entry_new;
    rp_grp_entry_t *entry_prev = NULL;
    grpentry_t *grpentry_ptr_prev;
    grpentry_t *grpentry_ptr_next;
    uint32_t rp_addr_h;
    uint8_t old_highest_priority = ~0;  /* Smaller value means "higher" */

    /* Input data verification */
    if (!inet_valid_host(rp_addr))
	return NULL;
    if (!IN_CLASSD(ntohl(group_addr)))
	return NULL;

    mask_ptr = add_grp_mask(used_grp_mask_list, group_addr, group_mask, bsr_hash_mask);
    if (mask_ptr == NULL)
	return NULL;

/* TODO: delete */
#if 0
    if (mask_ptr->grp_rp_next) {
	/* Check for obsolete grp_rp chain */
	if ((my_bsr_address != curr_bsr_address) && (mask_ptr->grp_rp_next->fragment_tag != fragment_tag)) {
	    /* This grp_rp chain is obsolete. Delete it. */
	    delete_grp_mask(used_cand_rp_list, used_grp_mask_list, group_addr, group_mask);
	    mask_ptr = add_grp_mask(used_grp_mask_list, group_addr, group_mask, bsr_hash_mask);

	    if (mask_ptr == NULL)
		return NULL;
	}
    }
#endif /* 0 */

    cand_rp_ptr = add_cand_rp(used_cand_rp_list, rp_addr);
    if (cand_rp_ptr == NULL) {
	if (mask_ptr->grp_rp_next == NULL)
	    delete_grp_mask(used_cand_rp_list, used_grp_mask_list,
			    group_addr, group_mask);
	return NULL;
    }

    rpentry_ptr = cand_rp_ptr->rpentry;
    SET_TIMER(rpentry_ptr->timer, rp_holdtime);
    rp_addr_h = ntohl(rp_addr);
    mask_ptr->fragment_tag = fragment_tag;   /* For garbage collection */

    entry_prev = NULL;
    entry_next = mask_ptr->grp_rp_next;
    /* TODO: improve it */
    if (entry_next != NULL)
	old_highest_priority = entry_next->priority;
    for ( ; entry_next; entry_prev = entry_next,
	      entry_next = entry_next->grp_rp_next) {
	/* Smaller value means higher priority. The entries are
	 * sorted with the highest priority first.
	 */
	if (entry_next->priority < rp_priority)
	    continue;
	if (entry_next->priority > rp_priority)
	    break;

	/*
	 * Here we don't care about higher/lower addresses, because
	 * higher address does not guarantee higher hash_value,
	 * but anyway we do order with the higher address first,
	 * so it will be easier to find an existing entry and update the
	 * holdtime.
	 */
	if (ntohl(entry_next->rp->rpentry->address) > rp_addr_h)
	    continue;
	if (ntohl(entry_next->rp->rpentry->address) < rp_addr_h)
	    break;
	/* We already have this entry. Update the holdtime */
	/* TODO: We shoudn't have old existing entry, because with the
	 * current implementation all of them will be deleted
	 * (different fragment_tag). Debug and check and eventually
	 * delete.
	 */
	entry_next->holdtime = rp_holdtime;
	entry_next->fragment_tag = fragment_tag;

	return entry_next;
    }

    /* Create and link the new entry */
    entry_new = (rp_grp_entry_t *)calloc(1, sizeof(rp_grp_entry_t));
    if (!entry_new)
	logit(LOG_ERR, 0, "Ran out of memory in add_rp_grp_entry()");
    entry_new->grp_rp_next = entry_next;
    entry_new->grp_rp_prev = entry_prev;
    if (entry_next)
	entry_next->grp_rp_prev = entry_new;
    if (entry_prev == NULL)
	mask_ptr->grp_rp_next = entry_new;
    else
	entry_prev->grp_rp_next = entry_new;

    /*
     * The rp_grp_entry chain is not ordered, so just plug
     * the new entry at the head.
     */
    entry_new->rp_grp_next = cand_rp_ptr->rp_grp_next;
    if (cand_rp_ptr->rp_grp_next)
	cand_rp_ptr->rp_grp_next->rp_grp_prev = entry_new;
    entry_new->rp_grp_prev = NULL;
    cand_rp_ptr->rp_grp_next = entry_new;

    entry_new->holdtime = rp_holdtime;
    entry_new->fragment_tag = fragment_tag;
    entry_new->priority = rp_priority;
    entry_new->group = mask_ptr;
    entry_new->rp = cand_rp_ptr;
    entry_new->grplink = NULL;

    /* If I am BSR candidate and rp_addr is NOT hacked SSM address, then log it */
    if( cand_bsr_flag && rp_addr != 0x0100fea9 ) {
	uint32_t mask;
	MASK_TO_MASKLEN(group_mask, mask);
	logit(LOG_INFO, 0, "New RP candidate %s for group %s/%d, priority %d",
	      inet_fmt(rp_addr, s1, sizeof(s1)), inet_fmt(group_addr, s2, sizeof(s2)), mask, rp_priority);
    }

    mask_ptr->group_rp_number++;

    if (mask_ptr->grp_rp_next->priority == rp_priority) {
	/* The first entries are with the best priority. */
	/* Adding this rp_grp_entry may result in group_to_rp remapping */
	for (entry_next = mask_ptr->grp_rp_next; entry_next; entry_next = entry_next->grp_rp_next) {
	    if (entry_next->priority > old_highest_priority)
		break;

	    for (grpentry_ptr_prev = entry_next->grplink; grpentry_ptr_prev; ) {
		grpentry_ptr_next = grpentry_ptr_prev->rpnext;
		remap_grpentry(grpentry_ptr_prev);
		grpentry_ptr_prev = grpentry_ptr_next;
	    }
	}
    }

    return entry_new;
}


void delete_rp_grp_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, rp_grp_entry_t *entry)
{
    grpentry_t *ptr;
    grpentry_t *ptr_next;

    if (entry == NULL)
	return;
    entry->group->group_rp_number--;

    /* Free the rp_grp* and grp_rp* links */
    if (entry->rp_grp_prev)
	entry->rp_grp_prev->rp_grp_next = entry->rp_grp_next;
    else
	entry->rp->rp_grp_next = entry->rp_grp_next;
    if (entry->rp_grp_next)
	entry->rp_grp_next->rp_grp_prev = entry->rp_grp_prev;

    if (entry->grp_rp_prev)
	entry->grp_rp_prev->grp_rp_next = entry->grp_rp_next;
    else
	entry->group->grp_rp_next = entry->grp_rp_next;

    if (entry->grp_rp_next)
	entry->grp_rp_next->grp_rp_prev = entry->grp_rp_prev;

    /* Delete Cand-RP or Group-prefix if useless */
    if (entry->group->grp_rp_next == NULL)
	delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, entry->group);

    if (entry->rp->rp_grp_next == NULL)
	delete_rp_entry(used_cand_rp_list, used_grp_mask_list, entry->rp);

    /* Remap all affected groups */
    for (ptr = entry->grplink; ptr; ptr = ptr_next) {
	ptr_next = ptr->rpnext;
	remap_grpentry(ptr);
    }

    free((char *)entry);
}

/* TODO: XXX: the affected group entries will be partially
 * setup, because may have group routing entry, but NULL pointers to RP.
 * After the call to this function, must remap all group entries ASAP.
 */
void delete_rp_list(cand_rp_t  **used_cand_rp_list, grp_mask_t **used_grp_mask_list)
{
    cand_rp_t      *cand_ptr,  *cand_next;
    rp_grp_entry_t *entry_ptr, *entry_next;
    grp_mask_t     *mask_ptr, *mask_next;
    grpentry_t     *gentry_ptr, *gentry_ptr_next;

    for (cand_ptr = *used_cand_rp_list; cand_ptr; ) {
	cand_next = cand_ptr->next;

	/* Free the mrtentry (if any) for this RP */
	if (cand_ptr->rpentry->mrtlink) {
	    if (cand_ptr->rpentry->mrtlink->flags & MRTF_KERNEL_CACHE)
		delete_mrtentry_all_kernel_cache(cand_ptr->rpentry->mrtlink);
	    FREE_MRTENTRY(cand_ptr->rpentry->mrtlink);
	}
	free(cand_ptr->rpentry);

	/* Free the whole chain of entry for this RP */
	for (entry_ptr = cand_ptr->rp_grp_next; entry_ptr; entry_ptr = entry_next) {
	    entry_next = entry_ptr->rp_grp_next;

	    /* Clear the RP related invalid pointers for all group entries */
	    for (gentry_ptr = entry_ptr->grplink; gentry_ptr; gentry_ptr = gentry_ptr_next) {
		gentry_ptr_next = gentry_ptr->rpnext;
		gentry_ptr->rpnext = NULL;
		gentry_ptr->rpprev = NULL;
		gentry_ptr->active_rp_grp = NULL;
		gentry_ptr->rpaddr = INADDR_ANY_N;
	    }

	    free(entry_ptr);
	}

	free(cand_ptr);
	cand_ptr = cand_next;
    }
    *used_cand_rp_list = NULL;

    for (mask_ptr = *used_grp_mask_list; mask_ptr; mask_ptr = mask_next) {
	mask_next = mask_ptr->next;
	free(mask_ptr);
    }
    *used_grp_mask_list = NULL;
}


void delete_grp_mask(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, uint32_t group_addr, uint32_t group_mask)
{
    grp_mask_t *ptr;
    uint32_t prefix_h = ntohl(group_addr & group_mask);

    for (ptr = *used_grp_mask_list; ptr; ptr = ptr->next) {
	if (ntohl(ptr->group_addr & ptr->group_mask) > prefix_h)
	    continue;

	if (ptr->group_addr == group_addr) {
	    if (ntohl(ptr->group_mask) > ntohl(group_mask))
		continue;
	    else if (ptr->group_mask == group_mask)
		break;
	    else
		return;   /* Not found */
	}
    }

    if (ptr == (grp_mask_t *)NULL)
	return;       /* Not found */

    delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, ptr);
}

static void delete_grp_mask_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, grp_mask_t *grp_mask_delete)
{
    grpentry_t *grp_ptr, *grp_ptr_next;
    rp_grp_entry_t *entry_ptr;
    rp_grp_entry_t *entry_next;

    if (grp_mask_delete == NULL)
	return;

    /* Remove from the grp_mask_list first */
    if (grp_mask_delete->prev)
	grp_mask_delete->prev->next = grp_mask_delete->next;
    else
	*used_grp_mask_list = grp_mask_delete->next;

    if (grp_mask_delete->next)
	grp_mask_delete->next->prev = grp_mask_delete->prev;

    /* Remove all grp_rp entries for this grp_mask */
    for (entry_ptr = grp_mask_delete->grp_rp_next; entry_ptr; entry_ptr = entry_next) {
	entry_next = entry_ptr->grp_rp_next;

	/* Remap all related grpentry */
	for (grp_ptr = entry_ptr->grplink; grp_ptr; grp_ptr = grp_ptr_next) {
	    grp_ptr_next = grp_ptr->rpnext;
	    remap_grpentry(grp_ptr);
	}

	if (entry_ptr->rp_grp_prev != (rp_grp_entry_t *)NULL)
	    entry_ptr->rp_grp_prev->rp_grp_next = entry_ptr->rp_grp_next;
	else
	    entry_ptr->rp->rp_grp_next = entry_ptr->rp_grp_next;

	if (entry_ptr->rp_grp_next != NULL)
	    entry_ptr->rp_grp_next->rp_grp_prev = entry_ptr->rp_grp_prev;

	/* Delete the RP entry */
	if (entry_ptr->rp->rp_grp_next == NULL)
	    delete_rp_entry(used_cand_rp_list, used_grp_mask_list, entry_ptr->rp);

	free(entry_ptr);
    }

    free(grp_mask_delete);
}

/*
 * TODO: currently not used.
 */
void delete_rp(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, uint32_t rp_addr)
{
    cand_rp_t *ptr;
    uint32_t rp_addr_h = ntohl(rp_addr);

    for(ptr = *used_cand_rp_list; ptr != NULL; ptr = ptr->next) {
	if (ntohl(ptr->rpentry->address) > rp_addr_h)
	    continue;

	if (ptr->rpentry->address == rp_addr)
	    break;
	else
	    return;   /* Not found */
    }

    if (ptr == NULL)
	return;       /* Not found */

    delete_rp_entry(used_cand_rp_list, used_grp_mask_list, ptr);
}


static void delete_rp_entry(cand_rp_t **used_cand_rp_list, grp_mask_t **used_grp_mask_list, cand_rp_t *cand_rp_delete)
{
    rp_grp_entry_t *entry_ptr;
    rp_grp_entry_t *entry_next;
    grpentry_t *grp_ptr;
    grpentry_t *grp_ptr_next;

    if (cand_rp_delete == NULL)
	return;

    /* Remove from the cand-RP chain */
    if (cand_rp_delete->prev)
	cand_rp_delete->prev->next = cand_rp_delete->next;
    else
	*used_cand_rp_list = cand_rp_delete->next;

    if (cand_rp_delete->next)
	cand_rp_delete->next->prev = cand_rp_delete->prev;

    if (cand_rp_delete->rpentry->mrtlink) {
	if (cand_rp_delete->rpentry->mrtlink->flags & MRTF_KERNEL_CACHE)
	    delete_mrtentry_all_kernel_cache(cand_rp_delete->rpentry->mrtlink);

	FREE_MRTENTRY(cand_rp_delete->rpentry->mrtlink);
    }
    free ((char *)cand_rp_delete->rpentry);

    /* Remove all rp_grp entries for this RP */
    for (entry_ptr = cand_rp_delete->rp_grp_next; entry_ptr; entry_ptr = entry_next) {
	entry_next = entry_ptr->rp_grp_next;
	entry_ptr->group->group_rp_number--;

	/* First take care of the grp_rp chain */
	if (entry_ptr->grp_rp_prev)
	    entry_ptr->grp_rp_prev->grp_rp_next = entry_ptr->grp_rp_next;
	else
	    entry_ptr->group->grp_rp_next = entry_ptr->grp_rp_next;

	if (entry_ptr->grp_rp_next)
	    entry_ptr->grp_rp_next->grp_rp_prev = entry_ptr->grp_rp_prev;

	if (entry_ptr->grp_rp_next == NULL)
	    delete_grp_mask_entry(used_cand_rp_list, used_grp_mask_list, entry_ptr->group);

	/* Remap the related groups */
	for (grp_ptr = entry_ptr->grplink; grp_ptr; grp_ptr = grp_ptr_next) {
	    grp_ptr_next = grp_ptr->rpnext;
	    remap_grpentry(grp_ptr);
	}

	free(entry_ptr);
    }

    free((char *)cand_rp_delete);
}


/*
 * Rehash the RP for the group.
 * XXX: currently, every time when remap_grpentry() is called, there has
 * being a good reason to change the RP, so for performancy reasons
 * no check is performed whether the RP will be really different one.
 */
int remap_grpentry(grpentry_t *grpentry_ptr)
{
    rpentry_t *rpentry_ptr;
    rp_grp_entry_t *entry_ptr;
    mrtentry_t *grp_route;
    mrtentry_t *mrtentry_ptr;

    if (grpentry_ptr == NULL)
	return FALSE;

    /* Remove from the list of all groups matching to the same RP */
    if (grpentry_ptr->rpprev) {
	grpentry_ptr->rpprev->rpnext = grpentry_ptr->rpnext;
    } else {
	if (grpentry_ptr->active_rp_grp)
	    grpentry_ptr->active_rp_grp->grplink = grpentry_ptr->rpnext;
    }

    if (grpentry_ptr->rpnext)
	grpentry_ptr->rpnext->rpprev = grpentry_ptr->rpprev;

    entry_ptr = rp_grp_match(grpentry_ptr->group);
    if (entry_ptr == NULL) {
	/* If cannot remap, delete the group */
	delete_grpentry(grpentry_ptr);
	return FALSE;
    }
    rpentry_ptr = entry_ptr->rp->rpentry;

    /* Add to the new chain of all groups mapping to the same RP */
    grpentry_ptr->rpaddr  = rpentry_ptr->address;
    grpentry_ptr->active_rp_grp = entry_ptr;
    grpentry_ptr->rpnext = entry_ptr->grplink;
    if (grpentry_ptr->rpnext)
	grpentry_ptr->rpnext->rpprev = grpentry_ptr;
    grpentry_ptr->rpprev = NULL;
    entry_ptr->grplink = grpentry_ptr;

    grp_route = grpentry_ptr->grp_route;
    if (grp_route) {
	grp_route->upstream   = rpentry_ptr->upstream;
	grp_route->metric     = rpentry_ptr->metric;
	grp_route->preference = rpentry_ptr->preference;
	change_interfaces(grp_route, rpentry_ptr->incoming,
			  grp_route->joined_oifs,
			  grp_route->pruned_oifs,
			  grp_route->leaves,
			  grp_route->asserted_oifs, MFC_UPDATE_FORCE);
    }

    for (mrtentry_ptr = grpentry_ptr->mrtlink; mrtentry_ptr; mrtentry_ptr = mrtentry_ptr->grpnext) {
	if (!(mrtentry_ptr->flags & MRTF_RP))
	    continue;

	mrtentry_ptr->upstream = rpentry_ptr->upstream;
	mrtentry_ptr->metric   = rpentry_ptr->metric;
	mrtentry_ptr->preference = rpentry_ptr->preference;
	change_interfaces(mrtentry_ptr, rpentry_ptr->incoming,
			  mrtentry_ptr->joined_oifs,
			  mrtentry_ptr->pruned_oifs,
			  mrtentry_ptr->leaves,
			  mrtentry_ptr->asserted_oifs, MFC_UPDATE_FORCE);
    }

    return TRUE;
}


rpentry_t *rp_match(uint32_t group)
{
    rp_grp_entry_t *ptr;

    ptr = rp_grp_match(group);
    if (ptr)
	return ptr->rp->rpentry;

    return NULL;
}

rp_grp_entry_t *rp_grp_match(uint32_t group)
{
    grp_mask_t *mask_ptr;
    rp_grp_entry_t *entry_ptr;
    rp_grp_entry_t *best_entry = NULL;
    uint8_t best_priority       = ~0; /* Smaller is better */
    uint32_t best_hash_value    = 0;  /* Bigger is better */
    uint32_t best_address_h     = 0;  /* Bigger is better */
    uint32_t curr_hash_value    = 0;
    uint32_t curr_address_h     = 0;
    uint32_t group_h            = ntohl(group);

    if (grp_mask_list == NULL)
	return NULL;

    for (mask_ptr = grp_mask_list; mask_ptr; mask_ptr = mask_ptr->next) {
	/* Search the grp_mask (group-prefix) list */
	if ((group_h & ntohl(mask_ptr->group_mask))
	    != ntohl(mask_ptr->group_mask & mask_ptr->group_addr))
	    continue;

	for (entry_ptr = mask_ptr->grp_rp_next; entry_ptr; entry_ptr = entry_ptr->grp_rp_next) {
	    if (best_priority < entry_ptr->priority)
		break;

	    curr_hash_value = RP_HASH_VALUE(group_h, mask_ptr->hash_mask, curr_address_h);
	    curr_address_h = ntohl(entry_ptr->rp->rpentry->address);

	    if (best_priority == entry_ptr->priority) {
		/* Compare the hash_value and then the addresses */
		if (curr_hash_value < best_hash_value)
		    continue;

		if (curr_hash_value == best_hash_value) {
		    if (curr_address_h < best_address_h)
			continue;
		}
	    }

	    /* The current entry in the loop is preferred */
	    best_entry = entry_ptr;
	    best_priority = best_entry->priority;
	    best_address_h = curr_address_h;
	    best_hash_value = curr_hash_value;
	}
    }

    return best_entry;
}


rpentry_t *rp_find(uint32_t rp_address)
{
    cand_rp_t *cand_rp_ptr;
    uint32_t address_h = ntohl(rp_address);

    for(cand_rp_ptr = cand_rp_list; cand_rp_ptr != NULL; cand_rp_ptr = cand_rp_ptr->next) {
	if (ntohl(cand_rp_ptr->rpentry->address) > address_h)
	    continue;

	if (cand_rp_ptr->rpentry->address == rp_address)
	    return cand_rp_ptr->rpentry;

	return NULL;
    }

    return NULL;
}


/*
 * Create a bootstrap message in "send_buff" and returns the data size
 * (excluding the IP header and the PIM header) Can be used both by the
 * Bootstrap router to multicast the RP-set or by the DR to unicast it to
 * a new neighbor. It DOES NOT change any timers.
 */
int create_pim_bootstrap_message(char *send_buff)
{
    uint8_t *data_ptr;
    grp_mask_t *mask_ptr;
    rp_grp_entry_t *entry_ptr;
    int datalen;
    uint8_t masklen;

    if (curr_bsr_address == INADDR_ANY_N)
	return 0;

    data_ptr = (uint8_t *)(send_buff + sizeof(struct ip) + sizeof(pim_header_t));
    if (curr_bsr_address == my_bsr_address)
	curr_bsr_fragment_tag++;

    PUT_HOSTSHORT(curr_bsr_fragment_tag, data_ptr);
    MASK_TO_MASKLEN(curr_bsr_hash_mask, masklen);
    PUT_BYTE(masklen, data_ptr);
    PUT_BYTE(curr_bsr_priority, data_ptr);
    PUT_EUADDR(curr_bsr_address, data_ptr);

    /* TODO: XXX: No fragmentation support (yet) */
    for (mask_ptr = grp_mask_list; mask_ptr; mask_ptr = mask_ptr->next) {
	if (IN_PIM_SSM_RANGE(mask_ptr->group_addr)) {
	    continue;  /* Do not advertise internal virtual RP for SSM groups */
	}
	MASK_TO_MASKLEN(mask_ptr->group_mask, masklen);
	PUT_EGADDR(mask_ptr->group_addr, masklen, 0, data_ptr);
	PUT_BYTE(mask_ptr->group_rp_number, data_ptr);
	PUT_BYTE(mask_ptr->group_rp_number, data_ptr); /* TODO: if frag.*/
	PUT_HOSTSHORT(0, data_ptr);

	for (entry_ptr = mask_ptr->grp_rp_next; entry_ptr; entry_ptr = entry_ptr->grp_rp_next) {
	    PUT_EUADDR(entry_ptr->rp->rpentry->address, data_ptr);
	    PUT_HOSTSHORT(entry_ptr->holdtime, data_ptr);
	    PUT_BYTE(entry_ptr->priority, data_ptr);
	    PUT_BYTE(0, data_ptr);  /* The reserved field */
	}
    }

    datalen = (data_ptr - (uint8_t *)send_buff) - sizeof(struct ip) - sizeof(pim_header_t);

    return datalen;
}


/*
 * Check if the addr is the RP for the group corresponding to mrt.
 * Return TRUE or FALSE.
 */
int check_mrtentry_rp(mrtentry_t *mrt, uint32_t addr)
{
    rp_grp_entry_t *ptr;

    if (!mrt)
	return FALSE;

    if (addr == INADDR_ANY_N)
	return FALSE;

    ptr = mrt->group->active_rp_grp;
    if (!ptr)
	return FALSE;

    if (mrt->group->rpaddr == addr)
	return TRUE;

    return FALSE;
}

/**
 * Local Variables:
 *  version-control: t
 *  indent-tabs-mode: t
 *  c-file-style: "ellemtel"
 *  c-basic-offset: 4
 * End:
 */