1/* 2 * Copyright (C) 2003 Yasuhiro Ohara 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" 27#include "prefix.h" 28#include "table.h" 29#include "vty.h" 30 31#include "ospf6_proto.h" 32#include "ospf6_lsa.h" 33#include "ospf6_lsdb.h" 34#include "ospf6d.h" 35 36struct ospf6_lsdb * 37ospf6_lsdb_create (void *data) 38{ 39 struct ospf6_lsdb *lsdb; 40 41 lsdb = XCALLOC (MTYPE_OSPF6_LSDB, sizeof (struct ospf6_lsdb)); 42 if (lsdb == NULL) 43 { 44 zlog_warn ("Can't malloc lsdb"); 45 return NULL; 46 } 47 memset (lsdb, 0, sizeof (struct ospf6_lsdb)); 48 49 lsdb->data = data; 50 lsdb->table = route_table_init (); 51 return lsdb; 52} 53 54void 55ospf6_lsdb_delete (struct ospf6_lsdb *lsdb) 56{ 57 if (lsdb != NULL) 58 { 59 ospf6_lsdb_remove_all (lsdb); 60 route_table_finish (lsdb->table); 61 XFREE (MTYPE_OSPF6_LSDB, lsdb); 62 } 63} 64 65static void 66ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len) 67{ 68 assert (key->prefixlen % 8 == 0); 69 70 memcpy ((caddr_t) &key->prefix + key->prefixlen / 8, 71 (caddr_t) value, len); 72 key->family = AF_INET6; 73 key->prefixlen += len * 8; 74} 75 76#ifdef DEBUG 77static void 78_lsdb_count_assert (struct ospf6_lsdb *lsdb) 79{ 80 struct ospf6_lsa *debug; 81 unsigned int num = 0; 82 for (debug = ospf6_lsdb_head (lsdb); debug; 83 debug = ospf6_lsdb_next (debug)) 84 num++; 85 86 if (num == lsdb->count) 87 return; 88 89 zlog_debug ("PANIC !! lsdb[%p]->count = %d, real = %d", 90 lsdb, lsdb->count, num); 91 for (debug = ospf6_lsdb_head (lsdb); debug; 92 debug = ospf6_lsdb_next (debug)) 93 zlog_debug ("%p %p %s lsdb[%p]", debug->prev, debug->next, debug->name, 94 debug->lsdb); 95 zlog_debug ("DUMP END"); 96 97 assert (num == lsdb->count); 98} 99#define ospf6_lsdb_count_assert(t) (_lsdb_count_assert (t)) 100#else /*DEBUG*/ 101#define ospf6_lsdb_count_assert(t) ((void) 0) 102#endif /*DEBUG*/ 103 104void 105ospf6_lsdb_add (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb) 106{ 107 struct prefix_ipv6 key; 108 struct route_node *current; 109 struct ospf6_lsa *old = NULL; 110 111 memset (&key, 0, sizeof (key)); 112 ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type)); 113 ospf6_lsdb_set_key (&key, &lsa->header->adv_router, 114 sizeof (lsa->header->adv_router)); 115 ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id)); 116 117 current = route_node_get (lsdb->table, (struct prefix *) &key); 118 old = current->info; 119 current->info = lsa; 120 lsa->rn = current; 121 ospf6_lsa_lock (lsa); 122 123 if (!old) 124 { 125 lsdb->count++; 126 127 if (OSPF6_LSA_IS_MAXAGE (lsa)) 128 { 129 if (lsdb->hook_remove) 130 (*lsdb->hook_remove) (lsa); 131 } 132 else 133 { 134 if (lsdb->hook_add) 135 (*lsdb->hook_add) (lsa); 136 } 137 } 138 else 139 { 140 if (OSPF6_LSA_IS_CHANGED (old, lsa)) 141 { 142 if (OSPF6_LSA_IS_MAXAGE (lsa)) 143 { 144 if (lsdb->hook_remove) 145 { 146 (*lsdb->hook_remove) (old); 147 (*lsdb->hook_remove) (lsa); 148 } 149 } 150 else if (OSPF6_LSA_IS_MAXAGE (old)) 151 { 152 if (lsdb->hook_add) 153 (*lsdb->hook_add) (lsa); 154 } 155 else 156 { 157 if (lsdb->hook_remove) 158 (*lsdb->hook_remove) (old); 159 if (lsdb->hook_add) 160 (*lsdb->hook_add) (lsa); 161 } 162 } 163 ospf6_lsa_unlock (old); 164 } 165 166 ospf6_lsdb_count_assert (lsdb); 167} 168 169void 170ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb) 171{ 172 struct route_node *node; 173 struct prefix_ipv6 key; 174 175 memset (&key, 0, sizeof (key)); 176 ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type)); 177 ospf6_lsdb_set_key (&key, &lsa->header->adv_router, 178 sizeof (lsa->header->adv_router)); 179 ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id)); 180 181 node = route_node_lookup (lsdb->table, (struct prefix *) &key); 182 assert (node && node->info == lsa); 183 184 node->info = NULL; 185 lsdb->count--; 186 187 if (lsdb->hook_remove) 188 (*lsdb->hook_remove) (lsa); 189 190 route_unlock_node (node); /* to free the lookup lock */ 191 route_unlock_node (node); /* to free the original lock */ 192 ospf6_lsa_unlock (lsa); 193 194 ospf6_lsdb_count_assert (lsdb); 195} 196 197struct ospf6_lsa * 198ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router, 199 struct ospf6_lsdb *lsdb) 200{ 201 struct route_node *node; 202 struct prefix_ipv6 key; 203 204 if (lsdb == NULL) 205 return NULL; 206 207 memset (&key, 0, sizeof (key)); 208 ospf6_lsdb_set_key (&key, &type, sizeof (type)); 209 ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router)); 210 ospf6_lsdb_set_key (&key, &id, sizeof (id)); 211 212 node = route_node_lookup (lsdb->table, (struct prefix *) &key); 213 if (node == NULL || node->info == NULL) 214 return NULL; 215 216 route_unlock_node (node); 217 return (struct ospf6_lsa *) node->info; 218} 219 220struct ospf6_lsa * 221ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router, 222 struct ospf6_lsdb *lsdb) 223{ 224 struct route_node *node; 225 struct route_node *matched = NULL; 226 struct prefix_ipv6 key; 227 struct prefix *p; 228 229 if (lsdb == NULL) 230 return NULL; 231 232 memset (&key, 0, sizeof (key)); 233 ospf6_lsdb_set_key (&key, &type, sizeof (type)); 234 ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router)); 235 ospf6_lsdb_set_key (&key, &id, sizeof (id)); 236 p = (struct prefix *) &key; 237 238 { 239 char buf[64]; 240 prefix2str (p, buf, sizeof (buf)); 241 zlog_debug ("lsdb_lookup_next: key: %s", buf); 242 } 243 244 node = lsdb->table->top; 245 /* walk down tree. */ 246 while (node && node->p.prefixlen <= p->prefixlen && 247 prefix_match (&node->p, p)) 248 { 249 matched = node; 250 node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)]; 251 } 252 253 if (matched) 254 node = matched; 255 else 256 node = lsdb->table->top; 257 route_lock_node (node); 258 259 /* skip to real existing entry */ 260 while (node && node->info == NULL) 261 node = route_next (node); 262 263 if (! node) 264 return NULL; 265 266 if (prefix_same (&node->p, p)) 267 { 268 node = route_next (node); 269 while (node && node->info == NULL) 270 node = route_next (node); 271 } 272 273 if (! node) 274 return NULL; 275 276 route_unlock_node (node); 277 return (struct ospf6_lsa *) node->info; 278} 279 280/* Iteration function */ 281struct ospf6_lsa * 282ospf6_lsdb_head (struct ospf6_lsdb *lsdb) 283{ 284 struct route_node *node; 285 286 node = route_top (lsdb->table); 287 if (node == NULL) 288 return NULL; 289 290 /* skip to the existing lsdb entry */ 291 while (node && node->info == NULL) 292 node = route_next (node); 293 if (node == NULL) 294 return NULL; 295 296 if (node->info) 297 ospf6_lsa_lock ((struct ospf6_lsa *) node->info); 298 return (struct ospf6_lsa *) node->info; 299} 300 301struct ospf6_lsa * 302ospf6_lsdb_next (struct ospf6_lsa *lsa) 303{ 304 struct route_node *node = lsa->rn; 305 struct ospf6_lsa *next = NULL; 306 307 do { 308 node = route_next (node); 309 } while (node && node->info == NULL); 310 311 if ((node != NULL) && (node->info != NULL)) 312 { 313 next = node->info; 314 ospf6_lsa_lock (next); 315 } 316 317 ospf6_lsa_unlock (lsa); 318 return next; 319} 320 321struct ospf6_lsa * 322ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router, 323 struct ospf6_lsdb *lsdb) 324{ 325 struct route_node *node; 326 struct prefix_ipv6 key; 327 struct ospf6_lsa *lsa; 328 329 memset (&key, 0, sizeof (key)); 330 ospf6_lsdb_set_key (&key, &type, sizeof (type)); 331 ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router)); 332 333 node = lsdb->table->top; 334 335 /* Walk down tree. */ 336 while (node && node->p.prefixlen <= key.prefixlen && 337 prefix_match (&node->p, (struct prefix *) &key)) 338 node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)]; 339 340 if (node) 341 route_lock_node (node); 342 while (node && node->info == NULL) 343 node = route_next (node); 344 345 if (node == NULL) 346 return NULL; 347 348 if (! prefix_match ((struct prefix *) &key, &node->p)) 349 return NULL; 350 351 lsa = node->info; 352 ospf6_lsa_lock (lsa); 353 354 return lsa; 355} 356 357struct ospf6_lsa * 358ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router, 359 struct ospf6_lsa *lsa) 360{ 361 struct ospf6_lsa *next = ospf6_lsdb_next(lsa); 362 363 if (next) 364 { 365 if (next->header->type != type || 366 next->header->adv_router != adv_router) 367 { 368 route_unlock_node (next->rn); 369 ospf6_lsa_unlock (next); 370 next = NULL; 371 } 372 } 373 374 return next; 375} 376 377struct ospf6_lsa * 378ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb) 379{ 380 struct route_node *node; 381 struct prefix_ipv6 key; 382 struct ospf6_lsa *lsa; 383 384 memset (&key, 0, sizeof (key)); 385 ospf6_lsdb_set_key (&key, &type, sizeof (type)); 386 387 /* Walk down tree. */ 388 node = lsdb->table->top; 389 while (node && node->p.prefixlen <= key.prefixlen && 390 prefix_match (&node->p, (struct prefix *) &key)) 391 node = node->link[prefix6_bit(&key.prefix, node->p.prefixlen)]; 392 393 if (node) 394 route_lock_node (node); 395 while (node && node->info == NULL) 396 node = route_next (node); 397 398 if (node == NULL) 399 return NULL; 400 401 if (! prefix_match ((struct prefix *) &key, &node->p)) 402 return NULL; 403 404 lsa = node->info; 405 ospf6_lsa_lock (lsa); 406 407 return lsa; 408} 409 410struct ospf6_lsa * 411ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa) 412{ 413 struct ospf6_lsa *next = ospf6_lsdb_next (lsa); 414 415 if (next) 416 { 417 if (next->header->type != type) 418 { 419 route_unlock_node (next->rn); 420 ospf6_lsa_unlock (next); 421 next = NULL; 422 } 423 } 424 425 return next; 426} 427 428void 429ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb) 430{ 431 struct ospf6_lsa *lsa; 432 433 if (lsdb == NULL) 434 return; 435 436 for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa)) 437 ospf6_lsdb_remove (lsa, lsdb); 438} 439 440void 441ospf6_lsdb_lsa_unlock (struct ospf6_lsa *lsa) 442{ 443 if (lsa != NULL) 444 { 445 if (lsa->rn != NULL) 446 route_unlock_node (lsa->rn); 447 ospf6_lsa_unlock (lsa); 448 } 449} 450 451int 452ospf6_lsdb_maxage_remover (struct ospf6_lsdb *lsdb) 453{ 454 int reschedule = 0; 455 struct ospf6_lsa *lsa; 456 457 for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa)) 458 { 459 if (! OSPF6_LSA_IS_MAXAGE (lsa)) 460 continue; 461 if (lsa->retrans_count != 0) 462 { 463 reschedule = 1; 464 continue; 465 } 466 if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type)) 467 zlog_debug ("Remove MaxAge %s", lsa->name); 468 if (CHECK_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED)) 469 { 470 UNSET_FLAG(lsa->flag, OSPF6_LSA_SEQWRAPPED); 471 /* 472 * lsa->header->age = 0; 473 */ 474 lsa->header->seqnum = htonl(OSPF_MAX_SEQUENCE_NUMBER + 1); 475 ospf6_lsa_checksum (lsa->header); 476 477 THREAD_OFF(lsa->refresh); 478 thread_execute (master, ospf6_lsa_refresh, lsa, 0); 479 } else { 480 ospf6_lsdb_remove (lsa, lsdb); 481 } 482 } 483 484 return (reschedule); 485} 486 487void 488ospf6_lsdb_show (struct vty *vty, enum ospf_lsdb_show_level level, 489 u_int16_t *type, u_int32_t *id, u_int32_t *adv_router, 490 struct ospf6_lsdb *lsdb) 491{ 492 struct ospf6_lsa *lsa; 493 void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL; 494 495 switch (level) 496 { 497 case OSPF6_LSDB_SHOW_LEVEL_DETAIL: 498 showfunc = ospf6_lsa_show; 499 break; 500 case OSPF6_LSDB_SHOW_LEVEL_INTERNAL: 501 showfunc = ospf6_lsa_show_internal; 502 break; 503 case OSPF6_LSDB_SHOW_LEVEL_DUMP: 504 showfunc = ospf6_lsa_show_dump; 505 break; 506 case OSPF6_LSDB_SHOW_LEVEL_NORMAL: 507 default: 508 showfunc = ospf6_lsa_show_summary; 509 } 510 511 if (type && id && adv_router) 512 { 513 lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb); 514 if (lsa) 515 { 516 if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL) 517 ospf6_lsa_show (vty, lsa); 518 else 519 (*showfunc) (vty, lsa); 520 } 521 return; 522 } 523 524 if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL) 525 ospf6_lsa_show_summary_header (vty); 526 527 if (type && adv_router) 528 lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb); 529 else if (type) 530 lsa = ospf6_lsdb_type_head (*type, lsdb); 531 else 532 lsa = ospf6_lsdb_head (lsdb); 533 while (lsa) 534 { 535 if ((! adv_router || lsa->header->adv_router == *adv_router) && 536 (! id || lsa->header->id == *id)) 537 (*showfunc) (vty, lsa); 538 539 if (type && adv_router) 540 lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa); 541 else if (type) 542 lsa = ospf6_lsdb_type_next (*type, lsa); 543 else 544 lsa = ospf6_lsdb_next (lsa); 545 } 546} 547 548/* Decide new Link State ID to originate. 549 note return value is network byte order */ 550u_int32_t 551ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router, 552 struct ospf6_lsdb *lsdb) 553{ 554 struct ospf6_lsa *lsa; 555 u_int32_t id = 1; 556 557 for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa; 558 lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa)) 559 { 560 if (ntohl (lsa->header->id) < id) 561 continue; 562 if (ntohl (lsa->header->id) > id) 563 { 564 ospf6_lsdb_lsa_unlock (lsa); 565 break; 566 } 567 id++; 568 } 569 570 return ((u_int32_t) htonl (id)); 571} 572 573/* Decide new LS sequence number to originate. 574 note return value is network byte order */ 575u_int32_t 576ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router, 577 struct ospf6_lsdb *lsdb) 578{ 579 struct ospf6_lsa *lsa; 580 signed long seqnum = 0; 581 582 /* if current database copy not found, return InitialSequenceNumber */ 583 lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb); 584 if (lsa == NULL) 585 seqnum = OSPF_INITIAL_SEQUENCE_NUMBER; 586 else 587 seqnum = (signed long) ntohl (lsa->header->seqnum) + 1; 588 589 return ((u_int32_t) htonl (seqnum)); 590} 591 592 593