/*
 * Center for Information Technology Integration
 *           The University of Michigan
 *                    Ann Arbor
 *
 * Dedicated to the public domain.
 * Send questions to info@citi.umich.edu
 * BOOTP is documented in RFC 951 and RFC 1048
 *
 * Delinted, ANSIfied and reformatted - 5/30/91 P. Karn
 */



/* Dynamic Ip Assignment for a Bootp Server
 * Called when a client request is received and the bootp server doesnt' have a
 * record for it.
 *
 * Design goals:
 *   Assign an IP address
 *   Separation/Identification of IP addresses assigned and not assigned
 *   Time out mechanism to reclaim IP address
 *	Timer, and arp on address with little activity
 *   Reassignment to same machine if possible.
 */     
#include <stdio.h>
#include <time.h>	

#include "global.h"
#include "arp.h"
#include "iface.h"
#include "mbuf.h"
#include "netuser.h"
#include "pktdrvr.h"
#include "timer.h"
#include "bootpd.h"


#define E_NOMEM 3101
#define ERR_NOIPADDRESS	3103		/* No IP address available. */

#define THRESH_ON            20    /* (%) When to turn on reclaimation of IP addresses. */
#define THRESH_CRITICAL       2    /* (#) */
#define THRESH_OFF           50    /* (%) */

#define R_OFF                   0x01    /* Reclaimation is off. */
#define R_RECLAIM               0x02    /* Reclaimation is on. */
#define R_CRITICAL              0x04    /* Reclaimation is operating in critical state. */
#define R_DONE                  0x08    /* Reclaimation is finishing up. */
#define V_SWAIT                 0x10    /* Reclaimation is wait to start verif cycle. */
#define V_VERIFY                0x20    /* Reclaimation is in verification cycle. */

#define TIME_RWAIT		(5) 	/* Time between running reclm da_task */
#define TIME_SWAIT              (30)    /* Time between cycles of starting address rec */
#define TIME_VWAIT              (10)    /* Time to wait between sending ARPs to verify add
resses. */
#define TIME_ADDRRETRY          (4 * 600)       /* Time to wait before trying to reclaim a
n address. */
#define TIME_ADDRRECLAIM        (900)   /* Time for which an address must be in the reclai
mation */
                                        /* queue before being moved to the free list. */

#define RECLAIM_QUEUE_MAX       15      /* Maximum number of addresses in reclaimation queue. */



/*      dynamic_ip.c
 *
 * This file contains code to manage a range of dynamic IP addresses on a network.
 */
	


/* Queue structures  */

typedef  struct  q_elt {
        struct  q_elt *next;
};

#define NULLQ_ELT (struct q_elt *) 0


struct  q {
        char *head;
        char *tail;
};

#define NULLQ_P (struct q *) 0


/* Dynamic IP structures */

struct daddr {
        struct daddr	*da_next;       /* Queue link. */
        int32		da_addr;        /* IP address. */
        time_t		da_time;        /* last time this address was answered for. */
	char		da_hwaddr[1];   /* Hardware address, variable length. */
};

#define NULLDADDR (struct daddr *) 0

struct drange_desc {
        struct drange_desc *dr_next;    /* Queue link. */
        struct iface    *dr_iface;      /* Pointer to network information. */
	struct timer	timer;		/* Timer for reclaiming */
        int32    	dr_start;       /* First IP address in range. */
        int32    	dr_end;         /* Last IP address in range. */
        int16           dr_acount;      /* Number of IP addresses in range. */
        int16           dr_fcount;      /* Number of IP addresses in free. */
        int16           dr_rcount;      /* Number of IP addresses on reclmation queue  */
        int16           dr_thon;        /* Threshold for turning on reclaimation. */
        int16           dr_thcritical;  /* Threshold for critical reclaimation. */
        int16           dr_thoff;       /* Threshold for turning off reclaimation. */
        int32           dr_time_addrretry;      /* Time to wait before retrying addresses.
						   Varies with state. */
        int16           dr_hwaddrlen;   /* Length of hardware address. */
        unsigned char   dr_rstate;      /* Reclaimation state. */
        unsigned char   dr_vstate;      /* Verification state. */
        time_t          dr_rtime;       /* Time stamp for reclaimation. */
        struct daddr    *dr_raddr;      /* Address being verified. */
        struct daddr    *dr_table;      /* Pointer to table of addresses. */
        struct q        dr_usedq;       /* Pointer to list of used addresses. */
        struct q        dr_reclaimq;    /* Pointer to list of addrs being reclaimed.  */
        struct q        dr_freeq;       /* Pointer to list of free addresses. */
};

