patch2.4

BCAST Implementation for NS2

-	    return;
 	// Fill in LSA contents
-	hdr = ospf->orig_buffer();
+    hdr = ospf->orig_buffer(length);
 	hdr->ls_opts = SPO_DC;
 	if (!if_area->a_stub)
 	    hdr->ls_opts |= SPO_EXT;
@@ -67,7 +98,6 @@
 	hdr->ls_type = LST_NET;
 	hdr->ls_id = hton32(if_addr);
 	hdr->ls_org = hton32(ospf->my_id());
-	hdr->ls_seqno = hton32(seqno);
 	hdr->ls_length = hton16(length);
 	// Body
 	nethdr = (NetLShdr *) (hdr + 1);
@@ -76,11 +106,10 @@
 	nbr_ids = (rtid_t *) (nethdr + 1);
 	*nbr_ids = hton32(ospf->my_id());
 	while ((np = iter.get_next()) != 0) {
-	    if (np->state() == NBS_FULL)
+	if (np->adv_as_full())
 		*(++nbr_ids) = hton32(np->id());
 	}
-	(void) ospf->lsa_reorig(0, if_area, olsap, hdr, forced);
-    }
+    return(hdr);
 }
 
 /* Constructor for a network-LSA (internal representation).
diff -X exclude_files -Nabur ospfd2.3/src/opqlsa.C ospfd2.4/src/opqlsa.C
--- ospfd2.3/src/opqlsa.C	Mon May 21 10:19:28 2001
+++ ospfd2.4/src/opqlsa.C	Thu Sep 13 16:05:44 2001
@@ -42,7 +42,7 @@
  * the body of the LSA.
  */
 
-void opqLSA::parse(LShdr *)
+void opqLSA::parse(LShdr *hdr)
 
 {
     exception = true;
@@ -51,14 +51,21 @@
     phyint = (lsa_ifp ? lsa_ifp->if_phyint : -1);
     if_addr = (lsa_ifp ? lsa_ifp->if_addr : 0);
     a_id = (lsa_ap ? lsa_ap->id() : 0);
+
+    // Certain Opaque-LSAs are used by OSPF extensions
+    if (lsa_type == LST_LINK_OPQ && ls_id() == (OPQ_T_HLRST<<24))
+        ospf->grace_LSA_rx(this, hdr);
 }
 
-/* Unparse an opaque-LSA. NULL function.
+/* Unparse an opaque-LSA.
  */
 
 void opqLSA::unparse()
 
 {
+    // Certain Opaque-LSAs are used by OSPF extensions
+    if (lsa_type == LST_LINK_OPQ && ls_id() == (OPQ_T_HLRST<<24))
+        ospf->grace_LSA_flushed(this);
 }
 
 /* Build an opaque-LSA. Since the parse function
@@ -112,11 +119,11 @@
     // Estimate size of LSA
     maxlen = sizeof(LShdr) + blen;
     // Get LS Sequence Number
-    seqno = ospf_get_seqno(lsap, maxlen, forced);
+    seqno = ospf_get_seqno(lstype, lsap, forced);
     if (seqno != InvalidLSSeq) {
 	LSA *nlsap;
 	// Fill in LSA header
-        hdr = ospf->orig_buffer();
+        hdr = ospf->orig_buffer(maxlen);
 	hdr->ls_opts = SPO_DC;
 	if (ap && !ap->a_stub)
 	    hdr->ls_opts |= SPO_EXT;
@@ -130,6 +137,7 @@
         hdr->ls_length = hton16(maxlen);
 	if ((nlsap = ospf->lsa_reorig(ip, ap, lsap, hdr, forced)))
 	    lsap = (opqLSA *) nlsap;
+	ospf->free_orig_buffer(hdr);
     }
 
     // Store local copy of body, in case it is overwritten
@@ -159,7 +167,7 @@
     if (!(ip = find_ifc(ifaddr, phyint)))
         return(false);
 
-    opq_orig(ip, 0, LST_LINK_OPQ, lsid, body, blen, adv, 0);
+    opq_orig(ip, ip->area(), LST_LINK_OPQ, lsid, body, blen, adv, 0);
     return(true);
 }
 
diff -X exclude_files -Nabur ospfd2.3/src/opqlsa.h ospfd2.4/src/opqlsa.h
--- ospfd2.3/src/opqlsa.h	Mon May 21 10:19:28 2001
+++ ospfd2.4/src/opqlsa.h	Thu Sep 13 16:05:44 2001
@@ -42,6 +42,7 @@
     virtual void unparse();
     virtual void build(LShdr *hdr);
     virtual void update_in_place(LSA *);
+    SpfNbr *grace_lsa_parse(byte *, int, SPFtime &, int &);
     friend class OSPF;
 };
 
diff -X exclude_files -Nabur ospfd2.3/src/ospf.C ospfd2.4/src/ospf.C
--- ospfd2.3/src/ospf.C	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/ospf.C	Thu Sep 13 16:05:43 2001
@@ -51,7 +51,7 @@
 /* Create an instance of the OSPF protocol.
  */
 
