2005-04-07 Paul Jakma <paul.jakma@sun.com>

[mirror_frr.git] / ospfd / ospf_ism.c

/*
 * OSPF version 2  Interface State Machine
 *   From RFC2328 [OSPF Version 2] 
 * Copyright (C) 1999, 2000 Toshiaki Takada
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra 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, or (at your option) any
 * later version.
 *
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GNU Zebra; see the file COPYING.  If not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.
 */

#include <zebra.h>

#include "thread.h"
#include "linklist.h"
#include "prefix.h"
#include "if.h"
#include "table.h"
#include "log.h"

#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
#include "ospfd/ospf_ism.h"
#include "ospfd/ospf_asbr.h"
#include "ospfd/ospf_lsa.h"
#include "ospfd/ospf_lsdb.h"
#include "ospfd/ospf_neighbor.h"
#include "ospfd/ospf_nsm.h"
#include "ospfd/ospf_network.h"
#include "ospfd/ospf_dump.h"
#include "ospfd/ospf_packet.h"
#include "ospfd/ospf_flood.h"
#include "ospfd/ospf_abr.h"
\f
/* elect DR and BDR. Refer to RFC2319 section 9.4 */
struct ospf_neighbor *
ospf_dr_election_sub (struct list *routers)
{
  struct listnode *node;
  struct ospf_neighbor *nbr, *max = NULL;

  /* Choose highest router priority.
     In case of tie, choose highest Router ID. */
  for (ALL_LIST_ELEMENTS_RO (routers, node, nbr))
    {
      if (max == NULL)
	max = nbr;
      else
	{
	  if (max->priority < nbr->priority)
	    max = nbr;
	  else if (max->priority == nbr->priority)
	    if (IPV4_ADDR_CMP (&max->router_id, &nbr->router_id) < 0)
	      max = nbr;
	}
    }

  return max;
}

struct ospf_neighbor *
ospf_elect_dr (struct ospf_interface *oi, struct list *el_list)
{
  struct list *dr_list;
  struct listnode *node;
  struct ospf_neighbor *nbr, *dr = NULL, *bdr = NULL;

  dr_list = list_new ();

  /* Add neighbors to the list. */
  for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
    {
      /* neighbor declared to be DR. */
      if (NBR_IS_DR (nbr))
	listnode_add (dr_list, nbr);

      /* Preserve neighbor BDR. */
      if (IPV4_ADDR_SAME (&BDR (oi), &nbr->address.u.prefix4))
	bdr = nbr;
    }

  /* Elect Designated Router. */
  if (listcount (dr_list) > 0)
    dr = ospf_dr_election_sub (dr_list);
  else
    dr = bdr;

  /* Set DR to interface. */
  if (dr)
    {
      DR (oi) = dr->address.u.prefix4;
      dr->d_router = dr->address.u.prefix4;
    }
  else
      DR (oi).s_addr = 0;

  list_delete (dr_list);

  return dr;
}

struct ospf_neighbor *
ospf_elect_bdr (struct ospf_interface *oi, struct list *el_list)
{
  struct list *bdr_list, *no_dr_list;
  struct listnode *node;
  struct ospf_neighbor *nbr, *bdr = NULL;

  bdr_list = list_new ();
  no_dr_list = list_new ();

  /* Add neighbors to the list. */
  for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
    {
      /* neighbor declared to be DR. */
      if (NBR_IS_DR (nbr))
	continue;

      /* neighbor declared to be BDR. */
      if (NBR_IS_BDR (nbr))
	listnode_add (bdr_list, nbr);

      listnode_add (no_dr_list, nbr);
    }

  /* Elect Backup Designated Router. */
  if (listcount (bdr_list) > 0)
    bdr = ospf_dr_election_sub (bdr_list);
  else
    bdr = ospf_dr_election_sub (no_dr_list);

  /* Set BDR to interface. */
  if (bdr)
    {
      BDR (oi) = bdr->address.u.prefix4;
      bdr->bd_router = bdr->address.u.prefix4;
    }
  else
    BDR (oi).s_addr = 0;

  list_delete (bdr_list);
  list_delete (no_dr_list);

  return bdr;
}

int
ospf_ism_state (struct ospf_interface *oi)
{
  if (IPV4_ADDR_SAME (&DR (oi), &oi->address->u.prefix4))
    return ISM_DR;
  else if (IPV4_ADDR_SAME (&BDR (oi), &oi->address->u.prefix4))
    return ISM_Backup;
  else
    return ISM_DROther;
}

