path: root/eigrpd/eigrp_topology.c

/*
 * EIGRP Topology Table.
 * Copyright (C) 2013-2016
 * Authors:
 *   Donnie Savage
 *   Jan Janovic
 *   Matej Perina
 *   Peter Orsag
 *   Peter Paluch
 *   Frantisek Gazo
 *   Tomas Hvorkovy
 *   Martin Kontsek
 *   Lukas Koribsky
 *
 * 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 "prefix.h"
#include "table.h"
#include "memory.h"
#include "log.h"
#include "linklist.h"
#include "vty.h"

#include "eigrpd/eigrp_structs.h"
#include "eigrpd/eigrpd.h"
#include "eigrpd/eigrp_interface.h"
#include "eigrpd/eigrp_neighbor.h"
#include "eigrpd/eigrp_packet.h"
#include "eigrpd/eigrp_zebra.h"
#include "eigrpd/eigrp_vty.h"
#include "eigrpd/eigrp_network.h"
#include "eigrpd/eigrp_dump.h"
#include "eigrpd/eigrp_topology.h"
#include "eigrpd/eigrp_fsm.h"
#include "eigrpd/eigrp_memory.h"

static int
eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *, struct eigrp_prefix_entry *);
static void
eigrp_prefix_entry_del(struct eigrp_prefix_entry *);
static int
eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *,
    struct eigrp_neighbor_entry *);

/*
 * asdf;laksdjf;lajsdf;kasdjf;asdjf;
 * asdfaskdjfa;sdkjf;adlskj
 * Returns linkedlist used as topology table
 * cmp - assigned function for comparing topology nodes
 * del - assigned function executed before deleting topology node by list function
 */
struct list *
eigrp_topology_new()
{
  struct list* new = list_new();
  new->cmp = (int
  (*)(void *, void *)) eigrp_prefix_entry_cmp;
  new->del = (void
  (*)(void *)) eigrp_prefix_entry_del;

  return new;
}

/*
 * Topology node comparison
 */

static int
eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *node1,
    struct eigrp_prefix_entry *node2)
{
  if (node1->af == AF_INET)
    {
      if (node2->af == AF_INET)
        {
          if (node1->destination_ipv4->prefix.s_addr
              < node2->destination_ipv4->prefix.s_addr)
            {
              return -1; // if it belong above node2
            }
          else
            {
              if (node1->destination_ipv4->prefix.s_addr
                  > node2->destination_ipv4->prefix.s_addr)
                {
                  return 1; //if it belongs under node2
                }
              else
                {
                  return 0; // same value... ERROR...in case of adding same prefix again
                }
            }
        }
      else
        {
          return 1;
        }
    }
  else
    { // TODO check if the prefix dont exists
      return 1; // add to end
    }
}

/*
 * Topology node delete
 */

static void
eigrp_prefix_entry_del(struct eigrp_prefix_entry *node)
{
  list_delete_all_node(node->entries);
  list_free(node->entries);
}

/*
 * Returns new created toplogy node
 * cmp - assigned function for comparing topology entry
 */

struct eigrp_prefix_entry *
eigrp_prefix_entry_new()
{
  struct eigrp_prefix_entry *new;
  new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY, sizeof(struct eigrp_prefix_entry));
  new->entries = list_new();
  new->rij = list_new();
  new->entries->cmp = (int
  (*)(void *, void *)) eigrp_neighbor_entry_cmp;
  new->distance = new->fdistance = new->rdistance = EIGRP_MAX_METRIC;
  new->destination_ipv4 = NULL;
  new->destination_ipv6 = NULL;

  return new;
}

/*
 * Topology entry comparison
 */

static int
eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *entry1,
    struct eigrp_neighbor_entry *entry2)
{
  if (entry1->distance < entry2->distance) // parameter used in list_add_sort ()
    return -1; // actually set to sort by distance
  if (entry1->distance > entry2->distance)
    return 1;

  return 0;
}

/*
 * Returns new topology entry
 */

struct eigrp_neighbor_entry *
eigrp_neighbor_entry_new()
{
  struct eigrp_neighbor_entry *new;

  new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY,
      sizeof(struct eigrp_neighbor_entry));
  new->reported_distance = EIGRP_MAX_METRIC;
  new->distance = EIGRP_MAX_METRIC;

  return new;
}

/*
 * Freeing topology table list
 */

void
eigrp_topology_free(struct list *list)
{
  list_free(list);
}

/*
 * Deleting all topology nodes in table
 */

void
eigrp_topology_cleanup(struct list *topology)
{
  assert(topology);

  eigrp_topology_delete_all(topology);
}

/*
 * Adding topology node to topology table
 */

void
eigrp_prefix_entry_add(struct list *topology, struct eigrp_prefix_entry *node)
{
  if (listnode_lookup(topology, node) == NULL)
    {
      listnode_add_sort(topology, node);
    }
}

/*
 * Adding topology entry to topology node
 */

void
eigrp_neighbor_entry_add(struct eigrp_prefix_entry *node,
    struct eigrp_neighbor_entry *entry)
{
  if (listnode_lookup(node->entries, entry) == NULL)
    {
      listnode_add_sort(node->entries, entry);
      entry->prefix = node;
    }
}

