Internet on FIRE

 * Object locks are represented by &object_lock structures which are in turn a

 * kind of resource. Lockable resources are uniquely determined by resource type

 * multicast address the port is bound to), port number, interface and optional

 * instance ID.

    x->inst == y->inst &&

  debug("(%d:%s:%I:%d:%d) [%s]\n", l->type, (l->iface ? l->iface->name : "?"), l->addr, l->port, l->inst, olock_states[l->state]);

  uint type;		/* ... object type (OBJLOCK_xxx) */

  uint port;		/* ... port number */

  uint inst;		/* ... instance ID */

ospf_send_dbdes(struct ospf_proto *p, struct ospf_neighbor *n, int next)

  if (n->ifa->oa->rt == NULL)

      req->lsa_body = LSA_BODY_DUMMY;

      ospf_send_dbdes(p, n, 1);

	ospf_send_dbdes(p, n, 0);

	ospf_send_dbdes(p, n, 1);

      ospf_send_dbdes(p, n, 1);

	ospf_send_dbdes(p, n, 0);

    uint t = ifa->type;

  lock->addr = ospf_is_v2(p) ? ifa->addr->prefix : IPA_NONE;

  lock->inst = ifa->instance_id;

	if (BIT32_TEST(s->active, id))

      ospf_iface_new(s.oa, a, s.ip);

	ospf_iface_new(s.oa, a, s.ip);

ospf_send_lsack_(struct ospf_proto *p, struct ospf_neighbor *n, int queue)

ospf_send_lsack(struct ospf_proto *p, struct ospf_neighbor *n, int queue)

    ospf_send_lsack_(p, n, queue);

  /* We send smaller LSREQ to prevent multiple LSACKs as answer */

  lsr_max = lsr_max / 4;

  ret->lsa = en->lsa;

  ret->lsa_body = LSA_BODY_DUMMY;

void

ospf_add_flushed_to_lsrt(struct ospf_proto *p, struct ospf_neighbor *n)

{

  struct top_hash_entry *en;

  WALK_SLIST(en, p->lsal)

    if ((en->lsa.age == LSA_MAXAGE) && (en->lsa_body != NULL) &&

	lsa_flooding_allowed(en->lsa_type, en->domain, n->ifa))

      ospf_lsa_lsrt_up(en, n);

}

static void ospf_send_lsupd_to_ifa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_iface *ifa);

 * ospf_flood_lsa - send LSA to the neighbors

 * @p: OSPF protocol instance

ospf_flood_lsa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from)

  /* RFC 2328 13.3 */

	    n->want_lsreq = 1;

    ospf_send_lsupd_to_ifa(p, en, ifa);

ospf_send_lsupd_to_ifa(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_iface *ifa)

  int skip_lsreq = 0;

  n->want_lsreq = 0;

      log(L_WARN "%s: Received LSA from %I with bad checksum: %x %x",

	skip_lsreq = 1;

      /*

       * We only need to remove it from the retransmission list of the neighbor

       * that send us the new LSA. The old LSA is automatically replaced in

       * retransmission lists by the new LSA.

       */

#if 0

       * Old code for removing LSA from all retransmission lists. Must be done

       * before (5b), otherwise it also removes the new entries from (5b).

       */

      struct ospf_iface *ifi;

      struct ospf_neighbor *ni;

      WALK_LIST(ifi, p->iface_list)

	WALK_LIST(ni, ifi->neigh_list)

	if (ni->state > NEIGHBOR_EXSTART)

	  ospf_lsa_lsrt_down(en, ni);

#endif

      int flood_back = ospf_flood_lsa(p, en, n);

      skip_lsreq = 1;

  /* Send direct LSACKs */

  ospf_send_lsack(p, n, ACKL_DIRECT);

  /*

   * In loading state, we should ask for another batch of LSAs. This is only

   * vaguely mentioned in RFC 2328. We send a new LSREQ only if the current

   * LSUPD actually removed some entries from LSA request list (want_lsreq) and

   * did not contain duplicate or early LSAs (skip_lsreq). The first condition

   * prevents endless floods, the second condition helps with flow control.

   */

  if ((n->state == NEIGHBOR_LOADING) && n->want_lsreq && !skip_lsreq)

init_lists(struct ospf_proto *p, struct ospf_neighbor *n)

  n->lsrqh = ospf_top_new(p, n->pool);

  n->lsrth = ospf_top_new(p, n->pool);

}