#define NULLDRANGE (struct drange_desc *) 0





#define da_structlen(dr)        (sizeof (struct daddr) + dr->dr_hwaddrlen)
#define da_getnext(dr,da)       ((struct daddr *) ((unsigned char *)da + da_structlen(dr)))


/*
 * Globals.
 */

int ifaceToArpMap[] = {
        0, 		                        /* CL_NONE */
        ARP_ETHER, 	                        /* CL_ETHERNET */
        ARP_PRONET, 	                        /* CL_PRONET_10 */
        ARP_IEEE802,	                        /* CL_IEEE8025 */
        0, 		                        /* CL_OMNINET */
        ARP_APPLETALK,                          /* CL_APPLETALK */
        0, 	          	                /* CL_SERIAL_LINE */
        0, 		                        /* CL_STARLAN */
        ARP_ARCNET, 	                        /* CL_ARCNET */
        ARP_AX25,                               /* CL_AX25 */
        0,                                      /* CL_KISS */
        0,                                      /* CL_IEEE8023 */
        0,                                      /* CL_FDDI */
        0,                                      /* CL_INTERNET_X25 */
        0,                                      /* CL_LANSTAR */
        0,                                      /* CL_SLFP */
        ARP_NETROM,                             /* CL_NETROM */
        0                                       /* NCLASS */
};



static struct q                 rtabq;
struct timer			da_timer;
char				bp_ascii[128];

static void da_runtask __ARGS((void *arg));
struct q_elt *q_dequeue __ARGS((struct q *queue));
static void da_closeup __ARGS((struct drange_desc *dr));
static void dprint_addresses __ARGS((struct drange_desc *dr));
static int q_remove __ARGS((struct q *source_queue,struct q_elt *qel));
static void iptoa __ARGS((int32 ipaddr,char ipstr[16]));
static void da_task __ARGS((void));
static int da_fill_reclaim __ARGS((struct drange_desc *dr));
static void da_do_verify __ARGS((struct drange_desc *dr,int pendtime));
static void da_enter_reclaim __ARGS((struct drange_desc *dr));
static void da_enter_done __ARGS((struct drange_desc *dr));
static void da_enter_off __ARGS((struct drange_desc *dr));
static void q_enqueue __ARGS((struct q 	*queue,struct q_elt *elem));
static int da_get_old_addr __ARGS((struct drange_desc *dr,char *hwaddr,struct daddr **dap));
static int da_get_free_addr __ARGS((struct drange_desc *dr,struct daddr **dap));
static void da_enter_critical __ARGS((struct drange_desc *dr));
static void q_init __ARGS((struct q *queue));

extern int bp_ReadingCMDFile;



/*
 * Shutdown routines.
 */

/*
 * Done serving a network.
 */
da_done_net(iface)
struct iface *iface;
{
        struct drange_desc *dr;

        /* Find the network table */
        for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
                if(iface == dr->dr_iface)
                        break;
        }

        if(dr == NULLDRANGE){
		bp_log("Range for interface '%s' not found.\n", iface->name);
		return -1;
	}

        da_closeup(dr);
	bp_log("Range removed for iface %s\n", iface->name);
        return 0;
}




/*
 * Print the status of the da structures.
 */
void
da_status(iface)
struct iface *iface;
{
        struct drange_desc *dr;

