]>
Commit | Line | Data |
---|---|---|
7f57883e DS |
1 | /* |
2 | * EIGRP Topology Table. | |
3 | * Copyright (C) 2013-2016 | |
4 | * Authors: | |
5 | * Donnie Savage | |
6 | * Jan Janovic | |
7 | * Matej Perina | |
8 | * Peter Orsag | |
9 | * Peter Paluch | |
10 | * Frantisek Gazo | |
11 | * Tomas Hvorkovy | |
12 | * Martin Kontsek | |
13 | * Lukas Koribsky | |
14 | * | |
15 | * This file is part of GNU Zebra. | |
16 | * | |
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 | |
20 | * later version. | |
21 | * | |
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. | |
26 | * | |
27 | * You should have received a copy of the GNU General Public License | |
28 | * along with GNU Zebra; see the file COPYING. If not, write to the Free | |
29 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
30 | * 02111-1307, USA. | |
31 | */ | |
32 | ||
33 | #include <zebra.h> | |
34 | ||
35 | #include "prefix.h" | |
36 | #include "table.h" | |
37 | #include "memory.h" | |
38 | #include "log.h" | |
39 | #include "linklist.h" | |
40 | #include "vty.h" | |
41 | ||
42 | #include "eigrpd/eigrp_structs.h" | |
43 | #include "eigrpd/eigrpd.h" | |
44 | #include "eigrpd/eigrp_interface.h" | |
45 | #include "eigrpd/eigrp_neighbor.h" | |
46 | #include "eigrpd/eigrp_packet.h" | |
47 | #include "eigrpd/eigrp_zebra.h" | |
48 | #include "eigrpd/eigrp_vty.h" | |
49 | #include "eigrpd/eigrp_network.h" | |
50 | #include "eigrpd/eigrp_dump.h" | |
51 | #include "eigrpd/eigrp_topology.h" | |
52 | #include "eigrpd/eigrp_fsm.h" | |
53 | #include "eigrpd/eigrp_memory.h" | |
54 | ||
f9e5c9ca DS |
55 | static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *, 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 *); | |
7f57883e DS |
59 | |
60 | /* | |
7f57883e DS |
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 function | |
64 | */ | |
65 | struct list * | |
66 | eigrp_topology_new() | |
67 | { | |
68 | struct list* new = list_new(); | |
69 | new->cmp = (int | |
f9e5c9ca | 70 | (*)(void *, void *)) eigrp_prefix_entry_cmp; |
7f57883e | 71 | new->del = (void |
f9e5c9ca | 72 | (*)(void *)) eigrp_prefix_entry_del; |
7f57883e DS |
73 | |
74 | return new; | |
75 | } | |
76 | ||
77 | /* | |
78 | * Topology node comparison | |
79 | */ | |
80 | ||
81 | static int | |
82 | eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *node1, | |
f9e5c9ca | 83 | struct eigrp_prefix_entry *node2) |
7f57883e DS |
84 | { |
85 | if (node1->af == AF_INET) | |
86 | { | |
87 | if (node2->af == AF_INET) | |
88 | { | |
89 | if (node1->destination_ipv4->prefix.s_addr | |
90 | < node2->destination_ipv4->prefix.s_addr) | |
91 | { | |
92 | return -1; // if it belong above node2 | |
93 | } | |
94 | else | |
95 | { | |
96 | if (node1->destination_ipv4->prefix.s_addr | |
97 | > node2->destination_ipv4->prefix.s_addr) | |
98 | { | |
99 | return 1; //if it belongs under node2 | |
100 | } | |
101 | else | |
102 | { | |
103 | return 0; // same value... ERROR...in case of adding same prefix again | |
104 | } | |
105 | } | |
106 | } | |
107 | else | |
108 | { | |
109 | return 1; | |
110 | } | |
111 | } | |
112 | else | |
113 | { // TODO check if the prefix dont exists | |
114 | return 1; // add to end | |
115 | } | |
116 | } | |
117 | ||
118 | /* | |
119 | * Topology node delete | |
120 | */ | |
121 | ||
122 | static void | |
123 | eigrp_prefix_entry_del(struct eigrp_prefix_entry *node) | |
124 | { | |
125 | list_delete_all_node(node->entries); | |
126 | list_free(node->entries); | |
127 | } | |
128 | ||
129 | /* | |
130 | * Returns new created toplogy node | |
131 | * cmp - assigned function for comparing topology entry | |
132 | */ | |
7f57883e DS |
133 | struct eigrp_prefix_entry * |
134 | eigrp_prefix_entry_new() | |
135 | { | |
136 | struct eigrp_prefix_entry *new; | |
137 | new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY, sizeof(struct eigrp_prefix_entry)); | |
138 | new->entries = list_new(); | |
139 | new->rij = list_new(); | |
9f56205c | 140 | new->entries->cmp = (int (*)(void *, void *))eigrp_neighbor_entry_cmp; |
7f57883e DS |
141 | new->distance = new->fdistance = new->rdistance = EIGRP_MAX_METRIC; |
142 | new->destination_ipv4 = NULL; | |
143 | new->destination_ipv6 = NULL; | |
144 | ||
145 | return new; | |
146 | } | |
147 | ||
148 | /* | |
149 | * Topology entry comparison | |
150 | */ | |
7f57883e DS |
151 | static int |
152 | eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *entry1, | |
f9e5c9ca | 153 | struct eigrp_neighbor_entry *entry2) |
7f57883e DS |
154 | { |
155 | if (entry1->distance < entry2->distance) // parameter used in list_add_sort () | |
156 | return -1; // actually set to sort by distance | |
157 | if (entry1->distance > entry2->distance) | |
158 | return 1; | |
159 | ||
160 | return 0; | |
161 | } | |
162 | ||
163 | /* | |
164 | * Returns new topology entry | |
165 | */ | |
166 | ||
167 | struct eigrp_neighbor_entry * | |
168 | eigrp_neighbor_entry_new() | |
169 | { | |
170 | struct eigrp_neighbor_entry *new; | |
171 | ||
172 | new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY, | |
f9e5c9ca | 173 | sizeof(struct eigrp_neighbor_entry)); |
7f57883e DS |
174 | new->reported_distance = EIGRP_MAX_METRIC; |
175 | new->distance = EIGRP_MAX_METRIC; | |
176 | ||
177 | return new; | |
178 | } | |
179 | ||
180 | /* | |
181 | * Freeing topology table list | |
182 | */ | |
7f57883e DS |
183 | void |
184 | eigrp_topology_free(struct list *list) | |
185 | { | |
186 | list_free(list); | |
187 | } | |
188 | ||
189 | /* | |
190 | * Deleting all topology nodes in table | |
191 | */ | |
7f57883e DS |
192 | void |
193 | eigrp_topology_cleanup(struct list *topology) | |
194 | { | |
195 | assert(topology); | |
196 | ||
197 | eigrp_topology_delete_all(topology); | |
198 | } | |
199 | ||
200 | /* | |
201 | * Adding topology node to topology table | |
202 | */ | |
7f57883e DS |
203 | void |
204 | eigrp_prefix_entry_add(struct list *topology, struct eigrp_prefix_entry *node) | |
205 | { | |
206 | if (listnode_lookup(topology, node) == NULL) | |
207 | { | |
208 | listnode_add_sort(topology, node); | |
209 | } | |
210 | } | |
211 | ||
212 | /* | |
213 | * Adding topology entry to topology node | |
214 | */ | |
7f57883e DS |
215 | void |
216 | eigrp_neighbor_entry_add(struct eigrp_prefix_entry *node, | |
f9e5c9ca | 217 | struct eigrp_neighbor_entry *entry) |
7f57883e DS |
218 | { |
219 | if (listnode_lookup(node->entries, entry) == NULL) | |
220 | { | |
221 | listnode_add_sort(node->entries, entry); | |
222 | entry->prefix = node; | |
223 | } | |
224 | } | |
225 | ||
226 | /* | |
227 | * Deleting topology node from topology table | |
228 | */ | |
7f57883e DS |
229 | void |
230 | eigrp_prefix_entry_delete(struct list *topology, | |
f9e5c9ca | 231 | struct eigrp_prefix_entry *node) |
7f57883e | 232 | { |
703beb67 DS |
233 | struct eigrp *eigrp = eigrp_lookup (); |
234 | ||
235 | /* | |
236 | * Emergency removal of the node from this list. | |
237 | * Whatever it is. | |
238 | */ | |
239 | listnode_delete(eigrp->topology_changes_internalIPV4, node); | |
240 | ||
7f57883e DS |
241 | if (listnode_lookup(topology, node) != NULL) |
242 | { | |
243 | list_delete_all_node(node->entries); | |
244 | list_free(node->entries); | |
245 | list_free(node->rij); | |
246 | listnode_delete(topology, node); | |
247 | XFREE(MTYPE_EIGRP_PREFIX_ENTRY,node); | |
248 | } | |
249 | } | |
250 | ||
251 | /* | |
252 | * Deleting topology entry from topology node | |
253 | */ | |
7f57883e DS |
254 | void |
255 | eigrp_neighbor_entry_delete(struct eigrp_prefix_entry *node, | |
f9e5c9ca | 256 | struct eigrp_neighbor_entry *entry) |
7f57883e DS |
257 | { |
258 | if (listnode_lookup(node->entries, entry) != NULL) | |
259 | { | |
260 | listnode_delete(node->entries, entry); | |
261 | XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY,entry); | |
262 | } | |
263 | } | |
264 | ||
265 | /* | |
266 | * Deleting all nodes from topology table | |
267 | */ | |
7f57883e DS |
268 | void |
269 | eigrp_topology_delete_all(struct list *topology) | |
270 | { | |
271 | list_delete_all_node(topology); | |
272 | } | |
273 | ||
274 | /* | |
275 | * Return 0 if topology is not empty | |
276 | * otherwise return 1 | |
277 | */ | |
7f57883e DS |
278 | unsigned int |
279 | eigrp_topology_table_isempty(struct list *topology) | |
280 | { | |
281 | if (topology->count) | |
282 | return 1; | |
283 | else | |
284 | return 0; | |
285 | } | |
286 | ||
287 | struct eigrp_prefix_entry * | |
288 | eigrp_topology_table_lookup_ipv4(struct list *topology_table, | |
f9e5c9ca | 289 | struct prefix_ipv4 * address) |
7f57883e DS |
290 | { |
291 | struct eigrp_prefix_entry *data; | |
292 | struct listnode *node; | |
293 | for (ALL_LIST_ELEMENTS_RO(topology_table, node, data)) | |
294 | { | |
7f57883e DS |
295 | if ((data->af == AF_INET) |
296 | && (data->destination_ipv4->prefix.s_addr == address->prefix.s_addr) | |
297 | && (data->destination_ipv4->prefixlen == address->prefixlen)) | |
298 | return data; | |
299 | } | |
300 | ||
301 | return NULL; | |
302 | } | |
f6709c16 | 303 | |
2118601d DS |
304 | /* |
305 | * For a future optimization, put the successor list into it's | |
306 | * own separate list from the full list? | |
307 | * | |
308 | * That way we can clean up all the list_new and list_delete's | |
309 | * that we are doing. DBS | |
310 | */ | |
7f57883e DS |
311 | struct list * |
312 | eigrp_topology_get_successor(struct eigrp_prefix_entry *table_node) | |
313 | { | |
314 | struct list *successors = list_new(); | |
7f57883e DS |
315 | struct eigrp_neighbor_entry *data; |
316 | struct listnode *node1, *node2; | |
03f0bd35 | 317 | |
7f57883e DS |
318 | for (ALL_LIST_ELEMENTS(table_node->entries, node1, node2, data)) |
319 | { | |
320 | if (data->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) | |
321 | { | |
322 | listnode_add(successors, data); | |
323 | } | |
324 | } | |
325 | ||
f6709c16 DS |
326 | /* |
327 | * If we have no successors return NULL | |
328 | */ | |
329 | if (!successors->count) | |
330 | { | |
331 | list_delete(successors); | |
332 | successors = NULL; | |
333 | } | |
334 | ||
7f57883e DS |
335 | return successors; |
336 | } | |
337 | ||
962251ae DS |
338 | struct list * |
339 | eigrp_topology_get_successor_max(struct eigrp_prefix_entry *table_node, | |
f9e5c9ca | 340 | unsigned int maxpaths) |
962251ae DS |
341 | { |
342 | struct list *successors = eigrp_topology_get_successor(table_node); | |
f9e5c9ca | 343 | |
962251ae DS |
344 | if (successors && successors->count > maxpaths) |
345 | { | |
346 | do | |
f9e5c9ca DS |
347 | { |
348 | struct listnode *node = listtail(successors); | |
962251ae | 349 | |
f9e5c9ca | 350 | list_delete_node(successors, node); |
962251ae | 351 | |
f9e5c9ca | 352 | } while (successors->count > maxpaths); |
962251ae DS |
353 | } |
354 | ||
355 | return successors; | |
356 | } | |
357 | ||
7f57883e DS |
358 | struct eigrp_neighbor_entry * |
359 | eigrp_prefix_entry_lookup(struct list *entries, struct eigrp_neighbor *nbr) | |
360 | { | |
361 | struct eigrp_neighbor_entry *data; | |
362 | struct listnode *node, *nnode; | |
363 | for (ALL_LIST_ELEMENTS(entries, node, nnode, data)) | |
364 | { | |
365 | if (data->adv_router == nbr) | |
366 | { | |
367 | return data; | |
368 | } | |
369 | } | |
370 | ||
371 | return NULL; | |
372 | } | |
373 | ||
374 | /* Lookup all prefixes from specified neighbor */ | |
375 | struct list * | |
376 | eigrp_neighbor_prefixes_lookup(struct eigrp *eigrp, struct eigrp_neighbor *nbr) | |
377 | { | |
378 | struct listnode *node1, *node11, *node2, *node22; | |
379 | struct eigrp_prefix_entry *prefix; | |
380 | struct eigrp_neighbor_entry *entry; | |
381 | ||
382 | /* create new empty list for prefixes storage */ | |
383 | struct list *prefixes = list_new(); | |
384 | ||
385 | /* iterate over all prefixes in topology table */ | |
386 | for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) | |
387 | { | |
f9e5c9ca | 388 | /* iterate over all neighbor entry in prefix */ |
7f57883e DS |
389 | for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) |
390 | { | |
f9e5c9ca | 391 | /* if entry is from specified neighbor, add to list */ |
7f57883e DS |
392 | if (entry->adv_router == nbr) |
393 | { | |
f9e5c9ca | 394 | listnode_add(prefixes, prefix); |
7f57883e DS |
395 | } |
396 | } | |
397 | } | |
398 | ||
399 | /* return list of prefixes from specified neighbor */ | |
400 | return prefixes; | |
401 | } | |
402 | ||
403 | int | |
404 | eigrp_topology_update_distance(struct eigrp_fsm_action_message *msg) | |
405 | { | |
406 | struct eigrp *eigrp = msg->eigrp; | |
407 | struct eigrp_prefix_entry *prefix = msg->prefix; | |
408 | struct eigrp_neighbor_entry *entry = msg->entry; | |
409 | int change = 0; | |
410 | assert(entry); | |
411 | ||
412 | struct TLV_IPv4_External_type *ext_data = NULL; | |
413 | struct TLV_IPv4_Internal_type *int_data = NULL; | |
414 | if (msg->data_type == EIGRP_TLV_IPv4_INT) | |
415 | { | |
416 | int_data = msg->data.ipv4_int_type; | |
417 | if (eigrp_metrics_is_same(&int_data->metric,&entry->reported_metric)) | |
418 | { | |
419 | return 0; // No change | |
420 | } | |
421 | change = | |
f9e5c9ca DS |
422 | entry->reported_distance |
423 | < eigrp_calculate_metrics(eigrp, &int_data->metric) ? 1 : | |
7f57883e | 424 | entry->reported_distance |
f9e5c9ca | 425 | > eigrp_calculate_metrics(eigrp, &int_data->metric) ? 2 : 3; // Increase : Decrease : No change |
7f57883e | 426 | entry->reported_metric = int_data->metric; |
f9e5c9ca DS |
427 | entry->reported_distance = |
428 | eigrp_calculate_metrics(eigrp, &int_data->metric); | |
7f57883e DS |
429 | entry->distance = eigrp_calculate_total_metrics(eigrp, entry); |
430 | } | |
431 | else | |
432 | { | |
433 | ext_data = msg->data.ipv4_ext_data; | |
434 | if (eigrp_metrics_is_same (&ext_data->metric, &entry->reported_metric)) | |
f9e5c9ca | 435 | return 0; |
7f57883e DS |
436 | } |
437 | /* | |
438 | * Move to correct position in list according to new distance | |
439 | */ | |
440 | listnode_delete(prefix->entries, entry); | |
441 | listnode_add_sort(prefix->entries, entry); | |
442 | ||
443 | return change; | |
444 | } | |
445 | ||
446 | void | |
447 | eigrp_topology_update_all_node_flags(struct eigrp *eigrp) | |
448 | { | |
449 | struct list *table = eigrp->topology_table; | |
450 | struct eigrp_prefix_entry *data; | |
451 | struct listnode *node, *nnode; | |
452 | for (ALL_LIST_ELEMENTS(table, node, nnode, data)) | |
453 | { | |
454 | eigrp_topology_update_node_flags(data); | |
455 | } | |
456 | } | |
457 | ||
458 | void | |
459 | eigrp_topology_update_node_flags(struct eigrp_prefix_entry *dest) | |
460 | { | |
461 | struct listnode *node; | |
462 | struct eigrp_neighbor_entry *entry; | |
463 | struct eigrp * eigrp = eigrp_lookup(); | |
464 | ||
465 | for (ALL_LIST_ELEMENTS_RO(dest->entries, node, entry)) | |
466 | { | |
7aeab9b5 | 467 | if ((entry->distance <= (u_int64_t)(dest->distance*eigrp->variance)) && |
f9e5c9ca | 468 | entry->distance != EIGRP_MAX_METRIC) // is successor |
7f57883e DS |
469 | { |
470 | entry->flags |= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG; | |
9f56205c | 471 | entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG; |
7f57883e DS |
472 | } |
473 | else if (entry->reported_distance < dest->fdistance) // is feasible successor | |
474 | { | |
475 | entry->flags |= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG; | |
9f56205c | 476 | entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG; |
7f57883e DS |
477 | } |
478 | else | |
479 | { | |
9f56205c | 480 | entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG; |
f9e5c9ca DS |
481 | entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG; |
482 | } | |
7f57883e DS |
483 | } |
484 | } | |
485 | ||
486 | void | |
487 | eigrp_update_routing_table(struct eigrp_prefix_entry * prefix) | |
488 | { | |
962251ae DS |
489 | struct eigrp *eigrp = eigrp_lookup(); |
490 | struct list *successors = eigrp_topology_get_successor_max(prefix, eigrp->max_paths); | |
7f57883e DS |
491 | struct listnode *node; |
492 | struct eigrp_neighbor_entry *entry; | |
493 | ||
2118601d | 494 | if (successors) |
7f57883e | 495 | { |
2118601d DS |
496 | eigrp_zebra_route_add(prefix->destination_ipv4, successors); |
497 | for (ALL_LIST_ELEMENTS_RO (successors, node, entry)) | |
f9e5c9ca | 498 | entry->flags |= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG; |
2118601d DS |
499 | |
500 | list_delete(successors); | |
501 | } | |
502 | else | |
503 | { | |
504 | eigrp_zebra_route_delete(prefix->destination_ipv4); | |
505 | for (ALL_LIST_ELEMENTS_RO (prefix->entries, node, entry)) | |
f9e5c9ca | 506 | entry->flags &= ~EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG; |
7f57883e DS |
507 | } |
508 | } | |
509 | ||
510 | void | |
511 | eigrp_topology_neighbor_down(struct eigrp *eigrp, struct eigrp_neighbor * nbr) | |
512 | { | |
513 | struct listnode *node1, *node11, *node2, *node22; | |
514 | struct eigrp_prefix_entry *prefix; | |
515 | struct eigrp_neighbor_entry *entry; | |
516 | ||
517 | for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) | |
518 | { | |
519 | for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) | |
520 | { | |
521 | if (entry->adv_router == nbr) | |
522 | { | |
523 | struct eigrp_fsm_action_message *msg; | |
524 | msg = XCALLOC(MTYPE_EIGRP_FSM_MSG, | |
f9e5c9ca | 525 | sizeof(struct eigrp_fsm_action_message)); |
7f57883e DS |
526 | struct TLV_IPv4_Internal_type * tlv = eigrp_IPv4_InternalTLV_new(); |
527 | tlv->metric.delay = EIGRP_MAX_METRIC; | |
528 | msg->packet_type = EIGRP_OPC_UPDATE; | |
529 | msg->eigrp = eigrp; | |
530 | msg->data_type = EIGRP_TLV_IPv4_INT; | |
531 | msg->adv_router = nbr; | |
532 | msg->data.ipv4_int_type = tlv; | |
533 | msg->entry = entry; | |
534 | msg->prefix = prefix; | |
535 | int event = eigrp_get_fsm_event(msg); | |
536 | eigrp_fsm_event(msg, event); | |
537 | } | |
538 | } | |
539 | } | |
540 | ||
541 | eigrp_query_send_all(eigrp); | |
542 | eigrp_update_send_all(eigrp,nbr->ei); | |
543 | ||
544 | } | |
545 | ||
546 | void | |
547 | eigrp_update_topology_table_prefix(struct list * table, struct eigrp_prefix_entry * prefix) | |
548 | { | |
703beb67 DS |
549 | struct listnode *node1, *node2; |
550 | ||
551 | struct eigrp_neighbor_entry *entry; | |
552 | for (ALL_LIST_ELEMENTS(prefix->entries, node1, node2, entry)) | |
553 | { | |
554 | if(entry->distance == EIGRP_MAX_METRIC) | |
555 | { | |
556 | eigrp_neighbor_entry_delete(prefix,entry); | |
557 | } | |
558 | } | |
559 | if(prefix->distance == EIGRP_MAX_METRIC && prefix->nt != EIGRP_TOPOLOGY_TYPE_CONNECTED) | |
560 | { | |
561 | eigrp_prefix_entry_delete(table,prefix); | |
562 | } | |
7f57883e | 563 | } |