2 * EIGRP Topology Table.
3 * Copyright (C) 2013-2016
15 * This file is part of GNU Zebra.
17 * GNU Zebra is free software; you can redistribute it and/or modify it
18 * under the terms of the GNU General Public License as published by the
19 * Free Software Foundation; either version 2, or (at your option) any
22 * GNU Zebra is distributed in the hope that it will be useful, but
23 * WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25 * General Public License for more details.
27 * You should have received a copy of the GNU General Public License along
28 * with this program; see the file COPYING; if not, write to the Free Software
29 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
41 #include "eigrpd/eigrp_structs.h"
42 #include "eigrpd/eigrpd.h"
43 #include "eigrpd/eigrp_interface.h"
44 #include "eigrpd/eigrp_neighbor.h"
45 #include "eigrpd/eigrp_packet.h"
46 #include "eigrpd/eigrp_zebra.h"
47 #include "eigrpd/eigrp_vty.h"
48 #include "eigrpd/eigrp_network.h"
49 #include "eigrpd/eigrp_dump.h"
50 #include "eigrpd/eigrp_topology.h"
51 #include "eigrpd/eigrp_fsm.h"
52 #include "eigrpd/eigrp_memory.h"
54 static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry
*, struct eigrp_prefix_entry
*);
55 static void eigrp_prefix_entry_del(struct eigrp_prefix_entry
*);
56 static int eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry
*,
57 struct eigrp_neighbor_entry
*);
60 * Returns linkedlist used as topology table
61 * cmp - assigned function for comparing topology nodes
62 * del - assigned function executed before deleting topology node by list function
67 struct list
* new = list_new();
69 (*)(void *, void *)) eigrp_prefix_entry_cmp
;
71 (*)(void *)) eigrp_prefix_entry_del
;
77 * Topology node comparison
81 eigrp_prefix_entry_cmp(struct eigrp_prefix_entry
*node1
,
82 struct eigrp_prefix_entry
*node2
)
84 if (node1
->af
== AF_INET
)
86 if (node2
->af
== AF_INET
)
88 if (node1
->destination_ipv4
->prefix
.s_addr
89 < node2
->destination_ipv4
->prefix
.s_addr
)
91 return -1; // if it belong above node2
95 if (node1
->destination_ipv4
->prefix
.s_addr
96 > node2
->destination_ipv4
->prefix
.s_addr
)
98 return 1; //if it belongs under node2
102 return 0; // same value... ERROR...in case of adding same prefix again
112 { // TODO check if the prefix dont exists
113 return 1; // add to end
118 * Topology node delete
122 eigrp_prefix_entry_del(struct eigrp_prefix_entry
*node
)
124 list_delete_all_node(node
->entries
);
125 list_free(node
->entries
);
129 * Returns new created toplogy node
130 * cmp - assigned function for comparing topology entry
132 struct eigrp_prefix_entry
*
133 eigrp_prefix_entry_new()
135 struct eigrp_prefix_entry
*new;
136 new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY
, sizeof(struct eigrp_prefix_entry
));
137 new->entries
= list_new();
138 new->rij
= list_new();
139 new->entries
->cmp
= (int (*)(void *, void *))eigrp_neighbor_entry_cmp
;
140 new->distance
= new->fdistance
= new->rdistance
= EIGRP_MAX_METRIC
;
141 new->destination_ipv4
= NULL
;
142 new->destination_ipv6
= NULL
;
148 * Topology entry comparison
151 eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry
*entry1
,
152 struct eigrp_neighbor_entry
*entry2
)
154 if (entry1
->distance
< entry2
->distance
) // parameter used in list_add_sort ()
155 return -1; // actually set to sort by distance
156 if (entry1
->distance
> entry2
->distance
)
163 * Returns new topology entry
166 struct eigrp_neighbor_entry
*
167 eigrp_neighbor_entry_new()
169 struct eigrp_neighbor_entry
*new;
171 new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY
,
172 sizeof(struct eigrp_neighbor_entry
));
173 new->reported_distance
= EIGRP_MAX_METRIC
;
174 new->distance
= EIGRP_MAX_METRIC
;
180 * Freeing topology table list
183 eigrp_topology_free(struct list
*list
)
189 * Deleting all topology nodes in table
192 eigrp_topology_cleanup(struct list
*topology
)
196 eigrp_topology_delete_all(topology
);
200 * Adding topology node to topology table
203 eigrp_prefix_entry_add(struct list
*topology
, struct eigrp_prefix_entry
*node
)
205 if (listnode_lookup(topology
, node
) == NULL
)
207 listnode_add_sort(topology
, node
);
212 * Adding topology entry to topology node
215 eigrp_neighbor_entry_add(struct eigrp_prefix_entry
*node
,
216 struct eigrp_neighbor_entry
*entry
)
218 struct list
*l
= list_new ();
220 listnode_add (l
, entry
);
222 if (listnode_lookup (node
->entries
, entry
) == NULL
)
224 listnode_add_sort (node
->entries
, entry
);
225 entry
->prefix
= node
;
227 eigrp_zebra_route_add (node
->destination_ipv4
, l
);
234 * Deleting topology node from topology table
237 eigrp_prefix_entry_delete(struct list
*topology
,
238 struct eigrp_prefix_entry
*node
)
240 struct eigrp
*eigrp
= eigrp_lookup ();
243 * Emergency removal of the node from this list.
246 listnode_delete (eigrp
->topology_changes_internalIPV4
, node
);
248 if (listnode_lookup (topology
, node
) != NULL
)
250 list_delete_all_node (node
->entries
);
251 list_free (node
->entries
);
252 list_free (node
->rij
);
253 listnode_delete (topology
, node
);
254 eigrp_zebra_route_delete (node
->destination_ipv4
);
255 XFREE (MTYPE_EIGRP_PREFIX_ENTRY
,node
);
260 * Deleting topology entry from topology node
263 eigrp_neighbor_entry_delete(struct eigrp_prefix_entry
*node
,
264 struct eigrp_neighbor_entry
*entry
)
266 if (listnode_lookup(node
->entries
, entry
) != NULL
)
268 listnode_delete(node
->entries
, entry
);
269 eigrp_zebra_route_delete (node
->destination_ipv4
);
270 XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY
,entry
);
275 * Deleting all nodes from topology table
278 eigrp_topology_delete_all(struct list
*topology
)
280 list_delete_all_node(topology
);
284 * Return 0 if topology is not empty
288 eigrp_topology_table_isempty(struct list
*topology
)
296 struct eigrp_prefix_entry
*
297 eigrp_topology_table_lookup_ipv4(struct list
*topology_table
,
298 struct prefix_ipv4
* address
)
300 struct eigrp_prefix_entry
*data
;
301 struct listnode
*node
;
302 for (ALL_LIST_ELEMENTS_RO(topology_table
, node
, data
))
304 if ((data
->af
== AF_INET
)
305 && (data
->destination_ipv4
->prefix
.s_addr
== address
->prefix
.s_addr
)
306 && (data
->destination_ipv4
->prefixlen
== address
->prefixlen
))
314 * For a future optimization, put the successor list into it's
315 * own separate list from the full list?
317 * That way we can clean up all the list_new and list_delete's
318 * that we are doing. DBS
321 eigrp_topology_get_successor(struct eigrp_prefix_entry
*table_node
)
323 struct list
*successors
= list_new();
324 struct eigrp_neighbor_entry
*data
;
325 struct listnode
*node1
, *node2
;
327 for (ALL_LIST_ELEMENTS(table_node
->entries
, node1
, node2
, data
))
329 if (data
->flags
& EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
)
331 listnode_add(successors
, data
);
336 * If we have no successors return NULL
338 if (!successors
->count
)
340 list_delete(successors
);
348 eigrp_topology_get_successor_max(struct eigrp_prefix_entry
*table_node
,
349 unsigned int maxpaths
)
351 struct list
*successors
= eigrp_topology_get_successor(table_node
);
353 if (successors
&& successors
->count
> maxpaths
)
357 struct listnode
*node
= listtail(successors
);
359 list_delete_node(successors
, node
);
361 } while (successors
->count
> maxpaths
);
367 struct eigrp_neighbor_entry
*
368 eigrp_prefix_entry_lookup(struct list
*entries
, struct eigrp_neighbor
*nbr
)
370 struct eigrp_neighbor_entry
*data
;
371 struct listnode
*node
, *nnode
;
372 for (ALL_LIST_ELEMENTS(entries
, node
, nnode
, data
))
374 if (data
->adv_router
== nbr
)
383 /* Lookup all prefixes from specified neighbor */
385 eigrp_neighbor_prefixes_lookup(struct eigrp
*eigrp
, struct eigrp_neighbor
*nbr
)
387 struct listnode
*node1
, *node11
, *node2
, *node22
;
388 struct eigrp_prefix_entry
*prefix
;
389 struct eigrp_neighbor_entry
*entry
;
391 /* create new empty list for prefixes storage */
392 struct list
*prefixes
= list_new();
394 /* iterate over all prefixes in topology table */
395 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
))
397 /* iterate over all neighbor entry in prefix */
398 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
))
400 /* if entry is from specified neighbor, add to list */
401 if (entry
->adv_router
== nbr
)
403 listnode_add(prefixes
, prefix
);
408 /* return list of prefixes from specified neighbor */
413 eigrp_topology_update_distance(struct eigrp_fsm_action_message
*msg
)
415 struct eigrp
*eigrp
= msg
->eigrp
;
416 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
417 struct eigrp_neighbor_entry
*entry
= msg
->entry
;
421 struct TLV_IPv4_External_type
*ext_data
= NULL
;
422 struct TLV_IPv4_Internal_type
*int_data
= NULL
;
423 if (msg
->data_type
== EIGRP_TLV_IPv4_INT
)
425 int_data
= msg
->data
.ipv4_int_type
;
426 if (eigrp_metrics_is_same(int_data
->metric
, entry
->reported_metric
))
428 return 0; // No change
431 entry
->reported_distance
432 < eigrp_calculate_metrics(eigrp
, int_data
->metric
) ? 1 :
433 entry
->reported_distance
434 > eigrp_calculate_metrics(eigrp
, int_data
->metric
) ? 2 : 3; // Increase : Decrease : No change
435 entry
->reported_metric
= int_data
->metric
;
436 entry
->reported_distance
=
437 eigrp_calculate_metrics(eigrp
, int_data
->metric
);
438 entry
->distance
= eigrp_calculate_total_metrics(eigrp
, entry
);
442 ext_data
= msg
->data
.ipv4_ext_data
;
443 if (eigrp_metrics_is_same (ext_data
->metric
, entry
->reported_metric
))
447 * Move to correct position in list according to new distance
449 listnode_delete(prefix
->entries
, entry
);
450 listnode_add_sort(prefix
->entries
, entry
);
456 eigrp_topology_update_all_node_flags(struct eigrp
*eigrp
)
458 struct list
*table
= eigrp
->topology_table
;
459 struct eigrp_prefix_entry
*data
;
460 struct listnode
*node
, *nnode
;
461 for (ALL_LIST_ELEMENTS(table
, node
, nnode
, data
))
463 eigrp_topology_update_node_flags(data
);
468 eigrp_topology_update_node_flags(struct eigrp_prefix_entry
*dest
)
470 struct listnode
*node
;
471 struct eigrp_neighbor_entry
*entry
;
472 struct eigrp
* eigrp
= eigrp_lookup();
474 for (ALL_LIST_ELEMENTS_RO(dest
->entries
, node
, entry
))
476 if (((uint64_t)entry
->distance
<= (uint64_t)(dest
->distance
*eigrp
->variance
)) &&
477 entry
->distance
!= EIGRP_MAX_METRIC
) // is successor
479 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
480 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
482 else if (entry
->reported_distance
< dest
->fdistance
) // is feasible successor
484 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
485 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
489 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
490 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
496 eigrp_update_routing_table(struct eigrp_prefix_entry
* prefix
)
498 struct eigrp
*eigrp
= eigrp_lookup();
499 struct list
*successors
= eigrp_topology_get_successor_max(prefix
, eigrp
->max_paths
);
500 struct listnode
*node
;
501 struct eigrp_neighbor_entry
*entry
;
505 eigrp_zebra_route_add(prefix
->destination_ipv4
, successors
);
506 for (ALL_LIST_ELEMENTS_RO (successors
, node
, entry
))
507 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG
;
509 list_delete(successors
);
513 eigrp_zebra_route_delete(prefix
->destination_ipv4
);
514 for (ALL_LIST_ELEMENTS_RO (prefix
->entries
, node
, entry
))
515 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG
;
520 eigrp_topology_neighbor_down(struct eigrp
*eigrp
, struct eigrp_neighbor
* nbr
)
522 struct listnode
*node1
, *node11
, *node2
, *node22
;
523 struct eigrp_prefix_entry
*prefix
;
524 struct eigrp_neighbor_entry
*entry
;
526 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
))
528 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
))
530 if (entry
->adv_router
== nbr
)
532 struct eigrp_fsm_action_message
*msg
;
533 msg
= XCALLOC(MTYPE_EIGRP_FSM_MSG
,
534 sizeof(struct eigrp_fsm_action_message
));
535 struct TLV_IPv4_Internal_type
* tlv
= eigrp_IPv4_InternalTLV_new();
536 tlv
->metric
.delay
= EIGRP_MAX_METRIC
;
537 msg
->packet_type
= EIGRP_OPC_UPDATE
;
539 msg
->data_type
= EIGRP_TLV_IPv4_INT
;
540 msg
->adv_router
= nbr
;
541 msg
->data
.ipv4_int_type
= tlv
;
543 msg
->prefix
= prefix
;
544 int event
= eigrp_get_fsm_event(msg
);
545 eigrp_fsm_event(msg
, event
);
550 eigrp_query_send_all(eigrp
);
551 eigrp_update_send_all(eigrp
,nbr
->ei
);
556 eigrp_update_topology_table_prefix(struct list
* table
, struct eigrp_prefix_entry
* prefix
)
558 struct listnode
*node1
, *node2
;
560 struct eigrp_neighbor_entry
*entry
;
561 for (ALL_LIST_ELEMENTS(prefix
->entries
, node1
, node2
, entry
))
563 if(entry
->distance
== EIGRP_MAX_METRIC
)
565 eigrp_neighbor_entry_delete(prefix
,entry
);
568 if(prefix
->distance
== EIGRP_MAX_METRIC
&& prefix
->nt
!= EIGRP_TOPOLOGY_TYPE_CONNECTED
)
570 eigrp_prefix_entry_delete(table
,prefix
);