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