home *** CD-ROM | disk | FTP | other *** search
/ The Pier Shareware 6 / The_Pier_Shareware_Number_6_(The_Pier_Exchange)_(1995).iso / 024 / psi110g.zip / BOOTPDIP.C < prev    next >
C/C++ Source or Header  |  1994-04-17  |  32KB  |  1,029 lines
  1. /*
  2.  * Center for Information Technology Integration
  3.  *           The University of Michigan
  4.  *                    Ann Arbor
  5.  *
  6.  * Dedicated to the public domain.
  7.  * Send questions to info@citi.umich.edu
  8.  * BOOTP is documented in RFC 951 and RFC 1048
  9.  *
  10.  * Delinted, ANSIfied and reformatted - 5/30/91 P. Karn
  11.  */
  12.   
  13.   
  14.   
  15. /* Dynamic Ip Assignment for a Bootp Server
  16.  * Called when a client request is received and the bootp server doesnt' have a
  17.  * record for it.
  18.  *
  19.  * Design goals:
  20.  *   Assign an IP address
  21.  *   Separation/Identification of IP addresses assigned and not assigned
  22.  *   Time out mechanism to reclaim IP address
  23.  *  Timer, and arp on address with little activity
  24.  *   Reassignment to same machine if possible.
  25.  */
  26. #include <time.h>
  27.   
  28. #include "global.h"
  29. #ifdef BOOTP
  30. #include "arp.h"
  31. #include "iface.h"
  32. #include "mbuf.h"
  33. #include "netuser.h"
  34. #include "pktdrvr.h"
  35. #include "timer.h"
  36. #include "bootpd.h"
  37.   
  38.   
  39. #define E_NOMEM 3101
  40. #define ERR_NOIPADDRESS 3103        /* No IP address available. */
  41.   
  42. #define THRESH_ON            20    /* (%) When to turn on reclaimation of IP addresses. */
  43. #define THRESH_CRITICAL       2    /* (#) */
  44. #define THRESH_OFF           50    /* (%) */
  45.   
  46. #define R_OFF                   0x01    /* Reclaimation is off. */
  47. #define R_RECLAIM               0x02    /* Reclaimation is on. */
  48. #define R_CRITICAL              0x04    /* Reclaimation is operating in critical state. */
  49. #define R_DONE                  0x08    /* Reclaimation is finishing up. */
  50. #define V_SWAIT                 0x10    /* Reclaimation is wait to start verif cycle. */
  51. #define V_VERIFY                0x20    /* Reclaimation is in verification cycle. */
  52.   
  53. #define TIME_RWAIT      (5)     /* Time between running reclm da_task */
  54. #define TIME_SWAIT              (30)    /* Time between cycles of starting address rec */
  55. #define TIME_VWAIT              (10)    /* Time to wait between sending ARPs to verify add
  56. resses. */
  57. #define TIME_ADDRRETRY          (4 * 600)       /* Time to wait before trying to reclaim a
  58. n address. */
  59. #define TIME_ADDRRECLAIM        (900)   /* Time for which an address must be in the reclai
  60. mation */
  61.                                         /* queue before being moved to the free list. */
  62.   
  63. #define RECLAIM_QUEUE_MAX       15      /* Maximum number of addresses in reclaimation queue. */
  64.   
  65.   
  66.   
  67. /*      dynamic_ip.c
  68.  *
  69.  * This file contains code to manage a range of dynamic IP addresses on a network.
  70.  */
  71.   
  72.   
  73.   
  74. /* Queue structures  */
  75. #ifndef __GNUC__
  76. /* was this supposed to accomplish something???  ++bsa */
  77. typedef
  78. #endif
  79. struct  q_elt {
  80.     struct  q_elt *next;
  81. };
  82.   
  83. #define NULLQ_ELT (struct q_elt *) 0
  84.   
  85.   
  86. struct  q {
  87.     char *head;
  88.     char *tail;
  89. };
  90.   
  91. #define NULLQ_P (struct q *) 0
  92.   
  93.   
  94. /* Dynamic IP structures */
  95.   
  96. struct daddr {
  97.     struct daddr    *da_next;       /* Queue link. */
  98.     int32       da_addr;        /* IP address. */
  99.     time_t      da_time;        /* last time this address was answered for. */
  100.     char        da_hwaddr[1];   /* Hardware address, variable length. */
  101. };
  102.   
  103. #define NULLDADDR (struct daddr *) 0
  104.   
  105. struct drange_desc {
  106.     struct drange_desc *dr_next;    /* Queue link. */
  107.     struct iface    *dr_iface;      /* Pointer to network information. */
  108.     struct timer    timer;      /* Timer for reclaiming */
  109.     int32       dr_start;       /* First IP address in range. */
  110.     int32       dr_end;         /* Last IP address in range. */
  111.     int16           dr_acount;      /* Number of IP addresses in range. */
  112.     int16           dr_fcount;      /* Number of IP addresses in free. */
  113.     int16           dr_rcount;      /* Number of IP addresses on reclmation queue  */
  114.     int16           dr_thon;        /* Threshold for turning on reclaimation. */
  115.     int16           dr_thcritical;  /* Threshold for critical reclaimation. */
  116.     int16           dr_thoff;       /* Threshold for turning off reclaimation. */
  117.     int32           dr_time_addrretry;      /* Time to wait before retrying addresses.
  118.                            Varies with state. */
  119.     int16           dr_hwaddrlen;   /* Length of hardware address. */
  120.     unsigned char   dr_rstate;      /* Reclaimation state. */
  121.     unsigned char   dr_vstate;      /* Verification state. */
  122.     time_t          dr_rtime;       /* Time stamp for reclaimation. */
  123.     struct daddr    *dr_raddr;      /* Address being verified. */
  124.     struct daddr    *dr_table;      /* Pointer to table of addresses. */
  125.     struct q        dr_usedq;       /* Pointer to list of used addresses. */
  126.     struct q        dr_reclaimq;    /* Pointer to list of addrs being reclaimed.  */
  127.     struct q        dr_freeq;       /* Pointer to list of free addresses. */
  128. };
  129.   
  130. #define NULLDRANGE (struct drange_desc *) 0
  131.   
  132.   
  133.   
  134.   
  135.   
  136. #define da_structlen(dr)        (sizeof (struct daddr) + dr->dr_hwaddrlen)
  137. #define da_getnext(dr,da)       ((struct daddr *) ((unsigned char *)da + da_structlen(dr)))
  138.   
  139.   
  140. /*
  141.  * Globals.
  142.  */
  143.   
  144. int ifaceToArpMap[] = {
  145.     0,                              /* CL_NONE */
  146.     ARP_ETHER,                          /* CL_ETHERNET */
  147.     ARP_PRONET,                             /* CL_PRONET_10 */
  148.     ARP_IEEE802,                            /* CL_IEEE8025 */
  149.     0,                              /* CL_OMNINET */
  150.     ARP_APPLETALK,                          /* CL_APPLETALK */
  151.     0,                              /* CL_SERIAL_LINE */
  152.     0,                              /* CL_STARLAN */
  153.     ARP_ARCNET,                             /* CL_ARCNET */
  154.     ARP_AX25,                               /* CL_AX25 */
  155.     0,                                      /* CL_KISS */
  156.     0,                                      /* CL_IEEE8023 */
  157.     0,                                      /* CL_FDDI */
  158.     0,                                      /* CL_INTERNET_X25 */
  159.     0,                                      /* CL_LANSTAR */
  160.     0,                                      /* CL_SLFP */
  161.     ARP_NETROM,                             /* CL_NETROM */
  162.     0                                       /* NCLASS */
  163. };
  164.   
  165.   
  166.   
  167. static struct q                 rtabq;
  168. struct timer            da_timer;
  169. char                bp_ascii[128];
  170.   
  171. static void da_runtask __ARGS((void *arg));
  172. struct q_elt *q_dequeue __ARGS((struct q *queue));
  173. static void da_closeup __ARGS((struct drange_desc *dr));
  174. static void dprint_addresses __ARGS((struct drange_desc *dr));
  175. static int q_remove __ARGS((struct q *source_queue,struct q_elt *qel));
  176. static void iptoa __ARGS((int32 ipaddr,char ipstr[16]));
  177. static void da_task __ARGS((void));
  178. static int da_fill_reclaim __ARGS((struct drange_desc *dr));
  179. static void da_do_verify __ARGS((struct drange_desc *dr,int pendtime));
  180. static void da_enter_reclaim __ARGS((struct drange_desc *dr));
  181. static void da_enter_done __ARGS((struct drange_desc *dr));
  182. static void da_enter_off __ARGS((struct drange_desc *dr));
  183. static void q_enqueue __ARGS((struct q  *queue,struct q_elt *elem));
  184. static int da_get_old_addr __ARGS((struct drange_desc *dr,char *hwaddr,struct daddr **dap));
  185. static int da_get_free_addr __ARGS((struct drange_desc *dr,struct daddr **dap));
  186. static void da_enter_critical __ARGS((struct drange_desc *dr));
  187. static void q_init __ARGS((struct q *queue));
  188.   
  189. extern int bp_ReadingCMDFile;
  190.   
  191.   
  192.   
  193. /*
  194.  * Shutdown routines.
  195.  */
  196.   
  197. /*
  198.  * Done serving a network.
  199.  */
  200. int
  201. da_done_net(iface)
  202. struct iface *iface;
  203. {
  204.     struct drange_desc *dr;
  205.   
  206.         /* Find the network table */
  207.     for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  208.         if(iface == dr->dr_iface)
  209.             break;
  210.     }
  211.   
  212.     if(dr == NULLDRANGE){
  213.         bp_log("Range for interface '%s' not found.\n", iface->name);
  214.         return -1;
  215.     }
  216.   
  217.     da_closeup(dr);
  218.     bp_log("Range removed for iface %s\n", iface->name);
  219.     return 0;
  220. }
  221.   
  222.   
  223.   
  224.   
  225. /*
  226.  * Print the status of the da structures.
  227.  */
  228. void
  229. da_status(iface)
  230. struct iface *iface;
  231. {
  232.     struct drange_desc *dr;
  233.   
  234.     /* If no interface was specified, print all the range information */
  235.     if(iface == NULLIF){
  236.         for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE;
  237.             dr = dr->dr_next)
  238.             dprint_addresses(dr);
  239.   
  240.     } else {
  241.         /* Print the specified range's information */
  242.         /* Find the specified interface */
  243.         for(dr = (struct drange_desc *) rtabq.head;
  244.             (dr != NULLDRANGE) && (dr->dr_iface != iface);
  245.             dr = dr->dr_next)
  246.             ;
  247.   
  248.         /* If network not found, return */
  249.         if(dr == NULLDRANGE){
  250.             tprintf("Range for interface '%s' not found.\n", iface->name);
  251.             return;
  252.         }
  253.         /* The range has been found.  Print it. */
  254.         dprint_addresses(dr);
  255.     }
  256. }
  257.   
  258.   
  259.   
  260. /*
  261.  * Finish up service.  Close up on each of the address ranges.
  262.  */
  263. void
  264. da_shut()
  265. {
  266.     struct drange_desc *dr;
  267.   
  268.     stop_timer(&da_timer);
  269.     while((dr = (struct drange_desc *)q_dequeue (&rtabq)) != NULLDRANGE)
  270.         da_closeup(dr);
  271. }
  272.   
  273.   
  274. /*
  275.  * Release resource for a network.
  276.  */
  277. static void
  278. da_closeup(dr)
  279. struct drange_desc *dr;
  280. {
  281.     free(dr->dr_table);         /* Free the address table. */
  282.     q_remove(&rtabq, (struct q_elt *)dr);   /* Dequeue the range descriptor. */
  283.     free(dr);               /* Free the range descriptor. */
  284. }
  285.   
  286.   
  287.   
  288. /* This is only called from a command */
  289. static void
  290. dprint_addresses(dr)
  291. struct drange_desc *dr;
  292. {
  293.     struct daddr *da;
  294.     char ipa[16];
  295.     char ipb[16];
  296.     struct arp_type *at;
  297.   
  298.     at = &Arp_type[dr->dr_iface->type];
  299.   
  300.     iptoa(dr->dr_start, ipa);
  301.     iptoa(dr->dr_end, ipb);
  302.     tprintf("Interface %s range: %s - %s\n", dr->dr_iface->name, ipa, ipb);
  303.   
  304.     da = (struct daddr *) dr->dr_freeq.head;
  305.     tprintf("Free address queue\n");
  306.     while(da){
  307.         iptoa(da->da_addr, ipa);
  308.         tprintf("    %s  last used by %s\n", ipa,(*at->format)(bp_ascii, da->da_hwaddr));
  309.         da = da->da_next;
  310.     }
  311.   
  312.     da = (struct daddr *) dr->dr_usedq.head;
  313.     tprintf("\nUsed address queue\n");
  314.     while(da){
  315.         iptoa(da->da_addr, ipa);
  316.         tprintf("    %s  in use by %s\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  317.         da = da->da_next;
  318.     }
  319.   
  320.     da =(struct daddr *) dr->dr_reclaimq.head;
  321.     tprintf("\nReclaimation address queue\n");
  322.     while(da){
  323.         iptoa(da->da_addr, ipa);
  324.         tprintf("    %s  in use by %s?\n", ipa, (*at->format)(bp_ascii, da->da_hwaddr));
  325.         da = da->da_next;
  326.     }
  327.     tprintf("\n");
  328. }
  329.   
  330.   
  331.   
  332. /*
  333.  * Reclaimation routines.
  334.  */
  335. static void
  336. da_runtask(p)
  337. void *p;
  338. {
  339.     stop_timer(&da_timer);
  340.     da_task();
  341.     set_timer(&da_timer,TIME_RWAIT*1000L);
  342.     start_timer(&da_timer);
  343. }
  344.   
  345. /*
  346.  * Called periodically to run reclaimation.
  347.  */
  348. static void
  349. da_task()
  350. {
  351.     struct drange_desc *dr;
  352.     time_t now;
  353.     int arpHardware, arpPendtime;
  354.   
  355.     now = time(NULL);
  356.   
  357.     for(dr = (struct drange_desc *)rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  358.   
  359.         arpHardware = ifaceToArpMap [dr->dr_iface->type];
  360.         arpPendtime = Arp_type[arpHardware].pendtime;
  361.   
  362.         if(!(dr->dr_rstate & R_OFF)){   /* If doing reclaimation on this range. */
  363.             if(dr->dr_vstate == V_SWAIT){   /* If in wait sub-state. */
  364.                 /* Doing reclaimation on this range and am waiting to
  365.                  * start a cycle of address
  366.                  * verification.  Check if it is time to start the
  367.                  * cycle. */
  368.   
  369.                 if(now - dr->dr_rtime > TIME_SWAIT){
  370.                     /* Start the cycle.  */
  371.                     if(!(dr->dr_rstate & R_DONE))
  372.                         da_fill_reclaim(dr);
  373.   
  374.                     dr->dr_vstate = V_VERIFY; /* verify sub-state. */
  375.                     dr->dr_raddr = NULLDADDR; /* start at beginning */
  376.                 }
  377.             }
  378.             /* If in the verify state (may have just been changed above), and
  379.              * enough time has passed since last lookup, check it and start
  380.              * the next lookup. */
  381.   
  382.             if(dr->dr_vstate == V_VERIFY){
  383.                 if(now - dr->dr_rtime > arpPendtime){
  384.                     da_do_verify(dr, arpPendtime); /* Verify address. */
  385.                     dr->dr_rtime = time(NULL); /* Set time stamp. */
  386.                     if(dr->dr_raddr == NULLDADDR){ /* If at end... */
  387.                         dr->dr_vstate = V_SWAIT; /* Q empty; enter wait sub-state. */
  388.                     }
  389.                 }
  390.             }
  391.   
  392.             /*
  393.              * State transitions.  May have moved some addresses to free list.
  394.              * If so, I may be able to move to a "lower" state.
  395.              */
  396.             switch(dr->dr_rstate){
  397.             /* case R_OFF: Not handled. */
  398.                 case R_CRITICAL:
  399.                 /* Have conditions droped below critical threshhold? */
  400.                     if(dr->dr_fcount > dr->dr_thcritical)
  401.                         da_enter_reclaim(dr);
  402.                 /* Fall through. */
  403.                 case R_RECLAIM:
  404.                 /* Have I reclaimed enough addresses? */
  405.                     if(dr->dr_fcount > dr->dr_thoff)
  406.                         da_enter_done(dr);
  407.                 /* Fall through. */
  408.                 case R_DONE:
  409.                 /* Am I in the done state and have exausted the reclaimation queue? */
  410.                     if((dr->dr_rstate & R_DONE) && dr->dr_reclaimq.head == NULLCHAR)
  411.                         da_enter_off(dr);
  412.                     break;
  413.             }
  414.         }
  415.     }
  416. }
  417.   
  418.   
  419.   
  420.   
  421. /*
  422.  * Enter the DONE state.  Can't get to the done state from the off state.
  423.  */
  424. static void
  425. da_enter_done(dr)
  426. struct drange_desc *dr;
  427. {
  428.     char ipa[16], ipb[16];
  429.   
  430.     iptoa(dr->dr_start, ipa);
  431.     iptoa(dr->dr_end, ipb);
  432.   
  433.     if((dr->dr_rstate & R_OFF) == 0){
  434.         dr->dr_rstate = R_DONE;
  435.         dr->dr_time_addrretry = TIME_ADDRRETRY;     /* Wait a while before retrying addresses. */
  436.     }
  437. }
  438.   
  439.   
  440. /*
  441.  * Enter the OFF state.
  442.  */
  443. static void
  444. da_enter_off(dr)
  445. struct drange_desc *dr;
  446. {
  447.     char ipa[16], ipb[16];
  448.   
  449.     iptoa(dr->dr_start, ipa);
  450.     iptoa(dr->dr_end, ipb);
  451.   
  452.     dr->dr_rstate = R_OFF;
  453. }
  454.   
  455.   
  456. /*
  457.  * Verify addresses.
  458.  * To avoid flodding the network and our address resolution queue I only send
  459.  * out one ARP at a time.  This routine is called periodically to step through
  460.  * the reclaimation queue.  The first step is to check for a responce to the
  461.  * ARP that was sent out previously.  If there is a responce I move the address
  462.  * to the used queue. The next step is to send out an ARP for the next address
  463.  * on the recliamation queue. After a suitable intervel (TIME_VTIME) I'll be
  464.  * called again.
  465.  */
  466. static void
  467. da_do_verify(dr, pendtime)
  468. struct drange_desc *dr;
  469. int pendtime;
  470. {
  471.     struct daddr *da, *dn;
  472.     struct iface *iface;
  473.     long now;
  474.     struct arp_tab *ap;
  475.     int16 arpType;
  476.   
  477.     now = time(NULL);
  478.     iface = dr->dr_iface;
  479.     arpType = ifaceToArpMap[iface->type];
  480.   
  481.     /*
  482.      * If I sent an ARP for an address, check if that ARP has been responded to.
  483.      * If dr_raddr points to an address record, I have previously sent an
  484.      * ARP for that address.  Check the ARP cache for a responce.
  485.      * If dr_raddr is NULL then I am to start at the head of the reclaim queue.
  486.      */
  487.   
  488.     if(dr->dr_raddr != NULLDADDR){
  489.         /* ARP has been sent for dr_raddr.  Check the ARP cache for a responce. */
  490.         da = dr->dr_raddr;
  491.         dn = da->da_next;
  492.   
  493.         ap = arp_lookup(arpType, da->da_addr, iface);
  494.   
  495.         if((ap != NULLARP) && (ap->state == ARP_VALID)){
  496.             /* Host responded to arp.  Place address on used queue.
  497.              * Copy in physical address of host using address to
  498.              * make sure our info is up to date.
  499.              * I could verify that physical address of host
  500.              * responding to  ARP matches the physical address of
  501.              * the host I think owns the address.  If don't match
  502.              * someone is probably using an incorrect address.
  503.              */
  504.   
  505.             q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  506.             --dr->dr_rcount;
  507.             da->da_time = now;      /* Time tested. */
  508.             memcpy(da->da_hwaddr, ap->hw_addr, Arp_type[ap->hardware].hwalen);
  509.             q_enqueue(&dr->dr_usedq, (struct q_elt *)da);
  510.   
  511.         } else {
  512.             /* Host did not respond to ARP.  If addr on reclaim
  513.              * queue long enough, move it to the free queue.
  514.              */
  515.             if(now - da->da_time >= pendtime){
  516.                 q_remove(&dr->dr_reclaimq, (struct q_elt *)da);
  517.                 --dr->dr_rcount;
  518.                 q_enqueue(&dr->dr_freeq,(struct q_elt *)da);
  519.                 ++dr->dr_fcount;
  520.                 bp_log("Reclaimed address %s on net %s.\n",
  521.                 inet_ntoa(da->da_addr), dr->dr_iface->name);
  522.             }
  523.         }
  524.     } else {
  525.         /* Use first addr in reclaimq. */
  526.         dn = (struct daddr *) dr->dr_reclaimq.head;
  527.     }
  528.     /*
  529.      * Now move to the next entry in the queue and ARP for it.
  530.      */
  531.     da = dn;
  532.     if(da != NULLDADDR){
  533.         ap = arp_lookup(arpType, da->da_addr, iface);
  534.         if(ap != NULLARP) arp_drop(ap);
  535.         res_arp(iface, arpType, da->da_addr, NULLBUF);
  536.     }
  537.     dr->dr_raddr = da;  /* Verify this address next time around. */
  538.     dr->dr_rtime = time(NULL);
  539. }
  540.   
  541.   
  542. /*
  543.  * Fill the reclaimation list from the used list.  Take addresses off the head
  544.  * of the used queue until the reclaim queue is full, the used queue is empty,
  545.  * or the address at the head of the used queue has been verified (responded
  546.  * to an ARP) within dr_time_addrretry tocks.
  547.  */
  548. static int
  549. da_fill_reclaim(dr)
  550. struct drange_desc *dr;
  551. {
  552.     struct daddr *da;
  553.     long now;
  554.   
  555.     now = time(NULL);
  556.   
  557.     while(dr->dr_rcount < RECLAIM_QUEUE_MAX){
  558.         /* Look at first address on used queue. */
  559.         da = (struct daddr *) dr->dr_usedq.head;
  560.         if(da == NULLDADDR)
  561.             return 0;    /* If used queue is empty, done filling. */
  562.         if(now - da->da_time < dr->dr_time_addrretry)
  563.             return 0;
  564.   
  565.         /* If the first element has responded to in ARP recently.
  566.          * I am done filling.
  567.          */
  568.         /* Get first address on used queue. */
  569.         da = (struct daddr *) q_dequeue(&dr->dr_usedq);
  570.         /* Mark time addr put in reclaim queue. */
  571.         da->da_time = now;
  572.         /* Put it at end of reclaim queue. */
  573.         q_enqueue(&dr->dr_reclaimq,(struct q_elt *)da);
  574.         ++dr->dr_rcount;
  575.     }
  576.     return 0;
  577. }
  578.   
  579.   
  580. /*
  581.  * Address assignment routines.
  582.  */
  583.   
  584. /*
  585.  * Assign an address.
  586.  */
  587. int
  588. da_assign(iface, hwaddr, ipaddr)
  589. struct iface *iface;    /* -> Pointer to lnet struct of net on which to assign addr. */
  590. char    *hwaddr;    /* -> Pointer to hardware address of hosts. */
  591. int32   *ipaddr;    /* <- Address assigned to host. */
  592. {
  593.     struct drange_desc *dr;
  594.     struct daddr *da;
  595.     int status;
  596.     struct arp_type *at;
  597.   
  598.     /* Find the network table */
  599.     for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE; dr = dr->dr_next){
  600.         if(iface == dr->dr_iface)
  601.             break;
  602.     }
  603.   
  604.     if(dr == NULLDRANGE){
  605.         *ipaddr = 0;
  606.         return ERR_NOIPADDRESS;
  607.     }
  608.   
  609.     /* If this host had an address assigned previously, try to reassign
  610.      * that. If no previous address, assign a new one.
  611.      */
  612.     status = da_get_old_addr(dr, hwaddr, &da);
  613.     if(status != 0)
  614.         status = da_get_free_addr(dr, &da);
  615.   
  616.     /* If I got an address, assign it and link it in to the use list. */
  617.     if(status == 0){
  618.         memcpy(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen);
  619.         *ipaddr = da->da_addr;
  620.         da->da_time = time(NULL);   /* Time assigned */
  621.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  622.         at = &Arp_type[dr->dr_iface->type];
  623.         bp_log("IP addr %s assigned to %s on network %s\n",
  624.         inet_ntoa(*ipaddr),
  625.         (*at->format)(bp_ascii, hwaddr), dr->dr_iface->name);
  626.     }
  627.   
  628.     switch(dr->dr_rstate){
  629.         case R_OFF:
  630.         case R_DONE:
  631.             if(dr->dr_fcount <= dr->dr_thon)
  632.                 da_enter_reclaim(dr);
  633.                 /* Fall through. */
  634.         case R_RECLAIM:
  635.             if(dr->dr_fcount <= dr->dr_thcritical)
  636.                 da_enter_critical(dr);
  637.             break;
  638.         /* case R_CRITICAL: is not handled. */
  639.     }
  640.     return status;
  641. }
  642.   
  643.   
  644. /*
  645.  * Enter the reclaimation state.
  646.  */
  647. static void
  648. da_enter_reclaim(dr)
  649. struct drange_desc *dr;
  650. {
  651.     char ipa[16], ipb[16];
  652.   
  653.     iptoa(dr->dr_start, ipa);
  654.     iptoa(dr->dr_end, ipb);
  655.   
  656.     if(dr->dr_rstate & R_OFF){
  657.         dr->dr_vstate = V_SWAIT;  /* da_enter_reclaim: R_OFF */
  658.         dr->dr_rtime = 0;
  659.     }
  660.     dr->dr_rstate = R_RECLAIM;
  661.     dr->dr_time_addrretry = TIME_ADDRRETRY;         /* Wait a while before retrying addresses. */
  662. }
  663.   
  664. /*
  665.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  666.  */
  667. static int
  668. da_get_free_addr(dr, dap)
  669. struct drange_desc *dr;
  670. struct daddr **dap;
  671. {
  672.     *dap = (struct daddr *) q_dequeue(&(dr->dr_freeq));
  673.     if(*dap == NULLDADDR)
  674.         return ERR_NOIPADDRESS;
  675.     --dr->dr_fcount;
  676.   
  677.     return 0;
  678. }
  679.   
  680. /*
  681.  * Search for hwaddr on the used list, the reclaimation list, and the free list.
  682.  */
  683. static int
  684. da_get_old_addr(dr, hwaddr, dap)
  685. struct drange_desc *dr;
  686. char    *hwaddr;
  687. struct daddr **dap;
  688. {
  689.     struct daddr *da;
  690.   
  691.     /* Search the used queue */
  692.     for(da = (struct daddr *) dr->dr_usedq.head; da != NULLDADDR; da = da->da_next){
  693.         if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  694.             q_remove(&dr->dr_usedq,(struct q_elt *)da);
  695.             *dap = da;
  696.             return 0;
  697.         }
  698.     }
  699.   
  700.     /* Search the relaimq queue */
  701.     for(da = (struct daddr *) dr->dr_reclaimq.head; da != NULLDADDR;
  702.     da = da->da_next){
  703.         if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  704.                         /* Here is the address.  I have to be carefull in removing it from
  705.              * reclaim queue, I may be verifying this address.
  706.                          * If I am, I have to fix up the pointers before removing this
  707.                          * element.
  708.                          */
  709.             if((dr->dr_rstate & R_OFF) == 0 && dr->dr_vstate == V_VERIFY
  710.             && dr->dr_raddr == da){
  711.                 /* I am verifying this very address.  */
  712.                                 /* Start over.
  713.                  * This should happen very infrequently at most. */
  714.                 dr->dr_vstate = V_SWAIT;  /* get_old_addr */
  715.             }
  716.             q_remove(&dr->dr_reclaimq,(struct q_elt *)da);
  717.             *dap = da;
  718.             return 0;
  719.         }
  720.     }
  721.   
  722.     /* Search the free queue */
  723.     for(da = (struct daddr *) dr->dr_freeq.head; da != NULLDADDR; da = da->da_next){
  724.         if(memcmp(da->da_hwaddr, hwaddr, dr->dr_hwaddrlen) == 0){
  725.             q_remove(&dr->dr_freeq,(struct q_elt *)da);
  726.             --dr->dr_fcount;
  727.             *dap = da;
  728.             return 0;
  729.         }
  730.     }
  731.     return ERR_NOIPADDRESS;
  732. }
  733.   
  734. #ifdef  notdef
  735. static void
  736. dprint_dr_record(dr)
  737. struct drange_desc *dr;
  738. {
  739.     bp_log("Queue link   x%lx\n", dr->dr_next);
  740.     bp_log("Pointer to network information         x%lx\n", dr->dr_iface);
  741.     bp_log("First IP address in range              x%lx\n", dr->dr_start);
  742.     bp_log("Last IP address in range               x%lx\n", dr->dr_end);
  743.     bp_log("Number of IP addresses in range        %d\n", dr->dr_acount);
  744.     bp_log("Number of IP addresses in free         %d\n", dr->dr_fcount);
  745.     bp_log("Number of IP addresses on reclaimation queue %d\n",
  746.     dr->dr_rcount);
  747.     bp_log("Threshold for turning on reclaimation  %d\n", dr->dr_thon);
  748.     bp_log("Threshold for critical reclaimation    %d\n", dr->dr_thcritical);
  749.     bp_log("Threshold for turning off reclaimation %d\n", dr->dr_thoff);
  750.     bp_log("Time to wait before retrying addresses %ld\n",
  751.     dr->dr_time_addrretry);
  752.     bp_log("Length of hardware address             %d\n", dr->dr_hwaddrlen);
  753.     bp_log("Reclaimation state                     %d\n",(int)dr->dr_rstate);
  754.     bp_log("Verification state                     %d\n",(int)dr->dr_vstate);
  755.     bp_log("Time stamp for reclaimation            %ld\n", dr->dr_rtime);
  756.     bp_log("Address being verified                 x%lx\n", dr->dr_raddr);
  757.     bp_log("Pointer to table of addresses          x%lx\n", dr->dr_table);
  758.     bp_log("uesdq x%lx  reclaimq                   x%lx  freeq x%lx\n", dr->dr_usedq,
  759.     dr->dr_reclaimq, dr->dr_freeq);
  760. }
  761. #endif
  762.   
  763.   
  764. /*
  765.  * Enter the critical reclaimation state.
  766.  */
  767. static void
  768. da_enter_critical(dr)
  769. struct drange_desc *dr;
  770. {
  771.     char ipa[16], ipb[16];
  772.     char *ipc;
  773.   
  774.     ipc = inet_ntoa(dr->dr_start);
  775.     strcpy(ipa, ipc);
  776.     ipc = inet_ntoa(dr->dr_end);
  777.     strcpy(ipb, ipc);
  778.   
  779.     if((dr->dr_rstate & R_OFF) == 0){
  780.         dr->dr_vstate = V_SWAIT;    /* Enter critical, & R_OFF */
  781.         dr->dr_rtime = 0;
  782.     }
  783.     dr->dr_rstate = R_CRITICAL;
  784.     dr->dr_time_addrretry = 0;      /* Retry addresses as fast as possible. */
  785. }
  786.   
  787. /*
  788.  * Initialization
  789.  */
  790. /*
  791.  * Initialize the Dynamic address assignment module.
  792.  */
  793. int
  794. da_init()
  795. {
  796.     q_init(&rtabq);
  797.     return 0;
  798. }
  799.   
  800. /*
  801.  * Begin dynamic address service for a network.
  802.  */
  803. int
  804. da_serve_net(iface, rstart, rend)
  805. struct iface *iface;        /* Pointer to lnet record. */
  806. int32 rstart;           /* First address in range. */
  807. int32 rend;         /* Last address in range. */
  808. {
  809.     struct drange_desc *dr; /* Pointer to the range descriptor. */
  810.     struct daddr *da;   /* Pointer to an address structure. */
  811.     int32 rcount;       /* Number of addresses range. */
  812.     time_t now;     /* Current time. */
  813.     int16 i;
  814.     char ipc[16], ipd[16];
  815.   
  816.         /* Find the network table */
  817.     for(dr = (struct drange_desc *) rtabq.head; dr != NULLDRANGE;
  818.     dr = dr->dr_next){
  819.         if(iface == dr->dr_iface)
  820.             break;
  821.     }
  822.   
  823.   
  824.     if(dr == NULLDRANGE){
  825.         /* If there is no network table, allocate a new one
  826.          *
  827.          * Allocate the memory I need.
  828.          */
  829.         dr = (struct drange_desc *) calloc(1, sizeof(*dr));
  830.         if(dr == NULLDRANGE)
  831.             return E_NOMEM;
  832.     } else if((dr->dr_start != rstart) || (dr->dr_end != rend))
  833.         /* If the range is different, create a new range */
  834.         free(dr->dr_table);
  835.     else
  836.         return 0; /* There is no change, return */
  837.   
  838.   
  839.     rcount = (rend - rstart) + 1;
  840.     da = (struct daddr *) calloc(1,(sizeof (*da) + iface->iftype->hwalen) * rcount);
  841.     if(da == NULLDADDR)
  842.         return E_NOMEM;
  843.   
  844.     /*
  845.      * Got the memory, fill in the structures.
  846.      */
  847.     dr->dr_iface = iface;
  848.     dr->dr_start = rstart;
  849.     dr->dr_end = rend;
  850.     dr->dr_acount = rcount;
  851.     dr->dr_fcount = 0;
  852.     dr->dr_rcount = 0;
  853.     dr->dr_thon = (rcount * THRESH_ON) / 100;
  854.     dr->dr_thcritical = THRESH_CRITICAL;
  855.     dr->dr_thoff = (rcount * THRESH_OFF) / 100;
  856.     dr->dr_time_addrretry = 0;
  857.     dr->dr_hwaddrlen = iface->iftype->hwalen;
  858.     dr->dr_rstate = R_OFF;
  859.     dr->dr_vstate = V_SWAIT;            /* Initialize */
  860.     dr->dr_rtime = 0;
  861.     dr->dr_raddr = NULLDADDR;
  862.     dr->dr_table = da;
  863.   
  864.     /*
  865.      * Fill in the table and link them all onto the used list.
  866.      */
  867.     time(&now);
  868.     for(i = 0, da = dr->dr_table; i < dr->dr_acount; ++i, da = da_getnext(dr, da)){
  869.         da->da_addr = rstart++;
  870.         da->da_time = 0;        /* Initiallize at 0, only here */
  871.         q_enqueue(&dr->dr_usedq,(struct q_elt *)da);
  872.     }
  873.     /* and set up the timer stuff */
  874.     if(rtabq.head == NULLCHAR){
  875.         set_timer(&da_timer,TIME_RWAIT*1000L);
  876.         da_timer.func = da_runtask;
  877.         da_timer.arg = (void *) 0;
  878.         start_timer(&da_timer);
  879.     }
  880.     q_enqueue(&rtabq,(struct q_elt *)dr);
  881.     da_enter_critical(dr);  /* Start reclaiming some of these addresses. */
  882.   
  883.     iptoa(dr->dr_start, ipc);
  884.     iptoa(dr->dr_end, ipd);
  885.     bp_log("DynamicIP range: %s - %s\n", ipc, ipd);
  886.     return 0;
  887. }
  888.   
  889.   
  890. /*
  891.  * Routines to implement a simple forward linked queue.
  892.  */
  893.   
  894. /*
  895.  *      q_init()
  896.  *      Initialize simple Q descriptor
  897.  */
  898. static void
  899. q_init(queue)
  900. struct q *queue;
  901. {
  902.     queue->head = 0;
  903.     queue->tail = 0;
  904. }
  905.   
  906.   
  907. /*
  908.  *      q_enqueue()
  909.  *              Enqueue an element in a simple Q.
  910.  */
  911. void
  912. q_enqueue(queue, elem)
  913. struct q *queue;
  914. struct q_elt *elem;
  915. {
  916.     struct q_elt *last;
  917.   
  918.     if(queue->tail != NULLCHAR){  /* If not empty Q... */
  919.         last = (struct q_elt *) queue->tail;
  920.         last->next = elem;
  921.     }
  922.     else
  923.         queue->head = (char *) elem;
  924.   
  925.     queue->tail = (char *) elem;
  926.     elem->next = NULLQ_ELT;
  927. }
  928.   
  929.   
  930. /*
  931.  *      q_dequeue       ()
  932.  *      Pull an element off of the head of a Q.
  933.  */
  934. struct q_elt *
  935. q_dequeue(queue)
  936. struct q *queue;
  937. {
  938.     struct q_elt *elem;
  939.   
  940.     if(queue->head == NULLCHAR)
  941.         return NULLQ_ELT; /* return NULL when empty Q */
  942.     elem = (struct q_elt *) queue->head;
  943.     queue->head = (char *) elem->next;
  944.     elem->next = NULLQ_ELT;
  945.     if(queue->head == NULLCHAR)
  946.         queue->tail = NULLCHAR;
  947.     return elem;
  948. }
  949.   
  950.   
  951. /*
  952.  *      Remove an element from the middle of a queue.  Note that
  953.  *      there is no mutex here, so this shouldn't be used on
  954.  *      critical Qs
  955.  */
  956.   
  957. static int
  958. q_remove(source_queue, qel)
  959. struct q *source_queue;
  960. struct q_elt *qel;
  961. {
  962.     struct q_elt *prev, *e;
  963.   
  964.         /*   Case : removing first in Q */
  965.   
  966.     if(qel == (struct q_elt *) source_queue->head){
  967.         source_queue->head = (char *)qel->next;  /* trying to remove first in queue... */
  968.         if(source_queue->head == NULLCHAR)      /* nothing left... */
  969.             source_queue->tail = NULLCHAR;  /* blank out the Q */
  970.         else if(source_queue->head == source_queue->tail){ /* One thing left */
  971.             e = (struct q_elt *) source_queue->head; /* As insurance, set it's next to NULL. */
  972.             e->next = NULLQ_ELT;
  973.         }
  974.         return 0;
  975.     }
  976.   
  977.         /* find Q element before qel, so that we can link around qel */
  978.     for(prev = (struct q_elt *) source_queue->head; prev->next != qel; prev = prev->next)
  979.         if(prev == NULLQ_ELT)
  980.             return 1;
  981.   
  982.         /* Case : Removing last in Q */
  983.   
  984.     if(qel == (struct q_elt *) source_queue->tail){     /* trying to remove last one in queue... */
  985.         prev->next = NULLQ_ELT;   /* there is a prev elt, since we return on first */
  986.         source_queue->tail = (char *) prev;
  987.         return 0;
  988.     }
  989.   
  990.         /*  else, removing a queue element in the middle...  */
  991.     prev->next = qel->next;
  992.     return 0;
  993. }
  994.   
  995. /*
  996.  * Support Routines
  997.  */
  998.   
  999. static void
  1000. iptoa(ipaddr, ipstr)
  1001. int32 ipaddr;
  1002. char ipstr[16];
  1003. {
  1004.     char *tmpStr;
  1005.   
  1006.     tmpStr = inet_ntoa(ipaddr);
  1007.     strcpy(ipstr, tmpStr);
  1008. }
  1009.   
  1010.   
  1011. #ifdef  notdef
  1012. static  void
  1013. build_hex_string(fromstr, len, tostr)
  1014. char *fromstr; int  len;
  1015. char *tostr;
  1016. {
  1017.     int i;
  1018.   
  1019.     for(i=0; i < len; i++){
  1020.         sprintf(tostr, "%02x", fromstr[i]);
  1021.         tostr++;
  1022.         tostr++;
  1023.     }
  1024.     fromstr[len] = 0;
  1025. }
  1026. #endif
  1027.   
  1028. #endif /* BOOTP */
  1029.