]>
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 | ||
55 | static int | |
56 | eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *, struct eigrp_prefix_entry *); | |
57 | static void | |
58 | eigrp_prefix_entry_del(struct eigrp_prefix_entry *); | |
59 | static int | |
60 | eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *, | |
61 | struct eigrp_neighbor_entry *); | |
62 | ||
63 | /* | |
64 | * asdf;laksdjf;lajsdf;kasdjf;asdjf; | |
65 | * asdfaskdjfa;sdkjf;adlskj | |
66 | * Returns linkedlist used as topology table | |
67 | * cmp - assigned function for comparing topology nodes | |
68 | * del - assigned function executed before deleting topology node by list function | |
69 | */ | |
70 | struct list * | |
71 | eigrp_topology_new() | |
72 | { | |
73 | struct list* new = list_new(); | |
74 | new->cmp = (int | |
75 | (*)(void *, void *)) eigrp_prefix_entry_cmp; | |
76 | new->del = (void | |
77 | (*)(void *)) eigrp_prefix_entry_del; | |
78 | ||
79 | return new; | |
80 | } | |
81 | ||
82 | /* | |
83 | * Topology node comparison | |
84 | */ | |
85 | ||
86 | static int | |
87 | eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *node1, | |
88 | struct eigrp_prefix_entry *node2) | |
89 | { | |
90 | if (node1->af == AF_INET) | |
91 | { | |
92 | if (node2->af == AF_INET) | |
93 | { | |
94 | if (node1->destination_ipv4->prefix.s_addr | |
95 | < node2->destination_ipv4->prefix.s_addr) | |
96 | { | |
97 | return -1; // if it belong above node2 | |
98 | } | |
99 | else | |
100 | { | |
101 | if (node1->destination_ipv4->prefix.s_addr | |
102 | > node2->destination_ipv4->prefix.s_addr) | |
103 | { | |
104 | return 1; //if it belongs under node2 | |
105 | } | |
106 | else | |
107 | { | |
108 | return 0; // same value... ERROR...in case of adding same prefix again | |
109 | } | |
110 | } | |
111 | } | |
112 | else | |
113 | { | |
114 | return 1; | |
115 | } | |
116 | } | |
117 | else | |
118 | { // TODO check if the prefix dont exists | |
119 | return 1; // add to end | |
120 | } | |
121 | } | |
122 | ||
123 | /* | |
124 | * Topology node delete | |
125 | */ | |
126 | ||
127 | static void | |
128 | eigrp_prefix_entry_del(struct eigrp_prefix_entry *node) | |
129 | { | |
130 | list_delete_all_node(node->entries); | |
131 | list_free(node->entries); | |
132 | } | |
133 | ||
134 | /* | |
135 | * Returns new created toplogy node | |
136 | * cmp - assigned function for comparing topology entry | |
137 | */ | |
138 | ||
139 | struct eigrp_prefix_entry * | |
140 | eigrp_prefix_entry_new() | |
141 | { | |
142 | struct eigrp_prefix_entry *new; | |
143 | new = XCALLOC(MTYPE_EIGRP_PREFIX_ENTRY, sizeof(struct eigrp_prefix_entry)); | |
144 | new->entries = list_new(); | |
145 | new->rij = list_new(); | |
146 | new->entries->cmp = (int | |
147 | (*)(void *, void *)) eigrp_neighbor_entry_cmp; | |
148 | new->distance = new->fdistance = new->rdistance = EIGRP_MAX_METRIC; | |
149 | new->destination_ipv4 = NULL; | |
150 | new->destination_ipv6 = NULL; | |
151 | ||
152 | return new; | |
153 | } | |
154 | ||
155 | /* | |
156 | * Topology entry comparison | |
157 | */ | |
158 | ||
159 | static int | |
160 | eigrp_neighbor_entry_cmp(struct eigrp_neighbor_entry *entry1, | |
161 | struct eigrp_neighbor_entry *entry2) | |
162 | { | |
163 | if (entry1->distance < entry2->distance) // parameter used in list_add_sort () | |
164 | return -1; // actually set to sort by distance | |
165 | if (entry1->distance > entry2->distance) | |
166 | return 1; | |
167 | ||
168 | return 0; | |
169 | } | |
170 | ||
171 | /* | |
172 | * Returns new topology entry | |
173 | */ | |
174 | ||
175 | struct eigrp_neighbor_entry * | |
176 | eigrp_neighbor_entry_new() | |
177 | { | |
178 | struct eigrp_neighbor_entry *new; | |
179 | ||
180 | new = XCALLOC(MTYPE_EIGRP_NEIGHBOR_ENTRY, | |
181 | sizeof(struct eigrp_neighbor_entry)); | |
182 | new->reported_distance = EIGRP_MAX_METRIC; | |
183 | new->distance = EIGRP_MAX_METRIC; | |
184 | ||
185 | return new; | |
186 | } | |
187 | ||
188 | /* | |
189 | * Freeing topology table list | |
190 | */ | |
191 | ||
192 | void | |
193 | eigrp_topology_free(struct list *list) | |
194 | { | |
195 | list_free(list); | |
196 | } | |
197 | ||
198 | /* | |
199 | * Deleting all topology nodes in table | |
200 | */ | |
201 | ||
202 | void | |
203 | eigrp_topology_cleanup(struct list *topology) | |
204 | { | |
205 | assert(topology); | |
206 | ||
207 | eigrp_topology_delete_all(topology); | |
208 | } | |
209 | ||
210 | /* | |
211 | * Adding topology node to topology table | |
212 | */ | |
213 | ||
214 | void | |
215 | eigrp_prefix_entry_add(struct list *topology, struct eigrp_prefix_entry *node) | |
216 | { | |
217 | if (listnode_lookup(topology, node) == NULL) | |
218 | { | |
219 | listnode_add_sort(topology, node); | |
220 | } | |
221 | } | |
222 | ||
223 | /* | |
224 | * Adding topology entry to topology node | |
225 | */ | |
226 | ||
227 | void | |
228 | eigrp_neighbor_entry_add(struct eigrp_prefix_entry *node, | |
229 | struct eigrp_neighbor_entry *entry) | |
230 | { | |
231 | if (listnode_lookup(node->entries, entry) == NULL) | |
232 | { | |
233 | listnode_add_sort(node->entries, entry); | |
234 | entry->prefix = node; | |
235 | } | |
236 | } | |
237 | ||
238 | /* | |
239 | * Deleting topology node from topology table | |
240 | */ | |
241 | ||
242 | void | |
243 | eigrp_prefix_entry_delete(struct list *topology, | |
244 | struct eigrp_prefix_entry *node) | |
245 | { | |
246 | if (listnode_lookup(topology, node) != NULL) | |
247 | { | |
248 | list_delete_all_node(node->entries); | |
249 | list_free(node->entries); | |
250 | list_free(node->rij); | |
251 | listnode_delete(topology, node); | |
252 | XFREE(MTYPE_EIGRP_PREFIX_ENTRY,node); | |
253 | } | |
254 | } | |
255 | ||
256 | /* | |
257 | * Deleting topology entry from topology node | |
258 | */ | |
259 | ||
260 | void | |
261 | eigrp_neighbor_entry_delete(struct eigrp_prefix_entry *node, | |
262 | struct eigrp_neighbor_entry *entry) | |
263 | { | |
264 | if (listnode_lookup(node->entries, entry) != NULL) | |
265 | { | |
266 | listnode_delete(node->entries, entry); | |
267 | XFREE(MTYPE_EIGRP_NEIGHBOR_ENTRY,entry); | |
268 | } | |
269 | } | |
270 | ||
271 | /* | |
272 | * Deleting all nodes from topology table | |
273 | */ | |
274 | ||
275 | void | |
276 | eigrp_topology_delete_all(struct list *topology) | |
277 | { | |
278 | list_delete_all_node(topology); | |
279 | } | |
280 | ||
281 | /* | |
282 | * Return 0 if topology is not empty | |
283 | * otherwise return 1 | |
284 | */ | |
285 | ||
286 | unsigned int | |
287 | eigrp_topology_table_isempty(struct list *topology) | |
288 | { | |
289 | if (topology->count) | |
290 | return 1; | |
291 | else | |
292 | return 0; | |
293 | } | |
294 | ||
295 | struct eigrp_prefix_entry * | |
296 | eigrp_topology_table_lookup_ipv4(struct list *topology_table, | |
297 | struct prefix_ipv4 * address) | |
298 | { | |
299 | struct eigrp_prefix_entry *data; | |
300 | struct listnode *node; | |
301 | for (ALL_LIST_ELEMENTS_RO(topology_table, node, data)) | |
302 | { | |
303 | ||
304 | if ((data->af == AF_INET) | |
305 | && (data->destination_ipv4->prefix.s_addr == address->prefix.s_addr) | |
306 | && (data->destination_ipv4->prefixlen == address->prefixlen)) | |
307 | return data; | |
308 | } | |
309 | ||
310 | return NULL; | |
311 | } | |
312 | /* TODO | |
313 | struct eigrp_prefix_entry * | |
314 | eigrp_topology_table_lookup_ipv6 (struct list *topology_table, | |
315 | struct prefix_ipv6 * address) | |
316 | { | |
317 | struct eigrp_prefix_entry *data; | |
318 | struct listnode *node, *nnode; | |
319 | for (ALL_LIST_ELEMENTS (topology_table, node, nnode, data)) | |
320 | { | |
321 | ||
322 | if (comparison) | |
323 | return data; | |
324 | } | |
325 | ||
326 | return NULL; | |
327 | } | |
328 | */ | |
329 | struct list * | |
330 | eigrp_topology_get_successor(struct eigrp_prefix_entry *table_node) | |
331 | { | |
332 | struct list *successors = list_new(); | |
333 | ; | |
334 | struct eigrp_neighbor_entry *data; | |
335 | struct listnode *node1, *node2; | |
336 | for (ALL_LIST_ELEMENTS(table_node->entries, node1, node2, data)) | |
337 | { | |
338 | if (data->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) | |
339 | { | |
340 | listnode_add(successors, data); | |
341 | } | |
342 | } | |
343 | ||
344 | return successors; | |
345 | } | |
346 | ||
347 | /*extern struct eigrp_neighbor_entry * | |
348 | eigrp_topology_get_fsuccessor (struct eigrp_prefix_entry *table_node) | |
349 | { | |
350 | struct eigrp_neighbor_entry *data; | |
351 | struct listnode *node, *nnode; | |
352 | for (ALL_LIST_ELEMENTS (table_node->entries, node, nnode, data)) | |
353 | { | |
354 | if ((data->flags & EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG) == 1) | |
355 | { | |
356 | return data; | |
357 | } | |
358 | } | |
359 | ||
360 | return NULL; | |
361 | }*/ | |
362 | ||
363 | struct eigrp_neighbor_entry * | |
364 | eigrp_prefix_entry_lookup(struct list *entries, struct eigrp_neighbor *nbr) | |
365 | { | |
366 | struct eigrp_neighbor_entry *data; | |
367 | struct listnode *node, *nnode; | |
368 | for (ALL_LIST_ELEMENTS(entries, node, nnode, data)) | |
369 | { | |
370 | if (data->adv_router == nbr) | |
371 | { | |
372 | return data; | |
373 | } | |
374 | } | |
375 | ||
376 | return NULL; | |
377 | } | |
378 | ||
379 | /* Lookup all prefixes from specified neighbor */ | |
380 | struct list * | |
381 | eigrp_neighbor_prefixes_lookup(struct eigrp *eigrp, struct eigrp_neighbor *nbr) | |
382 | { | |
383 | struct listnode *node1, *node11, *node2, *node22; | |
384 | struct eigrp_prefix_entry *prefix; | |
385 | struct eigrp_neighbor_entry *entry; | |
386 | ||
387 | /* create new empty list for prefixes storage */ | |
388 | struct list *prefixes = list_new(); | |
389 | ||
390 | /* iterate over all prefixes in topology table */ | |
391 | for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) | |
392 | { | |
393 | /* iterate over all neighbor entry in prefix */ | |
394 | for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) | |
395 | { | |
396 | /* if entry is from specified neighbor, add to list */ | |
397 | if (entry->adv_router == nbr) | |
398 | { | |
399 | listnode_add(prefixes, prefix); | |
400 | } | |
401 | } | |
402 | } | |
403 | ||
404 | /* return list of prefixes from specified neighbor */ | |
405 | return prefixes; | |
406 | } | |
407 | ||
408 | int | |
409 | eigrp_topology_update_distance(struct eigrp_fsm_action_message *msg) | |
410 | { | |
411 | struct eigrp *eigrp = msg->eigrp; | |
412 | struct eigrp_prefix_entry *prefix = msg->prefix; | |
413 | struct eigrp_neighbor_entry *entry = msg->entry; | |
414 | int change = 0; | |
415 | assert(entry); | |
416 | ||
417 | struct TLV_IPv4_External_type *ext_data = NULL; | |
418 | struct TLV_IPv4_Internal_type *int_data = NULL; | |
419 | if (msg->data_type == EIGRP_TLV_IPv4_INT) | |
420 | { | |
421 | int_data = msg->data.ipv4_int_type; | |
422 | if (eigrp_metrics_is_same(&int_data->metric,&entry->reported_metric)) | |
423 | { | |
424 | return 0; // No change | |
425 | } | |
426 | change = | |
427 | entry->reported_distance | |
428 | < eigrp_calculate_metrics(eigrp, &int_data->metric) ? 1 : | |
429 | entry->reported_distance | |
430 | > eigrp_calculate_metrics(eigrp, &int_data->metric) ? 2 : 3; // Increase : Decrease : No change | |
431 | entry->reported_metric = int_data->metric; | |
432 | entry->reported_distance = eigrp_calculate_metrics(eigrp, | |
433 | &int_data->metric); | |
434 | entry->distance = eigrp_calculate_total_metrics(eigrp, entry); | |
435 | } | |
436 | else | |
437 | { | |
438 | ext_data = msg->data.ipv4_ext_data; | |
439 | if (eigrp_metrics_is_same (&ext_data->metric, &entry->reported_metric)) | |
440 | return 0; | |
441 | } | |
442 | /* | |
443 | * Move to correct position in list according to new distance | |
444 | */ | |
445 | listnode_delete(prefix->entries, entry); | |
446 | listnode_add_sort(prefix->entries, entry); | |
447 | ||
448 | return change; | |
449 | } | |
450 | ||
451 | void | |
452 | eigrp_topology_update_all_node_flags(struct eigrp *eigrp) | |
453 | { | |
454 | struct list *table = eigrp->topology_table; | |
455 | struct eigrp_prefix_entry *data; | |
456 | struct listnode *node, *nnode; | |
457 | for (ALL_LIST_ELEMENTS(table, node, nnode, data)) | |
458 | { | |
459 | eigrp_topology_update_node_flags(data); | |
460 | } | |
461 | } | |
462 | ||
463 | void | |
464 | eigrp_topology_update_node_flags(struct eigrp_prefix_entry *dest) | |
465 | { | |
466 | struct listnode *node; | |
467 | struct eigrp_neighbor_entry *entry; | |
468 | struct eigrp * eigrp = eigrp_lookup(); | |
469 | ||
470 | for (ALL_LIST_ELEMENTS_RO(dest->entries, node, entry)) | |
471 | { | |
472 | if ((entry->distance <= (u_int64_t)(dest->distance*eigrp->variance)) && entry->distance != EIGRP_MAX_METRIC) // is successor | |
473 | { | |
474 | entry->flags |= EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG; | |
475 | entry->flags &= 0xfd; // 1111 1101 set fs flag to zero | |
476 | } | |
477 | else if (entry->reported_distance < dest->fdistance) // is feasible successor | |
478 | { | |
479 | entry->flags |= EIGRP_NEIGHBOR_ENTRY_FSUCCESSOR_FLAG; | |
480 | entry->flags &= 0xfe; // 1111 1110 set successor flag to zero | |
481 | } | |
482 | else | |
483 | { | |
484 | entry->flags &= 0xfc; // 1111 1100 set successor and fs flag to zero | |
485 | } | |
486 | } | |
487 | } | |
488 | ||
489 | void | |
490 | eigrp_update_routing_table(struct eigrp_prefix_entry * prefix) | |
491 | { | |
492 | struct listnode *node; | |
493 | struct eigrp_neighbor_entry *entry; | |
494 | ||
495 | for (ALL_LIST_ELEMENTS_RO(prefix->entries, node, entry)) | |
496 | { | |
497 | if (entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) | |
498 | { | |
499 | if (!(entry->flags & EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG)) | |
500 | { | |
501 | eigrp_zebra_route_add(prefix->destination_ipv4, entry); | |
502 | entry->flags += EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG; | |
503 | } | |
504 | } | |
505 | else if (entry->flags & EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG) | |
506 | { | |
507 | eigrp_zebra_route_delete(prefix->destination_ipv4, entry); | |
508 | entry->flags -= EIGRP_NEIGHBOR_ENTRY_INTABLE_FLAG; | |
509 | } | |
510 | } | |
511 | } | |
512 | ||
513 | void | |
514 | eigrp_topology_neighbor_down(struct eigrp *eigrp, struct eigrp_neighbor * nbr) | |
515 | { | |
516 | struct listnode *node1, *node11, *node2, *node22; | |
517 | struct eigrp_prefix_entry *prefix; | |
518 | struct eigrp_neighbor_entry *entry; | |
519 | ||
520 | for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) | |
521 | { | |
522 | for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) | |
523 | { | |
524 | if (entry->adv_router == nbr) | |
525 | { | |
526 | struct eigrp_fsm_action_message *msg; | |
527 | msg = XCALLOC(MTYPE_EIGRP_FSM_MSG, | |
528 | sizeof(struct eigrp_fsm_action_message)); | |
529 | struct TLV_IPv4_Internal_type * tlv = eigrp_IPv4_InternalTLV_new(); | |
530 | tlv->metric.delay = EIGRP_MAX_METRIC; | |
531 | msg->packet_type = EIGRP_OPC_UPDATE; | |
532 | msg->eigrp = eigrp; | |
533 | msg->data_type = EIGRP_TLV_IPv4_INT; | |
534 | msg->adv_router = nbr; | |
535 | msg->data.ipv4_int_type = tlv; | |
536 | msg->entry = entry; | |
537 | msg->prefix = prefix; | |
538 | int event = eigrp_get_fsm_event(msg); | |
539 | eigrp_fsm_event(msg, event); | |
540 | } | |
541 | } | |
542 | } | |
543 | ||
544 | eigrp_query_send_all(eigrp); | |
545 | eigrp_update_send_all(eigrp,nbr->ei); | |
546 | ||
547 | } | |
548 | ||
549 | void | |
550 | eigrp_update_topology_table_prefix(struct list * table, struct eigrp_prefix_entry * prefix) | |
551 | { | |
552 | struct listnode *node1, *node2; | |
553 | ||
554 | struct eigrp_neighbor_entry *entry; | |
555 | for (ALL_LIST_ELEMENTS(prefix->entries, node1, node2, entry)) | |
556 | { | |
557 | if(entry->distance == EIGRP_MAX_METRIC) | |
558 | { | |
559 | eigrp_neighbor_entry_delete(prefix,entry); | |
560 | } | |
561 | } | |
562 | if(prefix->distance == EIGRP_MAX_METRIC && prefix->nt != EIGRP_TOPOLOGY_TYPE_CONNECTED) | |
563 | { | |
564 | eigrp_prefix_entry_delete(table,prefix); | |
565 | } | |
566 | } | |
567 | /*int | |
568 | eigrp_topology_get_successor_count (struct eigrp_prefix_entry *prefix) | |
569 | { | |
570 | ||
571 | struct listnode *node; | |
572 | struct eigrp_neighbor_entry *entry; | |
573 | ||
574 | int count = 0; | |
575 | ||
576 | for (ALL_LIST_ELEMENTS_RO (prefix->entries,node,entry)) | |
577 | { | |
578 | if ((entry->flags & EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) == EIGRP_NEIGHBOR_ENTRY_SUCCESSOR_FLAG) | |
579 | { | |
580 | count ++; | |
581 | } | |
582 | } | |
583 | ||
584 | return count; | |
585 | } | |
586 | */ |