rerr.c

一种AODV实现方法

/*
               Kernel AODV  v2.0
National Institute of Standards and Technology
               Luke Klein-Berndt
-----------------------------------------------------
  Version 2.0 new features:
     * Updated to AODV draft version 11
     * Managed internet gatewaying
     * Monitor wireles signal strength
     * Many bug fixes!
-----------------------------------------------------

Originally based upon MadHoc code. I am not
sure how much of it is left anymore, but MadHoc
proved to be a great starting point.

MadHoc was written by - Fredrik Lilieblad,
Oskar Mattsson, Petra Nylund, Dan Ouchterlony
and Anders Roxenhag Mail: [e-mail]

This software is Open Source under the GNU General Public Licence.

*/

#include "rerr.h"

/****************************************************

   rerr
----------------------------------------------------
Handles the generation of RERR messages
****************************************************/


extern u_int32_t g_broadcast_ip;
extern u_int32_t g_my_ip;
void free_rerrhdr(struct rerrhdr *tmp_rerrhdr);

int send_rerr(struct rerrhdr *tmp_rerrhdr, u_int32_t sent_to);

/****************************************************

   link_break
----------------------------------------------------
link_break is called when a broken link to a neighbouring
is detected. All active routes that have the unreachable node as next
hop are invalidated. All precursors for this entry are removed. The
RERR meassage including the unreachable destinations and their
 incremented seq numbers is finally rebroadcast.

****************************************************/

int link_break( u_int32_t brk_dst_ip)
{
    struct route_table_entry *tmp_entry;
    struct rerrhdr *new_rerrhdr = NULL;
    struct precursor_entry *tmp_precursor;
    struct precursor_entry *dead_precursor;


    u_int32_t last_precursor;
    u_int8_t precursor_num=0;


    int rerrhdr_created = 0;

    // remove the borken link from all the route table entries
    delete_precursor_entry_from_route_table(brk_dst_ip);

    tmp_entry=get_first_route_table_entry();

    //go through list
    while(tmp_entry != NULL)
    {
        //if the route has the broken IP for the next hop and is active
        if((tmp_entry->next_hop == brk_dst_ip) && (tmp_entry->route_valid))
        {

#ifdef MESSAGES
            printk("RERR: Broken link as next hop for - %s \n",inet_ntoa(tmp_entry->dst_ip));
#endif
            //expire the route
            route_expiry(tmp_entry);

#ifdef TRACE
            printk("RERR: Route marked as expired\n");
#endif

            //if the rerr header has not been created yet
            if(!rerrhdr_created)
            {
                if((new_rerrhdr =create_rerrhdr(tmp_entry->dst_ip,tmp_entry->dst_seq)) == NULL)
                    return 1;
                rerrhdr_created = 1;
            }
            else
            {
                append_unr_dst(new_rerrhdr, tmp_entry->dst_ip, tmp_entry->dst_seq);
            }

#ifdef TRACE
            printk("RERR: About to delete precursors from route table entry\n");
#endif
            //remove all the precursors from the route
            tmp_precursor=tmp_entry->precursors;

            while (tmp_precursor!=NULL)
            {
                precursor_num++;
                last_precursor=tmp_precursor->ip;
                dead_precursor=tmp_precursor;
                tmp_precursor=tmp_precursor->next;
                kfree(dead_precursor);
            }
            tmp_entry->precursors=NULL;
        }

        //move on to the next entry
        tmp_entry = tmp_entry->next;
    }
    //if there was a RERR created, send it out
    if(rerrhdr_created)
    {
        if (precursor_num==1)
            send_rerr(new_rerrhdr,last_precursor);
        else
            send_rerr(new_rerrhdr,g_broadcast_ip);

        free_rerrhdr(new_rerrhdr);
    }

    return 0;
}



/****************************************************

   route_expiry
----------------------------------------------------
 route_expiry invalidates an active route, i e an entry
 in the routing table.
****************************************************/

void route_expiry(struct route_table_entry *tmp_entry)
{
    //marks a route as expired


    tmp_entry->lifetime = (getcurrtime() + DELETE_PERIOD);
    tmp_entry->dst_seq++;
    tmp_entry->route_valid=FALSE;
    delete_kernel_route_entry(tmp_entry->dst_ip, tmp_entry->next_hop);
}



/****************************************************

   host_unr
----------------------------------------------------
host_unr is called when a packet is received destined for a node
which the forwarding node does not have an active route to. A RERR
message is created to inform neighbours.
****************************************************/
int  host_unr(u_int32_t brk_dst_ip)
{
    struct rerrhdr *new_rerrhdr = NULL;
    struct route_table_entry *tmp_entry;

    tmp_entry = find_route_table_entry(brk_dst_ip);

    if((new_rerrhdr = create_rerrhdr(brk_dst_ip, 1)) == NULL)
        return 1;

    send_rerr(new_rerrhdr,g_broadcast_ip);
    free_rerrhdr(new_rerrhdr);

    return 0;
}


