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 ()
  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->table = route_table_init ();
  50   return lsdb;
  51 }
  52
  53 void
  54 ospf6_lsdb_delete (struct ospf6_lsdb *lsdb)
  55 {
  56   ospf6_lsdb_remove_all (lsdb);
  57   route_table_finish (lsdb->table);
  58   XFREE (MTYPE_OSPF6_LSDB, lsdb);
  59 }
  60
  61 static void
  62 ospf6_lsdb_set_key (struct prefix_ipv6 *key, void *value, int len)
  63 {
  64   assert (key->prefixlen % 8 == 0);
  65
  66   memcpy ((caddr_t) &key->prefix + key->prefixlen / 8,
  67           (caddr_t) value, len);
  68   key->family = AF_INET6;
  69   key->prefixlen += len * 8;
  70 }
  71
  72 #ifndef NDEBUG
  73 static void
  74 _lsdb_count_assert (struct ospf6_lsdb *lsdb)
  75 {
  76   struct ospf6_lsa *debug;
  77   int num = 0;
  78   for (debug = ospf6_lsdb_head (lsdb); debug;
  79        debug = ospf6_lsdb_next (debug))
  80     num++;
  81
  82   if (num == lsdb->count)
  83     return;
  84
  85   if (IS_OSPF6_DEBUG_LSA (DATABASE))
  86     {
  87       zlog_info ("PANIC !! lsdb[%p]->count = %d, real = %d",
  88                  lsdb, lsdb->count, num);
  89       for (debug = ospf6_lsdb_head (lsdb); debug;
  90            debug = ospf6_lsdb_next (debug))
  91         zlog_info ("%p %p %s", debug->prev, debug->next, debug->name);
  92       zlog_info ("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
 178             {
 179               if (lsdb->hook_remove)
 180                 (*lsdb->hook_remove) (old);
 181               if (lsdb->hook_add)
 182                 (*lsdb->hook_add) (lsa);
 183             }
 184         }
 185     }
 186   else if (OSPF6_LSA_IS_MAXAGE (lsa))
 187     {
 188       if (lsdb->hook_remove)
 189         (*lsdb->hook_remove) (lsa);
 190     }
 191   else
 192     {
 193       if (lsdb->hook_add)
 194         (*lsdb->hook_add) (lsa);
 195     }
 196
 197   if (old)
 198     ospf6_lsa_unlock (old);
 199
 200   ospf6_lsdb_count_assert (lsdb);
 201 }
 202
 203 void
 204 ospf6_lsdb_remove (struct ospf6_lsa *lsa, struct ospf6_lsdb *lsdb)
 205 {
 206   struct route_node *node;
 207   struct prefix_ipv6 key;
 208
 209   memset (&key, 0, sizeof (key));
 210   ospf6_lsdb_set_key (&key, &lsa->header->type, sizeof (lsa->header->type));
 211   ospf6_lsdb_set_key (&key, &lsa->header->adv_router,
 212                       sizeof (lsa->header->adv_router));
 213   ospf6_lsdb_set_key (&key, &lsa->header->id, sizeof (lsa->header->id));
 214
 215   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
 216   assert (node && node->info == lsa);
 217
 218   if (lsa->prev)
 219     lsa->prev->next = lsa->next;
 220   if (lsa->next)
 221     lsa->next->prev = lsa->prev;
 222
 223   node->info = NULL;
 224   lsdb->count--;
 225
 226   if (lsdb->hook_remove)
 227     (*lsdb->hook_remove) (lsa);
 228
 229   ospf6_lsa_unlock (lsa);
 230   route_unlock_node (node);
 231   ospf6_lsdb_count_assert (lsdb);
 232 }
 233
 234 struct ospf6_lsa *
 235 ospf6_lsdb_lookup (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 236                    struct ospf6_lsdb *lsdb)
 237 {
 238   struct route_node *node;
 239   struct prefix_ipv6 key;
 240
 241   if (lsdb == NULL)
 242     return NULL;
 243
 244   memset (&key, 0, sizeof (key));
 245   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 246   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 247   ospf6_lsdb_set_key (&key, &id, sizeof (id));
 248
 249   node = route_node_lookup (lsdb->table, (struct prefix *) &key);
 250   if (node == NULL || node->info == NULL)
 251     return NULL;
 252   return (struct ospf6_lsa *) node->info;
 253 }
 254
 255 /* Iteration function */
 256 struct ospf6_lsa *
 257 ospf6_lsdb_head (struct ospf6_lsdb *lsdb)
 258 {
 259   struct route_node *node;
 260
 261   node = route_top (lsdb->table);
 262   if (node == NULL)
 263     return NULL;
 264
 265   /* skip to the existing lsdb entry */
 266   while (node && node->info == NULL)
 267     node = route_next (node);
 268   if (node == NULL)
 269     return NULL;
 270
 271   route_unlock_node (node);
 272   if (node->info)
 273     ospf6_lsa_lock ((struct ospf6_lsa *) node->info);
 274   return (struct ospf6_lsa *) node->info;
 275 }
 276
 277 struct ospf6_lsa *
 278 ospf6_lsdb_next (struct ospf6_lsa *lsa)
 279 {
 280   struct ospf6_lsa *next = lsa->next;
 281
 282   ospf6_lsa_unlock (lsa);
 283   if (next)
 284     ospf6_lsa_lock (next);
 285
 286   return next;
 287 }
 288
 289 /* Macro version of check_bit (). */
 290 #define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1)
 291
 292 struct ospf6_lsa *
 293 ospf6_lsdb_type_router_head (u_int16_t type, u_int32_t adv_router,
 294                              struct ospf6_lsdb *lsdb)
 295 {
 296   struct route_node *node;
 297   struct prefix_ipv6 key;
 298   struct ospf6_lsa *lsa;
 299
 300   memset (&key, 0, sizeof (key));
 301   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 302   ospf6_lsdb_set_key (&key, &adv_router, sizeof (adv_router));
 303
 304   node = lsdb->table->top;
 305
 306   /* Walk down tree. */
 307   while (node && node->p.prefixlen <= key.prefixlen &&
 308          prefix_match (&node->p, (struct prefix *) &key))
 309     node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
 310
 311   if (node)
 312     route_lock_node (node);
 313   while (node && node->info == NULL)
 314     node = route_next (node);
 315
 316   if (node == NULL)
 317     return NULL;
 318   else
 319     route_unlock_node (node);
 320
 321   if (! prefix_match ((struct prefix *) &key, &node->p))
 322     return NULL;
 323
 324   lsa = node->info;
 325   ospf6_lsa_lock (lsa);
 326
 327   return lsa;
 328 }
 329
 330 struct ospf6_lsa *
 331 ospf6_lsdb_type_router_next (u_int16_t type, u_int32_t adv_router,
 332                              struct ospf6_lsa *lsa)
 333 {
 334   struct ospf6_lsa *next = lsa->next;
 335
 336   if (next)
 337     {
 338       if (next->header->type != type ||
 339           next->header->adv_router != adv_router)
 340         next = NULL;
 341     }
 342
 343   if (next)
 344     ospf6_lsa_lock (next);
 345   ospf6_lsa_unlock (lsa);
 346   return next;
 347 }
 348
 349 struct ospf6_lsa *
 350 ospf6_lsdb_type_head (u_int16_t type, struct ospf6_lsdb *lsdb)
 351 {
 352   struct route_node *node;
 353   struct prefix_ipv6 key;
 354   struct ospf6_lsa *lsa;
 355
 356   memset (&key, 0, sizeof (key));
 357   ospf6_lsdb_set_key (&key, &type, sizeof (type));
 358
 359   /* Walk down tree. */
 360   node = lsdb->table->top;
 361   while (node && node->p.prefixlen <= key.prefixlen &&
 362          prefix_match (&node->p, (struct prefix *) &key))
 363     node = node->link[CHECK_BIT(&key.prefix, node->p.prefixlen)];
 364
 365   if (node)
 366     route_lock_node (node);
 367   while (node && node->info == NULL)
 368     node = route_next (node);
 369
 370   if (node == NULL)
 371     return NULL;
 372   else
 373     route_unlock_node (node);
 374
 375   if (! prefix_match ((struct prefix *) &key, &node->p))
 376     return NULL;
 377
 378   lsa = node->info;
 379   ospf6_lsa_lock (lsa);
 380
 381   return lsa;
 382 }
 383
 384 struct ospf6_lsa *
 385 ospf6_lsdb_type_next (u_int16_t type, struct ospf6_lsa *lsa)
 386 {
 387   struct ospf6_lsa *next = lsa->next;
 388
 389   if (next)
 390     {
 391       if (next->header->type != type)
 392         next = NULL;
 393     }
 394
 395   if (next)
 396     ospf6_lsa_lock (next);
 397   ospf6_lsa_unlock (lsa);
 398   return next;
 399 }
 400
 401 void
 402 ospf6_lsdb_remove_all (struct ospf6_lsdb *lsdb)
 403 {
 404   struct ospf6_lsa *lsa;
 405   for (lsa = ospf6_lsdb_head (lsdb); lsa; lsa = ospf6_lsdb_next (lsa))
 406     ospf6_lsdb_remove (lsa, lsdb);
 407 }
 408
 409 void
 410 ospf6_lsdb_show (struct vty *vty, int level,
 411                  u_int16_t *type, u_int32_t *id, u_int32_t *adv_router,
 412                  struct ospf6_lsdb *lsdb)
 413 {
 414   struct ospf6_lsa *lsa;
 415   void (*showfunc) (struct vty *, struct ospf6_lsa *) = NULL;
 416
 417   if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 418     showfunc = ospf6_lsa_show_summary;
 419   else if (level == OSPF6_LSDB_SHOW_LEVEL_DETAIL)
 420     showfunc = ospf6_lsa_show;
 421   else if (level == OSPF6_LSDB_SHOW_LEVEL_INTERNAL)
 422     showfunc = ospf6_lsa_show_internal;
 423   else if (level == OSPF6_LSDB_SHOW_LEVEL_DUMP)
 424     showfunc = ospf6_lsa_show_dump;
 425
 426   if (type && id && adv_router)
 427     {
 428       lsa = ospf6_lsdb_lookup (*type, *id, *adv_router, lsdb);
 429       if (lsa)
 430         {
 431           if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 432             ospf6_lsa_show (vty, lsa);
 433           else
 434             (*showfunc) (vty, lsa);
 435         }
 436       return;
 437     }
 438
 439   if (level == OSPF6_LSDB_SHOW_LEVEL_NORMAL)
 440     ospf6_lsa_show_summary_header (vty);
 441
 442   if (type && adv_router)
 443     lsa = ospf6_lsdb_type_router_head (*type, *adv_router, lsdb);
 444   else if (type)
 445     lsa = ospf6_lsdb_type_head (*type, lsdb);
 446   else
 447     lsa = ospf6_lsdb_head (lsdb);
 448   while (lsa)
 449     {
 450       if ((! adv_router || lsa->header->adv_router == *adv_router) &&
 451           (! id || lsa->header->id == *id))
 452         (*showfunc) (vty, lsa);
 453
 454       if (type && adv_router)
 455         lsa = ospf6_lsdb_type_router_next (*type, *adv_router, lsa);
 456       else if (type)
 457         lsa = ospf6_lsdb_type_next (*type, lsa);
 458       else
 459         lsa = ospf6_lsdb_next (lsa);
 460     }
 461 }
 462
 463 /* Decide new Link State ID to originate.
 464    note return value is network byte order */
 465 u_int32_t
 466 ospf6_new_ls_id (u_int16_t type, u_int32_t adv_router,
 467                  struct ospf6_lsdb *lsdb)
 468 {
 469   struct ospf6_lsa *lsa;
 470   u_int32_t id = 1;
 471
 472   for (lsa = ospf6_lsdb_type_router_head (type, adv_router, lsdb); lsa;
 473        lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
 474     {
 475       if (ntohl (lsa->header->id) < id)
 476         continue;
 477       if (ntohl (lsa->header->id) > id)
 478         return ((u_int32_t) htonl (id));
 479       id++;
 480     }
 481
 482   return ((u_int32_t) htonl (id));
 483 }
 484
 485 /* Decide new LS sequence number to originate.
 486    note return value is network byte order */
 487 u_int32_t
 488 ospf6_new_ls_seqnum (u_int16_t type, u_int32_t id, u_int32_t adv_router,
 489                      struct ospf6_lsdb *lsdb)
 490 {
 491   struct ospf6_lsa *lsa;
 492   signed long seqnum = 0;
 493
 494   /* if current database copy not found, return InitialSequenceNumber */
 495   lsa = ospf6_lsdb_lookup (type, id, adv_router, lsdb);
 496   if (lsa == NULL)
 497     seqnum = INITIAL_SEQUENCE_NUMBER;
 498   else
 499     seqnum = (signed long) ntohl (lsa->header->seqnum) + 1;
 500
 501   return ((u_int32_t) htonl (seqnum));
 502 }
 503
 504