/*
 * Deleting topology node from topology table
 */

void
eigrp_prefix_entry_delete(struct list *topology,
    struct eigrp_prefix_entry *node)
{
  if (listnode_lookup(topology, node) != NULL)
    {
      list_delete_all_node(node->entries);
      list_free(node->entries);
      list_free(node->rij);
      listnode_delete(topology, node);
      XFREE(MTYPE_EIGRP_PREFIX_ENTRY,node);
    }
}

/*
 * Deleting topology entry from topology node
 */

void
eigrp_neighbor_entry_delete(struct eigrp_prefix_entry *node,
    struct eigrp_neighbor_entry *entry)
{
  if (listnode_lookup(node->entries, entry) != NULL)
    {
      listnode_delete(node->entries, entry);
      XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY,entry);
    }
}

/*
 * Deleting all nodes from topology table
 */

void
eigrp_topology_delete_all(struct list *topology)
{
  list_delete_all_node(topology);
}

/*
 * Return 0 if topology is not empty
 * otherwise return 1
 */

unsigned int
eigrp_topology_table_isempty(struct list *topology)
{
  if (topology->count)
    return 1;
  else
    return 0;
}

struct eigrp_prefix_entry *
eigrp_topology_table_lookup_ipv4(struct list *topology_table,
    struct prefix_ipv4 * address)
{
  struct eigrp_prefix_entry *data;
  struct listnode *node;
  for (ALL_LIST_ELEMENTS_RO(topology_table, node, data))
    {

      if ((data->af == AF_INET)
          && (data->destination_ipv4->prefix.s_addr == address->prefix.s_addr)
          && (data->destination_ipv4->prefixlen == address->prefixlen))
        return data;
    }

  return NULL;
}
/* TODO
 struct eigrp_prefix_entry *
 eigrp_topology_table_lookup_ipv6 (struct list *topology_table,
 struct prefix_ipv6 * address)
 {
 struct eigrp_prefix_entry *data;
 struct listnode *node, *nnode;
 for (ALL_LIST_ELEMENTS (topology_table, node, nnode, data))
 {

 if (comparison)
 return data;
 }

 return NULL;
 }
 */
struct list *
eigrp_topology_get_successor(struct eigrp_prefix_entry *table_node)
{
  struct list *successors = list_new();
  ;
  struct eigrp_neighbor_entry *data;
  struct listnode *node1, *node2;
  for (ALL_LIST_ELEMENTS(table_node->entries, node1, node2, data))
    {
      if (data->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)
        {
          listnode_add(successors, data);
        }
    }

  return successors;
}

/*extern struct eigrp_neighbor_entry *
 eigrp_topology_get_fsuccessor (struct eigrp_prefix_entry *table_node)
 {
 struct eigrp_neighbor_entry *data;
 struct listnode *node, *nnode;
 for (ALL_LIST_ELEMENTS (table_node->entries, node, nnode, data))
 {
 if ((data->flags & EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG) == 1)
 {
 return data;
 }
 }

 return NULL;
 }*/

struct eigrp_neighbor_entry *
eigrp_prefix_entry_lookup(struct list *entries, struct eigrp_neighbor *nbr)
{
  struct eigrp_neighbor_entry *data;
  struct listnode *node, *nnode;
  for (ALL_LIST_ELEMENTS(entries, node, nnode, data))
    {
      if (data->adv_router == nbr)
        {
          return data;
        }
    }

  return NULL;
}

/* Lookup all prefixes from specified neighbor */
struct list *
eigrp_neighbor_prefixes_lookup(struct eigrp *eigrp, struct eigrp_neighbor *nbr)
{
  struct listnode *node1, *node11, *node2, *node22;
  struct eigrp_prefix_entry *prefix;
  struct eigrp_neighbor_entry *entry;

  /* create new empty list for prefixes storage */
  struct list *prefixes = list_new();

  /* iterate over all prefixes in topology table */
  for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix))
    {
	  /* iterate over all neighbor entry in prefix */
      for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry))
        {
    	  /* if entry is from specified neighbor, add to list */
          if (entry->adv_router == nbr)
            {
        	  listnode_add(prefixes, prefix);
            }
        }
    }

  /* return list of prefixes from specified neighbor */
  return prefixes;
}