	/* If no interface was specified, print all the range information */
	if(iface == NULLIF){
        	for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; 
		 dr = dr->dr_next) 
			dprint_addresses(dr);
	
	} else {
		/* Print the specified range's information */
		/* Find the specified interface */
        	for(dr = (struct drange_desc *) rtabq.head; 
		 (dr != NULLDRANGE) && (dr->dr_iface != iface); 
		 dr = dr->dr_next)
			; 
		
		/* If network not found, return */
		if(dr == NULLDRANGE){
			tprintf("Range for interface '%s' not found.\n", iface->name);
			return;	
		}
		/* The range has been found.  Print it. */
		dprint_addresses(dr);
	}
}



/*
 * Finish up service.  Close up on each of the address ranges.
 */
void
da_shut()
{
        struct drange_desc *dr;

	stop_timer(&da_timer);
        while((dr = (struct drange_desc *)q_dequeue (&rtabq)) != NULLDRANGE)
                da_closeup(dr);
}


/*
 * Release resource for a network.
 */
static void
da_closeup(dr)
struct drange_desc *dr;
{
        free(dr->dr_table);			/* Free the address table. */
        q_remove(&rtabq, (struct q_elt *)dr);	/* Dequeue the range descriptor. */
        free(dr);				/* Free the range descriptor. */
}



/* This is only called from a command */
static void
dprint_addresses(dr)
struct drange_desc *dr;
{
        struct daddr *da;
        char ipa[16];
	char ipb[16];
	struct arp_type	*at;
	
	at = &Arp_type[dr->dr_iface->type];

	iptoa(dr->dr_start, ipa);
	iptoa(dr->dr_end, ipb);
	tprintf("Interface %s range: %s - %s\n", dr->dr_iface->name, ipa, ipb);

        da = (struct daddr *) dr->dr_freeq.head;
	tprintf("Free address queue\n");
        while(da){
                iptoa(da->da_addr, ipa);
                tprintf("    %s  last used by %s\n", ipa,(*at->format)(bp_ascii, da->da_hwaddr));
                da = da->da_next;
        }

