ospf6d/ospf6_lsdb.c

   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   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
  65 static void
  66 ospf6_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
  77 static 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
 104 void
 105 ospf6_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
 169 void
 170 ospf6_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
 197 struct ospf6_lsa *
 198 ospf6_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
 220 struct ospf6_lsa *
 221 ospf6_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 */
 281 struct ospf6_lsa *
 282 ospf6_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
 301 struct ospf6_lsa *
 302 ospf6_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
 321 struct ospf6_lsa *
 322 ospf6_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
 357 struct ospf6_lsa *
 358 ospf6_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
 377 struct ospf6_lsa *
 378 ospf6_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
 410 struct ospf6_lsa *
 411 ospf6_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
 428 void
 429 ospf6_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
 440 void
 441 ospf6_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
 451 int
 452 ospf6_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
 487 void
 488 ospf6_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 */
 550 u_int32_t
 551 ospf6_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 */
 575 u_int32_t
 576 ospf6_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