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
*,
55 struct eigrp_prefix_entry
*);
56 static void eigrp_prefix_entry_del(struct eigrp_prefix_entry
*);
57 static int eigrp_nexthop_entry_cmp(struct eigrp_nexthop_entry
*,
58 struct eigrp_nexthop_entry
*);
61 * Returns linkedlist used as topology table
62 * cmp - assigned function for comparing topology nodes
63 * del - assigned function executed before deleting topology node by list
66 struct list
*eigrp_topology_new()
68 struct list
*new = list_new();
69 new->cmp
= (int (*)(void *, void *))eigrp_prefix_entry_cmp
;
70 new->del
= (void (*)(void *))eigrp_prefix_entry_del
;
76 * Topology node comparison
79 static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry
*node1
,
80 struct eigrp_prefix_entry
*node2
)
82 if (node1
->af
== AF_INET
) {
83 if (node2
->af
== AF_INET
) {
84 if (node1
->destination
->u
.prefix4
.s_addr
85 < node2
->destination
->u
.prefix4
.s_addr
)
87 if (node1
->destination
->u
.prefix4
.s_addr
88 > node2
->destination
->u
.prefix4
.s_addr
)
99 * Topology node delete
102 static void eigrp_prefix_entry_del(struct eigrp_prefix_entry
*node
)
104 list_delete_all_node(node
->entries
);
105 list_free(node
->entries
);
109 * Returns new created toplogy node
110 * cmp - assigned function for comparing topology entry
112 struct eigrp_prefix_entry
*eigrp_prefix_entry_new()
114 struct eigrp_prefix_entry
*new;
115 new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY
,
116 sizeof(struct eigrp_prefix_entry
));
117 new->entries
= list_new();
118 new->rij
= list_new();
119 new->entries
->cmp
= (int (*)(void *, void *))eigrp_nexthop_entry_cmp
;
120 new->distance
= new->fdistance
= new->rdistance
= EIGRP_MAX_METRIC
;
121 new->destination
= NULL
;
127 * Topology entry comparison
129 static int eigrp_nexthop_entry_cmp(struct eigrp_nexthop_entry
*entry1
,
130 struct eigrp_nexthop_entry
*entry2
)
132 if (entry1
->distance
< entry2
->distance
)
134 if (entry1
->distance
> entry2
->distance
)
141 * Returns new topology entry
144 struct eigrp_nexthop_entry
*eigrp_nexthop_entry_new()
146 struct eigrp_nexthop_entry
*new;
148 new = XCALLOC(MTYPE_EIGRP_NEXTHOP_ENTRY
,
149 sizeof(struct eigrp_nexthop_entry
));
150 new->reported_distance
= EIGRP_MAX_METRIC
;
151 new->distance
= EIGRP_MAX_METRIC
;
157 * Freeing topology table list
159 void eigrp_topology_free(struct list
*list
)
165 * Deleting all topology nodes in table
167 void eigrp_topology_cleanup(struct list
*topology
)
171 eigrp_topology_delete_all(topology
);
175 * Adding topology node to topology table
177 void eigrp_prefix_entry_add(struct list
*topology
,
178 struct eigrp_prefix_entry
*node
)
180 if (listnode_lookup(topology
, node
) == NULL
) {
181 listnode_add_sort(topology
, node
);
186 * Adding topology entry to topology node
188 void eigrp_nexthop_entry_add(struct eigrp_prefix_entry
*node
,
189 struct eigrp_nexthop_entry
*entry
)
191 struct list
*l
= list_new();
193 listnode_add(l
, entry
);
195 if (listnode_lookup(node
->entries
, entry
) == NULL
) {
196 listnode_add_sort(node
->entries
, entry
);
197 entry
->prefix
= node
;
199 eigrp_zebra_route_add(node
->destination
, l
);
202 list_delete_and_null(&l
);
206 * Deleting topology node from topology table
208 void eigrp_prefix_entry_delete(struct list
*topology
,
209 struct eigrp_prefix_entry
*node
)
211 struct eigrp
*eigrp
= eigrp_lookup();
214 * Emergency removal of the node from this list.
217 listnode_delete(eigrp
->topology_changes_internalIPV4
, node
);
219 if (listnode_lookup(topology
, node
) != NULL
) {
220 list_delete_all_node(node
->entries
);
221 list_free(node
->entries
);
222 list_free(node
->rij
);
223 listnode_delete(topology
, node
);
224 eigrp_zebra_route_delete(node
->destination
);
225 XFREE(MTYPE_EIGRP_PREFIX_ENTRY
, node
);
230 * Deleting topology entry from topology node
232 void eigrp_nexthop_entry_delete(struct eigrp_prefix_entry
*node
,
233 struct eigrp_nexthop_entry
*entry
)
235 if (listnode_lookup(node
->entries
, entry
) != NULL
) {
236 listnode_delete(node
->entries
, entry
);
237 eigrp_zebra_route_delete(node
->destination
);
238 XFREE(MTYPE_EIGRP_NEXTHOP_ENTRY
, entry
);
243 * Deleting all nodes from topology table
245 void eigrp_topology_delete_all(struct list
*topology
)
247 list_delete_all_node(topology
);
251 * Return 0 if topology is not empty
254 unsigned int eigrp_topology_table_isempty(struct list
*topology
)
262 struct eigrp_prefix_entry
*
263 eigrp_topology_table_lookup_ipv4(struct list
*topology_table
,
264 struct prefix
*address
)
266 struct eigrp_prefix_entry
*data
;
267 struct listnode
*node
;
268 for (ALL_LIST_ELEMENTS_RO(topology_table
, node
, data
)) {
269 if (prefix_same(data
->destination
, address
))
277 * For a future optimization, put the successor list into it's
278 * own separate list from the full list?
280 * That way we can clean up all the list_new and list_delete's
281 * that we are doing. DBS
283 struct list
*eigrp_topology_get_successor(struct eigrp_prefix_entry
*table_node
)
285 struct list
*successors
= list_new();
286 struct eigrp_nexthop_entry
*data
;
287 struct listnode
*node1
, *node2
;
289 for (ALL_LIST_ELEMENTS(table_node
->entries
, node1
, node2
, data
)) {
290 if (data
->flags
& EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
) {
291 listnode_add(successors
, data
);
296 * If we have no successors return NULL
298 if (!successors
->count
) {
299 list_delete_and_null(&successors
);
307 eigrp_topology_get_successor_max(struct eigrp_prefix_entry
*table_node
,
308 unsigned int maxpaths
)
310 struct list
*successors
= eigrp_topology_get_successor(table_node
);
312 if (successors
&& successors
->count
> maxpaths
) {
314 struct listnode
*node
= listtail(successors
);
316 list_delete_node(successors
, node
);
318 } while (successors
->count
> maxpaths
);
324 struct eigrp_nexthop_entry
*
325 eigrp_prefix_entry_lookup(struct list
*entries
, struct eigrp_neighbor
*nbr
)
327 struct eigrp_nexthop_entry
*data
;
328 struct listnode
*node
, *nnode
;
329 for (ALL_LIST_ELEMENTS(entries
, node
, nnode
, data
)) {
330 if (data
->adv_router
== nbr
) {
338 /* Lookup all prefixes from specified neighbor */
339 struct list
*eigrp_neighbor_prefixes_lookup(struct eigrp
*eigrp
,
340 struct eigrp_neighbor
*nbr
)
342 struct listnode
*node1
, *node11
, *node2
, *node22
;
343 struct eigrp_prefix_entry
*prefix
;
344 struct eigrp_nexthop_entry
*entry
;
346 /* create new empty list for prefixes storage */
347 struct list
*prefixes
= list_new();
349 /* iterate over all prefixes in topology table */
350 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
)) {
351 /* iterate over all neighbor entry in prefix */
352 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
)) {
353 /* if entry is from specified neighbor, add to list */
354 if (entry
->adv_router
== nbr
) {
355 listnode_add(prefixes
, prefix
);
360 /* return list of prefixes from specified neighbor */
364 enum metric_change
eigrp_topology_update_distance(struct eigrp_fsm_action_message
*msg
)
366 struct eigrp
*eigrp
= msg
->eigrp
;
367 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
368 struct eigrp_nexthop_entry
*entry
= msg
->entry
;
369 enum metric_change change
= METRIC_SAME
;
370 u_int32_t new_reported_distance
;
374 switch(msg
->data_type
) {
375 case EIGRP_CONNECTED
:
376 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_CONNECTED
)
379 change
= METRIC_DECREASE
;
382 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_CONNECTED
) {
383 change
= METRIC_INCREASE
;
386 if (eigrp_metrics_is_same(msg
->metrics
,
387 entry
->reported_metric
)) {
388 return change
; // No change
391 new_reported_distance
= eigrp_calculate_metrics(eigrp
,
394 if (entry
->reported_distance
< new_reported_distance
) {
395 change
= METRIC_INCREASE
;
398 change
= METRIC_DECREASE
;
400 entry
->reported_metric
= msg
->metrics
;
401 entry
->reported_distance
= new_reported_distance
;
402 eigrp_calculate_metrics(eigrp
, msg
->metrics
);
403 entry
->distance
= eigrp_calculate_total_metrics(eigrp
, entry
);
406 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_REMOTE_EXTERNAL
) {
407 if (eigrp_metrics_is_same(msg
->metrics
,
408 entry
->reported_metric
))
411 change
= METRIC_INCREASE
;
416 zlog_err("%s: Please implement handler", __PRETTY_FUNCTION__
);
421 * Move to correct position in list according to new distance
423 listnode_delete(prefix
->entries
, entry
);
424 listnode_add_sort(prefix
->entries
, entry
);
429 void eigrp_topology_update_all_node_flags(struct eigrp
*eigrp
)
431 struct list
*table
= eigrp
->topology_table
;
432 struct eigrp_prefix_entry
*data
;
433 struct listnode
*node
, *nnode
;
434 for (ALL_LIST_ELEMENTS(table
, node
, nnode
, data
)) {
435 eigrp_topology_update_node_flags(data
);
439 void eigrp_topology_update_node_flags(struct eigrp_prefix_entry
*dest
)
441 struct listnode
*node
;
442 struct eigrp_nexthop_entry
*entry
;
443 struct eigrp
*eigrp
= eigrp_lookup();
445 for (ALL_LIST_ELEMENTS_RO(dest
->entries
, node
, entry
)) {
446 if (((uint64_t)entry
->distance
447 <= (uint64_t)dest
->distance
* (uint64_t)eigrp
->variance
)
448 && entry
->distance
!= EIGRP_MAX_METRIC
) // is successor
450 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
451 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
452 } else if (entry
->reported_distance
453 < dest
->fdistance
) // is feasible successor
455 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
456 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
458 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
459 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
464 void eigrp_update_routing_table(struct eigrp_prefix_entry
*prefix
)
466 struct eigrp
*eigrp
= eigrp_lookup();
467 struct list
*successors
=
468 eigrp_topology_get_successor_max(prefix
, eigrp
->max_paths
);
469 struct listnode
*node
;
470 struct eigrp_nexthop_entry
*entry
;
473 eigrp_zebra_route_add(prefix
->destination
,
475 for (ALL_LIST_ELEMENTS_RO(successors
, node
, entry
))
476 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_INTABLE_FLAG
;
478 list_delete_and_null(&successors
);
480 eigrp_zebra_route_delete(prefix
->destination
);
481 for (ALL_LIST_ELEMENTS_RO(prefix
->entries
, node
, entry
))
482 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_INTABLE_FLAG
;
486 void eigrp_topology_neighbor_down(struct eigrp
*eigrp
,
487 struct eigrp_neighbor
*nbr
)
489 struct listnode
*node1
, *node11
, *node2
, *node22
;
490 struct eigrp_prefix_entry
*prefix
;
491 struct eigrp_nexthop_entry
*entry
;
493 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
)) {
494 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
)) {
495 struct eigrp_fsm_action_message msg
;
497 if (entry
->adv_router
!= nbr
)
500 msg
.metrics
.delay
= EIGRP_MAX_METRIC
;
501 msg
.packet_type
= EIGRP_OPC_UPDATE
;
503 msg
.data_type
= EIGRP_INT
;
504 msg
.adv_router
= nbr
;
507 eigrp_fsm_event(&msg
);
511 eigrp_query_send_all(eigrp
);
512 eigrp_update_send_all(eigrp
, nbr
->ei
);
515 void eigrp_update_topology_table_prefix(struct list
*table
,
516 struct eigrp_prefix_entry
*prefix
)
518 struct listnode
*node1
, *node2
;
520 struct eigrp_nexthop_entry
*entry
;
521 for (ALL_LIST_ELEMENTS(prefix
->entries
, node1
, node2
, entry
)) {
522 if (entry
->distance
== EIGRP_MAX_METRIC
) {
523 eigrp_nexthop_entry_delete(prefix
, entry
);
526 if (prefix
->distance
== EIGRP_MAX_METRIC
527 && prefix
->nt
!= EIGRP_TOPOLOGY_TYPE_CONNECTED
) {
528 eigrp_prefix_entry_delete(table
, prefix
);