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   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 /* Macro version of check_bit (). */
 262 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
 263
 264 struct ospf6_lsa *
 265 ospf6_lsdb_lookup_next (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 266                         struct ospf6_lsdb *lsdb)
 267 {
 268   struct route_node *node;
 269   struct route_node *matched = NULL;
 270   struct prefix_ipv6 key;
 271   struct prefix *p;
 272
 273   if (lsdb == NULL)
 274     return NULL;
 275
 276   memset (&key, 0, sizeof (key));
 277   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 278   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 279   ospf6_lsdb_set_key (&key, &id, sizeof (id));
 280   p = (struct prefix *) &key;
 281
 282   {
 283     char buf[64];
 284     prefix2str (p, buf, sizeof (buf));
 285     zlog_debug ("lsdb_lookup_next: key: %s", buf);
 286   }
 287
 288   node = lsdb->table->top;
 289   /* walk down tree. */
 290   while (node && node->p.prefixlen <= p->prefixlen &&
 291          prefix_match (&node->p, p))
 292     {
 293       matched = node;
 294       node = node->link[CHECK_BIT(&p->u.prefix, node->p.prefixlen)];
 295     }
 296
 297   if (matched)
 298     node = matched;
 299   else
 300     node = lsdb->table->top;
 301   route_lock_node (node);
 302
 303   /* skip to real existing entry */
 304   while (node && node->info == NULL)
 305     node = route_next (node);
 306
 307   if (! node)
 308     return NULL;
 309
 310   if (prefix_same (&node->p, p))
 311     {
 312       struct route_node *prev = node;
 313       struct ospf6_lsa *lsa_prev;
 314       struct ospf6_lsa *lsa_next;
 315
 316       node = route_next (node);
 317       while (node && node->info == NULL)
 318         node = route_next (node);
 319
 320       lsa_prev = prev->info;
 321       lsa_next = (node ? node->info : NULL);
 322       assert (lsa_prev);
 323       assert (lsa_prev->next == lsa_next);
 324       if (lsa_next)
 325         assert (lsa_next->prev == lsa_prev);
 326       zlog_debug ("lsdb_lookup_next: assert OK with previous LSA");
 327     }
 328
 329   if (! node)
 330     return NULL;
 331
 332   route_unlock_node (node);
 333   return (struct ospf6_lsa *) node->info;
 334 }
 335
 336 /* Iteration function */
 337 struct ospf6_lsa *
 338 ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
 339 {
 340   struct route_node *node;
 341
 342   node = route_top (lsdb->table);
 343   if (node == NULL)
 344     return NULL;
 345
 346   /* skip to the existing lsdb entry */
 347   while (node && node->info == NULL)
 348     node = route_next (node);
 349   if (node == NULL)
 350     return NULL;
 351
 352   route_unlock_node (node);
 353   if (node->info)
 354     ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
 355   return (struct ospf6_lsa *) node->info;
 356 }
 357
 358 struct ospf6_lsa *
 359 ospf6_lsdb_next (struct ospf6_lsa *lsa)
 360 {
 361   struct ospf6_lsa *next = lsa->next;
 362
 363   ospf6_lsa_unlock (lsa);
 364   if (next)
 365     ospf6_lsa_lock (next);
 366
 367   return next;
 368 }
 369
 370 struct ospf6_lsa *
 371 ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
 372                              struct ospf6_lsdb *lsdb)
 373 {
 374   struct route_node *node;
 375   struct prefix_ipv6 key;
 376   struct ospf6_lsa *lsa;
 377
 378   memset (&key, 0, sizeof (key));
 379   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 380   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 381
 382   node = lsdb->table->top;
 383
 384   /* Walk down tree. */
 385   while (node && node->p.prefixlen <= key.prefixlen &&
 386          prefix_match (&node->p, (struct prefix *) &key))
 387     node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
 388
 389   if (node)
 390     route_lock_node (node);
 391   while (node && node->info == NULL)
 392     node = route_next (node);
 393
 394   if (node == NULL)
 395     return NULL;
 396   else
 397     route_unlock_node (node);
 398
 399   if (! prefix_match ((struct prefix *) &key, &node->p))
 400     return NULL;
 401
 402   lsa = node->info;
 403   ospf6_lsa_lock (lsa);
 404
 405   return lsa;
 406 }
 407
 408 struct ospf6_lsa *
 409 ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
 410                              struct ospf6_lsa *lsa)
 411 {
 412   struct ospf6_lsa *next = lsa->next;
 413
 414   if (next)
 415     {
 416       if (next->header->type != type ||
 417           next->header->adv_router != adv_router)
 418         next = NULL;
 419     }
 420
 421   if (next)
 422     ospf6_lsa_lock (next);
 423   ospf6_lsa_unlock (lsa);
 424   return next;
 425 }
 426
 427 struct ospf6_lsa *
 428 ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
 429 {
 430   struct route_node *node;
 431   struct prefix_ipv6 key;
 432   struct ospf6_lsa *lsa;
 433
 434   memset (&key, 0, sizeof (key));
 435   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 436
 437   /* Walk down tree. */
 438   node = lsdb->table->top;
 439   while (node && node->p.prefixlen <= key.prefixlen &&
 440          prefix_match (&node->p, (struct prefix *) &key))
 441     node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
 442
 443   if (node)
 444     route_lock_node (node);
 445   while (node && node->info == NULL)
 446     node = route_next (node);
 447
 448   if (node == NULL)
 449     return NULL;
 450   else
 451     route_unlock_node (node);
 452
 453   if (! prefix_match ((struct prefix *) &key, &node->p))
 454     return NULL;
 455
 456   lsa = node->info;
 457   ospf6_lsa_lock (lsa);
 458
 459   return lsa;
 460 }
 461
 462 struct ospf6_lsa *
 463 ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
 464 {
 465   struct ospf6_lsa *next = lsa->next;
 466
 467   if (next)
 468     {
 469       if (next->header->type != type)
 470         next = NULL;
 471     }
 472
 473   if (next)
 474     ospf6_lsa_lock (next);
 475   ospf6_lsa_unlock (lsa);
 476   return next;
 477 }
 478
 479 void
 480 ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
 481 {
 482   struct ospf6_lsa *lsa;
 483   for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
 484     ospf6_lsdb_remove (lsa, lsdb);
 485 }
 486
 487 void
 488 ospf6_lsdb_show (struct vty *vty, int 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   if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 496     showfunc = ospf6_lsa_show_summary;
 497   else if (level == OSPF6_LSDB_SHOW_LEVEL_DETAIL)
 498     showfunc = ospf6_lsa_show;
 499   else if (level == OSPF6_LSDB_SHOW_LEVEL_INTERNAL)
 500     showfunc = ospf6_lsa_show_internal;
 501   else if (level == OSPF6_LSDB_SHOW_LEVEL_DUMP)
 502     showfunc = ospf6_lsa_show_dump;
 503
 504   if (type && id && adv_router)
 505     {
 506       lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
 507       if (lsa)
 508         {
 509           if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 510             ospf6_lsa_show (vty, lsa);
 511           else
 512             (*showfunc) (vty, lsa);
 513         }
 514       return;
 515     }
 516
 517   if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 518     ospf6_lsa_show_summary_header (vty);
 519
 520   if (type && adv_router)
 521     lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
 522   else if (type)
 523     lsa = ospf6_lsdb_type_head (*type, lsdb);
 524   else
 525     lsa = ospf6_lsdb_head (lsdb);
 526   while (lsa)
 527     {
 528       if ((! adv_router || lsa->header->adv_router == *adv_router) &&
 529           (! id || lsa->header->id == *id))
 530         (*showfunc) (vty, lsa);
 531
 532       if (type && adv_router)
 533         lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
 534       else if (type)
 535         lsa = ospf6_lsdb_type_next (*type, lsa);
 536       else
 537         lsa = ospf6_lsdb_next (lsa);
 538     }
 539 }
 540
 541 /* Decide new Link State ID to originate.
 542    note return value is network byte order */
 543 u_int32_t
 544 ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
 545                  struct ospf6_lsdb *lsdb)
 546 {
 547   struct ospf6_lsa *lsa;
 548   u_int32_t id = 1;
 549
 550   for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
 551        lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
 552     {
 553       if (ntohl (lsa->header->id) < id)
 554         continue;
 555       if (ntohl (lsa->header->id) > id)
 556       {
 557         ospf6_lsa_unlock (lsa);
 558         break;
 559       }
 560       id++;
 561     }
 562
 563   return ((u_int32_t) htonl (id));
 564 }
 565
 566 /* Decide new LS sequence number to originate.
 567    note return value is network byte order */
 568 u_int32_t
 569 ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 570                      struct ospf6_lsdb *lsdb)
 571 {
 572   struct ospf6_lsa *lsa;
 573   signed long seqnum = 0;
 574
 575   /* if current database copy not found, return InitialSequenceNumber */
 576   lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
 577   if (lsa == NULL)
 578     seqnum = INITIAL_SEQUENCE_NUMBER;
 579   else
 580     seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
 581
 582   return ((u_int32_t) htonl (seqnum));
 583 }
 584
 585