-OSPF::OSPF(uns32 rtid) : myid(rtid)
+OSPF::OSPF(uns32 rtid, SPFtime grace) : myid(rtid)
 
 {
     int i;
@@ -84,10 +84,16 @@
     build_size = 0;
     orig_buff = 0;
     orig_size = 0;
+    orig_buff_in_use = false;
+    n_orig_allocs = 0;
     mon_buff = 0;
     mon_size = 0;
     shutdown_phase = 0;
     countdown = 0;
+    grace_period = 0;
+    restart_reason = HLRST_REASON_UNKNOWN;
+    hitless_prep_phase = 0;
+    phase_duration = 0;
     delete_neighbors = false;
     n_local_flooded = 0;
     ases_pending = 0;
@@ -107,6 +113,14 @@
     full_sched = false;
     ase_sched = false;
     need_remnants = true;
+    start_htl_exit = false;
+    exiting_htl_restart = false;
+    check_htl_termination = false;
+    htl_exit_reason = 0;
+    topology_change = false;
+    start_time = sys_etime;
+    last_topology_change = sys_etime;
+    n_helping = 0;
 
     n_dijkstras = 0;
 
@@ -128,7 +142,21 @@
     default_route = inrttbl->add(0, 0);
     fa_tbl = new FWDtbl;
 
+    // Determine whether we are doing a hitless restart
+    if (!time_less(sys_etime, grace)) {
+        // Normal start
     spflog(CFG_START, 5);
+    }
+    else {
+        // Hitless restart
+        int period;
+	period = time_diff(grace, sys_etime);
+	hlrsttim.start(period);
+	if (spflog(CFG_HTLRST, 5)) {
+	    log(period/Timer::SECOND);
+	    log("seconds");
+	}
+    }
 }
 
 /* Destructor for the OSPF class. Called when shutting
@@ -148,11 +176,13 @@
     // Signal configuration complete
     cfgDone();
 
+    // Cancel pending timers
+    htltim.stop();
+    origtim.stop();
+    dbtim.stop();
+    oflwtim.stop();
+    hlrsttim.stop();
     // Clean out global data structures
-    Timer *tqelt;
-    while ((tqelt = (Timer *) timerq.priq_rmhead())) {
-        ; // Don't delete, as some aren't allocated
-    }
     inrttbl->root.clear();
     fa_tbl->root.clear();
     default_route = 0;
@@ -501,6 +531,9 @@
       case MonReq_OpqNext:
 	opq_stats(msg, conn_id);
 	break;
+      case MonReq_LLLSA:  // Dump Link-local LSA contents
+	lllsa_stats(msg, conn_id);
+	break;
       default:
 	break;
     }
@@ -699,6 +732,11 @@
 {
     INrte *rte;
 
+    // Ignore delete notifications while in hitless restart
+    if (in_hitless_restart())
+        return;
+
+    // Normally store and reinstall into kernel after short delay
     if ((rte = inrttbl->find(net, mask)) && rte->valid()) {
         KrtSync *item;
 	item = new KrtSync(net, mask);
@@ -717,6 +755,18 @@
 {
     INrte *rte;
 
+    // If we're in hitless restart, just store remnant
+    // for later processing
+    if (in_hitless_restart()) {
+        AVLitem *rem;
+	if (!(rem = remnants.find(net, mask))) {
+	    rem = new AVLitem(net, mask);
+	    remnants.add(rem);
+	}
+        return;
+    }
+
+    // Normally delete all remnants from the kernel immediately
     if (!(rte = inrttbl->find(net, mask)) || !rte->valid()) {
         if (spflog(LOG_REMNANT, 5)) {
 	    log(&net, &mask);
@@ -854,4 +904,22 @@
 	sys->halt(0, "Shutdown complete");
 	break;
     }
+}
+
+/* Entry point to initiate a hitless restart.
+ * After preparation is complete, halt will be called.
+ */
+
+void OSPF::hitless_restart(int seconds, byte reason)
+
+{
+    if (hitless_prep_phase > 0)
+        return;
+
+    grace_period = seconds;
+    restart_reason = reason;
+
+    hitless_prep_phase = 1;
+    phase_duration = 0;
+    prepare_hitless_restart();
 }