        da = (struct daddr *) dr->dr_usedq.head;
        tprintf("\nUsed address queue\n");
        while(da){
                iptoa(da->da_addr, ipa);
                tprintf("    %s  in use by %s\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
                da = da->da_next;
        }

        da =(struct daddr *) dr->dr_reclaimq.head;
        tprintf("\nReclaimation address queue\n");
        while(da){
                iptoa(da->da_addr, ipa);
                tprintf("    %s  in use by %s?\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
                da = da->da_next;
        }
        tprintf("\n");
}



/*
 * Reclaimation routines.
 */
static void
da_runtask(p)
void *p;
{
	stop_timer(&da_timer);
	da_task();
	set_timer(&da_timer,TIME_RWAIT*1000L);
	start_timer(&da_timer);
}

/*
 * Called periodically to run reclaimation.
 */
static void
da_task()
{
	struct drange_desc *dr;
	time_t now;
	int arpHardware, arpPendtime;

	now = time(NULL);

	for(dr = (struct drange_desc *)rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){

		arpHardware = ifaceToArpMap [dr->dr_iface->type];
		arpPendtime = Arp_type[arpHardware].pendtime;

		if(!(dr->dr_rstate & R_OFF)){	/* If doing reclaimation on this range. */
			if(dr->dr_vstate == V_SWAIT){	/* If in wait sub-state. */
				/* Doing reclaimation on this range and am waiting to 
				 * start a cycle of address
				 * verification.  Check if it is time to start the 
				 * cycle. */

				if(now - dr->dr_rtime > TIME_SWAIT){
					/* Start the cycle.  */
					if(!(dr->dr_rstate & R_DONE))
						da_fill_reclaim(dr);

					dr->dr_vstate = V_VERIFY; /* verify sub-state. */
					dr->dr_raddr = NULLDADDR; /* start at beginning */
				}
			}
			/* If in the verify state (may have just been changed above), and 
			 * enough time has passed since last lookup, check it and start
			 * the next lookup. */

			if(dr->dr_vstate == V_VERIFY){
				if(now - dr->dr_rtime > arpPendtime){
					da_do_verify(dr, arpPendtime); /* Verify address. */
					dr->dr_rtime = time(NULL); /* Set time stamp. */
					if(dr->dr_raddr == NULLDADDR){ /* If at end... */
						dr->dr_vstate = V_SWAIT; /* Q empty; enter wait sub-state. */
					}
				}
			}
			
			/* 
			 * State transitions.  May have moved some addresses to free list.
			 * If so, I may be able to move to a "lower" state.
			 */
			switch(dr->dr_rstate){
			/* case R_OFF: Not handled. */
			case R_CRITICAL:
				/* Have conditions droped below critical threshhold? */
				if(dr->dr_fcount > dr->dr_thcritical)	
					da_enter_reclaim(dr);
				/* Fall through. */
			case R_RECLAIM:
				/* Have I reclaimed enough addresses? */
				if(dr->dr_fcount > dr->dr_thoff)	
					da_enter_done(dr);
				/* Fall through. */
			case R_DONE:
				/* Am I in the done state and have exausted the reclaimation queue? */
				if((dr->dr_rstate & R_DONE) && dr->dr_reclaimq.head == NULLCHAR) 
					da_enter_off(dr);
				break;
			}
		}
	}
}




/* 
 * Enter the DONE state.  Can't get to the done state from the off state.
 */
static void
da_enter_done(dr)
struct drange_desc *dr;
{
	char ipa[16], ipb[16];
	
	iptoa(dr->dr_start, ipa);
	iptoa(dr->dr_end, ipb);

	if((dr->dr_rstate & R_OFF) == 0){ 
		dr->dr_rstate = R_DONE;
		dr->dr_time_addrretry = TIME_ADDRRETRY;		/* Wait a while before retrying addresses. */
	}
}


/* 
 * Enter the OFF state.
 */
static void
da_enter_off(dr)
struct drange_desc *dr;
{
	char ipa[16], ipb[16];
	
	iptoa(dr->dr_start, ipa);
	iptoa(dr->dr_end, ipb);

	dr->dr_rstate = R_OFF;
}


/*
 * Verify addresses.
 * To avoid flodding the network and our address resolution queue I only send
 * out one ARP at a time.  This routine is called periodically to step through
 * the reclaimation queue.  The first step is to check for a responce to the
 * ARP that was sent out previously.  If there is a responce I move the address
 * to the used queue. The next step is to send out an ARP for the next address
 * on the recliamation queue. After a suitable intervel (TIME_VTIME) I'll be
 * called again.
 */
static void
da_do_verify(dr, pendtime)
struct drange_desc *dr;
int pendtime;
{
	struct daddr *da, *dn;
	struct iface *iface;
	long now;
	struct arp_tab *ap;
	int16 arpType;
	
 	now = time(NULL);
 	iface = dr->dr_iface;
	arpType = ifaceToArpMap[iface->type];

	/*
 	 * If I sent an ARP for an address, check if that ARP has been responded to.
	 * If dr_raddr points to an address record, I have previously sent an
	 * ARP for that address.  Check the ARP cache for a responce.
	 * If dr_raddr is NULL then I am to start at the head of the reclaim queue.
 	 */

	if(dr->dr_raddr != NULLDADDR){
		/* ARP has been sent for dr_raddr.  Check the ARP cache for a responce. */
		da = dr->dr_raddr;
		dn = da->da_next;

		ap = arp_lookup(arpType, da->da_addr);

		if((ap != NULLARP) && (ap->state == ARP_VALID)){
			/* Host responded to arp.  Place address on used queue.
			 * Copy in physical address of host using address to
			 * make sure our info is up to date.  
			 * I could verify that physical address of host
			 * responding to  ARP matches the physical address of
			 * the host I think owns the address.  If don't match
			 * someone is probably using an incorrect address.
			 */

			q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
			--dr->dr_rcount;
			da->da_time = now;		/* Time tested. */
			memcpy(da->da_hwaddr, ap->hw_addr, Arp_type[ap->hardware].hwalen);
			q_enqueue(&dr->dr_usedq, (struct q_elt *)da);

		} else {
			/* Host did not respond to ARP.  If addr on reclaim
			 * queue long enough, move it to the free queue.
			 */
			if(now - da->da_time >= pendtime){
				q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
				--dr->dr_rcount;
				q_enqueue(&dr->dr_freeq,(struct q_elt *)da);
				++dr->dr_fcount;
				bp_log("Reclaimed address %s on net %s.\n", 
					inet_ntoa(da->da_addr), dr->dr_iface->name);
			}
		}
	} else {
		/* Use first addr in reclaimq. */
		dn = (struct daddr *) dr->dr_reclaimq.head;
	}
	/*
 	 * Now move to the next entry in the queue and ARP for it.
 	 */
 	da = dn;
	if(da != NULLDADDR){
		ap = arp_lookup(arpType, da->da_addr);
		if(ap != NULLARP) arp_drop(ap);
		res_arp(iface, arpType, da->da_addr, NULLBUF);
	}
	dr->dr_raddr = da;	/* Verify this address next time around. */
	dr->dr_rtime = time(NULL);
}


/*
 * Fill the reclaimation list from the used list.  Take addresses off the head
 * of the used queue until the reclaim queue is full, the used queue is empty,
 * or the address at the head of the used queue has been verified (responded
 * to an ARP) within dr_time_addrretry tocks.
 */
static int
da_fill_reclaim(dr)
struct drange_desc *dr;
{
        struct daddr *da;
        long now;

        now = time(NULL);

        while(dr->dr_rcount < RECLAIM_QUEUE_MAX){
		/* Look at first address on used queue. */
                da = (struct daddr *) dr->dr_usedq.head;
                if(da == NULLDADDR)
			return 0;    /* If used queue is empty, done filling. */
                if(now - da->da_time < dr->dr_time_addrretry)
                        return 0;

		/* If the first element has responded to in ARP recently.
		 * I am done filling.
		 */
		/* Get first address on used queue. */
                da = (struct daddr *) q_dequeue(&dr->dr_usedq);
		/* Mark time addr put in reclaim queue. */
                da->da_time = now;
		/* Put it at end of reclaim queue. */
                q_enqueue(&dr->dr_reclaimq,(struct q_elt *)da);
                ++dr->dr_rcount;
        }
        return 0;
}


/*
 * Address assignment routines.
 */

/*
 * Assign an address.
 */
int
da_assign(iface, hwaddr, ipaddr)
struct iface *iface;	/* -> Pointer to lnet struct of net on which to assign addr. */
char	*hwaddr;	/* -> Pointer to hardware address of hosts. */
int32	*ipaddr;	/* <- Address assigned to host. */
{
	struct drange_desc *dr;	
	struct daddr *da;	
	int status;
	struct arp_type	*at;

	/* Find the network table */
	for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
		if(iface == dr->dr_iface)
			break;	
	}

	if(dr == NULLDRANGE){
		*ipaddr = 0;
		return ERR_NOIPADDRESS;
	}

	/* If this host had an address assigned previously, try to reassign
	 * that. If no previous address, assign a new one.
	 */
	status = da_get_old_addr(dr, hwaddr, &da);
	if(status != 0) 
		status = da_get_free_addr(dr, &da);
	
	/* If I got an address, assign it and link it in to the use list. */
	if(status == 0){
		memcpy(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen);
		*ipaddr = da->da_addr;
		da->da_time = time(NULL);	/* Time assigned */
		q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
		at = &Arp_type[dr->dr_iface->type];
		bp_log("IP addr %s assigned to %s on network %s\n",
		 inet_ntoa(*ipaddr),
		 (*at->format)(bp_ascii, hwaddr), dr->dr_iface->name);
	}

        switch(dr->dr_rstate){
        case R_OFF:
        case R_DONE:
                if(dr->dr_fcount <= dr->dr_thon) 
			da_enter_reclaim(dr);
                /* Fall through. */
        case R_RECLAIM:
                if(dr->dr_fcount <= dr->dr_thcritical) 
			da_enter_critical(dr);
                break;
        /* case R_CRITICAL: is not handled. */
        }
        return status;
}


/*
 * Enter the reclaimation state.
 */
static void
da_enter_reclaim(dr)
struct drange_desc *dr;
{
        char ipa[16], ipb[16];