static void

release_lsrtl(struct ospf_proto *p, struct ospf_neighbor *n)

{

  struct top_hash_entry *ret, *en;

  WALK_SLIST(ret, n->lsrtl)

  {

    en = ospf_hash_find_entry(p->gr, ret);

    if (en)

      en->ret_count--;

  }

reset_lists(struct ospf_proto *p, struct ospf_neighbor *n)

  release_lsrtl(p,n);

  init_lists(p, n);

  init_lists(p, n);

      /* Add MaxAge LSA entries to retransmission list */

      ospf_add_flushed_to_lsrt(p, n);

      /* FIXME: Why is this here ? */

	  reset_lists(p,n);

      reset_lists(p, n);

    reset_lists(p, n);

    reset_lists(p, n);

  s_get(&(n->dbsi));

  release_lsrtl(p, n);

rxmt_timer_hook(timer *t)

  struct ospf_neighbor *n = t->data;

    ospf_send_dbdes(p, n, 1);

    ospf_send_dbdes(p, n, 0);

ackd_timer_hook(timer *t)

  struct ospf_proto *p = n->ifa->oa->po;

  DBG("%s: ACKD timer fired on interface %s for neigh %I\n",

      p->p.name, n->ifa->ifname, n->ip);

  ospf_send_lsack(p, n, ACKL_DELAY);

 * The OSPF protocol is quite complicated and its complex implemenation is split

 * to many files. In |ospf.c|, you will find mainly the interface for

 * communication with the core (e.g., reconfiguration hooks, shutdown and

 * initialisation and so on). File |iface.c| contains the interface state

 * machine and functions for allocation and deallocation of OSPF's interface

 * data structures. Source |neighbor.c| includes the neighbor state machine and

 * functions for election of Designated Router and Backup Designated router. In

 * |packet.c|, you will find various functions for sending and receiving generic

 * OSPF packets. There are also routines for authentication and checksumming.

 * In |hello.c|, there are routines for sending and receiving of hello packets

 * as well as functions for maintaining wait times and the inactivity timer.

 * Files |lsreq.c|, |lsack.c|, |dbdes.c| contain functions for sending and

 * receiving of link-state requests, link-state acknowledgements and database

 * descriptions respectively.  In |lsupd.c|, there are functions for sending and

 * receiving of link-state updates and also the flooding algorithm. Source

 * |topology.c| is a place where routines for searching LSAs in the link-state

 * database, adding and deleting them reside, there also are functions for

 * originating of various types of LSAs (router LSA, net LSA, external LSA).

 * File |rt.c| contains routines for calculating the routing table. |lsalib.c|

 * is a set of various functions for working with the LSAs (endianity

 * conversions, calculation of checksum etc.).

 * One instance of the protocol is able to hold LSA databases for multiple OSPF

 * areas, to exchange routing information between multiple neighbors and to

 * calculate the routing tables. The core structure is &ospf_proto to which

 * multiple &ospf_area and &ospf_iface structures are connected. &ospf_proto is

 * also connected to &top_hash_graph which is a dynamic hashing structure that

 * describes the link-state database. It allows fast search, addition and

 * deletion. Each LSA is kept in two pieces: header and body. Both of them are

 * In OSPFv2 specification, it is implied that there is one IP prefix for each

 * physical network/interface (unless it is an ptp link). But in modern systems,

 * there might be more independent IP prefixes associated with an interface.  To

 * handle this situation, we have one &ospf_iface for each active IP prefix

 * (instead for each active iface); This behaves like virtual interface for the

 * purpose of OSPF.  If we receive packet, we associate it with a proper virtual

 * interface mainly according to its source address.

 * OSPF keeps one socket per &ospf_iface. This allows us (compared to one socket

 * approach) to evade problems with a limit of multicast groups per socket and

 * with sending multicast packets to appropriate interface in a portable way.

 * The socket is associated with underlying physical iface and should not

 * receive packets received on other ifaces (unfortunately, this is not true on

 * BSD). Generally, one packet can be received by more sockets (for example, if

 * there are more &ospf_iface on one physical iface), therefore we explicitly

 * filter received packets according to src/dst IP address and received iface.

 * Vlinks are implemented using particularly degenerate form of &ospf_iface,

 * which has several exceptions: it does not have its iface or socket (it copies

 * these from 'parent' &ospf_iface) and it is present in iface list even when

 * down (it is not freed in ospf_iface_down()).

 * (&ospf_proto->tick). It is responsible for aging and flushing of LSAs in the

 * database, updating topology information in LSAs and for routing table

 * calculation.

 * To every &ospf_iface, we connect one or more &ospf_neighbor's -- a structure

 * containing many timers and queues for building adjacency and for exchange of

 * routing messages.

 * BIRD's OSPF implementation respects RFC2328 in every detail, but some of

 * internal algorithms do differ. The RFC recommends making a snapshot of the

 * link-state database when a new adjacency is forming and sending the database

 * description packets based on the information in this snapshot. The database

 * can be quite large in some networks, so rather we walk through a &slist

 * structure which allows us to continue even if the actual LSA we were working

 * with is deleted. New LSAs are added at the tail of this &slist.

 * We also do not keep a separate OSPF routing table, because the core helps us

 * by being able to recognize when a route is updated to an identical one and it

 * suppresses the update automatically. Due to this, we can flush all the routes

 * we have recalculated and also those we have deleted to the core's routing

 * table and the core will take care of the rest. This simplifies the process

ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac)

  ospf_notify_rt_lsa(oa);

  p->gr = ospf_top_new(p, P->pool);

    ospf_area_add(p, ac);