diff -X exclude_files -Nabur ospfd2.3/src/ospf.h ospfd2.4/src/ospf.h
--- ospfd2.3/src/ospf.h	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/ospf.h	Thu Sep 13 16:05:43 2001
@@ -38,6 +38,20 @@
     virtual void action();
 };
 
+// Hitless Restart Preparation Timer
+
+class HitlessPrepTimer : public Timer {
+  public:
+    virtual void action();
+};
+
+// Hitless Restart Timer
+
+class HitlessRSTTimer : public Timer {
+  public:
+    virtual void action();
+};
+
 // Global timer queue
 extern PriQ timerq;		// Currently pending timers
 
@@ -80,10 +94,18 @@
     uns16 build_size;	// size of build area
     byte *orig_buff;	// Origination staging area
     uns16 orig_size;	// size of staging area
+    bool orig_buff_in_use;// Staging area being used?
+    uns32 n_orig_allocs;// # allocs for staging area
     byte *mon_buff;	// Monitor replay staging area
     int mon_size;	// size of staging area
     int	shutdown_phase;	// Shutting down if > 0
     int	countdown;	// Number of seconds before exit
+    int hitless_prep_phase;// Hitless restart version
+    int phase_duration; // Time in current phase
+    HitlessPrepTimer htltim;
+    int grace_period;	// Length of grace period (current or next)
+    byte restart_reason;// Encoding in lshdr.h
+    TLVbuf tlvbuf;	// Buffer in which grace-LSAs are built
     bool delete_neighbors; // Neighbors being deleted?
     AVLtree phyints;	// Physical interfaces
     AVLtree krtdeletes;	// Deleted, unsynced kernel routing entries
@@ -135,6 +157,19 @@
     bool enabled_msgno[MAXLOG+1];
     AVLtree opq_uploads; // Opaque-LSA requesting connections
 
+    // Hitless restart variables
+    HitlessRSTTimer hlrsttim; // Timing grace period
+    AVLtree remnants;	// Entries installed before restart	
+    bool start_htl_exit;
+    bool exiting_htl_restart;
+    bool check_htl_termination;
+    char *htl_exit_reason;
+    // Helper variables
+    bool topology_change;
+    SPFtime start_time;
+    SPFtime last_topology_change;
+    int n_helping;	// # neighbors being helped
+
     // Monitoring routines
     class MonMsg *get_monbuf(int size);
     void global_stats(class MonMsg *, int conn_id);
@@ -146,6 +181,7 @@
     void lsa_stats(class MonMsg *, int conn_id);
     void rte_stats(class MonMsg *, int conn_id);
     void opq_stats(class MonMsg *, int con_id);
+    void lllsa_stats(class MonMsg *, int conn_id);
 
     // Utility routines
     void clear_config();
@@ -166,8 +202,9 @@
     void phy_attach(int phyint);
     void phy_detach(int phyint, InAddr if_addr);
     void calc_my_addr();
+    LShdr *orig_buffer(int ls_len);
+    void free_orig_buffer(LShdr *);
     inline int mospf_enabled();
-    inline LShdr *orig_buffer();
     inline bool	mc_abr();
     inline bool	shutting_down();
     inline int donotage();
@@ -180,6 +217,7 @@
     LSA	*AddLSA(SpfIfc *,SpfArea *, LSA *current, LShdr *hdr, bool changed);
     void DeleteLSA(LSA *lsap);
     LSA *NextLSA(aid_t, byte, lsid_t, rtid_t);
+    LSA *NextLSA(InAddr, int, aid_t, byte, lsid_t, rtid_t);
     void update_lsdb_xsum(LSA *, bool add);
     Range *GetBestRange(INrte *rte);
     SpfArea *FindArea(aid_t id);
@@ -187,7 +225,7 @@
     inline SpfArea *SummaryArea();	// summary-LSAs from this area used
     void ParseLSA(LSA *lsap, LShdr *hdr);
     void UnParseLSA(LSA *lsap);
