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_neighbor_entry_cmp(struct eigrp_neighbor_entry
*,
58 struct eigrp_neighbor_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_ipv4
->prefix
.s_addr
85 < node2
->destination_ipv4
->prefix
.s_addr
) {
86 return -1; // if it belong above node2
88 if (node1
->destination_ipv4
->prefix
.s_addr
89 > node2
->destination_ipv4
->prefix
.s_addr
) {
90 return 1; // if it belongs under node2
92 return 0; // same value... ERROR...in
93 // case of adding same prefix
100 } else { // TODO check if the prefix dont exists
101 return 1; // add to end
106 * Topology node delete
109 static void eigrp_prefix_entry_del(struct eigrp_prefix_entry
*node
)
111 list_delete_all_node(node
->entries
);
112 list_free(node
->entries
);
116 * Returns new created toplogy node
117 * cmp - assigned function for comparing topology entry
119 struct eigrp_prefix_entry
*eigrp_prefix_entry_new()
121 struct eigrp_prefix_entry
*new;
122 new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY
,
123 sizeof(struct eigrp_prefix_entry
));
124 new->entries
= list_new();
125 new->rij
= list_new();
126 new->entries
->cmp
= (int (*)(void *, void *))eigrp_neighbor_entry_cmp
;
127 new->distance
= new->fdistance
= new->rdistance
= EIGRP_MAX_METRIC
;
128 new->destination_ipv4
= NULL
;
129 new->destination_ipv6
= NULL
;
135 * Topology entry comparison
137 static int eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry
*entry1
,
138 struct eigrp_neighbor_entry
*entry2
)
141 < entry2
->distance
) // parameter used in list_add_sort ()
142 return -1; // actually set to sort by distance
143 if (entry1
->distance
> entry2
->distance
)
150 * Returns new topology entry
153 struct eigrp_neighbor_entry
*eigrp_neighbor_entry_new()
155 struct eigrp_neighbor_entry
*new;
157 new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY
,
158 sizeof(struct eigrp_neighbor_entry
));
159 new->reported_distance
= EIGRP_MAX_METRIC
;
160 new->distance
= EIGRP_MAX_METRIC
;
166 * Freeing topology table list
168 void eigrp_topology_free(struct list
*list
)
174 * Deleting all topology nodes in table
176 void eigrp_topology_cleanup(struct list
*topology
)
180 eigrp_topology_delete_all(topology
);
184 * Adding topology node to topology table
186 void eigrp_prefix_entry_add(struct list
*topology
,
187 struct eigrp_prefix_entry
*node
)
189 if (listnode_lookup(topology
, node
) == NULL
) {
190 listnode_add_sort(topology
, node
);
195 * Adding topology entry to topology node
197 void eigrp_neighbor_entry_add(struct eigrp_prefix_entry
*node
,
198 struct eigrp_neighbor_entry
*entry
)
200 struct list
*l
= list_new();
202 listnode_add(l
, entry
);
204 if (listnode_lookup(node
->entries
, entry
) == NULL
) {
205 listnode_add_sort(node
->entries
, entry
);
206 entry
->prefix
= node
;
208 eigrp_zebra_route_add(node
->destination_ipv4
, l
);
215 * Deleting topology node from topology table
217 void eigrp_prefix_entry_delete(struct list
*topology
,
218 struct eigrp_prefix_entry
*node
)
220 struct eigrp
*eigrp
= eigrp_lookup();
223 * Emergency removal of the node from this list.
226 listnode_delete(eigrp
->topology_changes_internalIPV4
, node
);
228 if (listnode_lookup(topology
, node
) != NULL
) {
229 list_delete_all_node(node
->entries
);
230 list_free(node
->entries
);
231 list_free(node
->rij
);
232 listnode_delete(topology
, node
);
233 eigrp_zebra_route_delete(node
->destination_ipv4
);
234 XFREE(MTYPE_EIGRP_PREFIX_ENTRY
, node
);
239 * Deleting topology entry from topology node
241 void eigrp_neighbor_entry_delete(struct eigrp_prefix_entry
*node
,
242 struct eigrp_neighbor_entry
*entry
)
244 if (listnode_lookup(node
->entries
, entry
) != NULL
) {
245 listnode_delete(node
->entries
, entry
);
246 eigrp_zebra_route_delete(node
->destination_ipv4
);
247 XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY
, entry
);
252 * Deleting all nodes from topology table
254 void eigrp_topology_delete_all(struct list
*topology
)
256 list_delete_all_node(topology
);
260 * Return 0 if topology is not empty
263 unsigned int eigrp_topology_table_isempty(struct list
*topology
)
271 struct eigrp_prefix_entry
*
272 eigrp_topology_table_lookup_ipv4(struct list
*topology_table
,
273 struct prefix_ipv4
*address
)
275 struct eigrp_prefix_entry
*data
;
276 struct listnode
*node
;
277 for (ALL_LIST_ELEMENTS_RO(topology_table
, node
, data
)) {
278 if ((data
->af
== AF_INET
)
279 && (data
->destination_ipv4
->prefix
.s_addr
280 == address
->prefix
.s_addr
)
281 && (data
->destination_ipv4
->prefixlen
282 == address
->prefixlen
))
290 * For a future optimization, put the successor list into it's
291 * own separate list from the full list?
293 * That way we can clean up all the list_new and list_delete's
294 * that we are doing. DBS
296 struct list
*eigrp_topology_get_successor(struct eigrp_prefix_entry
*table_node
)
298 struct list
*successors
= list_new();
299 struct eigrp_neighbor_entry
*data
;
300 struct listnode
*node1
, *node2
;
302 for (ALL_LIST_ELEMENTS(table_node
->entries
, node1
, node2
, data
)) {
303 if (data
->flags
& EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
) {
304 listnode_add(successors
, data
);
309 * If we have no successors return NULL
311 if (!successors
->count
) {
312 list_delete(successors
);
320 eigrp_topology_get_successor_max(struct eigrp_prefix_entry
*table_node
,
321 unsigned int maxpaths
)
323 struct list
*successors
= eigrp_topology_get_successor(table_node
);
325 if (successors
&& successors
->count
> maxpaths
) {
327 struct listnode
*node
= listtail(successors
);
329 list_delete_node(successors
, node
);
331 } while (successors
->count
> maxpaths
);
337 struct eigrp_neighbor_entry
*
338 eigrp_prefix_entry_lookup(struct list
*entries
, struct eigrp_neighbor
*nbr
)
340 struct eigrp_neighbor_entry
*data
;
341 struct listnode
*node
, *nnode
;
342 for (ALL_LIST_ELEMENTS(entries
, node
, nnode
, data
)) {
343 if (data
->adv_router
== nbr
) {
351 /* Lookup all prefixes from specified neighbor */
352 struct list
*eigrp_neighbor_prefixes_lookup(struct eigrp
*eigrp
,
353 struct eigrp_neighbor
*nbr
)
355 struct listnode
*node1
, *node11
, *node2
, *node22
;
356 struct eigrp_prefix_entry
*prefix
;
357 struct eigrp_neighbor_entry
*entry
;
359 /* create new empty list for prefixes storage */
360 struct list
*prefixes
= list_new();
362 /* iterate over all prefixes in topology table */
363 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
)) {
364 /* iterate over all neighbor entry in prefix */
365 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
)) {
366 /* if entry is from specified neighbor, add to list */
367 if (entry
->adv_router
== nbr
) {
368 listnode_add(prefixes
, prefix
);
373 /* return list of prefixes from specified neighbor */
377 enum metric_change
eigrp_topology_update_distance(struct eigrp_fsm_action_message
*msg
)
379 struct eigrp
*eigrp
= msg
->eigrp
;
380 struct eigrp_prefix_entry
*prefix
= msg
->prefix
;
381 struct eigrp_neighbor_entry
*entry
= msg
->entry
;
382 enum metric_change change
= METRIC_SAME
;
385 struct TLV_IPv4_External_type
*ext_data
= NULL
;
386 struct TLV_IPv4_Internal_type
*int_data
= NULL
;
387 if (msg
->data_type
== EIGRP_TLV_IPv4_INT
) {
388 u_int32_t new_reported_distance
;
390 int_data
= msg
->data
.ipv4_int_type
;
391 if (eigrp_metrics_is_same(int_data
->metric
,
392 entry
->reported_metric
)) {
393 return change
; // No change
396 new_reported_distance
= eigrp_calculate_metrics(eigrp
,
399 if (entry
->reported_distance
< new_reported_distance
)
400 change
= METRIC_INCREASE
;
402 change
= METRIC_DECREASE
;
404 entry
->reported_metric
= int_data
->metric
;
405 entry
->reported_distance
= new_reported_distance
;
406 eigrp_calculate_metrics(eigrp
, int_data
->metric
);
407 entry
->distance
= eigrp_calculate_total_metrics(eigrp
, entry
);
409 ext_data
= msg
->data
.ipv4_ext_data
;
410 if (eigrp_metrics_is_same(ext_data
->metric
,
411 entry
->reported_metric
))
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 list
*table
= eigrp
->topology_table
;
426 struct eigrp_prefix_entry
*data
;
427 struct listnode
*node
, *nnode
;
428 for (ALL_LIST_ELEMENTS(table
, node
, nnode
, data
)) {
429 eigrp_topology_update_node_flags(data
);
433 void eigrp_topology_update_node_flags(struct eigrp_prefix_entry
*dest
)
435 struct listnode
*node
;
436 struct eigrp_neighbor_entry
*entry
;
437 struct eigrp
*eigrp
= eigrp_lookup();
439 for (ALL_LIST_ELEMENTS_RO(dest
->entries
, node
, entry
)) {
440 if (((uint64_t)entry
->distance
441 <= (uint64_t)(dest
->distance
* eigrp
->variance
))
442 && entry
->distance
!= EIGRP_MAX_METRIC
) // is successor
444 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
445 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
446 } else if (entry
->reported_distance
447 < dest
->fdistance
) // is feasible successor
449 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
450 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
452 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG
;
453 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG
;
458 void eigrp_update_routing_table(struct eigrp_prefix_entry
*prefix
)
460 struct eigrp
*eigrp
= eigrp_lookup();
461 struct list
*successors
=
462 eigrp_topology_get_successor_max(prefix
, eigrp
->max_paths
);
463 struct listnode
*node
;
464 struct eigrp_neighbor_entry
*entry
;
467 eigrp_zebra_route_add(prefix
->destination_ipv4
, successors
);
468 for (ALL_LIST_ELEMENTS_RO(successors
, node
, entry
))
469 entry
->flags
|= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG
;
471 list_delete(successors
);
473 eigrp_zebra_route_delete(prefix
->destination_ipv4
);
474 for (ALL_LIST_ELEMENTS_RO(prefix
->entries
, node
, entry
))
475 entry
->flags
&= ~EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG
;
479 void eigrp_topology_neighbor_down(struct eigrp
*eigrp
,
480 struct eigrp_neighbor
*nbr
)
482 struct listnode
*node1
, *node11
, *node2
, *node22
;
483 struct eigrp_prefix_entry
*prefix
;
484 struct eigrp_neighbor_entry
*entry
;
486 for (ALL_LIST_ELEMENTS(eigrp
->topology_table
, node1
, node11
, prefix
)) {
487 for (ALL_LIST_ELEMENTS(prefix
->entries
, node2
, node22
, entry
)) {
488 if (entry
->adv_router
== nbr
) {
489 struct eigrp_fsm_action_message
*msg
;
490 msg
= XCALLOC(MTYPE_EIGRP_FSM_MSG
,
492 eigrp_fsm_action_message
));
493 struct TLV_IPv4_Internal_type
*tlv
=
494 eigrp_IPv4_InternalTLV_new();
495 tlv
->metric
.delay
= EIGRP_MAX_METRIC
;
496 msg
->packet_type
= EIGRP_OPC_UPDATE
;
498 msg
->data_type
= EIGRP_TLV_IPv4_INT
;
499 msg
->adv_router
= nbr
;
500 msg
->data
.ipv4_int_type
= tlv
;
502 msg
->prefix
= prefix
;
503 int event
= eigrp_get_fsm_event(msg
);
504 eigrp_fsm_event(msg
, event
);
509 eigrp_query_send_all(eigrp
);
510 eigrp_update_send_all(eigrp
, nbr
->ei
);
513 void eigrp_update_topology_table_prefix(struct list
*table
,
514 struct eigrp_prefix_entry
*prefix
)
516 struct listnode
*node1
, *node2
;
518 struct eigrp_neighbor_entry
*entry
;
519 for (ALL_LIST_ELEMENTS(prefix
->entries
, node1
, node2
, entry
)) {
520 if (entry
->distance
== EIGRP_MAX_METRIC
) {
521 eigrp_neighbor_entry_delete(prefix
, entry
);
524 if (prefix
->distance
== EIGRP_MAX_METRIC
525 && prefix
->nt
!= EIGRP_TOPOLOGY_TYPE_CONNECTED
) {
526 eigrp_prefix_entry_delete(table
, prefix
);