]>
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 | * | |
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. | |
20 | */ | |
21 | ||
22 | #include <zebra.h> | |
23 | ||
24 | #include "memory.h" | |
25 | #include "log.h" | |
26 | #include "command.h" | |
508e53e2 | 27 | #include "prefix.h" |
28 | #include "table.h" | |
718e3744 | 29 | |
508e53e2 | 30 | #include "ospf6d.h" |
31 | #include "ospf6_proto.h" | |
32 | #include "ospf6_lsa.h" | |
718e3744 | 33 | #include "ospf6_lsdb.h" |
34 | ||
718e3744 | 35 | struct ospf6_lsdb * |
36 | ospf6_lsdb_create () | |
37 | { | |
38 | struct ospf6_lsdb *lsdb; | |
39 | ||
40 | lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb)); | |
41 | if (lsdb == NULL) | |
42 | { | |
43 | zlog_warn ("Can't malloc lsdb"); | |
44 | return NULL; | |
45 | } | |
46 | memset (lsdb, 0, sizeof (struct ospf6_lsdb)); | |
47 | ||
48 | lsdb->table = route_table_init (); | |
49 | return lsdb; | |
50 | } | |
51 | ||
52 | void | |
53 | ospf6_lsdb_delete (struct ospf6_lsdb *lsdb) | |
54 | { | |
55 | ospf6_lsdb_remove_all (lsdb); | |
56 | route_table_finish (lsdb->table); | |
57 | XFREE (MTYPE_OSPF6_LSDB, lsdb); | |
58 | } | |
59 | ||
60 | static void | |
508e53e2 | 61 | ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len) |
718e3744 | 62 | { |
508e53e2 | 63 | assert (key->prefixlen % 8 == 0); |
718e3744 | 64 | |
508e53e2 | 65 | memcpy ((caddr_t) &key->prefix + key->prefixlen / 8, |
66 | (caddr_t) value, len); | |
67 | key->family = AF_INET6; | |
68 | key->prefixlen += len * 8; | |
69 | } | |
718e3744 | 70 | |
508e53e2 | 71 | #ifndef NDEBUG |
72 | static void | |
73 | _lsdb_count_assert (struct ospf6_lsdb *lsdb) | |
74 | { | |
75 | struct ospf6_lsa *debug; | |
76 | int num = 0; | |
77 | for (debug = ospf6_lsdb_head (lsdb); debug; | |
78 | debug = ospf6_lsdb_next (debug)) | |
79 | num++; | |
718e3744 | 80 | |
508e53e2 | 81 | if (num == lsdb->count) |
82 | return; | |
83 | ||
84 | if (IS_OSPF6_DEBUG_LSA (DATABASE)) | |
85 | { | |
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", debug->prev, debug->next, debug->name); | |
91 | zlog_info ("DUMP END"); | |
92 | } | |
93 | assert (num == lsdb->count); | |
718e3744 | 94 | } |
508e53e2 | 95 | #define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t)) |
96 | #else /*NDEBUG*/ | |
97 | #define ospf6_lsdb_count_assert(t) ((void) 0) | |
98 | #endif /*NDEBUG*/ | |
718e3744 | 99 | |
100 | void | |
101 | ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb) | |
102 | { | |
718e3744 | 103 | struct prefix_ipv6 key; |
508e53e2 | 104 | struct route_node *current, *nextnode, *prevnode; |
105 | struct ospf6_lsa *next, *prev, *old = NULL; | |
106 | ||
107 | memset (&key, 0, sizeof (key)); | |
108 | ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type)); | |
109 | ospf6_lsdb_set_key (&key, &lsa->header->adv_router, | |
110 | sizeof (lsa->header->adv_router)); | |
111 | ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id)); | |
112 | ||
113 | current = route_node_get (lsdb->table, (struct prefix *) &key); | |
114 | old = current->info; | |
115 | current->info = lsa; | |
718e3744 | 116 | ospf6_lsa_lock (lsa); |
117 | ||
118 | if (old) | |
508e53e2 | 119 | { |
120 | if (old->prev) | |
121 | old->prev->next = lsa; | |
122 | if (old->next) | |
123 | old->next->prev = lsa; | |
124 | lsa->next = old->next; | |
125 | lsa->prev = old->prev; | |
126 | } | |
718e3744 | 127 | else |
508e53e2 | 128 | { |
129 | /* next link */ | |
130 | nextnode = current; | |
131 | route_lock_node (nextnode); | |
132 | do { | |
133 | nextnode = route_next (nextnode); | |
134 | } while (nextnode && nextnode->info == NULL); | |
135 | if (nextnode == NULL) | |
136 | lsa->next = NULL; | |
137 | else | |
138 | { | |
139 | next = nextnode->info; | |
140 | lsa->next = next; | |
141 | next->prev = lsa; | |
142 | route_unlock_node (nextnode); | |
143 | } | |
718e3744 | 144 | |
508e53e2 | 145 | /* prev link */ |
146 | prevnode = current; | |
147 | route_lock_node (prevnode); | |
148 | do { | |
149 | prevnode = route_prev (prevnode); | |
150 | } while (prevnode && prevnode->info == NULL); | |
151 | if (prevnode == NULL) | |
152 | lsa->prev = NULL; | |
153 | else | |
154 | { | |
155 | prev = prevnode->info; | |
156 | lsa->prev = prev; | |
157 | prev->next = lsa; | |
158 | route_unlock_node (prevnode); | |
159 | } | |
718e3744 | 160 | |
508e53e2 | 161 | lsdb->count++; |
162 | } | |
718e3744 | 163 | |
508e53e2 | 164 | if (old) |
718e3744 | 165 | { |
508e53e2 | 166 | if (OSPF6_LSA_IS_CHANGED (old, lsa)) |
167 | { | |
168 | if (OSPF6_LSA_IS_MAXAGE (lsa)) | |
169 | { | |
170 | if (lsdb->hook_remove) | |
171 | { | |
172 | (*lsdb->hook_remove) (old); | |
173 | (*lsdb->hook_remove) (lsa); | |
174 | } | |
175 | } | |
176 | else | |
177 | { | |
178 | if (lsdb->hook_remove) | |
179 | (*lsdb->hook_remove) (old); | |
180 | if (lsdb->hook_add) | |
181 | (*lsdb->hook_add) (lsa); | |
182 | } | |
183 | } | |
718e3744 | 184 | } |
508e53e2 | 185 | else if (OSPF6_LSA_IS_MAXAGE (lsa)) |
718e3744 | 186 | { |
508e53e2 | 187 | if (lsdb->hook_remove) |
188 | (*lsdb->hook_remove) (lsa); | |
189 | } | |
190 | else | |
191 | { | |
192 | if (lsdb->hook_add) | |
193 | (*lsdb->hook_add) (lsa); | |
718e3744 | 194 | } |
195 | ||
508e53e2 | 196 | if (old) |
197 | ospf6_lsa_unlock (old); | |
718e3744 | 198 | |
508e53e2 | 199 | ospf6_lsdb_count_assert (lsdb); |
718e3744 | 200 | } |
201 | ||
718e3744 | 202 | void |
508e53e2 | 203 | ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb) |
718e3744 | 204 | { |
508e53e2 | 205 | struct route_node *node; |
206 | struct prefix_ipv6 key; | |
718e3744 | 207 | |
508e53e2 | 208 | memset (&key, 0, sizeof (key)); |
209 | ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type)); | |
210 | ospf6_lsdb_set_key (&key, &lsa->header->adv_router, | |
211 | sizeof (lsa->header->adv_router)); | |
212 | ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id)); | |
718e3744 | 213 | |
508e53e2 | 214 | node = route_node_lookup (lsdb->table, (struct prefix *) &key); |
215 | assert (node && node->info == lsa); | |
718e3744 | 216 | |
508e53e2 | 217 | if (lsa->prev) |
218 | lsa->prev->next = lsa->next; | |
219 | if (lsa->next) | |
220 | lsa->next->prev = lsa->prev; | |
718e3744 | 221 | |
508e53e2 | 222 | node->info = NULL; |
223 | lsdb->count--; | |
718e3744 | 224 | |
508e53e2 | 225 | if (lsdb->hook_remove) |
226 | (*lsdb->hook_remove) (lsa); | |
718e3744 | 227 | |
508e53e2 | 228 | ospf6_lsa_unlock (lsa); |
229 | route_unlock_node (node); | |
230 | ospf6_lsdb_count_assert (lsdb); | |
718e3744 | 231 | } |
232 | ||
508e53e2 | 233 | struct ospf6_lsa * |
234 | ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router, | |
235 | struct ospf6_lsdb *lsdb) | |
718e3744 | 236 | { |
508e53e2 | 237 | struct route_node *node; |
238 | struct prefix_ipv6 key; | |
718e3744 | 239 | |
508e53e2 | 240 | if (lsdb == NULL) |
241 | return NULL; | |
718e3744 | 242 | |
508e53e2 | 243 | memset (&key, 0, sizeof (key)); |
244 | ospf6_lsdb_set_key (&key, &type, sizeof (type)); | |
245 | ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router)); | |
246 | ospf6_lsdb_set_key (&key, &id, sizeof (id)); | |
718e3744 | 247 | |
508e53e2 | 248 | node = route_node_lookup (lsdb->table, (struct prefix *) &key); |
249 | if (node == NULL || node->info == NULL) | |
250 | return NULL; | |
251 | return (struct ospf6_lsa *) node->info; | |
718e3744 | 252 | } |
253 | ||
508e53e2 | 254 | /* Iteration function */ |
255 | struct ospf6_lsa * | |
256 | ospf6_lsdb_head (struct ospf6_lsdb *lsdb) | |
718e3744 | 257 | { |
508e53e2 | 258 | struct route_node *node; |
259 | ||
260 | node = route_top (lsdb->table); | |
261 | if (node == NULL) | |
262 | return NULL; | |
263 | ||
264 | /* skip to the existing lsdb entry */ | |
265 | while (node && node->info == NULL) | |
266 | node = route_next (node); | |
267 | if (node == NULL) | |
268 | return NULL; | |
269 | ||
270 | route_unlock_node (node); | |
271 | if (node->info) | |
272 | ospf6_lsa_lock ((struct ospf6_lsa *) node->info); | |
273 | return (struct ospf6_lsa *) node->info; | |
718e3744 | 274 | } |
275 | ||
276 | struct ospf6_lsa * | |
508e53e2 | 277 | ospf6_lsdb_next (struct ospf6_lsa *lsa) |
718e3744 | 278 | { |
508e53e2 | 279 | struct ospf6_lsa *next = lsa->next; |
718e3744 | 280 | |
508e53e2 | 281 | ospf6_lsa_unlock (lsa); |
282 | if (next) | |
283 | ospf6_lsa_lock (next); | |
718e3744 | 284 | |
508e53e2 | 285 | return next; |
718e3744 | 286 | } |
287 | ||
508e53e2 | 288 | /* Macro version of check_bit (). */ |
289 | #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1) | |
718e3744 | 290 | |
508e53e2 | 291 | struct ospf6_lsa * |
292 | ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router, | |
293 | struct ospf6_lsdb *lsdb) | |
294 | { | |
295 | struct route_node *node; | |
296 | struct prefix_ipv6 key; | |
297 | struct ospf6_lsa *lsa; | |
718e3744 | 298 | |
508e53e2 | 299 | memset (&key, 0, sizeof (key)); |
300 | ospf6_lsdb_set_key (&key, &type, sizeof (type)); | |
301 | ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router)); | |
718e3744 | 302 | |
508e53e2 | 303 | node = lsdb->table->top; |
718e3744 | 304 | |
508e53e2 | 305 | /* Walk down tree. */ |
306 | while (node && node->p.prefixlen <= key.prefixlen && | |
307 | prefix_match (&node->p, (struct prefix *) &key)) | |
308 | node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)]; | |
718e3744 | 309 | |
508e53e2 | 310 | if (node) |
311 | route_lock_node (node); | |
312 | while (node && node->info == NULL) | |
313 | node = route_next (node); | |
718e3744 | 314 | |
508e53e2 | 315 | if (node == NULL) |
316 | return NULL; | |
317 | else | |
318 | route_unlock_node (node); | |
718e3744 | 319 | |
508e53e2 | 320 | if (! prefix_match ((struct prefix *) &key, &node->p)) |
321 | return NULL; | |
718e3744 | 322 | |
508e53e2 | 323 | lsa = node->info; |
324 | ospf6_lsa_lock (lsa); | |
718e3744 | 325 | |
508e53e2 | 326 | return lsa; |
718e3744 | 327 | } |
328 | ||
508e53e2 | 329 | struct ospf6_lsa * |
330 | ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router, | |
331 | struct ospf6_lsa *lsa) | |
718e3744 | 332 | { |
508e53e2 | 333 | struct ospf6_lsa *next = lsa->next; |
718e3744 | 334 | |
508e53e2 | 335 | if (next) |
718e3744 | 336 | { |
508e53e2 | 337 | if (next->header->type != type || |
338 | next->header->adv_router != adv_router) | |
339 | next = NULL; | |
718e3744 | 340 | } |
718e3744 | 341 | |
508e53e2 | 342 | if (next) |
343 | ospf6_lsa_lock (next); | |
344 | ospf6_lsa_unlock (lsa); | |
345 | return next; | |
718e3744 | 346 | } |
347 | ||
508e53e2 | 348 | struct ospf6_lsa * |
349 | ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb) | |
718e3744 | 350 | { |
508e53e2 | 351 | struct route_node *node; |
352 | struct prefix_ipv6 key; | |
353 | struct ospf6_lsa *lsa; | |
718e3744 | 354 | |
508e53e2 | 355 | memset (&key, 0, sizeof (key)); |
356 | ospf6_lsdb_set_key (&key, &type, sizeof (type)); | |
718e3744 | 357 | |
508e53e2 | 358 | /* Walk down tree. */ |
359 | node = lsdb->table->top; | |
360 | while (node && node->p.prefixlen <= key.prefixlen && | |
361 | prefix_match (&node->p, (struct prefix *) &key)) | |
362 | node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)]; | |
718e3744 | 363 | |
508e53e2 | 364 | if (node) |
365 | route_lock_node (node); | |
366 | while (node && node->info == NULL) | |
367 | node = route_next (node); | |
718e3744 | 368 | |
508e53e2 | 369 | if (node == NULL) |
370 | return NULL; | |
371 | else | |
372 | route_unlock_node (node); | |
718e3744 | 373 | |
508e53e2 | 374 | if (! prefix_match ((struct prefix *) &key, &node->p)) |
375 | return NULL; | |
718e3744 | 376 | |
508e53e2 | 377 | lsa = node->info; |
378 | ospf6_lsa_lock (lsa); | |
718e3744 | 379 | |
508e53e2 | 380 | return lsa; |
718e3744 | 381 | } |
382 | ||
508e53e2 | 383 | struct ospf6_lsa * |
384 | ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa) | |
718e3744 | 385 | { |
508e53e2 | 386 | struct ospf6_lsa *next = lsa->next; |
718e3744 | 387 | |
508e53e2 | 388 | if (next) |
718e3744 | 389 | { |
508e53e2 | 390 | if (next->header->type != type) |
391 | next = NULL; | |
718e3744 | 392 | } |
393 | ||
508e53e2 | 394 | if (next) |
395 | ospf6_lsa_lock (next); | |
396 | ospf6_lsa_unlock (lsa); | |
397 | return next; | |
718e3744 | 398 | } |
399 | ||
718e3744 | 400 | void |
508e53e2 | 401 | ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb) |
718e3744 | 402 | { |
508e53e2 | 403 | struct ospf6_lsa *lsa; |
404 | for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa)) | |
405 | ospf6_lsdb_remove (lsa, lsdb); | |
718e3744 | 406 | } |
407 | ||
408 |