-    LShdr *BuildLSA(LSA *lsap);
+    LShdr *BuildLSA(LSA *lsap, LShdr *hdr=0);
     void send_updates();
     bool maxage_free(byte lstype);
     void flush_self_orig(AVLtree *tree);
@@ -212,7 +250,7 @@
     // LSA origination
     int	self_originated(SpfNbr *, LShdr *hdr, LSA *database_copy);
     int	get_lsid(INrte *rte, byte lstype, SpfArea *ap, lsid_t &id);
-    seq_t ospf_get_seqno(LSA *lsap, int ls_len, int forced);
+    seq_t ospf_get_seqno(byte lstype, LSA *lsap, int forced);
     LSA	*lsa_reorig(SpfIfc *,SpfArea *ap, LSA *olsap, LShdr *hdr, int forced);
     void age_prematurely(LSA *);
     void sl_orig(INrte *rte, bool transit_changes_only=false);
@@ -254,6 +292,24 @@
     void mospf_clear_external_source(INrte *rte);
     void mospf_clear_group(InAddr);
 
+    // Hitless restart routines
+    // Preparation
+    void prepare_hitless_restart();
+    void send_grace_lsas();
+    bool verify_grace_acks();
+    void store_hitless_parameters();
+    void next_hitless_phase();
+    // Helper mode
+    void grace_LSA_rx(class opqLSA *, LShdr *);
+    void grace_LSA_flushed(class opqLSA *);
+    void htl_topology_change();
+    // While restarting hitlessly
+    bool in_hitless_restart();
+    void htl_exit_criteria();
+    void htl_check_consistency(SpfArea *, LShdr *);
+    void exit_hitless_restart(char *reason);
+    void htl_reorig(AVLtree *);
+
     // Logging routines
     bool spflog(int, int);
     void log(int);
@@ -273,11 +329,11 @@
     // Version numbers
     enum {
 	vmajor = 2,	// Major version number
-	vminor = 3,	// Minor version number
+	vminor = 4,	// Minor version number
     };
 
     // Entry points into the OSPF code
-    OSPF(uns32 rtid);
+    OSPF(uns32 rtid, SPFtime grace);
     ~OSPF();
     void rxpkt(int phyint, InPkt *pkt, int plen);
     int	timeout();
@@ -295,6 +351,7 @@
     InAddr ip_source(InAddr dest);
     InAddr if_addr(int phyint);
     void shutdown(int seconds);
+    void hitless_restart(int seconds, byte reason);
     void logflush();
     inline rtid_t my_id();
     inline int n_extLSAs();
@@ -354,6 +411,8 @@
     friend class MPath;
     friend class ExRtData;
     friend class opqLSA;
+    friend class HitlessPrepTimer;
+    friend class HitlessRSTTimer;
     friend void lsa_flush(class LSA *);
     friend void ExRtData::clear_config();
     friend SpfNbr *GetNextAdj();
@@ -371,10 +430,6 @@
 inline int OSPF::mospf_enabled()
 {
     return(g_mospf_enabled);
-}
-inline LShdr *OSPF::orig_buffer()
-{
-    return((LShdr *)orig_buff);
 }
 inline bool OSPF::mc_abr()
 {
diff -X exclude_files -Nabur ospfd2.3/src/ospfinc.h ospfd2.4/src/ospfinc.h
--- ospfd2.3/src/ospfinc.h	Mon May 21 10:19:27 2001
+++ ospfd2.4/src/ospfinc.h	Thu Sep 13 16:05:43 2001
@@ -31,6 +31,7 @@
 #include "avl.h"
 #include "lshdr.h"
 #include "spfparam.h"
+#include "tlv.h"
 #include "config.h"
 #include "pat.h"
 #include "rte.h"
diff -X exclude_files -Nabur ospfd2.3/src/restart.C ospfd2.4/src/restart.C
--- ospfd2.3/src/restart.C	Wed Dec 31 19:00:00 1969
+++ ospfd2.4/src/restart.C	Thu Sep 13 16:05:44 2001
@@ -0,0 +1,501 @@
+/*
+ *   OSPFD routing daemon
+ *   Copyright (C) 2001 by John T. Moy
+ *   
+ *   This program is free software; you can redistribute it and/or
+ *   modify it under the terms of the GNU General Public License
+ *   as published by the Free Software Foundation; either version 2
+ *   of the License, or (at your option) any later version.
+ *   
+ *   This program is distributed in the hope that it will be useful,
+ *   but WITHOUT ANY WARRANTY; without e