void
ospf_dr_eligible_routers (struct route_table *nbrs, struct list *el_list)
{
  struct route_node *rn;
  struct ospf_neighbor *nbr;

  for (rn = route_top (nbrs); rn; rn = route_next (rn))
    if ((nbr = rn->info) != NULL)
      /* Ignore 0.0.0.0 node*/
      if (nbr->router_id.s_addr != 0)
	/* Is neighbor eligible? */
	if (nbr->priority != 0)
	  /* Is neighbor upper 2-Way? */
	  if (nbr->state >= NSM_TwoWay)
	    listnode_add (el_list, nbr);
}

/* Generate AdjOK? NSM event. */
void
ospf_dr_change (struct ospf *ospf, struct route_table *nbrs)
{
  struct route_node *rn;
  struct ospf_neighbor *nbr;

  for (rn = route_top (nbrs); rn; rn = route_next (rn))
    if ((nbr = rn->info) != NULL)
      /* Ignore 0.0.0.0 node*/
      if (nbr->router_id.s_addr != 0)
	/* Is neighbor upper 2-Way? */
	if (nbr->state >= NSM_TwoWay)
	  /* Ignore myself. */
	  if (!IPV4_ADDR_SAME (&nbr->router_id, &ospf->router_id))
	    OSPF_NSM_EVENT_SCHEDULE (nbr, NSM_AdjOK);
}

int
ospf_dr_election (struct ospf_interface *oi)
{
  struct in_addr old_dr, old_bdr;
  int old_state, new_state;
  struct list *el_list;
  struct ospf_neighbor *dr, *bdr;

  /* backup current values. */
  old_dr = DR (oi);
  old_bdr = BDR (oi);
  old_state = oi->state;

  el_list = list_new ();

  /* List eligible routers. */
  ospf_dr_eligible_routers (oi->nbrs, el_list);

  /* First election of DR and BDR. */
  bdr = ospf_elect_bdr (oi, el_list);
  dr = ospf_elect_dr (oi, el_list);

  new_state = ospf_ism_state (oi);

  zlog_info ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi)));
  zlog_info ("DR-Election[1st]: DR     %s", inet_ntoa (DR (oi)));

  if (new_state != old_state &&
      !(new_state == ISM_DROther && old_state < ISM_DROther))
    {
      ospf_elect_bdr (oi, el_list);
      ospf_elect_dr (oi, el_list); 

      new_state = ospf_ism_state (oi);

      zlog_info ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi)));
      zlog_info ("DR-Election[2nd]: DR     %s", inet_ntoa (DR (oi)));
    }

  list_delete (el_list);

  /* if DR or BDR changes, cause AdjOK? neighbor event. */
  if (!IPV4_ADDR_SAME (&old_dr, &DR (oi)) ||
      !IPV4_ADDR_SAME (&old_bdr, &BDR (oi)))
    ospf_dr_change (oi->ospf, oi->nbrs);

  return new_state;
}

\f
int
ospf_hello_timer (struct thread *thread)
{
  struct ospf_interface *oi;

  oi = THREAD_ARG (thread);
  oi->t_hello = NULL;

  if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
    zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Hello timer expire)",
	  IF_NAME (oi));

  /* Sending hello packet. */
  ospf_hello_send (oi);

  /* Hello timer set. */
  OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
		     OSPF_IF_PARAM (oi, v_hello));

  return 0;
}

int
ospf_wait_timer (struct thread *thread)
{
  struct ospf_interface *oi;

  oi = THREAD_ARG (thread);
  oi->t_wait = NULL;

  if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
    zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Wait timer expire)",
	  IF_NAME (oi));

  OSPF_ISM_EVENT_SCHEDULE (oi, ISM_WaitTimer);

  return 0;
}

/* Hook function called after ospf ISM event is occured. And vty's
   network command invoke this function after making interface
   structure. */