ospf_schedule_rtcalc(struct ospf_proto *p)

  /* Process LSA DB */

 * @P: OSPF protocol instance

 * @P: OSPF protocol instance

 * @P: current instance of protocol (with old configuration)

      ospf_area_add(p, nac);

  ospf_schedule_rtcalc(p);

	if (net_he && (net_he->lsa.age < LSA_MAXAGE))

  uint num = p->gr->hash_entries;

  uint i, j;

  uint tick;

  list area_list;		/* list of area configs (struct ospf_area_config) */

  list vlink_list;		/* list of configured vlinks (struct ospf_iface_patt) */

struct ospf_area_config

  u32 areaid;

  u32 default_cost;		/* Cost of default route for stub areas

				   (With possible LSA_EXT3_EBIT for NSSA areas) */

  u8 type;			/* Area type (standard, stub, NSSA), represented

				   by option flags (OPT_E, OPT_N) */

  u8 summary;			/* Import summaries to this stub/NSSA area, valid for ABR */

  u8 default_nssa;		/* Generate default NSSA route for NSSA+summary area */

  u8 translator;		/* Translator role, for NSSA ABR */

  u32 transint;			/* Translator stability interval */

  list patt_list;		/* List of iface configs (struct ospf_iface_patt) */

  list net_list;	      	/* List of aggregate networks for that area */

  list enet_list;	      	/* List of aggregate external (NSSA) networks */

  list stubnet_list;		/* List of stub networks added to Router LSA */

struct nbma_node

  ip_addr ip;

  byte eligible;

  byte found; 

struct ospf_iface_patt

{

  struct iface_patt i;

  u32 type;

  u32 stub;

  u32 cost;

  u32 helloint;

  u32 rxmtint;

  u32 pollint;

  u32 waitint;

  u32 deadc;

  u32 deadint;

  u32 inftransdelay;

  list nbma_list;

  u32 priority;

  u32 voa;

  u32 vid;

  int tx_tos;

  int tx_priority;

  u16 tx_length;

  u16 rx_buffer;

#define OSPF_RXBUF_MINSIZE 256	/* Minimal allowed size */

  u8 instance_id;

  u8 autype;			/* Not really used in OSPFv3 */

#define OSPF_AUTH_NONE 0

#define OSPF_AUTH_SIMPLE 1

#define OSPF_AUTH_CRYPT 2

#define OSPF_AUTH_CRYPT_SIZE 16

  u8 strictnbma;

  u8 check_link;

  u8 ecmp_weight;

  u8 link_lsa_suppression;

  u8 real_bcast;		/* Not really used in OSPFv3 */

  u8 ptp_netmask;		/* bool + 2 for unspecified */

  u8 ttl_security;		/* bool + 2 for TX only */

  u8 bfd;

  u8 bsd_secondary;

  list *passwords;

};

struct ospf_proto

{

  struct proto p;

  timer *disp_timer;		/* OSPF proto dispatcher */

  uint tick;

  struct top_graph *gr;		/* LSA graph */

