// SPDX-License-Identifier: GPL-2.0-or-later

/*

 * OSPF version 2  Interface State Machine

 *   From RFC2328 [OSPF Version 2]

 * Copyright (C) 1999, 2000 Toshiaki Takada

 */

#include <zebra.h>

#include "frrevent.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"

DEFINE_HOOK(ospf_ism_change,

      (struct ospf_interface * oi, int state, int oldstate),

      (oi, state, oldstate));

/* elect DR and BDR. Refer to RFC2319 section 9.4 */

static 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;

}

static 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;

  else

    DR(oi).s_addr = 0;

  list_delete(&dr_list);

  return dr;

}

static 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;

  else

    BDR(oi).s_addr = 0;

  list_delete(&bdr_list);

  list_delete(&no_dr_list);

  return bdr;

}

static 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;

}

static 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 != INADDR_ANY)

        /* 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. */

static 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)) {

    nbr = rn->info;

    if (!nbr)

      continue;

    /*

     * Ignore 0.0.0.0 node

     * Is neighbor 2-Way?

     * Ignore myself

     */

    if (nbr->router_id.s_addr != INADDR_ANY

        && nbr->state >= NSM_TwoWay

        && !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;

  /* 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. */

  ospf_elect_bdr(oi, el_list);

  ospf_elect_dr(oi, el_list);

  new_state = ospf_ism_state(oi);

  if (IS_DEBUG_OSPF(ism, ISM_STATUS)) {

    zlog_debug("DR-Election[1st]: Backup %pI4", &BDR(oi));

    zlog_debug("DR-Election[1st]: DR     %pI4", &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);

    if (IS_DEBUG_OSPF(ism, ISM_STATUS)) {

      zlog_debug("DR-Election[2nd]: Backup %pI4", &BDR(oi));

      zlog_debug("DR-Election[2nd]: DR     %pI4", &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;

}

void ospf_hello_timer(struct event *thread)

{

  struct ospf_interface *oi;

  oi = EVENT_ARG(thread);

  oi->t_hello = NULL;

  /* Check if the GR hello-delay is active. */

  if (oi->gr.hello_delay.t_grace_send)

    return;

  if (IS_DEBUG_OSPF(ism, ISM_TIMERS))

    zlog_debug("ISM[%s]: Timer (Hello timer expire)", IF_NAME(oi));

  /* Sending hello packet. */

  ospf_hello_send(oi);

  /* Hello timer set. */

  OSPF_HELLO_TIMER_ON(oi);

}

static void ospf_wait_timer(struct event *thread)

{

  struct ospf_interface *oi;

  oi = EVENT_ARG(thread);

  oi->t_wait = NULL;

  if (IS_DEBUG_OSPF(ism, ISM_TIMERS))

    zlog_debug("ISM[%s]: Timer (Wait timer expire)", IF_NAME(oi));

  OSPF_ISM_EVENT_SCHEDULE(oi, ISM_WaitTimer);

}

/* Hook function called after ospf ISM event is occurred. And vty's

   network command invoke this function after making interface

   structure. */

static 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. */

    EVENT_OFF(oi->t_hello);

    EVENT_OFF(oi->t_wait);

    EVENT_OFF(oi->t_ls_ack);

    EVENT_OFF(oi->gr.hello_delay.t_grace_send);

    break;

  case ISM_Loopback:

    /* In this state, the interface may be looped back and will be

       unavailable for regular data traffic. */

    EVENT_OFF(oi->t_hello);

    EVENT_OFF(oi->t_wait);

    EVENT_OFF(oi->t_ls_ack);

    EVENT_OFF(oi->gr.hello_delay.t_grace_send);

    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_MSEC_ON(oi->t_hello, ospf_hello_timer, 1);

    OSPF_ISM_TIMER_ON(oi->t_wait, ospf_wait_timer,

          OSPF_IF_PARAM(oi, v_wait));

    EVENT_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_MSEC_ON(oi->t_hello, ospf_hello_timer, 1);

    EVENT_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_HELLO_TIMER_ON(oi);

    EVENT_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_HELLO_TIMER_ON(oi);

    EVENT_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_HELLO_TIMER_ON(oi);

    EVENT_OFF(oi->t_wait);

    OSPF_ISM_TIMER_ON(oi->t_ls_ack, ospf_ls_ack_timer,

          oi->v_ls_ack);

    break;

  }

}

static 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;

}

static int ism_loop_ind(struct ospf_interface *oi)

{

  /* call ism_interface_down. */

  /* ret = ism_interface_down (oi); */

  return 0;

}

/* Interface down event handler. */

static int ism_interface_down(struct ospf_interface *oi)

{

  ospf_if_cleanup(oi);

  return 0;

}

static int ism_backup_seen(struct ospf_interface *oi)

{

  return ospf_dr_election(oi);

}

static int ism_wait_timer(struct ospf_interface *oi)

{

  return ospf_dr_election(oi);

}

static int ism_neighbor_change(struct ospf_interface *oi)

{

  return ospf_dr_election(oi);

}

static int ism_ignore(struct ospf_interface *oi)

{

  if (IS_DEBUG_OSPF(ism, ISM_EVENTS))

    zlog_debug("ISM[%s]: ism_ignore called", IF_NAME(oi));

  return 0;

}

/* Interface State Machine */

const struct {

  int (*func)(struct ospf_interface *);

  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  */

  },

};

static const char *const ospf_ism_event_str[] = {

  "NoEvent",  "InterfaceUp", "WaitTimer", "BackupSeen",

  "NeighborChange", "LoopInd",     "UnLoopInd", "InterfaceDown",

};

static 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_debug("ISM[%s]: State change %s -> %s", IF_NAME(oi),

         lookup_msg(ospf_ism_state_msg, oi->state, NULL),

         lookup_msg(ospf_ism_state_msg, state, NULL));

  old_state = oi->state;

  oi->state = state;

  oi->state_change++;

  hook_call(ospf_ism_change, oi, state, old_state);

  /* 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 (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_update_area(oi->area);

  /* Originate network-LSA. */

  if (old_state != ISM_DR && state == ISM_DR)

    ospf_network_lsa_update(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_lsa_unlock(&oi->network_lsa_self);

    oi->network_lsa_self = NULL;

  }

  ospf_opaque_ism_change(oi, old_state);

  /* Check area border status.  */

  ospf_check_abr_status(oi->ospf);

}

/* Execute ISM event process. */

void ospf_ism_event(struct event *thread)

{

  int event;

  int next_state;

  struct ospf_interface *oi;

  oi = EVENT_ARG(thread);

  event = EVENT_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_debug("ISM[%s]: %s (%s)", IF_NAME(oi),

         lookup_msg(ospf_ism_state_msg, oi->state, NULL),

         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);

}