void
ism_timer_set (struct ospf_interface *oi)
{
  switch (oi->state)
    {
    case ISM_Down:
      /* First entry point of ospf interface state machine. In this state
	 interface parameters must be set to initial values, and timers are
	 reset also. */
      OSPF_ISM_TIMER_OFF (oi->t_hello);
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
      break;
    case ISM_Loopback:
      /* In this state, the interface may be looped back and will be
	 unavailable for regular data traffic. */
      OSPF_ISM_TIMER_OFF (oi->t_hello);
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
      break;
    case ISM_Waiting:
      /* The router is trying to determine the identity of DRouter and
	 BDRouter. The router begin to receive and send Hello Packets. */
      /* send first hello immediately */
      OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer, 1);
      OSPF_ISM_TIMER_ON (oi->t_wait, ospf_wait_timer,
			 OSPF_IF_PARAM (oi, v_wait));
      OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
      break;
    case ISM_PointToPoint:
      /* The interface connects to a physical Point-to-point network or
	 virtual link. The router attempts to form an adjacency with
	 neighboring router. Hello packets are also sent. */
      /* send first hello immediately */
      OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer, 1);
      
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
      break;
    case ISM_DROther:
      /* The network type of the interface is broadcast or NBMA network,
	 and the router itself is neither Designated Router nor
	 Backup Designated Router. */
      OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
			 OSPF_IF_PARAM (oi, v_hello));
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
      break;
    case ISM_Backup:
      /* The network type of the interface is broadcast os NBMA network,
	 and the router is Backup Designated Router. */
      OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
			 OSPF_IF_PARAM (oi, v_hello));
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
      break;
    case ISM_DR:
      /* The network type of the interface is broadcast or NBMA network,
	 and the router is Designated Router. */
      OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
			 OSPF_IF_PARAM (oi, v_hello));
      OSPF_ISM_TIMER_OFF (oi->t_wait);
      OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
      break;
    }
}

int
ism_stop (struct ospf_interface *oi)
{
  return 0;
}

int
ism_interface_up (struct ospf_interface *oi)
{
  int next_state = 0;

  /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
     the state transitions to Point-to-Point. */
  if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
      oi->type == OSPF_IFTYPE_POINTOMULTIPOINT ||
      oi->type == OSPF_IFTYPE_VIRTUALLINK)
    next_state = ISM_PointToPoint;
  /* Else if the router is not eligible to DR, the state transitions to
     DROther. */
  else if (PRIORITY (oi) == 0) /* router is eligible? */
    next_state = ISM_DROther;
  else
    /* Otherwise, the state transitions to Waiting. */
    next_state = ISM_Waiting;

  if (oi->type == OSPF_IFTYPE_NBMA)
    ospf_nbr_nbma_if_update (oi->ospf, oi);

  /*  ospf_ism_event (t); */
  return next_state;
}

int
ism_loop_ind (struct ospf_interface *oi)
{
  int ret = 0;

  /* call ism_interface_down. */
  /* ret = ism_interface_down (oi); */

  return ret;
}

/* Interface down event handler. */
int
ism_interface_down (struct ospf_interface *oi)
{
  ospf_if_cleanup (oi);
  return 0;
}


int
ism_backup_seen (struct ospf_interface *oi)
{
  return ospf_dr_election (oi);
}

int
ism_wait_timer (struct ospf_interface *oi)
{
  return ospf_dr_election (oi);
}

int
ism_neighbor_change (struct ospf_interface *oi)
{
  return ospf_dr_election (oi);
}

int
ism_ignore (struct ospf_interface *oi)
{
  if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
    zlog (NULL, LOG_DEBUG, "ISM[%s]: ism_ignore called", IF_NAME (oi));

  return 0;
}

/* Interface State Machine */
struct {
  int (*func) ();
  int next_state;
} ISM [OSPF_ISM_STATE_MAX][OSPF_ISM_EVENT_MAX] =
{
  {
    /* DependUpon: dummy state. */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_DependUpon },    /* InterfaceUp    */
    { ism_ignore,          ISM_DependUpon },    /* WaitTimer      */
    { ism_ignore,          ISM_DependUpon },    /* BackupSeen     */
    { ism_ignore,          ISM_DependUpon },    /* NeighborChange */
    { ism_ignore,          ISM_DependUpon },    /* LoopInd        */
    { ism_ignore,          ISM_DependUpon },    /* UnloopInd      */
    { ism_ignore,          ISM_DependUpon },    /* InterfaceDown  */
  },
  {
    /* Down:*/
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_interface_up,    ISM_DependUpon },    /* InterfaceUp    */
    { ism_ignore,          ISM_Down },          /* WaitTimer      */
    { ism_ignore,          ISM_Down },          /* BackupSeen     */
    { ism_ignore,          ISM_Down },          /* NeighborChange */
    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_Down },          /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* Loopback: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_Loopback },      /* InterfaceUp    */
    { ism_ignore,          ISM_Loopback },      /* WaitTimer      */
    { ism_ignore,          ISM_Loopback },      /* BackupSeen     */
    { ism_ignore,          ISM_Loopback },      /* NeighborChange */
    { ism_ignore,          ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_Down },          /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* Waiting: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_Waiting },       /* InterfaceUp    */
    { ism_wait_timer,	   ISM_DependUpon },    /* WaitTimer      */
    { ism_backup_seen,     ISM_DependUpon },    /* BackupSeen     */
    { ism_ignore,          ISM_Waiting },       /* NeighborChange */
    { ism_loop_ind,	   ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_Waiting },       /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* Point-to-Point: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_PointToPoint },  /* InterfaceUp    */
    { ism_ignore,          ISM_PointToPoint },  /* WaitTimer      */
    { ism_ignore,          ISM_PointToPoint },  /* BackupSeen     */
    { ism_ignore,          ISM_PointToPoint },  /* NeighborChange */
    { ism_loop_ind,	   ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_PointToPoint },  /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* DROther: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_DROther },       /* InterfaceUp    */
    { ism_ignore,          ISM_DROther },       /* WaitTimer      */
    { ism_ignore,          ISM_DROther },       /* BackupSeen     */
    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_DROther },       /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* Backup: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_Backup },        /* InterfaceUp    */
    { ism_ignore,          ISM_Backup },        /* WaitTimer      */
    { ism_ignore,          ISM_Backup },        /* BackupSeen     */
    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_Backup },        /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
  {
    /* DR: */
    { ism_ignore,          ISM_DependUpon },    /* NoEvent        */
    { ism_ignore,          ISM_DR },            /* InterfaceUp    */
    { ism_ignore,          ISM_DR },            /* WaitTimer      */
    { ism_ignore,          ISM_DR },            /* BackupSeen     */
    { ism_neighbor_change, ISM_DependUpon },    /* NeighborChange */
    { ism_loop_ind,        ISM_Loopback },      /* LoopInd        */
    { ism_ignore,          ISM_DR },            /* UnloopInd      */
    { ism_interface_down,  ISM_Down },          /* InterfaceDown  */
  },
};  

