]>
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 | * | |
896014f4 DL |
16 | * You should have received a copy of the GNU General Public License along |
17 | * with this program; see the file COPYING; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
718e3744 | 19 | */ |
508e53e2 | 20 | |
718e3744 | 21 | /* Shortest Path First calculation for OSPFv3 */ |
22 | ||
508e53e2 | 23 | #include <zebra.h> |
718e3744 | 24 | |
508e53e2 | 25 | #include "log.h" |
26 | #include "memory.h" | |
27 | #include "command.h" | |
28 | #include "vty.h" | |
718e3744 | 29 | #include "prefix.h" |
508e53e2 | 30 | #include "pqueue.h" |
31 | #include "linklist.h" | |
32 | #include "thread.h" | |
4ba03be5 | 33 | #include "lib_errors.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 | |
d62a17ae | 49 | static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route *rt, |
50 | struct ospf6_vertex *v) | |
c3c0ac83 | 51 | { |
d62a17ae | 52 | if (rt && v) |
53 | ospf6_copy_nexthops(rt->nh_list, v->nh_list); | |
c3c0ac83 DS |
54 | } |
55 | ||
d62a17ae | 56 | static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route *rt, |
57 | struct ospf6_vertex *v) | |
c3c0ac83 | 58 | { |
d62a17ae | 59 | if (rt && v) |
60 | ospf6_merge_nexthops(rt->nh_list, v->nh_list); | |
c3c0ac83 DS |
61 | } |
62 | ||
d62a17ae | 63 | static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex *v) |
c3c0ac83 | 64 | { |
d62a17ae | 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 | } |
d62a17ae | 76 | return 0; |
c3c0ac83 DS |
77 | } |
78 | ||
d62a17ae | 79 | static int ospf6_vertex_cmp(void *a, void *b) |
718e3744 | 80 | { |
d62a17ae | 81 | struct ospf6_vertex *va = (struct ospf6_vertex *)a; |
82 | struct ospf6_vertex *vb = (struct ospf6_vertex *)b; | |
718e3744 | 83 | |
d62a17ae | 84 | /* ascending order */ |
85 | if (va->cost != vb->cost) | |
86 | return (va->cost - vb->cost); | |
87 | return (va->hops - vb->hops); | |
718e3744 | 88 | } |
89 | ||
d62a17ae | 90 | static int ospf6_vertex_id_cmp(void *a, void *b) |
718e3744 | 91 | { |
d62a17ae | 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 | ||
d62a17ae | 106 | static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa) |
718e3744 | 107 | { |
d62a17ae | 108 | struct ospf6_vertex *v; |
718e3744 | 109 | |
d62a17ae | 110 | v = (struct ospf6_vertex *)XMALLOC(MTYPE_OSPF6_VERTEX, |
111 | sizeof(struct ospf6_vertex)); | |
718e3744 | 112 | |
d62a17ae | 113 | /* type */ |
26e14616 | 114 | if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) { |
d62a17ae | 115 | v->type = OSPF6_VERTEX_TYPE_ROUTER; |
26e14616 CS |
116 | /* Router LSA use Link ID 0 as base in vertex_id */ |
117 | ospf6_linkstate_prefix(lsa->header->adv_router, htonl(0), | |
996c9314 | 118 | &v->vertex_id); |
26e14616 | 119 | } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) { |
d62a17ae | 120 | v->type = OSPF6_VERTEX_TYPE_NETWORK; |
26e14616 CS |
121 | /* vertex_id */ |
122 | ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id, | |
996c9314 | 123 | &v->vertex_id); |
26e14616 CS |
124 | } else |
125 | assert(0); | |
718e3744 | 126 | |
d62a17ae | 127 | /* name */ |
128 | ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name)); | |
718e3744 | 129 | |
d62a17ae | 130 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
26e14616 CS |
131 | zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s", |
132 | __func__, v->name, | |
d62a17ae | 133 | ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) |
134 | ? "Router" | |
996c9314 LB |
135 | : "N/W"), |
136 | ntohs(lsa->header->type), lsa->name); | |
26e14616 | 137 | |
c3c0ac83 | 138 | |
d62a17ae | 139 | /* Associated LSA */ |
140 | v->lsa = lsa; | |
718e3744 | 141 | |
d62a17ae | 142 | /* capability bits + options */ |
d7c0a89a QY |
143 | v->capability = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header)); |
144 | v->options[0] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 1); | |
145 | v->options[1] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 2); | |
146 | v->options[2] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa->header) + 3); | |
718e3744 | 147 | |
d62a17ae | 148 | v->nh_list = list_new(); |
064d4355 | 149 | v->nh_list->cmp = (int (*)(void *, void *))ospf6_nexthop_cmp; |
996c9314 | 150 | v->nh_list->del = (void (*)(void *))ospf6_nexthop_delete; |
718e3744 | 151 | |
d62a17ae | 152 | v->parent = NULL; |
153 | v->child_list = list_new(); | |
154 | v->child_list->cmp = ospf6_vertex_id_cmp; | |
718e3744 | 155 | |
d62a17ae | 156 | return v; |
718e3744 | 157 | } |
158 | ||
d62a17ae | 159 | static void ospf6_vertex_delete(struct ospf6_vertex *v) |
718e3744 | 160 | { |
6a154c88 DL |
161 | list_delete(&v->nh_list); |
162 | list_delete(&v->child_list); | |
d62a17ae | 163 | XFREE(MTYPE_OSPF6_VERTEX, v); |
718e3744 | 164 | } |
165 | ||
d62a17ae | 166 | static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc, |
da086a3b | 167 | struct ospf6_vertex *v) |
718e3744 | 168 | { |
da086a3b | 169 | struct ospf6_lsa *lsa = NULL; |
d7c0a89a QY |
170 | uint16_t type = 0; |
171 | uint32_t id = 0, adv_router = 0; | |
d62a17ae | 172 | |
173 | if (VERTEX_IS_TYPE(NETWORK, v)) { | |
174 | type = htons(OSPF6_LSTYPE_ROUTER); | |
da086a3b | 175 | id = htonl(0); |
d62a17ae | 176 | adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc); |
177 | } else { | |
178 | if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) { | |
179 | type = htons(OSPF6_LSTYPE_ROUTER); | |
da086a3b | 180 | id = htonl(0); |
d62a17ae | 181 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc); |
182 | } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) { | |
183 | type = htons(OSPF6_LSTYPE_NETWORK); | |
184 | id = htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc)); | |
185 | adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc); | |
186 | } | |
187 | } | |
188 | ||
da086a3b CS |
189 | if (type == htons(OSPF6_LSTYPE_NETWORK)) |
190 | lsa = ospf6_lsdb_lookup(type, id, adv_router, v->area->lsdb); | |
191 | else | |
192 | lsa = ospf6_create_single_router_lsa(v->area, v->area->lsdb, | |
193 | adv_router); | |
d62a17ae | 194 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { |
195 | char ibuf[16], abuf[16]; | |
196 | inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf)); | |
197 | inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf)); | |
198 | if (lsa) | |
da086a3b CS |
199 | zlog_debug(" Link to: %s len %u, V %s", lsa->name, |
200 | ntohs(lsa->header->length), v->name); | |
d62a17ae | 201 | else |
da086a3b | 202 | zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s", |
26e14616 | 203 | ospf6_lstype_name(type), ibuf, abuf, |
da086a3b | 204 | v->name); |
d62a17ae | 205 | } |
206 | ||
207 | return lsa; | |
718e3744 | 208 | } |
209 | ||
d62a17ae | 210 | static char *ospf6_lsdesc_backlink(struct ospf6_lsa *lsa, caddr_t lsdesc, |
211 | struct ospf6_vertex *v) | |
718e3744 | 212 | { |
d62a17ae | 213 | caddr_t backlink, found = NULL; |
214 | int size; | |
215 | ||
216 | size = (OSPF6_LSA_IS_TYPE(ROUTER, lsa) | |
217 | ? sizeof(struct ospf6_router_lsdesc) | |
218 | : sizeof(struct ospf6_network_lsdesc)); | |
219 | for (backlink = OSPF6_LSA_HEADER_END(lsa->header) + 4; | |
220 | backlink + size <= OSPF6_LSA_END(lsa->header); backlink += size) { | |
221 | assert(!(OSPF6_LSA_IS_TYPE(NETWORK, lsa) | |
222 | && VERTEX_IS_TYPE(NETWORK, v))); | |
223 | ||
224 | if (OSPF6_LSA_IS_TYPE(NETWORK, lsa) | |
225 | && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink) | |
226 | == v->lsa->header->adv_router) | |
227 | found = backlink; | |
228 | else if (VERTEX_IS_TYPE(NETWORK, v) | |
229 | && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, backlink) | |
230 | && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink) | |
231 | == v->lsa->header->adv_router | |
232 | && ROUTER_LSDESC_GET_NBR_IFID(backlink) | |
233 | == ntohl(v->lsa->header->id)) | |
234 | found = backlink; | |
235 | else { | |
236 | if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, backlink) | |
237 | || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) | |
238 | continue; | |
239 | if (ROUTER_LSDESC_GET_NBR_IFID(backlink) | |
240 | != ROUTER_LSDESC_GET_IFID(lsdesc) | |
241 | || ROUTER_LSDESC_GET_NBR_IFID(lsdesc) | |
242 | != ROUTER_LSDESC_GET_IFID(backlink)) | |
243 | continue; | |
244 | if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink) | |
245 | != v->lsa->header->adv_router | |
246 | || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc) | |
247 | != lsa->header->adv_router) | |
248 | continue; | |
249 | found = backlink; | |
250 | } | |
251 | } | |
252 | ||
253 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
1ba43456 CS |
254 | zlog_debug("Vertex %s Lsa %s Backlink %s", v->name, lsa->name, |
255 | (found ? "OK" : "FAIL")); | |
d62a17ae | 256 | |
257 | return found; | |
718e3744 | 258 | } |
259 | ||
d62a17ae | 260 | static void ospf6_nexthop_calc(struct ospf6_vertex *w, struct ospf6_vertex *v, |
261 | caddr_t lsdesc) | |
718e3744 | 262 | { |
d62a17ae | 263 | int i; |
264 | ifindex_t ifindex; | |
265 | struct ospf6_interface *oi; | |
d7c0a89a QY |
266 | uint16_t type; |
267 | uint32_t adv_router; | |
d62a17ae | 268 | struct ospf6_lsa *lsa; |
269 | struct ospf6_link_lsa *link_lsa; | |
270 | char buf[64]; | |
271 | ||
272 | assert(VERTEX_IS_TYPE(ROUTER, w)); | |
273 | ifindex = (VERTEX_IS_TYPE(NETWORK, v) ? ospf6_spf_get_ifindex_from_nh(v) | |
274 | : ROUTER_LSDESC_GET_IFID(lsdesc)); | |
275 | if (ifindex == 0) { | |
1c50c1c0 QY |
276 | flog_err(EC_LIB_DEVELOPMENT, "No nexthop ifindex at vertex %s", |
277 | v->name); | |
d62a17ae | 278 | return; |
279 | } | |
280 | ||
281 | oi = ospf6_interface_lookup_by_ifindex(ifindex); | |
282 | if (oi == NULL) { | |
283 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
284 | zlog_debug("Can't find interface in SPF: ifindex %d", | |
285 | ifindex); | |
286 | return; | |
287 | } | |
288 | ||
289 | type = htons(OSPF6_LSTYPE_LINK); | |
290 | adv_router = (VERTEX_IS_TYPE(NETWORK, v) | |
291 | ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc) | |
292 | : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc)); | |
293 | ||
294 | i = 0; | |
295 | for (ALL_LSDB_TYPED_ADVRTR(oi->lsdb, type, adv_router, lsa)) { | |
296 | if (VERTEX_IS_TYPE(ROUTER, v) | |
297 | && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc)) | |
298 | != lsa->header->id) | |
299 | continue; | |
300 | ||
301 | link_lsa = (struct ospf6_link_lsa *)OSPF6_LSA_HEADER_END( | |
302 | lsa->header); | |
303 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { | |
304 | inet_ntop(AF_INET6, &link_lsa->linklocal_addr, buf, | |
305 | sizeof(buf)); | |
306 | zlog_debug(" nexthop %s from %s", buf, lsa->name); | |
307 | } | |
308 | ||
309 | ospf6_add_nexthop(w->nh_list, ifindex, | |
310 | &link_lsa->linklocal_addr); | |
311 | i++; | |
312 | } | |
313 | ||
314 | if (i == 0 && IS_OSPF6_DEBUG_SPF(PROCESS)) | |
315 | zlog_debug("No nexthop for %s found", w->name); | |
718e3744 | 316 | } |
317 | ||
d62a17ae | 318 | static int ospf6_spf_install(struct ospf6_vertex *v, |
319 | struct ospf6_route_table *result_table) | |
718e3744 | 320 | { |
d62a17ae | 321 | struct ospf6_route *route, *parent_route; |
322 | struct ospf6_vertex *prev; | |
26e14616 | 323 | char pbuf[PREFIX2STR_BUFFER]; |
d62a17ae | 324 | |
325 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
26e14616 CS |
326 | zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v->name, |
327 | v->lsa->name, v->hops, v->cost); | |
d62a17ae | 328 | |
329 | route = ospf6_route_lookup(&v->vertex_id, result_table); | |
330 | if (route && route->path.cost < v->cost) { | |
331 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
332 | zlog_debug( | |
333 | " already installed with lower cost (%d), ignore", | |
334 | route->path.cost); | |
335 | ospf6_vertex_delete(v); | |
336 | return -1; | |
337 | } else if (route && route->path.cost == v->cost) { | |
26e14616 CS |
338 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { |
339 | prefix2str(&route->prefix, pbuf, sizeof(pbuf)); | |
996c9314 LB |
340 | zlog_debug( |
341 | " another path found to route %s lsa %s, merge", | |
342 | pbuf, v->lsa->name); | |
26e14616 | 343 | } |
d62a17ae | 344 | ospf6_spf_merge_nexthops_to_route(route, v); |
345 | ||
346 | prev = (struct ospf6_vertex *)route->route_option; | |
347 | assert(prev->hops <= v->hops); | |
d62a17ae | 348 | |
996c9314 LB |
349 | if ((VERTEX_IS_TYPE(ROUTER, v) |
350 | && route->path.origin.id != v->lsa->header->id)) { | |
26e14616 | 351 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { |
996c9314 LB |
352 | zlog_debug( |
353 | "%s: V lsa %s id %u, route id %u are different", | |
354 | __PRETTY_FUNCTION__, v->lsa->name, | |
355 | ntohl(v->lsa->header->id), | |
356 | ntohl(route->path.origin.id)); | |
26e14616 CS |
357 | } |
358 | return 0; | |
359 | } | |
360 | ||
361 | ospf6_vertex_delete(v); | |
d62a17ae | 362 | return -1; |
c3c0ac83 | 363 | } |
508e53e2 | 364 | |
d62a17ae | 365 | /* There should be no case where candidate being installed (variable |
366 | "v") is closer than the one in the SPF tree (variable "route"). | |
367 | In the case something has gone wrong with the behavior of | |
368 | Priority-Queue. */ | |
369 | ||
370 | /* the case where the route exists already is handled and returned | |
371 | up to here. */ | |
372 | assert(route == NULL); | |
373 | ||
374 | route = ospf6_route_create(); | |
375 | memcpy(&route->prefix, &v->vertex_id, sizeof(struct prefix)); | |
376 | route->type = OSPF6_DEST_TYPE_LINKSTATE; | |
377 | route->path.type = OSPF6_PATH_TYPE_INTRA; | |
378 | route->path.origin.type = v->lsa->header->type; | |
379 | route->path.origin.id = v->lsa->header->id; | |
380 | route->path.origin.adv_router = v->lsa->header->adv_router; | |
381 | route->path.metric_type = 1; | |
382 | route->path.cost = v->cost; | |
383 | route->path.u.cost_e2 = v->hops; | |
384 | route->path.router_bits = v->capability; | |
385 | route->path.options[0] = v->options[0]; | |
386 | route->path.options[1] = v->options[1]; | |
387 | route->path.options[2] = v->options[2]; | |
388 | ||
389 | ospf6_spf_copy_nexthops_to_route(route, v); | |
390 | ||
391 | /* | |
392 | * The SPF logic implementation does not transfer the multipathing | |
393 | * properties | |
394 | * of a parent to a child node. Thus if there was a 3-way multipath to a | |
395 | * node's parent and a single hop from the parent to the child, the | |
396 | * logic of | |
397 | * creating new vertices and computing next hops prevents there from | |
398 | * being 3 | |
399 | * paths to the child node. This is primarily because the resolution of | |
400 | * multipath is done in this routine, not in the main spf loop. | |
401 | * | |
402 | * The following logic addresses that problem by merging the parent's | |
403 | * nexthop | |
404 | * information with the child's, if the parent is not the root of the | |
405 | * tree. | |
406 | * This is based on the assumption that before a node's route is | |
407 | * installed, | |
408 | * its parent's route's nexthops have already been installed. | |
409 | */ | |
410 | if (v->parent && v->parent->hops) { | |
411 | parent_route = | |
412 | ospf6_route_lookup(&v->parent->vertex_id, result_table); | |
413 | if (parent_route) { | |
414 | ospf6_route_merge_nexthops(route, parent_route); | |
415 | } | |
416 | } | |
417 | ||
418 | if (v->parent) | |
419 | listnode_add_sort(v->parent->child_list, v); | |
420 | route->route_option = v; | |
508e53e2 | 421 | |
d62a17ae | 422 | ospf6_route_add(route, result_table); |
423 | return 0; | |
718e3744 | 424 | } |
425 | ||
d62a17ae | 426 | void ospf6_spf_table_finish(struct ospf6_route_table *result_table) |
718e3744 | 427 | { |
d62a17ae | 428 | struct ospf6_route *route, *nroute; |
429 | struct ospf6_vertex *v; | |
430 | for (route = ospf6_route_head(result_table); route; route = nroute) { | |
431 | nroute = ospf6_route_next(route); | |
432 | v = (struct ospf6_vertex *)route->route_option; | |
433 | ospf6_vertex_delete(v); | |
434 | ospf6_route_remove(route, result_table); | |
435 | } | |
718e3744 | 436 | } |
437 | ||
d62a17ae | 438 | static const char *ospf6_spf_reason_str[] = { |
439 | "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*", | |
440 | }; | |
441 | ||
442 | void ospf6_spf_reason_string(unsigned int reason, char *buf, int size) | |
a0edf674 | 443 | { |
d62a17ae | 444 | unsigned int bit; |
445 | int len = 0; | |
446 | ||
447 | if (!buf) | |
448 | return; | |
449 | ||
450 | for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++) { | |
451 | if ((reason & (1 << bit)) && (len < size)) { | |
452 | len += snprintf((buf + len), (size - len), "%s%s", | |
453 | (len > 0) ? ", " : "", | |
454 | ospf6_spf_reason_str[bit]); | |
455 | } | |
a0edf674 | 456 | } |
a0edf674 DD |
457 | } |
458 | ||
6452df09 | 459 | /* RFC2328 16.1. Calculating the shortest-path tree for an area */ |
460 | /* RFC2740 3.8.1. Calculating the shortest path tree for an area */ | |
d7c0a89a | 461 | void ospf6_spf_calculation(uint32_t router_id, |
d62a17ae | 462 | struct ospf6_route_table *result_table, |
463 | struct ospf6_area *oa) | |
508e53e2 | 464 | { |
d62a17ae | 465 | struct pqueue *candidate_list; |
466 | struct ospf6_vertex *root, *v, *w; | |
467 | int size; | |
468 | caddr_t lsdesc; | |
da086a3b | 469 | struct ospf6_lsa *lsa; |
d62a17ae | 470 | struct in6_addr address; |
471 | ||
472 | ospf6_spf_table_finish(result_table); | |
473 | ||
474 | /* Install the calculating router itself as the root of the SPF tree */ | |
475 | /* construct root vertex */ | |
da086a3b | 476 | lsa = ospf6_create_single_router_lsa(oa, oa->lsdb_self, router_id); |
d62a17ae | 477 | if (lsa == NULL) { |
478 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
479 | zlog_debug("%s: No router LSA for area %s\n", __func__, | |
480 | oa->name); | |
481 | return; | |
482 | } | |
483 | ||
484 | /* initialize */ | |
485 | candidate_list = pqueue_create(); | |
486 | candidate_list->cmp = ospf6_vertex_cmp; | |
487 | ||
488 | root = ospf6_vertex_create(lsa); | |
489 | root->area = oa; | |
490 | root->cost = 0; | |
491 | root->hops = 0; | |
26e14616 | 492 | root->link_id = lsa->header->id; |
d62a17ae | 493 | inet_pton(AF_INET6, "::1", &address); |
494 | ||
495 | /* Actually insert root to the candidate-list as the only candidate */ | |
496 | pqueue_enqueue(root, candidate_list); | |
497 | ||
498 | /* Iterate until candidate-list becomes empty */ | |
499 | while (candidate_list->size) { | |
500 | /* get closest candidate from priority queue */ | |
501 | v = pqueue_dequeue(candidate_list); | |
502 | ||
503 | /* installing may result in merging or rejecting of the vertex | |
504 | */ | |
505 | if (ospf6_spf_install(v, result_table) < 0) | |
506 | continue; | |
507 | ||
508 | /* Skip overloaded routers */ | |
509 | if ((OSPF6_LSA_IS_TYPE(ROUTER, v->lsa) | |
510 | && ospf6_router_is_stub_router(v->lsa))) | |
511 | continue; | |
512 | ||
da086a3b CS |
513 | /* For each LS description in the just-added vertex V's LSA */ |
514 | size = (VERTEX_IS_TYPE(ROUTER, v) | |
515 | ? sizeof(struct ospf6_router_lsdesc) | |
516 | : sizeof(struct ospf6_network_lsdesc)); | |
517 | for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4; | |
518 | lsdesc + size <= OSPF6_LSA_END(v->lsa->header); | |
519 | lsdesc += size) { | |
520 | lsa = ospf6_lsdesc_lsa(lsdesc, v); | |
521 | if (lsa == NULL) | |
522 | continue; | |
523 | ||
524 | if (OSPF6_LSA_IS_MAXAGE(lsa)) | |
525 | continue; | |
526 | ||
527 | if (!ospf6_lsdesc_backlink(lsa, lsdesc, v)) | |
528 | continue; | |
529 | ||
530 | w = ospf6_vertex_create(lsa); | |
531 | w->area = oa; | |
532 | w->parent = v; | |
533 | if (VERTEX_IS_TYPE(ROUTER, v)) { | |
534 | w->cost = v->cost | |
26e14616 | 535 | + ROUTER_LSDESC_GET_METRIC(lsdesc); |
da086a3b CS |
536 | w->hops = |
537 | v->hops | |
538 | + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1); | |
539 | } else { | |
540 | /* NETWORK */ | |
541 | w->cost = v->cost; | |
542 | w->hops = v->hops + 1; | |
543 | } | |
544 | ||
545 | /* nexthop calculation */ | |
546 | if (w->hops == 0) | |
547 | ospf6_add_nexthop( | |
548 | w->nh_list, | |
d62a17ae | 549 | ROUTER_LSDESC_GET_IFID(lsdesc), NULL); |
da086a3b CS |
550 | else if (w->hops == 1 && v->hops == 0) |
551 | ospf6_nexthop_calc(w, v, lsdesc); | |
552 | else | |
553 | ospf6_copy_nexthops(w->nh_list, v->nh_list); | |
554 | ||
555 | ||
556 | /* add new candidate to the candidate_list */ | |
557 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
558 | zlog_debug( | |
d62a17ae | 559 | " New candidate: %s hops %d cost %d", |
996c9314 | 560 | w->name, w->hops, w->cost); |
da086a3b | 561 | pqueue_enqueue(w, candidate_list); |
d62a17ae | 562 | } |
563 | } | |
564 | ||
da086a3b | 565 | |
d62a17ae | 566 | pqueue_delete(candidate_list); |
567 | ||
da086a3b CS |
568 | ospf6_remove_temp_router_lsa(oa); |
569 | ||
d62a17ae | 570 | oa->spf_calculation++; |
718e3744 | 571 | } |
572 | ||
d62a17ae | 573 | static void ospf6_spf_log_database(struct ospf6_area *oa) |
2680aa2b | 574 | { |
d62a17ae | 575 | char *p, *end, buffer[256]; |
576 | struct listnode *node; | |
577 | struct ospf6_interface *oi; | |
578 | ||
579 | p = buffer; | |
580 | end = buffer + sizeof(buffer); | |
581 | ||
582 | snprintf(p, end - p, "SPF on DB (#LSAs):"); | |
583 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end); | |
584 | snprintf(p, end - p, " Area %s: %d", oa->name, oa->lsdb->count); | |
585 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) : end); | |
586 | ||
587 | for (ALL_LIST_ELEMENTS_RO(oa->if_list, node, oi)) { | |
588 | snprintf(p, end - p, " I/F %s: %d", oi->interface->name, | |
589 | oi->lsdb->count); | |
590 | p = (buffer + strlen(buffer) < end ? buffer + strlen(buffer) | |
591 | : end); | |
592 | } | |
593 | ||
594 | zlog_debug("%s", buffer); | |
2680aa2b | 595 | } |
596 | ||
d62a17ae | 597 | static int ospf6_spf_calculation_thread(struct thread *t) |
718e3744 | 598 | { |
d62a17ae | 599 | struct ospf6_area *oa; |
600 | struct ospf6 *ospf6; | |
601 | struct timeval start, end, runtime; | |
602 | struct listnode *node; | |
603 | int areas_processed = 0; | |
604 | char rbuf[32]; | |
605 | ||
606 | ospf6 = (struct ospf6 *)THREAD_ARG(t); | |
607 | ospf6->t_spf_calc = NULL; | |
608 | ||
609 | /* execute SPF calculation */ | |
610 | monotime(&start); | |
ab0f1135 | 611 | ospf6->ts_spf = start; |
d62a17ae | 612 | |
613 | if (ospf6_is_router_abr(ospf6)) | |
614 | ospf6_abr_range_reset_cost(ospf6); | |
615 | ||
616 | for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa)) { | |
617 | ||
618 | if (oa == ospf6->backbone) | |
619 | continue; | |
620 | ||
ab0f1135 | 621 | monotime(&oa->ts_spf); |
d62a17ae | 622 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
623 | zlog_debug("SPF calculation for Area %s", oa->name); | |
624 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
625 | ospf6_spf_log_database(oa); | |
626 | ||
627 | ospf6_spf_calculation(ospf6->router_id, oa->spf_table, oa); | |
628 | ospf6_intra_route_calculation(oa); | |
629 | ospf6_intra_brouter_calculation(oa); | |
630 | ||
631 | areas_processed++; | |
632 | } | |
633 | ||
634 | if (ospf6->backbone) { | |
ab0f1135 | 635 | monotime(&ospf6->backbone->ts_spf); |
d62a17ae | 636 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
637 | zlog_debug("SPF calculation for Backbone area %s", | |
638 | ospf6->backbone->name); | |
639 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
640 | ospf6_spf_log_database(ospf6->backbone); | |
641 | ||
642 | ospf6_spf_calculation(ospf6->router_id, | |
643 | ospf6->backbone->spf_table, | |
644 | ospf6->backbone); | |
645 | ospf6_intra_route_calculation(ospf6->backbone); | |
646 | ospf6_intra_brouter_calculation(ospf6->backbone); | |
647 | areas_processed++; | |
648 | } | |
649 | ||
650 | if (ospf6_is_router_abr(ospf6)) | |
651 | ospf6_abr_defaults_to_stub(ospf6); | |
652 | ||
653 | monotime(&end); | |
654 | timersub(&end, &start, &runtime); | |
655 | ||
656 | ospf6->ts_spf_duration = runtime; | |
657 | ||
658 | ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf)); | |
659 | ||
660 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
661 | zlog_debug("SPF runtime: %lld sec %lld usec", | |
662 | (long long)runtime.tv_sec, | |
663 | (long long)runtime.tv_usec); | |
664 | ||
665 | zlog_info( | |
666 | "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, " | |
667 | "Reason: %s\n", | |
668 | areas_processed, (long long)runtime.tv_sec, | |
669 | (long long)runtime.tv_usec, rbuf); | |
ab0f1135 | 670 | |
d62a17ae | 671 | ospf6->last_spf_reason = ospf6->spf_reason; |
672 | ospf6_reset_spf_reason(ospf6); | |
673 | return 0; | |
718e3744 | 674 | } |
675 | ||
3810e06e DD |
676 | /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we |
677 | set timer for SPF calc. */ | |
d62a17ae | 678 | void ospf6_spf_schedule(struct ospf6 *ospf6, unsigned int reason) |
718e3744 | 679 | { |
d62a17ae | 680 | unsigned long delay, elapsed, ht; |
681 | ||
cac84a16 | 682 | /* OSPF instance does not exist. */ |
683 | if (ospf6 == NULL) | |
684 | return; | |
685 | ||
d62a17ae | 686 | ospf6_set_spf_reason(ospf6, reason); |
687 | ||
688 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) { | |
689 | char rbuf[32]; | |
690 | ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf)); | |
691 | zlog_debug("SPF: calculation timer scheduled (reason %s)", | |
692 | rbuf); | |
693 | } | |
694 | ||
d62a17ae | 695 | /* SPF calculation timer is already scheduled. */ |
696 | if (ospf6->t_spf_calc) { | |
697 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
698 | zlog_debug( | |
699 | "SPF: calculation timer is already scheduled: %p", | |
700 | (void *)ospf6->t_spf_calc); | |
701 | return; | |
702 | } | |
703 | ||
704 | elapsed = monotime_since(&ospf6->ts_spf, NULL) / 1000LL; | |
705 | ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier; | |
706 | ||
707 | if (ht > ospf6->spf_max_holdtime) | |
708 | ht = ospf6->spf_max_holdtime; | |
709 | ||
710 | /* Get SPF calculation delay time. */ | |
711 | if (elapsed < ht) { | |
712 | /* Got an event within the hold time of last SPF. We need to | |
713 | * increase the hold_multiplier, if it's not already at/past | |
714 | * maximum value, and wasn't already increased.. | |
715 | */ | |
716 | if (ht < ospf6->spf_max_holdtime) | |
717 | ospf6->spf_hold_multiplier++; | |
718 | ||
719 | /* always honour the SPF initial delay */ | |
720 | if ((ht - elapsed) < ospf6->spf_delay) | |
721 | delay = ospf6->spf_delay; | |
722 | else | |
723 | delay = ht - elapsed; | |
724 | } else { | |
725 | /* Event is past required hold-time of last SPF */ | |
726 | delay = ospf6->spf_delay; | |
727 | ospf6->spf_hold_multiplier = 1; | |
728 | } | |
729 | ||
730 | if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF(TIME)) | |
731 | zlog_debug("SPF: calculation timer delay = %ld", delay); | |
732 | ||
733 | zlog_info("SPF: Scheduled in %ld msec", delay); | |
734 | ||
735 | ospf6->t_spf_calc = NULL; | |
736 | thread_add_timer_msec(master, ospf6_spf_calculation_thread, ospf6, | |
737 | delay, &ospf6->t_spf_calc); | |
718e3744 | 738 | } |
739 | ||
d62a17ae | 740 | void ospf6_spf_display_subtree(struct vty *vty, const char *prefix, int rest, |
741 | struct ospf6_vertex *v) | |
718e3744 | 742 | { |
d62a17ae | 743 | struct listnode *node, *nnode; |
744 | struct ospf6_vertex *c; | |
745 | char *next_prefix; | |
746 | int len; | |
747 | int restnum; | |
748 | ||
749 | /* "prefix" is the space prefix of the display line */ | |
750 | vty_out(vty, "%s+-%s [%d]\n", prefix, v->name, v->cost); | |
751 | ||
752 | len = strlen(prefix) + 4; | |
753 | next_prefix = (char *)malloc(len); | |
754 | if (next_prefix == NULL) { | |
755 | vty_out(vty, "malloc failed\n"); | |
756 | return; | |
757 | } | |
758 | snprintf(next_prefix, len, "%s%s", prefix, (rest ? "| " : " ")); | |
759 | ||
760 | restnum = listcount(v->child_list); | |
761 | for (ALL_LIST_ELEMENTS(v->child_list, node, nnode, c)) { | |
762 | restnum--; | |
763 | ospf6_spf_display_subtree(vty, next_prefix, restnum, c); | |
764 | } | |
765 | ||
766 | free(next_prefix); | |
718e3744 | 767 | } |
768 | ||
3b68735f | 769 | DEFUN (debug_ospf6_spf_process, |
770 | debug_ospf6_spf_process_cmd, | |
771 | "debug ospf6 spf process", | |
508e53e2 | 772 | DEBUG_STR |
773 | OSPF6_STR | |
774 | "Debug SPF Calculation\n" | |
3b68735f | 775 | "Debug Detailed SPF Process\n" |
508e53e2 | 776 | ) |
718e3744 | 777 | { |
d62a17ae | 778 | unsigned char level = 0; |
779 | level = OSPF6_DEBUG_SPF_PROCESS; | |
780 | OSPF6_DEBUG_SPF_ON(level); | |
781 | return CMD_SUCCESS; | |
718e3744 | 782 | } |
783 | ||
3b68735f | 784 | DEFUN (debug_ospf6_spf_time, |
785 | debug_ospf6_spf_time_cmd, | |
786 | "debug ospf6 spf time", | |
508e53e2 | 787 | DEBUG_STR |
718e3744 | 788 | OSPF6_STR |
508e53e2 | 789 | "Debug SPF Calculation\n" |
3b68735f | 790 | "Measure time taken by SPF Calculation\n" |
508e53e2 | 791 | ) |
718e3744 | 792 | { |
d62a17ae | 793 | unsigned char level = 0; |
794 | level = OSPF6_DEBUG_SPF_TIME; | |
795 | OSPF6_DEBUG_SPF_ON(level); | |
796 | return CMD_SUCCESS; | |
718e3744 | 797 | } |
798 | ||
2680aa2b | 799 | DEFUN (debug_ospf6_spf_database, |
800 | debug_ospf6_spf_database_cmd, | |
801 | "debug ospf6 spf database", | |
802 | DEBUG_STR | |
803 | OSPF6_STR | |
804 | "Debug SPF Calculation\n" | |
805 | "Log number of LSAs at SPF Calculation time\n" | |
806 | ) | |
807 | { | |
d62a17ae | 808 | unsigned char level = 0; |
809 | level = OSPF6_DEBUG_SPF_DATABASE; | |
810 | OSPF6_DEBUG_SPF_ON(level); | |
811 | return CMD_SUCCESS; | |
2680aa2b | 812 | } |
813 | ||
3b68735f | 814 | DEFUN (no_debug_ospf6_spf_process, |
815 | no_debug_ospf6_spf_process_cmd, | |
816 | "no debug ospf6 spf process", | |
508e53e2 | 817 | NO_STR |
818 | DEBUG_STR | |
819 | OSPF6_STR | |
820 | "Quit Debugging SPF Calculation\n" | |
3b68735f | 821 | "Quit Debugging Detailed SPF Process\n" |
508e53e2 | 822 | ) |
718e3744 | 823 | { |
d62a17ae | 824 | unsigned char level = 0; |
825 | level = OSPF6_DEBUG_SPF_PROCESS; | |
826 | OSPF6_DEBUG_SPF_OFF(level); | |
827 | return CMD_SUCCESS; | |
718e3744 | 828 | } |
829 | ||
3b68735f | 830 | DEFUN (no_debug_ospf6_spf_time, |
831 | no_debug_ospf6_spf_time_cmd, | |
832 | "no debug ospf6 spf time", | |
508e53e2 | 833 | NO_STR |
834 | DEBUG_STR | |
718e3744 | 835 | OSPF6_STR |
508e53e2 | 836 | "Quit Debugging SPF Calculation\n" |
3b68735f | 837 | "Quit Measuring time taken by SPF Calculation\n" |
508e53e2 | 838 | ) |
718e3744 | 839 | { |
d62a17ae | 840 | unsigned char level = 0; |
841 | level = OSPF6_DEBUG_SPF_TIME; | |
842 | OSPF6_DEBUG_SPF_OFF(level); | |
843 | return CMD_SUCCESS; | |
718e3744 | 844 | } |
845 | ||
2680aa2b | 846 | DEFUN (no_debug_ospf6_spf_database, |
847 | no_debug_ospf6_spf_database_cmd, | |
848 | "no debug ospf6 spf database", | |
849 | NO_STR | |
850 | DEBUG_STR | |
851 | OSPF6_STR | |
852 | "Debug SPF Calculation\n" | |
853 | "Quit Logging number of LSAs at SPF Calculation time\n" | |
854 | ) | |
855 | { | |
d62a17ae | 856 | unsigned char level = 0; |
857 | level = OSPF6_DEBUG_SPF_DATABASE; | |
858 | OSPF6_DEBUG_SPF_OFF(level); | |
859 | return CMD_SUCCESS; | |
2680aa2b | 860 | } |
861 | ||
d62a17ae | 862 | static int ospf6_timers_spf_set(struct vty *vty, unsigned int delay, |
863 | unsigned int hold, unsigned int max) | |
3810e06e | 864 | { |
d62a17ae | 865 | VTY_DECLVAR_CONTEXT(ospf6, ospf); |
3810e06e | 866 | |
d62a17ae | 867 | ospf->spf_delay = delay; |
868 | ospf->spf_holdtime = hold; | |
869 | ospf->spf_max_holdtime = max; | |
3810e06e | 870 | |
d62a17ae | 871 | return CMD_SUCCESS; |
3810e06e DD |
872 | } |
873 | ||
874 | DEFUN (ospf6_timers_throttle_spf, | |
875 | ospf6_timers_throttle_spf_cmd, | |
6147e2c6 | 876 | "timers throttle spf (0-600000) (0-600000) (0-600000)", |
3810e06e DD |
877 | "Adjust routing timers\n" |
878 | "Throttling adaptive timer\n" | |
879 | "OSPF6 SPF timers\n" | |
880 | "Delay (msec) from first change received till SPF calculation\n" | |
881 | "Initial hold time (msec) between consecutive SPF calculations\n" | |
882 | "Maximum hold time (msec)\n") | |
883 | { | |
d62a17ae | 884 | int idx_number = 3; |
885 | int idx_number_2 = 4; | |
886 | int idx_number_3 = 5; | |
887 | unsigned int delay, hold, max; | |
3810e06e | 888 | |
d62a17ae | 889 | delay = strtoul(argv[idx_number]->arg, NULL, 10); |
890 | hold = strtoul(argv[idx_number_2]->arg, NULL, 10); | |
891 | max = strtoul(argv[idx_number_3]->arg, NULL, 10); | |
3810e06e | 892 | |
d62a17ae | 893 | return ospf6_timers_spf_set(vty, delay, hold, max); |
3810e06e DD |
894 | } |
895 | ||
896 | DEFUN (no_ospf6_timers_throttle_spf, | |
897 | no_ospf6_timers_throttle_spf_cmd, | |
1d68dbfe | 898 | "no timers throttle spf [(0-600000) (0-600000) (0-600000)]", |
3810e06e DD |
899 | NO_STR |
900 | "Adjust routing timers\n" | |
901 | "Throttling adaptive timer\n" | |
1d68dbfe DW |
902 | "OSPF6 SPF timers\n" |
903 | "Delay (msec) from first change received till SPF calculation\n" | |
904 | "Initial hold time (msec) between consecutive SPF calculations\n" | |
905 | "Maximum hold time (msec)\n") | |
3810e06e | 906 | { |
d62a17ae | 907 | return ospf6_timers_spf_set(vty, OSPF_SPF_DELAY_DEFAULT, |
908 | OSPF_SPF_HOLDTIME_DEFAULT, | |
909 | OSPF_SPF_MAX_HOLDTIME_DEFAULT); | |
3810e06e DD |
910 | } |
911 | ||
813d4307 | 912 | |
d62a17ae | 913 | int config_write_ospf6_debug_spf(struct vty *vty) |
718e3744 | 914 | { |
d62a17ae | 915 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) |
916 | vty_out(vty, "debug ospf6 spf process\n"); | |
917 | if (IS_OSPF6_DEBUG_SPF(TIME)) | |
918 | vty_out(vty, "debug ospf6 spf time\n"); | |
919 | if (IS_OSPF6_DEBUG_SPF(DATABASE)) | |
920 | vty_out(vty, "debug ospf6 spf database\n"); | |
921 | return 0; | |
718e3744 | 922 | } |
923 | ||
d62a17ae | 924 | void ospf6_spf_config_write(struct vty *vty) |
3810e06e DD |
925 | { |
926 | ||
d62a17ae | 927 | if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT |
928 | || ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT | |
929 | || ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT) | |
930 | vty_out(vty, " timers throttle spf %d %d %d\n", | |
931 | ospf6->spf_delay, ospf6->spf_holdtime, | |
932 | ospf6->spf_max_holdtime); | |
3810e06e DD |
933 | } |
934 | ||
d62a17ae | 935 | void install_element_ospf6_debug_spf(void) |
508e53e2 | 936 | { |
d62a17ae | 937 | install_element(ENABLE_NODE, &debug_ospf6_spf_process_cmd); |
938 | install_element(ENABLE_NODE, &debug_ospf6_spf_time_cmd); | |
939 | install_element(ENABLE_NODE, &debug_ospf6_spf_database_cmd); | |
940 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_process_cmd); | |
941 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_time_cmd); | |
942 | install_element(ENABLE_NODE, &no_debug_ospf6_spf_database_cmd); | |
943 | install_element(CONFIG_NODE, &debug_ospf6_spf_process_cmd); | |
944 | install_element(CONFIG_NODE, &debug_ospf6_spf_time_cmd); | |
945 | install_element(CONFIG_NODE, &debug_ospf6_spf_database_cmd); | |
946 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_process_cmd); | |
947 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_time_cmd); | |
948 | install_element(CONFIG_NODE, &no_debug_ospf6_spf_database_cmd); | |
508e53e2 | 949 | } |
718e3744 | 950 | |
d62a17ae | 951 | void ospf6_spf_init(void) |
718e3744 | 952 | { |
d62a17ae | 953 | install_element(OSPF6_NODE, &ospf6_timers_throttle_spf_cmd); |
954 | install_element(OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd); | |
718e3744 | 955 | } |
da086a3b CS |
956 | |
957 | /* Create Aggregated Large Router-LSA from multiple Link-State IDs | |
958 | * RFC 5340 A 4.3: | |
959 | * When more than one router-LSA is received from a single router, | |
960 | * the links are processed as if concatenated into a single LSA.*/ | |
961 | struct ospf6_lsa *ospf6_create_single_router_lsa(struct ospf6_area *area, | |
962 | struct ospf6_lsdb *lsdb, | |
963 | uint32_t adv_router) | |
964 | { | |
965 | struct ospf6_lsa *lsa = NULL; | |
966 | struct ospf6_lsa *rtr_lsa = NULL; | |
967 | struct ospf6_lsa_header *lsa_header = NULL; | |
968 | uint8_t *new_header = NULL; | |
969 | const struct route_node *end = NULL; | |
970 | uint16_t lsa_length, total_lsa_length = 0, num_lsa = 0; | |
d7c0a89a | 971 | uint16_t type = 0; |
da086a3b CS |
972 | char ifbuf[16]; |
973 | uint32_t interface_id; | |
974 | caddr_t lsd; | |
975 | ||
996c9314 LB |
976 | lsa_length = sizeof(struct ospf6_lsa_header) |
977 | + sizeof(struct ospf6_router_lsa); | |
da086a3b CS |
978 | total_lsa_length = lsa_length; |
979 | type = htons(OSPF6_LSTYPE_ROUTER); | |
980 | ||
981 | /* First check Aggregated LSA formed earlier in Cache */ | |
982 | lsa = ospf6_lsdb_lookup(type, htonl(0), adv_router, | |
983 | area->temp_router_lsa_lsdb); | |
984 | if (lsa) | |
985 | return lsa; | |
986 | ||
987 | inet_ntop(AF_INET, &adv_router, ifbuf, sizeof(ifbuf)); | |
988 | ||
989 | /* Determine total LSA length from all link state ids */ | |
990 | end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa); | |
991 | while (rtr_lsa) { | |
992 | lsa = rtr_lsa; | |
993 | if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) { | |
994 | rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); | |
995 | continue; | |
996 | } | |
996c9314 LB |
997 | lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header; |
998 | total_lsa_length += (ntohs(lsa_header->length) - lsa_length); | |
da086a3b CS |
999 | num_lsa++; |
1000 | rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); | |
1001 | } | |
1002 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
1003 | zlog_debug("%s: adv_router %s num_lsa %u to convert.", | |
996c9314 | 1004 | __PRETTY_FUNCTION__, ifbuf, num_lsa); |
da086a3b CS |
1005 | if (num_lsa == 1) |
1006 | return lsa; | |
1007 | ||
1008 | if (num_lsa == 0) { | |
1009 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
1010 | zlog_debug("%s: adv_router %s not found in LSDB.", | |
1011 | __PRETTY_FUNCTION__, ifbuf); | |
1012 | return NULL; | |
1013 | } | |
1014 | ||
1015 | /* Allocate memory for this LSA */ | |
1016 | new_header = XMALLOC(MTYPE_OSPF6_LSA_HEADER, total_lsa_length); | |
da086a3b CS |
1017 | |
1018 | /* LSA information structure */ | |
1019 | lsa = (struct ospf6_lsa *)XCALLOC(MTYPE_OSPF6_LSA, | |
1020 | sizeof(struct ospf6_lsa)); | |
da086a3b CS |
1021 | |
1022 | lsa->header = (struct ospf6_lsa_header *)new_header; | |
1023 | ||
1024 | lsa->lsdb = area->temp_router_lsa_lsdb; | |
1025 | ||
1026 | /* Fill Larger LSA Payload */ | |
1027 | end = ospf6_lsdb_head(lsdb, 2, type, adv_router, &rtr_lsa); | |
cf29dab3 DS |
1028 | |
1029 | /* | |
1030 | * We assume at this point in time that rtr_lsa is | |
1031 | * a valid pointer. | |
1032 | */ | |
1033 | assert(rtr_lsa); | |
1034 | if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa)) { | |
1035 | /* Append first Link State ID LSA */ | |
1036 | lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header; | |
1037 | memcpy(new_header, lsa_header, ntohs(lsa_header->length)); | |
1038 | /* Assign new lsa length as aggregated length. */ | |
1039 | ((struct ospf6_lsa_header *)new_header)->length = | |
1040 | htons(total_lsa_length); | |
1041 | new_header += ntohs(lsa_header->length); | |
1042 | num_lsa--; | |
da086a3b CS |
1043 | } |
1044 | ||
1045 | /* Print LSA Name */ | |
1046 | ospf6_lsa_printbuf(lsa, lsa->name, sizeof(lsa->name)); | |
1047 | ||
1048 | rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); | |
1049 | while (rtr_lsa) { | |
1050 | if (OSPF6_LSA_IS_MAXAGE(rtr_lsa)) { | |
1051 | rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); | |
1052 | continue; | |
1053 | } | |
1054 | ||
1055 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) { | |
1056 | lsd = OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4; | |
1057 | interface_id = ROUTER_LSDESC_GET_IFID(lsd); | |
1058 | inet_ntop(AF_INET, &interface_id, ifbuf, sizeof(ifbuf)); | |
996c9314 LB |
1059 | zlog_debug( |
1060 | "%s: Next Router LSA %s to aggreat with len %u interface_id %s", | |
1061 | __PRETTY_FUNCTION__, rtr_lsa->name, | |
1062 | ntohs(lsa_header->length), ifbuf); | |
da086a3b CS |
1063 | } |
1064 | ||
1065 | /* Append Next Link State ID LSA */ | |
996c9314 | 1066 | lsa_header = (struct ospf6_lsa_header *)rtr_lsa->header; |
da086a3b CS |
1067 | memcpy(new_header, (OSPF6_LSA_HEADER_END(rtr_lsa->header) + 4), |
1068 | (ntohs(lsa_header->length) - lsa_length)); | |
1069 | new_header += (ntohs(lsa_header->length) - lsa_length); | |
1070 | num_lsa--; | |
1071 | ||
1072 | rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); | |
1073 | } | |
1074 | ||
1075 | /* Calculate birth of this lsa */ | |
1076 | ospf6_lsa_age_set(lsa); | |
1077 | ||
1078 | /* Store Aggregated LSA into area temp lsdb */ | |
1079 | ospf6_lsdb_add(lsa, area->temp_router_lsa_lsdb); | |
1080 | ||
1081 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
1082 | zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u", | |
1083 | __PRETTY_FUNCTION__, lsa->name, | |
1084 | ntohl(lsa->header->id), ntohs(lsa->header->type), | |
1085 | ntohs(lsa->header->length), num_lsa); | |
1086 | ||
1087 | return lsa; | |
1088 | } | |
1089 | ||
1090 | void ospf6_remove_temp_router_lsa(struct ospf6_area *area) | |
1091 | { | |
1092 | struct ospf6_lsa *lsa = NULL; | |
1093 | ||
1094 | for (ALL_LSDB(area->temp_router_lsa_lsdb, lsa)) { | |
1095 | if (IS_OSPF6_DEBUG_SPF(PROCESS)) | |
996c9314 LB |
1096 | zlog_debug( |
1097 | "%s Remove LSA %s lsa->lock %u lsdb count %u", | |
1098 | __PRETTY_FUNCTION__, lsa->name, lsa->lock, | |
1099 | area->temp_router_lsa_lsdb->count); | |
da086a3b CS |
1100 | ospf6_lsdb_remove(lsa, area->temp_router_lsa_lsdb); |
1101 | } | |
1102 | } |