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
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.
31 #include "ospf6_proto.h"
32 #include "ospf6_lsa.h"
33 #include "ospf6_lsdb.h"
37 ospf6_lsdb_create (void *data
)
39 struct ospf6_lsdb
*lsdb
;
41 lsdb
= XCALLOC (MTYPE_OSPF6_LSDB
, sizeof (struct ospf6_lsdb
));
44 zlog_warn ("Can't malloc lsdb");
47 memset (lsdb
, 0, sizeof (struct ospf6_lsdb
));
50 lsdb
->table
= route_table_init ();
55 ospf6_lsdb_delete (struct ospf6_lsdb
*lsdb
)
57 ospf6_lsdb_remove_all (lsdb
);
58 route_table_finish (lsdb
->table
);
59 XFREE (MTYPE_OSPF6_LSDB
, lsdb
);
63 ospf6_lsdb_set_key (struct prefix_ipv6
*key
, void *value
, int len
)
65 assert (key
->prefixlen
% 8 == 0);
67 memcpy ((caddr_t
) &key
->prefix
+ key
->prefixlen
/ 8,
68 (caddr_t
) value
, len
);
69 key
->family
= AF_INET6
;
70 key
->prefixlen
+= len
* 8;
75 _lsdb_count_assert (struct ospf6_lsdb
*lsdb
)
77 struct ospf6_lsa
*debug
;
79 for (debug
= ospf6_lsdb_head (lsdb
); debug
;
80 debug
= ospf6_lsdb_next (debug
))
83 if (num
== lsdb
->count
)
86 zlog_info ("PANIC !! lsdb[%p]->count = %d, real = %d",
87 lsdb
, lsdb
->count
, num
);
88 for (debug
= ospf6_lsdb_head (lsdb
); debug
;
89 debug
= ospf6_lsdb_next (debug
))
90 zlog_info ("%p %p %s lsdb[%p]", debug
->prev
, debug
->next
, debug
->name
,
92 zlog_info ("DUMP END");
94 assert (num
== lsdb
->count
);
96 #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t))
98 #define ospf6_lsdb_count_assert(t) ((void) 0)
102 ospf6_lsdb_add (struct ospf6_lsa
*lsa
, struct ospf6_lsdb
*lsdb
)
104 struct prefix_ipv6 key
;
105 struct route_node
*current
, *nextnode
, *prevnode
;
106 struct ospf6_lsa
*next
, *prev
, *old
= NULL
;
108 memset (&key
, 0, sizeof (key
));
109 ospf6_lsdb_set_key (&key
, &lsa
->header
->type
, sizeof (lsa
->header
->type
));
110 ospf6_lsdb_set_key (&key
, &lsa
->header
->adv_router
,
111 sizeof (lsa
->header
->adv_router
));
112 ospf6_lsdb_set_key (&key
, &lsa
->header
->id
, sizeof (lsa
->header
->id
));
114 current
= route_node_get (lsdb
->table
, (struct prefix
*) &key
);
117 ospf6_lsa_lock (lsa
);
122 old
->prev
->next
= lsa
;
124 old
->next
->prev
= lsa
;
125 lsa
->next
= old
->next
;
126 lsa
->prev
= old
->prev
;
132 route_lock_node (nextnode
);
134 nextnode
= route_next (nextnode
);
135 } while (nextnode
&& nextnode
->info
== NULL
);
136 if (nextnode
== NULL
)
140 next
= nextnode
->info
;
143 route_unlock_node (nextnode
);
148 route_lock_node (prevnode
);
150 prevnode
= route_prev (prevnode
);
151 } while (prevnode
&& prevnode
->info
== NULL
);
152 if (prevnode
== NULL
)
156 prev
= prevnode
->info
;
159 route_unlock_node (prevnode
);
167 if (OSPF6_LSA_IS_CHANGED (old
, lsa
))
169 if (OSPF6_LSA_IS_MAXAGE (lsa
))
171 if (lsdb
->hook_remove
)
173 (*lsdb
->hook_remove
) (old
);
174 (*lsdb
->hook_remove
) (lsa
);
177 else if (OSPF6_LSA_IS_MAXAGE (old
))
180 (*lsdb
->hook_add
) (lsa
);
184 if (lsdb
->hook_remove
)
185 (*lsdb
->hook_remove
) (old
);
187 (*lsdb
->hook_add
) (lsa
);
191 else if (OSPF6_LSA_IS_MAXAGE (lsa
))
193 if (lsdb
->hook_remove
)
194 (*lsdb
->hook_remove
) (lsa
);
199 (*lsdb
->hook_add
) (lsa
);
203 ospf6_lsa_unlock (old
);
205 ospf6_lsdb_count_assert (lsdb
);
209 ospf6_lsdb_remove (struct ospf6_lsa
*lsa
, struct ospf6_lsdb
*lsdb
)
211 struct route_node
*node
;
212 struct prefix_ipv6 key
;
214 memset (&key
, 0, sizeof (key
));
215 ospf6_lsdb_set_key (&key
, &lsa
->header
->type
, sizeof (lsa
->header
->type
));
216 ospf6_lsdb_set_key (&key
, &lsa
->header
->adv_router
,
217 sizeof (lsa
->header
->adv_router
));
218 ospf6_lsdb_set_key (&key
, &lsa
->header
->id
, sizeof (lsa
->header
->id
));
220 node
= route_node_lookup (lsdb
->table
, (struct prefix
*) &key
);
221 assert (node
&& node
->info
== lsa
);
224 lsa
->prev
->next
= lsa
->next
;
226 lsa
->next
->prev
= lsa
->prev
;
231 if (lsdb
->hook_remove
)
232 (*lsdb
->hook_remove
) (lsa
);
234 ospf6_lsa_unlock (lsa
);
235 route_unlock_node (node
);
237 ospf6_lsdb_count_assert (lsdb
);
241 ospf6_lsdb_lookup (u_int16_t type
, u_int32_t id
, u_int32_t adv_router
,
242 struct ospf6_lsdb
*lsdb
)
244 struct route_node
*node
;
245 struct prefix_ipv6 key
;
250 memset (&key
, 0, sizeof (key
));
251 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
252 ospf6_lsdb_set_key (&key
, &adv_router
, sizeof (adv_router
));
253 ospf6_lsdb_set_key (&key
, &id
, sizeof (id
));
255 node
= route_node_lookup (lsdb
->table
, (struct prefix
*) &key
);
256 if (node
== NULL
|| node
->info
== NULL
)
258 return (struct ospf6_lsa
*) node
->info
;
261 /* Iteration function */
263 ospf6_lsdb_head (struct ospf6_lsdb
*lsdb
)
265 struct route_node
*node
;
267 node
= route_top (lsdb
->table
);
271 /* skip to the existing lsdb entry */
272 while (node
&& node
->info
== NULL
)
273 node
= route_next (node
);
277 route_unlock_node (node
);
279 ospf6_lsa_lock ((struct ospf6_lsa
*) node
->info
);
280 return (struct ospf6_lsa
*) node
->info
;
284 ospf6_lsdb_next (struct ospf6_lsa
*lsa
)
286 struct ospf6_lsa
*next
= lsa
->next
;
288 ospf6_lsa_unlock (lsa
);
290 ospf6_lsa_lock (next
);
295 /* Macro version of check_bit (). */
296 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
299 ospf6_lsdb_type_router_head (u_int16_t type
, u_int32_t adv_router
,
300 struct ospf6_lsdb
*lsdb
)
302 struct route_node
*node
;
303 struct prefix_ipv6 key
;
304 struct ospf6_lsa
*lsa
;
306 memset (&key
, 0, sizeof (key
));
307 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
308 ospf6_lsdb_set_key (&key
, &adv_router
, sizeof (adv_router
));
310 node
= lsdb
->table
->top
;
312 /* Walk down tree. */
313 while (node
&& node
->p
.prefixlen
<= key
.prefixlen
&&
314 prefix_match (&node
->p
, (struct prefix
*) &key
))
315 node
= node
->link
[CHECK_BIT(&key
.prefix
, node
->p
.prefixlen
)];
318 route_lock_node (node
);
319 while (node
&& node
->info
== NULL
)
320 node
= route_next (node
);
325 route_unlock_node (node
);
327 if (! prefix_match ((struct prefix
*) &key
, &node
->p
))
331 ospf6_lsa_lock (lsa
);
337 ospf6_lsdb_type_router_next (u_int16_t type
, u_int32_t adv_router
,
338 struct ospf6_lsa
*lsa
)
340 struct ospf6_lsa
*next
= lsa
->next
;
344 if (next
->header
->type
!= type
||
345 next
->header
->adv_router
!= adv_router
)
350 ospf6_lsa_lock (next
);
351 ospf6_lsa_unlock (lsa
);
356 ospf6_lsdb_type_head (u_int16_t type
, struct ospf6_lsdb
*lsdb
)
358 struct route_node
*node
;
359 struct prefix_ipv6 key
;
360 struct ospf6_lsa
*lsa
;
362 memset (&key
, 0, sizeof (key
));
363 ospf6_lsdb_set_key (&key
, &type
, sizeof (type
));
365 /* Walk down tree. */
366 node
= lsdb
->table
->top
;
367 while (node
&& node
->p
.prefixlen
<= key
.prefixlen
&&
368 prefix_match (&node
->p
, (struct prefix
*) &key
))
369 node
= node
->link
[CHECK_BIT(&key
.prefix
, node
->p
.prefixlen
)];
372 route_lock_node (node
);
373 while (node
&& node
->info
== NULL
)
374 node
= route_next (node
);
379 route_unlock_node (node
);
381 if (! prefix_match ((struct prefix
*) &key
, &node
->p
))
385 ospf6_lsa_lock (lsa
);
391 ospf6_lsdb_type_next (u_int16_t type
, struct ospf6_lsa
*lsa
)
393 struct ospf6_lsa
*next
= lsa
->next
;
397 if (next
->header
->type
!= type
)
402 ospf6_lsa_lock (next
);
403 ospf6_lsa_unlock (lsa
);
408 ospf6_lsdb_remove_all (struct ospf6_lsdb
*lsdb
)
410 struct ospf6_lsa
*lsa
;
411 for (lsa
= ospf6_lsdb_head (lsdb
); lsa
; lsa
= ospf6_lsdb_next (lsa
))
412 ospf6_lsdb_remove (lsa
, lsdb
);
416 ospf6_lsdb_show (struct vty
*vty
, int level
,
417 u_int16_t
*type
, u_int32_t
*id
, u_int32_t
*adv_router
,
418 struct ospf6_lsdb
*lsdb
)
420 struct ospf6_lsa
*lsa
;
421 void (*showfunc
) (struct vty
*, struct ospf6_lsa
*) = NULL
;
423 if (level
== OSPF6_LSDB_SHOW_LEVEL_NORMAL
)
424 showfunc
= ospf6_lsa_show_summary
;
425 else if (level
== OSPF6_LSDB_SHOW_LEVEL_DETAIL
)
426 showfunc
= ospf6_lsa_show
;
427 else if (level
== OSPF6_LSDB_SHOW_LEVEL_INTERNAL
)
428 showfunc
= ospf6_lsa_show_internal
;
429 else if (level
== OSPF6_LSDB_SHOW_LEVEL_DUMP
)
430 showfunc
= ospf6_lsa_show_dump
;
432 if (type
&& id
&& adv_router
)
434 lsa
= ospf6_lsdb_lookup (*type
, *id
, *adv_router
, lsdb
);
437 if (level
== OSPF6_LSDB_SHOW_LEVEL_NORMAL
)
438 ospf6_lsa_show (vty
, lsa
);
440 (*showfunc
) (vty
, lsa
);
445 if (level
== OSPF6_LSDB_SHOW_LEVEL_NORMAL
)
446 ospf6_lsa_show_summary_header (vty
);
448 if (type
&& adv_router
)
449 lsa
= ospf6_lsdb_type_router_head (*type
, *adv_router
, lsdb
);
451 lsa
= ospf6_lsdb_type_head (*type
, lsdb
);
453 lsa
= ospf6_lsdb_head (lsdb
);
456 if ((! adv_router
|| lsa
->header
->adv_router
== *adv_router
) &&
457 (! id
|| lsa
->header
->id
== *id
))
458 (*showfunc
) (vty
, lsa
);
460 if (type
&& adv_router
)
461 lsa
= ospf6_lsdb_type_router_next (*type
, *adv_router
, lsa
);
463 lsa
= ospf6_lsdb_type_next (*type
, lsa
);
465 lsa
= ospf6_lsdb_next (lsa
);
469 /* Decide new Link State ID to originate.
470 note return value is network byte order */
472 ospf6_new_ls_id (u_int16_t type
, u_int32_t adv_router
,
473 struct ospf6_lsdb
*lsdb
)
475 struct ospf6_lsa
*lsa
;
478 for (lsa
= ospf6_lsdb_type_router_head (type
, adv_router
, lsdb
); lsa
;
479 lsa
= ospf6_lsdb_type_router_next (type
, adv_router
, lsa
))
481 if (ntohl (lsa
->header
->id
) < id
)
483 if (ntohl (lsa
->header
->id
) > id
)
488 return ((u_int32_t
) htonl (id
));
491 /* Decide new LS sequence number to originate.
492 note return value is network byte order */
494 ospf6_new_ls_seqnum (u_int16_t type
, u_int32_t id
, u_int32_t adv_router
,
495 struct ospf6_lsdb
*lsdb
)
497 struct ospf6_lsa
*lsa
;
498 signed long seqnum
= 0;
500 /* if current database copy not found, return InitialSequenceNumber */
501 lsa
= ospf6_lsdb_lookup (type
, id
, adv_router
, lsdb
);
503 seqnum
= INITIAL_SEQUENCE_NUMBER
;
505 seqnum
= (signed long) ntohl (lsa
->header
->seqnum
) + 1;
507 return ((u_int32_t
) htonl (seqnum
));