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