        iptoa(dr->dr_start, ipa);
        iptoa(dr->dr_end, ipb);

        if(dr->dr_rstate & R_OFF){
                dr->dr_vstate = V_SWAIT;  /* da_enter_reclaim: R_OFF */
                dr->dr_rtime = 0;
        }
        dr->dr_rstate = R_RECLAIM;
        dr->dr_time_addrretry = TIME_ADDRRETRY;         /* Wait a while before retrying addresses. */
}

/*
 * Search for hwaddr on the used list, the reclaimation list, and the free list.
 */
static int
da_get_free_addr(dr, dap)
struct drange_desc *dr;
struct daddr **dap;
{
        *dap = (struct daddr *) q_dequeue(&(dr->dr_freeq));
        if(*dap == NULLDADDR) 
		return ERR_NOIPADDRESS;
        --dr->dr_fcount;

        return 0;
}

/*
 * Search for hwaddr on the used list, the reclaimation list, and the free list.
 */
static int
da_get_old_addr(dr, hwaddr, dap)
struct drange_desc *dr;
char   	*hwaddr;
struct daddr **dap;
{
        struct daddr *da;

	/* Search the used queue */
        for(da = (struct daddr *) dr->dr_usedq.head; da != NULLDADDR; da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        q_remove(&dr->dr_usedq,(struct q_elt *)da);
                        *dap = da;
                        return 0;
                }
        }

