Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Constraints Shortest Path First algorithms - cspf.c
4 : *
5 : * Author: Olivier Dugeon <olivier.dugeon@orange.com>
6 : *
7 : * Copyright (C) 2022 Orange http://www.orange.com
8 : *
9 : * This file is part of Free Range Routing (FRR).
10 : */
11 :
12 : #include <zebra.h>
13 :
14 : #include "if.h"
15 : #include "linklist.h"
16 : #include "log.h"
17 : #include "hash.h"
18 : #include "memory.h"
19 : #include "prefix.h"
20 : #include "table.h"
21 : #include "stream.h"
22 : #include "printfrr.h"
23 : #include "link_state.h"
24 : #include "cspf.h"
25 :
26 : /* Link State Memory allocation */
27 12 : DEFINE_MTYPE_STATIC(LIB, PCA, "Path Computation Algorithms");
28 :
29 : /**
30 : * Create new Constrained Path. Memory is dynamically allocated.
31 : *
32 : * @param key Vertex key of the destination of this path
33 : *
34 : * @return Pointer to a new Constrained Path structure
35 : */
36 0 : static struct c_path *cpath_new(uint64_t key)
37 : {
38 0 : struct c_path *path;
39 :
40 : /* Sanity Check */
41 0 : if (key == 0)
42 : return NULL;
43 :
44 0 : path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
45 0 : path->dst = key;
46 0 : path->status = IN_PROGRESS;
47 0 : path->edges = list_new();
48 0 : path->weight = MAX_COST;
49 :
50 0 : return path;
51 : }
52 :
53 : /**
54 : * Copy src Constrained Path into dst Constrained Path. A new Constrained Path
55 : * structure is dynamically allocated if dst is NULL. If src is NULL, the
56 : * function return the dst disregarding if it is NULL or not.
57 : *
58 : * @param dest Destination Constrained Path structure
59 : * @param src Source Constrained Path structure
60 : *
61 : * @return Pointer to the destination Constrained Path structure
62 : */
63 0 : static struct c_path *cpath_copy(struct c_path *dest, const struct c_path *src)
64 : {
65 0 : struct c_path *new_path;
66 :
67 0 : if (!src)
68 : return dest;
69 :
70 0 : if (!dest) {
71 0 : new_path = XCALLOC(MTYPE_PCA, sizeof(struct c_path));
72 : } else {
73 0 : new_path = dest;
74 0 : if (dest->edges)
75 0 : list_delete(&new_path->edges);
76 : }
77 :
78 0 : new_path->dst = src->dst;
79 0 : new_path->weight = src->weight;
80 0 : new_path->edges = list_dup(src->edges);
81 0 : new_path->status = src->status;
82 :
83 0 : return new_path;
84 : }
85 :
86 : /**
87 : * Delete Constrained Path structure. Previous allocated memory is freed.
88 : *
89 : * @param path Constrained Path structure to be deleted
90 : */
91 0 : void cpath_del(struct c_path *path)
92 : {
93 0 : if (!path)
94 : return;
95 :
96 0 : if (path->edges)
97 0 : list_delete(&path->edges);
98 :
99 0 : XFREE(MTYPE_PCA, path);
100 0 : path = NULL;
101 : }
102 :
103 : /**
104 : * Replace the list of edges in the next Constrained Path by the list of edges
105 : * in the current Constrained Path.
106 : *
107 : * @param next_path next Constrained Path structure
108 : * @param cur_path current Constrained Path structure
109 : */
110 0 : static void cpath_replace(struct c_path *next_path, struct c_path *cur_path)
111 : {
112 :
113 0 : if (next_path->edges)
114 0 : list_delete(&next_path->edges);
115 :
116 0 : next_path->edges = list_dup(cur_path->edges);
117 0 : }
118 :
119 : /**
120 : * Create a new Visited Node structure from the provided Vertex. Structure is
121 : * dynamically allocated.
122 : *
123 : * @param vertex Vertex structure
124 : *
125 : * @return Pointer to the new Visited Node structure
126 : */
127 0 : static struct v_node *vnode_new(struct ls_vertex *vertex)
128 : {
129 0 : struct v_node *vnode;
130 :
131 0 : if (!vertex)
132 : return NULL;
133 :
134 0 : vnode = XCALLOC(MTYPE_PCA, sizeof(struct v_node));
135 0 : vnode->vertex = vertex;
136 0 : vnode->key = vertex->key;
137 :
138 0 : return vnode;
139 : }
140 :
141 : /**
142 : * Delete Visited Node structure. Previous allocated memory is freed.
143 : *
144 : * @param vnode Visited Node structure to be deleted
145 : */
146 0 : static void vnode_del(struct v_node *vnode)
147 : {
148 0 : if (!vnode)
149 : return;
150 :
151 0 : XFREE(MTYPE_PCA, vnode);
152 0 : vnode = NULL;
153 : }
154 :
155 : /**
156 : * Search Vertex in TED by IPv4 address. The function search vertex by browsing
157 : * the subnets table. It allows to find not only vertex by router ID, but also
158 : * vertex by interface IPv4 address.
159 : *
160 : * @param ted Traffic Engineering Database
161 : * @param ipv4 IPv4 address
162 : *
163 : * @return Vertex if found, NULL otherwise
164 : */
165 0 : static struct ls_vertex *get_vertex_by_ipv4(struct ls_ted *ted,
166 : struct in_addr ipv4)
167 : {
168 0 : struct ls_subnet *subnet;
169 0 : struct prefix p;
170 :
171 0 : p.family = AF_INET;
172 0 : p.u.prefix4 = ipv4;
173 :
174 0 : frr_each (subnets, &ted->subnets, subnet) {
175 0 : if (subnet->key.family != AF_INET)
176 0 : continue;
177 0 : p.prefixlen = subnet->key.prefixlen;
178 0 : if (prefix_same(&subnet->key, &p))
179 0 : return subnet->vertex;
180 : }
181 :
182 : return NULL;
183 : }
184 :
185 : /**
186 : * Search Vertex in TED by IPv6 address. The function search vertex by browsing
187 : * the subnets table. It allows to find not only vertex by router ID, but also
188 : * vertex by interface IPv6 address.
189 : *
190 : * @param ted Traffic Engineering Database
191 : * @param ipv6 IPv6 address
192 : *
193 : * @return Vertex if found, NULL otherwise
194 : */
195 0 : static struct ls_vertex *get_vertex_by_ipv6(struct ls_ted *ted,
196 : struct in6_addr ipv6)
197 : {
198 0 : struct ls_subnet *subnet;
199 0 : struct prefix p;
200 :
201 0 : p.family = AF_INET6;
202 0 : p.u.prefix6 = ipv6;
203 :
204 0 : frr_each (subnets, &ted->subnets, subnet) {
205 0 : if (subnet->key.family != AF_INET6)
206 0 : continue;
207 0 : p.prefixlen = subnet->key.prefixlen;
208 0 : if (prefix_cmp(&subnet->key, &p) == 0)
209 0 : return subnet->vertex;
210 : }
211 :
212 : return NULL;
213 : }
214 :
215 0 : struct cspf *cspf_new(void)
216 : {
217 0 : struct cspf *algo;
218 :
219 : /* Allocate New CSPF structure */
220 0 : algo = XCALLOC(MTYPE_PCA, sizeof(struct cspf));
221 :
222 : /* Initialize RB-Trees */
223 0 : processed_init(&algo->processed);
224 0 : visited_init(&algo->visited);
225 0 : pqueue_init(&algo->pqueue);
226 :
227 0 : algo->path = NULL;
228 0 : algo->pdst = NULL;
229 :
230 0 : return algo;
231 : }
232 :
233 0 : struct cspf *cspf_init(struct cspf *algo, const struct ls_vertex *src,
234 : const struct ls_vertex *dst, struct constraints *csts)
235 : {
236 0 : struct cspf *new_algo;
237 0 : struct c_path *psrc;
238 :
239 0 : if (!csts)
240 : return NULL;
241 :
242 0 : if (!algo)
243 0 : new_algo = cspf_new();
244 : else
245 : new_algo = algo;
246 :
247 : /* Initialize Processed Path and Priority Queue with Src & Dst */
248 0 : if (src) {
249 0 : psrc = cpath_new(src->key);
250 0 : psrc->weight = 0;
251 0 : processed_add(&new_algo->processed, psrc);
252 0 : pqueue_add(&new_algo->pqueue, psrc);
253 0 : new_algo->path = psrc;
254 : }
255 0 : if (dst) {
256 0 : new_algo->pdst = cpath_new(dst->key);
257 0 : processed_add(&new_algo->processed, new_algo->pdst);
258 : }
259 :
260 0 : memcpy(&new_algo->csts, csts, sizeof(struct constraints));
261 :
262 0 : return new_algo;
263 : }
264 :
265 0 : struct cspf *cspf_init_v4(struct cspf *algo, struct ls_ted *ted,
266 : const struct in_addr src, const struct in_addr dst,
267 : struct constraints *csts)
268 : {
269 0 : struct ls_vertex *vsrc;
270 0 : struct ls_vertex *vdst;
271 0 : struct cspf *new_algo;
272 :
273 : /* Sanity Check */
274 0 : if (!ted)
275 : return algo;
276 :
277 0 : if (!algo)
278 0 : new_algo = cspf_new();
279 : else
280 : new_algo = algo;
281 :
282 : /* Got Source and Destination Vertex from TED */
283 0 : vsrc = get_vertex_by_ipv4(ted, src);
284 0 : vdst = get_vertex_by_ipv4(ted, dst);
285 0 : csts->family = AF_INET;
286 :
287 0 : return cspf_init(new_algo, vsrc, vdst, csts);
288 : }
289 :
290 0 : struct cspf *cspf_init_v6(struct cspf *algo, struct ls_ted *ted,
291 : const struct in6_addr src, const struct in6_addr dst,
292 : struct constraints *csts)
293 : {
294 0 : struct ls_vertex *vsrc;
295 0 : struct ls_vertex *vdst;
296 0 : struct cspf *new_algo;
297 :
298 : /* Sanity Check */
299 0 : if (!ted)
300 : return algo;
301 :
302 0 : if (!algo)
303 0 : new_algo = cspf_new();
304 : else
305 : new_algo = algo;
306 :
307 : /* Got Source and Destination Vertex from TED */
308 0 : vsrc = get_vertex_by_ipv6(ted, src);
309 0 : vdst = get_vertex_by_ipv6(ted, dst);
310 0 : csts->family = AF_INET6;
311 :
312 0 : return cspf_init(new_algo, vsrc, vdst, csts);
313 : }
314 :
315 0 : void cspf_clean(struct cspf *algo)
316 : {
317 0 : struct c_path *path;
318 0 : struct v_node *vnode;
319 :
320 0 : if (!algo)
321 : return;
322 :
323 : /* Normally, Priority Queue is empty. Clean it in case of. */
324 0 : if (pqueue_count(&algo->pqueue)) {
325 0 : frr_each_safe (pqueue, &algo->pqueue, path) {
326 0 : pqueue_del(&algo->pqueue, path);
327 : }
328 : }
329 :
330 : /* Empty Processed Path tree and associated Path */
331 0 : if (processed_count(&algo->processed)) {
332 0 : frr_each_safe (processed, &algo->processed, path) {
333 0 : processed_del(&algo->processed, path);
334 0 : if (path == algo->pdst)
335 0 : algo->pdst = NULL;
336 0 : cpath_del(path);
337 : }
338 : }
339 :
340 : /* Empty visited Vertex tree and associated Node */
341 0 : if (visited_count(&algo->visited)) {
342 0 : frr_each_safe (visited, &algo->visited, vnode) {
343 0 : visited_del(&algo->visited, vnode);
344 0 : vnode_del(vnode);
345 : }
346 : }
347 :
348 0 : if (algo->pdst)
349 0 : cpath_del(algo->pdst);
350 :
351 0 : memset(&algo->csts, 0, sizeof(struct constraints));
352 0 : algo->path = NULL;
353 0 : algo->pdst = NULL;
354 : }
355 :
356 0 : void cspf_del(struct cspf *algo)
357 : {
358 0 : if (!algo)
359 : return;
360 :
361 : /* Empty Priority Queue and Processes Path */
362 0 : cspf_clean(algo);
363 :
364 : /* Then, reset Priority Queue, Processed Path and Visited RB-Tree */
365 0 : pqueue_fini(&algo->pqueue);
366 0 : processed_fini(&algo->processed);
367 0 : visited_fini(&algo->visited);
368 :
369 0 : XFREE(MTYPE_PCA, algo);
370 0 : algo = NULL;
371 : }
372 :
373 : /**
374 : * Prune Edge if constraints are not met by testing Edge Attributes against
375 : * given constraints and cumulative cost of the given constrained path.
376 : *
377 : * @param path On-going Computed Path with cumulative cost constraints
378 : * @param edge Edge to be validate against Constraints
379 : * @param csts Constraints for this path
380 : *
381 : * @return True if Edge should be prune, false if Edge is valid
382 : */
383 0 : static bool prune_edge(const struct c_path *path, const struct ls_edge *edge,
384 : const struct constraints *csts)
385 : {
386 0 : struct ls_vertex *dst;
387 0 : struct ls_attributes *attr;
388 :
389 : /* Check that Path, Edge and Constraints are valid */
390 0 : if (!path || !edge || !csts)
391 : return true;
392 :
393 : /* Check that Edge has a valid destination */
394 0 : if (!edge->destination)
395 : return true;
396 0 : dst = edge->destination;
397 :
398 : /* Check that Edge has valid attributes */
399 0 : if (!edge->attributes)
400 : return true;
401 0 : attr = edge->attributes;
402 :
403 : /* Check that Edge belongs to the requested Address Family and type */
404 0 : if (csts->family == AF_INET) {
405 0 : if (IPV4_NET0(attr->standard.local.s_addr))
406 : return true;
407 0 : if (csts->type == SR_TE)
408 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID) ||
409 0 : !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
410 : return true;
411 : }
412 0 : if (csts->family == AF_INET6) {
413 0 : if (IN6_IS_ADDR_UNSPECIFIED(&attr->standard.local6))
414 : return true;
415 0 : if (csts->type == SR_TE)
416 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_ADJ_SID6) ||
417 0 : !CHECK_FLAG(dst->node->flags, LS_NODE_SR))
418 : return true;
419 : }
420 :
421 : /*
422 : * Check that total cost, up to this edge, respects the initial
423 : * constraints
424 : */
425 0 : switch (csts->ctype) {
426 0 : case CSPF_METRIC:
427 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_METRIC))
428 : return true;
429 0 : if ((attr->metric + path->weight) > csts->cost)
430 : return true;
431 : break;
432 :
433 0 : case CSPF_TE_METRIC:
434 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_TE_METRIC))
435 : return true;
436 0 : if ((attr->standard.te_metric + path->weight) > csts->cost)
437 : return true;
438 : break;
439 :
440 0 : case CSPF_DELAY:
441 0 : if (!CHECK_FLAG(attr->flags, LS_ATTR_DELAY))
442 : return true;
443 0 : if ((attr->extended.delay + path->weight) > csts->cost)
444 : return true;
445 : break;
446 : }
447 :
448 : /* If specified, check that Edge meet Bandwidth constraint */
449 0 : if (csts->bw > 0.0) {
450 0 : if (attr->standard.max_bw < csts->bw ||
451 0 : attr->standard.max_rsv_bw < csts->bw ||
452 0 : attr->standard.unrsv_bw[csts->cos] < csts->bw)
453 0 : return true;
454 : }
455 :
456 : /* All is fine. We can consider this Edge valid, so not to be prune */
457 : return false;
458 : }
459 :
460 : /**
461 : * Relax constraints of the current path up to the destination vertex of the
462 : * provided Edge. This function progress in the network topology by validating
463 : * the next vertex on the computed path. If Vertex has not already been visited,
464 : * list of edges of the current path is augmented with this edge if the new cost
465 : * is lower than prior path up to this vertex. Current path is re-inserted in
466 : * the Priority Queue with its new cost i.e. current cost + edge cost.
467 : *
468 : * @param algo CSPF structure
469 : * @param edge Next Edge to be added to the current computed path
470 : *
471 : * @return True if current path reach destination, false otherwise
472 : */
473 0 : static bool relax_constraints(struct cspf *algo, struct ls_edge *edge)
474 : {
475 :
476 0 : struct c_path pkey = {};
477 0 : struct c_path *next_path;
478 0 : struct v_node vnode = {};
479 0 : uint32_t total_cost = MAX_COST;
480 :
481 : /* Verify that we have a current computed path */
482 0 : if (!algo->path)
483 : return false;
484 :
485 : /* Verify if we have not visited the next Vertex to avoid loop */
486 0 : vnode.key = edge->destination->key;
487 0 : if (visited_member(&algo->visited, &vnode)) {
488 : return false;
489 : }
490 :
491 : /*
492 : * Get Next Computed Path from next vertex key
493 : * or create a new one if it has not yet computed.
494 : */
495 0 : pkey.dst = edge->destination->key;
496 0 : next_path = processed_find(&algo->processed, &pkey);
497 0 : if (!next_path) {
498 0 : next_path = cpath_new(pkey.dst);
499 0 : processed_add(&algo->processed, next_path);
500 : }
501 :
502 : /*
503 : * Add or update the Computed Path in the Priority Queue if total cost
504 : * is lower than cost associated to this next Vertex. This could occurs
505 : * if we process a Vertex that as not yet been visited in the Graph
506 : * or if we found a shortest path up to this Vertex.
507 : */
508 0 : switch (algo->csts.ctype) {
509 0 : case CSPF_METRIC:
510 0 : total_cost = edge->attributes->metric + algo->path->weight;
511 0 : break;
512 0 : case CSPF_TE_METRIC:
513 0 : total_cost = edge->attributes->standard.te_metric +
514 0 : algo->path->weight;
515 0 : break;
516 0 : case CSPF_DELAY:
517 0 : total_cost =
518 0 : edge->attributes->extended.delay + algo->path->weight;
519 0 : break;
520 : default:
521 : break;
522 : }
523 0 : if (total_cost < next_path->weight) {
524 : /*
525 : * It is not possible to directly update the q_path in the
526 : * Priority Queue. Indeed, if we modify the path weight, the
527 : * Priority Queue must be re-ordered. So, we need fist to remove
528 : * the q_path if it is present in the Priority Queue, then,
529 : * update the Path, in particular the Weight, and finally
530 : * (re-)insert it in the Priority Queue.
531 : */
532 0 : struct c_path *path;
533 0 : frr_each_safe (pqueue, &algo->pqueue, path) {
534 0 : if (path->dst == pkey.dst) {
535 0 : pqueue_del(&algo->pqueue, path);
536 0 : break;
537 : }
538 : }
539 0 : next_path->weight = total_cost;
540 0 : cpath_replace(next_path, algo->path);
541 0 : listnode_add(next_path->edges, edge);
542 0 : pqueue_add(&algo->pqueue, next_path);
543 : }
544 :
545 : /* Return True if we reach the destination */
546 0 : return (next_path->dst == algo->pdst->dst);
547 : }
548 :
549 0 : struct c_path *compute_p2p_path(struct cspf *algo, struct ls_ted *ted)
550 : {
551 0 : struct listnode *node;
552 0 : struct ls_vertex *vertex;
553 0 : struct ls_edge *edge;
554 0 : struct c_path *optim_path;
555 0 : struct v_node *vnode;
556 0 : uint32_t cur_cost;
557 :
558 0 : optim_path = cpath_new(0xFFFFFFFFFFFFFFFF);
559 0 : optim_path->status = FAILED;
560 :
561 : /* Check that all is correctly initialized */
562 0 : if (!algo)
563 : return optim_path;
564 :
565 0 : if (!algo->csts.ctype)
566 : return optim_path;
567 :
568 0 : if (!algo->pdst) {
569 0 : optim_path->status = NO_DESTINATION;
570 0 : return optim_path;
571 : }
572 :
573 0 : if (!algo->path) {
574 0 : optim_path->status = NO_SOURCE;
575 0 : return optim_path;
576 : }
577 :
578 0 : if (algo->pdst->dst == algo->path->dst) {
579 0 : optim_path->status = SAME_SRC_DST;
580 0 : return optim_path;
581 : }
582 :
583 0 : optim_path->dst = algo->pdst->dst;
584 0 : optim_path->status = IN_PROGRESS;
585 :
586 : /*
587 : * Process all Connected Vertex until priority queue becomes empty.
588 : * Connected Vertices are added into the priority queue when
589 : * processing the next Connected Vertex: see relax_constraints()
590 : */
591 0 : cur_cost = MAX_COST;
592 0 : while (pqueue_count(&algo->pqueue) != 0) {
593 : /* Got shortest current Path from the Priority Queue */
594 0 : algo->path = pqueue_pop(&algo->pqueue);
595 :
596 : /* Add destination Vertex of this path to the visited RB Tree */
597 0 : vertex = ls_find_vertex_by_key(ted, algo->path->dst);
598 0 : if (!vertex)
599 0 : continue;
600 0 : vnode = vnode_new(vertex);
601 0 : visited_add(&algo->visited, vnode);
602 :
603 : /* Process all outgoing links from this Vertex */
604 0 : for (ALL_LIST_ELEMENTS_RO(vertex->outgoing_edges, node, edge)) {
605 : /*
606 : * Skip Connected Edges that must be prune i.e.
607 : * Edges that not satisfy the given constraints,
608 : * in particular the Bandwidth, TE Metric and Delay.
609 : */
610 0 : if (prune_edge(algo->path, edge, &algo->csts))
611 0 : continue;
612 :
613 : /*
614 : * Relax constraints and check if we got a shorter
615 : * candidate path
616 : */
617 0 : if (relax_constraints(algo, edge) &&
618 0 : algo->pdst->weight < cur_cost) {
619 0 : cur_cost = algo->pdst->weight;
620 0 : cpath_copy(optim_path, algo->pdst);
621 0 : optim_path->status = SUCCESS;
622 : }
623 : }
624 : }
625 :
626 : /*
627 : * The priority queue is empty => all the possible (vertex, path)
628 : * elements have been explored. The optim_path contains the optimal
629 : * path if it exists. Otherwise an empty path with status failed is
630 : * returned.
631 : */
632 0 : if (optim_path->status == IN_PROGRESS ||
633 0 : listcount(optim_path->edges) == 0)
634 0 : optim_path->status = FAILED;
635 0 : cspf_clean(algo);
636 :
637 0 : return optim_path;
638 : }
|