  slist lsal;			/* List of all LSA's */

  int calcrt;			/* Routing table calculation scheduled?

				   0=no, 1=normal, 2=forced reload */

  list iface_list;		/* List of OSPF interfaces (struct ospf_iface) */

  list area_list;		/* List of OSPF areas (struct ospf_area) */

  int areano;			/* Number of area I belong to */

  int padj;			/* Number of neighbors in Exchange or Loading state */

  struct fib rtf;		/* Routing table */

  byte ospf2;			/* OSPF v2 or v3 */

  byte rfc1583;			/* RFC1583 compatibility */

  byte stub_router;		/* Do not forward transit traffic */

  byte merge_external;		/* Should i merge external routes? */

  byte asbr;			/* May i originate any ext/NSSA lsa? */

  byte ecmp;			/* Maximal number of nexthops in ECMP route, or 0 */

  struct ospf_area *backbone;	/* If exists */

  void *lsab;			/* LSA buffer used when originating router LSAs */

  int lsab_size, lsab_used;

  linpool *nhpool;		/* Linpool used for next hops computed in SPF */

  sock *vlink_sk;		/* IP socket used for vlink TX */

  u32 router_id;

  u32 last_vlink_id;		/* Interface IDs for vlinks (starts at 0x80000000) */

};

struct ospf_area

{

  node n;

  u32 areaid;

  struct ospf_area_config *ac;	/* Related area config */

  struct top_hash_entry *rt;	/* My own router LSA */

  struct top_hash_entry *pxr_lsa; /* Originated prefix LSA */

  list cand;			/* List of candidates for RT calc. */

  struct fib net_fib;		/* Networks to advertise or not */

  struct fib enet_fib;		/* External networks for NSSAs */

  u32 options;			/* Optional features */

  u8 update_rt_lsa;		/* Rt lsa origination scheduled? */

  u8 trcap;			/* Transit capability? */

  u8 marked;			/* Used in OSPF reconfigure */

  u8 translate;			/* Translator state (TRANS_*), for NSSA ABR  */

  timer *translator_timer;	/* For NSSA translator switch */

  struct ospf_proto *po;

  struct fib rtr;		/* Routing tables for routers */

};

  list neigh_list;		/* List of neigbours (struct ospf_neighbor) */

struct ospf_neighbor

{

  node n;

  pool *pool;

  struct ospf_iface *ifa;

  u8 state;

  timer *inactim;		/* Inactivity timer */

  u8 imms;			/* I, M, Master/slave received */

  u8 myimms;			/* I, M Master/slave */

  u32 dds;			/* DD Sequence number being sent */

  u32 ddr;			/* last Dat Des packet received */

  u32 rid;			/* Router ID */

  ip_addr ip;			/* IP of it's interface */

  u8 priority;			/* Priority */

  u8 adj;			/* built adjacency? */

  u8 want_lsreq;		/* Set to 1 when lsrql was shortened during LSUPD */

  u32 options;			/* Options received */

  /* Entries dr and bdr store IP addresses in OSPFv2 and router IDs in

     OSPFv3, we use the same type to simplify handling */

  u32 dr;			/* Neigbour's idea of DR */

  u32 bdr;			/* Neigbour's idea of BDR */

  u32 iface_id;			/* ID of Neighbour's iface connected to common network */

  /* Database summary list iterator, controls initial dbdes exchange.

   * Advances in the LSA list as dbdes packets are sent.

   */

  siterator dbsi;		/* iterator of po->lsal */

  /* Link state request list, controls initial LSA exchange.

   * Entries added when received in dbdes packets, removed as sent in lsreq packets.

   */

  slist lsrql;			/* slist of struct top_hash_entry from n->lsrqh */

  struct top_graph *lsrqh;

  /* Link state retransmission list, controls LSA retransmission during flood.

   * Entries added as sent in lsupd packets, removed when received in lsack packets.

   * These entries hold ret_count in appropriate LSA entries.

   */

  slist lsrtl;			/* slist of struct top_hash_entry from n->lsrth */

  struct top_graph *lsrth;

  timer *rxmt_timer;		/* RXMT timer */

  list ackl[2];

#define ACKL_DIRECT 0

#define ACKL_DELAY 1

  timer *ackd_timer;		/* Delayed ack timer */

  struct bfd_request *bfd_req;	/* BFD request, if BFD is used */

