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_nexthop_entry_cmp(struct eigrp_nexthop_entry
*,
55 struct eigrp_nexthop_entry
*);
58 * Returns linkedlist used as topology table
59 * cmp - assigned function for comparing topology nodes
60 * del - assigned function executed before deleting topology node by list
63 struct route_table
*eigrp_topology_new()
65 return route_table_init();
69 * Returns new created toplogy node
70 * cmp - assigned function for comparing topology entry
72 struct eigrp_prefix_entry
*eigrp_prefix_entry_new()
74 struct eigrp_prefix_entry
*new;
75 new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY
,
76 sizeof(struct eigrp_prefix_entry
));
77 new->entries
= list_new();
78 new->rij
= list_new();
79 new->entries
->cmp
= (int (*)(void *, void *))eigrp_nexthop_entry_cmp
;
80 new->distance
= new->fdistance
= new->rdistance
= EIGRP_MAX_METRIC
;
81 new->destination
= NULL
;
87 * Topology entry comparison
89 static int eigrp_nexthop_entry_cmp(struct eigrp_nexthop_entry
*entry1
,
90 struct eigrp_nexthop_entry
*entry2
)
92 if (entry1
->distance
< entry2
->distance
)
94 if (entry1
->distance
> entry2
->distance
)
101 * Returns new topology entry
104 struct eigrp_nexthop_entry
*eigrp_nexthop_entry_new()
106 struct eigrp_nexthop_entry
*new;
108 new = XCALLOC(MTYPE_EIGRP_NEXTHOP_ENTRY
,
109 sizeof(struct eigrp_nexthop_entry
));
110 new->reported_distance
= EIGRP_MAX_METRIC
;
111 new->distance
= EIGRP_MAX_METRIC
;
117 * Freeing topology table list
119 void eigrp_topology_free(struct route_table
*table
)
121 route_table_finish(table
);
125 * Deleting all topology nodes in table
127 void eigrp_topology_cleanup(struct route_table
*table
)
129 eigrp_topology_delete_all(table
);
133 * Adding topology node to topology table
135 void eigrp_prefix_entry_add(struct route_table
*topology
,
136 struct eigrp_prefix_entry
*pe
)
138 struct route_node
*rn
;
140 rn
= route_node_get(topology
, pe
->destination
);
142 if (IS_DEBUG_EIGRP_EVENT
) {
143 char buf
[PREFIX_STRLEN
];
145 zlog_debug("%s: %s Should we have found this entry in the topo table?",
147 prefix2str(pe
->destination
, buf
,
157 * Adding topology entry to topology node
159 void eigrp_nexthop_entry_add(struct eigrp_prefix_entry
*node
,
160 struct eigrp_nexthop_entry
*entry
)
162 struct list
*l
= list_new();
164 listnode_add(l
, entry
);
166 if (listnode_lookup(node
->entries
, entry
) == NULL
) {
167 listnode_add_sort(node
->entries
, entry
);
168 entry
->prefix
= node
;
170 eigrp_zebra_route_add(node
->destination
, l
);
173 list_delete_and_null(&l
);
177 * Deleting topology node from topology table
179 void eigrp_prefix_entry_delete(struct route_table
*table
,
180 struct eigrp_prefix_entry
*pe
)
182 struct eigrp
*eigrp
= eigrp_lookup();
183 struct route_node
*rn
;
185 rn
= route_node_lookup(table
, pe
->destination
);
190 * Emergency removal of the node from this list.
193 listnode_delete(eigrp
->topology_changes_internalIPV4
, pe
);
195 list_delete_and_null(&pe
->entries
);
196 list_delete_and_null(&pe
->rij
);
197 eigrp_zebra_route_delete(pe
->destination
);
200 route_unlock_node(rn
); //Lookup above
201 route_unlock_node(rn
); //Initial creation
202 XFREE(MTYPE_EIGRP_PREFIX_ENTRY
, pe
);
206 * Deleting topology entry from topology node
208 void eigrp_nexthop_entry_delete(struct eigrp_prefix_entry
*node
,
209 struct eigrp_nexthop_entry
*entry
)
211 if (listnode_lookup(node
->entries
, entry
) != NULL
) {
212 listnode_delete(node
->entries
, entry
);
213 eigrp_zebra_route_delete(node
->destination
);
214 XFREE(MTYPE_EIGRP_NEXTHOP_ENTRY
, entry
);
219 * Deleting all nodes from topology table
221 void eigrp_topology_delete_all(struct route_table
*topology
)
223 struct route_node
*rn
;
224 struct eigrp_prefix_entry
*pe
;
226 for (rn
= route_top(topology
); rn
; rn
= route_next(rn
)) {
232 eigrp_prefix_entry_delete(topology
, pe
);
237 * Return 0 if topology is not empty
240 unsigned int eigrp_topology_table_isempty(struct list
*topology
)
248 struct eigrp_prefix_entry
*
249 eigrp_topology_table_lookup_ipv4(struct route_table
*table
,
250 struct prefix
*address
)
252 struct eigrp_prefix_entry
*pe
;
253 struct route_node
*rn
;
255 rn
= route_node_lookup(table
, address
);
261 route_unlock_node(rn
);
267 * For a future optimization, put the successor list into it's
268 * own separate list from the full list?
270 * That way we can clean up all the list_new and list_delete's
271 * that we are doing. DBS
273 struct list
*eigrp_topology_get_successor(struct eigrp_prefix_entry
*table_node
)
275 struct list
*successors
= list_new();
276 struct eigrp_nexthop_entry
*data
;
277 struct listnode
*node1
, *node2
;
279 for (ALL_LIST_ELEMENTS(table_node
->entries
, node1
, node2
, data
)) {
280 if (data
->flags
& EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
) {
281 listnode_add(successors
, data
);
286 * If we have no successors return NULL
288 if (!successors
->count
) {
289 list_delete_and_null(&successors
);
297 eigrp_topology_get_successor_max(struct eigrp_prefix_entry
*table_node
,
298 unsigned int maxpaths
)
300 struct list
*successors
= eigrp_topology_get_successor(table_node
);
302 if (successors
&& successors
->count
> maxpaths
) {
304 struct listnode
*node
= listtail(successors
);
306 list_delete_node(successors
, node
);
308 } while (successors
->count
> maxpaths
);
314 struct eigrp_nexthop_entry
*
315 eigrp_prefix_entry_lookup(struct list
*entries
, struct eigrp_neighbor
*nbr
)
317 struct eigrp_nexthop_entry
*data
;
318 struct listnode
*node
, *nnode
;
319 for (ALL_LIST_ELEMENTS(entries
, node
, nnode
, data
)) {
320 if (data
->adv_router
== nbr
) {
328 /* Lookup all prefixes from specified neighbor */
329 struct list
*eigrp_neighbor_prefixes_lookup(struct eigrp
*eigrp
,
330 struct eigrp_neighbor
*nbr
)
332 struct listnode
*node2
, *node22
;
333 struct eigrp_nexthop_entry
*entry
;
334 struct eigrp_prefix_entry
*pe
;
335 struct route_node
*rn
;
337 /* create new empty list for prefixes storage */
338 struct list
*prefixes
= list_new();
340 /* iterate over all prefixes in topology table */
341 for (rn
= route_top(eigrp
->topology_table
); rn
; rn
= route_next(rn
)) {
345 /* iterate over all neighbor entry in prefix */
346 for (ALL_LIST_ELEMENTS(pe
->entries
, node2
, node22
, entry
)) {
347 /* if entry is from specified neighbor, add to list */
348 if (entry
->adv_router
== nbr
) {
349 listnode_add(prefixes
, pe
);
354 /* return list of prefixes from specified neighbor */
358 enum metric_change
eigrp_topology_update_distance(struct eigrp_fsm_action_message
*msg
)
360 struct eigrp
*eigrp
= msg
->eigrp
;
361 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
362 struct eigrp_nexthop_entry
*entry
= msg
->entry
;
363 enum metric_change change
= METRIC_SAME
;
364 u_int32_t new_reported_distance
;
368 switch(msg
->data_type
) {
369 case EIGRP_CONNECTED
:
370 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_CONNECTED
)
373 change
= METRIC_DECREASE
;
376 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_CONNECTED
) {
377 change
= METRIC_INCREASE
;
380 if (eigrp_metrics_is_same(msg
->metrics
,
381 entry
->reported_metric
)) {
382 return change
; // No change
385 new_reported_distance
= eigrp_calculate_metrics(eigrp
,
388 if (entry
->reported_distance
< new_reported_distance
) {
389 change
= METRIC_INCREASE
;
392 change
= METRIC_DECREASE
;
394 entry
->reported_metric
= msg
->metrics
;
395 entry
->reported_distance
= new_reported_distance
;
396 eigrp_calculate_metrics(eigrp
, msg
->metrics
);
397 entry
->distance
= eigrp_calculate_total_metrics(eigrp
, entry
);
400 if (prefix
->nt
== EIGRP_TOPOLOGY_TYPE_REMOTE_EXTERNAL
) {
401 if (eigrp_metrics_is_same(msg
->metrics
,
402 entry
->reported_metric
))
405 change
= METRIC_INCREASE
;
410 zlog_err("%s: Please implement handler", __PRETTY_FUNCTION__
);
415 * Move to correct position in list according to new distance
417 listnode_delete(prefix
->entries
, entry
);
418 listnode_add_sort(prefix
->entries
, entry
);
423 void eigrp_topology_update_all_node_flags(struct eigrp
*eigrp
)
425 struct eigrp_prefix_entry
*pe
;
426 struct route_node
*rn
;
428 for (rn
= route_top(eigrp
->topology_table
); rn
; rn
= route_next(rn
)) {
434 eigrp_topology_update_node_flags(pe
);
438 void eigrp_topology_update_node_flags(struct eigrp_prefix_entry
*dest
)
440 struct listnode
*node
;
441 struct eigrp_nexthop_entry
*entry
;
442 struct eigrp
*eigrp
= eigrp_lookup();
444 for (ALL_LIST_ELEMENTS_RO(dest
->entries
, node
, entry
)) {
445 if (((uint64_t)entry
->distance
446 <= (uint64_t)dest
->distance
* (uint64_t)eigrp
->variance
)
447 && entry
->distance
!= EIGRP_MAX_METRIC
) // is successor
449 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
450 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
451 } else if (entry
->reported_distance
452 < dest
->fdistance
) // is feasible successor
454 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
455 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
457 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_FSUCCESSOR_FLAG
;
458 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG
;
463 void eigrp_update_routing_table(struct eigrp_prefix_entry
*prefix
)
465 struct eigrp
*eigrp
= eigrp_lookup();
466 struct list
*successors
=
467 eigrp_topology_get_successor_max(prefix
, eigrp
->max_paths
);
468 struct listnode
*node
;
469 struct eigrp_nexthop_entry
*entry
;
472 eigrp_zebra_route_add(prefix
->destination
,
474 for (ALL_LIST_ELEMENTS_RO(successors
, node
, entry
))
475 entry
->flags
|= EIGRP_NEXTHOP_ENTRY_INTABLE_FLAG
;
477 list_delete_and_null(&successors
);
479 eigrp_zebra_route_delete(prefix
->destination
);
480 for (ALL_LIST_ELEMENTS_RO(prefix
->entries
, node
, entry
))
481 entry
->flags
&= ~EIGRP_NEXTHOP_ENTRY_INTABLE_FLAG
;
485 void eigrp_topology_neighbor_down(struct eigrp
*eigrp
,
486 struct eigrp_neighbor
*nbr
)
488 struct listnode
*node2
, *node22
;
489 struct eigrp_prefix_entry
*pe
;
490 struct eigrp_nexthop_entry
*entry
;
491 struct route_node
*rn
;
493 for (rn
= route_top(eigrp
->topology_table
); rn
; rn
= route_next(rn
)) {
499 for (ALL_LIST_ELEMENTS(pe
->entries
, node2
, node22
, entry
)) {
500 struct eigrp_fsm_action_message msg
;
502 if (entry
->adv_router
!= nbr
)
505 msg
.metrics
.delay
= EIGRP_MAX_METRIC
;
506 msg
.packet_type
= EIGRP_OPC_UPDATE
;
508 msg
.data_type
= EIGRP_INT
;
509 msg
.adv_router
= nbr
;
512 eigrp_fsm_event(&msg
);
516 eigrp_query_send_all(eigrp
);
517 eigrp_update_send_all(eigrp
, nbr
->ei
);
520 void eigrp_update_topology_table_prefix(struct route_table
*table
,
521 struct eigrp_prefix_entry
*prefix
)
523 struct listnode
*node1
, *node2
;
525 struct eigrp_nexthop_entry
*entry
;
526 for (ALL_LIST_ELEMENTS(prefix
->entries
, node1
, node2
, entry
)) {
527 if (entry
->distance
== EIGRP_MAX_METRIC
) {
528 eigrp_nexthop_entry_delete(prefix
, entry
);
531 if (prefix
->distance
== EIGRP_MAX_METRIC
532 && prefix
->nt
!= EIGRP_TOPOLOGY_TYPE_CONNECTED
) {
533 eigrp_prefix_entry_delete(table
, prefix
);