]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* |
508e53e2 | 2 | * Copyright (C) 2003 Yasuhiro Ohara |
718e3744 | 3 | * |
4 | * This file is part of GNU Zebra. | |
5 | * | |
6 | * GNU Zebra is free software; you can redistribute it and/or modify it | |
7 | * under the terms of the GNU General Public License as published by the | |
8 | * Free Software Foundation; either version 2, or (at your option) any | |
9 | * later version. | |
10 | * | |
11 | * GNU Zebra is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
ac4d0be5 | 17 | * along with GNU Zebra; see the file COPYING. If not, write to the |
18 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 | * Boston, MA 02111-1307, USA. | |
718e3744 | 20 | */ |
508e53e2 | 21 | |
718e3744 | 22 | /* Shortest Path First calculation for OSPFv3 */ |
23 | ||
508e53e2 | 24 | #include <zebra.h> |
718e3744 | 25 | |
508e53e2 | 26 | #include "log.h" |
27 | #include "memory.h" | |
28 | #include "command.h" | |
29 | #include "vty.h" | |
718e3744 | 30 | #include "prefix.h" |
508e53e2 | 31 | #include "pqueue.h" |
32 | #include "linklist.h" | |
33 | #include "thread.h" | |
718e3744 | 34 | |
718e3744 | 35 | #include "ospf6_lsa.h" |
36 | #include "ospf6_lsdb.h" | |
37 | #include "ospf6_route.h" | |
508e53e2 | 38 | #include "ospf6_area.h" |
ca1f4309 DS |
39 | #include "ospf6_proto.h" |
40 | #include "ospf6_abr.h" | |
718e3744 | 41 | #include "ospf6_spf.h" |
508e53e2 | 42 | #include "ospf6_intra.h" |
718e3744 | 43 | #include "ospf6_interface.h" |
049207c3 | 44 | #include "ospf6d.h" |
1f9a9fff | 45 | #include "ospf6_abr.h" |
718e3744 | 46 | |
508e53e2 | 47 | unsigned char conf_debug_ospf6_spf = 0; |
718e3744 | 48 | |
ac4d0be5 | 49 | static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt, |
50 | struct ospf6_vertex *v) | |
c3c0ac83 | 51 | { |
ac4d0be5 | 52 | if (rt && v) |
53 | ospf6_copy_nexthops(rt->nh_list, v->nh_list); | |
c3c0ac83 DS |
54 | } |
55 | ||
ac4d0be5 | 56 | static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt, |
57 | struct ospf6_vertex *v) | |
c3c0ac83 | 58 | { |
ac4d0be5 | 59 | if (rt && v) |
60 | ospf6_merge_nexthops(rt->nh_list, v->nh_list); | |
c3c0ac83 DS |
61 | } |
62 | ||
ac4d0be5 | 63 | static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v) |
c3c0ac83 | 64 | { |
ac4d0be5 | 65 | struct ospf6_nexthop *nh; |
66 | struct listnode *node; | |
67 | ||
68 | if (v) { | |
69 | node = listhead(v->nh_list); | |
70 | if (node) { | |
71 | nh = listgetdata(node); | |
72 | if (nh) | |
73 | return (nh->ifindex); | |
74 | } | |
c3c0ac83 | 75 | } |
ac4d0be5 | 76 | return 0; |
c3c0ac83 DS |
77 | } |
78 | ||
ac4d0be5 | 79 | static int ospf6_vertex_cmp(void *a, void *b) |
718e3744 | 80 | { |
ac4d0be5 | 81 | struct ospf6_vertex *va = (struct ospf6_vertex *)a; |
82 | struct ospf6_vertex *vb = (struct ospf6_vertex *)b; | |
718e3744 | 83 | |
ac4d0be5 | 84 | /* ascending order */ |
85 | if (va->cost != vb->cost) | |
86 | return (va->cost - vb->cost); | |
87 | return (va->hops - vb->hops); | |
718e3744 | 88 | } |
89 | ||
ac4d0be5 | 90 | static int ospf6_vertex_id_cmp(void *a, void *b) |
718e3744 | 91 | { |
ac4d0be5 | 92 | struct ospf6_vertex *va = (struct ospf6_vertex *)a; |
93 | struct ospf6_vertex *vb = (struct ospf6_vertex *)b; | |
94 | int ret = 0; | |
95 | ||
96 | ret = ntohl(ospf6_linkstate_prefix_adv_router(&va->vertex_id)) | |
97 | - ntohl(ospf6_linkstate_prefix_adv_router(&vb->vertex_id)); | |
98 | if (ret) | |
99 | return ret; | |
100 | ||
101 | ret = ntohl(ospf6_linkstate_prefix_id(&va->vertex_id)) | |
102 | - ntohl(ospf6_linkstate_prefix_id(&vb->vertex_id)); | |
103 | return ret; | |
718e3744 | 104 | } |
105 | ||
ac4d0be5 | 106 | static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa) |
718e3744 | 107 | { |
ac4d0be5 | 108 | struct ospf6_vertex *v; |
718e3744 | 109 | |
ac4d0be5 | 110 | v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX, |
111 | sizeof(struct ospf6_vertex)); | |
718e3744 | 112 | |
ac4d0be5 | 113 | /* type */ |
114 | if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) | |
115 | v->type = OSPF6_VERTEX_TYPE_ROUTER; | |
116 | else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) | |
117 | v->type = OSPF6_VERTEX_TYPE_NETWORK; | |
118 | else | |
119 | assert(0); | |
718e3744 | 120 | |
ac4d0be5 | 121 | /* vertex_id */ |
122 | ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id, | |
123 | &v->vertex_id); | |
718e3744 | 124 | |
ac4d0be5 | 125 | /* name */ |
126 | ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name)); | |
718e3744 | 127 | |
ac4d0be5 | 128 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
129 | zlog_debug("%s: Creating vertex %s of type %s", __func__, | |
130 | v->name, | |
131 | ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) | |
132 | ? "Router" | |
133 | : "N/W")); | |
c3c0ac83 | 134 | |
ac4d0be5 | 135 | /* Associated LSA */ |
136 | v->lsa = lsa; | |
718e3744 | 137 | |
ac4d0be5 | 138 | /* capability bits + options */ |
139 | v->capability = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header)); | |
140 | v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 1); | |
141 | v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 2); | |
142 | v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END(lsa->header) + 3); | |
718e3744 | 143 | |
ac4d0be5 | 144 | v->nh_list = list_new(); |
718e3744 | 145 | |
ac4d0be5 | 146 | v->parent = NULL; |
147 | v->child_list = list_new(); | |
148 | v->child_list->cmp = ospf6_vertex_id_cmp; | |
718e3744 | 149 | |
ac4d0be5 | 150 | return v; |
718e3744 | 151 | } |
152 | ||
ac4d0be5 | 153 | static void ospf6_vertex_delete(struct ospf6_vertex *v) |
718e3744 | 154 | { |
916c7e84 | 155 | ospf6_free_nexthops(v->nh_list); |
ac4d0be5 | 156 | list_delete(v->nh_list); |
916c7e84 | 157 | |
ac4d0be5 | 158 | list_delete(v->child_list); |
159 | XFREE(MTYPE_OSPF6_VERTEX, v); | |
718e3744 | 160 | } |
161 | ||
ac4d0be5 | 162 | static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc, |
163 | struct ospf6_vertex *v) | |
718e3744 | 164 | { |
ac4d0be5 | 165 | struct ospf6_lsa *lsa; |
166 | u_int16_t type = 0; | |
167 | u_int32_t id = 0, adv_router = 0; | |
168 | ||
169 | if (VERTEX_IS_TYPE(NETWORK, v)) { | |
170 | type = htons(OSPF6_LSTYPE_ROUTER); | |
171 | id = htonl(0); | |
172 | adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc); | |
173 | } else { | |
174 | if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) { | |
175 | type = htons(OSPF6_LSTYPE_ROUTER); | |
176 | id = htonl(0); | |
177 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc); | |
178 | } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) { | |
179 | type = htons(OSPF6_LSTYPE_NETWORK); | |
180 | id = htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc)); | |
181 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc); | |
182 | } | |
183 | } | |
184 | ||
185 | lsa = ospf6_lsdb_lookup(type, id, adv_router, v->area->lsdb); | |
186 | ||
187 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { | |
188 | char ibuf[16], abuf[16]; | |
189 | inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf)); | |
190 | inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf)); | |
191 | if (lsa) | |
192 | zlog_debug(" Link to: %s", lsa->name); | |
193 | else | |
194 | zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA", | |
195 | ospf6_lstype_name(type), ibuf, abuf); | |
196 | } | |
197 | ||
198 | return lsa; | |
718e3744 | 199 | } |
200 | ||
ac4d0be5 | 201 | static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc, |
202 | struct ospf6_vertex *v) | |
718e3744 | 203 | { |
ac4d0be5 | 204 | caddr_t backlink, found = NULL; |
205 | int size; | |
206 | ||
207 | size = (OSPF6_LSA_IS_TYPE(ROUTER, lsa) | |
208 | ? sizeof(struct ospf6_router_lsdesc) | |
209 | : sizeof(struct ospf6_network_lsdesc)); | |
210 | for (backlink = OSPF6_LSA_HEADER_END(lsa->header) + 4; | |
211 | backlink + size <= OSPF6_LSA_END(lsa->header); backlink += size) { | |
212 | assert(!(OSPF6_LSA_IS_TYPE(NETWORK, lsa) | |
213 | && VERTEX_IS_TYPE(NETWORK, v))); | |
214 | ||
215 | if (OSPF6_LSA_IS_TYPE(NETWORK, lsa) | |
216 | && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink) | |
217 | == v->lsa->header->adv_router) | |
218 | found = backlink; | |
219 | else if (VERTEX_IS_TYPE(NETWORK, v) | |
220 | && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, backlink) | |
221 | && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink) | |
222 | == v->lsa->header->adv_router | |
223 | && ROUTER_LSDESC_GET_NBR_IFID(backlink) | |
224 | == ntohl(v->lsa->header->id)) | |
225 | found = backlink; | |
226 | else { | |
227 | if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, backlink) | |
228 | || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) | |
229 | continue; | |
230 | if (ROUTER_LSDESC_GET_NBR_IFID(backlink) | |
231 | != ROUTER_LSDESC_GET_IFID(lsdesc) | |
232 | || ROUTER_LSDESC_GET_NBR_IFID(lsdesc) | |
233 | != ROUTER_LSDESC_GET_IFID(backlink)) | |
234 | continue; | |
235 | if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink) | |
236 | != v->lsa->header->adv_router | |
237 | || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc) | |
238 | != lsa->header->adv_router) | |
239 | continue; | |
240 | found = backlink; | |
241 | } | |
242 | } | |
243 | ||
244 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
245 | zlog_debug(" Backlink %s", (found ? "OK" : "FAIL")); | |
246 | ||
247 | return found; | |
718e3744 | 248 | } |
249 | ||
ac4d0be5 | 250 | static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v, |
251 | caddr_t lsdesc) | |
718e3744 | 252 | { |
ac4d0be5 | 253 | int i; |
254 | ifindex_t ifindex; | |
255 | struct ospf6_interface *oi; | |
256 | u_int16_t type; | |
257 | u_int32_t adv_router; | |
258 | struct ospf6_lsa *lsa; | |
259 | struct ospf6_link_lsa *link_lsa; | |
260 | char buf[64]; | |
261 | ||
262 | assert(VERTEX_IS_TYPE(ROUTER, w)); | |
263 | ifindex = (VERTEX_IS_TYPE(NETWORK, v) ? ospf6_spf_get_ifindex_from_nh(v) | |
264 | : ROUTER_LSDESC_GET_IFID(lsdesc)); | |
265 | if (ifindex == 0) { | |
266 | zlog_err("No nexthop ifindex at vertex %s", v->name); | |
267 | return; | |
268 | } | |
269 | ||
270 | oi = ospf6_interface_lookup_by_ifindex(ifindex); | |
271 | if (oi == NULL) { | |
272 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
273 | zlog_debug("Can't find interface in SPF: ifindex %d", | |
274 | ifindex); | |
275 | return; | |
276 | } | |
277 | ||
278 | type = htons(OSPF6_LSTYPE_LINK); | |
279 | adv_router = (VERTEX_IS_TYPE(NETWORK, v) | |
280 | ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc) | |
281 | : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc)); | |
282 | ||
283 | i = 0; | |
284 | for (lsa = ospf6_lsdb_type_router_head(type, adv_router, oi->lsdb); lsa; | |
285 | lsa = ospf6_lsdb_type_router_next(type, adv_router, lsa)) { | |
286 | if (VERTEX_IS_TYPE(ROUTER, v) | |
287 | && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc)) | |
288 | != lsa->header->id) | |
289 | continue; | |
290 | ||
291 | link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END( | |
292 | lsa->header); | |
293 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { | |
294 | inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf, | |
295 | sizeof(buf)); | |
296 | zlog_debug(" nexthop %s from %s", buf, lsa->name); | |
297 | } | |
298 | ||
299 | ospf6_add_nexthop(w->nh_list, ifindex, | |
300 | &link_lsa->linklocal_addr); | |
301 | i++; | |
302 | } | |
303 | ||
304 | if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS)) | |
305 | zlog_debug("No nexthop for %s found", w->name); | |
718e3744 | 306 | } |
307 | ||
ac4d0be5 | 308 | static int ospf6_spf_install(struct ospf6_vertex *v, |
309 | struct ospf6_route_table *result_table) | |
718e3744 | 310 | { |
ac4d0be5 | 311 | struct ospf6_route *route, *parent_route; |
312 | struct ospf6_vertex *prev; | |
313 | ||
314 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
315 | zlog_debug("SPF install %s hops %d cost %d", v->name, v->hops, | |
316 | v->cost); | |
317 | ||
318 | route = ospf6_route_lookup(&v->vertex_id, result_table); | |
319 | if (route && route->path.cost < v->cost) { | |
320 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
321 | zlog_debug( | |
322 | " already installed with lower cost (%d), ignore", | |
323 | route->path.cost); | |
324 | ospf6_vertex_delete(v); | |
325 | return -1; | |
326 | } else if (route && route->path.cost == v->cost) { | |
327 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
328 | zlog_debug(" another path found, merge"); | |
329 | ||
330 | ospf6_spf_merge_nexthops_to_route(route, v); | |
331 | ||
332 | prev = (struct ospf6_vertex *)route->route_option; | |
333 | assert(prev->hops <= v->hops); | |
334 | ospf6_vertex_delete(v); | |
335 | ||
336 | return -1; | |
c3c0ac83 | 337 | } |
508e53e2 | 338 | |
ac4d0be5 | 339 | /* There should be no case where candidate being installed (variable |
340 | "v") is closer than the one in the SPF tree (variable "route"). | |
341 | In the case something has gone wrong with the behavior of | |
342 | Priority-Queue. */ | |
343 | ||
344 | /* the case where the route exists already is handled and returned | |
345 | up to here. */ | |
346 | assert(route == NULL); | |
347 | ||
348 | route = ospf6_route_create(); | |
349 | memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix)); | |
350 | route->type = OSPF6_DEST_TYPE_LINKSTATE; | |
351 | route->path.type = OSPF6_PATH_TYPE_INTRA; | |
352 | route->path.origin.type = v->lsa->header->type; | |
353 | route->path.origin.id = v->lsa->header->id; | |
354 | route->path.origin.adv_router = v->lsa->header->adv_router; | |
355 | route->path.metric_type = 1; | |
356 | route->path.cost = v->cost; | |
357 | route->path.u.cost_e2 = v->hops; | |
358 | route->path.router_bits = v->capability; | |
359 | route->path.options[0] = v->options[0]; | |
360 | route->path.options[1] = v->options[1]; | |
361 | route->path.options[2] = v->options[2]; | |
362 | ||
363 | ospf6_spf_copy_nexthops_to_route(route, v); | |
364 | ||
365 | /* | |
366 | * The SPF logic implementation does not transfer the multipathing | |
367 | * properties | |
368 | * of a parent to a child node. Thus if there was a 3-way multipath to a | |
369 | * node's parent and a single hop from the parent to the child, the | |
370 | * logic of | |
371 | * creating new vertices and computing next hops prevents there from | |
372 | * being 3 | |
373 | * paths to the child node. This is primarily because the resolution of | |
374 | * multipath is done in this routine, not in the main spf loop. | |
375 | * | |
376 | * The following logic addresses that problem by merging the parent's | |
377 | * nexthop | |
378 | * information with the child's, if the parent is not the root of the | |
379 | * tree. | |
380 | * This is based on the assumption that before a node's route is | |
381 | * installed, | |
382 | * its parent's route's nexthops have already been installed. | |
383 | */ | |
384 | if (v->parent && v->parent->hops) { | |
385 | parent_route = | |
386 | ospf6_route_lookup(&v->parent->vertex_id, result_table); | |
387 | if (parent_route) { | |
388 | ospf6_route_merge_nexthops(route, parent_route); | |
389 | } | |
390 | } | |
391 | ||
392 | if (v->parent) | |
393 | listnode_add_sort(v->parent->child_list, v); | |
394 | route->route_option = v; | |
508e53e2 | 395 | |
ac4d0be5 | 396 | ospf6_route_add(route, result_table); |
397 | return 0; | |
718e3744 | 398 | } |
399 | ||
ac4d0be5 | 400 | void ospf6_spf_table_finish(struct ospf6_route_table *result_table) |
718e3744 | 401 | { |
ac4d0be5 | 402 | struct ospf6_route *route, *nroute; |
403 | struct ospf6_vertex *v; | |
404 | for (route = ospf6_route_head(result_table); route; route = nroute) { | |
405 | nroute = ospf6_route_next(route); | |
406 | v = (struct ospf6_vertex *)route->route_option; | |
407 | ospf6_vertex_delete(v); | |
408 | ospf6_route_remove(route, result_table); | |
409 | } | |
718e3744 | 410 | } |
411 | ||
ac4d0be5 | 412 | static const char *ospf6_spf_reason_str[] = { |
413 | "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*", | |
414 | }; | |
415 | ||
416 | void ospf6_spf_reason_string(unsigned int reason, char *buf, int size) | |
a0edf674 | 417 | { |
ac4d0be5 | 418 | unsigned int bit; |
419 | int len = 0; | |
420 | ||
421 | if (!buf) | |
422 | return; | |
423 | ||
424 | for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) { | |
425 | if ((reason & (1 << bit)) && (len < size)) { | |
426 | len += snprintf((buf + len), (size - len), "%s%s", | |
427 | (len > 0) ? ", " : "", | |
428 | ospf6_spf_reason_str[bit]); | |
429 | } | |
a0edf674 | 430 | } |
a0edf674 DD |
431 | } |
432 | ||
6452df09 | 433 | /* RFC2328 16.1. Calculating the shortest-path tree for an area */ |
434 | /* RFC2740 3.8.1. Calculating the shortest path tree for an area */ | |
ac4d0be5 | 435 | void ospf6_spf_calculation(u_int32_t router_id, |
436 | struct ospf6_route_table *result_table, | |
437 | struct ospf6_area *oa) | |
508e53e2 | 438 | { |
ac4d0be5 | 439 | struct pqueue *candidate_list; |
440 | struct ospf6_vertex *root, *v, *w; | |
441 | int size; | |
442 | caddr_t lsdesc; | |
443 | struct ospf6_lsa *lsa; | |
444 | struct in6_addr address; | |
445 | ||
446 | ospf6_spf_table_finish(result_table); | |
447 | ||
448 | /* Install the calculating router itself as the root of the SPF tree */ | |
449 | /* construct root vertex */ | |
450 | lsa = ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_ROUTER), htonl(0), router_id, | |
451 | oa->lsdb_self); | |
452 | if (lsa == NULL) { | |
453 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
454 | zlog_debug("%s: No router LSA for area %s\n", __func__, | |
455 | oa->name); | |
456 | return; | |
457 | } | |
458 | ||
459 | /* initialize */ | |
460 | candidate_list = pqueue_create(); | |
461 | candidate_list->cmp = ospf6_vertex_cmp; | |
462 | ||
463 | root = ospf6_vertex_create(lsa); | |
464 | root->area = oa; | |
465 | root->cost = 0; | |
466 | root->hops = 0; | |
467 | inet_pton(AF_INET6, "::1", &address); | |
468 | ||
469 | /* Actually insert root to the candidate-list as the only candidate */ | |
470 | pqueue_enqueue(root, candidate_list); | |
471 | ||
472 | /* Iterate until candidate-list becomes empty */ | |
473 | while (candidate_list->size) { | |
474 | /* get closest candidate from priority queue */ | |
475 | v = pqueue_dequeue(candidate_list); | |
476 | ||
477 | /* installing may result in merging or rejecting of the vertex | |
478 | */ | |
479 | if (ospf6_spf_install(v, result_table) < 0) | |
480 | continue; | |
481 | ||
482 | /* Skip overloaded routers */ | |
483 | if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa) | |
484 | && ospf6_router_is_stub_router(v->lsa))) | |
485 | continue; | |
486 | ||
487 | /* For each LS description in the just-added vertex V's LSA */ | |
488 | size = (VERTEX_IS_TYPE(ROUTER, v) | |
489 | ? sizeof(struct ospf6_router_lsdesc) | |
490 | : sizeof(struct ospf6_network_lsdesc)); | |
491 | for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4; | |
492 | lsdesc + size <= OSPF6_LSA_END(v->lsa->header); | |
493 | lsdesc += size) { | |
494 | lsa = ospf6_lsdesc_lsa(lsdesc, v); | |
495 | if (lsa == NULL) | |
496 | continue; | |
497 | ||
498 | if (OSPF6_LSA_IS_MAXAGE(lsa)) | |
499 | continue; | |
500 | ||
501 | if (!ospf6_lsdesc_backlink(lsa, lsdesc, v)) | |
502 | continue; | |
503 | ||
504 | w = ospf6_vertex_create(lsa); | |
505 | w->area = oa; | |
506 | w->parent = v; | |
507 | if (VERTEX_IS_TYPE(ROUTER, v)) { | |
508 | w->cost = v->cost | |
509 | + ROUTER_LSDESC_GET_METRIC(lsdesc); | |
510 | w->hops = | |
511 | v->hops | |
512 | + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1); | |
513 | } else /* NETWORK */ | |
514 | { | |
515 | w->cost = v->cost; | |
516 | w->hops = v->hops + 1; | |
517 | } | |
518 | ||
519 | /* nexthop calculation */ | |
520 | if (w->hops == 0) | |
521 | ospf6_add_nexthop( | |
522 | w->nh_list, | |
523 | ROUTER_LSDESC_GET_IFID(lsdesc), NULL); | |
524 | else if (w->hops == 1 && v->hops == 0) | |
525 | ospf6_nexthop_calc(w, v, lsdesc); | |
526 | else { | |
527 | ospf6_copy_nexthops(w->nh_list, v->nh_list); | |
528 | } | |
529 | ||
530 | /* add new candidate to the candidate_list */ | |
531 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
532 | zlog_debug( | |
533 | " New candidate: %s hops %d cost %d", | |
534 | w->name, w->hops, w->cost); | |
535 | pqueue_enqueue(w, candidate_list); | |
536 | } | |
537 | } | |
538 | ||
539 | pqueue_delete(candidate_list); | |
540 | ||
541 | oa->spf_calculation++; | |
718e3744 | 542 | } |
543 | ||
ac4d0be5 | 544 | static void ospf6_spf_log_database(struct ospf6_area *oa) |
2680aa2b | 545 | { |
ac4d0be5 | 546 | char *p, *end, buffer[256]; |
547 | struct listnode *node; | |
548 | struct ospf6_interface *oi; | |
549 | ||
550 | p = buffer; | |
551 | end = buffer + sizeof(buffer); | |
552 | ||
553 | snprintf(p, end - p, "SPF on DB (#LSAs):"); | |
554 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end); | |
555 | snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count); | |
556 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end); | |
557 | ||
558 | for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) { | |
559 | snprintf(p, end - p, " I/F %s: %d", oi->interface->name, | |
560 | oi->lsdb->count); | |
561 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) | |
562 | : end); | |
563 | } | |
564 | ||
565 | zlog_debug("%s", buffer); | |
2680aa2b | 566 | } |
567 | ||
ac4d0be5 | 568 | static int ospf6_spf_calculation_thread(struct thread *t) |
718e3744 | 569 | { |
ac4d0be5 | 570 | struct ospf6_area *oa; |
571 | struct ospf6 *ospf6; | |
572 | struct timeval start, end, runtime; | |
573 | struct listnode *node; | |
574 | int areas_processed = 0; | |
575 | char rbuf[32]; | |
576 | ||
577 | ospf6 = (struct ospf6 *)THREAD_ARG(t); | |
578 | ospf6->t_spf_calc = NULL; | |
579 | ||
580 | /* execute SPF calculation */ | |
581 | monotime(&start); | |
582 | ||
583 | if (ospf6_is_router_abr(ospf6)) | |
584 | ospf6_abr_range_reset_cost(ospf6); | |
585 | ||
586 | for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) { | |
587 | ||
588 | if (oa == ospf6->backbone) | |
589 | continue; | |
590 | ||
591 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
592 | zlog_debug("SPF calculation for Area %s", oa->name); | |
593 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
594 | ospf6_spf_log_database(oa); | |
595 | ||
596 | ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa); | |
597 | ospf6_intra_route_calculation(oa); | |
598 | ospf6_intra_brouter_calculation(oa); | |
599 | ||
600 | areas_processed++; | |
601 | } | |
602 | ||
603 | if (ospf6->backbone) { | |
604 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
605 | zlog_debug("SPF calculation for Backbone area %s", | |
606 | ospf6->backbone->name); | |
607 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
608 | ospf6_spf_log_database(ospf6->backbone); | |
609 | ||
610 | ospf6_spf_calculation(ospf6->router_id, | |
611 | ospf6->backbone->spf_table, | |
612 | ospf6->backbone); | |
613 | ospf6_intra_route_calculation(ospf6->backbone); | |
614 | ospf6_intra_brouter_calculation(ospf6->backbone); | |
615 | areas_processed++; | |
616 | } | |
617 | ||
618 | if (ospf6_is_router_abr(ospf6)) | |
619 | ospf6_abr_defaults_to_stub(ospf6); | |
620 | ||
621 | monotime(&end); | |
622 | timersub(&end, &start, &runtime); | |
623 | ||
624 | ospf6->ts_spf_duration = runtime; | |
625 | ||
626 | ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf)); | |
627 | ||
628 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
629 | zlog_debug("SPF runtime: %lld sec %lld usec", | |
630 | (long long)runtime.tv_sec, | |
631 | (long long)runtime.tv_usec); | |
632 | ||
633 | zlog_info( | |
634 | "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, " | |
635 | "Reason: %s\n", | |
636 | areas_processed, (long long)runtime.tv_sec, | |
637 | (long long)runtime.tv_usec, rbuf); | |
638 | ospf6->last_spf_reason = ospf6->spf_reason; | |
639 | ospf6_reset_spf_reason(ospf6); | |
640 | return 0; | |
718e3744 | 641 | } |
642 | ||
3810e06e DD |
643 | /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we |
644 | set timer for SPF calc. */ | |
ac4d0be5 | 645 | void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason) |
718e3744 | 646 | { |
ac4d0be5 | 647 | unsigned long delay, elapsed, ht; |
648 | ||
649 | ospf6_set_spf_reason(ospf6, reason); | |
650 | ||
651 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) { | |
652 | char rbuf[32]; | |
653 | ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf)); | |
654 | zlog_debug("SPF: calculation timer scheduled (reason %s)", | |
655 | rbuf); | |
656 | } | |
657 | ||
658 | /* OSPF instance does not exist. */ | |
659 | if (ospf6 == NULL) | |
660 | return; | |
661 | ||
662 | /* SPF calculation timer is already scheduled. */ | |
663 | if (ospf6->t_spf_calc) { | |
664 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
665 | zlog_debug( | |
666 | "SPF: calculation timer is already scheduled: %p", | |
667 | (void *)ospf6->t_spf_calc); | |
668 | return; | |
669 | } | |
670 | ||
671 | elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL; | |
672 | ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier; | |
673 | ||
674 | if (ht > ospf6->spf_max_holdtime) | |
675 | ht = ospf6->spf_max_holdtime; | |
676 | ||
677 | /* Get SPF calculation delay time. */ | |
678 | if (elapsed < ht) { | |
679 | /* Got an event within the hold time of last SPF. We need to | |
680 | * increase the hold_multiplier, if it's not already at/past | |
681 | * maximum value, and wasn't already increased.. | |
682 | */ | |
683 | if (ht < ospf6->spf_max_holdtime) | |
684 | ospf6->spf_hold_multiplier++; | |
685 | ||
686 | /* always honour the SPF initial delay */ | |
687 | if ((ht - elapsed) < ospf6->spf_delay) | |
688 | delay = ospf6->spf_delay; | |
689 | else | |
690 | delay = ht - elapsed; | |
691 | } else { | |
692 | /* Event is past required hold-time of last SPF */ | |
693 | delay = ospf6->spf_delay; | |
694 | ospf6->spf_hold_multiplier = 1; | |
695 | } | |
696 | ||
697 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
698 | zlog_debug("SPF: calculation timer delay = %ld", delay); | |
699 | ||
700 | zlog_info("SPF: Scheduled in %ld msec", delay); | |
701 | ||
702 | ospf6->t_spf_calc = thread_add_timer_msec( | |
703 | master, ospf6_spf_calculation_thread, ospf6, delay); | |
718e3744 | 704 | } |
705 | ||
ac4d0be5 | 706 | void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest, |
707 | struct ospf6_vertex *v) | |
718e3744 | 708 | { |
ac4d0be5 | 709 | struct listnode *node, *nnode; |
710 | struct ospf6_vertex *c; | |
711 | char *next_prefix; | |
712 | int len; | |
713 | int restnum; | |
714 | ||
715 | /* "prefix" is the space prefix of the display line */ | |
716 | vty_out(vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL); | |
717 | ||
718 | len = strlen(prefix) + 4; | |
719 | next_prefix = (char *)malloc(len); | |
720 | if (next_prefix == NULL) { | |
721 | vty_out(vty, "malloc failed%s", VNL); | |
722 | return; | |
723 | } | |
724 | snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); | |
725 | ||
726 | restnum = listcount(v->child_list); | |
727 | for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) { | |
728 | restnum--; | |
729 | ospf6_spf_display_subtree(vty, next_prefix, restnum, c); | |
730 | } | |
731 | ||
732 | free(next_prefix); | |
718e3744 | 733 | } |
734 | ||
3b68735f | 735 | DEFUN (debug_ospf6_spf_process, |
736 | debug_ospf6_spf_process_cmd, | |
737 | "debug ospf6 spf process", | |
508e53e2 | 738 | DEBUG_STR |
739 | OSPF6_STR | |
740 | "Debug SPF Calculation\n" | |
3b68735f | 741 | "Debug Detailed SPF Process\n" |
508e53e2 | 742 | ) |
718e3744 | 743 | { |
ac4d0be5 | 744 | unsigned char level = 0; |
745 | level = OSPF6_DEBUG_SPF_PROCESS; | |
746 | OSPF6_DEBUG_SPF_ON(level); | |
747 | return CMD_SUCCESS; | |
718e3744 | 748 | } |
749 | ||
3b68735f | 750 | DEFUN (debug_ospf6_spf_time, |
751 | debug_ospf6_spf_time_cmd, | |
752 | "debug ospf6 spf time", | |
508e53e2 | 753 | DEBUG_STR |
718e3744 | 754 | OSPF6_STR |
508e53e2 | 755 | "Debug SPF Calculation\n" |
3b68735f | 756 | "Measure time taken by SPF Calculation\n" |
508e53e2 | 757 | ) |
718e3744 | 758 | { |
ac4d0be5 | 759 | unsigned char level = 0; |
760 | level = OSPF6_DEBUG_SPF_TIME; | |
761 | OSPF6_DEBUG_SPF_ON(level); | |
762 | return CMD_SUCCESS; | |
718e3744 | 763 | } |
764 | ||
2680aa2b | 765 | DEFUN (debug_ospf6_spf_database, |
766 | debug_ospf6_spf_database_cmd, | |
767 | "debug ospf6 spf database", | |
768 | DEBUG_STR | |
769 | OSPF6_STR | |
770 | "Debug SPF Calculation\n" | |
771 | "Log number of LSAs at SPF Calculation time\n" | |
772 | ) | |
773 | { | |
ac4d0be5 | 774 | unsigned char level = 0; |
775 | level = OSPF6_DEBUG_SPF_DATABASE; | |
776 | OSPF6_DEBUG_SPF_ON(level); | |
777 | return CMD_SUCCESS; | |
2680aa2b | 778 | } |
779 | ||
3b68735f | 780 | DEFUN (no_debug_ospf6_spf_process, |
781 | no_debug_ospf6_spf_process_cmd, | |
782 | "no debug ospf6 spf process", | |
508e53e2 | 783 | NO_STR |
784 | DEBUG_STR | |
785 | OSPF6_STR | |
786 | "Quit Debugging SPF Calculation\n" | |
3b68735f | 787 | "Quit Debugging Detailed SPF Process\n" |
508e53e2 | 788 | ) |
718e3744 | 789 | { |
ac4d0be5 | 790 | unsigned char level = 0; |
791 | level = OSPF6_DEBUG_SPF_PROCESS; | |
792 | OSPF6_DEBUG_SPF_OFF(level); | |
793 | return CMD_SUCCESS; | |
718e3744 | 794 | } |
795 | ||
3b68735f | 796 | DEFUN (no_debug_ospf6_spf_time, |
797 | no_debug_ospf6_spf_time_cmd, | |
798 | "no debug ospf6 spf time", | |
508e53e2 | 799 | NO_STR |
800 | DEBUG_STR | |
718e3744 | 801 | OSPF6_STR |
508e53e2 | 802 | "Quit Debugging SPF Calculation\n" |
3b68735f | 803 | "Quit Measuring time taken by SPF Calculation\n" |
508e53e2 | 804 | ) |
718e3744 | 805 | { |
ac4d0be5 | 806 | unsigned char level = 0; |
807 | level = OSPF6_DEBUG_SPF_TIME; | |
808 | OSPF6_DEBUG_SPF_OFF(level); | |
809 | return CMD_SUCCESS; | |
718e3744 | 810 | } |
811 | ||
2680aa2b | 812 | DEFUN (no_debug_ospf6_spf_database, |
813 | no_debug_ospf6_spf_database_cmd, | |
814 | "no debug ospf6 spf database", | |
815 | NO_STR | |
816 | DEBUG_STR | |
817 | OSPF6_STR | |
818 | "Debug SPF Calculation\n" | |
819 | "Quit Logging number of LSAs at SPF Calculation time\n" | |
820 | ) | |
821 | { | |
ac4d0be5 | 822 | unsigned char level = 0; |
823 | level = OSPF6_DEBUG_SPF_DATABASE; | |
824 | OSPF6_DEBUG_SPF_OFF(level); | |
825 | return CMD_SUCCESS; | |
2680aa2b | 826 | } |
827 | ||
ac4d0be5 | 828 | static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay, |
829 | unsigned int hold, unsigned int max) | |
3810e06e | 830 | { |
ac4d0be5 | 831 | VTY_DECLVAR_CONTEXT(ospf6, ospf); |
3810e06e | 832 | |
ac4d0be5 | 833 | ospf->spf_delay = delay; |
834 | ospf->spf_holdtime = hold; | |
835 | ospf->spf_max_holdtime = max; | |
3810e06e | 836 | |
ac4d0be5 | 837 | return CMD_SUCCESS; |
3810e06e DD |
838 | } |
839 | ||
840 | DEFUN (ospf6_timers_throttle_spf, | |
841 | ospf6_timers_throttle_spf_cmd, | |
6147e2c6 | 842 | "timers throttle spf (0-600000) (0-600000) (0-600000)", |
3810e06e DD |
843 | "Adjust routing timers\n" |
844 | "Throttling adaptive timer\n" | |
845 | "OSPF6 SPF timers\n" | |
846 | "Delay (msec) from first change received till SPF calculation\n" | |
847 | "Initial hold time (msec) between consecutive SPF calculations\n" | |
848 | "Maximum hold time (msec)\n") | |
849 | { | |
ac4d0be5 | 850 | int idx_number = 3; |
851 | int idx_number_2 = 4; | |
852 | int idx_number_3 = 5; | |
853 | unsigned int delay, hold, max; | |
854 | ||
855 | VTY_GET_INTEGER_RANGE("SPF delay timer", delay, argv[idx_number]->arg, | |
856 | 0, 600000); | |
857 | VTY_GET_INTEGER_RANGE("SPF hold timer", hold, argv[idx_number_2]->arg, | |
858 | 0, 600000); | |
859 | VTY_GET_INTEGER_RANGE("SPF max-hold timer", max, | |
860 | argv[idx_number_3]->arg, 0, 600000); | |
861 | ||
862 | return ospf6_timers_spf_set(vty, delay, hold, max); | |
3810e06e DD |
863 | } |
864 | ||
865 | DEFUN (no_ospf6_timers_throttle_spf, | |
866 | no_ospf6_timers_throttle_spf_cmd, | |
1d68dbfe | 867 | "no timers throttle spf [(0-600000) (0-600000) (0-600000)]", |
3810e06e DD |
868 | NO_STR |
869 | "Adjust routing timers\n" | |
870 | "Throttling adaptive timer\n" | |
1d68dbfe DW |
871 | "OSPF6 SPF timers\n" |
872 | "Delay (msec) from first change received till SPF calculation\n" | |
873 | "Initial hold time (msec) between consecutive SPF calculations\n" | |
874 | "Maximum hold time (msec)\n") | |
3810e06e | 875 | { |
ac4d0be5 | 876 | return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT, |
877 | OSPF_SPF_HOLDTIME_DEFAULT, | |
878 | OSPF_SPF_MAX_HOLDTIME_DEFAULT); | |
3810e06e DD |
879 | } |
880 | ||
813d4307 | 881 | |
ac4d0be5 | 882 | int config_write_ospf6_debug_spf(struct vty *vty) |
718e3744 | 883 | { |
ac4d0be5 | 884 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
885 | vty_out(vty, "debug ospf6 spf process%s", VNL); | |
886 | if (IS_OSPF6_DEBUG_SPF(TIME)) | |
887 | vty_out(vty, "debug ospf6 spf time%s", VNL); | |
888 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
889 | vty_out(vty, "debug ospf6 spf database%s", VNL); | |
890 | return 0; | |
718e3744 | 891 | } |
892 | ||
ac4d0be5 | 893 | void ospf6_spf_config_write(struct vty *vty) |
3810e06e DD |
894 | { |
895 | ||
ac4d0be5 | 896 | if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT |
897 | || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT | |
898 | || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT) | |
899 | vty_out(vty, " timers throttle spf %d %d %d%s", | |
900 | ospf6->spf_delay, ospf6->spf_holdtime, | |
901 | ospf6->spf_max_holdtime, VTY_NEWLINE); | |
3810e06e DD |
902 | } |
903 | ||
ac4d0be5 | 904 | void install_element_ospf6_debug_spf(void) |
508e53e2 | 905 | { |
ac4d0be5 | 906 | install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd); |
907 | install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd); | |
908 | install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd); | |
909 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd); | |
910 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd); | |
911 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd); | |
912 | install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd); | |
913 | install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd); | |
914 | install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd); | |
915 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd); | |
916 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd); | |
917 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd); | |
508e53e2 | 918 | } |
718e3744 | 919 | |
ac4d0be5 | 920 | void ospf6_spf_init(void) |
718e3744 | 921 | { |
ac4d0be5 | 922 | install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd); |
923 | install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd); | |
718e3744 | 924 | } |