int
eigrp_topology_update_distance(struct eigrp_fsm_action_message *msg)
{
  struct eigrp *eigrp = msg->eigrp;
  struct eigrp_prefix_entry *prefix = msg->prefix;
  struct eigrp_neighbor_entry *entry = msg->entry;
  int change = 0;
  assert(entry);

  struct TLV_IPv4_External_type *ext_data = NULL;
  struct TLV_IPv4_Internal_type *int_data = NULL;
  if (msg->data_type == EIGRP_TLV_IPv4_INT)
    {
      int_data = msg->data.ipv4_int_type;
      if (eigrp_metrics_is_same(&int_data->metric,&entry->reported_metric))
        {
          return 0; // No change
        }
      change =
          entry->reported_distance
              < eigrp_calculate_metrics(eigrp, &int_data->metric) ? 1 :
          entry->reported_distance
              > eigrp_calculate_metrics(eigrp, &int_data->metric) ? 2 : 3; // Increase : Decrease : No change
      entry->reported_metric = int_data->metric;
      entry->reported_distance = eigrp_calculate_metrics(eigrp,
          &int_data->metric);
      entry->distance = eigrp_calculate_total_metrics(eigrp, entry);
    }
  else
    {
      ext_data = msg->data.ipv4_ext_data;
      if (eigrp_metrics_is_same (&ext_data->metric, &entry->reported_metric))
	return 0;
    }
  /*
   * Move to correct position in list according to new distance
   */
  listnode_delete(prefix->entries, entry);
  listnode_add_sort(prefix->entries, entry);

  return change;
}

void
eigrp_topology_update_all_node_flags(struct eigrp *eigrp)
{
  struct list *table = eigrp->topology_table;
  struct eigrp_prefix_entry *data;
  struct listnode *node, *nnode;
  for (ALL_LIST_ELEMENTS(table, node, nnode, data))
    {
      eigrp_topology_update_node_flags(data);
    }
}

void
eigrp_topology_update_node_flags(struct eigrp_prefix_entry *dest)
{
  struct listnode *node;
  struct eigrp_neighbor_entry *entry;
  struct eigrp * eigrp = eigrp_lookup();

  for (ALL_LIST_ELEMENTS_RO(dest->entries, node, entry))
    {
      if ((entry->distance <= (u_int64_t)(dest->distance*eigrp->variance)) && entry->distance != EIGRP_MAX_METRIC) // is successor
        {
          entry->flags |= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG;
          entry->flags &= 0xfd; // 1111 1101 set fs flag to zero
        }
      else if (entry->reported_distance < dest->fdistance) // is feasible successor
        {
          entry->flags |= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG;
          entry->flags &= 0xfe; // 1111 1110 set successor flag to zero
        }
      else
        {
          entry->flags &= 0xfc; // 1111 1100 set successor and fs flag to zero
        }
    }
}

void
eigrp_update_routing_table(struct eigrp_prefix_entry * prefix)
{
  struct listnode *node;
  struct eigrp_neighbor_entry *entry;

  for (ALL_LIST_ELEMENTS_RO(prefix->entries, node, entry))
    {
      if (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)
        {
          if (!(entry->flags & EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG))
            {
              eigrp_zebra_route_add(prefix->destination_ipv4, entry);
              entry->flags += EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG;
            }
        }
      else if (entry->flags & EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG)
        {
          eigrp_zebra_route_delete(prefix->destination_ipv4, entry);
          entry->flags -= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG;
        }
    }
}

void
eigrp_topology_neighbor_down(struct eigrp *eigrp, struct eigrp_neighbor * nbr)
{
  struct listnode *node1, *node11, *node2, *node22;
  struct eigrp_prefix_entry *prefix;
  struct eigrp_neighbor_entry *entry;

  for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix))
    {
      for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry))
        {
          if (entry->adv_router == nbr)
            {
              struct eigrp_fsm_action_message *msg;
              msg = XCALLOC(MTYPE_EIGRP_FSM_MSG,
                  sizeof(struct eigrp_fsm_action_message));
              struct TLV_IPv4_Internal_type * tlv = eigrp_IPv4_InternalTLV_new();
              tlv->metric.delay = EIGRP_MAX_METRIC;
              msg->packet_type = EIGRP_OPC_UPDATE;
              msg->eigrp = eigrp;
              msg->data_type = EIGRP_TLV_IPv4_INT;
              msg->adv_router = nbr;
              msg->data.ipv4_int_type = tlv;
              msg->entry = entry;
              msg->prefix = prefix;
              int event = eigrp_get_fsm_event(msg);
              eigrp_fsm_event(msg, event);
            }
        }
    }

  eigrp_query_send_all(eigrp);
  eigrp_update_send_all(eigrp,nbr->ei);

}

void
eigrp_update_topology_table_prefix(struct list * table, struct eigrp_prefix_entry * prefix)
{
	struct listnode *node1, *node2;

	  struct eigrp_neighbor_entry *entry;
	      for (ALL_LIST_ELEMENTS(prefix->entries, node1, node2, entry))
	        {
	    	  if(entry->distance == EIGRP_MAX_METRIC)
	    	  {
	    		  eigrp_neighbor_entry_delete(prefix,entry);
	    	  }
	        }
	      if(prefix->distance == EIGRP_MAX_METRIC && prefix->nt != EIGRP_TOPOLOGY_TYPE_CONNECTED)
	      {
	    	  eigrp_prefix_entry_delete(table,prefix);
	      }
}
/*int
 eigrp_topology_get_successor_count (struct eigrp_prefix_entry *prefix)
 {

 struct listnode *node;
 struct eigrp_neighbor_entry *entry;

 int count = 0;

 for (ALL_LIST_ELEMENTS_RO (prefix->entries,node,entry))
 {
 if ((entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) == EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG)
 {
 count ++;
 }
 }

 return count;
 }
 */