	/* Search the relaimq queue */
        for(da = (struct daddr *) dr->dr_reclaimq.head; da != NULLDADDR; 
		da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        /* Here is the address.  I have to be carefull in removing it from
			 * reclaim queue, I may be verifying this address.
                         * If I am, I have to fix up the pointers before removing this
                         * element.
                         */
                        if((dr->dr_rstate & R_OFF) == 0 && dr->dr_vstate == V_VERIFY 
				&& dr->dr_raddr == da){ 
				/* I am verifying this very address.  */
                                /* Start over.  
				 * This should happen very infrequently at most. */
                                dr->dr_vstate = V_SWAIT;  /* get_old_addr */
                        }
                        q_remove(&dr->dr_reclaimq,(struct q_elt *)da);
                        *dap = da;
                        return 0;
                }
        }

	/* Search the free queue */
        for(da = (struct daddr *) dr->dr_freeq.head; da != NULLDADDR; da = da->da_next){
                if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
                        q_remove(&dr->dr_freeq,(struct q_elt *)da);
                        --dr->dr_fcount;
                        *dap = da;
                        return 0;
                }
        }
        return ERR_NOIPADDRESS;
}

#ifdef	notdef
static void
dprint_dr_record(dr)
struct drange_desc *dr;
{
        bp_log("Queue link   x%lx\n", dr->dr_next);
        bp_log("Pointer to network information         x%lx\n", dr->dr_iface);
        bp_log("First IP address in range              x%lx\n", dr->dr_start);
        bp_log("Last IP address in range               x%lx\n", dr->dr_end);
        bp_log("Number of IP addresses in range        %d\n", dr->dr_acount);
        bp_log("Number of IP addresses in free         %d\n", dr->dr_fcount);
        bp_log("Number of IP addresses on reclaimation queue %d\n", 
		dr->dr_rcount);
        bp_log("Threshold for turning on reclaimation  %d\n", dr->dr_thon);
        bp_log("Threshold for critical reclaimation    %d\n", dr->dr_thcritical);
        bp_log("Threshold for turning off reclaimation %d\n", dr->dr_thoff);
        bp_log("Time to wait before retrying addresses %ld\n", 
		dr->dr_time_addrretry);
        bp_log("Length of hardware address             %d\n", dr->dr_hwaddrlen);
        bp_log("Reclaimation state                     %d\n",(int)dr->dr_rstate);
        bp_log("Verification state                     %d\n",(int)dr->dr_vstate);
        bp_log("Time stamp for reclaimation            %ld\n", dr->dr_rtime);
        bp_log("Address being verified                 x%lx\n", dr->dr_raddr);
        bp_log("Pointer to table of addresses          x%lx\n", dr->dr_table);
        bp_log("uesdq x%lx  reclaimq                   x%lx  freeq x%lx\n", dr->dr_usedq, 
		dr->dr_reclaimq, dr->dr_freeq);
}
#endif


