]> git.proxmox.com Git - mirror_frr.git/blame - ospf6d/ospf6_lsdb.c
Merge pull request #12837 from donaldsharp/unlikely_routemap
[mirror_frr.git] / ospf6d / ospf6_lsdb.c
CommitLineData
acddc0ed 1// SPDX-License-Identifier: GPL-2.0-or-later
718e3744 2/*
508e53e2 3 * Copyright (C) 2003 Yasuhiro Ohara
718e3744 4 */
5
6#include <zebra.h>
7
8#include "memory.h"
9#include "log.h"
10#include "command.h"
508e53e2 11#include "prefix.h"
12#include "table.h"
049207c3 13#include "vty.h"
718e3744 14
508e53e2 15#include "ospf6_proto.h"
3a94ed56 16#include "ospf6_area.h"
508e53e2 17#include "ospf6_lsa.h"
718e3744 18#include "ospf6_lsdb.h"
3a94ed56 19#include "ospf6_abr.h"
4dc43886 20#include "ospf6_asbr.h"
c3c0ac83 21#include "ospf6_route.h"
049207c3 22#include "ospf6d.h"
c3c0ac83 23#include "bitfield.h"
718e3744 24
30043e4c
DL
25DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_LSDB, "OSPF6 LSA database");
26
d62a17ae 27struct ospf6_lsdb *ospf6_lsdb_create(void *data)
718e3744 28{
d62a17ae 29 struct ospf6_lsdb *lsdb;
30
31 lsdb = XCALLOC(MTYPE_OSPF6_LSDB, sizeof(struct ospf6_lsdb));
d62a17ae 32 memset(lsdb, 0, sizeof(struct ospf6_lsdb));
33
34 lsdb->data = data;
35 lsdb->table = route_table_init();
36 return lsdb;
718e3744 37}
38
d62a17ae 39void ospf6_lsdb_delete(struct ospf6_lsdb *lsdb)
718e3744 40{
d62a17ae 41 if (lsdb != NULL) {
42 ospf6_lsdb_remove_all(lsdb);
43 route_table_finish(lsdb->table);
44 XFREE(MTYPE_OSPF6_LSDB, lsdb);
45 }
718e3744 46}
47
d62a17ae 48static void ospf6_lsdb_set_key(struct prefix_ipv6 *key, const void *value,
49 int len)
718e3744 50{
d62a17ae 51 assert(key->prefixlen % 8 == 0);
718e3744 52
d62a17ae 53 memcpy((caddr_t)&key->prefix + key->prefixlen / 8, (caddr_t)value, len);
54 key->family = AF_INET6;
55 key->prefixlen += len * 8;
508e53e2 56}
718e3744 57
e39d0538 58#ifdef DEBUG
d62a17ae 59static void _lsdb_count_assert(struct ospf6_lsdb *lsdb)
508e53e2 60{
0db96688 61 struct ospf6_lsa *debug, *debugnext;
d62a17ae 62 unsigned int num = 0;
0db96688 63 for (ALL_LSDB(lsdb, debug, debugnext))
d62a17ae 64 num++;
65
66 if (num == lsdb->count)
67 return;
68
69 zlog_debug("PANIC !! lsdb[%p]->count = %d, real = %d", lsdb,
70 lsdb->count, num);
0db96688 71 for (ALL_LSDB(lsdb, debug, debugnext))
c811f101 72 zlog_debug("%s lsdb[%p]", debug->name, debug->lsdb);
d62a17ae 73 zlog_debug("DUMP END");
74
75 assert(num == lsdb->count);
718e3744 76}
508e53e2 77#define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
d62a17ae 78#else /*DEBUG*/
508e53e2 79#define ospf6_lsdb_count_assert(t) ((void) 0)
e39d0538 80#endif /*DEBUG*/
718e3744 81
8935a149
DS
82static inline void ospf6_lsdb_stats_update(struct ospf6_lsa *lsa,
83 struct ospf6_lsdb *lsdb, int count)
84{
85 uint16_t stat = ntohs(lsa->header->type) & OSPF6_LSTYPE_FCODE_MASK;
86
87 if (stat >= OSPF6_LSTYPE_SIZE)
88 stat = OSPF6_LSTYPE_UNKNOWN;
89 lsdb->stats[stat] += count;
90}
91
d62a17ae 92void ospf6_lsdb_add(struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
718e3744 93{
d62a17ae 94 struct prefix_ipv6 key;
95 struct route_node *current;
96 struct ospf6_lsa *old = NULL;
97
98 memset(&key, 0, sizeof(key));
99 ospf6_lsdb_set_key(&key, &lsa->header->type, sizeof(lsa->header->type));
100 ospf6_lsdb_set_key(&key, &lsa->header->adv_router,
101 sizeof(lsa->header->adv_router));
102 ospf6_lsdb_set_key(&key, &lsa->header->id, sizeof(lsa->header->id));
103
104 current = route_node_get(lsdb->table, (struct prefix *)&key);
105 old = current->info;
106 current->info = lsa;
107 lsa->rn = current;
108 ospf6_lsa_lock(lsa);
109
110 if (!old) {
111 lsdb->count++;
8935a149 112 ospf6_lsdb_stats_update(lsa, lsdb, 1);
d62a17ae 113
114 if (OSPF6_LSA_IS_MAXAGE(lsa)) {
115 if (lsdb->hook_remove)
116 (*lsdb->hook_remove)(lsa);
117 } else {
118 if (lsdb->hook_add)
119 (*lsdb->hook_add)(lsa);
120 }
121 } else {
7c20ee06
MN
122 lsa->retrans_count = old->retrans_count;
123
d62a17ae 124 if (OSPF6_LSA_IS_CHANGED(old, lsa)) {
125 if (OSPF6_LSA_IS_MAXAGE(lsa)) {
126 if (lsdb->hook_remove) {
127 (*lsdb->hook_remove)(old);
128 (*lsdb->hook_remove)(lsa);
129 }
130 } else if (OSPF6_LSA_IS_MAXAGE(old)) {
131 if (lsdb->hook_add)
132 (*lsdb->hook_add)(lsa);
133 } else {
134 if (lsdb->hook_remove)
135 (*lsdb->hook_remove)(old);
136 if (lsdb->hook_add)
137 (*lsdb->hook_add)(lsa);
138 }
139 }
d107621d
CS
140 /* to free the lookup lock in node get*/
141 route_unlock_node(current);
4b0e09d8 142 ospf6_lsa_unlock(old);
a765eb93 143 }
d62a17ae 144
145 ospf6_lsdb_count_assert(lsdb);
718e3744 146}
147
d62a17ae 148void ospf6_lsdb_remove(struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
718e3744 149{
d62a17ae 150 struct route_node *node;
151 struct prefix_ipv6 key;
718e3744 152
d62a17ae 153 memset(&key, 0, sizeof(key));
154 ospf6_lsdb_set_key(&key, &lsa->header->type, sizeof(lsa->header->type));
155 ospf6_lsdb_set_key(&key, &lsa->header->adv_router,
156 sizeof(lsa->header->adv_router));
157 ospf6_lsdb_set_key(&key, &lsa->header->id, sizeof(lsa->header->id));
718e3744 158
d62a17ae 159 node = route_node_lookup(lsdb->table, (struct prefix *)&key);
160 assert(node && node->info == lsa);
718e3744 161
d62a17ae 162 node->info = NULL;
163 lsdb->count--;
8935a149 164 ospf6_lsdb_stats_update(lsa, lsdb, -1);
718e3744 165
d62a17ae 166 if (lsdb->hook_remove)
167 (*lsdb->hook_remove)(lsa);
718e3744 168
d62a17ae 169 route_unlock_node(node); /* to free the lookup lock */
170 route_unlock_node(node); /* to free the original lock */
4b0e09d8 171 ospf6_lsa_unlock(lsa);
6452df09 172
d62a17ae 173 ospf6_lsdb_count_assert(lsdb);
718e3744 174}
175
d7c0a89a
QY
176struct ospf6_lsa *ospf6_lsdb_lookup(uint16_t type, uint32_t id,
177 uint32_t adv_router,
d62a17ae 178 struct ospf6_lsdb *lsdb)
718e3744 179{
d62a17ae 180 struct route_node *node;
181 struct prefix_ipv6 key;
718e3744 182
d62a17ae 183 if (lsdb == NULL)
184 return NULL;
718e3744 185
d62a17ae 186 memset(&key, 0, sizeof(key));
187 ospf6_lsdb_set_key(&key, &type, sizeof(type));
188 ospf6_lsdb_set_key(&key, &adv_router, sizeof(adv_router));
189 ospf6_lsdb_set_key(&key, &id, sizeof(id));
718e3744 190
d62a17ae 191 node = route_node_lookup(lsdb->table, (struct prefix *)&key);
192 if (node == NULL || node->info == NULL)
193 return NULL;
a765eb93 194
d62a17ae 195 route_unlock_node(node);
196 return (struct ospf6_lsa *)node->info;
718e3744 197}
198
4dc43886
MR
199struct ospf6_lsa *ospf6_find_external_lsa(struct ospf6 *ospf6, struct prefix *p)
200{
201 struct ospf6_route *match;
202 struct ospf6_lsa *lsa;
203 struct ospf6_external_info *info;
204
205 match = ospf6_route_lookup(p, ospf6->external_table);
206 if (match == NULL) {
207 if (IS_OSPF6_DEBUG_ASBR)
208 zlog_debug("No such route %pFX to withdraw", p);
209
210 return NULL;
211 }
212
78982818 213 info = match->route_option;
4dc43886
MR
214 assert(info);
215
216 lsa = ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_AS_EXTERNAL),
217 htonl(info->id), ospf6->router_id, ospf6->lsdb);
218 return lsa;
219}
220
3a94ed56
RW
221struct ospf6_lsa *ospf6_find_inter_prefix_lsa(struct ospf6 *ospf6,
222 struct ospf6_area *area,
223 struct prefix *p)
224{
225 struct ospf6_lsa *lsa;
226 uint16_t type = htons(OSPF6_LSTYPE_INTER_PREFIX);
227
228 for (ALL_LSDB_TYPED_ADVRTR(area->lsdb, type, ospf6->router_id, lsa)) {
229 struct ospf6_inter_prefix_lsa *prefix_lsa;
230 struct prefix prefix;
231
232 prefix_lsa =
233 (struct ospf6_inter_prefix_lsa *)OSPF6_LSA_HEADER_END(
234 lsa->header);
235 prefix.family = AF_INET6;
236 prefix.prefixlen = prefix_lsa->prefix.prefix_length;
237 ospf6_prefix_in6_addr(&prefix.u.prefix6, prefix_lsa,
238 &prefix_lsa->prefix);
239 if (prefix_same(p, &prefix))
240 return lsa;
241 }
242
243 return NULL;
244}
245
d7c0a89a
QY
246struct ospf6_lsa *ospf6_lsdb_lookup_next(uint16_t type, uint32_t id,
247 uint32_t adv_router,
d62a17ae 248 struct ospf6_lsdb *lsdb)
2680aa2b 249{
d62a17ae 250 struct route_node *node;
251 struct prefix_ipv6 key;
2680aa2b 252
d62a17ae 253 if (lsdb == NULL)
254 return NULL;
2680aa2b 255
d62a17ae 256 memset(&key, 0, sizeof(key));
257 ospf6_lsdb_set_key(&key, &type, sizeof(type));
258 ospf6_lsdb_set_key(&key, &adv_router, sizeof(adv_router));
259 ospf6_lsdb_set_key(&key, &id, sizeof(id));
2680aa2b 260
2dbe669b 261 zlog_debug("lsdb_lookup_next: key: %pFX", &key);
2680aa2b 262
d62a17ae 263 node = route_table_get_next(lsdb->table, &key);
2680aa2b 264
d62a17ae 265 /* skip to real existing entry */
266 while (node && node->info == NULL)
267 node = route_next(node);
2680aa2b 268
d62a17ae 269 if (!node)
270 return NULL;
2680aa2b 271
d62a17ae 272 route_unlock_node(node);
273 if (!node->info)
274 return NULL;
2680aa2b 275
d62a17ae 276 return (struct ospf6_lsa *)node->info;
2680aa2b 277}
278
d62a17ae 279const struct route_node *ospf6_lsdb_head(struct ospf6_lsdb *lsdb, int argmode,
280 uint16_t type, uint32_t adv_router,
281 struct ospf6_lsa **lsa)
718e3744 282{
d62a17ae 283 struct route_node *node, *end;
284
285 *lsa = NULL;
286
287 if (argmode > 0) {
288 struct prefix_ipv6 key = {.family = AF_INET6, .prefixlen = 0};
289
290 ospf6_lsdb_set_key(&key, &type, sizeof(type));
291 if (argmode > 1)
292 ospf6_lsdb_set_key(&key, &adv_router,
293 sizeof(adv_router));
294
295 node = route_table_get_next(lsdb->table, &key);
296 if (!node || !prefix_match((struct prefix *)&key, &node->p))
297 return NULL;
298
299 for (end = node; end && end->parent
300 && end->parent->p.prefixlen >= key.prefixlen;
301 end = end->parent)
302 ;
303 } else {
304 node = route_top(lsdb->table);
305 end = NULL;
306 }
307
308 while (node && !node->info)
309 node = route_next_until(node, end);
310
311 if (!node)
312 return NULL;
313 if (!node->info) {
314 route_unlock_node(node);
315 return NULL;
316 }
317
318 *lsa = node->info;
319 ospf6_lsa_lock(*lsa);
320
321 return end;
718e3744 322}
323
d62a17ae 324struct ospf6_lsa *ospf6_lsdb_next(const struct route_node *iterend,
325 struct ospf6_lsa *lsa)
718e3744 326{
d62a17ae 327 struct route_node *node = lsa->rn;
718e3744 328
4b0e09d8 329 ospf6_lsa_unlock(lsa);
718e3744 330
d62a17ae 331 do
332 node = route_next_until(node, iterend);
333 while (node && !node->info);
718e3744 334
d62a17ae 335 if (node && node->info) {
336 struct ospf6_lsa *next = node->info;
337 ospf6_lsa_lock(next);
338 return next;
339 }
718e3744 340
d62a17ae 341 if (node)
342 route_unlock_node(node);
343 return NULL;
718e3744 344}
345
d62a17ae 346void ospf6_lsdb_remove_all(struct ospf6_lsdb *lsdb)
718e3744 347{
2e37407f 348 struct ospf6_lsa *lsa, *lsanext;
a765eb93 349
d62a17ae 350 if (lsdb == NULL)
351 return;
a765eb93 352
2e37407f 353 for (ALL_LSDB(lsdb, lsa, lsanext))
d62a17ae 354 ospf6_lsdb_remove(lsa, lsdb);
718e3744 355}
356
d62a17ae 357void ospf6_lsdb_lsa_unlock(struct ospf6_lsa *lsa)
a765eb93 358{
d62a17ae 359 if (lsa != NULL) {
360 if (lsa->rn != NULL)
361 route_unlock_node(lsa->rn);
4b0e09d8 362 ospf6_lsa_unlock(lsa);
d62a17ae 363 }
a765eb93
DD
364}
365
d62a17ae 366int ospf6_lsdb_maxage_remover(struct ospf6_lsdb *lsdb)
2449fcd6 367{
d62a17ae 368 int reschedule = 0;
2e37407f 369 struct ospf6_lsa *lsa, *lsanext;
d62a17ae 370
2e37407f 371 for (ALL_LSDB(lsdb, lsa, lsanext)) {
ad500b22
K
372 if (!OSPF6_LSA_IS_MAXAGE(lsa)) {
373 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
374 zlog_debug("Not MaxAge %s", lsa->name);
d62a17ae 375 continue;
ad500b22
K
376 }
377
d62a17ae 378 if (lsa->retrans_count != 0) {
ad500b22
K
379 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
380 zlog_debug("Remove MaxAge %s retrans_count %d",
381 lsa->name, lsa->retrans_count);
382
d62a17ae 383 reschedule = 1;
384 continue;
385 }
386 if (IS_OSPF6_DEBUG_LSA_TYPE(lsa->header->type))
387 zlog_debug("Remove MaxAge %s", lsa->name);
76249532 388
d62a17ae 389 if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED)) {
390 UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED);
391 /*
392 * lsa->header->age = 0;
393 */
394 lsa->header->seqnum =
395 htonl(OSPF_MAX_SEQUENCE_NUMBER + 1);
396 ospf6_lsa_checksum(lsa->header);
397
e16d030c 398 EVENT_OFF(lsa->refresh);
8c1186d3 399 event_execute(master, ospf6_lsa_refresh, lsa, 0);
d62a17ae 400 } else {
ad500b22 401 zlog_debug("calling ospf6_lsdb_remove %s", lsa->name);
d62a17ae 402 ospf6_lsdb_remove(lsa, lsdb);
403 }
2449fcd6 404 }
d62a17ae 405
406 return (reschedule);
2449fcd6
DD
407}
408
d7c0a89a
QY
409uint32_t ospf6_new_ls_id(uint16_t type, uint32_t adv_router,
410 struct ospf6_lsdb *lsdb)
049207c3 411{
d62a17ae 412 struct ospf6_lsa *lsa;
d7c0a89a 413 uint32_t id = 1, tmp_id;
d62a17ae 414
415 /* This routine is curently invoked only for Inter-Prefix LSAs for
416 * non-summarized routes (no area/range).
417 */
418 for (ALL_LSDB_TYPED_ADVRTR(lsdb, type, adv_router, lsa)) {
419 tmp_id = ntohl(lsa->header->id);
420 if (tmp_id < id)
421 continue;
422
423 if (tmp_id > id) {
424 ospf6_lsdb_lsa_unlock(lsa);
425 break;
426 }
427 id++;
428 }
429
d7c0a89a 430 return ((uint32_t)htonl(id));
049207c3 431}
432
433/* Decide new LS sequence number to originate.
434 note return value is network byte order */
d7c0a89a
QY
435uint32_t ospf6_new_ls_seqnum(uint16_t type, uint32_t id, uint32_t adv_router,
436 struct ospf6_lsdb *lsdb)
049207c3 437{
d62a17ae 438 struct ospf6_lsa *lsa;
439 signed long seqnum = 0;
049207c3 440
d62a17ae 441 /* if current database copy not found, return InitialSequenceNumber */
442 lsa = ospf6_lsdb_lookup(type, id, adv_router, lsdb);
443 if (lsa == NULL)
444 seqnum = OSPF_INITIAL_SEQUENCE_NUMBER;
445 else
446 seqnum = (signed long)ntohl(lsa->header->seqnum) + 1;
049207c3 447
d7c0a89a 448 return ((uint32_t)htonl(seqnum));
049207c3 449}