/****************************************************

   rec_rerr
----------------------------------------------------
rec_rerr is called when the node receives a RERR packet from
another node. If the precursor list for a broken destinations is
not empty a new RERR is created for that destination.
****************************************************/

int recv_rerr(struct event_queue_entry *working_packet)
{
    struct rerr *tmp_hdr;
    struct rerrhdr *new_rerrhdr = NULL;
    struct rerrdst *tmp_dst;
    struct route_table_entry *tmp_route;
    struct interface_list_entry *tmp_interface;

    int new_rerr_created = 0;
    int i;

    tmp_interface=find_interface_by_dev(working_packet->dev);
    if (tmp_interface==NULL)
        return 0;
    tmp_hdr =(struct rerr *) ((char *) working_packet->data);
    tmp_dst = (struct rerrdst *) ((char *) tmp_hdr + sizeof (struct rerr));

#ifdef MESSAGES
    printk("RERR: recieved a route error, count= %u\n",tmp_hdr->dst_count);
#endif

    for(i = 0; i < tmp_hdr->dst_count; i++)
    {
        //go through all the unr dst in the rerr
#ifdef MESSAGES
        printk("       -> %s",inet_ntoa(tmp_dst->unr_dst_ip));
#endif

        tmp_route = find_route_table_entry(tmp_dst->unr_dst_ip);

        //Is the sender of the rerr the next hop for a broken destination for the current node?
        if(tmp_route != NULL)
        {

            if( tmp_route->dst_ip != tmp_interface->ip )
            {

                if (tmp_route->next_hop == working_packet->src_ip)
                {
#ifdef MESSAGES
                    printk(" Removing route");
#endif

                    tmp_route->dst_seq = ntohl(tmp_dst->unr_dst_seq);
                    tmp_route->route_valid=FALSE;
                    tmp_route->lifetime = (getcurrtime() + DELETE_PERIOD);
                    delete_kernel_route_entry(tmp_route->dst_ip, tmp_route->next_hop);

                    if(tmp_route->precursors != NULL)
                    {
                        // precursors exist
                        if(!new_rerr_created)
                        {
                            new_rerr_created = 1;
                            new_rerrhdr = create_rerrhdr(tmp_dst->unr_dst_ip, tmp_dst->unr_dst_seq);

                        }
                        else
                        {
                            append_unr_dst(new_rerrhdr, tmp_dst->unr_dst_ip,  tmp_dst->unr_dst_seq);

                        }
                    }
                }
            }

        }
	#ifdef MESSAGES
        printk(" \n");
	#endif
        tmp_dst =(struct rerrdst *) ((char *) tmp_dst + sizeof (struct rerrdst));



    }

    if(new_rerr_created)
    {
        send_rerr(new_rerrhdr,g_broadcast_ip);
        free_rerrhdr(new_rerrhdr);
    }

    return 0;
}


/****************************************************

   create_rerrhdr
----------------------------------------------------
create_rerrhdr is used to create a new RERR message
****************************************************/

struct rerrhdr* create_rerrhdr(u_int32_t tmp_ip, u_int32_t tmp_dst_seq)
{
    struct rerr_unr_dst *tmp_rerr_unr_dst;
    struct rerrhdr *tmp_rerrhdr;