/*
 * Enter the critical reclaimation state.
 */
static void
da_enter_critical(dr)
struct drange_desc *dr;
{
        char ipa[16], ipb[16];
	char *ipc;

	ipc = inet_ntoa(dr->dr_start);
	strcpy(ipa, ipc);
	ipc = inet_ntoa(dr->dr_end);
	strcpy(ipb, ipc);

        if((dr->dr_rstate & R_OFF) == 0){
                dr->dr_vstate = V_SWAIT;	/* Enter critical, & R_OFF */
                dr->dr_rtime = 0;
        }
        dr->dr_rstate = R_CRITICAL;
        dr->dr_time_addrretry = 0;      /* Retry addresses as fast as possible. */
}

/*
 * Initialization	
 */
/*
 * Initialize the Dynamic address assignment module.
 */
int
da_init()
{
        q_init(&rtabq);
        return 0;
}

/*
 * Begin dynamic address service for a network.
 */
int
da_serve_net(iface, rstart, rend)
struct iface *iface;		/* Pointer to lnet record. */
int32 rstart;			/* First address in range. */
int32 rend;			/* Last address in range. */
{
	struct drange_desc *dr;	/* Pointer to the range descriptor. */
	struct daddr *da;	/* Pointer to an address structure. */
	int32 rcount;		/* Number of addresses range. */
	time_t now;		/* Current time. */
	int16 i;
	char ipc[16], ipd[16];

        /* Find the network table */
        for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE;
	 dr = dr->dr_next){
                if(iface == dr->dr_iface)
                        break;
        }

	
	if(dr == NULLDRANGE){
		/* If there is no network table, allocate a new one
		 *
 		 * Allocate the memory I need.
 		 */
		dr = (struct drange_desc *) calloc(1, sizeof(*dr));
		if(dr == NULLDRANGE) 
			return E_NOMEM;
	} else if((dr->dr_start != rstart) || (dr->dr_end != rend)) 
		/* If the range is different, create a new range */
		free(dr->dr_table);
	else
		return 0; /* There is no change, return */


	rcount = (rend - rstart) + 1;
	da = (struct daddr *) calloc(1,(sizeof (*da) + iface->iftype->hwalen) * rcount);
	if(da == NULLDADDR) 
		return E_NOMEM;

	/* 
	 * Got the memory, fill in the structures.
	 */
	dr->dr_iface = iface;
	dr->dr_start = rstart;
	dr->dr_end = rend;
	dr->dr_acount = rcount;
	dr->dr_fcount = 0;
	dr->dr_rcount = 0;
	dr->dr_thon = (rcount * THRESH_ON) / 100;
	dr->dr_thcritical = THRESH_CRITICAL;
	dr->dr_thoff = (rcount * THRESH_OFF) / 100;
	dr->dr_time_addrretry = 0;
        dr->dr_hwaddrlen = iface->iftype->hwalen;
	dr->dr_rstate = R_OFF;
	dr->dr_vstate = V_SWAIT;			/* Initialize */
	dr->dr_rtime = 0;
	dr->dr_raddr = NULLDADDR;
	dr->dr_table = da;

	/* 
	 * Fill in the table and link them all onto the used list.
	 */
	time(&now);
	for(i = 0, da = dr->dr_table; i < dr->dr_acount; ++i, da = da_getnext(dr, da)){
		da->da_addr = rstart++;
		da->da_time = 0;		/* Initiallize at 0, only here */
		q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
	}
	/* and set up the timer stuff */
	if(rtabq.head == NULLCHAR){
		set_timer(&da_timer,TIME_RWAIT*1000L);
       		da_timer.func = da_runtask;
	       	da_timer.arg = (void *) 0;
		start_timer(&da_timer);
	}
	q_enqueue(&rtabq,(struct q_elt *)dr);
	da_enter_critical(dr);	/* Start reclaiming some of these addresses. */

	iptoa(dr->dr_start, ipc);
	iptoa(dr->dr_end, ipd);
	bp_log("DynamicIP range: %s - %s\n", ipc, ipd);
	return 0;
}