const static char *ospf_ism_event_str[] =
{
  "NoEvent",
  "InterfaceUp",
  "WaitTimer",
  "BackupSeen",
  "NeighborChange",
  "LoopInd",
  "UnLoopInd",
  "InterfaceDown",
};

void
ism_change_state (struct ospf_interface *oi, int state)
{
  int old_state;
  struct ospf_lsa *lsa;

  /* Logging change of state. */
  if (IS_DEBUG_OSPF (ism, ISM_STATUS))
    zlog (NULL, LOG_DEBUG, "ISM[%s]: State change %s -> %s", IF_NAME (oi),
	  LOOKUP (ospf_ism_state_msg, oi->state),
	  LOOKUP (ospf_ism_state_msg, state));

  old_state = oi->state;
  oi->state = state;
  oi->state_change++;

  /* Set multicast memberships appropriately for new state. */
  ospf_if_set_multicast(oi);

  if (old_state == ISM_Down || state == ISM_Down)
    ospf_check_abr_status (oi->ospf);

  /* Originate router-LSA. */
  if (oi->area)
    {
      if (state == ISM_Down)
	{
	  if (oi->area->act_ints > 0)
	    oi->area->act_ints--;
	}
      else if (old_state == ISM_Down)
	oi->area->act_ints++;

      /* schedule router-LSA originate. */
      ospf_router_lsa_timer_add (oi->area);
    }

  /* Originate network-LSA. */
  if (old_state != ISM_DR && state == ISM_DR)
    ospf_network_lsa_timer_add (oi);
  else if (old_state == ISM_DR && state != ISM_DR)
    {
      /* Free self originated network LSA. */
      lsa = oi->network_lsa_self;
      if (lsa)
	{
	  ospf_lsa_flush_area (lsa, oi->area);
	  OSPF_TIMER_OFF (oi->t_network_lsa_self);
	}

      ospf_lsa_unlock (oi->network_lsa_self);
      oi->network_lsa_self = NULL;
    }

#ifdef HAVE_OPAQUE_LSA
  ospf_opaque_ism_change (oi, old_state);
#endif /* HAVE_OPAQUE_LSA */

  /* Check area border status.  */
  ospf_check_abr_status (oi->ospf);
}

/* Execute ISM event process. */
int
ospf_ism_event (struct thread *thread)
{
  int event;
  int next_state;
  struct ospf_interface *oi;

  oi = THREAD_ARG (thread);
  event = THREAD_VAL (thread);

  /* Call function. */
  next_state = (*(ISM [oi->state][event].func))(oi);

  if (! next_state)
    next_state = ISM [oi->state][event].next_state;

  if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
    zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi),
	  LOOKUP (ospf_ism_state_msg, oi->state),
	  ospf_ism_event_str[event]);

  /* If state is changed. */
  if (next_state != oi->state)
    ism_change_state (oi, next_state);

  /* Make sure timer is set. */
  ism_timer_set (oi);

  return 0;
}