2 * Copyright (C) 2003 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
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
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.
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
30 #include "ospf6_proto.h"
31 #include "ospf6_lsa.h"
32 #include "ospf6_lsdb.h"
33 #include "ospf6_route.h"
38 ospf6_lsdb_create (void *data
)
40 struct ospf6_lsdb
*lsdb
;
42 lsdb
= XCALLOC (MTYPE_OSPF6_LSDB
, sizeof (struct ospf6_lsdb
));
45 zlog_warn ("Can't malloc lsdb");
48 memset (lsdb
, 0, sizeof (struct ospf6_lsdb
));
51 lsdb
->table
= route_table_init ();
56 ospf6_lsdb_delete (struct ospf6_lsdb
*lsdb
)
60 ospf6_lsdb_remove_all (lsdb
);
61 route_table_finish (lsdb
->table
);
62 XFREE (MTYPE_OSPF6_LSDB
, lsdb
);
67 ospf6_lsdb_set_key (struct prefix_ipv6
*key
, void *value
, int len
)
69 assert (key
->prefixlen
% 8 == 0);
71 memcpy ((caddr_t
) &key
->prefix
+ key
->prefixlen
/ 8,
72 (caddr_t
) value
, len
);
73 key
->family
= AF_INET6
;
74 key
->prefixlen
+= len
* 8;
79 _lsdb_count_assert (struct ospf6_lsdb
*lsdb
)
81 struct ospf6_lsa
*debug
;
83 for (debug
= ospf6_lsdb_head (lsdb
); debug
;
84 debug
= ospf6_lsdb_next (debug
))
87 if (num
== lsdb
->count
)
90 zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d",
91 lsdb
, lsdb
->count
, num
);
92 for (debug
= ospf6_lsdb_head (lsdb
); debug
;
93 debug
= ospf6_lsdb_next (debug
))
94 zlog_debug ("%p %p %s lsdb[%p]", debug
->prev
, debug
->next
, debug
->name
,
96 zlog_debug ("DUMP END");
98 assert (num
== lsdb
->count
);
100 #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
102 #define ospf6_lsdb_count_assert(t) ((void) 0)
106 ospf6_lsdb_add (struct ospf6_lsa
*lsa
, struct ospf6_lsdb
*lsdb
)
108 struct prefix_ipv6 key
;
109 struct route_node
*current
;
110 struct ospf6_lsa
*old
= NULL
;
112 memset (&key
, 0, sizeof (key
));
113 ospf6_lsdb_set_key (&key
, &lsa
->header
->type
, sizeof (lsa
->header
->type
));
114 ospf6_lsdb_set_key (&key
, &lsa
->header
->adv_router
,
115 sizeof (lsa
->header
->adv_router
));
116 ospf6_lsdb_set_key (&key
, &lsa
->header
->id
, sizeof (lsa
->header
->id
));
118 current
= route_node_get (lsdb
->table
, (struct prefix
*) &key
);
122 ospf6_lsa_lock (lsa
);
128 if (OSPF6_LSA_IS_MAXAGE (lsa
))
130 if (lsdb
->hook_remove
)
131 (*lsdb
->hook_remove
) (lsa
);
136 (*lsdb
->hook_add
) (lsa
);
141 if (OSPF6_LSA_IS_CHANGED (old
, lsa
))
143 if (OSPF6_LSA_IS_MAXAGE (lsa
))
145 if (lsdb
->hook_remove
)
147 (*lsdb
->hook_remove
) (old
);
148 (*lsdb
->hook_remove
) (lsa
);
151 else if (OSPF6_LSA_IS_MAXAGE (old
))
154 (*lsdb
->hook_add
) (lsa
);
158 if (lsdb
->hook_remove
)
159 (*lsdb
->hook_remove
) (old
);
161 (*lsdb
->hook_add
) (lsa
);
164 ospf6_lsa_unlock (old
);
167 ospf6_lsdb_count_assert (lsdb
);
171 ospf6_lsdb_remove (struct ospf6_lsa
*lsa
, struct ospf6_lsdb
*lsdb
)
173 struct route_node
*node
;
174 struct prefix_ipv6 key
;
176 memset (&key
, 0, sizeof (key
));
177 ospf6_lsdb_set_key (&key
, &lsa
->header
->type
, sizeof (lsa
->header
->type
));
178 ospf6_lsdb_set_key (&key
, &lsa
->header
->adv_router
,
179 sizeof (lsa
->header
->adv_router
));
180 ospf6_lsdb_set_key (&key
, &lsa
->header
->id
, sizeof (lsa
->header
->id
));
182 node
= route_node_lookup (lsdb
->table
, (struct prefix
*) &key
);
183 assert (node
&& node
->info
== lsa
);
188 if (lsdb
->hook_remove
)
189 (*lsdb
->hook_remove
) (lsa
);
191 route_unlock_node (node
); /* to free the lookup lock */
192 route_unlock_node (node
); /* to free the original lock */
193 ospf6_lsa_unlock (lsa
);
195 ospf6_lsdb_count_assert (lsdb
);
199 ospf6_lsdb_lookup (u_int16_t type
, u_int32_t id
, u_int32_t adv_router
,
200 struct ospf6_lsdb
*lsdb
)
202 struct route_node
*node
;
203 struct prefix_ipv6 key
;
208 memset (&key
, 0, sizeof (key
));
209 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
210 ospf6_lsdb_set_key (&key
, &adv_router
, sizeof (adv_router
));
211 ospf6_lsdb_set_key (&key
, &id
, sizeof (id
));
213 node
= route_node_lookup (lsdb
->table
, (struct prefix
*) &key
);
214 if (node
== NULL
|| node
->info
== NULL
)
217 route_unlock_node (node
);
218 return (struct ospf6_lsa
*) node
->info
;
222 ospf6_lsdb_lookup_next (u_int16_t type
, u_int32_t id
, u_int32_t adv_router
,
223 struct ospf6_lsdb
*lsdb
)
225 struct route_node
*node
;
226 struct route_node
*matched
= NULL
;
227 struct prefix_ipv6 key
;
233 memset (&key
, 0, sizeof (key
));
234 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
235 ospf6_lsdb_set_key (&key
, &adv_router
, sizeof (adv_router
));
236 ospf6_lsdb_set_key (&key
, &id
, sizeof (id
));
237 p
= (struct prefix
*) &key
;
240 char buf
[PREFIX2STR_BUFFER
];
241 prefix2str (p
, buf
, sizeof (buf
));
242 zlog_debug ("lsdb_lookup_next: key: %s", buf
);
245 node
= lsdb
->table
->top
;
246 /* walk down tree. */
247 while (node
&& node
->p
.prefixlen
<= p
->prefixlen
&&
248 prefix_match (&node
->p
, p
))
251 node
= node
->link
[prefix_bit(&p
->u
.prefix
, node
->p
.prefixlen
)];
257 node
= lsdb
->table
->top
;
258 route_lock_node (node
);
260 /* skip to real existing entry */
261 while (node
&& node
->info
== NULL
)
262 node
= route_next (node
);
267 if (prefix_same (&node
->p
, p
))
269 node
= route_next (node
);
270 while (node
&& node
->info
== NULL
)
271 node
= route_next (node
);
277 route_unlock_node (node
);
278 return (struct ospf6_lsa
*) node
->info
;
281 /* Iteration function */
283 ospf6_lsdb_head (struct ospf6_lsdb
*lsdb
)
285 struct route_node
*node
;
287 node
= route_top (lsdb
->table
);
291 /* skip to the existing lsdb entry */
292 while (node
&& node
->info
== NULL
)
293 node
= route_next (node
);
298 ospf6_lsa_lock ((struct ospf6_lsa
*) node
->info
);
299 return (struct ospf6_lsa
*) node
->info
;
303 ospf6_lsdb_next (struct ospf6_lsa
*lsa
)
305 struct route_node
*node
= lsa
->rn
;
306 struct ospf6_lsa
*next
= NULL
;
309 node
= route_next (node
);
310 } while (node
&& node
->info
== NULL
);
312 if ((node
!= NULL
) && (node
->info
!= NULL
))
315 ospf6_lsa_lock (next
);
318 ospf6_lsa_unlock (lsa
);
323 ospf6_lsdb_type_router_head (u_int16_t type
, u_int32_t adv_router
,
324 struct ospf6_lsdb
*lsdb
)
326 struct route_node
*node
;
327 struct prefix_ipv6 key
;
328 struct ospf6_lsa
*lsa
;
330 memset (&key
, 0, sizeof (key
));
331 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
332 ospf6_lsdb_set_key (&key
, &adv_router
, sizeof (adv_router
));
334 node
= lsdb
->table
->top
;
336 /* Walk down tree. */
337 while (node
&& node
->p
.prefixlen
<= key
.prefixlen
&&
338 prefix_match (&node
->p
, (struct prefix
*) &key
))
339 node
= node
->link
[prefix6_bit(&key
.prefix
, node
->p
.prefixlen
)];
342 route_lock_node (node
);
343 while (node
&& node
->info
== NULL
)
344 node
= route_next (node
);
349 if (! prefix_match ((struct prefix
*) &key
, &node
->p
))
353 ospf6_lsa_lock (lsa
);
359 ospf6_lsdb_type_router_next (u_int16_t type
, u_int32_t adv_router
,
360 struct ospf6_lsa
*lsa
)
362 struct ospf6_lsa
*next
= ospf6_lsdb_next(lsa
);
366 if (next
->header
->type
!= type
||
367 next
->header
->adv_router
!= adv_router
)
369 route_unlock_node (next
->rn
);
370 ospf6_lsa_unlock (next
);
379 ospf6_lsdb_type_head (u_int16_t type
, struct ospf6_lsdb
*lsdb
)
381 struct route_node
*node
;
382 struct prefix_ipv6 key
;
383 struct ospf6_lsa
*lsa
;
385 memset (&key
, 0, sizeof (key
));
386 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
388 /* Walk down tree. */
389 node
= lsdb
->table
->top
;
390 while (node
&& node
->p
.prefixlen
<= key
.prefixlen
&&
391 prefix_match (&node
->p
, (struct prefix
*) &key
))
392 node
= node
->link
[prefix6_bit(&key
.prefix
, node
->p
.prefixlen
)];
395 route_lock_node (node
);
396 while (node
&& node
->info
== NULL
)
397 node
= route_next (node
);
402 if (! prefix_match ((struct prefix
*) &key
, &node
->p
))
406 ospf6_lsa_lock (lsa
);
412 ospf6_lsdb_type_next (u_int16_t type
, struct ospf6_lsa
*lsa
)
414 struct ospf6_lsa
*next
= ospf6_lsdb_next (lsa
);
418 if (next
->header
->type
!= type
)
420 route_unlock_node (next
->rn
);
421 ospf6_lsa_unlock (next
);
430 ospf6_lsdb_remove_all (struct ospf6_lsdb
*lsdb
)
432 struct ospf6_lsa
*lsa
;
437 for (lsa
= ospf6_lsdb_head (lsdb
); lsa
; lsa
= ospf6_lsdb_next (lsa
))
438 ospf6_lsdb_remove (lsa
, lsdb
);
442 ospf6_lsdb_lsa_unlock (struct ospf6_lsa
*lsa
)
447 route_unlock_node (lsa
->rn
);
448 ospf6_lsa_unlock (lsa
);
453 ospf6_lsdb_maxage_remover (struct ospf6_lsdb
*lsdb
)
456 struct ospf6_lsa
*lsa
;
458 for (lsa
= ospf6_lsdb_head (lsdb
); lsa
; lsa
= ospf6_lsdb_next (lsa
))
460 if (! OSPF6_LSA_IS_MAXAGE (lsa
))
462 if (lsa
->retrans_count
!= 0)
467 if (IS_OSPF6_DEBUG_LSA_TYPE (lsa
->header
->type
))
468 zlog_debug ("Remove MaxAge %s", lsa
->name
);
469 if (CHECK_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
))
471 UNSET_FLAG(lsa
->flag
, OSPF6_LSA_SEQWRAPPED
);
473 * lsa->header->age = 0;
475 lsa
->header
->seqnum
= htonl(OSPF_MAX_SEQUENCE_NUMBER
+ 1);
476 ospf6_lsa_checksum (lsa
->header
);
478 THREAD_OFF(lsa
->refresh
);
479 thread_execute (master
, ospf6_lsa_refresh
, lsa
, 0);
481 ospf6_lsdb_remove (lsa
, lsdb
);
489 ospf6_lsdb_show (struct vty
*vty
, enum ospf_lsdb_show_level level
,
490 u_int16_t
*type
, u_int32_t
*id
, u_int32_t
*adv_router
,
491 struct ospf6_lsdb
*lsdb
)
493 struct ospf6_lsa
*lsa
;
494 void (*showfunc
) (struct vty
*, struct ospf6_lsa
*) = NULL
;
498 case OSPF6_LSDB_SHOW_LEVEL_DETAIL
:
499 showfunc
= ospf6_lsa_show
;
501 case OSPF6_LSDB_SHOW_LEVEL_INTERNAL
:
502 showfunc
= ospf6_lsa_show_internal
;
504 case OSPF6_LSDB_SHOW_LEVEL_DUMP
:
505 showfunc
= ospf6_lsa_show_dump
;
507 case OSPF6_LSDB_SHOW_LEVEL_NORMAL
:
509 showfunc
= ospf6_lsa_show_summary
;
512 if (type
&& id
&& adv_router
)
514 lsa
= ospf6_lsdb_lookup (*type
, *id
, *adv_router
, lsdb
);
517 if (level
== OSPF6_LSDB_SHOW_LEVEL_NORMAL
)
518 ospf6_lsa_show (vty
, lsa
);
520 (*showfunc
) (vty
, lsa
);
525 if (level
== OSPF6_LSDB_SHOW_LEVEL_NORMAL
)
526 ospf6_lsa_show_summary_header (vty
);
528 if (type
&& adv_router
)
529 lsa
= ospf6_lsdb_type_router_head (*type
, *adv_router
, lsdb
);
531 lsa
= ospf6_lsdb_type_head (*type
, lsdb
);
533 lsa
= ospf6_lsdb_head (lsdb
);
536 if ((! adv_router
|| lsa
->header
->adv_router
== *adv_router
) &&
537 (! id
|| lsa
->header
->id
== *id
))
538 (*showfunc
) (vty
, lsa
);
540 if (type
&& adv_router
)
541 lsa
= ospf6_lsdb_type_router_next (*type
, *adv_router
, lsa
);
543 lsa
= ospf6_lsdb_type_next (*type
, lsa
);
545 lsa
= ospf6_lsdb_next (lsa
);
550 ospf6_new_ls_id (u_int16_t type
, u_int32_t adv_router
,
551 struct ospf6_lsdb
*lsdb
)
553 struct ospf6_lsa
*lsa
;
554 u_int32_t id
= 1, tmp_id
;
556 /* This routine is curently invoked only for Inter-Prefix LSAs for
557 * non-summarized routes (no area/range).
559 for (lsa
= ospf6_lsdb_type_router_head (type
, adv_router
, lsdb
); lsa
;
560 lsa
= ospf6_lsdb_type_router_next (type
, adv_router
, lsa
))
562 tmp_id
= ntohl (lsa
->header
->id
);
568 ospf6_lsdb_lsa_unlock (lsa
);
574 return ((u_int32_t
) htonl (id
));
577 /* Decide new LS sequence number to originate.
578 note return value is network byte order */
580 ospf6_new_ls_seqnum (u_int16_t type
, u_int32_t id
, u_int32_t adv_router
,
581 struct ospf6_lsdb
*lsdb
)
583 struct ospf6_lsa
*lsa
;
584 signed long seqnum
= 0;
586 /* if current database copy not found, return InitialSequenceNumber */
587 lsa
= ospf6_lsdb_lookup (type
, id
, adv_router
, lsdb
);
589 seqnum
= OSPF_INITIAL_SEQUENCE_NUMBER
;
591 seqnum
= (signed long) ntohl (lsa
->header
->seqnum
) + 1;
593 return ((u_int32_t
) htonl (seqnum
));