    //create header
    if((tmp_rerrhdr = kmalloc(sizeof(struct rerrhdr),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("RERR: Error creating tmp_rerrhdr \n");
#endif
        return NULL;
    }

    //create spot for first entry
    if((tmp_rerr_unr_dst = kmalloc(sizeof(struct rerr_unr_dst),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("RERR: Error creating temp_rerr_unr_dst\n");
#endif
        return NULL;
    }

    //fill in info for first entry
    tmp_rerr_unr_dst->unr_dst_ip = tmp_ip;
    tmp_rerr_unr_dst->unr_dst_seq = tmp_dst_seq;
    tmp_rerr_unr_dst->next = NULL;

    //fill in info for header
    tmp_rerrhdr->unr_dst = tmp_rerr_unr_dst;
    tmp_rerrhdr->type = 3;
    tmp_rerrhdr->dst_count = 1;

    return tmp_rerrhdr;
}


/****************************************************

   append_unr_dst
----------------------------------------------------
append_unr_dst adds an unreachable node to the previously
created RERR message.
****************************************************/

int append_unr_dst(struct rerrhdr *tmp_rerrhdr, u_int32_t tmp_ip,u_int32_t tmp_dst_seq)
{
    struct rerr_unr_dst *tmp_rerr_unr_dst;

    //get memory for new entry
    if((tmp_rerr_unr_dst = kmalloc(sizeof(struct rerr_unr_dst),GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("RERR: Error appending new unr_dst\n");
#endif
        return 1;
    }

    //fill in info for entry
    tmp_rerr_unr_dst->next = tmp_rerrhdr->unr_dst;
    tmp_rerrhdr->unr_dst = tmp_rerr_unr_dst;
    tmp_rerrhdr->dst_count++;
    tmp_rerr_unr_dst->unr_dst_ip = tmp_ip;
    tmp_rerr_unr_dst->unr_dst_seq = tmp_dst_seq;

    return 0;
}

/****************************************************

   free_rerrhdr
----------------------------------------------------
 free_rerrhdr frees the allocated memory for the rerrhdr
 list structure.
****************************************************/
void free_rerrhdr(struct rerrhdr *tmp_rerrhdr)
{
    struct rerr_unr_dst *tmp_unr_dst;
    struct rerr_unr_dst *dead_dst;

    //for all the unreachable destinataion in the rerr
    tmp_unr_dst=tmp_rerrhdr->unr_dst;

    while (tmp_unr_dst!=NULL)
    {
        dead_dst=tmp_unr_dst;

        tmp_unr_dst = tmp_unr_dst->next;
        kfree(tmp_unr_dst);
    }

    kfree(tmp_rerrhdr);
}



/****************************************************

   send_rerr
----------------------------------------------------
 send_rerr copies the incoming RERR message to a connected
 data area, which is a suitable format for the function send_datagram.
****************************************************/
int send_rerr(struct rerrhdr *tmp_rerrhdr, u_int32_t sent_to)
{
    struct rerr *out_hdr;
    struct rerrdst *out_dst;
    struct rerr_unr_dst *tmp_dst;
    void *data;

    int datalen, i;

    datalen = sizeof(struct rerr) + sizeof(struct rerrdst) * (tmp_rerrhdr->dst_count);
    //get the needed memory
    if((data = kmalloc(datalen,GFP_ATOMIC)) == NULL)
    {
#ifndef NO_ERROR
        printk("RERR: Error creating packet to send RERR\n");
#endif
        return -1;
    }

    out_hdr =(struct rerr *) ((char *) data);
    out_hdr->type = 3;
    out_hdr->dst_count = tmp_rerrhdr->dst_count;
    out_hdr->reserved =0;

    out_dst=(struct rerrdst *) ((char *) out_hdr + sizeof(struct rerr));
    tmp_dst = tmp_rerrhdr->unr_dst;

    for(i = 0; i < tmp_rerrhdr->dst_count; i++)
    {
        out_dst->unr_dst_ip=tmp_dst->unr_dst_ip;
	#ifdef MESSAGES
        printk("RERR: adding... %s to RERR\n",inet_ntoa(out_dst->unr_dst_ip));
	#endif

        //convert it to network byte order
        out_dst->unr_dst_seq=htonl(tmp_dst->unr_dst_seq);
        out_dst =(struct rerrdst *) ((char *) out_dst + sizeof(struct rerrdst));
        tmp_dst = tmp_dst->next;
    }
#ifdef TRACE
    printk("RERR: sending out a RERR with %d UNR hosts\n",i);
#endif
    if (sent_to==g_broadcast_ip)
        local_broadcast(NET_DIAMETER, data, datalen);
    else
        send_message(sent_to,NET_DIAMETER, data, datalen);

    kfree(data);



    return 0;
}

/*
 * print_rerrhdr
 *
 * Description:
 *   print_rerrhdr prints a RERR message
 *
 * Arguments:
 *   struct rerrhdr *new_rerrhdr - Pointer to the rerrhdr
 *
 * Returns: void
 */
void print_rerrhdr(struct rerrhdr *new_rerrhdr)
{
    struct rerr_unr_dst *tmp_rerr_unr_dst;
    struct in_addr tmp_in_addr;
    int i;

    printk("Outgoing RERR message: type: %d dst_cnt: %d\n",
           new_rerrhdr->type, new_rerrhdr->dst_count);

    for(i = 0, tmp_rerr_unr_dst = new_rerrhdr->unr_dst;
            i < new_rerrhdr->dst_count;
            i++, tmp_rerr_unr_dst = tmp_rerr_unr_dst->next)
    {
        tmp_in_addr.s_addr = tmp_rerr_unr_dst->unr_dst_ip;
        printk("unr_dst_ip: %s unr_dst_seq %d\n",
               inet_ntoa(tmp_in_addr.s_addr),
               tmp_rerr_unr_dst->unr_dst_seq);
    }
}