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