/*
 * Routines to implement a simple forward linked queue.
 */

/*
 *      q_init()
 *      Initialize simple Q descriptor
 */
static void
q_init(queue)
struct q *queue;
{
        queue->head = 0;
        queue->tail = 0;
}


/*
 *      q_enqueue()
 *              Enqueue an element in a simple Q.
 */
void
q_enqueue(queue, elem)
struct q *queue;
struct q_elt *elem;
{
        struct q_elt *last;

        if(queue->tail != NULLCHAR){  /* If not empty Q... */
                last = (struct q_elt *) queue->tail;
                last->next = elem;
        }
        else
		queue->head = (char *) elem;

        queue->tail = (char *) elem;
        elem->next = NULLQ_ELT;
}


/*
 *      q_dequeue       ()
 *      Pull an element off of the head of a Q.
 */
struct q_elt *
q_dequeue(queue)
struct q *queue;
{
        struct q_elt *elem;

        if(queue->head == NULLCHAR)
		return NULLQ_ELT; /* return NULL when empty Q */
        elem = (struct q_elt *) queue->head;
        queue->head = (char *) elem->next;
        elem->next = NULLQ_ELT;
        if(queue->head == NULLCHAR)
		queue->tail = NULLCHAR;
        return elem;
}


/*
 *      Remove an element from the middle of a queue.  Note that
 *      there is no mutex here, so this shouldn't be used on
 *      critical Qs
 */

static int
q_remove(source_queue, qel)
struct q *source_queue;
struct q_elt *qel;
{
        struct q_elt *prev, *e;

        /*   Case : removing first in Q */

        if(qel == (struct q_elt *) source_queue->head){
                source_queue->head = (char *)qel->next;  /* trying to remove first in queue... */
                if(source_queue->head == NULLCHAR)  	/* nothing left... */
                        source_queue->tail = NULLCHAR; 	/* blank out the Q */
                else if(source_queue->head == source_queue->tail){ /* One thing left */
                        e = (struct q_elt *) source_queue->head; /* As insurance, set it's next to NULL. */
                        e->next = NULLQ_ELT;
                }
                return 0;
        }

        /* find Q element before qel, so that we can link around qel */
        for(prev = (struct q_elt *) source_queue->head; prev->next != qel; prev = prev->next)
                if(prev == NULLQ_ELT)
                        return 1;

        /* Case : Removing last in Q */

        if(qel == (struct q_elt *) source_queue->tail){     /* trying to remove last one in queue... */
                prev->next = NULLQ_ELT;   /* there is a prev elt, since we return on first */
                source_queue->tail = (char *) prev;
                return 0;
        }

        /*  else, removing a queue element in the middle...  */
        prev->next = qel->next;
        return 0;
}

/*
 * Support Routines
 */

static void
iptoa(ipaddr, ipstr)
int32 ipaddr;
char ipstr[16];
{
	char *tmpStr;

	tmpStr = inet_ntoa(ipaddr);
	strcpy(ipstr, tmpStr);
}


#ifdef	notdef
static  void
build_hex_string(fromstr, len, tostr)
char *fromstr; int  len;
char *tostr;
{
	int i;

	for(i=0; i < len; i++){
		sprintf(tostr, "%02x", fromstr[i]);
		tostr++;
		tostr++;
	}
	fromstr[len] = 0;
}
#endif