  void *ldd_buffer;		/* Last database description packet */

  u32 ldd_bsize;		/* Buffer size for ldd_buffer */

  u32 csn;                      /* Last received crypt seq number (for MD5) */

};

/* OSPF interface types */

#define OSPF_IT_BCAST	0

#define OSPF_IT_NBMA	1

#define OSPF_IT_PTP	2

#define OSPF_IT_PTMP	3

#define OSPF_IT_VLINK	4

#define OSPF_IT_UNDEF	5

/* OSPF interface states */

#define OSPF_IS_DOWN	0	/* Not active */

#define OSPF_IS_LOOP	1	/* Iface with no link */

#define OSPF_IS_WAITING	2	/* Waiting for Wait timer */

#define OSPF_IS_PTP	3	/* PTP operational */

#define OSPF_IS_DROTHER	4	/* I'm on BCAST or NBMA and I'm not DR */

#define OSPF_IS_BACKUP	5	/* I'm BDR */

#define OSPF_IS_DR	6	/* I'm DR */

/* Definitions for interface state machine */

#define ISM_UP		0	/* Interface Up */

#define ISM_WAITF	1	/* Wait timer fired */

#define ISM_BACKS	2	/* Backup seen */

#define ISM_NEICH	3	/* Neighbor change */

#define ISM_LOOP	4	/* Link down */

#define ISM_UNLOOP	5	/* Link up */

#define ISM_DOWN	6	/* Interface down */

/* OSPF neighbor states */

#define NEIGHBOR_DOWN	0

#define NEIGHBOR_ATTEMPT 1

#define NEIGHBOR_INIT	2

#define NEIGHBOR_2WAY	3

#define NEIGHBOR_EXSTART 4

#define NEIGHBOR_EXCHANGE 5

#define NEIGHBOR_LOADING 6

#define NEIGHBOR_FULL	7

/* Definitions for neighbor state machine */

#define INM_HELLOREC	0	/* Hello Received */

#define INM_START	1	/* Neighbor start - for NBMA */

#define INM_2WAYREC	2	/* 2-Way received */

#define INM_NEGDONE	3	/* Negotiation done */

#define INM_EXDONE	4	/* Exchange done */

#define INM_BADLSREQ	5	/* Bad LS Request */

#define INM_LOADDONE	6	/* Load done */

#define INM_ADJOK	7	/* AdjOK? */

#define INM_SEQMIS	8	/* Sequence number mismatch */

#define INM_1WAYREC	9	/* 1-Way */

#define INM_KILLNBR	10	/* Kill Neighbor */

#define INM_INACTTIM	11	/* Inactivity timer */

#define INM_LLDOWN	12	/* Line down */

#define TRANS_OFF	0

#define TRANS_ON	1

#define TRANS_WAIT	2	/* Waiting before the end of translation */

/* Generic option flags */

#define OPT_V6		0x01	/* OSPFv3, LSA relevant for IPv6 routing calculation */

#define OPT_E		0x02	/* Related to AS-external LSAs */

#define OPT_MC		0x04	/* Related to MOSPF, not used and obsolete */

#define OPT_N		0x08	/* Related to NSSA */

#define OPT_P		0x08	/* OSPFv2, flags P and N share position, see NSSA RFC */

#define OPT_EA		0x10	/* OSPFv2, external attributes, not used and obsolete */

#define OPT_R		0x10	/* OSPFv3, originator is active router */

#define OPT_DC		0x20	/* Related to demand circuits, not used */

/* Router-LSA VEB flags are are stored together with links (OSPFv2) or options (OSPFv3) */

#define OPT_RT_B	(0x01 << 24)

#define OPT_RT_E	(0x02 << 24)

#define OPT_RT_V	(0x04 << 24)

#define OPT_RT_NT	(0x10 << 24)

/* Prefix flags, specific for OSPFv3 */

#define OPT_PX_NU	0x01

#define OPT_PX_LA	0x02

#define OPT_PX_P	0x08

#define OPT_PX_DN	0x10

struct ospf_packet

{

  u8 version;

  u8 type;

  u16 length;

  u32 routerid;

  u32 areaid;

  u16 checksum;

  u8 instance_id;		/* See RFC 6549 */

  u8 autype;			/* Undefined for OSPFv3 */

};

static inline uint

#ifdef IPV6

#endif